基于CORDIC算法的数控振荡器及其FPGA实现_刘春雅

CRC16算法原理

CRC算法及C实现 学习体会2008-09-20 15:21:13 阅读161 评论0 字号：大中小订 阅 一、CRC算法原理 CRC校验的基本思想是利用线性编码理论，在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（既CRC码）r位，并附在信息后边，构成一个新的二进制码序列数共(k+r)位，最后发送出去。在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。 16位的CRC码产生的规则是先将要发送的二进制序列数左移16位（既乘以）后，再除以一个多项式，最后所得到的余数既是 CRC码。 假设数据传输过程中需要发送15位的二进制信息 g=101001110100001，这串二进制码可表示为代数多项式g(x) = x^14 + x^12 + x^9 + x^8 + x^7 + x^5 + 1，其中g中第k位的值，对应g(x)中x^k的系数。将g(x)乘以x^m，既将g后加m个0，然后除以m阶多项式h(x)，得到的(m-1)阶余项 r(x)对应的二进制码r就是 CRC编码。 h(x)可以自由选择或者使用国际通行标准，一般按照h(x)的阶数m，将CRC算法称为CRC-m，比如CRC-32、CRC-64等。国际通行标准可

以参看 https://www.wendangku.net/doc/048392758.html,/wiki/Cyclic_redundancy_check g(x)和h(x)的除运算，可以通过g和h做xor（异或）运算。比如将 11001与10101做xor运算： 明白了xor运算法则后，举一个例子使用CRC-8算法求101001110100001的效验码。CRC-8标准的h(x) = x^8 + x^7 + x^6 + x^4 + x^2 + 1，既h是9位的二进制串111010101。

CRC校验解读

