통신및부호이론 의사랜덤수열과정보통신 표준 + 오픈소스개념을활용하여최고의사물인터넷플랫폼에도전한다 송민규, 김정현, 송홍엽 연세대학교 Ⅰ. 랜덤수열과의사랜덤수열 만드는방법은매우간단하고단순하며일정한연산법칙을사용하지만, 그결과는랜덤한것처럼보이는비트스트림을의사랜덤수열이라부른다. 수학에서, 일련의숫자들이연속적으로나열된형태를 수열 이라고부른다. 하나의수열내에서나타나는서로다른숫자들의개수는무한할수도있고, 유한할수도있다. 전자의경우자연현상을설명할때많이사용하는피보나치수열이, 후자의경우는유한한길이의비트스트림이좋은예이다. 0과 1, 두개의숫자 ( 또는두개의문자 ) 로이루어진수열을 2진수열 이라한다. 또한, 이러한수열중에서정해진길이의하나의패턴이지속적으로반복되는구조를갖는수열을일컬어 주기적수열 이라한다. 정보통신의다양한분야에서특정길이의 2진수열혹은비트스트림이사용된다. 물론, 비트스트림에요구되는특성은사용목적만큼이나다양하다. 이중에서가장흔하게요구되는특성은랜덤특성이다. 이는다음항이 0인지혹은 1인지가확률적으로결정될뿐, 예측이불가능함을뜻한다. 가장완벽한랜덤특성은동전던지기시행을연속적으로반복하여얻어질수있다. 앞면 (0) 과뒷면 (1) 이나올확률이각각 1/2이므로다음항이무엇일지는확률로정의될뿐, 결정적이지않다는특성이있다. 그렇다면과연컴퓨터는어떻게동전던지기와같은랜덤한시행을 쉽게 답습할수있을까? 또하나의중요한둘째요구사항은일반적으로하나의랜덤비트스트림이한번사용된후에버려지는것이아니라정확히동일한랜덤비트스트림을다시발생시켜서재사용해야한다는것이다. 통신시스템의송 / 수신기, 암호시스템의암 / 복호화기가이를요구하는좋은예이다. 두번째요구사항을위해서는, 컴퓨터가매우간단한연산을반복함으로써일정길이의비트스트림을만들어내는것이이상적이다. 또한그결과로얻어진비트스트림이동전던지기의결과와구분이어렵다면, 첫번째요구사항을만족시키기충분할것이다. 이러한랜덤비트스트림을 의사랜덤 수열이라부른다. 즉, 만드는방법은매우간단하고단순하며일정한연산법칙을사용하지만, 그결과는랜덤한혹은랜덤한것처럼보이는비트스트림인것이다. 이를또다른표현으로말하자면, 생성법을모른다면랜덤하게보이지만, 생성법을안다면전혀랜덤하지않다 27 그림 1. 다양한 2 진수열의예 본자료는정보통신분야의전문기술을누구나쉽게이해할수있도록풀어쓴지상강의로서, 한국통신학회에서발간하여무료로배포하는자료입니다
그림 2. 2 진덧셈과곱셈연산 28 는뜻이다. 또한, 매우간단하고단순한연산법칙을사용하므로두번째요구사항인재생산이쉽게가능해진다. 본논문에서는의사랜덤수열을만드는다양한방법들중에서도현실적으로가장많이사용되는 선형궤환시프트레지스터 (Linear feedback shift register, LFSR) 에대해다룬다. 전개상의편의를위해, 본문에서다루는수열은 2진수열로제한한다. < 그림 2> 는 0과 1 두개의원소로이루어진집합에서의덧셈과곱셈을나타내고있다. < 그림 2> 가설명하는덧셈과곱셈은 2진수열의생성과분석에사용되는기본적인연산법칙이므로매우중요하다. 2진선형궤환시프트레지스터수열에대한설명에앞서, Ⅱ장에서의사랜덤수열이정보통신시스템에서사용되는몇가지예를소개한다. Ⅲ장에서는정보통신시스템에서널리사용되는선형궤환시프트레지스터를이용한의사랜덤수열의생성에대해이야기한다. Ⅳ장에서선형궤환시프트레지스터수열의기본이되는 m-수열 (Maximal length linear feedback shift register sequence, m-sequence) 을소개하고, m-수열의몇가지랜덤특성에대해이야기하며글을마무리한다. 의사랜덤수열을만드는다양한방법들중가장많이사용되는선형궤환시스트레지스터 (LFSR) 에대해다룬다. II. 의사랜덤수열의응용 의사랜덤수열의생성에대해이야기하기전에, 정보통신시스템에서의사랜덤수열이사용되는예를통하여의사랜덤수열의중요성을알아보자. 의사랜덤수열을직접적으로이용하는대표적인정보통신기술로, 정보보호시스템과통신시스템이있다. 또한, 의사랜덤수열은오류정정기술의한분야인오류정정부호와도밀접한연관이있다. 1. 정보보호시스템스트림암호는의사랜덤수열을이용하는대표적인정보보호기법이다 [4]. 스트림암호는 그림 3. 스트림암호의일반적인구성 정보와통신열린강좌
< 그림 3> 과같이, 다수의선형궤환시프트레지스터들의출력을가지고정해진 ( 비선형 ) 함수연산을수행한후, 이결과를메시지비트와 2진덧셈연산을수행함으로써메시지비트스트림을암호화한다. 사용된선형궤환시프트레지스터들의궤환함수와이들을결합하는비선형함수가공개되어도, 초기값에해당하는비밀키를아는적절한사용자만이, 암호화과정에서메시지비트스트림과더해진수열을다시생성하여메시지비트스트림을얻을수있다. 이러한선형궤환시프트레지스터수열사용은선형궤환시프트레지스터수열이랜덤수열과유사한특성을갖는다는점에기반한다. 비선형함수의결합은암호키수열 (keystream) 의암호학적강도를보강한다. 2. 통신시스템 그림 4. 길이 7 인 m- 수열을이용한송수신기의동기화 코드분할다중접속 (CDMA) 에서는상관도가낮은다수의의사랜덤수열을각사용자에게할당하여동시에송수신을가능하게한다. 통신시스템에서의사랜덤수열을사용하는방법은정보보호시스템과는조금다르다. 통신시스템에서는의사랜덤수열의상관특성을주로이용한다. < 그림 4> 는통신시스템에서의사랜덤수열을이용하는하나의예이다. 송신기가사각형펄스 (Rectangular pulse) 를이용하여주기가 7인의사랜덤수열 0011101을반복적으로전송하는시스템을가정해보자. 본예에서사용한의사랜덤수열은 m-수열로, 후에 Ⅳ장에서자세히다루어진다. 전송을위해서송신기는비트 0을 +A, 비트 1을 A의전압을갖는사각형펄스로변환한다. < 그림 4 > 는사각형펄스로변환된송신신호이다. 수신기에서는송신기가전송한신호 0011101을사각형펄스로변화한 기준신호 (< 그림 4 > 참고 ) 의시작시간을바꿔가며상관도를측정한다. 측정된상관도는 m-수열의자기상관특성에따라 < 그림 4 > 과같이나타나고, 송신기가전송한 m-수열 0011101과기준신호의시작시간이정확히일치할때, 상관값이최대가된다. 따라서, 수신기는상관값이최대가되는지점, 즉첨점 (Peak) 를확인하여수신한신호에서 m-수열이시작되는시간을알수있다. 이처럼, 서로약속된신호를송수신함으로써송수신기간의시간동기를일치시킬수있는데, 이때사용되는신호를파일럿신호 (Pilot Signal) 라한다. < 그림 4> 는파일럿신호 0011101을사용한예이다. 파일럿신호는시간동기를맞추는작업외에도, 무선전송채널의상태를추정하는등의다양한용도로사용된다. 중화권의지상방송표준인 DTMB(Digital Terrestrial Multimedia Broadcast) 는주기가 127 인 m-수열을파일럿신호로채택하고있다. 코드분할다중접속 (Code division multiple access, CDMA) 는의사랜덤수열을이용하는통신시스템의또다른좋은예이다 [3][4]. 상호간의상관도가낮은다수의의사랜덤수열을각사용자에게할당하고, 이를이용하여동시에다수가입자의송수신을가능케하는이기법은다양한통신시스템에서사용되고있다. 일상생활에서위치기반통신을위한차량용네비게이션은 GPS(Global positioning system) 신호를사용하는데바로이신호는긴길이와짧은길이의 m-수열을사용한다. 또한, 군통신에 29
서는주파수도약통신시스템이주로사용되는데, 이때주파수도약순서를결정하는비2진수열생성에도 LFSR이유용하게사용된다. 3. 오류정정부호와의관계 마지막으로, 의사랜덤수열은디지털통신시스템의오류를제어하기위한기술인 오류정정부호 와도밀접한관련이있다. 예를들어, 이전절에서설명한통신시스템예에서파일럿신호로사용된 0011101은의사랜덤수열임과동시에, 가장기본적인오류정정부호로알려져있는그림 5. [7,4,3] 해밍부호길이 7의해밍부호 (Hamming code) 의부호어이기도하다. 구체적으로길이 7인해밍부호는 0011101와이것의모든순환부호, 1111111과의합인 1100010과이것의모든순환부호로이루어져있다. < 그림 5> 는 16개의 [7,4,3] 해밍부호어전체를표시한다. 일반적으로 m-수열은항상같은길이의해밍부호의부호어 (Codeword) 이다. 더나아가, 모든주기가있는 2진수열은오류정정부호의한종류인순환부호 (Cyclic Code) 의부호어가된다. 특히, m-수열이부호어로사용되면자기상관값이우수하다는특성으로인해부호어들의최소거리를최대화시키는데유용하다. 더자세한내용은 [5] 를참고하기바란다. 모든주기가있는 2 진수열은오류정정부호의한종류인순환부호의부호어가된다. 30 Ⅲ. 선형궤환시프트레지스터수열 Ⅱ장에서알아본바와같이, 의사랜덤수열은여러정보통신시스템에성공적으로적용되어다양한역할을수행하고있다. 본장에서는여러가지많은방법중에서선형궤환시프트레지스터수열에대해알아보고자한다. 매인가된클럭 (Clock) 마다기존의값을출력하고새로운값을입력받는다수의메모리를선입선처리 (FIFO, First Input First Output) 형태로구성한디지털논리회로의기본적인요소를시프트레지스터라한다. < 그림 6> 과같이시프트레지스터의각메모리가가지는값으로선형궤환함수의값을계산하고, 이를시프트레지스터의입력에되먹임 ( 궤환 ) 함으로써선형궤환시 그림 6. 선형궤환시프트레지스터의구조 정보와통신열린강좌
선형궤환시프트레지스터에서궤환값을계산하기위해서 n 개의메모리가배열되어사용되면단수가 n 이라고한다. 프트레지스터를구성한다. < 그림 6> 에나타난선형궤환시프트레지스터는궤환값을계산하기위해서연속적으로배열된개의메모리가사용되기에, 보통단선형궤환시프트레지스터라불린다. < 그림 6> 에서왼쪽끝에위치한메모리의출력을선형궤환시프트레지스터의출력이라하고, 오른쪽끝에있는 b를선형궤환시프트레지스터의입력이다한다. 이때선형궤환시프트레지스터는항상하나의출력이존재하나, 입력은존재하지않을수있다. 입력이존재하지않으면동차 (Homogeneous) 라고부르며, 의사랜덤수열을생성하그림 7. 진리표와상태천이도를이용한 3단 LFSR의해석는방법으로는동차 LFSR이주로사용되므로, 앞으로의전개에서등장하는선형궤환시프트레지스터는동차로제한한다. < 그림 7 > 에나타난 3단선형궤환시프트레지스터를이용하여선형궤환시프트레지스터의동작에대해자세히알아보자. 선형궤환시프트레지스터가동작을시작한이래로번째클럭이인가되었을때, < 그림 7 > 의 3단선형궤환시프트레지스터에서각각의메모리가보유하는값들을와같이표현할수있다. 이를선형궤환시프트레지스터의상태라한다. 자명하게도, < 그림 7 > 의 2진선형궤환시프트레지스터는개의서로다른상태를가질수있다. < 그림 6> 과비교하면, 그림 7 에서이기때 문에, 번째클럭에서선형궤환시프트레지스터는 (1) 의궤환함수연산을통하여궤환값을계산하고, 이궤환값을이용해서선형궤환시프트레지스터가의상태로바뀐다. 자명하게도, 가 0일때, 즉동작후한번도클럭이인가되지않았을때에도, 각각의메모리들은일정한값을가져야한다. 이값을초기값 (Seed) 라한다. 따라서, 단하나의동차선형궤환시프트레지스터의출력수열은다음의값들로부터결정된다. 1 선형궤환함수 2 초기값식 (1) 의궤환함수로부터출력수열이다음을만족함을알수있다. 31 위의수열이만족하는관계를선형점화식이라고부르며, 이수열의일반항을표현하는핵심은이점화식의특성다항식 (Characteristic polynomial) 이다. (2) 이를또한최소차연결다항식 (Minimum Degree Connection polynomial) 이라고도한다. 선형궤환시프트레지스터역시디지털논리회로이기에, 진리표와상태천이도를이용하여그동작을예측할수있다. < 그림 7> 은예시로주어진 3단선형궤환시프트레지스터의진리표와
상태천이도를이용한해석을보여주고있다. < 그림 7 > 를통해서알수있는선형궤환시프트레지스터의특성이있다. 1 모든상태들은오직하나의이전상태와이후상태를갖는다. 2 상태는항상스스로를이전 / 이후상태로갖는다. 이를통해서, 선형궤환시프트레지스터수열은주기적수열이고, 더나아가그주기는을제외한모든상태의개수보다작거나같다는사실을유추할수있다. < 그림 7 > 의 3단선형궤환시프트레지스터의경우, 상태의변화는일정한주기를갖고있으며, 이아닌모든초기값에대해변화주기내에서을제외한모든상태가정확히한번씩나타난다. 선형궤환시프트레지스터의출력은왼쪽에있는상태값과같기에, 결과적으로 < 그림 7 > 의선형궤환시프트레지스터는주기가 7인수열을생성한다. 이는 3단선형궤환시프트레지스터수열이가질수있는최대주기이다. 일반적으로단수가일때, 2진선형궤환시프트레지스터수열이가질수있는최대주기는이되며, 이러한최대주기를가지는출력수열을 m-수열이라정의한다. 단수가 n 일때, 2 진선형궤환시프트레지스터수열이가질수있는최대주기인 2 n -1 을가지는출력수열을 m- 수열이라고한다. Ⅳ. m- 수열의몇가지랜덤특성 32 선형궤환시프트레지스터수열중에서, 주어진단수에대해생성가능한최대주기의수열을일컬어 m-수열이라고정의했다. 주기인 m-수열은최대주기를갖는다는특성외에도몇가지상당히중요한랜덤특성을갖는다. 이러한연유로 m-수열은의사랜덤수열이며다양한분야에서널리사용되고있다. 본장에서는주기가인 2진 m-수열이갖는몇가지랜덤특성에대해이야기하고자한다. m-수열의특성에대한보다자세한정보는 [3] 을참고하기바란다. 1. 균형특성 (Balanced property) 균형특성은한주기내부에 0과 1의개수가최대한균형을맞춘다는특성이다. 주기가홀수이므로그차이가 1일때최대한균형이맞는다. 주기가인 2진 m-수열에서 0은번나타나며, 1은번나타난다. 이를 m-수열의균형특성이라부른다. 2. 연속마디분포특성 (Run property) -연속마디(Run) 란, 하나의문자가연속적으로번나타나고, 그양쪽끝에다른문자가위치하는것을의미한다. 예를들어 01110 은 1의 3-연속마디이다. m-수열의연속마디분포특성은짧은길이의연속마디가보다긴길이의연속마디보다자주나타나고, 1의연속마디개수와 0의연속마디개수가같음을의미한다. m-수열에서각연속마디들이나타날확률은, 2진랜덤수열에서같은연속마디들이나타날확률과매우유사하다. 3. 이상적자기상관특성주기가인임의의 2진수열에대해, 정규화된주기적자기상관함수를 (3) 정보와통신열린강좌
와같이정의하자. 여기서, 는임의의정수이다. 위의수식계산에서, 산한다. 주기 을갖는 m- 수열의자기상관함수는 는모듈로 - 로연 (4) 이다. 이는주기가홀수인 2진수열이가질수있는최적의자기상관이다. 참고로, 길이인 2 진랜덤수열이갖는정규화된주기적자기상관의평균값은일때항상 0이다. m-수열은주기가인모든 2진수열중에서자기상관특성이 2진랜덤수열과가장유사한수열이다. 이밖에도, m-수열은스팬특성 (Span property) 과순환-덧셈특성 (Cycle-and-add property) 같은다양한랜덤특성을갖는다 [3]. Acknowledgement 이논문은 2015 년도정부 ( 교육부 ) 의재원으로한국연구재단의지원을받아수행된기초연구사 업임 (No.2013R1A1A2062061). 참고문헌 [1] S. W. Golomb, Digital Communications with Space Applications, Prentice-Hall, 1964. [2] M. K. Simon, J. K. Omura, R. A. Scholtz, and B. K. Levitt, Spread Spectrum Communications Handbook, McGraw-Hill, 1994. [3] S. W. Golomb, Shift Register Sequences, Aegean Park Press, 1982. [4] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996. [5] 양경철, 오류제어기술, 정보와통신열린강좌, 33권, 6호, pp. 18-26, 2016년 6월. 33