저밀도 패리티 검사 부호

저밀도 패리티 검사 부호 또는 저밀도 패리티 체크 코드(low-density parity-check code, LDPC)는 1990년대 후반부터 부호 이론과 정보 이론에서 명성을 얻은 오류 정정 부호의 한 종류이다(밀접하게 관련된 터보 부호와 함께). 오늘날 이 코드는 무선 통신부터 플래시 메모리 저장 장치에 이르는 다양한 응용 분야에서 널리 사용된다. 터보 코드와 함께 이들은 부호 이론에 혁명을 일으켰고, 전통적인 오류 정정 코드에 비해 성능을 몇 배 향상시켰다.

LDPC 부호 성능의 핵심은 반복적인 신뢰전파 디코딩 알고리즘에 대한 적응성이다. 이 알고리즘을 사용하면 낮은 계산 비용으로 많은 채널의 이론적 한계(채널 용량)에 접근하도록 설계할 수 있다.

이론적으로 LDPC 부호의 분석은 고정된 부호율과 증가하는 블록 길이를 가진 부호 시퀀스에 초점을 맞춘다. 이러한 시퀀스는 일반적으로 일련의 채널에 맞게 조정된다. 적절하게 설계된 시퀀스의 경우, 신뢰 전파에 따른 디코딩 오류는 채널 용량에 매우 가까운 속도에서 사라질 정도로 작게(블록 길이가 증가함에 따라 0에 가까워짐) 증명될 수 있다. 또한, 이는 블록 길이에 선형적인 복잡도로 달성될 수 있다.

이러한 이론적 성능은 희소한 태너 그래프(특수화된 이분 그래프)를 기반으로 하는 유연한 설계 방법으로 가능하다.

역사
LDPC 부호는 원래 로버트 G. 갤러거가 고안했으며 (따라서 갤러거 부호라고도 알려져 있다). 갤러거는 1960년 매사추세츠 공과대학교에서 박사 학위 논문에서 이 부호를 개발했다. 당시 이 부호는 반복적인 디코딩 알고리즘(선형 복잡도를 가짐에도 불구하고)이 사용 가능한 하드웨어에 비해 너무 많은 계산 비용이 들어 대부분 무시되었다.

1993년 밀접하게 관련된 터보 부호가 발명되면서 부호에 대한 관심이 다시 불붙었는데, 이는 비슷한 반복 디코딩 알고리즘이 당시 사용되던 다른 부호들을 능가했기 때문이다. LDPC 부호는 그 후 1996년에 재발견되었다. 초기에 산업계에서 터보 부호보다 LDPC 부호를 선호했던 이유는 터보 부호에 대한 특허 관련 제약 때문이었다. 발견 이후 LDPC 부호의 발전은 오류 바닥 및 높은 부호율 범위에서의 성능 면에서 터보 부호를 능가하여, 터보 부호는 낮은 부호율에서만 더 적합하게 되었다. 터보 부호의 근본적인 특허는 2013년에 만료되었지만, LDPC 부호는 여전히 기술적 장점 때문에 선호되고 있다.

LDPC 부호에 대한 이론적 관심은 수학적 분석에 대한 적합성에서도 비롯된다. 갤러거는 자신의 논문에서 LDPC 부호가 높은 확률로 이진 필드에서 길버트-바샴 경계선형 부호를 달성함을 보였다. 이진 소거 채널에서 부호 시퀀스는 채널 용량에 임의로 가까운 속도로 설계되었으며, 입증 가능한 소거 디코딩 오류 확률과 선형 디코딩 복잡도를 가졌다. 2020년에는 갤러거의 LDPC 부호가 목록 디코딩 용량을 달성하고 일반 필드에서 길버트-바샴 경계선형 부호도 달성하는 것으로 나타났다.

2013년부터 LDPC 부호는 다니엘 고테스만, 스트라스부르 대학교, 앨리스 & 밥(기업) 등이 입증한 바와 같이 오류를 수정하는 데 추가 큐비트가 거의 필요하지 않으므로 양자 컴퓨터의 오류를 수정하는 수단으로도 제안되었다.