三种常用的CRC16校验算法的C51程序的优化2009-10-10 09:34:17| 分类：技术知识| 标签：|字号大 CRC校验又称为循环冗余校验，是数据通讯中常用的一种校验算法。它可以有效的判别出数据在传输过程中是否发生了错误，从而保障了传输的数据可靠性。 CRC校验有多种方式，如：CRC8、CRC16、CRC32等等。在实际使用中，我们经常使用CRC16校验。CRC16校验也有多种，如：1005多项式、1021多项式（CRC-ITU）等。在这里我们不讨论CRC算法是怎样产生的，而是重点落在几种算法的C51程序的优化上。 计算CRC校验时，最常用的计算方式有三种：查表、计算、查表＋计算。一般来说，查表法最快，但是需要较大的空间存放表格；计算法最慢，但是代码最简洁、占用空间最小；而在既要求速度，空间又比较紧张时常用查表＋计算法。 下面我们分别就这三种方法进行讨论和比较。这里以使用广泛的51单片机为例，分别用查表、计算、查表＋计算三种方法计算1021多项式（CRC-ITU）校验。原始程序都是在网上或杂志上经常能见到的，相信大家也比较熟悉了，甚至就是正在使用或已经使用过的程序。 编译平台采用Keil C51 7.0，使用小内存模式，编译器默认的优化方式。 常用的查表法程序如下，这是网上经常能够看到的程序范例。因为篇幅关系，省略了大部分表格的内容。 code unsigned int Crc1021Table[256] = { 0x0000, 0x1021, 0x2042, 0x3063,... 0x1ef0 }; unsigned int crc0(unsigned char *pData, unsigned char nLength) { unsigned int CRC16 = 0;

CRC算法

CRC算法与实现bhw98 摘要: 本文首先讨论了CRC的代数学算法，然后以常见的CRC-ITU为例，通过硬件电路的实现，引出了比特型算法，最后重点介绍了字节型快速查表算法，给出了相应的C 语言实现。 关键词: CRC, FCS, 生成多项式, 检错重传 引言 CRC的全称为Cyclic Redundancy Check，中文名称为循环冗余校验。它是一类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域广泛地用于实现差错控制。实际上，除数据通信外，CRC在其它很多领域也是大有用武之地的。例如我们读软盘上的文件，以及解压一个ZIP文件时，偶尔会碰到“Bad CRC”错误，由此它在数据存储方面的应用可略见一斑。 差错控制理论是在代数理论基础上建立起来的。这里我们着眼于介绍CRC的算法与实现，对原理只能捎带说明一下。若需要进一步了解线性码、分组码、循环码、纠错编码等方面的原理，可以阅读有关资料。 利用CRC进行检错的过程可简单描述为：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位监督码(CRC码)，附在原始信息后边，构成一个新的二进制码序列数共k+r位，然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”。 1 代数学的一般性算法 在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如1100101 表示为 1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1，即x6+x5+x2+1。 设编码前的原始信息多项式为P(x)，P(x)的最高幂次加1等于k；生成多项式为G(x)，G(x)的最高幂次等于r；CRC多项式为R(x)；编码后的带CRC的信息多项式为T(x)。 发送方编码方法：将P(x)乘以xr(即对应的二进制码序列左移r位)，再除以G(x)，所得余式即为R(x)。用公式表示为 T(x)=x r P(x)+R(x) 接收方解码方法：将T(x)除以G(x)，如果余数为0，则说明传输中无错误发生，否则说

CORDIC算法的优化及硬件实现

CORDIC算法的优化及硬件实现 【摘要】本文介绍了CORDIC算法的基本原理并分析了其优化的方法，在QUARTUS9.0平台上基本实现了其功能，有效的降低了资源的消耗并提升了工作频率。 【关键词】CORDIC优化；FPGA；仿真 CORDIC算法全称为坐标旋转数字计算机，它是由J.V older于1959年提出，cordic的运用大大降低了常用函数如sin，cos，sinh，cosh等在硬件上实现的难度，它主要是将复杂的函数在硬件上通过加减和移位运算递归计算出函数值，由于以上特性使得这一算法特变适合在FPGA上实现。 1.CORDIC算法基本原理 CORDIC算法主要是在一个平面上某一向量（x1，y1）经过旋转角后得到新的向量（x2，y2），如图1所示。 根据变换规则二者有如下关系： 2.传统CORDIC算法的局限性及优化 CORDIC算法在FPGA中主要通过流水线来实现，通常要将提前算出作为的输入预先存储到ROM中，随着流水线级数的增加ROM表的容量成指数增长增加了系统的资源消耗，CORDIC每次运算都要经过多次迭代随着迭代次数的增加计算速度受到很大的影响，一个结果往往要经过多个时钟周期才能得到，此外传统的CORDIC算法的角度范围受到很大的约束，旋转的最大的角度范围为-99.88≤≤99.88无法达到0≤≤360必须对输入的角度预先进行处理才能使其达到收敛针对以上情况采取优化反正切函数表来减少迭代次数，简化校正因子等可以解决资源和速度的缺陷，对于角度的收敛问题采用分象限法如表1。 对于一个15级流水线可以通过以上的方法减少到12次迭代减少了3级流水线，并且减少了ROM的使用量提高了运行效率。 3.CORDIC算法硬件的实现 由于CORDIC算法主要通过加减以及移位来实现，说以特别适合在FPGA 上实现，在这里我采用Altera公司的Cyclon2器件组中的EP2C5Q208C8整个实现过程都是在Quartus9.0中完成图2为系统的整体架构。 当接收完六个字节数据后开始进行优化CORDIC算法迭代运算流程图如图3所示。

CORDIC算法原理及matlab仿真

.1、坐标旋转数字计算机CORDIC 坐标旋转数字计算机CORDIC(COordinate Rotation DIgital Computer)算法，通过移位和加减运算，能递归计算常用函数值，如Sin，Cos，Sinh，Cosh等函数，由J. Volder于1959年提出，首先用于导航系统，使得矢量的旋转和定向运算不需要做查三角函数表、乘法、开方及反三角函数等复杂运算。J. Walther 在1974年用它研究了一种能计算出多种超越函数的统一算法。 1.2、CORDIC原理 如图所示，初始向量（X(0)，Y(0)）旋转θ角度之后得到向量（X1，Y1），此向量有如下关系： CORDIC算法 X1=X0*cos(θ)-Y0*sin(θ)=cos(θ)(X0-Y0*tan(θ)) Y1=Y0*cos(θ)+X0*sin(θ)=cos(θ)(Y0+X0*tan(θ)) 注：θ为待求角 假设初始向量经过N次旋转之后得到新向量，且每次旋转角度δ正切值都为2的倍数，则第i次旋转角度为δ=arctan(2^(-i))，即cosδ=（1/（1+2^(-2i)））^0.5。 容易得到角度θ≈∑S(i)●δ(i)，其中S(i)=1或－1，表示旋转角度的方向，第i步旋转可以表示为： X(i+1)=(（1/（1+2^(-2i)））^0.5)●(X(i)-S(i)Y(i)2^(-i)) Y(i+1)=(（1/（1+2^(-2i)））^0.5)●(Y(i)+S(i)X(i)2^(-i)) 其中（1/（1+2^(-2i)））^0.5)称为校模因子，当旋转次数一定时，趋于一个常数，Π（1/（1+2^(-2i)））^0.5)≈0.6073 这样，算法每一步就可以简化为： X(i+1)=0.6073●(X(i)-S(i)Y(i)2^(-i)) Y(i+1)=0.6073●(Y(i)+S(i)X(i)2^(-i)) 从而可以看出，对于移动的角度θ，现在只需要硬件加减法器和移位器就可以算出结果。引入Z，表示i次旋转后相位累加的部分和，则： Z(i+1)=Z(i)-S(i)arctan(2^(-i)) 经过n次旋转之后，Z→0，即与目标角重合，即： X(n)=X1=X0*cos(θ)-Y0*sin(θ) Y(n)=Y1=Y0*cos(θ)+X0*sin(θ)

