Home

스크램블링에 사용된 LFSR의 피드백 다항식을 추정하기 위해서는 메시지, 확산부호, m-시퀀스가 섞여 있는 수신 신호로부터 m-시퀀스만을 추출해야 한다. m-시퀀스를 추출하기 위해서는 확산부호가 주기적으로 반복되는 성질을 이용하여 수신 신호를 shift한 후 더하는 방법을 사용한다[7]. [7]의 방법을 간단히 요약하면 다음과 같다.

우선 수신 신호의 동기가 맞았다고 가정하고 식 (3)과 같은 연산을 통해 생성되는 U를 생각하자.

식 (3)에서 U의 j(=kt+i)번째 비트 값은 S_j, S_j+1, S_j+k, S_j+k+1의 합이므로 i≠0인 경우에는 식 (2)에 따라 식 (4)와 같이 m-시퀀스의 합으로만 나타낼 수 있다.

반면, i=0인 경우에는 식 (5)와 같이 LFSR 출력 시퀀스 이외에 메시지 비트의 영향이 있는 식으로 구성된다.

여기서 p^j=pj⊕pj+1⊕pj+k⊕pj+k+1이라고 정의하면 m-시퀀스의 cycle-and-add property[12]에 의해서 p^j에 대하여 p^j=pj+α를 만족하는 α값이 존재한다. 즉, p^와 p는 동일한 피드백 다항식을 갖는 m-시퀀스이다. 따라서 U로부터 k비트마다 반복되는 1비트를 제외한 나머지 위치에서는 메시지와 확산부호가 제거된 순수한 LFSR 출력인 m-시퀀스 값을 추출 할 수 있다[7]. 또한, 순수한 m-시퀀스가 아닌 비트의 다음 비트를 기준으로 신호를 동기화하면 확산부호의 시작점과 신호를 일치시킬 수 있다.

피드백 다항식의 차수가 n인 LFSR의 출력 시퀀스, m-시퀀스는 2ⁿ-1길이의 주기를 갖게 된다. m-시퀀스에 대해서는 다양한 특성들이 연구되었는데[12][13], 본 절에서는 데시메이션에 관련한 특성을 소개한다.

d비트 데시메이션이란 시퀀스 X=x1x2x3...이 주어져 있을 때 d비트마다 1비트를 추출하여 시퀀스 X'=x1xd+1x2d+1... 을 생성하는 것을 말한다. 여기서 Xʹ을 X의 d비트 데시메이션 시퀀스라고 한다. 피드백 다항식이 n차인 LFSR의 출력 시퀀스 X에 대한 d비트 데시메이션 시퀀스 Xʹ에 대해 다음의 Theorem 1 이 성립한다[13].

Theorem 1. n차 피드백 다항식 p₁(x)를 사용하여 생성한 m-시퀀스에 대해서, d비트 데시메이션한 시퀀스를 생성할 수 있는 n차 피드백 다항식 p₂(x)가 항상 존재하며, p₂(x)는 p₁(x)와 d에 대해 유일하다. 이때, d비트 데시메이션한 시퀀스의 주기는 2n-1gcdd,2n-1이다.

예를 들어 n차 피드백 다항식으로부터 생성된 m-시퀀스 X=x1x2x3...이 주어졌다고 하자. 이때, X의 d비트 데시메이션 시퀀스 Xa=xaxd+ax2d+a...는 Theorem 1에 의해 어떤 a 에서든지 X^(a)를 생성하는 LFSR의 피드백 다항식이 항상 존재하고, 이 다항식은 a에 관계없이 동일하다는 것을 알 수 있다. 또한 이 다항식은 Theorem 1에 의해 d⊥2n-1을 만족한다면 원시 다항식이다.

LFSR 출력 시퀀스가 주어져 있을 때, 피드백 다항식을 찾는 방법에 대해서 많이 연구되어 왔으며[14][15] 가장 대표적인 알고리즘으로는 BM(Berlekamp-Massey) 알고리즘이 있다[16]. BM 알고리즘은 피드백 다항식의 차수 n에 대해 최소 2n길이의 비트열을 입력으로 받아서 다항식을 찾는 알고리즘이다. 따라서 2n길이만큼의 LFSR 출력 시퀀스를 얻을 수 있는 경우 BM 알고리즘을 사용하면 간단하게 피드백 다항식을 찾을 수 있다.

2.1절에서 제시한 방법을 통해서 스크램블링된 DSSS 신호로부터 순수한 LFSR 출력 시퀀스인 m-시퀀스를 얻을 수 있다. 이번 절에서는 m-시퀀스를 얻었을 때 2.2절에서 설명한 데시메이션 특성을 활용하여 수신 신호를 동기화하는 방법을 제안한다.

식 (3)을 이용하여 U를 생성하면 식 (4), (5)와 같이 U는 각 k비트마다 1비트는 메시지의 영향을 받은 값이고 나머지 k-1비트들은 순수한 m-시퀀스이다. 만약 신호의 동기가 맞는 경우에는 S를 통해 U를 생성하면 Uj=kt+i에 대해서 식 (5)와 같이 i = 0일 때의 비트가 메시지의 영향을 받은 비트다. 반면, 신호의 동기가 맞지 않는 경우에는 어떤 r값에 대해 i = r인 Uj=kt+i의 비트가 메시지의 영향을 받은 비트가 된다. 따라서 r을 아는 경우에는 수신 신호 S를 r만큼 left shift하게 되면 동기를 맞출 수 있다.

