第五章 信道编码

1、第五章 信道编码,信道编码的基本概念和基本原理 线性分组码 循环码、卷积码和秩距离码 突发错误的纠正 级连码、交织码及TCM码 纠错码的应用,编码信道：包括信道编码器、实际信道、信道译码器。 该模型是研究信道纠错编码和译码的模型，集中研究通信可靠性。 通信可靠性问题：消息通过信道传输的时候，如何选择编码方案来减少差错。首先与信道统计特性有关，其次与编码方法、译码方法也有关系。,第一节 信道编码的基本概念和基本原理,信道是信号从信源传送到信宿的通路。 由于信道有干扰，使得传送的数据流(码流)中产生误码。 误码的处理技术有纠错、交织、线性内插等。 信道编码的目的是提高信息传输或通信的可靠性。 信道

2、编码的任务是降低误码率，使系统具有一定的纠错能力和抗干扰能力，提高数据传输效率。 信道编码的过程是在源数据码流中加插一些码元，达到在接收端进行检错和纠错的目的。 在带宽固定的信道中，总的传送码率是固定的，由于信道编码增加了数据量，其结果只能是以降低传送有用信息码率为代价了。,一、信道编码概念,目的：降低错误译码概率PE。 对象：信息序列（设码元间彼此无关且等概出现）。,方法：在传输的信息码之中按一定规律产生一些附加数字，经信道传输，在传输中若码字出现错误，收端能利用编码规律发现码的内在相关性受到破坏，从而按一定的译码规则自动纠正或发现错误，降低误码率。,一、信道编码概念,实质：在保持一定传输信

3、息速率条件下，通过增加一定的码元多余度，使输出的码字具有特定的相关性，从而使收端易于发现或纠正由于信道噪声而引起的传输错误。,q=rk个 k维矢量,信息序列,许用码组,编码过程,M,C,校验元,信息序列,码字,编码规则,rk个,传输模式,PE信道传输特征 PE译码方法,C2k Ci C2n-1,许用码组,禁用码组,不可检出错误传输,正确传输,可检出错误传输,二、信道编码的基本原理（检错、纠错原理）,寻找一种编码方法，使所加的监督码元最少，而检错纠错能力又高，且便于实现。,理论基础：香农第二定理 对于一个给定的有扰信道，如信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，

4、使编码错误概率p随码长n的增加，按指数下降到任意小的值。也就是说，可以通过编码使通信过程实际上不发生错误，或使错误控制在允许数值之下。即：,信息传输率,E(R),随机编码指数,码长,Pexp-nE(R), E (R)意义：n给定，则最佳编码的P上界既定。, 适用于DMC，有记忆信道及连续信道;,香农第二定理说明：,PE0，可靠编码条件：,有噪信道编码逆定理 设离散无记忆信道X，p(y|x)，Y的信道容量为C，R是信息传输率，当RC时，则无论码长N多长，总找不到一种编码，使译码的平均错误概率任意小。,表述二、设某信道有r个输入符号，s个输出符号，信道容量为C。只要码长N足够长，总可以在输入的rN

5、个符号的集合中找到M（M2N(C-)，为任意小的正数）个码字，分别代表M个等可能性的消息，组成一个码以及相应的译码规则，使信道输出端的平均错误译码概率PE达到任意小。,1) 差错类型 1随机错误: 数据流中发生的错误彼此无关 , 表现为错 误之间的无相关性. 2突发错误: 数据流中一个错误的发生 , 带来一连串错 误的发生 , 表现为误错之间的相关性. 2) 差错控制的途径 1增加信道容量措施 扩展带宽、提高发送功率、降低噪声 2编码措施 减小码率、增加码长、交织器、纠错码 3传输方式措施 重复发送、反馈重发、多进制信号,三、差错控制,需要双向信道，和前向信道有相同的通信容。 引入较大的停顿（

