（应用数学专业论文）四元线性码的研究及其推广.pdf

中文摘要 四元线性码是经典的纠错码理论在近十年间发展起来的一个重要研究方向， 它与二元非线性码的构造及研究有着紧密的联系.本文讨论了四元线性码及其推 广中的几个间题. 本文的主要结果为: 1 . 给出了判定一个四元负循环码的二元像是否是循环码的充分必要条件， 并 在条件成立时，给出了其二元像的结构; 2 .给出了四元 g o e t h a ls 码的对偶码的迹表示及 2 - a d i c 表示，并证明了它在 g r a y 映射下的二元像是二元g o e t h a ls 码的 形式对偶码; 从而可以 将对非线性码二 元g o e t h a ls 码及其形式对偶码的 研究 转化为 对四元线性码的研究; 3 . 对于类型为4 k 的四 元线性码， 建立了 联系它与其对偶码的支集重最分布之 间的m a c wi ll i a m s 恒等式; 4 . 对于伽罗华环g r ( 4 n ) 上的一 类循环码. 以及g r ( 4 - ) 在z 4 上的一组基， 给出了满足这类循环码相对于该组基展开后得到的码是四元循环码的充 分必要条 件，该条件简便实用; 5 . 建立了 多项 式环- p . 12 ) 中 的h e n s e l 引 理 及提升， 证明 了x n 一 1 在多 项 式环 马e 12 ) 中 的 唯 一 分 解 性， 并 给出 了耳 上 所 有 循环 码的 结 构; 6 . 将著名的b e r le k a m p - m a s s e y 解码算法推广到伽罗华环上，给出了 伽罗华环 g r ( p e p e m ) 上的b e r le k a m p - m a s s e y 解码算法. 关锐词:四元线性码 g r a y 映射 伽罗华环 垂本不可约多项式 abs tract t h e t h e o ry o f q u a t e r n a r y l i n e a r c o d e s i s o n e o f t h e i m p o r t a n t s u b j e c t s i n r e c e n t t e n y e a r s , w h i c h i s c l o s e l y r e l a t e d w i t h t h e s t u d y o n c o n s t r u c t i o n s a n d p r o p e r t i e s o f b i n a r y n o n l i n e a r c o d e s . i n t h i s p a p e r , s e v e r a l q u e s t i o n s a b o u t q u a t e r n a r y c o d e s a n d t h e i r g e n e r a li z a t i o n a r e d i s c u s s e d . s o l u t i o n s p r e s e n t e d i n t h i s t h e s i s c a n b e s u m m a r i z e d a s f o l l o w s : 一 a s u ffi c i e n t a n d n e c e s s a ry c o n d i t i o n i s g i v e n i m a g e s u n d e r t h e g r a y m a p b e i n g c y c l i c , a n d t h e t h e c o n d i t i o n i s s a t i s fi e d . f o r t h ec li c c o d e s w h o s e b i n a r y b i n a ry i m a g e s a r e d e t e r m i n e d w h e n 一 t h e t r a c e r e p r e s e n t a t i o n a n d t h e 2 - a d i c r e p r e s e n t a t i o n f o r t h e d u a l o f t h e q u a t e r - n a r y g o e t h a l s c o d e a r e g i v e n , a n d i t s b i n a r y i m a g e i s p r o v e d t o b e t h e f o r m a l d u a l o f t h e b i n a r y g o e t h a l s c o d e . 一 t h e g e n e r a l i z e d m a c wi l li a m s i d e n t it ie s a r e g i v e n f o r t h e s u p p o r t w e i g h t d i s t r i b u - t i o n o f a q u a t e r n a ry l i n e a r c o d e w it h t y p e 4 k a n d t h a t o f i t s d u a l c o d e . 一 a l l o f t h e c y c l ic c o d e s o v e r t h e g a lo i s r i n g g r ( 4 - ) , a n d t h e b a s e s f o r g r ( 4 m ) o v e r 瓜 a r e d e t e r m i n e d , s u c h t h a t w i t h r e s p e c t t o t h e b a s e s , t h e 4 - a r y i m a g e o f t h e c y c l i c c o d e s a r e s t i ll c y c l i c . 一t h e he n s e l s l e mma a n d l i t t i t i s p r o v e d t h a t 二 ” 一1 , w h e r e ( n , p ) o v e r t h e p o l y n o m ia l r i n g 马. 【月 =1 , c a n b e u n i q u e l y f a c t o r e d . a r e d i s c u s s e d , a n d f u r t h e r m o r e , al l o f t h e c y c l i c c o d e s o v e r 马. a r e d e t e r m i n e d 一 t h e b e r l e k a m p - m a s s e y a l g o r i t h m o v e r t h e g a lo i s r i n g g r ( p e p i) i s g i v e n . ke y w o r d s : q u a t e r n a r y l i n e a r c o d e g r a y ma p g a l o i s r i n g b a s i c i r r e d u c i b l e p o l y n o mi a l 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果;也不包含为获得西安电子科技大学或 其他教育机构的学位证书而使用过的材料。与我一同 工作的同志对本研究所做的 任何贡献均己 在论文中做了明确的说明并表示了谢意。 本人签名:日期: 关于论文使用授权的说明 本人完 全了 解西安电 子科技大 学有关 保留 和使用学 位论 文的 规定， 即: 学 校有 权保留送交论文的复印件，允许查阅和借阅论文:学校可以公布论文的全部或部 分内容，可以允许采用影印、 缩印或其他复制手段保存论文。( 保密的论文在解密 后遵守此规定) 本人签名: 日期: 导师签名: 日 期:y i o 2 一 兰兰 夕 第一章绪论 1 . 1 经典的纠错码理论简介 早在 1 8 世纪后期，就有关于某个特定码的构造及解码算法的论文，如 b c h 码 但是直到1 9 4 8 年s h a n n o n 的论文is 7 1 的 发表才标志着编码理论的真正建立 在此之前， 人们一直认为减小信息传送中的误码率的唯一方法就是减少传输率. 显然， 这是不明智的.s h a n n o n 在论文中引入了信道容量的概念， 并给出了信道 容量的 计算方法. 同时， 他 证明只 要传输率小于信道容量， 就可以 通过使用适当的 编码方法，使得误码率任意小. s h a n n o n 的工作给人们提出了一个问题: 如何构造传精率充分接近于信道容量 的编码? 尽管这个问题至今尚未得到完全解决，但事实证明寻求答案的过程更为 重要:因为在这个过程中产生了许多非常重要的编码技巧. 有很多因素影响着信息传送中的可靠性， 例如: 噪音， 同步化， 干扰， 等等 经典的编码理论主要考虑的是噪音的影响.它主要分为纠错码理论及g a u s s ia n 信 道中 信息的传送.这里主要介绍的是纠错码理论的发展. 经 典的 纠 错码理 论 通 常 研究 的 是有 限 域 上 的 编 码， 特 别 是 在 二 元 域 上. 令巩 是 含 有9 个 元 素的 有限 域 ，岭 是。 元 向 量 空间 ，卿 中 的 任 一 子 集c 就 是 一 个 编 码 ， 其中c的 元 素 称 为码 元 ， 而衅 中 的向 量 称 为字 在刃 中 引 入h a m m in g 重 量 的 概 念， 对于任 意的x = ( x i , x 2 ， 一， x . ) c 岭， 定 义 w h ( x ) = 1 : x i 36 0 1 , 称 为x 的h a m m in g 盆f . 这 个重 量函 数 就 决 定了卿 中 的 一 个 度 童 ， d h ( x , y ) = 、 二 ( x 一 y ) , b x , y e 衅 称为x 与y的h a m m i n g 距离. 令 d =m i n d h ( x , y ) i x , y c , x 36 y , 称为码c的极小h a m m i n g 距离. 这样， 一个纠 错码c 就包含了3 个重要的参数: 码长。 ， 码元个数回， 及极小h a m m i n g 距离d ， 通常记作( 。 ， i c i , d ) 码 第一章绪论 由 于每个码元代表着一条信息， 故码元个数决定了码的信息量的大小; 而在解 码过程中， 我们 通常依据的 是极大似然译码理论， 在这个理论中， 极小h a m m in g 距 离 决定了 码c的 纠 错 能 力 因 此， 在 码长固 定的 情况下， 码 元个 数 及极小h a m m in g 距离就可以用来衡量一个码的好坏. 为了在应用上的实现， 一个好的纠错码还必须易于编码及解码. 通常情况下， 我 们 会 要 求 码 具 有 一 定 的 代 数 结 构 ， 例 如 要 求 码c 是f9 的 线 性 子 空 间 ， 即 所 谓 的线性码. 此时码的势就由 它的维数k 决定， 我们通常用 n , k , d 表示一个长度 为。 ， 维数为k , 极小h a m m i n g 距离为d 的线性码. 对于线性码的编码， 我们只濡 找到一组基就可以很容易的实现.而对于解码:一般地我们也可以利用校验子的 分类， 绘制译码表得以实现. 对于某些特殊的线性码， 例如循环码， 还有著名的 b e r l e k a m p m a s s e y 解码算法. 线性码一直是经典的纠错码理论研究的 重点. 在s h a n n o n 的论文6 7 发表不 久， g o la y 3 0 与h a m m i n g 3 2 分别构造t g o l a y 码与h a m m in g 码， 它们 是编码理论 中 非 常 重 要的 两 类线 性 码 后 来， v a n l in t 7 4 , z in o v i e v 及l e o n t ie v 8 5 证明 了 完 备 码 只有h a m m i n g 码，g o l a y 码及二元重复码三类.s le p ia n 的工作6 8 , 6 9 , 7 0 1 更是 给 线 性 码 的 研究 打下 了 坚 实 的 基 础. 继 于b c h 码的 研 究1 1 ， 1 2 ， p e t e r s o n 5 7 第 一次证明了b c h码实际上就是循环码一 这是一类非常 重要的线性码. 对于线性 码的解码， 也有着大量的工作. 尽管s l e p i a n 6 7 中 给出的 译码表的 构造方法非常简 单， 但对 于码元较多的 线 性码却不 是 很实 用.p e t e r s o n 5 7 , g o r e n s t e i n 与z i e r l e r 3 1 及b e r l e k a m p 3 相继研究了b c h码的 解码. m a s s e y 在文献5 2 及5 3 中 ， 对 b e r le k a m p 在3 中 提出 的 算法加以 改 进， 最 终形成了 著名的b e r l e k a m p m a s s e y 算 法. 然而， 在线性码易于编码及解码的同时， 其信息量及纠错能力上的要求势必 会降 低. 我们 知 道， 一 个线 性码的 维数k 及 极小h a m m i n g 距离 必须 满足s i n g le t o n 界!7 4 ， 即k 1 , 2 ,-r 0 , 3 -+ 1 ; 口:0 卜 - 今 0 , 1 一r 0 , 2 卜 一 净1 , 3 卜 一 ，1 ; ，y:0 + 0 , 1 - - + 1 , 2 - - + 1 , 3 - - + 0 很自 然地， 我们可以把上述三个映射推广为由月 到z n2 的映射， 并且也分别记 为a , 0 , - y . 定义 0 : 71 4一叫n( 2 .4 ) c 一( r ( c ) , 7 ( c ) ) d 称为g r a y 映射 令c 是一个7 1 4 线性码， 它在g r a y 映射下的 像o ( c ) 称为它的 二元像 通常我们用大写的花写体字母表示四元码， 而用相应的大写拉丁字母表示 其 的 二元 像. 显 然，g r a y 映 射 建立了 一 个由刃 到川” 的 一 一 对 应， 更为 重要 的 是，它是一个保距映射. 命题2 . 1 . ( 8 2 定理3 . 1 ) 是由( a 4 , l e e 重量 ) 到( 时” ， h a m m i n g 重量) 的 保 重映射，即 二 。 ( x ) =w a ( (k ( x ) ) , h x e 7 1 4 , ( 2 .5 ) 2 . 2四元负循环码 并且，0 是由( 粉 ， l e e 距离) 到( 叫” ， h a m m in g 距离) 的保距映射， 即 d t ( x , y ) =d h ( o ( x ) , 沪 ( y ) ) , d x , y e 7 6 4( 2 . 6 ) 我们通常把映射。只简单地记作” 一 ” . 很自 然地，” 一 ” 可以扩展为映射 z 4 x ) n o +a i x + +a n - 1 x n - 1 z 2 阂 而+瓦x + +瓦_ 1 砂一 1 . 我们把这个扩展映射也记作” 一 对于任意首项系数为1 的多项式f ( x ) z 4 x ) ， 如果y ( x ) 在- 2 - 中 是不可约 的 或本原的) ， 则称f ( x ) 是墓本不可约多项式( 或荃本本原多项式) . 令h ( 二 ) , f 2 ( x ) 是a s x 1 中的多项式， 如果存在a 1 ( x ) , 1 2 ( x ) z 4 (- 1 ， 使得 a 1 ( x ) f 1 ( 二 ) +a 2 ( x ) f 2 ( 二 ) =1 , 或等价地， 肠阂f 1 ( x ) 十 瓜阂f 2 阁 =瓜阂， 则我们称f 1 ( x ) 与f 2 ( x ) 是互素的. 对于- 2 x ) 中 多项式的互素， 也有类似的定 义.同时，由于7 l 2 是有限域， 故f 1 ( x ) 与f 2 ( x ) 互素当且仅当它们无次数1 的 公因式. 引 理2 .2 . ( a 2 引 理5 . 1 ) 令f 1 ( x ) 与f 2 ( x ) 是z 4 x 中 的 多 项 式，7 , w, 7 2 ( x ) 分 别为它们 在映 射， 一 ” 下的 像， 则f 1 ( x ) 与f 2 ( x ) 在7l 4 x 中 互 素当 且仅当7 , ( x ) 与 几( x ) 在z 2 闰中互素.口 2 .2 四 元负 循环码 在本节中，我们令。 是一个奇数. 令c 是一个长度为。 的四元线性码， 如果满足 v ( c o , c l , , c 。 一 1 ) e c = = * - ( - c . - l , c o , c 1 ， 一 ， c_ 2 ) e c , 则 称c 为四 元 负 循 环 码 ， 或p .4 负 循 环 码 ， 同 循 环 码 一 样 ， 我 们 把 a = ( a o , a l ， 一， a n - 1 ) 等同 于z 4 x j i ( 2 n + 1 ) 中的多 项式a ( 二 ) = a 0 + a l x + 则( 2 . 7 ) 等价于 ( 2 . 7 ) z n4中的向 量 . . -+ a _j x n - 1 , v c o + c j x + + c , - j x - e c = :* x ( c o 十 c 1 x + 十 c n _ 1 x n - 1 ) c , ( 2 .8 ) 第二章四元负循环码 则c 是一个四元负循环码当且仅当c 是z .4 闰/ ( x + 1 ) 中的一个理想. 命题2 .3 . 令c 是一个长度为。 的肠 负循环码， 则 c 二( f ( x ) 9 ( x ) , 2 f ( x ) h ( x ) ) , ( 2 .9 ) 其中， f ( x ) , 9 ( x ) , h ( x ) 是x b ;x . 同 样 地 ， 我 们 可 以 对脚中 的 向 量 及 e 2 (x )l (x n 一 ， ) 中 的 多 项 式 i =o * 运算。 引 理2 .5 . ( 3 3 定理5 ) 令o ( c ) 是x 4 线 性码c 的 二元 像， 则 且仅当 对于任意的a , b c , 2 a ( a ) * a ( b ) e c . 命题 2 .6 .令 f ( x ) , 9 ( x ) 及 h ( x ) 是 z 4 闰 中 首项系数为 1 f ( 二 ) 9 ( x ) h ( 二 ) =二 ” + 1 ， 且c =( f ( 二 ) 9 ( 二 ) , 2 f ( 二 ) h ( 二 ) ) 是z 4 负循环码. m ( c ) 是线性码当 口 的多项式，满足 则m ( c ) 是a 上 长 度 为2 ， 的 循环 码当 且 仅当 对于 任 意 的。 兰 “d e g h ( 幻一 1 , 了 阵 万 ( x ) * x 了 ( 劝 9 ( x ) 。 j ( x ) ) ， 其中仔 ( x ) ) 是z 2 冈/ ( x n 一 1 ) 中由了 ( x ) 生 成的 理想. 证明: 假设o ( c ) 是循环码， 则一定是线性码.由引 理 2 .5 得， 对于任意的 0 d e g h ( x ) 一1 , 2 a ( f (x ) 9 ( 二 ) ) * a ( 二 f ( 二 )9 ( x ) ) = 2 f ( x ) 9 ( 二 ) * x if (二 ) ， ( 二 ) 】 e c , ( 2 .1 0 ) 令c 然， = c ec 2 c =0 ， 则c 是c 的 子码， 由 所有 分量是。 或2 的 码元 组成. 显 c 也 是 循环 码， 且己 =( 2 f (二 ) )由( 2 . 1 0 ) 得2 f (二 ) ， ( 二 ) * 二 f ( 二 ) 9 ( 二 ) 1 ( 2 f (二 ) ) ， 故 存在a ( x ) 瓜x / ( x n 十 1 ) 使 得 2 f ( 二 ) 9 ( 二 ) * 二 f ( x ) 9 ( 二 ) 1 = 2 a ( x ) f ( 二 ) ， 则f ( 二 ) 夕 ( 二 ) * 理想.因此， x f ( x ) 9 ( x ) l 一 a ( 二 ) f ( x ) ( 2 ) ， 其中( 2 ) 是z 4 x ) f ( x n + 1 ) 由2 生 成的主 而) 9 ( x ) # x f (x )9 ( . 不 a (x )f (x ) =0 , 第二章四元负循环码 f ( 二 ) g ( x ) * x i f ( 二 ) 9 ( x ) =f ( 二 ) g ( x ) * 二 ， f ( x ) 9 ( 二 ) =a ( 二 ) f ( 二 ) ， 故f ( x ) 9 ( x 下 * x 了 ( x ) 9 ( 二 ) ( 了 ( 二 ) ) 另一方面， 假设 对于任 意的。 三 : h 一 1 , f ( x ) 9 ( x )刃( x ) 9 ( x ) ( f ( x ) ) ， 其中 d e g h ( x ) =h ， 则 2 f ( 二 ) 9 ( 二 ) * 二 f ( 二 ) 9 ( 二 ) e ( 2 f ( x ) ) 二 c c c . 对于任意的0 们不妨假定 i ， ， h 一 1 ， 则 一定 有2 x i f ( x ) g ( x ) * x i f ( x ) 9 ( x ) ) 。 c . 事实 上. 我 a . 当 = 1 . 时， -i 时， 对于任意的 h-1 2 (x f ( x ) 9 面* 获 币 而 面卜2 x (f ( x ) 9 ( x ) * x ， 一 f (x ) 9 ( x ) c . c l ( 二 ) i c 2 ( 二 ) e c ， 我们假设c l ( 二 ) =a i ( x ) f ( 二 ) 9 ( 二 ) + 2 b i ( x ) f ( 二 ) h ( 二 ) ， 其中 a i ( x ) =艺a ij x 3 , j =0 =1 , 2 . 则 2 a ( c l ( 二 ) ) * a ( c 2 ( 二 ) )，2 e a l j x l f ( 二 ) 9 二 ) ， ( e a 2 k x k f ( 二 ) 9 ( 二 ) i a l j a 2 k x j f ( x ) 9 ( x ) * x k f ( x ) 9 ( x ) e c 目艺倒 粼艺间 由 引 理2 .5 得 ( c ) 是z 2 上的线性码， 而由 命题2 .4 知o ( c ) 在循环移位下保持不 变， 故叔 c ) 是d + 2 上长度为2 。 的循环码.口 n _1 对于任意的a ( x ) = 艺a i x a( x l ( 二 ” +1 ) ， 令 # ( a ( 二 ) ) = 为了叙述方便， q ( a i ) 二 ， 及-y ( a ( x ) ) 一 甘-y(a i)x i， 则 g ra y 映 射 可 以 写 成 o ( a ( 二 ) ) =( p ( a ( x ) ) , 7 ( a ( x ) ) ) , d a ( x ) e z 4 x f ( x n +1 ) . 在z 黔中 长度为2 n 的向 量与x +2 同i ( x 2 ” 一 1 ) 中 的 多 项式的 等同 关系 下，0 ( a ( x ) ) 可以 表示成多项式p ( a ( 幻 ) 十 x n 城 a ( x ) ) . 命题2 . 7令c 二( f ( x ) 9 ( x ) , 2 f ( x ) h ( x ) ) 是一 个z 4 负 循环码. 其中， f ( x ) , 9 ( x ) , h ( x ) 是z 4 x ) 中 首项系数为1 的 多项式， 满足f ( x ) 9 ( x ) h ( x ) 二 x + 1 若o ( c ) 是z + 2 上 2 . 2四元负循环码 的 循环码， 则o ( c ) = ( 7 ( - ) 2 9 ( x ) ) ， 其中( f ( - ) 2 9 ( x ) ) 是x 2 阂a x e ” 一 1 ) 中由7 ( x ) z s ( x ) 生成的理想. 证明: 若 o ( c ) 是循环码， 则o ( c ) 是 z 2 (x ) i ( x 2 ” 一1 ) 中的一个理想.由 于 f ( x ) 9 ( x ) h ( 二 ) = , n + 1 ， 故 在z + 2 闺中 ， 我们 有了 ( 二 ) 9 (x 巧 ( 二 ) = 二 ” + 1 . 因为2 f ( 二 ) e c , 所以 ( 2 f ( 二 ) ) =( f ( 二 ) 1 7 ( 二 ) ) 二 f ( 二 ) ( - n + 1 ) = f ( - ) 2 9 ( 二 ) h ( 二 ) e o ( c ) . ( 2 . 1 1 ) 假设f ( 二 ) 9 ( 二 ) 则 = 省。 二 . 对 于 * = 。 ， 1 , 2 , 3 ， 令凡= =k ) ， 及a k ( x ) =艺 x , i e e t f ( 二 ) 9 ( x ) 二a l ( 二 ) +2 a 2 ( 二 ) +3 a 3 ( 二 ) ， 了 ( x ) g ( x ) = a i ( x ) + a 3 ( x ) . 故 0 ( f ( x ) 9 ( x ) )二 ( a ( f ( 二 ) 9 ( x ) ) , - y ( f ( x ) 9 ( 二 ) ) ) = a 2 ( 二 ) + a 3 ( 二 ) +x 0 ( a i ( 二 ) + a 2 ( 二 ) ) = a 3 ( 二 ) + 4 3 ( 二 ) +( 二 ” +1 ) ( a 1 ( x ) +a 2 ( - ) ) = 了 ( x ) 9 ( 二 ) 1 + ( a 1 ( 二 ) + a 2 ( 二 ) ) h ( 二 ) d ( c ) -( 2 . 1 2 ) 令石 ( 二 ) 二1 + ( 西 ， ( 二 ) + a 2 ( 二 ) ) 万 ( : ) ， 则 b ( x ) + ( a 1 ( 二 ) + a 2 ( 二 ) ) h ( x ) =1 .( 2 . 1 3 ) 对( 2 . 1 3 ) 两边同 乘以f ( x ) 2 9 ( x ) 得 了 (二 ) 2 9 ( x ) = 了 ( 二 ) 2 9 (二 ) 6 ( 二 ) + (a 1 ( 二 ) + a 2 ( 二 ) ) 了 (二 ) 2 9 ( 二 ) h ( 二 ) ( c ) 由 于o ( c ) 是一个理想， 故( f ( x ) 2 9 ( x ) ) s o ( c ) ， 其中( f ( x ) 2 9 ( x ) ) 是z + 2 阂a x ,一 1 ) 中由f ( x ) 2 9 ( x ) 生成的 理想.由 于 i o ( c ) i- i c i= 2 2 d e g h (x )+ d e g 9 (x ) = 2 2 a - (2 d e b f (z )+ d e g 9 (x ) ) = i ( f ( 二 ) 2 9 ( 二 ) ) i+ 故o ( c ) =( 了 ( 二 ) 2 9 ( x ) ) . o 由 命题2 .6 及2 .7 ， 我们 可以 得到下面 几 类岛 负 循环 码， 它们的 二 元 像是场 上的循环码. 第二章四元负循环码 推论2 . 8 . 令f ( 二 ) 与9 ( 二 ) 是z 中 首项系 数为1 的多项式， 满足x + 1 =f ( x ) 9 ( x ) , c 二( 2 f ( x ) ) 是长度为。 的7l 4 负循环码. 则o ( c ) 是长度为2 n 的二元循环码， 且 o ( c ) =( 了 ( x ) ( x n +1 ) ) . o 推 论2 .9 ， 令抓 劝与h 回是z 4 上首项系 数为1 的 多项式， 满 足x + 1 = 9 回h 冈， c =( 9 ( x ) , 2 h ( x ) ) 是长度为。 的tl 4 负 循环码 则 ( c ) 是长度为2 。 的二元循环码， 且o ( c ) =( 9 ( 二 ) ) .11 令。 , b 是正整数满足a 。 ， 且a b 二二 ， 而c , d 是正整数满足。 a ， 且“=a . 则x n + 1 在z 4 阔中 可 被 分解 为 x + 1= ( x a +1 ) ( 二 ( b - 1 ) a 一 二 ( b - 2 ) a + b -1 = ( x a +1 ) 艺( 一 1 ) ， 二 ，a +1 ) i = od - 1 = ( x +1 ) ( e ( - 1 ) x ) ( 艺( 一 1 ) s x s a ) i =o i = a ( 2 . 1 4 ) 推论2 . 1 0 . 令a , b 是上面所给的正整数，f ( x ) , 9 ( x ) 是z 4 中 的首项系数为1 的 多 项 式 : 满 足 f (x )9 (二 ) 一 省 (一 1 )二 令 。 一 (f (x )9 (二 ), 2 f (二 ) (二 。 + 1 ) 是 长 度 为 。 的 二 负 循 环 码 贝 。 qs(c ) 是 长 度 为 2n 的 二 元 循 环 码 ， 且 “ c ) = (7 (x ) 蕙 二 “ ) 推论2 . 1 1 . 令。 , b , c , d 是上面所给的正整 数. 的 多 项 式 ， 满 足 f (二 )9 1 二 ) 一 省 卜 1 加 “ ， 且 。 - 令f ( x ) , 9 1 ( 二 ) 是z 4 上首项系数为i (f (x )9 1 (x ) (x + 1 ) , 2 f (x ) 三 ( 一 p x ) 是长度为， 的z + 4 负循环码， 则m ( c ) 是长度为2 n 的 二元循环 码， 且o ( c ) =j 闰( x + 1 ) 6e - 1 x sa ).卜口 t =o 注2 .1 . w o lf m a n n 在文 献!咧中 通 过直 接 计 算 得 到了 一 类长 度 为。 的四 元负 循 环码， 其在g r a y 映射下的二元像是长度为2 。的二元循环码， 是推论 2 . 1 0 中当 a =1 时的一个特例. 第三章四元 g o e t h a l s 码的对偶码的二元像 3 . 1 伽罗华环 我们在研究有限域上的编码时， 经常会用到它的有限次伽罗华扩张域. 与此 类似地， 伽罗华环是研究四元线性码的一个必不可少的工具. 伽罗华环的理论是 由k r u l l 在上世纪二十年代建立起来的( 见(4 3 ) ) . 本节的内 容与记号引自 文献 8 2 ) 第六章 一般地，伽罗华环r是指一个含有单位元的有限交换环，其中的零因子及零 元素构成主理想(p ) , p 是一 个素数 在有限环中， 如果一个元素不是零因子， 则一 定为可 逆元. 因此，r是一个局部环，树 是其中唯一的一个 极大理想. 单位元1 在r的加法群中的阶称为环的特征. 可以 证明， 伽罗华环r的 特征一定 是p 的一 个方幕.本节只简单介绍一些特征为4 的伽罗华环的内容，推广到一般情形是直 接的. 对于任意两个特征为4 的伽罗华环，如果它们的元素个数一样， 则它们是同 构的.因此， 我们可以 用g r ( 4 m ) 统一地表示特征为4 ， 元素个数为4 -的伽罗 华 环，x 4 是。=1 时的特例.由!8 2 定理6 .7 知在伽罗华环g r ( 4 m ) 中， 含有一 个 阶为2 m 一 1 的元素6 ，它是。次基本本原多项式h ( 习的 根， 且 g r ( 4 m ) = 7l 4 x ) / ( h ( 二 ) ) = a 4 c ) - 因此， 伽罗华环g r ( 4 m ) 中 任意一个元素c 可唯一地表示成 。 =。 。 + a l + ， 二 + a . - i ,。 e tl 4 , ( 0 _ q 叫曰5 第三章四元 g o e t h a l s 码的对偶码的二元像 其中a i e t l 4 , i = 0 , 1 , - - - , 。一 1 , 万 是有限域迅中的本原元. 显然， 这是一个满同 态， 且核为g r ( 4 - ) 中的极大理想( 2 ) . 因 此，g r ( 4 - ) 1 ( 2 ) 几二 引理3 . 1 . ( (8 2 推论6 . 8 ) 把伽罗华环中的元素 表示成2 - a d i c 表示的形式:c = a + 2 b ， 其中a , b e t ， 则 ( i ) 若a = 0 ， 则。 是幕零的， 故也是零因 子或零元素. 所有这样的元素 构成主 理想( 2 ) ; ( i i ) 若a 0 。 ， 则。 是可逆元; ( i i )。 的阶是2 - 一 1 的因 子当且仅当a 00 ， 且b 二 0 .口 有限域1 f 2 ，上的f r o b e n i u s 映射 f 2 : 2 升巩 a h a 2 可以 如 下推广 到伽罗华环g r ( 4 叫上: f : g r ( 4 ) - - + g r ( 4 ) c =a +2 b . - - 4 c f =a 2 +2 6 2 f 称为g r ( 4 哟上推广的f r o b e n i u s 映射. ( 3 . 3 ) 推广的f r o b e n i u s 映射f 是伽罗华环g r ( 4 - ) 的一个自 同构， 且保持z 4 中的 元素不变.由4 的阶为2 - 一 i ， 可以推出f 的阶为。 另一方面，g r ( 4 m ) 中的任 一个自 同 构都是f 的形式， 其中。 i ，一 1 ， 故i 生成的 循环群就是g r ( 4 - ) 的 自同构群. 我们知道，有限域1 f 2 .到b 2 的迹映射定义为 t r ( a ) = 。 + 。 八 + a f s + 一+ 。 m - a f t , v a 。 f 2 - . 同样地， 这个定义可以推广为g r ( 4 叫到z + 4 上的迹映射: 叩( c ) = c + j+ c p + + c f “ 一 ， v c 。 g r ( 4 - ) . 命 题3 .2 . ( (8 2 命 题6 .1 3 ) 叩 是g r (4 - ) 到tl 4 的 满 射， 且 有 ( i ) t ,- ( c + c ) 二甲( c ) + s 1 n ( c! ) ， v c , c g r ( 4 - ) , ( ii ) t ,- ( a c ) 二a 双” ( c ) , v a 瓜， c e g r ( 4 ) , ( 、玛 了= 砂，v c e g r ( 4 m ) , ( 3 .4 ) 3 . 2 二元g o e t h a l s 码的 形式对偶码 ( i v ) 叩 ( c ) =t r ( c ) , 6 c e g r ( 4 ) . 最后， 我们简单介绍一些伽罗华环的扩张理论. 与g r ( 4 k ) , g r ( 4 k ) c g r ( 4 - ) 当 且 仅当k 。 . 令e = 广的t o b e n i u s 映射. 在扩环g 侧4 叫 中， 任意元素 的作用下保持不变. 并且，产生成g r ( 4 - ) 上保持 群.定义 t k (c ) 一 c + e f k + c f 2 k + + c f , 一 ，) ， 对于任意的伽罗华环g r ( 4 哟 二 / k ， 且了 是g r ( 4 叫上的推 c 。 g r ( 4 k ) 当 且 仅当c 在f k g r ( 4 勺中 元素 不变的自 同 构 吮 e g r ( 4 - ) . 为g r ( 4 - ) 到g r ( 4 k ) 上的迹映射. f在子环g r ( 4 k ) 中的限制映射是 限制映射的阶为k . 定义 ( 3 . 5 ) g r ( 4 k ) 上 的自 同构， 保持x 4 中元素不变. 并且， (3.6)(37) 玲( c ) = c + c f + c f z + + c f 一 ， ， d c 。 g r ( 4 k ) 为g r ( 4 k ) 到z 4 上的 迹映射 由( 3 .5 ) 及( 3 .6 ) ， 我们 显然有 t i (c ) = 对( t k ( c ) ) , b c e g r ( 4 ) . 3 . 2 二元g o e t h a l s 码的形式对偶码 在3 . 2 - 3 .4 节中， 我们令二= 2 t 十 1 是一个正整数全 5 ， 且。 =2 - 一1 . g o e t h a ls 2 8 ! 构 造t 两 个 长 度 为2 m + 的 二 元 非 线 性 码g m + ; 与g m + ， 一 ， 由 于 它 们的h a m m i n g 重量分布满足m a c wi l l i a m s 恒等式，g m 十 : 称为二元g o e t h a ls 码， 而g - 十 1 * 称为它的形式对偶码 首先，我们介绍一些记号. 令。 是有限域1f 2 二中的一个本原元，m + ( x ) 表示 。 一 的 极小多项式，r i ( x ) 表示a闰a x , 一 1 ) 中由( 2 n 一 1 ) / m i ( x ) 生成的不可约理 想的 生 成幕等 元. 我们 通常 用z 2 x / ( x n 一 1 ) 中 的 多 项式c o + c 1 2 + . . . + c- - 1 x n - 1 表示。 元向量( c o , c l , , c n - 1 ) 写. g 。 十 : 一 是由 一 个线 性码的2 2 t + 1 个陪集的 并 构成的 非线 性码， 其中 这个 线 性 码称为g 二 十 ; : 的核， 记作k e r g m + 1 1 . 核k e r g 二 十 1 二由 所有形式如下的码元组成 ( u l ( 1 ) , - l ( 二 ) ， 。 二 ( 1 ) , u n ( 二 ) ) ，( 3 . 8 ) 第三章四元 g o e t h a l s 码的对偶码的二元像 其中 圳期+411).lz)la)l)l5) (s4t价侈侈侣(3 u l ( 二 ) =a o # o ( x ) +a l x # 1 ( 二 ) +a 3 x ， 3 # 3 ( 二 ) ， u r ( 二 ) =b o # o ( 二 ) +a l x # 1 ( 二 ) + a 3 a # 3 仕 ) ， a o , b o , a 1 , a 3 z 2 ， 且i 1 , i 3 e o , l , ， 二 ， 。 一 1 1 . 显然k e r g - + 1 1 是一 个维数为 的二元线性码. 对于任意的与。 互素的正整数， ， 1 r 。 ， 我们有 几一1 # r (x ) = 艺二 t r ( w r i 1 . i =0 令7 0 二 a l 。 一 “ ， ， : 二 a 3 w 一 3 i3 ， 则由( 3 . 3 ) 与( 3 . 1 0 ) 得 u l ( 1 ) = a o ,。 : ( 二 ) = 又( a o + t r ( y o w + l w 3 i ) ) 二 ; 。 二 ( 1 ) 二 b o , u x ( x ) = 艺( b o + t r (-yo w i + 7 1 w u ) ) 二 ， i -0 g . + ， 二的陪集代表元分别为u o =0 及户+ 1 _1 个非零向量 u i 二( o , x e ( 二 ) , 0 , x , ( # ( x ) + # 1 ( 二 ) ) ) ，1 j j m (2 3 (n - 1) ,t i (2 ) ,(2 4 3 ), ， 二 ， 对于任意的7= b