32

논문 6-31-4C-3 한국통신학회논문지 '6-4 Vol.31 No.4C 짧고효과적인주파수도약수열생성 준회원김영준 *, 김대선 *, 종신회원송홍엽 * Short and Efficient Frequency Hopping Codes Young-Joon Kim*, Dae-Son Kim* Associate Members, Hong-Yeop Song* Lifelong Member 요 약 본논문에서는주파수도약시스템에사용될짧은길이의도약수열의생성법세가지를제안한다. 우선, 기존에알려져있는한개일치수열과다상멱잉여류수열의생성법에대해설명하고, 한개일치수열의변형으로얻어진생성법하나와다상멱잉여류수열을이용한방법두개를제안한다. 다상멱잉여류수열에서 최적지움위치 ' 를지운수열이제안된세가지수열들중에서가장좋은상관특성을가지고, 그다음은첫번째위치지운수열, 한개일치수열의변형수열순으로상관특성이좋음을확인한다. 또한이들세수열이심볼이균형성이우수하고쉽게구현될수있음을설명한다. Key Words : frequency hopping, Hamming correlation, balance, power residue, optimal deletion ABSTRACT In this paper we propose three methods to generate short hopping sequences for the frequency hopping system. First, we explain the one coincidence set of sequences and the polyphase power residue seqences which have been known previously, and we suggest a method by modifying the one coincidence sequence and two methods by using the power residue sequences. We verify that the optimal position deleted-power residue sequences have the best Hamming autocorrelation property and the first position deleted-power residue sequences and the modified one coincidence sequences follows with respect to Hamming autocorrelation. We also explain that these sequences have the good balance property and can be implemented with low complexity. Ⅰ. 서론주파수도약은대역확산신호전송방식에서사용되는기본적인변조방식중의하나이다 [1, 2]. 주파수도약은전파의전송도중에주파수변경을되풀이하는데이는인가되지않은간섭이나통신방해를최소화하기위해서이다. 주파수도약시스템은중심주파수를도약수열에따라변경하며이는주파수합성기를통해이루어진다. 주파수도약시스템은일반적으로도약의경향이쉽게노출되는것을방지하기위해도약주파수의 개수에비해훨씬긴길이의주기를갖는도약수열을사용한다. 그러므로이러한시스템에서주파수영역에서충돌은불가피하고, 충돌의횟수는종종해밍상관값으로측정이된다. 길이 인두개의수열 와 의해밍상관값 는다음과같이정의된다 [1, 3]. 여기서 는 와 가같으면 1, 다르면 이고, 본연구는한국과학재단특정기초연구 (R1-3--3-) 지원으로수행되었음. * 연세대학교전기전자공학과부호및정보이론연구실 ({yj.kim, ds.kim, hy.song}@coding.yonsei.ac.kr) 논문번호 :KICS6-1-29, 접수일자 :6 년 1 월 16 일, 최종논문접수일자 : 6 년 4 월 12 일 318

