《数字通信原理》第8章 差错控制编码：基本概念与线性分组码

1、数字通信原理(8-1)冯穗力等编著电子工业出版社2012年8月2010 Copyright 1SCUT DT&P Labs第 8 章 差错控制编码基本概念与线性分组码本章第一部份的基本内容：差错控制编码的基本概念；简单的差错控制方法；信道编码的基本概念与定理*；线性分组码的代数基础*；线性分组码的基本性质循环码。2010 Copyright 2SCUT DT&P Labs8.1 引言 2010 Copyright 3SCUT DT&P Labs 引言 数据在物理信道中传输时通常会因为信道的非理想特性和引入的噪声造成传输的错误。 差错控制编码的基本概念：通过对数据进行某种编码处理，使得接收端可以

2、判断接收到的数据，是否出现错误，甚至可以纠正一定范围内错误。 差错控制编码是将有误码的物理信道改造成无差错的逻辑信道的一种方法。 所谓差错控制编码，通常是通过代数的方法，加入与待传输的数据有一定关联关系的监督位来实现的。 在接收端可根据特定的关联关系是否受到破环来判别是否出现错误，并可在一定程度上根据出错的情况纠正错误。 在纠错编码中加入的监督位本身并不携带信息，因此有时也将监督位成为冗余位。第8章 差错控制编码2010 Copyright 4SCUT DT&P Labs 引言 若每一组 位信息位，编码后生成 位长度的码字 则定义编码效率 冗余度第8章 差错控制编码2010 Copyright

3、 5SCUT DT&P Labs8.2 差错控制编码的主要类型和方式 2010 Copyright 6SCUT DT&P Labs 差错控制编码的主要类型和方式 差错控制编码的主要类型 (1)线性码与非线性码 线性码：监督码元与信息码元间的关系是一种线性关系； 非线性码：监督码元与信息码元间的关系则是一种非线性的关系。 (2)分组码与卷积码 分组码：监督码元与信息码元间以码组为单位建立关系； 卷积码：监督码元不仅与本组的信息码元有关，还与前面若干个码组的信息码元有关。 第8章 差错控制编码2010 Copyright 7SCUT DT&P Labs第8章 差错控制编码 差错控制编码的主要类型和

4、方式(续) 差错控制编码的主要类型 (3)系统码与非系统码 系统码：编码后信息码元部分的排列结构保持不变； 非系统码，编码后码组中信息码元部分的排列结构发生了变化，一般不能看出原来信息码元的图样结构。 2010 Copyright 8SCUT DT&P Labs 差错控制编码的主要类型和方式(续) 通信系统通常可分为单工、半双工、和全双工三种工作方式。 单工：单向、没有回传通道的系统称之； 半双工：双向，但发送和接收必须分时进行的系统称之； 全双工：双向，发送和接收可同时进行的系统称之。 不同的差错控制方式，对系统有不同的要求。 差错控制方式 (1)检错重发：通过差错控制编码，使得接收端具有检

5、错能力，接收端如果发现传输出错，通过反向信道请求重发。 检错重发方式，要求系统具有反向传输通道； 检错重发方式通常具有较高的编码效率。 第8章 差错控制编码2010 Copyright 9SCUT DT&P Labs 差错控制编码的主要类型和方式(续) (2)前向纠错：采用具有检错和纠错的编码算法，接收端不仅能够检测出错误，而且定位出码字中错误的位置并加以纠正。 前向纠错的方法适用于包括单工通信系统的应用场合。 在一些对实时性要求较高的通信场合，必须采用前向纠错的方法。 前向纠错需要定位错误的位置和出现何种错误(对二进制以外的纠错编码)，通常编译码的方法比较复杂，效率较低、 (3)混合差错控制

6、：结合检错重发和前向纠错方式优点的差错控制方法； 对于出现较少错误时，由前向纠错方式加以纠正；当经纠错后仍有错误时，则启动检错重发机制。 混合差错是一种兼顾效率和复杂性的方法。第8章 差错控制编码2010 Copyright 10SCUT DT&P Labs8.3 简单的差错控制方法 2010 Copyright 11SCUT DT&P Labs 简单的差错控制方法 奇偶校验码 奇偶校验码是一种通过增加1位监督位，从而使得码组具有检测1位误码的差错控制方法。 (1)偶校验 设待发送的信息码组： 加入监督位 其中 由此可得监督位与信息位的关联关系 若传输过程中出现1位的误码，上述关联关系将被破坏

7、，因此可发现出现错误。 因编码后码组 中有偶数个1，故称为偶校验。第8章 差错控制编码2010 Copyright 12SCUT DT&P Labs 简单的差错控制方法(续) (2)奇校验 若加入的监督位由下式确定 则由此建立的关联关系为 编码后产生的码组 中将有奇数个1，故称奇校验。 同样，传输过程的1位误码将破坏上述的关联关系。 容易验证：当出现奇数位的误码时，关联关系均被破坏，因此可以发现错误。而当出现偶数位的错误时，不能发现错误。第8章 差错控制编码2010 Copyright 13SCUT DT&P Labs 简单的差错控制方法(续) 所有可能的信息码组经过差错控制编码后，得到的输出

