《信息论与编码民大循环码优秀PPT.ppt》由会员分享，可在线阅读，更多相关《信息论与编码民大循环码优秀PPT.ppt（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息论与编码民大循信息论与编码民大循环码环码1第1页，本讲稿共18页 循环码的概念：循环码的概念：循环码的概念：循环码的概念：循环性是指任一码组字循环一位后仍然是该编码中的一个码字。循环性是指任一码组字循环一位后仍然是该编码中的一个码字。循环性是指任一码组字循环一位后仍然是该编码中的一个码字。循环性是指任一码组字循环一位后仍然是该编码中的一个码字。例：一种例：一种(7,3)(7,3)循环码的全部码字如下循环码的全部码字如下 表中第表中第2 2码字向右移一位即得到第码字向右移一位即得到第5 5码字；第码字；第5 5码字向右移码字向右移一位即得到第一位即得到第7 7码字。码字。码组编号信息位监督位
2、码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a010000000510010112001011161011100301011107110010140111001811100102第2页，本讲稿共18页一般情况一般情况 若若(a an n-1-1 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
3、a a2 2 a a1 1)仍然是该编码中的码字。仍然是该编码中的码字。多项式表示法多项式表示法一个长度为一个长度为n n的码字的码字(a an n-1-1 a an n-2-2 a a0 0)可以表示成可以表示成 上式中上式中x x 的值没有任何意义，仅用它的幂代表码元的位置。的值没有任何意义，仅用它的幂代表码元的位置。例：码字例：码字1 1 0 0 1 0 11 1 0 0 1 0 1可以表示为可以表示为 3第3页，本讲稿共18页循环码的运算循环码的运算 整数的按模运算整数的按模运算在整数运算中，有模在整数运算中，有模n n运算。例如，在模运算。例如，在模2 2运算中，有运算中，有1+1=
4、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运算下，有运算下，有m m p p (模模n n)所以，在模所以，在模n n运算下，一个整数运算下，一个整数m m等于它被等于它被n n除得的余数。除得的余数。4第4页，本讲稿共18页码多项式的按模运算码多项式的按模运算 若任意一个多项式若任意一个多项式F F(x x)被一个被一个n n次多项式次多项式N N(x x)除，得到商除，得到商式
5、式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)除，得到余项除，得到余项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运算中加法和减法一样。运算中加法和减法一样。5第5页，本讲稿共18页循环码的数学表示法循环码的数学表示法 在循环码中，设在循环码中，设T(T(x x
6、)是一个长度为是一个长度为n n的码字，若的码字，若则则T T (x x)也是该编码中的一个码字。也是该编码中的一个码字。证证 设一循环码为设一循环码为 则有则有 上式中的上式中的T T (x x)正是码组正是码组T T(x x)向左循环移位向左循环移位 i i 次的结果。次的结果。例：例：一循环码为一循环码为11001011100101，即，即 若给定若给定 i i=3=3，则有，则有 上式对应的码组为上式对应的码组为01011100101110，它正是，它正是T T(x x)向左移向左移3 3位的结果。位的结果。结论：一个长为结论：一个长为n n的循环码必定为按模的循环码必定为按模(x x
7、n n+1)+1)运算的一个余式。运算的一个余式。6第6页，本讲稿共18页循环码的生成循环码的生成 n n如果有了生成矩阵如果有了生成矩阵G G，就可以由，就可以由k k个信息位得出整个码字个信息位得出整个码字A A：例例:(7,4):(7,4)码码式中，式中，生成矩阵生成矩阵G G的每一行都是一个码组。的每一行都是一个码组。n n因此，若能找到因此，若能找到 k k 个已知的码字，就能构成矩阵个已知的码字，就能构成矩阵G G。如前所。如前所述，这述，这k k个已知码组必须是线性不相关的。个已知码组必须是线性不相关的。n n在循环码中，一个在循环码中，一个(n n,k k)码有码有2 2k k
8、个不同的码字。若用个不同的码字。若用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)都是码组，而且这都是码组，而且这k k个码组是线性无关的。因个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵此它们可以用来构成此循环码的生成矩阵G G。7第7页，本讲稿共18页l l在循环码中除全在循环码中除全在循环码中除全在循环码中除全“0”“0”码组外，再没有连续码组外，再没有连续码组外，再没有连续码组外，再没有连续k k位均为位均为位均
9、为位均为“0”“0”的码组。的码组。的码组。的码组。否则，在经过若干次循环移位后将得到否则，在经过若干次循环移位后将得到否则，在经过若干次循环移位后将得到否则，在经过若干次循环移位后将得到k k位信息位全为位信息位全为位信息位全为位信息位全为“0”“0”，但监督，但监督，但监督，但监督位不全为位不全为位不全为位不全为“0”“0”的一个码组。这在线性码中显然是不可能的。的一个码组。这在线性码中显然是不可能的。的一个码组。这在线性码中显然是不可能的。的一个码组。这在线性码中显然是不可能的。l l因此，因此，因此，因此，g g(x x)必须是一个常数项不为必须是一个常数项不为必须是一个常数项不为必须
10、是一个常数项不为“0”“0”的的的的(n n-k k)次多项式，而且这次多项式，而且这次多项式，而且这次多项式，而且这个个个个g g(x x)还是这种还是这种还是这种还是这种(n n,k k)码中次数为码中次数为码中次数为码中次数为(n n k k)的唯一一个多项式。因为的唯一一个多项式。因为的唯一一个多项式。因为的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于且此
11、码组多项式的次数将小于且此码组多项式的次数将小于且此码组多项式的次数将小于(n n k k)，即连续，即连续，即连续，即连续“0”“0”的个数多于的个数多于的个数多于的个数多于(k k 1)1)。显然，这是与前面的结论矛盾的。显然，这是与前面的结论矛盾的。显然，这是与前面的结论矛盾的。显然，这是与前面的结论矛盾的。l l我们称这唯一的我们称这唯一的我们称这唯一的我们称这唯一的(n n k k)次多项式次多项式次多项式次多项式g g(x x)为码的生成多项式。一旦为码的生成多项式。一旦为码的生成多项式。一旦为码的生成多项式。一旦确定了确定了确定了确定了g g(x x)，则整个，则整个，则整个，则
12、整个(n n,k k)循环码就被确定了。循环码就被确定了。循环码就被确定了。循环码就被确定了。8第8页，本讲稿共18页n n因此，循环码的生成矩阵因此，循环码的生成矩阵G G可以写成可以写成n n例：例：上表中的编码为上表中的编码为(7,3)(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，与它对应的码多项式，与它对应的码多项式，即生成多项式，为即生成多项式
13、，为g g(x x)=)=x x4 4+x x2 2+x x+1+1。码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a010000000510010112001011161011100301011107110010140111001811100109第9页，本讲稿共18页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 形式，所以它不是标准生成矩阵。但形式，所以它不是标准生
14、成矩阵。但它经过线性变换后，不难化成标准阵。它经过线性变换后，不难化成标准阵。此循环码的码字多项式表示式此循环码的码字多项式表示式T T(x x)：上式表明，所有码字多项式上式表明，所有码字多项式T T(x x)都能够被都能够被g g(x x)整除，而整除，而且任意一个次数不大于且任意一个次数不大于(k k 1)1)的多项式乘的多项式乘g g(x x)都是码多项都是码多项式。式。10第10页，本讲稿共18页寻求码生成多项式寻求码生成多项式 因为任意一个循环码因为任意一个循环码T T(x x)都是都是g g(x x)的倍式，故它可以写成的倍式，故它可以写成T T(x x)=)=h h(x x)g
15、 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 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。因此，上式可以写成因此，上式可以写成11第11
16、页，本讲稿共18页将将 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 n+1)+1)的一个因子。的一个因子。例：例：(x x7 7+1)+1)可以分解为可以分解为为了求出为了求出(7,3)(7,3)循环码的生成多项式循环码的生成多项式 g g(x x)，需要从上，需要从上式中找到一个式中找到一个(n kn k)=4)=4次的因子。这样的因子有两个，次的因子。这样的因子有两个，即即以上两式都可以作为生成多项式。以上两式都可以作为生成
17、多项式。选用的生成多项式不同，产生出的循环码码字也不同。选用的生成多项式不同，产生出的循环码码字也不同。12第12页，本讲稿共18页循环码的编码方法循环码的编码方法用用x xn-kn-k乘乘m m(x x)。这一运算实际上是在信息码后附加上。这一运算实际上是在信息码后附加上(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，它表示，它
18、表示码组码组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 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=110010
19、1 13第13页，本讲稿共18页 循环码的解码方法循环码的解码方法循环码的解码方法循环码的解码方法在检错时：当接收码字没有错码时，接收码组在检错时：当接收码字没有错码时，接收码组R R(x x)必定能被必定能被g g(x x)整除，即下式整除，即下式中余项中余项r r(x x)应为零；否则，有误码。应为零；否则，有误码。n n当接收码组中的错码数量过多，超出了编码的检错能力当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被时，有错码的接收码组也可能被g g(x x)整除。这时，错码就整除。这时，错码就不能检出了。不能检出了。在纠错时：在纠错时：n n用生成多项式用生成
20、多项式g g(x x)除接收码组除接收码组R R(x x)，得出余式，得出余式r r(x x)。n n按照余式按照余式r r(x x)，用查表的方法或计算方法得出错误图样，用查表的方法或计算方法得出错误图样E E(x x)。n n从从R(R(x x)中减去中减去E E(x x)，便得到已经纠正错码的原发送码组，便得到已经纠正错码的原发送码组T T(x x)。14第14页，本讲稿共18页BCHBCH码码BCHBCH码是能够纠正多个随机错码的循环码。码是能够纠正多个随机错码的循环码。BCH BCH码分为两类：本原码分为两类：本原BCHBCH码和非本原码和非本原BCHBCH码。码。n n本原本原BC
21、HBCH码：码长码：码长n n=2=2m m 1(1(m m 3 3，任意正整数，任意正整数)，它的，它的生成多项式生成多项式g g(x x)中含有最高次数为中含有最高次数为m m次的本原多项式；次的本原多项式；n n非本原非本原BCHBCH码：码长码：码长n n是是(2(2m m 1)1)的一个因子，它的生成多的一个因子，它的生成多项式项式g g(x x)中不含有最高次数为中不含有最高次数为m m的本原多项式。的本原多项式。BCHBCH码的工程设计：可以用查表法找到所需的生成多项式。码的工程设计：可以用查表法找到所需的生成多项式。例：二进制非本原例：二进制非本原BCHBCH码的生成多项式系数
22、码的生成多项式系数 表中表中g g(x x)是用是用8 8进制数字表示的；进制数字表示的；t t 为纠错能力。为纠错能力。nktg(x)nktg(x)1721233341912122221223247271663534351456647133476565732453404652444307335710761354300067171777353715第15页，本讲稿共18页常用常用BCHBCH码：码：n n戈莱戈莱(Golay)(Golay)码：码：(23,12)(23,12)非本原非本原BCHBCH码，它能纠正码，它能纠正3 3个随个随机错码，并且容易解码机错码，并且容易解码 。n n扩展扩展
23、BCHBCH码码(n n+1,+1,k k)：ppBCHBCH码的长度为奇数。在应用中，为了得到偶数长度码的长度为奇数。在应用中，为了得到偶数长度的码，并增大检错能力，可以在的码，并增大检错能力，可以在BCHBCH码生成多项式中乘码生成多项式中乘上一个因式上一个因式(x x+1)+1)，从而得到扩展，从而得到扩展BCHBCH码码(n n+1,+1,k k)。pp扩展扩展BCHBCH码已经不再具有循环性。码已经不再具有循环性。n n扩展戈莱码扩展戈莱码(24,12)(24,12)：其最小码距为：其最小码距为8 8，码率为，码率为1/21/2，能够纠，能够纠正正3 3个错码和检测个错码和检测4 4
24、个错码。个错码。16第16页，本讲稿共18页几种二进制分组码的性能比较几种二进制分组码的性能比较 2PSK汉明码(7,4)t=1 汉 明 码(31,26)t=1 扩展戈莱码(24,12)t=3BCH码(127,64)t=10Eb/n0 (dB)Pe17第17页，本讲稿共18页RSRS码码RSRS码：是码：是q q进制进制BCHBCH码的一个特殊子类，并且具有很强的纠错码的一个特殊子类，并且具有很强的纠错能力。能力。RSRS码的参数：码长码的参数：码长n n=q q 1=m(2 1=m(2mm-1)-1)，(其中其中q q进制码元对应进制码元对应mm位二进制码元位二进制码元)，监督元数目，监督元
25、数目r r=2=2tmtm，(其中其中t t是能够纠正的是能够纠正的错码数目错码数目)；其生成多项式为；其生成多项式为g g(x x)=()=(x x+)()(x x+2 2)()(x x+2 2t t)式中，式中，为伽罗华域为伽罗华域GF(2GF(2m m)中的本原元。中的本原元。RSRS码的主要优点：码的主要优点：n n它是多进制纠错编码，所以特别适合用于多进制调制的场它是多进制纠错编码，所以特别适合用于多进制调制的场合；合；n n它能够纠正它能够纠正t t个个q q位二进制错码，即能够纠正不超过位二进制错码，即能够纠正不超过q q个连续个连续的二进制错码，所以适合在衰落信道中纠正突发性错码。的二进制错码，所以适合在衰落信道中纠正突发性错码。18第18页，本讲稿共18页