基于流水线结构的cordic算法的实现

基于流水线结构的cordic 算法的实现 摘要 系统在处理数据的时候，一个指令周期含有多个时钟脉冲，每个脉冲周期由不同的部件完成不同的操作。非流水线结构是指一个指令周期完成以后再接受下一条处理数据的指令；而流水线结构，每个时钟脉冲都接受下一条处理数据的指令，只是不同的部件做不同的事情，就象生产线流水操作一样，并不是等一个或一批产品做完，再接受下一批生产命令，而是每个工序完成以后，立即接受下一批生产任务。这样提高了系统处理数据的速度。 随着超大规模集成电路(Very Large Scale Integrated circuits , VLSI)技术的飞速发展,经常需要用硬件快速和精确地进行三角函数值的计算,而坐标旋转算法(Coordinate Rotational Digital Computer, CORDIC)能够将多种难以用硬件电路直接实现的复杂的三角函数运算分解为统一的加减、移位操作,极大地降低了硬件设计的复杂性。 在现代信号处理中,经常会遇到三角函数、超越函数和坐标转化等问题。传统的实现方法有查找表多项式展开等方法，但是这些方法在精度、速度、简单性和效率方面往往不能兼顾。CORDIC 算法则可以很好地兼顾这几方面的要求。CORDIC算法只使用移位和加减运算，硬件实现简单。使用流水线结构，每级CORDIC使用独立的单元，这样使运算速度非常快。当流水线填满之后，每个时钟周期就会得到一个结果。 从CORDIC算法的基本原理出发，讨论其工作过程以及旋转角的覆盖范围，在此基础上，给出具有流水线结构的FPGA实现方法以及增益因子的大小与流水线级数的确定关系，给出了verilog实现算法，在Quartus6.0调试与仿真，验证采用FPGA实现的CORDIC算法的有效性。

16位CRC算法原理及C语言实现

