信息论基础——线性分组码

背景
在通信中，由于信息码元序列是一种随机序列，接收端无法预知码元的取值，也无法识别其中有无错码。所 以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元（校验元）。这些监督码元和信息 码元之间有确定的关系。
在信息码元序列中加监督码元就称为差错控制编码，差错控制编码属于信道编码。
信息码元和监督码元之间有一种关系，关系不同，形成的码类型也不同。可分为两大类：分组码和卷积码。 其中，分组码是把信息码元序列以每k个码元分组，编码器将每个信息组按照一定规律产生r个多余的码元（称为 校验元），形成一个长为n=k+r的码字。
感谢观看

校验矩阵H
这也表示由G的行矢量所扩张成的k维子空间与H矩阵行矢量所扩张成的r维子空间是正交的。
G与H中只要有一个确定，另一个就是可以确定的。只要校验矩阵给订=定，校验码元和信息码元之间的关系 就完全确定了。
举例
下面是一个（7,3）线性分组码，有信息组(m2m1m0),信息组在码字的前部，即： 生成矩阵为 信息组和对应的码字由表3.1给出。 则其校验矩阵为
基本概念
当分组码的信息码元与监督码元之间的关系为线性关系时（用线性方程组），这种分组码就称为线性分组码。 包括汉明码和循环码。
对于长度为n的二进制线性分组码，它有种可能的码字，从中可以选择M=个码字（k<n）组成一种编码，其中 码字称为许用码字，其余码字称为禁用码字。这样，一个k比特信息可以映射到一个长度为n的码组中，该码字是 从M个码字构成的码字集合中选出来的，剩下的码字即可以对这个分组码进行检错或纠错。
在线性分组码中，两个码字对应位上数字不同的位数称为码字距离，简称距离，又称汉明距离。 编码中各个码字间距离的最小值称为最小码距d，最小码距是衡量码组检错和纠错能力的依据，其关系如下： （1）为了检测e个错码，则要求最小码距d>e+1; （2）为了纠正t个错码，则要求最小码距d>2t+1; （3）为了纠正t个错码，同时检测e个错码，则要求最小码距d>e+t+1,e>t。

举例：(7,4) 线性码的生成矩阵为：
1 0 0 0 1 0 1
G 47
0 0
1 0
0 1
0 0
1 1
1 1
1 0
0 0 0 1 0 1 1
若m14 (1010)， 则 ：
1 0 0 0 1 0 1
C17 m14G47 1
0
1
00
0
1 0
0 1
0 0
1 1
1 1
1 (1010011) 0
8.1 一般概念
(1) 线性分组码的编码：编码过程分为两步： 把信息序列按一定长度分成若干信息码组, 每组由 k 位
组成; 编码器按照预定的线性规则（可由线性方程组规定），
把信息码组变换成 n 重（n>k）码字，其中 (n－k) 个附 加码元是由信息码元的线性运算产生的。
(2) 线性分组码的码字数：信息码组长 k 位，有 2k 个不同 的信息码组，有 2k 个码字与它们一一对应。
H GS S I(Q kkQ r)T krIr
(7.3.6)
8.3 线性分组码的生成矩阵
(3) 生成矩阵与一致监督矩阵的关系
由于生成矩阵 G 的每一行都是一个码字，所以 G 的每行都满足：
Cm k1g1m k2g2 m 0gk
（ 8.3.1）
m iG(F 2)i,0,1, ,k1。 写 成 矩 阵 形 式 得 ：
g1
C1nmk1mk2,m0 g2m1kGkn
gk
(8.3.2)
mmk1mk2m0 ──待编码的信息组
G─ kn
─
是k一 n阶 个矩
阵
。
8.3 线性分组码的生成矩阵
在 k 个信息码元之后附加 r(r=n－k) 个监督码元，使每个监督元是其 中某些信息元的模 2 和。

个错误
2018/10/27
12
第六章 信道编码