논문 / 짧고효과적인주파수도약수열생성 는 mod 으로계산된다. 상관값이높다는것은충돌의확률이높음을의미하므로낮은해밍상관특성을갖는도약수열을사용하는것이바람직하다 [1]. 우수한해밍상관값과더불어도약심벌의균형성 (balance) 또한도약수열의설계에서중요하게고려되는요소이다 [3]. 왜냐하면상대적으로높은빈도를갖는심벌에대응되는주파수는악의적인공격자나간섭자의공격대상이될수있기때문이다. 또하나의고려해야할중요한인자는선형복잡도이다. 선형복잡도는주어진수열을생성할수있는선형귀환쉬프트레지스터의최소단수를말하므로이값이작으면도약수열의길이가길어도짧은단수의선형귀환레지스터로재합성할수있으므로전체도약수열이쉽게노출될위험성이있어서선형복잡도는가능한크게되도록설계해야한다 [3, 4]. 다시말해, 주파수도약시스템에사용될매우긴길이의도약수열은많은개수의수열, 우수한상관특성, 심벌개수의균형성, 높은선형복잡도등의특성을필요로한다. 하지만, 주파수도약시스템은종종긴길이의도약수열뿐만아니라짧은길이의도약수열도필요로한다. 예를들어동기화혹은주파수참조점을찾기위한목적으로한개혹은적은개수의파일럿신호를필요로하는경우가있다. 이러한경우에수열의길이가짧기때문에선형복잡도는고려의대상이아니고우수한해밍자기상관특성, 심벌의균형성을만족하는수열을필요로한다. 본논문에서는이처럼짧은길이의도약수열을위한생성방법으로기존의한개일치 (one coincidence) 수열 [5] 과다상멱잉여류수열 [6] 을설명하고이를변형하여도약수열을생성하는방법을제안한다. 그리고, 이들을최대해밍자기상관, 균형성및구현성의관점에서비교한다. Ⅱ. 주요생성법들이논문전체에서 는임의의소수, 는 의한약수, 는 의한원시근으로용어를통일한다. 2.1 기존의생성법 2.1.1 한개일치수열 [5]. 한개일치수열집합 은주기가 인수열들 로구성되어있다. 여기서 는다음과같이정의된다. (1) 여기서연산 는 mod 에서계산된다. 가원시근이므로, 순환군 는곱셈군 의위수가 인부분군이다. 따라서 는 의모든원소가한번씩나타나는수열이며, 는 의원소각각을 만큼 mod 연산에서더한수열이다. 2.1.2 다상멱잉여류수열 [6] mod 연산을하였을때영이아닌정수들을 개의코셑들 ( ) 로분할하자. 여기서 는 차멱잉여류 (mod ) 집합이고, 에대해서 이다. 길이 이고 상의값을원소로갖는 진수열 은다음과같이정의된다. (2) 예제 1. 다음은길이 13인삼진수열 (, 그리고 일때 ) 의생성예제이다. 1 2 3 4 5 6 7 8 9 11 1 2 4 8 3 6 12 11 9 5 7 그러므로길이 13인삼진수열 는다음과같다. 1 2 3 4 5 6 7 8 9 11 12 1 1 2 2 2 2 1 1 2.2 제안한생성법 2.2.1 한개일치수열의변형 [ 생성법 1] 길이 인수열 은다음과같이정의하자. (2) 식 (2) 에서원시근의연속적인멱을 mod 가아닌 mod 연산만을하여얻은수열이한개일치수열이므로, 수열 는한개일치수열집 319

한국통신학회논문지 '6-4 Vol.31 No.4C 합 의 과 mod 의관계로연관되어있다. 예제 2., 그리고 일때, 길이 12 인삼진수열 은다음과같다. 1 2 3 4 5 6 7 8 9 11 1 2 4 8 3 6 12 11 9 5 7 1 2 1 2 2 2 1 1 2.2 첫번째위치지운다상멱잉여류수열 [ 생성법 2] 엄밀히말해, -진다상멱잉여류수열 는영심벌이다른심벌에비해한번더나타나므로균형성을만족하지못한다. 다시말해영심벌은 번그리고나머지심벌들은 번나타난다. 균형성을맞추기위해 번째위치의심볼영을지움으로써길이 인 진수열 을얻을수있다. 심볼영이다른위치에서도나타나지만굳이첫번째위치의영심볼을지우는것은원시근의연속적인멱의 mod 연산으로부터얻어지는다상멱잉여류수열로부터추가적인복잡도의증가없이간단히구현하기위해서이다. 예제 3. 아래는, 그리고 일때길이 12인삼진수열 의예이다. 1 2 3 4 5 6 7 8 9 11 12 1 1 2 2 2 2 1 1 2.3 최적위치지운다상멱잉여류수열 [ 생성법 3] -진수열 가비록균형성을만족하고다상멱잉여류수열로부터쉽게만들수있지만, 해밍자기상관값은다상멱잉여류수열 에비해나쁘다. 만약서로다른심벌간의개수의차이가 2보다크지않다면, 번째위치를지우는것을고집할필요가없다. 여기서길이 인 진수열 의생성방법을찾을수있다. 우선주어진다상멱잉여류수열 에서각각의위치를지움으로써얻은수열들의집합 를먼저생성하자. 그다음집합 의원소수열들의최대해밍자기상관값을구하면분명히집합 에는이들최대값들중에서최소값을주 는수열이존재한다. 이처럼최소값을주는지움위치를앞으로 최적지움위치 라하겠다. 최적지움위치를지워서얻은수열이 이다. 예제 4. 아래는, 그리고 일때길이 12인삼진수열 의예이다. 먼저집합 를생성한후각위치를지웠을때최대해밍자기상관값 을구하면다음과같다. 지움위치 1 2 3 4 5 6 7 8 9 11 12 4 4 4 4 5 6 6 6 6 5 4 4 4 최적지움위치들 : {, 1, 2, 3,, 11, 12 } 최적지움위치로 2를선택하면, 1 2 3 4 5 6 7 8 9 11 12 1 1 2 2 2 2 1 1 del 1 2 2 2 2 1 1 = 1 2 2 2 2 1 1 이다. Ⅲ. 제시된네가지수열들의비교 1974 년 A. Lempel 과 H. Geenberger 는길이가 이고사용하는심벌집합 의크기가 인수열 의최대해밍자기상관값에대한다음과같은하한을유도하였다 [7]. (3) 여기서 는불일치위상에서해밍자기상관의 max H XX ( ) 최대값, 즉, < < n 이고, 는 을 mod 연산을하여얻은음이아닌최소의잉여류값이다. 제안된세가지수열들과다상멱잉여류수열의해밍상관값을각각비교하고각각의경우에위의하한식 (3) 과도비교해보겠다. 여기서한개일치수열과의비교를하지않은것은한개일치수열은 진수열이고, 위네종류의수열은 진수열이기때문이다. 그림 1은 가 41이고 가 일때 Ⅱ장에서제안된수열들과다상멱잉여류수열의해밍자기상관값이다. 각그래프에서가로축은시간천이 를나타내며, 세로축은 에서의해밍상관 3

