降低RS碼算法復(fù)雜度的改進(jìn)KV算法

江南

(福建信息職業(yè)技術(shù)學(xué)院軟件工程系，福建福州350003)

降低RS碼算法復(fù)雜度的改進(jìn)KV算法

江南

(福建信息職業(yè)技術(shù)學(xué)院軟件工程系，福建福州350003)

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

KV算法；重編碼算法；RS碼；復(fù)雜度

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

1 Koetter-Vardy算法實現(xiàn)步驟

1.1 重數(shù)分配

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

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

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

1.2 插值

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

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

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

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

1.3 因式分解

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

1.4 ML判決

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

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

2 重編碼算法

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

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

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

重編碼算法的步驟是：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

這實際上是將每個硬判決符號分配重數(shù)C(M)'的GS算法的C(M)．而現(xiàn)在，重數(shù)矩陣?yán)锶サ袅薻個m，C(M)'的上界是：

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

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

3 算例及性能仿真

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

編碼后發(fā)送碼字為:

經(jīng)過BPSK調(diào)制，AWGN信道，SNR=4.0．

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

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

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

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

以此為偏移量，對重數(shù)矩陣偏移，得到：

同時，可以計算出：

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

將它們編碼后：

這時候，要將它們恢復(fù)到偏移前的碼字，然后再進(jìn)行ML判決：

進(jìn)行ML判決選出c2作為譯碼輸出，譯碼成功．

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

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

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

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

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

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

4 結(jié)語

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

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

[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ìn)展[J].電子科學(xué)技術(shù)評論,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-)，女，副教授，工學(xué)學(xué)士，研究方向為計算機(jī)軟件及項目管理

時間：2013-10-30 15:06

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