6、不实时）。 可以纠正任何错误。,1反馈检验法(IRQ),3) 差错控制的分类,2检错重发法（ARQ）,自动请求重发 也需要反向信道，但容量可以降低，也会引入停顿,3前向纠错（FEC）,不需要双向信道 不会引入停顿 靠纠错编码,3混合纠错检错（HEC）,4) 差错控制编码的基本原理,如用三位二进制编码来代表八个字母 000 A100E 001 B101F 010C110G 011D111H 不管哪一位发生错误，都会使传输字母错误 如用三位字母传四个字母 000 A011B101 C110D 发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。,如用三位字母传二个字母 000

7、A111B 检三个错误，纠正一个错误。大数法则纠错。 结论 具有检错或纠错的码组，其所用的比特数必须大于信息码组原来的比特数 引入余度。,5）、检错、纠错能力,码重(weight) 一个码组中“1”的数目 码距(distance) 两个码组之间对应位置上1、0不同的位数，又叫汉明(Hamming)距。 10 1 1 0 码重：3 01 1 0 0 2 距离：3,为检查出 个错误，要求最小码距为 为纠正 个错误，要求最小码距为 为纠正 个错误，同时检查出 个错误，要求最小码距为 纠正 个错误和p个删除，要求最小码距为：,检错、纠错能力,按功能分 检错码 纠错码 纠删码（发现不可纠正的错误时，可发

8、出指示或删除） 按信息码元和监督码元之间的校验关系分 线性码 非线性码 按信息码元和监督码元之间的约束方式分 分组码 卷积码,6）、差错控制编码分类,卷积码,非线性码,线性码,纠错码,分组码,循环码,非循环码,纠随机错误码,纠突发错误码,纠随机和突发错误码,纠同步错误码,纠错码分类,第二节 线性分组码,表示： (n,k) n : 帧（组）长 k/n : 编码效率 特点 监督码只用来监督本帧中的信息位 分类 线性码 信息码与监督码之间为线性关系 非线性码 不存在线性关系,一、基本概念,分组码的监督方程 矩阵形式,监督矩阵 H矩阵称为典型形式，各行一定是线性无关的。而一个非典型形式的经过初等变换运

9、算可以化成典型形式，通过监督矩阵可以知道监督码和信息码的监督关系。,生成矩阵 ，通过监督矩阵可以得到生成码组。 如果输入码组为 A=0011,编码器输出码字为:C=AG,由这种方式得到的生成矩阵称为典型生成矩阵，由它产生的分组码必定为系统码，也就是信息码字保持不变，监督位附加其后，每行一定是线性无关的，每行都是一个生成码组。,定理：设二元线性分组码CI是由监督矩阵H所定义的，若X和Y为其中的任意两个码字，则X+Y也是CI中的一个码字。线性码的封闭性,对偶码：以G作监督矩阵，以H为生成矩阵，得到另一个码CJ（n，n-k）线性码。CJ为原码CI的对偶码。它们的码矢彼此正交，两个子空间是互为零化空间

10、。,缩短码：将分组码最左边i位为0的消息和对应的码字挑选出来，把最左边的0删去，构成（n-i，k-i）线性分组码。纠错检错能力与原码相同。,缩短码的监督矩阵：（n，k）一致监督矩阵删去最左边一列。 缩短码的生成矩阵：（n，k）生成矩阵删去最左边一列和最上面的一行。,二、汉明码能纠正单个错误的线性分组码,汉明码的监督矩阵H的列为所有非零的r维向量组成，一旦r给定，就可以构造出具体的（n，k）汉明码。,例：构造一个二元的（7，4，3）汉明码。,分析：r=n-k=3,除0以外的所有2r个元素构成矩阵H的列。,截短汉明码,(n,k) (n-x, k-x) 如 (15,11) (12,8) 监督矩阵 H

