Home

C 를 (n, k) 파라미터를 갖는 GF(q) 위의 선형 부호라고 하자, 여기서 n은 부호의 길이를 나타내고, k 는 부호의 차원을 나타내며, GF(q)는 원소의 개수가 q인 Galois field 혹은 유한체(Finite Field)를 나타낸다. 선형성으로 인해서, 임의의 부호어(Codeword) c∈C 는 다음과 같이 표현할 수 있다[1].

여기서 c는 1 × n 행벡터(Row Vector)를 나타내고, m은 1 × k 행벡터를 나타내며, G 는 최대 차원(Full Rank)를 갖는 k × n 행렬을 나타낸다.

거의 모든 통신 시스템에서는 인터리버 사이즈 S 는 부호어 길이의 정수배, 즉, S = β_n가 된다 (여기서 β 는 자연수). t를 인터리빙된 데이터 스트림이라고 하고 z를 중간에 t를 캡쳐한 데이터이고 길이가 M 이라고 하자. 이 데이터를 중간에 취하게 된 사람은 인터리버 파라미터에 대한 정보가 전혀 없으므로, 처음 몇몇 심볼 t0개는 놓칠 수 있다. 일반성을 잃지 않고, 0 ≤t₀< S 라고 가정한다. 앞으로의 설명의 편의를 위해서 다음과 같은 데이터 스트림 z_d를 정의한다.

여기서 e(i)는 채널 오류를 나타낸다. 본 논문에서는 통신 채널로 오류 확률이 P_e인 이진 대칭 채널(Binary Symmetric Channel)을 가정한다. l을 예측된 인터리버 주기라고 가정하자. 이 경우, z_d를 사용해서 크기가 D ×l인 인터셉션 행렬(Interception Matrix) Z_l.d를 만들 수 있다. (여기서 D=M-dl을 나타내며 ⌊x⌋는 x를 넘지 않는 가장 큰 정수를 나타낸다.) 이때, 행렬은 캡쳐한 순서대로 왼쪽 맨위부터 오른쪽 맨아래까지 래스터 스캔(Raster Scan) 순서로 쌓는다.

C 를 (n, k) 파라미터를 갖는 GF(q) 위의 선형 부호라고 할 때, 쌍대 부호 C^⊥는 아래의 조건을 만족하는 길이가 n인 모든 벡터로 정의된다[2].

여기서 T 는 전치(Transpose)를 나타낸다. y를 쌍대 부호어(Dual Codewords)라 하자. 이 경우 다음의 식을 통해서 인터리버의 주기를 찾을 수 있다.

여기서 u 는 l ×D 행렬을 나타낸다. d + t₀ = S 이며 l = S 라고 가정해 보자. 그리고 캡쳐된 데이터에 오류가 전혀 발생하지 않았다면, u 의 해밍 무게(Hamming Weight)는 반드시 0이 될 것이다. 만약, 몇몇 오류가 발생했다면, u 의 해밍 무게의 기대값은 아래와 같이 주어진다[2].

여기서 w 는 쌍대 부호어 y의 해밍 무게를 나타낸다.

식 (1)을 통해서 부호의 몇 몇 심볼의 경우는 다른 심볼의 선형 결합으로 표현될 수 있다는 것을 알 수 있다. 따라서 만약 추정된 주기 l이 실제 주기 S의 정수배라면, 우리는 행렬 Z_l,d의 차원을 계산함으로써 이러한 선형 의존성을 확인할 수 있게 된다[5].

