RS碼編碼算法

1、RS碼編碼算法RSRS 編碼對于能包糾正 t t 個錯誤的 RS(n,k,dRS(n,k,d) )碼，具有如下特征：1)碼長：n=2m一1符號或m(2m一1)比特2)信息碼元數(shù)：k=n一2t或mk比特；3)監(jiān)督碼元數(shù)：nk=2t符號或m(n-k)比特；4)最小距離：d=2t+1=nk+1符號或m(n-k+1)比特;最小距離為 d d 的本原 RSRS 碼的生成多項式為23d一2g(x)二(x-二)(x一二)(x二)(x一二)式中的 m m 是一個任意整數(shù)。令信息元多項式為：.2k-1m(x);m0m1m2x-myx二.RSRS 編碼器的類型1 1 . .基于乘法形式的 RSRS 編碼器公式:c

2、(x)=m(x)g(x)結(jié)構(gòu)圖如下：由上面結(jié)構(gòu)的乘法編碼器輸出的碼字是非系統(tǒng)碼。2 2 . .基于除法形式的 RSRS 編碼器(1)根據(jù)生成多項式g(x)構(gòu)造的除法編碼器。r(x)=b(x)g(x)剩余多項式r(x)至少比g(x)低一次。/、2t-1.2t-2.2.SoSo徜出乘法編碼器乘法編碼器nkxa(x)g(x)r(x)=r2t_1xr2t_2xr2xr1xr0則編程的碼多項式為nk.c(x)=xa(x)r(x)n_1n_22:cn1xcn2x-，c2xc1xc0具體實現(xiàn)如下圖:除工電路構(gòu)成的心編碼器(2)根據(jù)校驗碼多項式h(x)構(gòu)造的除法編碼器設(shè)校驗多項式為：.k.k_1h(x)=hk

3、xhk_1x-，h1xh0系統(tǒng)碼的多項式為：n-1n-2n-kn-k-1C(x)=cnqx卻_2*備_卜*g_k.G“xc0它的前k位系數(shù)：cn_1,cnj,，cn_k是已知的信息位，而后n-k位系數(shù)：cn_k_1,cn_2，c1,c0是需求的校驗位。碼多項式必是生成多項式g(x)的背式，所以C(x)=q(x)g(x)C(x)-n-1,：:g(x)=n-k,：:q(x)-k-1而h(x)C(x)=q(x)g(x)h(x)=q(x)(xn-1)=q(x)xn-q(x)由于C(x)n1,fg(x)=n-k,；:g(x)=n-k,；:q(x)k-1所以q(x)xn的最低位次數(shù)至少為n次，而在h(x)

4、C(x)的乘積中xn-1,xn2,，xk的次數(shù)為 0 0。xn1的系數(shù)：cn_1_0h0cn_1_1h1cn_1_khkxn/的系數(shù)：cn-2-0h0cn_2_1h1,，cn_2khk而k、cn_jhj=0i=0,1,2,n-kj=0由于h(x)為首一多項式，hk=1,故上式可寫為k_1c.=_chi=12n-knkinijj,j=0上式展開為：cn_k_1=-(cn_1h0，cn二h1cn-khk-1)cn_k_2=(cn_2h0，cn_3h1-cn_k-1hk-1)acn_k_(n_k)=c=-(ckh。,ck/h15hk_1)由上式看出碼字C的第一個碼元cnU1可由k個信息元cn1,cn

5、2，cnk與k1n12kh(x)的系數(shù)相乘得到,而由cn_2,cn,，cnkcnk可得到第二個校驗元cn_k_2,再由cn_3,，備信息元和第一、第二校驗元.k_1,.k_2可得到第三校驗元cn二。按這樣的線性關(guān)系遞推，一直可求得所有的n-k個校驗兀cnk3,cnk2,c1,c00具體實現(xiàn)如下圖： 輸出碼字輸出碼字tnTk循環(huán)碼循環(huán)碼k級編碼器級編碼器(3)(3)RSRS 的時域編碼實際例子RSRS 碼是非二進制碼，它是在GF(q)上的，這里q#2。這里我們選用GF(16)域來進行，域中 1616 個元素可用 4bits4bits 符號表示。例構(gòu)造一個能糾正 3 3 個錯誤符號，碼長為 15,

