第7章7-9(RS码)学生用课件.ppt

1、 7.0 概述概述 7.1 数字电视基带传输编码码型与扰码数字电视基带传输编码码型与扰码 7.2 无码间干扰基带传输无码间干扰基带传输 7.3 二进制数字电视信号的调制传输二进制数字电视信号的调制传输 7.4 多进制数字电视信号的调制传输多进制数字电视信号的调制传输 7.5 纠错编码概述纠错编码概述 7.6 线性分组码线性分组码 7.7 循环码循环码 7.9 里德里德-索罗门码索罗门码 7.10 交织及去交织交织及去交织 7.11 卷积编码与维特比解码卷积编码与维特比解码 7.12 正交频分复用调制正交频分复用调制主要内容主要内容7.9.1 概述 7.9.2 本原多项式与有限域7.9.3 RS

2、码的纠错原理7.9 7.9 里德里德-索罗门码索罗门码7.9.1 7.9.1 概述概述 里德里德-索罗门索罗门(Reed-Solomon)码码（简称（简称RS码）码）u RS码码(n,k,t)是一种是一种多元多元(2m元元)循环码循环码 一个码字：一个码字：C=Cn-1 Cn-2 C1 C0 Ci GF(2m)码多项式：码多项式：C(x)=Cn-1 xn-1+Cn-2 xn-2+C1x+C0 Ci GF(2m)各码元各码元Ci 是由是由m位二进制码组成的符号位二进制码组成的符号uRS码码(n,k,t)的参数：的参数：码长码长:n 2m-1 (符号符号)信息长信息长:k (符号符号)纠错能力：纠

3、错能力：t=(n-k)/2 (符号符号)监督码长：监督码长：n-k=2t(符号符号)(n,k)可截短，如可截短，如m=8：RS(255,239,8)截短截短 RS(204,188,8)多进制码，即q=2m进制码元Ci属于伽罗华域uRS码码(n,k,t)是一种是一种多元多元(2m元元)循环码循环码uRS码码(n,k,t)的参数：的参数：码长码长:n 2m-1 (符号符号)信息长信息长:k (符号符号)纠错能力：纠错能力：t=(n-k)/2 (符号符号)监督码长：监督码长：n-k=2t(符号符号)uRS码是一种码是一种 能纠突发错误的好码能纠突发错误的好码 编码率编码率k/n最大（给定最大（给定t

4、时）时）最小码距最小码距 d0=2t+1 生成多项式生成多项式:g(x)=(x+a a)(x+a a2)(x+a a2t)共共2t+1项，全为非零项，全为非零 W=2t+1=d0 例：笔记例：笔记 7.9.1 7.9.1 概述概述7.9.2 7.9.2 本原多项式与有限域本原多项式与有限域域域F是定义了加、乘运算的非空集合是定义了加、乘运算的非空集合 加、乘运算满足封闭性、交换律、结合律、分配律加、乘运算满足封闭性、交换律、结合律、分配律 对于加运算（对于加运算（+）：）：有恒等元有恒等元 0，任何元素，任何元素a有逆元有逆元(-a)，a+(-a)=0 对于乘运算（对于乘运算（）：）：有恒等元

5、有恒等元 1，任何非零元素，任何非零元素a有逆元有逆元a-1，a a-1=1因此，必有四则运算因此，必有四则运算例如：实数域例如：实数域 复数域复数域 但整数不能构成域但整数不能构成域 一一 域（域（F,FieldF,Field）二二 有限域（又称伽罗华域有限域（又称伽罗华域 GFGF，Galois FieldGalois Field）有限域有限域GF(q)元素个数有限元素个数有限(q)个的域个的域1 素域素域 GF(q)(q为素数为素数)0,1,2,q-1 加、乘运算：模加、乘运算：模q运算运算 模模q运算的剩余类全体构成运算的剩余类全体构成GF(q)如：如：GF(2):0,1 -1=1,1

