通用并行BCH編碼器結構探究

杜暖男，馬瑩瑩（1.武漢理工大學信息工程學院，武漢，430070 ；.平頂山工業職業技術學院，平頂山，467001）

通用并行BCH編碼器結構探究

杜暖男1，2，馬瑩瑩2
（1.武漢理工大學信息工程學院，武漢，430070 ；2.平頂山工業職業技術學院，平頂山，467001）

本文研究了并行BCH和RS編碼電路的通用設計方法和優化結構。針對信息位長度不能整除并行度的問題，采用在信息位前補零，可以不改變并行編碼器結構的條件下解決了這個問題。

BCH碼；并行編碼電路；Frobenius標準型

1 串行編碼器電路

對于一個BCH（n，k，t）碼，其中，n為碼長，k為信息位長度，糾錯能力為t。假設生成多項式g（x）為：

式中，gn-k-1，…，g0為生成多項式的系數，都是GF（2m）中的元素。

設碼長為n的碼字多項式為c（x），長度為k的信息多項式為m（x），用x2tm（x）除以生成多項式g（x）可以得到余式r（x），即r（x）=（x2tm（x））modg（x），則系統編碼可由c（x）=x2tm（x）+r（x）得到。這一計算過程可用圖1中的線性移位寄存器（LFSR）實現。LFSR完成校驗位的計算，信息符號由最高位輸入，相當于乘以x2t。在開關的控制下，k個信息符號直接輸出，然后輸出n-k個校驗位就完成了n位碼長的系統碼的編碼。

在CRC編碼器和BCH編碼器中，gn-k-1，…，g0在GF（2）上取值，乘法器實際上代表了連線的連通還是斷開：若碼生成多項式的系數為1則直接連通，為0則斷開，而RS編碼器中的乘法器為實際的有限域乘法器。有限域乘法器可以根據不同的應用選擇并行或串行結構來實現。在光纖通信中，一般使用并行乘法器來滿足對速度的要求。

編碼器可以用狀態方程來描述，如下：

其中，R（n）為n時刻編碼器中寄存器組［r0（n），r1（n），…，rn-k-1（n）］T的狀態，R（n+1）為下一時刻即n+1時刻寄存器組的狀態；U（n）為編碼器的輸入向量［0，0，…，0，u（n）］T的狀態，A 是GF（2）上的（n-k）×（n-k）維矩陣：

式（2）的狀態方程可以用圖2來描述，其中Z-1為單位延時單元。

根據矩陣理論可知，矩陣A稱為多項式Ψ（λ）的Frobenius矩陣，Ψ（λ）的形式為：

通過比較式（1）和（4）可以看出，多項式Ψ（λ）與生成多項式g（x）的系數相同。通過生成多項式g（x），可以直接構造其Frobenius矩陣，來獲得編碼器的狀態方程。

從電路角度來說，矩陣A與編碼電路相對應，編碼電路的特性可以用矩陣的特性來描述。對于高速編碼器來說，關鍵路徑是重要的指標，矩陣中非零元素最多的行決定了電路的關鍵路徑的長短。設非零元素最多的行有d個非零項，忽略輸入引入段的加法器，則電路的關鍵路徑為Tmul+（d-1）×Tadd，其中Tmul和Tadd分別為乘法器和加法器的計算時間；如果采用樹形結構，則電路的關鍵路徑為log2d×Tadd+Tmul。

2 并行BCH編碼器的推導

串行編碼電路在一個時鐘周期內處理一個信息碼元，而并行編碼電路在一個時鐘周期內能處理p個信息碼元，其中p為并行度，同時使得狀態寄存器從R（n）變換到R（n+p）。對串行電路的狀態方程進行p次迭代，可以得到式（7）

對于Frobenius矩陣，當i≥2時，Ai和Ai-1存在如下關系：

式（8）表明由Ai-1計算Ai只需計算Ai-1×［g0，g1，…，gl-2，gl-1］T來確定Ai的最后一列，而Ai的第一列到第-1列就是矩陣Ai-1的后-1列。由于U（n）=［0，0，…，0，u（n）］T只有最后一個元素不為零，Ai×U（n）相當于Ai的最后一列乘以u（n），如下式所示：

當p≤l時，根據式（8）描述的遞推關系，可以得出矩陣Ap，Ap-1，…，A1的最后一列，分別為矩陣Ap的第列、第-1列、…、第 -p+1列。定義V（n）為n時刻到n+p時刻的輸入向量［0， 0，…，0， u（n），…， u（n+p-1）］T，則有：

根據式（11），可以得出并行BCH編碼電路的結構，如圖1所示。與串行結構相比只要把矩陣A換成矩陣Ap，此時輸入變為包含p個數據的向量V（n），實現了一個時鐘周期處理p個數據。當n/p個時鐘后，狀態寄存器Z-1的狀態值就是校驗位的內容。