6.2.6 线性分组码的译码
对纠两个错误的 (n,k) 线性码，必须能纠 误图样，所以 个错

依此类推，一个纠 t 个错误的 (n,k) 线性码必须满足

对于完备码，由码的纠错能力所确定的伴随式数恰好等于可纠 的错误图样数，所以完备码的 (n－k) 个监督码元得到了充分的 利用。
t

dmin dmin t t
t
图6.2.8 以码字为中心、半径t=INT [(dmin－1)/2]的差错控制球体示意图
2018/10/27 16
第六章 信道编码
6.2.6 线性分组码的译码

举例：对纠一个错误的 (7,4) 汉明码，
可见，(7,4)汉明码是一个完备码。

所有汉明码都是完备码（满足2n－k = 2m=n+1）。
第六章 信道编码
To choose time is to save time
2018/10/27 1
第六章 信道编码
6.2 线性分组码
一般概念 一致监督方程和一致监督矩阵 线性分组码的生成矩阵 线性分组码的编码 线性分组码的最小距离、检错和纠错能力 线性分组码的译码 线性分组码的性能 汉明码 由已知码构造新码的方法 线性分组码的码限

p(C)：发送码字C 的先验概率 p(C/R)：后验概率

若码字数为 2k，对充分随机的消息源有p(C)=1/ 2k，所以最小化的 pwe等价为最小化p(C’≠C│R )，又等价为最大化p(C’=C│R)；
3
2018/10/27
第六章 信道编码

6.2.6 线性分组码的译码

第3章 线性分组码
式中， m=(mn -1， mn -2， …， mn -k )是k 个信息元 组成的信息组。 因此， 若已知信息组 m ， 通过式 (3.2.9)可求得相应的码字， 称式(3.2.8)的G为 ［n ， k ， d］码的生成矩阵。
第3章 线性分组码
如表 3 - 1中的［7， 3， 4］码， 可从它的8个码
c0=c5+c4=0+1=1
由此得到的码字为： (1010011)。
第3章 线性分组码
可以检验例3.1中的［7， 3， 4］码的8个码字均满 足式(3.2.1)和式(3.2.2)。 若用矩阵形式表示这些线性方 程组， 则式(3.2.1)或式(3.2.2)可表示为：
1 1 1 0
C ,i
2
第3章 线性分组码
对所有i=0， 1， …， n -1， 则
(C1 ) c ,i
i 0
1
n 1
(C2 ) c ,i
i 0
2
n 1
(C1 C2 ) ( c ,i c ,i )
i 0
1 2
n 1
第3章 线性分组码
信息元求得r=n -k 个校验元。
第3章 线性分组码
这相当于建立一组线性方程组， 已知k 个系数，
要求n-k 个未知数， 使得到的码恰好有所要求的最小 距离d。 上例中的［7， 3， 4］码， 若c6， c5， c4代表3个 信息元， 则c3， c2， c1， c0 这 4 个校验元， 可由以下 线性方程组求得： 1·c3=1·c6+0·c5+1·c4 1·c2=1·c6+1·c5+1·c4
第3章 线性分组码

1 1 0 0 0 1 0 0 1 1 0 0 0 1
(8.2.3)
将式(8.2.2)可写成：
H ·CT=0T 或 C ·HT=0 CT、HT、0T 分别表示 C、 H、0 的转置矩阵。
17.07.2020
Department of Electronics and Information, NCUT Song Peng
c0 c5
c4
(8.2.1)
表 8.2.1 (7,3)分组码编码表
信息组 对应码字 000 0000000 001 0011101 010 0100111 011 0111010
c6 0 c4 c3 0 0 0 0
cc66
c5 c5
c4 0
0 0
c2 0 0 c1
0 0
0 0
0 c5 c4 0 0 0 c0 0
Department of Electronics andc0Infocr5mation, Nc4CUT Song Peng
第7页
8.2 一致监督方程和一致监督矩阵
(1) 一致监督方程
一致监督方程/一致校验方程：确定信息元得到监督元 规则的一组方程称为监督方程/校验方程。由于所有码 字都按同一规则确定，又称为一致监督方程/一致校验 方程。
100 101 110 111
1001110 1010011 1101001 1110100
返回目录
17.07.2020
Department of Electronics and Information, NCUT Song Peng
第9页
8.2 一致监督方程和一致监督矩阵
(3) 一致监督矩阵
为了运算方便，将式(7.2.1)监 督方程写成矩阵形式，得：

