一種縮短循環碼糾錯解碼算法的集成電路實現方法及電路的製作方法
2023-04-22 17:25:41 1
專利名稱：一種縮短循環碼糾錯解碼算法的集成電路實現方法及電路的製作方法
技術領域：
本發明涉及編解碼和集成電路技術，特別涉及一種縮短循環碼的糾錯解碼算法的集成電路(ASIC)實現方法及其電路。
其中實現最複雜的是第2、3兩個步驟，下面是兩種常見的實現方法
圖1為經典解碼算法的實現方案原理圖。這種算法為經典的BCH碼解碼算法，對於碼字長度很短的情況，這種方法能夠很好的解碼，而且對於非高速系統也能很好的運用，這種解碼算法的思想是通過輸入的碼流計算出伴隨式S，在計算伴隨式的時候，如果採用的解碼碼字為原碼，那麼，只要按照幾個生成多項式的表達式，對其進行求餘，並作簡單的替換即可完成伴隨式的計算(參見 王新梅 《糾錯碼--原理和方法》西安電子科技大學出版社，1996)，計算完成伴隨式之後，通過迭代解碼算法利用LFSR作迭代運算，即可得到錯誤位置多項式，最後通過解錯誤位置多項式的根可以計算出錯誤位置，計算出an-i是錯誤位置數，那麼碼字中第n-i位置錯誤的，將其與1進行異或進行糾錯。
對於圖1方案，採用的是經典的BCH-3解碼算法，由伴隨式計算錯誤位置多項式的時候通過迭代方法一步一步的進行迭代而得到錯誤位置多項式，這種方法不僅在算法上顯得非常煩瑣，而且運用迭代解碼算法的結果是使得每作一步迭代需要運算較長時間。在求出錯誤位置多項以後，經過解方程的方法求出錯誤位置，然後進行糾錯，這種方法雖然實現起來在硬體資源上不是太多浪費，但是其在作迭代算法時採用線性反饋移位寄存器的方案要得到實現，延時卻非常大，這在高速系統中無法運用。
圖2為在伴隨式計算錯誤位置多項式上有所改進的方案。
此方案在由伴隨式計算錯誤位置多項式的實現上作了改進(參見KraftBCH error-location polynomial decoder，1994)，此方案的目的是為了提高速率，但是在計算中間變量的時候，大量的使用乘法和除法運算，對於有限域上的乘法和除法，要用ASIC來實現是有很大困難的，尤其是對於除法電路，因此這種實現方法的乘除法的實現是通過ROM存儲的方式，通過ROM尋址來得到乘除法的結果的，這對於碼字較短的碼流來說，對於提高速率具有很好的效果，但是如果碼字的長度很長，比如本例的4359，那麼用這種方法來實現所需要的ROM(Read Only Memory只讀存儲器)將是非常大的，對於資源來說顯得過於浪費。
圖2的實現方法主要在由伴隨式計算錯誤位置多項式的一步有所改進，但是在計算判決向量a、b、c和δ1、δ3、δ5用到了大量的乘除法運算，這些乘除法運算都是通過ROM尋址來得到乘除法的結果的，因此採用此方法對於較大數據流的糾錯是非常浪費的，比如實現有限域GF(213)來說，首先將有限域上的各個元素的次冪和各次冪對應的有限域上的值進行存儲，然後在作乘法時先將兩個元素的指數相加，得到一個指數，根據這個指數再到存儲值的ROM查到結果，這種方法雖然從根本上解決了計算δ的速度，但是在資源上形成了很大浪費。
綜上所述，上述譯瑪算法的實現電路複雜，延時大，運算速度低，在電路資源上存在一定浪費。
本發明提出的高效BCH解碼算法的ASIC實現方法，包括如下步驟a、由伴隨式計算單元根據輸入碼字R(x)計算伴隨式S(x)；b、將步驟a所述的各個伴隨式S(x)分別送入相應的伴隨式修正單元進行修正，得到修正後的伴隨式係數P(x)；c、將步驟b所述的各個伴隨式係數P(x)輸入錯誤位置定位單元，根據條件判別式如P13(1+P1+P13)+P3(1+P1+P12+P13+P3)+P5(1+P1)=0]]>分析判斷，在錯誤發生的地方錯誤位置定位單元輸出糾錯比特E(x)；d、將步驟c所述的糾錯比特E(x)和通過K級緩衝器的信息碼元R(x)進行異或運算，輸出糾錯後的碼元V(x)。
實現本發明方法的電路，包括輸入碼元R(x)的K級緩存器、若干伴隨式S(x)計算單元以及異或運算電路，異或運算電路的一個輸入端接K級緩存器輸出，其特徵在於還包括與伴隨式S(x)相應的伴隨式修正單元；以及一個錯誤位置定位單元，它的輸出連接異或運算電路的另一個輸入端，根據輸入的各個伴隨式係數P(x)分析判斷，在錯誤發生的地方輸出糾錯比特E(x)再通過異或運算電路輸出糾正後的碼元V(x)。
現有技術在計算錯誤位置的時候，一般都是先由計算出的伴隨式解出錯誤位置多項式，然後通過Chien搜索算法來求得錯誤位置，本發明巧妙利用循環碼中的牛頓恆等式，直接有伴隨式就得到了錯誤位置，完成錯誤位置的定位，這種計算採用組合邏輯並行實現了乘法的運算，在速度上加快了計算速度，而且由於直接由伴隨式就計算輸出錯誤位置，這樣將錯誤位置多項式的求出和Chien搜索算法用一個電路來實現，解決了現有現有解碼算法電路運算速度不高，延時過大的問題，ASIC實現方案使硬體資源大大節省。
本發明經過RTL級代碼仿真，驗證，證明確實有效，工作正確。
本發明巧妙利用循環碼中的牛頓恆等式，直接有伴隨式就得到了錯誤位置，完成錯誤位置的定位，這種計算採用組合邏輯並行實現了乘法的運算，在速度上加快了計算速度，而且由於直接由伴隨式就計算輸出錯誤位置，這樣將錯誤位置多項式的求出和Chien搜索算法用一個電路來實現，在資源上也是大大的節省。
對於循環碼的伴隨式，有如下牛頓恆等式S1-δ1＝0S3-δ1S2+δ2S1-3δ3＝0S5-δ1S4+δ2S3-δ3S2+δ4S1-5δ5＝0可以解得行列式=111.......1S110.......0S3S21.......0S5S4S3S2....0=11.....1B.....A]]>A=100S2S11S4S3S2B=S1S3S5]]>可以將錯誤圖樣分為三類沒有出現錯誤E(x)＝{0000...0000}出現一個錯誤E(x)＝{100......000，0100....000，00100....000，...000....001}出現兩個錯誤E(x)＝{1100...000，01100...000，001010...000，...00...0011}出現三個錯誤E(x)＝{11100...00，01110...000，0010110...000，...00...0111}
這樣可以得到下面的S判別式沒有錯誤時S1＝0、S3＝0、S5＝0對於BCH-3，當出現一個錯誤時|A|＝0可以解得S3=S13]]>當有兩個或三個錯誤出現時|A|≠0但是θ＝0。
錯誤個數大於三個時，伴隨式計算電路實效，糾錯會出現判斷不對的情況，將出現亂糾錯，但是通過仿真發現當錯誤大於三個以上時，出現亂糾錯的概率大概是1/(！N)(其中N為加入的錯誤數)。對於光纖通信信道來說，其本身出現錯誤的概率就比較小，所以出現BCH解碼失效亂糾錯的情況也是幾乎不可能發生的，因此在光纖傳輸網絡中一般只考慮對電路進行糾錯，而不對電路進行錯誤多少的判斷。下面就是具體的實現方案，以縮短碼(4359，4320)的解碼方法為例介紹本發明對於原碼來說不需要作計算伴隨式和錯誤位置時的修正，直接即可實現，因此主要針對縮短碼進行介紹，此也為本發明對BCH-3進行解碼的一個主要優點。下面仔細進行論述。
1、伴隨式計算對於二進位BCH的解碼，只需要求出S1、S3......S2t-1即可完成糾錯電路的糾錯功能。因此只對S1、S3......S2t-1(t為糾錯能力，本例t為3)進行計算。
本例所用到的碼字為(213＝8192)的縮短碼，縮短位數為8192-4359＝3833位，所以在計算伴隨式時相當於前面3833位全為「0」，也就相當於在計算伴隨式之前首先乘以x3833，然後再作伴隨式的計算，由於計算伴隨式時相當於R(x)/m(x)的模，其中
m1(x)＝x13+x4+x3+x+1m3(x)＝x13+x10+x9+x7+x5+x4+1m5(x)＝x13+x11+x8+x7+x4+x+1在計算時乘以x3833相當於乘以x1mod(3833/11)，乘以x11的示意圖，首先計算S1。圖5為伴隨式S1的計算電路實例，由本原多項式可以得到伴隨式的計算電路.它由寄存器D0-D12和四個異或電路組成，寄存器D11、D12和D0依次串接，寄存器D1和D2串接，寄存器D4--D10依次串接，異或電路1接於D0和D1之間，異或電路2接於D2和D3之間，異或電路3接於D3和D4之間，異或電路4接於D10和D11之間，異或電路1、2、3的另一個輸入端均接寄存器D12的輸出，輸入碼流R(x)接於異或電路4的另一個輸入端，經過4320個循環周期之後，寄存器D12-D0內存儲的值就是伴隨式向量的值。
計算S3和S5採用同樣的方法完成，只是經過4320的循環周期之後，還必須對寄存器中的值進行處理之後才能得到伴隨式S3和S5的值。其變換規則根據有限域乘除法概念可以輕鬆實現，在此不作詳述。
2.乘於a3821實現電路因為每一個錯誤圖樣都分別對應一組伴隨式S1、S3、S5，而且它們之間的關係是由其中某一組伴隨式無輸入循環移位都可以得到另外的伴隨式。在由伴隨式計算錯誤位置的時候，因為是縮短碼，錯誤位置的出現比原碼要晚3833-11＝3822cycle，所以在由伴隨式計算錯誤位置的時候需要乘以一個修正因子a3822(a為有限域上的元素)，因為在計算錯誤位置的時候至少需要一個時鐘的延時(本發明按照一個時鐘周期延時為例)，所以糾錯碼元輸出延時一個時鐘周期，這樣作通過乘以修正因子a3821即可得到伴隨式的值，可使縮短碼錯誤位置根據實際延時需求輸出，糾錯正常。注意上面談到的乘(除)法都是有限域上的乘(除)法，根據有限域上的乘法概念，即可用組合邏輯實現乘法，乘以a3821的具體實現電路如圖6所示。圖6所示的p12-p0為修正後伴隨式係數，該電路由13個異或運算單元(XOR)組成，13個異或運算單元的輸出分別為P12-P0，伴隨式S12-S0連接所述13個異或運算單元的相應輸入端。乘於a3272、a2723方法相同，不再詳細闡述。
P與S的關係P1＝S1a3821、P3＝S3a3272、P5＝S5a2723在進行錯誤位置定位的時候，每一個時鐘Pi(i＝1、3、5)分別乘於ai，然後通過下面的判決條件即可在錯誤發生的地方輸出糾錯比特，讓糾錯比特和信息碼元進行異或即完成了錯誤碼元的糾正。通過牛頓恆等式，在進行糾錯比特計算時可以得到相應下面相應的行列式=111.......1P110.......0P3P21......0P5P4P3P2....0=11......1B..A]]>對於BCH-3，當出現一個錯誤時|A|＝0可以解得P3=P13]]>P1＝1當有兩個或三個錯誤出現時|A|≠0 但是θ′＝0，亦即P3P13]]>，可以通過解行列式得到產生三個錯誤的條件P13(1+P1+P13)+P3(1+P1+P12+P13+P3)+P5(1+P1)=0]]>3、糾錯的電路的實現每一個時鐘周期都可以通過計算得到一組P1、P3、P5，根據上面的關係式就可以得到相應的糾錯比特。在計算過程中需要求解13位二進位數的有限域上的平方以及乘法，根據二進位數有限域上的乘法概念，可以簡化平方電路的算法而不必使用乘法電路來實現平方電路，通過綜合發現憑此方法實現的平方電路大概只有平方電路1/10的面積大小，下面就是P12的實現過程
設P1＝a12a12+a11a11+a10a10+......+a1a+a0，則根據二進位數的加法概念，兩個相同的數相加結果為0，可以得到P1·P1＝a12a24+a11a22+a10a20+....+a1a2+a0，依據二進位數有限域上乘法的概念，依據下表可以將ai(i＞12)的元素用次數小於12的元素來表示，於是可以得到P12相對於P1作如下變換得到a12→a12+a11+a6a11→a12+a10a10→a11+a10+a5a9→a11+a9a8→a10+a9+a4a7→a10+a8a6→a12+a9+a8+a3a5→a9+a7a4→a12+a11+a8+a7+a2a3→a12+a11+a8a2→a7+a1a1→a12+a11+a7a0→a11+a0根據上面的變換可以得到平方電路的實現電路圖7，該電路由13個異或運算單元(XOR)組成，修正後伴隨式係數P12-P0接所述13個異或運算單元的相應輸入端。逐一計算出條件表達式的各個條件以後，根據結果，條件為真產生糾錯比特1，與信息碼元作異或就可完成二進碼的糾錯。如果條件不成立，則糾錯比特不可能出現。
本發明經過RTL級代碼仿真，驗證，效果理想。其運算速度、資源的利用情況與現有技術對比如表一。
表一
表一中t表示最大能糾正的錯誤個數 n表示信息比特+校驗比特k表示碼字的信息比特，需糾錯比特m＝log2n。
權利要求
1.一種高效BCH解碼算法的ASIC實現方法，其特徵在於包括如下步驟a、由伴隨式計算單元根據輸入碼字R(x)計算伴隨式S(x)；b、將步驟a所述的各個伴隨式S(x)分別送入相應的伴隨式修正單元進行修正，得到修正後的伴隨式係數P(x)；c、將步驟b所述的各個伴隨式係數P(x)輸入錯誤位置定位單元，根據條件判別式如P13(1+P1+P13)+P3(1+P1+P12+P13+P3)+P5(1+P1)=0]]>分析判斷，在錯誤發生的地方錯誤位置定位單元輸出糾錯比特E(x)；d、將步驟c所述的糾錯比特E(x)和通過K級緩衝器的信息碼元R(x)進行異或運算，輸出糾錯後的碼元V(x)。
2.實現權利要求1所述方法的電路，包括輸入碼元R(x)的K級緩存器，若干伴隨式S(x)計算單元以及異或運算電路，異或運算電路的一個輸入端接K級緩存器輸出，其特徵在於還包括與伴隨式S(x)相應的伴隨式修正單元；以及一個錯誤位置定位單元，它的輸出連接異或運算電路的另一個輸入端，根據輸入的各個伴隨式係數P(x)分析判斷，在錯誤發生的地方輸出糾錯比特E(x)再通過異或運算電路輸出糾正後的碼元V(x)。
3.根據權利要求2所述的電路，其特徵在於所述的伴隨式修正單元中採用了並行的組合邏輯乘法電路。
4.根據權利要求3所述的電路，其特徵在於所述的組合邏輯乘法電路由13個異或運算單元(XOR)組成，13個異或運算單元的輸出分別為修正後伴隨式係數P12-P0，伴隨式S12-S0連接所述13個異或運算單元的相應輸入端。
5.根據權利要求2所述的電路，其特徵在於所述的錯誤位置定位單元中採用了簡化平方電路。
6.根據權利要求5所述的電路，其特徵在於所述的簡化平方電路由13個異或運算單元(XOR)組成，修正後伴隨式係數P12-P0連接所述13個異或運算單元的相應輸入端。
全文摘要
本發明涉及一種縮短循環碼糾錯解碼算法的集成電路實現方法及電路，其包括如下步驟a、由伴隨式計算單元根據輸入碼字R(x)計算伴隨式S(x)；b、將所述的各個伴隨式S(x)分別送入相應的伴隨式修正單元進行修正，得到修正後的伴隨式係數P(x)；c、將所述各個伴隨式係數P(x)輸入錯誤位置定位單元，根據條件判別式分析判斷，在錯誤發生的地方錯誤位置定位單元輸出糾錯比特E(x)；d、將所述的糾錯比特E(x)和通過K級緩衝器的信息碼元R(x)進行異或運算，輸出糾錯後的碼元V(x)。其電路包括緩存器、若干伴隨式S(x)計算單元、相應的伴隨式修正單元、異或運算電路以及一個錯誤位置定位單元。
文檔編號H03M13/15GK1411151SQ0113329
公開日2003年4月16日 申請日期2001年9月27日 優先權日2001年9月27日
發明者何志闊 申請人:華為技術有限公司