信息论第九讲-代数基础与线性分组码共71页

线性分组码与循环码1．线性分组码的概念线性分组码是指信息位和监督位满足一组线性代数方程式的分组码。

其中分组码（n，k）满足条件式中，r＝n－k为监督位数。

2．线性分组码的原理（1）监督矩阵①监督矩阵的表示形式式中，H为r×n阶监督矩阵；A为分组码构成的1×n阶矩阵。

②监督矩阵的典型式式中，P为r×k阶矩阵；I r为r×r阶单位方阵。

（2）生成矩阵式中，G为k×n阶生成矩阵；Q为k×r阶矩阵，是P的转置，即由生成矩阵可以产生整个码组式中，A0为由分组码的信息位构成的1×k阶矩阵。

3．线性分组码的检验（1）检验计算式中，S称为校正子；B为接收码组。

（2）检验规则①若为0，代表该位无错码；②若为1，代表该位有错码。

4．线性分组码的性质（1）封闭性线性分组码的任意两个码组之和仍为这种码中的一个码组。

（2）最小码距最小码距就是码组的最小重量（全“0”码组除外）。

六、循环码1．循环码的原理（1）循环码的定义循环码是指除了具有线性码的一般性质外，还具有循环性的码，即任一码组循环一位以后，仍为该码中的一个码组的编码方式。

（2）循环码的特点a．编码和解码设备简单；b．检（纠）错的能力较强。

（3）循环码的运算①循环码的代数表示将码组中各码元当作是一个多项式的系数，即把一个长度为n的码组表示成式中，x仅是码元位置的标记，该多项式称为码多项式。

②码多项式的按模运算一个长为n的循环码必为按模（x n＋1）运算的一个余式，即式中，的作用是将代表的许用码组向左循环移位次得到许用码组。

③循环码的生成矩阵循环码的生成矩阵G可以写成式中，g(x)为循环码的生成多项式。

④循环码的生成多项式（n，k）循环码的生成多项式g(x)必须是一个常数项不为“0”的（n－k）次多项式且是的一个因子。

如（7，3）循环码的生成多项式g(x)为2．循环码的编解码方法（1）循环码的编码方法①用x n－k乘信息码元多项式m(x)；②用g(x)除x n－k m(x)，得到商Q(x)和余式r(x)，即③令编出的码组为（2）循环码的解码方法①检错a．检错方法在接收端将用原生成多项式g(x)除接收码组B(x)。

设码字x5 (x0 , x1, x2 , x3, x4 )， 可得 信息位 码字
00 00000 01 01101 10 10111 11 11010
x2
x3
x0 x0
x1
x4 x0 x1
20
线性分组码的基本概念
改写为
1 1
x0 x0
1 0
x1 x1
1 x2 0 0 x2 1
二战期间在路易斯维尔大学当教授，1945年参加曼哈顿计划， 负责编写电脑程式，计算物理学家所提供方程的解。该程式 是判断引爆核弹会否燃烧大气层，结果是不会，于是核弹便 开始试验。
1946至76年在贝尔实验室工作。他曾和约翰·怀尔德·杜奇、 克劳德·艾尔伍德·香农合作。1956年他参与了IBM 650的程 式语言发展工作。
码字无关！
记S= en·HT ，称之为接收序列rn的伴随式.
36
线性分组码的译码
（n，k）线性分组码的校验矩阵，用列向量
表出：
h1,1
h1,2
H
h2,1
h2,2
h1,n
h2,n
h1
h2
hn
hnk
,1
hnk ,2
hnk
,n
其中，hn-i为H矩阵的第i列.
37
线性分组码的译码
设en=(e1， e2，…，en)=(0，…，ei1，0，…，ei2，0，…， ei3，0，…，eit，0，…，0)
信息位 码字
00 00000
1(01) 1(10) 11
01 01101 10 10111
f (11) 11010
11 11010
1(01101) 1(10111) 11010
f (1(01) 1(10)) 1(01101) 1(10111)