11、 是将原 H 的前 3 列 去掉 截短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。,能纠 t 个错误的(n,k)应满足 取等号时为完备码 不同结构的线性码其纠错能力不同，能力和dmin 有关，dmin 越大越好。,如果在汉明码基础上，再加上一位对所有码字进行校验的监督位 监督码字由 r 位增加到 r+1 位 信息位不变 码长 码结构 纠 1 位错，检测 2 位错 如 （8，4），（16，11）,扩展汉明码,扩展汉明码的监督矩阵,编码器的实现 上例 m=(m1 m2 m3 m4) m1 , m2 , m3 , m4 0 ,1 Ci = mG Ci = (c1 c2 c3 c4 c5

12、 c6 c7) = (m1 m2 m3 m4 m1+m2 + m3 m2+m3+m4 m1+m2+m4) m1 c1 m2 c2 m3 c3 m4 c4 c5 c6 c7,+,+,+,三、线性分组码的编码,根据线性码的监督矩阵或生成矩阵将长为k的信息组变换成长为n（nk）的码字。,四、线性分组码的译码,当给定接收码字R时，译码器的错误译码概率表示经过译码后平均接受到一个码字所产生的错误大小。 平均错误概率：,1、 最大似然译码 1) 编码译码过程 源数据码流划分为信息组 m ,编码译码过程如下: 信息组 m 码字Ci 接收字R Ci的估值 干扰 2) 译码 发送码字Ci , 接收字R ; 译码

13、器根据编码规则和信道特性, 对接收码字 R 作出判决 , 此过程称为译码 . 译码器的基本任务就是根据一套译码规则或算法 , 由接 收字R 给出与发送信息组 m 的最好估计值 . 由于m 与C 之 间是一一对应的 , 这就等价于译码器根据R 对C 的估计.,编码器,译码器,信道,3) 最佳译码 在已知接收字R 的条件下 , 找出可能性最大的发送码字Ci 作为译码的估值 , 令 这种译码方法叫做最佳译码或最大后验译码(MAP) 根据Bayes公式 式中 p( Ci ) 发送码字Ci 的概率 p(R) 接收字R的概率 p(R|Ci ) 先验概率,如果以下条件成立 码C中的 q k 个码字以等概率发

14、送 , p( Ci ) = 1/ q k p(R) 对于任何R 都有相同的值 , p(R) = 1/ q n 则后验概率p(Ci| R) 最大 , 等同于先验概率p(R|Ci )最大. 4) 最大似然译码 在已知接收字R 的条件下 , 使得先验概率最大的译码方 法称为最大似然译码 对于无记忆信道 , 若 Ci = ( ci 1 , ci 2 , , ci n ) , R = ( r 1 , r 2 , , r n ) 则最大似然函数,对数似然函数 5) 最小距离译码 对于BSC信道 , 最大似然译码可以简化为最小距离译码. 码 C 中任一码字Ci 与R的距离为d , 则 d 表示Ci 在BSC

15、信道传输过程中码元传错的个数 . 因此此时的似然函数,结论 (1-p)n 是常数 , 而 p/(1-p) 1 , d 越大则 p(R | Ci ) 越小 反之 , d 越小则 p(R | Ci ) 越大. 因此求最大似然函数的问题就转化为求Hamming最小 距离的问题 .,5.4 线性分组码 5.4.1 线性分组码的基本概念 1) 模运算(对于整数) 1同余 a = b (mod m) : a 除以 m 与 b 除以 m(m1) 的余数相同; 或称为 a 和 b 对于模 m 同余 . 最小非负剩余 : a = r (mod m) ; 0 r m ; r 为模 m最小非负剩余 模m运算 : a

16、 , b 0 , 1 , 2 , , m-1 ; r为最小非负剩余 将 a + b=r (mod m) , a b =r (mod m) 记为 这种求a + b 和 a b 的模 m 最小非负剩余称为模m的加法运算和模 m的乘法运算. 为了简单起见 , 以后将运算符号 简记为+和 .,2模 2 运算 (二进制) 3模 q 运算(q进制) 例 : 模 3 运算 1+1+1=1 , 1+1+1+1=0 , 0-1=1 , 1-0=1 , 1-1=0 2) 线性分组码 定义1 设 Ci = ( ci 1 , ci 2 , , ci n ) , Cj= ( cj 1 , cj 2 , , cj n )

