hi guys... I WILL RAISE THE POINTS TO 5000 - 9000 ( THAT\'S ALL I HAVE) PLEASE H
ID: 3547074 • Letter: H
Question
hi guys... I WILL RAISE THE POINTS TO 5000 - 9000 ( THAT'S ALL I HAVE) PLEASE HELP.....!!!
can anyone give me a Matlab code for Quine-McCluskey algorithm, with following specifications:
1: input is n numbers ( each of m bits) in the product form.
2: inputs are given as: 010 for x'yz', 100 for xy'z' ....here it's 3bits..you have to generalise for m bits/
3 you have to show all prime implicants and essential prime implicant and then the simplified sum of product form.
4. again outputs are like 1010 for xy'zw' etc.
I hope you understand the problem.
I WILL RAISE THE POINTS TO 5000 - 9000 ( THAT'S ALL I HAVE) PLEASE HELP.....!!!
Explanation / Answer
%function [Bins,inps,Nums,tt] = minTruthtable(tt, verify)
% Function to minimize a truth table using the Quine-McCluskey algorithm.
% * tt = truth table, as character (filled with '0's, '-'s or '1's). E.g. '00011-10'.
% tt must not be more than 2^15 long, due to an int16 optimization.
% * verify = if set and non-zero, perform some self-check of the result.
% * inps = number of logical gates input for a minimal nand-nand-synthesis of tt. E.g. 7
% * ott = output truth table, as character, filled with '0's and '1'. E.g. tt='00011010'
% * Bins = character matrix. E.g. ['1-0'; '011'] (meaning => x2*/x0 + /x2*x1*x0).
% * Nums = cell array with arrays indicating which terms contains which '1's in the tt.
% (0-indexed, so '1001' => [0 3]. E.g. {[4 6], [3]}.
%
% Example:
% # >> minTruthtable('0-11--10110010--')
% # | All terms:
% # | * T( 1): "001-" <-> {2 3}
% # | * T( 2): "100-" <-> {8 9}
% # | * T( 3): "-1-0" <-> {6 4 12 14}
% # | y = ~x(3)*~x(2)*x(1) + x(3)*~x(2)*~x(1) + x(2)*~x(0);
% # |
% # | Logical complexity: 11 inputs
% # |
% # | Input tt: '0-11--10110010--'
% # | Output tt: '0011101011001010'
% # >> [Bins,inps,Nums,tt] = minTruthtable('0-11--10110010--');
% -> Bins = ['001-'; '100-'; '-1-0']
% -> inps = 11
% -> Nums = {[2 3]; [8 9]; [6 4 12 14]}
% -> tt = '0011101011001010'
%
function [Bins,inps,Nums,ott] = minTruthtable(tt, verify)
% Step description: http://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm
%% Initial setup
if nargin < 1
% Use a test vector if nothing was given.
tt = '0000100-1-1110-1'; % m(4,8,10,11,12,15) + d(7,9,14)
verify = true;
% Kmap: 0 1 3 2 <- x10
% / 0 0 0 0 0
% x32 1 1 0 - 0 Sol: x2*/x1*/x0 + x3*/x2 + x3*/x0 + x3*x1
% | 3 1 0 1 -
% 2 1 - 1 1
% This test vector will be used as example in the code.
end
if 0 < nargin && nargin < 2, verify = false; end
if ~ischar(tt)
if islogical(tt)
tt = char('0'+tt);
elseif isfloat(tt)
tt2 = char('-'+zero(size(tt)));
tt2(tt==0) = '0';
tt2(tt==1) = '1';
tt = tt2;
else
error('minTruthtable:tt_type', 'tt should be a character array. tt is of type %s.', class(tt))
end
end
if size(tt,2) == 1, tt = tt'; end
assert(size(tt,1) == 1, 'minTruthtable:multi_output', 'Error in minTruthtable: tt must be a vector.');
N = round(log2(size(tt,2)));
assert(size(tt,2) == 2^N, 'minTruthtable:tt_size_mismatch', 'Error in minTruthtable: tt has height %d, which is not a power of two.', size(tt,1));
assert(all(tt=='-' | tt=='0' | tt=='1'), 'minTruthtable:tt_char', 'Error in minTruthtable: Unexpected character in tt');
% N: Number of variables
% *On*: everything that has to do with '1' in the truth table
% *Dc*: everything that has to do with '-' in the truth table
% n*: count variable of *
% An "atomic" term: Like a '1' in the Kmap
% A term: Like a "ring" in the Kmap
Ons = find(tt=='1'); % '1's. Ex: [4 8 10 11 12 15] + 1
Dcs = find(tt=='-'); % '-'s. Ex: [7 9 14] + 1
nOn = length(Ons);
nDc = length(Dcs);
%% Step 1: Generate product terms
% Variables used in the loop:
% Each row in those stands for a product term. Initially atomic terms.
% - Bins*: binary (char) representations of the terms. Ex: x3*/x0 = '1--0'
% - Covs*: true iff the term does not have to be included (again). Cov = Covered (or don't care at input).
% - Nums*: vector with all atomic terms included in the term. Ex: '-100' => [4 12]
% - Dons*: position of all '-' as int. Eg. Bins='-1-0' => Dons=[1 0 1 0]*[8;4;2;1] = 10
% Dons=-1 => This is a double and should be ignored.
% - Ones*: position of all '1' as int. Eg. Bins='-1-0' => Dons=[0 1 0 0]*[8;4;2;1] = 4
% - nVars*: Number of rows.
% - *1: Input to each iteration.
% - *2: Output from each iteration, used as input to the next iteration.
% - *3: Output totally (filled in during each iteration).
% - n: iteration index. 1,2,...,N (will most likely stop before N).
Bins1 = [dec2bin(Ons-1,N); dec2bin(Dcs-1,N)]; % width = N
Covs1 = [false(nOn,1); true(nDc,1)]; % width = 1
Nums1 = [Ons'-1; Dcs'-1]; % width = 2^(n-1) in each iteration
nVars1 = size(Bins1,1);
twoexp = 2.^(N-1:-1:0)'; % coeff to calculate Dons, [8;4;2;1]
MINC = 100; % matrix increase size: Larger => faster for big tt, Smaller => slower for very big tt's.
BinsNew = char('X'*ones(MINC,N)); % To prealloc an "empty" matrix (use 'X' for debug purpose)
Bins2 = BinsNew;
Covs2 = false(MINC,1);
Nums2 = int16(-ones(MINC,1));
% nVars2 initiated in each iteration.
Bins3 = BinsNew;
% Cov3 is not used, since we only move "uncovered" terms to *3.
Nums3 = cell(MINC,1); % The content will differ in size - this saves memory.
nVars3 = 0;
for n=1:N % Main iteration loop. Will break in the middle (unless tt = ones(2^N,1))
% If there is no terms to test, then we are done.
if ~nVars1, break; end
six = [find(~Covs1); find(Covs1)]; % Sort the variables so uncovered comes first
Bins1 = Bins1(six,:);
Covs1 = Covs1(six,:);
Nums1 = Nums1(six,:);
Dons1 = int16((Bins1 == '-')*twoexp); % '-1-0' => [1 0 1 0]*[8;4;2;1] = 10
Ones1 = uint16((Bins1 == '1')*twoexp); % '-1-0' => [0 1 0 0]*[8;4;2;1] = 4
Nums2 = [Nums2,Nums2]; % We will double the number of atomic terms each time
nVars2 = 0;
% What do we have here, in each iteration?
% n=1:
% *3 = empty
% Bins1 = [0100;1000;1010;1011;1100;1111;0111;1001;1110]
% Covs1 = [ 0; 0; 0; 0; 0; 0; 1; 1; 1]
% Nums1 = [ 4; 8; 10; 11; 12; 15; 7; 9; 14]
% Dons1 = [ 0; 0; 0; 0; 0; 0; 0; 0; 0]
% 4; 8; 10; 11; 12; 15; 7; 9; 14]
% n=2:
% *3 = empty 1 2 3 4 5 6 7 8 9 10* 11*
% Bins1 = [-100;10-0; 101-; 1-11;1-00;100-; 1-10;10-1; 11-0;-111; 111-]
% Covs1 = [ 0; 0; 0; 0; 1; 1; 1; 1; 1; 1; 1]
% Nums1 = [4,12;8,10;10,11;11,15;8,12; 8,9;10,14;9,11;12,14;7,15;14,15]
% Dons1 = [ 8; 2; 1; 4; 4; 1; 4; 2; 2; 8; 1]
% 4; 8; 10; 11; 8; 8; 10; 9; 12; 7; 14]
% n=3:
% Bins3 = [ -100]
% Nums3 = {[4,12]} 1 2 3 4 5 6
% Bins1 = [ 10--; 10--; 1-1-; 1--0; 1-1-; 1--0]
% Covs1 = [ 0; 0; 0; 1; 1; 1]
% Nums1 = [8,9,10,11;8,9,10,11;10,11,14,15;8,10,12,14;10,11,14,15;8,10,12,14]
% Dons1 = [ 3; 3; 5; 6: 5; 6]
% Dons1 = [ 8; 8; 10; 8: 10; 8]
% n=4 (before breaking due to ~nVars1):
% *1 = empty
% Bins3 = [ -100; 10--; 1-1-]
% Nums3 = {[4,12];[8,9,10,11];[10,11,14,15]}
for ix0 = 1:nVars1-1
% All *10 is current row from *1.
Dons10 = Dons1(ix0);
if Dons10 < 0, continue; end
Bins10 = Bins1(ix0,:);
Covs10 = Covs1(ix0);
Nums10 = Nums1(ix0,:);
Ones10 = Ones1(ix0);
for ix1 = ix0+1:nVars1
if Dons10 ~= Dons1(ix1), continue; end % Also works if Dons(ix1) = -1
tmp = bitxor(Ones10,Ones1(ix1)); % binary version of Bins10 ~= Bins1(ix1,:)
if tmp > 0 && bitand(tmp, tmp-1) > 0, continue; end % if at most 1 bit => continue.
diffs = find(Bins10 ~= Bins1(ix1,:), 1); % find at most 1 pos. where they differs.
if ~isempty(diffs) % Bins1(ix0,:) and Bins1(ix1,:) differs in only one pos
nVars2 = nVars2 + 1;
if length(Covs2) < nVars2 % grow *2 with MINC at a time
Bins2 = [Bins2; BinsNew];
Covs2 = [Covs2; false(MINC,1)];
Nums2 = [Nums2; -ones(MINC,2^n)];
end
Bins2(nVars2,:) = Bins10;
Bins2(nVars2,diffs) = '-';
Covs2(nVars2) = false;%Covs10 & Covs1(ix1); % if both terms are covered, then this entire term is covered.
% The above function (Covs10 & Covs1(ix1)) gave problem. Better to let Step2 handle the coverage.
Nums2(nVars2,:) = [Nums10 Nums1(ix1,:)];
Covs1([ix0 ix1]) = true;
Covs10 = true;
else % Those are equal => "remove" the first one
Dons1(ix1) = -1; % indicate a duplicate
if ~Covs10, Covs1(ix1) = true; end % prohibit it from being moved to *3, if first one is
end
end
end
% Cover yet uncovered terms with *3: Uncovered *1 -> *3
ixUC1 = find(~Covs1); % Number index for UnCovered terms
if ~isempty(ixUC1)
ixUCRng3 = nVars3 + (1:length(ixUC1)); % UnCovered, as index range for *3
nVars3 = ixUCRng3(end);
Bins3(ixUCRng3,:) = Bins1(ixUC1,:);
Nums3(ixUCRng3) = num2cell(Nums1(ixUC1,:),2); % each row in Nums1 will be a cell element.
end
% Copy *2 -> *1: We don't want to test the already tested again, so only test the generated.
Bins1 = Bins2(1:nVars2,:);
Covs1 = Covs2(1:nVars2);
Nums1 = Nums2(1:nVars2,:);
nVars1 = nVars2;
end
if nVars1 > 0 % This can happend iff there are no '0' in tt.
ixUCRng3 = nVars3 + (1:nVars1); % UnCovered, as index range for *3
nVars3 = ixUCRng3(end);
Bins3(ixUCRng3,:) = Bins1;
Nums3(ixUCRng3) = num2cell(Nums1,2); % each row in Nums1 will be a cell element.
end
% Remove all no longer needed variables
clear *1 *10 *2 ix* BinsNew Dcs MINC diffs n nDc nOn Ons six twoexp
% Okay, what do we give to the next step? We give:
% - Bins3: char-binary representation of the terms. E.g. [ -100 ; 10-- ; 1-1- ]
% - Nums3: cell array containing vectors E.g. {[4,12]; [8,9,10,11]; [10,11,14,15]}
% with covered atomic terms.
% - nVars3: integer counting terms. E.g. 3
% - tt: original truth table (char). E.g. '0000100-1-1110-1'
% - N: number of boolean variables (tt = 2^N long) E.g. 4
%% Step 2: Reduce terms covered by other terms.
% List which atomic terms are covered by which term
A = false(nVars3,2^N); % tt = '0000100-1-1110-1'
for i = 1:nVars3 % A = [0000100000001000
A(i,Nums3{i}+1) = true; % 0000000011110000
end % 0000000000110011] after the loop
vcnt = sum(A,1); % count = [0000100011221011]. % vertical count of A.
if verify
% Check that no tt=='0' are covered, and all tt=='1' are covered.
% This should never happend, independent of user input.
% ("UNEXPECTED ERROR: ..." means there an error in the script.)
assert(all(vcnt(tt=='0') == 0), 'minTruthtable:zero_covered', 'UNEXPECTED ERROR: A ''0'' is covered.');
assert(all(vcnt(tt=='1') >= 1), 'minTruthtable:ones_uncovered', 'UNEXPECTED ERROR: A ''1'' is not covered.');
end
% Remove from count and A all columns but thous with '1' in tt
ttEq1 = tt=='1';
A = A(:,ttEq1);
vcnt = vcnt(:,ttEq1);
% Detect all "Essential" prime implicant (that are alone on an atomic term).
vars3 = (1:nVars3)'; % pointers of all *3 variables, used to index rows in A.
vars4 = zeros(0,1); % pointers of all *4 variables (points to rows in *3).
vcntEq1 = find(vcnt==1);
for c = vcntEq1(end:-1:1); % look from right, to not "destroy" the index.
if vcnt(c) == 1
r = find(A(vars3,c),1); % which row (in vars3) contains the "true"?
% r points at an essential term -> move this to *4
vcnt(A(vars3(r),:)) = 0; % Remove column by setting to count to 0.
vars4 = [vars4; vars3(r)]; % Add row to *4
vars3 = vars3([1:r-1,r+1:end]); % Remove row from *3
end
end
% If there happens to be any non-essential terms (rows left), just pick the biggest first.
% This cannot guarantee the best solution.
cntDC = sum(Bins3(1:nVars3,:) == '-',2); % Number of '-' for each prod term.
while any(vcnt > 0)
% Remove the "removed" columns for real. Keep the row index for simplicity.
A = A(:,vcnt > 0);
vcnt = vcnt(vcnt > 0);
hcnt = sum(A(vars3,:),2); % Count used number of ones (indexing vars3)
% Remove all terms that are by now covered by others.
vars3 = vars3(hcnt > 0); % Keep rows that can contribute.
hcnt = hcnt(hcnt > 0); % Update...
%ccnt = A(vars3,:)*vcnt'; % Cover Count. ccnt(3) = how many '1' in A that will be removed if vars3(3) is selected.
cntDC2 = cntDC(vars3); % Count the number of '-' (indexing vars3)
% Using count2 <=> smaller AND gates. Using count3 <=> fewer AND gates <=> smaller OR gate.
[~,r] = max(hcnt*N+cntDC2); % r = the vars3 index corresponding to biggest term, in some sence
vcnt(A(vars3(r),:)) = 0; % Remove column by setting to count to 0.
vars4 = [vars4; vars3(r)]; % Add row to *4.
vars3 = vars3([1:r-1,r+1:end]); % Remove row from *3.
end
vars4 = sort(vars4);
clear A c vcnt count2 countEq1 i ixs nVars3 r ttEq1 vars3
% Okay, to the next step we leave:
% - Bins3: (same as before). E.g. [ -100 ; 10-- ; 1-1- ]
% - Nums3: (same as before). E.g. {[4,12]; [8,9,10,11]; [10,11,14,15]}
% - vars4: Index to the rows in Bins3. E.g. [1;2;3]
%% Step 3: Finalize.
Bins = Bins3(vars4,:);
Nums = Nums3(vars4);
inps = sum(Bins ~= '-', 2);
inps = sum(inps .* (inps > 1),1) + length(inps)*(length(inps)>1);
if nargout >= 4 || verify || nargout == 0 % calculate tt (out)
ott = char('0'*ones(1,2^N));
for i = 1:length(Nums)
ott(Nums{i}+1) = '1';
end
if verify
assert(all(ott(tt=='0') == '0'), 'minTruthtable:0_to_1', 'UNEXPECTED ERROR: A ''0'' become a ''1''.');
assert(all(ott(tt=='1') == '1'), 'minTruthtable:1_to_0', 'UNEXPECTED ERROR: A ''1'' became a ''0''.');
% Extra verification that Bins <=> Nums. Uncomment this if you suspect that the result is not correct.
for i=1:size(Bins,1)
Binsi = Bins(i,:);
Zerosi = find(Binsi == '0');
Onesi = find(Binsi == '1');
Donsi = find(Binsi == '-');
assert(length(Zerosi)+length(Onesi)+length(Donsi) == N, 'minTruthtable:CharInBins', 'UNEXPECTED ERROR: Unexpected character in Bins.');
Numsi = sum(2.^(N-Onesi));
for j=1:length(Donsi)
Numsi = [Numsi (Numsi+2^(N-Donsi(j)))];
end
assert(length(Numsi) == length(Nums{i}), 'minTruthtable:LenNums_vs_Dons', 'UNEXPECTED ERROR: Length(Nums{%d}) ~= 2^(#-=%d).', i, length(Donsi));
assert(all(sort(Numsi) == sort(Nums{i})), 'minTruthtable:Nums_vs_Dons', 'UNEXPECTED ERROR: Nums{%d} ~= Bins(%d,:).', i, i);
end
end
end
%% If no output required: Print result
if nargout == 0
fprintf('| All terms: ');
for i=1:size(Bins,1)
fprintf('| * T(%2d): "%s" <-> {', i,Bins(i,:))
Tnums = Nums{i};
if ~isempty(Tnums)
fprintf('%d', Tnums(1));
fprintf(' %d', Tnums(2:end));
end
fprintf('} ');
end
if verify
fprintf('| Relation "<->" has been verified ');
end
fprintf('| y = ');
ors = ''; % or-string, will change to ' + '
for i=1:size(Bins,1)
fprintf('%s',ors);
ors = ' + ';
ands = ''; % and-string, will change to '*'
for j=1:size(Bins,2)
x = size(Bins,2) - j;
if Bins(i,j) == '0', fprintf('%s~x(%d)',ands,x); ands = '*';
elseif Bins(i,j) == '1', fprintf('%sx(%d)',ands,x); ands = '*';
end
end
if all(Bins(i,:) == '-'), fprintf('1'); end
end
if size(Bins,1) == 0, fprintf('0'); end
fprintf('; | ');
fprintf('| Logical complexity: %d inputs ', inps);
fprintf('| ');
fprintf('| Input tt: ''%s'' ', tt);
fprintf('| Output tt: ''%s'' ', ott);
clear Bins Nums inps ott
end
end
%% TODOs:
% * Rewrite the second part of step 2, so it will guarantee optimality.
% * Rewrite so the function can take several truth tables (a truth matrix), and co-optimize it.
% - Suggested way: Run Step1 for each tt, and optimization shared logic in step 2.
% * Major change: Rewrite so 0 <= tt(i) <= 1, where tt(i) is double.
% Then minimize cost = inps + sum(abs(tt - ott) / abs(1-ott-tt)).
% In this way, the user can say "try to make this to a '1', but don't wast too many inputs on it".
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.