쿨백-라이블러 발산을 이용한 인터리버 파라미터 추정

Ⅰ. 서 론

근래의 디지털 통신 시스템의 경우, 통신상에서 일어날 수 있는 다양한 오류 등에 대비한 안정적인 통신을 위해서 거의 항상 오류 정정 부호를 사용한다. 일반적으로 이러한 오류 정정 부호는 오류에 대응하기 위해서 부가 정보를 추가하며, 대부분의 오류 정정 부호는 랜덤 오류에 강인하게 디자인한다. 그러나 군집 오류가 발생했을 경우, 일반적인 오류 정정 부호의 오류 정정 능력은 급격히 떨어지게 되어 전체적인 시스템의 성능을 떨어뜨리게 된다. 이러한 문제를 해결하기 위해서, 군집 오류를 랜덤 오류로 바꾸어 줄 수 있는 기술인 인터리버를 사용하게 된다[1].

일반적인 통신 시스템의 경우, 송신단과 수신단은 통신 각 모듈에 대한 구체적인 파라미터를 알고 있어서 통신 자체에 어려움이 발생하지 않으나, 비협력적인 상황에서는 각 통신에 대한 구체적인 파라미터를 알 수 없으므로 통신 내용을 파악하기 위해서는 무엇보다 각 통신 모듈에 사용되는 파라미터를 파악하는 것이 무엇보다 중요하다. 본 논문에서는 이 중에서 인터리버 파라미터를 찾아내는 방법론에 대해서 제안하도록 한다.

기존의 인터리버 파라미터를 찾는 방법론은 기본적으로 오류 정정 부호가 갖고 있는 각 부호어내의 선형성을 이용하는 것이 일반적이다[2]-[8]. 이 방법론을 좀 더 세부적으로 구분해 보자면, 쌍대 부호를 사용하는 방법[2]-[6], 부호어내의 선형 의존성(Linear Dependence within a Codeword)을 이용하는 방법[7], 그리고 이 두가지 방법을 모두 다 차용하는 방법으로 나눌 수 있다[8]. 본 논문에서는 부호어내의 선형 의존성 뿐만 아니라 부호어간 선형 의존성(Linear Dependence Among Codewords)을 활용하여 인터리버 주기를 찾는 방법론을 확장하였고, 랜덤 정방 행렬의(Random Square Matrix) 차원 분포와 쿨백-라이블러 발산(Kullback-Leibler Divergence)을 이용하여 인터리버 주기를 찾는 방법론을 제안한다.

Ⅱ. 기존 연구

Ⅲ. 제안하는 블라인드 인터리버 파라미터 추정 알고리즘

3.2 정방 랜덤 행렬의 차원 분포

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

$\[ P_r=q^{-l^2}\frac{\left[\prod _{i=0}^{r-1}\left(q^l-q^i\right)\right]\left[\prod _{i=0}^{r-1}\left(q^l-q^i\right)\right]}{\prod _{i=0}^{r-1}\left(q^r-q^i\right)} \]$

(6)

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

Table 1.

Distribution of the ranks of the random matrices over GF(3) Pr

Table 2.

Distribution of the ranks of the random matrices over GF(22) Pr

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

$\[ P_s=2^{-s^2}\left[\prod _{i=s+1}^{\infty }\left(1-2^{-i}\right)\right]\left[\prod _{i=1}^s{\left(1-2^{-i}\right)}^{-1}\right] \]$

(7)

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

Table 3.

Distribution of the ranks of the random matrices over GF(2) Ps

일반적인 예상과는 다르게, 랜덤 이진 정방 행렬의 차원 분포에서의 최대값은 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.3 제안하는 인터리버 파라미터 추정 방법

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

$\[ \left(\begin{array}{c}100\\ 10\end{array}\right)\approx 1.731\times {10}^{13} \]$

(8)

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

$\[ D_{KL,l}=\sum _{i}P\left(i\right)\log \frac{P\left(i\right)}{Q_l\left(i\right)} \]$

(9)

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

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

Fig. 1.

Proposed blind interleaver parameter estimation

Ⅳ. 성능 분석

제안하는 알고리즘을 검증하기 위해서 다양한 실험을 진행하였다. 제안하는 방법은 기본적으로 선형 부호의 선형성만을 활용함으로, 모든 선형 부호에 적용 가능하다. 본 논문에서는 가장 간단한 부호인 (7, 4) 해밍 부호를 활용하여 실험을 진행하였다. 그리고, 계산의 편의성을 위해서, KLD 계산 과정에서 표 3의 모든 값을 사용하지 않고, s가 3일때까지의 값만을 활용하였다. 이 경우, P_s는 0.005238에서 1–0.288788–0.577576–0.128350 = 0.005286이 된다.

우선, 제안하는 방법에서 검출 오경보 확률(False Alarm Probability)을 조절하기 위해서, 관련한 실험을 진행하였다. 이 경우 최대 KLD 값이 특정한 문턱값(Threshold) 아래인 경우는 검출 실패로 간주하였고, 최대 KLD 값이 문턱값 보다는 크지만, 추정한 인터리버 주기가 실제 인터리버 주기와 다른 경우를 오경보로 판단하였다.

그림 2는 인터리버 주기가 28일 때, 각 문턱값에 따른 검출 확률을 채널 오류 확률 BER(Bit Error Rate)에 따라서 나타낸다. 그림에서 볼 수 있듯이 문턱값을 높일수록 전반적인 검출 성능이 약간씩 떨어지는 결과를 알 수 있다.

Fig. 2.

Detection probability for varying thresholds