8、码组(也称为码字)构成了一个称为许用码字的集合：许用码字集 不在许用码字集中的码字称为禁用码字。 一般地，如果传输出错使得原来的许用码字变为禁用码字，则这种错误可被发现； 示例：偶校验码字中所有含偶数个“1”的码字为许用码字； 所有含奇数个“1”的码字为禁用码字。 奇校验码字中所有含奇数个“1”的码字为许用码字； 所有含偶数个“1”的码字为禁用码字。 如果传输过出错使得原来的许用码字变为另外一个许用码字，则这种错误不能被发现。第8章 差错控制编码2010 Copyright 14SCUT DT&P Labs 简单的差错控制方法(续) 示例: 3位二进制码组的所有组合 000，001，010，0

9、11，100，101，110，111 (1)若所有组合均为许用码字，每个码字可携带3比特信息； 任一许用码字出错都变为另一许用码字，无差错控制功能 (2) 若选择 许用码字：000，011，101，110 禁用码字：111，001，010，100 编码后每个3位的许用码字可携带2比特信息； 任一许用码字的1位误码都会变为禁用码字，因此可发现任意的1位误码；该码实际上是一种偶校验码。 2位的误码将变为另一许用码字，错误不能被发现。 注意：需要合理地确定许用码字方可使编码码字具有检错能力。第8章 差错控制编码2010 Copyright 15SCUT DT&P Labs第8章 差错控制编码 简单的

10、差错控制方法(续) (2) 若选择 许用码字：000，111 禁用码字：001，010，100，011，101，110 编码后每个3位的许用码字可携带1比特信息； 任一许用码字的2位以下的误码都会变为禁用码字，因此可发现任意的2位误码； 采用择多逻辑的方法可纠正出现1位误码时的错误 3位的误码将使“000” “111” ，错误不能被发现。 本例的启示： 差错控制能力越强，相应的冗余的开销越大； 任何一种差错控制编码，其差错控制能力都有一定限制； 需要合理地选择许用码字。2010 Copyright 16SCUT DT&P Labs 简单的差错控制方法(续) 重复码 在上例中可见，“000”和“

11、111”是3位码元均相同，是一种3位的重复码，可发现任意的2位错误和纠正1位错误。 3位的重复编码可推广到一般的情形，若 n 位的重复码用于表示1比特信息。如 “0000” 0 ； “1111” 1 则可发现任意的 位误码；采用择多逻辑进行判决，可纠正任意的少于 位的误码。 重复码编译码简单，但效率较低。第8章 差错控制编码2010 Copyright 17SCUT DT&P Labs 简单的差错控制方法(续) 水平奇偶校验码 奇偶校验码简单且效率高 但只能检测出奇数位的错误。 水平奇偶校验码是一种通过组合 个简单奇偶校验码字而构建的一种能够检测任意的小于等于 位连续误码的编码方法。第8章 差

12、错控制编码2010 Copyright 18SCUT DT&P Labs 简单的差错控制方法(续) 编码： 个简单的奇偶校验码字按照如下的方式排列 信息码组 监督码元 (*) 传输： 按列顺序发送数据 译码： 接收到数据后重新按照(*)排列，当连续误码的个数小于等于 时，每一行中只会1位误码，因此可以检测出相应的误码。第8章 差错控制编码2010 Copyright 19SCUT DT&P Labs8.4 信道编码的基本概念和定理* 2010 Copyright 20SCUT DT&P Labs 信道编码的基本概念和定理 编码信道的基本模型 记 信源符号集 编码输出码字集 接收码字集 信道译码

13、输出码字集 发送码字的先验概率 注：在本教材中，只讨论离散无记忆信道的情形。第8章 差错控制编码2010 Copyright 21SCUT DT&P Labs 信道编码的基本概念和定理(续) 记接收码字的统计特性为 对于离散信道，其特性可由转移概率矩阵来表示 因为有第8章 差错控制编码2010 Copyright 22SCUT DT&P Labs 信道编码的基本概念和定理(续) 由先验概率 及转移概率矩阵，可导出后验概率矩阵 及 的分布特性第8章 差错控制编码2010 Copyright 23SCUT DT&P Labs 信道编码的基本概念和定理(续) 译码规则对译码性能的影响 示例 设发送码

14、字集 接收码字集 两不同的二元对称信道分别为 (1) (2) 分析在两种信道下不同译码规则对译码性能的影响。 解：若记译码的规则为第8章 差错控制编码2010 Copyright 24SCUT DT&P Labs 信道编码的基本概念和定理(续) 可能的译码方法包括如下 4 种 对于信道1： 不同译码规则导致的出错概率依次分别为 采用规则(2),出错概率最小；第8章 差错控制编码2010 Copyright 25SCUT DT&P Labs 信道编码的基本概念和定理(续) 对于信道2： 不同的译码规则导致的出错概率依次分别为 采用规则(3),出错概率最小。 启示： 不同的译码规则，对误码率的影响

