오류 정정 부호

컴퓨팅, 원거리 통신, 정보 이론, 부호 이론에서 전방 오류 정정(forward error correction, FEC) 또는 채널 코딩(channel coding)^[1]^[2]^[3]은 신뢰할 수 없거나 잡음이 많은 통신 채널을 통해 데이터 전송에서 오류를 제어하는 데 사용되는 기술이다.

핵심 아이디어는 송신자가 메시지를 여유있게 인코딩하는 것으로, 대부분 오류 정정 부호 또는 오류 정정 부호(ECC)를 사용한다.^[4]^[5] 여유도를 통해 수신자는 메시지 어디에서든 발생할 수 있는 오류를 감지할 수 있을 뿐만 아니라 종종 제한된 수의 오류를 수정할 수 있다. 따라서 재전송을 요청하는 역방향 채널이 필요하지 않을 수 있다. 비용은 고정된 더 높은 전방 채널 대역폭이다.

미국의 수학자 리처드 해밍은 1940년대에 이 분야를 개척했으며 1950년에 최초의 오류 정정 부호인 해밍 (7,4) 부호를 발명했다.^[5]

FEC는 재전송 비용이 많이 들거나 불가능한 상황(예: 단방향 통신 링크 또는 멀티캐스트에서 여러 수신자로 전송하는 경우)에 적용될 수 있다.

장시간 지연 연결도 이점을 얻는다. 멀리 떨어진 행성 궤도를 도는 위성의 경우, 오류로 인한 재전송은 몇 시간의 지연을 초래한다. FEC는 모뎀과 셀룰러 네트워크에서도 널리 사용된다.

수신기의 FEC 처리는 디지털 비트 스트림에 적용되거나 디지털 변조된 캐리어의 복조에 적용될 수 있다. 후자의 경우, FEC는 수신기에서 초기 아날로그-디지털 변환의 필수적인 부분이다. 비터비 디코더는 잡음으로 손상된 아날로그 신호에서 디지털 데이터를 복조하기 위해 연판정 알고리즘을 구현한다. 많은 FEC 디코더는 비트 오류율(BER) 신호를 생성할 수도 있으며, 이는 아날로그 수신 전자 장치를 미세 조정하는 피드백으로 사용될 수 있다.

FEC 정보는 손상된 데이터를 복구할 수 있도록 대용량 스토리지 (자기, 광학 및 솔리드 스테이트/플래시 기반) 장치에 추가되며, 신뢰성을 위해 특별한 조치가 필요한 시스템에서 ECC 컴퓨터 메모리로 사용된다.

수정할 수 있는 최대 오류 또는 누락된 비트의 비율은 ECC 설계에 따라 결정되므로, 다른 전방 오류 정정 부호는 다른 조건에 적합하다. 일반적으로 강력한 부호는 사용 가능한 대역폭을 사용하여 전송해야 하는 더 많은 여유도를 유도하여 유효 비트율을 감소시키면서 수신된 유효 신호 대 잡음비를 향상시킨다. 클로드 섀넌의 잡음 채널 부호화 정리는 주어진 최대 허용 오류 확률에 대해 달성 가능한 최대 통신 대역폭을 계산하는 데 사용될 수 있다. 이는 주어진 기본 잡음 수준을 가진 채널의 이론적 최대 정보 전송 속도에 대한 한계를 설정한다. 그러나 이 증명은 건설적이지 않으므로 용량 달성 부호를 구축하는 방법에 대한 통찰력을 제공하지 않는다. 수년간의 연구 끝에 극 부호^[3]와 같은 일부 고급 FEC 시스템은 무한 길이 프레임의 가설 하에 섀넌 채널 용량에서 주어지는 이론적 최대값에 매우 가깝다.

Remove ads

방법

요약

관점

ECC는 알고리즘을 사용하여 전송되는 정보에 여유성을 추가함으로써 달성된다. 중복 비트는 많은 원래 정보 비트의 복잡한 함수일 수 있다. 원래 정보는 인코딩된 출력에 문자 그대로 나타날 수도 있고 나타나지 않을 수도 있다. 수정되지 않은 입력을 출력에 포함하는 부호는 체계적 부호인 반면, 그렇지 않은 부호는 비체계적 부호이다.

