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

2012/1/2
7/52
线性分组码： 线性分组码：通过预定的线性运算将长为 k 位的信息码 组变换成 n位的码字 (n>k)。由 2k 个信息码组所编成的 2k 位的码字 。 个码字集合，称为线性分组码 线性分组码。 个码字集合，称为线性分组码。 码矢： 码矢：一个 n 重的码字可以用矢量来表示
C=(Cn－1,Cn－1,…,C1,C0 ) － －
2012/1/2
16/52
线性分组码的生成矩阵
线性码的封闭性: 线性码的封闭性
线性码的封闭性： 线性码的封闭性：线性码任意两个码字之和仍是 一个码字。 一个码字。 因为： 为线性码的任意两个码字， 因为：若 U 和 V 为线性码的任意两个码字，故有
HUT=0T，HVT=0T 0 0 那么 H(U+V)T=H(UT+VT)=HUT+HVT=0T 0 满足监督方程， 即 U+V 满足监督方程，所以 U+V 一定是一个
所以码字又称为码矢。 所以码字又称为码矢。 (n,k) 线性码：信息位长为 k，码长为 n 的线性码。 线性码： 的线性码。 ， 编码效率/码率： 编码效率 码率：R=k /n。它说明了信道的利用效率，R是 码率 。它说明了信道的利用效率， 是 衡量编码性能的一个重要参数。 衡量编码性能的一个重要参数。注：用编码提高通信系 统的可靠性， 是以降低有效性为代价换来的。 统的可靠性， 是以降低有效性为代价换来的。
2012/1/2
19/52
线性系统分组码: 线性系统分组码
通过行初等变换， 列是单位子阵的标准 通过行初等变换，将 G 化为前 k 列是单位子阵的标准 形式
2012/1/2
20/52
线性系统分组码： 线性系统分组码：用标准生成矩阵 Gk×n 编成的码字， × 编成的码字， 位为信息数字， 前面 k 位为信息数字，后面 r=n－k 位为校验字，这种 － 位为校验字， 信息数字在前校验数字在后的线性分组码称为线性系 统分组码。 统分组码。
一致监督矩阵特性: 一致监督矩阵特性
各行实行初等变换， 列化为单位子阵， 对H 各行实行初等变换，将后面 r 列化为单位子阵，于是得到 下面矩阵(行变换所得方程组与原方程组同解 行变换所得方程组与原方程组同解)。 下面矩阵 行变换所得方程组与原方程组同解 。
的标准形式： 监督矩阵H 的标准形式：后面 r 列是一单位子阵的监督矩阵H。
2012/1/2
12/52
推广到一般情况： 线性分组码， 推广到一般情况：对 (n,k) 线性分组码，每个码字中的 r(r=n－k) 个监督元与信息元之间的关系可由下面的线性 － 方程组确定
2012/1/2
13/52
一致监督方程和一致监督矩阵
令系数矩阵为 H，码字行阵列为 C
2012/1/2
14/52
的码字有 r 个监督元。 个监督元。 为了得到确定的码， 个监督方程（ 阵的r 为了得到确定的码，r 个监督方程（或H 阵的 行）必 须是线性独立 线性独立的 须是线性独立的，这要求H 阵的秩为 r。 。 阵化成标准形式，只要检查单位子阵的秩， 若把H 阵化成标准形式，只要检查单位子阵的秩，就 阵本身的秩。 能方便地确定H 阵本身的秩。
2012/1/2 2/52
二进制(n, 分组码 可用编码空间的序列数为2 序列数为 二进制 k) 分组码，可用编码空间的序列数为 n个， 许用码字数为 码字数为2 个码字未被选用， 许用码字数为 k ，其余 2n-2k个码字未被选用，称为 禁用码组。 禁用码组。 任一种2 信息集合到二进制序列集合2 任一种 k信息集合到二进制序列集合 n的映射都是一 2k 种(n, k)码。因此总共可能的编码方案有C n种。 码
2012/1/2
8/52
一致监督方程和一致监督矩阵
一致监督方程： 一致监督方程：
在 k 个信息码元之后附加 r(r=n－k) 个监督码元，使每个监督元是 － 个监督码元， 其中某些信息元的模2和 其中某些信息元的模 和。 线性分组码。 例k=3, r=4构成 (7,3) 线性分组码。设码字为 构成 (C6,C5,C4,C3,C2,C1,C0) C6,C5,C4为信息元，C3,C2,C1,C0为监督元，每个码元取“0”或 为信息元， 为监督元，每个码元取“0”或 “1” 监督元可按下面方程组计算
2012/1/2 4/52
线性码的好处
可以简化分析：将距离谱变成重量谱。 可以简化分析：将距离谱变成重量谱。 简化译码： 简化译码： 随机分组码译码需要2 次长为n的距离计算及比较 的距离计算及比较。 随机分组码译码需要 k次长为 的距离计算及比较。 线性分组码译码只需要n-k次长为 的矢量内积和一 线性分组码译码只需要 次长为n的矢量内积和一 次长为 张大小为长2k宽2n-k的表。 张大小为长 的表。 说明约束起了作用，但还不够， 说明约束起了作用，但还不够，需要进一步引入其它 约束
当生成矩阵 G 确定之后，(n,k) 线性码也就完全被确定 确定之后， 只要找到码的生成矩阵，编码问题也同样解决了。 了，只要找到码的生成矩阵，编码问题也同样解决了。
2012/1/2
21/52
例:
(7,4) 线性码的生成矩阵为
2012/1/2
22/52
生成矩阵与一致监督矩阵的关系: 生成矩阵与一致监督矩阵的关系
2012/1/2
9/52
信息码组 (101)，即C6=1, C5=0, C4=1 ， 由线性方程组得： 由线性方程组得： C3=0, C2=0, C1=1, C0=1 即信息码组 (101) 编出的码字为 (1010011)。 。 其它7个码字如表 个码字如表。 其它 个码字如表。 (7,3)分组码编码表
汉明距离： 线性码中， 汉明距离：(n,k)线性码中，两个码字 U、V 之间对应码元 线性码中 位上符号取值不同的个数， 的汉明距离。 位上符号取值不同的个数，称为 U、V 的汉明距离。 之间第2、 、 和 位不 例：码字 U=0011101,V=0100111之间第 、3、4和6位不 之间第 因此， 的距离为4。 同。因此，码字 U 和 V 的距离为 。 最小距离d 线性码中， 最小距离 min：(n,k) 线性码中，任意两个码字间距离的最小 叫码的最小距离。 值，叫码的最小距离。 最小距离是衡量码的抗干扰能力（ 最小距离是衡量码的抗干扰能力（检、纠错能力）的重 纠错能力） 要参数。最小距离越大，抗干扰能力就越强。 要参数。最小距离越大，抗干扰能力就越强。 汉明球： 为中心， 汉明球：汉明球是以码字C为中心，半径为 t ，并与 C 的 汉明距离≤ 的全体向量集合。 汉明距离 t 的全体向量集合。 任意两个汉明球不相交最大程度取决于任意两个码字之 间的最小汉明距离d 间的最小汉明距离 min 。
信息组 000 001 010 对应码字 000 0000 001 1101 010 0111 011 1010 100 1110 101 0011 110 1001 111 0100
10/52
C6 +0+C4 +C3 +0+0+0 = 0 C +C +C +0+C +0+0 = 0 6 5 4 2 1 C6 +C5 +0+0+0+C +0 = 0 0+C5 +C4 +0+0+0+C0 = 0
码字。 码字。
2012/1/2
17/52
线性分组码的生成矩阵: 线性分组码的生成矩阵
维子空间中， 在由 (n,k) 线性码构成的线性空间 Vn 的 k 维子空间中， 个线性独立的码字： 。 一定存在 k 个线性独立的码字：g1,g2,…, gk,。码 CI 中 个码字的线性组合， 其它任何码字C都可表示为这 k 个码字的线性组合，即
2
译码运算量：如果直接用最大似然序列译码， 译码运算量：如果直接用最大似然序列译码，对一般 性的编码而言，正比于n* 几乎是不可能译码。 性的编码而言，正比于 2k 。几乎是不可能译码。
2012/1/2
3/52
引入线性码
发现或构造好码是信道编码研究的主要问题。 发现或构造好码是信道编码研究的主要问题。 编码方案太多，以至全局搜索是不可能的。 编码方案太多，以至全局搜索是不可能的。 现实的做法是对编码方案加以一定的约束， 现实的做法是对编码方案加以一定的约束，在一个子 集中寻找局部最优。 集中寻找局部最优。 这种约束即要能包含尽可能好的码，又要便于分析， 这种约束即要能包含尽可能好的码，又要便于分析， 便于译码。 便于译码。 线性分组码是最具实用价值的一类码，比如汉明码、 线性分组码是最具实用价值的一类码，比如汉明码、 循环码、 码等。 循环码、BCH码、RS码等。 码 码等 目前对线性系统的研究远远比非线性系统要充分。 目前对线性系统的研究远远比非线性系统要充分。
2012/1/2
011 100 101 110 111
一致监督矩阵： 一致监督矩阵：
将监督方程写成矩阵 形式， 形式，得：
H CT=0T或 0 C HT=0 0 CT、HT、0T分别表 示C、H、0的转置
矩阵。 矩阵。
2012/1/2 11/52
系数矩阵 H 的后四列组成一个 (4×4) 阶单位子阵，用 I4 × 阶单位子阵， 表示， 表示，H 的其余部分用 P 表示
2012/1/2
5/52
对信道编码的一般要求是： 对信道编码的一般要求是： ①纠错检错能力强； 纠错检错能力强； ②信息传输率高； 信息传输率高； ③编码规律简单，实现设备简单且费用合理； 编码规律简单，实现设备简单且费用合理； ④与信道的差错统计特性相匹配。 与信道的差错统计特性相匹配。20121/2线 性 分 组 码
2012/1/2
1/52
分组码的基本概念