터보 부호

정보 이론에서 **터보 부호**()는 1990년에서 91년 사이에 개발되었지만 1993년에 처음 발표된 고성능 전방 오류 정정 (FEC) 부호의 한 종류이다. 이들은 특정 잡음 수준이 주어졌을 때 신뢰할 수 있는 통신이 가능한 부호율의 이론적 최대치인 최대 채널 용량 또는 섀넌 한계에 근접한 최초의 실용적인 부호였다. 터보 부호는 3G/4G 이동 통신(예: UMTS 및 LTE) 및 (심우주) 인공위성 통신과 같은 응용 분야에서 사용되며, 설계자들이 데이터 손상 잡음이 있는 대역폭 또는 지연 시간 제약 통신 링크를 통해 신뢰할 수 있는 정보 전송을 달성하고자 하는 다른 응용 분야에서도 사용된다. 터보 부호는 유사한 성능을 제공하는 저밀도 패리티 검사 부호 (LDPC)와 경쟁한다. 터보 부호의 특허가 만료될 때까지 LDPC 부호의 특허가 없는 상태는 LDPC의 지속적인 관련성에 중요한 요소였다.

"터보 부호"라는 이름은 엔진 터보차저에 사용되는 배기 피드백에 비유된 일반적인 터보 부호 디코딩 중에 사용되는 피드백 루프에서 유래되었다. 하겐아워는 인코딩 과정에 피드백이 없기 때문에 터보 부호라는 용어는 잘못된 명칭이라고 주장했다.

## 역사
터보 부호에 대한 기본 특허 출원은 1991년 4월 23일에 제출되었다. 특허 출원에는 클로드 베루가 터보 부호의 유일한 발명가로 기재되어 있다. 이 특허 출원으로 2013년 8월 29일에 만료된 미국 특허 5,446,747을 포함한 여러 특허가 나왔다.

터보 부호에 대한 첫 번째 공개 논문은 "Near Shannon Limit Error-correcting Coding and Decoding: Turbo-codes"였다. 이 논문은 1993년 IEEE 국제 통신 컨퍼런스 회보에 발표되었다. 1993년 논문은 공간 제약으로 인해 세 개의 별도 제출물이 결합되어 구성되었다. 합병으로 인해 논문에는 베루, 글라비외, 티티마지마 (프랑스 Télécom Bretagne, 구 ENST Bretagne) 세 명의 저자가 기재되었다. 그러나 원래 특허 출원에서 베루가 터보 부호의 유일한 발명가이며 논문의 다른 저자들은 핵심 개념 외의 자료를 기고했음이 분명하다.

터보 부호는 도입 당시 너무나 혁명적이어서 코딩 분야의 많은 전문가들이 보고된 결과를 믿지 않았다. 성능이 확인되었을 때 코딩 세계에 작은 혁명이 일어났고 이는 다른 많은 유형의 반복 신호 처리 조사를 이끌었다.

첫 번째 터보 부호 클래스는 병렬 연결 컨볼루션 부호(PCCC)였다. 1993년에 원래 병렬 터보 부호가 도입된 이래로 직렬 연결 컨볼루션 부호와 반복 누적 부호를 포함한 다른 많은 터보 부호 클래스가 발견되었다. 반복 터보 디코딩 방법은 리드 솔로몬 정정 컨볼루션 부호를 포함하여 더 전통적인 FEC 시스템에도 적용되었지만, 이러한 시스템은 반복 디코더의 실제 구현에는 너무 복잡하다. 터보 등화도 터보 코딩 개념에서 파생되었다.

터보 부호 외에도 베루는 특허에 설명된 터보 부호의 예시 구현에 사용되는 재귀 체계적 컨볼루션(RSC) 부호도 발명했다. RSC 부호를 사용하는 터보 부호는 RSC 부호를 사용하지 않는 터보 부호보다 성능이 더 좋은 것으로 보인다.

터보 부호 이전에는 외부 리드 솔로몬 부호와 내부 비터비 디코딩 짧은 제약 길이 컨볼루션 부호를 기반으로 하는 직렬 연결 부호가 최상의 구성이었으며, 이는 RSV 부호로도 알려져 있다.

