Блог

Я разрабатываю множитель в MATLAB, но не уверен, как выполнять умножение двоичных чисел. Например, я хочу умножить двоичный файл 110011 на двоичный файл 0011. Но MATLAB выдает ошибку размеров матрицы. Кроме того, если я добавлю нули в MSB меньшего числа элементов, это все равно не позволит мне умножать. Есть ли какой-либо конкретный алгоритм, который мне не хватает?

Я не хочу делать побитовое И. Мне нужно выполнить правильное умножение как,

           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
  

вот фрагмент кода, в который я добавляю нули.

 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: Извините за плохую читаемость, это мой самый первый пост в stackoverflow, я мало что знаю о форматировании)

Это всего лишь одна возможная реализация из многих. Он не должен быть самым быстрым и ярким. Его также можно было бы сильно сократить, но ради показа промежуточных шагов я оставил его довольно расширенным.

Шаг 1: подготовьте все шаги (строки)

Вместо того, чтобы управлять добавлением нулей здесь или там в зависимости от длины каждого ввода, я считаю, что проще просто определить матрицу, достаточно большую, чтобы вместить все наши значения и циклические сдвиги, которые нам придется выполнять:

 %% 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) ;
  

На этом этапе ваша матрица steps выглядит следующим образом:

 >> 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
  

Каждая строка представляет полный вектор a , умноженный на каждый элемент b
, прежде чем мы сможем суммировать эти строки, нам нужно сдвинуть каждую строку, чтобы она была выровнена с соответствующей степенью 2 . Для этого мы сначала добавим в матрицу необходимые нули слева, затем мы будем использовать 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
  

К настоящему времени ваша матрица mat выглядит следующим образом:

 >> 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
  

Почти готово, теперь нам просто нужно суммировать строки, чтобы получить наш результат. К сожалению, в MATLAB нет встроенного двоичного суммирования, поэтому нам придется реализовать его самостоятельно. Я приведу 2 метода: циклическую версию (более читаемую) и векторизованную версию (более критичную).

Шаг 2: суммирование

 %% [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
  

Обратите внимание, что цикл останавливается на столбце 2 вместо столбца 1. Это потому, что я уже добавил еще один столбец слева, который будет содержать только нули. Это делается для того, чтобы res переменная имела достаточно столбцов для размещения переноса в случае, если оно не равно null.

Ниже приведена более компактная версия (шага 2), но она даст строго те же результаты:

 %% [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
  

Вот так, извините за длинный пост, но я хотел подробно описать шаги. Если вы берете только код, вы можете сжать его в короткую функцию:

 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) ;