15、很大； 对不同的信道特性，应选择不同的译码规则。第8章 差错控制编码2010 Copyright 26SCUT DT&P Labs 信道编码的基本概念和定理(续) 最大后验译码准则 已知后验概率矩阵 若 译码正确 译码错误 误码的概率 正确译码的概率第8章 差错控制编码2010 Copyright 27SCUT DT&P Labs 信道编码的基本概念和定理(续) 若规定译码规则 则可使得差错概率最小最佳译码方法。 具体的译码操作方法 由 若 则取 作为译码输出。第8章 差错控制编码2010 Copyright 28SCUT DT&P Labs 信道编码的基本概念和定理(续) 示例：利用最大后验

16、译码准则分析上一示例的译码问题。 (1)首先确定系统的后验概率矩阵 a.若转移概率矩阵为 因为有 可得 导出后验概率矩阵第8章 差错控制编码2010 Copyright 29SCUT DT&P Labs 信道编码的基本概念和定理(续) 最佳的译码规则 正确译码的概率 误码率第8章 差错控制编码2010 Copyright 30SCUT DT&P Labs第8章 差错控制编码 信道编码的基本概念和定理(续) b.若转移概率矩阵为 同理可得 相应的后验概率矩阵 2010 Copyright 31SCUT DT&P Labs 信道编码的基本概念和定理(续) 此时译码规则相应地变为 正确译码的概率 误

17、码率为 由本例可见： 采用后验概率译码准则，无论哪一种情形，总是可以得到最好的译码效果。 第8章 差错控制编码2010 Copyright 32SCUT DT&P Labs 信道编码的基本概念和定理(续) 最大似然译码准则 已知概率的基本关系式 对于离散无记忆信道 因而 在先验等概的条件下，最大后验概率译码规则可变为 即此时直接可根据转移概率矩阵进行最佳判决。 注意在上例中转移概率矩阵与后验概率矩阵完全相同。第8章 差错控制编码2010 Copyright 33SCUT DT&P Labs 信道编码的基本概念和定理(续) 费诺不等式 若记 发送符号集及分布 接收符号集及分布 发送与接收符号集中

18、元素相同 发送符号经信道传输后出错的概率(误码率)可表示为 疑义度：发送 接收到 后，关于 仍然存在的平均不确定性称之。 根据条件熵的定义，疑义度为第8章 差错控制编码2010 Copyright 34SCUT DT&P Labs 信道编码的基本概念和定理(续) 接收译码错误判决的概率 正确的判决概率 与熵的定义类似，可定义判决的不确定性 定理 8.4.1(费诺不等式) 与 间有如下的关 系式 费诺不等式表明 的大小主要由判决不确定性及判决错误导致信息的丢失的多少决定。 平均每个符号判决错误导致信息的丢失小于等于 。第8章 差错控制编码2010 Copyright 35SCUT DT&P La

19、bs 信道编码的基本概念和定理(续) 联合典型序列集 满足下列条件的序列集 分别称之 的 典型序列集和联合典型序列集。 分别记为 和 。第8章 差错控制编码2010 Copyright 36SCUT DT&P Labs 信道编码的基本概念和定理(续) 条件下 的典型序列集定义为 记为 。 典型序列的有关性质 性质1 当 N 足够大时，有 性质2 当 N 足够大时，有 上述性质描述了典型序列集与熵函数及平均互信息之间的关系。第8章 差错控制编码2010 Copyright 37SCUT DT&P Labs 信道编码的基本概念和定理(续) 定义8.4.3 编码速率(纠错编码的信息率)定义为: 其中

20、 信息位长度， 编码输出码字长度。 归一化信道容量 已知离散信道的容量 有信息论的基本知识，有 定义归一化信道容量为第8章 差错控制编码2010 Copyright 38SCUT DT&P Labs 信道编码的基本概念和定理(续) 若记发送序列为 接收序列为 对于离散无记忆信道： 对于N位的二元码元序列，若编码速率为 则 可能的码字组合数 合法的码字组合数 合法的码字标号集 设发送的消息编号为 ； 编码 译码第8章 差错控制编码2010 Copyright 39SCUT DT&P Labs 信道编码的基本概念和定理(续) 发送编号为 消息时出错的概率 平均误码率可定义为 定义8.4.4 (可达

21、编码速率) 若 则称 是可达的。 第8章 差错控制编码2010 Copyright 40SCUT DT&P Labs 信道编码的基本概念和定理(续) 定理8.4.5 (信道编码定理) 给定归一化信道容量 若 ，则 是可达的。 信道编码定理给出了编码速率 可达的基本条件。 信道可达性的定义包含了可通过增大码字的长度来改善信道编码误码性能的思想。 信道编码定理并没有告诉我们如何具体应如何编码，才能保证译码能够满足 的条件。 第8章 差错控制编码2010 Copyright 41SCUT DT&P Labs第8章 差错控制编码 信道编码的基本概念和定理(续) 例8.4.4 设某通信系统的不加编码的错

