연접 오류 정정 코드

부호 이론에서 연접 부호(영어: concatenated codes)는 내부 부호(영어: inner code)와 외부 부호(영어: outer code)를 결합하여 파생되는 오류 정정 부호의 한 종류이다. 이 개념은 1966년 데이브 포니에 의해 블록 길이가 증가함에 따라 오류 확률이 기하급수적으로 감소하고 다항 시간 디코딩 복잡도를 갖는 부호를 찾는 문제에 대한 해결책으로 고안되었다.^[1] 연접 부호는 1970년대 우주 통신에 널리 사용되었다.

배경

채널 코딩 분야는 주어진 통신 채널을 통해 가능한 가장 높은 속도로 데이터 스트림을 전송한 다음, 주어진 기술에서 구현 가능한 인코딩 및 디코딩 알고리즘을 사용하여 수신기에서 원본 데이터를 안정적으로 디코딩하는 것을 다룬다.

섀넌의 채널 코딩 정리는 많은 일반적인 채널에서 주어진 채널의 채널 용량이라고 불리는 특정 임계값 ${\displaystyle C}$ 미만의 모든 속도 ${\displaystyle R}$에서 데이터를 안정적으로 전송할 수 있는 채널 코딩 방식이 존재함을 보여준다. 실제로 디코딩 오류 확률은 코딩 방식의 블록 길이 ${\displaystyle N}$이 무한대로 갈수록 기하급수적으로 감소할 수 있다. 그러나 모든 가능한 전송된 코드워드의 가능성을 단순히 계산하는 순진한 최적 디코딩 방식의 복잡도는 ${\displaystyle N}$에 따라 기하급수적으로 증가하므로 이러한 최적 디코더는 빠르게 실현 불가능해진다.

데이브 포니는 그의 박사 학위 논문에서 연접 부호가 용량 미만의 모든 데이터 속도에서 기하급수적으로 감소하는 오류 확률을 달성하는 데 사용될 수 있으며, 디코딩 복잡도는 코드 블록 길이에 따라 다항식으로만 증가함을 보여주었다.

설명

내부 부호와 외부 부호로 구성된 연접 부호의 개략도

이것은 부호 연접의 그림 표현이며, 특히 n=q=4, k=2인 리드-솔로몬 부호가 외부 부호로 사용되고 n=q, k=log q인 아다마르 부호가 내부 부호로 사용된다. 전체적으로 연접 부호는 ${\displaystyle [q^{2},k\log q]}$ 부호이다.

C_in이 [n, k, d] 부호, 즉 알파벳 A에 대한 길이 n, 차원 k, 최소 해밍 거리 d, 부호율 r = k/n인 블록 부호라고 하자.

${\displaystyle C_{in}:A^{k}\rightarrow A^{n}}$

|B| = |A|^k 기호를 가진 알파벳 B에 대한 C_out이 [N, K, D] 부호라고 하자.

${\displaystyle C_{out}:B^{K}\rightarrow B^{N}}$

내부 부호 C_in은 |A|^k = |B| 가능한 입력 중 하나를 받아 A에 대한 n-튜플로 인코딩하고, 전송하며, |B| 가능한 출력 중 하나로 디코딩한다. 우리는 이것을 알파벳 B의 한 기호를 전송할 수 있는 (슈퍼) 채널로 간주한다. 이 채널을 N번 사용하여 C_out의 코드워드에 있는 N개의 각 기호를 전송한다. C_out (외부 부호)와 C_in (내부 부호)의 연접, C_out${\displaystyle \circ }$C_in은 따라서 알파벳 A에 대한 길이 Nn의 부호이다.^[1]

${\displaystyle C_{out}\circ C_{in}:A^{kK}\rightarrow A^{nN}}$

