第3章 线性分组码

第3章 线性分组码

第3章 线性分组码

第3章 线性分组码 章3.1 线性分组码的基本概念 3.2 码的一致校验矩阵与生成矩阵 3.3 伴随式与标准阵列及其它译码 3.4 线性码的覆盖半径 3.5 由一个已知码构造新码的简单方法 3.6 用多个已知码构造新码的方法 3.7 线性码的重量分布与译码错误概率 3.8 线性码的纠错能力1

第3章 线性分组码

第3章 线性分组码

3.1 线性分组码的基本概念线性空间是一个非空集合, 是一个数域, 在集合V 设V 是一个非空集合 P 是一个数域 在集合 中定 义了一种代数运算，叫做加法 即对在V 加法: 义了一种代数运算，叫做加法 即对在 中都存在唯 记为： 一的一个元素λ, 一的一个元素 ，称λ为α与β的和，记为： 的 λ = α + β ;在P与V的元素之间还定义了一种运算， 的元素之间还定义了一种运算， 与 的元素之间还定义了一种运算 叫做数量乘法 数量乘法： 叫做数量乘法：即 α ∈ V , k ∈ P , 中都存在唯一的一个元素δ与它们对应 在V中都存在唯一的一个元素 与它们对应，称δ为 中都存在唯一的一个元素 与它们对应， 为 k与α 的数量乘积，记为 δ = kα . 如果加法和数量乘法 数量乘积， 还满足下述规则，则称V 为数域P上的线性空间： 上的线性空间 还满足下述规则，则称 为数域 上的线性空间：

第3章 线性分组码

第3章 线性分组码

3.1 线性分组码的基本概念加法满足下列四条规则： 加法满足下列四条规则： α , β , γ ∈ V ① α + β = β +α ② (α + β ) + γ = α + ( β + γ ) 中有一个元素0, ③ 在V中有一个元素 ，对 α ∈ V , 有 α + 0 = α 中有一个元素 都有V中的一个元素 中的一个元素β ④ 对 α ∈V , 都有 中的一个元素β,使得 具有这个性质的元素0称为 称为V的零元素) (具有这个性质的元素 称为 的零元素)

α + β = 0 ;(β称为 α 的负元素) 负元素)

第3章 线性分组码

第3章 线性分组码

3.1 线性分组码的基本概念数量乘法满足下列两条规则 : ⑤ 1α = α ⑥ k ( lα ) = ( kl )α 数量乘法与加法满足下列两条规则： 数量乘法与加法满足下列两条规则： ⑦ ( k + l )α = kα + lα ⑧ k (α + β ) = kα + k β

第3章 线性分组码

第3章 线性分组码

3.1 线性分组码的基本概念线性空间的性质零元素是唯一的 负元素是唯一的， 负元素是唯一的， α ∈ V 关于0元素有 关于 元素有 0α = 0, k 0 = 0, ( 1)α = α , - α唯一

k (α β ) = kα k β如果

如果 kα =0,那么 =0或 α =0. ,那么k= 或

第3章 线性分组码

第3章 线性分组码

3.1 线性分组码的基本概念 线性分组码定义[n, k]线性分组码是GF(q)上的n维线性空间中的一个k 维子空间。 线性分组码的基本特性：线性结构。即如果 c1、c2 分别是信息序列 m1、m2的码字， 则 c1+c2 必定是信息序列 m1+m2 的

码字。 两码字C1和C2之间的距离d(C1, C2)必等于第三个码字C1+C2 的汉明重量。 [n,k,d]线性分组码的最小距离等于非零码字的最小重量

d m = minw(Ci )Ci ∈[ n , k ]

第3章 线性分组码

第3章 线性分组码

3.1 线性分组码的基本概念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]线性分组码， 码字的重量或全部为 偶数， 或者奇数重量的码字数等于偶数重量的码字数。

第3章 线性分组码

第3章 线性分组码

3.2 码的一致校验矩阵与生成矩阵[n , k , d]分组码 在n 维线性空间Vn 中， 如何找出满足一定要求的， 有 2k 个矢量组成的k 维线性子空间Vn , k 。 在满足给定条件(码的最小距离d或码率R)下， 如何从 已知的k 个信息元求得r=n -k 个校验元。

第3章 线性分组码

第3章 线性分组码

3.2 码的一致校验矩阵与生成矩阵码的生成矩阵( k 维线性子空间)由于[n,k,d]线性分组码是一个k维线性空间。因此必 可找到k个线性无关的矢量，能张成该线性空间。设 C 1 , C 2 , K C k 是k个线性无关的矢量，则对任意 C ,可有：

C = m1C 1 + m 2 C 2 + K + m k C k C1 C2 = (m1 , m 2 , K m k ) M C k G称为该分组码的生成矩阵 = mG9

第3章 线性分组码

第3章 线性分组码

3.2 码的一致校验矩阵与生成矩阵例：一个[7, 3 ]码，m2 m1 m0 → c6 c5 c4 c3 c2 c1 c0 ,如 果码字的生成规则为：

若用矩阵形式表示这些线性方程 组， 则：

C = [ m2 m1

1 0 0 1 1 1 0 m0 ] 0 1 0 0 1 1 1 0 0 1 1 1 0 1