피봇팅을 이용한 가우스-조던 소거법(GJETP, Gauss-Jordan Elimination Through Pivoting)은 Sicot 등이 제안한 방식으로 쌍대 부호 특성과 부호어내의 선형 의존성을 동시에 이용하고 있다[8]. 이 방법은 가우스 소거법을 하는 과정에서 쌍대 부호어를 동시에 계산함으로써 기존의 방식을 확장하였다. 캡쳐된 데이터에 몇 몇 오류가 발생하였을 경우, 선형 의존인(Linear Dependence) 열이 생기지 않을 수 있다. GJETP 알고리즘은, 이 경우에 선형 의존인 행을 찾는 것이 아니라, 거의 선형 의존인(Almost Linear Dependence) 행을 찾도록 되어 있다. 이 경우, 가우스 소거법은 쌍대 부호어를 찾기 위해서 가로 방향(Horizontally)으로 연산이 이루어진다. GJETP가 끝난 후, 선형 독립인(Linearly Independent) 행들의 해밍 무게가 인터리버 주기를 찾는 일종의 메트릭(Metric) 역할을 한다.

앞에서 살펴 본 모든 알고리즘들은 기본적으로 부호어내의 선형 의존성을 이용하고 있다. 그렇기 때문에, 행렬의 차원을 계산하기 위하여 가우스 소거법을 사용할 때 항상 가로 방향으로 연산을 하고 있다. (반대로 만약 부호어가 가로 방향으로 정렬되어 있으면, 이 경우의 가우스 소거법 연산은 세로 방향으로 진행된다.) 본 논문에서는, 이러한 부호어 내의 선형 의존성뿐만 아니라, 부호어간의 선형 의존성을 이용하여 행렬의 차원을 예측하는 새로운 관점을 제시한다.

갈루아 필드 GF(q) 위의 (n, k) 선형 부호는 전체가 n -차원인 벡터 공간의 k -차원의 부분공간(Subspace)이므로, k개의 기저(Basis)가 존재한다. 그러므로 만약 k +1개의 부호어가 존재한다면, 최소한 한 개 이상의 부호어는 다른 부호어들의 선형 결합으로 표현할 수 있다. 이렇게 부호어내의 선형의존성과는 별개로 부호어간의 선형 의존성을 활용하면 행렬의 차원 예측을 보다 더 정교하게 할 수 있다. 예를 들면, 만약 행렬 Z_l,d에서 같은 부호어가 2번 발생했다면, 부호어내의 선형 의존성을 이용한 방법은 실제로 나타나는 차원을 제대로 예측하지 못한다.

GF(q) 위의 원소들을 임의로 선택해서 (이때, 각 심볼의 발생 확률은 같다고 가정한다) l × l 정방 행렬(Square Matrices)을 만들었을 때, 이 행렬의 차원이 r이 될 확률 P_r은 아래와 같이 주어진다[9].

GF(₃) 및 GF(2²) 위에서 이 값을 계산해보면 아래와 같다. 이때, l → ∞라고 가정한다.

제안하는 알고리즘은 랜덤 정방 행렬의 차원만을 활용하므로, 제안하는 알고리즘의 심볼이 어떤 갈루아 필드 위에 있어도 적용이 가능하다. 따라서 표현의 편의를 위해서 이진 심볼을 이용하는 GF(2) 위에서 설명을 이어가도록 한다. 또한, l × l 정방 행렬의 차원이 l - s 이고 l → ∞일 때의 확률을 P_s 라고 하자. 이 값은 다음과 같이 계산할 수 있다[10].

이때의 값을 계산해보면, 아래의 표로 나타낼 수 있다.

일반적인 예상과는 다르게, 랜덤 이진 정방 행렬의 차원 분포에서의 최대값은 0이 아니라 1에서 나타난다.