ECC의 간단한 예는 각 데이터 비트를 세 번 전송하는 것으로, 이를 (3,1) 반복 부호라고 한다. 잡음이 많은 채널을 통해 수신자는 아래 표와 같이 8가지 버전의 출력을 볼 수 있다.

자세한 정보 수신된 삼중항, 해석 ...

수신된 삼중항	해석
000	0 (오류 없음)
001	0
010	0
100	0
111	1 (오류 없음)
110	1
101	1
011	1

이를 통해 세 샘플 중 하나에 있는 오류를 "다수결 투표" 또는 "민주적 투표"를 통해 수정할 수 있다. 이 ECC의 수정 능력은 다음과 같다:

삼중항의 최대 한 비트 오류, 또는
삼중항의 최대 두 비트 누락(표에 표시되지 않은 경우).

구현하기 간단하고 널리 사용되지만, 이 삼중 모듈 중복성은 상대적으로 비효율적인 ECC이다. 더 나은 ECC 코드는 일반적으로 현재의 소수의 비트(일반적으로 2~8비트 그룹)를 디코딩하는 방법을 결정하기 위해 이전의 수십 또는 수백 비트를 검사한다.

오류 감소를 위한 잡음 평균화

ECC는 "잡음 평균화"를 통해 작동한다고 말할 수 있다. 각 데이터 비트는 여러 전송된 기호에 영향을 미치므로, 잡음에 의한 일부 기호의 손상은 일반적으로 동일한 사용자 데이터에 의존하는 다른 손상되지 않은 수신 기호에서 원래 사용자 데이터를 추출할 수 있게 한다.

이러한 "위험 풀링" 효과 때문에 ECC를 사용하는 디지털 통신 시스템은 특정 최소 신호 대 잡음비 이상에서 잘 작동하고 그 이하에서는 전혀 작동하지 않는 경향이 있다.
이러한 일방적인 경향, 즉 낭떠러지 효과는 이론적인 섀넌 한계에 더 가까이 다가가는 더 강력한 코드가 사용될수록 더욱 두드러진다.
ECC 코딩된 데이터를 인터리빙하면 채널 오류가 버스트로 발생하는 경향이 있을 때 전송된 ECC 코드의 일방적인 특성을 줄일 수 있다. 그러나 이 방법에는 한계가 있다. 협대역 데이터에 가장 잘 사용된다.

대부분의 통신 시스템은 예상되는 최악의 비트 오류율을 허용하도록 설계된 고정 채널 부호를 사용하며, 비트 오류율이 더 나빠지면 전혀 작동하지 않는다. 그러나 일부 시스템은 주어진 채널 오류 조건에 적응한다. 일부 하이브리드 자동 반복 요청 사례는 ECC가 오류율을 처리할 수 있는 한 고정 ECC 방식을 사용하다가 오류율이 너무 높아지면 ARQ로 전환한다. 적응 변조 및 코딩은 다양한 ECC 속도를 사용하여, 채널에 오류율이 높을 때 패킷당 더 많은 오류 정정 비트를 추가하거나 필요하지 않을 때 제거한다.

Remove ads

종류

요약

관점

ECC 부호의 두 가지 주요 범주는 블록 부호와 컨볼루션 부호이다.

블록 부호는 미리 정해진 크기의 고정 크기 비트 또는 기호 블록(패킷)에 대해 작동한다. 실제 블록 부호는 일반적으로 블록 길이에 대해 다항 시간에 하드 디코딩될 수 있다.
컨볼루션 부호는 임의 길이의 비트 또는 기호 스트림에 대해 작동한다. 다른 알고리즘이 가끔 사용되기는 하지만, 대부분 비터비 알고리즘으로 연판정 디코딩된다. 비터비 디코딩은 컨볼루션 부호의 제약 길이가 증가함에 따라 점근적으로 최적의 디코딩 효율을 허용하지만, 지수 시간적으로 증가하는 복잡성을 대가로 한다. 종단된 컨볼루션 부호 또한 입력 데이터 블록을 인코딩한다는 점에서 '블록 부호'이지만, 컨볼루션 부호의 블록 크기는 일반적으로 임의적인 반면, 블록 부호는 대수적 특성에 의해 결정되는 고정된 크기를 갖는다. 컨볼루션 부호의 종단 유형에는 "꼬리 물기(tail-biting)" 및 "비트 플러싱(bit-flushing)"이 있다.

