第六章_信道编码.ppt

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.3 编码信道 6.1.3：检错和纠错原理 6.1.4：检错和纠错方式和能力,消息,编码信道模型,n-1,当码字C和接受向量R均由二元序列表时，称编码信道为二进制信道 C=(c0,c1,cn-1) 如果对于任意的n都有： P(r/c)=p(ri/ci) 则称此二进制信道为无记忆二进制信道。 p(0/1)=p(1/0)=p0 则称此信道为无记忆二进制对称信道BSC,i=0,BSC输入输

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等重码如表（6.1.1）所示，其码率 为,5中取3等重码,5中取3等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错,

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

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

8、.2.1 线性分组码的描述 6.2.2 线性分组码的译码 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

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

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

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

12、生，要么差错图案恰好为一个码字。,定理 可纠t错的q元线性分组码满足,伴随式纠错译码的通用译码方法,（1）按最可能出现的 个差错图案 ，计算相应 的伴随式，并构造伴随式差错图案表 ； （2）对接收向量 计算伴随式； （3）查 表得 ； （4）纠错计算 。,6.2.1 线性分组码的描述 6.2.2 线性分组码的译码 6.2.3 码例与码的重构,常见的线形分组码有重复码，汉明 码，里德-穆勒码，戈雷码 （1）汉明码：,二元 Hamming码是一种 的完备码，满足,其中列向量 为全部可能的非零 元组。,Hamming码的对偶码是一个 线性分组码，称为最大长度码，由于所有非零码字的重量均为 ，又称为等

13、距码或单形（simplex）码。,例6.2.4 一个二元（7，4）Hamming码的系统码形式的矩阵和校验矩阵分别为,等价的编码方程为,伴随式计算方程,（2）Hadamard码,Hadamard码是由Hadamard矩阵派生出的一种纠错码。,阶实Hadamard矩阵由元素为+1，-1的矩阵递归定义为,例如,Hadamard矩阵为正交矩阵，即 中的任意不同两行（列）的点积为0，即,超正交矩阵 ：Hadamard矩阵 中的第1列（全+1列）去掉后由于任两行的点积为-1。,将Hadamard矩阵元素+1/-1映射为0/1，则Hadamard矩阵映射后的行向量为一个二元向量，以这些二元向量的部份或全体

14、就构成标准0/1二元意义上的分组码，并称为Hadamard码。具体的Hadamard码的选择构成有正交码、双正交码和超正交码三种形式。,（A）正交码：以 的全部行向量的0/1映射向量为码字。,（B）双正交码：以 和- 的全部行向量的0/1映射向量为码字。,（C）超正交码：以 的全部行向量的0/1映射向量为码字。,可以证明正交码、双正交码和超正交码均是线性分组码。,例6.2.5（7，3）超正交码的超正交矩阵 和生成矩阵G分别为,(3)里德-穆勒（Reed-Muller）,阶码 是一种线性分组码，满足,其中各个子矩阵的定义为 1） 为 矩阵，由全1向量构成。 2） 为 矩阵，由所有可能的m元组组成

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

16、5循环码的编码电路,6.3.6循环码的伴随多项式与检测,6.3.7BCH码与RS码,6.3.1 循环码的多项式描述 6.3.2循环码的生成矩阵 6.3.3系统循环码 6.3.4多项式运算电路 6.3.5循环码的编码电路 6.3.6循环码的伴随多项式与检测 6.3.7BCH码与RS码,更好的设计和实现线性分组码的方法是引入特定的数学结构来界定某一类线性分组码。循环码即是采用循环移位特性界定的一类线性分组码。,6.3.1 循环码的多项式描述,定义 如果一个线性分组码的任意一个码字c(n元组)都是另外一个码字c 的循环移位,称此线性分组码为一个循环码.,将循环码的码字用多项式c(x)，称为码多项式（

17、简称码式）表示后，循环码集合表示C(x),例 6.3.2 如下确定的CA是线性循环码，CB是非循环的线性分组码，CC是非线性的循环码。,， ，,定理： （n,k）循环码C( x)中存在唯一的一个 非零的，首一的和最低次为r（rn）的码 多项式g(x)满足： g(x)=xr+gr-1xr-1+.+g1X+g0 g00 r=n-k 并且c(x)是码式当且仅当c(x)是g(x)的倍式,定义 由上述定理确定的码式g(x)称为循环码(n,k)的生成多项式.,因此(n,k)循环码的构造是如何构造生成多项式g(x)。,循环码由生成多项式的倍式组成,定理： g(x)是（n,k）循环码的生成多项式， 当且仅当g

18、(x)是xn-1的r=n-k次因式。,6.3.1循环码的多项式描述 6.3.2 循环码的生成矩阵 6.3.3系统循环码 6.3.4多项式运算电路 6.3.5循环码的编码电路 6.3.6循环码的伴随多项式与检测 6.3.7BCH码与RS码,6.3.2循环码的生成矩阵和校验矩阵,(n,k)循环码的生成矩阵为,(n,k)循环码的校验矩阵为,6.3.1循环码的多项式描述 6.3.2循环码的生成矩阵 6.3.3 系统循环码 6.3.4多项式运算电路 6.3.5循环码的编码电路 6.3.6循环码的伴随多项式与检测 6.3.7BCH码与RS码,6.3.3 系统循环码,循环码的系统码码式为,6.3.1循环码的

19、多项式描述 6.3.2循环码的生成矩阵 6.3.3系统循环码 6.3.4 多项式运算电路 6.3.5循环码的编码电路 6.3.6循环码的伴随多项式与检测 6.3.7BCH码与RS码,6.3.4 多项式运算电路,因为多项式,表示时间序列,所以多项式的计算表现为对时间序列的操作.,多项式a(x)与b(x相加电路,a(x)与g(x)的一般乘法电路,6.3.1循环码的多项式描述 6.3.2循环码的生成矩阵 6.3.3系统循环码 6.3.4多项式运算电路 6.3.5 循环码的编码电路 6.3.6循环码的伴随多项式与检测 6.3.7BCH码与RS码,非循环码编码器 根据多项式乘法电路和循环码码式是生多 项式倍式原理，多项式乘法电路