（应用数学专业论文）环zq与环fpufp…uk1fp上的重根循环码.pdf

环乙与环e + 嵋+ + “h e 上的重根循环码 摘要 循环码是一类重要的纠错码。目前，随着生产技术的飞速发展和理论研究 的不断深入，有限环上的循环码研究不仅具有重要的理论意义，而且具有重要 的实际应用价值。本文主要研究了有限环上循环码的码长拧与环的特征p 不互 素，即循环码的生成多项式有重根时循环码的结构这是现在编码理论研究的熟 点在环乙( q = p ) 中，作者使用离散傅立叶变换，得到乙( q = p 。) 上长度为 n = p k n ( 其中( 栉，p ) = l ，p 为素数) 的循环码的谱表示和结构，并利用循环码的 谱表示计算出了码的汉明重量，这对乙上长为p k n 循环码的构造和译码有重要 作用环兄+ “兄是介于环z 与域n 之间的一种四元素环，因此分享了环z 。与 域f 4 的一些好的性质；p u d a y a 等首先将环昂+ “昂+ + “缸0 用于最优频率跳 跃序列的构造，研究此类环上循环码的一些性质被广泛的关注。作者考虑环 五= 耳。) 中长为= p 锄的循环码，给出环弓+ 嵋+ o + u k - i c 上任意长度循 环码的结构定理，并进一步给出了该环上循环码的多项式表示，及一种表示 g a l o i sr i n g & ( 哆国) 理想的方法 关键词：纠错码；线性码；循环码；离散傅立叶交换；多项式表示 r e p e a t e d r o o tc y c f i cc o d e so v e r 乙a n d + 蟛+ + “0 a b s t r a c t c y c l i cc o d e 爆a r eaw i d e l ys t u d i e df a m i l yo fc o d e s a tp r e s e n t , w i t ht h es u c c e s s i v e d e v e l o p m e n to fp r o d u c t i o nt e c h n i q u ea n dt h es u c o e s s i v ed e e p - g o i i l gr e s e a r c h e s0 1 1c y c l i c c o d i n gt h e o r yo v e ff m i t er i n g sh a v en o to n l yi m p o r t a n tt h e o r e t i c a ls 王鲥f i c a n c eb u ta l s o i m p o r t a n tp r a c t i c a lv a l u e t h i sd i s s e r t a t i o ns t u d yc y c l i cc o d e so v e rf i n i t er i n g so f l e n g t hn w h e r e pd i v i d e sn t h i ss t u d yh a sb e e ns h o w na ne n o r m o u si n t e r e s ti nr e c e n ty e a r s o nr i n g z , ( q - - p ) ，t h e a u t h o r u s i n g t h ed i s c r e t cf o u r i e rt r a n s f o r m , d e s c r i b et h es t i b c t b r ea n ds p e c t r a l r e p r e s e n t a t i o n o f c y c l i c c o d e s c o f l e n g t hn = p 一o v c q r 乙t h e n t h e a u t h o r c o m p u t e t h e h a m m i n gw e i g h to fc y c l i cc o d e sc r i n gr 却兄i saf o u r - d e m e n tr i n gw h i c hs h a r e ss o m e g o o dp r o p e r t i e so f b o t hz 4a n d 乃t h er i n g 斥+ 绵+ + 矿。易w h i c hi st h eg e n e r a lc a s e o fr i i l gf 2 + l l n ，h 丛a l r e a d yb e e nu s e di nt l 摇c o n s t r u c t i o no fo p t i m a lf r e q u e n c y - h o p p i n g s e q u e n c eb yp u d a y ac o d i n gt h e o r yo v 盱t h e r i n g sh a sr e c e n t l yr e c e i v e dag r e a td e a lo f ；s t 黜。鹪c o d 啦m c 。d s t s ma u t 妇删髂c y c l i cc o d e so v e r r = f p u 矩u t ) 缅 a r b i t r a r yl e n g t hm w es h a l lu s ed i s c r e t ef o u r i e rt r a n s f o r mt oo b t a i na r ti s o m o r p h i s m ， b c 咖尉一1 ) 础蝴一。以舰国) s o , w e 蛳m e m o d t o s e n t a l li d e a li ng a l o i s r i n g 站( 埘，纠，t h e no b t a i n i n g t h es t r u c t u r eo fc y c l i cc o d e so v e r r t ) 也曲i s o 删啦，m 概洳删s m 0 柚酬谢y d e t e r m i n e d , s ot h a tt h ep o l y n o m i a lr e p r e s e n t a t i o n so ft h ec o r r e s p o n d i n gi d e a l sc a nb e c a l c u l a t e d k e yw o r d s ：e r r o r - c o r r e c t i n gc o d e ；l i n e a rc o d e ；c y c l i cc o d e ；d i s e r e mf o u r i e rt r a n s f o r m ； p o l y n o m i a lr e p r e s e n t a t i o n s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 金i 墨王墼太堂 或其他教育机构的学位或证书而使用过的材科与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 学位论文作者签名：璐签字日期：厶刁铝月f 日 学位论文版权使用授权书 本学位论文作者完全了解金熙王些盔堂有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权盒目b 王些太堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期；胛年n - 6 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： ，易乡臼 致谢 在这三年的研究生学习阶段，我的导师朱士信教授不仅在学业上对我进行 耐心的指导，而且还在生活上给予我无微不至的关怀。朱老师严谨的治学态度、 宽广的胸怀和豁达的处世之道给我留下了深刻的印象，并将成为我以后学习和 工作中的楷模。值此论文完成之际，作者向朱老师致以最诚挚的敬意和衷心的 感谢! 在本人学习期间，还得到了苏化明教授、杜学樵教授等多位老师的热心关 怀和无私帮助；在此，向各位老师表示深深的谢意。 同时，真诚感谢师兄李平、余海峰、童宏玺，吴波，师姐钱开燕，以及王 敏秋、王冬银、开晓山、唐淼、施敏加等同学的关心和帮助，在此一一表示感 谢。 最后，感谢我的父母、在我研究生学习阶段对我提供的物质帮助和精神鼓 励。正是家人的无私帮助和默默奉献，才使我在研究生阶段全身心的投入到学 习之中，并顺利完成研究生期间的各项工作任务。 作者：韩牟 2 0 0 7 年5 月 第一章绪论 1 1 纠错码理论的起源和发展 s h a n n o n 在1 9 4 8 年发表的论文“a m a t h e m a t i c a lt h e o r yo f c o m m u n i c a t i o n ” ”】中首次提出了著名的有扰信道编码定理，开创了纠错码理论的研究方向，奠 定了纠错码理论的基石。根据s h a n n o n 的思想，h a m m i n g 2 1 、b o s e 、c h a u d h u r i 、 h o c q u e n g h e m ( b c h ) 3 - 5 、m a s s e y l 6 - 8 、m a c w i l l i a m s t 9 - 1 1 】、g o p p a 1 2 , 1 3 、n e c h a e v 1 4 1 、 冯贵良【1 5 , 1 6 等纠错码理论专家先后给出了一系列设计好码和有效译码的方法。 而后，纠错码受到了越来越多的通信和数学工作者，特别是数学家的重视，使 纠错码无论在理论上还是在实际中都得到飞速发展。迄今，纠错码已有五十多 年的历史，其发展过程大致分为以下几个阶段： 2 0 纪5 0 年代至6 0 年代初，主要研究各种有效的编、译码方法，奠定了线 性分组码的理论基础，提出了著名的b c h 码，同时也给出了纠错码的基本码限。 这是纠错码从无到有得到迅速发展的年代。 2 0 纪6 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期。不仅 提出了许多有效的编、译码方法，而且注意到了纠错码的实用化问题，讨论了 与实用有关的各种问题，所有这些问题的研究为纠错码的实用打下了坚实基础。 在此期间，以代数方法特别以有限域理论为基础的线性分组码理论已趋成熟。 2 0 纪7 0 年代至8 0 年代初，这是纠错码发展史中具有极其重要意义的时期。 在理论上以g o p p a 为首的一批学者，构造了一类g o p p a 码，其中一类子码能达 到s h a n n o n 在信道编码定理中所提出的s h a n n o n 码所能达到的性能，这在纠错 码历史上具有划时代意义。在这期间大规模集成电路和微机的迅速发展，为纠 错码的实用打下了坚实的物质基础，因而与实用相关的各种技术及有关问题得 到了极大关注，并在实用中取得了巨大的成功。 自2 0 纪8 0 年代初至今，g o p p a 等从几何观点讨论分析码，利用代数曲线 构造了一类代数几何码，在这些码中，某些码的性能达到了s h a n n o n 码所能达 到的性能。由于代数几何码是一类范围非常广的码，在理论上已证明它具有优 越性能，因而受到了编码理论研究者，尤其是代数几何学家的重视，使代数几 何码的研究得到迅速发展，取得了许多成果。自上世纪7 0 年代末以来，纠错码 技术已开始渗透到很多领域。利用纠错码中的许多编、译码原理和方法，与通 信系统中其它有关技术相结合，得到了一些令人惊喜的结果。如：纠错码与调 制技术相结合所产生的t c m 技术，已作为国际通信中标准技术而推广使用； 纠错码与密码结合。可以构造出一类既能加密签名，又具有纠错功能的密码系 统；纠错码与信源编码相结合的结果，使得通信系统更为有效与可靠。不仅如 此，纠错码中的许多译码思想和方法，与神经元网络中的能量函数有密切关系， 可以用来解决神经元网络中的一些问题因此，可以预料，随着科学的进步和 实际需要，纠错码理论必将进一步发展，它的应用范围必将进一步扩大。 1 2 本课题的来源和主要内容 目前，随着生产技术的飞速发展和理论研究的不断深入，有限环上的纠错 码理论的研究不仅具有重要的理论意义而且具有重要的实际应用价值。在循环 码的理论研究中。通常要求码字的长度n 与有限环的特征p 互素，即似p ) = l 。 这样才能保证循环码的生成多项式没有重根。但近几年环z ，上长为栉与环的特 征p 不互素的循环码的讨论已成为编码理论研究的热点。尤其是z i 环上重根循 环码已经被广泛研究。本文研究了z q 上长度为= p t n 循环码的一些性质。环 ，2 + 讥是介于环z 与域风之间的一种四元素环，因此分享了环z 与域凡的一 些好的性质；p u d a y a 等首先将环0 + 缉+ + 狂“0 用于最优频率跳跃序列的 构造，此类环上的编码理论研究成为一个新的热点。本文研究了环昂+ 蜗+ + b 。昂上重根循环码结构具体内容如下， 1 使用离散傅立叶变换，得到乙( q = p ) 上长度为n = p n ( 其中( p ) = 1 ，p 为素数) 的循环码的谱表示和结构； 2 并利用循环码的m a t t s o n s o l o m o n 多项式计算出了乙上的循环码的汉明 重量，这对z 口上长为p 竹循环码的构造和译码有重要作用： 3 考虑环r = b 。) 中长为= p 疗的循环码，给出环o + 僻+ + “o 上重根循环码的结构定理； 4 给出了环r = 耳q 循环码的多项式表示； 5 给出一种表示g a l o i sr i n g ( 哆彩) 理想的方法。 2 这些内容的研究对进一步丰富纠错码在有限环上的理论及构造一些性能较好的 码都有一定的指导意义。 第二章环乙上长为p k n 的循环码的谱表示 从1 9 4 8 年s h a n n o n “3 开创纠错码理论以后，人们利用有限域理论“”作为工 具，建立了系统的有限域上的纠错码理论，这些理论在文献 1 1 、5 2 中有全面 的研究。近年来，编码理论中的一个突破性的进展是h a m m o n s 等人在文献 1 7 】 中证明了一些高效的二元非线性码，如p r e p a r a t a 码，k e r d o c k 码等可视为环z 上循环码在g r a y 映射下的像，从而环z 乃至更一般的有限环上的编码理论的 研究进入一个全新方向。文献 2 6 一( q u a t e r n a r yc o d e s 的出版标志着环z 上的纠错码理论已有了基本框架，随后，环z 上的纠错码理论进入全面发展时 期目前利用纠错码降低各类数字通信系统以及计算机存储和运算系统中的误 码率，提高通信质量，延长计算机无故障运行时间等。都有非常重要的作用。 近几年来，关于循环码的研究大多都只限于循环码的生成多项式没有重根的情 况。但自j h v a nl i n t 和g c a s t a g n o l i 在1 9 9 1 年分别在文献 2 8 1 和【2 9 】中介绍了 在特征为p 的有限域上码长咒与p 不互素的循环码，即有重根的循环码后，目 前z ，上长为厅与p 不互素的循环码的讨论已成为编码理论研究的热点文献 【3 0 研究了z l 上长为少的循环码，文献 3 1 1 讨论了z 上奇偶长度的循环码，文献 【3 2 】全面的分析了互上长为1 矿= 2 n 的循环码，自此把对z 4 上循环码的研究推向 了一个新的高度而我们知道，循环码的谱表示m a t t s o n s o l o m o n ( m s ) 多项式， 在码的构造及译码中扮演着重要的角色，因为如果把码字看成时间域或频率域 上的信号，则循环码的译码可以分别利用离散傅立叶变换和信号处理技术的频 域译码以及时域译码。 本章使用离散傅立叶变换( d f t ) ，得到z 口( q = p 1 ) 上长度为n = 矿珂( 其中( 塌 p ) = l ，p 为素数) 的循环码的谱表示和结构，并利用循环码的谱表示计算出了码 的重量，这对乙上长为p * n 循环码的构造和译码有重要作用。 2 1 基本概念 对于环r 上长度为的线性码c ，如果对某一口r ，码字在自同构下是不 变的，即( 气，c l ，c - 1 ) 一( 口1 ，c o ，气2 ) ，那么称c 为口一常循环码。当口= 1 时，码c 称为循环码同样对五上长度为的口一常循环码c ，经过从r ”到 4 r x ! ( x ”- 1 ) 的同构映射( c o ，q ，铀) 一c o + q x + - l x “可以将口一常循环码 c = l r t i 为r x l ( x ”一1 ) 的理想。 当r 。，a = l 并且( m 力= 1 时，理想具有的形式为( 厂) ，其中厂为x 一1 的因子；当r = z ，并且为奇数时，每个循环码具有的形式为( g ) ，其中 f l g i x ”一1 ，与g 为z 4 【x 】中的首一多项式 我们知道n 为奇数时，x ”一l 在z 眵】中的分解是唯一的，所以环互上循 环码所具有的形式很容易得到。但当环的特征与码的长度不互素，即有重根的 情况，循环码所具有的形式就不容易得到了 本文中研究的循环码，我们约定为乙( g = p 1 ) _ k - k 度为= 以( 其中 瓴p ) = l , p 为素数) 的循环码。 我们引入多项式剩余类环9 1 的概念，即吼定义为： 私，一。) 则对每一个a i 吼，4 都能唯一的表示为 a 2 口i n + a o l t + + o t 舻如 a t 。i z q 且存在一个自然同构： 妒；撒万一( 乙) ” ( 4 ，4 ，以- 1 ) 2 ( a o o ，o l ，o ， ，a o a ，q 。咖，吒，- 1 ) ，_ j m ，| - 1 ) ) 显然( z 口) ”中的循环码对应为吼栉中的”一常循环码。即 矿( 1 “厶- l ，a 。，4 ，以1 ) = ( 气- l m ，一i ) ，口0 一，q 冉，a o ，( ，1 1 ) ，0 卜2 m ，- 1 ) ) 因此我们有下面定理： 定理2 1 在自然同构妒下，乙上长度为n 的循环码对应于吼上常循环码 2 2g a l o i s 环 如果 _ ( x ) 为z , t x 】中一个次数为m 的首一基本不可约多项式，且 n ( x ) l x f - - 1 , 那么印，d 括环可定义为g 置( g ，所) = 乙乞扳( x ) ) ，我们也可将 g r ( q ，功写成乙【掌】，u pg r ( q ，哟= 乙【纠，善为p m _ 1 次本原单位根， f = x + ( k ( x ) ) 。乙= 如，1 掌，孝，- q v 天g r ( q ，神都有唯一的一个p 一础c 表 示 a = 厶+ p + p 2 毛+ + p - 1 五- l ，五r 。 f r o b e n i u s 映射： f ：g r ( q ，肼) 专g r ( q ，帕 k 。- i p 五一y ：g p ，a 乙。 定义迹映射为g r ( q ，m ) 一乙；乙( 却= a + 五7 + + 名尸。 2 3 ( 函f o 妇扩环为倪4 ，埘) ： 吼9 = 吼坍) 【川u ：一1 ，显然孵m = 孵 v a g ，m ) ，a = a o + a l “+ + 一l “，一，q g r ( q ，m ) f r o b e n i u s 映射：a f = 嘞，+ q ，批+ + 口一一i ，甜，- 1 口fe g r ( q ，埘) 定义迹映射为乙= 4 + 口7 + + ，- 1 2 3m a t t s o n - s o l o m o n 多项式 设m 是使h l p ”一l 成立的最小正整数，设善为g r ( q ，聊) 的珂次本原单位根。 定义2 1 ；设c = ( c o , o , c i ，。，c ( 川 ，c o j c 1 ，l ，c ( 。1 ”，c o ，_ i ) ，气( ，i - 1 ) ，气，卜i h ，一i ) ) 6 鬻山旷 ，专 ， 刎二 ， 业n 山 ( 乙) 幽，c ( 幻= ：= ：勺石叫，c ( ) 的离散傅立叶变换为向量： ( i ，写，弘) 毛( “，肼y ，其中瓦= c ( 封；尹) = ：譬勺“如7 亭“，( o j ， 玎 耐= i m o d p ) 定义2 2c 的m s 多项式为： f ( z ) = 瓦。z 6 引理2 1 ( 反演公式) ：设c e ( 乙) 小，- ( z ) 为其m s 多项式，那么 c = ( 1 ，雄一， “，雄巾埘) 幸( 亭( 1 ) ，石g ) ，石( f ”1 ) ) ，其中木记为多项 式的卷积运算 证明：设o t 疗一1 ，那么有 万偕，) ：。孝一：n - i ( n - 19 k - i n - i _ _勺“机，眇苫一：艺窆勺“机，芝f 一。- 1 ) ：( 疗扩) 皇白万偕) = 。孝一= ( 勺“机7 眇苫一= 勺“机7 f 岬i o = ( 疗矿) 白 - o 扣01 = 0j 0j = o h - o j = o ( = o 当j o m o d 万对) 所以萨 ( 1 ，甜，甜“，”巾- 1 “) 牛( 万( 1 ) ，( o ，石( 尹- 1 ) ) 湘2 2 如果口( 砷啦) 豺一一1 ) 叫z 【z 】分别为其粥多项 式： ( 1 ) 口( x ) + 6 ( x ) 的播多项式为z 【z 卜召【z 】) ： ( 2 ) a ( x ) 6 ( x ) ( r o o dx ”一1 ) 的m s 多项式为彳【z 】木b 【z 】2 4 马z ( | c 记为多项式的卷积运算) ： ( 3 ) 向量0 和1 的m s 多项式为0 和z z 。： ( 4 ) z a ( x ) 的m s 多项式为a 4 彳( 孝- 1 z ) 证明：( 1 ) 和( 3 ) 显然，由于一”f 是一1 的根，所以( 2 ) 成立。 当6 ( x ) = x 时，( 4 ) 是( 2 ) 的特殊情况 令j 为模栉的p 一元分圆陪集代表元集，且m 。 刀是使印；a m o d n p 成 立的最小整数。 设s 是所有变换向量( - ，写，弘) e 墨( ，埘) ”的集合，且对所有口，有 ；，皿o d 。= - ，在s 中定义对加法和乘法的卷积运算使其成为一个环，则可直接验证 s 丝o 吼f ( ，”) 定义映射： 一咒九，) 哼s 矿( c ( x ) ) = ( o ，o 蠢- ) 一c h = c c u ” 、= , - “o z , 鼬j oc d a 函j p 为c 的第h 个傅立叶系数，则我们有下面重要定理： 定理2 2 令= 矿开，( 其中，力= l p 为素数) ，那么映射： 一九，) 州 是环同构映射 证明：由引理2 2 ，可知伊是环同态映射，下证矿是单射如果妒( c ( x ) ) = o ，那 么由反转公式知2 掣= o ( o t g 珂一1 ) ，由于“，= 1 ，甜的每一次幂从0 到 p l l 在和里只出现一次，因此对o s ，行一1 ，o 。叫叱 由此同构映射，及同构映鼽我们可将环r 一1 ) 分解成一些环得直和，来 研究此环上的重根循环码的结构，但用这种方法研究循环码的结构是很困难的， 所以本章将使用离散傅立叶变换分析釉t ) 上重根循环码的结构 3 2 g a l o i s 环 五= b t ) 为一个局部环，其最大理想为艘，商域为乃，设： ：e x l - f a x l ，l a ( j o = f ( m o d 圳 表示，到f ( r o o d 甜) 的环同态映射。 设埘为正整数，并且设g r ( t l k , l n ) = 剐毒场( z ) ) 为r 上次数为所的g 4 f d 括 扩张，称为r 的g 口f o i s 环，其中_ l 御为re 次数为m 的一个基本不可约名砸 式，且h ( x ) i x g 1 - 1 ，取f = 石+ ( 1 l ( 幻) ，f 为p ”- 1 次本原单位根，那么有 g r ( u k , 脚) = r 【纠为一个有限局部环，其最大理想为，剩余类域为，事实 上g r 0 ，帕为一个有限链环，因为其中每一个理想具有的形式为 办( o 茎f s k - 1 ) 我们可将映射t 很自然的扩展成为： 声：且) 一。) = _ ，+ ( 矗( y ) ) 卜 + ( p ( ，吼r ) ) 记集合乙= 0 ，1 ，f ，f ，- 2 ) ，v a g r ( ，m ) ，都可以唯一的表示成： 口= 口o + q “+ 嘞2 + + q i k - i 口j 乙 ( 口) = a o ，所以a 为一个单位当且仅当z ( a ) o 引理3 1 若d b 为一个环的幂零元，那么a 是一个单位当且仅当b 是一个单 位。 g r ( 矿，m ) 中的每一个元素也可以用f a d i c 表示为： b = + 两f + + b 卅- l f “。1 岛r f r o b e n i u s 映射f r ： 乃( 岛f 。) = 岛f 妒 下面我们定义g 足( 矿，肼) 的扩环： 哟c 脚咖啡，一1 ) 映射又可以很自然地扩展为： s s u s 1 ) ，一) 定义迹映射瓦：s 。( m ，) 一吼，即：瓦仁) = n 7 ( z ) 引理3 2 如果有限链环置：g r ( u ，码) ，是= g r ( ，) ，则r l 岛g 码i ；如果 1 2 羁c 岛，则g r ( u ，啊) = p e g r ( u ，r 坞) l f r 一铆= 刁 城咙正s 2 7 ，一1 ) 2 州 ( 1 ) v s s 有s = s ( c o ) = s o + s , ( c o 一1 ) + s 2 ( e o 1 ) 2 + + 占，- l ( 一1 ) ，一，其中墨e g r ( u ，m ) s o = s ( 1 ) ； ( 2 ) s e s 为一个单位当且仅当( 而) o ； o ) s 是一个局部环，其最大理想为( 虬：- 0 一i ) ，剩余类域为o ： ( 4 ) 飒是一个局部环，其最大理想为( u , - i ) ，剩余类域为c ； ( 5 ) s 是孵的g a l o i s 扩环，s 弁= s e s l f n ( o = s = 吼 证明：( 1 ) 坼e s 有s = s ( 奶= + 毛( 国一1 ) + 屯( 国一1 ) 2 + + s ，i ( 一i ) ，1 ( 2 ) 由引理3 1 若j = 工+ 缈为s 中的一个单位，当且仅当工为s 中的单位，如果x 在s 中为一个单位，显然有声o ) 在中也为一个单位，若o ) 为中的单 位，则有= 1 + u s x ，j s ，则搿7 为s 中的单位，因此若5 为s 中的单位，当 且仅当( 功为r 中一个g ：- 位，又因为u ( c o 一1 ) = 国一1 为影q 中的幂零元，如果 ，o ，w s = s o + ( c o 一1 ) ，有声( s ) = “) + p 一1 ) ( s ) ，因此若o ) 为中的单位当且仅 当u ( s 0 1 o ( 3 ) 因为v u s = f f ( c o - 1 ) ，) j 舻1 ) 兰。，_ 为一储贼所以 ( 甜，脚一1 ) 为一个最大理想，t i 正( u ，一1 ) 为唯一的最大理想，设j 薯( “，1 ) ，则 f ( s o ) o 由( 2 ) 知s 为s 中的单位，所以( u , 口o - i ) 为唯一的最大理想。 ( 4 ) 同理可证得9 l 是一个局部环，其最大理想为( ”，一1 ) ，剩余类域为乃 ( 5 ) 显然s 是筑的g a l o l s 扩环，s 丹= ps i f r ( s ) = s j = 孵 3 3 离散傅立叶变换 设m 为p 模玎的阶，即m 为使得p 。= i m o d n 成立的最小正整数，幺为 g 足( 矿，坍) 中的玎次本原单位根，即乞= f ，吃，其中；为g r ( 矿，m ) 中的p _ 一1 次 龋娅渺= 嘞刀，一。) 。q 纠- ) - 定义3 1 设c = ( c o ) ，v c 。o ( i ) ，r ( n - i ) ，。_ l ( 0 ) ，1 “( n - 1 ) ，哆_ ，档) r 一对应的多项式为 c ( = 妒x 埘， 定义c 的离散傅立叶变换为向量 ；= $ ，；妒_ 一) e ( 历，矗，r ，其中苏= c ( 珊。露) = 萎善g m 7 掣，( 。s | j l 拧。 朋= l i m o d p ) 。 定义c 的埘多项式为：g a z ) ：n - i “j - z 6 e 定理3 3 ( 反演公式) c 五巾，m ( z ) 为其反演公式。则 c = 9 ( 1 ，国一，脚- 2 a c 埘。一p ) 形( 心( 1 ) ，以慨) ，必( 筝，) ) 证明：设0 t n - - 1 ，那么有 h - 1 n - in - i - in - i ，- i n _ 1 ， - i m ( 幺) = ；一靠“= ( c 国腑叫掣) ，= 毋国柏”露。川( 群= o 当 _ ，0 m o d7 时) 所以c = 伊 ( 1 ，国州，国- 2 s , s o - n - i f ) 形( 丝( 1 ) ，坂慨) ，杠( 簖一) ) 定理3 4 设c ，d 科一一1 ) ，蜂( z ) ，鸩( z ) 分别为其淞多项 式： ( 1 ) 眠= o ，m , ( z ) - - e z ； ( 2 ) 虬( z ) = 批仁) ( 口r ) ； ( 3 ) 幔柑( z ) = 鸠( z ) + 心( z ) ； ( 4 ) 岛( z ) = 丝( z ) 允( z ) 将m 视为一个映射，即肌砒必”一1 - 4 c 寸帆( z ) ( o 万一1 ) ，我们有： c 扣= 丹( c ) ， 必却= 丹( 鸩j ) 设a2 ( 4 ，4 ，缸) e l 如= ，r ( 4 ) 在a 中定义对加法和乘法的运 算使其成为一个环，则可直接验证 a 兰。村斗( r a , ，) 令，为模万的p 一元分圆陪集代表元集，4 置。( ，t o ) ( j j i ，) 弓i 理3 3 设昨) = 4 蝉+ + 如e 文。一1 ) 为次数小于刀的多项式 若彳( ) = o ( o t ：；n - 1 ) ，那么4 ( z ) = o 证明：因为 ll 1 1 管 l 嚣q l ) 2 簖) 2 ( ) 2 4 4 4 ： 4 一i 范德蒙矩阵的行列式是n ( 幺一烈) 每一个“一纠是s 的单位。因此4 = o 设o h g n - 1 ，模n 包含h 的p - 元分圆陪集代表元集是 c l p ( h , n ) = h ，幼，纫2 ，助q l ， 其中是使幼 h ( m o d n ) 成立最小的正整数。 定舭s 删) 一a 一构怵其中 ，( c ( x ) ) = 【4 ，4 ，4 。】 证明：由引理3 4 ，可知，是环同态映射，那么由反转公式知，是单射，只要 证，是满射 设彳= ( 二，4 ，4 _ ) a 且彳( z ) = 4 z 。 我们只需说明 c _ 札( 1 “，也，m 州矿) ( 蛭( 1 ) ，心 ) ，鸠( 等1 ) ) 的分量在r 中即可因为向量c 对应的多项式为c ( x ) ，0 ( ) ) = 彳。事实上只 lliiiiiij卜 。盯哆州 需说明4 ( ) e 孵 引理3 3 说明丝( z ) = z ( z ) ( o g t g n - i ) 4 ( ) = 4 嚣= 4 彰 厂、 。 因为f ，l 4 彰l = 丹( 4 ) 卯= 如第= 4 彰，这说明 l j d ，聃一)，j t 咋o 一) j 截l e ( h , n ) 扣乩( 一) 4 舅s “= 孵，所以彳( ) 孵 推论3 1 ：如果c 是r 上长为p 疗的循环码，那么c 望e h , g ，其中 q = p ( 露) i c c ) 为( ，由的理想。 3 4 循环码的多项式表示 通过逆映耵可得到环五w 1 ) 中理想的多项式表示 v ( 巩x | ，o e ，& ( ，国) 我们能得到相应的元素d = ( 磊，嘎，钆) a ，并且钆= 丹( 吨) 设 彳( z ) = 矗叫z 7 ( d h ) h a 在y 下的逆映射为： ，。( ( 吨) 。“) = 矿 ( 1 ，珊“，沪，一d 矽) 么( 彳( 1 ) ，彳( ) ，彳( ) ) ， 且，。( ( 以) 埘) r x l ( x ”- 1 ) 下面我们具体的计算逆映射我们固定厅，并且vj ( 脚，) 考虑元素 秀( s ) = ( o ，o , s ，o ，0 ) e 吼e ，露( t n , ，国) ，其中s 是第h - 分量。 我们设 e 。，( x ) = y 。1 ( 或( s ) ) ，即e ，( x ) 黜i x l ( x ”一1 ) 中的元素，并且 ( 幺) = 信矗产矗似，) 引理3 4 设：( 6 0 , m h ) - + 9 的迹映射，定义为：死( z ) = f r 7 ( z ) 那么：( x ) = 札( 1 ，缈1 ，彩唰，缈廿妒) ( ( s ) ，_ ( s ) ，( s ) 6 ) ) 证明：因为 彳( ) ：n - i 吃铲：嘭：m - i 乃，( 。) 缈：笙乃，( s - ) ：墨o 知) ，- oj e 啡( 月) ，i o ，量0 所以： ， 最，) = 妒 ( 1 ，0 7 - s ，m “，国+ 咿) z ( _ ( s ) ，( s p ) ， ( 量掣“) ) 映射s 寸e ，( x ) 是( 彩，m h ) 到r x g ( x ”一1 ) 的同态映射， ，1 ( ( ) 。，) _ 否( x ) 毗，只需计算s 2 l ，姐d 钿= 护舻1 时的 e ，( x ) 就足够了设易( x ) = e j ( _ ：j ) ，i 泌) = 6 ( j ) ( v6 孵，m = l m o d p ) 引理3 5 ( 1 ) e ( x ) = 么羹_ ( ) 删劬) ( 2 ) 一( x ) = z 耐毛( 奶 ( 3 ) 磊铂) = 薹毛( 禾断茸矽。栩 证明： ( 1 ) 毛( x ) = e j ( x ) = 伊 ( 1 ，国”，口m ，印+ 。p ) 么( _ ( 1 ) ，( 6 ) ，( 坤) ) = 善n - - i ( 靠聊) x j ( 1 ” ( 2 ) 一( x ) 2 9 ( 1 ，国”，国- 2 n oo 国+ 叫) 么( 气”) ，气( 靠6 ) ，( 国。掣“) 6 ) ) f i x “e ) ( 3 ) e 铀2 尹 ( 1 ，( o - n ，彩制，国帕矽) z ( ( 缸1 ) ，( 缸) ，墨( 缸l 靠删) ) = l 玎丢n - ! ( 旬，】靠9 声川m “ 1 7 因为毛( ) 2 ( 却) ，所以：z 。c x ) 2 毛( 靠茸) x x “铀 j 时 l t d ，u j v j 。莩军氧l 口& ( 织) ，e 胄，我们将其中的血1 ，换为e 讯l ( x ) ， x 耐得。 s ( e 铀( n z 耐) 2 莩；e 缸( x 耐掣”一。) ， 定理3 6 e ，= s ( e 讯l ( x ) ，x 埘，) 局( z ) 证明：由定理3 5 及$ 1 - - e ，是同态映射和毛( z ) e ，( z ) = 咒，( z ) 可得 e ，；s ( e 讯l ( z ) ，x 耐) 巨( 彳) 我们引入另一个逆映射，vs e ( 珊，) ，设 d ：( s ) = ( 1 ，1 ，s ，l 1 一，1 ) o 脚( 职一) ， 辄肌蝇并蚝( 删r 必”一1 ) ，使得 吼( 彰) = 孙n 因为( s ) = ( 1 ，x ) - a ( 1 ) + 以( s ) ，我们有： g ，( z ) = 1 一毛( z ) + e ，( x ) 定理3 7 设c c 斗( 致) ，g 为理想( h e l ) 。我们假定g 的形式为 g 2 ( 6 i ，6 2 ：，岛，岛) ( 屯e r ) ，且& ( 出，) ，那么： y - ( o 村g ) = ( 6 l 兀g 舳( x ) 岛兀瓯 ：( x ) ，岛兀g 山( x ) ) “删hel i 证明：岛u ( ) 2 ( t e ，l _ ，川 定理3 7 和g ，( z ) = l 一毛( z ) + e ，( x ) 提供给我们一个具体的方法计算 埘多坛w 一1 ) 的理想的生成多项式，根据已知的其相对应。( q ) 的理想。 1 8 3 5 卧( 坍，) 的理想 在妒节，我们给出跏川2 ，呐，一。) 的弧设；为环 _ ，矿 定义3 2 设c 为环r 【纠上长为l 的码，定义： t o r , ( c ) = “v e 五【f 】，l u i v 6 c ) ( o s f 七一1 ) 觋( c ) 称为码c 的i t ht o r s i o n 码。砜( c ) = ( a 称为剩余类码，记为r c s ( c ) 则： 气南钆 0 地弛2 0 0 2 毛 0oo - z 耻_ ) l c l = p ” 4 “ 批4 j - i 2 4 j - l 甜h 屯 。上的码t o r , ( c ) 的生成矩阵为：a ， 则：i t o r , ( c ) l = - 兀p 帕 4 j 址“ “2 4 j “h 4 - i j 气4 j4 2 4 4 j 0 4 2 4 i4 j 0 0 气4 纠4 j i； ；i 00 0 如 定理3 8 r 眵】上的码c ，我们有i c l = | 兀乃( c ) l 。 证明：兀k - ii r o t , ( c ) i = f i i ! i 一：p “鬻- - p ”驴m 刊c证明：兀兀n p 帕= p 盏盏。笳刊c 扣0 s - o , i - , 0 弓f 理3 6 设0 f s k - 1 ，o ，s p 一1 ( 1 ) 如瓢冰啦m 使得在科纠，- 1 ) r f | d e g g ( 小蚰妇( 咖。在 硝纠，- 1 ) “瓤咖净“蜘! 撕叫钏】 ( 2 ) 如果砌”纠艄在f ，_ 1 ) 矿”咖- o 那么 j r ( ) = ( 国一1 ) ，叫石( 国) 其中z ( 珊) o 【m 】 证明：( 1 ) 因为g ( 缈) ：宝g i p 1 ) 其中盔e 丑眵1 。那么 g ( ) = 材。& ( 国一1 ) l = o ，则在五 f 】中“& = o ，则岛= “愿，其中 拈势叫；( 2 ) 如果在_ - 1 ) ，) 中时啪_ o ，黼在 4 ( 0 0 ) 0 【国】使得在0 【】中0 【由】( 国一1 y ( ) = 石( 口) ( 一1 ) ，则 ，(