고전적인 블록 부호는 일반적으로 하드 결정 알고리즘을 사용하여 디코딩된다.^[6] 이는 모든 입력 및 출력 신호에 대해 1 또는 0 비트에 해당하는지 여부를 하드 결정한다는 의미이다. 이와 대조적으로, 컨볼루션 부호는 일반적으로 비터비, MAP 또는 BCJR 알고리즘과 같은 연판정 알고리즘을 사용하여 디코딩되며, 이는 (이산화된) 아날로그 신호를 처리하고 하드 결정 디코딩보다 훨씬 높은 오류 정정 성능을 제공한다.

거의 모든 고전적인 블록 부호는 유한체의 대수적 특성을 적용한다. 따라서 고전적인 블록 부호는 종종 대수적 부호라고 불린다.

블록 부호

다양한 유형의 블록 부호가 있다. 리드 솔로몬 부호는 콤팩트 디스크, DVD 및 하드 디스크 드라이브에서 널리 사용되는 것으로 유명하다. 고전적인 블록 부호의 다른 예로는 골레, BCH, 다차원 패리티 및 해밍 부호가 있다.

해밍 ECC는 일반적으로 ECC 메모리 및 초기 SLC NAND 플래시 메모리 오류를 수정하는 데 사용된다.^[7] 이는 단일 비트 오류 정정 및 2비트 오류 감지를 제공한다. 해밍 부호는 보다 신뢰할 수 있는 단일 레벨 셀 (SLC) NAND에만 적합하다. 더 밀도 높은 멀티 레벨 셀 (MLC) NAND는 BCH, 리드-솔로몬 또는 LDPC와 같은 다중 비트 정정 ECC를 사용할 수 있다.^[8]^[9]^[10] NOR 플래시는 일반적으로 어떤 오류 정정도 사용하지 않는다.^[8]

연판정 부호

저밀도 패리티 검사 (LDPC)

저밀도 패리티 검사 부호 (LDPC) 부호는 많은 단일 패리티 검사 (SPC) 부호로 구성된 매우 효율적인 선형 블록 부호의 한 종류이다. 블록 길이에 대해 선형 시간 복잡도로 반복적인 연판정 디코딩 접근 방식을 사용하여 채널 용량 (이론적 최대값)에 매우 가까운 성능을 제공할 수 있다. 실제 구현은 구성 SPC 부호의 병렬 디코딩에 크게 의존한다.

LDPC 부호는 1960년 로버트 G. 갈라거의 박사 학위 논문에서 처음 소개되었지만, 인코더 및 디코더 구현의 계산 노력과 리드 솔로몬 부호의 도입으로 인해 1990년대까지는 거의 무시되었다.

LDPC 부호는 현재 DVB-S2 (디지털 비디오 방송 – 위성 – 2세대), 와이맥스 (IEEE 802.16e 전자레인지 통신 표준), 고속 무선 LAN (IEEE 802.11n)^[11], 10GBase-T 이더넷 (802.3an) 및 G.hn/G.9960 (ITU-T 전력선, 전화선 및 동축 케이블을 통한 네트워킹 표준)과 같은 많은 최신 고속 통신 표준에서 사용된다. 다른 LDPC 부호는 3GPP MBMS 내의 무선 통신 표준으로 표준화되어 있다 (분수 부호 참조).

터보 부호

터보 부호화는 두 개 이상의 비교적 간단한 컨볼루션 부호와 인터리버를 결합하여 섀넌 한계의 1데시벨 이내로 작동할 수 있는 블록 부호를 생성하는 반복적인 연판정 디코딩 방식이다. 실제 적용 측면에서 LDPC 부호보다 앞서 등장했으며, 현재 유사한 성능을 제공한다.

