RS的BM迭代譯碼算法

2024年2月15日發(作者：愛情的詩)

BM迭代譯碼算法的基本原理

時域上的RS譯碼的關鍵在于求解錯誤位置多項式,1966年伯利坎普（Berlekamp）提出了可以由伴隨式計算錯誤位置多項式的迭代譯碼算法，這極大地加快了求解錯誤位置多項式的速度，該方法簡單且易于實現，從而從工程上解決了RS譯碼的問題；1969年梅西（Masy）指出了該算法與序列的最短線形移位寄存器綜合之間的關系，并進行了簡化，因此，此譯碼算法就稱為BM迭代譯碼算法。

如果由接收碼組已經求出了伴隨式S=［S1,S2,…,S2t］,其中，t為RS碼的糾錯距離,記S(x)=1+

上式即為求解錯誤位置多項式的關鍵方程，且它其實說明了S(x)σ(x)的最高次數不會大于2t。在上式中，S(x)是已知的，因此，可以利用上式進行迭代。先人為設定σ(x)和ω(x)的初始值，然后以此初始值表示下一次迭代的結果，并使得下一迭代結果的次數不減，如此反復迭代求出滿足(1)式的方程即可。由于每一次迭代都使得σ(x)和ω(x)的次數不減，故迭代至第j步時，應有：

通常，滿足(2)式的每一步迭代都不是唯一的，因此必須對迭代過程加以條件限制。

在m進制無記憶離散對稱信道中，如果信道轉移概率p<1/m，則信道產生錯誤個數少的可能性最大，即σ(x)次數越低的可能性越大。故如果每一次迭代都能保證求的σj(x)次數最低，且滿足此時的譯碼結果就是滿足譯碼錯誤概率最小的最大似然譯碼，并且此時的解是唯一的。

其中i是j前面的某一行，且滿足最大，這樣能保證每次迭代總是使σ(x)的次數最小化。因此，令j=-1和0，得到兩組初始值，利用(3)式求出dj，再結合(４)式和(５)式即可得到下一步的結果。迭代步驟如下：

否則，由(4)式和(5)式求出σj+1（x)、ωj+1(x)，然后進行下一次迭代。

FPGA實現及調試

實現電路

該算法的FPGA實現電路如圖1所示。

其中，Syndrome模塊主要完成伴隨式的計算，Dj和Di模塊分別完成dj和dj/di的計算，Iterater模塊則完成迭代的更新及計算，Sj和Oj分別為需要求出的σj(x)和ωj(x)。當同步信號SYN到來時，所有模塊完成初始化，di、Sj和Oj初始化為1。Syndrome模塊求出伴隨式Spoly后串行輸出，同時將此刻的迭代次數Ite－Num輸出，而且當迭代達到要求的次數時，輸出一個CLR信號，在Dj模塊接收到此信號后，將dj置為0，于是后面的輸出不再改變，直到下一同步信號SYN到來；Dj模塊用一組移位寄存器將伴隨式的當前狀態和之前的t個狀態緩存,和當前Sj一起可以求出dj,當dj不為0時，同時計算輸出到J－rank中；為了讓下一步的計算更簡單，Di模塊中計算直接dj/di和rank=j-i的值，di的逆元用一個查找表來完成，同時預設=0，當該值小于J－rank時，將此時的存儲值作相應的更新，同時輸出一個fresh信號以標明這種更新；Iterater模塊在收到fresh信號后進行相應的更新。

在設計過程中，可以將(4)式和(５)式中求滿足i-

一個完整的RS譯碼原理框圖如圖2所示。其中，伴隨式計算電路由輸入的碼組計算出相應的伴隨式，同時將結果送到下一模塊中，該模塊即為實現BM迭代算法的電路。伴隨式經BM迭代后，計算出錯誤位置多項式σ(x),同時也計算出ω(x)。Chien搜索電路則由給定的σ(x)找出錯誤位置，然后控制門打開或者關閉，當該位置有錯時，門打開，輸出該位置上的錯誤值，當該位置沒有錯時，門關閉，此時錯誤值為0。利用σ(x)和ω(x)可以進行錯誤值的計算。因為整個譯碼過程中存在延遲，為使相應的數據互相對齊而必須加入一個移位存儲器。

2.電路調試

經過軟件仿真和硬件電路仿真后，就需要將編譯后的程序下載到實際的FPGA芯片中調試，以驗證實際電路的正確性和可靠性，這是電路設計中的一個重要步驟。軟件仿真主要是產生正確的數據源以驗證硬件電路仿真的結果，軟件仿真主要采用的是Matlab6.1。Matlab是Mathworks公司推出的一套仿真軟件，其數學運算功能非常強大，是工程中一種非常理想的仿真工具，在調試過程中主要是提供調試數據、結果數據，包括中間結果。硬件電路仿真是用電路設計軟件完成電路設計，我們使用的是ALTERA公司的Quartus2.0軟件，再進行編譯、仿真，仿真的結果要與上面Matlab的仿真結果一致。

當上面的驗證完成后，就可將編譯后的程序下載到實際的FPGA芯片中調試，然后用邏輯分析儀隨機抓取數據，保存到文件中，并與Matlab仿真的結果進行比較，如果不正確，則對電路中的每一模塊進行查錯、修改，直到用邏輯分析儀隨機抓取數據完全正確為止，此時可認為電路調試完成。Quartus2.0電路仿真結果如圖3。

圖3的仿真圖給出了在GF(256)內用Quartus2.0進行BM迭代算法的電路仿真結果，為了進行詳細對比，我們將每一次迭代結果都保留下來。經比較，該結果和Matlab仿真的結果完全一致。