[10, 3, 5]二元线性码的构造
The Construction of [10, 3, 5] Binary Linear Codes

作者: 刘 颖 , 牛 帅 , 许 娟 :临沂大学数学与统计学院,山东 临沂;

关键词: 线性码汉明码推广Linear Code Hamming Code Extend

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

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.

1. 引言

F q 上的线性码(或称线性分组码) C是线性空间 F q n 中的子空间。特别地,当 q = 2 时,称为二元线性码。如果这个线性子空间的维数是k,则称C是一个 [ n , k ] 码,其中n是码长,k是码的维数。对于线性码C,若又有 d = d ( C ) = min { w ( c ) , c 0 C } ,即d是C中所有 q k 1 个非零码字中Hamming权的最小值,则记线性码C为 [ n , k , d ] 码。设 c i = ( c i 1 , c i 2 , , c i n ) , i = 1 , 2 , , k F q 上的k个线性独立的码字,即构成C的一组基,这样,对于C中的每一个码字 c = ( c 1 , c 2 , , c n ) 总存在k个在 F q 中的系数 a 1 , a 2 , , a k 使 得 c = ( c 1 , c 2 , , c n ) = ( a 1 , a 2 , , a k ) ( c 11 c 12 c 1 n c 21 c 22 c 2 n c k 1 c k 2 c k n ) 。一个 k × n 矩阵为码C的生成矩阵,如果它的行向量构成C的一组基,通常用G来表示生成矩阵,若有 G H T = 0 则H称为该码的校验矩阵 [1] [2]。

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

我们首先确定一个含有八个码字且能纠正2个错误位的码长应该是 n 10 的。根据二元码的Plotkin界知,一个码长为9并且最小距离为5的二元码最多含有6个码字。设一个参数为 ( 9 , K , 5 ) 的二元码C1,由此再重新考虑一个新码 C = { ( c 1 , c 2 , , c 9 , c 10 ) | ( c 1 , c 2 , , c 9 ) C 1 , c 1 + c 2 + + c 9 + c 10 = 0 } ,于是,新码C 的参数为 ( 10 , K , 6 ) ,由于 [ d 2 d n ] = [ 6 2 × 6 10 ] = 3 ,从而 K 2 [ d 2 d n ] = 6 ,于是我们可以确定一个含有八个码字且能纠正2个错误位的码字长度至少为10。

汉明码是一类非常重要的完全线性码,设 m 2 ,以 H m = ( u 1 , u 2 , , u n ) 为校验矩阵的q元线性码叫做汉明码,其中 u i , i = 1 , 2 , , n F q m q m 1 个非零向量的各等价类里面的代表向量,长度为m,每个等 价类里面恰有 q 1 个向量。汉明码的参数为 [ n , k , d ] = [ q m 1 q 1 , q m 1 q 1 m , 3 ] ,当 q = 2 时,二元汉明码的参数为 [ n , k , d ] = [ 2 m 1 , 2 m 1 m , 3 ] ,若又 m = 3 ,此时 [ n , k , d ] = [ 7 , 4 , 3 ] H 3 = ( u 1 , u 2 , , u 7 ) = ( 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 )

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

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

m 0 = ( 0 , 0 , 0 ) , m 1 = ( 0 , 0 , 1 ) , m 2 = ( 0 , 1 , 0 ) , m 3 = ( 0 , 1 , 1 ) , m 4 = ( 1 , 0 , 0 ) , m 5 = ( 1 , 0 , 1 ) , m 6 = ( 1 , 1 , 0 ) , m 7 = ( 1 , 1 , 1 )

从中选取任意三个相互独立的向量与 H 3 中的行向量共同组成[10, 3, 5]码的生成矩阵G。比如,我们选取 m 1 = ( 0 , 0 , 1 ) , m 2 = ( 0 , 1 , 0 ) , m 4 = ( 1 , 0 , 0 ) 并适当调整排列顺序得到系统码的生成矩阵,即生成矩阵 G = ( c 1 c 2 c 3 ) = ( 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 ) = ( I 3 , H 3 ) ,其中 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 = ( 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ) c 1 = ( 1 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 ) c 2 = ( 0 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 ) c 3 = ( 0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 ) 以及 c 4 = ( 1 , 1 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 0 ) c 5 = ( 1 , 0 , 1 , 1 , 0 , 1 , 1 , 0 , 1 , 0 ) c 6 = ( 0 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 0 ) c 7 = ( 1 , 1 , 1 , 1 , 1 , 0 , 1 , 0 , 0 , 1 ) ,显然,构造出的码最小距离为5,可以检出4位错误并能纠正2位错误。

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

H 3 = ( u 1 , u 2 , , u 13 ) = ( 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 )

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

致谢

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

基金项目

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

文章引用: 刘 颖 , 牛 帅 , 许 娟 (2021) [10, 3, 5]二元线性码的构造。 应用数学进展, 10, 651-653. doi: 10.12677/AAM.2021.103070

参考文献

[1] 冯良贵, 吴新文, 著. 代数几何码[M]. 北京: 科学出版社, 2000.

[2] 冯克勤, 著. 纠错码的代数理论[M]. 北京: 清华大学出版社, 2006.

分享
Top