터보 부호화의 초기 상업적 응용 중 하나는 퀄컴이 개발하고 버라이즌 와이어리스, 스프린트 넥스텔, 기타 통신사가 판매한 CDMA2000 1x (TIA IS-2000) 디지털 셀룰러 기술이었다. 또한 인터넷 접속을 위한 CDMA2000 1x의 진화형인 1xEV-DO (TIA IS-856)에도 사용된다. 1x와 마찬가지로 EV-DO는 퀄컴이 개발했으며, 버라이즌 와이어리스, 스프린트 넥스텔, 기타 통신사가 판매한다 (버라이즌의 1xEV-DO 마케팅 명칭은 브로드밴드 액세스이며, 스프린트의 소비자 및 비즈니스 1xEV-DO 마케팅 명칭은 각각 파워 비전 및 모바일 브로드밴드이다).

Remove ads

ECC 성능 설명

요약

관점

오류 감지 또는 오류 정정 능력을 종종 명시하는 고전적인 블록 부호와 달리, 저밀도 패리티 검사 부호와 같은 많은 현대 블록 부호는 그러한 보증이 부족하다. 대신, 현대 부호는 비트 오류율 측면에서 평가된다.

대부분의 전방 오류 정정 부호는 비트 삽입이나 비트 삭제가 아닌 비트 뒤집힘만 수정한다. 이 설정에서 해밍 거리는 비트 오류율을 측정하는 적절한 방법이다. 몇몇 전방 오류 정정 부호는 마커 부호 및 워터마크 부호와 같이 비트 삽입 및 비트 삭제를 수정하도록 설계되었다. 레벤슈타인 거리는 이러한 부호를 사용할 때 비트 오류율을 측정하는 더 적절한 방법이다. ^[12]

부호율과 신뢰성 및 데이터 전송률 간의 절충

ECC의 기본 원리는 디코더가 송신기에서 인코딩된 실제 메시지를 찾아내는 데 도움이 되도록 중복 비트를 추가하는 것이다. 주어진 ECC 시스템의 부호율은 정보 비트 수와 주어진 통신 패키지 내의 총 비트 수(즉, 정보 비트 + 중복 비트) 간의 비율로 정의된다. 따라서 부호율은 실수이다. 0에 가까운 낮은 부호율은 좋은 성능을 달성하기 위해 많은 중복 비트를 사용하는 강력한 부호를 의미하며, 1에 가까운 큰 부호율은 약한 부호를 의미한다.

정보를 보호하는 중복 비트는 보호하려는 동일한 통신 자원을 사용하여 전송되어야 한다. 이는 신뢰성과 데이터 전송률 간의 근본적인 절충을 야기한다.^[13] 한 극단에서는 강력한 부호(낮은 부호율)가 수신기 SNR(신호 대 잡음비)에서 상당한 증가를 유도하여 비트 오류율을 감소시키지만, 유효 데이터 전송률을 감소시키는 대가를 치른다. 다른 극단에서는 ECC를 전혀 사용하지 않는 것(즉, 부호율이 1인 것)은 정보 전송 목적으로 전체 채널을 사용하지만, 비트에 추가적인 보호를 제공하지 않는 대가를 치른다.

한 가지 흥미로운 질문은 다음과 같다. 무시할 만한 디코딩 오류율을 가진 ECC가 정보 전송 측면에서 얼마나 효율적일 수 있는가? 이 질문은 클로드 섀넌이 그의 두 번째 정리에서 답변했으며, 채널 용량은 오류율이 0으로 수렴하는 모든 ECC가 달성할 수 있는 최대 비트 전송률이라고 말한다.^[14] 그의 증명은 실제 응용에 적합하지 않은 가우스 무작위 부호화에 의존한다. 섀넌의 연구에서 제시된 상한은 궁극적인 성능 한계에 근접할 수 있는 ECC를 설계하는 오랜 여정에 영감을 주었다. 오늘날 다양한 부호는 거의 섀넌 한계에 도달할 수 있다. 그러나 용량 달성 ECC는 일반적으로 구현하기가 매우 복잡하다.