17、是 二元码 C 的两个码字 , 则 Ci 与 Cj 的和 为 Ci 与 Cj 对应码元的模 2 运算 ; 若 Cs = ( cs 1 , cs 2 , , cs n ) 且 Cs =Ci + Cj 即 cs r = ci r + cj r (r =1, 2, , n ),定义2 设( n , k )分组码 C 中的任意两个码字 1C 中有全 0 码元的码字; 2C 中的任意两个码字的和仍为码 C 的码字; 则分组码 C 称为( n , k )线性分组码 . 推论 线性分组码任意两个以上码字的和仍为码 C 的码字. 根据分组码的定义 , 信息组 m 的 k 个码元(信息位)应包 含在线性分组码的

18、码字中. 定义3 若信息组 m的 k 个码元以整体不变的形式 , 放在码字 的任意位置中 , 该码为系统码 . 否则 , 称为非系统码. 系统码通常如下图将信息组放在码字的最左边或最右边.,例 试构造 (5 , 2) 线性分组码 , 且d min = 3 信息组 m 00 01 10 11 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 1100

19、1 11010 11011 11100 11101 11110 11111 1组 2组 3组 4组 5组 6组 7组 8组 9组 00000 00000 00000 00000 00000 00000 00000 00000 00000 01011 01011 01011 01101 01101 01101 01110 01110 01110 10101 10110 10111 10011 10110 10111 10011 10101 10111 11110 11101 11100 11110 11011 11010 11101 11001 11001,3) 码字的重量 定义4 ( n ,

20、k )码 C 的一个码字C i中非零码元的个数称为码 字C i 的Hamming重量 , 简称码重 , 记为W(C i) . 定义5 ( n , k )码 C中所有非零码字的Hamming重量的最小 值称为码 C 的最小Hamming重量 , 或码C最小重量 记为Wmin . 推论 设Ci , Cj 为二元分组码C的任意两个码字 , 则 W(Ci + Cj ) = d (Ci , Cj ). 证明 Ci , Cj 的对应码元相同时 , 则 Ci + Cj 对应的码元为0 ; Ci , Cj 的对应码元不同时 , 则 Ci + Cj 对应的码元为1 ; 则 W(Ci + Cj ) 为Ci , C

21、j 的对应码元不同的个数 ,而 d (Ci , Cj )为Ci , Cj 的对应码元不同的个数 , 故推论成立.,定理 二元( n , k )线性分组码C的最小距离等于其最小重量. 证明 设C 中的任意两个码字 Ci , Cj , 且Ci Cj 则 Cs= Ci + Cj 是非零码字 , 同时是码 C 的码字 又因为W(Ci + Cj ) = W (Cs ) =d (Ci , Cj ) , 因此 Wmin =d min 结论: 二元线性分组码 C 的最小重量 , 即非零码字“1”的个数 最少的码字决定了码 C 的检错或纠错能力. 如何获得二元线性分组码,5.4.2 近世代数学初步 1) 群的概

22、念 定义1 G是一个非空集合，*是G中的一个代数运算，若 1 a , bG , 有 a * b G (封闭性) 2 a , b , cG , 有(a * b) * c = a * ( b * c ) (结合律) 3存在单位元素 eG , aG , 有e * a = a * e = a 4 aG , 存在逆元素 a -1G , 有a-1 * a = a-1 * a = e 5 a , bG , 有 a * b = b * a (交换律 ) 如果这种运算 * 满足： 条件1, 2, 3, 4 则 G 称对代数运算为一个群,或称 G为一个非交换群. 条件 1, 2, 3, 4 , 5则称G为一个交换