按字节计算ＣＲＣ unsigned int cal_crc(unsigned char *ptr,unsigned char len) { unsigned int crc; unsigned char da; unsigned int crc_ta[256]={/*CRC余式表*/ 0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7, 0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef, 0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,0x72f7,0x62d6, 0x9339,0x8318,0xb37b,0xa35a,0xd3bd,0xc39c,0xf3ff,0xe3de, 0x2462,0x3443,0x0420,0x1401,0x64e6,0x74c7,0x44a4,0x5485, 0xa56a,0xb54b,0x8528,0x9509,0xe5ee,0xf5cf,0xc5ac,0xd58d, 0x3653,0x2672,0x1611,0x0630,0x76d7,0x66f6,0x5695,0x46b4, 0xb75b,0xa77a,0x9719,0x8738,0xf7df,0xe7fe,0xd79d,0xc7bc, 0x48c4,0x58e5,0x6886,0x78a7,0x0840,0x1861,0x2802,0x3823, 0xc9cc,0xd9ed,0xe98e,0xf9af,0x8948,0x9969,0xa90a,0xb92b, 0x5af5,0x4ad4,0x7ab7,0x6a96,0x1a71,0x0a50,0x3a33,0x2a12, 0xdbfd,0xcbdc,0xfbbf,0xeb9e,0x9b79,0x8b58,0xbb3b,0xab1a, 0x6ca6,0x7c87,0x4ce4,0x5cc5,0x2c22,0x3c03,0x0c60,0x1c41, 0xedae,0xfd8f,0xcdec,0xddcd,0xad2a,0xbd0b,0x8d68,0x9d49, 0x7e97,0x6eb6,0x5ed5,0x4ef4,0x3e13,0x2e32,0x1e51,0x0e70, 0xff9f,0xefbe,0xdfdd,0xcffc,0xbf1b,0xaf3a,0x9f59,0x8f78, 0x9188,0x81a9,0xb1ca,0xa1eb,0xd10c,0xc12d,0xf14e,0xe16f, 0x1080,0x00a1,0x30c2,0x20e3,0x5004,0x4025,0x7046,0x6067, 0x83b9,0x9398,0xa3fb,0xb3da,0xc33d,0xd31c,0xe37f,0xf35e, 0x02b1,0x1290,0x22f3,0x32d2,0x4235,0x5214,0x6277,0x7256, 0xb5ea,0xa5cb,0x95a8,0x8589,0xf56e,0xe54f,0xd52c,0xc50d, 0x34e2,0x24c3,0x14a0,0x0481,0x7466,0x6447,0x5424,0x4405, 0xa7db,0xb7fa,0x8799,0x97b8,0xe75f,0xf77e,0xc71d,0xd73c, 0x26d3,0x36f2,0x0691,0x16b0,0x6657,0x7676,0x4615,0x5634,

CORDIC算法VHDL实现

LIBRARY ieee; USE ieee.std_logic_1164.all; USE ieee.std_logic_arith.all; USE ieee.STD_LOGIC_UNSIGNED.all; ENTITY cordicCOS_SIN IS PORT ( clk :IN std_logic; deg_in :IN std_logic_vector (13 downto 0); cos :OUT std_logic_vector(15 downto 0); sin :OUT std_logic_vector(15 downto 0) ); END cordicCOS_SIN; architecture rlt_cordicCOS_SIN of cordicCOS_SIN is constant c1:std_logic_vector(13 downto 0):=CONV_STD_LOGIC_VECTOR(4096,14); constant c2:std_logic_vector(13 downto 0):=CONV_STD_LOGIC_VECTOR(2048,14); constant c3:std_logic_vector(13 downto 0):=CONV_STD_LOGIC_VECTOR(1209,14); --arctan(1/2) constant c4:std_logic_vector(13 downto 0):=CONV_STD_LOGIC_VECTOR(639,14); --arctan(1/4) --constant x0:std_logic_vector(15 downto 0):=CONV_STD_LOGIC_VECTOR(19895,16); signal x0 :std_logic_vector(15 downto 0); signal y1,x1 :std_logic_vector(15 downto 0); signal y2,x2 :std_logic_vector(15 downto 0); signal y3,x3 :std_logic_vector(17 downto 0); signal y4,x4 :std_logic_vector(19 downto 0); signal p1,p2,p3,p4 :std_logic_vector(13 downto 0); begin x0 <= conv_std_logic_vector(26980,16); ---------------------------------step 1------------------------------------ process(clk) begin if rising_edge(clk) then if deg_in(13) ='1' then y1 <= x"0000" -x0; else y1 <= x0; end if;

CRC校验实用程序库(一)

CRC校验实用程序库(一) 在数据存储和数据通讯领域，为了保证数据的正确，就不得不采用检错的手段。在诸多检错手段中，CRC是最著名的一种。CRC的全称是循环冗余校验，其特点是:检错能力极强，开销小，易于用编码器及检测电路实现。从其检错能力来看，它所不能发现的错误的几率仅为0.0047%以下。从性能上和开销上考虑，均远远优于奇偶校验及算术和校验等方式。因而，在数据存储和数据通讯领域，CRC无处不在:著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC-CCITT，ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。 CRC的本质是模-2除法的余数，采用的除数不同，CRC的类型也就不一样。通常，CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式如表1所示。 @@10A08800.GIF;表1.最常用的CRC码及生成多项式@@ 由于CRC在通讯和数据处理软件中经常采用，笔者在实际工作中对其算法进行了研究和比较，总结并编写了一个具有最高效率的CRC通用程序库。该程序采用查表法计算CRC，在速度上优于一般的直接模仿硬件的算法，可以应用于通讯和数据压缩程序。 通常的CRC算法在计算一个数据段的CRC值时，其CRC值是由求解每个数值的CRC值的和对CRC寄存器的值反复更新而得到的。这样，求解CRC的速度较慢。通过对CRC算法的研究，我们发现:一个8位数据

加到16位累加器中去，只有累加器的高8位或低8位与数据相作用，其结果仅有256种可能的组合值。因而，我们可以用查表法来代替反复的运算，这也同样适用于CRC32的计算。本文所提供的程序库中，函数crchware是一般的16位CRC的算法；mk-crctbl用以在内存中建立一个CRC数值表；crcupdate用以查表并更新CRC累加器的值；crcrevhware和crcrevupdate是反序算法的两个函数；BuildCRCTable、CalculateBlockCRC32和UpdateCharac terCRC32用于CRC32的计算。 /*CRC.C——CRC程序库*/ #defineCRCCCITT0x1021 #defineCCITT-REV0x8408 #defineCRC160x8005 #defineCRC16-REV0xA001 #defineCRC32-POLYNOMIAL0xEDB88320L /*以上为CRC除数的定义*/ #defineNIL0 #definecrcupdate(d,a,t)*(a)=(*(a)>8)^(d)]; #definecrcupdate16(d,a,t)*(a)=(*(a)>>8^(t)(*(a)^(d))&0x00ff]) /*以上两个宏可以代替函数crcupdate和crcrevupdate*/ #include #include

CRC16 三种算法及c实现

标准CRC生成多项式如下表： 名称生成多项式简记式* 标准引用 CRC-4 x4+x+1 3 ITU G.704 CRC-8 x8+x5+x4+1 0x31 CRC-8 x8+x2+x1+1 0x07 CRC-8 x8+x6+x4+x3+x2+x1 0x5E CRC-12 x12+x11+x3+x+1 80F CRC-16 x16+x15+x2+1 8005 IBM SDLC CRC16-CCITT x16+x12+x5+1 1021 ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS CRC-32 x32+x26+x23+...+x2+x+1 04C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS CRC-32c x32+x28+x27+...+x8+x6+1 1EDC6F41 SCTP 生成多项式的最高位固定的1，故在简记式中忽略最高位1了，如0x1021实际是0x11021。 I、基本算法（人工笔算）： 以CRC16-CCITT为例进行说明，CRC校验码为16位，生成多项式17位。假如数据流为4字节：BYTE[3]、BYTE[2]、BYTE[1]、BYTE[0]； 数据流左移16位，相当于扩大256×256倍，再除以生成多项式0x11021，做不借位的除法运算（相当于按位异或），所得的余数就是CRC校验码。 发送时的数据流为6字节：BYTE[3]、BYTE[2]、BYTE[1]、BYTE[0]、CRC[1]、CRC[0]； 注意：使用长除法进行计算式，需要将除数多项式与预置位0x0000或0xFFFF异或以后再进行计算。II、计算机算法1（比特型算法）： 1)将扩大后的数据流（6字节）高16位（BYTE[3]、BYTE[2]）放入一个长度为16的寄存器； 2)如果寄存器的首位为1，将寄存器左移1位(寄存器的最低位从下一个字节获得)，再与生成多项式的简记式异或； 否则仅将寄存器左移1位(寄存器的最低位从下一个字节获得)； 3)重复第2步，直到数据流（6字节）全部移入寄存器； 4)寄存器中的值则为CRC校验码CRC[1]、CRC[0]。

