(2.7)--第4章 EDA技术及应用提高篇总结复习.ppt

第4章 EDA技术及应用提高总结复习4.4 CORDIC算法的应用设计内容提要内容提要 CORDIC算法的应用设计：系统设计要求；CORDIC算法简介；CORDIC算法推导；CORDIC算法实现结构；CORDIC算法编程思路；VHDL程序设计；仿真结果验证。4.4.1 CORDIC算法的应用设计(1)二、CORDIC算法简介在现代信号处理中，经常会遇到三角函数、超越函数和坐标转化等问题。传统的实现方法有查找表、多项式展开等方法。这些方法在精度、速度、简单性和效率方面往往不能兼顾，而CORDIC算法则可以很好地兼顾这几方面的要求。一、系统设计要求CORDIC是坐标旋转数字计算机(Coordinate Rotations Digital Computer)的英文字头缩写，它于1959年由J.Volder提出，首先应用于导航系统，使得矢量的旋转和定向运算不需要做复杂运算。CORDIC算法的基本思想是通过一系列固定的、与运算基数相关的角度偏摆来逼近所需的旋转角度。可通过该算法的圆周模式、双曲线模式、线性模式等不同的实现模式，来计算乘除、平方根、正弦、余弦、反正切向量旋转以及指数运算等。由于基本运算单元只有移位与加减法，这就为CORDIC算法的FPGA实现打下了良好的基础。1971年，J.Walther提出了统一的CORDIC算法，把圆周旋转、双曲线旋转、线性旋转统一到同一个CORDIC迭代方程中，为用统一的硬件实现多功能CORDIC算法奠定了理论基础。三、CORDIC算法推导CORDIC算法包含圆周系统、线性系统、双曲系统三种旋转系统。图1 坐标旋转图图1 坐标旋转图如果圆周的半径为R，平面坐标与旋转坐标之间存在如下关系：(1)(2)所有迭代角之和等于旋转角度，亦即每一步旋转角度，因此(3)经过N次迭代后，有(4)其中K为增益因子，当N=+时有(5)在旋转模式中，Z为初始化需要旋转的角，当Z旋转变为0时，公式变化如下：(6)经过N次迭代后，CORDIC公式的输出变为(7)其中，如果则N次迭代后有(8)从式(8)的分析可以看出，CORDIC 算法在圆周系统的旋转模式可以用来计算一个输入角度的正弦值、余弦值和正切值，此外还可将极坐标变换为平面坐标。四、CORDIC算法实现结构CORDIC算法的实现有两种结构方案：迭代结构和流水线结构。基于迭代结构的CORDIC算法实现方案只需要一组移位及加减运算的单元，硬件开销很小，但控制比较复杂，而且完成一次CORDIC运算需要多个时钟周期，当对速度要求较高时很难满足要求。基于流水线结构的实现方案，每级CORDIC迭代运算都使用单独的一套运算单元，与基于迭代结构的实现方案相比，流水线结构的处理速度非常快，当流水线填满之后每个时钟周期就会计算出一组结果。本设计采用流水线结构进行设计：图2 CORDIC算法的流水线结构XIYIZI外部输入XI、YI、ZI作为第一级流水线单元的输入X(0)、Y(0)、Z(0)；中间各个单元首尾相接，也就是第N个单元的输入与N-1个单元的输出X(N-1),Y(N-1),Z(N-1)相连，第N个单元的输出X(N),Y(N),Z(N)又与N+1个单元的输入相连；XOYOYO最后一级处理单元的输出X(N)、Y(N)、Z(N)就是整个系统的输出XO、YO、ZO。内容提要内容提要 CORDIC算法的应用设计：系统设计要求；CORDIC算法简介；CORDIC算法推导；CORDIC算法实现结构；CORDIC算法编程思路；VHDL程序设计；仿真结果验证。4.4.1 CORDIC算法的应用设计(2)一、CORDIC算法编程思路利用CORDIC算法求解正弦和余弦函数的程序可分为三个层次，二、VHDL程序设计1实现CORDIC算法的流水线单元电路CORDICPIPE.VHDLIBRARY IEEE;USE IEEE.STD_LOGIC_1164.ALL;USE IEEE.STD_LOGIC_ARITH.ALL;ENTITY CORDICPIPE IS GENERIC(WIDTH:NATURAL:=16;PIPEID:NATURAL:=1);PORT(CLK:IN STD_LOGIC;ENA:IN STD_LOGIC;XI:IN SIGNED(WIDTH-1 DOWNTO 0);YI:IN SIGNED(WIDTH-1 DOWNTO 0);ZI:IN SIGNED(19 DOWNTO 0);XO:OUT SIGNED(WIDTH-1 DOWNTO 0);YO:OUT SIGNED(WIDTH-1 DOWNTO 0);ZO:OUT SIGNED(19 DOWNTO 0);END ENTITY CORDICPIPE;类属表端口表ARCHITECTURE ART OF CORDICPIPE IS FUNCTION CATAN(N:NATURAL)RETURN INTEGER ISVARIABLE RESULT:INTEGER;BEGINCASE N IS WHEN 0=RESULT:=16#020000#;WHEN 1=RESULT:=16#012E40#;WHEN 2=RESULT:=16#09FB4#;WHEN 3=RESULT:=16#05111#;.WHEN 15=RESULT:=16#05#;WHEN 16=RESULT:=16#03#;WHEN 17=RESULT:=16#01#;WHEN OTHERS=RESULT:=16#0#;END CASE;RETURN RESULT;END CATAN;函数CATAN的定义该函数的功能是：根据迭代步骤N的值求解该步需要旋转的角度ATAN(1/2N）,具体求解的方法就是通过1个预计算的CASE查找表来实现。-FUNCTION DELTA IS ACTUALLY AN ARITHMATIC SHIFT RIGHT FUNCTION DELTA(ARG:SIGNED;CNT:NATURAL)RETURN SIGNED ISVARIABLE TMP:SIGNED(ARGRANGE);CONSTANT LO:INTEGER:=ARGHIGH-CNT+1;BEGINFOR N IN ARGHIGH DOWNTO LO LOOP TMP(N):=ARG(ARGHIGH);END LOOP;FOR N IN ARGHIGH-CNT DOWNTO 0 LOOP TMP(N):=ARG(N+CNT);END LOOP;RETURN TMP;END FUNCTION DELTA;函数DELTA的定义该函数的功能就是根据输入ARG和CNT求解ARG/2CNT，具体求解方法是通过将ARG算术右移CNT位的方式来实现，-将右移后空余各位补符号位-TMP的数据右移的CNT位图1 DELTA函数的有关参数的含义及移位操作操作示意图其中图中上面是ARG移位前的数位分布及移位操作的有关参数要求，下面是ARG移位之后的结果及有关操作的说明。FUNCTION ADDSUB(DATAA,DATAB:IN SIGNED;ADD_SUB:IN STD_LOGIC)RETURN SIGNED ISBEGINIF(ADD_SUB=1)THEN RETURN DATAA+DATAB;ELSE RETURN DATAA-DATAB;END IF;END FUNCTION ADDSUB;函数ADDSUB的定义该函数的功能就是根据控制信号ADD_SUB的不同分别将DATAA和 DATAB做加法或减法 SIGNAL DX,XRESULT:SIGNED(WIDTH-1 DOWNTO 0);SIGNAL DY,YRESULT:SIGNED(WIDTH-1 DOWNTO 0);SIGNAL ATAN,ZRESULT:SIGNED(19 DOWNTO 0);SIGNAL ZNEG,ZPOS:STD_LOGIC;BEGIN DX=DELTA(XI,PIPEID);DY=DELTA(YI,PIPEID);ATAN=CONV_SIGNED(CATAN(PIPEID),20);-GENERATE ADDER STRUCTURES ZNEG=ZI(19);ZPOS=NOT ZI(19);-XADD XRESULT=ADDSUB(XI,DY,ZNEG);-YADD YRESULT=ADDSUB(YI,DX,ZPOS);-ZADD ZRESULT=ADDSUB(ZI,ATAN,ZNEG);-调用函数DELTA求出2-nXn，并将函数的返回值赋值给DX-调用函数DELTA求出2-nYn，并将函数的返回值赋值给DY-将ZI的符号位ZI(19)赋值给ZNEG，实际上ZNEG就是-Sn-将ZI的符号位ZI(19)求反后赋值给ZPOS，实际上ZPOS就是Sn GEN_REGS:PROCESS(CLK)ISBEGINIF(CLKEVENT AND CLK=1)THEN IF(ENA=1)THENXO=XRESULT;YO=YRESULT;ZO 0);ZI:IN SIGNED(WIDTH-1 DOWNTO 0);XO:OUT SIGNED(WIDTH-1 DOWNTO 0);YO:OUT SIGNED(WIDTH-1 DOWNTO 0);END ENTITY CORDIC;ARCHITECTURE ART OF CORDIC IS TYPE XYVECTOR IS ARRAY(PIPELINE DOWNTO 0)OF SIGNED(WIDTH-1 DOWNTO 0);TYPE ZVECTOR IS ARRAY(PIPELINE DOWNTO 0)OF SIGNED(19 DOWNTO 0);COMPONENT CORDICPIPE GENERIC(WIDTH:NATURAL:=16;PIPEID:NATURAL:=1);PORT(CLK:IN STD_LOGIC;ENA:IN STD_LOGIC;XI:IN SIGNED(WIDTH-1 DOWNTO 0);YI:IN SIGNED(WIDTH-1 DOWNTO 0);ZI:IN SIGNED(19 DOWNTO 0);XO:OUT SIGNED(WIDTH-1 DOWNTO 0);YO:OUT SIGNED(WIDTH-1 DOWNTO 0);ZO:OUT SIGNED(19 DOWNTO 0);END COMPONENT CORDICPIPE;SIGNAL X,Y:XYVECTOR;SIGNAL Z:ZVECTOR;CORDICPIPE的元件例化声明-定义模块间连接信号，它用于16个流水线单元电路CORDICPIP的级联 BEGIN -FILL FIRST NODES -FILL X X(0)=XI;-FILL Y Y(0)=YI;-FILL Z Z(0)(19 DOWNTO 4)=ZI;Z(0)(3 DOWNTO 0)0);-将外部输入XI赋值给第一级流水线单元的输入X（0）-将外部输入YI赋值给第一级流水线单元的输入Y（0）-把外部输入ZI赋值给第一级流水线单元的输入Z（0）的4到20位-给Z（0）的0到3位补零，也是就20位数据左对齐-GENERATE PIPELINE GEN_PIPE:FOR N IN 1 TO PIPELINE GENERATEPIPE:CORDICPIPE GENERIC MAP(WIDTH=WIDTH,PIPEID=N-1)PORT MAP(CLK,ENA,X(N-1),Y(N-1),Z(N-1),X(N),Y(N),Z(N);END GENERATE GEN_PIPE;-ASSIGN OUTPUTS XO=X(PIPELINE);YO TEMP1=CONV_INTEGER(SEC)-CONV_INTEGER(SEC)/10*10;TEMP2 TEMP1=CONV_INTEGER(MIN)-CONV_INTEGER(MIN)/10*10;TEMP2 TEMP1=CONV_INTEGER(HOUR)-CONV_INTEGER(HOUR)/10*10;TEMP2 TEMP1=CONV_INTEGER(WEEK)-CONV_INTEGER(WEEK)/10*10;TEMP2NULL;END CASE;其中以CASE CNT开始的选择语句，是根据控制信号CNT的周期性变化，将对应的当前整数秒、分、时、日、月、年、星期值，分解为个位和十位，并保存在信号TEMP1和TEMP2中。将矢量分MIN转换成整数分整数分CONV_INTEGER(MIN)的十位CONV_INTEGER(MIN)/10再乘以10MIN的个位MIN的十位例如MIN=65,则MIN/10=6,TEMP1=65-65/10*10=65-6*10=5,TEMP2=65/10=6。其他语句类似。CASE TEMP1 IS WHEN 0 =LBCDLBCDLBCDLBCDLBCDLBCDHBCDHBCDHBCDHBCDHBCDHBCD10Mbits/s；动态响应时间：100ms/frame。主处理器初步选用德州公司的DSP芯片TMS320C5402，协处理器拟采用ALTERA公司的FPGA自行开发设计。德州仪器商标ALTERA商标图2 图像处理系统接口关系图阀值/像素值选择端口T_D=1时，表示输入的数据为像素阀值T_D=0时，表示输入的数据为像素值像素边界判别信号输出MAGOUT为1时，表示当前像素为边界像素MAGOUT为0表示为非边界像素。二、系统总体设计图像边缘检测，有许多边缘检测算法。由于Sobel算法只涉及加法操作，但却可以得到很好的划分效果，因而是图像处理系统中最常用的边缘检测算法。Sobel算法包括带4个33掩码的输入图像数据，即Sobel算子，它设置权重来检测水平、垂直、左对角、右对角各个不同方向上密度幅度的不同。这个过程通常被称为过滤。1算法选择图3 像素窗口水平、垂直、左对角、右对角各图像方向上密度幅度的变化，可以用H,V,DL,DR四个滤波器进行计算：H=(Q0+2Q3+Q6)-(Q2+2Q5+Q8);V=(Q0+2Q1+Q2)-(Q6+2Q7+Q8);DR=(Q1+2Q0+Q3)-(Q5+2Q8+Q7);DL=(Q1+2Q2+Q5)-(Q3+2Q6+Q7);对梯度大小的一个普遍估计值为：MagnitudeMax(H,V,DR,DL)。如果Magnitude大于Threshold，则该像素被声明为边界像素，否则为一般像素。2算法实现为了减少设计的复杂度，我们可对Sobel的滤波函数中的乘法运算改写成加法运算：H=(Q0+Q3+Q3+Q6)-(Q2+Q5+Q5+Q8);V=(Q0+Q1+Q1+Q2)-(Q6+Q7+Q7+Q8);DR=(Q1+Q0+Q0+Q3)-(Q5+Q8+Q8+Q7);DL=(Q1+Q2+Q2+Q5)-(Q3+Q6+Q6+Q7);如果使用CPLD/FPGA进行自行设计，首先，H，V，DR，DL四个方向的滤波可以全部并行，同时，每一个方向的滤波函数可以采用一级四路并行加法器与一级双路并行加法器串连，这样以来，算上两级串行比较器，实际上整个系统只有四级串行结构，假设使用50M的系统时钟，处理完一个像素点的时间为 41/(50M)=80ns，处理完一帧图像的时间为 80060080ns38.4ms。3总体设计方案图4 图像处理流程示意图步长为一行步距为一列图5 图像边缘检测器总体结构图帧窗口接收模块负责接收DSP传送过来的一个帧窗口的数据，其本质为一个双端口先入先出栈FIFO，其数据宽度为8，深度等于一个帧窗口内的像素点个数(60031800)。串入并出模块负责把FIFO内的数据转换成为像素处理窗口的列像素向量，便于像素处理窗口的数据刷新处理。像素窗口刷新模块实现对需要处理的像素数据的刷新数据处理模块主要是实现Sobel算法三、主要模块设计1帧窗口接收模块FIFO由于高速设备与慢速设备之间处理速度的差别，本系统数据传输选择了帧同步方式。存储器的类型拟选用FIFO，堆栈空时向主机发出准备好信号，主机检测到它的数据传输请求时，传送一帧数据，由于FIFO的大小与一帧图像的大小是一致的，所以接收完毕后，堆栈满，Sobel处理器启动边缘检测进程，处理完一帧数据后，堆栈重新变为空，为下一帧数据处理作准备。图6 帧窗口接收模块FIFO的内部结构图2串入并出模块SIPO串入并出模块的主要功能是负责一列像素的刷新，也就是把主处理器传送过来的像素值转换成33像素窗口的一列。该模块的实现主要是通过六个D触发器和一个三进制的计数器组成，当计数器产生进位溢出时，串行输入的三个像素点并行输出。图7 串入并出模块SIPO的内部结构图3像素窗口刷新模块REFRESH像素刷新窗口的主要功能是接收串入并出模块的3个并行像素，把窗口中原有的第二列像素推入第三列，第一列推入第二列，新到的并行像素填入第一列。其本质为一个移位寄存器。图8 像素刷新窗口REFRESH的内部结构图4滤波模块FILTER对于SOBEL算法的各个滤波器，经变换后可得到：H=(Q0+Q3+Q3+Q6)-(Q2+Q5+Q5+Q8);V=(Q0+Q1+Q1+Q2)-(Q6+Q7+Q7+Q8);DR=(Q1+Q0+Q0+Q3)-(Q5+Q8+Q8+Q7);DL=(Q1+Q2+Q2+Q5)-(Q3+Q6+Q6+Q7);通用滤波器水平方向滤波器图9 滤波模块FILTER的内部结构图图9 滤波模块FILTER的内部结构图为提高加法运算的速度，本设计中的加法器采用超前进位加法器,超前进位的基本思想是让本位和与本位进位与低位的进位无关。对于上面图中提到的减法运算，我们需要考虑符号问题。同时考虑到与输出模块的衔接，必须使用符号位，而不能丢弃。减法运算的本质先对减数求补码，然后采用加法运算。5数据处理模块PROCESSOR数据处理模块PROCESSOR的主要功能是求出四个方向的图像梯度数据绝对值的最大值，同时判别最大值出现的方向。图10 数据处理模块PROCESSOR的内部结构图四、程序设计与调试根据前面已经讲解的系统总体设计、主要模块设计的思想，完成各种VHDL源程序的设计、仿真以及硬件验证。其中各模块的设计，既可使用VHDL编程的方式进行，也可使用兆功能块调用的方式进行，还可使用VHDL编程和兆功能块调用相结合的方式进行。硬件的验证，可在原有设计的基础上进行适当修改进行，比如增加1个数据寄存器模块，将需要测试的有关数据（比如36个数据）事先存储在数据寄存器模块中，每来1个时钟信号上升沿，按要求不断地输出数据进入现有的图像边缘检测器来模拟数据采集；增加1个动态数据显示模块，将输入和输出的有关数据使用动态扫描的方式进行显示。本课题可作为一个时长1周的EDA技术课程设计的来完成，具体任务就是用FPGA设计与实现一个SOBEL图像边缘检测器。具体内容包括：系统需求分析、系统总体设计、主要模块设计、各种源程序设计、程序的仿真验证、系统的硬件验证等内容，并完成课程设计报告。