22、误概率为 编码速率为 ，分析不同编码方式的效果。 (1)每两比特信息为一组进行编码 详见书中的分析，相应的错误概率变为 2010 Copyright 42SCUT DT&P Labs第8章 差错控制编码 信道编码的基本概念和定理(续) (2)每三比特信息为一组进行编码 相应的错误概率变为 本例给出了一个示例，说明在反映编码效率的编码速率不变的情况下，可以通过改变码字的长度来改善误码性能。2010 Copyright 43SCUT DT&P Labs8.5 线性分组码的代数基础* 2010 Copyright 44SCUT DT&P Labs 线性分组码的代数基础 定义8.5.1 对于某种代数运

23、算法则“*”的非空集合G,满足下列公理条件的时称之为一个群： 封闭性： 结合率： 存在恒等元素： 存在逆元素： 定义8.5.2 称群为交换群，若满足如下的交换率 第8章 差错控制编码2010 Copyright 45SCUT DT&P Labs 线性分组码的代数基础(续) 示例：整数集，按照加法运算规则，构成一个交换群。其中的恒等元素为“0”，任一元素的逆元素为即为该整数的负数。 示例：在二元的非空集合0,1中，定义运算法则 该二元集合构成一个交换群，其中的恒等元素为“0”，每个元素的逆元素为其自身。 第8章 差错控制编码2010 Copyright 46SCUT DT&P Labs 线性分组

24、码的代数基础(续) 定理8.5.3 群G具有以下的性质： (1) 群G的恒等元是唯一的，群中每个元素的逆元素也是唯一的； (2) 定义了运算法则“*”的群G， ，有 定义8.5.4 若H是群G的一个非空子集，如果在同样的运算法则“*”下，集合H也构成一个群，则非空子集称为群G的一个子群。 定义8.5.5 设集合 是群 的一个子群， 是G中的一个满足条件 的元素，则把 定义为子群H在群中的一个关于的左陪集；把 定义为子群H在群中的一个关于的右陪集。 第8章 差错控制编码2010 Copyright 47SCUT DT&P Labs 线性分组码的代数基础(续) 对于交换群，左陪集和右陪集相等，简称

25、为陪集。 定理8.5.6 子群具有以下的主要性质（1）群 的所有元素可由子群 以及它的若干陪集构成的集合表示其中 。（2）群G中的两个元素 和 在子群的同一陪集之中的充分必要条件是： （3）子群H的两个不相同的陪集一定不相交，即两个不同的陪集一定没有公共元素。 第8章 差错控制编码2010 Copyright 48SCUT DT&P Labs 线性分组码的代数基础(续)定义8.5.7 若在非空集合F中，规定了“”和“*”两种运算，且如下的条件（1）非空集合构成运算法则“”的交换群；（2）非空集合构成运算法则“*”的交换群；（3）对两种运算法则“”和“*”，非空集合中的元素满足分配律，即对任意的

26、 ，有 则称非空集合F构成一个域，其集合中包含的元素的个数称为该集合的阶数。示例：对于普通的加法和乘法运算 全体有理数构成一个有理数域； 全体实数构成一个实数域； 全体复数则构成一个复数域。第8章 差错控制编码2010 Copyright 49SCUT DT&P Labs 线性分组码的代数基础(续) 有限域的概念 有限域：包含有限的q个元素的域称之； 有限域又称为伽罗华（Galois）域，记为 。 有限域中元素的个数q，一定是某个素数p的幂，即 。 示例：非空的二元集合0,1中，定义加、乘运算 加运算 乘运算 构成二元有限域第8章 差错控制编码2010 Copyright 50SCUT DT&

27、P Labs 线性分组码的代数基础(续) 包含素数 的 n 次幂 个元素的有限域 是线性分组码中最常用的有限域。 元素 的阶 ，因为 中只有有限个元素 一定存在正整数k，使得 ，能使上式成立的最小的k 称为元素 的阶。 本原元 若对于元素 ，其阶等于 ，则该元素称为有限域 的本原元。 任何有限域都存在本原元。 有限域中的任一非零元素都可以用本原元的某次幂来表示。第8章 差错控制编码2010 Copyright 51SCUT DT&P Labs 线性分组码的代数基础(续) 示例：有限域 ，其中 为本原元。 由本原元的定义，有 。 对该有限域，加法和乘法可分别定义为第8章 差错控制编码 *2010

28、 Copyright 52SCUT DT&P Labs 线性分组码的代数基础(续) 系数定义在二元有限域上的多项式 一般地，总有 其中的余式可记为 ，称 为模。 多项式关于模 的加法和乘法运算 加法 乘法 若 为 次的多项式，则余式具有如下的一般形式第8章 差错控制编码2010 Copyright 53SCUT DT&P Labs 线性分组码的代数基础(续) 因为 若 则 共有 种不同的组合， 相应地有 种不同的 余式。 若将每个余式 看作一个元素，若 是一个不可约多项式，则所对应的 个余式 作为元素的集合构成一个有限域。第8章 差错控制编码2010 Copyright 54SCUT DT&P