응용
2003년, 불규칙 반복 누적 (IRA) 방식의 LDPC 부호가 6개의 터보 부호를 제치고 새로운 DVB-S2 디지털 텔레비전 표준의 오류 정정 부호가 되었다. DVB-S2 선정 위원회는 병렬 디코더 아키텍처 대신 훨씬 덜 효율적인 직렬 디코더 아키텍처를 사용하여 터보 부호 제안에 대한 디코더 복잡도 추정치를 만들었다. 이로 인해 터보 부호 제안은 LDPC 제안의 프레임 크기의 약 절반 정도의 프레임 크기를 사용해야 했다.

2008년, LDPC는 ITU-T G.hn 표준의 전방 오류 정정 (FEC) 시스템으로 컨볼루션 터보 부호를 이겼다. G.hn은 LDPC 부호를 터보 부호보다 선택했는데, 이는 LDPC 부호의 디코딩 복잡도가 낮고 (특히 1.0 Gbit/s에 가까운 데이터 속도에서 작동할 때) 제안된 터보 부호가 원하는 작동 범위에서 상당한 오류 바닥을 보였기 때문이다.

LDPC 부호는 또한 트위스트 페어 케이블을 통해 초당 10기가비트의 데이터를 전송하는 10기가비트 이더넷에도 사용된다. 2009년 현재 LDPC 부호는 와이파이 802.11 표준의 선택적 부분인 802.11n 및 802.11ac의 고속 처리량(HT) PHY 사양의 일부이기도 하다. LDPC는 802.11ax (Wi-Fi 6)의 필수적인 부분이다.

일부 OFDM 시스템은 낮은 비트 오류율에서도 LDPC 오류 정정 내부 코드를 통과하는 가끔 발생하는 오류("오류 바닥")를 수정하는 추가적인 외부 오류 정정 기능을 추가한다.

예를 들어: LDPC 부호 변조(RS-LCM)가 포함된 리드-솔로몬 부호는 리드-솔로몬 외부 부호를 사용한다. DVB-S2, DVB-T2, DVB-C2 표준은 모두 LDPC 디코딩 후 잔류 오류를 제거하기 위해 BCH 부호 외부 부호를 사용한다.

5G NR은 제어 채널에 극 부호를 사용하고 데이터 채널에 LDPC를 사용한다.

LDPC 부호는 상업용 하드 디스크 드라이브에서 성공을 거두었지만, SSD에서 오류 수정 기능을 완전히 활용하려면 기존과는 다른 미세한 플래시 메모리 감지가 필요하여 메모리 읽기 대기 시간이 증가한다. LDPC-in-SSD는 대기 시간 증가를 최소화하면서 SSD에 LDPC를 배포하는 효과적인 방법으로, LDPC-in-SSD를 현실화했다. 그 이후로 LDPC는 주요 스토리지 공급업체에 의해 소비자 및 엔터프라이즈 등급의 상업용 SSD에 널리 채택되었다. 많은 TLC(및 그 이후) SSD는 LDPC 부호를 사용하고 있다. 빠른 하드 디코딩(이진 소거)이 먼저 시도되며, 이는 더 느리지만 더 강력한 소프트 디코딩으로 되돌아갈 수 있다.

운용 사용

LDPC 부호는 기능적으로 희소한 패리티 검사 행렬로 정의된다. 이 성긴 행렬은 종종 희소성 제약 조건에 따라 무작위로 생성된다. LDPC 부호 구성은 나중에 논의된다. 이 부호는 1960년 로버트 갤러거에 의해 처음 설계되었다.

아래는 포니의 팩터 그래프 표기법을 사용한 예시 LDPC 부호의 그래프 조각이다. 이 그래프에서 상단에 있는 n개의 변수 노드는 하단에 있는 (n−k)개의 제약 노드에 연결된다.

이는 (n, k) LDPC 부호를 그래픽으로 표현하는 일반적인 방법이다. 그래프 상단의 'T'에 유효한 메시지의 비트가 놓이면 그래픽 제약 조건을 만족한다. 특히, 변수 노드('=' 기호가 있는 상자)에 연결되는 모든 선은 동일한 값을 가지며, 팩터 노드('+' 기호가 있는 상자)에 연결되는 모든 값은 모듈러 산술 2를 기준으로 합이 0이 되어야 한다 (다시 말해, 합이 짝수이거나 홀수 값의 개수가 짝수여야 한다).

