Convolutional code (컨볼루션 코드)

 

 Convolutional codes는 1955년 Elias [1]에 의해서 처음 발견되었다. 1959년 Hagelbarger [2]에 의해서 recurrent codes로 재 소개되었다. 1970년대 초에 Forney [3]에 의해 convolutional codes가 대수적으로 정립되었다.

Convolutional codes는 단순히 k 비트의 부가 데이터를 포함시켜 부호화하는 블록 부호와 달리 메모리 소자를 이용하여 이전에 저장된 정보가 현재의 데이터에 일정한 규칙을 가지고 영향을 미치는 방식이다. 이러한 방법으로 인해 convolutional codes는 블록 부호 방식보다 오류 정정 효율이 좋기 때문에 channel coding에 주로 사용된다[4].

 Convolutional codes의 일반적인 구조는 아래 그림과 같다. 아래 구조는 constraint length가 7이고 1/2 coding rate을 갖는다.  Constraint length는 현재 정보에 영향을 미치는 정보의 비트 수를 의미하며 길쌈 부호의 생성은 가산기와 쉬프트 레지스터를 통해 이루어진다. 입력된 input bit k에 대해 부호화된 출력 비트 n의 비율을 부호율이라 하며 R=k/n 또는 (n.k)로 표현한다. 부호율이 작으면 부호 이득은 높으나 전송해야 할 data의 증가로 인해 전송 효율은 떨어지게 된다.

 

 

 

 그림과 같은 convolutional encoder 구조는 constraint length와 같은 길이를 갖는 2 진수의 쌍으로 표현할 수 있다. 위 구조는 constraint length K=7, coding rate R=1/2 또는 (2,1)로 표현 할 수 있다. 즉, K=7, (2,1)인 convolutional encoder에 의해 생성되는 G(j)는 아래와 같이 표현 할 수 있다.

 

 

  이를 다항식으로 표현하면 다음과 같다.
 

  
  

  입력 되는 intput data의 sequence를 U라하면 convolutional encoder의 출력은 다름과 같이 나타낼 수 있다.
 

  

   

 

 위의 식은 다음과 같은 형태로 다시 나타낼 수 있다.
 

  

 

 위 그림과 같은 convolutional codes는 K=7, (2,1), G=(1111001,1011011) 로 나타낼 수 있다. 보통 convolutional codes의 생성 식 G는 8진수의 형태로 나타내기 때문에 G=(171,133) 이라 표현 할 수 있다.

 Convolutional codes를 표현하기 위한 방법은 connection representation, state representation, tree presentation, trellis representation 등이 존재하지만 state representation, trellis representation (트렐리스 표현)이 가장 많이 쓰인다.

 

•  State diagram representation

   

 

 

•  Trellis representation

   

   

 

 

[1] P. Elias, “Coding for noisy channels” 1955 IRE International Convention Record(Part IV), pp. 37-46.

[2] D.W. Hagelbager, “Recurrent codes: easily mechanized, burst-correcting binary codes,” Bell Syst. Tech. J., vol.38, pp. 969-984, July 1959.

[3] G.D. Forney, “Convolutional codes I: algebraic structure,” IEEE Trans. Inform. Theory, IT-16, pp. 720-738, November 1970.

[4] Anderson, S. Mohan, "Source and channel coding : an algorithmic approach," Kluwer Academic Pub, Boston, May 1991.