即: ( A1+A2 ) ·HT =0
所以 ( A1+A2 )也是一个许用码组.
由封闭性可知两个码组(A1、A2 )的码距必是另一码组 ( A1+A2 )的码重。
1 .2 汉明码
汉明码是一种能够纠正单个错误的线性分组码。它有 以下特点：
（1）最小码距dmin＝3，可纠正一位错误； （2）码长n与监督元个数r之间满足关系式：
1 1 1 0 1 0 0
0
1 1 0 1 0 1 0 a6 a5 a4 a3 a2 a1 a0 T 0
1 0 1 1 0 0 1
0
上式可以记作：HAT=0T或AHT=0 。
其中： 0 0 0 0
A a6 a5 a4 a3 a2 a1 a0
1 1 1 0 1 0 0
H 1 1 0 1 0 1 0 P Ir
E B A
其中பைடு நூலகம்=［en-1,en-2,…,e1,e0］，且：
ei
0
1
；当bi=ai ；当bi≠ai
式(10.6)也可写作
B AE
令S=BHT，称为伴随式或校正子。
S BHT (A E)HT EHT
因此，校正子仅与E有关，即错误图样与校正子之 间有确定的关系。如表10.4所示, 用于检错并能纠正一位 错码。
n 2r 1
通常二进制汉明码可以表示为：
n,k 2r 1 , 2r 1 r
（7，4）系统汉明码的编码器电路：
a6
a6
a5
a5
a4
a4
a3
a3
a2
a1
a0
（7，4）系统汉明码的译码器电路：
b6
a6
b5
a5

由上式经移项运算，解出监督位为
a2 a6 a5 a4 a1 a 6 a 5 a 3 a0 a6 a4 a3
已知信息位后，就可直接计算出监督位。由此得出16个许用码组 表4-5（7，4）汉明码的许用码组 信息码 a6a5a4a3 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 监督码 a2a1a0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 信息码 a6a5a4a3 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 监督码 a2a1a0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 1
§3.2 码的一致校验矩阵与生成矩阵
一、 码的校验矩阵与生成矩阵
– ［n ，k ，d］分组码的编码问题就是在n 维 线性空间Vn 中，如何找出满足一定要求的， 有2k 个矢量组成的k 维线性子空间Vn ，k 。 – 或者说， 在满足给定条件(码的最小距离d或 码率R)下， 如何从已知的k 个信息元求得r=n -k 个校验元。
• 二进制(5,3)码
– K位信息空间23
• • • • • • • • 000 001 010 011 100 101 110 111
n位编码空间25
00000 00100 01000 01100 10000 10100 11000 11100 00001 00101 01001 01101 10001 10101 11001 11101 00010 00110 01010 01110 10010 10110 11010 11110 00011 00111 01011 01111 10011 10111 11011 11111