none
그림 밖으로 나가는 선을 무시하면 유효한 코드워드에 해당하는 8개의 6비트 문자열이 가능하다 (즉, 000000, 011001, 110010, 101011, 111100, 100101, 001110, 010111). 이 LDPC 부호 조각은 3비트 메시지가 6비트로 인코딩된 것을 나타낸다. 여기서는 채널 오류로부터 복구할 가능성을 높이기 위해 중복을 사용한다. 이는 n = 6, k = 3인 (6, 3) 선형 부호이다.

다시 그림 밖으로 나가는 선을 무시하면, 이 그래프 조각을 나타내는 패리티 검사 행렬은 다음과 같다.

이 행렬에서 각 행은 세 개의 패리티 검사 제약 조건 중 하나를 나타내고, 각 열은 수신된 코드워드의 여섯 비트 중 하나를 나타낸다.

이 예시에서, 8개의 코드워드는 패리티 검사 행렬 H를 갈루아 체 GF(2)에서 기본 행 연산을 통해 형식으로 변환함으로써 얻을 수 있다.

1단계: H.

2단계: 1행을 3행에 더한다.

3단계: 2행과 3행을 교환한다.

4단계: 1행을 3행에 더한다.

이로부터 생성 행렬 G는 로 얻을 수 있다 (이것이 이진 코드인 특별한 경우 임을 유의하라). 구체적으로는 다음과 같다.

마지막으로, 가능한 모든 3비트 문자열 8개를 G에 곱하여 8개의 유효한 코드워드를 모두 얻는다. 예를 들어, 비트 문자열 "101"에 대한 코드워드는 다음과 같이 얻어진다.

,

여기서 는 모듈러 2 곱셈 기호이다.

확인으로, G의 행 공간은 이 되도록 H와 직교한다.

입력 비트열 "101"은 항등 행렬 의 존재로 인해 코드워드 "101011"의 처음 3비트로 발견된다. 코드워드의 마지막 3비트 "011"은 패리티 비트이다.

 인코더 예시 

섬네일|none|500px|LDPC 인코더

프레임을 인코딩하는 동안, 입력 데이터 비트 (D)는 반복되어 일련의 구성 인코더에 분배된다. 구성 인코더는 일반적으로 어큐뮬레이터이며, 각 어큐뮬레이터는 패리티 심볼을 생성하는 데 사용된다. 원본 데이터 (S0,K-1)의 단일 사본은 패리티 비트 (P)와 함께 전송되어 코드 심볼을 구성한다. 각 구성 인코더의 S 비트는 폐기된다.

패리티 비트는 다른 구성 코드 내에서 사용될 수 있다.

DVB-S2의 2/3 부호율 코드의 예시를 사용하면, 인코딩된 블록 크기는 64800개의 심볼(N=64800)이며, 43200개의 데이터 비트(K=43200)와 21600개의 패리티 비트(M=21600)를 포함한다. 각 구성 코드(체크 노드)는 16개의 데이터 비트를 인코딩하지만, 첫 번째 패리티 비트는 8개의 데이터 비트를 인코딩한다. 처음 4680개의 데이터 비트는 13번 반복되며(13개의 패리티 코드에서 사용됨), 나머지 데이터 비트는 3개의 패리티 코드에서 사용된다(불규칙 LDPC 코드).

비교를 위해, 고전적인 터보 부호는 일반적으로 병렬로 구성된 두 개의 구성 부호를 사용하며, 각 부호는 전체 입력 데이터 비트 블록(K)을 인코딩한다. 이러한 구성 인코더는 중간 깊이(8 또는 16 상태)의 재귀 컨볼루션 부호(RSC)이며, 프레임의 한 사본을 인터리빙하는 부호 인터리버에 의해 분리된다.

반면 LDPC 부호는 병렬로 많은 저심도 구성 부호(어큐뮬레이터)를 사용하며, 각 부호는 입력 프레임의 작은 부분만 인코딩한다. 많은 구성 부호는 반복 및 분배 연산을 통해 연결된 많은 저심도(2 상태) "컨볼루션 부호"로 볼 수 있다. 반복 및 분배 연산은 터보 부호에서 인터리버의 기능을 수행한다.

