콘볼루션 코드

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "콘볼루션 코드" – 뉴스 · 신문 · 도서 · 학자 · JSTOR (2015년 5월) (이 템플릿 메시지 삭제 방법과 시기 학습)

통신에서, 콘볼루션 코드는 데이터 스트림에 부울 다항식 함수의 슬라이딩 적용을 통해 패리티 기호를 생성하는 오류 수정 코드의 일종이다. 슬라이딩 애플리케이션은 데이터 위에 있는 인코더의 '콘볼루션'을 나타내며, '콘볼루션 코딩'이라는 용어가 생겨난다. 경련 코드의 슬라이딩 특성은 시간 인바리어트 트렐리스를 사용하여 트렐리스 디코딩을 용이하게 한다. 시간 불변 트렐리스 디코딩은 경련 코드가 합리적인 복잡성으로 최대 우도 소프트 결정을 디코딩할 수 있도록 한다.

경제적 최대우도 소프트 의사결정 디코딩을 수행할 수 있는 능력은 수녀원 코드의 주요 이점 중 하나이다. 이는 일반적으로 시간변수 trellis로 표현되며 따라서 일반적으로 하드 결정으로 디코딩되는 고전적인 블록 코드와는 대조적이다. 콘볼루션 코드는 흔히 인코더의 기본 코드율과 깊이(또는 메모리)로 특징지어진다$$$[{\displaystyle n,}$ k${\displaystyle ,}$ ${\displaystyle k}$ ${\displaystyle ]}$ ${\displaystyle [n,$${\displaystyle k}$$,K]}.$ 기본 코드율은 일반적으로 $n{\displaystyle }$/ k ${\displaystyle n/k}$로 주어지는데$,$ 여기서 n은 원시 입력 데이터 속도, k는 출력 채널 인코딩 스트림의 데이터 속도다. 채널 코딩은 입력 비트에 중복성을 삽입하기 때문에 n이 k보다 작다. 메모리는 흔히 "기존 길이" K라고 부르는데, 여기서 출력은 $이전$의 ${\displaystyle \mathrm{K}}$ ${\displaystyle -}$ 1 ${\displaystyle K-1}$ 입력뿐만$$ 아니라 전류 입력의 함수다. 깊이는 다항식의 메모리 요소 수 v 또는 인코더의 가능한 최대 상태 수(일반적으로 : 2 ${\displaystyle v^{}}$ ${\$로도 지정할 수 있다.$$

콘볼루션 코드는 종종 연속적인 것으로 설명된다. 그러나 대부분의 실제 콘볼루션 인코딩은 데이터 블록에서 수행되기 때문에 콘볼루션 코드는 연속성이 아니라 임의 블록 길이를 갖는다고도 할 수 있다. 콘볼루션으로 인코딩된 블록 코드는 일반적으로 종료를 채택한다. 경련 코드의 임의 블록 길이는 일반적으로 대수적 특성에 의해 결정되는 고정 블록 길이를 갖는 고전적인 블록 코드와 대조될 수 있다.

경련 코드의 코드 속도는 일반적으로 기호 구멍을 통해 수정된다. 예를 들어, '어머니' 코드 $비율{\displaystyle }$n /${\displaystyle k}$ =${\displaystyle 1}$ / ${\displaystyle 2\mathrm{}}${\$displaystyle$n/$k=1/2}$을(를) 가진 합성 코드는 코드 기호 일부를 전송하지 않는 것만으로도$$ $7{\displaystyle \mathrm{}}$/ 8 ${\displaystyle 7/8}$의 ${\displaystyle 더\mathrm{}}$ 높은 비율로 구멍을 뚫을 수 있다$$. 펑크가 난 경련 코드의 성능은 일반적으로 전송되는 패리티의 양에 따라 잘 조정된다. 경련 코드의 블록 길이와 코드 비율 유연성뿐만 아니라 경련 코드에 대한 경제적 소프트 의사결정을 수행할 수 있는 능력은 디지털 통신에 매우 인기가 있다.

역사

콘볼루션 코드는 1955년 피터 엘리아스에 의해 도입되었다. 경련 코드는 계산과 지연을 희생하면서 임의의 품질로 해독될 수 있다고 생각되었다. 1967년에 앤드류 비테르비는 시간 불변 트렐리스 기반 디코더인 비테르비 알고리즘을 사용하여 합당한 복잡성과 함께 최대 우도를 디코딩할 수 있다고 결정했다. 다른 trellis 기반 디코더 알고리즘은 BCJR 디코딩 알고리즘을 포함하여 나중에 개발되었다.

1991년경 Claude Berrou에 의해 재귀적 체계적 경련 코드가 발명되었다. 이러한 코드는 터보 코드와 같은 연결된 코드의 처리를 포함한 반복 처리에 특히 유용하다는 것이 입증되었다.^[1]

"융합형" 용어를 사용하는 경우, 고전적인 경련 코드는 유한 충동 응답(FIR) 필터로 간주될 수 있고, 재귀성 경련 코드는 무한 충동 응답(IIIR) 필터로 간주될 수 있다.

콘볼루션 코드가 사용되는 경우

콘볼루션 코드는 디지털 비디오, 라디오, 모바일 통신(예: GSM, GPRS, Edge 및 3G 네트워크 (3GPP 릴리스 7까지))^[3][4]과 위성 통신과 같은 수많은 애플리케이션에서 신뢰성 있는 데이터 전송을 달성하기 위해 광범위하게 사용된다.^[5] 이러한 코드는 종종 하드 결정 코드, 특히 리드-솔로몬과 결합하여 구현된다. 터보 코드 이전에는 그러한 구조가 섀넌 한계치에 가장 근접한 가장 효율적인 것이었다.

콘볼루션 인코딩

데이터를 콘볼루션 방식으로 인코딩하려면 각각 하나의 입력 비트를 고정하는 k 메모리 레지스터로 시작하십시오. 달리 지정하지 않는 한 모든 메모리 레지스터는 0의 값으로 시작한다. 인코더에는 n modulo-2 추가자가 있다(모듈로 2 추가자는 단일 부울 XOR 게이트로 구현할 수 있으며, 여기서 논리는 0+0 = 0, 0+1 = 1, 1+0 = 0, 1+1 = 0), n 제너레이터 다항식(아래 그림 참조). 입력 비트 m은₁ 가장 왼쪽 레지스터에 공급된다. 제너레이터 다항식 및 나머지 레지스터의 기존 값을 사용하여 인코더는 n 기호를 출력한다. 이러한 기호는 원하는 코드 속도에 따라 전송되거나 뚫릴 수 있다. 이제 비트가 모든 레지스터 값을 오른쪽으로 이동(m이₁ m으로₀ 이동, m이₀ m으로₋₁ 이동)하고 다음 입력 비트를 기다린다. 입력 비트가 남아 있지 않으면 모든 레지스터가 0 상태(플루시 비트 터미네이션)로 돌아갈 때까지 인코더는 계속 이동한다.

아래 수치는 비율이다. 제약 조건 길이(k)가 3인 1⁄3 (½n) 인코더. 제너레이터 다항식은 G₁ = (1,1,1), G₂ = (0,1,1) 및₃ G = (1,0,1)이다. 따라서 출력 비트는 다음과 같이 계산된다(modulo 2)

n₁ = m₁ + m₀ + m₋₁

n₂ = m₀ + m₋₁

n₃ = m₁ + m₋₁.

콘볼루션 코드는 체계적이고 비체계적일 수 있다.

• 인코딩하기 전에 메시지 구조를 체계적으로 반복한다.

• 비지연으로 초기 구조 변경

비체계적 경련 코드는 소음 면역이 개선돼 더욱 인기가 높다. 그것은 수녀원 코드의 자유 거리와 관련이 있다.^[6]

• 

  비체계적 경련 코드의 짧은 그림.

• 

  체계적 경련 코드에 대한 짧은 삽화.

재귀 및 비재귀 코드

위 사진의 인코더는 비복구 인코더다. 여기 재귀적 사례의 예가 있으며, 따라서 피드백 구조를 인정한다.

입력 데이터가 출력 기호(출력 2)에도 사용되기 때문에 인코더의 예는 체계적이다. 입력 데이터를 포함하지 않는 출력 기호가 있는 코드를 비시스템적 코드라고 한다.

재귀 코드는 전형적으로 체계적이고 반대로 비재귀 코드는 전형적으로 비체계적이다. 그것은 엄격한 요구사항이 아니라 일반적인 관행이다.

Img. 2.의 예시 인코더는 3개의 레지스터가 8개의 가능한 인코더 상태³(2)를 생성하기 때문에 8개의 상태 인코더가 된다. 상응하는 디코더 트레일리스도 일반적으로 8개 주를 사용한다.

터보 코드에 사용하기 때문에 재귀적 체계적 경련(RSC) 코드는 더욱 대중화되었다. 재귀적 계통 코드는 사이비 계통 코드라고도 한다.

기타 RSC 코드 및 예시 애플리케이션은 다음과 같다.

LDPC 코드 구현에 유용하며, 직렬 연결 콘볼루션 코드(SCCC)의 내부 구성 코드로 유용하다.

SCCC 및 다차원 터보 코드에 유용함.

위성 링크와 같은 응용 프로그램에 대한 낮은 오류율 터보 코드의 구성 코드로 유용하다. SCCC 외부 코드로도 적합함.

임펄스 반응, 전달 함수 및 제약 조건 길이

콘볼루션 인코더는 다음과 같은 인코더의 충동 응답으로 입력 스트림의 콘볼루션을 수행하기 때문에 그렇게 불린다.

${\displaystyle y_{i}^{j}=\sum _{k=0}^{\infit }h_{k}^{j}x_{i-k}=(x*h^{j})[i],}$

여기서 x는 입력 시퀀스, y는^j 출력 j에서 나오는 시퀀스, h는^j 출력 j에 대한 임펄스 응답이며 and${\$는 콘볼루션을 나타낸다$$.

콘볼루션 인코더는 이산형 선형 시간 변화 시스템이다. 인코더의 모든 출력은 발전기 다항식과 밀접한 관련이 있는 자체 전송 기능으로 설명할 수 있다. 임펄스 응답은 Z 변환을 통해 전달 함수와 연결된다.

첫 번째(비복구) 인코더의 전송 기능은 다음과 같다.

• ${\displaystyle H_{1}(z)=1+z^{-1}+z^{-2},\,}$
• ${\displaystyle H_{2}(z)=z^{-1}+z^{-2},\,}$
• ${\displaystyle H_{3}(z)=1+z^{-2}\,}$

두 번째(재발적) 인코더의 전송 기능은 다음과 같다.

• ${\displaystyle H_{1}(z)={\frac {1+z^{-1}+z^{-3}{1-z^{1-z^{-2}}{1-z^{-3}}}{1-z^{-2}-z^{-3}}}},}$
• ${\displaystyle H_{2}(z)=1.\,}$

m 정의 기준

${\displaystyle m=\max _{i}\operatorname {폴리데그}(H_{i}(1/z))\,}$

여기서, 모든 ${\displaystyle \mathrm{합리적}}$인 함수 $f{\displaystyle }$( ${\displaystyle z}$)${\displaystyle }$= P${\displaystyle }$( ${\displaystyle z}$)${\displaystyle }$/ Q${\displaystyle }$( ${\displaystyle z}$) ${\$

${\displaystyle \mathrm{polydeg}}$ ${\displaystyle }$(${\displaystyle f}$)${\displaystyle }$= ${\displaystyle 최대}$(${\displaystyle \mathrm{deg}}$ ${\displaystyle }$( P${\displaystyle }$)${\displaystyle }$, ${\displaystyle \mathrm{deg}}$ ${\displaystyle }$(${\displaystyle Q}$)${\$

그 다음 m은 ${\displaystyle {Hi}_{}1}$/ z${\displaystyle }$) ${\$의 다항식 도수의 최대값이며, 제약조건 길이는 $K{\displaystyle }$= ${\displaystyle m}$+ ${\displaystyle 1}$ ${\$로 정의된다. 예를 들어, 첫 번째 예에서 제약조건 길이는 3이고, 두 번째 제약조건 길이는 4이다$.$

트렐리스 도표

콘볼루션 인코더는 유한한 상태 기계다. n개의 2진수 셀을 가진 인코더는 2개의ⁿ 상태를 가질 것이다.

인코더(Img.1, 위와 같은)가 왼쪽 메모리 셀(m)에 '1', 오른쪽 메모리 셀(m₀₋₁)에 '0'이 있다고 상상해 보십시오. (m은₁ 현재 값을 나타내기 때문에 실제로 메모리 셀이 아니다.) 우리는 그러한 주를 "10"으로 지정할 것이다. 입력 비트에 따르면 다음 방향에서 인코더는 "01" 상태 또는 "11" 상태로 변환할 수 있다. 모든 전환이 가능한 것은 아니라는 것을 알 수 있다(예: 디코더는 "10" 상태에서 "00" 상태로 변환하거나 심지어 "10" 상태로 유지될 수 없다).

가능한 모든 전환은 다음과 같이 표시할 수 있다.

실제 인코딩된 시퀀스는 이 그래프에서 경로로 나타낼 수 있다. 하나의 유효한 경로가 예로서 빨간색으로 표시된다.

이 다이어그램은 우리에게 디코딩에 대한 아이디어를 준다: 수신된 시퀀스가 이 그래프에 맞지 않으면, 오류가 발생하여, 우리는 가장 가까운 (그래프에 맞는) 시퀀스를 선택해야 한다. 진짜 해독 알고리즘은 이 아이디어를 이용한다.

자유 거리 및 오차 분포

자유 거리^[7](d)는 인코딩된 다른 시퀀스 사이의 최소 해밍 거리이다. 경련 코드의 교정 능력(t)은 코드로 교정할 수 있는 오류의 수입니다. 라고 계산할 수 있다.

${\displaystyle t=\좌측\l바닥 {\frac {d-1}{2}}\우측\표시장치 .}$

콘볼루션 코드는 블록을 사용하지 않고, 대신 연속 비트스트림을 처리하므로, t의 값은 상대적으로 서로 가까이에 위치한 많은 오류에 적용된다. 즉, t 오차의 여러 그룹은 비교적 멀리 떨어져 있을 때 대개 고칠 수 있다.

자유 거리는 콘볼루션 디코더의 출력에서 잘못된 "버스트"의 최소 길이로 해석할 수 있다. 오류가 "버스트"로 나타나는 사실은 내부 경련 코드로 연결된 코드를 설계할 때 설명되어야 한다. 이 문제에 대한 일반적인 해결책은 콘볼루션 인코딩 전에 데이터를 상호 보존하여 외부 블록(대개 리드-솔로몬) 코드가 대부분의 오류를 수정할 수 있도록 하는 것이다.

콘볼루션 코드 디코딩

콘볼루션 코드를 해독하기 위한 몇 가지 알고리즘이 존재한다. 상대적으로 작은 k 값의 경우, Viterbi 알고리즘은 최대우도 성능을 제공하고 매우 병렬적으로 사용할 수 있기 때문에 보편적으로 사용된다. Viterbi 디코더는 따라서 VLSI 하드웨어와 SIMD 명령 집합이 있는 CPU의 소프트웨어에서 구현하기 쉽다.

긴 제약 조건 길이 코드는 몇 가지 순차적 디코딩 알고리즘 중 어느 것으로든 더 실제적으로 디코딩되며, 그 중 Fano 알고리즘이 가장 잘 알려져 있다. 순차적 디코딩은 비테르비 디코딩과 달리 최대우도는 아니지만 제약조건 길이에 따라 복잡성이 약간만 증가하므로 강력하고 긴 길이의 코드를 사용할 수 있다. 그러한 코드는 1970년대 초 목성과 토성에 대한 파이오니어 프로그램에서 사용되었지만, 일반적으로 전체 비트-오류율 곡선을 경사진 큰 리드-솔로몬 오류 보정 코드로 결합되고 극도로 낮은 잔류 미검출 오류율을 생성하는 더 짧은 비테르비 코드에게 자리를 내주었다.

Viterbi와 순차적 디코딩 알고리즘은 둘 다 어려운 결정, 즉 가장 가능성이 높은 코드 워드를 형성하는 비트들을 반환한다. 소프트 출력 Viterbi 알고리즘을 사용하여 각 비트에 근사 신뢰도를 추가할 수 있다. 각 비트에 대한 최대 후미(MAP) 소프트 결정은 BCJR 알고리즘을 사용하여 얻을 수 있다.

인기 있는 합성 코드

사실, 과학 연구 중에 얻은 미리 정의된 합성 코드 구조가 산업에서 사용되고 있다. 이는 치명적인 경련 코드 선택 가능성과 관련이 있다(오류 수가 더 많다).

Voyager 프로그램이 제약 조건 길이 K와 비율 r의 1/2을 가지기 때문에 적어도 사용된, 특히 인기 있는 Viterbi-decd convolutional 코드.^[12]

Mars Pathfinder, Mars Discovery Rover 및 토성으로 가는 카시니 탐사선은 15의 K와 1/6의 비율을 사용하며, 이 코드는 256배의 디코딩 복잡성(Voyager 미션 코드와 비교했을 때)의 비용으로 단순한 $K{\displaystyle }$= ${\displaystyle 7}$ ${\displaystyle K=7}$ 코드보다$$ 약 2dB의 성능을 발휘한다.

GSM에서는 오차 보정 기법으로 제약 길이 2와 속도 1/2의 경련 코드가 사용된다.^[13]

펑크 난 경련 코드

어떤 코드 비율의 경련 코드는 다항식 선택에 기초하여 설계할 수 있지만,^[15] 실제로 필요한 코드 비율을 달성하기 위해 펑크 절차를 사용하는 경우가 많다. 펑크는 "기본" 저율(예: 1/n) 코드로 m/n 레이트 코드를 만드는 데 사용되는 기법이다. 인코더 출력에서 일부 비트를 삭제함으로써 달성된다. 비트는 펑크 행렬에 따라 삭제된다. 다음 펑크 행렬이 가장 많이 사용된다.

코드 레이트	펑크 행렬	자유 거리(NASA 표준 K=7 콘볼루션 코드의 경우)
1/2 (관류 없음)	1 1	10
2/3	1 0 1 1	6
3/4	1 0 1 1 1 0	5
5/6	1 0 1 0 1 1 1 0 1 0	4
7/8	1 0 0 0 1 0 1 1 1 1 1 0 1 0	3

예를 들어 위의 표에서 적절한 매트릭스를 사용하여 속도 2/3의 코드를 만들려면 기본 인코더 출력을 가져와 첫 번째 분기에서 모든 첫 번째 비트, 두 번째 분기에서 모든 비트를 전송해야 한다. 전송의 구체적인 순서는 각 통신 표준에 의해 정의된다.

예를 들어, INTELSAT 시스템과 디지털 비디오 방송과 같은 위성 통신에서 펑크 난 경련 코드가 널리 사용된다.

구멍이 난 경련 코드는 "상응"이라고도 불린다.

터보 코드: 콘볼루션 코드 교체

단순한 비테르비 디코딩 경련 코드는 현재 동일한 성능에 필요한 긴 경련 코드의 비테르비 알고리즘보다 훨씬 더 해독 복잡성이 적은 섀넌의 정리가 부과한 이론적 한계에 근접하는 새로운 종류의 반복된 짧은 경련 코드에 자리를 내주고 있다. 외부 대수 코드(예: 리드-솔로몬)와의 결합은 터보 코드 설계에 내재된 오류 층 문제를 다룬다.

참고 항목

• 양자 합성 코드

참조

• 이 문서에는 일반 서비스 관리 문서의 공용 도메인 자료가 포함되어 있다. "Federal Standard 1037C".

외부 링크

• 온라인 교과서: David J.C.에 의한 정보 이론, 추론 및 학습 알고리즘. 맥케이는 48장에서 콘볼루션 코드를 논한다.
• 오류 수정 코드(ECC) 페이지
• 매트랩 설명
• 디지털 통신 향상을 위한 컨볼루션 디코더의 기초
• 콘볼루션 코드(MIT)
• 정보이론과 부호화 (TU Ilmenau)는 48페이지의 콘볼루션 코드를 논한다.

추가 읽기