原创 布思算法

高性能乘法器是现代微处理器中的重要部件,是实时图像处理和数字信号处理的核心. 同时乘法器也是微处理器数据处理的关键路径, 乘法器完成一次乘法操作的周期基本上决定了微处理器的主频. 因此人们对提高乘法器的性能进行了大量的研究.在这个研究过程中，布思算法便起到了很大的作用。

假设A为乘数，B为被乘数。

乘数A可表示为：
    A = - A[N-1] * 2^N-1 + A[N-2] * 2^N-2 + …… + A[1] * 2^1 + A[0] * 2^0 

则：
    D = A * B
      = (- A[N-1] * 2^N-1 + A[N-2] * 2^N-2 + …… + A[1] * 2^1 + A[0] * 2^0) * B 
      = - A[N-1] * B * 2^N-1 + A[N-2] * B * 2^N-2 + …… + A[1] * B * 2^1 + A[0] * B * 2^0

做变形，得

    A = - A[N-1] * 2^N-1 + A[N-2] * 2^N-2 + …… + A[1] * 2^1 + A[0] * 2^0
      = - A[N-1] * 2^N-1 + (2A[N-2] - A[N-2]) * 2^N-2 + (2A[N-3] - A[N-3]) * 2^N-3 + …… +
        (2A[2] - A[2]) * 2^2 + (2A[1] - A[1]) * 2^1 + (2A[0] - A[0]) * 2^0 
      = - A[N-1] * 2^N-1 + A[N-2] * 2^N-1 - A[N-2] * 2^N-2 + A[N-3] * 2^N-2 - A[N-3] * 2^N-3 + …… +
        A[2] * 2^3 - A[2] * 2^2 + A[1] * 2^2 - A[1] * 2^1 + A[0] * 2^1 - A[0] * 2^0
      = (- A[N-1] + A[N-2]) * 2^N-1 + (- A[N-2] + A[N-3]) * 2^N-2 + …… +
        (- A[2] + A[1]) * 2^2 + (- A[1] + A[0]) * 2^1 + (- A[0] + 0) * 2^0 
      =     Σ
n = 0,A[-1] = 0
N - 1
   ((- A[n] + A[n-1]) * 2^n) 
      =  Σ
n = 0
N - 1
(E * 2n) (3-5)
其中：
    E = - A[n] + A[n-1] (0 ≤ n ≤ (N-1) , A[-1] = 0) (3-6)
其值如下表所示：
A[n]     A[n-1]        E
0            0        - 0 + 0 = 0
0            1        - 0 + 1 = 1
1            0        - 1 + 0 = - 1
1            1        - 1 + 1 = - 0
则：
    D = A * B
      = ( Σ
n = 0
N - 1
(E * 2n)) * B (3-7)
      =  Σ
n = 0
N - 1
((E * B) * 2^n) 这就是布思算法！

它考虑本位及相邻低位，确定操作为加或减、运算量为0或B。总的编码项为N 项，乘积项（被乘数与由乘数所
得某一编码项值的乘积。此表达方式可能更具一般性！）为N项。
 

对无符号数乘法：
乘数A可表示为
    A = A[N-1] * 2^N-1 + A[N-2] * 2^N-2 + …… + A[1] * 2^1 + A[0] * 2^0       =  Σ
n = 0
N - 1
(A[n] * 2^n) )
则：
    D = A * B
      = ( Σ
n = 0
N - 1
(A[n] * 2^n)) * B       =  Σ
n = 0
N - 1
((A[n] * B) * 2^n) (3-12)
可见，式(3-8)、式(3-12)表达形式是相同的，在此又将无符号数与符号数的乘法运统一起来。