九乡新闻网脑男男主:8.3 线性分组码
来源：百度文库 编辑：九乡新闻网 时间：2024/04/29 14:01:27
本节知识要点：
分组码 线性分组码 线性分组码的性质 线性分组码的构造
监督矩阵H 生成矩阵G 校验子 汉明码
8.3.1 基本概念
对于长度为 n 的二进制线性分组码，它有
种可能的码组，从种码组中，可以选择 M =
个码组（ k
线性分组码是建立在代数群论基础之上的，各许用码的集合构成了代数学中的群，它们的主要性质如下：
（1）任意两许用码之和（对于二进制码这个和的含义是模二和）仍为一许用码，也就是说，线性分组码具有封闭性；
（2）码组间的最小码距等于非零码的最小码重。
在8.2.1节中介绍的奇偶监督码，就是一种最简单的线性分组码，由于只有一位监督位通常可以表示为（ n, n- 1），式（8-5）表示采用偶校验时的监督关系。在接收端解码时，实际上就是在计算：
（8-6）
其中，
…
表示接收到的信息位，
表示接收到的监督位，若 S ＝0，就认为无错；若 S ＝1就认为有错。式（8-6）被称为监督关系式， S 是校正子。由于校正子 S 的取值只有“0”和“1”两种状态，因此，它只能表示有错和无错这两种信息，而不能指出错码的位置。
设想如果监督位增加一位，即变成两位，则能增加一个类似于式（8-6）的监督关系式，计算出两个校正子
和
， 而共有4种组合：00，01，10，11，可以表示4种不同的信息。除了用00表示无错以外，其余3种状态就可用于指示3种不同的误码图样。
同理，由 r 个监督方程式计算得到的校正子有 r 位，可以用来指示
-1种误码图样。对于一位误码来说，就可以指示-1个误码位置。对于码组长度为 n 、信息码元为 k 位、监督码元为 r ＝ n - k 位的分组码（常记作（ n ， k ）码），如果希望用 r 个监督位构造出 r 个监督关系式来指示一位错码的 n 种可能，则要求：
（8-7)
下面通过一个例子来说明线性分组码是如何构造的。设分组码（ n , k ）中k = 4，为了能够纠正一位错误，由式（8-7）可以看到，要求 r ≥ 3，若取 r = 3，则 n = k+r = 7。因此，可以用
表示这7个码元，用
、、表示利用三个监督方程，通过计算得到的校正子，并且假设、、三位校正字码组与误码位置的关系如表8-4（当然，也可以规定成另一种对应关系，这并不影响讨论的一般性）：
由表中规定可已看到，仅当一错码位置在
时，校正子为1；否则为0。这就意味着
四个码元构成偶数监督关系：
(8-8a）
同理，
构成偶数监督关系：
（8-8b）
表8-4校正字与误码位置
S 1 S 2 S 3
误码位置
S 1 S 2 S 3
误码位置
001
010
100
011
a 0
a 1
a 2
a 3
101
110
111
000
a 4
a 5
a 6
无错
以及
构成有数监督关系：
（8-8c）
在发送端编码时
是信息码元，它们的值取决于输入信号，因此是随机的。
是监督码元，它们的取值由监督关系来确定，即监督位应使式（8-8）的三个表达式中的、和的值为零（表示编成的码组中应无错码），这样式（8-8）的三个表达式可以表示成下面的方程组形式：
（8-9）
由上式经移项运算，接出监督位
（8-10）
根据上面两个线性关系，可以得到16个许用码组如表8-5所示：
表8-5许用码组
信息位
监督位
信息位
监督位
信息位
监督位
信息位
监督位
a 6 a 5 a 4 a 3
a 2 a 1 a 0
a 6 a 5 a 4 a 3
a 2 a 1 a 0
a 6 a 5 a 4 a 3
a 2 a 1 a 0
a 6 a 5 a 4 a 3
a 2 a 1 a 0
0000
0001
0010
0011
000
011
101
110
0100
0101
0100
0111
110
101
011
000
1000
1001
1010
1011
111
100
010
001
1100
1101
1100
1111
001
010
100
111
接收端收到每个码组后，计算出、和，如不全为0，则可按表8-4确定误码的位置，然后予以纠正。例如，接收码组为0000011，可算出＝011，由表8-4可知在
位置上有一误码。
不难看出，上述（7，4）码的最小码距
，因此，它能纠正一个误码或检测两个误码。如超出纠错能力，则反而会因“乱纠”而增加新的误码。
8.3.2 监督矩阵 H 和生成矩阵 G
式（8-9）所述（7，4）码的三个监督方程式可以重新改写为如下形式：
（8-11）
对于式（8-11）可以用矩阵形式来表示：
（8-12）
上式可以记作：
或
，其中
（8-13a）
（8-13b）
（8-13c）
通常 H 称为监督矩阵， A 称为信道编码得到的码字。在这个例子中 H 为r×n阶矩阵， P 为r×k阶矩阵， I r为r×r阶单位矩阵，具有这种特性的 H 矩阵称为典型监督矩阵，这是一种较为简单的信道编译码方式。典型形式的监督矩阵各行是线性无关的，非典型形式的监督矩阵可以经过行或列的运算化为典型形式。
对于式（8-10）也可以用矩阵形式来表示：
或者
（8-14）
比较式（8-13a）和式（8-14）可以看到
，如果在 Q 矩阵的左边在加上一个k×k的单位矩阵，就形成了一个新矩阵 G ：
（8-15）
这里 G 称为生成矩阵，利用它可以产生整个码组
（8-16）
由式（8-15）表示的生成矩阵形式称为典型生成矩阵，利用式（8-16）产生的分组码必为系统码，也就是信息码元保持不变，监督码元附加在其后。
8.3.3 校验子 S
在发送端信息码元 M 利用式（8-16），实现信道编码，产生线性分组码 A ；在传输过程中有可能出现误码，设接收到的码组为 B 。则收发码组之差为：
（8-17）
这里
，
，表示 i 位有错，
，表示 i 位无错。基于这样的原则接收端利用接收到的码组 B 计算校正子：
（8-18）
因此，校正子仅与 E 有关，即错误图样与校正子之间有确定的关系。
对于上述（7，4）码，校正子S与错误图样的对应关系可由式（8-18）求得，其计算结果见表8-6所示。在接收端的译码器中有专门的校正子计算电路，从而实现检错和纠错。
表8-6（7，4）码校正子与错误图样的对应关系
序号
错误码位
E
S
e 6 e 5 e 4 e 3 e 2 e 1 e 0
S 3 S 2 S 1
0
1
2
3
4
5
6
7
/
b0
b1
b2
b3
b4
b5
b6
0 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 1 0
0 0 0 0 1 0 0
0 0 0 1 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0
0 0 1
0 1 0
1 0 0
0 1 1
1 0 1
1 1 0
1 1 1
8.3.4 汉明码
汉明码是一种能够纠正单个错误的线性分组码。它有以下特点：
（1）最小码距
，可以纠正一位错误；
（2）码长 n 与监督元个数 r 之间满足关系式：
。
如果要产生一个系统汉明码，可以将矩阵 H 转换成典型形式的监督矩阵，进一步利用 Q = P T的关系，得到相应的生成矩阵 G 。通常二进制汉明码可以表示为：
（8-19）
根据上述汉明码定义可以看到，8.3.1构造的（7，4）线性分组码实际上就是一个汉明码，它满足汉明码的两个特点。图8-5中给出（7，4）系统汉明码的编码器和译码器电路。
（a）发端编码器
（b）收端译编码器
图8-5 （7，4）汉明码的编译码器
分组码 线性分组码 线性分组码的性质 线性分组码的构造
监督矩阵H 生成矩阵G 校验子 汉明码
8.3.1 基本概念
对于长度为 n 的二进制线性分组码，它有
种可能的码组，从种码组中，可以选择 M =个码组（ k线性分组码是建立在代数群论基础之上的，各许用码的集合构成了代数学中的群，它们的主要性质如下：
（1）任意两许用码之和（对于二进制码这个和的含义是模二和）仍为一许用码，也就是说，线性分组码具有封闭性；
（2）码组间的最小码距等于非零码的最小码重。
在8.2.1节中介绍的奇偶监督码，就是一种最简单的线性分组码，由于只有一位监督位通常可以表示为（ n, n- 1），式（8-5）表示采用偶校验时的监督关系。在接收端解码时，实际上就是在计算：
（8-6）其中，
…表示接收到的信息位，表示接收到的监督位，若 S ＝0，就认为无错；若 S ＝1就认为有错。式（8-6）被称为监督关系式， S 是校正子。由于校正子 S 的取值只有“0”和“1”两种状态，因此，它只能表示有错和无错这两种信息，而不能指出错码的位置。设想如果监督位增加一位，即变成两位，则能增加一个类似于式（8-6）的监督关系式，计算出两个校正子
和， 而共有4种组合：00，01，10，11，可以表示4种不同的信息。除了用00表示无错以外，其余3种状态就可用于指示3种不同的误码图样。同理，由 r 个监督方程式计算得到的校正子有 r 位，可以用来指示
-1种误码图样。对于一位误码来说，就可以指示-1个误码位置。对于码组长度为 n 、信息码元为 k 位、监督码元为 r ＝ n - k 位的分组码（常记作（ n ， k ）码），如果希望用 r 个监督位构造出 r 个监督关系式来指示一位错码的 n 种可能，则要求： （8-7)下面通过一个例子来说明线性分组码是如何构造的。设分组码（ n , k ）中k = 4，为了能够纠正一位错误，由式（8-7）可以看到，要求 r ≥ 3，若取 r = 3，则 n = k+r = 7。因此，可以用
表示这7个码元，用、、表示利用三个监督方程，通过计算得到的校正子，并且假设、、三位校正字码组与误码位置的关系如表8-4（当然，也可以规定成另一种对应关系，这并不影响讨论的一般性）：由表中规定可已看到，仅当一错码位置在
时，校正子为1；否则为0。这就意味着四个码元构成偶数监督关系： (8-8a）同理，
构成偶数监督关系： （8-8b）表8-4校正字与误码位置
S 1 S 2 S 3
误码位置
S 1 S 2 S 3
误码位置
001
010
100
011
a 0
a 1
a 2
a 3
101
110
111
000
a 4
a 5
a 6
无错
以及
构成有数监督关系： （8-8c）在发送端编码时
是信息码元，它们的值取决于输入信号，因此是随机的。是监督码元，它们的取值由监督关系来确定，即监督位应使式（8-8）的三个表达式中的、和的值为零（表示编成的码组中应无错码），这样式（8-8）的三个表达式可以表示成下面的方程组形式： （8-9）由上式经移项运算，接出监督位
（8-10）根据上面两个线性关系，可以得到16个许用码组如表8-5所示：
表8-5许用码组
信息位
监督位
信息位
监督位
信息位
监督位
信息位
监督位
a 6 a 5 a 4 a 3
a 2 a 1 a 0
a 6 a 5 a 4 a 3
a 2 a 1 a 0
a 6 a 5 a 4 a 3
a 2 a 1 a 0
a 6 a 5 a 4 a 3
a 2 a 1 a 0
0000
0001
0010
0011
000
011
101
110
0100
0101
0100
0111
110
101
011
000
1000
1001
1010
1011
111
100
010
001
1100
1101
1100
1111
001
010
100
111
接收端收到每个码组后，计算出
、和，如不全为0，则可按表8-4确定误码的位置，然后予以纠正。例如，接收码组为0000011，可算出＝011，由表8-4可知在位置上有一误码。不难看出，上述（7，4）码的最小码距
，因此，它能纠正一个误码或检测两个误码。如超出纠错能力，则反而会因“乱纠”而增加新的误码。8.3.2 监督矩阵 H 和生成矩阵 G
式（8-9）所述（7，4）码的三个监督方程式可以重新改写为如下形式：
（8-11）对于式（8-11）可以用矩阵形式来表示：
（8-12）上式可以记作：
或，其中 （8-13a） （8-13b） （8-13c）通常 H 称为监督矩阵， A 称为信道编码得到的码字。在这个例子中 H 为r×n阶矩阵， P 为r×k阶矩阵， I r为r×r阶单位矩阵，具有这种特性的 H 矩阵称为典型监督矩阵，这是一种较为简单的信道编译码方式。典型形式的监督矩阵各行是线性无关的，非典型形式的监督矩阵可以经过行或列的运算化为典型形式。
对于式（8-10）也可以用矩阵形式来表示：
或者
（8-14）比较式（8-13a）和式（8-14）可以看到
，如果在 Q 矩阵的左边在加上一个k×k的单位矩阵，就形成了一个新矩阵 G ： （8-15）这里 G 称为生成矩阵，利用它可以产生整个码组
（8-16）由式（8-15）表示的生成矩阵形式称为典型生成矩阵，利用式（8-16）产生的分组码必为系统码，也就是信息码元保持不变，监督码元附加在其后。
8.3.3 校验子 S
在发送端信息码元 M 利用式（8-16），实现信道编码，产生线性分组码 A ；在传输过程中有可能出现误码，设接收到的码组为 B 。则收发码组之差为：
（8-17）这里
，，表示 i 位有错，，表示 i 位无错。基于这样的原则接收端利用接收到的码组 B 计算校正子： （8-18）因此，校正子仅与 E 有关，即错误图样与校正子之间有确定的关系。
对于上述（7，4）码，校正子S与错误图样的对应关系可由式（8-18）求得，其计算结果见表8-6所示。在接收端的译码器中有专门的校正子计算电路，从而实现检错和纠错。
表8-6（7，4）码校正子与错误图样的对应关系
序号
错误码位
E
S
e 6 e 5 e 4 e 3 e 2 e 1 e 0
S 3 S 2 S 1
0
1
2
3
4
5
6
7
/
b0
b1
b2
b3
b4
b5
b6
0 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 1 0
0 0 0 0 1 0 0
0 0 0 1 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0
0 0 1
0 1 0
1 0 0
0 1 1
1 0 1
1 1 0
1 1 1
8.3.4 汉明码
汉明码是一种能够纠正单个错误的线性分组码。它有以下特点：
（1）最小码距
，可以纠正一位错误；（2）码长 n 与监督元个数 r 之间满足关系式：
。如果要产生一个系统汉明码，可以将矩阵 H 转换成典型形式的监督矩阵，进一步利用 Q = P T的关系，得到相应的生成矩阵 G 。通常二进制汉明码可以表示为：
（8-19）根据上述汉明码定义可以看到，8.3.1构造的（7，4）线性分组码实际上就是一个汉明码，它满足汉明码的两个特点。图8-5中给出（7，4）系统汉明码的编码器和译码器电路。
（a）发端编码器
（b）收端译编码器
图8-5 （7，4）汉明码的编译码器
8.3 线性分组码
线性思维
线性官僚组织
电视节目线性与非线性编辑
什么是线性畸变
均线性买卖
三线性极线和三线性极点 | 数学
自由度系统的线性振动
什么是单线性相关分析 -
线性思维---方圆极点教育
函数与线性回归分析
物理地址与线性地址详解
50 1.8 的 焦外二线性
物理内存与线性地址的关系
[通达信] 线性回归预则指(注释版)
线性历史观的终结-周口论文网
线性光耦与非线性光耦
三端可调线性集成稳压器
[通达信] 线性回归预则指标(注释
转：线性回归（有助于理解REGRESS）
线性元件和非线性元件的区别
使用eviews做线性回归分析
线性链表的应用----箱排序和基数排序
用线性加深工具拉出漂亮的虚化背景