다양한 구성 부호의 연결과 각 입력 비트에 대한 중복 수준을 더 정확하게 관리할 수 있는 능력은 LDPC 부호 설계에 더 많은 유연성을 제공하며, 경우에 따라 터보 부호보다 더 나은 성능을 제공할 수 있다. 터보 부호는 낮은 부호율에서 LDPC 부호보다 여전히 더 나은 성능을 보이는 것 같으며, 최소한 낮은 부호율 부호의 설계는 터보 부호가 더 쉽다.

실용적인 문제로, 어큐뮬레이터를 형성하는 하드웨어는 인코딩 과정에서 재사용된다. 즉, 첫 번째 패리티 비트 세트가 생성되고 패리티 비트가 저장되면, 동일한 어큐뮬레이터 하드웨어가 다음 패리티 비트 세트를 생성하는 데 사용된다.

디코딩

다른 코드와 마찬가지로, 이진 대칭 채널에서 LDPC 코드의 최대 우도 디코딩은 NP-완전 문제이며, 3차원 매칭으로부터의 환원을 통해 입증되었다. 따라서 널리 믿어지는 바와 같이 P ≠ NP라고 가정하면, 유용한 크기의 임의 코드에 대한 최적 디코딩을 수행하는 것은 실용적이지 않다.

그러나 반복적인 신뢰전파 디코딩을 기반으로 하는 준최적 기술은 우수한 결과를 제공하며 실용적으로 구현할 수 있다. 준최적 디코딩 기술은 LDPC를 구성하는 각 패리티 검사를 독립적인 단일 패리티 검사(SPC) 코드로 간주한다. 각 SPC 코드는 소프트 입력 소프트 출력 (SISO) 기술(예: SOVA, BCJR 알고리즘, MAP 및 그 파생 기술)을 사용하여 개별적으로 디코딩된다. 각 SISO 디코딩의 소프트 결정 정보는 동일한 정보 비트의 다른 중복 SPC 디코딩과 교차 검사 및 업데이트된다. 그런 다음 각 SPC 코드는 업데이트된 소프트 결정 정보를 사용하여 다시 디코딩된다. 이 과정은 유효한 코드워드가 달성되거나 디코딩이 소진될 때까지 반복된다. 이러한 유형의 디코딩을 종종 합-곱 디코딩이라고 한다.

SPC 코드의 디코딩은 종종 "체크 노드" 처리라고 불리며, 변수의 교차 검사는 종종 "변수 노드" 처리라고 불린다.

실제 LDPC 디코더 구현에서는 처리량을 높이기 위해 여러 SPC 코드 세트가 병렬로 디코딩된다.

반대로, 이진 소거 채널에서의 신뢰 전파는 반복적인 제약 만족으로 구성되어 특히 간단하다.

예를 들어, 위 예시의 유효한 코드워드 101011이 이진 소거 채널을 통해 전송되어 첫 번째 비트와 네 번째 비트가 지워져 ?01?11로 수신되었다고 가정해 보자. 전송된 메시지는 코드 제약 조건을 만족해야 하므로, 수신된 메시지를 팩터 그래프 상단에 기록하여 메시지를 표현할 수 있다.

이 예시에서는 연결된 모든 제약 조건에 두 개 이상의 알 수 없는 비트가 있기 때문에 첫 번째 비트는 아직 복구할 수 없다. 메시지 디코딩을 진행하려면 지워진 비트 중 하나에만 연결되는 제약 조건을 식별해야 한다. 이 예시에서는 두 번째 제약 조건만 충분하다. 두 번째 제약 조건을 검토하면, 그 위치에 0이 있어야만 제약 조건을 만족할 수 있으므로 네 번째 비트는 0이었음이 분명하다.

이 절차는 반복된다. 네 번째 비트에 대한 새로운 값은 이제 첫 번째 제약 조건과 함께 사용하여 아래에서 볼 수 있듯이 첫 번째 비트를 복구할 수 있다. 이는 첫 번째 비트가 가장 왼쪽 제약 조건을 만족하기 위해 1이어야 함을 의미한다.

none

따라서 메시지는 반복적으로 디코딩될 수 있다. 다른 채널 모델의 경우, 변수 노드와 체크 노드 사이에 전달되는 메시지는 확률과 신뢰의 가능성을 나타내는 실수이다.

