常用数字处理算法的Verilog实现

常用数字处理算法的Verilog实现1．加法器的Verilog实现串行加法器组合逻辑的加法器可以利用真值表，通过与门和非门简单地实现。假设和表示两个加数，表示和，表示来自低位的进位，表示向高位的进位。每个全加器都执行如下的逻辑表达式：

这样可以得到加法器的一种串行结构。因此，式(2.1)所示的加法器也被称为串行加法器。如图2-20给出了一个4位串行加法器的结构示意图。

图2-20串行加法器的结构示意图在无线通信的信号处理中，常常要用到多位数字量的加法运算。如果用串行加法器实现，速度较慢，而并行加法器就能满足要求，并且结构并不复杂。现在普遍使用的并性加法器是超前进位加法器，只是在几个全加器的基础上增加了一个超前进位形成逻辑，以减少由于逐步进位信号的传递所造成的时延。图2-21给出了一个４位并行加法器的结构示意图。

图2-21串行加法器的示意图

在4位并行加法器的基础上，可以递推出16位、32位和64位的快速并行加法器。流水线加法器在使用了并行加法器后，仍旧只有在输出稳定后才能输入新的数进行下一次计算，即计算的节拍必须大于运算电路的延迟；此外，许多门级电路和布线的延迟会随着位数的增加而累加，因此加法器的频率还是受到了限制。但如果采用流水线，就有可能将一个算术操作分解为一些小规模的基本操作，将进位和中间值存储在寄存器中，并在下一个时钟周期内继续运算，这样就可以提高电路的利用效率。将流水线规则应用于FPGA中，只需要很少或根本不需要额外的成本。这是因为每个逻辑单元都包含两个触发器，大多数情况下这两个触发器或者没有用到，或者用于存储布线资源，那么就可以利用其来实现流水线结构。如果采用了流水线后，加法器的速度仍然不能满足需要的话，可以采用第3章中将会提到的串并转换来进一步提高计算的并行度。

由于一个slice中有两个触发器，还需要有1个触发器来作为进位输出，那么采用级流水线，就可以构造一个最大位数为位的加法器。

下面给出一个16位流水线加法器的代码。例2-2416位2级流水线加法器的Verilog设计

moduleadder16_2(cout,sum,clk,cina,cinb,cin);

input[15:0]cina,cinb;

inputclk,cin;

output[15:0]sum;

outputcout;

regcout;

regcout1;

reg[7:0]sum1;

reg[15:0]sum;

always@(posedgeclk)begin//低8位相加;

{cout1,sum1}={cina[7],cina[7:0]}+{cinb[7],cinb[7:0]}+cin;

end

always@(posedgeclk)begin//高8位相加，并连成16位

{cout,sum}={{cina[15],cina[15:8]}+{cinb[15],cinb[15:8]}+cout1,sum1};

end

endmodule

上述程序经过synplifyPro综合后，得到如图2-22所示的RTL级结构图。

2-2216位加法器的RTL结构图在ModelSim6.2b中完成仿真，其结果如图2-23所示，正确地实现了16比特加法。图2-2316位加法器的RTL结构图2．乘法器的Verilog实现串行乘法器两个N位二进制数x、y的乘积，最简单的方法就是利用移位操作来实现，用公式可以表示为：

(2.3)

这样输入量随着k的位置连续地变化，然后累加

。

例2-25用Verilog实现一个8位串行乘法器

moduleade(clk,x,y,p);

inputclk;

input[7:0]x,y;

output[15:0]p;

reg[15:0]p;

parameters0=0,s1=1,s2=2;

reg[2:0]count;

reg[1:0]state;

reg[15:0]p1,t;//比特位加倍

reg[7:0]y_reg;

always@(posedgeclk)begin

case(state)

s0:begin//初始化

y_reg<=y;

state<=s1;

count=0;

p1<=0;

t<={{8{x[7]}},x};

end

s1:begin//处理步骤

if(count==7)//判断是否处理结束

state<=s2;

elsebegin

if(y_reg[0]==1)

p1<=p1+t;

y_reg<=y_reg>>1;//移位

t<=t<<1;

count<=count+1;

state<=s1;

end

end

s2:begin

p<=p1;

state<=s0;

end

endcase

end

endmodule

上述程序在SynplifyPro中综合后，得到如图2-24所示的RTL级结构示意图。图2-24串行乘法器的RTL结构图