6、-1=1 GF(5):0,1,2,3,4 -4=?4+1=0 -4=1 4-1=?44=1 4-1=4 2 2 素域的扩展域素域的扩展域 GF(qGF(qm m)(q)(q为素数为素数)GF(qm)系数取自系数取自GF(q)的的(m-1)次多项式的集合次多项式的集合 共有共有n=qm-1个非零元个非零元 如如GF(23)：0,1,x,x+1,x2,x2+1,x2+x,x2+x+1 运算：加运算：加“+”：系数模：系数模q加加 乘乘“”：模：模G(x)乘，乘，G(x)是是GF(qm)的的本原多项式本原多项式二二 有限域（又称伽罗华域有限域（又称伽罗华域 GFGF）GF(qm)的本原多项式的本原多

7、项式G(x)系数取自系数取自GF(q)的的m次即约多项式，且可整除次即约多项式，且可整除xn+1 (n=qm-1)如如GF(23)的本原多项式：的本原多项式：G(x)=x3+x+1 m=3,n=23-1=7 x7+1=(x+1)(x3+x+1)(x3+x2+1)2 2 素域的扩展域素域的扩展域 GF(qmGF(qm)(q)(q为素数为素数)二二 有限域有限域各次本原多项式各次本原多项式G(x)：x3+x+1 x4+x+1 x5+x2+1 x6+x+1 x7+x3+1 x8+x4+x3+x2+1 x9+x4+1 x10+x3+1 x11+x2+1 x12+x6+x4+1 二二 有限域有限域2 2

8、 素域的扩展域素域的扩展域 GF(qmGF(qm)(q)(q为素数为素数)由此看到，由此看到，GF(2m)的元素可进行加减乘除四则运算的元素可进行加减乘除四则运算 减法加上加逆元减法加上加逆元 （-a）除法乘以乘逆元除法乘以乘逆元 （a-1）而且，而且，GF(2m)的四则运算具有封闭性的四则运算具有封闭性在在RS码中，码中，GF(2m)的元素与码元符号相对应：的元素与码元符号相对应：如如 GF(23)：0,1,x,x+1,x2,x2+1,x2+x,x2+x+1 与与 000,001,010,011,100,101,110,111相对应相对应 RS码的码多项式码的码多项式 C(x)=Cn-1 x

9、n-1+Cn-2 xn-2+C1x+C0 Ci GF(2m)二二 有限域有限域2 素域的扩展域素域的扩展域 GF(qm)(q为素数为素数)三三 有限域的本原元有限域的本原元元素元素a的级的级n满足满足an=1的最小正整数的最小正整数n为为a的级的级如如GF(7):元素元素2的级数的级数n=?23=1 n=3 (虽然虽然26=1)n级元素级元素a可表示可表示GF(q)中中n个非零元素个非零元素a0,a1,an-1证：由乘法的封闭性可知，证：由乘法的封闭性可知，a0,a1,an-1 GF(q)用反证法证明用反证法证明 a0,a1,an-1互不相同互不相同 假设假设 ai=aj,0j i n,则则

10、a(i-j)=1 ,0(i-j)n,与与n最小相矛盾最小相矛盾 因此因此 aiaj (证毕证毕)元素元素a的级的级n满足满足an=1的最小正整数的最小正整数n为为a的级的级n级元素级元素a可表示可表示GF(q)中中n个非零元素个非零元素 a0,a1,an-1如如GF(7):0,1,2,3,4,5,6 2为为3级，因为级，因为 23=81，3是满足是满足2n=1的最小正整数的最小正整数 2可表示可表示3个元素个元素:20=1,21=2,22=4 3为为6级，因为级，因为 36=729104711，6是满足是满足3n=1的最小的最小 正整数正整数 3 可表示可表示6个元素个元素:30=1,31=3

11、,32=2,33=27=6,34=81=4,35=243=5 (36=729=1)GF(7)中的中的3为为671级，可表示级，可表示 GF(7)的一切非零元素，的一切非零元素，称称 3是是GF(7)的的本原元本原元三三 有限域的本原元有限域的本原元元素元素a的级的级n满足满足an=1的最小正整数的最小正整数n为为a的级的级n级元素级元素a可表示可表示GF(q)中中n个非零元素个非零元素 a0,a1,an-1本原元本原元a a：若：若a a GF(q)且为且为n=q-1级，则级，则a a为本原元为本原元(生成元生成元)用用a a i(i=0,1,n-1)可表示可表示 GF(q)的一切非零元的一切

12、非零元如如 GF(7):3为为6级，级，因此因此3是是GF(7)的本原元的本原元 3可表示可表示GF(7)的所有的所有非零元非零元 30=1,31=3,32=2,33=6,34=4,35=5 3i适合于乘除：适合于乘除：如：如：4/5=(34)/(35)=3-1=36-1=35=5 (25 mod 7=4)45=39=33=6 (20 mod 7=6)三三 有限域的本原元有限域的本原元四四 多项式有限域多项式有限域GF(2GF(2m m)的本原元的本原元 a a=x本原元本原元a a：若：若a a GF(q)且为且为n=q-1级，则级，则a a为本原元为本原元(生成元生成元)GF(2m)的本原

13、元的本原元 a a=x 证：证：设设 n=2m-1,则则 xn=1 mod G(x)x为n级元素级元素 （证毕）（证毕）在数字电视中，在数字电视中，m=8，a a=02H用用a ai(i=0,1,6)表示表示 GF(23)的非零元的非零元 G(x)=x3+x+1 a a0=1 001 a a1=x 010 a a2=x2 100 a a3=x3=x+1 011 a a4=x4=x2+x 110 a a5=x5=x3+x2=x2+x+1 111 a a6=x6=x3+x2+x=x2+1 101 1 0 00 1 00 0 11 1 00 1 11 1 11 0 1D1D2D3四四 多项式有限域多

14、项式有限域GF(2m)的本原元的本原元 a a=xGF(2m)的元素的的元素的3种表示形式种表示形式（以（以m=3为例）为例）GF(2m)上的四则运算上的四则运算加减：用矢量表示，模加减：用矢量表示，模2加加乘除：用乘除：用a ai表示，注意：表示，注意：a an=a a0=1 (n=2m-1)如如 GF(23)上计算：上计算：1.(x2)-1 2.a a3+a a4+a a9+a a2 3.(1+x)/(1+x2)解：解：1.(x2)-1=a a-2=a a7-2=a a5=x2+x+1 2.a a3+a a4+a a9+a a2=a a3+a a4+a a2+a a2=a a3+a a4=

15、011+110=101=a a6 3.(1+x)/(1+x2)=a a3/a a6=a a-3=a a7-3=a a4=x2+x0，a ai 0 a a0 a a1 a a2 a a3 a a4 a a5 a a6多项式多项式 0 1 x1 x2 x+1 x2+x x2+x+1 x2+1 矢量矢量 000 001 010 100 011 110 111 101五五 x xn n-1=0-1=0的的n n个根个根方程方程 xn-1=0的的n个根是的个根是的n=q-1个非零元个非零元:a ai(i=0,n-1)证：证：设设 b b=a ai GF(q)b b n=(a ai)n=(a an)i=(

16、1)i=1 即即 b b n-1=0 b b是方程是方程 xn-1=0的根的根 证毕证毕如：如：GF(23):x7+1=(x+1)(x3+x+1)(x3+x2+1)(x+1)=0的根的根:a a0 (x3+x+1)=0的根的根:a a、a a2、a a4 (x3+x2+1)=0的根的根:a a3、a a5、a a6可以验证：可以验证：(x3+x+1)|x=a a2=a a6+a a2+1=101+100+001=000=00，a ai 0 a a0 a a1 a a2 a a3 a a4 a a5 a a6矢量矢量 000 001 010 100 011 110 111 1017.9.3 RS

17、7.9.3 RS码的纠错原理码的纠错原理RS码的码元码的码元:是有限域是有限域GF(2m)的元素的元素,以以 m bit为一为一 个符号个符号 C=Cn-1 Cn-2 C1 C0 Ci GF(2m)GF(2m)是次数低于是次数低于m的、系数取自的、系数取自GF(2)的多项式集合的多项式集合 GF(2m)的运算的运算:系数模系数模2加加,多项式模多项式模G(x)乘乘,G(x)为为 m 次本原多项式次本原多项式 GF(2m)的任何非零元素都是的任何非零元素都是本原本原元的幂元的幂RS(n,k)是是多元分组循环码多元分组循环码,码长度码长度:n 2m-1 符号符号 纠错能力纠错能力:t=(n k)/

18、2 符号符号码多项式码多项式 C(x)是生成多项式是生成多项式 g(x)的倍式的倍式 即即 C(x)=p(x)g(x)一一 编码编码编码的步骤：编码的步骤：1 确定有限域确定有限域 GF(2m)及其元素及其元素确定一个符号的位数确定一个符号的位数 m,共有共有2m种符号种符号 确定确定m次本原多项式次本原多项式G(x)m=3:G(x)=x3+x+1 m=4:G(x)=x4+x+1 m=8:G(x)=x8+x4+x3+x2+1 确定确定GF(2m)上的上的2m个符号个符号(元素元素):0,1,a a,a a2,a a2m-2 a ai与矢量表示的符号之间的对应关系与矢量表示的符号之间的对应关系1

19、 确定有限域确定有限域 GF(2m)及其元素及其元素2 确定生成多项式确定生成多项式 g(x)纠错能力纠错能力 t 生成多项式生成多项式 g(x)2t-1 g(x)=(x-a ai)=(x-1)(x-a a)(x-a a2t-1)i=0 2t g(x)=(x-a ai)=(x-a a)(x-a a2)(x-a a2t)i=1 展开后展开后,得多项式：得多项式：g(x)=x2t+g2t-1x2t-1+g1 x+g0一一 编码编码一一 编码编码1确定有限域确定有限域 GF(2m)及其元素及其元素2确定生成多项式确定生成多项式 g(x)3 确定码元长确定码元长 n和信息元长和信息元长 k 码元长码元

20、长 n 2m-1,信息元长信息元长 k=n-2t,监督元长监督元长 n-k=2t一一 编码编码1确定有限域确定有限域 GF(2m)及其元素及其元素2确定生成多项式确定生成多项式 g(x)3 确定码元长确定码元长 n和信息元长和信息元长 k 4 编码编码由于由于RS码是循环码，任何码字是码是循环码，任何码字是g(x)的倍式的倍式因此：可通过因此：可通过xn-km(x)除以除以g(x)求余数得到监求余数得到监督码元督码元 C(xC(x)=xn-km(x)+xn-km(x)mod mod g(x)一一 编码编码 4 编码编码由于由于RSRS码是循环码，任何码字是码是循环码，任何码字是g(xg(x)的

21、倍式的倍式.因此：因此：可通过可通过x xn-kn-km(xm(x)除以除以g(x(x)求余数得到监督码元求余数得到监督码元 C(xC(x)=x xn-kn-km(xm(x)+x)+xn-kn-km(xm(x)mod)mod g(x(x)编码电路原理：编码电路原理：g(x)=xn-k+gn-k-1 xn-k-1 +g2 x2+g1 x+g0D1D2gn-k-1Dn-kg1g2g0一一 编码编码 如：如：m=3,t=2 可构成可构成(7,3,2)码码1 有限域有限域 GF(23),本原多项式本原多项式 G(x)=x3+x+1 8个元素：个元素：0，a ai 0 a a0 a a1 a a2 a

22、a3 a a4 a a5 a a6 矢量矢量 000 001 010 100 011 110 111 1012 生成多项式生成多项式 g(x)=(x+1)(x+a a)(x+a a2)(x+a a3)g(x)=x4+a a3 x3+a a5 x2+a a5 x+a a6 D1D2a a3D4a a5a a6D3a a5一一 编码编码有限域有限域 GF(23),G(x)=x3+x+1 0，a ai 0 a a0 a a1 a a2 a a3 a a4 a a5 a a6矢量矢量 000 001 010 100 011 110 111 101生成多项式生成多项式 g(x)=(x+a a0)(x+a

23、 a1)(x+a a2)(x+a a3)g(x)=x4+a a2 x3+a a5 x2+a a5 x+a a6 g(x)是是RS(7,3,2)码中次数最低码中次数最低(7-3=4次次)的码多项式：的码多项式：对应的信息：对应的信息：M=0 0 10 0 1 0 0 0 01 a a2 a a5 a a5a a6 11 a a2 a a5 a a5a a6a a2 a a5 a a5a a6C=0 0 C=0 0 1 a a2 a a5 a a5a a6 或C=C=000 000 001 100 111 111 101 一一 编码编码有限域有限域 GF(23),G(x)=x3+x+1 0，a a

24、i 0 a a0 a a1 a a2 a a3 a a4 a a5 a a6 矢量矢量 000 001 010 100 011 110 111 101生成多项式生成多项式 g(x)=(x+a a0)(x+a a1)(x+a a2)(x+a a3)g(x)=x4+a a2 x3+a a5 x2+a a5x+a a6 xg(x)x5+a a2 x4+a a5 x3+a a5 x2+a a6x 也是也是RS(7,3,2)码中的码多项式：码中的码多项式：对应的信息：对应的信息：M=0 1 a a2 0 1 a a2 0 0 0 01 a a2 a a5 a a5a a6 11 a a2 a a5a a

25、5 a a6 a a5 a a5a a6 0C=0 C=0 1 a a2 a a5 a a5a a6 0 0 一一 编码编码有限域有限域 GF(23),G(x)=x3+x+1 0，a ai 0 a a0 a a1 a a2 a a3 a a4 a a5 a a6 矢量矢量 000 001 010 100 011 110 111 101生成多项式生成多项式 g(x)=(x+a a0)(x+a a1)(x+a a2)(x+a a3)g(x)=x4+a a2 x3+a a5 x2+a a5 x+a a6 如：如：M=0 a a4 a a5,求求C0 a a4 a a5 0 0 0 01 a a2 a

26、 a5 a a5a a6 a a4a a4 a a6 a a9 a a9 a a10a a a a2 a a2 a a3 a a a a a a3 a a6 a a6 a a7a a5 1 a a4 1 C=C=0 a a4 a a5 a a5 1 a a4 1 解解:或C=C=000 110 111 111 001 110 001 二二 译码译码根据循环码的性质根据循环码的性质:任何码字是任何码字是g(x)的倍式的倍式 C(x)=m(x)g(x)=xn-1 xn-2 x2 x 1 CT根据根据 g(x)=(x-a a0 )(x-a a1)(x-a a 2t-1)有有 C(a ai)=m(a

27、ai)g(a ai)=0 (i=0,2t-1)即即 C(1 )=1 1 1 1 1 CT=0 C(a a )=a a(n-1)a a(n-2)a a2 a a1 1 CT=0 C(a a2t-1)=a a(2t-1)(n-1)a a(2t-1)(n-2)a a(2t-1)2 a a2t-1 1 CT=0 H HC CT=0=0TH=H=1 1 1 1 1a a(n-1)a a(n-2)a a2 a a 1a a(2t-1)(n-1)a a(2t-1)(n-2)a a(2t-1)2 a a2t-1 1(2t(2tn)n)为一致监督矩阵为一致监督矩阵1 一致监督矩阵一致监督矩阵 H二二 译码译码

28、一致监督方程一致监督方程 H HC CT=0=0T设设 R为接收矢量为接收矢量 R=C+E 其中其中 E 为错误图样为错误图样伴随式伴随式 ST=HRT=H(C+E)T=HET当正确接收时当正确接收时,E=0,伴随式伴随式 S=0当有错时当有错时:S:S002 伴随式伴随式 S二二 译码译码一致监督方程一致监督方程 H HC CT=0=0T伴随式伴随式 ST=HRT=H(C+E)T=HET 设有设有k个错误个错误(kt),位于位于:j1,j2,j,jkE(x)=ej1xj1+ejkxjk (kt)ej1 +ejk ej1 a a j1 +ejk a a jkej1 a a(2t-1)j1+ej

29、k a a(2t-1)jk 则则 ST=s0 s1 :s2t-1H=H=1 1 1 1 1a a(n-1)a a(n-2)a a2 a a 1a a(2t-1)(n-1)a a(2t-1)(n-2)a a(2t-1)2 a a2t-1 1(2t(2tn)n)=1 1 1 1 1 1a a(n-1)a a(n-2)a a 1a a(n-1)(2t-1)a a(n-2)(2t-1)a a(2t-1)1en-1en-2 :e1e0=二二 译码译码设设E(x)=ej1xj1+ejkxjk (kt)=ej1 +ejk ej1 a a j1 +ejk a a jkej1 a a(2t-1)j1+ejk a

30、 a(2t-1)jk 则则 ST=s0 s1 :s2t-1根据根据S(2t个方程个方程),求解求解2t个变量个变量:j1 jk (用于定位用于定位)ej1 ejk (错误图样错误图样)根据根据 j1 jk 和和 ej1 ejk 对对rj1 r rjk纠错纠错:cj1=rj1+ej1 cjk=rjk+ejk 对于纠正t=1个错误,需用S的前2个元素二二 译码译码H HC CT=0=0TST=HRT=HET 设设E(x)=elxl n-1则则 s0=ri=el i=0 n-1 s1=a ai ri=el a al i=0 计算计算:s1/s0=a al 定位定位 l el=s0得得 el 纠错纠错

31、:ri+el=cl 重算重算S:S=0H=H=1 1 1 1 1a a(n-1)a a(n-2)a a2 a a 1a a(2t-1)(n-1)a a(2t-1)(n-2)a a(2t-1)2 a a2t-1 13 纠错纠错1个符号的方法个符号的方法例例:(7,3,2)码码,R=0 0 a a6 a a2 a a5 a a5 a a6,有有1个错误符号个错误符号,求求CH=H=1 1 1 1 1 1 1a a6 a a5 a a4 a a3 a a2 a a 1a a12 a a10 a a8 a a6 a a4 a a2 1a a18 a a15 a a12 a a9 a a6 a a3 1

32、解解:n=7,t=2,H为为4 7的矩阵的矩阵 1 1 1 1 1 1 1a a6 a a5 a a4 a a3 a a2 a a 1a a5 a a3 a a a a6 a a4 a a2 1a a4 a a a a5 a a2 a a6 a a3 1=s0=ri=a a6+a a2+a a5+a a5+a a6=a a2s1=a ai ri=a a6 a a4+a a2a a3+a a5 a a2+a a5a a+a a6=a a3+a a5+1+a a6+a a6 =1+a a3+a a5=a a6 s1/s0=a a4 l=4 e4=s0=a a2 c4 =r4+e4=a a6+a a

33、2=1 C=0 0 1 a a2 a a5 a a5 a a6 7.9.3 RS7.9.3 RS码的纠错原理码的纠错原理三三 数字电视中的数字电视中的RS码码数字电视中数字电视中,m=8 有限域为有限域为GF(28)本原多项式本原多项式:G(x)=x8+x4+x3+x2+1=11DH=285DVB制式制式:t=8,k=188 n=k+2t=204 RS(204,188,8)生成多项式生成多项式:g(x)=(x+a a)(x+a a2)(x+a a16)ATSC制式制式:t=10,k=187 n=k+2t=207 RS(207,187,10)生成多项式生成多项式:g(x)=(x+a a0)(x+a a1)(x+a a19)g(x)=(x+a0)(x+a1)(x+a2).(x+a19)=x20+152x19+185x18+240 x17+5x16+111x15+99x14+6x13 +220 x12+112x11+150 x10+69x9+36x8+187x7+22x6+228x5 +198x4+121x3+121x2+165x1+174