信息论与编码 第6章 信道编码课件

《信息论与编码 第6章 信道编码课件》由会员分享，可在线阅读，更多相关《信息论与编码 第6章 信道编码课件（168页珍藏版）》请在金锄头文库上搜索。

1、第1章：概述,第2章：信源熵,第3章：信道容量,第4章：信息率失真函数,第5章：信源编码,第6章：信道编码,第7章：密码体制的安全性测度,6.1 信道编码的概念 6.2 线形分组码 6.3 循环码 6.4 卷积码,6.1.1 信道编码的作用和分类 6.1.2：编码信道 6.1.3：检错和纠错原理 6.1.4：检错和纠错方式和能力,信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题： 如何正确接收载有信息的信号 线路编码 如何避免少量差错信号对信息内容的影响 纠错编码,广义信道编码=特定信道上传输信息而进行的传输信号或信号格式的设计与实现,描述编码 用于对特定数据信号的描述

2、约束编码 用于对特定信号特性的约束 扩频编码 用于扩展信号频谱为近似白噪声谱并满足某些相关特性 纠错编码 用于检测与纠正信号传输过程中因噪声干扰导致的差错,1,2,3,4, 6.1.1：信道编码的作用和分类 6.1.2 编码信道 6.1.3：检错和纠错原理 6.1.4：检错和纠错方式和能力,消息,编码信道模型,当码字C和接受向量R均由二元序列表时，称编码信道为二进制信道 C=(c0,c1,cn-1) 如果对于任意的n都有： 则称此二进制信道为无记忆二进制信道。 p(0/1)=p(1/0)=p0 则称此信道为无记忆二进制对称信道BSC,BSC输入输出关系等效为,差错图案：随机序列 或 ，,第i位

3、上的一个随机错误：,长的突发错误：第 至第 位之间有很多错误,对于一个BSC信道总有转移概率 1/2， 比特传输中发生差错数目越少，概率越大，即,从而总认为发生差错的图案是差错数目较少的图案,二元软判决信道,用多个比特（理想情况下为实数）表示每一个无记忆编码信道的二元符号输出,信道干扰z为零均值正态分布的随机变量，噪声干扰功率为均方差 ，z的概率分布为 。对于BPSK调制，二元输入符号 为二元符号取值为+1或-1, 6.1.1：信道编码的作用和分类 6.1.2：编码信道 6.1.3 检错和纠错原理 6.1.4：检错和纠错方式和能力,检纠错是根据信道输出序列 自身判断 是否可能是发送 的，或纠正

4、导致 不等于 的错误。 冗余编码：码字 的长度 一定大于消息 的长度,编码码率 ：每个码字的序列符号（或码元）平均传送的消息比特数,偶（或奇）校验方法：实现检纠错目的的一个基本方法。,一个偶校验位 是对消息 使得如下校验方程成立的二进制符号，即,一个偶校验码码字,一个码率为 的 偶校验码，所有可能的 的全体,校验方程为1表明一定有奇数个差错，校验方程为0表明可能有偶数个差错,m0+m1+m2+mk1+p=0 （mod 2） 称c=(m0,m1,m2mk-1,p)为一个偶校验字 确定校验位P的编码方程为： P=m0+m1+mk-1,编码可以产生多个奇偶校验位，即一个校验位可以由消息位的部分或全部

5、按某种校验方程产生，例如对阵列消息进行垂直与水平校验以及总校验的码字 和其码率分别为,重复消息位：实现检纠错目的第二个基本方法,一个 重复码是一个码率为 的码，仅有两个码字 和 ，传送1比特（ ）消息。,重复码可以检测出任意小于 个差错的错误图案，纠正任意小于 个差错的错误图案。,纠1位差错 的3重复码,等重码或定比码：实现检纠错的第三个方法。,设计码字重量 恒为常数，即,例如一种用于表示0至9数字的5中取3等重码如下表所示，其码率 R为,5中取3等重码,5中取3等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错, 6.1.1：信道编码的作用和分类 6.1.2：编码信道

