CODEWITHSUNDEEP
matlab
Maryam
Maryam

Reputation: 13

Binary vectors multiplication

I am designing a multiplier in MATLAB but not sure how to perform binary numbers multiplication. For example i want to multiply binary 110011 with binary 0011. But MATLAB gives an error of matrix dimensios. Also, if i append zeros in the MSBs of smaller element number, it still won't allow me to multiply. Is there any specific algorithm that i am missing?

I don't want to do bit-wise AND. I need to perform proper multiplication as,

          1 1 0 0 1 1
              0 0 1 1

          1 1 0 0 1 1
        1 1 0 0 1 1
      0 0 0 0 0 0
  0 0 0 0 0 0

  0 0 1 0 0 1 1 0 0 1

here is the code piece where i append zeros. 

if numel(operand1)<numel(operand2)
append=zeros(1, (numel(operand2)-numel(operand1)));
operand1=[operand1 append];
else
append=zeros(1, (numel(operand1)-numel(operand2)));
operand2=[operand2 append];
end

(PS: Sorry for poor readability, this is my very first post on stackoverflow, i don't know much about formatting)

Upvotes: 1

Views: 673

Answers (1)

Hoki
Hoki

Reputation: 11792

This is just one possible implementation out of many. It is not meant to be the fastest and brightest. It could also be shortened heavily but for the sake of showing the intermediate steps I left it quite expanded.

Step 1 : prepare all the steps (lines)

Instead of having to manage appending zeros here or there depending on the length of each input, I find it simpler to simply define a matrix large enough to accomodate all our values and the circular shifts we'll have to perform:

%% Input values
a = [ 1 1 0 0 1 1 ] ;
b = [     1 0 1 1 ] ;

%% create all the steps
nstep = numel(b) ;
steps = bsxfun( @times , flipud(b.') , a) ;

At this stage, your matrix steps looks like:

>> steps
steps =
     1     1     0     0     1     1
     1     1     0     0     1     1
     0     0     0     0     0     0
     1     1     0     0     1     1

Each line represent the full vector a multiplied by each element of b Before we can sum these lines, we need to shift each line so it is aligned with its proper power of 2. For that we'll first pad the matrix with the necessary zeros on the left, then we'll use circshift:

%% pad the matrix to prepare for the shifts
pad = zeros( nstep , nstep ) ;
mat = [pad steps] ;

%% shift the step lines
for k=2:nstep
    mat(k,:) = circshift(mat(k,:),[0,-(k-1)]) ; % shift each line to the left by [k-1]
end

By now, your matrix mat looks like:

>> mat
mat =
     0     0     0     0     1     1     0     0     1     1
     0     0     0     1     1     0     0     1     1     0
     0     0     0     0     0     0     0     0     0     0
     0     1     1     0     0     1     1     0     0     0

Almost there, now we just need to sum the lines to get our result. Unfortunately, MATLAB does not have binary summation built in that way so we'll have to implement it ourselves. I'll give 2 methods, a loop version (more readable), and a vectorised version (more crytic).

Step 2 : Summation

%% [LOOP method] Do the summation
ncol = size(mat,2) ;
res  = zeros( 1 , ncol ) ;  % pre-allocate result line
sumline = sum(mat) ;        % put sum of each column in a buffer

c = 0 ; % carry
for k=ncol:-1:2             % we process the column from right to left
    s      = sumline(k)+c ; % sum of the column [k] plus the carry
    res(k) = mod( s , 2 ) ; % result for this column
    c = floor(s/2)        ; % carry value for the next column
end
% now we are almost finished but there may be value left in the carry
res(1) = c  % set the (MSb) on the left

Notice that the loop stops at column 2 instead of column 1. This is because I already added one more column to the left, which will contain only zeros. This is done so the res variable has enough columns to accomodate the carry in case it is not null.

Below is a more compact version (of step 2), but it will give strictly the same results:

%% [Vectorised method] ... just as good but more cryptic
sumline  = sum(mat) ;                                   % put sum of each column in a buffer
carrytmp = floor(sumline/2) ;                           % calculate all the "carry" values (1/2)
carry    = carrytmp + circshift( carrytmp, [0,-1] ) ;   % calculate all the "carry" values (2/2)
tsum     = sumline + circshift( carry , [0,-1] ) ;      % total sum
res      = mod( tsum , 2 ) ;                            % final result

There you go, sorry for the long post but I wanted to detail the steps. If you take only the code you can compact it into a short function:

function res = binary_multiplication(a,b)

nstep = numel(b) ;
mat   = [zeros( nstep , nstep ) , bsxfun( @times , flipud(b.') , a) ] ;
for k=2:nstep
    mat(k,:) = circshift(mat(k,:),[0,-(k-1)]) ;
end
sumline  = sum(mat) ;
res      = mod(sumline+circshift(floor(sumline/2)+circshift(floor(sumline/2),[0,-1]),[0,-1]),2) ;

Upvotes: 1

Related Questions