우선 신호에 잡음이 없는 이상적인 상황에서 신호 동기화 방법은 다음과 같다. 식 (3)을 이용하여 수신 신호 S로부터 U를 생성한 후 k비트 데시메이션을 수행하여 식 (6)을 생성할 수 있다.

여기서 a = 1,...,k 이다. a≠r인 U^(a)는 식 (4)와 (5)에 따라 m-시퀀스의 k비트 데시메이션 시퀀스가 된다. 반면에 a = r일 때의 U^(α)는 랜덤한 시퀀스의 k비트 데시메이션 시퀀스와 같게 된다. Theorem 1에 따르면 m-시퀀스의 k비트 데시메이션 시퀀스를 생성하는 LFSR의 피드백 다항식은 유일하다. 즉, a≠r인 경우에는 a값에 관계없이 U^(a)를 생성하는 LFSR의 피드백 다항식이 존재하며 이 다항식은 모두 동일하다. 반면, a = r인 경우에는 이를 만족하지 않는다. 따라서 각 a = 1,...,k에 대해 U^(a)을 BM 알고리즘에 적용하면 a = r인 경우를 제외하고는 모두 동일한 다항식을 얻을 수 있게 된다. 즉, 다른 다항식이 출력으로 나오는 값을 r라고 추정할 수 있으며, 최종적으로 수신 신호 S를 r만큼 left shift해서 동기를 맞출 수 있다.

BM 알고리즘으로 피드백 다항식을 얻기 위해서는 n차 피드백 다항식을 통해서 만들어진 LFSR 출력 시퀀스인 경우, 각 a에 대해서 최소 2n비트의 입력이 필요하다. 즉, 2nk길이의 U값이 필요하며 이를 생성하기 위해서는 (2n + 1)k + 1길이의 S값이 필요하다. 따라서 수신 신호에 잡음이 없는 상황에서 제시한 방법으로 동기화를 진행하기 위해서는 최소 (2n + 1)k + 1길이의 S가 필요하다.

한편, 수신 신호에 잡음이 있는 경우에는 a≠r이더라도 U^(a)값이 잡음의 영향으로 순수한 LFSR 출력 시퀀스 값으로만 이루어지지 않는 경우도 존재한다. BM 알고리즘의 입력 시퀀스에 오류가 있는 경우 틀린 다항식을 얻게 되는 경우가 존재하므로 위의 방법을 그대로 적용하면 잡음 상황에서는 동기화를 올바르게 하지 못하는 경우가 발생한다. 따라서 이 경우 데시메이션 시퀀스에 대한 피드백 다항식을 찾는 과정을 반복 적용한다. 여러 번의 반복 과정을 거치면 U^(a)에 대한 생성 다항식 p₂(x)를 가장 많이 찾게 되고 이를 올바른 데시메이션 시퀀스에 대한 피드백 다항식이라고 추정하여 잡음이 없는 경우와 유사한 방법으로 동기화를 진행한다. 잡음환경에서 DSSS 신호 블라인드 동기화 과정은 알고리즘 1과 같이 구성된다.

먼저 데시메이션 시퀀스 U^(a)에 대한 올바른 피드백 다항식, poly를 찾는다. 이 때 poly는 U^(a)에 대한 피드백 다항식 추정을 반복적으로 수행하여 가장 많이 추정된 다항식으로 선정한다.

각 데시메이션 시퀀스 별로 poly를 찾은 후에는 U^(a)의 피드백 다항식을 구하여 이를 poly와 비교한다. 만약 U^(a)가 메시지의 영향을 받은 위치에서 데시메이션한 스트림이라면 아무리 반복을 많이 하더라도 BM 알고리즘의 결과로 데시메이션 시퀀스에 대한 poly가 나타나지 않는다. 반면 U^(a)가 메시지의 영향을 받지 않은 위치에서 데시메이션한 스트림이라면 피드백 다항식 추정을 반복하였을 때 적어도 1번은 데시메이션 시퀀스에 대한 poly를 추정할 가능성이 크다. 따라서 k - 1개의 위치에서 데시메이션 시퀀스에 대한 올바른 다항식을 찾을 때까지 피드백 다항식 추정을 반복하여 메시지의 영향을 받은 위치를 찾는다. 그 후 메시지의 영향을 받은 위치만큼 수신 신호를 shift하여 동기화를 수행한다.

Algorithm 1의 과정을 위해 필요한 수신 신호의 최소 길이에 대해서 생각해보자. M이 N보다 큰 경우에는 4번 과정에서 필요한 S의 길이보다 8번 과정에서 필요한 S의 길이가 더 길기 때문에 8번 과정에서 필요한 S의 길이만 생각하면 된다.

M회 반복을 하는 경우 U가 처음 생성되었을 때보다 kM비트 left shift된 상황까지 반복을 진행해야한다. 가장 마지막 반복에서는 2nk길이의 U가 필요하므로 총 k(M + 2n)길이의 U가 필요하다. 이를 생성하기 위해서는 k(M + 2n +1)+1 길이의 수신 신호 S가 필요하다. 따라서 Algorithm 1을 통해서 동기화를 하기 위해서는 k(M + 2n +1)+1길이의 시퀀스가 필요하다.