논문 / 짧고효과적인주파수도약수열생성 값 을나타낸다. 이경우최대해밍자기상관값의하한식 (3) 을계산하면생성법 1, 2과 3에대해서는길이 이 4, 심볼수 이므로 19.48이고, 길이 41의 진다상멱잉여류수열열들에서일치하는위치의개수를세는것이므로에대해서는 19.5이다. 해밍상관값은비교하는수정수값이고위두경우모두에대해서최대자기상관값의하한은 이다. 표 1은 과 사이에있는소수들 에대하여 이 의배수인경우 으로고정시킨후네가지수열의최대해밍자기상관값을비교한것이다. 그림 1과표 1로부터제안한세가지생성법중에서생성법 3이가장좋고, 그다음생성법 2, 생성법 1의순서로좋다. 이는최대해밍상관값이작을수록해밍자기상관값이우수하다는관점에서평가이다. 다음은심벌의균형성에대해비교해보자. 확실히생성법 1과 2은균형성을만족한다. 다상멱잉여류수열은영이아닌심벌모두가 번씩 동일하게나타나고, 영심벌이 번으로한번더나타나지만주어진길이조건 에대해서는균형성측면에서는최적의분포이다. 생성법 3에서는최적지움위치에따라심벌개수들사이의차이가 ( 균형 ), 1 또는 2이다. 만약최적지움위치의심벌이영이면심벌개수들사이의차이는 이다. 최적지움위치의심벌이영이아닌경우에는심벌개수들사이의차기가, 1 또는 2이다. 이경우심벌들은다음세가지경우로분류된다. (i) 영심벌, (ii) 최적지움위치의심벌, 그리고 (iii) 나머지 개의심벌이다. (i), (ii) 과 (iii) 에해당되는심벌의발 생빈도는각각, 그리고 이므로심벌개수간의차이는, 1 또는 2이다. 이분포가균형성면에서최적은아니지만두번째로최적이므로거의균형성있게분포한다고할수있다. Ⅳ. 구현성 HX() HX() 8 7 6 5 4 8 7 6 5 4 생성법 1 1 41 81 121 161 1 241 281 321 361 생성법 3 1 41 81 121 161 1 241 281 321 361 HX() HX() 8 7 6 5 4 8 7 6 5 4 생성법 2 1 41 81 121 161 1 241 281 321 361 다상멱잉여류수열 1 41 81 121 161 1 241 281 321 361 그림 1. =41, = 일때제안된수열들과다상멱잉여류수열의해밍자기상관분포 표 1. 사이의 이 의배수인경우 진수열들의최대상관비교 생성법1 생성법2 생성법3 의 의 의 다상멱잉여류수열 1 2 18 16 12 11 131 2 22 15 13 151 6 26 22 17 15 181 2 32 21 19 191 19 34 24 22 19 211 2 38 23 21 241 7 42 32 26 25 251 6 44 34 28 25 271 6 48 36 27 281 3 5 36 31 29 제안된네가지수열생성의용이함을보기위해그림 2를보자. 그림 2는생성법 1과다상멱잉여류수열의구현을흐름에따라순서도로만든것이다. 생성법 2과 3는다상멱잉여류수열에기반한것이므로여기서는생략하였다. 생성법 1과다상멱잉여류수열모두 와 만으로써생성하기에충분하므로매우간단히구현된다. 좀더자세히살펴보면생성법 1은매계산시 mod 연산직전의값을메모리에저장해놓고이값을 mod 하여수열원소값으로내놓은다음메모리저장된값에 를곱한값으로갱신하고이값을 mod 연산을하여다음수열값을내놓는일련의반복과정에의해쉽게구현된다. 다상멱잉여류수열은그림 2에서알수있듯이원시근 의연속적인멱을계산해나가면서각원소가어느코셑에속하는지분류하는과정 mod 이있으므로어느코셑에속하는지저장할목적혹은 이증가하는순서로 을재배치하기위해메모리가더필요하다는차이가있다. 물론다상멱잉여류수열과생성법 2, 3에서집합 의원소들에대한정보가있다면구현이더욱간단해짐은자명하다. 생성법 3에서는추가적으로최적지움위치에대한정보를메모리나여타저장장치에저장하고이위치를지우는과정이추가되어야하지만, 여전히구현은간단하다. 321

