7.1-线性分组码与汉明码
- 格式：pdf
- 大小：454.67 KB
- 文档页数：9
8.1.3 生成矩阵(Generator matrix )
（1）[生成矩阵的基本形式]： 由上面(7,4)汉明码的例子；可以将基本监督方程 扩展写为： c6=c6 c5=c5 c4=c4 c3=c3 c2=c5+c4+c3 c1=c6+c4+c3 c0=c6+c5+c3
13
1000011 [ c 6 , c 5 , c 4 , c 3 , c 2 , c1 , c 0 ] [ m 3 , m 2 , m 1 , m 0 ] 0100101 0010110 0001111
如果对于系统码，其前k位为信息位，后r位监督位。 信息位=[mk-1,mk-2,……,m0]=[cn-1,cn-2,……,cn-k] 监督位=[cn-k-1,……c1,c0]
由于线性分组码的监督元与信息元之间是线性关系，可以用 二元域上的线性方程组描述。记为： cn-k-1=h1,n-1cn-1+h1,n-2cn-2+……+h1,n-kcn-k cn-k-2=h2,n-1cn-1+h2,n-2cn-2+……+h2,n-kcn-k … c0=hr,n-1cn-1+hr,n-2cn-2+……+hr,n-kcn-k
12
P矩阵
11
I矩阵
2
Generated by Foxit PDF Creator © Foxit Software For evaluation only.
7.1.3 生成矩阵
7.1.3 生成矩阵 用矩阵表示：
1000011 0100101 [ c 6 , c 5 , c 4 , c 3 , c 2 , c1 , c 0 ] [c 6 , c 5 , c 4 , c 3 ] 0010110 0001111
8
注：在二元 域上： hij:{0,1}
电子与信息工程学院
7.1.2 基本监督矩阵 整理这个方程组，可得：
记为：[H][C]T=[0]
7.1.2 基本监督矩阵
c c h h n
1 ,n 1 2 ,n 1 n 1 n 2
0 0
c n 1 cn2 h 1 , n 1 h 1 , n 2 ... h 1 , n k 1 0 ... 0 ... h 2 , n 1 h 2 , n 2 ... h 2 , n k 0 1 ... 0 c n k [0] ... ... ... ... ... ... c n k 1 h r , n 1 h r , n 2 ... h r , n k 0 0 ... 1 ... c1 c0
17
7.1.3 生成矩阵
总结： 根据线性矢量空间的知识，这k个码字矢量就可以生成这 个k维子空间，将这k个矢量组成的矩阵就是(n,k)分组码 的生成矩阵。所以生成矩阵是一个k行n列的矩阵。 确定(n,k)码的生成矩阵的问题就是确定n重矢量空间中k 维子空间的k个线性无关的码字矢量的问题。也就是寻找 子空间基底的问题。 (n,k)码的n重矢量空间中的一个k维子空间的基底可以有 多个，因此可以有不同的生成矩阵[G]，但都产生相同的 码组。 非系统汉明码的编码与矩阵
7.1.2 基本监督矩阵
7.1.2 基本监督矩阵 这种码的码字矢量为：
[汉明码定义]：
对于任意正整数r≥3 ，存在有下列参数的线 性分组码—— 码长：n=2r-1 信息位：k=2r-1-r=n-r 监督位：r（=n-k） 最小码距：dmin=3 这种码称为狭义汉明码，也称为完备汉明 码。
7
[C]={cn-1,cn-2,……c1,c0}
19
7.1.4 校验子与译码 （2）接收码字矢量 这时接收码字可以表示为， [R]=[C]+[E] =(cn-1+en-1, cn-2+en-2,……c0+e0)
译码器的作用：从接收码字[R]中得到发送码字
的估计值，或者说从接收码字中确定错误图样[E]， 然后由[C]’=[R]-[E]得到发送码字的估计值，如果 估计正确则译码正确，否则译码错误。
16
...
系统码的生成矩阵也 称为典型生成矩阵， 其基本形式为： [G]=[Ik,Q]， [Q]为k×r矩阵， [I k]为k×k单位阵。
7.1.3 生成矩阵 （ 2） [系统码基本监督矩阵与典型生成矩阵的关系]： 比较[G]与许用码字可以知道，[G]的每行都是一 个码字矢量，则[G]的每行都应当满足监督矩阵所规定 的监督关系，即应当有： [H][G]T=[0]，同时有：[G][H]T=[0] 称[H]与[G]为正交矩阵； 由[P Ir] [Ik Q]T=[0] 可以得到： [P+QT]=[0] 即： [P]=[Q]T 和 [Q] = [P] P矩阵与Q矩阵互为转置矩阵。
7.1.1 线性分组码的定义 7.1.2 基本监督矩阵 7.1.3 生成矩阵 7.1.4 校验子与译码
2
电子与信息工程学院
第 7章 线性分组码
7.1.1 线性分组码的定义
[m]= (mk,mk-1,…m0) [C]=(cn-1,cn-2,…,c0) Encoder
7.1 汉明码
5 6 7 7.1.5 分组码的纠检错能力 7.1.6 标准阵与校验子译码 7.1.7 分组码的其他概念
1 1 1
1 0 0
1000 1001 1010 1011
0 1 0
1000 011 1001 100 1010 101 1011 010
0 0 1
1100 1101 1110 1111 1100 110 1101 001 1110 000 1111 111
由其得到的汉明码字如下表：
T
18
3
Generated by Foxit PDF Creator © Foxit Software For evaluation only.
7.1.4 校验子与译码 （1）错误图样 设发送码字为：[C]=(cn-1,cn-2,……,c0)； 由于信道干扰产生差错，反映到接收码字上可以用 一个二元矢量[E]表示， 这个矢量称为错误图样(error patterns)， [E]=(en-1,en-2,……,e0) 其中： ei=1表明相应位有错，ei=0表明相应位无错。 注：错误图样就是对位反映接收码字错误与否。
14
7.1.3 生成矩阵 可以写为： [C]=[m3,m2,m1,m0]•[G] [汉明码字]=[信息码字][生成矩阵] [G]称为生成矩阵。 可以看出：(n,k)码的生成矩阵的基本形式为：
g1,n 1 g1,n 2 ... g1,1 g1,0 g 2,n1 g 2,n 2 ... g 2,1 g 2 ,0 [G ] ... ... ... ... ... g k ,n 1 g k ,n 2 ... g k ,1 g k ,0
Generated by Foxit PDF Creator © Foxit Software For evaluation only.
第7章 线性分组码
7.1 汉明码
第7章 线性分组码
哈尔滨工业大学 电子与信息工程学院 顾学迈、石 硕
1 2 3 1 4
[ R ] = ( c n -1 + e n -1 , c n -2 + e n -2 ,… … c 0 + e 0 ) D ec o d e r
20
[ C ’ ] =( c ’ n- 1 ,c’ n - 2,… ,c’ 0)
电子与信息工程学院
电子与信息工程学院
7.1.4 校验子与译码 (3)校验子 定义[S]为校验子（伴随式）： [S]=[R][H]T=[C][H]T+[E][H]T=[E][H]T [S]T=[H][R]T=[H][C]T+[H][E]T=[H][E]T [S]=[sr,sr-1,……s1] [S]T=[sr,sr-1,……s1]T 错误图样[E]=0 <=> 校验子 [S]=0 <=> 接收码无错 错误图样[E]≠0 <=> 校验子 [S]≠0 <=> 接收码错
21
7.1.4 校验子与译码 举例: (7,4)汉明码的基本监督矩阵[H]为已知， 0 [H]= 1 1
0000 0001 0010 0011 0000 000 0001 111 0010 110 0011 001 0100 0101 0110 0111
1 0 1
1 1 0
0100 101 0101 010 0110 011 0111 100
当分组码监督元与信息元之间的代数关系是线性的， 则称这种分组码为线性分组码。
信息元(k 位)
监督元(r 位）
5
电子与信息工程学院
6
电子与信息工程学院
1
Generated by Foxit PDF Creator © Foxit Software For evaluation only.
15
7.1.3 生成矩阵 利用生成矩阵的编码关系为[C]=[m][G] 而系统(n,k)码的生成矩阵的基本形式应当为
[G ]
1 0 ... 0 g1,n k 1 ... g1,0 0 1 ... 0 g 2, n k 1 ... g 2, 0 ... ......... ... ... 0 0 ... 1 g k ,n k 1 ... g k ,0
7.1.1 线性分组码的定义 (n,k)线性分组码：是长度为n，有2k个码字的分组码 ，同时这2k个码字是二元域上所有n维矢量空间的一 个k维子空间。 二元分组码为线性分组码的充要条件为两个码字的模 二加也是一个码字（线性闭合）。 线性分组码的一个重要参数为码率(Code rate)： R=k/n; 它实际上也就是编码效率或传输效率。 如果(n,k)码位信息位没有变化，与信息码元排列相 同，并且与监督位分开，称为系统码，否则称为非系 统码。
