RS編譯碼

2024年2月15日發(fā)(作者：條分縷析)

一．RS碼

RS碼是有限域GF（p^m）上，碼長為n=p^m-1的本原BCH碼，它是多進制的BCH碼。

RS碼不但可以糾正隨機錯誤、突發(fā)錯誤以及二者的組合，而且可以用來構(gòu)造其它碼類。

在計算機中數(shù)據(jù)是以二進制的形式存在，所以p通常取值為2。

RS碼的參數(shù)：符號取自GF(2^m)，糾t個錯的RS(n,k)碼的定義如下：

符號大小m．表示符號比特數(shù)為m位。碼塊總長度為n個符號，其中信息長度k個符號，校驗位長度K=n—k個符號。RS碼的糾錯能力是出碼塊中的冗余數(shù)據(jù)校驗碼的長度K決定的。在碼塊中的錯誤位置事先并不知道的情況下，RS(n，k)碼可以糾正t=K／2個錯誤符號。顯然t值越大，RS碼的糾錯能力越強，但與之相對應(yīng)的是更復(fù)雜的算法，更長的運算時間，更低效的數(shù)據(jù)傳輸率。

RS碼既可以糾隨機錯又可以糾突發(fā)錯。但RS碼中采用符號這一特性使得它特別適用于產(chǎn)生突發(fā)錯的場合。因為不論一個符號中錯了多少位，在RS解碼過程中。它只會被認為是產(chǎn)生了一個符號錯。一個可以糾t個符號的RS碼，它至少可以糾一個(t-1)m+1個連續(xù)比特組成的突發(fā)錯，而當隨機錯恰好都不在同一個符號中時只能糾正t個比特的隨機錯。

二．RS碼編碼

對于GF(2^m)來說，若域中非零元素a的級是2^m-1，則將a稱為本原域元素。設(shè)符號取自GF(2^m)，糾t個錯的RS(n,k)碼,它的最小距離d=2t+1，則由本原域元素a的2t個連續(xù)根?m0,?，?m0?2t?1作為g(x)的根來構(gòu)造生成多項式g(x)=(x+?m0)(x+?m0?1)?(x??2t?1?m0)

通常情況下取通常取m0 = 0或m0 = 1

只要將信息碼多項式m(x)=mk?1xk?1???m1x?m0 乘以xn?k次，然后以g(x)為模，求出余式q(x)便可以得到系統(tǒng)碼。

q（x）= m(x)

xn?kmodg(x)=qn?k?1xn?k?1???q1x?q0

C(x)= m(x)

xn?k+ q（x）

例 構(gòu)造能糾正2個錯誤，碼長為15符號的RS碼

n=15，t=2可得m=4，k=11，d=5．因此RS碼為(15，11)碼，生成多項式為g(x)=(x+?)(x+?2)(x+?3)(x+?4) =x4??13x3??6x2??3x??10

假設(shè)待發(fā)送的信息碼組為m(x)=m(x)??2x10??3x6??9x則編碼后的碼組多項式為C(x)= m(x)

xn?k+ m(x)

xn?kmodg(x)=?2x14??3x10??9x5?x3??3x??13

編碼的實現(xiàn)：

1）首先構(gòu)造有限域，RS碼的性質(zhì)和運算法則均定義在Galois域上，Galois域是能進行加減乘除運算的有限個元素的封閉集合，它的加減運算符合結(jié)合律、交換律和分配律。有限域中的元素有兩種表示方法：即指數(shù)形式和多項式形式。乘除法運算需用元素指數(shù)形式，加減法運算要用多項式形式。

指數(shù)形式表示多項式形式的十迸制值為i的元素，它的指數(shù)形式的指數(shù)

指數(shù)形式為?i的元素它的多項式形式

GF（24） 元素表 最小多項式為x4?x?1

序號i 指數(shù)形式 多項式形式

2)構(gòu)造生成多項式g(x)=(x+?m0)(x+?m0?1)?(x??2t?m0)