2r 1 n 或 2r k r 1
设分组码 (n, k) 中k = 4，为了纠正1位错码，监 督位需要多少位？
2r k r 1
监督位数 r 3 若取 r = 3，则n = k + r = 7
码组：（a6 a5 a4 a3 a2 a1 线性分组码的一般原理
线性分组码的构造
H矩阵
a 6 a 5 a 4 a 2 0 上面(7, 4)汉明码的例子有 a6 a5 a3 a1 0 a a a a 0 4 3 0 6
1 a 6 1 a5 1 a 4 0 a3 1 a 2 0 a1 0 a 0 0 改写为 1 a 6 1 a5 0 a 4 1 a3 0 a 2 1 a1 0 a 0 0 1 a 6 0 a5 1 a 4 1 a3 0 a 2 0 a1 1 a 0 0
S1 S2 S3 001
010 100 011
假设校正子与错码位置的对应关系如表规定(也可以另外规定) 。 错码位置 a0
a1 a2 a3
S1 S2 S3 101
110 111 000
错码位置 a4
a5 a6 无错码
仅当一位错码在a2 、a4、a5或a6时，校正子S1为1, 偶数监督关系 S1 a6 a5 a4 a2
S2 a6 a5 a3 a1 a1、a3、a5和a6构成偶数监督关系： a0、a3、a4和a6构成偶数监督关系： S3 a6 a4 a3 a0
监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即 监督位应使S1、S2和S3的值为0:
a 6 a 5 a 4 a 2 0 a6 a5 a3 a1 0 a a a a 0 4 3 0 6

10.3 线性分组码10.3.1 线性分组码的基本概念1. 线性分组码及其描述方法()k n ,线性分组码是把信息码元序列的每k 个码元(Symbol)分成一组，通过线性变换，映射成由n 个码元组成的码组，且每一码组仅与本码组的k 个信息位有关，与其他码组的信息无关。

对于线性分组码，码组中任一码元都是信息码元的线性组合。

例10.3.1 设某（7，4）二进制线性分组码编码器的输入信息组（又称信息段）是m ()0123m m m m =,编码输出是A ()0123456a a a a a a a =，已知输入、输出码元之间的关系式是36m a =，25m a =，14m a =，03m a =，1232m m m a ++=，0231m m m a ++=，0130m m m a ++=，这里，“+”指模二加。

求编码时“码组到信息”间的映射关系以及输出码组集合。

解 将题中所给输入、输出码元之间的线性变换关系用线性方程组描述如下：⎪⎩⎪⎨⎧++=++=++=⎪⎪⎩⎪⎪⎨⎧====o o oomm m a m m m a m m m a m a m a m a m a 1323112323142536监督位信息位 （10.3.1） 还可以将式（10.3.1）改写成矩阵形式： A []⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=00010110010101010011010001110123m m m m （模2加） = m G （10.3.2） 分别令信息组()0123m m m m 为（0000），（0001），…，（1111），代入上面的矩阵算式，不难算得各信息组对应的码组，列于表10.3.1 。

2. 线性分组码性质表10.3.1 反映出线性分组码所具备的基本性质：(1) 一个()k n ,线性分组码共有k 2个许用码组；(2) 对加法满足封闭性，即线性分组码中任意两个码组之和（模二加）仍是分组码中的一个码组；(3) 全零码是线性分组码中的一个码组；(4) 线性分组码各码组之间的最小码距，等于除全零码外的码组的最小重量。

的每一行都是一个码字， 由于生成矩阵G的每一行都是一个码字，所以G 的每 行都满足Hr×nCTn×1=0Tr×1，则有 × × 0 × Hr×nGTn×k=0Tr×k 或 Gk×nHTn×r=0k×r × × 0 × × × 0 线性系统码的监督矩阵 H 和生成矩阵 G 之间可以直接 互换。 互换。
2012/4/14
电信学院 汪汉新
17/58
G中每一行 gi=(gi1,gi2,…, gin ) 都是一个码字； 都是一个码字； 对每一个信息组m，由矩阵G都可以求得 (n,k)
线性码对应的码字。 线性码对应的码字。 生成矩阵： 线性码， 生成矩阵：由于矩阵 G 生成了 (n,k) 线性码， 线性码的生成矩阵。 称矩阵 G 为 (n,k) 线性码的生成矩阵。
2012/4/14 电信学院 汪汉新
011 100 101 110 111
一致监督矩阵： 一致监督矩阵：
将监督方程写成矩阵 形式， 形式，得：
H CT=0T或 0 C HT=0 0 CT、HT、0T分别表 示C、H、0的转置
矩阵。 矩阵。
2012/4/14 10/58
电信学院 汪汉新
系数矩阵 H 的后四列组成一个 (4×4) 阶单位子阵，用 I4 × 阶单位子阵， 表示， 表示，H 的其余部分用 P 表示
2012/4/14
电信学院 汪汉新
18/58
线性系统分组码: 线性系统分组码
通过行初等变换， 列是单位子阵的标准 通过行初等变换，将 G 化为前 k 列是单位子阵的标准 形式
2012/4/14
电信学院 汪汉新
19/58
线性系统分组码： 线性系统分组码：用标准生成矩阵 Gk×n 编成的码字， × 编成的码字， 位为信息数字， 前面 k 位为信息数字，后面 r=n－k 位为校验字，这种 － 位为校验字， 信息数字在前校验数字在后的线性分组码称为线性系 统分组码。 统分组码。