6、15,m=4m=4 的 RSRS 碼。求生成多項式和編碼電路。解：當t=3=3 時，最小碼距Dmin=7,信息元長度k=9。該碼為(15,9)(15,9)RSRS碼，其生成多項式為：2、，3、，4、，5、，6a)(xa)(xa)(xa)(xa由分圓多項式多項式：,、，24八g(x)=(xx1)(xx1)awGF(16)是本原域元素，它是多項式x4+x+1的根，則4,八aa1=0a4=a1以x4+x+1為模的GF(24)的元素如下表:a0-1a0001000182a=a+101010101a0010001093a=a+a101010102a01000100102a=a+a+1011101113a

7、10001000113,2a=a+a+a11101110a4=a+100110011123,2.a=a+a+a+11111111152.a=a+a01100110133,2,da=a+a+11101110163.2a=a+a11001100143.a=a+11001100173a=a+a+11011101115.a=100010001GF(24)中每個元素都可表示成它的自然基地1,a,a2,a3(在域GF(2)上)的線性組合，如下形式:g(x)=(xa)(x610=xax5144ax43629axaxaxa32a3aa2aa1aa0因此在GF(24)上的24進制 RSRS 馬，它的編碼電路可用

8、k或n-k級24進制寄存器實現(xiàn)。本例是用n-k=6級乘法器電路實現(xiàn)，如下圖。圖中的移位積存器必須是由能積存 1616 進制的元件組成，這可用 4 4 級觸發(fā)器組成的移存器完成。a10,a14,a4,a6,a9常乘器可用模 2 2 加法器構(gòu)成。在域GF(24)上的系數(shù)a10,a14,a4,a6,a9可用自然基地表示為如下形式：103213121110a(a3aa2aa1aa0)=a3aa2aa1aa0a,32,、,32，32,2=a3(aa1)a2(aaa1)a1(aaa)a0(aa1),、3,、2=(a3a2a1)a(a3a2-a1a0)a-(a2a1-a0)a(a2-a0)32,、=aaa3

9、aa2a(aa。)4/320.7654a(a3aa2aa1aa0a);a3aa2aa1aa0a3322二a3(aa1)a2(aa)a1(aa)a0(a1),、3,、2,、，、二(a3a2)a(a2a)a(a?aa0)a(a?a)6329876a(a3aa2aa1aa0)=a3aa2aa1aa0a32332二a3(a-a)a2(a1),a1(aa1)a0(a-a),、3,、2,、，、14/3a(a3a2、17a2aaaa0)=a3aa2a1514a1aaU5,9RS 編碼電路信息符號輸出碼;區(qū)a1a0)a(a2a)a,。aa0)a(a2a1)9,32、121110a(a3aa2aa1aa0)=a

10、3aa2aa1a,32,、，32、,2,、，3、=a3(aaa1)a2(aaa)a1(aa1)a0(aa)aiao)a包a1)=(a3、3,、2,a2ao)a(a3a2ai)a,(a3,a21，GF(24)中乘a10的轉(zhuǎn)換電路如下表示:a2=a3a2,a1-a0a1=a2a1-a0ao=a2a。GF(214)中乘a14電路91032a(a3aa2aa1aa0),、3,、2,、，、二(a3a2a1)a0a2.aa0)a(a2aa0)a凡a0)a3=a3a2-a1GF(214)中乘a10電路GF(24)中乘a14的轉(zhuǎn)換電路如下表示:a2=a2a1a3=a3a2a0=a1a1=a3a1.a0-a0-a0aGF(24)中乘a4的轉(zhuǎn)換電路如下表示:GF(24)中乘a6的轉(zhuǎn)換電路如下表示:al=a3a1a0GF(214)中乘a6電路GF(24)中乘a9的轉(zhuǎn)換電路如下表?。篴3=a3a2a0a2=a3a2a1a1=a3a2a1a0a0=a3a1a3=a0a1=a2a2=a3a?=a3aia。a2=a2a0a0-a3a0GF(214)中乘a14電路a0=a2ai15,9,7RSRS 編碼器具體實現(xiàn)電路如下圖所示:表示撤JI1工作過程如下：(1)(1)門打開，開關(guān)撥到符號輸入端，所有移存器清 0000 然后將 6 6 個 1616 進制信息符號，一邊送入移存器，一邊送入信道。注意每一節(jié)拍移動一