信息论与编码杜玉华第8章

错编码，在接收端用译码器对接收到的数据进行
译码后检测有无差错，通过按预定规则的运算，
如检测到差错，则确定差错的具体位置和性质， 自动加以纠正，故称为“前向纠错”。
8.2 纠错编码分类
HEC方式：是检错重发和前向纠错两种方式的
混合。发送端用编码器对发送数据进行便于检错
和纠错的编码，通过正向信道送到接收端，接收
8.3 线性分组码
2. 系统形式的生成矩阵 (n,k)码的任何生成矩阵都可以通过行运算（以 及列置换）简化成“系统形式” 。
1 0 0 | p ( k 1)( n k 1) 0 1 0 | T G [I k P ] | p1( n k 1) 0 0 1 | p 0 ( n k 1) p ( k 1)1 p11 p 01 p ( k 1) 0 p10 p 00
8.2 纠错编码分类
前向纠错方式----用于纠错的纠错码在译码器输 出端总要输出一个码字或是否出错的标志，这种 纠错码的应用方式称为前向纠错方式(FEC， Forward-error control)。
另外用于检错与纠错的方式还有混合纠错(HEC ，Hybrid Error Correction)。 如图所示为上述几种检错与纠错方式示意图， 图中有斜线的方框表示在该端检出错误。
两个序列之间的汉明距离定义为两个序列 之间对应位不同的位数。
8.1 纠错编码的基本概念
例如：α和β为码组X中的两个不同码字， X为一个长度为N的二元码组，其中：
α=[a1,a2,……aN] β=[b1,b2,……bN] 则α与β的汉明距离为： d=0表明为全同码，d=N表明为全异码 ai∈{0,1} bi∈{0,1}
8.3 线性分组码
4. 系统码 若通过行运算和列置换能将两个生成矩阵G互
等，则称这两个G等效。非系统码的G可通过运算
转变为系统码的G。等效的两个G生成的两个(n,k) 线性码也是等效的。因此，每个(n,k)线性码都可 以和一个系统的(n,k)线性码等效。
8.3 线性分组码
5. 空间构成 n维n重空间有相互正交的n个基底，选择k个基 底构成码空间C，选择另外的(n-k)个基底构成空 间H，C和H是对偶的CHT＝0, GHT=0 。
8.3 线性分组码
n维n重空间 Vn
k维k重 信息组 空间m
k维n重 码空间c G
n-k 维 n 重对偶 空间D H
8.3 线性分组码
用gi表示第i个基底并写成矩阵
g i [ gi ( n1) , gi ( n2) ,, gi1 , gi 0 ]
再将k个基底排列成k行n列的G矩阵
g ( k 1)( n 1) g ( k 1)1 T G [ g k 1 , g k , , g1 , g 0 ] g1( n 1) g11 g 01 g 0 ( n 1) g ( k 1) 0 g10 g 00
8.3 线性分组码
为了叙述方便，以下认为码失、码字、码组是
同义词，对n重矢量、1n矩阵、行矢量等的数学
表达式也不作严格区别。
8.3 线性分组码
设有等概出现的M组待传信源消息，每组有k位
，即 。今加上r个多余位，使每组消息变成
n=k+r位。而n位长的二进制序列共有2n个，但由
于信息组只有2k个，故有2n-2k个n位序列不是码字 。 设码字的形式为：
dmin=min{d(α,β)
α,β∈X
α≠β}
码的最小汉明距离是衡量码的纠、检错能力 的重要参数，码的最小距离越大，其纠、检 错能力越强。
8.1 纠错编码的基本概念
对于码C中的某一码字，其非零元素的 个数称为该码字的汉明重量。
8.2 纠错编码分类
8.2 纠错编码分类
对不同的信道需要设计不同类型的信道编码方 案，按照信道特性进行划分，信道编码可分为： 以纠独立随机差错为主的信道编码、以纠突发差 错为主的信道编码和纠混合差错的信道编码。
Ik是k×k单位矩阵，P是k×(n-k)矩阵。
8.3 线性分组码
3. 生成的码字C
前k位由单位矩阵Ik决定，等于把信息组m原封
不动搬到码字的前k位；其余的n-k位叫冗余位或
一致校验位，是前k个信息位的线性组合。这样生
成的（n,k）码叫做系统码。若生成矩阵G不具备 系统形式，则生成的码叫做非系统码。系统化不 改变码集，只是改变了映射规则。
8.2 纠错编码分类
其中分组码又可分循环码和非循环码：对循环
码而言，其码书的特点是，若将其全部码字分成
若干组，则每组中任一码字中码元循环移位后仍
是这组的码字；对非循环码来说，任一码字中的
码元循环移位后不一定再是该码书中的码字。
8.2 纠错编码分类
卷积码----把信息序列以每k0(通常较小)个码元 分段，编码器输出该段的监督码元r=n- k0 不但与本段的k0个信息元有关，而且还与其前面L 段的信息码元有关，故记卷积码为(n, k0,L)。 按照每个码元的取值来分，可有二元码和多元 码。由于目前的传输或存储系统大都采用二进制 的数字系统，所以一般提到的纠错码都是指二元 码。
传输特性不理想以及存在加性噪声,在接收端往
往会产生误码。
8.1 纠错编码的基本概念
目的在于提高通信（或存储）的可靠性， 减低误码率。 假设信源信息是二进制数字序列，将信 源编码其的输出序列构成长度为n的段， 记为C
C=c1,c2,…,cn
8.1 纠错编码的基本概念
设有m个不同的信息序列，每个不同的 序列由k（k<n)位（信息位），它由码元 组成。[C]为编码器的输出，称为码字矢 量，它由n位码元组成，其中有k位信息 元，r=n-k位监督元。
设某(7,3)线性分组码各码字的校验元与信息元
之间的关系由下述方程决定：
8.3 线性分组码
称此方程为该（7,3）线性分组码的校验方程， 由于该码系的所有码字都按同一规则确定与校验 ，故又称为一致校验方程。
8.3 线性分组码
如：信息组为101，即
代入一致校验方程得：
所以由信息组101编出的可送给信道传输的、具 有一定纠错能力的码字为：1010011。同理可求出 与其他7个信息组相对应的码字见下表：
从功能上看，信道编码可分为检错(可以发现 错误)码与纠错(不仅能发现而且能自动纠正)码两 类，纠错码一定能检错，检错码不一定能纠错， 平常所说的纠错码是两者的统称。
Hale Waihona Puke 8.2 纠错编码分类根据信息码元与监督码元之间的关系，纠错码
分为线性码和非线性码。
线性码——信息码元与监督码元之间呈线性关
系，它们的关系可用一组线性代数方程联系起来
8.1 纠错编码的基本概念
对于二元符号表上的分组码C，由表示消 息序列的长度为n的m个二元序列构成的集 合，称为二元分组码。 对于2k个n长码字全体构成的分组码，其 码字中的k位称为信息位，n-k位称为校验 位或监督位。 线性分组码：监督元与信息元之间的关系可 用一组线性方程组来描述的(n, k)分组码。
d min 2t 1
③ 若要求发现e个同时又纠正t个独立差错，则
dmin e t 1(e t )
8.3 线性分组码
消息m m=(mk-1,…,m1,m0)
(n,k) 分组编码器
码字c c=(cn-1,…,c1,c0)
码集 C 能否构成 n 维 n 重矢量空间的一个 k 维 n 重 子空间？如何寻找最佳的码空间？ qk 个信息元组 以什么算法一一对应映射到码空间。 码率－－编码效率：Rc =k/n
8.1 纠错编码的基本概念
• 编码效率：
–一个组中信息所占的比重
k R n
–k：信息码元的数目 –n：编码组码元的总数目 –r：监督码元的数目 n = k+ r
8.1 纠错编码的基本概念
若（n，k）分组码中k个信息位同原始k 个信息位相同，且位于n长码字的前（或后） k位，为校验位位于其后（或前），则称该 分组码为系统码，否则为非系统码。
8.2 纠错编码分类
1.检错与纠错方式
自动请求重发方式----用于检错的纠错码在译
码器输出端给出当前码字传输是否可能出错的指
示，当有错时按某种协议通过一个反向信道请求 发送端重传已发送的全部或部分码字，这种纠错 码的应用方式称为自动请求重发方式(ARQ， Automatic-Repeat-reQuest)。
端对少量的接收差错进行自动前向纠正，而对超 出纠正能力的差错则通过反馈重发方式加以纠正 ，所以是一种纠检结合的混合方式。
定理1 若纠错码的最小距离为dmin，那么如下三个 结论的任何一个结论独立成立： ① 若要发现e个独立差错，则要求最小码距 d min e 1 ② 若要纠正t个独立差错，则要求最小码距
第8章 纠错编码
8.1纠错编码的基本概念
8.2 纠错编码分类 8.3线性分组码 8.4循环码
8.1 纠错编码的基本概念
• 信源编码提高数字信号有效性
• 将信源的模拟信号转变为数字信号
• 降低数码率,压缩传输频带(数据压缩)
• 信道编码提高数字通信可靠性
• 数字信号在信道的传输过程中,由于实际信道的
信息组 000 001 010 011
对应码字 0000000 0011101 0100111 0111010
信息组 100 101 110 111
8.3 线性分组码
线性分组码码空间C是由k个线性无关的基底
g k 1 ,, g 1 , g 0 张成的k维n重子空间，码空间的所有
元素（即码字）都可以写成k个基底的线性组合， 即 c mk 1g m1 m1g1 m0 g 0
这种线性组合特性正是线性分组码名称的来历 。显然，研究线性分组码的关键是研究基底、子 空间和映射规则，如图所示