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

所需积分/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

...展开详情
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 签到新秀

    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 分享宗师

    成功上传21个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
    最新推荐