（概率论与数理统计专业论文）二元非对称信道的纠错编码.pdf

摘要 摘要 在很多二元通信信道中，交叉错误即发生1 _ o 错和o _ 1 错的概率近似相等， 我们称这样的信道为二元对称信道( b s c ) 人们已经广泛的研究了基于对称信道 的纠错方法，提出了很多有应用价值的纠错码而在其他一些通信信道中，例如大 规模与超大规模半导体集成电路存储器中，由器件的某些类别的故障常引起码字 的非对称错和单向错这一现象引起了人们研究非对称错和单向错的兴趣，针对 二元非对称错和单向错的纠错码出现了众多的研究成果 本文只对二元非对称纠错码进行讨论首先对二元非对称错的基本知识和一 些常见的纠错码进行了介绍然后在此基础上提出了自己的构造方法；首次讨论 了当佗一1 和n - 2 是素数幂次的情况时，基于多项式剩余环构造码长为扎的t - a e c 码， 并且给出码字个数最大值的下界 关键词非对称信道，非对称错，多项式剩余环，c o n s t a n t i n r a o 码 a b s t r a c t a b s t r a c t i nm a n yb i n a r yc o m m u n i c a t i o ns y s t e m s t h ep r o b a b i l i t i e so ft h ec r o s s o v e r s1 _ 0 a n do _ 1a l ea p p r o x i m a t e l yt h es a m e a n dt h es y s t e m sa r ew e l lm o d e l e db yt h eb i n a r y s y m m e t r i cc h a n n e l ( b s c ) e r r o rc o r r e c t i n gc o d e sf o rb s c sh a v eb e e ns t u d i e de x t e n - s i v e l y b u ti no t h e rc o m m u n i c a t i o ns y s t e m s ，e g ，t h el s i v l s ic i r c u i t s ，t h ef a u l t s a l ed i f f e r e n ta n dt h e ye x h i b i tah i g hi n c i d e n c eo fa s y m m e t r i ce r r o r sa n du n i d i r e c t i o n a l e r r o r s t h e r ea r em a n yp a p e r sd e d i c a t e dt ot h ec o n s t r u c t i o no fg o o dc o d e sa n dt h e d e r i v a t i o no fl o w e ra n du p p e rb o u n d sf o rb i n a r ye r r o r - c o r r e c t i n gc o d e s ，w h i c hc a nb e c a p a b l eo fd e t e c t i n go rc o r r e c t i n gc o d e sa s y m m e t d co ru n i d i r e c t i o n a le r r o r s t h i sp a p e r so n l yd i s c u s s e sb i n a r ya s y m m e t r i ce r r o r - c o r r e c t i n gc o d e s w ef i r s t l y i n t r o d u c et h eb a s i ck n o w l e d g ea b o u ta s y m m e t r i ce r r o r , a n dt h ec o n s t r u c t i o no fs o m e b i n a r ye r r o rc o r r e c t i n gc o d e ，w h i c hc a nb ec a p a b l eo fc o r r e c t i n ga s y m m e t r i ce r r o r s t h e np r e s e n to u rc o n s t r u c t i o no ft - a e cc o d e ：w h e n 死一1o r 佗一2i sap r i m ep o w e r , w e f i r s tg i v et h ec o n s t r u c t i o nt - a e cc o d eo fl e n g t hnb a s e do nr e s i d u er i n g so fp o l y n o m i a l s ， a n dl o w e rb o u n d sf o rs u c hc o d e sa r eo b t a i n e df r o mt h ec o n s t r u c t i o n k e yw o r d sa s y m m e t r i cc h a n n e l ，a s y m m e t r i ce r r o r , r e s i d u er i n g so fp o l y - n o m i a l s 。 c o n s t a n t i n r a oc o d e 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 泳蒸r i 伽罗年f 月蚕日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： r 一一飞 ；内部5 年( 最长5 年，可少于5 年) | 秘密l o 年( 最长l o 年，可少于1 0 年) | 机密2 0 年( 最长2 0 年，可少于2 0 年) 。+ 。一。，j 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、己公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者繇操立叼 温年岁月如日 第一章引言 第一章引言 纠错编码是一种重要的容错计算技术它广泛应用于计算机和通信系统中， 为提高系统的可靠性发挥了重要作用传统的纠随机和突发错误的编码理论是建 立在对称错误模型的假定之上但在大规模和超大规模半导体集成电路存储器中， 由器件的某些类别的故障常引起码字的非对称错与单向错从历史发展来看，非对 称错纠错码的研究早在5 0 年代末已经开始【1 【2 】【3 】稍后，在8 0 年代和9 0 年代初， 随着集成电路特别是超大规模集成电路的发展，非对称错与单向错真实地出现在 计算机系统内的码字中，这一现象极大地激发了人们对非对称错与单向错纠检错 码的研究兴趣，出现了众多研究成果( 5 】- 【2 6 】) 下面我们介绍一下二元对称错、非对称错和单向错的基本概念 定义1 1 用1 _ 0 错表示码字中1 变为o 的错误i 用o 一1 错表示码字中0 变为1 的 错误那么对称错、非对称错和单向错的定义如下? ( 1 ) 对称错? 1 _ 0 错和o _ 1 错可同时出现在一个码字中 ( 2 ) 非对称错? 1 _ 0 错和0 _ 1 错中仅仅一种类型出现于所有码字中，且错误类 型是预先就知道的 ( 3 ) 单向错? 1 _ 0 错和o _ 1 错两种都可出现在码字中，但它们不能同时出现 在同一码字中 由上而定义可知，非对称错误类是单向错误类的子类，而单向错误类又是对 称错误类的子类，因而任何一个可纠检亡个对称错的码也可纠检个单向错或t 个 非对称错，而任一个可纠检t 个单向错的码也可纠检个非对称错然而，反过来 一般不成立 本文主要研究二元非对称错的纠错码全文的结构如下：第二章介绍二元非 对称错的有关知识和相关定理；第三章简要介绍儿种纠单个非对称错纠错码的构 造方法；第四章介绍儿种纠t ( t 2 ) 个非对称错的纠错码的构造方法；第五章首先 介绍了利用多项式剩余环构造t - a e c 码的方法，在此基础上首次给出了当n - 1 和 佗一2 是素数幂次时码长为n 的t - a e c 码的构造方法及码字个数最大值的下界 第二章二元非对称信道纠检错码的基本知识 第二章二元非对称信道纠检错码的基本知识 我们先介绍一下有关二元纠检错码的基本知识我们用k 表示马= o ，1 ) 上 所有咒维向量组成的集合；我们称k 上含有m 个向量的子集c 为一个长度为n ，码字 个数为m 的二元码，或者简记为二元( 礼，m ) 码 定义2 1 设z = ( z l ，x 2 ，z 佗) 与可= ( y 1 ，y 2 ，) 是有限域足的两个n 维 向量，若x i = o 而玑= 1 ，则称z 的第 个分量为茁对可的0 1 型分量，所有z 对可的o 一 1 型分量的个数记为( z ，可) ，即 n ( x ，可) d = e fi ii 钇= o 且玑= 1 1 特别的，若z 与可满足条件”每当兢= 1 时，有y l = 1 ”r 即( 可，z ) = o j ，则称可覆 盖z ，事己为z 冬y 定义2 2 设z = ( x l ，x 2 ，x n ) 与可= ( y 1 ，y 2 ，) 是有限域r 的两个n 维 向量，向量z 与y 的汉明距离d h ( x ，可) 定义为这两向量问不同分量的个数，即 d 日( z ，秒) 型i ij1 i 佗，z l 玑) j 定义2 3 对于足上的两个n 维向量z = ( x l ，x 2 ，z 。) 与y = ( y 1 ，y 2 ，) ， 我们称 比( z ，秒) d = e fm a x n ( x ，可) ，n ( y ，z ) ) 为向量茁= ( x l ，x 2 ，x n ) 与可= ( y l ，y 2 ，) 的非对称距离 注所定义的如( z ，y ) n 妇( z ，影) 一样满足数学上关于距离的三个条件： ( 1 ) d a ( 2 ，y ) 0 ，且也( z ，y ) = o 当且仅当z = 可； ( 2 )也( z ，y ) = 也( 秒，z ) ； ( 3 )比( z ，名) 如( z ，可) + 比( 剪，名) 定义2 4 对于足上的n 维向量z = ( x 1 ，x 2 ，z 竹) ，我们称 叫( z ) d = e fi ix i = 1 ，1 i 礼 i 为向量z 的汉明重量 2 第二章二元非对称信道纠检错码的基本知识 通过上而的定义，我们显然可以看出有下面的关系： 妇( z ，秒) 比( z ，可) 掣1 d h ( x ，y ) = n ( x ，y ) + n ( y ，z ) w ( x ) = d h ( x ，0 ) = 比( z ，0 ) 这里。为n 维。向量( 0 ，0 ，0 ) 而三者的精确关系由下面引理给出 引理2 1 设z = ( x l ，x 2 ，x n ) 与可= ( y l ，y 2 ，) 是有限域局的两个n 维 向量，那么有 2 d a ( z ，y ) = d h ( x ，可) + i 叫( z ) 一叫( 可) i 证明因为 ( z ) = i i i x i = 1 1 = j i y i = 0 ，鼢= 1 - i + l i l y , = 1 ，x i = 1 】i = l i l y , = 1 ，兢= 1 】- i + n ( y ，z ) 叫( 可) = i i l y i = 1 1 = i i l x i = 0 ，y i = 1 ) i + i i l x , = 1 ，y i = 1 】i = j ij x , = 1 ，玑= 1 ) i + n ( x ，y ) 所以有 n ( x ，可) + 伽( z ) = n ( y ，z ) + w ( y ) 我们不妨假设叫( z ) 伽( 秒) ，那么有n ( x ，可) n ( y ，z ) 因此有： 2 d a ( z ，y ) = 2 n ( y ，z ) = ( z ，y ) + g ( y ，z ) + ( g ( y ，z ) 一( z ，秒) ) = d g ( x ，y ) + ( 叫( 茁) 一伽( 可) ) 3 口 第二章二元非对称信道纠检错码的基本知识 定义2 5 一个二元码c 的汉明距离d 日( c ) 定义为码c 中不同码字之间汉明距离 的最小值，即? d h ( c ) d = e fm i n d hc ，c 7 ) i v ，c ，c ，c c ，) 非对称距离d 0 ( c ) 定义为码c 中不同码字之问非对称距离的最小值，即? d 。( c ) d = e fm i n d 。( c ，d ) l c ，c i c ，c c ，) 一个可纠t 个对称错的码，我们记为t - s e c 码( t s y m m e t r i c e r r o rc o r r e c t i n gc o d e ) ； 一个可纠个非对称错的码，我们记为t - a e c 码( t a s y m m e t r i c e r r o rc o r r e c t i n gc o d e ) 一个码的检错纠错能力与该码的距离有关下面的定理给出了它们的关系 定理2 2 ( 文献【3 5 】定理1 2 4 ) 二元码c 可检个错误的充要条件为如( c ) = t + 1 j 二元码c 为t s e c 码的充要条件为妇( c ) = 2 t + 1 或d n ( c ) = 2 t + 2 定理2 3 二元码c 为a e c 石- 5 的充要条件为比( c ) t + 1 证明我们只证发生1 0 错的情况对z k ，我们记 & ( z ) = v k i 钐5z ，n ( v ，z ) t ) & ( z ) 为z 出现t + l _ 0 错后所得向量的集合 先证充分性我们只需证明对任意的z ，y c 有& ( z ) n & ( 可) = 仍即可因 为d 。( c ) t + 1 ，那么对任意的z ，可c 有d 。( z ，可) t + 1 若t ，& ( z ) n ( 可) ， 那么有 t n ( v ，z ) n ( y ，z ) t n ( v ，y ) ( z ，y ) 那么有 t m a x n ( x ，! ，) ，n ( y ，z ) ) t + 1 矛盾所以& ( 茁) n & ( 可) = 国 所以设口是个接收信号，且t ，( z ) ，那么对任何y z c ，有v 譬s ( 可) 即 t ，5z ，g ( v ，z ) t ，v 苤y 4 第二章二元非对称信道纠检错码的基本知识 那么根据非对称错的性质和最小非对称距离译码方法，可唯一的把v 译为2 所 以c 是t - a e c 码 下面证必要性c 是t a e c 码z c ，若u z c 满足丸( u ，z ) t 我们如下 定义向量t ，： f 1 u i = 觑= 1 v i21 o 其他 那么有 v5z ，n ( v ，z ) = n ( u ，z ) t 可u ，n ( v ，u ) = n ( x ，让) t 所以有 v & ( t 正) n & ( z ) 即若v 为接收信号，则我们无法唯一的译码，所以有ugc 因此d n ( z ，y ) t + 1 ，对 任意的z ，y c 口 根据引理2 1 。上曲的定理也可写成下而的形式： 定理2 4 - t l 码c 是t a e c 码的充要条件是对任意的z ，妙c ，z y 有 ( 1 )i 叫( z ) 一叫( 可) i t + 1 或 ( 2 )i 叫( z ) 一伽( 可) i t - e k d h ( x ，y ) 2 ( 亡+ 1 ) 一i 叫( z ) 一w ( y ) 1 5 、l ， z移 ，j 可 一 移 一 z移 il z 1 该码构造如下 如果n = 2 m 。那么 c = ( z i 茁oh ) jz v m ，叫( 茁) 为偶数，h 月么o ) u ( z iz ) ix v m ) 如果佗= 2 m + l 。那么 c = ( zj ( zj0 ) oh ) jz v ”，叫( z ) 为偶数，h h m + l o ) u ( z lz 10 ) ix v m ) 我们可看出该码的码字个数为 2 m - x ( 1 + i i ) 如果n = 2 m 2 m - 1 ( 1 - i - i k + 1 i ) 如果礼= 2 m + 1 说明当n = 2 一1 时，该码的码字个数少于等长的汉明码字个数，其他情况均 大于汉明码字个数 3 2c o n s t a n t i n r a o 码 令g 为礼+ 1 阶交换群，其上的运算为加法+ ，记g = g o ，9 1 ，鲰 ，其中9 0 为 单位元对任意的g g ，定义 c 9 = ( ，z 佗) kl 兢g i = 夕) 其中 x i g i = l 仂g o 耋薹i 吕眷 6 第三章纠单个非对称错的纠错码 那么对每一个g g ，已是1 一a e c 码 1 2 由于 c g i g g 】- 构成的一个分割，即 ( 1 ) k = u g g 巳 ( 2 ) c gn q = 仍，g h 那么我们可得到下血关系式 m a x l g i 磊 m c e l i e c e 在文献 【1 5 】 得到当夕= 夕。时，即g 。所含码字最多，且给出了其上界 i 而1 ( 2 n - q - n , 2 孚) 3 3a n a n i a s h v i l i 码 该码【5 是系统码，构造思想是在信息位后面加上一些冗余使其构成1 一a e c 码 下面介绍一下它的构造思想： t 正是y 知到y 的映射( 其中m = l 0 9 2 ( 尼+ 1 ) 1 + 1 ) ，其定义如下：对任意的z = ( z 1 ，x 2 ，z 七) v 七，令 s 三觑术i ( m o d k + 1 ) ，0 s 七 设沓1u i 2 一1 是s 的二进制展开，计算 m 一1 = u t ( m o d 2 ) 令 那么码 u ( x ) = ( u l ，u 2 ，u 。) c = ( z i u ( z ) ) iz v 岛) 是1 一a e c 码但该码的码率较低 7 第二章纠单个非对称错的纠错码 3 4 其他构造方法 令a = o o ，1 p ) a 1 ，a 2 ，4 是4 的一个划分，满巳a in 冯= 0 ， u a t = a ，且d a ( a i ) 2 ，1 i 7 令b = 6 o ，1 q l w ( b ) y 可偶数) b 1 ，b 2 ，鼠是b 的一个划分， 满足d 0 ( b i ) 2 ，1 i 8 码c 是由a ，鼠的笛卡尔积a xb i 得到，即 c = a lxb 1ua 2 b 2u ua k b k ，k = m i n ( r ，8 ) 刃璐么石弓c 是1 - a e c 五弓 通过c o n s t a n t i n r a o 构造方法，我们很容易得到至少含有2 n ( n + 1 ) 个码字 的码而对有些情况，通过该构造方法可得到至少含有2 竹佗 个码字的码我们有 下面的定理 定理3 1 ( 1 2 7 1 定9 2 _ 2 j 令q = m 木2 ，1 m 6 ，i 1 我们能构造一个码长 为n = 2 q 一2 且包含码字个数至少为2 ”礼 的码c 8 第p q 章纠多个非对称错的纠错码 第四章纠多个非对称错的纠错码 在上一章我们介绍了几种1 a e c 码的构造方法，在这一章中我们将介绍 几种t - a e c 码( 2 ) 4 1 基于集构造亡- a e c 码 我们首先给出关于k 集的定义 定义4 1 令g 为f * - y9 2 尔群，g 的的子集h = 九1 ，h 2 ，h n ) 被称为k 集，如果对 所有的 吃l + 尼t 2 + + 九讳， 1 i 1 i 2 i ，n ，1 r t 互不相同 下面给出基于k 集构造t a e c 码的方法，它可看作是c o n s t a n t i n r a o 石q 的推广 构造方法4 1 令日是阿贝尔群g 的k 集那么对于g g c ；= _ ( z 1 ，x 2 ，z n ) i 是二元t a e c 码 可见该构造方法的关键是怎样构造阿贝尔群的k 集下面介绍两种k 集的构 造方法【4 儿1 4 】 构造方法4 1 1 令g = z 口c - 1 p 是有限域巧的本原元那么 h = gi h + 1 一e ) 是g 的集且1 日i = q 一1 构造方法4 1 2 令m = ( q t + 1 ) ( g 一1 ) ，g = z m p 是有限域b 的本原元那 么 h = 允10 h 佗) 个元素的有限域b ，q l ，0 1 2 ，q 竹是其上n 个非 零元素对于z = ( x l ，x 2 ，x n ) k ，令z a = ( x l o l l ，x 2 0 1 2 ，x n o l 。) 对于任意 的夕1 ，9 2 ，g t 日，令 g 。，吼= z i 吼( z q ) = g t ，1 z t ) 那么g ，m 是t a e c $ - 马 构造方法4 3 令是有限域b 的本原元a l ，a 2 ，是z 口一l 上几个非零元令 o t i = p m 一1 ，i = 1 ，2 ，礼，q = q 1 ，q 2 ，o z 佗) ，a = 0 1 ，a 2 ，a n 对于任意 的夕1 ，夕2 ，g t 一1 b 和m z 口一1 ，令 c j 。，9 t 一，m = z ko l ( x a ) = g l ，1 1 t 一1 ，f f l ( 茁a ) = m ) 那么巳，g ，m 是亡一a e c 码 我们用f ( n ，t ) 表示码长为n 的最小非对称距离为t 的码的码字个数的最大值 那么基于以上构造方法，我们可以得出关7 = r ( n ，) 下界的结果： 1 0 q zu 田 = 毗 +z ，汹 一 一 uuu 毒打 l 琏q = = = 第四章纠多个非对称错的纠错码 定理4 1 ( 【3 4 】足理6 1 ) ( 1 ) 如果佗是一个素数的幂次，则 r ( n ，t ) 万f 而南丽 ( 2 ) 如果几+ 1 是一个素数的幂次，则 r ( 州) 两祀 ( 3 ) 如果q 是礼+ 2 中最小的的素数的幂次，则 r ( n ，。) q t - 1 兰_ q t - 2 ( 4 1 ) ( 4 2 ) ( 4 3 ) 第五章基于多项式剩余环构造t a e c 码 第五章基于多项式剩余环构造t a e c 码 近年来，符方伟等人基于多项式剩余类环 3 1 1 给出了一种构造方法 3 2 】，不仅 能够得到上述码字个数的下界 定理4 1 】，而且还能得出更好的下界界限在此基础 上我们讨论了佗一1 和n 一2 是素数幂次的情况，给出了码长为n 的t - a e c 码的构造 方法及码字最大值的下界 我们先介绍一些关于多项式剩余类环的基本知识令b 为含有口个元素的有 限域，q 是某素数的幂次方对于首一多项式f ( x ) b i x ，考虑剩余类环 r = 引z 】( ，( z ) ) 事实上，在同构意义下，剩余类环r 可等价地表示为 r = 9 ( z ) b z ld e g ( g ( x ) ) d e 9 ( ，( z ) ) - 假设厂( z ) 可因式分解为如下形式： 知 m ) = p 弛) t = l 其中p ( z ) ，m ( z ) 是b i x 中不同的首一不可约多项式，e l ，e 七是j 下整数易知 环r 中与厂( z ) 互素的多项式构成一个阿贝尔群r 4 ： r + = 夕( z ) 日【z id e g ( g ( x ) ) d e g ( f ( x ) ) 且( 夕( z ) ，厂( z ) ) = 1 ) r 4 中乘法运算。是模厂( z ) 的多项式乘法，因此群r 4 中包含 l r + i = 圣( ，( z ) ) = i i ( q 也一1 ) g 也e t 一1 个元素，其中也是多项式胁( z ) 的次数显然，巧= 日 o ) 是群r 的子群则商群 g = r + ( 巧) 是一个阿贝尔群且包含 i g i 卅( m ) ) = 刍吣( 圳= 击垂( 卜1 ) q 引州) 第五章基丁多项式剩余环构造t a e c 码 个元素事实上，在同构意义下，我们可以把g 看作是r + 中所有首一多项式的集合， 即， g = 夕( z ) 日 x l d e g ( g ( x ) ) d e g ( f ( x ) ) ，夕( z ) 是首- - 的j t ( g ( x ) ，( z ) ) = 1 ) g 中乘法运算。定义为： a ( x ) ob ( x ) = h - 1 ( o ( z ) o6 ( z ) ) 其中n ( z ) ，b ( z ) g ， 为a ( z ) o6 ( z ) 最高项的系数，且九露 5 1 基于多项式剩余环构造t a e c 码 下面我们应用商群g 来构造t a e c 码，具体的构造方法如下 构造方法5 1 令扎和是两个正整数，满足他 q ，2 t + 1 n 令f ( x ) 日h 是次数为t + 1 的首一多项式，满足条件? 在r 中存在n 个不同的元素o l l ，q 2 a m 满足t 厂( q t ) 0 ，对所有的i = 1 ，2 ，n 那么显然有x o l i ) 与，( z ) 互素，因此有? ( z o l i ) g ，i = 1 ，2 ，n 考虑映射 ：一 ( c l ，c 2 ，c n ) _ g i i 。( z 一) 。g t = 1 对于每个9 ( z ) g ，我们记 岛= q 一1 ( 9 ( z ) ) 对于每个9 ( z ) g ，如果c g 0 ，则巳是一个长度为n 的一a e c 码 译码方法：假设接收端收到的向量是 y = ( y l ，y 2 ，y n ) k 我们计算 r y ( x ) = 。( z 一啦) 玑g 驰) = 器g 1 3 第五章基于多项式剩余环构造t a e c 码 我们记i = d e g ( e ( x ) ) ，那么有： ( 1 ) 如果f = 0 ，即e ( z ) = 1 ，那么把可译为可 ( 2 ) 如果0 l 且e ( z ) 有z 个不同的跟锄，o q 。，o q 。，那么把可译为 c = ( c 1 ，c 2 ，) ，满足： 勺= 关 。1 ， j i l ，i 2 ，i l j22 1 ，z 2 ，钆 ( 3 ) 其他情况译码出错 口 关于此构造方法译码方法的证明以及其他细节，可以参考文献 3 2 】易知g ， g ( x ) g 构成了对集合的一个划分，则我们一定可以找到一个元素丌( z ) g 使 得 9 n 蚓反而 这样我们得到了下而的定理 定理5 1 假设q 是某素数的幂次方，疋为舍有q 个元素的有限战他和t 是两个正 整数满足n 5 当n + 1 是素数时有： ( 5 7 ) 一( 4 2 ) ：o ( 学) ，是偶数且t 4 ( 5 8 ) 一( 4 2 ) = o ( 譬) ，是奇数且5 1 6 第五章基丁：多项式剩余环构造t a e c 码 当n + 2 是素数时有： ( 5 9 ) _ ( 4 3 ) = d ( 譬) ， 提偶数且4 ( 5 1 。) 一( 4 3 ) = d ( 簪) ，是奇数且t 5 5 2 改进的二元t - a e c 码的构造方法 上一节讨论了当n ，礼+ 1 ，佗+ 2 是素数的幂次时构造码长为n 的t a e c 码的方 法，并给出了关于码字最大值下界的一些结果本节我们讨论当n 一1 或几一2 是素 数的幂次时构造n 长的t a e c 码的方法，并给出了码字最大值的下界我们首先考 虑n 一1 是素数幂次的情况 构造方法5 2 当n 一1 是素数的幂次时，我们令q = n 一1 ，我们可以构造舍 有q 个元素的有限域日2 4 * f ( x ) b m 是次数为亡+ 1 的首一多项式满足? 对于有 限域r 中的所有元素q t ，1 i n 一1 有f ( o l i ) 0 那么( z q t ) 是与，( z ) 互素的 首一多项式，因此， ( z o q ) g ，1 i 冬n 一1 考虑映射 皿：y n ( 1 ，0 ，c 2 ，a n 一1 ) _ g 对于每个g ( x ) g ，我们记 g = 皿- 1 ( 9 ( z ) ) 对于每个夕( z ) g ，如果0 d ，则g 是一个长度为他的t a e c 码 证明如果我们在k 上考虑映射，假设c 1 = ( 0 ，1 ，c 2 ，a n 一1 ) 白，那么易 知c 2 = ( 1 ，0 ，c 2 ，a n 一1 ) 巳，而d 。( g ，c 2 ) = 1 2 t + 1 与已知矛盾所以去 掉前两个字符是1 0 的码字，只考虑其余码字，而剩余码字个数为木2 竹 对于每个g ( x ) g ，如果巳0 ，我们只需证明对于任意的牡，t ，g 且 t 正口有 比( 缸，v ) t + 1 1 7 户 q z o “n 汹 o 口 一 z_ 一沈 o1 、 一 q 印 第五章基于多项式剩余环构造a e c 码 令u = ( u 1 ，u 2 ，u n ) ，v = ( v l ，v 2 ，v n ) 那么有 皿( u ) = v ( v ) = g ( x ) g 由上式我们可以推出元素皿( t 正) ( t ，) 是g 中的单位元这说明在群r + 中，元素 墼堕一羔! q ! 兰二竺监 皿( 口) 一n ：。o ( z q t ) 仇 等于子群巧中的某个元素我们记 s = i ：仳l = 0 a n d v i = 1 t = i ：u i = 1 a n d v i = o ) 那么sat = d 由于t 正t ，可推出s d ，t 仍且有 i s l = n ( u ，t ，) ，i t i = n ( v ，u ) 我们容易看出 型：皿! q ! 兰二竺立：口 皿( 口)n 汹o ( z 一0 ：t ) p 在群r + 中这等价于，( z ) 整除多项式 a ( z ) 全n ( z 一口t ) 一z1 ( x a t ) b m t t i e s 多项式n t t ( z q 1 ) 的根是q t ，i t ，而多项式兀i sx q i ) 的根是q l ，i s 由于 a t ，i s ) n 口i t ) = 仍 且s 0 ，t 仍，那么我们有 n ( z n t ) zi ( x q t ) i t s 因此a ( z ) 0 由于a ( z ) 次数至多为 m a x l s l ，i t i = d a ( u ，口) 因此 d 。( 乱，口) a ( z ) d e g ( f ( x ) ) = t + 1 1 8 第五章基于多项式剩余环构造t a e c 码 这就证明了g 是一个t a e c 码 口 由上l 酊的构造过程可知，g ( 9 ( z ) g ) 构成了对集合k ( 1 0 c 2 c n 一1 ) 的一个划 分则我们一定可以找到一个元素丌( z ) g 使得 怫i 者志 这样我们就得到了下面的定理 定理5 4 假设g = 礼一1 是素数的幂次，e 是含有q 个元素的有限战t 为正整 数满足2 t + 1 仡令，( z ) 是日吲上次数为+ 1 的首一多项式满足? 任给有 限域b 中的元素啦，1 i n 一1 有，( q i ) 0 则一定存在一个码字长度为他的 a e c 码，其码字个数满足? 俐赢淼 由定理5 4 。我们有如下的定理 定理5 5 如果佗一1 是素数的幂次，且2 t n ，则 咐) 而哥等麓 ( 5 1 1 ) 其中r 和s 是两个非负整数，满足t = 2 r + 3 s _ e 1 s o ，1 ) 证明由于n 一1 是素数的幂次，可令 r 一1 = ( 2 1 ，q 2 ，q n 一1 ， 因为在有限域r l 中首一的二次不可约多项式的个数是垃掣竽望，且 ，t ，n ，( 扎一1 ) ( 几一2 ) rs 一2 一2 乏。2 因此我们可以取r z 】中r 个不同的首一的二次多项式p l ( x ) ，p 2 ( z ) ，p r ( z ) 和一个 首一的三次不可约多项式p ( z ) ，令 ，( z ) = 矿( z ) 1 - ip t ( z ) 那么有d e 夕( 厂( z ) ) = 且圣+ ( ，( z ) ) = 击 ( 凡一1 ) 2 1 ( 礼一1 ) 3 1 卜易知对所有 的i = 1 ，2 ，n 一1 ，有f ( c e t ) 0 因此由定理5 4 可得( 5 11 ) 口 下界( 5 11 ) 也可以表示为下面的形式： 1 9 第五章基丁= 多项式剩余环构造t a e c 码 推论5 6 如果t t 一1 是素数的幂次，且2 t m 则 跏端，功偶数 ( 5 1 2 ) m 而# 睾，功奇数凰3 对于当佗一2 是素数的幂次时，我们可用类似构造方法5 2 的方法构造码长为佗的 二元t a e c 码对于死长的向量我们只考虑前四个分量是0 0 0 0 ，0 0 0 1 ，0 0 1 1 ，0 1 0 0 ， 0 1 0 1 ，0 1 1 1 ，1 1 0 0 ，1 1 0 1 ，1 1 1 1 形式的向量的集合s 到g 的映射s o 向量个数为杀2 ” 构造方法5 3 当n 一2 是素数的幂次时，我们令q = n 一2 ，我们可以构造含 有口个元素的有限域r z 】令厂( z ) 日m 是次数为+ 1 的首一多项式满足? 对于 有限域b 中的所有元素q t ，1 i 扎一2 有f ( a i ) o 那么( z q t ) 是与厂( z ) 互素的 首一多项式因此， ( z 一 ) g ，1 i 礼一2 考虑映射 。s _ g ( c l ，c 2 ，c n )一( z q 1 ) c 1o ( z q 1 ) c 2o ( z q 2 ) c 3o ( z q 2 ) c 4 n - 2 。( z q t ) + 2 ) i = 3 对于每个g ( x ) g ，我们记 巳= 皿。( g ( z ) ) 对于每i 。g ( x ) g ，如果c 夕谚，则已是一个长度为礼的t a e c 石$ 对于当扎一2 是素数的幂次时，通过上面的构造方法我们可得关于码字个数最 大值的下界的结论 定理5 7 如果n 一2 是素数的幂次且2 t 那么有 咐) 而可卷可可 ( 5 1 4 ) 其中r 和s 是两个非负整数，满足= 2 r + 3 s e 1 s ( o ，u 上而定理也可写成下血形式 第五章基丁二多项式剩余环构造t a e c 码 推论5 8 如果n 一2 是素数的幂次，且2 t n ，则 跏茄等舞，郴数 r ( 扎，t ) i 可石- 二互乒芝才三圣，r 为奇数且t 3 ( 5 _ 6 ) 一些t a e c 码的下界 n q t = 8t = 9t = = 1 0 6 1 = 6 2 11 0 8 3 6 8 01 7 7 6 12 9 2 6 26 4 = 6 2 + 21 0 6 6 0 0 01 6 6 5 7 2 6 1 6 4 = 6 2 + 21 0 6 5 2 2 01 6 6 4 52 6 1 礼 g t = 7t = = 8t = 9 5 14 9 = 5 1 28 9 7 2 0 1 8 3 33 8 5 15 3 = 5 1 + 21 0 3 6 2 4 1 9 5 53 7 佗 g t = = 6t = 7 t = 8 4 24 1 = 4 2 12 7 8 2 76 7 9 1 7 4 24 3 = 4 2 + 12 9 9 4 96 9 71 7 构造码长为几的t a e c 码时，我们选择的g 要与n 距离尽可能的小；对于口1 ，9 2 与 n ( q 1 n q 2 ) 有相同的距离时，要选择l t n 大的q 2 来构造一a e c 码，这样得到的下 界较好 2 1 结束语 结束语 本文主要对二元非对称纠错码进行了讨论，并存前人的基础上首次讨论了 当n 一1 和几一2 是素数幂次时，基于多项式剩余环构造码长为n 的t a e c 码的方法 并给出了相应的码字最大值的下界然而此下界是一个较弱的界因为我们有 结果f ( n ，t ) m a 3 c g e g 峨| 该下界要优于我们在定理中给出的下界，但该表达式 不够直观，而且计算的复杂度极大如何找到使得l c g i 达到最大的9 ，这是个值得进 一步探讨的问题对于t = 2 的情况，该构造码为类c o n s t a n t i n r a o 码而人们已 经对c r 码进行了深入透彻的研究，得到了该码的重量分布及证明了当g 为单位元 时c r 码的码字最多而且对于不同构的阿贝尔群g ，c 口。包含的码字也不一样多 对于该码我们可以猜想当g = 1 即单位元时c 。达到最大 另外当n 一1 和n 一2 是素数幂次时，我们提出的码长为几的t a e c 码构造方法只 是形成了对k 的子集s 的一个分割，对于佗一1 是素数的幂次时，包含的向量为；水2 n ， 而对于n 一2 是素数的幂次时，包含的向量仅为畏木2 n 这使得每个分割包含的码 字要相应的减少如何找到新的构造方法对k 进行分割需要我们进一步的思考 2 2 参考文献 参考文献 1 】w ：h k i ma n dc vf r e i m a n ，s i n