标签: 布思算法

高性能乘法器是现代微处理器中的重要部件,是实时图像处理和数字信号处理的核心. 同时乘法器也是微处理器数据处理的关键路径, 乘法器完成一次乘法操作的周期基本上决定了微处理器的主频. 因此人们对提高乘法器的性能进行了大量的研究.在这个研究过程中，布思算法便起到了很大的作用。 假设A为乘数，B为被乘数。 乘数A可表示为：     A = - A * 2^N-1 + A * 2^N-2 + …… + A * 2^1 + A * 2^0   则：     D = A * B       = (- A * 2^N-1 + A * 2^N-2 + …… + A * 2^1 + A * 2^0) * B        = - A * B * 2^N-1 + A * B * 2^N-2 + …… + A * B * 2^1 + A * B * 2^0 做变形，得     A = - A * 2^N-1 + A * 2^N-2 + …… + A * 2^1 + A * 2^0       = - A * 2^N-1 + (2A - A ) * 2^N-2 + (2A - A ) * 2^N-3 + …… +         (2A - A ) * 2^2 + (2A - A ) * 2^1 + (2A - A ) * 2^0        = - A * 2^N-1 + A * 2^N-1 - A * 2^N-2 + A * 2^N-2 - A * 2^N-3 + …… +         A * 2^3 - A * 2^2 + A * 2^2 - A * 2^1 + A * 2^1 - A * 2^0       = (- A + A ) * 2^N-1 + (- A + A ) * 2^N-2 + …… +         (- A + A ) * 2^2 + (- A + A ) * 2^1 + (- A + 0) * 2^0        =     Σ n = 0,A = 0 N - 1    ((- A + A ) * 2^n)        =  Σ n = 0 N - 1 (E * 2n) (3-5) 其中：     E = - A + A (0 ≤ n ≤ (N-1) , A = 0) (3-6) 其值如下表所示： A      A         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 * 2^N-1 + A * 2^N-2 + …… + A * 2^1 + A * 2^0       =  Σ n = 0 N - 1 (A * 2^n) ) 则：     D = A * B       = ( Σ n = 0 N - 1 (A * 2^n)) * B       =  Σ n = 0 N - 1 ((A * B) * 2^n) (3-12) 可见，式(3-8)、式(3-12)表达形式是相同的，在此又将无符号数与符号数的乘法运统一起来。