戈莱码

1. 简介

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

2. 二元戈莱码 $G_{24}$

2.1 定义

设 $\boldsymbol{G} = (\boldsymbol{I}_{12} | \boldsymbol{A})$，其中 $\boldsymbol{I}_{12}$ 是 $12 \times 12$ 的单位矩阵，

$$\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)$$

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

2.2 性质

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

令 $A_i$ 表示二元戈莱码 $G_{24}$ 中重量为 $i$ 的码字的数目，$0 \leq i \leq 24$。通过编程可以计算得：

$$A_0 = A_{24} = 1, A_8 = A_{16} = 759, A_{12} = 2576, A_{20} = 0$$

3. 二元戈莱码 $G_{23}$

3.1 定义

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

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

3.2 性质

• 定理六：二元戈莱码 $G_{23}$ 是完备码。

令 $A_i$ 表示二元戈莱码 $G_{23}$ 中重量为 $i$ 的码字的数目，$0 \leq i \leq 23$。通过编程可以计算得：

$$A_0 = A_{23} = 1, A_7 = A_{16} = 253, A_8 = A_{15} = 506, A_{11} = A_{12} = 1288$$

4. 三元戈莱码 $G_{12}$

4.1 定义

设 $\boldsymbol{G} = (\boldsymbol{I}_6 | \boldsymbol{B})$，其中 $\boldsymbol{I}_6$ 是 $6 \times 6$ 阶单位矩阵，

$$\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)$$

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

4.2 性质

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

令 $A_i$ 表示三元戈莱码 $G_{12}$ 中重量为 $i$ 的码字的数目，$0 \leq i \leq 12$。通过编程，可以计算得：

$$A_0 = 1, A_6 = 264, A_9 = 440, A_{12} = 24$$

5. 三元戈莱码 $G_{11}$

5.1 定义

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

5.2 性质

• 定理九：三元戈莱码 $G_{11}$ 是完备码。

令 $A_i$ 表示三元戈莱码 $G_{11}$ 中重量为 $i$ 的码字的数目，$0 \leq i \leq 11$。通过编程，可以计算得：

$$A_0 = 1, A_5 = A_6 = 132, A_{8} = 330, A_{9} = 110, A_{11} = 24$$

6. 实现

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

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 陈鲁生