RS編解碼的基本方法

2024年2月15日發(作者：團干部培訓心得體會)

RS編解碼的基本方法

作者：劉延海 張亮

來源：《科技資訊》 2011年第32期

劉延海 張亮

(陜西凌云電器集團有限公司 陜西寶雞 721006)

摘 要:總體介紹了RS碼的基本理論,講述了RS編解碼的基本方法。實踐證明,RS編解碼適用于大多數無線通訊信道的糾錯碼。

關鍵詞:伽羅華域 生成多項式 伴隨多項式 錯誤多項式

中圖分類號:TP393.33 文獻標識碼:A 文章編號:1672-3791(2011)11(b)-0003-02

BCH碼是迄今為止所發現的一類很好的線性糾錯碼。它的糾錯能力很強,可以糾正多個隨機錯誤,特別是它在短和中等碼長下,其性能很接近于理論值,并且構造方便,編碼簡單。特別是它具有嚴謹的代數結構,因此在編碼理論中起著重要的作用。BCH碼是迄今為止研究得最為詳盡,分析最為透徹,取得的成果也是最多的碼類之一。

在實際應用中,所選擇碼字主要看其編譯碼是否簡單,速度是否足夠快,是否易于工程實現,是否能取得較好的性能。BCH碼有很多譯碼算法,其中Berlekamp或Euclid迭代譯碼算法,大大加快了譯碼速度。且易于軟硬件實現,從實際上解決了BCH碼的譯碼問題。正是由于這些優點,使得它在實際中受到工程技術人員的歡迎,是目前應用最為廣泛的碼類之一。

RS碼是一類有很強糾錯能力的多進制BCH碼,也是一類典型的代數幾何碼。它的編譯碼技術比較成熟且性能優良,因此在數字通信和數字存儲系統中得到廣泛應用。這些應用包括無線通信,移動通信,衛星通信,數字電視,DVB,及象ADSL,或xDSL這樣的高速調制解調器中。在這些系統中,RS碼已經被選為用于FEC的碼類,作為規范的一部分。

1 RS碼的性能

在實際的通信中,由于各種噪聲及其它不可預知的因素,不可避免的造成傳輸的信息錯誤。這種錯誤的特性和信道及系統特性有關。一般來說,所發生的錯誤可以分為以下兩類。

(1)一類是隨機錯誤。即單個比特錯誤,而且各個錯誤彼此獨立,不相關,它一般是由于熱噪聲引起的。糾此類錯誤,可以用RS碼和卷積碼。由于RS碼是塊碼,如果在一個信息塊中,錯誤較少,則錯誤可以被RS碼全部糾正。

(2)第二類是突發錯誤。即錯誤比特連續出現,但不是很長。糾正此類錯誤,RS碼非常有效。

RS碼是最大距離可分碼,其最小距離dmin=n-k+1,最多可糾正(n-k)/2個錯誤,如RS(16,7)可糾正4個錯誤,RS(31,15)可糾正8個錯誤。

RS碼的糾錯能力是以所能糾正的符號數來表示的。對RS碼來說,一個符號內錯一個比特與錯所有比特是相同的,這使得RS碼特別適用于糾突發錯誤,如RS(16,7)可糾正連續20比特的錯誤,RS(31,15)可糾正連續40比特的錯誤。相對而言,RS碼就對隨機錯誤比較敏感。

綜上所述,RS碼是一類非常好的碼字,性能優良。

2 有限域的基本知識

2.1 (定義)域是一種代數結構,它由一個集合F構成,并在該集合上定義了加法運算(+)和乘法運算(×),且對集合F中的任意元素滿足以下性質

3 RS編碼原理

RS編碼方式為系統碼,碼字多項式的第n-1次至n-k次系數是信息位,其余為校驗位,這相當于C(x)=m(x)xn-k+r(x),式中m(x)=mk-1xk-1+mk-2xk-2+…+m1x+m0是信息多項式,(mk-1,m1,m0)是信息位,而r(x)=rn-k-1xn-k-1+rn-k-2xn-k-2+…+r1x+r0是校驗多項式,相應的系數是碼元的校驗位。編碼過程即是根據k個信息碼元及[n,k]RS碼的特性獲得n-k個校驗碼元的過程。[n,k]RS循環碼的校驗碼元可根據校驗多項式h(x)=hkxk+hk-1xk-1+…+h1x+h0獲得。設系統碼多項式為C(x)=cn-1xn-1+cn-2xn-2+…+cn-kxn-k+cn-k-1xn-k-1+…+c1x+c0,它的前k位系數。cn-1,cn-2,cn-k是已知的信息位,后n-k位系數。cn-k-1,cn-k-2,…,c1,c0是需要求的校驗位。因為碼多項式必是生成多項式g(x)的倍式,故有C(x)=q(x)g(x),而h(x)C(x)=q(x)g(x)h(x)=q(x)(xn-1)=q(x)xn-q(x),q(x)xn的最低次數至少為n次,因此h(x)C(x)的乘積中,xn-1,xn-2,…,xk次的系數應為0,而xn-1的系數由cn-1-0h0+cn-1-1h1+…+cn-1-khk組成,xn-2的系數由cn-2-0h0+cn-2-1h1+…+cn-2-khk組成。這表明碼字C的第一個校驗元cn-k-1可由k個信息元cn-1,cn-2,,cn-k與h(x)的系數相乘得到,而由cn-2,cn-3,…,cn-k,cn-k-1可得到第二個校驗元cn-k-2,再由cn-3,…,cn-k信息元和第一、第二校驗元cn-k-1,cn-k-2可得到第三校驗元cn-k-3。依此類推,可求得所有的n-k個校驗元cn-k-1,cn-k-2,…,c1,c0。

根據以上的過程分析,可知RS編碼的軟件實現過程如下。

(1)首先求出域GF(2m)中的所有元素并存儲備用。

(2)在[n,k,d]RS碼中,其生成多項式是唯一的,由xn-1=g(x)h(x),可知校驗多項式h(x)也是唯一確定的,且g(x)=(x-)(x-2)…(x-n-k),根據伽羅華域上的運算規則可求出h(x)=(xn-1)/g(x)的各項系數。

(3)據上面的分析,依次求出所需的校驗元cn-k-1,cn-k-2,…,c1,c0。

4 RS解碼

解碼比編碼困難得多,解碼過程描述如下。

(1) 求伴隨式。

(2)檢查伴隨式,若全為0,則接收碼字為有效碼字,轉到9)。

(3)初始化。

其中和分別是和的最高次項系數,m是和的度數之差;執行這個迭代過程直到。

(5)分別對和歸一化,使常數項為1,求得和。

(6)求的根,得到錯誤位置;如果根的數目小于的度數(說明有重根,或在擴域上有根),譯碼失敗,轉到10)。

(7)由Forney算法,求錯誤值,如果分母為0,則譯碼失敗,轉到10)。

(8)接收碼字對應位置減去錯誤值,糾錯。

(9)輸出正確碼字中的信息位。

(10)輸出接收碼字中的信息位,置譯碼失敗標志。

5 結語

RS編解碼過程涉及域、線性分組碼、生成矩陣、校驗矩陣、伴隨式等概念,文中將編解碼方法做了總結。

參考文獻

[1]王新梅,肖國鎮.糾錯碼原理與方法[M].西安:西安電子科技大學出版社,2001.

[2]JyhHorng Jeng,TrieuKien ding of Both Errors and Erasures of

aReed-Solomon CodeUsing an Inver-FreeBerlekamp-Masy Algorithm[J].IEEE

Transactions on Communications,1999,47(10):1488～1494.