一种有限域上除法快速实现算法-硬件开发文档类资源-CSDN下载

一种有限域上除法快速实现算法

所需积分/C币：30 2017-11-11 21:26:46 495KB PDF
11

收藏
举报

有助于crc校验的理解，从有限域的整体理解crc校验，有公式相关的论证以及代码流程
做次:如果u<l那么 p+ -g a q q a l←i-i 与此同时如果v>v那么v←v-v否则v←v+p-v b 4←l qb)v 如果v为偶数v←ν否则v←p+ν 这样变换后u就一定有一个元素减小∫。同样,第二如果<u2那么步是用a做r的带余除法得a=qr+r,对u实行初等变 l!←l-ll 换如果v>v那么v←-v否则v←v+p-y + g r+r-g 转步与此同时 GF(2)下除法算法描述输入:ab∫;输出ba;其中∫是域的生成多项式, 此时a乂减少一元素,这实际是欧儿里得转相除法。常数项为 f 6, v a和p互素总能变为,的形式,或”的形式,如果 h 如果u=,返回ba 是第二种情况,最后再对u和ν同时做次第三种初等变如果做 ;其中换就变成第·种情况了。此时ν的第·个元素即为ba。这表示作为多项式时的多项式次数个算法不止对GF)可行,对GF(2)也适用,此时,p 如果a=u那么无逆,不存在ba 用GF(2)的生成多项式f(x)代替,大小用多项式次数来比较即可。如果l+<u那么 l←l!<< 表示左移一·位操作逐步消去高位的有限域除法如果ν+ ∫那么ν←<< 上节给出的算法因要做大数的除法,不适合硬件实现。否则v←ν<⊕∫,⊕为异或运算本节对上节算法进行改进,给出逐步消去高位的有限域玢 n=n十转步法实现方法。该改进方法只需加减、异或和移位运算,不做次:如果= 那么使用乘除运算,因而适合硬件快速实现 ←tt,←vEp 表小向右移位一位 GF(⑩)下除法算法描述如果ν为偶数v←ν>否则输入:abp;输出ba;其中p为有限域的特征为 v←f⊕v>> 齐素数。如果u=u那么 l(a,l∈p,ν←b,← ←l田,v←v⊕v转步。如果n 返回ba=v 这实际上两种有限域的算法都是对u 和如果u>u做tlv4p 如果u=那么无逆,不存在ba 做一系列的相同的初等变换如果u<u那么变换的日的是逐步减小向量u的分量值GF(p)或向量分量的次数(GF(2”),最后达到u的个分量变为1,同如果ν<p那么v←v 时向量ν的相应分量就是ba。与欧儿里的银转相除一样, 否则ν←v-p 逐步消去每个元素的高位,缩减位串长度,最后达到目标。这和算法不只限于有限域,第一种算法也可在整数环 n=n 转步的仁意剩余类环上操作;第ˉ种算法可以推)到GH(2)的 31 21994-2017ChinaacAdcmicjOUrnalElcctronicPublishingHousc.ALlrightsrescrvcd.http://www.cnki.nct 多项式重模多项式环上操作。仿真实验用模多项式乘功能验证模多项式除法的正确性算法通过用语言编程,在下通过了功能仿真。用和综合布线后,用仿真也通过,且用通过以上验证说明GF(/2)卜的模多项式模遊运算和的系列芯片上可模除运算是正确的,同理GF(2)下的结果也是正确的。以达到徹一次有限域FG(p)下的m位除法需要2m个时钟周期,例如位除法需要时钟周期, 结束语每时钟周期为总共用。以下是所给出的算法方法可以在GF)和GF(2")两类不同位运算在下仿真输出的实例结果: 的有限域中实现,一步即可完成有限域的除法,运算量和求逆运算的运算量相当,省去∫乘法,较之文献中的 GF()运算验证方法提高了运算效率整数环求逆实例参考文献 Acta Scientiarum Naturalium Universitatis Pekinensis 整数环模除实例 IEEE Trans Computers Modern electi 用乘法验证如下: 通过验证说明整数环上的大数模除法运算结果正确 Computer engineering 齿而GF)下的模除运算是正确的用同样的数,作为GF(2)的多项式运算结果如下 GF(y)运算验证 Computer engineering and applications 模多项式求逆模多项式除法 21994-2017ChinaacAdcmicjOUrnalElcctronicPublishingHousc.ALlrightsrescrvcd.http://www.cnki.nct

...展开详情

有限域上除法

立即下载