논문 07-32-10-01 한국통신학회논문지 '07-10 Vol. 32 No. 10 진 Sidel'nikov 수열의서로다른자기상관분포의개수 정회원정정수 *, 김영식 **, 종신회원노종선 *, 정하봉 *** On the Number of Distinct Autocorrelation Distributions of -ary Sidel'nikov Sequences Jung-Soo Chung*, Young-Sik Kim** Regular Members Jong-Seon No*, Ha-Bong Chung*** Lifelong Members 요 약 이논문에서는 진 Sidel'nikov 수열을생성하는원시원을바꾸었을때, 생성된수열의서로다른자기상관분포의개수를계산한다. 는소수이고 은 의약수일때 진 Sidel'nikov 수열의서로다른자기상관분포는 일때, 유일하다. 은 2보다크고어떤 ( ) 에대해서 의약수일때, 진 Sidel'nikov 수열의자기상관분포는 1개이다. 은 2보다크고어떤 ( ) 에대해서 의약수가아닐때, 서로다른자기상관분포의개수는 ( 혹은 ) 보다작거나같다. 여기서 는 를만족하는가장작은정수이다. Key Words : Autocorrelation, Autocorrelation Distributions, Cyclotomic Number, -ary Sequences, Sidel'nikov Sequences ABSTRACT In this paper, we enumerate the number of distinct autocorrelation distributions that -ary Sidel'nikov sequences can have, while we change the primitive element for generating the sequence. Let be a prime and. For, there is a unique autocorrelation distribution. If and for some,, then the autocorrelation distribution of -ary Sidel'nikov sequences is unique. If and for any,, then the autocorrelation distribution of -ary Sidel'nikov sequences is less than or equal to (or ), where is the smallest integer satisfying. Ⅰ. 서론 를만족하는소수, 양의정수, 에대해서, Sidel'nikov는주기가 인 진수열 (Sidel'nikov 수열이라부름 ) 을제안하였다 [1]. 이수 열의자기상관값은위상이맞지않을경우상한값이 4이다. 최근, Kim, Chung, No, 그리고 Chung 는위수 인원분의수 (cyclotomic number) 를이용해서 진 Sidel'nikov sequence의자기상관분포를유도하였고서로다른자기상관값의최대 본연구는교육인적자원부, 산업자원부, 노동부의출연금으로수행한최우수실험실지원사업의연구결과입니다. * 서울대학교전기 컴퓨터공학부및뉴미디어통신공동연구소 (integer@ccl.snu.ac.kr, jsno@snu.ac.kr) ** 삼성전자 (kingsi@ccl.snu.ac.kr), *** 홍익대학교전자전기공학부 (habchung@hongik.ac.kr) 논문번호 :KICS2007-06-252, 접수일자 :2007 년 6 월 9 일, 최종논문접수일자 :2007 년 10 월 2 일 929
한국통신학회논문지 '07-10 Vol. 32 No. 10 개수는 과수열의주기와관련있다고언급하였다 [4]. 이때, 최대개수는 보다작거나같다. 일반적으로주기가 인수열을생성하는데사용하는원시원 (primitive element) 이다르면각각의 진 Sidel'nikov 수열도서로다르다. 논문에서는두 진 Sidel'nikov 수열의관계를살펴보고, 서로다른원시원으로생성된 진 Sidel'nikov 수열의서로다른자기상관분포의개수를계산한다. Ⅱ. 배경지식 주기가 인 진수열 에대해서, 자기상관함수 는다음과같이정의된다. 여기서 이다. (1) Multiplicative character 은 이고 이다. [4] 에서 진 Sidel'nikov 수열의자기상관분포를위수가 인원분의수로표현하였다. 원분의수는다음과같이정의된다. 정의 2. [6] 는유한체 의원시원이라하고, 의약수이며 2보다큰 을생각하자. 원분의집합 (cyclotomic classes), 는다음과같이정의된다. 고정된양수 에대해서, 원분의수 은 를만족하는 의개수를의미한다. 논문에서사용하는원분의수의유용한성질은다음과같다. 정의 1. [1] 를소수라고하고 는유한체 (finite field) 의원시원이라고하자. 은 의약수이며 2보다큰수이다. 의공통원소를가지지않는부분집합 (disjoint subsets) 을,, 라하고다음과같이정의한다. (2) 주기가 인 진 Sidel'nikov 수열은다음과같이정의한다. (3) 보조정리 3. [6] 1) 임의의 와 에대해서 2) 3) 4) 5) for. 여기서 이다. 식 (3) 에서 진 Sidel'nikov 수열 는유한체 상에서위수 (order) 가 인 multiplicative character 와지시함수 로표현할수있다.. (4) 여기서지시함수는다음과같다. Baumert와 Mills, Ward는 에서위수 의원분의수가일정함을다음과같이보였다. 정리 4. [7] 는소수, 라하고 은 의약수라고하자. 이때 이어야한다. 그러면 상의위수가 인원분의수는항상일정하고다음과같다. 930
논문 / 진 Sidel'nikov 수열의서로다른자기상관분포의개수 여기서 Ⅲ. Sidel'nikov 수열의서로다른자기상관분포의개수 이번장에서는, 수열을생성하는원시원을변경한 진 Sidel'nikov 수열 의서로다른자기상관분포의개수를유도한다. 이때, 는주기와서로소이다. 정의 1로부터수열을생성하는원시원을바꾸면, 진 Sidel'nikov 수열은달라진다. 원시원 를 로바꾸었을때, 는식 (2) 와같이정의되는공통원소를가지지않는부분집합이고 는식 (3) 에서의수열이다. 명백하게, 이다. 다음보조정리는 와 사이의관계를보여준다. 보조정리 5. [10] 여기서 와 은서로소이다. 보조정리 5 로부터, 의자기상관함수인 는 [4] 에서유도한것처럼, 의자기상관함수인 와비슷하게구할수있다. 정리 6. [10] 의자기상관함수인 ( 이때, 라가정한다.) 는다음과같다. 여기서 은 의복소공액이다. [4],[10] 의결과를이용하면, 는다음과같다. 이고, 이거나 이짝수일때, (5) 이거나 이홀수일때, 이다. (6) 의자기상관분포는 의자기상관분포의일반화로생각할수있다. 정리 7. [10] 와 는각각 이고 를만족하는개수이다. ( 여기서 ) 그러면 진 Sidel'nikov 수열 의위상이일치하지않는자기상관분포는다음과같다. Case 1. ; 1) 2) 3) Case 2. ; 1) 2) 3) 위의정리를이용하여, 다음정리는 Sidel'nikov 수열의서로다른자기상관분포의개수를구하는것을보여준다. 정리 8. 는소수이고 은 의약수이다. 은 의 nontrivial multiplicative character 이다. 주기 과 가서로소일때, 진 Sidel'nikov 수열 의서로다른자기상관분포는다음과같다 : 931
한국통신학회논문지 '07-10 Vol. 32 No. 10 Case 1) 일때, 자기상관분포는유일하다. Case 2) 은 2보다크고어떤 ( ) 에대해서 의약수일때, 진 Sidel'nikov 수열의자기상관분포는 1개이다. Case 3) 은 2보다크고어떤 ( ) 에대해서 의약수가아닐때, 서로다른자기상관분포의개수는 가 0, 가아닌경우 보다작거나같다. 가 0또는 인경우 보다작거나같다. 여기서 는 를만족하는가장작은정수이다. 증명 ) Case 1) 인경우, 주기와서로소인임의의 는홀수이다. 는 의 -decimation이다. 주기와서로소인상수에의해 decimation된수열은같은자기상관분포를가지기때문에, 자기상관분포는유일하다. Case 2) 이경우, 은짝수이고 는 의약수 이다. 이짝수이므로 이다. 정리 4 와 7을이용하면다음을얻을수있다. (1) 인경우 (2) 인경우 ÿ (3) 이고 인경우 여기서, ± ± ± ± 위의결과로부터, 자기상관분포가 와독립적임을알수있다. 따라서자기상관분포는유일하다. Case 3) 서로다른자기상관분포의개수를계산하는것은 의조건을만족하는 의개수를계산하는것과관련이있다. 가변할때, 주어진 에대해서 값이변한다. 이변하는값을계산하면자기상관분포 표 1. 5 진 Sidel'nikov 수열의자기상관분포 의발생횟수 1330 1 1 1 1 1 1 1 1 1 1 54 55 55 54 55 54 60 49 42 54 54 55 55 54 55 54 60 49 42 54 103 102 91 96 114 109 102 114 120 109 108 110 108 115 103 97 109 114 104 96 108 110 108 115 103 97 109 114 104 96 110 108 114 104 96 109 97 108 115 103 110 108 114 104 96 109 97 108 115 103 55 54 49 42 54 60 54 55 54 55 55 54 49 42 54 60 54 55 54 55 102 103 114 120 109 102 109 91 96 114 0 470 470 472 483 490 478 478 472 483 490 932
논문 / 진 Sidel'nikov 수열의서로다른자기상관분포의개수 의개수를계산할수있다. 정리 7 에서는위수 인원분의수로 를나타낼수있다. 와 가서로소라는것은 과 가서로소라는것을의미하기때문에, 서로다른자기상관분포의개수의최대값은 을넘지않을것이다. Euler의정리는다음과같다. 은 을만족하는가장작은정수라고하면, 이다. 는 으로나눈나머지가서로다르다. 보조정리 3으로부터, 다음을알수있다. 그러므로, 자기상관분포의개수는 보다작거나같다. 보조정리 3의 2) 에서임의의 와 이 일때, 이고 이다. 그러므로, 가 0 또는 이면, 이다. 는사실로부터, 서로다른자기상관분포의개수의최대값은 이다.,, 의다양한값에대해서수치적분석을통해, Case 3) 에서, 이고 인경우는자기상관분포의개수는 1이지만, 이외의경우는자기상관분포의개수는주어진상한값과같다. 다음예제는, 진 Sidel'nikov 수열의서로다른자기상관분포의개수가 의값에따라변함을보여준다. 예제 9. 주기 을 1330( ) 이라하고 을 5 라하자. 5진 Sidel'nikov 수열의자기상관분포는표 1과같다. Ⅳ. 결론 이논문에서는 진 Sidel'nikov 수열을생성하는원시원을바꾸었을때, 생성된수열의서로다른자기상관분포의개수를계산하였다. 참고문헌 [1] V. M. Sidel nikov, Some k-valued pseudorandom sequences and nearly equidistant codes, Probl. Inf. Transm., vol. 5, no. 1, pp. 12 16, 1969. [2] A. Lempel, M. Cohn, and W. L. Eastman, A class of balanced binary sequences with optimal autocorrelation properties, IEEE Trans. Inform. Theory, vol. 23, no. 1, pp. 38 42, Jan. 1977. [3] T. Helleseth, S.-H. Kim, and J.-S. No, Linear complexity over and trace representation of Lempel-Cohn-Eastman sequences, IEEE Trans. Inform. Theory, vol. 49, no. 6, pp. 1548 1552, June 2003. [4] Y.-S. Kim, J.-S. Chung, J.-S. No, and H. Chung, On the autocorrelation distributions of Sidel nikov sequences, IEEE Trans. Inf. Theory, vol. 51, no. 9, pp. 3303 3307, Sep. 2005. [5] R. Lidl and H. Niederreiter, Finite Fields, vol. 20 of Encyclopedia of Mathematics and Its Applications Reading, MA: Addison- Wesley, 1983. [6] T. Storer, Cyclotomy and Difference Sets, Lectures in Advanced Mathematics Chicago, IL: Markham, 1967. [7] L.D. Baumert, W.H. Mills, and R.L. Ward, Uniform cyclotomy, J. Number Theory, vol. 14, pp. 67 82, 1982. [8] L. E. Dickson, Cyclotomy, higher congruences, and Waring s problem, Amer. J. Math., vol. 57, pp. 391 424, 1935. [9] R. J. McEliece and H. C. Rumsey, Euler products, cyclotomy, and coding, J. Number Theory, vol. 4, pp. 302 311, 1972. [10] Tae-Hyung Lim, Young-Sik Kim, Jung-Soo Chung, Jong-Seon No, and Habong Chung, On the relationship of Sidel nikov sequences, ISITA 2006(International Symposium on Information Theory and its Applications, Seoul, Korea), Oct. 29 - Nov. 1, 2006, pp. 934-937. 933
한국통신학회논문지 '07-10 Vol. 32 No. 10 정정수 (Jung-Soo Chung) 정회원 2003년 2월서울대학교전기공학부공학사 2003년 3월 ~ 현재서울대학교대학원전기 컴퓨터공학부석 박사통합과정 < 관심분야 > 시퀀스, 오류정정부호, 디지털통신 노종선 (Jong-Seon No) 종신회원 1981년 2월서울대학교전자공학과공학사 1984년 2월서울대학교대학원전자공학과석사 1988년 5월 University of Southern California, 전기공학과공학박사 1988년 2월 ~1990년 7월 Hughes Network Systems, Senior MTS 1990년 9월 ~1999년 7월건국대학교전자공학과부교수 1999년 8월 ~ 현재서울대학교전기컴퓨터공학부교수 < 관심분야 > 시퀀스, 시공간부호, LDPC 부호, OFDM, 이동통신, 암호학 김영식 (Young-Sik Kim) 정회원 2001년 2월서울대학교전기공학부공학사 2003년 2월서울대학교전기컴퓨터공학부석사 2007년 2월서울대학교전기컴퓨터공학부박사 2007년 3월 ~ 현재삼성전자 < 관심분야 > 시퀀스, 오류정정부호, 디지털통신 정하봉 (Ha-Bong Chung) 종신회원 1981년 2월서울대학교전자공학과졸업공학학사 1985년미국 University of Southern California, 전기공학과공학석사 1988년미국 University of Southern California, 전기공학과공학박사 1988년 ~1991년미국뉴욕주립대전기공학과조교수 1991년 ~ 현재홍익대학교전자전기공학부교수 < 관심분야 > 부호이론, 조합수학, 시퀀스설계 934