二元向量乘法

Question

我在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上的第一篇文章，我对格式化知之甚少）

Answer 1

这只是众多可能的实现之一。它并不意味着是最快和最聪明的。它也可以大大缩短，但为了显示中间步骤，我把它放大了。

第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变量有足够的列来容纳进位，以防它不为空。

下面是一个更紧凑的版本（步骤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) ;