临沂大学数学与统计学院，山东 临沂

收稿日期：2021年2月8日；录用日期：2021年3月3日；发布日期：2021年3月10日

摘要

本文恰当地利用了二元[7, 4, 3]汉明码的校验矩阵构造了[10, 3, 5]二元线性码，并论述这一方法可以推广到其他元码的构造中。

关键词

线性码，汉明码，推广

The Construction of [10, 3, 5] Binary Linear Codes

Ying Liu, Shuai Niu, Juan Xu

School of Mathematics and Statistics, Linyi University, Linyi Shandong

Received: Feb. 8^th, 2021; accepted: Mar. 3^rd, 2021; published: Mar. 10^th, 2021

ABSTRACT

In this paper, we construct [10, 3, 5] binary linear codes by using the check matrix of [7, 4, 3] binary Hamming codes, and discuss that this method can be extended to the construction of other linear codes.

Keywords:Linear Code, Hamming Code, Extend

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

在 ${\text{F}}_q$ 上的线性码(或称线性分组码) C是线性空间 ${\text{F}}_q^n$ 中的子空间。特别地，当 $q=2$ 时，称为二元线性码。如果这个线性子空间的维数是k，则称C是一个 $\left[n,k\right]$ 码，其中n是码长，k是码的维数。对于线性码C，若又有 $d=d\left(C\right)=\min \left\{w\left(c\right),c\ne 0\in C\right\}$，即d是C中所有 $q^k-1$ 个非零码字中Hamming权的最小值，则记线性码C为 $\left[n,k,d\right]$ 码。设 $c_i=\left(c_{i1},c_{i2},\cdots ,c_{in}\right),i=1,2,\cdots ,k$ 是 ${\text{F}}_q$ 上的k个线性独立的码字，即构成C的一组基，这样，对于C中的每一个码字 $c=\left(c_1,c_2,\cdots ,c_n\right)$ 总存在k个在 ${\text{F}}_q$ 中的系数 $a_1,a_2,\cdots ,a_k$ 使 得 $c=\left(c_1,c_2,\cdots ,c_n\right)=\left(a_1,a_2,\cdots ,a_k\right)\left(\begin{array}{cccc}{c}_{11}& c_{12}& \cdots & c_{1n}\\ c_{21}& c_{22}& \cdots & c_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ c_{k1}& c_{k2}& \cdots & c_{kn}\end{array}\right)$。一个 $k\times n$ 矩阵为码C的生成矩阵，如果它的行向量构成C的一组基，通常用G来表示生成矩阵，若有 $G{H}^{\text{T}}=0$ 则H称为该码的校验矩阵 [1] [2]。

2. [10, 3, 5]二元线性码的构造

我们首先确定一个含有八个码字且能纠正2个错误位的码长应该是 $n\ge \text{10}$ 的。根据二元码的Plotkin界知，一个码长为9并且最小距离为5的二元码最多含有6个码字。设一个参数为 $\left(9,K,5\right)$ 的二元码C¹，由此再重新考虑一个新码 $C=\left\{\left(c_1,c_2,\cdots ,c_9,c_{10}\right)|\left(c_1,c_2,\cdots ,c_9\right)\in {\text{C}}^1,c_1+c_2+\cdots +c_9+c_{10}=0\right\}$，于是，新码C 的参数为 $\left(\text{10},K,\text{6}\right)$，由于 $\left[\frac{d}{2d-n}\right]=\left[\frac{6}{2\times 6-10}\right]=3$，从而 $K\le \text{2}\left[\frac{d}{2d-n}\right]=6$，于是我们可以确定一个含有八个码字且能纠正2个错误位的码字长度至少为10。