图2-25给出了串行乘法器模块在ModelSim中的仿真结果，验证了功能的正确性。

图2-25串行乘法器的局部仿真结果示意图从仿真结果可以看出，上述串行乘法器，速度比较慢，时延很大，但这种乘法器的优点是所占用的资源是所有类型乘法器中最少的，在低速的信号处理中有着广泛的应用。流水线乘法器一般的快速乘法器通常采用逐位并行的迭代阵列结构，将每个操作数的N位都并行地提交给乘法器。但是一般对于FPGA来讲，进位的速度快于加法的速度，这种阵列结构并不是最优的。所以可以采用多级流水线的形式，将相邻的两个部分乘积结果再加到最终的输出乘积上，即排成一个二叉树形式的结构，这样对于N位乘法器需要log2(N)级来实现。一个8位乘法器，如图2-26所示。

图2-26流水线乘法器结构图

例2-26用VerilogHDL实现一个4位的流水线乘法器

modulemul_addtree(mul_a,mul_b,mul_out,clk,rst_n);

parameterMUL_WIDTH=4;

parameterMUL_RESULT=8;

input[MUL_WIDTH-1:0]mul_a;

input[MUL_WIDTH-1:0]mul_b;

inputclk;

inputrst_n;

output[MUL_RESULT-1:0]mul_out;

reg[MUL_RESULT-1:0]mul_out;

reg[MUL_RESULT-1:0]stored0;

reg[MUL_RESULT-1:0]stored1;

reg[MUL_RESULT-1:0]stored2;

reg[MUL_RESULT-1:0]stored3;

reg[MUL_RESULT-1:0]add01;

reg[MUL_RESULT-1:0]add23;

always@(posedgeclkornegedgerst_n)

begin

if(!rst_n)

begin//初始化寄存器变量

mul_out<=8'b0000_0000;

stored0<=8'b0000_0000;

stored1<=8'b0000_0000;

stored2<=8'b0000_0000;

stored3<=8'b0000_0000;

add01<=8'b0000_0000;

add23<=8'b0000_0000;

end

else

begin//实现移位相加

stored3<=mul_b[3]?{1'b0,mul_a,3'b0}:8'b0;

stored2<=mul_b[2]?{2'b0,mul_a,2'b0}:8'b0;

stored1<=mul_b[1]?{3'b0,mul_a,1'b0}:8'b0;

