降低RS碼算法復雜度的改進KV算法

江南

(福建信息職業技術學院軟件工程系，福建福州350003)

降低RS碼算法復雜度的改進KV算法

江南

(福建信息職業技術學院軟件工程系，福建福州350003)

提出對Koetter-Vardy(KV)算法進行改進后的重編碼算法，利用Reed-Solomon(RS)碼的線性性質對重數矩陣進行預處理，改進了插值算法的初始多項式條件，降低插值算法的復雜度，從而降低了KV算法的總體復雜度，帶來的復雜度的節省因子是n2(n-k)2．對該算法的軟件實現以及仿真結果顯示，對高碼率的RS碼，重編碼算法幾乎不犧牲譯碼性能．

KV算法；重編碼算法；RS碼；復雜度

KV算法是Koetter和Vardy于2003年在Guruswami-Sudan算法的基礎上提出來的[1-2]、實現Reed-Solomon(RS)碼代數軟譯碼的算法簡稱.它將信道軟信息轉化成代數約束條件，然后再利用GS算法的部分步驟，相對于傳統的Berlekamp-Massey硬判決算法有著0.28～1.23 dB的增益.假設RS碼碼長為n，信息長度為k，KV算法復雜度與n成多項式關系，是目前較為有效的RS碼軟譯碼算法．經過改進后的Koetter-Vardy算法[3-4]可以達到更好的譯碼效果，但其復雜度也不能忽視.重編碼算法[5]是降低KV算法復雜度的重要算法，能夠在幾乎不損失性能的情況下將復雜度較高的插值算法的復雜度降低n2(n-k)2因子，有著廣泛的潛在應用[6]．

1 Koetter-Vardy算法實現步驟

1.1 重數分配

發送符號從有限域GF(Q)取出，在無記憶信道傳輸．信道輸入輸出是隨機變量X和Y．觀察信道輸出的軟信息是后驗概率：

其中1≤i≤Q,1≤j≤n．這個可靠性矩陣Π就是KV算法的輸入．

從可靠性矩陣計算出一個(Q×n)的整數矩陣M,此矩陣稱為重數矩陣，矩陣中的元素用mi,j表示.其Q行代表一個符號的Q種不同取值，即αi,1≤i≤Q.n列代表一個碼字中n個符號位置，即支持集中的xj，1≤j≤n.文本只考慮Gross提出的簡單重數分配方案[7]，即這是目前KV算法研究中較為常用的方案，更好的方案見文獻[8]．

1.2 插值

尋找一個二元多項式Q(x,y)，使其滿足下面兩個條件：①對重數矩陣中每個非零的元素mi,j，Q(x,y)以重數mi,j通過GF(Q)×GF(Q)平面上的點(xj,αi)，或者說(xj,αi)是Q(x,y)的mi,j重零點；②Q(x,y)的(1,k-1)-加權階數盡可能小．要求加權階數盡可能小的原因是這樣算法的搜索半徑最大，糾錯能力最強．該步驟是KV算法復雜度的主要來源，本文所要介紹的重編碼算法也就是要降低這一步算法的復雜度．不難看出，上述條件①說明二元多項式Q(x,y)需要滿足C(M)=個線性約束條件．Koetter提出一種插值算法[9]，其基本步驟如下，假定C=C(M)：

(1)將二元多項式的集合FL[x,y]按照首單項式的y-階數進行劃分，劃分成L個子集，初始化L個多項式．這里FL[x,y]指的是所有y階數低于L的二元多項式．

(2)每次迭代，更新分別來自上面劃分出來的L個集合的L個多項式，i次迭代后，L個多項式都能滿足第1到i個線性約束，而且在各自的所在的劃分集合中，它是最小的．

(3)C次迭代后，L個多項式都能滿足C個條件，并且在各自集合中加權階數最低，在這L個里面再選出最小的那個，作為結果輸出．

1.3 因式分解

找出二元多項式Q(x,y)的所有形式為y-f(x)的因式，degf(x)＜k，這些因式是預選的消息多項式，將他們重新編碼，就得到預選碼字列表．

1.4 ML判決

根據極大似然估計Maximum Likelihood準則，在列表上尋找一個與接收矢量y→最接近的碼字，作為譯碼結果輸出．

從以上步驟中可以看出，KV算法的復雜度在很大程度上取決于插值的復雜度，而插值的復雜度則取決于所需要滿足的線性條件的總個數．因此，降低插值算法的復雜度就可以降低KV算法的復雜度，從而提高算法效率．