汉明码是一类非常重要的完全线性码，设 $m\ge \text{2}$，以 $H_m=\left(u_1,u_2,\cdots ,u_n\right)$ 为校验矩阵的q元线性码叫做汉明码，其中 $u_i,i=1,2,\cdots ,n$ 是 $F_q^m$ 中 $q^m-1$ 个非零向量的各等价类里面的代表向量，长度为m，每个等 价类里面恰有 $q-1$ 个向量。汉明码的参数为 $\left[n,k,d\right]=\left[\frac{q^m-1}{q-1},\frac{q^m-1}{q-1}-m,3\right]$，当 $q=2$ 时，二元汉明码的参数为 $\left[n,k,d\right]=\left[2^m-1,2^m-1-m,3\right]$，若又 $m=3$，此时 $\left[n,k,d\right]=\left[7,4,3\right]$ 且 $H_3=\left(u_1,u_2,\cdots ,u_7\right)=\left(\begin{array}{ccccccc}0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 1\\ 1& 0& 1& 0& 1& 0& 1\end{array}\right)$。

在校验矩阵 $H_3$ 中，我们发现向量的长度为7，每行向量的非零元个数为4，且两两向量相加的非零元个数是4，三个向量相加得到的向量非零个数亦是4。

我们要构造的二元线性码含有8个码字，信息元为三位，即

$\begin{array}{l}{m}_0=\left(0,0,0\right),m_1=\left(0,0,1\right),m_2=\left(0,1,0\right),m_3=\left(0,1,1\right),\\ m_{\text{4}}=\left(\text{1},\text{0},\text{0}\right),m_{\text{5}}=\left(\text{1},\text{0},\text{1}\right),m_{\text{6}}=\left(\text{1},\text{1},\text{0}\right),m_7=\left(1,1,1\right)\end{array}$

从中选取任意三个相互独立的向量与 $H_3$ 中的行向量共同组成[10, 3, 5]码的生成矩阵G。比如，我们选取 $m_1=\left(0,0,1\right),m_2=\left(0,1,0\right),m_4=\left(1,0,0\right)$ 并适当调整排列顺序得到系统码的生成矩阵，即生成矩阵 $G=\left(\begin{array}{c}{c}_1\\ c_2\\ c_3\end{array}\right)=\left(\begin{array}{cccccccccc}1& 0& 0& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 1& 0& 0& 1& 1\\ 0& 0& 1& 1& 0& 1& 0& 1& 0& 1\end{array}\right)=\left(I_3,H_3\right)$，其中 $c_1,c_2,c_3$ 为三个相互独立的码字且码重都为5。由 $k_1{c}_1+k_2{c}_2+k_3{c}_3,k_i=0,1$ 我们可以得到八个码字，即 $c_0=\left(0,0,0,0,0,0,0,0,0,0\right)$，$c_1=\left(1,0,0,0,0,0,1,1,1,1\right)$，$c_2=\left(0,1,0,0,1,1,0,0,1,1\right)$，$c_3=\left(0,0,1,1,0,1,0,1,0,1\right)$ 以及 $c_4=\left(1,1,0,0,1,1,1,1,0,0\right)$，$c_5=\left(1,0,1,1,0,1,1,0,1,0\right)$，$c_6=\left(0,1,1,1,1,0,0,1,1,0\right)$ 和 $c_7=\left(1,1,1,1,1,0,1,0,0,1\right)$，显然，构造出的码最小距离为5，可以检出4位错误并能纠正2位错误。

由于汉明码校验矩阵的形式，上述我们得到的构造方法可以推广到其他元码字的构造，比如 $q=3,m=3$，此时三元汉明码的校验矩阵为

$H_3=\left(u_1,u_2,\cdots ,u_{13}\right)=\left(\begin{array}{ccccccccccccc}1& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0& 1& 2& 1& 1& 2& 2\\ 0& 0& 1& 1& 2& 1& 2& 0& 0& 1& 2& 1& 2\end{array}\right)$

我们可以构造码长为13的三元线性码。

致谢

在学习和本论文的写作过程中，我们得到了许娟老师的悉心指导和帮助，在此向她表示感谢！

基金项目

山东临沂大学大学生创新创业训练计划项目编号X202010452128。

文章引用

刘 颖,牛 帅,许 娟. [10, 3, 5]二元线性码的构造
The Construction of [10, 3, 5] Binary Linear Codes[J]. 应用数学进展, 2021, 10(03): 651-653. https://doi.org/10.12677/AAM.2021.103070

参考文献