（2）传输差错产生的过程
图9-1 传输差错产生过程
（3）差错控制机制 差错控制机制分类：反馈纠错，前向纠错，及所派生出的 混合纠错。 a）反馈纠错 发信端采用某种能发现一定程度传输差错的简单编码 方法对所传信息加入少量监督码元进行编码，在接收端则 根据编码规则对收到的编码信号进行检查，当检测出错码 时，即向发信端发出询问的信号，要求重发。发信端收到 询问信号时，立即重发已发生传输差错的那部分信息，直 到正确收到为止。 发现差错：在若干接收码元中，知道有一个或一些是 错的，但不一定知道错误的准确位置。 优点：纠错能力强，检错能力与信道干扰变化无关，编 译码器简单。
由于每两个1的模2相加为0，故利用模2加法可以判断一个 码组中码重是奇数或是偶数。模2加法等同于“异或”运算。 现以偶监督为例。 对于偶校验，应满足
故监督位码元 C0 可由下式求出：
奇偶校验编码只能检出单个或奇数个误码，而无法检知偶 数个误码，对于连续多位的突发性误码也不能检知，故检错 能力有限，另外，该编码后码组的最小码距为 d =2，故没有 纠错码能力。 奇偶监督码常用于反馈纠错法。
9.4 纠错编码方式简介 （1）奇偶监督码 奇-偶校验码（奇偶监督码），一种最简单的线性分组 检错编码方式。 编码方法： ① 把信源编码后的信息数据流分成等长码组。 ② 在每一信息码组之后加入一位(1比特)监督码元作 为奇偶检验位。 使得总码长n(包括信息位k和监督位1)中的码重为 偶数(称为偶校验码)或为奇数 (称为奇校验码)。 ③ 校验：如果在传输过程中任何一个码组发生一位 (或奇数位)错误，则收到的码组必然不再符合奇偶校验 的规律，因此可以发现误码。 奇校验和偶校验两者具有完全相同的工作原理和检 错能力，原则上采用任一种都是可以的。
min

其中“ 表示定义的代数运算，如二元运算、＋、－、 其中“O”表示定义的代数运算，如二元运算、＋、－、·、 /、 ⊕ 等 。
东南大学移动通信国家重点实验室
7
《信息论与编码》课件 信息论与编码》
10.1 近世代数的基础知识
10.1.2 群的基本概念
1. 群的定义 非空集合， 内定义了一种代数运算， 定义10.4 设 G是 非空集合， 并在 G内定义了一种代数运算 ， 四个条件， 为一个群： 若满足如下四个条件 若满足如下四个条件，则称G为一个群： (1) 封闭性。 对任意a∈G，b∈G，恒有a O b∈G。 封闭性。 (2) 结合率成立。对任意a∈G，b∈G ，c∈G，恒有 结合率成立。 (a O b)O c = a O (b O c)。 (3) 若G中有一元素e，对任意的a∈G，满足aOe = eOa = a， 称为单位元或恒元 单位元或恒元。 则e称为单位元或恒元。 (4) 若对于任意 a∈G，G中存在有另一元素a –1，使 a O a –1 = a –1O a = e，则a –1称为a的逆元。 的逆元。
东南大学移动通信国家重点实验室
3
《信息论与编码》课件 信息论与编码》
10.1 近世代数的基础知识
10.1.1 整数的有关概念 1. 整数的运算及其性质
整数的运算包括加、减、乘、除、开方、乘方、取对数 等，这里仅重述几个在编码中常用的概念： 素数：只能被1和它本身整除的整数。 素数 合数：除1和自身外，还存在其它因数的整数。 合数 最大公约数（ ）的性质： 最大公约数（a, b）的性质 任意正整数a, b，必存在整数A, B，使： (10.1) （a, b）= Aa + Bb 最小公倍数[a, 的性质： 最小公倍数 b] 或LCM (a，b)的性质 ， 的性质 任意正整数a, b，必存在关系式： (10.2) ab = [a, b](a, b)