一、 线性分组码的基本原理差错控制编码的基本作法是：在发送端被传输的信息序列上附加一些监督码元，这些多余的码元与信息之间以某种确定的规则建立校验关系。

接收端按照既定的规则检验信息码元与监督码元之间的关系，一旦传输过程中发生差错，则信息码元与监督码元之间的校验关系将受到破坏，从而可以发现错误，乃至纠正错误。

对于（n ，k ）线性分组码编码器，输出的n 比特码字包含k 比特信息码元和k n -比特监督码元。

如图1所示。

根据图1的表示法，码字最右边的k n -比特为监督比特，最左边k 比特与相应的信息比特相同。

因此有⎩⎨⎧--=--==+-1,, , 1,,1,0 , n k n i m k n i b c k n i i i （1）k n -个监督比特是k 个信息比特的线性和，可以用一般的多项式表示：1)1(1100--+++=k k i m p m p m p b i i i （2） 系数的定义如下⎪⎩⎪⎨⎧=i im ,0m ,1不依赖于如果依赖于如果j j ij b b p （3）系数ij p 的选择要是生成矩阵的各行线性独立，且校验式唯一。

式（1）和式（2）给出了（n ，k ）线性分组码的数学结构。

这两个等式可以用矩阵表示法重新表示为一种紧凑的形式。

为此，我们定义k ⨯1的信息矢量m ，()k n -⨯1监督矢量b 和n ⨯1的码矢量c ，其形式分别为 ],,,[021m m m k k --=m （4）],,,[021b b b k n k n ----=b （5）],,,[021c c c n n --=c（6）注意，这三个都是行矢量。

这样就可以用紧凑的矩阵形式将定义监督比特的联立等式写为m P c = （7） 其中，P 为()k n k -⨯的系数矩阵，其定义如下：⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=------------------0,02,01,00,22,21,20,12,11,1p p p p p p p p p k n k n k k n k k n k k k n k k n k P （8） 其中，ij p 取值1或0。

3.从剩下的元素中任取一个重量最轻的，按相同方式 构成第三行，依此类推…
34
伴随式译码
陪集首 陪集
伴随式
35
伴随式译码
(6,3)码的标准阵
陪集首
伴随式
36
伴随式译码
BSC下，二元线性码正确译 码的概率：
第l个陪集
首的重量
重量为i的陪 集首的数量
37
伴随式译码
译码步骤： 计算接收矢量的伴随式 由伴随式确定陪集首 将陪集首作为错误图样e
将v译为c=v-e
38
最小距离和纠错能力
Th. v属于码字集合的充要条件是v的非 零码元与H相应列的乘积之和为0。
推论：若矩阵H中任意d-1列线性无关，相应码的最小距离至少为d。
39
最小距离和纠错能力
1.最小距离与纠错能力：(n,k) 线性码能纠t个错误的充要条件是码的最小距离 为
[证明]：设码C的最小距离为dmin,以码字为中心，以 t为半径的球应不相交。反证若相交，设V为其中元 素，C1,C2来自两相交球的码字，有三角不等式。
所以码字又称为码矢。 编码速率/编码效率/码率/传信率：R=k/n。它说明了信道的利用效率，R是衡量码
性能的一个重要参数。
2
线性分组码
码字重量：码字中非0码元符号的个数，汉明重量。 在二元线性码中，码字重量是码字中含“1”的个数。
等重码: 所有码字具有相同的重量. 汉明距离：在(n,k)分组码中，两个码字 U、V 之间 对应码元位上符号取值不同的个数。 最小距离dmin：任意两个码字间距离最小值.
10
线性分组码
证明 （要证明，第一个码中任一个码字也是第二个 码中的码字；第二个码中任一个码字也是第一个码 中的码字）

3.6.2标准阵列和译码 3.6.2译码
第三章
3.6.1信息传输系统模型
将信息传输系统模型简化成图3-3所 示的简化模型。
噪声源
E
信源
u
纠错码 编码器
c
编码信道
y
纠错码 译码器
ˆ y
信宿
图3-3 简化的信息传输系统模型
第三章
译码过程中的两个重要的概念
第三章
第三章
3.6.2标准阵列和译码
第三章
HGT 0
第三章
第三章
3.3系统线性分组码
第三章
第三章
第三章
第三章
第三章
第三章
第三章
常用的系统码有两种形式：信 息组被排在码字的最左边k位，或信 息组被排在码字的最右边k位。 一般来说，系统码的译码相对非 系统码要简单一些，但两者的纠错 能力完全等价，因此一般总希望线 性分组码采用系统码形式。
n 的码字
c (cn1cn2 c1c0 )(n k )
码字共有 n
位，其中k位为信息位， n k
位为校验位，称为一个
(n, k ) 分组码。
在分组码中，若c与u的对于关系是线性的， 则称为线性分组码。
第三章
第三章
例如3-1 有一个（5，2）分组码 C=｛00000，01011，10101，11110｝， 假设消息序列与码字的映射为：
对一个给定的线性码，它的生成矩阵不是唯 一的，因为生成矩阵的行可以有多种选择。
第三章
生成矩阵 G 提供了一种简明而有效地表示
线性分组码的方法。k×n阶矩阵可以生成 2k 个码字。因此，我们只需要一个生成矩阵
k 2 而不需要含 个码字的查询表。

码矢：一个 n 重的码字可以用矢量来表示：
C=(cn－1,cn－1,…,c1,c0 )
(n,k) 线性码：信息位长为 k，码长为 n 的线性码。
编码效率/编码速率/码率/传信率：R=k /n。它说明了信
道的利用效率，R 是衡量码性能的一个重要参数。
返回目录
31.12.2020
h
第4页
8.2 一致监督方程和一致监督矩阵
(8.2.8)
监督矩阵 H 的标准形式：后面 r 列是一单位子阵的监 督矩阵 H。
31.12.2020
h
第13页
8.2 一致监督方程和一致监督矩阵
(4) 一致监督矩阵特性
H 标准形式的特性
H 阵的每一行都代表一个监督方程，它表示与该行中“1”相对应的码
元的模 2 和为 0。 参见方程
H 的标准形式表明了相应的监督元是由哪些信息元决定的。例如 (7,3) 码的 H 阵的第一行为 (1011000)，说明第一个监督元等于第一个和第三
c0h c5
c4
(7.2.1)
第6页
8.2 一致监督方程和一致监督矩阵
(1) 一致监督方程
一致监督方程/一致校验方程：确定信息元得到监督元 规则的一组方程称为监督方程/校验方程。由于所有码 字都按同一规则确定，又称为一致监督方程/一致校验 方程。
为什么叫线性分组码？由于一致监督方程是线性的，即 监督元和信息元之间是线性运算关系，所以由线性监督 方程所确定的分组码是线性分组码。
1 1
1 0
0 0 0 1 0 1 1
若m14 (1010)，则：
1 0 0 0 1 0 1
C17 m G 14 47 1
0
1
00