한국통신학회논문지 '6-4 Vol.31 No.4C n a(n) 1 set t() as 1 n k 1 t(k) 1 n n+1 n n+1 a(n) a(n-1) μ k k μ k k mod p a(n) a(n) mod q t(k) n mod q No n = p-1? No n = p-2? Yes Yes End End [ 생성법 1] [ 다상멱잉여류수열 ] 그림 2. 생성법 1 과다상멱잉여류수열의생성흐름도 Ⅴ. 결론본논문에서는주파수도약시스템에사용될수열중에특히짧은길이의도약수열의세가지생성방법을제안하였다. 생성법 1은 상의원시근 의연속적인멱을 mod 연산을함으로써얻어지는수열로균형성을만족한다. 생성법 2, 3은다상멱잉여류수열에기반을둔수열들이다. 생성법 2 은다상멱잉여류수열에서첫번째위치를지움으로써얻어지는수열, 생성법 3은해밍상관특성관점에서최적지움위치를지워서얻어지는수열이다. 생성법 2 수열은균형성을만족하고, 생성법 3 수열은준최적의균형성을갖는다. 최대해밍자기상관이작을수록우수하다는관점에서생성법 3이가장좋고, 그다음으로생성법 2 그리고생성법 1이좋다. 이들생성법들이 와 만으로간단히구현될수있음을확인하였다. [4] J. L. Massey, Shift-Register Synthesis and BCH Decoding, IEEE Trans. Inform. Theory, Vol. IT-15, No. 1, January 1969. [5] A. A. Shaar and P. A. Davies, A survey of one-coincidence sequences for frequencyhopped spread-spectrum systems, IEE Proceedings, Vol. 131, Pt. F, No. 7, December 1984. [6] V. M. Sidelnikov, Some k-valued pseudo-random and nearly equidistant codes, Probl. Pered. Inform., vol. 5, no. 1, pp. 16-22, 1969. [7] A. Lempel and H. Greenberger, Families of Sequences with Optimal Hamming Correlation Properties, IEEE Trans. Inform. Theory, Vol. IT-, No. 1, January 1974. 참고문헌 [1] M. K. Simon, J. K. Omura, R. A. Scholtz and B. K. Levitt, Spread Spectrum Communications Handbook, revised ed. McGraw- Hill, Inc., 1994. [2] R. L. Peterson, R. E. Ziemer and D. E. Borth, Introduction to Spread Spectrum Communications, Prentice Hall, 1995. [3] V. S. Pless and W. C. Huffman, Handbook of Coding Theory, North Holland, Elservier, 1998. 김영준 (Young-Joon Kim) 준회원 2년 2월연세대학교전자공학과졸업 ( 공학사 ) 4년 2월연세대학교대학원전기전자공학과졸업 ( 공학석사 ) 4년 3월 ~ 현재연세대학교대학원전기전자공학과박사과정 < 관심분야 > Design of Set of PN Sequences, Application of PN Sequences to Spread Spectrum and Crypto Systems 322

논문 / 짧고효과적인주파수도약수열생성 김대선 (Dae-Son Kim) 준회원 1년 2월건국대학교전자공학과졸업 ( 공학사 ) 3년 2월연세대학교대학원전기전자공학과졸업 ( 공학석사 ) 6년 ~ 현재연세대학교대학원전기전자공학과박사과정 < 관심분야 > Error Correcting Codes, Turbo code, LDPC, MC-CDMA, Spread Spectrum Communication Systems 송홍엽 (Hong-Yeop Song) 종신회원 1984년 2월연세대학교전자공학과졸업 ( 공학사 ) 1986년 5월 USC 대학원전자공학과졸업 ( 공학석사 ) 1991년 12월 USC 대학원전자공학과졸업 ( 공학박사 ) 1992년 ~1993년 Post Doc., USC 전자공학과 1994년 ~1995년 8월 Qualcomm Inc., 선임연구원 2년 3월 ~3년 2월 University of Waterloo, Canada, 방문연구교수 1995년 9월 ~ 현재연세대학교전기전자공학부교수 < 관심분야 > PN Sequences, Error Correcting Codes, Spread Spectrum Communication Systems, Steam Cipher Systems 323