만약 l × l 이진 정방 행렬의 차원이 l - s (s ≥ 3)이라고 가정해 보자. 이렇게 낮은 차원을 가진 경우에 대한 설명은 크게 보면 두가지 정도가 있을 수 있다. 첫 번째는 순전히 운에 의존해서 이렇게 낮은 확률을 갖는 경우이다. 예를 들면, 만약 s = 4라고 가정해 보자. 이런 사건이 발생할 확률은 4.65669×10^-5이며, 극단적으로 낮은 값으로 100만번 정도 실험을 하면면 47번쯤 나올 수 있는 확률이다. 또 하나의 가능한 설명은 l × l 이진 정방 행렬 내부에 어떤 규칙성이 존재하는 경우이다. 즉, 본 논문에서 해결하려고 하는 문제인 인터리버 파라미터를 찾는 문제를 생각해 보면, 이진 정방 행렬이 오류 정정 부호화되어 있고, 이 후에 인터리버를 거친 데이터라고 하면 부호어간의 선형 의존성으로 인해서 행렬의 차원이 낮은 값을 가질 수 있을 것이다. 보다 더 정확히 말하자면, 만약 l = S 라면, l × l 이진 정방 행렬의 차원 분포는 표 3과는 전혀 다른 분포를 가질 것이고, l ≠ S라면 표 3의 분포를 따르게 될 것이다.

3.2절에서 설명했듯이, 캡쳐된 데이터를 특정 주기를 단위로 정방 행렬로 만든 후에, 그 데이터의 차원 분포를 이용하면 인터리버의 파라미터를 쉽게 추정할 수 있다. 그러나 일반적으로 캡쳐 된 데이터는 적을 수도 있고, 빠른 계산을 위해서는 데이터양이 적은 경우에도 이러한 방법론을 사용할 수 있어야 한다. 그러나 캡쳐하는 데이터를 정방 행렬로 순서대로 만들어서 차원 분포를 계산하게 되면, 실제로 만들 수 있는 정방 행렬의 개수가 심하게 제한된다. 예를 들면, 길이 1,000인 데이터를 캡쳐 했다고 가정해 보자. 이 경우, 10×10인 정방 행렬을 만든다고 가정하면, 우리가 만들 수 있는 최대치는 10개 정도가 되며, 이 경우는 행렬의 차원 분포를 보기에 심각하게 미흡한 숫자가 되게된다. 여기서, 선형 부호어간의 의존성은 부호어의 순서와는 아무런 관련이 없으므로 다음과 같이 정방 행렬의 개수를 늘릴 수 있다. 길이가 1,000인 데이터를 각각 길이가 10인 시퀀스로 중복되지 않도록 쪼갠다(Partition). 이 경우, 총 시퀀스의 개수는 100이 된다. 이렇게 쪼개진 100개의 시퀀스 중에서 임의로 10개의 시퀀스를 선택한다. 이렇게 하면, 이론상 다음과 같은 조합이 가능하다.

즉, 약 10¹² 정도 가지수가 늘어나게 되어 정방 행렬의 차원 분포를 보는데 아무런 문제가 발생하지 않는다. 물론, 이 경우 중복되는 행들이 발생할 수 있으나, 전체적으로 보면 정방 행렬의 차원 분포를 왜곡시키지는 않는다. 캡쳐되고 이동된 데이터 Z_l,d를 특정한 길이 l로 쪼갠 시퀀스들을 w_i (j ) (0 ≤ i < D , 0 ≤ j < l )라 하자. 이러한 방법을 통해서, 정방 행렬의 분포를 계산한 후, 그 분포가 표 3과 크게 다른 l을 찾게 된다. 분포가 표 3과 다른 분포를 찾기 위해서 아래와 같은 쿨백-라이블러 발산(Kullback-Leibler Divergence)값을 이용한다[11].

식 (9)에서 P(i )는 표 3의 확률값을 나타내고, Q_l (i)는 l × l 정방 행렬의 차원 분포를 나타낸다.

만약 l이 인터리버 주기와 다르다면, 이 값 D_{KL, i}는 0에 수렴할 것이고, 그렇지 않을 경우는 다른 값을 갖게 될 것이다. 제안하는 블라인드 인터리버 파라미터 추정 방법을 정리하면 그림 1과 같다.

Fig. 1. 
Proposed blind interleaver parameter estimation