圖1　并行編碼器實現框圖

3 碼長不能整除并行度時的并行結構設計

上文討論了信息位長度k恰好是并行度p的整數倍的情況，即kmodp=0，但實際應用中會經常出現碼長不能整除并行度的情況。設kmodp=q，當q≠0時式（11）不成立，無法使用圖3設計并行編碼器。文獻［11］給出了一種針對并行CRC編碼器的解決方法，在信息位后面補上p-q個零，使得（k+p-q）modp=0。在電路實現上，需要在最后一個時鐘周期乘以一個新的反饋矩陣，來彌補補零帶來的影響。

設最后一個時鐘周期輸入的向量為V（n）=［0，0，…，0，u（n+k-q），…，u（n+k-1），0，…，0，］T，其中前面有-p個零，后面有p-q個零。由于在最后一個時鐘周期只輸入q個信息位，則只需要進行q次矩陣乘法，根據文獻［11］，可以得到最后一個周期的迭代關系為：

根據式（12），可以得到如圖2所示的改進型并行編碼器結構。與圖1相比，增加了一個矩陣Aq。在前 k/p 個周期，每個周期輸入p個信息位，選擇矩陣Ap進行乘法；在最后一個周期，輸入q個信息位，補零后，再選擇矩陣Aq進行乘法。這樣雖然能處理碼長不能整除并行度的情況，但增加了矩陣Aq，使得實現的邏輯復雜度增加了一倍。

圖2　k mod p ≠ 0時的改進并行編碼器

上面的方法是在最后一個時鐘周期輸入q個信息碼元，如果在第一個時鐘周期輸入q個信息碼元，則R（n+q）與R（n）的關系如下：

由于R（n）為狀態寄存器的初始狀態，則有R（n）=0，將其帶入式（13），得到：

根據式（8）描述的遞推關系，可以得出矩陣Ap的第1列、第2列、…、第q列，分別為矩陣A1，A2，…，Aq的最后一列。根據式（10），則有

其中V（n）=［0，0，…，0，u（n），…，u（n+q-1）］T為輸入向量，其前面有（-p）+（p-q）即-q個零。由式（14）、（15）及R（n）=0，第一個時鐘周期的迭代關系可以寫成

對比式（11）和式（16），可以看出第一個時鐘周期的迭代關系和其他時鐘周期的迭代關系相同，可以把表達式統一為：

根據式（17），第一個時鐘周期的實現電路與其他時鐘周期的實現電路相同，可以用如圖3所示電路實現。與后面補零的并行實現電路相比，在前面補零可以節省一半的邏輯資源。

4 并行度大于生成多項式階數時的并行結構設計

對于式（8），只有當乘方次數小于等于矩陣維數時，該式描述的迭代關系才成立。對于并行編碼器，最高的乘方次數等于并行度，矩陣維數等于生成多項式的階數，故當并行度大于生成多項式的階數時，式（8）表示的遞推關系并不成立，無法使用圖3描述的并行編碼器。本節研究并行度大于生成多項式階數的問題。

為簡化表達，設矩陣A1，A2，…，Ap的最后一列分別為α1，α2，…，αp，為編碼器的輸入向量［0， 0，…， u（n）］T的狀態，為n時刻到n+p時刻的輸入向量［u（n）， u（n+1），…，u（n+p-1）］T且和的維數都為p×1。

5 結束語

本文研究了并行BCH和RS編碼電路的通用設計方法和優化結構。針對信息位長度不能整除并行度的問題，采用在信息位前補零，可以不改變并行編碼器結構的條件下解決了這個問題。針對并行度大于生成多項式階數的問題，建立增廣矩陣，使其滿足并行編碼器的迭代關系，從而給出一種通用的表達式。

A.M.Patel.A multi-channel CRC register.AFIPS Conference proceedings，1971，63-71

Research on Structure of General Parallel BCH Encoder

Du Nuannan1，2，Ma Yingying2
（1.Department of Information Engineering，Wuhan University of Technology，Wuhan Hubei，430070，China；2.Department of Computer and Software Engineering，Pingdingshan Industrial College of Technology，Pingdingshan Henan，467001，China）

This paper research into design approach and structural optimization of parallel BCH and RS coding circuit.Through padding zero in front of information bits，solve the problem of length of information bits isn’t divisible by degree of parallelism under condition of structure of parallel BCH encoder didn’t be changed.

BCH code；parallel coding circuit；standard Frobenius matrix

2014—06—28

杜暖男（1982-），男，博士生，主要研究方向為網絡存儲技術、集成電路設計