1. LDPC (Low Density Parity Check Code)
ㅇ 1962년 Robert G. Gallager에 의해 제안되었으나, 1990년대 후반에 상용화 측면에서 재조명됨
- 확률 기반의 반복 복호 알고리즘(Message Passing Algorithm)을 사용하며,
- 당시로써는 계산 복잡도가 너무 커 실용화되지 못했으나,
- 1990년대 중반 이후 컴퓨팅 기술 발전과 함께 다시 주목받게 됨
ㅇ 즉, 터보 코드와 유사한 반복 복호(Iterative Decoding) 기술의 성공 이후 재평가됨
- 블록 길이가 충분히 큰 경우,
- 샤논 한계(Channel Capacity)에 매우 근접한 성능(0.1 dB 차이)을 보이며,
- 터보 코드 대비 복호 복잡도가 상대적으로 낮고, 병렬 구현에 유리함
2. LDPC의 특징
ㅇ 버스트 오류에 강한 선형 블록 부호
- 뛰어난 오류정정 능력
ㅇ 패리티 검사 행렬이 특수한 형태를 갖는 선형 블록 부호의 일종
- `패리티 검사 행렬`의 요소 값들 중 극소수 만 `1` 임 (sparse)
- 이를두고, 저 밀도 라고 불리움 (low density)
* 이러한 저 밀도 특성이, 복호 복잡성 감소, 좋은 거리 특성을 강화함
ㅇ 터보 코드 처럼, `반복 복호 (Iterative Decoding)` 기술을 사용
- 코드 길이를 크게함에 따라 오류정정능력은 커지나,
- 비트 당 계산복잡도는 크게 변하지 않음
3. LDPC의 비교 : (LDPC 코드, 터보 코드 간의 비교)
ㅇ 두 방식은, 구현 디테일은 다르지만, 샤논 한계에 근접한 성능을 보이며, 큰 틀에서 유사함
- "메시지를 반복적으로 주고받으면서, 점점 더 나은 추정치를 얻는" 반복 복호 과정을 가짐
ㅇ 터보 코드 대비 LDPC 코드의 장점
- 높은 에러 성능을 보이기 위해 긴 인터리버를 요구하지 않음
. LDPC 코드 자체의 램덤성 때문에, 긴 인터리버에 대한 의존성이 상대적으로 낮음
- 더 나은 블록 에러 성능을 보임
. 버스트 오류 정정에 강함
- 더 낮은 BER에서 에러 최저치를 보임
- 복호가 트렐리스 기반으로 이루어지지 않아, 에러 전파가 되지 않는 등
ㅇ 터보 코드 대비 LDPC 코드의 단점
- 블록길이가 작을때에는, 부호화시 복잡도가 더 큼
. LDPC 코드는 블록 길이가 작을 때, 터보 코드보다 부호화 과정이 더 복잡해질 수 있음
4. LDPC의 표기
ㅇ 만일, 어떤 선형 부호가, `(r,s) Gallager Code` 이라고 하면,
- 이의 패리티 검사 행렬의 요소값들이, 다음 구성을 보임
. 매 열(column) 마다 r개 만 `1`
. 매 행(row) 마다 s개 만 `1` 임
* (Gallager Code : LDPC의 최초 원형이자 기본 구조)
ㅇ 이때, r,s 갯수가 작을 경우에 (즉,`1`의 개수가 저 밀도 이면),
- 이를, LDPC 코드 라고 함
ㅇ 또한, r ≤ log2 n (n : 블록길이) 이면,
- 이 경우에, (n,r,s) LDPC 코드 라고 함
5. LDPC의 구성
ㅇ 생성 행렬 G가 아닌, 패리티 검사 행렬 H를 의해 정의됨
- 조건 : 패리티 검사 행렬의 조건을 만족하는, 모든 부호어 벡터 집합이 LDPC 코드가 됨
. v HT = 0 : (1 x n) (n x j) = (1 x j)
. 또는, HT v = 0 : (j x n) (n x 1) = (j x 1)
- 부호화 : 위 조건을 만족토록, 메세지어 u로부터 부호어 v를 생성하는 것
- 특징 : 비록, 패리티 검사 행렬 H 크기가 매우 크지만,
. 요소 값들의 `0` 개수 대비 `1` 개수가 매우 낮은 저 밀도 특성을 가짐
6. LDPC의 표현
ㅇ 행렬 표현에 의한 연산,저장의 효율성 추구
- 패리티 검사 행렬(H)을 이용하여 부호를 정의되며,
- H의 희소한 행렬 구조 때문에, 저장 및 연산이 효율적
ㅇ 그래프 표현에 의한 시각적 알고리즘 도모
- Tanner 그래프를 이용하여 부호 구조를 시각적으로 나타냄
. 희소 그래프 기반의 효율적인 반복 복호 알고리즘 구현 가능
* Tanner 그래프
. 두 종류의 노드 집합과 이들간의 연결선으로 나타냄
. 변수 노드(Variable Nodes)와 검사 노드(Check Nodes)로 구성되며,
. 메시지 전달 알고리즘(Message Passing Algorithm) 을 통한 복호 과정이 효율적으로 수행됨
7. LDPC의 복호
ㅇ 주로, 메세지 전달 반복 복호 방식 사용
- 수신 정보로부터, Tanner 그래프 상에서, 변수 노드(비트 노드)와 검사 노드(체크 노드)들이,
- 서로 추정값을 담은 메세지를 주고받으며, 송신 부호어를 확률적으로 추론하는 일련의 과정