原创 基于FPGA的乘累加运算的分布式算法概述

乘累加运算的分布式算法概述<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

分布式算法在20多年前被首次提出，但直到Xilinx发明FPGA的查找表结构以后，分布式算法才在20世纪90年代初重新受到重视，并被有效地应用在FIR滤波器的设计中。

   分布式算法是基于查找表的一种计算方法，在利用FPGA实现数字信号处理方面发挥着重要的作用，可以大大提高信号的处理效率。它主要应用于数字滤波、频率转换等数字信号处理的乘累加运算。

乘累加运算的分布式算法原理分析

设Ak是已知常数（滤波器系数），xk(n)是变量，可以看作是n时刻的第k个采样输入数据，y(n)代表n时刻的系统响应。那么它们的内积为下式（1） ：

<?xml:namespace prefix = v ns = "urn:schemas-microsoft-com:vml" />

在上式（1）中，xk(n)变量可以写成下式（2）的形式：

  （2）式中，B为数据格式的字长,xkb是变量的二进制位，只有“<?xml:namespace prefix = st1 ns = "urn:schemas-microsoft-com:office:smarttags" />0”和“1”两种状态。将（2）式代入（1）式便可以推导出下页公式：

FPGA实现过程中查找表的构造方法

上图公式中括号里的每一乘积项代表着输入变量的某一位与常量的二进制“与”操作，加号代表着算术和操作，指数因子对括号中的值加权。如果事先构造一个查找表，该表存储着括号中所有可能的组合值，就可以通过所有输入变量相对应位的组合向量（XNb,X(N-1)b,...x1b）对该表进行寻址，该查找表称为DALUT。DALUT的构造规则如下页表1所示。

FPGA实现分布式算法的硬件结构如图：

以下是基于查找表实现的一个卷和运算，其中假设输入信号要通过一个三阶的滤波器，其系数为A1=-2,A2=3,A3=1。输入信号xin（x1=2,x2=1,x3=-3依次输入），输出信号yout。实现了卷和运算。

Verilog代码如下：

module filter(clk,rst,en,xin,yout,rdy);

input clk;              //主时钟信号

input rst;        //复位信号

input en;        //使能信号

input[3:0] xin;  //输入信号

output[7:0] yout;     //输出信号

output rdy;            //

reg rdy;

reg[3:0]  xreg1,xreg2,xreg3;

reg[7:0] ak0,ak1,ak2,ak3;

reg[7:0] yout;

always @ (posedge clk)

begin

       if(rst)

       begin

              rdy <= 0;

              xreg1 <= xin;

              xreg2 <= 4'd0;

              xreg3 <= 4'd0;

              yout <= 8'd0;

       end

       else if(en)

       begin

              xreg1 <=       xin;

              xreg2 <=       xreg1;

              xreg3 <=       xreg2;

              rdy <=1;

              yout <= ak0+ak1+ak2+ak3;

       end

       else

       begin

              rdy <=0;

              xreg1 <= xin;

              xreg2 <= 4'd0;

              xreg3 <= 4'd0;

              yout <= 8'd0;

       end

end

//用case语句构造的查找表

always @ (xreg1 or xreg2 or xreg3)

begin

       case({xreg1[0],xreg2[0],xreg3[0]})

              3'd0:       ak0 <= 8'h00;

              3'd1:       ak0 <= 8'h01;

              3'd2:       ak0 <= 8'h03;

              3'd3:       ak0 <= 8'h04;

              3'd4:       ak0 <= 8'hfe;

              3'd5:       ak0 <= 8'hff;

              3'd6:       ak0 <= 8'h01;

              3'd7:       ak0 <= 8'h02;

              endcase

       case({xreg1[1],xreg2[1],xreg3[1]})

              3'd0:       ak1 <= 8'h00;

              3'd1:       ak1 <= 8'h02;

              3'd2:       ak1 <= 8'h06;

              3'd3:       ak1 <= 8'h08;

              3'd4:       ak1 <= 8'hfc;

              3'd5:       ak1 <= 8'hfe;

              3'd6:       ak1 <= 8'h02;

              3'd7:       ak1 <= 8'h04;

              endcase

       case({xreg1[2],xreg2[2],xreg3[2]})

              3'd0:       ak2 <= 8'h00;

              3'd1:       ak2 <= 8'h04;

              3'd2:       ak2 <= 8'h0c;

              3'd3:       ak2 <= 8'h10;

              3'd4:       ak2 <= 8'hf8;

              3'd5:       ak2 <= 8'hfc;

              3'd6:       ak2 <= 8'h04;

              3'd7:       ak2 <= 8'h08;

              endcase

       case({xreg1[3],xreg2[3],xreg3[3]})

              3'd0:       ak3 <= 8'h00;

              3'd1:       ak3 <= 8'hf8;

              3'd2:       ak3 <= 8'he8;

              3'd3:       ak3 <= 8'he0;

              3'd4:       ak3 <= 8'h10;

              3'd5:       ak3 <= 8'h08;

              3'd6:       ak3 <= 8'hf8;

              3'd7:       ak3 <= 8'hf0;

              endcase

end

endmodule