表示所有G中的元素。 例：设G是整数集合，在普通加法+下为一个交 换群，而H为G的一个子群，它由整数m的倍数 构成，那么，所有正整数均可用H中的元素表示 ，且划分为子群H的若干个陪集。 H:{nm}; n=0,±1,±2,…。 例如m=3,则子群H的元素为： H:{0, ±3, ±6, ±9, ±12, ±15, ±18,…} 利用分元陪集的方法，用H的元素表示G中的所 有元素。
•GF(2)上的多项式若有偶数项，则一定可被x+1除 尽。
•对于任意m≥1,都存在m次不可约多项式。
•GF(2) 上 的 任 意 m 次 不 可 约 多 项 式 ， 一 定 能 除 尽
xn+1，其中n=2m-1。
例如：x3+x+1,可以除尽x7+1。
2019/11/24
16
x3+x+1
2019/11/24
• 这样，利用分元陪集的方法，可以构成所有G中 的元素。
陪集1
0
3
-3
6
-6
9
-9
…
陪集2
1+0= 1
1+3= 4
-2
7
-5
10
-8
…
陪集3
2+0= 2
2+3= 5
-1
8
-4
11
-7
…
2019/11/24
6
5.4.2 域(Field)
[域的定义]：如果一个元素集合F，在其中定义加法 和乘法两种运算，并满足下列条件则称为一个域
2019/11/24
2
例如：p=5为一个素数, G={1,2,3,4}为一个乘法 群，
*
1

二、线性分组码的严格数学定义2
2. 定理1 (码的封闭性）
设CH为由监督矩阵H定义的分组码，则c1,c2CH : c1+c2CH 证明： 由c1CH，得Hc1T=0T;
由c2CH，得Hc2T=0T;
所以 H(c1+c2)T=H(c1T+c2T) =Hc1T+Hc2T=0T c1+c2满足HcT=0T，所以c1+c2 CH
+
+
考虑如何用串行方式？
三、G与H的关系4
0 1 2 3 4 5 6 7 8 9 10 11 12 13
D0
D1
+
D2
+
D3
+
D0
D1
+
D2
+
D3
+
m4m5m6
m6
m6
D0
D1
m6+m5 m6
D0
D1
m6
m6
+
D2
+
D3
+
m4m5
m6+m5
m6+m5
+
D2
m6+m5+m6
=m5
+
D3
+
m4
m5+m4
互为对偶码，若CH=CG, 则称为自对偶码（P62)
[Q In-k] [IkP]T= [QIn-k] [IkT PT]T= Q + PT = 0
所以 P= - QT 或 Q = -PT
由此得 G=[Ik P] = [ Ik –QT] H=[Q In-k]= [ -PT In-k]
三、G与H的关系2

线性分组码8.3.1 基本概念是一组固定长度的码组，可表示为（n, k），通常它用于前向纠错。

在分组码中，监督位被加到信息位之后，形成新的码。

在编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错与纠错。

当分组码的信息码元与监督码元之间的关系为线性关系时，这种分组码就称为。

对于长度为n的二进制线性分组码，它有种可能的码组，从种码组中，可以选择M=个码组（k<n）组成一种码。

这样，一个k比特信息的线性分组码可以映射到一个长度为n码组上，该码组是从M=个码组构成的码集中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。

线性分组码是建立在代数群论基础之上的，各许用码的集合构成了代数学中的群，它们的如下：（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) 下面通过一个例子来说明的。

25、学习是劳动，是充满思想的劳动。——乌申斯基
谢谢！
1、不要轻言放弃，否则对不起自己。
2、要冒一次险!整个生命就是一场冒险。走得最远的人，常是愿意 去做，并愿意去冒险的人。“稳妥”之船，从未能从岸边走远。-戴尔．卡耐基。
梦Hale Waihona Puke 境3、人生就像一杯没有加糖的咖啡，喝起来是苦涩的，回味起来却有 久久不会退去的余香。
信息论基础——线性分组码. 4、守业的最好办法就是不断的发展。 5、当爱不能完美，我宁愿选择无悔，不管来生多么美丽，我不愿失 去今生对你的记忆，我不求天长地久的美景，我只要生生世世的轮 回里有你。
21、要知道对好事的称颂过于夸大，也会招来人们的反感轻蔑和嫉妒。——培根 22、业精于勤，荒于嬉；行成于思，毁于随。——韩愈
23、一切节省，归根到底都归结为时间的节省。——马克思 24、意志命运往往背道而驰，决心到最后会全部推倒。——莎士比亚

