논문 07-32-3-05 한국통신학회논문지 07-3 Vol. 32 No. 3 유연한 LCZ와집합크기를갖는새로운이진 LCZ 수열집합의생성 준회원김영식 *, 장지웅 *, 종신회원노종선 **, 정하봉 *** New Constructions of Binary LCZ Sequence Sets With Flexible LCZ and Set Size Young-Sik Kim*, Ji-Woong Jang* Jong-Seon No*, Ha-Bong Chung** Associate Members, Lifelong Members 요 약 이논문에서는파라미터 를갖는새로운낮은상관구역수열을생성한다. 이방식에서는자유롭게낮은상관구간의길이 을선택할수있으며, 이에따라서집합의크기 이결정이된다. 그리고이생성방식을사용하게되면선택된낮은상관구간의길이 과집합의크기 이 Tang, Fan, 그리고 Matsufuji 한계를기준으로최적에가까운집합을생성할수가있다. Key Words : Binary sequences, Flexible low correlation zone, Low correlation zone, PN sequences, QS-CDMA system ABSTRACT In this paper, we construct new LCZ sequence sets with parameters. In this scheme, we can relatively freely choose the LCZ length and the resulting LCZ sequence set has the size, which is nearly optimal with respect to Tang, Fan, and Matsufuji bound. Ⅰ. 서론부호분할다중접속 (code division multiple access) 시스템에서는많은사용자들이 Gold 수열군과같은좋은상관특성을갖는의사불규칙수열을사용해서무선자원을공유할수있다. 하나의 Gold 수열집합은주어진집합의크기와주기에대해서이론적인하한을만족하는최대의상관값을갖는다는의미에서 Sidel'nikov 한계에대해서최적인수열이다 [1]. 이하한은대략수열의주기의 2배 의제곱근과같다. 그래서수열군이최적이라고하더라도자기상관과상호상관값은상대적으로큰값을갖게된다. 그래서최적의수열군을사용한다고하더라도상당한양의다중접속간섭이생길수있다. Gaudenzi, Elia, 그리고 Vilola는 [2] 준동기부호분할다중접속시스템 (QS-CDMA) 을제안하였다. 이시스템에서는서로다른사용자간의수칩이내의시간지연이허용되고이것은무선통신시스템을설계하는데더큰유연성을제공해준다. 본연구는교육인적자원부, 산업자원부, 노동부의출연금으로수행한최우수실험실지원사업과정보통신부의출연금으로수행하고있는과제의연구결과입니다. * 삼성전자 (kingsi@ccl.snu.ac.kr, stasera@ccl.snu.ac.kr), ** 서울대학교전기 컴퓨터공학부및뉴미디어통신공동연구소 (jsno@snu.ac.kr) *** 홍익대학교전자전기공학부 (habchung@hongik.ac.kr) 논문번호 :KICS2006-10-417, 접수일자 :2006 년 10 월 11 일, 최종논문접수일자 :2007 년 2 월 6 일 226
논문 / 유연한 LCZ 와집합크기를갖는새로운이진 LCZ 수열집합의생성 QS-CDMA 시스템을위한수열집합을설계할때가장중요한문제는전체적인상관값의최대값을최소화시키는것이아니라원점근처에서낮은상관구역을 (low correlation zone) 갖는것이다. 사실구역안에서작은상관값을갖는 LCZ 수열은다른잘알려진최적의상관특성을갖는수열군보다도더좋은성능을보여주었다 [3]. 가주기가 인 개의수열의집합이라하자. 만일 에있는임의의두개의수열들사이의상관함수의크기가 offset 의구간 안에서 보다작거나같은값을갖는다면 는 LCZ 수열집합이라부른다. Long, Zhang, 그리고 Hu는 [3] Gordon-Mills-Welch (GMW) 수열을사용해서이진 LCZ 수열집합을제안하였다. 소수 에대해서 Tang과 Fan은 [4] Long의연구에서각각의수열의알파벳크기를확장해서 진 LCZ 수열을제안하였다. Kim, Jang, No, 그리고 Chung은 [5] 최적의 4진 LCZ 수열집합을제안하였다. 그리고 Jang, No, Chung, 그리고 Tang은 [6] 새로운최적의 진 LCZ 수열집합을생성하였다. 최근에 Jang, No, 그리고 Chung은 [7] unified 수열을사용해서최적의 진 LCZ 수열집합을생성하는방법을발견하였다 [8]. 또한 LCZ 수열의특수한경우라할수있는 인 ZCZ 수열에대한연구도진행되어왔다 [9],[10]. 이논문에서는파라미터 를갖는새로운낮은상관구역설계방식을제안한다. 이방식에서는자유롭게낮은상관구간의길이 을선택할수있으며, 이에따라서집합의크기 이결정이된다. 그리고선택된낮은상관구간의길이 과 은 Tang, Fan, 그리고 Matsufuji 한계를기준으로최적에가까운집합을생성할수가있다. Ⅱ. 새로운수열집합의설계 라하자. 이 modulo 인정수의집합이라하자. 즉, 이다. 가이상적인자기상관특성을갖는주기가 인이진수열이라하자. 는 인특성집합이라하자. 즉, 이다. 여기서,, 그리고 는 modulo 덧셈을의미한다. 라하자. 의균형성으로부터다음 을얻는다. (1) (2) 의 difference-balance 성질로부터 에대해서다음식이성립한다. (3) (4) (5) 중국인의나머지정리로부터동형사상 에의해 가성립한다. 여기서 는 direct product이다. 논문에서우리는 과 을같은의미로사용할것이다. 에대해서 가다음과같은 의부분집합이라하자. (6) 여기서 는 또는 이다. 그러면다음식이성립한다. (7) 가다음과같이정의되는 의특성수열이라하자. 에따라서 의두개의서로다른부분집합중하나가될수있는 처럼수열 도하나는 개의 1을갖고다른하나는 개의 1을갖는두개의서로다른수열중하나가될수있다. 이진수열 와 의상관함수 는다음과같이정의된다. 227
한국통신학회논문지 07-3 Vol. 32 No. 3 라하자. 여기서,, 그리고 는 modulo 덧셈을의미한다. 그러면다음의보조정리를얻을수있다. 보조정리 1. 상관함수 는다음과같이표현될수있다. 이제 (6) 에서의 의두개의특성수열의집합을정의하자. 정의 2. 집합 는 인 의모든특성수열, 의집합이다. 마찬가지로 인 의모든특성수열, 의집합을 라부른다. 다음정리는정의 2에서의수열들사이의상관값을보여준다. 정리 3. 에서의두개의수열 와 사이의상관함수는다음과같다. 경우 1) ⅰ) ⅱ) 경우 2), ⅰ) ⅱ) 경우 3) ⅰ) ± ± ⅱ) ± 증명 ) 이라하자. 정의 2로부터 임은자명하다. 그러면다음이성립한다. 경우 1) ; ⅰ) (8) 이경우 이고 이다. 이로부터 (1) 과 (3) 을 (8) 에대입하면 228
논문 / 유연한 LCZ 와집합크기를갖는새로운이진 LCZ 수열집합의생성 를얻을수있고, 따라서다음식이성립한다. ⅱ) 이경우마찬가지로다음식을얻는다. 따라서 경우 2) 와경우 3) 은각각, 그리고, 이고이것을 (8) 에대입하면경우 1) 과유사하게증명할수가있다. 여기서경우 1)-ⅱ) 와경우 3)-ⅱ) 는자기상관함수에해당한다. 또한 인경우에각각의상관함수에는두개의 sidelobe가존재한다. 즉, 을넘는상관값이두개있다. 그리고다른경우에는총네개의 sidelobe가존재한다. 다음의예제는생성과정을보여준다. 예제 4. 일때, 주기가 15인이진 m-수열을다음과같이얻을수있다. 그러면이 m-수열의 support 집합은다음과같이주어진다. 인경우에다음식이성립한다. 그리고 그래서특성집합 을갖는수열 는다음과같이주어진다. 여기서특성집합을보면, 이논문에서제안한 interleaving 방식은단순히 을짝수위치에그리고 를홀수위치에대입하는방식과는분명히다른것을알수있다. 마찬가지로 에대해서수열 을다음과같이얻을수있다. 와 사이의상호상관값들은다음과같이열거할수있다. 이경우에 LCZ 는 7 이고 이다. 예제에서살펴볼수있었던것처럼 에있는수열들사이의상관함수들에는다양한 LCZ가존재한다. 다음장에서 에서적절한수열들을선택함으로써 LCZ 수열집합을설계할것이다. Ⅲ. 준최적이진 LCZ 수열집합의생성 이장에서는 에서이진수열을생성하는두가지방법을제시할것이다. 그결과나온이진 LCZ 수열집합은다음의한계를기준으로거의최적에가까운집합을이룬다. 정리 5. [Tang, Fan, 그리고 Matsufuji [11]] 가파라미터 을갖는하나의 LCZ 수열집합이라하자. 그러면다음식이성립한다. 229
한국통신학회논문지 07-3 Vol. 32 No. 3 (9) 이경우 이기때문에 (9) 은다음과같이된다. 그리고 인경우다음식이성립한다. (10) 여기서 는 보다작거나같은최대의정수를의미한다. LCZ 수열집합이 (10) 의등식을만족시킬때최적이라부른다. 앞에서 sidelobe의위치가원점에대해서대칭인것을상기하라. 그래서원점으로부터 sidelobe까지의거리를볼때최대두개의서로다른거리가존재한다. 가 에서의원점으로부터가장가까운 sidelobe들의거리를나타낸다. 하자. 그러면 는다음의보조정리에서처럼결정될수있다. 보조정리 6., 에대해서 는다음과같이주어진다. (11) 증명 ) 0에서 까지의거리 이다음과같이주어진다. 마찬가지로 0에서 까지의거리 는다음과같이주어진다. 그래서 는,, 그리고 중최소값이고이것으로보조정리가증명되었다. 보조정리 6은 에서선택한수열 들의집합의 LCZ는 가 또는 중어디에서선택된것인가에는상관없이 값에만의존한다는것을말해준다. 그래서우리가이제하려는것은 index 집합 을선택해서다음과같은수열의집합 을생성하는것이고그결과좋은 LCZ 수열집합을만들어내는것이다. 보조정리 6은집합 의 LCZ가, 가홀수인경우, 가영이아닌짝수인경우, 그리고 인경우, 이렇게세가지값중최소값이된다는것을말해준다. 그래서주어진파라미터 을유지하기위해서, 집합 의 LCZ는다음과같은조건을만족시켜야한다. ⅰ) 에서의 index들은 보다크거나같아야한다. ⅱ) 두개의 index들의합은그차이가짝수가아니라면 보다작거나같아야한다. ⅲ) 그차이는 보다작은짝수가돼서는안된다. 동시에주어진 에대해서 의크기가가능하면크게만들어야한다. 이러한제약조건들로부터상당히복잡한최적화설계문제를만들수있다. 이문제에대한해는매우복잡할것이지만, 앞서말한제약조건들은 index 집합 가홀수의공차를갖는등차수열을형성하도록하는방안을암묵적으로제시해준다. 생성 1. 홀수인정수 와음이아닌정수 를선택하자. 그런후에 index 집합 를다음과같이만들자. 그러면생성 1에서의 의집합의크기 과 LCZ 이다음정리에서처럼주어지는것은쉽게알수있다. 230
논문 / 유연한 LCZ 와집합크기를갖는새로운이진 LCZ 수열집합의생성 정리 7. 와 이각각 의 로나누었을때의몫과나머지라하자. 즉, 이다. 그러면생성 1에서의 는파라미터 를갖는이진 LCZ 수열집합이되고 과 은다음과같이주어진다. 그리고만일 이면 그리고만일 이면 (12) (13) 증명 ) 보조정리 6 과 가홀수라는사실로부터 은,, 그리고 중가장작은값이된다. 여기서 와 는 에서가장큰값과두번째로큰값을의미한다. 이기때문에 가된다. 그래서다음식이성립한다. (14) (14) 으로부터 (12) 와 (13) 를얻을수있다. 만일 가짝수면보조정리 6으로부터집합 의 LCZ는다음과같이된다. 그러나만일 가홀수이면정리 7 로부터 LCZ 는 보다는크게되고이것이바로우리가공차 를홀수로한이유이다. 이제우리는다음의따름정리를쉽게얻을수있다. 생성 1을통해생성된집합의최적화정도는따름정리 8을통해서쉽게계산해볼수있다. (15) 에서의결과를 (10) 에서의한계와비교해봄으로써 (15) 에서의처음세개의부등식은최적이될수없음을쉽게볼수있다. 그러나대부분의집합은거의최적에가까운값을갖게된다. 생성 1이최적의집합을생성하지못하였기때문에자연히우리는또다른생성방식을찾아보았다. 그결과 에서의인접한 index들사이의차이가 또는 이렇게두개의서로다른값을갖도록하는다음의생성방식을찾았다. 생성 2. 과 모두에서선택된수열 의 index 는인접한 index들간의차이가번갈아가면서 와 가되는 로부터시작하는하나의수열을이루도록선택한다. 즉, 여기서 는 을만족하는최대의정수이고, 는 0 또는 1 이고 는홀수인정수이다. 집합의크기 과 LCZ 은다음정리에서처럼주어진다. 정리 9. 와 이각각 로나누었을때의몫과나머지라하자. 즉, 이다. 그러면생성 2에서의 는파라미터 를갖는이진 LCZ 수열집합이된다. 여기서 은다음과같이주어진다. 그리고 은 (16) 과같이주어진다. 증명 ) 보조정리 6과 가홀수라는사실로부터 은따름정리 8. 생성 1에서의집합의크기와 LCZ는, (15) 와같이주어진다., 그리고 중에서가장작은값이된다. 여기서 와 는각각 에서 (15) 231
한국통신학회논문지 07-3 Vol. 32 No. 3 가장큰원소와그다음으로큰원소이다. 만일 이면 이고 이다. 그래서 이다. 따라서다음식이성립한다. (17) 만일 이면 이고 이다. 그래서 이다. 따라서다음식이성립한다. (18) (18) 로부터 (16) 과 (17) 을얻을수있다. 이제우리는다음의따름정리를쉽게얻을수있다. 따름정리 10. 생성 2에서의 과 의곱은 (19) 와같이주어진다. 여기서생성 1과생성 2는같은주기내에서도서로다른 과 을갖는수열집합을만들어낼수있다. 또한따름정리 8과따름정리 10은 LCZ 수열집합을생성할때의유연성과집합의크기와집합의 LCZ 사이의상충관계를보여준다. 이러한설계방식은 LCZ 수열집합을설계할때상당한유연성을제공해줄수있는데다가많은경우최적에가까운집합을만들어내기때문에유용한방식이다. Ⅳ. 결론이논문에서는파라미터 를갖는새로운낮은상관구역설계방식을제안하였다. 기존의 LCZ 수열의생성방법에서는낮은상관구역의길이가고정되어있었지만, 이논문에서제시한생성방법을사용하면비교적자유롭게낮은상관구간의길이를선택할수있으면서도동시에거의최적에가까운수열군의크기를얻을수있다. 이러한특징은 LCZ 수열을사용하는 QS-CDMA 시스템의설계에상당량의유연성을제공해줄수가있다. 참고문헌 [1] P. V. Kumar and C.-M. Liu, On lower bounds to the maximum correlation of complex roots-of unity sequences, IEEE Trans. Inf. Theory, vol. 36, no. 3, pp. 633-640, May 1990. [2] R. De Gaudenzi, C. Elia, and R. Viola, Bandlimited quasi-synchronous communication systems, IEEE J. Sel. Areas Commun., vol. 10, no. 2, pp. 328-343, Feb. 1992. [3] B. Long, P. Zhang, and J. Hu, A generalized QS-CDMA system and the design of new spreading codes, IEEE Trans. Veh. Technol., nol. 47, no. 6, pp. 1268-1275, Nov. 1998. [4] X. H. Tang and P. Z. Fan, A class of pseudonoise sequences over GF(p) with low correlation zone, IEEE Trans. Inf. Theory, vol. 47, no. 4, pp. 1644-1649, May 2001. [5] S.-H. Kim, J.-W. Jang, J.-S. No, and H. Chung, (16) (19) 232
논문 / 유연한 LCZ 와집합크기를갖는새로운이진 LCZ 수열집합의생성 New constructions of quaternary low correlation zone sequences, IEEE Trans. Inf. Theory, vol. 51, no. 4, pp. 1469-1477, Apr. 2005. [6] J.-W. Jang, J.-S. No, H. Chung, and X. Tang, New sets of optimal p-ary low correlation zone sequences, IEEE Trans. Inf. Theory, to be published. [7] J.-W. Jang, J.-S. No, and H. Chung, A new construction of optimal p 2 -ary low correlation zone sequences using unified sequences, IEICE Trans. Fundamentals, to be published in Nov. 2006. [8] J.-S. No, p-ary unified sequences: p-ary extended d-form sequences with ideal autocorrelation property, IEEE Trans. Inf. Theory, vol. 48, no. 9, pp. 2540-2546, Sep. 2002. [9] P. Z. Fan, N. Suehiro, N. Kuroyanagi and X. M. Deng, Class of binary sequences with zero correlation zone, IEE Electron. Lett., vol. 35, no. 10, pp. 777-779, May 1999. [10] H. Torii, M. Nakamura, and N. Suehiro, A new class of zero-correlation zone sequences, IEEE Trans. Inf. Theory, vol. 50, no. 3, pp. 559-565, Mar. 2004. [11] X. H. Tang, P. Z. Fan, and S. Matsufuji, Lower bounds on correlation of spreading sequence set with low or zero correlation zone, IEE Electron. Lett., vol. 36, no. 6, pp. 551-552, Mar. 2000. 김영식 (Young-Sik Kim) 준회원 2001년 2월 : 서울대학교전기공학부공학사 2003년 2월 : 서울대학교전기컴퓨터공학부석사 2007년 2월 : 서울대학교전기컴퓨터공학부박사 2007년 3월 : 삼성전자 < 관심분야 > 시퀀스, 오류정정부호, 디지털통신 장지웅 (Ji-Woong Jang) 준회원 2000년 2월 : 서울대학교전기공학부공학사 2002년 2월 : 서울대학교전기컴퓨터공학부석사 2006년 2월 : 서울대학교전기컴퓨터공학부박사 2006년 3월 ~ 현재 : 삼성전자 < 관심분야 > 시퀀스, 오류정정부호, 디지털통신노종선 (Jong-Seon No) 종신회원 1981년 2월 : 서울대학교전자공학과공학사 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, 이동통신, 암호학정하봉 (Ha-Bong Chung) 종신회원 1981년 2월 : 서울대학교전자공학과졸업공학학사 1985년 : 미국 University of Southern California, 전기공학과공학석사 1988년 : 미국 University of Southern California, 전기공학과공학박사 1988년~1991년 : 미국뉴욕주립대전기공학과조교수 1991년~현재 : 홍익대학교전자전기공학부교수 < 관심분야 > 부호이론, 조합수학, 시퀀스설계 233