6、 6.1.3：检错和纠错原理 6.1.4 检错和纠错方式和能力,纠错码的应用方式：前向纠错方式（FEC），自动请求重发（ARQ）方式，混合纠错（HEC）方式以及信息反馈（IRQ方式）,FEC与ARQ纠错应用方式,常用汉明距离来描述检纠差错的数目，对于两n长向量u、v，汉明距离为：,最小汉明距离 （最小码距d）：任意两码字之间的汉明距离的最小值,定理 对一个最小距离为 纠错码，如下三个结论仅有其中任意一个结论成立：,（1） 可以检测出任意小于等于 个差错；,（2） 可以纠正任意小于等于 个差错；,（3）可以检测出任意小于等于l同时纠正小于等于t个差错，其中l和t满足,最小码距与检纠错能力,差错概

7、率：通信作为一个统计过程时，纠检错能力的统计特性。,FEC方式纠错码的码字差错概率,：发送码字 的先验概率,：码字数，对于充分随机的消息源,对BSC信道,最大化 等价于 最小化，最小差错概率译码等价为使接收向量与输出码字距离最小的最小距离译码，即,信息比特信噪比 ：传输一个比特信息所需的最小信噪比,比特差错概率 （又称误码率）与信噪比 的关系如下图所示，采用纠错码后，达到同样比特差错概率实际需要的信噪比减小量称为编码增益。,编码增益,6.2 线性码,6.2.1 线性分组码的描述,6.2.2 线性分组码的译码,6.2.3 码例与码的重构,6.2.1 线性分组码的描述 6.2.2 线性分组码的译码

8、 6.2.3 码例与码的重构,一个（n,k）线形分组码C是称为码字c的n维 向量的集合 C=c| c=mG 其中m为任意的k维向量并称为消息向量。 G是k行n行列秩为k（nk）的矩阵并称为 生成矩阵，,对于二元编码， 和 是二元向量， 是一个二元矩阵， ，向量与矩阵，矩阵与矩阵之间的基本运算是模二加和模二乘运算。,表6.2.1 模二加/乘法表,例6.2.1 3重复码是一个（3，1）线性分组码,例6.2.2（4，3）偶校验码是一个（4，3）线性分组码,当生成矩阵 给定时线性分组码有如下性质： (1)零向量 一定是一个码字，称为零码字； (2)任意两码字的和仍是一个码字； (3)任意码字 是 的行

9、向量 的线性组合； （4）线性分组码的最小距离等于最小非零码字重量。,由偶校验码的检错概念，可以通过计算接收向量的所有校验方程值是否为0来判断传输是否可能有错，那么必有一个矩阵 满足,显然 的每一列或 的每一行确定了一个可能的分组码的校验方程， 的线性不相关行数最少要等于该码的所有可能的校验方程数，称这样的 矩阵 为 线性分组码的一致校验矩阵。,由 的每一行都是一个码字有,其中 G是k行、n列；H是r行、n列。 由线性空间的理论，当H的行秩为r时，H作为一个(n,r) 线性分组码的生成矩阵所生成的码是与G对应空间正交 的r维线性子空间，称为(n,k)线性分组码的对偶码或对 偶空间，并且有如下的

10、维数关系成立,定理： 任何满足下式的n维向量a均是一（n,k）线性分组码的码字 其中满足公式的H矩阵形式不唯一，但一个线性码的对偶码是惟一的。,系统码：生成矩阵 具有如下形式,在码字集合不变的情况下，任何一个线性分组码都可以一对一的去对应一个系统码。,对于系统码相应的一致校验矩阵,注意 与 仍然满足 。,以线性分组码的一致校验矩阵为生成矩阵产生的线性分组码称为原线性分组码的对偶码。,例6.2.3一个（5，3）线性分组码的,其中 到 的行初等变换过程为（ 表示第i行）,（5，3）线性分组码码例,由一致校验矩阵可以比较容易确定线性分组码的最小码距,定理 线性分组码的最小码距为 ，当且仅当其一致校验