각 입력 메시지 m = (m₁, m₂, ..., m_K)를 코드워드 (C_in(m'₁), C_in(m'₂), ..., C_in(m'_N))로 매핑한다. 여기서 (m'₁, m'₂, ..., m'_N) = C_out(m₁, m₂, ..., m_K)이다.

이 접근 방식의 핵심 통찰력은 C_in이 최대 우도 접근 방식을 사용하여 디코딩되고 (따라서 길이가 증가함에 따라 기하급수적으로 감소하는 오류 확률을 보임), C_out이 N = 2^nr 길이를 가지며 N의 다항 시간에 디코딩될 수 있는 부호일 때, 연접 부호는 결합된 길이 n2^nr = O(N⋅log(N))의 다항 시간에 디코딩될 수 있으며, C_in이 기하급수적인 디코딩 복잡도를 가지더라도 기하급수적으로 감소하는 오류 확률을 보인다는 것이다.^[1] 이는 연접 부호 디코딩 섹션에서 더 자세히 논의된다.

위의 연접의 일반화에서 N개의 가능한 내부 부호 C_in,i가 있고, C_out의 코드워드에 있는 i번째 기호는 i번째 내부 부호를 사용하여 내부 채널을 통해 전송된다. 유스테센 부호는 외부 부호가 리드-솔로몬 부호인 일반화된 연접 부호의 예시이다.

속성

1. 연접 부호 C_out${\displaystyle \circ }$C_in의 거리는 최소 dD이다. 즉, D' ≥ dD인 [nN, kK, D'] 부호이다.

증명: 두 개의 다른 메시지 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})_{i}))\geq d.}$

결과적으로 두 코드워드가 다른 알파벳 A에서 가져온 n⋅N개 기호 시퀀스에는 적어도 d⋅D개의 위치가 존재하므로

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

2. C_out과 C_in이 선형 블록 부호라면, C_out${\displaystyle \circ }$C_in도 선형 블록 부호이다.

이 속성은 C_out과 C_in의 생성 행렬을 사용하여 연접 부호의 생성 행렬을 정의하는 아이디어를 기반으로 쉽게 보여줄 수 있다.

연접 부호 디코딩

연접 부호의 디코딩 알고리즘에 대한 자연스러운 개념은 먼저 내부 부호를 디코딩한 다음 외부 부호를 디코딩하는 것이다. 알고리즘이 실용적이기 위해서는 최종 블록 길이에 대해 다항 시간이어야 한다. 외부 부호에 대한 다항 시간 고유 디코딩 알고리즘이 있다고 가정하자. 이제 내부 부호에 대한 다항 시간 디코딩 알고리즘을 찾아야 한다. 여기서 다항 시간 실행 시간은 최종 블록 길이에 대한 다항식임을 의미한다. 주요 아이디어는 내부 블록 길이가 외부 부호 크기에 대해 로그로 선택되면 내부 부호에 대한 디코딩 알고리즘이 내부 블록 길이의 지수 시간으로 실행될 수 있으며, 따라서 내부 부호에 대해 지수 시간이지만 최적인 최대 우도 디코더 (MLD)를 사용할 수 있다는 것이다.

자세히 말하면, 디코더의 입력이 벡터 y = (y₁, ..., y_N) ∈ (Aⁿ)^N이라고 하자. 그러면 디코딩 알고리즘은 두 단계 프로세스이다.

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) (즉, 다항 시간)이다. 두 번째 단계의 외부 디코딩 알고리즘이 다항 시간에 실행된다고 가정했으므로 전체 디코딩 알고리즘의 복잡도 또한 다항 시간이다.

참고

위에서 설명한 디코딩 알고리즘은 dD/4 미만의 모든 오류를 수정하는 데 사용될 수 있다. 최소 거리 디코딩을 사용하면 외부 디코더는 D/2 미만의 오류 기호 y'_i를 가진 모든 입력 y'를 수정할 수 있다. 마찬가지로, 내부 부호는 d/2 미만의 내부 기호가 오류인 경우 입력 y_i를 안정적으로 수정할 수 있다. 따라서 내부 디코딩 후 외부 기호 y'_i가 올바르지 않으려면 최소한 d/2개의 내부 기호가 오류였어야 하며, 외부 부호가 실패하려면 이것이 최소한 D/2개의 외부 기호에 대해 발생했어야 한다. 결과적으로, 연접 부호가 실패하기 위해 잘못 수신되어야 하는 총 내부 기호 수는 최소 d/2⋅D/2 = dD/4이다.

