（概率论与数理统计专业论文）无限长信号中值滤波的根与循环序列.pdf

号中值滤波的根与循环序列 周性伟 教授 凌晖 南开大学数学科学学院 1 9 9 9 年 5月 摘 要 设 k 表示一个固定的正整数， x = x ( n ) n . z 是一列实数。对每个n，用e f , x ( n ) 或x 0 1 ( n ) 表示x (i) ， _ 、 n+ 、 这 2 k + 1 个实数由小到大重排后位于中 间的 那个数。 通过这样的重排运算， x ( n ) 变成了一个新的实数列， 记为m f k x ( n ) 或x o ( n ) ， 它称为x 的 窗宽为2 k + 1 的中 值滤波。 对x o ) =x ( n ) 又可 进t r 窗 宽为2 k + l 的中 值滤波， 结果记为x (2 ) = x 12 1 ( ( n ) 。 一般地， x 通过p次窗宽为2 k + 1 的中 值滤波后的结果记为洲 一x 0 1 ( n ) 。若x 在中 值滤波算子m f k 作用下不变， 即x 0 二x， 则称x 为中 值滤波m f k 的根; 若x 不是根， 但有s - 2 ，使得x 经中 值滤波算子m f k 的: 次作用后不变，即x ls ) 二 x， 则称x 为中 值滤波m f k 的 次 循环序列。 设x 二 x ( n ) 是实 数列， 若对某个n 有x ( n ) # x ( n + 1 ) ， 则称( n , n + l ) 为x 的 跳点对。若x 是中值滤波m f k 的第1 1 类根t2 1 ， ( n , n + 1 ) 是x的跳点对，则称段 落x n - k , n + l 十 k 为根x 的对称段。若x 是中 值滤波m f , 的循环序列，则我们定 义有序序列对( x , x c ) 为循环序列对;若( n , n + l ) 是x 的 跳点对，则我们定义段 落对( x n - k , n + l + k , x ( ) n - k , n + l + k ) 为 循环序列对( x , x 0 ) 的 对称段。 中值滤波的 概念自1 9 7 4 年由t u k e y 提出后，在波形估计、图 像增强及噪声 消除等方面得到了广泛应用。二十多年来，中值滤波的理论研究也有了很大的 进展。关于中值滤波的根的结构，已经有了完满的结果:( 1 ) 中值滤波的根有两 类，第i 类根的任何长度为k + l 的段落都单调，第1 1 类根的 任何长度为k + l 的 段落都不单调 ,2 ; ( 2 ) 第i i 类根是二值序列2 ; ( 3 ) 第1 1 类根被它的任一对称段所 完全确定3 ，即一 个对称段能唯一地扩张成一个第 1 1 类根:( 4 ) 第1 1 类根的构造 定 理 3 ， 即 第 1 1 类根的 对称段的 充要条件。 关于中 值滤波的 循环序列的结构， 也 已 经 知 道 : ( 1 ) 循 环 序 列 是 二 值 庆 列 :(2 ) 循 环 序 列 必 然 是 二 次 循 环 的 5 尹 一 本文 本文详细 些结论的基础 匕 r重点研究中值滤波的循环序列的性质和结构。 究了 循环序列对( x , x ( ) 的对称段的基本性质( 定理1 一定理3 ) ，得 到了 三个主要结果: ( 1 ) 循环序列对( x , x 1 ) 被它的任一对称段所完全确定，即， ( 循环 序列对的 ) 一个对 称段能唯 一地扩张成一个循环序列 对( 定理 4 一定理 5 ) , 从而 唯一确定一个循环序列x ; ( 2 ) 中 值滤波的循环序列的构造定理( 定理8 ) ，即 循环序列对的对称段的充要条件;( 3 ) 作为循环序列构造定理的一个特殊情形， 本文 得出了中 值滤波第i i 类根的构造定理， 并给出了 它的 一 个代数表示( 定理9 一 定理1 0 ) 。上述结果完全解决了无限长信号中 值滤波的循环序列的结构问 题，并 使第1 1 类根的实际构造过程得以简化。 o n r o o t s a n d r e c u r r e n t s e q u e n c e s t o me d i a n f i l t e r i n g o f i n f i n i t e s i g n a l s tu t o r: au t h o r: d e p t . : ti me: p r o f x i n g w e i z h o u h u i l i n g s c h o o l o f ma t h e m a t i c s , n a n k a i u n i v e r s i t y ma y , 1 9 9 9 ab s t r a c t s u p p o s e t h a t k d e n o t e s a f i x e d p o s it i v e n u m b e r a n d x = 笼 x ( n ) e z i s a s e q u e n c e o f r e a l n u m b e r s . f o r a n y n , w e d e n o t e m f k x ( n ) , o r x o ( n ) , t h e m e d i a n v a lu e o f t h e s e t ( x 0 - a - 、 。 * . t h u s , a n e w s e q u e n c e i s f o r m e d f r o m x ( n ) . i t i s c a l l e d t h e me d i a n f i l t e r i n g ( w i t h 2 k + l 一 w i d e w i n d o w ) o f x a n d d e n o t e d b y m f k x ( n ) o r x ( ( n ) 1 . w e c a n p e r f o r m t h e o p e r a t i o n o n x o ( ( n ) ) a g a in a n d g e t x (2 ) = x t2 ( n ) ) . g e n e r a l ly , t h e p - th r e s u l t o f m e d i a n f i l t e r i n g o f x i s d e n o t e d b y 沙) 二 x ) ( n ) . i f x i s i n v a r i a n t t o t h e o p e r a t o r m 凡， e .g . x ( i ) 一 x , t h e n w e c a l l x a r o o t t o t h e m e d i a n f i l t e r m f , ; i f x i s n o t a r o o t , b u t t h e r e i s s - 2 s u c h t h a t x e q u a l s t h e s - t h r e s u l t o f me d i a n f i l t e r i n g , e .g . x w = x t h e n w e c a l l x a s - t h r e c u r r e n t s e q u e n c e t o mf , . l e t x = x ( n ) ) b e a s e q u e n c e o f r e a l n u m b e r s , i f f o r s o m e n , x ( n ) #x ( n + 1 ) , t h e n w e c a l l ( n , n + 1 ) a j u m p i n g p o i n t p a i r . i f x i s a c l a s s i i r o o f s t o m f , ， ( n , n + l ) b e i n g a j u m p in g p o i n t p a i r , w e c a l l x n - k , n + l + k a s y m m e t r i c s e c t i o n o f t h e r o o t x . i f x i s a r e c u r r e n t s e q u e n c e t o m f , ， w e d e f i n e t h e o r d e r e d p a i r ( x ， x ( ) a r e c u r r e n t s e q u e n c e p a i r , a n d , i f ( n , n + l ) i s a j u m p i n g p o i n t p a i r , d e f i n e ( x n - k , n + l + k , x ( ) n 一 k , n + l + k ) a s y m m e t r i c s e c t i o n p a i r o f t h e r e c u r r e n t s e q u e n c e p a i r ( x , x o ) . s i n c e t h e c o n c e p t w a s s u g g e s t e d b y t u k e y i n 1 9 7 4 , me d i a n f i l t e r i n g h a s b e e n w i d e l y u s e d i n w a v e f o r m e s t i ma t i o n , i m a g e e n h a n c e me n t , n o i s e e l i m i n a t i o n , e t c . t h e o r e t i c a l s t u d i e s o n me d i a n f i l t e r in g h a v e a l s o g r e a t l y a d v a n c e d i n t w o d e c a d e s . n o w w e h a v e i d e a l c o n c lu s i o n s o n s t r u c t u r e s o f r o o t s : ( a ) r o o t s a r e d i v i d e d i n t o t w o c l a s s e s 1 1 ,2 1; ( b ) c l a s s i l r o o t s a r e b i - v a l u e d 12 1; ( c ) a c l a s s i i r o o t i s d e t e r m i n e d b y a n y o f it s s y m m e t r i c s e c t i o n s (3 1 ; ( d ) t h e s t r u c t u r e t h e o r e m o f c l a s s i i r o o t s l3 . a n d w e h a v e a l s o k n o w n t h a t r e c u r r e n t s e q u e n c e s a r e a l w a y s b i - v a l u e d a n d b i - r e c u r r e n t j0 ， ! b a s e d o n t h e r e s u l t s , t h i s p a p e r s t u d i e s p r o p e r t i e s a n d s t r u c t u r e s o f r e c u r r e n t s e q u e n c e s t o me d i a n f i l t e r i n g . a ft e r c a r e f u l l y s t u d y i n g p r o p e r t i e s o f t h e s y m m e t r i c s e c t i o n p a ir , w e r e a c h t o t h r e e i m p o rt a n t c o n c l u s i o n s : ( a ) a r e c u r r e n t s e q u e n c e p a i r i s e n t i r e l y d e t e r m i n e d b y a n y o f i t s s y m m e t r ic s e c t i o n p a i r s ; ( b ) t h e s t r u c t u r e t h e o r e m o f r e c u r r e n t s e q u e n c e s ; ( c ) a s a s p e c i a l c a s e o f t h e t h e o r e m , w e p r e s e n t t h e s t r u c t u r e t h e o r e m o f c l a s s 1 1 r o o t s t o me d i a n f i l t e r i n g a n d g i v e it a n a l g e b r a i c r e p r e s e n t a t io n . t h e r e f o r e , w e h a v e s o l v e d t h e p r o b l e m o f c o n s t r u c t i o n o f r e c u r r e n t s e q u e n c e s t o m e d i a n f i l t e r i n g a n d s i m p l i f i e d t h e a c t u a l c o n s t r u c t i o n o f c l a s s 1 1 r o o t s . 致谢 衷心感谢我的导师周性伟教授三年来的精心指导。是导师的指 导使我在三年中学到了许多深刻而系统的专业知识，同时导师的敬 业精神，严谨的治学态度，在数学领域里不断探索的精神深深地影 响了我。本论文是在导师的悉心指导下完成的。 在木文写作过程中，教研室的诸位老师，本专业的诸位同学给了 我很多启发和建议，对此表示由衷的感谢。 无限 长信号中值滤波的根与循环序列 一、 引言 设 正 整 数k 1 ， 给定 实 数 列x = x ( n ) ) . 士 :.士 z , . ， 则 对每一n ， 我 们用 记号 m f k x ( n ) 或x ( l) ( n ) 表示 x ( n - k ) , x ( n - k + l ) , , x ( n ) , - - - , x ( n + k - 1 ) , x ( n + k ) 这2 k + l 个实数由 小到大重排后位于中间的 那个数。 若对某n 有m f k x ( n ) = x ( n ) ，则我们 说 中 值 滤波算子一 f对x ( n ) 不 变。 于是通过 这样的 重排运算 x ( n ) 变成了 个 新的实数列，iel 为m f k x ( n ) ) ， 或x ) ( ( n ) ) ，它称为x 的中值滤波( 窗宽为2 k + 1 ) o 对x ( i ， 一 x o ，) 厦 ( n ) 又 可进行中值滤波( 窗宽为2 k + l ) ，结果记为x + ) 一 x (2 1 ( n ) ) 。一般 地， x 通 过 p 次 窗 宽 为2 k + l 的 中 值 滤 波 后的 结 果 记 为x (0 ) 一 x (p ) ( ( n ) ) - o, 1 1, = 2 ,- ， 特别地，记x (0 ) = x。 若x 在中 值滤 波算子m f k 作用下不变，即x m = x， 则 称x 为中 值滤波m f ; 的 根; 若x 不是 根， 但有s 2 ， 使得x 经中 值滤波算子m f k 的 次 作用后不变， 即x ,“ 二x， 则称x 为中值滤波m f k 的: 次循环序列;当p 2时， 沙) 统称为二 的广义中值滤波;若对每一 n , 滤 波 收 敛 川 。 极 限l i m p )( np - -) 存 在 有 限 ， 则 称 的广义中值 以 下本文用n表示正整数全体， z 表示整数全体， k 为固定的正整数， ( x ( n ) ) 表示两端均无限的实数列， x i ,j 表示 x ( n ) 中的段落 x ( i ) x ( i + l ) , - - . , x ( i - 1 ) , x (1 ) o x 2 ,j 】 称为常数段，是指该段中 所有项都取相同的 值。 关于中值滤波的根和循环序列的结构以及广义中值滤波的收敛性，已经有 这样一些结论。 命题1 若x = x ( n ) 是中值滤波m f k 的根，则或者 ( i ) x ( n ) 中任何长度为 k + l 的段落都单调;或者 ( i i ) x ( n ) 中 任何长度为k + l 的段落都不单调。此时， 满足( i ) 的 称为m f k 的 第i 类根，满足( i i ) 的称为m f k 的第i i 类根2 1 命题2 x = x ( n ) 是中 值滤波m f k 的第i 类根的充分必要条件是或者 x ( n ) ) 单调， 或者 x ( n ) 中 任何常 数段的 长度不小于k + l r i , 命题3 中 值滤波m f k 的任何第i i 类根都是二值序列2 1 命题4 中值滤波m f k 的 所有第1 1 类根可被一组长度为2 k + 2 的满足适当 条 件的 二 值 序 列 构造出 来 (3 ) 命题5 若x = x ( n ) 是中值滤波m f , 的循环序列， 则x 必然是二值序列， 并 且 x 是 二 次 循 环 的 ， 即 ， (，) 一 二 4 , 51 命题6 若x = x ( n ) 中 含有长度为k + l 的常数段， 则x 的广义中值滤波收 敛 于 一 个 根 6 7!。 命 题7: 一 ( x ( n ) ) 为 实 数 列， 则 对于x的 广 义中 值 滤 波 有: 或 者 x n )( n ) p , 收 敛 于一 个 根， 或 者( x (w -)( n ) n a ， 和( x (2v )( n ) p a ， 分别 收 敛 于 循环 序列“ 和几 它 们 都 是 二 值 的 ， 并 且, o ) 一 r , 0 1 ,) 一 。 。 山上述命题可知，第 i 类根有无穷多个，但其结构是清楚的;第 i i 类根的 结构也己经有了完整的结果。本文将在以上结论基础上，研究并导出循环序列 的结构，日 _ 此时第 n类根的结构将成为其一个特殊情形。 二 、循环序列的基本性质 由 卜 一 节的命题 3至命题 6 可知，为了研究中值滤波的第 1 1 类根与循环序 列，我们只需研究由下面定义的类 9 2 . 定义1 s 2 表示满足下面两个条件的数列x 全体: ( 0 i)对一切整数n， x ( n ) 取1 或 一 i; ( 。 : )x 中 任何长度为k + l 的段落不为常数。 以下为了叙述方便，我们所指的循环序列均指稍为广义的循环序列，即既 包括循环序列，又包括第1 1 类根 ( 此时第1 1 类根可视为特殊的一次循环的循环 序列，当然也是二次循环的)。 定义2 设 x ( n ) 为实数列， 若对某个n 有x ( n ) : - x ( n + l ) ，则n 和n + l 分别 称为x 的 左跳点和右跳点，并把( n , n + l ) 称为跳点对。 定理1 设x : s 2 ， 则x 有无穷多个左、 右跳点， 若用认从z 和伙 j , , + 1 。 :表 示x 的左、右跳点全体， 其中j s j i ，则对任何: ， ( i ) 蕊l , 且x i , , 1 .,1 是常数段; ( i i ) x ( i , p - x ( i, + i ) , x ( i, ) = x ( i , , ) ; ( i i i ) x ij, 单调; ( i v ) 0 拜 i , 一 i , k - 1 。 证: ( i ) , ( i i ) 和( i i i ) 都是+分明显的， 至于( i v ) ，由 于x 伙j 、 为常数段，再由 类d 2 的定义可知该段的长度小于k + l ， 即大 戈 0 ，从而引理成立。 当x ( n ) = 一 1 时可类似地来证。 证毕。 定 理2 设x 。 。 ， (js， 尔 1 ) 是x 的 一个跳点 对， 其中i ., + , - 1 :+ 1 ， 则为使( m f k ) 2 对x ( l .,) 和x ( i. ) 都不 变，即x (z 呱) = x ( o , x z ( i. ) 一x ( i , j ， 充分必要条件是f 面 二式同时成立: f x (0 (i,.- k ) 一 x (i,) l 2 : ) 以- k , i , + l + k x 0 ( i, + i+ k ) = x ( i ,. i) 二0 证: 必要性。 先设x 认 ) 月， 于是x ( i ,) = - 1 。 由 于x 12 w s ) = x v ., ) , 所以从引理i 知， a =e x 0 u .,.- k , j .,十 k 0，b 一e x o ) ,十 ， 一 k , 4 ,* ,+ k 0。 ( t ) x z ( t ,十 ， ) = x ( i 十 ) ， 这样必定有 a = b 一 1，x.,-k)=1，x ( ,+ , + k ) = 一 1。 进一步又有， 0 一 a + x )( i , ,+ k ) =e x )u , - k , ,. ,+ k 。 于是 ( 1 ) 中的3 个等式成立。当x 认 ) = - 1 时可类似地来证。 充分性。仍先设x ( / , ) = 1 ，于是x ( i, + , ) = - 1 。 此时从( 1 ) 中的3 个等式得到， e x l u ,- k , j s + k 一 1， e x l i ., 0 为 证x i i , + k , i ,.十 .十 月 单调，只需证q - l 。 用反证法， 假设q 1 ，于是 i 1 k 、 洲 t i( ,) 认， 、i,+ i+ k 从而 。 二 j p c o - k ( i i ) 。 此时由 定 理2 知， 对x 的 一 切跳点 对认， 人 十 .) ， 均有 - x (2 )认 ) = x 认 ) ，x (2 )( i 十 1) 一 x ( 4 + ,) 所以为证x 是一个循环序列 只需证对x 的一切非跳点。 ， 有x 12 ) ( u ) = x ( u ) 即可， 其中不妨设i , 0 ( 4 ) 现在分两种情况讨论。 情形1 . x ( u 十 k ) = i。 此时由 于i , + k u + k 0 再山x ( u ) = 1 及引理1 再次得到) 2 ( u ) 二 1 = x ( u ) o 证毕。 三、对称段与循环序列的进一步性质 定义5 设x e s 2 , ( x , 尸 ) 是一 个循环序列 对， u , , 十 !) 是x 的 一个跳点 对， 其中1 , + , = + 1 ， 则段落x u , - k , i , + k l 和段落x 呱- k , t ,+ , + k 合起来称为循环序列对( x , x m ) 的 对称段，记为 (x x i 0 ) ，即 ( x x ) = ( x u , - k , i., , + k ， x o u , - k , i., * ,+ k ) 其中x称为对称段(x x 0 ) 的 上半部分， x o )称为对称段(x , , x c 0 ) 的下半部分。 定理4 设x。s 2 , ( x , x ) 是一个循环序列对，则(x , x ( 1 1) 的 任何两个相邻的 对称段是相互完全确定的。 证: 为证明本定理， 我们来研究循环序列对( x ， x ( l ) 的两个相邻的对称段 ( x x ; ) = ( x u , - k , i , , ,+ k ， x 0 ) u , - k , i, . , + k )和 ( 戈 十 ， ， 戈 + ( ) 一 ( x u , - k , ?,*2+k， x o 呱十 ， - k , .,42+k) 的相互关系。 首先由定理1 ， 对任何s 有。 i ， 一 k - 1 ， 故 j _, - k j , , , - k i , + , i ., z - i ., + , + k i.1 z + k ( 9 ) 因此有下面第 一 个结论: ( p , ) i , + : 是戈中 大于i, . 】 的 最小 右跳点， i, + , 是x 中 小于 2 的 最大右跳点。 现 在令a , = x u ,- k , j ,* , - k , b , = x l 0 i.,十 ,+ k , i,+ , + k 。 易 知a ， 和b ， 长 度 相等， 此外由 ( x , x ( ) 的 左、 右跳性及 左、 右单调 性得知a 。 和b , 都 单调， 并且a ， 的 左 端点等于b ; 的右端点， a . 的 右端点等于b : 的 左端点。再从( x , x ( 0 ) 的平衡性知 e x ( 0 u , - k , j , - k - i + e x ( )u .,+ , - k , i ,+ , + k 二 0 ( 1 0 ) e x m u , 十 ! - k , + ， + 闷+ 艺 x ( i,_+ ,+ k + l , i ,+ , + k 一 0 ( 1 1 ) 但x (0 ( i ,+ , - k ) = x )( i, ,+ k ) ， 从而由 ( 1 0 ) 和 ( 1 1 ) 式 得 知a ， 中 所有 项的 和 与b ， 中 所有 项的和相等。这样我们有 ( p 2 )把x c o = x ()u , - k , i,+ ,十 k 中 的 段落x ( )u , - k , 1 , + , - k 的 先 后次 序 倒排， 然 后 平 移 到 i, + ,+ k , i,+ z + k 即 得x + ,() = x )u ,+ , - k , i, ,+ k 。 反 之， 把x , ，m 中 的 段 落x (0 i,+ ,+ k , i,+ , + k 的 先 后次 序 倒排， 然 后 平 移 到认 - k , 1 ,+ , - k 即 得x ,m . 目 前我们已 证明了 (x , ) p ) 的相邻两个对称段均能确定对方的下半部分，只 需再证它们还能确定对方的上半部分即可。 设侧， . z 和笼 1 ， ， ，=j，_ ，( ，)+ 1 ，。 2 是x ( ) 的左、 右跳点全体， 再令 -= x ( 1 ) ( 从而- - y 1 1) , 分两种情形讨论从( x , vii ) 确定x . 1 情 形i , 存 在 某p e z , 使 刀 ” 一 办 于 是今 尸 ， 一 1 。 此时 (r i, l) = 叮o , im !o ) 也 是x (， 的 跳点 对。 由 引 理2 , ( v , y ) 二 (x 0 ) , x ) 也 是 循 环 序 列 对。 再由 定 义5 , ( 耳 ， 军 1) = (x 0 ) , x ,) 是 循 环 序 列 对 (v , 少 1) ) 的 对 称 段， 从 而 完 全 类 似 (p ,) 和 ( p 2 ) 的 论 证， ( 珠 ， 刁 ，) 可 以 确 定珠!“ ， ， 若ir -2 ( p i_. 2 ， 注 意 到 y 妹 十 ,(1) - k , r,2(1)+k = x ( 1)陈尸 )- k , i, , 2( 1)+ k 在 ( p 2 ) 中 己 被 确 定 ， 所以 由 ( 珠!， 珠! ，) 可 确 定y 2( 1) ， 此 过 程 可 持 续 到 某 个q , 2 使侧1), i, 2 为 止 ， 此 时 由刀 ” ， y ,(,) , ， 称尸即 可 知x 在【 i. ,+ k , i, 2 + k 上 的 值， 即x , ， 被 (x , x ( ) 所 确定， 从 而 (x ,十 ， ， x . ,( 1) ) 被( x x ,( l) 所确定。 情 形2 ， 存 在 某p e z， 使洲 ) + k ) 都是循环序列对 ( v , ) 0 ) 一w , x ) 的对称段， 且它们是相邻的。由 定理3 知， x i,( )+ k ， i 1 ()+ k 是 单 调 的 ， x ( i, ( 0 + k ) :# x ( i, , ,()+ k ) ， 并 且e x u p m - k ， i ! )+ k 一 。 ， 其 中 x 叼l- k , i_,+ ,+ k 是 在 段 落x = x j , - k , i ,+ k 中 的 。 因 此 可 知二 i,. + k + l ,i, , ,(l+ k 是 单 调 的 ， 而由 于x ( 留+ k ) 是 属 于 段 落x的 且x ( 酬 + k ) # x ( i, ( + k ) ， 所以 能 使e x 昭- k , in 0 4 k 一 0 成 立的 段 落 x i ,+ k + l ， 仙(+ k 必 然是 唯 一 确 定 的( 由 于 (x 0 , x ) 是 循 环 序列 对 ， 所以 这 样的 解已 经 是 存 在 的 ) ， 即习， 己 被 确 定 。 此 时 若i i _ ， 则戈， 一 x / ,.+ , - k , i.,-+ z + k 已 经 被 确 定 : 若协 1c oi, 1 使， 岁 ) i, + z 为 止 此 时弋， 己 被 确 定， 从 而 试+ . ， 戈 十 . ，) 被 比， 犬 ) 所 确定。 从( 1 k , l , x , ， ()确定(x, x (的证明也可分为j .,; ， 是否为x ) 的 左跳点的两种情 形， 寸 论，证明过程完全类似。 证毕。 山上 述定理立即得到下面的 定理5 若。中的元x 是m f k 的 循环序列，则循环序列对( x , x o ) 被它的任 一对称段所完全确定。此时，若对称段的上半部分完全等于下半部分，则 x是 几 刀 ; 的第 1 1 类根。 定理 6 证 : 若。中的元x 是m f 飞 的循环序列，则x 必然是周期的 首先约定，两个长度有限或无限的数列称为可重合的，是指其中的 一个通过适当的平移能与另一个相等。 现设 以, x q ) 一 ( x u ., - k , i., ,+ k , x 0 呱- k , i ,+ k )是 循环序列对( : ， x o ) 的对称段全体，长度都是2 k 十 2 0 令a是形如( y o ， y i) = ( y o ( 1 ) , y o ( 2 ) , ， 二 ， y o ( 2 k + 2 ) ， y ,( 1 ) , y , ( 2 ) , . . . , y ,( 2 k + 2 ) ) ( 其中y ,( n ) = 1 或一 1 , i = o , 1 ) 的有限 数列对全体，则a是一个有限 集，总共有 2 2 k , 2 个元， 因此存在( y o * , y , ) e a ， 使有无穷多 个(x, v0 ) 与之重合。 从而必有p a r , 使x r, 与 x v ， x v ， 与 x 0e 可 重 合 ， 即 x ( n ) 一 x ( n + j 9 i v ) ，x ()( n ) 一 )p ( n + j 9 j , ) ，( j v - k n ir ,+ k ) ( 1 2 ) 现 在 令z o ( n ) 二 x ( n + j 4 j v ) ， z , ( n ) = x )( n + j 9 j p ) , n 。 z o 既 然z o , z . 是x , x ( ) 的 平移， 故2 o , z , ( = s 2 且 ( z o , z i ) 也是 循环序列对， 但由 ( 1 2 ) 式 知 对j v - k - n - ip + k 有x ( n ) = z o ( n ) , x )( n ) = z ,( n ) ， 从 而由 定 理4 和定 理5 知 对 一 切n 有x ( n ) 一 z p ( n ) 一 x ( n + j 4 一 x ( ( n ) 一 z , ( n ) 一 x (l)( n + j v j ,) 。 这 样x 和x (” 均 是 周期的， 几 一是它 们的 一 个 周期。 证毕。 定理7 s 2 中能成为m f k 的 循环序列的元是有限多 个。 证:由定理 6 ，任何循环序列都是周期的，所以任何一个循环序列通过 平移只能产生有限多个不同的 循环序列。这样我们只需证明以j o = k 为左跳点的 那il r 循环序列只 有有限 多个即 可。 事实上此时 这些循环序列被对称段(x . x ( , )- ( x 0 , 2 k + 1 , x 0 , 2 k + 1 ) 所唯一确定， 而这种对称段的 状态只有有限多种。 证毕。 四、循环序列的构造 现在我们来讨论循环序列的构造问题。由引理2 和定理4 、定理5 ，此问题 归结为构造循环序列对的对称段。 定 理8设s 2 中 的 元x 是m f k 的 循 环 序 列， y o , i i) 是二 的 跳点 对， 姗 一 阵 。 。 是* 在 u o - k + l , j o 上 的 右 跳 点 全 体， i，(，) 一 杯 、 。 是x (l)在 u o - k + l , j o 上 的 右 跳 点 全 体，则循环序列对( x , x ( 1) 的 对称段( x o , x c 0 ) 一 ( x u . - k , i , + k , x ( u . - k , i ,+ k ) 满足f 面 7 个条件: i) oii) o x u o - k , i , + k 和x ( 0 u o - k , i ,+ k 是取1 和一 1 的 二 值序列; x l ( j o - k ) = x ( j o ) # x ( i ,) 二 x ( )( i , + k ) ; 段落x u o - k , j o , x i , , i ,+ k , x ( )u o - k , j o 和x ( ) i i , + k 均不为常数: x )( i, + k ) 一 x ( i, ) ( - p , s 0 )， x ( i ,( ) + k ) 一 x ( d ( i 1 ( 1 )( 一 q - t -0 ); x )u . , i- + k 及x i_+ k ， i., + k ( - p - s 0 ) 都单 调1 、乍。 iiilvv) x j o , i-, + k , x , + k , i,+ i( )+ k (-q-) x-, x ( l)( i 1 o ) ， 此外， 若i i ( ” 一 i , ， 则x )( i i 1 1) = x ( i i0 + k ) 且e x o - k ， i , + k = 0 若r l o 1 l ， 则存在唯一的二值序列段x o i l + k + i , i , o l + k , 当令x ( n ) = x o ( n ) , i , + k + l - k ， i + k = 0 x 在 i )+ k , i , i+ k 上单调， 且x ( i , )+ k ) = x l q ( i l ( ) (a)(b) ( c ) o x u o - k , j o ()- k 的 先 后次 序 倒 排 后 与x io 10 + k , i ,0 + k 的 前 v 。 (i0 一+ l ) 项的取值和顺序完全相同。 反之，若j o 是任一整数，i , = j , + 1 ， 数列对( x u o - k , i .十 k , x u o - k , i , + k ) 满足条 件 ( i) 。 一 ( v ii ) o ， 则 它可以 扩 张 成一 个 循 环 序 列 对 ( x ( n ) ) _ z, ( x )( n ) ,) 。 证:先证本定理的第一部分。 其中 条 件( i ) , ( i i ) , , ( i i i 沁 ， ( i v ) 。 和 ( v i) 。 的 成立是十分明 显的。 ( i v ) 。 的 证明。 其中x () i.+ k , i,+ + k ( p s + k , i，+ , )+ k ( _ q t 一 i ) 的 单调 性 可以 从 循 环 序 列 对 ( x , x t l ) 和 份 1 ) , x ) 的 右 单 调 性 得 到 而 至 于 )x u o , i-,+ k 的 单 调 性 ， 由 于 1瓤- k i.n ， 其 中， ， 是二 的 小 于1- 。 的 最 大 右 跳 点 ， 众 声a i_石 + k y o i , ， e x u o ) - k , i ,( )+ k = 0 仍成立， 且此时有x 在 i )+ k , i ,( )+ k 上单调， x ( i , ( )+ k ) 一 x ()( ,( ) # x ( )( io 1) ( = x ( d oj 0 ) 二 x (j 0 )- k ) ) 。 此外， 有x ( io (0 + k ) 二 x ()( i ( )0， 故x ( i ( + k ) = x ( ia ( 0 - k ) a 再由 ( x ) , x ) 在住 、o )， i o ( ov _ i , ) 上的 跳性、 单调 性和平 衡性可知x u ， (1 )- k , j ( ) - k 单调， x ( j - 1 ( ) - k ) = x ( 0 ( j - ,( ) = x )q , ) = x )( i lm ) 一 x ( i , ) + k )