11、矩阵H中任意 列线性无关，某 列线性相关。,该定理实际给出了计算线性分组码最小码距的一种方法。,6.2.1 线性分组码的描述 6.2.2 线性分组码的译码 6.2.3 码例与码的重构,译码的概念,检错译码：译码器输出为当前接收向量r和r是否有差错的标志s，即 。,r=c-e=c+e,纠错译码的译码成功状态：译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字 ，即 。,纠错译码的译码失败状态：译码器不能输出一个确切的码字 ，通常此时的输出y与检错译码输出相同。,定义：(n,k）线形分组码的伴随式是一个r(r=n-k)维向量s,，则传输中一定有错误发生,，则传输中要么无差错发生，要么差错

12、图案恰好为一个码字。,码组在传输中可能由于干扰而出错，例如发送码组为c，接收到的码组却是r，它们都是n位码的行向量，我们就定义erc为错码向量，错误图案。 其中,定理 可纠t错的q元线性分组码满足,当q=2，即二元码时：,当取等号时称为完备码。,伴随式纠错译码的通用译码方法,（1）按最可能出现的 个差错图案e，计算相应的伴随式s，并构造伴随式差错图案表 ； （2）对接收向量 计算伴随式 s ； （3）查 表得 ； （4）纠错计算 。,S是一个1r的向量，因此它有 种可能。而错误图样e的个数远大于 ，因此，必然有多个错误图样对应同一个校正子s。 标准阵列：,(7,4)码,例 已知(6,3)码生成

13、矩阵G如下，列出s与e的对照表。当收到码字r1 1 1 0 1 1时，解出对应的正确码字c及消息码字m。 解：已知生成矩阵为： Ik Q,我们知道s有23种形式，相应的码重最小的e向量有8种。s与e的对照表如下：,注意，（6，3）码只具有纠错1位的能力，s111时对应双错情况，即超出了该码的纠错能力范围。,查表我们可知，e向量为： e=0 1 0 0 0 0 这样我们就可得到正确的码字c，即 所以，消息码字为：,6.2.1 线性分组码的描述 6.2.2 线性分组码的译码 6.2.3 码例与码的重构,常见的线性分组码有重复码、汉明码、里德-穆勒码、戈雷码 （1）汉明码：,二元 Hamming码是

14、一种 的完备码，满足,其中列向量 为全部可能的非零 元组。,Hamming码的对偶码是一个 线性分组码，称为最大长度码，由于所有非零码字的重量均为 ，又称为等距码或单形（simplex）码。,例6.2.4 一个二元（7，4）Hamming码的系统码形式的矩阵和校验矩阵分别为,等价的编码方程为,伴随式计算方程,（2）Hadamard码,Hadamard码是由Hadamard矩阵派生出的一种纠错码。,阶实Hadamard矩阵由元素为+1，-1的矩阵递归定义为,例如,Hadamard矩阵为正交矩阵，即 中的任意不同两行（列）的点积为0，即,超正交矩阵 ：Hadamard矩阵 中的第1列（全+1列）去

15、掉后由于任两行的点积为-1。,将Hadamard矩阵元素+1/-1映射为0/1，则Hadamard矩阵映射后的行向量为一个二元向量，以这些二元向量的部份或全体就构成标准0/1二元意义上的分组码，并称为Hadamard码。具体的Hadamard码的选择构成有正交码、双正交码和超正交码三种形式。,（A）正交码：以 的全部行向量的0/1映射向量为码字。,（B）双正交码：以 和- 的全部行向量的0/1映射向量为码字。,（C）超正交码：以 的全部行向量的0/1映射向量为码字。,可以证明正交码、双正交码和超正交码均是线性分组码。,例6.2.5（7，3）超正交码的超正交矩阵 和生成矩阵G分别为,(3)里德-

16、穆勒（Reed-Muller）,阶码 是一种线性分组码，满足,其中各个子矩阵的定义为 1） 为 矩阵，由全1向量构成。 2） 为 矩阵，由所有可能的m元组组成矩阵的列向量。 3） 为 的所有两不同行向量的叉积构成其全部行向量的矩阵。两向量的叉积为 4） 为 的所有三不同行向量的叉积构成其全部行向量的矩阵。 5） 为 的所有 个不同行向量的叉积构成其全部行向量的矩阵。,r,例6.2.6 的 阶RM码的各个子矩阵有,码的对偶码仍是一个Reed-Muller码， 为 码。,（4）戈雷码 二元戈雷码是一种就纠3个错的完备线形分组码， 满足： n=23 k=12,由于,因此某种二元（23,12）码一定可以纠正任意小于等于3个差错，所以,6.3 循环码,6.3.1循环码的多项式描述,6.3.2循环码的生成矩阵,6.