연결 오류 수정 코드

코딩 이론에서, 결합된 코드는 내부 코드와 외부 코드를 결합하여 파생되는 오류 수정 코드의 클래스를 형성한다. 그것들은 블록 길이가 증가하고 다항식 시간 디코딩 복잡성이 증가하면서 기하급수적으로 오류 확률이 감소하는 코드를 찾는 문제에 대한 해결책으로 데이브 포니에 의해 1966년에 고안되었다.^[1] 연결된 코드는 1970년대에 우주 통신에 널리 사용되었다.

배경

채널 코딩 분야는 주어진 통신 채널에 걸쳐 가능한 최고 속도로 데이터 스트림을 전송한 다음, 주어진 기술에서 구현이 가능한 인코딩 및 디코딩 알고리즘을 사용하여 수신기에서 신뢰성 있게 원본 데이터를 디코딩하는 것과 관련이 있다.

섀넌의 채널 코딩 정리는 많은 공통 채널에 걸쳐 주어진 채널의 채널 용량이라 불리는$$특정 임계값 $C{\displaystyle }$ ${\displaystyle$ $R$$}$보다 작은 모든 속도 $R{\displaystyle }$ ${\displaystyle$ $R$$}$에서 데이터를 신뢰성 있게 전송할 수 있는 채널 코딩 체계가 존재함을 보여준다. 실제로 부호화 방식의 $블록$ 길이 N ${\displaystyle N}$이(가) 무한대로 이동함에 따라 디코딩 오류 발생 확률은 기하급수적으로 감소할 수 있다. 그러나, 단순히 모든 가능한 전송 코드 워드의 가능성을 계산하는 순진한 최적 해독 체계의 복잡성은 $N{\displaystyle }$ ${\displaystyle N}$과 함께 기하급수적으로 증가하므로, 그러한 최적의 해독기는 빠르게 실현 불가능해진다$.$

Dave Forney는 박사 논문에서 코드 블록 길이와 함께 다항식으로만 증가하는 복잡성을 해독하면서 용량보다 적은 모든 데이터 속도에서 기하급수적으로 오류 확률을 감소시키는 데 결합된 코드를 사용할 수 있다는 것을 보여주었다.

설명

C를_in [n, k, d] 코드, 즉 길이 n, 치수 k, 최소 해밍 거리 d 및 속도 r = k/n의 블록 코드가 되도록 한다.

${\displaystyle C_{in}:A^{k}\오른쪽 화살표 A^{n}}$

B = A 기호가 있는 알파벳 B에 C를_out [N, K, D] 코드로 표시:

${\displaystyle C_{out}:B^{K}\오른쪽 화살표 B^{N}}$

내부 코드 C는_in A = B 가능한 입력 중 하나를 취하여 A를 통해 n-투플에 인코딩하고, B 가능한 출력 중 하나로 송신 및 해독한다. 우리는 이것을 알파벳 B에서 하나의 기호를 전송할 수 있는 (슈퍼) 채널로 간주한다. 우리는 이 채널 N번으로 각각의 N 기호를 C의_out 코드 워드로 전송한다. C_out∘C로_in 표시된 C_in (내부 코드로서)와_out C (외부 코드로서)의 연결은 따라서 알파벳 A에 대한 길이 Nn의 코드다.^[1]

${\displaystyle C_{out}\circule C_{in}:A^{K}\오른쪽 화살표 A^{N}}$