設(shè)m0 = 1 g(x)=(x+?1)(x+?2)?(x??2t)

n?k?2t

g(x)?gn?kxn?k???g1x?g0，g=1

n?k3）對信息數(shù)據(jù)進行編碼

RS時域編碼原理圖（n-k級時域編碼器）其電路特征是一個實現(xiàn)除法求模運算的線性反饋移位寄存器，該方法得到的是系統(tǒng)碼。

信息碼組從高位到低位送入線性反饋移位寄存器，每一個碼元一方面經(jīng)過控制開關(guān)送出編碼器，另一方面該碼元與移位寄存器Dn?k的輸出進行異或運算，結(jié)果作為feedback反饋回電路與系數(shù)g[O]到g[n-k-1]相乘后再與各個移位寄存器的輸出進行異或運算。當所有的信息碼元都輸入線性反饋移位寄存器后，n-k個移位寄存器中的值就是生成的n-k個校驗碼元。這樣信息碼元在前，校驗碼元在后，這就完成了編碼。

三．RS碼的譯碼

基于伴隨式的譯碼算法，由于其譯碼過程較為簡單，譯碼速度快，是最為常用的譯碼算法。伴隨式譯碼的一般步驟為：

1)計算接收碼字r(x)的2t個伴隨式si，i=l，2，…2t；

2)求出錯誤位置多項式，確定錯誤位置；

3)求出錯誤位置上的錯誤值：

4)由步驟2和步驟3得到錯誤圖樣E(x)的多項式，則糾錯后的碼字多項式c(x)

為：c(x)=r(x)-e(x)。

假設(shè)發(fā)送的碼字為：c(x)?cn?1xn?1???c1x?c0

由于在傳輸過程中發(fā)生了錯誤，接收到的碼字為：r(x)?rn?1xn?1???r1x?r0

錯誤圖案是：e（x)=r(x)-c(x)=en?1xn?1???e1x?e0

若信道產(chǎn)生t個錯誤，則e（x）=?Yixli 式中，Yi?GF(2m)，xli稱為錯誤i?1t位置數(shù)，說明錯誤發(fā)生在r（x）中的第n?li位，錯誤值是Yi.

?0???????0????Yt??????????0?