29、 Labs第8章 差错控制编码 线性分组码的代数基础(续) 示例：多项式 是一不可约多项式，以此为模的余式为元素的集合： 构成一有限域。 元素间的加法 与乘法运算， 参见加法表与 乘法表。2010 Copyright 55SCUT DT&P Labs第8章 差错控制编码 线性分组码的代数基础(续) 本原多项式 n 次不可约多项式 模 有限域 若 的根是本原元，则称 是本原多项式。 示例：多项式 是一不可约多项式。 由此 因为对于模 因此 是多项式 的根 即有2010 Copyright 56SCUT DT&P Labs第8章 差错控制编码 线性分组码的代数基础(续) 示例(续) 参见右表，元素

30、 的阶为 ， 可见 是一本 原元。 多项式 为本原多项式。2010 Copyright 57SCUT DT&P Labs第8章 差错控制编码 线性分组码的代数基础(续) 多项式的根 这里所讨论的多项式是指系数与根均定义在有限域中的多项式。 示例：求解定义在有限域 上的多项式 的根。 注意：在上面的方程中，未知数是 。 有限域上的方程并无一般解，因为方程的解是定义在有限域上的，所有可能的解只有有限多个，所以可用试探法求解； 根据上一示例的元素表，可得 2010 Copyright 58SCUT DT&P Labs第8章 差错控制编码 线性分组码的代数基础(续) 同样可得 可见 是方程的根。 多项

31、式的一个重要性质 定理8.5.8 系数取值在二元域0,1上的多项式 对任意的整数 l ，均有2010 Copyright 59SCUT DT&P Labs第8章 差错控制编码 线性分组码的代数基础(续) 极小多项式 定义8.5.9 设 是 中的元素， 是系数为二元域上元素、以 为根的最低次多项式，则称 是 的极小多项式。 定理8.5.10 上的任何元素 必有一个极小多项式。 定理8.5.11 有限域 上的极小多项式一定是不可约、且是唯一的。 若 的极小多项是 ，则应有 ，由定理8.5.8，有 即 均为该极小多项式的根。2010 Copyright 60SCUT DT&P Labs第8章 差错控

32、制编码 线性分组码的代数基础(续) 线性分组码的代数基础(续) 示例：求有限域 上，元素 的极小多项 。 由前面分析，对 均有： 因为 可见从 的第四项后开始重复，因此最小多项式为2010 Copyright 61SCUT DT&P Labs第8章 差错控制编码 线性分组码的代数基础(续) 线性空间与其子空间 定义8.5.12 设 是一个数域， 是某一类运算对象的非空集合，在“”和“*”两种运算规则下，满足下列条件（1）非空集合 对“”运算规则构成一交换群；（2）非空集合 和数域 在运算规则“*”下满足封闭性，即对任 ，有（3）非空集合 和数域 在运算规则“*”下满足结合律，即对任 ，有（4）

33、非空集合和数域在运算规则“”和“*”下满足分配律，即对任 ，有 则称非空集合 为 上的线性空间。2010 Copyright 62SCUT DT&P Labs第8章 差错控制编码 线性分组码的代数基础(续) 线性分组码与线性空间 线性分组码的码字是定义在有限域上的线性空间中的元素。 码字 码字 的“+”运算定义为 系数的“*”运算定义为 在本章中，均假定2010 Copyright 63SCUT DT&P Labs第8章 差错控制编码 线性分组码的代数基础(续) 定义8.5.13 在n维的线性空间 中，若某非空子集 满足线性空间的条件，则称 为线性空间的子空间。 子空间的基本性质（1）子空间

34、在“”运算规则下满足封闭性，即对任意的 ，有 （2）子空间 在“”运算规则下满足交换律 （3）子空间 满足结合律，即对任意2010 Copyright 64SCUT DT&P Labs第8章 差错控制编码 线性分组码的代数基础(续) 子空间的基本性质（4）恒等元 一定在子空间 中: （5）若 ，则其逆元素 一定在子空间 中，即有 （6）子空间 在“*”运算规则下满足封闭性，即若 则 （7）子空间 在“*”运算规则下满足结合律，即若 则（8）子空间 在“”运算规则和“*”运算规则下，满足分配律，即若 ,则 2010 Copyright 65SCUT DT&P Labs8.6 线性分组码的基本性质

35、 2010 Copyright 66SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质 线性分组码编码的一般表达形式 输入信息码组 输出编码码字 其中 线性分组码的一般记法： 其中k表示码字中信息位的个数，n为码字的长度。 线性分组码 中许用码字的个数为 。2010 Copyright 67SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 许用码字间的距离码距 定义8.6.1 两个n元的码字： 与 两者间的汉明距离定义为 有关码距的性质（1）自反性：任一码字 与其自身间的码距为零。（2）对称性：对任两码字 与 ， 与 间的码距与 与 间的码距相等

36、 （3）三角不等式成立：对任意的三个码字 、 和 ，它们间的码距关系满足 2010 Copyright 68SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 码距与码的检错纠错能力之间的关系 码字间的最小距离：最小码距定义为 线性分组码的基本性质 性质1 若要线性分组码能够检测出任一码字中的小于等于 位的误码，则应满足 2010 Copyright 69SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 性质2 若要线性分组码能够检出并纠正任一码字中的小于等于 位的误码，则应满足 性质3 若要线性分组码能够检出任一码字中的 位误码，同时能够

