（基础数学专业论文）代数几何码渐近界的改进.pdf

摘要 摘要 对任意素数幂次g ，令o t 口( 6 ) 表示码的渐近理论中的标准函数，即，给 定渐近相对最小距离下g 一元码能达到的最大渐近( 相对) 信息率码的渐近 理论一个核心问题是寻找o t 口( 6 ) ，0 万 ( q 一1 ) q 的下界关于函数( 6 ) 的一个已知下界是g i l b e r t - v a r s h a m o v ( g v ) 界：l 一鼠( 6 ) ，其中鼠( 6 ) 为q 一元 熵函数1 9 8 2 年，t s f a s m a n 等人取得了编码理论中的突破性进展他们基于 g a p p a 构造利用曲线在某类特定阶的有限域上改进了g v 界，得到a 4 ( 6 ) 的 t s f a s m a n v l i i d u v z i n k ( t v z ) 界：1 6 一a ( 口) 由此，代数几何码成为编码 理论中的研究热点随后，e l k i e s ，邢，n i e d e r r e i t e r ，o z b u d a k ，s t i c h t e n o t l l 以 及m a h a r a j 等人相继改进了t v z 界 本文基于n i e d e r r e i t e r 和0 z b u d a k 【1 3 】方法得到一个改进的a 口( 6 ) 下界。 改进的关键是构造集合u ( n ，s ；咱，n ) 取代n i e d e r r e i t e r 和o z b u d a k 构造的集合 u ( n ，s ，叫) ，使得构造码的映射涉及到函子在函数域上n 个有理位处的二阶导 数，由此在口口( 6 ) 的下界估计中引进了两个参数z 和秒，从而对特定的口以及 某些6 得到下界1 6 一a ( 口) 一1 + l o g q ( 1 + 2 q 3 ) + l o g 口( 1 + ( g 一1 ) q 6 ) 从而使 1 3 1 中的构造成为我们结果的特例 关键词： 码的渐近理论，代数函数域，g i l b e r t v a r s h a m o v ( g v ) 界，t s f a s m a n v l i i d u l - z i n k ( t v z ) 界，邢界 a b s t r a c t a b s t r a c t f o ra n yp r i m ep o w e rg ，l e tq 口( 6 ) b et h es t a n d a r df u n c t i o ni nt h ea s y m p t o t i c t h e o r yo fc o d i n g ，i e ，( 6 ) i st h el a r g e s ta s y m p t o t i c ( r e l a t i v e ) i n f o r m a t i o nr a t et h a t c a nb ea c h i e v e df o rag i v e na s y m p t o t i cr e l a t i v em i n i m u md i s t a n c ejo f 口一a r _ yc o d e s ac 2 n t r a lp r o b l e mi nt h ea s y m p t o t i ct h e o r yo fc o d i n gi st of i n dl o w e rb o u n d so f ( 回 f o r0 6 o ) 是可k 的位，o f = z f ：v p ( z ) o ) 为相应的赋值环 一3 一 第l 章前青 由此可知函数域的离散赋值和赋值环是一一对应的函数域的一个最 简单例子是有理函数域称f k 为有理函数域，如果对k 上的某个超越元 z f 有f = k ) 任给首一不可约多项式p ( x ) k 吲， = 器：m 加( 小删 p ( 引出) ) 为函数域k ( x ) k 的赋值环，具有极大理想 昂= 器：m ) ，出) k 吲，p ( 圳m ) ，p ( 引出) ) 多项式妒( t ) k ( z ) 【卵称为绝对不可约的，如果妒( t ) 在多项式环 k 0 ) t i 上不可约且在多项式环露( 茁) 【邳上也不可约( 霞表示k 的代数闭 包) 设p 是函数域f k 的位，p p 为其赋值环因为p 为极大理想，所 以剩余类环o p p 为域对茹p p ，定义x ( p ) 为z 模p 的剩余类对 x f o p ，定义z ( p ) ：- - - 0 0 由命题1 1 1 可知，k o p 且knp = o 】， 所以剩余类映射侈p _ 移p p 诱导出嵌入映射k _ o p p 从而可将k 看 作o p p 的予域，以上论断对露也成立，所以k 也可看作o p p 的子域 定义1 1 5 ( 剩余类域和位的次数) f p ：= o p p 为p 的剩余类域映射 f f pu0 0 ，zh x ( p ) 称为关于p 的剩余类映射d e gp ：= 【f p ：网称为位 p 的次数当d e gp = 1 时，位p 称为函数域f k 的有理位 定义1 1 6 ( 零点和极点) 设z ep 路称p 为彳的零点当且仅当 u p ( z ) 0 称p 为名的极点当且仅当v p ( z ) 0 ，则尸 为名的m 阶零点如果v e ( z ) = 一m 0 ，则p 为z 的r f $ 阶极点 注l 11 在函数域州k 中，任意0 。f 只有有限多个零点和极点 赋值的重要特性是独立性即假设l j l ，屹，是f k 上两两不同的赋 值且z f ，则即使已知z ，l ( z ) ，屹( z ) ，一1 ( 名) ，也不能确定关于( 2 ) 的 任何信息 定理1 1 3 ( 弱逼近定理) 设f k 为函数域，r ，恳，r p f 为州k 上两 一4 一 第1 章前青 两不同的位，x l ，z 2 ，x n f 且r l ，r 2 ，z 则存在z f 使得 一x i ) = n ，i = 1 ，2 ，n 推论1 11 任意函数域都有无穷多个位 易知函数域刚k 的常数域霞为k 的有限扩张，且f 可以看作詹上的 函数域因此以下不妨假设f k 为具有完全常数域k 的函数域 定义1 1 7 ( 除子) 州k 的除子群记为d f d f 中的元素称为州k 的除子， 除子d 为以下和式 d = h e r , p e p f 其中n p z 且只有有限多个n p 0 若d = p ，p p f ，则称d 为素除子 令s u p p d 表示除子d 的支集，即s u p p d ：- - p p f ：礼p o ) m 是加法交换群，即对任意d = 勿f ，有d + d = ( n p + n ) 尸成立 p e p v n p p d f ，d =死，p 尸 p e p pp e p p 除子群d r 中的零元素为 0 ：= n p p , 所有的礼p = 0 p e p f 对任意d = n p p ，除子的赋值定义为v e ( d ) ：- - - j n p 定义除子间 p 警f 的偏序关系如下：任意d 1 ，d 2 d f ，d 1 d 2 当且仅当对任意p p f 有 v p ( d 1 ) v p ( d 2 ) 称a 聊为有效除子如果a 0 除子的次数定义为 d e g d = v p ( d ) d e g p p e p p 定义1 1 8 ( 主除子) 设0 z f ，令z ( 或) 表示z 的所有零点( 极点) 集 合则分别定义x 的零点除子，极点除子和主除子如下 ( z ) o ：= v e ( z ) p , ( z ) 。：= ( 一坳缸) ) p ，d i v ( z ) ：= ( z ) o 一( z ) p zp e n 一5 一 第1 章前言 显然( x ) o 0 ，( z ) 0 且 d i v ) = z ，p 扛) p p e p p 定义1 1 9 ( 主除子群和除子类群) 尹i f ：嚣 d i v ( z ) ：z f + ) 称为f k 的主除子群它是球的子群，从而可定义州k 的除子类群 c f ：= d f i 9 f c f 中的元素记作 d 】，其中d 次数为d e g d 1 = d e g d 任意d 1 ，d 2 d f ，除子间的等价表示为d 1 一d 2 d i 一跳当且仅当存 在某个z f 奎使得d l d 2 = d i v 扛) ，即【d 1 】= 【d 2 】 砩：- - - d 砚：d e gd = o ) 表示州耳的零次除子群定义j f ：2 d 晏御= “d 】，d e g d = 0 ，d 所) 令h ( f ) 表示函数域f 的除子类数，定 义为h ( f ) 7 - i j f i 令a ( f ) 表示f 的次数为k 的有效除子组成的集合，记a k ( f ) = l a k ( f ) i ，简记为a 知 下面介绍函数域理论中的重要定义 定义1 1 1 0 ( r i e m a n n r o c h 空间) 对任意a ：d r ，定义以的r i c m a n n - r o c h 空间 为 c ( a ) ：- - ，f 事：d i v ( f ) + a o ) u o 命题1 1 2 对r i e m a n n r o c h 空间，有以下结论成立 1 任意a 巩，c ( a ) 为k 上的有限维向量空间 2 对任意d l ，d 2 d f ，若d 1 d 2 ，则p - ( d 1 ) ( d 2 ) 3 除子a 的维数定义为d i m a ：- - d i m ( a ) 特别，( o ) = k 4 z z ( a ) 当且仅当对所有的p 赡，有u p ( x ) 一印似) 第1 章前青 函数域理论中一个最重要的课题就是计算r i e m a n n r o c h 空间的维数，略 去详细证明( 参见 1 9 1 ) ，这里只叙述函数域的亏格和r i e m a n n r o c h 定理的相 关知识 命题1 1 3 存在常数，y z 使得对所有的除子a d f ，有 d e g a d i m a ，y 定义1 1 1 1 ( 函数域的亏格) 函数域f k 的亏格定义为 g ：= m a x d e g a d i m a + 1 ：a ， 注意到由命题1 1 1 3 可以保证亏格的定义有意义亏格是函数域中最重 要的不变量在以上亏格的定义中，令a = 0 ，则d e g ( 0 ) 一d i m ( 0 ) + 1 = 0 ， 所以g 0 定义1 1 1 2 ( 函数域的a d e l e ) 函数域州k 的a d e l e 是指一个映射 q ： ? = 0 ， 满足对几乎所有的p p f 有q p o p ( 即只有有限个q pgo p ) 如：- - - q ：o t 是f k 的a d e l e 称为州k 的a d e l e 空间对a 聊，定义 a f ( a ) ：= o l a f ：v p ( o t ) 一即( a ) ，对所有的p 脚) 显然，a f ( a ) 为a f 的k 一子空间 定义1 1 1 3 ( 函数域的w e i l 微分) 函数域的w e l l 微分是指一个k 一线性映 射u ：, a f k ，满足对某个除子a ，u 在a f ( a ) + f 上消失( 即 w ( a f ( a ) + f ) = 0 ) 定义 q f ：= 扣：为f k 的w e i l 微分) 一7 一 第1 章前言 q f 为k 上的模，称为州k 的w e l l 微分模对a 诉，定义 f 2 f ( a ) ：= o j q f ：u 在a f ( a ) + f 上消失) 为了将w e i l 微分u 0 与除子联系起来，考虑如下除子集合 m ( w ) ：= a 巩：u 在a f ( a ) + f 上消失) 命题1 1 4 设0 u q f 则存在唯一除子w m ( u ) ，使得对任意a m ( u ) 有a w 记与u 相对应的这个除子彤为) 定义1 1 1 4 ( 典范除子) 除子彬被称为州k 的典范除子，如果对某个u q f 有w = p ) 定理1 1 4 ( r i e m a n n r o c h 定理) 设为f k 的典范除子则对任意a df奄l d i m a = d e g a + 1 一g + d i m ( w a ) 作为r i e m a n n - r o c h 定理的重要应用，我们有如下定理 定理1 1 5 对任意a d f ，有d i m a d e g a + 1 一g 若d e g a 2 9 一1 ，则 有d i ma = d e ga + 1 一g 1 1 2 纠错码的基本理论 本小节主要介绍纠错码理论的基本概念和几何g o p p a 码的构造，详细知 识参见【1 9 1 定义1 1 1 5 ( 码) 设n 为正整数，a 为非空有限集合码定义为a 竹的任意非 空子集c ，其中a n ：= ( o l ，a 2 ，a n ) ：a i a ，1 i 佗) c 中的元素称为 码字，扎称为码长，m ：= i c i 称为码字个数 ， 设f q 为具有口个元素的有限域当a = f q 且c 瑶为线性子空间时， c 称为线性码此时称d i m c ( c 作为f q 一向量空间) 为码c 的维数 定义1 1 1 6 ( 码的最小距离) 任意a = ( a l ，a 2 ，口n ) ，b = ( b l ，5 2 ，厶n ) a n ，定义 d ( a ，b ) ：- - m 1 ，2 ，扎) ：a i b a l l ， 第1 章前言 d 称为a n 上的h a m m i n g 距离元素a a 牡的重量定义为 w t ( a ) ：= d ( a ，0 ) = m 1 ，2 ，n ：口0 1 非零码c 的最小距离a ( c ) 定义为 a ( c ) ：一- - - m i n d ( a ，b ) ：a ，b c 且a b ) 因为d ( a ，b ) = a ( a b ，0 ) = w t ( a b ) ，所以当c 为线性码时，d ( c ) ：- - - m i n w t ( c ) ：0 c c ) 注1 1 2 h a m m i n g 距离d 是一种度量，即满足对任意x ，y ，z a n 有 1 d ( x ，y ) 0 e ( x ，y ) = 0 当且仅当x = y 2 d ( x ，y ) = d ( y ，x ) 3 d ( x ，z ) d ( x ，y ) + d ( y ，z ) h ，尬明码是指具有码长为n 。码字个数为m ，最小距离为d 的码作为 线性码，阮明码是指具有码长为死，维数为后，最小距离为d 的码 纠错码理论中有许多有用的码，比如循环码，b c h 码以及r e e ds o l o m o n 码( 几何g o p p a 码被认为是r e e ds o l o m o n 码的自然推广) 等等，它们在通信中 都起着重要的作用这里我们只介绍几何o o p p a 码 设叫是亏格为9 的函数域最，r 为f 峨的两两不同的有理 位令d = p 1 + + r g 为f 的除子满足s u p p g n8 u p p d = 仍 定义1 1 1 7 ( 几何g o p p a 码) 与除子d 和g 有关的几何g o p p a 码既( d ，g ) 定 义为 c z ( d ，g ) ：= ( z ( 毋) ，z ( 恳) ，z ( r ) ) ：z c ( g ) ) f 孑 注意到z ( g ) 且$ u p p gn $ u p p d = d ，所以v p , ( x ) 0 “= 1 ，死) ， 于是z ( 最) f p , 0 = 1 ，佗) 因为d e g 毋= 1 ，所以f 只= f q ，即z ( 只) ( i = 1 ，他) 定理1 1 6 q ( d ，g ) 为h ，七，碉线性码且 k = d i m g d i m ( c d ) ，d n d e g g 第1 章前言 推论1 1 2 若d e g g 扎，则几何g o p p a 码的定义映射z ( a ) 一q ( d ，g ) ，zh ( z ( 只) ，z ( 最) ，z ( r ) ) 为单射，且有如下结论成立：c 2 ( d ，g ) 为b ，k ，明码 且 k = d i m g d e g g + 1 一g ，d n d e g g 由此，k + d 佗+ 1 一g ，从而可得到著名的1 、厂z 界( 参见下一节) 1 1 3 代数曲线与代数函数域 为方便第2 章的叙述，本小节从射影簇的角度介绍代数曲线和代数函数 域的关系以下假设k 为代数闭域 定义1 1 1 8 ( 射影簇) + 1 维仿射空间a 蚪1 = ”+ 1 ( k ) 是由中元素组 成的所有忍+ 1 元组的集合在集合a n + 1 ( 0 ，o ) ) 中定义等价关系一 如下，( a o ，a l ，a n ) 一( b o ，b l ，k ) 当且仅当存在元素0 a k 使得 k = a a i ，0 i 钆( a o ，a l ，a n ) 关于形成的等价类记为( a o ：8 1 ： 口n ) n 维射影空间p n = p n ( k ) 定义为等价类的集合 p n = ( 知：a l ：a n ) ：啦k ，并非所有的a i = o ) 元素p = ( a o ：a l ：a n ) p n 称为点，a o ，8 l ，a n 称为点p 的齐次坐 标 令k 【弱，墨，】表示k 上死+ 1 个变量的多项式环，d 次单项 式g k x o ，x a ，矗】具有形式g = a 1 - i 砰，其中0 d k 且 n = o 呔= d 多项式f 称为齐次多项式是指f 为相同次数的单项式的和式由 齐次多项式生成的理想j k x o ，x t ，k 】称为齐次理想 子集y p n 称为射影代数集，如果存在齐次多项式子集m k f 矗，x l ，】使得 v = 尸p n ：f ( 聊= 0 ，对所有的f m ) 给定射影代数集y p n ，多项式集 i ( v ) = 0 若g 为平方数，则a ( q ) = 撕一1 ，达到 a ( q ) = 狮一l 的函数域序列已由g a r c i a 和s t i c h t e n o t h 【7 】，【8 】具体构造出来 但对于非平方数口，a ( q ) 的值未知，现已知关于a ( q ) 的一些上下界例 如，【l 】中证明了对任意立方数口，有z i i l l 【下界 讹) 帮 关于a ( q ) 的具体内容参见【1 5 】 码的渐近理论一个核心问题是寻找a 口( 6 ) ，0 6 ( 口一x ) q 的下界而 几何g o p p a 码构造方法的各种推广对此下界的寻找起着重要作用( 具体参见 【1 8 ， 2 9 】，【3 0 】，【1 7 】，【2 1 ，【2 8 】， 2 1 1 ，【3 】) 邢基于有限域上曲线的偏z e t a 函数证明 了几何g o p p a 码对所有的素数幂次q ( 包含q = 2 ) 可达到口一元g v 界f 2 7 而t s f a s m a n 等人的贡献在于利用代数几何码在某个开区间上改进了g v 界 【15 】，得到t s f a s m a n - v l 备k l u t z i n k 界( 简称1 v z 界) q 口( j ) 1 6 一a ( g ) 一1 ，0 6 1 ( 1 2 2 ) 随后v 1 2 t d u i 【2 4 】和邢f 2 5 】改进了非线性码的1 、亿界邢构造出非线性码 在整个区间【0 ，1 】上改进了t v z 界1 2 6 - , 0 0 ( 6 ) 1 5 - a ( q ) 一1 + l o g q ( 1 + ( g 一1 ) q 蕊) ( 1 2 3 ) i = 2 之后不久，这个新界由e l k i e s 【4 】， 5 1 利用模曲线的工具对某些口( 即口= p 2 ，p 第1 章前言 为任意素数幂次) 改进为： ( 6 ) 1 6 一a ( g ) _ l + l o g q ( 1 + 矿1 ) ( 1 2 4 ) 注1 2 1 ( 1 2 3 ) 式的下界约为1 一j a ( q ) 一+ l o g 口( 14 - ( g 一1 ) q a ) ，所以( 1 2 4 ) 式给出的下界要更优 而e l k i e s 【5 】提出将构造码的方法推广到考虑g o p p a 构造里函子的高阶 导数，据此本文在第2 章中得到e l k i e s 方法的一般结果后来n i e d e r r e i t e r 和 o z b u d a k 【1 2 】将界( 1 2 4 ) 改进到对任意素数幂次g 成立而后s t i c h t e n o t h 和 邢【2 0 】利用代数函数域的知识通过构造代数几何码给出了此界的简单证明， 证明的关键在于引入了函子的极点和极点重数 近来，n i e d e r r e i t e r 和0 z b u d a k 【1 3 】对特定的q 和6 进一步改进渐近界 【1 3 1 ： a q ( 6 ) l 一6 一a ( g ) 一1 + 凰( z ) - - 4 x + 丽1 矽( x , 1 - - 缸一6 ) ，( 1 2 5 ) 其中0 z 1 4 为实数，0 j 1 一缸也为实数，妒( z ，1 一缸一6 ) 为关于 z 和j 的非负值函数作为此结果的特例在某些6 上可得到下界 ( 6 ) l 一6 一a ( q ) q + l 。g q ( 1 + 争) ( 1 2 6 ) ) m a h a r a j 综合应用n i e d e r r e i t e r 和o z b u d a k ，s t i c h t e n o t h 和邢的构造方法得到更 好的渐近界 1 1 】如下设实数0 0 定义函数 假设 且 e ( c , r , x ) ：= c l o g q ( q 一1 ) 一贯5 c c l o g qc 一( 1 一c ) l o g q ( 1 一c ) + o rl o g 口r c ( r 一1 ) l o g 口p 一1 ) + 凰( z ) 一4 x ) + a ( 口) ( 胎p ( 肿) 1 + a ( q ) l o g q 寺， 。 6 m i n 2 - 4 c - 2 r c - 缸一需1 _ 缸- 3 c ) ， 第i 章前言 则 a 口( 巧) 1 6 一a ( g ) 。1 + 南+ e ( c ，n z ) ， 其中j ( 盯) 定义参见第3 3 节，区域r ：= ( p ，叼) ：c p 2 c ，p 叩冬p + 2 x ， 伊( p ，7 ) ：= - 2 p l o g qp + 2 r c l o g 呵( 2 r c ) 一( 2 r c p ) l o g q ( 2 r c 一力一( ，7 一p ) l o g q ( r 一力 - ( 1 4 c 一4 x 一6 + 叼) l o g q ( 1 4 c 一4 x 一6 + 卵) 一( 4 c + 4 z + 6 2 r ) l o g 口( 4 c + 4 x + 6 2 7 7 ) 最新的结果由n i e d e r r e i t e r 和o z b u d a k 通过对其构造特殊除子的方法【1 3 】改进 和补充得到 1 4 1 ：设x l ，x 2 ，z m 0 为满足2 ( 2 x l + 3 x 2 + + ( m + 1 ) ) l 的实数对任意实数0 6 l 一2 ( 2 x l + 3 x 2 + + ( m + 1 ) x m ) 有 ( 6 ) 1 6 一a ( q ) 一1 + ( x l + + z m ) l o g 口( 口一1 ) 一( x ll o g qx 1 + + z ml o g qx m ) - ( 1 一( x l + + x m ) ) l o g 口( 1 一( x l + + x m ) ) 一( 4 x l + 5 x z + + ( m + 3 ) x m ) + 高帅一6 - 2 ( 2 。- + 缸2 + - + ( m + 1 ) ) ，渤) ， 其中妒( 1 6 - 2 ( 2 x l + 缸2 + + ( 仇+ 1 ) z m ) ，z l ，x 2 ，z m ) 为关于6 ，x l ，z m 的实值函数 下面介绍本文的主要结论 1 3 主要结论 本节主要介绍我们在第2 章和第3 章中得到的主要结论 在第2 章中我们在模曲线上利用函子的高阶导数构造码，得到e l k i e s 方 法【4 】，【5 】的一般结果e l k i e s 方法的特点在于将无穷远点引入码的映射中， 得到渐近界 m 一1 m - - 1 口口( 6 ) 1 6 一a ( g ) 一1 + l 。g q ( q + 1 ) 峨+ 1 ( 印) + 最g ( 吼) 一2 ( m + 1 ) ( 死) i = 1i = 0 第1 章前言 对任意m 1 ，令 经计算可知，当a o = l ( 1 + q 2 m + 1 ) ，a i = ( g 一1 ) ( q 2 ( m + 1 ) + g 一1 ) ，1 i m 一1 且m = 1 时，h m ( o o ，0 1 ，o m 1 ) 取得最大值l o g q ( 1 + 1 q a ) 即e l k i e s 方法 的最好渐近下界为 ( 6 ) 1 6 一圳一1 + l o g 口( 1 + 1 ) ( 1 3 1 ) 在第3 章中我们基于n i e d e r r e i t e r 和o z b u d a k 【1 3 】方法构造出非线性码改 进渐近界，得到新界 0 f q ) 1 6 一a ( q ) 一1 + 峨( 正) 一6 z + 峨( 掣) 一4 矽 + 南矽( x , g , 1 - - 6 x - - 幻棚， ( 1 3 2 ) 其中0 z x 6 ，0 y v 4 为实数，0 一 扩p 0 ，j 一铷 一 ，j印 足s u p p gn1 只，r = 口，则对任意f c ( g ) ，有v p , ( f ) 0 ，1 i n 再设t i 为f 上最处的局部参数，则函子f 在只处有局部展式为 f = ，( o ( 只) + ，( 1 ( b ) 如+ ，( 2 ( 只) 亡；+ 其中f ( j ) ( p ) f 口，歹= 0 ，1 ，2 ， 对任意整数0 。， 引理2 2 3 ( 参见【4 】) 若( q a p f ) ( p ) = ( 妒p ，) ( p ) = 有限值 若( 5 p p f ) ( p ) = ( p p ) ( p ) = 0 0 若p 不是f = f 7 的解 脚捌：= 南暑刚蚓， 如果c 为渐近最优曲线( 即当亏格g 0 0 时，曲线上至少有( 钷一1 一d ，( 1 ) ) 9 个有理点) ，则对任意p 2 q ( q 2 1 ) ，当2 h n p 时， 脚，c ) = ( 字) 咖宁g 第2 章e l k i e s 方法的推广 推论2 22 存在d o 矗使i m d o ( h ) i ( 学) n 州n ) 9 2 h 呻 引理2 2 4 ( 参见【5 】) 假设，m d ( h ) ，厂( ) ，f ，则对任意p c ( f q ) ，有 r e ( p ) = h + h p c ( 岛) 推论2 2 3 任意，m d ( h ) ，= 解的总重数不超过2 设0 吼 n 咖州l = q 眦蔷蜘卜册烈u 1 ( 2 2 2 ) i = 0j = o 、。，i = 0 由( 2 2 1 ) 式和( 2 2 2 ) 式可得， 3 , 1 m l 一2 5 一 ( 2 2 3 ) m d“ m一以 e ：l n g gc 第2 章e l k i e s 方法的推广 2 3 码的构造及渐近界 本节将对e l k i e s 构造非线性码的方法作一般性推广，得到一般情况下的 渐近界并验证出此种方法得到的最优结果仍是( 1 2 4 ) 式以下提到的除予d 满足d e gd = 0 ，h 为任意非负整数 定义映射 如：m o ( h ) 一p 1 ( f q ) n ，h( ( 妒r ，) ( 只) ，( 妒r ，) ( r ) ) ：= ( z ( o ) ，。9 ) 其中p 1 ( f q ) = i f 口u 【o 。) 对任意i 1 ，定义相关集合和映射 以：m d ( h ) 叫叼 ，h( z f ，z g ) 其中 个( t ) 一j ( 妒弓，) ( ) ( 弓) ， 若( q o p j f ) ( p j ) = 有限值 。j 一1 【( 妒弓，) 一1 p ( 弓) ，若( 妒巧，) ( 易) = o o 朋笤( 九) ：= ，a 幻( h ) ：d ( q ，如( ，) ) l 吼州) a 幻( 九) 引理2 3 1 ( 参见【5 】) 1 j 佗对任意m 1 ，p j 为，= 的m 重解当且 仅当咖( ，) 与办( ) ( o ，- c 字n ) q 2 h - g 唪装筹铲g 。g 啪) - ”1 ) d ( 1 ) l = ( 字) o c n ) q 2 h - g - n ( ) n h 口+ l ( a o ) - o ( 1 ) q n l 量州引书_ 卜沏。1 卜“。1 。m ，d e g a x 。：ol m 。，m ( 叭= l m d ，m ( 叭 m 一1 m d m ( ) l 口2 h - g - n ( g + 1 ) n 【凰+ ) 一“1 ) l q n 量凰慨卜呻一1 卜觚一1 。1 1 码定义为，m ( 九) ：= m ( 朋d ，m ( 九) ) 下面计算码m ( ) 的最小距离 对任意，m d m ( ) ，有 d ( 龟，晚( ，) ) o n ，d ( q ，b i ( f ) ) 吒佗，0 i m 一1 于是 d ( o i ( f ) ，妒i ( ，) ) 2 a i n ，0 i m 1 设也( ，) = ? ，拷) ，也( 厂) = ( 可) ，毋) ，0 i m 则 d 1 川2 ，佗) ：锣= 正o ) l 佗一2 a o n ， l d 1 ，2 ，n ) ：x ，( o = 秽且龟1 菇1 ) i ：= d l d 1 ( ，) ，l ( ，) ) 2 a l 佗， 一2 7 第2 章e l k i e s 方法的推广 因此 d 1 ，2 ，n ) ：锣= z o 且毒1 = 菇1 ) l n 一2 a o n - d l 竹一2 c r o n - - 2 a l n 又 f u l ，2 ，n ) ：母= 西o 且砖1 = z 1 且乎z 2 ) i ：= d 2 d ( 锄( 厂) ，如( ) ) 2 0 r 2 n ， 所以 d 1 ，2 ，n ) ：z j ( o = 西o 且弓1 = 彰1 且乎= 髟2 ) 扎一2 0 r o n 一2 0 x n 一如扎一2 a o n 一2 0 1 n 一2 0 2 n 类似下去，由引理2 3 1 可知，d i 表示p l ，b ，r 中为f = f 的i 重解的 个数，l i m 于是有 j 1 ，2 ，n ) ：母= 彰n ，1 i m 一1 且哆彰m ) l ：= d ( ( ，) ，b m ( f ) ) i j l 川2 一，他) ：母= 孙，1 i 仇) =i 歹 1 ，2 ，n ) ：m ( 马) m + l l2 住一2 c r o n 一2 0 1 n 一2 0 2 n 一一2 仃m i n d 击 由推论2 2 3 可得， 2 h d l + 2 如+ 3 d 3 + + m d m + ( m + 1 ) ( 佗一2 0 r o n 一2 c r x n 一2 c r 2 n 一一2 一l 死一d 未) ( 仇+ 1 ) ( 佗一2 0 o n 一2 c r l n 一2 a 2 n 一一2