연결 오류 수정 코드

Concatenated error correction code

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

배경

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

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

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

설명

내부 코드와 외부 코드에 작성된 연결 코드의 개략적인 묘사.
이것은 코드 결합을 그림으로 표현한 것으로, 특히 n=q=4와 k=2를 가진 리드-솔로몬코드를 외부코드로, n=q와 k=logq를 가진 하다마드코드를 내부코드로 사용한다. 전체적으로 연결 코드는 [ ,k -code이다.

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

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

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

각 입력 메시지 m = (m12, m, ..., mK)을 코드 워드(Cin(m),1 Cin(m),2 ..., Cin(m')N에 매핑하며, 여기서 (m',1 m',2 m', ..., m')N = C(m1, m, m, ..., mK) = Cout(m, m2, m)이다.

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

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

특성.

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

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

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

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

2. Cout Cin 선형 블록 코드라면 C cCoutin 선형 블록 코드다.

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

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

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

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

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

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

언급

위에서 설명한 디코딩 알고리즘은 숫자로 dD/4 미만까지의 모든 오류를 수정하는 데 사용할 수 있다. 최소 거리 디코딩을 사용하여 외부 디코더는 오류 발생 D/2 기호 y'i 미만으로 모든 입력 y'를 수정할 수 있다. 마찬가지로, d/2 미만의 내부 기호가 잘못되었을 경우 내부 코드가 입력 yi 신뢰성 있게 수정할 수 있다. 따라서 내부 디코딩 후 외부 기호 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]

참고 항목

참조

  1. ^ a b c d e G. D. Forney (1967). "Concatenated codes". Cambridge, Massachusetts: MIT Press. {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
  2. ^ Forney, G. David (April 1966). "Generalized Minimum Distance Decoding". IEEE Transactions on Information Theory. 12 (2): 125–131. doi:10.1109/TIT.1966.1053873.
  3. ^ Yu, Christopher C.H.; Costello, Daniel J. (March 1980). "Generalized Minimum Distance Decoding for Qary Output Channels". IEEE Transactions on Information Theory. 26 (2): 238–243. doi:10.1109/TIT.1980.1056148.
  4. ^ Wu, Yingquan; Hadjicostis, Christoforos (January 2007). "Soft-Decision Decoding of Linear Block Codes Using Preprocessing and Diversification". IEEE Transactions on Information Theory. 53 (1): 387–393. doi:10.1109/tit.2006.887478.
  5. ^ a b c d e f g Robert J. McEliece; Laif Swanson (20 August 1993). "Reed–Solomon Codes and the Exploration of the Solar System". JPL. {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
  6. ^ a b c K. Andrews 외, 2007년 11월, IEEE 95, 11번, 심우주 응용을 위한 터보LDPC 코드 개발
  7. ^ J. P. Odenwalder (1970). "Optimal decoding of convolutional codes". U.C.L.A., Systems Science Dept. (dissertation). {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
  8. ^ R. Ludwig, J. Taylor, Voyager Telecommunications Manual, JPL DESKANSO(Design and Performance Summary Series), 2002년 3월.
  9. ^ 디지털 비디오 방송 (DVB); 11/12 GHz 위성 서비스에 대한 프레임 구조, 채널 코딩 변조, ETSI EN 300 421, V1.1.2, 1997년 8월.
  10. ^ DVB(디지털 비디오 방송); 방송, 대화형 서비스, 뉴스 수집기타 광대역 위성 애플리케이션(DVB-S2)을 위한 2세대 프레임 구조, 채널 코딩 변조 시스템, ETSI EN 302 307, V1.2.1, 2009년 4월.

추가 읽기

외부 링크