37、纠正其中 ( )位的误码，则应满足 2010 Copyright 70SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 线性分组码的生成矩阵与监督矩阵 差错控制编码一般可表示为 特别地，对线性分组码 表示为矩阵形式2010 Copyright 71SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 生成矩阵 生成矩阵定义为 系统码的生成矩阵 系统码的特点 系统码的编码输出结构 信息位部份 监督位部份2010 Copyright 72SCUT DT&P Labs 线性分组码的基本性质(续) 由 可得生成矩阵 若系统码结构为 生成矩阵相应地为第

38、8章 差错控制编码2010 Copyright 73SCUT DT&P Labs 线性分组码的基本性质(续) 监督矩阵 在线性分组码的码生成方程组中的监督位为 因为 因此可得第8章 差错控制编码2010 Copyright 74SCUT DT&P Labs 线性分组码的基本性质(续) 方程的矩阵形式 定义监督矩阵为 监督矩阵确定了码字没有错误的必要条件。第8章 差错控制编码2010 Copyright 75SCUT DT&P Labs 线性分组码的基本性质(续) 错误图样：描述错误及位置的一个矢量。 对于定义在二元域上的码字，知道了错误的位置等效于知道了错误。 若将 看作一特殊的错误图样 接收

39、码字可一般地表示为： 若没有出错，显然有第8章 差错控制编码2010 Copyright 76SCUT DT&P Labs 线性分组码的基本性质(续) 伴随式(校正子) 因为 定义伴随式为 伴随式是一个 维的向量，总共有 种不同的组合。 个不同的伴随式可对应 种不同错误图样。 伴随式只与错误图样和监督矩阵有关。 若 则接收码字 中一定出现了错误； 若 如果错误图样是一个许用码字，在错误不能被检测出； 如何错误图样不是一个许用图样，则可检测出该错误。第8章 差错控制编码2010 Copyright 77SCUT DT&P Labs 线性分组码的基本性质(续) 示例：构建一个可纠正一位误码、具有系

40、统码结构的（7，4）线性分组码。 解：该码的码字长度n7，信息位k4，监督位有nk3位 伴随式共有 刚好可对于无误码，不同位置的7种1比特误码共8种状态 设建立伴随式与误码的对应关系第8章 差错控制编码2010 Copyright 78SCUT DT&P Labs 线性分组码的基本性质(续) 当仅出现一位误码时，有如下关系 若没有误码： 应使得 因为错误的比特实际上并不能够单独提出进行伴随式的计算 因此编码时应保证 (*)第8章 差错控制编码2010 Copyright 79SCUT DT&P Labs 线性分组码的基本性质(续) 对于系统码结构的分组码， 已由输入信息位决定 因此应选择监督位

41、， ，使得上述关系式成立，即 由上面的(*)式可得监督方程第8章 差错控制编码2010 Copyright 80SCUT DT&P Labs 线性分组码的基本性质(续) 相应地监督矩阵为 由监督矩阵与生成矩阵的关系式，可得生成矩阵 注意：线性分组码中伴随式与误码的对应关系并非可任意设定 纠错编码监督矩阵和生成矩阵更一般的求解方法将在稍后讨论。第8章 差错控制编码2010 Copyright 81SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 生成矩阵与监督矩阵的有关性质 系统码结构的生成矩阵与监督矩阵结构 2010 Copyright 82SCUT DT&P La

42、bs第8章 差错控制编码 线性分组码的基本性质(续) 主要性质（1）生成矩阵G中的每一行都是一个许用码字； 因为 若取 即有 因而有上述结论。2010 Copyright 83SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续)（2）生成矩阵G的秩等于k，生成矩阵中的个独立的行向量码字构成码字子空间的一组基； 因为G中的行向量 因此任一码字可表示为 由此可得上述结论。2010 Copyright 84SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) （3）生成矩阵G和监督矩阵H满足如下的关系 因为 因此有 由此可得上述结论。2010 Copy

43、right 85SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 线性分组码的最小码距与最小码重的关系 定义8.6.2 线性分组码每个码字中“1”的码元的个数定义为该码字的重量，简称为码重；码字集中码重最小的码字的重量定义为最小码重。 定理8.6.3 线性分组码的最小码距等于其非零码字的最小码重。 记码字 码重 因为 码字间距离 因此有2010 Copyright 86SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 示例：已知某线性分组码的生成矩阵 (1)分析该码的差错控制能力。该分组码所有可能的码字 直接观测可得最小码重为3，由此可得

44、最小码距3； 该码若用于检错，可检出2位误码； 该码若用于纠错，可纠正1位误码。2010 Copyright 87SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) (2)求监督矩阵 由监督矩阵与生成矩阵间的关系 可得监督矩阵2010 Copyright 88SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) (3)1位误码与伴随式之间的关系，1位误码的所有图样 可得 归纳可得2010 Copyright 89SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) (4)纠错能力分析 a、假定只出现1位误码，若收到码字