2 重編碼算法

重編碼算法是降低KV算法復雜度的重要算法，它能夠在幾乎不損失性能的情況下將插值算法的復雜度降低n2(n-k)2因子．下面先介紹其步驟和原理，再通過算例和仿真結果做進一步了解．

重編碼算法利用了RS碼的線性性質和廣義系統碼編碼，線性分組碼具有線性性質，即如果是碼字集合，則這個性質在譯碼中可以得到應用，比如在硬判決譯碼中，可以將接收碼字加上一個碼字，或者可以叫做偏移量，則得到的結果仍然是一個碼字，對其進行譯碼，譯碼輸出再加上(GF(2m)上加減法是一樣的)，就可以得到原接收碼字的譯碼輸出．這是因為，和的錯誤圖樣是一樣的．設發送碼字為，錯誤圖樣為，則：

下面討論RS碼的系統碼編碼．所謂系統碼，就是消息碼元“顯式”地在編碼后碼字中出現．常提到的系統碼，消息碼元都是連續地在碼字的前k位或者后k位出現，這叫做嚴格的系統碼．這里要用到的是，k個編碼前碼元任意地出現在碼字中任何k個位置的系統碼，可以稱之為廣義系統碼．這種廣義系統碼編碼也可以看作已知一個碼字任意k個位置的碼元，要求出這個碼字．由于RS碼是Maximum Distance Separable碼，總是可以用一個糾刪譯碼器來求出這個碼字．

重編碼算法的步驟是：

(1)當譯碼器接收到軟信息時，首先做硬判決，得到硬判決碼字r→．

(2)由可靠性矩陣Π求出重數矩陣M，這里采用簡單的分配方案，即

(3)根據的M元素值，選擇出含有最大重數mmax(即可靠性較高)的k個碼元位置，設為集合R，其余碼元位置設為集合U(假定可以找到k個這樣的位置，找不滿k個的情況在后面討論)．

(4)將r→中k個對應于R中元素位置的碼元看作消息碼元，對其進行重編碼，使編碼后碼字在這k個位置上與相同，將此碼字記為(用了廣義系統碼編碼)．

(6)對重數矩陣插值，這樣處理的重數矩陣可以減少插值算法的迭代次數.

(7)對插值多項式進行因式分解，后面的步驟和原KV算法相同．

分析重編碼算法的原理：第(5)步中對重數矩陣的偏移類似于上面提到的對接收硬判碼字進行偏移．只不過，KV是軟判決譯碼算法，這里要偏移的不僅是一個碼字，而是整個重數矩陣．重數矩陣的Q行代表著GF(Q)上的符號，n列代表一個碼字中n個碼元的位置．矩陣中某列各行代表的符號加上ψ→中對應位置的符號，就得到新的符號，該符號又對應了新的矩陣行號．矩陣中每個元素都要按照這種關系進行變換．例如，對GF(8),(7,5)RS碼，M中某個元素：m7,3=3，說明第三個符號位置，對應于α6的重數為3，而ψ→的第三個符號為α1，α1+α6=α5，則m7,3的值移到m6,3，原先m6,3的值也根據此規則進行移動，如果把行號視為正整數集合：NQ:{0,1,…,Q-1}，則可以把這種變換關系視為一個映射NQ?NQ，這個映射是一一映射，也就是說不會出現某個值被其它值覆蓋的情況．

再看這種偏移帶來的效果．重數矩陣中最大的重數為mmax，用m來簡化表示．重數為m的位置說明了該位置可靠性較高．在重數矩陣對應的k列中，m所在的行對應的符號就是硬判決的符號．對矩陣做偏移時，偏移碼字ψ→在這k個可靠符號位置上和硬判決碼字是一樣的(因為做的是廣義系統碼編碼)．這樣，偏移之后，這k個m就被移到了第0行，即對應GF(Q)零元所在的行上．注意到，由于m是最大的重數，把C(M)'/C(M)個m移到零元位置就相當于把相當多的重數移到了y分量為零的插值點上，這個插值點集合可以記為：

對這些插值點的插值，可以直接求得滿足這些點的多項式．

對PR中的k個重數均為m點，一個滿足這些插值重數要求且次數最低的多項式是p(x)m，其中

同時，不難看出，p(x)m-jyj也是滿足各點的重數要求，且次數最低，因此可以將本文第一部分插值算法中的初始條件設為：

這樣，這些初始條件已經滿足(1-k n) C(M)個重數為m的插值點的要求，后面的插值就不需要再在這些點上進行迭代，這就是重編碼算法降低復雜度的原理．