이후 논문에서 베루는 "80년대 후반 확률적 처리의 중요성을 강조한 G. Battail, J. 하겐아워 및 P. Hoeher의 직관"에 공로를 돌렸다. 그는 "R. 갈라거와 M. 태너는 이미 일반적인 원칙이 밀접하게 관련되어 있는 코딩 및 디코딩 기술을 상상했지만, 당시에는 필요한 계산이 비실용적이었다"고 덧붙였다.

## 예시 인코더
다양한 터보 부호 인스턴스가 있으며, 서로 다른 구성 요소 인코더, 입/출력 비율, 인터리버 및 천공 패턴을 사용한다. 이 예시 인코더 구현은 고전적인 터보 인코더를 설명하고 병렬 터보 부호의 일반적인 설계를 보여준다.

이 인코더 구현은 세 개의 비트 서브 블록을 전송한다. 첫 번째 서브 블록은 페이로드 데이터의 m 비트 블록이다. 두 번째 서브 블록은 재귀 체계적 컨볼루션 부호 (RSC 부호)를 사용하여 계산된 페이로드 데이터에 대한 n/2 패리티 비트이다. 세 번째 서브 블록은 페이로드 데이터의 알려진 순열에 대한 n/2 패리티 비트이며, 역시 RSC 부호를 사용하여 계산된다. 따라서 두 개의 중복되지만 다른 패리티 비트 서브 블록이 페이로드와 함께 전송된다. 전체 블록은 부호율이 인  비트의 데이터를 갖는다. 페이로드 데이터의 순열은 인터리버라는 장치에 의해 수행된다.

하드웨어적으로 이 터보 부호 인코더는 그림에 묘사된 것과 같이 두 개의 동일한 RSC 코더 C1과 C2로 구성되며, 이들은 병렬 연결이라는 연결 방식으로 서로 연결된다.

파일:turbo encoder.svg

그림에서 M은 메모리 레지스터이다. 지연선과 인터리버는 입력 비트 dk가 다른 시퀀스로 나타나도록 한다.
첫 번째 반복에서 입력 시퀀스 dk는 인코더의 체계적인 특성으로 인해 인코더의 두 출력 xk와 y1k 또는 y2k에 모두 나타난다. 인코더 C1과 C2가 n1과 n2 반복에서 사용되면, 그들의 비율은 각각 다음과 같다.

:\begin{align}
  ~R_1 &= \frac{n_1 + n_2}{2n_1 + n_2}\\
  ~R_2 &= \frac{n_1 + n_2}{n_1 + 2n_2}
\end{align}

## 디코더
디코더는 위 인코더와 유사하게 구성된다. 두 개의 기본 디코더는 병렬이 아닌 직렬로 서로 연결된다. \textstyle DEC_1 디코더는 저속(즉, \textstyle R_1)으로 작동하므로 \textstyle C_1 인코더용이며, \textstyle DEC_2는 그에 따라 \textstyle C_2용이다. \textstyle DEC_1은 소프트 결정을 생성하여 \textstyle L_1 지연을 유발한다. 동일한 지연은 인코더의 지연선에 의해 발생한다. \textstyle DEC_2's의 작동은 \textstyle L_2's 지연을 유발한다.

파일:turbo decoder.svg

두 디코더 사이에 설치된 인터리버는 \textstyle DEC_1 출력에서 오는 오류 버스트를 분산시키는 데 사용된다. DI 블록은 역다중화 및 삽입 모듈이다. 스위치처럼 작동하여 입력 비트를 한 순간에는 \textstyle DEC_1's로, 다른 순간에는 \textstyle DEC_2's로 리디렉션한다. OFF 상태에서는 \textstyle y_{1k}'s와 \textstyle y_{2k}'s 입력에 모두 패딩 비트(0)를 공급한다.

기억 없는 AWGN 채널을 고려하고, k번째 반복에서 디코더가 다음과 같은 한 쌍의 확률 변수를 수신한다고 가정한다.

:\begin{align}
  ~x_k &=  (2d_k - 1) + a_k\\
  ~y_k &= 2( Y_k - 1) + b_k