45、计算伴随式 查表可知该伴随式对应错误图样 纠错 获得正确的码字 。2010 Copyright 90SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) b、假定出现2位误码，例如收到码字 该码字由许用码字 出现2位误码得到。 计算伴随式 查表可知该伴随式对应错误图样 纠错操作 并不能获得正确的码字。2010 Copyright 91SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 出现2位误码时伴随式的计算结果可分解为 与出现错误图样 所得的伴随式相同。 应为该伴随式已经用于对应1位误码 的错误图样，因而不能纠正该2位误码。 两位误码已经超

46、出了该分组码的纠错能力范围。2010 Copyright 92SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 线性分组码的标准阵、陪集首和陪集 线性分组码 具有 个不同的伴随式，除全零的图样 外，可分别对应 种不同的错误图样： 这 种错误图样与伴随式建立的确定的对应关系，是所有可纠正的错误图样。 许用码字 与 的任意组合 ，均可正确译码2010 Copyright 93SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 所有可正确译码的接收码字可用如下的矩阵表示 该矩阵称为线性分组码 的标准阵。 标准阵中第一列的每个元素称为一个陪集首 标

47、准阵的每一行为该行陪集首所对应的陪集 2010 Copyright 94SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 综上， 对于标准阵中的陪集首，有特定的伴随式与其对应 一般地，记接收码字为 若 则 若2010 Copyright 95SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 示例：分析生成矩阵如下的 线性分组码的标准阵等特性 由生成矩阵可得许用码字集为 确定可纠错的误码图样 可纠正的错误图样的选择： (1)具有不同伴随式的图样； (2)通常正常工作的通信系统误码出现少的概率较大，选择可纠正的错误图样通常从1比特的错误图样开

48、始。2010 Copyright 96SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 标准阵 错误图样与 伴随式的关系2010 Copyright 97SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 汉明码 定义8.6.4 如果线性分组码 满足码字长度 ，信息位 的参数条件，则称这种码为汉明码。 汉明码的编码效率所以当码字足够长时，汉明码是一种高效码。 汉明码的纠错能力分析 汉明码码字长度 信息位长度 监督位长度 伴随式个数 2010 Copyright 98SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续)

49、 其中全零的伴随式用于对应无误码的状态 其余的 个伴随式可分别对应 种错误图样。 因为合理的通信系统设计应使得一个码字中误码位数少的概率大于误码位数大的概率。 因此伴随式应用于对应误码位数少的错误图样。 汉明码长度为 。汉明码的非零伴随式全部用于对应1位误码，所以汉明码能纠正所有的1位误码。2010 Copyright 99SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 系统码结构的汉明码的构建 监督矩阵共有n列，其中第i列对应码字第i位错误图样的伴随式，系统码结构的监督矩阵右侧的子阵必须是一个单位阵。 监督矩阵的n个不同组合的列除了构成单位阵的 列外，其余的k列

50、可任意的排列。 确定监督矩阵之后，可得生成矩阵如下2010 Copyright 100SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 示例：设计一个 的汉明码 构建监督矩阵 由此可得2010 Copyright 101SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 可得生成矩阵2010 Copyright 102SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 扩展汉明码 已知普通汉明码可纠正所有1位误码，所以最小码距 当同时出现第 i 位和第 j 两位不同的误码时，有 因为 已经用于对应第 k 位误码的伴

51、随式，因此该伴随式用于纠错时将产生错误。即两位或两位以上误码无法发现，因此 综合上面有关最小码距的关系式，且码距必须为整数，因此2010 Copyright 103SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 扩展汉明码可通过增加1位编码的监督位长度，使得该码可以纠正任意的1位错误，同时发现任意的2位错误。 扩展汉明码的监督矩阵 其中 是原来普通汉明码的监督矩阵。2010 Copyright 104SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 扩展汉明码码字 其中原汉明码码字 新增监督位 当无误码时 扩展汉明码的伴随式仍然为零向量

52、。 2010 Copyright 105SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 当出现任意的1位，如第 j 位误码时 伴随式等于监督矩阵的第 j 列，可发现出错并可纠正。2010 Copyright 106SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 若第 i 和 j 位同时出错，伴随式 其中的最后1位为零。由此可判断出现了2位错误。 扩展汉明码通过增加1位监督为，使得码字间的最小距离2010 Copyright 107SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 线性分组码的纠错能力分析 汉

53、明界：汉明界确定了一个参数为 的线性分组码可能获得的最大纠错能力。有关汉明界有如下的定理： 定理8.6.5 线性分组码 能够纠正码字中任意的小于等于 位误码的图样数小于 。 若符号 表示所有的 个元素中取 个的组合数。 长度为 的码字中任意的小于等于 位错误的图样数为 线性分组码 不同的伴随式的个数为 ，要保证每个不同的错误图样有不同的伴随式与其对应，应有 因而有上述结论。2010 Copyright 108SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 定义8.6.6 若能够纠正 个及个以下的全部错误的线性分组码满足条件 则称这种线性分组码为完备码。 汉明码是一

