（运筹学与控制论专业论文）单调有向设计.pdf

摘要 三角差集在数据通信方面有很多应用，还可以用于很多编码的构造完美差 族可以看作一类最优的三角差集g e ，l i n g 与m i a o 利用差族来构造雷达阵列f 8 1 。 通过对三角差集、差族、还有雷达阵列的定义的分析，我们可以知道这三者是紧 密相关的c h u 与c o l b o u m 为构造三角差集提出了单调有向设计的概念f 4 1 。文中 指出对于区组大小超过6 的单调有向设计是不存在的我们仅仅需要探讨区组大 小为3 ，4 5 , 5 的情况对于单调有向设计的存在性问题，目前还没有任何系统的结 果。本文针对单调有向设计问题给出了区组为大小为3 的系统结果，并且开始了对 区组大小为4 的研究。主要结果如下： 1 当区组大小为3 时，我们可以得到m d d ( 秽，3 ) 存在的，必要条件是v 三0 ，1 ，4 ，9 ( r o o d1 2 ) u 4 为证明此条件是充分条件，我们需要找到所有满足此条件的设计通 过对设计基本条件的分析，当秒三1 ，4 ( r o o d1 2 ) 时，我们可以通过它与差族 的等价性找到所有的满足此条件的单调有向设计为了构造另外的m d d ， 我们需要通过直接构造一些小的设计来进行递归在进行递归构造时， 我们利用到了已有的可分组区组设计( g d d s ) 在得到所有满足必要条件 的设计之后，我们可以得到结论：区组大小为3 的单调有向设计的充要条件 是移三0 ，1 ，4 ，9 ( m o d1 2 ) 2 当区组大小为4 时，我4 j r 】- - 3 , ：z 得i e i m d d ( v ，4 ) 存在的必要条件是秒兰1 ( r o o d3 ) 。 当u 三1 ( r o o d6 ) ，m d d s 可以通过已有差族得到部分结果，区组为4 的差族 目前的结果也是不完整的当 = 4 ，1 0 时，通过分析，我们给出了它们不存 在的证明通过计算机的搜索，也找到几个小的满足移兰4 ( m o d6 ) 的设计， 但是对于递归构造还是不足的 以上就是本文的主要结果为了构造三角差集，我们需要构造更多的区组大小 为4 和5 的单调有向设计，相应的难度也大大的增加了我们需要更加有效的算法来 进行搜索。这需要我们进一步的研究和探讨 关键词：w i l s o n 基本构造；三角差集；单调有向设计 a b s tr a c t d i f f e r e n c et r i a n g l es e t sh a v em a n yi n t e r e s t i n ga p p l i c a t i o n si nd a t ac o m m u n i c a - t i o n s p e r f e c td i f f e r e n c ef a m i l yi sa no p t i m a ld i f f e r e n c et r i a n g l es e t g e ，l i n ga n d m i a oc o n s t r u c tr a d a ra r r a y sw i t hd i f f e r e n c ef a m i l y 【8 】i t se a s yt ok n o wd i f f e r e n c et r i - a n g l es e t ，r a d a ra r r a ya n dd i f f e r e n c ef a m i l ya r eh i 曲l yr e l a t e dt oe a c ho t h e ri nd e s i g n t h e o r y t h en o t i o no fm o n o t o n i cd i r e c t e dd e s i g n s ( m d d s ) w a sf i r s ti n t r o d u c e db y c h ua n dc o l b o u mi nf 4 1f o rt h ec o n s t r u c t i o no fd i f f e r e n c et r i a n g l es e t s a l t h o u g ht h e e x i s t e n c eo fd i r e c t e dd e s i g n sh a sb e e ne x t e n s i v e l ys t u d i e d 。f e wf a m i l i e so fmd d s ，a r e k n o w nc u r r e n t l y h o w e v e r w es h o u l dn o te x p e c ta n ymd dw i t hb l o c ks i z eg r e a t e r t h a n6 a ne x a m p l eo fm d d ，n o tc o n s t r u c t e df r o mar e g u l a rd i f f e r e n c et r i a n g l es e t ， w o u l db eo fg r e a ti n t e r e s t t h em a i nr e s u l ta r ea sf o l l o w s ： 1 f o rt h ec a s eo f 七= 3 ，t h en e c e s s a r yc o n d i t i o nf o rt h ee x i s t e n c eo fm d d ( v ，3 ) i st ，兰0 ，1 ，4 ，9 ( m o d1 2 ) ，口4 w en e e dt op r o v et h en e c e s s a r yc o n d i t i o n i sa l s os u 伍c i e n t f i r s t w ec a nd e r i v em d d sf r o md i f f e r e n c ef a m i l yw h e n 口三1 ，4 ( r o o d12 ) i no r d e rt of i n dt h er e m a i n i n gd e s i g n s ，w en e e df i n ds o m e s m a l ld e s i g n sw h i c ha x en e c e s s a r yf o rt h ec o n s t r u c t i o n w i t hs o m eg d d st h a t a l r e a d ye x i s t ，w ec a nf i n dt h er e m a i n i n gm d d s s o ，w ec a nc o m et ot h e c o n c l u s i o n ：a nm d d ( v ，3 ) e x i s t si fa n do n l yi f 三0 ，1 ，4 ，9 ( m o d1 2 ) 2 f o rt h ec a s eo f 七= 4 ，t h en e c e s s a r yc o n d i t i o nf o rt h ee x i s t e n c eo fm d d ( v ，4 ) i s 口三1 ( r o o d3 ) w h e nu 三1 ( r o o d6 ) ，m d d sc a nb ed e r i v e df r o md i f f e r e n c e f a m i l y ，w h i c hi ss t i l lu n s e t t l e d w h e nt ，三4 ( r o o d6 ) ，w eg i v et h ep r o o f f o rt h e n o n e x i s t e n c eo fm d d ( v ，4 ) ，口= 4 ，1 0 w ea l s of o u n ds o m es m a l lm d d ( v ，4 ) i i i w h e n 钉兰4 ( m o d6 ) ，b u ti t sn o ts u f f i c i e n te n o u g l lf o rt h e r e c u r s i v ec o n s t r u c t i o n t h ea b o v ea r et h em a i nr e s u l t so ft h i st h e s i s i no r d e rt oc o n s t r u c td i f f e r e n c et r i a n g l e s e t s ，w en e e dm o r em d d sw i t hb l o c ks i z e4a n d5 o fc o u r s e ，i tw o u l db em u c h m o r ed i f f i c u l tt of i n dt h e m w en e e dm u c hm o r ee f f i c i e n ta l g o r i t h mi ns e a r c h i n g t h a tn e e d sf u r t h e rs t u d ya n de x p l o r a t i o n k e y w o r d s ：w i l s o n sf u n d a m e n t a lc o n s t r u c t i o n ；d i f f e r e n c et r i a n g l es e t s ； m o n o - t o n i cd i r e c t e dd e s i g n i v c h a p t e r 1 i n t r o d u c t i o n 1 1d i f f e r e n c et r i a n g l es e t s t h en o t i o no fm o n o t o n i cd i r e c t e dd e s i g nw a si n t r o d u c e di n 【4 】i no r d e rt o c o n s t r u c td i f f e r e n c et r i a n g l es e t s a n ( n ，k ) - d i f f e r e n c et r i a n g l es e t , o r ( 佗，尼) 一d a s ， i sas e tx = x l ，托，) w h e r e 五= 10 j j ) ，f o r1 i na r es e t so f i n t e g e r sc a l l e db l o c k s ，s u c ht h a ta l lt h ed i f f e r e n c e sa o a o ，w i t h1 i 钆a n d0 j j tsk ，a r ea l ld i s t i n c ta n dn o n z e r o o r d e r i n gt h e e l e m e n t so fx ta n ds u b t r a c t i n g t h es m a l l e s t ，w eg e tt h e ，k ) 一d a si nn o r m a l i z e df o r m ：0 = a i o 吼1 a i k f o ra l l1 i n t h i si sad a si fa l lt h ed i f f e r e n c e s 一叼，w i t h1 i na n d 0 歹j ka r ed i s t i n c t t h ed i f f e r e n c e sa r eo f t e nd i s p l a y e di nat r i a n g u l a ra r r a y , h e n c et h en a m e t h ef o l l o w i n ge x a m p l es h o w sa ( 3 ，3 ) 一d a sa n di t sd i f f e r e n c e si n t r i a n g u l a rf o r m ： o ，1 ，6 ，1 3 o ，3 ，1 4 ，1 8 o ，2 ，1 0 ，1 9 15731】4289 61 21 41 51 01 7 1 3 ，1 8 ， 1 9 n l e tm = m ( x ) = m a x a l a u 五) b et h em a x i m u md i f f e r e n c eo ft h es c o p e i = l o fa l l ( n ，后) 一d a s t h es m a l l e s tp o s s i b l es c o p ef o ra n ( n ，k ) 一d a si sm ( n ，k ) = m i n m ( x ) i xi sa n ( n ，k ) 一d a s m ( x ) = m ( n ，七) ，t h e nx i sc a l l e do p t i m a l 1 t h em a s t e rd e g r e et h e s i so fz h e j i a n gu n i v e r s i t y a n ( n ，k ) 一d a si sr e g u l a ri fm ( x ) = 业2 c l e a r l y , a n yr e g u l a rd a s i so p t i m a l d i f f e r e n c et r i a n g l es e t sh a v ean u m b e ro fi n t e r e s t i n ga p p l i c a t i o n si nd a t ac o m m u - n i c a t i o n s f o ra l lo ft h e s ea p p l i c a t i o n s ，d i f f e r e n c et r i a n g l es e t sw i t hs m a l ls c o p e s a r ed e s i r a b l e as p e c i a lc a s et od e t e r m i n em ( 1 ，k ) w h i c hi st h ew e l lk n o w np r o b l e m g o l o m br u l e r s ，ap r o b l e mt h a ti ss t i l lf a rf r o ms e t t l e d t h e o r e m1 1 1 历t h e r ee x i s t sa n ( n ，1 ) 一d a sw i t hs c o p e 亿加ro f fn 1 t h e r e e x i s t s 帆( n ，2 ) 一d a sw i t hs c o p e3 nw h e n e v e r 佗三0 ，1 ( m o d4 ) ，a n ds c o p e3 n + 1 w h e n e v e rn 三2 ，3 ( m o d4 ) ，t h e s es c o p e sa r em i n i m u m 1 2d i f f e r e n c ef a m i l ya n dr a d a ra r r a y s d i f f e r e n c ef a m i l yi si m p o r t a n tf o rt h ec o n s t r u c t i o no fd a s i n 【4 】w e l lg i v e m o r ei n f o r m a t i o nl a t e r i t sa l s ou s e f u li nt h ec o n s t r u c t i o no fr a d a ra r r a y s 8 】 ar a d a rm a yt r a n s m i ta s e q u e n c eo ft o n e sw h o s ef r e q u e n c y “h o p s ”i nt i m e t h e e c h or e t u r n i n gt ot h er a d a rf r o ma m o v i n go b j e c ti ss h i f t e di nb o t ht i m ea n df r e q u e n c y , a c c o r d i n gt ot h er a n g ea n dv e l o c i t y , r e s p e c t i v e l y , o ft h eo b j e c t o n ed e s i g ng o a lf o r s u c har a d a ri st oc o n s t r u c ta f r e q u e n c y - h o p p i n gp a t t e r nt h a tr e s u l t si nt h em i n i m u m a m b i g u i t yi nt h er a n g ea n dv e l o c i t yo ft h eo b j e c tu p o ne v a l u a t i o no ft h er e t u r n e d s i g n a l t h ef r e q u e n c y - h o p p i n gp a t t e r nm a yb ed e s c r i b e db ya nnxmb i n a r ya r r a y ( m a t r i x ) w i t he x a c t l yo n e “1 p e rc o l u m n a “1 ”i nt h e ( t ，j ) t hp o s i t i o ni n d i c a t e s t h a tt h ei t hf r e q u e n c yt o n ei st r a n s m i t t e di nt h ej t ht i m es l o t w h e nt h ev e l o c i t y i sn o ti m p o r t a n t ，s u c ha sf o rs l o w l ym o v i n go b j e c t s ，t h er e t u r n e de c h op a t t e r nw i l l c o r r e s p o n dt oab i n a r ya r r a ys h i f t e di nt i m e ，i e ，s h i f t e dh o r i z o n t a l l y t h ed i s t a n c e o ft h eo b j e c ti sd e t e r m i n e db yt h eh o r i z o n t a ls h i f tt h a tm a x i m i z e st h ec o r r e l a t i o n b e t w e e nt h et r a n s m i t t e ds i g n a la n dr e t u r n e de c h o t h u sa g o o dd e s i g nf o rt h eb i n a r y a r r a yi so n ew h i c hh a sal a r g en u m b e ro fc o l u m n sa n dy e ti nw h i c ht h eh o r i z o n t a l a u t o c o r r e l a t i o ni sn e a r l yz e r oa te v e r ys h i f te x c e p tt h en u l l s h i f t t h em o r ec o l u m n s ab i n a r ya r r a yh a s ，t h em o r ed i f f i c u l ti tb e c o m e st os a t i s f ys u c ha l la u t o c o r r e l a t i o n r e q u i r e m e n t w e g e n e r a l i z et w od e f i n i t i o n sa sf o l l o w s 1 3 】： 2 t h em a s t e rd e g r e et h e s i so fz h e j i a n gu n i v e r s i t y d e f i n i t i o n1 2 1 ar a d a ra r r a yi sa nn mm a t r i xo fo n e sa n dz e r o s ，w i t ha s i n g l e o n ep e rc o l u m n ，s u c ht h a tt h eh o r i z o n t a la u t o c o r r e l a t i o nf u n c t i o nh a st h r e ev a l u e s ： 0 ，1 ，a n dm ( i e ，f o ra n yh o r i z o n t a ls h i f tt h es h i f t e dm a t r i xh a se i t h e rm o n e so ra t m o s ta s i n g l eo n ei nc o m m o nw i t ht h eo r i g i n a lm a t r i x ) d e f i n i t i o n1 2 2 a n n t h i so p t i m a lv a l u e b o u n d sf o r g r 矿( n ) o p t i m a lr a d a rh a st h em a x i m a ln u m b e ro fc o l u m n sf o rag i v e n i sd e n o t e db yg r ( n ) t h ep r o b l e mi st of i n du p p e ra n dl o w e r i no r d e rt os t u d yt h er a d a ra r r a y si nd e s i g nt h e o r y , g ea n dl i n g 【8 】 r e p r e s e n ta r a d a ra r r a yra1xmv e c t o ri nw h i c ht h ei t hc o m p o n e n tc o r r e s p o n d st ot h ep o s i t i o n o f1i nt h ei t hc o l u m n ，o re x p l i c i t l y ，r = ( r 0 ，r l ，r m 一1 ) ，w h e r e0 r i 一1 ，i = 0 ，1 ，m 一1 r e g a r dar a d a ra r r a ya sa nn mg r i d ，w i t ho n e “d o t ”p e rc o l u m n t h ep o s i t i o no ft h ei t hd o te q u a l st h ev a l u eo fr i s u p p o s et h a tt h ei t hd o ta n dt h e j t hd o to fr a r ei nt h es j 9 , m er o w ，i e ，r i = 巧t h e nt h e s p a c i n g o ft h ep a i r ( i ，歹) i sd e f i n e da st h ea b s o l u t ev a l u eo ft h e i rd i f f e r e n c e ，li 一歹1 a c c o r d i n gt h ed e f i n i t i o n o far a d a ra r r a y , w eh a v et h ef o l l o w i n gn e c e s s a r ya n ds u f f i c i e n tc o n d i t i o nf o ra1 m v e c t o rt ob ear a d a ra r r a y 【3 ，8 】 l e m m a1 2 3 a1 mv e c t o ru r i t he l e m e n t s # o r ei n = 0 ，1 ，一1i sar a d a r a r r a y 毡a n do n l y 畸e a c ho ft h es p a c i n g sa p p e a r sa tm o s to n c e t h er a d a ra r r a yp r o b l e mw a sf i r s ti n t r o d u c e db yg o l o m ba n dt a y l o ri n1 9 8 2 ，t h e y a l s op r o v i d e dt h ef o l l o w i n gb o u n d s 9 】 p r o p o s i t i o n1 2 4 2 l i ms u p 警3 b l o c k h u i sa n d t i e r s m a 【3 1p r o v e dt h ef o l l o w i n gp r o p o s i t i o ni n1 9 8 8 ： p r o p o s i t i o n1 2 5 而3 0 6 l i m 。，s u p 剑n 万8 0 t h ea s y m p t o t i cr e s u l tw a sf u r t h e ri m p r o v e db yz h a n ga n dt u 【1 6 i n1 9 9 4 ： p r o p o s i t i o n1 2 6 而3 0 6 l i m ，s u p 警学 t h eb e s tk n o w na s y m p t o t i cb o u n d sw e r ei m p r o v e db yh a m k i n sa n dz e g e r 1 0 】i n 1 9 9 7 ： p r o p o s i t i o n1 2 7 而2 7 6 脚s u p 警学 3 1 3t h ea p p l i c a t i o n so fd i f f e r e n c et r i a n g l es e t s d i f f e r e n c et r i a n g l es e t sh a v ean u m b e ro fd i f f e r e n ta p p l i c a t i o n s ( 1 ，k ) - d sw a s u s e db yb a b c o c kt oc o n s t r u c tar a d i o s y s t e mw i t h o u ta c e r t a i nk i n do fi n t e r m o d u l a t i o n i n t e r f e r e n c e a n o t h e ra p p l i c a t i o na r e ai si ns p a c i n go fr a d i oa n t e n n a s ，s e e 【1 1 i t s a l s oq u i t eu s e f u li nc o n s t r u c t i n gc o d e s f o re a c hj 毛w ec a nd e r i v eas e q u e n c ez ，) w h e r e 山x 口( o j = 1 ，f o r0 歹ka n d z = 0o t h e r w i s e t h e s es e q u e n c e sh a v eg o o da p e r i o d i cc o r r e l a t i o np r o p e r t i e s ： m 、个( t ) 个( 7 ) = 乙j4 j + t j = 0 s j + 1 ， 、0d r1 ， i fi = i 7a n dt = 0 a t h e r w i s e t h i si su s e f u lf o rt h ed e s i g no fm i s s i l eg u i d a n c ec o d e s 【6 】 a n ( 扎，u ，k ，a c ) o p t i c a lo r t h o g o n a lc o d e ( o o c ) ci saf a m i l yo f ( 0 , 1 ) s e q u e n c eo f l e n g t h 礼a n dw e i g h tuw h i c hs a t i s f i e st h ef o l l o w i n gt w op r o p e r t i e s ： 1 t h ea u t o c o r e l a t i o np r o p e r t y ： n 一1 兢x t 。r 儿乙兢。rs 九 t = o f o ra n yz ca n de v e r yi n t e g e r7 ，7 o ( 加d 佗) w h e r ez = z ) 竹t = 一0 1 。 2 t h ec r o s s c o r e l a t i o np r o p e r t y ： n 一1 勉y t 。r 入。l 勉。rs a c t = o f o ra n y2 7 c ，y cw i t hz ya n de v e r yi n t e g e r 丁； w h e r eod e n o t e sa d d i t i o nr o o dn i f ，k = a c = a ，t h es h o r t h a n dn o t a t i o n ( 他，“，a ) w i ub eu s e d t h e r ei sas i m p l ec o n n e c t i o nb e t w e e nad a sa n da no o c i tw a ss t a t e di nt h e f o l l o w i n gl e m m a 【5 1 4 l e m m a1 3 1 可t h e r ee x i s t sa n ( n ，k ) 一d a sw i t hs c o p em ( x ) ，t h e nt h e r ee x i s t s 口 ( 2 m ( x ) + 1 ，七+ 1 ，1 ) o o c ac a n o n i c a ls e l f - o r t h o g o n a lc o d e ( c s o c ) i sar e c u r r e n t ( o rc o n v o l u t i o n a l ) c o d e f o rw h i c hn ot w op a r i t ye q u a t i o n si n c l u d et h es a m eb i t s ac o n s t r u c t i o nb a s e do n d a sw a si n t r o d u c e db yr o b i n s o na n db e r n s t e i n 【1 4 t h ec s o cc o r r e s p o n d i n gt o t h e ( 佗，k ) 一d a sh a sg e n e r a t o rp o l y n o m i a l s 1 i n t h ec o d eg e n e r a t e di sa n ( n + 1 ，他，m ) c s o cw i t h 如i 竹= k + 2 1 4t h em a i nr e s u l t so ft h et h e s i s i nt h i st h e s i s ，f i r s t ，w eg e tt h en e c e s s a r yc o n d i t i o n sf o rt h ee x i s t e n c eo f m d d ( v ，七) ，k = 3 ，4 t h e n ，w eu s e t h ec o n s t r u c t i o nm e t h o d si nt h ec o m b i n a t o r i a l d e s i g n st op r o v et h ea b o v en e c e s s a r yc o n d i t i o n sa r ea l s os u f f i c i e n tf o rt h em d d ( v ，3 ) w ea l s od e r i v es o m er e s u l t so nt h ee x i s t e n c eo fm d d ( v ，4 ) ，a n dg i v et h en o n e x i s t e n c e o fm d d ( i o ，4 ) b a s e do nt h er e s u l to no t h e rd e s i g n t h i st h e s i si so r g a n i z e da st h ef o l l o w i n g ：i nc h a p t e r1 ，w es i m p l yi n t r o d u c et h e b a c k g r o u n do fm o n o t o n i cd i r e c t e dd e s i g n ；i nc h a p t e r2 ，w ei n t r o d u c es o m ep r d i m - i n a r yk n o w l e d g ea b o u tt h em o n o t o n i cd i r e c t e dd e s i g n ；i nc h a p t e r3 ，w ep r o v et h e e x i s t e n c eo fm d d ( v ，3 ) ；i nc h a p t e r4 ，w eg i v es o m er e s u l t so nt h em d d ( v ，4 ) ；i n t h el a s tc h a p t e r ，w es u m m a r i z et h ew h o l et h e s i sa n dg i v es o m eo u t l o o ko fm o n o t o n i c d i r e c t e dd e s i g n 5 u 俨 七伽 c h a p t e r2 p r e l i m i n a r i e s 2 1s o m eu s e f u ld e s i g n s l e tx = 2 7 0 ，x l ，z 口一1 ) b eav - s e to fp o i n t s ，a n dkap o s i t i v ei n t e g e r a t r a n s i t i v e l yo r d e r e dk - s u b s e tb = ( ，如l ，x i k _ 1 ) o fx c o n s i s t so f 坐2 型o r d e r e d p a i r so ff o r m ( x i ，x i t ) w i t h0 8 t k 一1 l e tb b eac o l l e c t i o no ft r a n s i t i v e l y o r d e r e dk - s u b s e t ( c a l l e dd i r e c t e db l o c k s ) o fx ap a i r ( x ，1 3 ) i sad i r e c t e d ( v ，k ，a ) 一 d e s i g ni fa n yo r d e r e dp a i ro fd i s t i n c tp o i n t sf r o mx i sc o n t a i n e di ne x a c t l yad i r e c t e d b l o c k s l e tt h ep o i n t so fxb el i n e a r l yo r d e r e db yx o z 1 x v 一1 ，a n db= ( x i o ，x i l ，x i ) bb ea d i r e c t e db l o c ko fx l e tp o s ( ) d e n o t et h ep o s i t i o no f 甄ji nt h eo r d e r e dv - s e t ( z 如，x i o + 1 ，一1 ，x 0 ，x l ，z 如一1 ) t h e nb i sam o n o t o n i c d i r e c t e db l o c ki fp o s ( z i o ) p o s ( x i l ) p o s ( x t k 1 ) i nt h er e a ln u m b e rs y s t e m ， t h a ti s ，i ft h ed i r e c t e db l o c kb = ( z t 0 ，戤l ，z 珏一1 ) p r e s e r v e st h eo r i g i n a l e n d t o - e n d ”l i n e a ro r d e ro fp o i n t si nx ，o rm o r ep r e c i s e l y , t h eo n l yp o s s i b l ed e r i v e dl i n e a r o r d e ro ft h ep o i n t si nt h ed i r e c t e db l o c kb = ( x i o ，z 1 ，x i 一1 ) i sx i 。 z t 。+ l x i k 一1 x i o z i l a ne x p o n e n t i a ln o t a t i o n i su s u r yu s e dt od e s c r i b et y p e s ： at y p e 夕卜船d e n o t e su io c c u r r e n c e so fg i ， 1 i5 仇 ad i r e c t e dg d d ( k ，a ) 一d g d do ft y p eti sa ( k ，2 入) 一g d do ft h es a m et y p ei n w h i c ht h eb l o c k sa r et r a n s i t i v e l yo r d e r e dk - t u p l e s ( c a l l e dd i r e c t e db l o c k s ) ，k k ， a n de a c ho r d e r e dp a i ro fp o i n t s ( z ，y ) f r o md i s t i n c tg r o u p si sc o n t a i n e di ne x a c t l y 入 d i r e c t e db l o c k s l e t9 = g o ，g ”g 铲1 ) ，a n dt h eg r o u p sa r el i n e a r l yo r d e r e db yg o g 1 g 乞一1 g o l e tb = ( x i o ，甄1 ，戤k 1 ) b ，w h e r ez t j g i j l e tp 0 8 ( x i j ) d e n o t et h ep o s i t i o no fg i fi nt h eo r d e r e du - s e t ( g 主o ，g i o + 1 ，吼_ 1 ，g 0 ，g 1 ， g 如一1 ) t h e nb i sam o n o t o n i cd i r e c t e db l o c ki f p o s ( x i o ) p o s ( x i l ) 1 9 0 8 ( x i ) i nt h er e a ln u m b e rs y s t e m ，t h a ti s ，i f ( x