c6 = m2 c = m1 5 c4 = m0 m0 c3 = m2 + c = m + m + m 2 1 0 2 c1 = m2 + m1 c = m1 + m0 010

第3章 线性分组码

第3章 线性分组码

3.2 码的一致校验矩阵与生成矩阵则矩阵

1 0 0 1 1 1 0 G = 0 1 0 0 1 1 1 0 0 1 1 1 0 1 就是该[7, 3 ]码的生成矩阵。 注： 1) 生成矩阵 中的每一行都是一个码字 生成矩阵G中的每一行都是一个码字 2) 任意 个线性独立的码字都可以作为生成矩阵 任意k个线性独立的码字都可以作为生成矩阵 3) 给定一个 给定一个[n,k,d]线性分组码，其生成矩阵可有多个 线性分组码， 线性分组码11

第3章 线性分组码

第3章 线性分组码

3.2 码的一致校验矩阵与生成矩阵码的校验矩阵(求r=n -k 个校验元)c n 1 c n 2 K c n k c n k 1 c n k 2 K c 0 144424443 1444 24444 4 4 4 3k个信息位 n k个校验位

n-k个校验位可用k个已知的信息位表示出来

cn k 1 =hn k 1,n 1 cn 1 + hn k 1,n

2 cn 2 +K+ hn k 1,n k cn k c n k 2 =hn k 2,n 1 cn 1 + hn k 2,n 2 cn 2 +K+ hn k 2,n k cn k L c0 =h0,n 1 cn 1 + h0,n 2 cn 2 +K+ h0,n k cn k 12

第3章 线性分组码

第3章 线性分组码

3.2 码的一致校验矩阵与生成矩阵 hn k 1,n 1 cn 1 +hn k 1,n 2 cn 2 +K+hn k 1,n k cn k +cn k 1 =0 h n k 2,n 1 cn 1 +hn k 2,n 2 cn 2 +K+hn k 2,n k cn k +cn k 2 =0 M h0,n 1 cn 1 +h0,n 2 cn 2 +K+h0,n k cn k +c0 =0 0 0 K c n 1 0 hn k 1, n 1 K hn k 1, n k 1 1 0 K c n 2 0 hn k 2, n 1 K hn k 2, n k 0 K M = M K K K K K h K h01, n k 0 0 K 1 c 0 0 0, n 1 44444444 44444444 1 2 3

校验矩阵H与任意一个码字之积为零，因此有 校验矩阵 T T

校验矩阵 ( n k行，n列)

H G = 0

第3章 线性分组码

第3章 线性分组码

3.2 码的一致校验矩阵与生成矩阵 例 1 c3 = 1 c6 + 0 c5 + 1 c4 1 c = 1 c + 1 c + 1 c 2 6 5 4 1 c1 = 1 c6 + 1 c5 + 0 c4 1 c0 = 0 c6 + 1 c5 + 1 c4 c6 +c4+c3  c6+c5+c4 +c2 c6+c5 +c1  c5+c4 +c0 =0 =0 =0 =014

第3章 线性分组码

第3章 线性分组码

3.2 码的一致校验矩阵与生成矩阵

1 1 H = 1 0

0 1 1 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 =0 =0 =0 =015

c6 +c4+c3  c6+c5+c4 +c2 c6+c5 +c1  c5+c4 +c0

第3章 线性分组码

第3章 线性分组码

3.2 码的一致校验矩阵与生成矩阵系统码、对偶码和缩短码系统码 若信息组以不变的形式在码组的任意k 位(通常在最 前面： cn -1, cn -2, …, cn -k )中出现的码称为系统 码，生成矩阵和校验矩阵应该具有性质

k 位信息位

n -k 位校验位

G = [I k P ]H = P T I n kT

P G H = [I k P ] =0 I n k 16

[

]

第3章 线性分组码

第3章 线性分组码

3.2 码的一致校验矩阵与生成矩阵[7, 3, 4]码

1 0 0 1 1 1 0 G = 0 1 0 0 1 1 1 = [I 3 P ] 0 0 1 1 1 0 1 1 1 H = 1 0 0 1 1 0 0 0 1 1 0 1 0 0 = PT I 4 1 0 0 0 1 0 1 1 0 0 0 1

[

]17

第3章 线性分组码

第3章 线性分组码

3.2 码的一致校验矩阵与生成矩阵对偶码 设C是[n , k , d]码， 则它的对偶码C⊥是C⊥={x∈V n , (n -k ); 对所有y∈C使x·y=0}

式中， x·y为x与y的内积。由G生成的[n, k, d]码C与由H生成的[n, n-k, d]码 C⊥互为对偶码。

H G = 0T

T

第3章 线性分组码

第3章 线性分组码

3.2 码的一致校验矩阵与生成矩阵缩短码 缩短码是k 维子空间Vn,k 中取前i位均为0的码字 组成的一个子集,该子集组成了一个[n –i, k -i] 分组码。

[ n –i, k -i]缩短码的纠错能力至少与原[n, k ]码 相同。 [n –i, k -i]缩短码是[n , k ]码缩短i位得到的， 因而码率R 比原码要小， 但纠错能力不一定比原码 强。

本文来源：https://www.bwwdw.com/article/f81m.html