그리고 각 알고리즘의 오경보 확률은 각각, 0.14%, 0.18%, 0.12%, 0.03%, 그리고 0%로 문턱값이 커짐에 따라서 전반적으로 오경보 확률이 작아지는 결과를 보여준다. 여기서 나온 실험 결과를 통해서, 문턱값이 0.015일 때가 검출 성능과 오경보 확률 사이에서 균형 잡힌 결과를 난다고 판단된다. 따라서 이후의 실험 결과는 문턱값을 0.015로 고정하였다.

그림 3은 제안하는 알고리즘과 GJETP 알고리즘(GJETP로 표시)의 성능을 비교한 그림이다. 이 경우 인터리버 주기는 28이다. 그림에서 볼 수 있듯이 제안하는 알고리즘이 전반적으로 좋은 검출 성능을 나타내는 것을 알 수 있다. 또한, 실제 필드 환경에서 안정적인 통신을 위한 타켓 BER 이 0.001 정도인 것을 감안하면, 제안하는 알고리즘은 항상 100%의 검출 성능을 나타냄을 알 수 있다. 이 경우, 제안하는 알고리즘의 오경보 확률은 0.03%이고, GJETP 알고리즘의 오경보 확률은 0.2%로, 제안하는 알고리즘이 안정성 측면에서도 월등한 결과를 나타냄을 알 수 있다.

Fig. 3.

Detection probability when the interleaver period is 28

그림 4 역시 GJETP 알고리즘과 제안하는 알고리즘의 비교를 나타내는데, 이 경우의 인터리버 주기는 21이다. 역시 그림에서 볼 수 있듯히 제안하는 알고리즘이 훨씬 나은 성능을 나타내고 있다. 이 경우의 오경보 확률은 제안하는 알고리즘은 0%, GJETP 알고리즘은 0.06%를 나타낸다.

Fig. 4.

Detection probability when the interleaver period is 21

Ⅴ. 결론 및 향후 과제

본 논문에서는 비협력적 상황에서 정방 랜덤 행렬의 차원 분포와 쿨백-라이블러 발산값을 활용하여 수신 신호의 복원을 위한 인터리버 파라미터 추정 방법을 제안하였다. 오류 정정 부호 및 인터리빙 된 데이터의 경우, 인터리버 주기 l과 동일한 크기로 l ×l 정방 행렬을 만들었을 때, 이 행렬들의 차원 분포는 랜덤 정방 행렬의 차원 분포와는 완전히 다르게 된다. 이 특성을 활용해서, 캡쳐된 데이터를 특정 단위로 잘라서 정방 행렬을 만든 후에, 그 정방 행렬들의 차원 분포를 계산하였다. 이 후, 이 분포와 랜덤 정방 행렬의 차원 분포를 이용하여 쿨백-라이블러 발산값을 계산한 후, 가장 큰 값을 갖는 특정 단위를 인터리버 주기로 선언하였다. 모의 실험 결과를 통해서 제안하는 방법이 기존의 방법보다 검출 성능 뿐 아니라 오경보 확률에서 월등히 좋은 성능을 나타냄을 알 수 있었다. 제안한 알고리즘에서는 오경보 확률을 조절할 수 있는 문턱값을 실험에 의존하여 결정하였으나, 추후 연구를 통해서 오경보 확률에 따른 문턱값을 결정하도록 할 예정이다.

Acknowledgments

본 연구는 방위사업청 및 국방과학연구소에 의해 설립된 신호정보 특화연구센터의 지원을 받아 수행되었음.

References

• S. B. Wicker, "Error control systems for digital communications and storage", Englewood Cliffs, NJ, USA, Prentice-Hall, p424-427, (1995).
• A. Valembois, "Detection and recognition of a binary linear code", Discrete Applied Mathematics, 111(1-2), p199-218, Jul), (2001. [https://doi.org/10.1016/s0166-218x(00)00353-x]
• A. Canteaut, and F. Chabaud, "A new algorithm for finding minimum-weight words in a linear code: application to McEliece’s cryptosystem and to narrow-sense BCH codes of length 511", IEEE Trans. Inf. Theory, 44(1), p367-378, Jan), (1998. [https://doi.org/10.1109/18.651067]
• M. Cluzeau, and M. Finiasz, "Recovering code’s length and synchronization from a noisy intercepted bitstream", in Proc. of ISIT, Seoul, Korea, p2737-2741, Jun./Jul), (2009. [https://doi.org/10.1109/isit.2009.5205843]
• Swaminathan R, A. S. Madhukumar, N. W. Teck, and C. M. S. See, "Parameter estimation of convolutional and helical interleavers in a noisy environment", IEEE Access, 5, p6151-6167, Mar), (2017.
• J. Jeong, J. Oh, H. Lim, and D. Yoon, "Estimation of Interleaver Parameters for Punctured Channel Coded Signals in Noisy Channels", Journal of KIIT, 14(11), p49-57, Nov), (2016. [https://doi.org/10.14801/jkiit.2016.14.11.49]
• G. Burel, and R. Gautier, "Blind estimation of encoder and interleaver characteristics in a non cooperative context", in Proc. of IASTED, Scottsdale, AZ, USA, Nov), (2003.
• G. Sicot, S. Houcke, and J. Barbier, "Blind detection of interleaver parameters", Signal Processing, 89(4), p450-462, Apr), (2009. [https://doi.org/10.1016/j.sigpro.2008.09.012]
• E. M. Gabidulin, "Theory of codes with maximum rank distance", Problems of Information Transmission, 21(1), p1-12, Jan), (1985.
• V. F. Kolchin, "Random graphs", New York, Cambridge University Press, p126-135, (1999).
• T. M. Cover, and Joy A. Thomas, "Elements of Information Theory", New York, Wiley, p12-49, (1991).