cordic算法详解

CORDIC The calculus courses provide us with tools to compute the values of trigonometric functions,for example,via series expansions, polynomial,and rational function approximations.However,these implementations tend to require multiplication and division operations that make them expensive in hardware. In contrast,CORDIC(COrdinate Rotation Digital Computer)algorithms need only adders,shifters and comparators for computing a wide range of elementary functions.The method is especially e?cient when?xed point implementations of signal processing algorithms on hardware are considered.For example,CORDIC is extremely popular in hardware accelerators and also in SIMD(Single-Instruction Multiple Data)realizations.Furthermore,almost all function calculators employ CORDIC. Intel processors used CORDIC for trigonometric functions till80486. CORDIC is a good choice for hardware solutions such as FPGA in which cost(gate count)minimization is more important than throughput maximization.In software implementations CORDIC enables most of the code and data be shared between routines for trigonometric and hyperbolic functions,helping to conserve memory.CORDIC algorithm is often used to implement rotations needed in modulators and demodulators. CORDIC algorithm was introduced in1959by Volder for implementing a real-time navigation computer for aeronautical appli-cations.The algorithm was initially formulated for computing the values of trigonometric functions.In early1970s the CORDIC techniques were extended to exponential,logarithm,forward and inverse circular and hyperbolic functions,ratios and square roots(Walther1971).Its concepts have also been developed to include calculation of the Discrete Fourier Transform(Despain 1974).More recently(Bajard et al1994)e?cient hardware technique known as BKM for computing complex exponentials and trigonometric functions was proposed and has since been very widely applied. 1

CRC算法原理

CRC校验算法 CRC(Cyclic Redundancy Check)循环冗余校验是常用的数据校验方法，讲CRC算法的文章很多，之所以还要写这篇，是想换一个方法介绍CRC算法，希望能让大家更容易理解CRC 算法。 先说说什么是数据校验。数据在传输过程（比如通过网线在两台计算机间传文件）中，由于传输信道的原因，可能会有误码现象（比如说发送数字5但接收方收到的却是6），如何发现误码呢？方法是发送额外的数据让接收方校验是否正确，这就是数据校验。最容易想到的校验方法是和校验，就是将传送的数据(按字节方式)加起来计算出数据的总和，并将总和传给接收方，接收方收到数据后也计算总和，并与收到的总和比较看是否相同。如果传输中出现误码，那么总和一般不会相同，从而知道有误码产生，可以让发送方再发送一遍数据。 CRC校验也是添加额外数据做为校验码，这就是CRC校验码，那么CRC校验码是如何得到的呢？ 非常简单，CRC校验码就是将数据除以某个固定的数（比如ANSI-CRC16中，这个数是0x18005），所得到的余数就是CRC校验码。 那这里就有一个问题，我们传送的是一串字节数据，而不是一个数据，怎么将一串数字变成一个数据呢？这也很简单，比如说2个字节B1，B2,那么对应的数就是(B1<<8)+B2；如果是3个字节B1，B2，B3，那么对应的数就是((B1<<16)+(B2<<8)+B3),比如数字是0x01,0x02, 0x03，那么对应的数字就是0x10203；依次类推。如果字节数很多，那么对应的数就非常非常大，不过幸好CRC只需要得到余数，而不需要得到商。 从上面介绍的原理我们可以大致知道CRC校验的准确率，在CRC8中出现了误码但没发现的概率是1/256，CRC16的概率是1/65536，而CRC32的概率则是1/2^32，那已经是非常小了，所以一般在数据不多的情况下用CRC16校验就可以了，而在整个文件的校验中一般用CRC32校验。 这里还有个问题，如果被除数比除数小，那么余数就是被除数本身，比如说只要传一个字节，那么它的CRC就是它自己，为避免这种情况，在做除法之前先将它移位，使它大于除数，那么移多少位呢？这就与所选的固定除数有关了，左移位数比除数的位数少1，下面是常用标准中的除数： CRC8：多项式是X8+X5+X4+1，对应的数字是0x131，左移8位