信息论与编码基础
线性分组码
1、汉明码的结构
码长 信息位数
n 2m 1
k 2m m 1
监督码位 最小码距 纠错能力
r nk m
d 3
t 1
信息论与编码基础
线性分组码
2、扩展汉明码
C [mk1mk2...m1m0cr1...c1c0 ]
(8,4(7)扩,4)展汉汉明明码码
C [C c0 ]
1 2
1 1
H
2 2
1 2
1 0
0 1
利用伴随式译码对(1122),(2110),(2222)码字进行译码。
E 0000 1000 0100 00010010 0011 1001 1010 0200 S 00 22 12 01 10 11 20 02 21
信息论与编码基础
线性分组码
思考题2：
考虑码率为1/2的（n,n/2）的线性分组码C，其生 成矩阵为G。 证明：如果
其定充理要条件(n是,k)H线矩性阵分中组任码何最2小t列距线离性等H无于关d。111min的110 充110要条100 件100是H100
0 0 0
矩阵中任何 dmin 1 列线性无关。
0 1 1 0 0 0 1
结论：
1、上述定理是构造距离为d的任何类型线性分组码的基础
2、H矩阵列排序不同，码集不同，但纠错能力不变
线性分组码
伴随式译码
定理 每个陪集全部 2k个矢量都有相同的伴随式 而不同陪集有不同的伴随式。
C C C C （0）
（1）
（2）
（3）
S
0000 0111 1010 1101 00
1000 1111 0010 0101 10

Thank you
线性分组码的编码原理
31、别人笑我太疯癫，我笑他人看不 穿。(名 言网) 32、我不想听失意者的哭泣，抱怨者 的牢骚 ，这是 羊群中 的瘟疫 ，我不 能被它 每天的 成功， 避免以 失败收 常在别 人停滞 不前时 ，我继 续拼搏 。
6、最大的骄傲于最大的自卑都表示心灵的最软弱无力。——斯宾诺莎 7、自知之明是最难得的知识。——西班牙 8、勇气通往天堂，怯懦通往地狱。——塞内加 9、有时候读书是一种巧妙地避开思考的方法。——赫尔普斯 10、阅读一切好书如同和过去最杰出的人谈话。——笛卡儿
33、如果惧怕前面跌宕的山岩，生命 就永远 只能是 死水一 潭。 34、当你眼泪忍不住要流出来的时候 ，睁大 眼睛， 千万别 眨眼!你会看到 世界由 清晰变 模糊的 全过程 ，心会 在你泪 水落下 的那一 刻变得 清澈明 晰。盐 。注定 要融化 的，也 许是用 眼泪的 方式。
35、不要以为自己成功一次就可以了 ，也不 要以为 过去的 光荣可 以被永 远肯定 。

的每一行都是一个码字， 由于生成矩阵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 位为校验字，这种 － 位为校验字， 信息数字在前校验数字在后的线性分组码称为线性系 统分组码。 统分组码。

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
线性分组码
证明 （要证明，第一个码中任一个码字也是第二个 码中的码字；第二个码中任一个码字也是第一个码 中的码字）