23、群或Abel群.,若运算 * 是普通的加法“+”,则群称为加群 . 若运算 * 是普通的乘法“”,则群称为乘群 . 定义2 若群G 仅有有限个原素则称为有限群 ;否则为无限群. 1无限群的例子 例1 整数集对加法构成Abel群 ,对乘法不是群. 例2 有理数、实数、复数集对加法构成Abel群 , 不含数 0 的有理数、实数、复数集对乘法构成Abel群. 例3 n 维方阵的集合加法构成Abel群 ,对乘法不是群. 例4 n 维非奇异方阵对乘法构成非Abel群 . 2有限群的例子 例1 数 0 对加法构成群 , 数 1 对乘法构成群.,例2 集合 0 , 1 , 2 , , m-1对模m加法运算构

24、成Abel群 , 对乘法不是群. 例3 当 m 为素数时 , 集合 1 , 2 , , m-1对模 m 乘法运 算构成Abel群 . 例4 方程 x n - 1= 0的本原根 e j 2k/n , k=0 , 1 ,n-1对乘法 构成Abel群. 例5 线性分组码构成Abel群 , 所以线性分组码又称为群码.,2) 域的概念 定义1 F 是一个非空集合 , 对于F 的任意两个元素a 和 b , 定义集合元素的加法运算 , 记作ab ; 乘法运算 , 记作a b ; 且有如下规则 : 加法运算 1 a , b F , 有 ab F ; 2 a , b F , 有 ab = ba ; 3 a，b，

25、c F , 有 (ab)c = a( bc) ; 4存在0 F , a F , 有 a0 = a ； 5 a F , 存在 - a F , 有 a(- a) = 0 ;,乘法运算 1 a , b F , 有 a b F ; 2 a , b F , 有 a b = b a ; 3 a，b，c F , 有 (a b) c = a ( b c) ; 4存在e F , a F , 有 a e = a ； 5 a F ,且a0 , 存在 a -1 F , 有 a a -1= e ; 乘法对加法的分配律 a , b , c F , 有 a (bc) = a ba c 以上运算规则都成立，则称 F 对于所规

26、定的加法运算 和乘法运算是一个域 . 定义2 设F 是一个域 , 如果F 中的元素个数无限 , 则F 称为 无限域 . 如果 F 中的元素个数有限 , 则 F 称为有限 域，有限域亦称为Galois域.,1无限域的例子 例1 有理数、实数、复数集对加法 , 乘法构成域 . 例2 形如 的数对加法 ,乘法构成域 . 2有限域的例子 例1 集合 0 , 1 , 2 , , m-1对模m加法,乘法运算构成域.,5.4.3 生成矩阵和校验矩阵 1) 生成矩阵 例1 试构造 (5 , 2) 线性分组码 , 且d min = 3 m=(m1 m2 ) = (00) , (01) , (10) , (11)

27、 Ci=( m1 m2 m1 m2 m1+m2 ) (00) (0 0 0 0 0) (01) (0 1 0 1 1) (10) (1 0 1 0 1) (11) (1 1 1 1 0) 1(n , k) 线性分组码的生成矩阵G 是一个k n 维矩阵 . 为了获得系统线性分组码 , 生成矩阵由两个分块矩阵组成: G = I k P k(n-k) I k : k 维单位矩阵 , 以获得信息位; P k(n-k): k(n-k)矩阵, 以获得校验位.,2线性分组码生成矩阵的特点 生成矩阵不是唯一的; 生成矩阵的行矢量均为线性分组码的码字; 生成矩阵的行矢量是模 2 运算下线性无关; 线性分组码任一码字是行矢量模 2 运算下的线性组合. 3如何获得生成矩阵? 例2 试构造 (7 , 4) 线性分组码 , 且d min = 3 生成矩阵生成的线性分组码要有尽可能大的d min , 即生 成矩阵的行矢量中的“1”的个数 d min , 且生成矩阵各行矢 量(码字)的对应元素不相同的个数 d min .,2) 一致校验矩阵 (n , k) 线性分组码为一系统码 , 则码字有 (c1 c2 ck ck+1 cn) = (m1 m2 mk ck+1 cn) 由生成矩阵