CORDIC算法在FPGA中的实现

微　处　理　机 M I CROPROCESS ORS ?大规模集成电路设计、制造与应用? C OR D I C 算法在FPG A 中的实现 王智霞,王广生 (北京工业大学电控学院,北京100022) 摘　要:CORD I C 算法是在许多角度计算方面有着广泛应用的经典算法,通过考虑FPG A 的结构、精度局限和速度要求,采用流水线技术(p i peline ),在FPG A 上用CORD I C 算法实现了对于大吞吐量数据的向量倾角的计算,并对实际应用中内部步骤寄存器精度的选取给出了较为详细的方法。 关键词:坐标旋转数字计算;FPG A;流水线中图分类号:T N4 文献标识码:B 文章编号:1002-2279(2007)01-0004-04 FP GA B a sed R ea li za ti o n o f CO RD I C A l go rithm WANG Zhi -xia,WANG Guang -sheng (B eijing university of technology,B eijing 100022,China ) Abstract:CORD I C algorithm is a classic algorith m with many app licati ons .Considering the archi 2tecture,p recisi on and s peed of FPG A ,the p i peline technol ogy is used in computing large number of vect or angle values .This article p r ovides the way of confir m the wide of inner p r ocessing register . Key words:CORD I C;FPG A;Pi peline 1　引　言 FPG A 以其灵活性和使用方便在现今的数字领 域已经得到了广泛的应用。但FPG A 实现数字系统也有其自身的局限性,其一是器件资源的门阵列规模的限制,其二是单元延迟限制,所以,这就需要设计者充分考虑器件的实际工作能力。 角度的旋转计算在数字领域尤其是数字通信领域是一种应用非常广泛的计算,如果用传统的除法器、乘法器等计算方法,需要占用大量的FPG A 资源,这样就不能满足设计者的要求,需要设计者考虑其他的算法实现这种类型的计算。 CORD I C 算法在硬件电路的实现上只用到了加法器和移位器,这样就大大节约了FPG A 的资源,从而可以满足设计者的要求。 2　CORD I C 算法简介 CORD I C (Coordinate Rotati on D igital Computer ), 又名:坐标旋转数字计算,是J.Voider 等人于1959 年在设计美国航空导航控制系统的过程中提出来的 一种算法。下面就简要地介绍一下CORD I C 算法的 基本数学思想。 如图1所示,向量逆时针旋转θ度角得到 向量OB ,这个关系可以用矩阵表示如式1[1] : X j Y j = cos θ　-sin θsin θ　cos θX i Y i =cos θ1 -tan θ tan θ 1X i Y j (1) 图1　向量旋转坐标图 如果假设θ是由n 个θn 角度叠加而成的,那么根据式( 1)得出每一步的叠加操作需要按照式(2)行 X n +1Y n +1=cos θn 1 -tan θn tan θn 1X n Y n (2)利用式2经过n 步叠加可以表示由向量旋 转到向量OB ,如下表示: X j Y j =cos θ0?cos θ1...cos θn 1 -tan θ0tan θ0 1...1 - tan θn tan θn 1X i Y i (3)作者简介:王智霞(1980-),女,北京人,硕士研究生,主研方向:嵌入式系统设计与实现,大规模集成电路系统设计,数字通信。 收稿日期:2005-02-23 第1期 2007年2月 　 　 No .1Feb .,2007

cordic算法详解