이 결과는 수정된 코드워드 r에 패리티 검사 행렬 H를 곱하여 확인할 수 있다.

이 연산의 결과 z (증후군)가 3 × 1 제로 벡터이므로, 결과 코드워드 r은 성공적으로 검증된다.

디코딩이 완료되면, 원본 메시지 비트 '101'은 코드워드의 첫 3비트를 확인하여 추출할 수 있다.

이 소거 예시는 설명적이지만, 거의 모든 상업용 LDPC 디코더에서 사용되는 소프트 결정 디코딩 또는 소프트 결정 메시지 전달의 사용을 보여주지는 않는다.

노드 정보 업데이트
최근 몇 년 동안 변수 노드 및 제약 노드 업데이트에 대한 대체 스케줄링의 효과를 연구하는 데 많은 노력이 투자되었다. LDPC 코드를 디코딩하는 데 사용된 원래 기술은 플러딩(flooding)으로 알려져 있었다. 이 유형의 업데이트는 변수 노드를 업데이트하기 전에 모든 제약 노드를 업데이트해야 했으며, 그 반대도 마찬가지였다. Vila Casado 등이 나중에 수행한 연구에서는 변수 노드가 가장 최신 체크 노드 정보를 사용하여 업데이트되는 대체 업데이트 기술이 연구되었다.

이러한 알고리즘의 직관은 값이 가장 많이 변하는 변수 노드가 먼저 업데이트되어야 한다는 것이다. 로그 우도 비율(LLR) 크기가 크고 한 업데이트에서 다음 업데이트로 크게 변하지 않는 신뢰도가 높은 노드는 부호와 크기가 더 넓게 변동하는 다른 노드와 동일한 빈도로 업데이트할 필요가 없다. 이러한 스케줄링 알고리즘은 플러딩을 사용하는 알고리즘보다 더 빠른 수렴 속도와 더 낮은 오류 바닥을 보여준다. 이러한 낮은 오류 바닥은 Informed Dynamic Scheduling (IDS) 알고리즘이 근접 코드워드의 트랩핑 세트를 극복하는 능력으로 달성된다.

비플러딩 스케줄링 알고리즘을 사용할 때는 반복에 대한 대안적인 정의가 사용된다. 속도 k/n의 (n, k) LDPC 부호의 경우, n개의 변수 노드와 n-k개의 제약 노드가 업데이트되면 업데이트 순서에 관계없이 완전한 반복이 발생한다.

부호 구성
블록 크기가 큰 경우, LDPC 부호는 일반적으로 디코더의 동작을 먼저 연구하여 구성된다. 블록 크기가 무한대로 커질수록 LDPC 디코더는 디코딩이 안정적으로 이루어지는 노이즈 임계값과 디코딩이 이루어지지 않는 노이즈 임계값을 가지는 것으로 나타났는데, 이를 통칭하여 절벽 효과라고 한다. 이 임계값은 체크 노드와 변수 노드에서 오는 아크의 최적 비율을 찾아 최적화할 수 있다. 이 임계값을 시각화하는 대략적인 그래픽 접근 방식은 EXIT 차트이다.

이러한 최적화 후 특정 LDPC 부호의 구성은 크게 두 가지 주요 기술 유형으로 나뉜다.

 의사 난수 접근 방식
 조합론적 접근 방식

의사 난수 접근 방식에 의한 구성은 큰 블록 크기에 대해 무작위 구성이 우수한 디코딩 성능을 제공한다는 이론적 결과에 기반한다. 일반적으로 의사 난수 부호는 복잡한 인코더를 가지지만, 최상의 디코더를 가진 의사 난수 부호는 간단한 인코더를 가질 수 있다. 무한 블록 크기의 이론적 한계에서 예상되는 원하는 속성이 유한 블록 크기에서 발생하도록 보장하기 위해 다양한 제약 조건이 종종 적용된다.

조합론적 접근 방식은 작은 블록 크기 LDPC 부호의 속성을 최적화하거나 간단한 인코더를 가진 부호를 생성하는 데 사용될 수 있다.