각 입력 메시지 m = (m₁₂, m, ..., m_K)을 코드 워드(C_in(m),₁ C_in(m),₂ ..., C_in(m')_N에 매핑하며, 여기서 (m',₁ m',₂ m', ..., m')_N = C(m₁, m, m, ..., m_K) = C_out(m, m₂, m)이다.

이 방법의 중요한 영감이 그러는데, Cin은 디코딩 되어 사용한 maximum-likelihood 접근( 늘어나고 따라서 길이와 함께 기하 급수적으로 감소하는 오류 확률을 보여 주), Cout은 코드 길이 N=2nr이 될 수 있는 디코딩에 다항 시간의 N, 그 종속 코드가 될 수 있다를 디코딩에 다항 시간의 총 길이 n2.nr)O(N⋅Log_in(N) 및 C가 지수 디코딩 복잡성을 가지고 있더라도 기하급수적으로 감소하는 오차 확률을 나타낸다.^[1] 이것은 디코딩 연결 코드 절에서 더 자세히 설명된다.

위의 연결의 일반화에서는 N개의 가능한 내부_in,i 코드 C가 있으며, C의_out 코드 워드에 있는 i번째 기호는 i번째 내부 코드를 사용하여 내부 채널을 통해 전송된다. 저스틴 코드는 일반화된 연결 코드의 예로서, 여기서 외부 코드는 리드-솔로몬 코드다.

특성.

1. 연결된 코드 C_out∘C의_in 거리는 최소한 dD, 즉 D' ≥ dD를 가진 [nN, kK, D'] 코드다.

증명: 두 개의 다른 메시지 m m¹ m² ∈ B를^K 생각해 보라. Δ는 두 암호어 사이의 거리를 나타내도록 한다. 그러면

${\displaystyle \Delta(C_{out}(m^{1}), C_{out}(m^{2})\geq D.}$

따라서 코드워드 C_out(m¹)와 C_out(m²)의 N 기호의 순서가 다른 D 위치가 최소한 있다. 이 자리에 대해 말하자면, I로 알려졌듯이,

${\displaystyle \Delta(C_{in})(C_{out}(m^{1})_{i}), C_{in}(C_{out}(m^{2})\geq d.}$

결과적으로, 두 개의 코드 단어가 다른 알파벳 A에서 nnN 기호를 추출한 순서에 최소한 d positionsD 위치가 있다.

${\displaystyle \Delta(C_{in})(C_{out}(m^{1}),C_{in}(C_{out}(m^{2})\geq dD.}$

2. C와_out C가_in 선형 블록 코드라면 C cC도_outin 선형 블록 코드다.

이_out 특성은_in C와 C의 발전기 매트릭스 측면에서 연결된 코드에 대한 발전기 매트릭스를 정의한다는 개념에 근거하여 쉽게 알 수 있다.

연결된 코드를 디코딩하는 중

연결된 코드에 대한 디코딩 알고리즘의 자연적인 개념은 먼저 내부 코드를 디코딩한 다음 외부 코드를 디코딩하는 것이다. 알고리즘이 실용적이 되려면 최종 블록 길이의 다항식 시간이어야 한다. 외부 코드에 대한 다항식 시간 고유 디코딩 알고리즘이 있다고 생각해 보십시오. 이제 내부 코드에 대한 다항식 시간 디코딩 알고리즘을 찾아야 한다. 여기서 다항식 실행시간은 최종 블록길이의 다항식 실행시간을 의미하는 것으로 파악된다. 주요 아이디어는 내부 블록 길이가 외부 코드 크기의 로그로 선택되면 내부 블록 길이의 기하급수적인 시간에 내부 코드의 디코딩 알고리즘이 실행될 수 있으며, 따라서 내부 코드의 경우 기하급수적이지만 최적의 최대우도 디코더(MLD)를 사용할 수 있다는 것이다.

세부적으로 디코더에 대한 입력을 벡터 y = (y₁, ..., y_N) ∈ (Aⁿ)가 되도록 한다.^N 그러면 디코딩 알고리즘은 2단계 과정이다.

1. 내부 코드 C의_in MLD를 사용하여 y' = (y',₁ ..., y')_N의 내부 코드 단어 집합을 y'_i = MLD_Cin(y_i), 1 ≤ i ≤ N으로 재구성한다.
2. 'Y'에서 C에_out 대한 고유 디코딩 알고리즘을 실행한다.

이제 첫 번째 단계의 시간 복잡성은 O(N⋅exp(n)이며 여기서 n = O(log(N))는 내부 블록 길이이다. 즉, 외부 블록 길이 N의 관점에서 N^O(1)(즉, 다항식 시간)이다. 2단계에서 외부 디코딩 알고리즘이 다항식 시간에서 실행되는 것으로 가정하기 때문에 전체 디코딩 알고리즘의 복잡성도 다항식 시간이다.

언급

위에서 설명한 디코딩 알고리즘은 숫자로 dD/4 미만까지의 모든 오류를 수정하는 데 사용할 수 있다. 최소 거리 디코딩을 사용하여 외부 디코더는 오류 발생 시 D/2 기호 y'_i 미만으로 모든 입력 y'를 수정할 수 있다. 마찬가지로, d/2 미만의 내부 기호가 잘못되었을 경우 내부 코드가 입력 y를_i 신뢰성 있게 수정할 수 있다. 따라서 내부 디코딩 후 외부 기호 y'_i가 부정확하게 되려면 적어도 d/2 내부 기호가 잘못되어 있어야 하며, 외부 코드가 실패하려면 적어도 D/2 외부 기호에 대해 이러한 현상이 발생해야 한다. 따라서 연결 코드가 실패하기 위해 잘못 수신해야 하는 내부 기호의 총 수는 d/22D/2 = dD/4 이상이어야 한다.

알고리즘은 내부 코드가 다른 경우(예: 저스틴 코드)에도 작동한다. Forney가 개발한 일반화된 최소 거리 알고리즘은 최대 dD/2 오류를 수정하는 데 사용될 수 있다.^[2] 내부 코드의 삭제 정보를 사용하여 외부 코드의 성능을 향상시켰으며, 소프트 결정 디코딩을 사용한 알고리즘의 첫 번째 예였다.^[3][4]

적용들

비록 1971년 메리너 화성 탐사선 임무를 위해 이미 간단한 연결 계획이 실행되었지만,^[5] 1977년 두 개의 우주 탐사선을 발사했던 보이저 프로그램과의 심층 우주 통신에 연결된 코드가 정기적으로 사용되기 시작하고 있었다.^[6] 그 이후로, 연결된 코드는 효율적인 오류 수정 코딩의 작업마가 되었고, 적어도 터보 코드와 LDPC 코드가 발명될 때까지 그렇게 유지되었다.^[5][6]

전형적으로 내부코드는 블록코드가 아니라 제약조건 길이가 짧은 소프트 결정형 비테르비 디코딩 코드다.^[7] 외부 코드의 경우, 더 긴 하드 결정 블록 코드, 흔히 8비트 기호가 있는 리드-솔로몬 코드가 사용된다.^[1][5] 기호 크기가 클수록 채널 손상으로 인해 발생할 수 있는 오류 버스트에 대해 외부 코드가 더 강력해지고, 또한 콘볼루션 코드 자체의 잘못된 출력이 버스트이기 때문이다.^[1][5] 인터리빙 계층은 일반적으로 두 코드 사이에 추가되어 오류 버스트를 더 넓은 범위로 분산시킨다.^[5]

보이저 2에서는 내부 비테르비 콘볼루션 코드와 외부 리드-솔로몬 코드(RSV 코드)의 조합이 처음 사용되었으며, 우주 분야 내외에서 인기 있는 건축물이 되었다.^[5][8] 그것은 오늘날에도 DVB-S 디지털 텔레비전 방송 표준과 같은 위성 통신에 특히 많이 사용되고 있다.^[9]

더 느슨한 의미에서는 둘 이상의 코드(시리얼)의 조합을 연결 코드라고 할 수 있다. 예를 들어, DVB-S2 표준 내에서, 고유 오류 층으로 인해 내부 LDPC 코드에서 남아 있는 복원력 있는 오류를 제거하기 위해 매우 효율적인 LDPC 코드를 대수적 외부 코드와 결합한다.^[10]

컴팩트 디스크(CD)에도 간단한 결합 방식이 사용되는데, 크기가 다른 두 리드-솔로몬 코드 사이의 인터리빙 레이어가 여러 블록에 오류를 퍼뜨린다.

터보 코드: 병렬 연결 접근법

위의 설명은 현재 연속적으로 연결된 코드라고 불리는 것에 대해 주어진다. 1993년에 처음 설명한 터보 코드는 두 개의 콘볼루션 코드의 병렬 결합을 구현했는데, 두 코드 사이에 인터리버가 있고 코드 사이에 정보를 앞뒤로 전달하는 반복 디코더가 있다.^[6] 이 설계는 이전에 고안된 어떤 연결 코드보다 성능이 좋다.

그러나 터보 코드의 핵심 측면은 반복된 디코딩 접근법이다. 이제 연속적으로 연결된 경련 코드(SCCC) 내에서와 같이 더 높은 코딩 이득을 얻기 위해 직렬 연결에도 반복된 디코딩이 적용된다. 갈릴레오 우주탐사기의 "갈릴레오 코드"에서 2-5번의 반복으로 초기 형태의 반복된 반복 디코딩이 구현되었다.^[5]

참고 항목

• 저스틴 코드
• 자야블로프 바인딩
• 싱글톤 바운드
• 길버트-바르샤모프 바운드

참조

추가 읽기

• Shu Lin; Daniel J. Costello Jr. (1983). Error Control Coding: Fundamentals and Applications. Prentice Hall. pp. 278–280. ISBN 978-0-13-283796-5.
• F.J. MacWilliams; N.J.A. Sloane (1977). The Theory of Error-Correcting Codes. North-Holland. pp. 307–316. ISBN 978-0-444-85193-2.

외부 링크

• Dave Forney (ed.). "Concatenated codes". Scholarpedia.
• 버팔로 대학교 코딩 이론 강의 노트 - 닥터 아트리 루드라