（应用数学专业论文）二元golay码的构造.pdf

三垄鱼生! 芷璺塑塑造 二元g o l a y 码的构造 研究生：祝杰 指导教师：薰学东 学科专业：庶用数学 撩簧二元b l 姆羁是= 冤壤土难一豹 平慝多绸镬完备码，圜魏，分辑二元g 。1 8 y 磅 的特点，利用码的有关知识，缭出二元g o l a y 筠静构造方法具有重要豹壤论意义和实 际意义 首先，我们回顾了硝的有关定义及其性质，然后讨论了二元g o l a y 码的基本性 质 其次，我们总结了国王五鞠糯证g 码，p 8 l e y 艇酶，q r 羁，h e a c o d e 码和字典序最小 = 嚣疆擒造二元g | 0 1 8 y 稻豹方法+ 最后，证明了由一个s t e i n e x 系s ( 5 ，8 ，2 4 ) 可以构造出一个= 元g o l 姆码，并证明 了构造二元g o l a y 码和构造s t e i n e r 系s ( 5 ，8 ，2 4 ) 怒等价的 燕键词二元g o l a y 码；s t e i n e r 系；h a m m i n g 码；p a l e y 矩阵；q r 码 1 1 弓l 言 对予弱麓骥究，志羲燕对羁魏参数迸卷灌谂。鹞弱参数主要惫攒：褐长，羁瑗藐 达到的码的数目上下界，碣的极小距离和极小鬟嚣等码字的数目制约这一个码所 能传递的信息的容量，而粥的极小距离与码的纠锚和检错能力有很大的关系因此 对予码字数目的上下界的估计以及码的极小璧嫩和极小距离的讨论，引超许多学者 的必趣也取得了较多的成聚 二元g 。l a y 码鎏3 ，1 2 ，镌戆球毽半径帮覆麓半径稿等，宅满足h a m m i n 9 3 睐包 羧，窕是= 元壤土唯一麴嚣平氖多绸错完备鹦溺诧，分辑二元；c o l a y 鞴的籍点，剥 用码的有关知识，给出二元g o l a y 码的构造方法具有重要的理论意义和实际意义 = 鼐g o l a y 码【2 3 ，1 2 ，7 】被记为妒2 3 ，而扩充二元g o l 8 y 码【2 4 ，1 2 ，8 被i 己为妒2 4 为方便 起见，以下把扩充二元g o l a y 码也称为二元g o l 蚶码。由于_ - _ 元g o l a # r q 妒2 4 有较大 蛹爨同构群，所| 三 它的对称性更好。文1 1 ，2 ，3 ，4 】融经讨论了由h a m r n i n g 码，p 啦e y 矩 黪，q 琢鼹，嚣e x 盎c o d e 嚣譬典穿最小二元羁拣选二嚣g 蘸a y 玛。文l l ，2 ； 熟谖明了壶二 多黾g o l 8 源可稳戒s t e i n e r 系s ( 5 ，8 ，2 4 ) ，探讨憝喾由一母 s t e i n e r 系s ( 5 ，8 ，2 4 ) 胃秘构 造出一个二元g o t a y 码就是个值得研究的问麒，本论文完满地解决了选一问题，并 诞明了构造二元g o l a y 码和构造s t e i n e z 系s ( s ，8 2 4 ) 是等价的 本论文的第二章酋先简要回顾了码的有必定义及其性质，讨论了= 元g o l a y 码 的基本性质。 在薰三章孛我娥滚入臻窕骞关二元g 蘸辫戮熬鞠逢。羞走慈缝了蠡h a m m i n 蕊， p a e y 矩阵, q r 羁，珏e x o d e 码帮字典序最小二辩褥构造二元g o l 8 y 翳豹方法然后 诚明了由一个s t e i n e r 系s ( s ，8 ，2 4 ) 可以构造出一个二元g o l a y 码，井证明了构造二 鼐g o l a y 码和构造：s t e i n e r ：瓶s ( 5 ，8 ，2 4 ) 是等价的 本论文未加说明的符号与术语可参考文献f l ，2 】 2 三垄g ! ! ! 翌竺塑塑兰 2 预备知识 本章第一节简要回顾了码的有关定义第二节阐述了二元g o l a y 码的定义及其 基本性质，并对某些性质做了简要的证明 2 1 码的有关定义 关于码的有关定义在文献 1 中有详细的阐述，这里为了保持论文完整方便阅 读，我们将主要的定义写入这一节详细内容参见f 1 1 定义2 1 1 【1 l 在f 口上的线性码( 或线性分组码) c 是线性空间露中的一个子空 间，如果这个线性子空间的维数是k ，则称c 是一个【n ，纠码，n 是码长，是码的维数 如果h ，叫线性码c 任意两个码字的最小h m m i n g 距离为d ，则记此线性码为| n ，k ，硼 若口= 2 ，则称c 为二元码 定义2 1 2 【1 l 码g f ( 2 ) 上的n 维向量空间k 的维线性子空间k 称为分组长 为n ，信息位为k 的2 元线性分组码，简称2 元线性码或2 元h ，剐码 定义2 1 3 【1 l 设c 是长为竹的线性码，a i 是重量为i 的码字的个数，则a ) = a 称为c 的重量计数子 i = 0 定义2 1 4 1 1 】 设c 是一个h ，叫线性码，则h ，n 一叫码c 1 = z | 。k 且v c ，( z ，y ) = o ) 称为c 的对偶码( 或正交码) 当g = c 1 时，我们称g 是自对偶码 定义2 1 5 【1 l 设毒q “，可q ”，则碉日釉距离d ( 章，国定义为d ( z ，刃= i i l l 墨 i n ，鼽) 1 定义2 1 6 【1 】 童的重量叫( 定义为 ( 回= d ( 富，西 定义2 1 7 1 1 】 一个非平凡码c 的极小距离是m 饥 d 喊回l z c ，矿c ，量 讲码c 的极小重量是m 饥 ( 回博c ，孑田 定义2 1 8 f 1 】 设g 是f 口上的一个长为 的码，则我们定义码a 的扩充码百为虿= ( c 1 ，c 2 ，r ，c 。，岛+ i ) i ( c i ，c 2 j 一，) q q = o ) 定义2 1 9 1 1 l 设口，巴是码字，如果g 可由一个固定的符号位置的置换作用 在口的所有码字上而得到我们称这种码是等价的 3 三垄鱼! ! 塑璺塑塑造 定义2 1 _ 1 0 f 1 】 在r 中洳果q 是偶数，那么每个元素都是平方元浊果q 是奇数， 郑么最禽寄妇一1 ) 2 个非零平方元和( 窖一1 ) 2 个非平方元在蜀中是平方的那些 整数k ( 1 k 茎p 1 ) 邋鬻稼为罄匆豹二次裂余。是二次剩余当显双瓷# 。) 雎i 1 r o o dp ) 定义2 1 _ i i l l 】 一个极小距离为2 e + 1 的碣g q ”称为完全码，如果每个z q ”都恰与一个码字之间的距离se 定义2 1 1 2 1 1 l设x 鼹一个 元集合，它的笼索称为点或品种，t 一设计是x 的 元 子集合斡集体( k 元t - 集会称为区组) ，并且x 的镣个t 元子集合都包含农天个区组里。 换匈话说，宅霆一个瓢口令久孛逸袋委员会熬集会，每令委员会毽售女令大，经t 个天一 起在 个委员会中，我们称它为一扣，k ， ) 设计 p = ( ；l i ：1 ) g 的姆一行都有重量兰0 ( r o o d4 】g 的任意两行内积为0 这隐含着a 的任意行的线 性缝合的重量都是eo ( m o a 4 】观察，然居诞明g 的报多行的线性结含的薰量至少 为8 考虑由g 生成钓= 冗码，称它为轨4 - 潮减任一位得到一个二元 2 3 ，l2 1 码，它的 最小距离至少为7 ，这个距离不能再大了周为我们知道，若g 是一个的究金码，则它 的e 应该满足e = 3 事实上，l p 0 3 就是一个完全码 对( 2 3 ，1 2 ，7 ) g o l a y 码扩展一位则也得到( 2 4 1 2 ，8 ) 扩展自对偶g o l a y 码 4 二元g o l a y 码的构造 引理2 2 1 【2 1 伽4 是白对偶的，即妒2 4 = 妒矗 证 如果订，馄g 的行，那么 t 砩= o ( m o d2 ) 因此g 的每行都是正交 的忱4c 妒是但g 的秩是1 2 所以妒孔的维数也是1 2 所以妒2 4 = 妒矗 引理2 2 2 【2 】 妒2 4 的每个码字的重量可被4 整除 引理2 2 3 1 2 j 妒2 4 没有重量为4 和2 0 的码字 引理2 2 4 【2 】 如果c 是二元码，并且长为2 4 ，i g l = 2 ”，m i nd = 8 ，而且如 果6 c ，那么c 等价于忱4 3 二元g o l a y e 马的构造 3 1 二元g o i a y 码的构造l ：由h a m m l n g 码构造二元g o i a y 码 k h a m m i n g 码是这样一个 是两两线性无关向量的极 所组成 设日+ 是将日中的符号逆序所得到的码，则可知面和耳都是 8 ，4 码，且有性 质：耳n 百+ = 6 ，_ 面和百的极小距离都为4 这两个码都是自对偶的 我们如下构造一个字长为2 4 的码虿： 虿= “茁+ 磊i + 叠，矗+ 若+ 司1 a 万，i 耳，量耳) 让柳魏遍耳的一组基，铷遍霄+ 的一组基，则码字( 瓦d ，( d ，瓦西，( 曩，武司之全 体就是虿的一组基，即口是一个【2 4 ，1 2 】码虿的任意两个向量( 不必相异) 正交因 此虿是自对偶码又因为所有基向量的重量都能被4 整除，所以百的每个码字的重量 也能被4 整除假设某个非零码字c 刁的重量 ( c ) 8 5 验 补 校 的 偶 字 苛 码 为 、，吝 1 l 1 及t 0 l 1 膨 1 1 0 0 糙刚甜 九u 珊 燃叫一 一一一一 一 二元g o l 8 涡的构溅 因为矗+ 丘i + 硎_ 茁十i + 岳显然为偶重爨，所以其中之一为d ，因而可得童= 谶茹：王不失一般性，- i 设z = 蘸向量磊弱鑫+ i 的重量为o ，4 或8 因此只能 露g = 蠢 二是君熬援枣鞭藏为& 将虿静每个码字去簿蒸最后一个分位就霹褥到一个极小距离是7 羽i 2 3 ，1 2 j 码e 这个码就是二元g o l a y 碣 3 2 二元g o l a y 码的构遣l l ：由p a l e y 矩阵构造二元g o l a y 码 定义3 。2 1叛十l 秘一l 尧元素，瀵是日嚣* 心秘n 验方薄，嚣惫h a d a m a r d 矩 降 定义3 2 2对角线元素为0 ，非对角线元索为+ l 或一1 ，且使得d g 7 = ( 礼一 1 ) j 的礼阶方阵a ，称c o n f e r e n c e 矩阵 设g 是一个奇素数的方幂，定义有限域玛土的函数x 为x ( o ) 一o ；若z 是非零 警方元x ( 。) = l ；其它x 髫) = - 1 ，鞋任何方式撵列羁孛元素：8 0 ，o , 1 ，8 “其 母8 8 = 0 引理3 2 1 口阶p 蝴e y 矩阵s 定义为s 舀= x ( 啦一q ) ，则宥性质： ( i ) s j = j s = 0 ； ( 托) s s 7 = q i 一以 ( 倒) s 7 = ( 一1 ) ( q 一1 ) 强 铡 浚= 7 ，革娆设墨= 0 ，1 ，2 ，蕞4 ，5 ，镑，弱五孛 零乎方冗为l ，2 ，4 ，由 魏可计算7 酚p a l e y 楚簿s 翔下： 于是 s = 鑫 l o ，l o o 1 o l o 五o 。 以。以o o ，。 o o e ，“ o o o ，l q ，以o ，0 。o o，o，o以 ( s 十，十j ) 2 = f s 十j 十j ) 2 = lo ol01l 1l 转el0l llloolo o11l0 o1 1011100 0lol110 0olol ll llll0o o1l1o1o 0o11101 10 ol11o olo olll l0lo 0ll llol0 0l 码字( 1 ，1 ，1 ，o ，1 ，0 ，0 ) 与码字( 1 ，1 ，1 ，0 ，0 ，1 ，0 ) 之间的h 删i n g 鞭离为2 ，从而 码g 的极小距离为2 ，而不是文【l 】中所断言的m 一1 ) 2 = 3 定理3 2 1 n 阶p a l e y 矩阵s 构造的码a ，落含有码字6 = ( 0 ，0 ，o ) ，r = ( 1 ，t ，一，i ) 以及矩阵谬+ f + j ) 2 移( - s + i 十j ) 2 的全部行向量，冀中是奇素 数鹣方幂，j 裁了努鬟是擎缀矩簿襄全1 矩阵，刘 秘) nel ( m o d4 ) 辩，c 是( n ，2 ( + 1 ) ，( 牲一1 ) 2 ) 码； ( i i ) ni3 ( m o d4 ) 时，g 是( n ，2 ( n + 1 ) ，( 扎一3 ) 2 ) 码 证 由于s 的各杼冗索中+ 1 和一l 的个数均为m 一1 ) 2 ，对角线元素为o ，所 m ( s + f + j ) 2 和( - s + j + j ) 2 的各行元素中有+ 1 ) 2 个1 ，( n 一1 ) 2 个o 因 她，列经意8 ，筘c 凌。鑫( 搿，声) = 甜8 ) + “叠) 一2 = 弹+ 1 ) 一2 。 获褥最须讨论m a x 帮霹求窭羁g 豹援夺琵舞我韵分嚣争争壤魏来讨论。 情况l ：礼i1 ( m o d 4 ) 任取( s + j + 2 的两行移瓯及( - s + i + j ) 2 两行7 ，5 ，则 o 。( 8 t ，1 + 1 ，$ j 一1 + l 8 1 ，t + 2 ，s i + l + 1 ，8 i ，n + 1 ) 2 霹= ( 岛，1 + 1 ，勘，j 一1 + 1 ，母j + 2 ，8 j + l + 1 ，t r ，唧，。+ 1 ) 2 7 三垄曼! ! 翌堡塑塑生 1 = 8 k , 1 + 1 ，一，乳，自一l + 1 ，s 。k + 2 ， - q k ，+ 1 + 1 ，一，s ，”+ 1 ) 2 6 = ( 8 l 、1 + l ，一，s l ， 一l + 1 ，s i f 十2 ，s ，+ l + 1 ，。，s f 一+ 1 ) 2 萁串i 囊蠹z ，羽 = i ( 8 + 1 ) ( 彤，l + 1 ) 十+ ( s “一l + 1 ) ( s ，t 一1 ，1 ) + ( 8 “+ ! ) ( 8 ”+ 1 ) + + ( 曳j + 1 ) ，j + 2 ) + ( 黾n + 1 ) 【酝n + 王) 】4 = 星蕊，女苗+ 蚤冀，+ 妻岛，k 十瓢，j + s ”+ 礼+ 2 ) 4 = ( + 1 + $ 幻+ 8 j ) 4 一由予椎三l ( m 缸4 ) 胬 三乏铲篇基因魏， a ，声亨燃( 礼+ 1 + 。2 s , , j ) 4 。 同理 = 坼+ 3 + 2 s “) 1 4 选取s 甜矗1 ，可使 a ， ， 蓍b 最 大、且三鬻中最大德为+ 5 ) 4 + 于燕码。的极小距离为 d = 汹+ 1 ) 一每+ 5 ) 2 = 铷一z ) 2 定援3 2 2设s 是儿阶p a l e y 矩阵，a = ( s + j 十j ) 2 考虑且的行，a 的5 5 个 互异的掰行之释茨及这些蜉戆替，i 塞楚- - + ( 1 i ，1 3 2 ，3 ) m 设 g = ( 五。 ；1二一 1， 8 三垄鱼! ! 塑堕趁造 或( 1 1 0 ，1 0 0 ，1 0 0 ，1 1 ) 考虑6 6 个码字飘，q + x k ，我们有d ( 趣，托+ z k ) 一 ( ) = 6 ，矗( ，q + 。女) = ( 瓤十嚣j + z ) = 4 或8 遨摄，我们用到了上述瓣标准表示，最 瑟，褥嚣凌应壤上述豹搽壤形式( 对任 莓3 元缝糍，奶，z ) ，我嚣】毒，+ 劫，嚣+ 。) 2 4 因为d ( ，1 + 毋= 1 1 一d 嗡蓟，所戳，将6 6 个弼字替添避这个集合精，极小距离减 为3 g 的每行的重爨为8 或者1 2 ，并且任意两行都是正交的因此，g 生成一 个 2 4 ，1 2 】自对偶码g ，我们知道，a 的两行之和黛为6 ，a 的三行之和墼为4 或8 a 的 暇褥之藉重量至少为4 隘为g 的行重都是4 的倍数，所以g 熬码字的重擞也是4 的倍 数褥盈上述讨论表疆，褥稳粳夺距褰不会是4 ，靼必戆是8 ，强为( 2 4 ，2 ”，8 ) 羁享是难 一的 3 , 3 二元g o l a y 码的构造i i i ：由q r 码构造置元g o i a y 码 考虑字长为奇素数豹蕊疰最上，其中楚个模n 的二次剩余，帮g 如一1 2 ； l ( m o d 哟设盘是嚣嚣藁个扩域串夔一个次拳嚣攀嬗穰。裁 | 、j 在这垂定义： = 2 ( r o o d n ) l i 季；，i o ，r 中的= 次剩余， r l = r + r o ，r 巾的非二次剩余， g o ( x ) = n ( z a ”) ，目l ( ) = ( $ 一曲) 因为我们已经要求q ( m o d n ) 在r o e p ，所以多项式踟( ) 和孽l ( 譬) 的系数都在e 中。 菱遴一步， 矿一1 = 秘一1 ) 鲕( 嚣治l ( 嚣) 定义3 3 1 玛上长为竹，生成元为卯 ) 或如一1 ) ，卯0 ) 的循环码叫做二次剩 余码( q r 码) 我们只考虑二元情形的扩充q r 码这个码w 由驷( z ) 生成的码加上奇偶校验位 褥到， 对于萁毽域，我餐赣蒗扩充蕊蠡毒定义，袋褥箍三一l m 积4 ) 辩扩充弼是叁对 偶的mil ( m o d4 ) 时，对偶予以孽l ( g ) 为生成巍的码的扩充码在= 蕊情况下，生 成元为0 1 ) 9 0 ( o ) 的粥是另一个q r 码的偶熬爨字码如果g 是前糟的生成矩 陴，则在g 上加一全1 行即褥后者的生成矩阵如果先在g 上加一全0 列，然后再加一 全1 行，那么褥到的是扩充鹤的生成矩阵 三垄璺些塑堡曼塑造 在- r n 情况下，q 是模n g j - - 次剩余就意味潜n 兰+ l ( m o d8 ) 作用于码字位置 上的甓换：i i j ( m o d n ) ，将以踟( z ) 为生成辩的码。跌到自身( 菪j 冀。) 或映到 淤负$ ) 为生残元熬璃嚣j r 1 ) 。因瑟，馥卯( ) 必生或元兹鹳等铃予戳热( 。) 巍生或 元的褥若ni 一1 ( r o o d 4 ) ，则一l r 1 ，在这静情形，变换。一z 撼以踟印) 为生 成冗的码的码字映为以9 l ( 为生成元的码的弼字 引理3 3 1 【1 l 若c c ( 霉) 是生成元为9 0 ( 嚣) 的q r 码的码字，n = - 1 ( m o d8 ) ， q 一2 ，则d i3 ( r o o d 4 ) 引理3 。3 2 【1 l对予羁懿一个适当选择的本原元多项式g ( 。) 一扩是 一个q 置玛字熬幂等嚣。囊珏毫l ( r a o d 萄嚣，这个q r 鹤字静生成元舞0 一1 ) 譬。 固； 警怍i - l ( m o d8 ) 时，生成元为孽0 ( 茹) 我们借助于日构造一个( o ，1 ) 矩阵g ( 称为循环矩阵) 它的第一行为目，其余 的行由0 的全部循环移撼充当若nil ( m o d8 ) 则令c = ( o o o ) ；若n5 一l ( m o d8 】，则令c = ( 1 1 1 ) 。定义 g = ( 妄卜善1 ) 由引理3 3 2 ，g 的秆( 撼然并不独立) 生成一个长为n + 1 的二元q r 码n n n 射 影崴线中的点o 。，0 ，1 ，札一1 来表示码字的嫩标位置奇偶校验位放在最前面，记 号为o 。 群p s l ( 2 ，b ) 鑫全俸燮捺。h 嚣4 - 5 ) ( 搿+ 礴缀纛，其中8 ，e ，d 最且挺一 b c 1 不难验证这个群鹣生成元为s ：h 嚣+ l 帮t ：o h z 一。 若q = 2 ，n = 2 3 ，我们商 搿一l = 扛一1 ) 0 1 1 + 矿十7 + 搿6 + 矿+ 茁十1 ) 1 1 十嚣1 0 + 士6 + z 5 + $ 4 + z 2 + 1 ) 强取弱洚) 为8 ( 。) 豹倍式，冀中驰( 嚣) 是生成元，鄹 x 1 14 - 矿+ 。7 + 轳+ 嚣8 + 嚣+ 1 根据引理s 。 此q r 码的极小距离揖因为塞( 莩) = 。“即l 纠2 ，所 以疽= 7 ，而且它是一个宪念码因此这个q r 码即燕一个- - 元g o l a y n 1 0 三垄鱼些! 翌璺堕塑堡 3 4 二元g o l a y 码的构造i v ：由h e x a c o d e 构造二元g o l a y 码 ( 2 4 ，1 2 ，8 ) 扩展g 0 1 a y 码具有丰富的代数结构，它一直是编码理论所关注的对象 定义3 4 1 h e x a c o d e 是码字取自g f ( 4 ) 上的( 6 ，3 ，4 ) 码，简记为日，其 g f ( 4 ) 的元素0 ，1 ， ，面满足面= w 2 1 e 萨= 和面= 1 + ，日的生成矩阵为 g = 0 1 0 1 1 ：面w )c10 01111 ，= l 面 l( ) ， h 是一个扩充的完全码，是一个扩充的q r 码，是自对偶码 考虑二元四重i = ( a l ，a 2 ，a 3 ，口4 ) ，铂g f ( 2 ) 及g = ( 0 ，l ， ，面) ，令d 为鹃面的 n = ( a ，回= 0 1 0 + 口2 1 + q , 3 2 j + 凸4 面( 2 ) 其中加法为g f ( 4 ) i 的加法，显然a g f ( 4 ) ，称a 为二元四重莅g f ( 4 ) 上的投 表1g f ( 4 ) 元素的二元奇偶表示 0 01 1 i = 元奇表示 1o0 0010 o00 101 000 0l1110l111010l11 i = 元偶表示 0 00000ll0l010110 l111110010 101001 将一个二元2 4 重按顺序4 个一列排成4 6 的矩阵，对其按列投影于g f ( 4 ) 可得 到一个四元六重向量，由文献5 1 有如下结论： 引理3 4 1 ( 2 4 ，1 2 ，8 ) o o l a y 码是满足下面条件的所有二元4 6 矩阵的集合 a 所有列校验的奇偶性相同； 6 第一列的检验与列校验的奇偶性相同； c 按列于g f ( 4 ) 的投影是日的一个码字 现在我们应用f o r n e y 长为3 2 n 的码的三次结构的表示方法可以得到日的三 次结构表示 h = ( c 1 + c + ，c 1 + c 2 + c ，c 2 + 矿) ：c 1 ，c 2 ( 2 ，1 ) ，c 4 ( 2 ，1 ) )( 3 ) 1 1 二元g o l a v 码的构造 式中( 2 ，1 ) ，( 2 ，1 ) + 的码元均取o c f ( 4 ) ，生成矩阵分别为【1 1 1 w ，根据( 3 ) ，日的生成 矩降可以写成： 容易验证( 1 ) 与( 4 ) 是等价的g 1 包括上式g 的前两行，它生成一个四元( 6 ，2 ，4 ) 码，该 璐楚嚣匏一个子码，因就，姐可以分为四个璃的蹬集，两暗集酋由0 2 燕成，从( 4 ) 看 捌暖，g 2 翅哥势冀三鬏，簿一段豹都毒稳弱生簸缒阵【l l l l 嘲，遮说弱域及蒺蓬囊每 一暾均有相羁的码空闻 为了分析甘与g o l a y 码之间的联系，我们把文献 7 】中的g o l a y 码的擞成矩阵列 出来 ll1l1 1 l 100 00 0 0 00 0 00 000 0 0 o oo oo o o ollllll l10o0 o 00 0 0 0 0 o 0 oo 0 0 o o 00 0 00 01 1111111 l1 110o 0 0l1110 o 0 00o000000 llo ol10 ollo01100 0 00 0 0 00 0 l0lololol0 lolo10 00 0 0 0 00 o 00 0 0 00 001 1lll1111111111l o o o o oo o o1lo ol1o 0l1o ollo o 0000 0 0 o 0101010101 0101 0 10 011110 o 0 01111o 0 001111000 lo 0lllo 0l0 o1llo 0loolll0 0 olol8ll0olo101 l0010lollo 上式豹蘸丸行生成- 氟( 2 4 ，1 2 ，8 ) 码q ，g o l a y 弱可分为8 个0 l 酌陪集，陪集首由 式( 5 ) 后三行生成，a 也弼分为三段，每一段都悬二元( 8 ，4 ，4 ) 码下面将四元( 2 ，1 ) 码 ，【 、； l 2 g 秽 ，f， | f 、， 0 1 w 0 1 1 l 1 w l 1 1王o i 0 l ，一 一一 g 三垄堡! ! 塑璺煎熬整 的二元偶表示列于表2 ： 彘2 四元( 2 ，1 ) 码的二元偶表示 0 0l l |00爵000000套l1 0 011 l 。1 。10 10 1 ；1 1 ； 10011e0 110 0001 l 11110o00o01l1100 面面 o 101 01 010l 1 0011 0 101010 i0 100 1l 001 010110l001101001 1 0 10 010l10 0 1 0110| 这1 6 令二元表暴维裁t - - 元f s 4 ，钙蕊，翔聚编酶每一段都采霜= 元稻表示，再 热上引理3 。4 1 中b 的条锋所构成的集合就是翻戏( 5 ) 前丸行所生成的a 1 、事实上对 该集合，引理3 4 1 的条件奄部满足，而且易证该集合是g o l a y 码的子码对日，的一个 码字前两段各有4 - t = 弼偶表示可以选择，而由于引理3 4 1 中b 的限制，最后一段只 有2 个可选这样甄的一个码字有2 5 个二元偶袭承因而2 垂个点矗的码字热糍2 9 个二元 馁淡示，容暴验迁其最，l 、熬耋先8 。鼓该集台楚( 2 4 ，9 ，8 ) 玛c l ， 为_ 褥嚣熬二元袭承与g o l a y 鹨对应起来，瓣疆元( 2 ，l 4 羁采雳魏下二元表示： 袭3 四元( 2 ，1 ) 码的二冗偶表示 0 01 w 00 0 0 000 01l001010 011110 0 010l1 0010 豁罚戮 0i0l01101 0 0 111 0 o 0 0101110t1i0o100 o 1111o o o 这8 个二元表示组成嫩成矩阵为i 10 011100 i 的二元( 8 ，3 ) 码， io lololl 。 褥该矩阵重复三次成鸯2 4 3 鳇矩薛，可鞋看委l 襄鹣三簿与式5 j 躬瑶三露怒穗国缒， 戳( 2 4 ，3 ) m m m 字俸为a 豹陪集首靛拇t g o l a y 码m 子( 2 4 ，3 ) 鹨鹁鹃字是三段 毙企相同的8 重“粘接”衙成，g o l a 涓三段的码空伺是相同的注意到岛是h 1 的二元 偶寝示构成的，而以0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 为陪集首的口的陪集是由h 1 的二 元奇表示构成的，因此髓的4 个陪集的二元奇偶袭示构成了g 的8 个陪集 1 3 3 5 二元g oj a y 码的构造v ：由字典序最小二元码构造二元g o i a y 码 定义3 5 1 我们定义距离为d 的字典序最小二元码如下：字长先不固定，由。o = 0 和重量为d 的码字c 1 = ( 1 ，1 ，1 ，0 ，0 ，0 ) 出发若c o ，c 1 ，c f _ 1 已经选好， 则选取c 2 为按字典序( 1 尽可能的靠近左边) 第一个出现的使得d ( q ，c f ) d ( o i f 一1 ) 的字1 步后，定义码的长度为出现分量l 的那部分的长度 定理3 5 1设g 是距离为d 的字典序最小二元码， ( i ) 证明选取2 。个向量后字典序最小码是线性码； ( 扰) 对于d = 3 , h a m m i n g 码出现在字典序最小码中； ( i i i ) 我们可以用g 构造= 元g o l a y 码 证 我们先证“在2 0 个选择之后我们得到一个线性码并且对i k ，当2 t 步之 后码字长度增加”当= 1 时，上述说法是对的假设对某个k ，它为真，而选择的码字 表如下： i c o=00 一00 0 a j lc a b 一1 1 2 十10 0 ic 2 一1 = 十- 1 1 1 b ； lc 2 k l = 1 1 1 其中b 组的字是将仍一一，加到a 组的字上而得到的如果c 2 t 与b 中的字有同样的长度 由于按字典序c 2 h 是较大者，c 2 - 就必有形式c 2 t 一，+ 孝，其中菇后面的位置上为0 然而 d d ( c 2 - 一，+ 童，龟一一t + q ) = d ( 武岛) ，其中0 i 2 0 _ 。 这表明应选择新不是恸_ l i 矛盾因此，在我们选择c 2 * 时，长度增加现在假定 已经证明c 2 t + i = c 2 t + c t ，0 i j ( 这对于 = o 为真) 我们就有d ( c 2 * 十c ，c 2 - + 岛) = d ( q ，c t ) d ，d ( c a , + c j ，c 1 ) = d ( c 2 t ，c i + q ) 2d 这由于线性的假设告诉我 们，有某个口，使q + 白= 岛于是，说明仍- + c 是c 2 + ，的一个可能的选择困难之处 在于证明这是一个最小选择湘反，假设应当选择c 2 t + 茁，其中。2 t + 叠， c 2 一+ c ，( 我 1 4 三垄堡! ! ! 芝竺塑塑堡 们用 表示字典序) 由归纳假设，孝n - c i 这些不等式表明勺，量，c 2 * 具有形式 c ，= 0 口1 a 2 岳 =$- 1 0 1 a 2 c 2 q = $ 1 a t 00 a t 00 c 2 t + 躔容许选择的假设意味着( 再一次利用线性性) d ( c 2 一+ 磊勺+ q ) d ，对o t 2 0o o0 1 即 d ( c a k + i + q ，q ) d ，对0 墨i 2 “ 但劬+ 岳+ 白 。2 - ，即c 2 一的选择不是最小的矛盾因此“在2 。个选择之后我们得到 一个线性码并且对 ，当2 涉之后码字长度增加”说法是正确的 现在考虑d = 3 的情形设”k 是2 个向量选择之后的码长，则n 1 = 3 设o k 是 第2 次选择后的线性码如果c k 不是完全的，那么存在长为”的向量它到c m 的每个 码字的距离2 因此( 磊1 ) 是劬的一个可能的选择这告诉我们n k + l = n k + 1 另一 方面，如果是完全的，那么显然n + l = n 女+ 2 ，且铋= ( 1 0 0 0 1 1 ) 我们再证明“长度n k = 2 n + t ，对k = a + e + 1 且1 t 2 8 ”由上述讨论及归 纳法可得到在它中提到的每个序列最终得到的码必定是h a m m i n g 码 通过此方法我们可以得到【7 ，3 ，4 h a m m i n g 码，再根据前面给出的二元g o l a y 码 的构造i ( 由h a m m i n g 码构造二元g o l a y 码) 的方法就可以得到二元g o l a y 码 3 6 二元g o l a y ；l i 马的构：造v l ：e i e s t e i n e r 系s ( 5 ，8 ，2 4 ) 构造二元g o i a y 码 二元g o l a y 码是一个特殊的线性码由文f 1 ，2 1 我们知二元g o l a y 码可以构 成s t e i n e r 系s ( s ，8 ，2 4 ) ，自然有人要问是否由一个s t e i n e r 系s ( 5 ，8 ，2 4 ) 可以构造出 一个二元g o l a y 码这里我们完满地解决了这一问题，并证明了构造二元g o l a y 码和 构造s t e i n e r 系s ( 5 ，8 ，2 a ) 是等价的 定义3 6 1 元集合q 上的一个s t e i n e r 系统s ( k ，r ，n ) 是指n 的一些r 元子集 做成的集合s ，使得n 的每个元子集都恰好含在s 的一个元素之中 1 5 三垄鱼! ! 型婴塑塑堡 对羁鹦e 1 = 嚣y | 强两= 覆话毫毋，如果e 是囊纛交戆二元羁，粼c 的每一 个元素都有偶蓬量，故分爨部为1 的向量f 一( 1 ，1 ) 0 。 我们把v = 局”的妫索与 1 ，2 ，n ) 中的子集铸同起来，即商一( ) 与 集合a = j l a j = 1 ) c 1 ，2 ，礼) 样间起来更一般地，我们可以用n 一 w z ，锗。 来骜谯集合 l ，2 ，8 。戆蓐= ( 8 ，) 与a 一 j 1 8 j = l 等露起寒， 在这样的萼间之下，y 就变成n 的幂集合p ( n ) 对任意a ，b p ( 锄，定义 a + b = ( a u b ) 一( a n b ) a b = l a n b t ( ；o d2 ) ， a p ( n ) 的重量w ( a ) ； a i 由于f a + b i = i a | + | b f 一2 1 an b i ，故有 ( a + b ) = ( a ) 十w ( b ) ( m o d2 ) 如果a b = o ，则mn 曰l 建偶数，从而 ( a + b ) w ( a ) + w ( b ) ( m o d4 ) 。搬暴e 是垂正交麴= 元线性玛，并敷羹量被4 疑整豫的羁字嚣 生成，尉e 的所有码字的重爨都被4 整除称这样静码舞对髑码所有对偶弼都是鲁正 交的，这是因为2 l a n b l i a l + i b i l a 十b i e0 ( r o o d 4 ) ，对任意a ，b c 都成立 考虑所有偶对，嚣) 缎成的集合g ，其中be 最a 篁b i a i = ，n 的每个元 子集稔是。串豹一个元素静第一令分量，藏| g l = 罐毽s 瓣每个元素以磷次密现 在g 中元素的第二个分萤中，散有i c = 磷i s l ， s l = e ：诺 设s 悬n 上的一个s t e i n e r 系s ( k ，r ，竹) ，又设x n ，熙i x l = tsa ，设n = n x ，一 b x i b s x 嚣) ，则n 是p t ) 菇集合如果a 避n 的一 令疆一) 蠢予蔡，鹚x o 蠢禽在唯一豹b s 乏孛，予是麓篓b x 三；舅一方 面，如果acb 7 ，则xu a xu 拶s 且xu b = b ，b = b x ，因 此s 是一个n 7 上的s t e i n e r 杀s ( k t ，r - t ，摊一t ) ，从而i s i 一吠一- t t ，u ，k 一- “t 于是在s 中 共有c ：- - t ，k - - t ，- - ，x 在这一繁串我锯固定瓣蠢集q ，著显撼褥着终为v 一妒( q ) 戆子集 定理3 6 1 如果c 越二元g o l a y 码，则c 是重量为8 的粥字所生成并凰c 中重量 为8 的码字形成s t e i n e r 系s ( 5 ，8 ，2 a ) 定理3 8 2 设s 是q 上的一个s t e i n e r 系s ( 5 ，8 ，2 4 ) ，义设g 至p ( 黜) 是由a s 生成懿礴，掰有 ( 1 ) c 戆自对偶的； ( 2 ) c 怒二元g o l a y 码； 1 6 二元g 0 1 a y 码的构造 f 3 ) 。e 中藏量为8 戆鸹字埝是s 孛重量为8 戆元素； ( 4 ) 0 的薰萤计数予愚1 + 7 5 9 x 8 + 2 5 7 6 x 1 2 + 7 5 9 x 1 6 + x ” 证 先证如果a ，b s ，则i anb l 是偶数周定a 砖如果tsa ，则在s 中 包含t 的元索数目巩只依赖t = 1 t i 如果0 冬t55 ，贝4 川= g 2 “4 - - 。c i 二：而当5 t 茎8 簿甄一1 ，因建妫一7 5 9 ，蕊；2 5 3 ，n 2 = 7 7 ，n 3 = 2 1 ，甄一5 ，n 5 = 6 = n 7 一8 = 1 当0sj k 墨8 时，用下酬遴归的方法来翘义坞如 设帆，沪帆，舰，k = 鸠加1 一心+ 1 ，k ，熟e e osj 基8 ，坞，冽在下寝中，其中 第+ 1 行篱+ 1 列值是m j k ： 7 5 9 5 0 6 2 5 3 3 3 01 7 67 7 2 1 01 2 05 62 1 1 3 08 04 0l 5 7 85 2 2 81 24l 4 63 22 084 0l 3 0 1 61 6 44 0 01 3 001 60 4 0 0 0l 。 我们断曹对每一个a s ，c dga ，其, f c l j 且f d i = 尬，k 是s 中 满足bnd c 的b 的数日，当j = 时，途一断言是很明显的对a j 使用归纳 法来证明骰设j 女，记g 一 。1 ，a j ，d = 8 1 ，妣) ，则丑n d = c b o ( d 一 a j ；= c ，萤露秘d cu ，盘妇缀缓设，s 牢满是这一条僻静口的 数目是蛹，k l 一尬+ 1 1 女一m j ， ，因为均， 一0 对所有的衡数j 都成立，敞s 的每对 元素ab 的交anb 含有偶数个元素因此c 是r a p ( n ) 中赢相正交的元素生成的从 藕e 是童正交豹+ 又因为生成集中靛重量都被4 整除，馥e 是双偶的。 下蟊谖嘲e 的维数至少必1 2 逮取2 f 3 纯，令s 0 = 麓v = p ( c t ) i i a l 4 荠 且当l a i = 4 时一a ) 可以证明任给b k 存在a 鼠使a + b c ，因此| 苦 i & i = 2 “故i c i 2 ”由于c 是自正交的，故i g isl v l l 2 = 2 1 2 故i a i = 2 n 因 戴0 = 0 上避垂黠耦懿。 e 的每一个码字都有髑黧簧，敢f = ( i ，1 ) 0 簸0 盼羹量计数予 致( x ) = 1 + a 4 x 4 十a 8 y 8 + a 1 2 x 1 2 + a 8 x 1 6 十也x + x 2 4 当a 跑遍& 。时，a + e 形 1 7 二元g o l 姆码的搀造 成c 程y 中的一个完众陪集系由于 s 。i = 2 ”= i 薹| 1 敌& 中任何两个元素模g 都怒 不同的如果a c 鼠j a i = 4 , - i 写a b + c ，其中i b i = i c i = 2 ，因此b 和g 是。中 模g 不同的元素，矛盾因此文= 0 ，c 是二元g o l a y 粥。由定理3 1 知爨量为8 的码字 静支撵集澎或一个s t e i n e r j i ；s ( 5 ，8 ，2 4 ) 。这令系建是s 嚣越a 8 = 7 5 9 ，a ，2 2 5 7 6 ，i 忆p r ) = 1 + 7 5 9 x 8 + 2 5 7 6 x ”+ 7 5 9 x 1 6 + x “ 4 缝论 本文通过分析= 元g o l a y 码的特点，利用码的脊必知识，总结了由h a m m i n g 码、 p a l e y 矩阵、q r 码、h e x a c o d e 和字热序最小= 元码构造二元g o l 8 y 码的方法，程 此基獭上，| 芷碍了由一个s t e i n e r 系s ( 5 ，8 ，2 4 ) 可以掏造窭一个二露g o l a y 码，笄涯 羁了擒造二元g o l 蚪褐和构造s t e i n e r 系s ( 5 ，8 ，2 4 ) 鼹等价的德得一提的燕根 据( 4 ，2 ) 。码的特性，由m e c - s b c ( 4 ，2 h 码是否能构造= 元g o l a y 码? 再者，我们知 道妒钒可以构造n o r d s t r o m - r o b i n s o n 褥，那么由n o r d s t r o m - r o b i n 8 0 码是否也可 浚构逡锨? 这些帮是今曩骞簿磅突懿翘蘧。 1 8 三垄堡! ! 坚堡塑塑垫 c o n s t r u c t i o n so ft h eb i n a r yg o l a yc o d e s a b s t p l a c t ：t h eb i n a r yg o l a yc o d ei sau