（应用数学专业论文）域fq上广义rs码的一类扩充码.pdf

巾山大学硕士学位论文 域f 。上广义r s 码的一类扩充码 专 业：应用数学 姓名：徐春平 指导教师：胡国权 摘要 多项式码是一类非常重要的码，具有性能好，构造简单等特点，近年来在 这一领域有许多人做了大量的工作。域r 上的广义r s 码作为多项式码，在具 有上述优点的同时，码。k n 受到q 的限制。为了解决这个问题，c x i n g 和s 1 i n g 借助r 的扩域f 4 z 上的元素对其进行了扩充；随后，s l i n g ，h n i e d e r r e i t e r 和 c x i n g 利用对称多项式构造码，将扩域的次数s 由2 推广到任意正整数：n a y d i n 和d kr a y - c h a u d h u r i 则用直接的方法将扩域的次数s 由2 推广到任意 正素数。他们在使码长n 突破口限制的同时，得到了许多性能较优的码。 本文的研究就是在文献 4 的基础上开始的，首先，为得到更多的码，在扩 域次数s 等于3 时，我们引入了一个新的参数来构造码，对其作了详细讨论， 并补充了3 整除坷时的详细讨论；然后，在扩域次数s 为素数时，构造码时， 我们引入了r 中的元素，因此在对码的参数进行估计时，是分“s 整除口时” 和“s 不整除q 时”两种情况来讨论的；最后我们补充了扩域次数s 为非素数时 码的构造，即设b 为s 的非平凡因子，先将j 0 和，。- 中的元素分为若干个共轭 类：卢，卢2 f 。( i = s ，b ) 共轭是指它们是f q 上同一个i 次不可约多项式的根， 引入局t 和f 。中的元素来构造码，并对其进行了参数估计。 根据本文的新构造方法，我们得到了一些与 1 对照参数较优的码。 关键词：线性码，多项式，最小距离，扩域。 巾山大学硕士学位沦文 ac l a s so fe x t e n d e dc o d e so fg e n e r a l i z e dr - sc o d e so v e r f q m a j o r ：a p p l i e dm a t h e m a t i c s n a m e ：x uc h u n p i n g s u p e r v i s o r ：h ug u o q u a n a b s t r a c t p o l y n o m i a lc o d e sa r ec o d e so fa ni m p o r t a n tc l a s s ，h a v eg o o de r r o r - c o r r e c t i n g a b i l i t ya n dc a nb ec o n s t r u c t e de a s i l y i nr e c e n ty e a r s ，m a n yp e o p l ed i dm u c hw o r ki n t h i sf i e l d a sp o l y n o m i a lc o d e s ，g e n e r a l i z e dr sc o d e so v e r 凡h a v et h ea d v a n t a g e s d e s c r i b e da b o v e ，b u tt h e kl e n g t h sna r ea tm o s tq i no r d e rt oi n c r e a s et h el e n g t h o fc o d e s ，c x i n ga n ds 1 i n gg e n e r a l i z e dt h ec o n s t r u c t i o n so fg e n e r a l i z e dr sc o d e s u s i n gt h ee l e m e n t so ft h ee x t e n s i o nf i e l df 辛o ff q s u b s e q u e n t l y , s l i n g ，h n i e d e r r e i t e ra n d c x i n gc o n s t r u c t e d c o d e s b ye v a l u a t i n g t h e s y m m e t r i c p o l y n o m i a l so v e rf q ，a tt h ee l e m e n t si nt h ee x t e n s i o nf i e l df fo f q ，w h e r esi sa n a r b i t r a r yp o s i t i v ei n t e g e r n a y d i na n dd kr a y - c h a u d h u r ig e n e r a l i z e dt h e c o n s t r u c t i o nd i r e c t l yf o rt h ee x t e n s i o nf i e l df fo t f q ，w h e r esi sa na r b i t r a r yp o s i t i v e p r i m e t h e yh a v ec o n s t r u c t e dal o to fc o d e sw i t ho p t i m a lp a r a m e t e r s w eb e g i no u rw o r ko nt h eb a s i so f 【4 】f i r s to fa l l , w ei n t r o d u c eo n en e w p a r a m e t e rt oc o n s t r u c tc o d e sf o rt h ee x t e n s i o nf i e l do fd e g r e e3 m o r ec o d e sa r e o b t a i n e da n dd i s c u s s e di nd e t a i l w ea l s oh a v ead i s c u s s i o no nt h ec o d e sw h e n q c a nb ed i v i d e db y3 s e c o n d l y , w h e nt h ed e g r e eo ft h ee x t e n s i o nf i e l dsi sap r i m e ， w eu s et h ee l e m e n t so f 凡t oc o n s t r u c tc o d e s ，s ow eh a v et od i s c u s st h et w oc a s e s ： sc a nd i v i d eq ”o r ”sc a nn o td i v i d eq ”f i n a l l y , w es u p p l e m e n tt h ec o n s t r u c t i o n w h e nt h ed e g r e eo ft h ee x t e n s i o nf i e l dsi sn o tap r i m e s e tbi san o n t r i v i a ld i v i s o r o fs ，w el i s tt h ee l e m e n t so ff q ，a n df 矿i n t od i f f e r e n tc o n j u g a c yc l a s s e s ：w h e r e 卢1 ，卢2 e f 4 r ( i = s ，b ) a r es a i d t ob ec o n j u g a t ei f ft h e ya r er o o t so ft h es a m e i r r e d u c i b l e p o l y n o m i a l o v e rf 。o fd e g r e ei w ei n t r o d u c et h ee l e m e n t so f f i a n d f t oc o n s t r u c t c o d e sa n d e s t i m a t e t h ep a r a m e t e r o f t h e m w eo b t a i ns o m eb e t t e rc o d e sb yu s i n go u rn e wc o n s t r u c t i o n s ，c o m p a r e dw i t h t h eo p t i m a lc o d e s i n 【1 】 k e yw o r d s ：l i n e a rc o d e s ，p o l y n o m i a l s ，t h em i n i m u md i s t a n c e ，e x t e n s i o nf i e l d 中山大学硕十学位论文 第1 章背景知识 1 1 数字通讯与纠错码 通讯是由甲地的信息传送到乙地，通常把甲地叫信源，把乙地叫接收者。一 个数字通信系统主要由信源、信道、信道编码器、信道译码器和接收者五个基本 部分组成。 实际上，我们又必须考虑到，信源发出的数字信息在传送的过程中可能会受 到种种干扰，这样接收者接收到的数字信息就不再是信源发出的数字信息，即我 们通常说的信息失真。为了使信息源发送的信息能准确地传给收信者，除采用技 术上的种种措施外，还要采用抗干扰的编码方法，从而不但能检验出信息在传送 中是否发生错误( 检错码) ，而且能够对发现的错误加以纠正( 纠错码) 。这也就 是说，在数字信息传送之前，先进行一次编码，再传送。考虑到实际的需要，我 们往往对纠错码更感兴趣。数字信息经过信道编码之后具有以下性能：一旦由于 干扰发生了传送错误，在允许的错误量范围之内，接收端可以检验出错误并能进 行纠错。接收端的这一操作叫译码。译码后的数字信息传给接收者，完成整个传 送过程。可以用框图表示如下： 图1 1 巾山大学硕十学位论文 1 2 码的定义及相关概念 数字信息利用有限域，q 上的七维向量：0 。，a 。，a ：，口。) 来表示。为了使 通讯系统具有纠错能力，我们增加向量的维数，使之变为n ( ，z ，k ) 维向量 ( a o ，a i ，a 2 ，a 一，a 一a ) 。也就是说，是建立向量空间n ( f 。) 到向量空间 n ( f 。) 的一个一一映射，这里n 陋。) = a 。，口。，a ：，a 。) ：口。e f 。) 。 定义1 1 一般地，设信息源的数字信息的集合是n 陋。) ，q 是一个素数的 幂，而，z 是大于七的一个整数，设盯y t 叭v k ( f ，) 映入旧。) 的一个一一映射 口：v t ( f 。) 一v 。( f 。) ( 口o ，a l ，a 2 ，a 女一1 ) 卜( 口o ，a 1 ，a 2 ，a t 一1 ，a i ，a 。) 记c = 盯( n ( f ，) ) ，那么c c v 。( f 。) 。v 。( f 。) 的这个非空子集c 叫做一个g 元 码，c 中的向量叫做码字，甩叫做码长，而码字中的分量叫做码元，如果j c i = m 我们称c 是一个口元0 ，m ) 码。 码率：一个q 元( 厅，m ) 码c 的码率定义为 r ( c ) ：l o g 口m 。 挖 h a m m i n g 距离：设x ，y n ( f 4 ) ，x 和y 的h a m m i n g 距离d o ，y ) 定义为石 和y 中不同分量的个数，简称距离。即设z = ( 舶，工：，x 。) ，y = ( y l , y ：，y 。) 对于i = 1 , 2 ，r l ，定义 m 彬沪 ：! 麓咄= y i 则d ( ) 2 善d ( 础) 。 h a m m i n g 重量：工y 。( f ，) ，石中非零分量的个数称为h a m m i n g 重量，简 中山大学硕士学位论文 称重量，碳j w ( x ) 。设x = ( 石，z ：，z 。) ，对于i ；1 , 2 ，门，定义 毗，2 口麓二0 则 ) = ( 溉) 。码c 中所有不为。的码字的重量的最小值，也即 i = 1 m i n w ( x ) ：x e c ，x 0 ) 叫做码c 的最小重量。 由距离和重量的定义我们不难看出 对任意x ，y n ( f 。) ，a ( x ，y ) = w ( x y ) 。 最小距离( m i n i m u md i s t a n c e ) ：设c 是一个( 肛，m ) 码，码c 的最小距离定 义为c 中任意两个不同的码字的距离的最小值，记为d ( c 1 ，即 d ( c ) = r a i n 似( x ，y ) ：石，y e c ，x y a 线性码：设c 是码长为n 的留元码，即cc v 。( f 。) ，如果c 是儿( f 。) 的子 空间，我们就浣c 是g 元线性码。 显然，q 元线性码c 的码率r ( c ) ：生，最小距离等于其最小重量。 我们用0 ，m ，d ) 表示码长为n ，码字个数为m ，最小距离为d 的码，用 i n ，k ，d 表示码长为, r ，维数为k ，最小距离为d 的线性码。无特别说明，本文 所有的讨沦均是在线性码的范围内进行的，所有符号的含义参见文献【4 】。 1 3 有关译码和码的纠错性能的基础知识 我们假设数字信息是在一个q 元对称信道传送的，即 ( 1 ) 每个字符在传输过程中发生错误的概率相同，都为p 。 ( 2 ) 如果一个字符在传输过程中发生了错误，则它错为其它q 一1 个字符中的 任意一个的概率是相同的。 r i i 山大学硕士学位沦文 我们还要假设：收到一个字是从一个码字经错传较少的位数而来的可能性， 比从一个码字经错传较多位数而来的可能性要大，即p = 1 。从直观上来理解， 要求信道对数字信息的每一分量来既，正确传送的可能性比错误传送的可能性要 大，这是合乎情理的，否则这个信道的可靠性令人质疑，也就失去了使用的价值。 有了以上两个假设作为前提，通常译码采取的方法是极大似然译码( m a x i m a l l i k e l i h o o d d e c o d i n g ) ：设码字石经信道传送后，我们收到向量y ，由于干扰因素 的影响，可能石一y ，更甚者y 可能不是一个码字，此时，我们将y 译为与y 的 距离最小的码字x 。 需要注意的是：这罩的x 并不一定就是x ，也就是说采取这种策略并不总是 译码正确。这就要求码字在传送过程中的出错位数必须在码c 的纠错能力之内， 否则就会出现译码错误。 码的最小距离是刻画码的检错( e r r o r - d e t e c t i n g ) 和纠错( e r r o r c o r r e c t i n g ) 性能的一个重要参数。 更加具体的描述通过下面这个定理给出： 定理1 1 码c 至多可以纠难t 个错误的充分必要条件为d ( c 、= 2 t + 1 或 丑+ 2 。 定理的证明参见文献【9 】。 下面我们只从直观上来解释一下这个定理： 对任意x n ( f 。) 以及整数r 0 ，以x 为中心，以，为半径的球( s p h e r e ) 为 s 。( x ，) = y 矿。( f 。) ：d ( x ，y ) s ，) 。 设c c v 。( f 。) 是一个码。若d ( c ) 2 2 t + 1 ，则以c 中的码字为中心，以f 为 半径的球互不相交。事实上，如果y e s 。x ，t ) n s 。x ，f ) ，其中x c ，则我们有 d ( x ，x ) 蔓d ( x ，y ) + d ( z ，y ) s t + f ；2 t ，这与d ( c ) 2 t + 1 矛盾。 中山大学硕士学位论文 如图1 2 所示 图1 2 设x 为要发送的码字，y 是在接收端接收到的向量，并且x 在传送过程中错 误不多于f 个，即d ( x ，y ) s t ，则一定有y e s 。( 工，t ) ，根据极大似然译码，y 被 正确译为x 。如图l 3 所示： 图1 3 推论1 1 c 是一个鼢距离为d 胍鹏睚多可州正【竿卜 误。 总结以上知识，我们得到以下结论：一个好的q 元【，z ，k ，d 】码，应该具有如 下性质： ( 1 ) 为了更快地传送信息，就要尽量减少信息的冗余度，即码长，z 应该尽 可能小； ( 2 ) 为了更多的传送信息，码字个数m 应该大，即维数k 应该尽可能大； ( 3 ) 为了能纠正更多的错误，最小距离d 应该尽可能大。 事实上这些条件是相互矛盾的，纠错编码的主要目标之一，就是要寻找这些 条件之间的一个平衡点，构造出能纠正尽可能多的错误并且冗余度又不大的好 码。 中山大学硕士学位论文 第2 章广义r s 码及其在域r 上已有的扩充 2 1 广义r s 码 多项式码是一类非常重要的码，具有性能好，构造简单等特点。截短r s 码是一个多项式码，其构造如下： 设，k 为两个整数，且1c n s q ，1 s k n ，p 。表示，。i x 中次数小 于k 的多项式的集合。选取f 口的个子集 a 。，a ：，口。 ，定义广义r s 码如 下： g r s ，( ，k ) = ( ，( 口。) ，f ( a z ) ，q 。) ) ：f ( x ) e p 。) ， n a r s 。( ，k ) 是一个参数为 ，k ，n k + 1 的q 元码。 根据定义，我们知道广义r - s 码是f q 上的m d s 码( 详见文献【5 】) 。码 g r s 。( ，k ) 的码长n s q ，因此它的维数足s s q ，因此码g 黜。( ，k ) 能够 传送的信息量会受到很大的限制。我们希望能选择，。的某个扩域f 矿的某个子 集z ，借助丁中的元素来构造码，突破g 对码长的限制，使码g r s 。( ，k ) 得到推 广。 为了使推广后的码仍然是，。上的码，我们要适当地选取多项式f ( x ) ，即： ，0 ) f 。【x 】，使得对任意卢t ，都有，( 卢) f 。因为t 是f 。的扩域f 。，的 某个子集，所以往往要求f ( x ) * f f ：, g f l f 。一，有，( 励f 。 基于广义r s 码的这种局限性，许多人对这一问题进行了深入思考，作了大 量的工作：先构造这样一类特殊的多项式，o ) ，弓i k f 。的扩域f 矿中的元素 来构造f 。上的码，使码长突破了q 的限制，得到了许多参数优于【1 】中最优码的 新码。 中山大学硕士学位论文 2 2 在f 。上借助2 次扩域f 。：对广义r - s 码的扩充 c x i n g 和s 1 i n g 在文献【2 】中借助f 目：中的元素对广义r - s 码进行了推广， 其主要构造过程如下： 首先，设f 。= k 。，a ：，a w ，因为对所有的p e f 。z f 。，有卢9 卢成 立，所以我们可以列举f q z 的元素如下 f 。：= 口。，口：，a 。，卢。，卢；，卢：，卢；，卢，卢3 其中r = f q 2 一q ) 2 。 对i ，j 芑0 ，当q 为奇数时，令b ，j ) = x 4 + + x 州；当q 为偶数时，令 ，、r x 9 + 十护“，如果i j “叫2 i x 一，女果i ；， 显然，对任意卢f g ，一f q ，e i , j ( f 1 ) e f g 。 设聊为整数，且15 m 蔓q ，用y 。表示集合 。，b l o s i 蔓，s 优一1 在f 。上 张成的f 。i x 】的线性子空间。不难看出，对任意卢f 。s f 口，( x ) e v 。 f ( f 1 ) e f 。 当0 s t 蔓q ，1 s ms q 一1 时，定义 c 。( f ，m ) = ，( a 。) ，( a ：) ，( 口。) ，f ( f l 。) ，f ( f l ：) ，f ( f l ，) ：，( 工) f ，。 。 则c 。( f ，m ) 是一个q 元线性码，码长厅= f + ( q 2 - q ) 2 ，维数忌= j 1 ( m 一1 ) 。当 q 为奇数时，最小距离dz ，l 一三( ( q + 1 ) + 1 ) + m i n 2 ( m 一1 ) ，f ”；当g 为偶数时， 最，j 、距离d2 以一三( ( q + 1 ) ( ，”+ 1 ) + m a x 2 t 一目，m i n ，行一1 ，f ) ) 。 在这里，码c 。( f ，m ) 的维数由m 唯一决定。为了得到更多的码，又引入了参 数z ，对m 2 和0 szs m 一1 ，令v 。j 表示由集合 中山大学硕+ 学位论文 缸，( x ) ：0 s ie ，s 历一2 u e 。，一，( x ) ：o 蔓f 茎z 在f ，上张成的n 【x 】的子空间( 实际上，当z = 埘一1 时，有n = v 。) 。构造 码 c q 0 ，m ，f ) = ，( a 1 ) ，( a ：) ，( a 。) ，( 卢，) ，f ( f l ：) ，( 卢，) ：f ( x ) e v m 。 关于码c 。0 ，珑，) 的参数估计和其它详细的讨论可参看文献【2 。 用这种构造方法得到了许多新码，这些码比已知的最优码【1 】具有更好的性 能。以g = 7 ，8 ，9 时为例，详见附录i 。其不足就是仅仅考虑了扩域的次数s 为 2 的情况。 2 3 在f 。上借助任意次扩域f 。t 对广义r s 码的扩充 s l i n g ，h n i e d e r r e i t e ra n dc x i n g 在文献 3 中利用f 。上初等对称多项式 将f 。的扩域的次数s 推广为任意正整数，具体操作描述如下 设q 为素数的幂，s 为任意正整数。考虑凡 卫，】，】上的多项式 巅6 r 一) 叫一r 1 坳y “+ 十( 叫一嘶y + ( _ 咖， 显然对1 s iss ，盯。为f 。b 】上关于符号盖，x q , j - ，x 。“1 的初等对称多项式。 令( ，：，) 为s 元非负整数组，定义f 。 z 】中的多项式e 1 川，l 如 下： e ，1 ，2 ，：= 仃1 ) l 盯2 j z 盯j & ， 设2 s ms q ，z = ( 1 1 ) f 2 ，f 。一1 ) e z ，r o s l ，一1sz 卜2 s s s ，挖一l 。令y ；押是 由集合 h 以2 ：- ，。s 聊一2 ，j ：o u e 。：墨，j = 小一1 ，；芑0 ， j ，s ，一- ，+ ，s ，一：，： sz ) 中山大学硕士学位论文 在凡上张成的f 。i x 】的线性子空间。 用符号l q o ) 表示f 。上不同的s 次首一不可约多项式的个数，a ( s ，m ，f ) 表 示集合 e j ，j 。：z - ，= 聊一l ，j ，芑o ，j ，s f ，一，+ j ，。s ，z ，：j ，sz ， 的元素个数。 对s 2 ，0sts 窜，1 sr 5 i q ( s ) ，2 s ms q ，z 按上述定义，定义一 个f 。上的码c 目( s ，t ，r ，m ，f ) 为 c ，0 ，t ，r ，m ，f ) = ( ，( 口t ) ，( 口：) ，( a ，) ，f ( f l ，) ，f ( f l ：) ，f ( f l ，) ) ：，( x ) i ， ， 其中，厶o ) 己r ，；( ( 历一1 ) 矿- i + 厶q , - i q _ t ) ，卢，卢：，卢，为f ，上不同的s 次首一不可约多项式的根。 q 元码c 。( s ，t ，r ，m ，1 ) 的码长为，l = t + r ，维数 最小距离 七：f m + 5 2 1 + 4 ( s ，m ，f ) s d 己r 一( 仰一1 ) q “+ 橐q 5 - i - 1 _ t ) 。 5 关于这一内容的讨论，详见文献【3 】。 按这种构造方法，得到了不少新的达到【1 】中最优码的界的好码，见附录i i 。 2 4 在f 。借助素数次扩域f 。s 对广义r s 码的扩充 n a y d i n 和d i cr a y c h a u d h u r i 文献【4 】中，用文献【2 】的思想直接把n 的 扩域的次数s 推广为任意素数： 当s 为素数时，对任意3 f 。，一f 。，它一定属于一个大小为s 的共轭类 9 中山大学硕士学位沦文 卢，f l q , 卢。，卢。 ，这样的共轭类共有型个。 s 用向量云表示s 元整数组( i ，i ：，f ：) ，其中 0s i l s i 2 s s i ；s m 一1 s q 一1 表示左循环移位：, t ( i ，i ：，玉) = ( f ：，i ，i 。) ，表示按如此方式循环移位n 次。 定义 气( x ) ：= z q ”1 目2 ”训“b 以， j - 1 则对任意卢f q 5 ，有e f 够) ，。 令y ，表示由集合 巴 ) ：0 s j ，s i zs s i ，s m 一1 s q 一1 ) 张成的f 。上 的线性空间，则a i m 以”2 ( 肼+ ；一1 ) 。 对1 sb r = 垡 ，1 s ms 1 + t b s ( q - 1 ) ，定义f ，上的码c ，m ) 为 s口一1 c 。( b ，m ) = ( ，( 卢。) ，f ( f l ：) ，f ( f l 。) ) ：， ) “。) 其中卢j 耿自型个不同的共轭类。 s 则此码的长，z ：6 ，维数忌：m + 5 1 1 ，最小距离d 6 一型q s - 1 。 l s j s 口一1 另外文献【4 】还给出了从另外一个角度构造这种扩充的多项式码： 设s 为素数，p k 表示凡上次数小于七的多项式的集合，整数6s 缎。定 义线性空间n = f ( x ) e p 。：f ( f l 。) ，f ( f l ：) ，f ( f l 。) f 。 ，其中卢。含义同上。 类似地，可利用n 来构造码，随后文献【4 耐论了n 。的维数。详细过程见文献 【4 。 巾山大学硕士学位论文 第3 章在域r 上对广义r s 码新的扩充 上一章我们介绍了一些广义r s 码在域f 。上已有的一些扩充：文献【2 】借助 f 。扩域r z 上的元素对其进行了扩充。随后文献 3 利用对称多项式构造新码， 将扩域的次数5 出2 推广到任意正整数：文献【4 】则用直接的方法将扩域的次数s 由2 推广到任意正素数。 但是文献 4 存在许多未完成的工作：( 1 ) 扩域次数s 为3 时，码的维数由 一个参数m 唯一决定，且当3 整除q 时没有详细讨论，因此我们可以考虑引入一 个新参数f 从而可得到更多的码，且增加3 整除q 时码的构造及其参数估计的 详细讨论；( 2 ) 扩域次数s 为素数时，构造码没有引用j 0 上的元素，故对码的参 数进行估计时，没有关于s 是否整除q 的讨论，我们将对这一点加以补充；( 3 ) 没 有扩域次数s 为非素数时的讨论，因此我们在这一章会给出s 为非素数时码的构 造，并给出码的参数估计。 3 1 扩域次数s 为3 时的新扩充 对s = 3 且3 不整除q 时，为了得到更多的码，我们引入参数z 对m 2 ，0szsm 一1 ，令 e 。，驯= e 。小 ( x ) ：0 蔓i 蔓，兰k 蔓m 一2 ) u e f 。一l ( x ) ：0s isjsf ) a 设矿祁是由e 。，纠在f 。上张成的线性空间。显然，当，；历一1 时， v m 3 j = v m3 。 定义3 1 对。sfsg ，1 6 ：r ：q 3 _ _ q ， j 1 1 湍 smv i2 中山大学硕士学位论文 0 s l 蔓m 一1 ，定义r 上的q 元码 c 。( f ，b ，m ，z ) = ( ，( a - ) ，f ( a ：) ，( a ，) ，f ( f l ，) ，f ( f l ：) ，f ( f l 。) ) ：f ( x ) e v 。川 ， 其中e u ，口z ，屈的定义同文献【4 】。( 无特殊注明时文中e w ，口。，3 j 的含义 均与此相同。1 定理3 1 当3 不整除口时，对2 主肌；1 + 之! 兰生和o s fs m 一1 ， q + q 1 - 1 c 。( f ，b ，m ，z ) 是一个q 元【，z ，k ，d 】码，其中 n ；t + b ， 拈l 。n ( - 1 ) ( m + 1 ) + 丢( ，+ 1 ) ( f + 2 ) ， d ，2 一言( ( m 一1 ) q 2 + l ( q + 1 ) + 2m i n m a x 3 ( m 一2 ) ，川+ 2 f 一1 ) ，f ) ) 。 证明：码长n 是显然的；维数 k = i e 。 。( x ) ：0s i5 ，s 七s m 一2 ) i + i e ：，。一。( z ) ：0si ，5f ) l = i u ，j ，忌) ：0 蔓i 蔓，s ks m 一2 ) l + l o ，) ：0 蔓i s ，sz ) l ；i 1 埘( 优一1 ) + 1 ) + i 1 ( z + 1 ) ( z + 2 ) 下面来讨论最小距离d 。设在集合亿。o t ：， 中f ( x ) 的根的个数为n ， 在集合 卢。，卢：，卢， 中f ( x ) 的根的个数为r ：。 因川刈1 士= 思e r - 口r ，b ，m ( 0 0 = 口”，集合 x 1 + + ：0 s isjs ks m 一2 中 元素的最高次数为3 ( m 一2 ) ，集合b ”肭。：0 s is ，s f 中元素的最高次数为 m + 2 l 一1 ，所以有，1 m i n m a x 3 ( m 一2 ) ，m + 2 1 1 ，f ) 。 对任意， ) n ， ，d e g ( f ( x ) ) 蔓( m 一1 ) q 2 + z ( q + 1 ) ，所以有： r 1 + 3 r 2s ( m 一1 ) q 2 + f ( q + 1 ) 。 更进一步有 中山大学硕十学位论文 所以 故 2 r l + r 1 + 3 ，2s ( 州一1 ) q 2 + f ( q + 1 ) + 2 m i n m a x 3 ( m 一2 ) ，m + 2 l q ，t ， r l + 班；( ( m _ 1 ) q 2 + z 国+ 1 ) + 2 m i n m a x 3 ( m - 2 ) ，m + 2 f - 1 力) d = 珂_ n _ r 2 己，z 一三( _ 1 ) 口2 + f ( q + 1 ) + 2 m i n m a x 3 ( r n _ 2 ) ，m + 卫- 1 一) 。 取q = 4 ，且6 = ，= 2 0 时，得到一些码，如下表 l m ， ，z kd do d2j2 041 31 3 0322 01 068 d3d2 041 51 3 j2j2 141 41 4 3312 3791 2 3322 31 071 0 4312 4791 3 4302 441 21 6 口 表3 1 注：d 。为【1 】中最小距离的界。表中斜体表示用我们的构造方法得到的优于 【1 】的码或次最优码( 概念见文献【4 】) 。下同。 中山大学硕士学位论文 取q = 5 ，且b = r = 4 0 时，得到的码，如下表 tm f 凡 七d db 0434 02 091 3 04 24 01 61 11 5 d2 j4 0 4 3 33 口 j2 4 1 4 3 33 0 22 j4 2 4 3 23 1 33 24 31 02 22 3 对s = 3 且3 整除目的情形，我们给出码的构造，并对其进行详细讨论如下： 首先定义： 民“小譬冀鬻麓。恸l 令，s 是由集合 巴。 ) ：0 s js ，s 尼s 埘一1 ) 在n 上张成的线性空间。 定妯z 桃一鲋吖2 挈一器，定 义f 。上的q 元码 c ，0 ，b ，脚) = ( 厂( a ，) ，f ( a ：) ，( a ，) ，( 卢，) ，f o o ：) ，f ( f l 。) ) ：f ( x ) e v 。， 。 定理3 2 上述定义的码c ，( f ，b ，m ) 是一个q 元【，z ，k ，d 】码，其中 后= 1 6m ( 小+ 1 ) ( 聊+ 2 ) ， d 甩一号( ( q 2 + q + 1 ) ( 卅一1 ) + m a x 3 t - q , 2m i n 川一1 ，f ) ) 。 证明：码长挖= t + b 是显然的，关于维数七的讨论见文献【4 ，下面讨论最小距 中山大学硕士学位论文 离d 。 设 m ) 2 荟。+ 颡甜( 工) 。 情形1 ：a 。n 。= 以l l ，l = = 以川川= o 对任意a f ，有e u ) = 3 口”= 0a 所以在集合 卢。，卢：，卢j 中，0 ) 的根的个数至多为( d e g ( f ( x ) ) 一q ) 3 个，从而在集合缸。，口：，口，卢。，卢：，卢。) 中，o ) 的根的个数至多为t + ( d e g ( f ( x ) ) 一q ) 3 个。 故 d _ f z 一( f + l ( d e g ( ，( x ) ) 一q ) ) 芑甩一o + ；( 白2 + q + 1 ) ( 历一1 ) 一q ) ) j = n 一三( ( q 2 + q 十1 ) ( ，以一1 ) + 3 t - q ) ) 。 情形2 ：存在某个“sm 一1 ，使得口。，0 ，e * , i n 雨c u n - r l + r 2 ) n 一三( ( q 2 + q + 1 ) ( m - 1 ) + 2 m i n 伽_ 1 ，啪。 综合以上两种情况即得 d n - 三( ( 目2 + q + 1 ) ( m 一1 ) + m a x 3 t q ，2 m i n 坍一1 ，f ) ) 。口 取q ；3 ，且b = r = 8 时，得到一些码，如下表： t ，竹忍 kd d 目 口?占474 ， 2 9擘拿j ? 皇 1 04f疗 j21 1 45疗 这里我们得到了一些次最优码。 表3 3 1 6 中山大学硕士学位论文 3 2 扩域次数s 为任意素数时的新扩充 文献【4 】将s 扩充为任意素数，但在构造码时没有引入f 。中的元素，因此避 免了对s 是否整除q 的讨论。 下面我们来讨沦一下引入f 。中的元素来构造码时，码参数的估计。 ( 一) 当s 不整除q 时： 将f 。s 划分为( q 一q ) s 个共轭类，v 。的定义同文献【4 。 定义3 3 对0 蔓f 蔓q ，1 6 sr ：q - q ，1 s s 1 + ( t + b j s ) ( q = - - 一1 ) ， s 口一1 定义n 上的码c 。( f ，b ，m ) 如下： c ，( f ，b ，m ) = ( ，( a ，) ，f ( a ：) ，f ( a ，) ，f ( f l ，) ，f ( f l ：) ，f f l 。) ) ：f ( x ) e v 。， 其中f l , 取螋个自不同的共轭类。 s 定理3 3 上述定义的码c ，( f ，b ，m ) 是一个口元【n ，k ，d 】码，其中，l = t + b ， 七2 ( 埘+ ；一1 ) ， d 苫胛一三( ( m 一1 ) 里二二；+ m a x s f 一2 q ，( s 一1 ) m i n s ( 历一1 ) ，f ) ) ) 。 5玎一1 证明： 码长挖= t + b 是显然的，关于维数k 的讨论详见【4 】。下重点讨论d 。 设 ，( x ) 。荟州磊络瓯o ) 情形1 ：。：酝。0 任意。引s 5 ( m - 1 ) 则： r f l 山大学硕士学位沦文 s ( m 一1 )，佃一1 ) ，o ) = 芝以i 饩 ) 一(以i ) ( z 。+ 一+ f = 0 f l + 1 2 + 吖j 5 = 0 i j + i z + + f ；= f 0 q l 可2 l f 拥- 10 l s i 二ss f i 扑1 j r m l 、 2 荟，盖。，盘超坠璺兰二! ! ! 0 5 性5 ，”1 r ( r 则对任意口f 。，矗( 口) 一p ： ) = o ，所以有( x q - - x , ) 2if ( z ) 。 设占2 器对任意胙舻- ：，甜，( 鳓- 0 当且仅当 g ( f l 。) = 0 ，又因为在集合 - ，a z ，a ，卢。，卢：，卢。 中f ( x ) 的根的个数至多为 所以 d n p + d e g ( g ( x ) ) s ) 月一(f+三(沏一1)粤q-ts 一2 q ) ) 挖一三( ( 川一1 ) 4 - 1 + s t - 2 q ) 。 s口一l 情形2 ：y a y 去o s “ss ( m 一1 ) ，使得 日i 。0 ，且对“sz ss ( m 一1 ) ， * 篙；：2 = 一 以i = o 。 i t + i z + + t 5 = l 0 可i 2 i 刮f 蝴一1 则对任意口f 。， ) = o - k 且仅当 当且仅当 ( s 口i ) 口。= 0 。 j 1 0 “+ f 2 + + j j f o 2 e i 蜘一 因此在f 。中， ) 至多有m 个根，而“ss ( m 一1 ) ，故在集合 a 。口：，a ，) 中 f ( x ) 的根至多有m i n s ( m 一1 ) ，f 个。 1 8 0 = ， 磬一 篱 ， 峙 荟 中山大学硕士学位论文 设在集合k 。，a ：，口。 中f ( x ) 的根的个数为n ，在集合 卢。，卢：，卢， 中 f ( x ) 的根的个数为r ：。 则 n s m i n s ( m 一1 ) ，f ， n + m 到e g ( m ) ) s _ 1 ) 篱。 所以 ( s 一1 ) r 。+ n + 5 r ：s o 栉一1 ) 望_ _ 二；+ ( 5 1 ) m i n s ( m 一1 ) ，f ， 日一1 故 n + r ：s ! s ( ( m 一1 ) 望q ；1 + o 一1 ) m i n $ ( m 一1 ) ，f ) ， 一 于是有 d ：，z 一( r t + r 2 ) ：疗一! ( ( m 一1 ) 望二二三+ ( s 1 ) m i n s ( ，竹一1 ) ，f ) 。 s c 一上 综合以上两种情况得到s 不整除q 时，得到最小距离 d 苫甩一三( ( 埘一1 ) 里二_ 二；+ m a x s f 一2 q ，( s 一1 ) m i n p ( 埘一1 ) ，f ) 。口 s口一1 取q = 3 ，s = 5 ，且6 = 4 0 时，得到一些码，如下表 tm n kd 324 361 8 224 261 7 124 161 6 表3 4 遗憾的是，当s 不整除g 时，我们引入n 中的元素后，没能得到一些性能好 一些的码。 ( 二) 当s 整除q 时 r p 山大学硕士学位论文 定义 d 班2 黔= ：纛； 其中卢。的含义同文献 4 。 矿：，是由集合 e i s ) ：0 s i - s i z s s i ，s m 一1 s q 一1 ) 在f 。上张成的线 性空间。 定义3 4 对。s t 蔓q ，1 蔓6 蔓r = q 。- q ，和l a ma l + 警，定 z f 。上的码c ：( f ，b ，m ) c ：o ，b ，历) = ( ，( 口，) ，( a ：) ，( 口，) ，( 卢，) ，f ( f l ：) ，f ( f l 。) ) ：，( 工) 以， 其中卢，取自盟个不同的共轭类。 s 中 定理3 4 若s 整除q ，上述定义的码c ：( f ，b ，川) 是一个q 元陋，k ，d 码，其 d 芑九一! ( ( ，栉 s n = t + 6 ， j 2 ( 小+ f 一1 ) 1 ) 等一a x 矿“卜1 ) m i n 枷- 1 力) ) o 证明：码长咒；t + b 是显然的，关于维数k 的讨论详见文献 4 】。下面重点讨论最 小距离d 。 仍设 m ) 2 荟，；磊擎z ) 。 对任意口f 。，当f 1 一i 2 = = i ，不成立时，e g ( a ) = s o t “”2 + 1 。+ “= 0 。 情形1 ： a o n ，o = a 1 ，1 = = a ( 。一1 ) ，( 卅_ 1 。- 1 ) = 0 。 2 0 。p 山大学硕士学位论文 则对任意口n ，有f ( a ) = 0 。 在集合亿。，口：，口。卢。，卢：，玩 中，f ( x ) 的根的个数至多为 t + d e g ( g ( x ) ) s 个。因此 d 刀一0 + 兰( d e g ( ，( x ) ) 一q ” s