cordic算法详解 转载自小一休哥的文章： https://www.wendangku.net/doc/048392758.html,/qq_39210023/article/details/77456031 目前，学习与开发FPGA的程序员们大多使用的是Verilog HDL语言（以下简称为Verilog），关于Verilog的诸多优点一休哥就不多介绍了，在此，我们将重点放在Verilog的运算操作上。 我们都知道，在Verilog中，运算一般分为逻辑运算（与或非等）与算术运算（加减乘除等）。而在一开始学习Verilog 时，老司机一定会提醒我们，“切记，千万别用‘/’除、‘%’取模（有的也叫取余）和‘**’幂。”这话说的不无道理，因为这三个运算是不可综合的。但，需清楚理解的是，不可综合的具体意思为不能综合为简单的模块，当我们在程序中调用了这些运算时，‘/’除和‘%’取模在Quartus软件中是可以综合的，因此可以正常调用运行，但是会消耗一些逻辑资源，而且会产生延时，即这两个运算的处理时间会很长，可能会大于时序控制时钟的单周期时间。此时呢，我们会建议你调用IP 核来实现运算操作，虽然这样也会消耗许多逻辑资源，但产生的延时相对较小满足了你基本的需求。 问题好像迎刃而解了，可是仔细一想，除了这些运算，我们

还剩下什么？对呀，三角函数，反三角函数，对数函数，指数函数呢，这些函数我们在高中就学习了的呀，难道在FPGA 中就没有用武之地吗？有人会说，查找表呗，首先将某个运算的所有可能的输入与输出对一一罗列出来，然后放进Rom 中，然后根据输入查表得到输出。这个方法虽然有效的避免了延时问题，却是一个十分消耗资源的方法，不适合资源紧张的设计。那么，就真的没有办法了吗？ 答案就是咱们今天的标题了，CORDIC，而且CORDIC是一个比较全能的算法，通过这一原理，我们可以实现三角函数，反三角函数，对数函数，指数函数等多种运算。接下来，一休哥就带领大家来学习CORDIC的原理吧。（题外话：请相信一休哥，本文不会让你感到太多痛苦~） 本文将分三个小部分来展开介绍： 1、CORDIC的基本原理介绍 2、CORDIC的具体操作流程介绍 3、CORDIC的旋转模式——Verilog仿真 本文涉及到的全部资料链接：

CRC校验算法

CRC(Cyclic Redundancy Check)循环冗余校验是常用的数据校验方法，讲CRC 算法的文章很多，之所以还要写这篇，是想换一个方法介绍CRC算法，希望能让大家更容易理解CRC算法。 先说说什么是数据校验。数据在传输过程（比如通过网线在两台计算机间传文件）中，由于传输信道的原因，可能会有误码现象（比如说发送数字5但接收方收到的却是6），如何发现误码呢？方法是发送额外的数据让接收方校验是否正确，这就是数据校验。最容易想到的校验方法是和校验，就是将传送的数据(按字节方式)加起来计算出数据的总和，并将总和传给接收方，接收方收到数据后也计算总和，并与收到的总和比较看是否相同。如果传输中出现误码，那么总和一般不会相同，从而知道有误码产生，可以让发送方再发送一遍数据。 CRC校验也是添加额外数据做为校验码，这就是CRC校验码，那么CRC校验码是如何得到的呢？ 非常简单，CRC校验码就是将数据除以某个固定的数（比如ANSI-CRC16中，这个数是0x18005），所得到的余数就是CRC校验码。 那这里就有一个问题，我们传送的是一串字节数据，而不是一个数据，怎么将一串数字变成一个数据呢？这也很简单，比如说2个字节B1，B2,那么对应的数就是(B1<<8)+B2；如果是3个字节B1，B2，B3，那么对应的数就是((B1<<16)+(B2<<8)+B3),比如数字是0x01,0x02,0x03，那么对应的数字就是0x10203；依次类推。如果字节数很多，那么对应的数就非常非常大，不过幸好CRC只需要得到余数，而不需要得到商。 从上面介绍的原理我们可以大致知道CRC校验的准确率，在CRC8中出现了误码但没发现的概率是1/256，CRC16的概率是1/65536，而CRC32的概率则是1/2^32，那已经是非常小了，所以一般在数据不多的情况下用CRC16校验就可以了，而在整个文件的校验中一般用CRC32校验。 这里还有个问题，如果被除数比除数小，那么余数就是被除数本身，比如说只要传一个字节，那么它的CRC就是它自己，为避免这种情况，在做除法之前先将它移位，使它大于除数，那么移多少位呢？这就与所选的固定除数有关了，左移位数比除数的位数少1，下面是常用标准中的除数： CRC8：多项式是X8+X5+X4+1，对应的数字是0x131，左移8位 CRC12：多项式是X12+X11+X3+X2+1，对应的数字是0x180D，左移12位 CCITT CRC16：多项式是X16+X12+X5+1，对应的数字是0x11021，左移16位 ANSI CRC16：多项式是X16+X15+X2+1，对应的数字是0x18005，左移16位 CRC32：多项式是 X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1，对应数字是 0x104C11DB7，左移32 因此，在得到字节串对应的数字后，再将数字左移M位（比如ANSI-CRC16是左移16位），就得到了被除数。 好了，现在被除数和除数都有了，那么就要开始做除法求CRC 校验码了。CRC除法的计算过程与我们笔算除法类似，首先是被除数与除数高位对齐后，被除数减去除数，得到了差，除数再与差的最高位对齐，进行减法，然