가장 인기 있는 ECC는 성능과 계산 복잡성 사이에 절충점이 있다. 일반적으로 해당 매개변수는 시나리오에 따라 최적화될 수 있는 가능한 코드율 범위를 제공한다. 일반적으로 이 최적화는 데이터 전송률에 대한 영향을 최소화하면서 낮은 디코딩 오류 확률을 달성하기 위해 수행된다. 코드율을 최적화하는 또 다른 기준은 낮은 오류율과 재전송 횟수를 균형 있게 맞춰 통신 에너지 비용을 달성하는 것이다.^[15]

부호의 지역 디코딩 및 테스트

때로는 메시지의 단일 비트만 디코딩하거나, 주어진 신호가 코드워드인지 확인해야 하며, 이 모든 작업을 전체 신호를 보지 않고 수행해야 할 때가 있다. 이는 스트리밍 환경에서 코드워드가 너무 커서 고전적으로 충분히 빠르게 디코딩할 수 없고 메시지의 일부 비트만 지금 당장 관심 대상인 경우에 의미가 있을 수 있다. 또한 이러한 부호는 계산 복잡도 이론에서 중요한 도구가 되었으며, 예를 들어 확률적으로 검증 가능한 증명 설계를 위한 것이다.

지역 디코딩 가능 부호는 코드워드가 일부 일정한 비율의 위치에서 손상된 후에도 코드워드의 작은(예: 상수) 수의 위치만 보고 메시지의 단일 비트를 확률적으로 복구할 수 있는 오류 정정 부호이다. 지역 테스트 가능 부호는 신호의 작은 수의 위치만 보고 신호가 코드워드에 가까운지 확률적으로 확인할 수 있는 오류 정정 부호이다.

모든 지역 디코딩 가능 부호(LDC)가 지역 테스트 가능 부호(LTC)는 아니다.^[16] 또한 지역 수정 가능 부호(LCC)도 아니다.^[17] q-query LCC는 지수적으로 제한되는 반면^[18]^[19] LDC는 준지수 길이를 가질 수 있다.^[20]^[21]

Remove ads

성능 향상

요약

관점

연결(결합)

고전적인 (대수적) 블록 부호와 컨볼루션 부호는 짧은 제약 길이의 비터비 디코딩 컨볼루션 부호가 대부분의 작업을 수행하고 더 큰 심볼 크기와 블록 길이를 가진 블록 부호(일반적으로 리드-솔로몬)가 컨볼루션 디코더가 만든 오류를 "정리"하는 연결된 코딩 방식에서 자주 결합된다. 이 오류 정정 부호 계열을 사용한 단일 패스 디코딩은 매우 낮은 오류율을 산출할 수 있지만, 장거리 전송 조건(심우주와 같은)에서는 반복 디코딩이 권장된다.

연결 부호는 보이저 2호가 1986년 천왕성과의 조우에서 이 기술을 처음 사용한 이후 위성 및 심우주 통신에서 표준 관행이었다. 갈릴레오 우주선은 안테나 고장으로 인한 매우 높은 오류율 조건을 보상하기 위해 반복 연결 부호를 사용했다.

인터리빙

인터리빙은 전방 오류 정정 부호의 성능을 향상시키기 위해 디지털 통신 및 저장 시스템에서 자주 사용된다. 많은 통신 채널은 메모리가 없다. 오류는 일반적으로 독립적으로 발생하기보다는 버스트로 발생한다. 코드 워드 내의 오류 수가 오류 정정 부호의 기능을 초과하면 원래 코드 워드를 복구하지 못한다. 인터리빙은 여러 코드 워드에 걸쳐 소스 심볼을 섞음으로써 오류의 보다 균일한 분포를 생성하여 이 문제를 완화한다.^[22] 따라서 인터리빙은 버스트 오류 정정에 널리 사용된다.

