汉明码

1. 简介

汉明码是一种完备的线性码,具有很多很好的性质,而且其译码方法也非常简洁高效。

2. 汉明码

2.1 二元汉明码

  • 定义一:设 rr 是一个正整数,设 H\boldsymbol{H} 是一个 r×(2r1)r \times (2^r - 1) 阶矩阵,其列向量由 V(r,2)V(r, 2) 中的所有不同的非零向量组成。以 H\boldsymbol{H} 为校验矩阵的线性码称为二元汉明码,记为 Ham(r,2)\mathrm{Ham}(r, 2)

    显然,二元汉明码 Ham(r,2)\mathrm{Ham}(r, 2) 的码长为 n=2r1n = 2^r - 1,维数为 k=nr=2r1rk = n - r = 2^r - 1 - rrr 为校验位的数目。在等价意义下,Ham(r,2)\mathrm{Ham}(r, 2) 是惟一的。

2.2 多元汉明码

  • 定义二:设 rr 是一个正整数,对任意 αV(r,q)\boldsymbol{\alpha} \in V(r, q),令 Vα={λα0λGF(q)}V_{\boldsymbol{\alpha}} = \{\lambda \boldsymbol{\alpha} | 0 \neq \lambda \in GF(q)\}。不难发现,对任意 α,βV(r,q)\boldsymbol{\alpha}, \boldsymbol{\beta} \in V(r, q)VαV_{\boldsymbol{\alpha}}VβV_{\boldsymbol{\beta}} 或者相同或者不相交。显然,当 α=0\boldsymbol{\alpha} = 0 时,Vα=1|V_{\boldsymbol{\alpha}}| = 1;当 α0\boldsymbol{\alpha} \neq 0 时,Vα=q1|V_{\boldsymbol{\alpha}}| = q - 1。因此,存在非零的 α1,α2,,αnV(r,q)\boldsymbol{\alpha}_1, \boldsymbol{\alpha}_2 , \cdots, \boldsymbol{\alpha}_n \in V(r, q),其中 n=qr1q1n = \frac{q^r - 1}{q - 1},使得 Vα1,Vα2,,VαnV_{\boldsymbol{\alpha}_1}, V_{\boldsymbol{\alpha}_2}, \cdots, V_{\boldsymbol{\alpha}_n} 互不相交,并且

    i=1nVαi=V(r,q){0}\bigcup_{i=1}^n V_{\boldsymbol{\alpha}_i} = V(r, q) - \{\boldsymbol{0}\}

    分别从 Vα1,Vα2,,VαnV_{\boldsymbol{\alpha}_1}, V_{\boldsymbol{\alpha}_2}, \cdots, V_{\boldsymbol{\alpha}_n} 中任取一个向量作为列向量构成一个 r×nr \times n 阶的矩阵 H\boldsymbol{H}。以 H\boldsymbol{H} 为校验矩阵的线性码称为 qq 元汉明码,记为 Ham(r,q)\mathrm{Ham}(r, q)

    qq 元汉明码 Ham(r,q)\mathrm{Ham}(r, q) 的码长为 n=qr1q1n = \frac{q^r - 1}{q-1},维数为 k=nr=qr1q1rk = n - r = \frac{q^r - 1}{q - 1} - rrr 为校验位的数目。对于给定的 rrqq,由于 H\boldsymbol{H} 中的列向量可以任意排列,并且 VαiV_{\boldsymbol{\alpha}_i} 中的向量可以任意选取,1in1 \leq i \leq n,所以 qq 元汉明码 Ham(r,q)\mathrm{Ham}(r, q) 指的是一类等价的码中的任意一个。在等价意义下,Ham(r,q)\mathrm{Ham}(r, q) 是惟一的。

不难看出,对任意 0αV(r,q)0 \neq \boldsymbol{\alpha} \in V(r, q)VαV_{\boldsymbol{\alpha}} 中恰好有一个向量,其第一个非零分量为 11。因此,一种写出 Ham(r,q)\mathrm{Ham}(r, q) 的校验矩阵的简单方法就是:按字典排序写出 V(r,q)V(r, q) 中所有第一个非零分量为 11 的非零向量

3. 性质

  • 定理一qq 元汉明码 Ham(r,q)\mathrm{Ham}(r, q) 是一个完备的 qq[n,nr,3][n, n-r, 3] 线性码,其中 n=qr1q1n = \frac{q^r - 1}{q - 1}

  • 定理二:设 r2r \geq 2 是一个整数,qq 是一个素数的幂次方。如果 n=qr1q1n = \frac{q^r - 1}{q - 1},则 Aq(n,3)=qnrA_q(n, 3) = q^{n-r}

    Aq(n,d)A_q(n, d) 表示在所有 qq(n,M,d)(n, M, d) 码中,MM 的最大值。

4. 译码方法

由于 Ham(r,q)\mathrm{Ham}(r, q) 是一个完备的 qq[n,nr,3][n, n-r, 3] 线性码,其中 n=qr1q1n = \frac{q^r - 1}{q-1}Ham(r,q)\mathrm{Ham}(r, q) 至多可以纠正一个错误,所以 V(n,q)V(n, q) 中所有重量不大于 11 的向量恰好就是 Ham(r,q)\mathrm{Ham}(r, q) 的标准阵中的所有陪集代表元。

qq 元汉明码 Ham(r,q)\mathrm{Ham}(r, q) 的译码过程描述如下:

  1. 对于在信道接收端接收到的向量 y\boldsymbol{y},计算其伴随 S(y)=yHS(\boldsymbol{y}) = \boldsymbol{y} \boldsymbol{H}^\top

  2. 如果 S(y)=0S(\boldsymbol{y}) = \boldsymbol{0},则认为没有错误发生,y\boldsymbol{y} 就是发送的码字;

  3. 如果 S(y)0S(\boldsymbol{y}) \neq \boldsymbol{0},则 S(y)=bHi0S(\boldsymbol{y}) = b\boldsymbol{H}_i^\top \neq \boldsymbol{0},其中 0bGF(q),1in0 \neq b \in GF(q), 1 \leq i \leq n。此时,y\boldsymbol{y} 中第 ii 个分量发生错误,y\boldsymbol{y} 被译为码字 yαi\boldsymbol{y} - \boldsymbol{\alpha}_i,其中

    αi=00i1b00n\boldsymbol{\alpha}_{i}=\overbrace{\underbrace{0 \cdots 0}_{i-1} b 0 \cdots 0}^{n}

    也就是说,将 y\boldsymbol{y} 的第 ii 个分量减去 bb 所得到的向量就是 y\boldsymbol{y} 译成的码字。

5. 对偶码

5.1 二元汉明码的对偶码

二元汉明码 Ham(r,2)\mathrm{Ham}(r, 2) 的对偶码有时也称为极长码单纯码,记为 Σr\Sigma_rΣr\Sigma_r 的生成矩阵(也即 Ham(r,2)\mathrm{Ham}(r, 2) 的校验矩阵)记为 Gr\boldsymbol{G}_rΣr\Sigma_r 是一个二元 [2r1,r][2^r-1, r] 线性码。

  • 定理三:在二元汉明码 Ham(r,2)\mathrm{Ham}(r, 2) 的对偶码 Σr\Sigma_r 中,任意一个非零码字的重量都是 2r12^{r-1},并且任意两个不同码字之间的距离都等于 2r12^{r-1}

附录

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

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