???0???????Y1????0???????0??m0n?1m0n?2?(?)?(?)?m0?1n?1m0?1n?2?T(?)S?HET=?(?)????m0?2t?1n?1m0?2t?1n?2?))(?(???1???m0?11???????m0?2t?11???m0??m0li1m0li2m0lit????)))(?(?(?YYY12t?????=??

???li1li2lit?2t?1?2t?1?2t?1mmm000?Y1(?)?Y2(?)???Yt(?)???sj??Yi?i?1tjli?r(?j)?i?1j?Yixi （*）

t1）首先計算伴隨式，定義伴隨多項式s(x)?1?s1x?s2x2???stxt若S（x）=0，則表示接收到的碼字沒有錯誤或者發(fā)生了無法檢測的錯誤。輸出原接收碼字。用Horner法實現(xiàn)si?r(?i)?{?((rn?1?i?rn?2)?i?rn?3)?i???r1}?i?r0

2）用BM迭代算法求錯誤位置多項式，由（*）式中的2t個方程求出2t個未知數(shù)xi，Yi。分兩步進行，先解出錯誤位置數(shù)xi，再求出錯誤值。

定義錯誤位置多項式為?(x)??(1?xix)?1??1x????txt

i?1t若xk?1?1為錯誤位置則?(xk)?0兩邊乘以xkt，得

tt?1xk??1xk????t?0,k?1,2?,t

上式j(luò)?t兩??1Ykxk邊j?t?1再乘以jjYkxk,j?m0,?,m0?t?1得Ykxk????tYkxk?0,k?1,2?,t

對k求和得sj?t??1sj?t?1????tsj?0 （**）

作乘積s(x)?(x)并用?(x)?1??1x??2x2??表示，由（**）式可得t+1次以上系數(shù)為0。

得關(guān)鍵方程s(x)?(x)??(x)modx2t?1

用關(guān)鍵方程求?(x)的迭代譯碼算法：

用迭代方法求解到第j步時，求得滿足

s(x)?(j)(x)??(j)(x)modxj?1的解?(j)(x)，?(j)(x)。

在第j+1步時以xj?2為模，?(j)(x)，?(j)(x)不再滿足上式。

所以引入一個差值dj，使下式成立

s(x)?(j)(x)??(j)(x)?djxj?1modxj?2 （***）

(j)t(j)(j)?(x)?1??1x????D(j)x

將（***）式左邊展開推出dj?sj?1??sj?1?i?ii?1D(j)(j)將dj代入關(guān)鍵方程求解得

??(j?1)(x)??(j)(x)?djdixj?i?(i)(x)

(x)??(j)(x)?djdixj?i?(i)(x)

?1?1(j?1)I是j之前的某一行，它在所有j行之前各行中的i-D（i）最大，且di?0

D（j+1）=max（D（j），j-i+D（i））

迭代過程如下：

設(shè)定初值為?(?1)(x)?1，?(?1)(x)?0，D（-1）=0，d?1?1

(0)(0)?(x)?1，?(x)?1，D（0）=0，d0?s1

開始迭代 j=1，2，……2t

D(j)i?1(j)首先計算dj?sj?1??sj?1?i?i

若dj=0則?(j?1)(x)??(j)(x)

?(j?1)(x)??(j)(x)

D（j+1）=D（j）

若dj?0則找出j之前的某一行i，它在所有j行之前各行中的i-D（i）最大，且di?0

??(j?1)(x)??(j)(x)?djdixj?i?(i)(x)

(x)??(j)(x)?djdixj?i?(i)(x)

?1?1(j?1)D（j+1）=max（D（j），j-i+D（i））

一直迭代2t次，得到的?(2t)(x)，?(2t)(x)即為所求的?(x)和?(x)

判斷?(x)次數(shù)是否大于t，如果大于t說明有不可糾的錯誤，如果小于等于t則求?(x)=0的根，即為錯誤位置數(shù)。

3）用錢氏搜索求錯誤位置

r(x)?rn?1xn?1???r1x?r0

判斷rn?l是否錯誤，?n?l是否是錯誤位置數(shù)，判斷??(n?l)是否是?(x)的根，

??(n?l)??l代入?(x)=0

1??ltl1?????t??0 則rn?l有錯

1??1?l????tlt??0 則rn?l正確

3）錯誤值的計算

用Forney算法

Y?(xi??xii?1)?'(xi?1)

若實際產(chǎn)生的錯誤個數(shù)??t

?si???1Ykxjk

ks(x)?1?s1x?s2x2??i?????1?Ykxkxi?1six?1??i?1sixi=1+k??11?xkx?s(x)?(x)=（1+?Ykxkx）?(x)=?(x)mod?11?xkxx2??1

k由于恒等式左邊最高次數(shù)為2?

?得出?(x)?Ykxkxk?11?xkx=?(x)-?(x)

Yixix1?x?(x)+?(x)??Yjxjx=?(x)-?(x)

ixjj??11?ixjx得Yxr?xYjxjxiix?(1?jx)+?(x)?=?(x)-?(x)

ij??1jj1?j??1ix

jx代入rx?1i得Yixix?1i?(1?jxjx?1?1i)=?(xi)

i??1j?因為?'(x)???r(1?i?1xi?xjx)

ij??1j****）

（

代入xi?1得-xi?1?1?(xi)???xi?(1?xjxi)

i?1j?1i?j'?1?r代入（****）式得-Yixixi得錯誤值Yi?

?1?1?1?(()??xi)

xixi?1'?xi?(xi)?1?(xi)'?1