戈莱码

1. 简介

19491949 年,Marcel Golay 给出了四个线性码,分别记为 G23,G24,G11,G12G_{23}, G_{24}, G_{11}, G_{12},现在称这四个线性码为戈莱码。G23G_{23}G24G_{24} 为二元线性码,G11G_{11}G12G_{12} 是三元线性码。无论从理论还是实用的角度看,戈莱码都是一类重要的线性码。

2. 二元戈莱码 G24G_{24}

2.1 定义

G=(I12A)\boldsymbol{G} = (\boldsymbol{I}_{12} | \boldsymbol{A}),其中 I12\boldsymbol{I}_{12}12×1212 \times 12 的单位矩阵,

A=(011111111111111011100010110111000101101110001011111100010110111000101101110001011011100010110111100101101110101011011100110110111000101101110001)\boldsymbol{A}=\left(\begin{array}{llllllllllll} 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \end{array}\right)

G\boldsymbol{G} 为生成矩阵的二元 [24,12][24, 12] 线性码称为二元戈莱码 G24G_{24}

2.2 性质

  • 定理一:二元戈莱码 G24G_{24} 是自对偶的,即 G24=G24G_{24}^\bot = G_{24}
  • 定理二(AI12)(\boldsymbol{A} | \boldsymbol{I}_{12}) 也是二元戈莱码 G24G_{24} 的生成矩阵,其中 A\boldsymbol{A} 同定义中的矩阵。
  • 定理三:二元戈莱码 G24G_{24} 中每个码字的重量都能被 44 整除。
  • 定理四:二元戈莱码 G24G_{24} 没有重量为 44 的码字。
  • 定理五:二元戈莱码 G24G_{24} 是一个 [24,12,8][24, 12, 8] 线性码。

AiA_i 表示二元戈莱码 G24G_{24} 中重量为 ii 的码字的数目,0i240 \leq i \leq 24。通过编程可以计算得:

A0=A24=1,A8=A16=759,A12=2576,A20=0A_0 = A_{24} = 1, A_8 = A_{16} = 759, A_{12} = 2576, A_{20} = 0

3. 二元戈莱码 G23G_{23}

3.1 定义

将二元戈莱码 G24G_{24} 的每个码字的最后一个分量去掉,得到一个新的二元码,称之为二元戈莱码 G23G_{23}。不难看出,G23G_{23} 是一个二元 [23,12,7][23, 12, 7] 线性码。

G24G_{24} 的所有码字排列成一个 212×242^{12} \times 24 阶矩阵,其中每一行是一个码字。可以证明,去掉这个矩阵中的任意一列所得到的二元 [23,12,7][23, 12, 7] 线性码是相互等价的。另外,二元戈莱码 G24G_{24} 也可以通过二元戈莱码 G23G_{23} 增加一个奇偶校验位得到。

3.2 性质

  • 定理六:二元戈莱码 G23G_{23} 是完备码。

AiA_i 表示二元戈莱码 G23G_{23} 中重量为 ii 的码字的数目,0i230 \leq i \leq 23。通过编程可以计算得:

A0=A23=1,A7=A16=253,A8=A15=506,A11=A12=1288A_0 = A_{23} = 1, A_7 = A_{16} = 253, A_8 = A_{15} = 506, A_{11} = A_{12} = 1288

4. 三元戈莱码 G12G_{12}

4.1 定义

G=(I6B)\boldsymbol{G} = (\boldsymbol{I}_6 | \boldsymbol{B}),其中 I6\boldsymbol{I}_66×66 \times 6 阶单位矩阵,

B=(011111101221110122121012122101112210)\boldsymbol{B}=\left(\begin{array}{llllll} 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 2 & 2 & 1 \\ 1 & 1 & 0 & 1 & 2 & 2 \\ 1 & 2 & 1 & 0 & 1 & 2 \\ 1 & 2 & 2 & 1 & 0 & 1 \\ 1 & 1 & 2 & 2 & 1 & 0 \end{array}\right)

G\boldsymbol{G} 为生成矩阵的三元 [12,6][12, 6] 线性码称为三元戈莱码 G12G_{12}

4.2 性质

  • 定理七:三元戈莱码 G12G_{12} 是自对偶的,即 G12=G12G_{12}^\bot = G_{12}
  • 定理八:三元戈莱码 G12G_{12} 是一个三元 [12,6,6][12, 6, 6] 线性码。

AiA_i 表示三元戈莱码 G12G_{12} 中重量为 ii 的码字的数目,0i120 \leq i \leq 12。通过编程,可以计算得:

A0=1,A6=264,A9=440,A12=24A_0 = 1, A_6 = 264, A_9 = 440, A_{12} = 24

5. 三元戈莱码 G11G_{11}

5.1 定义

将三元戈莱码 G12G_{12} 的每个码字的最后一个分量去掉,得到一个新的三元线性码,称之为三元戈莱码 G11G_{11}。不难看出,G11G_{11} 是一个三元 [11,6,5][11, 6, 5] 线性码。

5.2 性质

  • 定理九:三元戈莱码 G11G_{11} 是完备码。

AiA_i 表示三元戈莱码 G11G_{11} 中重量为 ii 的码字的数目,0i110 \leq i \leq 11。通过编程,可以计算得:

A0=1,A5=A6=132,A8=330,A9=110,A11=24A_0 = 1, A_5 = A_6 = 132, A_{8} = 330, A_{9} = 110, A_{11} = 24

6. 实现

计算戈莱码的码字重量分布代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import os
import numpy as np
from itertools import combinations, product


G11 = np.array(
[[1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1],
[0, 1, 0, 0, 0, 0, 1, 0, 1, 2, 2],
[0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 2],
[0, 0, 0, 1, 0, 0, 1, 2, 1, 0, 1],
[0, 0, 0, 0, 1, 0, 1, 2, 2, 1, 0],
[0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 1]], dtype=np.int64
)
G12 = np.array(
[[1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[0, 1, 0, 0, 0, 0, 1, 0, 1, 2, 2, 1],
[0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 2, 2],
[0, 0, 0, 1, 0, 0, 1, 2, 1, 0, 1, 2],
[0, 0, 0, 0, 1, 0, 1, 2, 2, 1, 0, 1],
[0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 1, 0]], dtype=np.int64
)
G23 = np.array(
[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0]], dtype=np.int64
)
G24 = np.array(
[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1]], dtype=np.int64
)

q = 2
G = G23

cnt = np.zeros(G.shape[1]+1, dtype=np.int64)
coefs = range(q)
idxs = range(G.shape[0])
for coef in product(coefs, repeat=G.shape[0]):
val = np.zeros(G.shape[1], dtype=np.int64)
for i in range(len(coef)):
val = (val + (coef[i]*G[i])) % q

print(val)
cnt[np.count_nonzero(val)] += 1

for i in range(G.shape[1]+1):
print("A{} = {}".format(i, cnt[i]))

附录

  • 《编码理论基础》by 陈鲁生

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!