1. 길쌈부호의 복호화(Decoding)의 특징
ㅇ 확률적 복호 방식 (Probabilistic Decoding) 임
- 메세지 비트열과 부호어와 1:1 대응을 갖는, 추상대수학을 이용한, 블록부호와는 달리,
- 주로 확률적으로 복호하므로, 확률적 복호 방식 이라고 함
- 복호 규칙으로는, 최대 우도 복호(ML) 또는 최대 사후확률 복호(MAP) 규칙을 사용함
ㅇ 과거,미래가 상호 의존적임
- 동일 비트열이 수신되더라도,
- 그 이전 또는 이후가 무엇이냐에 따라, 다른 메세지로 복호될 수 있음
ㅇ 김쌈부호의 부호어 길이는, 메세지 비트 수에 따라서도 달라짐
- 블록부호는, Block Decoding (블록 복호) 라고 하고,
- 길쌈부호는, Sequence Decoding (시퀀스 복호) 라고 함
ㅇ 거의 대부분, 연판정 비터비 복호 방식을 이용
- 단, 구속장 길이가 10을 초과하면, 하드웨어 복잡성이 커지므로,
- 이때에는, 순차 복호 방식을 사용
2. 길쌈부호의 주요 복호 방법 종류
※ 트렐리스 구조를 따라, 가능한 코드 경로 중 가장 가능성이 높은 (또는, 오류 확률 최소),
- 경로를 찾아, 원래의 정보 비트를 복원하는 복호화 과정을 거침
- 대표적인 복호 알고리즘은 다음 세 가지가 있음
ㅇ 순차 복호 방식 (Sequential Decoding)
- 트렐리스 경로를 순차적으로 탐색하며 가장 가능성 높은 경로를 추적
. 복호 복잡도가 입력 길이에 비례하여 가변적
. 긴 제약길이 코드에 적합
- 방법
. 트리구조를 이용하여 전체 트리구조를 모두 탐색하지 않고,
. 하나의 경로 만을 따라가며 전후로 탐색해가며 복호
- 계산량 특징
. 구속장 길이와는 관계 없으므로,
.. 구속장 길이를 크게 증가시킨 성능 좋은 컨볼루션 부호 사용 가능
. 계산량 변화 형태가 불규칙
.. 채널 상태가 좋지 않을 경우에 예측 못한 많은 계산량을 보일 수 있고
.. 이 경우, 오히려 동작속도가 느릴 수 있음
- 1957년 Wozencraft에 의해 제안
ㅇ 문턱 복호 방식 (Threshold Decoding), 다수결 논리 복호 (Majority Logic Decoding)
- 경로 메트릭(metric)이 일정 문턱(Threshold)을 넘지 않도록 제한하면서 탐색
. 트렐리스 탐색 시 각 경로의 누적 메트릭이 일정 문턱값을 넘지 않도록 제한하여,
. 계산량을 줄이는 단순화된 복호 방식
- 계산량 특징
. 순차 복호 방식보다 연산량을 줄일 수 있어, 구현이 비교적 간단함
. 그러나, 경로 탐색의 제약으로 인해 성능은 다소 낮을 수 있음
. 일반적으로, 오류 정정 성능보다 계산 효율을 중시할 때 사용됨
- 1963년 Massey에 의한 MIT 박사학위 논문에 의해 제안
ㅇ 비터비 복호 방식 (Viterbi Decoding) : (Viterbi 복호 알고리즘 사용 방식, 가장 널리 사용)
- 방법
. 트렐리스도의 모든 경로(path)에 대해 메트릭 값을 이용하여 탐색한 후,
. 트렐리스도 상의 최적 경로를 선정하여 복호
- 계산량 특징
. 트렐리스도의 상태 수에 따라 복잡도가 결정되며,
. 구속장 길이가 클수록, 상태 수(=2K−1)가 지수적으로 증가 → 계산량도 급격히 늘어남
- 1967년 Andrew J. Viterbi에 의해 제안.