上面假定了重數矩陣中存在k個重數為m的點，如果沒有這么多個點該怎么辦？在此做個近似，將重數m-1的點(如果還不夠的話就采用重數m-2的點)的重數升為m，這樣就一樣能使用重編碼算法了．當然，這樣的修改重數可能會帶來一些性能上的降低，但是從仿真結果上看，幾乎沒有什么影響，特別是在高信噪比的情況下，這種修正重數的情況是很少的．

重編碼算法能降低插值算法的復雜度，而插值算法的復雜度使用線性約束條件的個數C(M)來表示的．采用Gross的重數分配方案，C(M)的上界是：

這實際上是將每個硬判決符號分配重數C(M)'的GS算法的C(M)．而現在，重數矩陣里去掉了k個m，C(M)'的上界是：

這樣可以估計出迭代次數的節省，在高碼率情況下是很可觀的．后面通過仿真能夠看到更直觀的數據．

另外，這里還討論一下“可靠性較高”的含義．選取重編碼位置的集合R時，選取k個可靠性較高的位置作為重編碼位置．這里的可靠性較高，并不是要求這些位置上的碼元實現了無誤傳輸，而只是說在接收機看來，可靠性較高而已．從前文提到的線性分組碼性質可以知道，其實隨便設定一個偏移碼字ψ→，對重數矩陣按照這個偏移碼字進行偏移，再進入KV算法譯碼，譯碼后再偏移回來，如果原先碼字是KV算法可譯的，這樣偏移一下也一樣還是可以譯出來的．選擇可靠性較高是因為這些位置對應有最大的重數m，能夠最大程度地把最大重數移動到y坐標為零的點上，降低插值復雜度．換句話說，如果這些“可靠性高”的碼字實際上是有誤的，但通過KV算法，仍然能夠把它糾正．

3 算例及性能仿真

下面的算例突出了和重編碼有關的步驟．考慮一個(7,5)碼，消息碼字是:

編碼后發送碼字為:

經過BPSK調制，AWGN信道，SNR=4.0．

從可靠性矩陣能得到硬判決碼字：

可以看到，這里有2個錯誤．

設C(M)，用Gross重數分配方法得到重數矩陣：

可以選擇前5個重數均為4的位置作為重編碼位置集合R，即

以此為偏移量，對重數矩陣偏移，得到：

同時，可以計算出：

將M'首行5個4全部置為0，同時將(2)作為插值初始條件，進行插值，可以得到多項式QM(x,y)，該多項式較長，這里不再寫出．進行因式分解，可以得到2個預選消息碼字：

將它們編碼后：

這時候，要將它們恢復到偏移前的碼字，然后再進行ML判決：

進行ML判決選出c2作為譯碼輸出，譯碼成功．

圖1和圖2分別仿真了RS(15,11)和RS(63,55)兩種碼型，ReEn表示重編碼算法，KV表示原KV算法，復雜度因子m一律取4．可以看到，重編碼和原KV算法的性能確實是十分接近的，在長碼字表現得甚至略好些，這說明，使用重編碼算法在性能上是不會受到損失的．

圖1 BPSK調制,AWGN信道下,RS(15,11)碼重編碼算法性能

圖2 BPSK調制,AWGN信道下,RS(63,55)碼重編碼算法性能