⎡
⎢
H
=
⎢ ⎢
h0
h1 #
⎤⎡
⎥⎢
⎥ ⎥
=
⎢ ⎢
h0,0
h1,0 #
⎢⎣h
n−
k
−1
⎥ ⎦
⎢⎣hn−k −1,0
h0,1 h1,1 #
hn−k −1,1
" h0,n−1 ⎤
#
h1,n−1
⎥ ⎥
" #⎥
"
hn−k
−1,n
−1
⎥ ⎦
一致校验矩阵
由对偶空间的定义知，有对任意的 c∈C
cHT = 0
即H可以检验一个n重是否为码字，称H为码C的 一致校验矩阵。
例题
设二元（5,3）码，其生成矩阵为
⎡1 0 0 1 1⎤ G = ⎢⎢1 1 0 0 0⎥⎥
⎢⎣1 1 1 1 1⎥⎦
将其化为标准形式？
一致校验矩阵
与任何一个(n,k)码的码空间C相对应，一定存在一个 对偶空间D，它的每个矢量都与C中的每个矢量正交， 其维数为n-k。 事实上，若找出生成空间D的基底（n-k个）用这n-k个 矢量同样可以生成包含 2n个−k码字的(n,n-k)线性分组 码，我们称其(n,k)码的对偶码，生成矩阵为
pw(c) 1− p n−w(c)
w(e)≠0
w(c)≠0
e∈C
c∈C
• 令一个(n,k)线性分组码，Ai为码组中重量为i的码字的个 数，码字集合（码组）的重量分布为A0,A1,…An。这时码 字在转移概率为pe的BSC信道上的漏检概率为：
n
∑ Pud = Ai pei (1− pe )n−i i =1
• 例如：(7,4)汉明码的重量分布为：

2r 1 n 或 2r k r 1
当“=”成立时，构造的线性分组码 称为汉明码 —能纠1位错码
(n, k) (2r 1, 2r 1 r)
高效线性分组码
信息元和校验(parity check)元是平等的。此外，后者不应称为监督元。
南京邮电大学 通信与信息学院
课件制作：朱 5彤
例 (7, 4)汉明码
偶校验关系是经典使用的。它的一个特 点是：全0信息码必对应全0校验码。
编码时，用ai替代bi。校验位a2 、 a1、 a0的取值应使上3式中s1、 s2和s3为0 （无错码），即
课件制作：朱 7彤
a6 a5 a4 a2 0 a6 a5 a3 a1 0 a6 a4 a3 a0 0
南京邮电大学 通信与信息学院
课件制作：朱 彤
差错控制
南京邮电大学 通信与信息学院
课件制作：朱 彤
§3
线性分组码
南京邮电大学 通信与信息学院
课件制作：朱 彤
基本概念
线性码：按照一组线性方程构成的代数码。 即每个码字的校验码元是信息码元的线性组合。
代数码：建立在代数学基础上的编码。 分组码：每一码组的校验码元仅与本组中的信息码元有关。 线性分组码：按照一组线性方程构成的分组码。
[例2解]依次取从0000到1111信息码与G相乘，实际上就是把G中一行或 几行按位相加凑成前4位是所需信息码，则整个码组就是所需编码。例如， 第2行与第4行相加得0101101。所有码组见前述汉明码码字表(p.8)
[例3解] n=4，对于奇偶校验码来说，校验位r=1。H矩阵为14阵。由于 校验和式是把所有位都模2加，因此，H=[1 1 1 1]。 H中，P=[1 1 1](前3 位)，单位矩阵为[1]。因此， G为34阵，G=[I3 PT]100 1

1、既然我已经踏上这条道路，那么，任何东西都不应妨碍我沿着这条路走下去。——康德 72、家庭成为快乐的种子在外也不致成为障碍物但在旅行之际却是夜间的伴侣。——西塞罗 73、坚持意志伟大的事业需要始终不渝的精神。——伏尔泰 74、路漫漫其修道远，吾将上下而求索。——屈原 75、内外相应，言行相称。——韩非
线性分组码的编码原理
46、法律有权打破平静。——马·格林 47、在一千磅法律里，没有一盎司仁 爱。— —英国
48、法律一多，公正就少。——托·富 勒 49、犯罪总是以惩罚相补偿；只有处 罚才能 使犯罪 得到偿 还。— —达雷 尔
50、弱者比强者更能得到法律的保护 。—— 威·厄尔
谢谢你的阅读