当前位置：文档之家 › 信息论基础——线性分组码

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

  • 格式：ppt
  • 大小：860.00 KB
  • 文档页数：75

下载文档原格式

  / 75

合集下载

线性分组编码

线性分组编码

背景
在通信中，由于信息码元序列是一种随机序列，接收端无法预知码元的取值，也无法识别其中有无错码。所 以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元（校验元）。这些监督码元和信息 码元之间有确定的关系。
在信息码元序列中加监督码元就称为差错控制编码，差错控制编码属于信道编码。
信息码元和监督码元之间有一种关系，关系不同，形成的码类型也不同。可分为两大类：分组码和卷积码。 其中，分组码是把信息码元序列以每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。

信息论与编码原理_第8章_线性分组码

信息论与编码原理_第8章_线性分组码

举例：(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 和。

信息论与编码理论-信道编码-线性分组码2剖析

信息论与编码理论-信道编码-线性分组码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章 线性分组码

[理学]信息论与编码原理第8章线性分组码PPT课件

[理学]信息论与编码原理第8章线性分组码PPT课件
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

第3章 线性分组码

由上式经移项运算，解出监督位为
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

103线性分组码

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) 线性分组码各码组之间的最小码距，等于除全零码外的码组的最小重量。

信息论与编码09-线性分组码

的每一行都是一个码字， 由于生成矩阵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 位为校验字，这种 － 位为校验字， 信息数字在前校验数字在后的线性分组码称为线性系 统分组码。 统分组码。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。