1、通信原理课件通信原理课件第七章第七章 信道编码信道编码7.1 引言引言7.2 信道信道编码的基本原理的基本原理7.3 线性分性分组码7.4 卷卷积码 7.5 其他几种常用的差其他几种常用的差错控制控制编码方法方法通信原理课件通信原理课件7.1 引言引言差差错控制的基本概念控制的基本概念数字信号在数字信号在传输过程中，由于信道不理程中，由于信道不理想、加性噪声以及想、加性噪声以及码间串串扰等都会等都会产生生误码。为了提高系了提高系统的抗干的抗干扰性能，可以采性能，可以采用差用差错控制技控制技术。通信原理课件通信原理课件差错即是误码。差错即是误码。差错控制的核心是抗干扰编码，差错控制的核心是抗干扰
2、编码，简称简称差错编码差错编码。差错控制的目的是提高信号传输的差错控制的目的是提高信号传输的可可靠性。靠性。通信原理课件通信原理课件图图7-1 信道编码的数字通信模型信道编码的数字通信模型通信原理课件通信原理课件差错控制的实质差错控制的实质给信息信息码元增加冗余度，即增加一定数元增加冗余度，即增加一定数量的多余量的多余码元（称元（称为监督督码元或校元或校验码元）元），由，由信息信息码元元和和监督督码元元共同共同组成一个成一个码字字，两者，两者间满足一定的足一定的约束关系。如果在束关系。如果在传输过程中受到干程中受到干扰，某位，某位码元元发生了生了变化，就破坏了它化，就破坏了它们之之间的的约束关
3、系。束关系。通信原理课件通信原理课件纠错码的分类纠错码的分类（1 1）根据）根据纠错码各各码组信息信息码元和元和监督督码元之元之间的函数关系，可分的函数关系，可分为线性性码和和非非线性性码。（2 2）根据信息）根据信息码元和元和监督督码元之元之间的的约束方式束方式不同，可分不同，可分为分分组码和和卷卷积码。（3 3）根据）根据码的用途，可分的用途，可分为检错码和和纠错码。通信原理课件通信原理课件7.2 7.2 信道编码的基本原理信道编码的基本原理所所谓差差错控制控制编码实际上就是在保持信上就是在保持信息的位数不息的位数不变的情况下，采用增加的情况下，采用增加码长的的方法来降低方法来降低误码率。
4、率。具体来具体来说：码的的检错和和纠错能力是用信能力是用信息量的冗余度来息量的冗余度来换取的。取的。通信原理课件通信原理课件 由此可由此可见，纠错编码之所以具有之所以具有检错和和纠错能力，能力，是因是因为在信息在信息码之外附加了之外附加了监督督码，监督督码不不载荷信荷信息，它的作用是用来息，它的作用是用来监督信息督信息码在在传输中有无差中有无差错，对接收端的用接收端的用户来来说是多余的，最是多余的，最终也不也不传送送给用用户，但它提高了但它提高了传输的可靠性。的可靠性。但是，但是，监督督码的引入，的引入，降低了信道的降低了信道的传输效率。效率。一般来一般来说，引入，引入监督督码越多，越多，码的
5、的检错、纠错能能力越力越强，但信道的，但信道的传输效率下降也越多。效率下降也越多。研究的目研究的目标：寻找一种找一种编码方法使所加的方法使所加的监督督码元元最少而最少而检错、纠错能力又高，且便于能力又高，且便于实现。通信原理课件通信原理课件码重、码距以及检错纠错能力码重、码距以及检错纠错能力码重：重：对于二于二进制制码组，码组中非中非0 0码元的数目，元的数目，用用W W表示。表示。码距：距：两个等两个等长码组之之间相相应位取位取值不同的数目。不同的数目。最小最小码距：距：码组集合中各集合中各码组之之间距离的距离的最小最小值用用 表示。表示。码组间最小距离越大，最小距离越大，说明明码字字间最小
6、差最小差别越大，抗干越大，抗干扰能力越能力越强，因此是极重要，因此是极重要的参数，它是衡量的参数，它是衡量码检错、纠错能力的依据。能力的依据。通信原理课件通信原理课件若若检错能力用检错能力用e e、纠错能力用纠错能力用t t表示，可以表示，可以证明，检、纠能力与最小码距有如下关系：证明，检、纠能力与最小码距有如下关系：（1 1）为了能检测）为了能检测e e个错码，要求最小码距个错码，要求最小码距 （2 2）为了能纠正）为了能纠正t t个错码，要求最小码距个错码，要求最小码距 （3 3）为了能纠正）为了能纠正t t个错码，同时检测个错码，同时检测e e个错个错码，要求最小码距码，要求最小码距 通
7、信原理课件通信原理课件编码效率编码效率设编码后的码组长度、码组中所含信息设编码后的码组长度、码组中所含信息码元以及监督码元的个数分别为码元以及监督码元的个数分别为n n，k k和和r r，三者间满足三者间满足 编码效率编码效率R R为为 通信原理课件通信原理课件7.2.2 信道编码的译码方法信道编码的译码方法图图7-1所示的信道编码的数字通信模型中，信道译所示的信道编码的数字通信模型中，信道译码器根据一套译码规则，从接收到的码字给出与发码器根据一套译码规则，从接收到的码字给出与发送的信息序列最接近的估值序列。由于发送端与码送的信息序列最接近的估值序列。由于发送端与码字之间存在一一对应关系，这等
8、价于译码器根据字之间存在一一对应关系，这等价于译码器根据R产生一个产生一个C的估值序列的估值序列 。显然，当且仅当。显然，当且仅当C=时，这时译码器正确译码。时，这时译码器正确译码。通信原理课件通信原理课件一、最大后验概率（一、最大后验概率（MAP）译码）译码通信原理课件通信原理课件二、最大似然（二、最大似然（ML）译码）译码通信原理课件通信原理课件三、最小汉明距离译码三、最小汉明距离译码通信原理课件通信原理课件7.3 7.3 线性分组码线性分组码一个长为一个长为n n的分组码，码字由两部分构成：的分组码，码字由两部分构成：信息码元（信息码元（k k位）和监督码元（位）和监督码元（r r位），
9、位），n=k+rn=k+r，表示为（，表示为（n n，k k）码。（）码。（n n，k k）码可）码可以表示以表示 个状态，即可以有个状态，即可以有 个码字，但个码字，但其中只有其中只有 个是个是许用码字许用码字，其余为，其余为禁用码禁用码。通信原理课件通信原理课件要从要从k k个信息元中求出个信息元中求出r r个监督元，必个监督元，必须有须有r r个独立的线性方程。根据不同的个独立的线性方程。根据不同的线性方程，可得到不同的（线性方程，可得到不同的（n n，k k）线）线性分组码性分组码。通信原理课件通信原理课件线性分性分组码的主要性的主要性质如下：如下：（1）封封闭性：性：线性分性分组码中
10、任意两个中任意两个码字之和仍是分字之和仍是分组码中的一个中的一个码字；字；（2）线性分性分组码各各码字之字之间的最小距离的最小距离等于非零等于非零码的最小的最小码重。重。通信原理课件通信原理课件例如，已知一（例如，已知一（7 7，4 4）线性分组码，）线性分组码，4 4个信息元个信息元 和和3 3个监督元个监督元 之间的关系可以表示为之间的关系可以表示为 通信原理课件通信原理课件1 1、监督矩阵、监督矩阵H H改写式所示（改写式所示（7 7，4 4）线性分组码的）线性分组码的3 3个线个线性方程式性方程式通信原理课件通信原理课件写成矩阵形式写成矩阵形式并简记为并简记为或或 通信原理课件通信原理
11、课件式中式中 称为线性分组码的一致称为线性分组码的一致监督矩阵监督矩阵（或（或校验矩阵校验矩阵）它它决定了信息码元和监督码元之间的校验关系决定了信息码元和监督码元之间的校验关系通信原理课件通信原理课件通信原理课件通信原理课件2 2、生成矩阵、生成矩阵G G改写为矩阵形式改写为矩阵形式通信原理课件通信原理课件通信原理课件通信原理课件利用利用G G可以产生码组可以产生码组C C，即，即 通信原理课件通信原理课件7.3.2 线性分组码的译码线性分组码的译码设发送端进入信道的码字设发送端进入信道的码字 信道译码器接收到的信道译码器接收到的n n长的码字长的码字 通信原理课件通信原理课件由于信道中存在干
12、扰，由于信道中存在干扰，R R中的某些码元可中的某些码元可能与能与C C中对应码元的值不同，二进制序列中中对应码元的值不同，二进制序列中的错误即是的错误即是“1 1”错成错成“0 0”或者或者“0 0”错成错成“1 1”，因此，如果把信道中的干扰也用二，因此，如果把信道中的干扰也用二进制序列进制序列 表示，则有错的表示，则有错的 值为值为“1 1”，无错的，无错的 值为值为“0 0”，我们称，我们称E E为信道的为信道的错误图样错误图样。通信原理课件通信原理课件接收码字接收码字R R是发送的码字是发送的码字C C与错误图样与错误图样E E模模2 2相加的结果，可表示为相加的结果，可表示为 R
13、RC C E E例如：例如：发送码字发送码字 C=(10111000)C=(10111000)接收码字接收码字 R=(10010100)R=(10010100)错误图样错误图样 E=(00101100)E=(00101100)通信原理课件通信原理课件校验子（或伴随式）校验子（或伴随式）如果如果则接收码字无错码，否则有错。则接收码字无错码，否则有错。通信原理课件通信原理课件结论：结论：（1 1）校正子仅与错误图样有关，而与发）校正子仅与错误图样有关，而与发送的具体码字无关送的具体码字无关（2 2）若）若 ，则判断没有错码出现，则判断没有错码出现，它表明接收的码字是一个许用码字，当然如它表明接收的
14、码字是一个许用码字，当然如果错码超过了纠错检错的能力，也无法检测果错码超过了纠错检错的能力，也无法检测出错码；若出错码；若 ，则判有错码出现，则判有错码出现通信原理课件通信原理课件【例例7-3-1】设线性分性分组码的的监督矩督矩阵为（1）确定确定线性分性分组码的的n和和k；（2）写出生成矩写出生成矩阵；（3）写出写出该码的全部的全部码字；字；（4）说明明检测错误的能力和的能力和纠错能力；能力；（5）当接收端收到的当接收端收到的码字字为011100时，判断是，判断是否出否出错？通信原理课件通信原理课件（1）由由监督矩督矩阵得得，n=6，r=k=3（2）通信原理课件通信原理课件(3)000000，
15、001011，010110，100101，011101，101110，110011，111000(4)最小最小码距距为3，因此可以因此可以检测2位位错误，能能纠正正1位位错误。(5)判断该接收码字有错判断该接收码字有错通信原理课件通信原理课件7.3.3 7.3.3 汉明码汉明码汉明码是一种可以纠正单个随机错误的线性分汉明码是一种可以纠正单个随机错误的线性分组码。它有以下特点：组码。它有以下特点：码长码长 最小码距最小码距 信息码位信息码位 纠错能力纠错能力监督码位监督码位 通信原理课件通信原理课件这里这里m m为为 的正整数，给定的正整数，给定m m后，即可构后，即可构造出具体的汉明码（造出具
16、体的汉明码（n n，k k）。）。汉明码的监督矩阵有汉明码的监督矩阵有n n列，列，m m行，它的行，它的n n列列分别由除了全分别由除了全0 0之外的之外的m m位码组构成，每个位码组构成，每个码组只在某列中出现一次。码组只在某列中出现一次。通信原理课件通信原理课件 不同的错误图样具有不同的校正子，不同的错误图样具有不同的校正子，对于纠一位错码的汉明码的监督矩阵，校对于纠一位错码的汉明码的监督矩阵，校正子就是正子就是H H阵中与错误码元位置对应的各阵中与错误码元位置对应的各列列通信原理课件通信原理课件例例7-3-2 已知（已知（7，4）汉明明码的生成矩的生成矩阵为（1）写出典型形式的生成矩写
17、出典型形式的生成矩阵和和监督矩督矩阵；（2）写出全部的写出全部的码字；字；（3）判断判断该码检错的能力、的能力、纠错的能力；的能力；（4）写出校写出校验子与子与错码位置的位置的对应关系；关系；（5）如果接收如果接收码字字R为(1011000)、(0111011)、(1100000)，试计算校算校验子，并子，并进行行译码。通信原理课件通信原理课件(1)(2)全部的全部的许用用码字字为：0000000，0001011，0010110，0011101，0100111，0101100，0110001，01110101000101，1001110，1010011，1011000，1100010，1101
18、001，1110100，1111111通信原理课件通信原理课件(3)最小最小码距距为3，因此可以因此可以检测2位位错误，能，能纠正正1位位错误。(4)通信原理课件通信原理课件判断该接收码字无错判断该接收码字无错通信原理课件通信原理课件判断该接收码字判断该接收码字有有错错由（由（7，4）汉明明码的校的校验子与子与错码位置的位置的对应关系关系可知，校可知，校验子子为001代代码错码位置位置为 C0，故将收到的，故将收到的码字字0111011，纠正正为0111010的的译码输出。出。通信原理课件通信原理课件判断该接收码字判断该接收码字有有错错由（由（7，4）汉明明码的校的校验子与子与错码位置的位置的
19、对应关系关系可知，校可知，校验子子为001代代码错码位置位置为C1，故将收到的，故将收到的码字字1100000，纠正正为1100010的的译码输出。出。通信原理课件通信原理课件7.3.4 7.3.4 循环码循环码在在线性分性分组码中，有一种重要的中，有一种重要的码称称为循循环码。它除了具有它除了具有线性分性分组码的一般特点外，的一般特点外，还具有循具有循环性：循性：循环码中任一中任一码字的字的码元循元循环移位（左移移位（左移或右移）后仍是或右移）后仍是该码的一个的一个码字。字。例如例如,（7 7，3 3）循）循环码的一个的一个码组集集为00000000000000，00101110010111
20、，01011100101110，10111001011100，01110010111001，11100101110010，11001011100101，10010111001011通信原理课件通信原理课件1 1、循、循环码的的码多多项式式循循环码可用多种方式可用多种方式进行描述。在代数行描述。在代数编码理理论中，通常用多中，通常用多项式去描述循式去描述循环码，它把它把码字中各字中各码元当作是一个多元当作是一个多项式的系式的系数，即把一个数，即把一个n n长的的码字字用一个次数不超用一个次数不超过（n-1）的）的码多多项式表示式表示通信原理课件通信原理课件2 2、循环码的生成多项式与生成矩阵、循
21、环码的生成多项式与生成矩阵(n,k)(n,k)循循环码组集合中（全集合中（全“0”0”码除外）除外）幂次最低的多次最低的多项式称式称为生成多生成多项式式 。它是能整除它是能整除 且常数且常数项为1 1的的 阶多多项式，具有唯一性。式，具有唯一性。的的码重就是重就是码组的最小的最小码距。距。通信原理课件通信原理课件根据各码组集合中生成多项式的唯一性，根据各码组集合中生成多项式的唯一性，可以构成生成矩阵可以构成生成矩阵 循环码的生成矩阵多项式可以写成循环码的生成矩阵多项式可以写成通信原理课件通信原理课件例：（例：（7 7，3 3）循）循环码的生成多的生成多项式式为 ，它是，它是码组00101110
22、010111的的码多多项式。（式。（7 7，3 3）循循环码的生成矩的生成矩阵为通信原理课件通信原理课件通信原理课件通信原理课件3 3、循环码的编码方法、循环码的编码方法（n n，k k）循环码的多项式可表示为）循环码的多项式可表示为 为为k k位信息码多项式，位信息码多项式，是是 除以生成多项式的余式，代表监督码元，除以生成多项式的余式，代表监督码元，将其附加在信息码元之后即得循环码。将其附加在信息码元之后即得循环码。通信原理课件通信原理课件 例例7-3-37-3-3已知（已知（7 7，3 3）循环码的生成多项式）循环码的生成多项式 ，求信息位为（，求信息位为（110110）时的循环码。）时
23、的循环码。解：解：信息码多项式信息码多项式 通信原理课件通信原理课件则码多项式为则码多项式为 即信息码（即信息码（110110）对应的（）对应的（7 7，3 3）循环码）循环码为（为（11010011101001）通信原理课件通信原理课件4 4、循环码的译码方法、循环码的译码方法接收到的接收到的码组是否能被生成多是否能被生成多项式整除作式整除作为判判断断传输当中是否当中是否发生生错误的依据的依据当当传输中未中未发生生错误时，接收的，接收的码组与与发送的送的码组相同，相同，则接收的接收的码组必能被整除，余必能被整除，余项为0 0若若传输中中发生了生了错误，不能被整除，余，不能被整除，余项不不为0
24、 0通信原理课件通信原理课件循环码的译码可以分三步进行：循环码的译码可以分三步进行：（1 1）将接收码组多项式）将接收码组多项式 除以特征多除以特征多项式项式 ，得到伴随多项式，得到伴随多项式 ；（2 2）由）由 确定错误图样确定错误图样 ；（3 3）与与 进行模进行模2 2加，纠正错误。加，纠正错误。通信原理课件通信原理课件例例7-3-4（7,4）循循环码生成多生成多项式式为（1）求求错误图样与校与校验子之子之间的的对应关系。关系。（2）根据根据纠错检验表，如果接收的表，如果接收的码字字为0111100，试进行行纠正正。通信原理课件通信原理课件通信原理课件通信原理课件如果接收的如果接收的码字字为0111100，可得可得错误图样为0010000，即第，即第 a4位位错，则纠正接收正接收码字的字的错误后，得到的后，得到的码字字为0101100通信原理课件通信原理课件例例7.3.5 已知循已知循环码的生成多的生成多项式式为（1）当当输入的信息入的信息码是是1000时，求，求码组；（2）若接收若接收码组 试问该码组在在传输中是否中是否发生生错误？通信原理课件通信原理课件通信原理课件通信原理课件7.4 卷积码卷积码图7-3 卷积码编码器结构 卷积码不同于前面讲的线性分组码和循环码，它是一类有记忆的非分组码。通信原理课件通信原理课件