stored0<=mul_b[0]?{4'b0,mul_a}:8'b0;

add01<=stored1+stored0;

add23<=stored3+stored2;

mul_out<=add01+add23;

end

end

endmodule

上述程序在SynplifyPro软件中综合后，得到如图2-27所示的RTL级结构示意图。

图2-27流水线乘法器的RTL结构示意图

图2-28给出了流水线乘法器模块在ModelSim中的仿真结果，验证了功能的正确性。

图2-28流水线乘法器的局部仿真结果示意图

从仿真结果可以看出，上述流水线乘法器比串行加法器的速度快很多，在非高速的信号处理中有着广泛的应用。至于高速信号的乘法一般需要利用FPGA芯片中内嵌的硬核DSP单元来实现。

3．无符号除法器的Verilog实现

两个无符号二进制数（如正整数）相除的时序算法是通过“减并移位”的思想来实现的，即从被除数中重复地减去除数，直到已检测到余数小于除数。这样可以通过累计减法运算的次数而得到商；而余数是在减法运算结束时被除数中的剩余值。当除数较小时，这种基本电路都必须进行多次减法，因此效率都不高。图2-29给出了一种更加高效的除法器基本结构[3]。在进行两个数相除的运算时，通常采用的步骤是调整除数与被除数使其最高位相对齐，然后反复地从被除数中减去除数，并将除数向被除数的最低位移动，且在高效除法器结构中可以并行运行这些操作步骤。而在具体的硬件实现中，是通过将被除数寄存器的内容不断地向除数的最高位移动来完成除法运算的。

无符号二进制字自调整除法器

在设计除法器结构的过程中应特别小心。在图中的减法运算步骤中，必须要将除数和被除数对齐，这取决于它们的相应大小和每个字的最高一位1的相对位置。同样，被除数寄存器也应向左扩展一位，以适应可能出现的已调整的除法寄存器内容初始值超过被除数寄存器中相应4位值的情况，在这种情况下，在进行减法操作之前，应从被除数的最高位移出一个1。例如(1100)2与(0111)2相除，应首先将被除数向左移，为下一步减法运算调整好被除数。因此，该机器的控制器会变得更加复杂，而且要包括能使除数和被除数移动的控制信号，如图2-29所示。

该物理结构将调整除数字与被除数的8位数据通道中的最左边4位对齐。在操作中，被除数字不断地从右向左移动，而且每一步都要从已调整的被除数的相应位中减去除数，这种操作取决于除数是否比被除数选定部分的对应值小。调整机器使得从被除数中减去的不是除数而是除数与2的幂的最大乘积，这样在当除数较小时就可以消去一些需要重复进行的减法运算。这种调整被称为是自调整的，因为它在一个除法运算序列的开始就能自动判断是否需要调整除数或被除数，这取决于它们最左非0位的相对位置。在除法运算中经常性地启动对两个字的调整使得其最高位为1的方法效率较低，因为这可能会需要更多的移位。所采用的方法是在一开始就将除数移到被除数的最左非0位（而不是被除数的最低位）。

有两种需要对数据通路字进行初始调整的情况：(1)被除数最左4位的值小于除数的值（例如(1100)2除以(1110)2），(2)除数的最低位为0，同时除数字节可以向左移动，而且仍然可以去除被除数（例如(1100)2除以(0101)2）。对于前者，应将被除数依次向左移动1位直到扩展1位的被除数的最左5位等于或大于除数，或者直到不能再移位为止。而对于后者，则应将除数向左移直到再移动所得到的字节不能去除被除数字节的最左4位为止（不包括扩展位）。余数位在除法运算序列结束时的物理位置取决于被除数是否进行了移位调整。因此，可将调整移位记录下来，并用来控制状态机调整在执行序列结束后的余数值。

图2-30给出了自调整除法器的状态转移图[3]。在一个给定状态下，从一个状态节点出发的支路中所使用的控制标记仅适于该支路，而在其他没有明确使用该标记离开当前状态的支路中被视为是不成立的。在任何离开一个状态节点的支路中都没有出现的标记被认为是无关紧要的。只有S_idle状态下才会给出复位信号，而在其他的所有状态上复位信号均被视为是异步动作。

该机器的状态与它的动作有关。S_Adivr状态下Shift_divisor的动作是将除法调整到被除数的最高非0位；S_Adivr状态下Shift_dividend的动作将调整被除数寄存器以进行减法运算；S_div状态下同时进行实际的减法运算和许多移位操作。状态S_Adivn和S_Adivr下变量Max将检测所允许的最大移位何时发生。

图2-30自调整除法器的状态转移图

例2-27用Verilog实现一个被除数为8位，除数为4位的高效除法器

moduledivider(clock,reset,word1,word2,Start,quotient,remainder,Ready,Error);

parameterL_divn=8;

parameterL_divr=4;

parameterS_idle=0,S_Adivr=1,S_Adivn=2,S_div=3,S_Err=4;

parameterL_state=3,L_cnt=4,Max_cnt=L_divn-L_divr;

input[L_divn-1:0]word1;//被除数数据通道

input[L_divr-1:0]word2;//除数数据通道

inputStart,clock,reset;

output[L_divn-1:0]quotient;//商

output[L_divn-1:0]remainder;//余数

outputReady,Error;

reg[L_state-1:0]state,next_state;

regLoad_words,Subtract,Shift_dividend,Shift_divisor;

reg[L_divn-1:0]quotient;

reg[L_divn:0]dividend;//扩展的被除数

reg[L_divr-1:0]divisor;

reg[L_cnt-1:0]num_shift_dividend,num_shift_divisor;

reg[L_divr:0]comparison;

wireMSB_divr=divisor[L_divr-1];

wireReady=((state==S_idle)&&!reset);

wireError=(state==S_Err);

wireMax=(num_shift_dividend==Max_cnt+num_shift_divisor);

wiresign_bit=comparison[L_divr];

always@(state

ordividendordivisororMSB_divr)begin//从被除数中减去除数

case(state)

S_Adivr:if(MSB_divr==0)

comparison=dividend[L_divn:L_divn-L_divr]+{1'b1,~(divisor<<1)}+1'b1;

else

comparison=dividend[L_divn:L_divn-L_divr]+{1'b1,~divisor[L_divr-1:0]}+1'b1;

default:comparison=dividend[L_divn:L_divn-L_divr]+{1'b1,~divisor[L_divr-1:0]}+1'b1;

endcase

end

//将余数移位来对应于整体的移位

assignremainder=(dividend[L_divn-1:L_divn-L_divr])-num_shift_divisor;

always@(posedgeclock)begin

if(reset)

state<=S_idle;

else

state<=next_state;

end

//次态与控制逻辑

always@(stateorword1orword2orstateorcomparisonorsign_bitorMax)begin

Load_words=0;

Shift_dividend=0;

Shift_divisor=0;

Subtract=0;

case(state)

S_idle:case(Start)

0:next_state=S_idle;

1:if(word2==0)

next_state=S_Err;

elseif(word1)begin

next_state=S_Adivr;

Load_words=1;

end

else

next_state=S_idle;

endcase

S_Adivr:case(MSB_divr)

0:if(sign_bit==0)begin

next_state=S_Adivr;

Shift_divisor=1;//可移动除数

end

elseif(sign_bit==1)begin

next_state=S_Adivn;//不可移动除数

end

1:next_state=S_div;

endcase

S_Adivn:case({Max,sign_bit})

2'b00:next_state=S_div;

2'b01:begin

next_state=S_Adivn;

Shift_dividend=1;

end

2'b10:begin

next_state=S_idle;

Subtract=1;

end

2'b11:next_state=S_idle;

endcase

S_div:case({Max,sign_bit})

2'b00:begin

next_state=S_div;

Subtract=1;

end

2'b01:next_state=S_Adivn;

2'b10:begin

next_state=S_div;

Subtract=1;

end

2'b11:begin

next_state=S_div;

Shift_dividend=1;

end

endcase

default:next_state=S_Err;

endcase

end

always@(posedge

clock)begin//寄存器,数据通道操作

if(reset)begin

divisor<=0;

dividend<=0;

quotient<=0;

num_shift_dividend<=0;

num_shift_divisor<=0;

endelseif(Load_words==1)begin

dividend<=word1;

divisor<=word2;

quotient<=0;

num_shift_dividend<=0;

num_shift_divisor<=0;

end

elseif(Shift_divisor)begin

divisor<=divisor<<1;

num_shift_divisor<=num_shift_divisor+1;

end

elseif(Shift_dividend)begin

dividend<=dividend<<1;

quotient<=quotient<<1;

num_shift_dividend<=num_shift_dividend+1;

end

elseif(Subtract)begin

dividend[L_divn:L_divn-L_divr]<=comparison;

quotient[0]<=1;

end

end

endmodule

上述程序经过Synplify综合后得到如图2-31所示的RTL级结构。

图2-31无符号高效除法器的RTL级结构图在ModelSim中经过仿真，其仿真结果如图2-31所示。仿真中输入了两组数据，且在输出信号Ready为高时输出相应的商和余数。当被除数为57，除数为6时，可以看到商和余数分别为9和3；当被除数为98，除数为9时，可以看到商和余数分别为10和8。这表明上述程序的正确性。

图2-32无符号高效除法器的仿真波形

4.CORDIC算法的Verilog实现CORDIC算法的原理CORDIC算法可以将多种难以用硬件电路直接实现的复杂运算分解为统一的简单的移位、加迭代运算，而且结构规则、运算周期可以预测、适合于VLSI实现。许多数字信号处理算法，如DXT、FFT、复数滤波器、格形滤波器、基于Givens旋转的QR分解、奇异值/特征值分解、最小二乘求解以及线性系统求解等，都很容易用圆周旋转或双曲旋转来描述其基本的操作，因此都可以用CORDIC算法得到很好地实现。因此以CORDIC为核心的FPGA应用日益受到人们的重视。

CORDIC是用于计算广义矢量旋转的一种迭代方法。由J.D.Volder于1959年提出的[6]，主要用于三角函数、双曲函数、指数和对数的运算[7,8]。该算法使得矢量的旋转和定向运算不需要三角函数表以及乘法、开方、反三角函数等复杂的运算，仅需要进行加减和移位即可。1971年，Walther提出了统一的CORDIC算法[9]，引入了参数m将CORDIC实现的三种迭代模式：三角运算、双曲运算和线性运算统一于一个表达式下，形成目前所用到的CORDIC算法最基本的数学基础。该算法的基本思想是通过一系列固定的、与运算基数相关的角度不断偏摆以逼近所需的旋转角度，可由下列等式进行描述：