터보 부호 및 저밀도 패리티 검사 부호와 같은 최신 반복 부호의 분석은 일반적으로 독립적인 오류 분포를 가정한다.^[23] 따라서 LDPC 부호를 사용하는 시스템은 일반적으로 코드 워드 내의 심볼 전반에 걸쳐 추가적인 인터리빙을 사용한다.^[24]

터보 부호의 경우 인터리버는 필수 구성 요소이며 올바른 설계는 좋은 성능에 매우 중요하다.^[22]^[25] 반복 디코딩 알고리즘은 디코더를 나타내는 팩터 그래프에 짧은 사이클이 없을 때 가장 잘 작동한다. 인터리버는 짧은 사이클을 피하기 위해 선택된다.

인터리버 설계는 다음과 같다:

직사각형 (또는 균일) 인터리버 (위에서 설명한 건너뛰기 계수를 사용하는 방법과 유사)
컨볼루션 인터리버
무작위 인터리버 (인터리버가 알려진 무작위 순열인 경우)
S-무작위 인터리버 (인터리버가 알려진 무작위 순열이지만, 거리 S 내의 입력 심볼이 출력에서 거리 S 내에 나타나지 않는 제약이 있음).^[26]
경합 없는 이차 순열 다항식 (QPP).^[27] 사용 예시는 3GPP 롱텀 에볼루션 이동통신 표준에 있다.^[28]

다중 캐리어 통신 시스템에서, 주파수 선택적 페이딩 또는 협대역 간섭을 완화하기 위해 주파수 다이버시티를 제공하도록 캐리어 간 인터리빙이 사용될 수 있다.^[29]

인터리빙 예시

인터리빙 없이 전송:

오류 없는 메시지:                                 aaaabbbbccccddddeeeeffffgggg
버스트 오류와 함께 전송:                    aaaabbbbccc____deeeeffffgggg

여기서 같은 글자 그룹은 4비트 1비트 오류 정정 코드 워드를 나타낸다. 코드 워드 cccc는 1비트가 변경되어 수정될 수 있지만, 코드 워드 dddd는 3비트가 변경되어 전혀 디코딩할 수 없거나 잘못 디코딩될 수 있다.

인터리빙과 함께:

오류 없는 코드 워드:                              aaaabbbbccccddddeeeeffffgggg
인터리빙됨:                                        abcdefgabcdefgabcdefgabcdefg
버스트 오류와 함께 전송:                    abcdefgabcd____bcdefgabcdefg
디인터리빙 후 수신된 코드 워드:           aa_abbbbccccdddde_eef_ffg_gg

각 코드 워드 "aaaa", "eeee", "ffff", "gggg"에서 단 한 비트만 변경되었으므로, 1비트 오류 정정 코드는 모든 것을 올바르게 디코딩할 것이다.

인터리빙 없이 전송:

원래 전송된 문장:                      ThisIsAnExampleOfInterleaving
버스트 오류와 함께 수신된 문장:               ThisIs______pleOfInterleaving

"AnExample"이라는 용어는 대부분 이해하기 어렵고 수정하기 어렵다.

인터리빙과 함께:

전송된 문장:                               ThisIsAnExampleOfInterleaving...
오류 없는 전송:                            TIEpfeaghsxlIrv.iAaenli.snmOten.
버스트 오류와 함께 수신된 문장:               TIEpfe______Irv.iAaenli.snmOten.
디인터리빙 후 수신된 문장:             T_isI_AnE_amp_eOfInterle_vin_...

어떤 단어도 완전히 손실되지 않았으며, 누락된 글자는 최소한의 추측으로 복구할 수 있다.

인터리빙의 단점

인터리빙 기술의 사용은 총 지연 시간을 증가시킨다. 이는 패킷을 디코딩하기 전에 전체 인터리빙된 블록이 수신되어야 하기 때문이다.^[30] 또한 인터리버는 오류의 구조를 숨긴다. 인터리버가 없으면 고급 디코딩 알고리즘이 오류 구조를 활용하여 인터리버와 결합된 간단한 디코더보다 더 신뢰할 수 있는 통신을 달성할 수 있다. 이러한 알고리즘의 예로는 신경망^[31] 구조를 기반으로 하는 것이 있다.

Remove ads