仿真表明了復雜度降低的情況．設RS碼為(63,55)的RS碼，碼率為0.87，通過BPSK調制和AWGN信道后用KV算法進行譯碼，在每個信噪比上仿真100個碼字，取插值迭代次數的平均值來估計實際迭代次數，得到表1(C(M)為原KV算法迭代次數，C(M)'為重編碼算法迭代次數)．

表1 重編碼算法與原KV算法迭代次數對比

從表1看出，實際上，迭代次數的節省比上面用上界得出的結論還要多，基本達到了90%的節省，這是很可觀的，當然，要在碼率較高的時候才會有如此可觀的節省．插值的復雜度和迭代次數C呈二次方關系[10]，注意到重編碼以后C已經減少了1-k n因子，因此，重編碼帶來的復雜度的節省因子是n2(n-k)2．

4 結語

本文討論了KV算法的一種簡單而且有效的改進——重編碼算法．對高碼率的RS碼來說，使用重編碼算法可以大大降低復雜度，同時幾乎不犧牲性能．KV算法的復雜度雖然是多項式時間的，但和傳統的硬判決算法相比還是復雜許多，這成為了它實際應用的一個瓶頸．重編碼算法大大降低了插值算法的復雜度，可以想象，在大部分應用KV算法的實際系統中，該算

法將有廣泛的應用．最新研究成果表明[11-12]，KV算法除了在信道編碼方面的應用以外，還可以用于分布式信源編碼，上述論文并未提及重編碼算法．未來研究方向可以朝包括研究如何將重編碼算法應用到分布式信源編碼上的方向發展．

[1]Koetter R,Vardy A.Algebraic soft-decision decoding of Reed-Solomon codes[J].Information Theory,IEEE Transactions on,2003,49(11): 2809-2825.doi:10.1109/TIT.2003.819332.

[2]丁溯泉,楊知行,潘長勇.RS碼軟判決譯碼算法研究的最新進展[J].電子科學技術評論,2005(2):37-41.

[3]Jiang J,Narayanan K R.Algebraic soft-decision decoding of Reed-Solomon codes using bit-level soft information[C].Proc Allerton Conference on Communications,Control and Computing,2006.doi:10.1109/ TIT.2008.928238.

[4]El-Khamy M,McEliece R J.Iterative Algebraic soft-decision List decoding of Reed-Solomon codes[J].IEEE Journal on Selected Areas in Communications,2006,24(3):481-490.doi:10.1109/JSAC.2005.862399.

[5]Koetter R,Vardy A.A complexity reducing transformation in algebraic list-decoding of Reed-Solomon codes[C].Proc.IEEE Inform.Theory Workshop,Paris,France,April 2003.doi:10.1109/ITW.2003.1216682.

[6]Koetter R,Ma J,Vardy A.The re-encoding transformation in Algebraic list-decoding of Reed-Solomon codes[J].Information Theory,IEEE Transactions on,2011,57(2):633-647.

[7]Gross W J,Kschischang F R,Koetter R,et al.Applications of algebraic soft-decision decoding of Reed-Solomon codes[J].IEEE Trans Communication,2006,54(7):1224-1234.doi:10.1109/TCOMM.2006.877972.

[8]Huang Q,Wu J,Zhao C M,et al.Waterfilling-like multiplicity assignment algorithm for algebraic soft-decision decoding of Reed-Solomon codes[C].IEEE International Conference on Communications(ICC), 2007.doi:10.1109/ICC.2007.1028.

[9]Koetter R.Fast generalized minimum-distance decoding of algebraicgeometry and Reed-Solomon codes[J].IEEE Trans Inform Theory, 1996,42(3):721-737.doi:10.1109/18.490540.

[10]Cassuto Y,Bruck J;McEliece R J.On the average complexity of Reed-Solomon list decoders[J].Information Theory,IEEE Transactions on, 2013,59(4):2336-2351.doi:10.1109/TIT.2012.2235522.

[11]Li S Z,Ramamoorthy A.Algebraic code design for Slepian-Wolf codes [C].IEEE International Symposium on Information Theory(ISIT),Saint Petersburg,Russia,2011:1861-1865.

[12]Ali M,Kuijper M.Source coding with side information using list decoding[J].Information Theory Proceedings(ISIT),IEEE International Symposium on,2010:91-95.doi:10.1109/ISIT.2010.5513280.

【編校：王露】

Improved KV Algorithm with RS Code Algorithm Complexity Reduction

JIANG Nan
(Fujian Polytechnic of Information Technology,Fuzhou,Fujian 350003,China)

The reencoding algorithm,an improvement on the Koettery-Vardy(KV)algorithm for Reed-Solomon(RS)soft decoding was introduced.This algorithm takes advantage of the linearity of the Reed-Solomon codes.It preprocesses the multiplicity matrix,improve the initial polynomials in the interpolation algorithm and reduces the complexity of the interpolation algorithm. The overall complexity of the KV algorithm is reduced by a factor ofn2(n-k)2.Observed from the software implementation and simulations,for high rate RS codes,the algorithm reduces the complexity of the KV algorithm without sacrificing much performance.

Koetter-Vardy(KV)algorithm;reencoding algorithm;Reed-Solomon(RS)codes;complexity

TP301.6

A

1671-5365(2014)06-0094-05

2013-09-10修回：2013-10-20

2012年度福建省A類科技項目計劃立項(JA12385)

江南(1972-)，女，副教授，工學學士，研究方向為計算機軟件及項目管理

時間：2013-10-30 15:06

http://www.cnki.net/kcms/detail/51.1630.Z.20131030.1506.007.html