\end{align}

여기서 \textstyle a_k와 \textstyle b_k는 동일한 분산 \textstyle \sigma^2을 갖는 독립적인 잡음 성분이다. \textstyle Y_k는 \textstyle y_k 인코더 출력에서 k번째 비트이다.

여분 정보는 역다중화되어 DI를 통해 \textstyle DEC_1 ( \textstyle y_k = y_{1k}일 때)과 \textstyle DEC_2's ( \textstyle y_k = y_{2k}일 때)로 전송된다.

\textstyle DEC_1's은 소프트 결정을 생성한다. 즉:

:\Lambda(d_k) = \log\frac{p(d_k = 1)}{p(d_k = 0)}

그리고 그것을 \textstyle DEC_2's로 전달한다. \textstyle \Lambda(d_k)'s는 우도비의 로그(LLR)라고 불린다. \textstyle p(d_k = i),\, i \in \{0, 1\}'s는 수신된 \textstyle d_k's 비트를 \textstyle i's로 해석할 확률을 나타내는 \textstyle d_k's 데이터 비트의 사후 확률(APP)이다. LLR을 고려하여 \textstyle DEC_2's는 하드 결정, 즉 디코딩된 비트를 생성한다.

비터비 알고리즘은 APP를 계산할 수 없으므로 \textstyle DEC_1's에 사용할 수 없다는 것이 알려져 있다. 대신 수정된 BCJR 알고리즘이 사용된다. \textstyle DEC_2's의 경우 비터비 알고리즘이 적절하다.

그러나 묘사된 구조는 최적의 구조가 아니다. 왜냐하면 \textstyle DEC_1's은 사용 가능한 여분 정보의 적절한 부분만을 사용하기 때문이다. 구조를 개선하기 위해 피드백 루프가 사용된다 (그림의 점선을 참조).

## 소프트 결정 접근 방식
디코더 프런트엔드는 데이터 스트림의 각 비트에 대해 정수를 생성한다. 이 정수는 비트가 0 또는 1일 가능성이 얼마나 높은지를 나타내는 척도이며 소프트 비트라고도 불린다. 정수는 [-127, 127] 범위에서 가져올 수 있으며, 여기서:
* -127은 "확실히 0"을 의미
* -100은 "매우 0일 가능성이 높음"을 의미
* 0은 "0 또는 1일 수 있음"을 의미
* 100은 "매우 1일 가능성이 높음"을 의미
* 127은 "확실히 1"을 의미

이는 프런트엔드에서 데이터 스트림에 확률적 측면을 도입하지만, 각 비트에 대해 0 또는 1보다 더 많은 정보를 전달한다.

예를 들어, 각 비트에 대해 기존 무선 수신기의 프런트엔드는 내부 아날로그 전압이 주어진 임계 전압 수준보다 높거나 낮은지를 결정해야 한다. 터보 부호 디코더의 경우 프런트엔드는 내부 전압이 주어진 임계값에서 얼마나 떨어져 있는지에 대한 정수 측정값을 제공한다.

 비트 데이터 블록을 디코딩하기 위해 디코더 프런트엔드는 데이터 스트림의 각 비트에 대한 하나의 가능성 측정값으로 구성된 가능성 측정값 블록을 생성한다. 두 개의 병렬 디코더가 있으며, 각각  비트 패리티 서브 블록 중 하나를 위한 것이다. 두 디코더 모두 페이로드 데이터에 대한 m 가능성 서브 블록을 사용한다. 두 번째 패리티 서브 블록에서 작동하는 디코더는 코더가 이 서브 블록에 사용한 순열을 알고 있다.

## 비트를 찾기 위한 가설 해결
터보 부호의 핵심 혁신은 두 디코더 간의 차이를 조화시키기 위해 가능성 데이터를 사용하는 방식이다. 두 컨볼루션 디코더는 페이로드 서브 블록의 m 비트 패턴에 대한 가설(파생된 가능성과 함께)을 생성한다. 가설 비트 패턴을 비교하고, 다른 경우 디코더는 가설의 각 비트에 대해 파생된 가능성을 교환한다. 각 디코더는 다른 디코더의 파생된 가능성 추정치를 통합하여 페이로드의 비트에 대한 새로운 가설을 생성한다. 그런 다음 이러한 새로운 가설을 비교한다. 이 반복 프로세스는 두 디코더가 페이로드의 m 비트 패턴에 대해 동일한 가설을 제시할 때까지 계속되며, 일반적으로 15~18회 주기 동안 진행된다.

