第3章线性分组码.ppt

第3章线性分组码
线性分组码的基本概念
码的一致校验矩阵与生成矩阵
伴随式与标准阵列及其它译码
线性码的覆盖半径
由一个已知码构造新码的简单方法
用多个已知码构造新码的方法
线性码的重量分布与译码错误概率
线性码的纠错能力
1
线性分组码的基本概念
线性空间
设V 是一个非空集合, P 是一个数域, 在集合V 中定义了一种代数运算,叫做加法: 即对在V 中都存在唯一的一个元素λ,称λ为α与β的和,记为:
;在P与V的元素之间还定义了一种运算,叫做数量乘法:即
在V中都存在唯一的一个元素δ与它们对应,称δ为
的数量乘积,记为如果加法和数量乘法还满足下述规则,则称V 为数域P上的线性空间:
2
线性分组码的基本概念
加法满足下列四条规则:
①
④对
都有V中的一个元素β,使得
③在V中有一个元素0,对
(具有这个性质的元素0称为V的零元素)
;(β称为的负元素)
②
3
线性分组码的基本概念
⑤
⑥
数量乘法与加法满足下列两条规则:
⑦
数量乘法满足下列两条规则:
⑧
4
线性分组码的基本概念
线性空间的性质
零元素是唯一的
负元素是唯一的, - 唯一
关于0元素有
如果
如果
=0,那么k=0或=0.
5
线性分组码的基本概念
线性分组码定义
[n, k]线性分组码是GF(q)上的n维线性空间中的一个k维子空间。
线性分组码的基本特性:
线性结构。即如果 c1、c2 分别是信息序列 m1、m2的码字,则 c1+c2 必定是信息序列 m1+m2 的码字。
两码字C1和C2之间的距离d(C1, C2)必等于第三个码字C1+C2的汉明重量。
[n,k,d]线性分组码的最小距离等于非零码字的最小重量
6
线性分组码的基本概念
GF(2)上[n , k , d]线性分组码中, 任何两个码字C1, C2之间有如下关系:
w(C1+C2)=w(C1)+w(C2)-2w(C1·C2)
或
d(C1, C2)≤w(C1)+w(C2)
式中, C1·C2是两个码字的内积。
GF(2)上线性分组码任3个码字C1, C2, C3之间的汉明距离, 满足以下三角不等式
d(C1, C2)+d(C2, C3)≥d(C1, C3)
任何[n , k , d]线性分组码, 码字的重量或全部为偶数, 或者奇数重量的码字数等于偶数重量的码字数。
7
码的一致校验矩阵与生成矩阵
[n , k , d]分组码
在n 维线性空间Vn 中, 如何找出满足一定要求的, 有2k 个矢量组成的k 维线性子空间Vn , k 。
在满足给定条件(码的最小距离d或码率R)下, 如何从已知的k 个信息元求得r=n -k 个校验元。
8
码的一致校验矩阵与生成矩阵
码的生成矩阵( k 维线性子空间)
由于[n,k,d]线性分组码是一个k维线性空间。因此必可找到k个线性无关的矢量,能张成该线性空间。设
是k个线性无关的矢量,则对任意
,可有:
G称为该分组码的生成矩阵
9
码的一致校验矩阵与生成矩阵
例:一个[7, 3 ]码,m2 m1 m0 → c6 c5 c4 c3 c2 c1 c0 ,如果码字的生成规则为:
若用矩阵形式表示这些线性方程组, 则:
10