minbool.m

this is for demo in matlab

function result = minBool(numbers, resulttype)
% minBool - Quine-McCluskey method for boolean function minimization
%
% R = minBool( N, V )
%
% R - result matrix
% N - input arguments. N should be vector with integers
% V - visualization type
%     1) 1=normal; -1=inverse; NaN = not used
%     2) 1=normal; -1=inverse; 0   = not used
%
% Example
% R = minBool([5 13 14 26 30],1)
% R =
%    1     2     3     4     5
%   -1   NaN     1    -1     1
%  NaN     1     1     1    -1
%    1     1   NaN     1    -1
%
% minBool ver. 1.3    release: Sept 2002     Last update: 24 Feb 2007

% Copyright 2002-2007     Andrey Popov     [e-mail]


%% Input arguments check
if (nargin==0)
    error('minBool:noinput','No input data');
end

% The input argument is integer numbers, so the minimization is
% independant on the size of the boolean variables, i.e. we are not
% interested whether the real boolean variables are represented with 3 or
% 30 bits

numbers = round(abs(numbers));
v = size(numbers,2);
numbers = numbers(:);

%% Remove repeated input numbers ------------------------------------------
S = numbers(1);
for g = 2:v
    if ~any(S == numbers(g))
        S = [S numbers(g)];
    end
end

numbers = sort(S);
v = length(numbers);

% Determine the number of involved boolean variables
n = max(1,ceil(log2(max(numbers)+1)));

% Create empty disjunction matrix s
W = zeros(v,n);

%% Convert the input numbers to binary ------------------------------------
for i = 1:v % cycle over the numbers
    k = numbers(i);
    for j = 1:n % cycle over the bits
        p = 2^(n-j);
        if  k >= p
            k = k - p;
            W(i,j) = 1;
        end
    end
end

%% Arange the numbers according to the number of '1' they have ------------
w1 = [1:v; sum(W,2)'];   % [no; num 1's]
w1 = sortrows(w1',2);    % sort by num 1's
w = w1(:,1);
G = [W(w,:) numbers(w)'];% arrange by num 1's

%% Joining the numbers close in a boolean sence ---------------------------
extend=1;		%
stitched=1;		% to be able to enter 'while'

if v == 1
    F = G;
else
    while (stitched~=0)
        F = [];
        stitched = 0;

        G = [G zeros(v,1)];
        ncomb = 0;

        for i=1:v                   % loop over all combinations
            if ~isinf(G(i,1))
                % Inf on first position can appearonly if we have 2
                % combinations which are identical. Since this is covered
                % for the initial input variables, such case can only
                % occure after combining several variables and having
                % invariant bits.
                joined=0;
                
                for j=(i+1):v		% compare with all other combinations
                    if ~isinf(G(j,1)) % allowed
                        k = sum(abs(G(i,1:n)-G(j,1:n)));
                        if k == 1   % difference by exactely 1 bit
                            L = G(i,1:(n+extend));	% copy the combination
                            p = find(G(i,1:n)-G(j,1:n)); % find the differing bit
                            L(1,p) = -1;			% mark it with -1
                            L = [L G(j,(n+1):(n+extend))]; % add the other combination
                            F = [F; L];             % store in the pass matrix F
                            ncomb = ncomb + 1;
                            stitched = stitched + 1;% mark that there was stictch
                            joined = joined + 1; %
                            G(i,n+extend+1) = 1; % mark the combinations as used
                            G(j,n+extend+1) = 1;
                        elseif k == 0 % could be only by 2 identical combinations
                                      % at later stage of stitching
                            G(j,1)=inf;
                        end
                    end
                end

                if joined == 0 && G(i,n+extend+1) == 0
                    % the current combination cannot be joined with any
                    % other
                    L = G(i,1:(n+extend));
                    L = [L Inf*ones(1,extend)];
                    F = [F; L];
                    ncomb = ncomb + 1;	% however this is a combination
                end
            end
        end % end of the cycle over the combinations

        if stitched == 0	% not a single combination pare found
            F = F(:,1:(n+extend));	% this removes the extra combination columns
        else
            extend = 2*extend; % the number of spaces to mark combinations is doubled
        end

        G = F; % not the combinations are written again in G

        v = ncomb;
    end
end % end of the while cycle


%% Create the table -------------------------------------------------------
%  extend - max number of the involved input variables in the output
%  n - number of boolean variables
%  v - number of derived combinations
%  y - number input combinations
y = length(numbers);

E = zeros(v+2,y+3);			% create empty table of the form
%  0 0 0 i i i i i i i   		i