54、种完备码。 普洛特金界：普洛特金界确定了线性分组码 差错控制能力的上限。 定理8.6.6 线性分组码 的最小码距 小于由下式确定的所谓的普洛特金界 2010 Copyright 109SCUT DT&P Labs第8章 差错控制编码 线性分组码的基本性质(续) 示例 (1)判断线性分组码 有无纠正2位误码的可能性； (2)判断线性分组码 有无纠正2位误码的可能性。 分析 (1)对于线性分组码 ，因为 所以不可能构建能够纠正2位错误的分组码； (2)对于线性分组码 ，因为 因此有可能可以构建能够纠正2位错误的分组码。2010 Copyright 110SCUT DT&P Labs8.7 循环码2

55、010 Copyright 111SCUT DT&P Labs 循环码 循环码是线性分组码的一个重要子类。 循环码为我们根据纠错的要求进行编码参数的设计和结构的实现提供了一种系统的方法。 定义 8.7.1 记 为线性分组码的码字集，如果对任意的 ， 循环左移或循环右移任意位后得到的码字 ，仍有 ，则称该线性分组码为循环码。 码多项式 码字与多项式可建立如下的对应关系，相应的多项式称之。 码多项式系数的加乘运算规则 加运算 乘运算 第8章 差错控制编码2010 Copyright 112SCUT DT&P Labs 循环码(续) 整数域中的同余类 在整数除法中，取定整数除数n，将所有整数m按除以

56、所得的余数进行分类，余数相同的整数归为一类，称为关于n的同余类 Q与p均为整数。关于n的同余类记为 多项式域中的同余类 同理可定义关于 多项式的同余类 记为第8章 差错控制编码2010 Copyright 113SCUT DT&P Labs 循环码(续) 示例：多项式 关于多项式 因为 即两者的余式相同。第8章 差错控制编码2010 Copyright 114SCUT DT&P Labs 循环码(续) 循环码的代数结构(有关循环码的主要定理) 定理 8.7.2 若 是长度为n的循环码中的一个码多项式，i为不等于零的整数，则 按模 运算的余式必为循环码中的另一码多项式。 定理 8.7.3 在循环

57、码 中，幂次数为 ，且其常数项不等于“0”的码字多项式有一个且只有一个。 因为多项式 的幂均小于n，由上述两个定理，可知这些多项式均为码多项式。第8章 差错控制编码2010 Copyright 115SCUT DT&P Labs第8章 差错控制编码 循环码(续) 由 可知矩阵g中的每一行均为一个码字。 因为矩阵g的秩为k，可知相应的k个码字互不相关，因此可以构成相应的码字空间的一组基。 因此可定义相应的码多项式生成矩阵2010 Copyright 116SCUT DT&P Labs 循环码(续) 相应地可定义码的生成多项式 给定信息码组 ，由码多项式生成矩阵，可得相应的码多项式为第8章 差错控

58、制编码2010 Copyright 117SCUT DT&P Labs 循环码(续) 定理 8.7.4 在循环码中，所有的码多项式 都可以被生成多项式 整除。 因为 所以定理的结论。 推论 8.7.5 次数不大于 次的任何多项式与生成多项式 的乘积都为码多项式。 有上式很容易看出结论成立。 定理 8.7.6 循环码的生成多项式 是多项式 的一个因式。 第8章 差错控制编码2010 Copyright 118SCUT DT&P Labs 循环码(续) 由定理8.7.3，定理8.7.6，可归纳判断生成多项式的充要条件 （1） 是一个 次的多项式； （2） 的常数项不等于0； （3） 是 的一个因式

59、。 定义 8.7.7 定义式 为循环码的一致校验多项式。 因为码多项式可以表示为 因此有 由此，可利用一致校验多项式对接收的码字进行差错校验。第8章 差错控制编码2010 Copyright 119SCUT DT&P Labs 循环码(续) 示例：分析多项式 能否作为循环码 的生成多项式。 因为 且其幂 及常数项不为零，所以可作为 的生成多项式。 所得到的循环码的生成矩阵 输入信息位 编码输出 是一种非系统码的编码方式。第8章 差错控制编码2010 Copyright 120SCUT DT&P Labs 循环码(续) 系统码结构的循环码 输入信息位与对应的多项式 由 可得 整理后可得 取编码输

60、出 根据推论 8.7.5，且该多项式对应的码字具有系统码结构 因此该码为系统码结构的循环码。第8章 差错控制编码2010 Copyright 121SCUT DT&P Labs 循环码(续) 示例：已知循环码 的生成多项式 输入信息码组 求系统码编码输出。 由 可得 码字多项式为 或 系统码编码输出第8章 差错控制编码2010 Copyright 122SCUT DT&P Labs 循环码(续) 系统码结构的循环码的生成矩阵和监督矩阵 已知系统码结构的线性分组码生成矩阵为 系统码结构的循环码码多项式的一般形式 根据生成矩阵每一行对应相应一个特殊码字的特点 分别取 计算 可得 由此可导出系统码结