《信息论与编码循环码精选PPT.ppt》由会员分享，可在线阅读，更多相关《信息论与编码循环码精选PPT.ppt（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息论与编码循环码信息论与编码循环码1第1页，此课件共35页哦线性分组码的一般原理线性分组码的构造H矩阵（监督阵）H AT=0T 或或A HT=0监督阵2第2页，此课件共35页哦H矩阵的性质：H的行数就是监督关系式的数目，等于监督位个数r。典型监督阵可分解为P Ir形式，P为r k阶矩阵，Ir 为r r阶单位方阵。由代数理论可知，H矩阵的各行应该是线性无关的 3第3页，此课件共35页哦生成阵如果找到了码的生成矩阵G，则编码的方法就完全确定了。具有IkQ形式的生成矩阵称为典型生成矩阵典型生成矩阵。系统码4第4页，此课件共35页哦G矩阵的性质：G矩阵的各行是线性无关的。G的各行本身就是一个码组。如
2、果已有k个线性无关的码组，则可以用其作 为生成矩阵G。5第5页，此课件共35页哦错误图样 B A=E错误图样接收码发送码6第6页，此课件共35页哦2.监督矩阵H和生成矩阵G（1）监督矩阵第7页，此课件共35页哦我我们们把把H称称为为监监督督矩矩阵阵，或或称称一一致致校校验验矩矩阵阵，一一旦旦H给给定定，信信息息位位和和监监督督位位之之间间的的关关系系也也就就确确定定了了。H为为 rn阶阶矩矩阵阵，H矩矩阵阵每每行行之之间间是是彼彼此此线线性性无无关关的的。H矩矩阵阵可可分分成成两两部部分分，其其中中P为为rk阶阶矩矩阵阵，Ir为为rr阶阶单单位位阵阵。能能写写成成H=PIr形形式式的的矩矩阵称
3、为典型监督矩阵。阵称为典型监督矩阵。第8页，此课件共35页哦（2）生成矩阵第9页，此课件共35页哦称称为为生生成成矩矩阵阵，由由G和和信信息息组组就就可可以以产产生生全全部部码码字字。G为为kn阶阶矩矩阵阵，各各行行也也是是线线性性无无关关的的。生生成成矩矩阵阵也也可可以以分分为为两两部部分分：其其中中Q为为kr阶阶矩矩阵阵，Ik为为k阶阶单单位位阵阵，可可以以写写成成式式（8-12）形形式式的的G矩矩阵阵，称称为为典典型型生生成成矩矩阵阵。非非典典型型形形式式的的矩矩阵阵经经过过运运算算也一定可以化为典型矩阵形式。也一定可以化为典型矩阵形式。第10页，此课件共35页哦（3）监督矩阵H和生成矩
4、阵G之间的关系由由上上可可知知，监监督督矩矩阵阵H和和生生成成矩矩阵阵G之之间间有有一一一一对对应应的的关关系系。由由于于G的的每每一一行行都为码字，因此它必然满足式都为码字，因此它必然满足式HAT=0T即即HGT=0T第11页，此课件共35页哦3.线性分组码的译码伴随式（校正子）S若若某某一一码码字字为为许许用用码码组组，则则它它必必然然满满足足式式。利利用用这这一一关关系系，在在接接收收端端将将收收到到的的码码组组和和事事先先与与发发端端约约定定好好的的监监督督矩矩阵阵相相乘乘，看看是是否否为为零零。若若满满足足条条件件，则则认认为为接接收收正正确确；反反之之，则则认认为为传传输输过过程程
5、中中发发生生了了错错误误，进而设法确定错误的数目和位置。进而设法确定错误的数目和位置。第12页，此课件共35页哦w例：设分组码分组码(n,k)中k=4，为了纠正1位错码，由上式可知，要求监督位数 r 3。若取 r=3，则n=k+r=7。S1 S2 S3错码位错码位置置S1 S2 S3错码位错码位置置001a0101a4010a1110a5100a2111a6011a3000无错码无错码错码位置与校正子关系监督关系式13第13页，此课件共35页哦令令S=BHT，称为伴随式或校正子。，称为伴随式或校正子。S=BHT=（A+E）HT=EHT由由此此可可见见，伴伴随随式式S与与错错误误图图样样E之之间
6、间有有确确定定的的线线性性变变换换关关系系，与与发发送送码码组组A无无关关。接接收收端端译译码码器器的的任任务务就就是是从从伴伴随随式式确确定定错错误误图图样样，然然后后从从接接收收到到的的码码字字中中减减去去错错误误图样。图样。第14页，此课件共35页哦从从以以上上分分析析可可以以得得出出线线性性分分组组码码译译码码的基本步骤：的基本步骤：计算接收码组计算接收码组B的伴随式的伴随式S；根根据据S找找出出错错误误图图样样E，判判定定误误码码位置；位置；根根据据E纠纠正正错错误误，得得到到正正确确的的码码组组A=E+B。第15页，此课件共35页哦错误图样和伴随式定义：定义：发送码字c=(c1,c
7、2,cn)经过有扰信道得到接收向量v=(v1,v2,vn)，则称e=(e1,e2,en)为错误图样错误图样，其中ei=vi ci。定义：定义：设码C的校验矩阵为H，接收向量v的伴随式伴随式为s=v HT。16第16页，此课件共35页哦译码步骤1）由接收向量v计算伴随式s；2）由伴随式s求得错误图样e；3）c=v e。17第17页，此课件共35页哦循环码循环码18第18页，此课件共35页哦 循环码的概念：循环码的概念：循环码的概念：循环码的概念：循环性是指任一码组字循环一位后仍然是该编码中的一个码字。循环性是指任一码组字循环一位后仍然是该编码中的一个码字。循环性是指任一码组字循环一位后仍然是该编
8、码中的一个码字。循环性是指任一码组字循环一位后仍然是该编码中的一个码字。例：一种例：一种(7,3)(7,3)循环码的全部码字如下循环码的全部码字如下 表中第表中第2 2码字向右移一位即得到第码字向右移一位即得到第5 5码字；第码字；第5 5码字向右移码字向右移一位即得到第一位即得到第7 7码字。码字。码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001019第19页，此课件共35页哦一般情况一般情况 若若(a an n-1-1
9、 a an n-2-2 a a0 0)是循环码的一个码字，则循环移位后的码是循环码的一个码字，则循环移位后的码字：字：(a an n-2-2 a an n-3-3 a a0 0 a an n-1-1)(a an n-3-3 a an n-4-4 a an n-1-1 a an n-2-2)(a a0 0 a an n-1-1 a a2 2 a a1 1)仍然是该编码中的码字。仍然是该编码中的码字。多项式表示法多项式表示法一个长度为一个长度为n n的码字的码字(a an n-1-1 a an n-2-2 a a0 0)可以表示成可以表示成 上式中上式中x x 的值没有任何意义，仅用它的幂代表码元
10、的位置。的值没有任何意义，仅用它的幂代表码元的位置。例：码字例：码字1 1 0 0 1 0 11 1 0 0 1 0 1可以表示为可以表示为 20第20页，此课件共35页哦循环码的运算循环码的运算 整数的按模运算整数的按模运算在整数运算中，有模在整数运算中，有模n n运算。例如，在模运算。例如，在模2 2运算中，有运算中，有1+1=2 1+1=2 0(0(模模2)2)，1+2=3 1+2=3 1(1(模模2)2)，2 2 3=6 3=6 0(0(模模2)2)等等。等等。一般说来，若一个整数一般说来，若一个整数m m可以表示为可以表示为式中，式中，Q Q为整数，则在模为整数，则在模n n运算下，
11、有运算下，有m m p p (模模n n)所以，在模所以，在模n n运算下，一个整数运算下，一个整数m m等于它被等于它被n n除得的余数。除得的余数。21第21页，此课件共35页哦码多项式的按模运算码多项式的按模运算 若任意一个多项式若任意一个多项式F F(x x)被一个被一个n n次多项式次多项式N N(x x)除，得到商除，得到商式式Q Q(x x)和一个次数小于和一个次数小于n n的余式的余式R R(x x)，即，即则在按模则在按模N N(x x)运算下，有运算下，有这时，码多项式系数仍按模这时，码多项式系数仍按模2 2运算。运算。例例1 1：x x3 3被被(x(x3 3+1)+1)
12、除，得到余项除，得到余项1 1，即，即 例例2 2：因为因为x xx x3 3+1 +1 x x4 4+x x2 2+1+1x x4 4+x x x x2 2+x x+1 +1 在模在模2 2运算中加法和减法一样。运算中加法和减法一样。22第22页，此课件共35页哦循环码的数学表示法循环码的数学表示法 在循环码中，设在循环码中，设T(T(x x)是一个长度为是一个长度为n n的码字，若的码字，若则则T T (x x)也是该编码中的一个码字。也是该编码中的一个码字。证证 设一循环码为设一循环码为 则有则有 上式中的上式中的T T (x x)正是码组正是码组T T(x x)向左循环移位向左循环移位
13、 i i 次的结果。次的结果。例：例：一循环码为一循环码为11001011100101，即，即 若给定若给定 i i=3=3，则有，则有 上式对应的码组为上式对应的码组为01011100101110，它正是，它正是T T(x x)向左移向左移3 3位的结果。位的结果。结论：一个长为结论：一个长为n n的循环码必定为按模的循环码必定为按模(x xn n+1)+1)运算的一个余式。运算的一个余式。23第23页，此课件共35页哦循环码的生成循环码的生成 n n如果有了生成矩阵如果有了生成矩阵G G，就可以由，就可以由k k个信息位得出整个码字个信息位得出整个码字A A：例例:(7,4):(7,4)码
14、码式中，式中，生成矩阵生成矩阵G G的每一行都是一个码组。的每一行都是一个码组。n n因此，若能找到因此，若能找到 k k 个已知的码字，就能构成矩阵个已知的码字，就能构成矩阵G G。如前所。如前所述，这述，这k k个已知码组必须是线性不相关的。个已知码组必须是线性不相关的。n n在循环码中，一个在循环码中，一个(n n,k k)码有码有2 2k k个不同的码字。若用个不同的码字。若用g g(x x)表示表示其中前其中前(k k-1)-1)位皆为位皆为“0”0”的码字，则的码字，则g g(x x)，x gx g(x x)，x x2 2 g g(x x)，x xk-1k-1 g g(x x)都是
15、码组，而且这都是码组，而且这k k个码组是线性无关的。因此个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵它们可以用来构成此循环码的生成矩阵G G。24第24页，此课件共35页哦l l在循环码中除全在循环码中除全在循环码中除全在循环码中除全“0”0”码组外，再没有连续码组外，再没有连续码组外，再没有连续码组外，再没有连续k k位均为位均为位均为位均为“0”0”的码组。的码组。的码组。的码组。否则，在经过若干次循环移位后将得到否则，在经过若干次循环移位后将得到否则，在经过若干次循环移位后将得到否则，在经过若干次循环移位后将得到k k位信息位全为位信息位全为位信息位全为位信息位全为“0”
16、0”，但监，但监，但监，但监督位不全为督位不全为督位不全为督位不全为“0”0”的一个码组。这在线性码中显然是不可能的。的一个码组。这在线性码中显然是不可能的。的一个码组。这在线性码中显然是不可能的。的一个码组。这在线性码中显然是不可能的。l l因此，因此，因此，因此，g g(x x)必须是一个常数项不为必须是一个常数项不为必须是一个常数项不为必须是一个常数项不为“0”0”的的的的(n n-k k)次多项式，而且这个次多项式，而且这个次多项式，而且这个次多项式，而且这个g g(x x)还是这种还是这种还是这种还是这种(n n,k k)码中次数为码中次数为码中次数为码中次数为(n n k k)的唯
17、一一个多项式。因为如果的唯一一个多项式。因为如果的唯一一个多项式。因为如果的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于组多项式的次数将小于组多项式的次数将小于组多项式的次数将小于(n n k k)，即连续，即连续，即连续，即连续“0”0”的个数多于的个数多于的个数多于的个数多于(k k 1)1)。显。显。显。显然，这是与前面的结论矛盾的。然，这是与前面的结
18、论矛盾的。然，这是与前面的结论矛盾的。然，这是与前面的结论矛盾的。l l我们称这唯一的我们称这唯一的我们称这唯一的我们称这唯一的(n n k k)次多项式次多项式次多项式次多项式g g(x x)为码的生成多项式。一旦确定为码的生成多项式。一旦确定为码的生成多项式。一旦确定为码的生成多项式。一旦确定了了了了g g(x x)，则整个，则整个，则整个，则整个(n n,k k)循环码就被确定了。循环码就被确定了。循环码就被确定了。循环码就被确定了。25第25页，此课件共35页哦n n因此，循环码的生成矩阵因此，循环码的生成矩阵G G可以写成可以写成n n例：例：上表中的编码为上表中的编码为(7,3)(
19、7,3)循环码，循环码，n n=7,=7,k k=3,=3,n n k k=4=4，其中唯，其中唯一的一个一的一个(n n k k)=4)=4次码多项式，且前次码多项式，且前(k k-1)=2-1)=2位皆为位皆为“0”0”的码字是第二码字的码字是第二码字00101110010111，与它对应的码多项式，即生成，与它对应的码多项式，即生成多项式，为多项式，为g g(x x)=)=x x4 4+x x2 2+x x+1+1。码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111
20、071100101401110018111001026第26页，此课件共35页哦g g(x x)=)=x x4 4+x x2 2+x x+1 +1 即即 “1 0 1 1 1”1 0 1 1 1”将此将此g g(x x)代入上矩阵，得到代入上矩阵，得到 或或上式不符合上式不符合G G=I Ik kQ Q 形式，所以它不是标准生成矩阵。但形式，所以它不是标准生成矩阵。但它经过线性变换后，不难化成标准阵。它经过线性变换后，不难化成标准阵。此循环码的码字多项式表示式此循环码的码字多项式表示式T T(x x)：上式表明，所有码字多项式上式表明，所有码字多项式T T(x x)都能够被都能够被g g(x
21、x)整除，而整除，而且任意一个次数不大于且任意一个次数不大于(k k 1)1)的多项式乘的多项式乘g g(x x)都是码多项式。都是码多项式。27第27页，此课件共35页哦寻求码生成多项式寻求码生成多项式 因为任意一个循环码因为任意一个循环码T T(x x)都是都是g g(x x)的倍式，故它可以写成的倍式，故它可以写成T T(x x)=)=h h(x x)g g(x x)而生成多项式而生成多项式g(x)g(x)本身也是一个码组，即有本身也是一个码组，即有 T T (x x)=)=g g(x x)由于码字由于码字T T (x x)是一个是一个(n n k k)次多项式，故次多项式，故x xk
22、k T T (x x)是一个是一个n n次多次多项式。由项式。由可知，可知，x xk k T T (x x)在模在模(x(xn n+1)+1)运算下也是一个码组，所以有运算下也是一个码组，所以有上式左端分子和分母都是上式左端分子和分母都是n n次多项式，故相除的商式次多项式，故相除的商式Q Q(x x)=1)=1。因此，上式可以写成因此，上式可以写成28第28页，此课件共35页哦将将 T T(x x)=)=h h(x x)g g(x x)和和 T T (x x)=)=g g(x x)代入代入化简后，得到化简后，得到上式表明，生成多项式上式表明，生成多项式g g(x x)应该是应该是(x xn
23、n+1)+1)的一个因子。的一个因子。例：例：(x x7 7+1)+1)可以分解为可以分解为为了求出为了求出(7,3)(7,3)循环码的生成多项式循环码的生成多项式 g g(x x)，需要从上式，需要从上式中找到一个中找到一个(n kn k)=4)=4次的因子。这样的因子有两个，即次的因子。这样的因子有两个，即以上两式都可以作为生成多项式。以上两式都可以作为生成多项式。选用的生成多项式不同，产生出的循环码码字也不同。选用的生成多项式不同，产生出的循环码码字也不同。29第29页，此课件共35页哦循环码的编码方法循环码的编码方法用用x xn-kn-k乘乘m m(x x)。这一运算实际上是在信息码后
24、附加上。这一运算实际上是在信息码后附加上(n n k k)个个“0”0”。例如，信息码为。例如，信息码为110110，它写成多项式为，它写成多项式为m m(x x)=)=x x2 2+x x。当当n n k k=7 3=4=7 3=4时，时，x xn-kn-k m m(x x)=)=x x4 4(x x2 2+x x)=)=x x6 6+x x5 5，它表示码，它表示码组组11000001100000。用用g g(x x)除除x xn-k n-k m m(x x)，得到商，得到商Q Q(x x)和余式和余式r r(x x)，即有，即有例：若选定例：若选定g g(x x)=)=x x4 4+x
25、x2 2+x x+1+1，则有，则有 上式是用码多项式表示的运算。它和下式等效：上式是用码多项式表示的运算。它和下式等效：编出的码字编出的码字T T(x x)为：为：T T(x x)=)=x xn-k n-k m m(x x)+)+r r(x x)在上例中，在上例中，T T(x x)=1100000+101=1100101)=1100000+101=1100101 30第30页，此课件共35页哦 循环码的解码方法循环码的解码方法循环码的解码方法循环码的解码方法在检错时：当接收码字没有错码时，接收码组在检错时：当接收码字没有错码时，接收码组R R(x x)必定能被必定能被g g(x x)整除，即
26、下式整除，即下式中余项中余项r r(x x)应为零；否则，有误码。应为零；否则，有误码。n n当接收码组中的错码数量过多，超出了编码的检错能力当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被时，有错码的接收码组也可能被g g(x x)整除。这时，错码就整除。这时，错码就不能检出了。不能检出了。在纠错时：在纠错时：n n用生成多项式用生成多项式g g(x x)除接收码组除接收码组R R(x x)，得出余式，得出余式r r(x x)。n n按照余式按照余式r r(x x)，用查表的方法或计算方法得出错误图样，用查表的方法或计算方法得出错误图样E E(x x)。n n从从
27、R(R(x x)中减去中减去E E(x x)，便得到已经纠正错码的原发送码组，便得到已经纠正错码的原发送码组T T(x x)。31第31页，此课件共35页哦2.监督多项式和监督矩阵为为了了便便于于对对循循环环码码编编译译码码，通通常常还还定定义监督多项式，令义监督多项式，令其其中中g（x）是是常常数数项项为为1的的r次次多多项项式式，是是生成多项式；生成多项式；h（x）是常数项为）是常数项为1的的k次多次多项项式式，称称为为监监督督多多项项式式。同同理理，它它的的监监督督矩阵矩阵H第32页，此课件共35页哦第33页，此课件共35页哦根根据据上上述述原原理理，循循环环码码编编码码步步骤骤可可归归
28、纳如下。纳如下。用用xr乘乘m（x）。这这一一运运算算实实际际上上是是把把信信息息码码后后附附加加上上r个个“0”，给给监监督督位位留留出地方。出地方。用用g（x）去去除除xrm（x），得得到到商商Q（x）和余式）和余式r（x）。）。编出的码组为编出的码组为A（x）=xrm（x）+r（x）。）。第34页，此课件共35页哦（2）循环码的译码原则上纠错可按下述步骤进行：原则上纠错可按下述步骤进行：用用生生成成多多项项式式g（x）去去除除接接收收码码组组B（x）=A（x）+E（x），得得出出余余式式r（x）；）；按按余余式式r（x）用用查查表表的的方方法法或或通通过过某某种种运运算算得得到到错错误误图图样样E（x），就就可可以以确确定错码位置。定错码位置。从从B（x）中中减减去去E（x），便便得得到到已纠正错误的原发送码组已纠正错误的原发送码组A（x）。）。第35页，此课件共35页哦