이 과정과 십자말 또는 스도쿠와 같은 상호 참조 퍼즐을 푸는 과정 사이에 비유를 할 수 있다. 부분적으로 완성되었지만 손상될 수 있는 십자말 퍼즐을 생각해 보자. 두 명의 퍼즐 해결사(디코더)가 이를 풀려고 한다. 한 명은 "세로" 단서(패리티 비트)만 가지고 있고, 다른 한 명은 "가로" 단서만 가지고 있다. 시작하기 위해 두 해결사는 각자 자신의 단서에 대한 답(가설)을 추측하고, 각 글자(페이로드 비트)에 대해 얼마나 확신하는지 기록한다. 그런 다음, 그들은 서로 답과 확신 등급을 교환하여 메모를 비교하고, 어디에서 어떻게 다른지 확인한다. 이 새로운 지식을 바탕으로 그들은 모두 업데이트된 답과 확신 등급을 제시하고, 동일한 해결책으로 수렴할 때까지 전체 과정을 반복한다.

## 성능
터보 부호는 채널에서 부호의 무작위적인 모양과 물리적으로 실현 가능한 디코딩 구조의 매력적인 조합으로 인해 성능이 우수하다. 터보 부호는 오류 마루의 영향을 받는다.

## 터보 부호를 활용한 실제 응용
통신:
* 터보 부호는 3G 및 4G 이동 통신 표준, 예를 들어 HSPA, EV-DO 및 LTE에 광범위하게 사용된다.
* 퀄컴의 지상파 모바일 TV 시스템인 미디어FLO.
* DVB-RCS 및 DVB-RCS2와 같은 인공위성 통신 시스템의 상호작용 채널.
* 화성 정찰위성과 같은 최근의 NASA 임무에서는 터보 부호를 리드 솔로몬 부호-비터비 디코더 부호의 대안으로 사용한다.
* 무선 도시권 네트워크 표준인 IEEE 802.16 (와이맥스)은 블록 터보 코딩과 컨볼루션 터보 코딩을 사용한다.

## 베이즈 공식화
인공지능 관점에서 볼 때 터보 부호는 베이즈 네트워크에서 반복적인 신뢰전파의 한 인스턴스로 간주될 수 있다.

## 같이 보기
* BCJR 알고리즘
* 컨볼루션 부호
* 전방 오류 정정
* 인터리버
* 저밀도 패리티 검사 부호
* 직렬 연결 컨볼루션 부호
* 소프트 결정 디코딩
* 터보 등화
* 비터비 알고리즘

## 각주

## 추가 자료
### 출판물
* 
* 
*

## 외부 링크
* 
* "The UMTS Turbo Code and an Efficient Decoder Implementation Suitable for Software-Defined Radios"  (International Journal of Wireless Information Networks)
* 
* "Pushing the Limit", a *[[Science News]]* feature about the development and genesis of turbo codes
* International Symposium On Turbo Codes
* Coded Modulation Library, an open source library for simulating turbo codes in matlab
* "Turbo Equalization: Principles and New Results" , an *[[IEEE Transactions on Communications]]* article about using convolutional codes jointly with channel equalization.
* IT++ Home Page The IT++ is a powerful C++ library which in particular supports turbo codes
* Turbo codes publications by David MacKay
* AFF3CT Home Page (A Fast Forward Error Correction Toolbox) for high speed turbo codes simulations in software
* 
* 3GPP LTE Turbo Reference Design.
* Estimate Turbo Code BER Performance in AWGN  (MatLab).
* Parallel Concatenated Convolutional Coding: Turbo Codes (MatLab Simulink)

분류:오류 검출 정정
분류:프랑스의 발명품