일부 LDPC 부호는 리드-솔로몬 부호를 기반으로 하며, 10기가비트 이더넷 표준에 사용되는 RS-LDPC 부호가 그 예이다. 무작위로 생성된 LDPC 부호와 비교할 때, DVB-S2 표준에 사용되는 LDPC 부호와 같은 구조화된 LDPC 부호는 더 간단하고 따라서 더 저렴한 하드웨어를 가질 수 있다. 특히, H 행렬이 순환 행렬이 되도록 구성된 부호의 경우 그렇다.

LDPC 부호를 구성하는 또 다른 방법은 유한기하학을 사용하는 것이다. 이 방법은 Y. Kou 등이 2001년에 제안했다.

 터보 부호와 비교 
LDPC 부호는 다른 강력한 부호화 방식, 예를 들어 터보 부호와 비교될 수 있다. 한편, 터보 부호의 비트 오류율 (BER) 성능은 낮은 부호 한계의 영향을 받는다. LDPC 부호는 최소 거리의 제한이 없으므로, 간접적으로 LDPC 부호가 터보 부호보다 상대적으로 높은 부호율 (예: 3/4, 5/6, 7/8)에서 더 효율적일 수 있음을 의미한다. 그러나 LDPC 부호가 완전히 대체하는 것은 아니다. 터보 부호는 낮은 부호율 (예: 1/6, 1/3, 1/2)에서 여전히 최상의 솔루션이다.

 같이 보기 

인물
 리처드 해밍
 클로드 섀넌
 데이비드 J. C. 맥케이
 어빙 S. 리드
 마이클 루비

이론
 그래프 이론
 해밍 부호
 희소 그래프 코드
 익스팬더 코드

응용

 G.hn (전력선, 전화선 및 동축 케이블을 통한 네트워킹을 위한 ITU-T 표준)
 802.3an 또는 10GBASE-T (트위스트 페어 케이블을 통한 10 기가비트/초 이더넷)
 CMMB (중국 멀티미디어 모바일 방송)
 DVB-S2 / DVB-T2 / DVB-C2 (디지털 비디오 방송, 2세대)
 DMB-T/H (디지털 비디오 방송)
 와이맥스 (마이크로파 통신을 위한 IEEE 802.16e 표준)
 IEEE 802.11n-2009 (와이파이 표준)
 DOCSIS 3.1
 ATSC 3.0 (차세대 북미 지상파 디지털 방송)
 3GPP (5G-NR 데이터 채널)

다른 용량 근접 코드
 분수 부호
 LT 코드
 온라인 부호
 랩터 부호
 반복 누적 부호 (간단한 터보 부호의 일종)
 직렬 연결 컨볼루션 코드
 토네이도 부호 (이진 소거 채널용으로 설계된 LDPC 부호)
 터보 부호

용량 달성 코드
지금까지 설계 및 증명을 통해 용량을 달성하는 코드는 하나뿐이다.
 극 부호

 각주 

 외부 링크 
 저밀도 패리티 검사 코드 소개 (Sarah J Johnson, 2010)
 LDPC 코드 – 간략한 튜토리얼 (Bernhard Leiner, 2005)
 LDPC 코드 (TU Wien) 
 
 
 LDPC 코드: 소개 (Amin Shokrollahi, 2003)
 LDPC 코드의 신뢰 전파 디코딩 (Amir Bennatan, 프린스턴 대학교)
 터보 및 LDPC 코드: 구현, 시뮬레이션 및 표준화 (웨스트버지니아 대학교)
 정보 이론 및 코딩 (마르코 헨호퍼, 2011, 일메나우 공과대학교) - 74-78페이지에서 LDPC 코드를 논한다.
 LDPC 코드 및 성능 결과
 LDPC 코딩을 포함한 DVB-S.2 링크 (매트랩)
LDPC 코드 인코딩, 디코딩 및 시뮬레이션을 위한 소스 코드는 다양한 곳에서 구할 수 있다.
 C로 된 이진 LDPC 코드
 파이썬용 이진 LDPC 코드 (C로 된 코어 알고리즘)
 매트랩으로 된 LDPC 인코더 및 LDPC 디코더
 C++11로 된 빠른 전방 오류 정정 툴박스 (AFF3CT)로 빠른 LDPC 시뮬레이션 가능

분류:오류 검출 정정
분류:부호 이론