1、RS碼編碼算法RS編碼對于能夠糾正t個錯誤的RS( n,k,d )碼，具有如下特征：1) 碼長：n =2m -1符號或m(2m-1)比特2) 信息碼元數：k二n - 2t或mk比特；3) 監督碼元數：n - k = 2t符號或m(n - k)比特；4) 最小距離：d = 2t T二n - k 1符號或m(n - k T)比特;最小距離為d的本原RS碼的生成多項式為g(x) = (x - ： )(x - ： 2)(x - ： 3) (x - ： d -2)式中的m是一個任意整數。令信息元多項式為：2 k 1m(x) =m0 m1 m2x 亠亠 mk-1x二.RS編碼器的類型1 .基于乘法形式的R

2、S編碼器公式：c(x)二 m(x)g(x)結構圖如下：輸入%JiLlc (x)-噸浪編嗎器由上面結構的乘法編碼器輸出的碼字是非系統碼2 .基于除法形式的RS編碼器(1)根據生成多項式g(x)構造的除法編碼器。xnka(x)g(x)b(x)器剩余多項式r(x)至少比g(x)低一次r(x) = r2t_1x21r2t-2x2t_2r2x2 jx r0則編程的碼多項式為c(x)二 xn-ka(x) r(x)c2x輸出碼2c1xc0n 1 丄n 2二 cn_1xcn_2x除法電路構成的RS編碼辭(2)根據校驗碼多項式h(x)構造的除法編碼器設校驗多項式為：h(x) = hkxkhkx11 亠 亠 h1

3、x h0系統碼的多項式為:C(X)二C n_iXn5 _2乂"25kx" 5 _必1 Cq它的前k位系數：Cn _1,Cn_2，Cn _k是已知的信息位，而后n-k位系數:Cn _k_1,Cn_2，,C1,C0是需求的校驗位。碼多項式必是生成多項式 g(x)的背 式，所以C(x) =q(x)g(x)C(x)乞 n _ 1,： g(x) = n _ k,r 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) - n - 1, g(x)二 n - k, g(x)二 n - k, q(x)

4、- k - 1所以q(x)xn的最低位次數至少為n次，而在h(x)C(x)的乘積中xn T,x門一2,xk的次數為0。X1的系數：Cn _1h° C n_i_ihi C n_i_khkxn _2的系數：Cn _2血 Cn_2_lhiCn_2_khk而k工 Cn jhj =0i = 0,1,2,，n - kro由于h(x)為首一多項式，hk =1，故上式可寫為k -1Cn_k_i 八' Cnijhji = 1,2, ,n-kj=0上式展開為：Cn -k = -(Cn-1ho Cn_2hiCn-khk-1)Cn _k_2 = (Cn_2ho Cn -3h1 Cn-k-1hk-1)

5、-Cn -k-(n-k) - Co 八(Ckho “柑qhk_1)由上式看出碼字C的第一個碼元Cn kJ可由k個信息元Cn _1,C n_2,，c n_k與h(x)的系數相乘得到，而由Cn _2,C n<,，C n_k,C n _k J可得到第二個校驗元Cn _k _2，再由Cn _3, ,C n _k信息元和第一、第二校驗元 5 _k_1,C n_k2可得到第三校驗元Cn _k_3。按這樣的線性關系遞推，一直可求得所有的n - k個校驗'“ B兀 Cn -k -1，Cn -k -2，C1, Co 0瓦循壞碼k級編碼器(3) RS的時域編碼實際例子RS碼是非二進制碼，它是在GF(

6、q)上的，這里q= 2。這里我們選用GF(16)域來進行，域中16個元素可用4bits符號表示。例 構造一個能糾正3個錯誤符號，碼長為15, m=4的RS碼。求生成多項式和 編碼電路。解：當t = 3時，最小碼距D min = 7，信息元長度k = 9。該碼為(15， 9) RS碼，其生成多項式為：g(x) = (x a)(x a2 )(x a3)(x a4)(x a5)(x a6=x6 - a10x5 a14x4 - a4x3 a6x2 a9x a6由分圓多項式多項式：g(x) = (x2 x 1)(x4 x 1)a GF(16)是本原域元素，它是多項式x4 x 1的根，則a4 a 1 =

7、0或a4 = a 1以x4 x 1為模的GF(24)的元素如下表：a0 =1000182斗a = a +10101a001093a = a + a10102 a0100a = a + a + 101113 a1000113 丄2a = a + a + a1110a4 = a + 10011a =a + a +a + 11111a5 = a2 + a0110a = a + a + 1110163+2a = a + a1100a = a + 11001a = a + a +1101115.a =10001GF(24)中每個元素都可表示成它的自然基地1,a,a2,a3 (在域GF(2)上)的線 性組

8、合，如下形式：32asaa?aaaa°14信息符號L15p9JRS編創電路圖TICD因此在GF(24)上的24進制RS碼，它的編碼電路可用k或n-k級24進制寄存 器實現。本例是用n -k = 6級乘法器電路實現，如下圖。圖中的移位積存器必須是由能積存16進制的元件組成，這可用4級觸發器組成的移存器完成。a10,a14,a4,a6,a9常乘器可用模2加法器構成。輸出碼在域GF(24)上的系數a10,a14,a4,a6,a9可用自然基地表示為如下形式:1032131211103 a23 a2a(83aa?aaaa°)-83aa?aaaa°a= a3(a3 a21)

9、a2(a3 a2 a 1) a1(a3 a2 a) a0(a2 a 1)=3a2aja3(a?a?aa°)a2(a?aa°)a(a?a。)14/32、17161514a(a3aa2aa1aa0)=a3aa2aa1aa32=a°aa3aa?a (aa。)4 320765 -.4a (a3aa2aa1a a0a ) =a3a a2a a1a a0a= a3(a3a 1)a2(a3 a2)a1(a2 a)a0(a1)=3 a?)a3 (a? aja2 (a?aa°)a a。)63 2.9 876a (a3aa2a a1aa0)=a3a a2aa1aa0a二 a

10、3(a3a) a2(a21) a1(a3a 1)a0(a3a2)3 2=3 a1 ao)a(a? a°)a 3 a a°)a (a? aja9(a3a3 a2a2 a1a a0)=a3a12 a2a11 a1a10 a0a9ai a°)a a)=a3(a3 a2 a 1) a2(a3 a2 a) a1(a2 a 1) a0(a3 a) =3 a2 a°)a3 Q3 a? aja2 Q3 a?a10(a3a3 +a2a2 +aa + a0)=3 +a? +a)a3 +(a3 +a?+ 印 + a°)a2 + (a?式中：a3'=a3 +a

11、2 十 aa2= 83+ a? + aa*=a2 +a +a0a0 | = a2 + a0j'a：'GF(24)中乘a10的轉換電路如下表示:ai a°)a (a? a。)aH JL I IH l HKa。GF(214)中乘a10電路GF(24)中乘a14的轉換電路如下表示:ai a?a?'= a? aiGF(214)中乘a14電路a31 = a3a?GF(24)中乘a4的轉換電路如下表示:a31 二 a。二 a3a* = a2a。' = a3aGF(214)中乘a14電路GF(24)中乘a6的轉換電路如下表示:a3> a3a1a0a2 丨 a2a0aj = a3 - aia。ao'pai1GF(214)中乘a6電路GF(24)中乘a9的轉換電路如下表示:a3 J a3a2a0a? i = a3a?aiai、a3 a2 aa。ao'a?aiGF(214)中乘a9電路15,9,7 RS編碼器具體實現電路如下圖所示:符界輸入9f ?RS編碼瞬工作過程如下：(1) 門打開，開關撥到符號