CRC原理 及算法总结

引言 CRC 的全称为Cyclic Redundancy Check ，中文名称为循环冗余校验。它是一类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域广泛地用于实现差错控制。实际上，除数据通信外，CRC 在其它很多领域也是大有用武之地的。例如我们读软盘上的文件，以及解压一个ZIP 文件时，偶尔会碰到“Bad CRC ”错误，由此它在数据存储方面的应用可略见一斑。 CRC 的算法与实现，对原理只能捎带说明一下。若需要进一步了解线性码、分组码、循环码、纠错编码等方面的原理，可以阅读有关资料。 利用CRC 进行检错的过程可简单描述为： k 位二进制码序列，以一定的规则产生一个校验用的r 位监督码(CRC 码)，附在原始信息后边，构成一个新的二进制码序列数共k+r 位， 然后发送出去。 CRC 码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”。 1 代数学的一般性算法 在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如 1100101 表示为 1·x^6+1·x^5+0·x^4+0·x^3+1·x^2+0·x+1，即 x^6+x^5+x^2+1。 设: 编码前的原始信息多项式为P(x)，P(x)的最高幂次加1等于k ； 生成多项式为G(x)，G(x)的最高幂次等于r ； CRC 多项式为R(x)； 编码后的带CRC 的信息多项式为T(x)。 发送方编码方法： 将P(x)乘以x^r(即对应的二进制码序列左移r 位)，再除以G(x)，所得余式即为R(x)。用公式表示为 ()()()r T x x P x R x =+ 接收方解码方法： 将T(x)除以G(x)，如果余数为0，则说明传输中无错误发生，否则说明传输有误。 举例来说，设信息码为1100，生成多项式为1011，即P(x)=x3+x2，G(x)=x3+x+1，计算CRC 的过程为 ()()()()3326532333 111 r x x x x P x x x x x x x G x x x x x x x ++==+++++++++= 即 R(x)=x 。注意到G(x)最高幂次r=3，得出CRC 为010。

CRC 三种检验方法

计算机网络报告 CRC 三种检验方法 CRC 三种检验方法： //CRC16校验在通讯中应用广泛，这里不对其理论进行讨论，只对常见的3种//实现方法进行测试。方法1选用了一种常见的查表方法,类似的还有512字//节、256字等查找表的，至于查找表的生成,这里也略过。 // ---------------- POPULAR POL YNOMIALS ----------------

// CCITT: x^16 + x^12 + x^5 + x^0 (0x1021) // CRC-16: x^16 + x^15 + x^2 + x^0 (0x8005) #define CRC_16_POL YNOMIALS 0x8005 // -------------------------------------------------------------- // CRC16计算方法1:使用2个256长度的校验表 // -------------------------------------------------------------- const BYTE chCRCHTalbe[] = // CRC 高位字节值表{ 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40 }; const BYTE chCRCLTalbe[] = // CRC 低位字节值表{ 0x00, 0xC0, 0xC1, 0x01, 0xC3, 0x03, 0x02, 0xC2, 0xC6, 0x06, 0x07, 0xC7, 0x05, 0xC5, 0xC4, 0x04, 0xCC, 0x0C, 0x0D, 0xCD, 0x0F, 0xCF, 0xCE, 0x0E, 0x0A, 0xCA, 0xCB, 0x0B, 0xC9, 0x09, 0x08, 0xC8, 0xD8, 0x18, 0x19, 0xD9, 0x1B, 0xDB, 0xDA, 0x1A, 0x1E, 0xDE, 0xDF, 0x1F, 0xDD, 0x1D, 0x1C, 0xDC, 0x14, 0xD4, 0xD5, 0x15, 0xD7, 0x17, 0x16, 0xD6, 0xD2, 0x12, 0x13, 0xD3, 0x11, 0xD1, 0xD0, 0x10, 0xF0, 0x30, 0x31, 0xF1, 0x33, 0xF3, 0xF2, 0x32, 0x36, 0xF6, 0xF7, 0x37, 0xF5, 0x35, 0x34, 0xF4, 0x3C, 0xFC, 0xFD, 0x3D, 0xFF, 0x3F, 0x3E, 0xFE, 0xFA, 0x3A, 0x3B, 0xFB, 0x39, 0xF9, 0xF8, 0x38, 0x28, 0xE8, 0xE9, 0x29, 0xEB, 0x2B, 0x2A, 0xEA, 0xEE, 0x2E, 0x2F, 0xEF,