bch三种译码算法之比较

《bch三种译码算法之比较》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、BCH译码中三种译码算法之比较北京大学微电子系SoC实验室BCH三种译码算法之比较龙进凯崔小欣北京大学信息科学技术学院微电子学研究院摘要本文从BCH译码中错位多项式的求解这一关键步骤入手，详细分析了彼得森算法（Peterson）、伯利坎普算法（Berlekamp）和欧几里得算法（Euclidean）这三种译码算法的数学原理，并给出了三种算法相应的硬件实现。文章的最后还给出了三种算法的实现比较，希望能够对BCH译码工作起到一定的参考价值。关键词：错位多项式，彼得森算法，伯利坎普算法，欧几里得算法1引言二进制BCH译码一般来说分为四个步骤，如图1所示。首先根据接收到的码字R(x)来计算伴随多项

2、式S(x)，然后通过伴随多项式S(x)的系数S1，S2，…,S2t(t为最多可纠正的错误个数)来计算错误位置多项式σ(x)，最后再根据错误位置多项式σ(x)的系数σ1，σ2，…,σt利用Chien搜索算法来求出错误位置并对接收码字进行纠错译码。图1译码器结构框图在上述的四个步骤中，决定BCH译码器的复杂性和速度的关键在于错位多项式σ(x)系数的计算。因此，本文着重对错位多项式σ(x)的各种计算方法以及相应的硬件实现展开讨论。2算法描述2.1彼得森（Peterson）译码算法定义错误图案为，则有6BCH译码中三种译码算法之比较北京大学微电子系SoC实验室（2.11）若传输过程中有个错误，则

3、对于，有（2.12）令，则有（2.13）称为错误位置。定义错误位置多项式（2.14）的根的倒数为。因此需要求出错误位置多项式的系数。的系数可以通过解下面的方程组得出：（2.15）这种通过直接解方程组来得到错位多项式系数的方法称为彼得森(Peterson)译码算法。假设某种码的纠错能力t=2，则方程（2.1-5）变为（2.16）从而解得，2.2伯利坎普（Berlekamp）译码算法令（2.21）且满足6BCH译码中三种译码算法之比较北京大学微电子系SoC实验室称式2.2-1为Berlekamp关键方程。满足方程2.2-1的解不唯一，而由最小距离译码原理，求得的应该是对应发生错误码

4、元最少的错误图案，即是次数最低的解，记作。求一个，使得（2.22）满足解关键方程的迭代步骤如下：1)设；2)若，则若，则其中，且有最大值；3)如果，则迭代结束，否则执行4)；4)令，计算回到2)。2.3欧几里得（Euclidean）译码算法定义错误值多项式（2.31）且满足6BCH译码中三种译码算法之比较北京大学微电子系SoC实验室式2.3-1的等价表达为（2.32）其中，是除以的商，是余数。可由下面两式开始迭代计算得到：具体迭代步骤如下：1)初始化，迭代次数；，；，；2)如果，则停止迭代；否则就进行以下运算：a)，；b)，；，；c)如果，；否则，；d)；3)迭代次数，返回2）。当进

5、行完2t次迭代计算后，的个系数中的高个为错误位置多项式的个系数。3硬件实现下面我们以（15,7）二元BCH码（最多可以纠正2个随机错误）为例，将以上的三种译码算法分别用硬件描述语言加以实现，以供比较。1）对于彼得森（Peterson）算法，如果输入的伴随多项式的系数S1=S2=S3=S4=0，则表示接收到的码字没有错误，那么相应的错位多项式的系数σ1=σ2=0；有一个或者两个错误时的情况如下：6BCH译码中三种译码算法之比较北京大学微电子系SoC实验室2）对于改进的伯利坎普（Berlekamp）算法，有一个或者两个错误时的情况如下：3）对于欧几里得（Euclidean）算法，有一个或者两个

6、错误时的情况如下：4分析比较6BCH译码中三种译码算法之比较北京大学微电子系SoC实验室从以上的仿真结果可以看出，对于三种算法，同样的一组伴随多项式的系数得到了相同的错位多项式的系数；但是三种算法所花费的计算时间是不一样的。Peterson算法对于三种情况（接收码字没有错误、有一个错误、有两个错误）来说计算时间都是相等的，都只要经过2拍就能得到结果；Berlekamp算法对于接收码字没有错误或者只有一个错误时，也只需要2拍就能得到结果，但是对于两个错误，该算法则需要（t+e+2=6）拍；而Euclidean算法对于接收码字有一个或两个错误的情况则分别需要（2t+4=8）拍和（4t+7=15

7、）拍来得到结果。对三种算法的硬件描述进行FPGA综合，结果如下（所选器件为XilinxVirtex2:XC2V40:CS144:-6）：1）三种算法在该器件上可以达到的最高频率如下表所示：算法RequestedFrequencyEstimatedFrequency彼得森（Peterson）算法250.0MHz259.5MHz伯利坎普（Berlekamp）算法120.0MHz121.0MHz欧几里得（Euclidean）算