分布式算法原理

---

分布式算法（distributed arithmetic，DA）是一种以实现乘法运算为目的的运算方法。它与传统实现乘法运算的不同之处在于：执行部分积运算的先后顺序不同。简单地说，分布式算法在完成乘加功能时时通过将各输入数据每一对应位产生的部分积预先进行相加形成相应部分积，然后再对各部分积进行累加形成最终结果；而传统算法是等到所以乘积产生之后再进行相加来完成乘加运算的。与传统算法相比，分布式算法可以极大地减少硬件电路规模，很容易实现流水线处理，提高电路的执行速度。

 分布式算法（distributed arithmetic，DA）是一项重要的FPGA技术， 被广泛运用于计算机的乘法运算中。该算法将乘法运算转换成加法以及移位运算，能够高速完成大量的乘法运算，极大地提高了芯片的使用效率。 为了方便分析，将滤波器表达式改为：

假设h(n)都是已知常数，x(n)是变量。无符号数x(n)的表达式为：

式中： 表示第n个采样值，b表示x(n)的第b位，则y可以表示为：

变换求和次序，重新求和得：

化简成如下形式：

式中：xb(n) 表示第n个数据的第b位。由于x(n)为有限位数据，且xb(n)的取值为[0,1],故 有2^N种不同的取值，又因为已知，所以可以通过查表的方法来实现f(h(n,xb(n)))。再通过相应的二次幂加权并累加，就可得到内积y的结果。

实现框图如下：

图中a为传统算法，b为分布式DA算法。

根据DA算法原理，可以实现FIR滤波器。滤波器系数可由matlab求得，然后根据滤波器输入数据位宽，对系数进行合适的放大，在实现过程中对累加值进行右移，最终得到滤波器的输出。

作者：杭州卿萃科技ALIFPGA