알고리즘은 내부 부호가 다른 경우에도 작동한다. 예를 들어 유스테센 부호의 경우이다. 포니가 개발한 일반화된 최소 거리 디코딩 알고리즘은 dD/2 오류까지 수정할 수 있다.^[2] 이것은 내부 부호의 소거 정보를 사용하여 외부 부호의 성능을 향상시켰으며, 소프트 결정 디코딩을 사용하는 알고리즘의 첫 번째 예시였다.^[3][4]

응용

간단한 연접 방식은 1971년 마리너 화성 탐사선 임무를 위해 이미 구현되었지만,^[5] 연접 부호는 1977년에 두 대의 우주 탐사선을 발사한 보이저 계획으로 심우주 통신에 정기적으로 사용되기 시작했다.^[6] 그 이후로 연접 부호는 효율적인 오류 정정 부호의 핵심 기술이 되었고, 적어도 터보 부호와 저밀도 패리티 검사 부호가 발명될 때까지 그렇게 유지되었다.^[5][6]

일반적으로 내부 부호는 블록 부호가 아니라 짧은 구속 길이를 가진 소프트 결정 콘볼루션 비터비 디코딩 부호이다.^[7] 외부 부호에는 더 긴 하드 결정 블록 부호, 종종 8비트 기호를 사용하는 리드-솔로몬 부호가 사용된다.^[1][5]더 큰 기호 크기는 외부 부호를 채널 손상으로 인해 발생할 수 있는 오류 버스트에 더 강하게 만들고, 콘볼루션 부호 자체의 오류 출력이 버스티하기 때문이기도 하다.^[1][5] 인터리빙 계층은 일반적으로 오류 버스트를 더 넓은 범위로 분산시키기 위해 두 부호 사이에 추가된다.^[5]

내부 비터비 콘볼루션 부호와 외부 리드-솔로몬 부호 (RSV 부호로 알려짐)의 조합은 보이저 2호에서 처음 사용되었으며,^[5][8] 우주 분야 안팎에서 인기 있는 구조가 되었다. 이는 DVB-S 디지털 텔레비전 방송 표준과 같은 위성 통신에 오늘날까지도 사용되고 있다.^[9]

더 넓은 의미에서 두 개 이상의 코드의 (직렬) 조합은 연접 코드로 지칭될 수 있다. 예를 들어, DVB-S2 표준 내에서 고효율 저밀도 패리티 검사 부호는 내부 LDPC 코드의 고유한 오류 플로어로 인해 남은 잔류 오류를 제거하기 위해 대수적 외부 코드와 결합된다.^[10]

간단한 연접 방식은 컴팩트 디스크(CD)에서도 사용되는데, 여기서 서로 다른 크기의 두 리드-솔로몬 부호 사이에 인터리빙 계층이 오류를 다양한 블록에 걸쳐 분산시킨다.

터보 부호: 병렬 연접 접근 방식

위의 설명은 현재 직렬 연접 부호라고 불리는 것에 대한 것이다. 1993년에 처음 설명된 터보 부호는 두 콘볼루션 부호의 병렬 연접을 구현했는데, 두 부호 사이에 인터리버와 부호 간에 정보를 주고받는 반복 디코더를 사용했다.^[6] 이 설계는 이전에 고안된 어떤 연접 부호보다 더 나은 성능을 보여준다.

그러나 터보 부호의 핵심 측면은 반복 디코딩 접근 방식이다. 반복 디코딩은 이제 직렬 연접 콘볼루션 부호(SCCC)와 같이 더 높은 코딩 이득을 얻기 위해 직렬 연접에도 적용된다. 반복 디코딩의 초기 형태는 갈릴레오 탐사선의 "갈릴레오 부호"에서 2~5회 반복으로 구현되었다.^[5]

같이 보기

• 길버트-바샴 경계
• 유스테센 부호
• 싱글턴 경계
• 자블로프 경계