1. LDPC (Low Density Parity Check Code)
ㅇ 1962년 R. Gallager에 의해 제안되었으나, 1990년대 후반에 상용화 측면에서 재발견됨
- 복호 방식이, 각 비트 마다 MAP 판정규칙을 기반으로 수행되어,
- 당시로써는, 계산복잡도가 너무 컸으나, 1990년대 중반에, 다시 주목을 받게됨
ㅇ 즉, 터보 코드의 반복 복호(Iterative Decoding) 기술을 토대로 재평가 됨
- 블록 길이가 충분히 큰 경우에,
- 샤논 한계(채널 용량)에 근접한 성능(0.1 dB 차이)을 보이나,
- 터보 코드 보다, 복호 복잡성이 상대적으로 낮음을 알게 됨
2. LDPC의 특징
ㅇ 버스트 오류에 강한 선형 블록 부호
- 뛰어난 오류정정 능력
ㅇ 패리티 검사 행렬이 특수한 형태를 갖는 선형 블록 부호의 일종
- `패리티 검사 행렬`의 요소 값들 중 극소수 만 `1` 임 (sparse)
- 이를두고, 저 밀도 라고 불리움 (low density)
* 이러한 저 밀도 특성이, 복호 복잡성 감소, 좋은 거리 특성을 강화함
ㅇ 터보 코드 처럼, `반복 복호 (Iterative Decoding)` 기술을 사용
- 코드 길이를 크게함에 따라 오류정정능력은 커지나,
- 비트 당 계산복잡도는 크게 변하지 않음
3. LDPC 코드, 터보 코드 비교
ㅇ 두 방식은 구현 디테일은 다르지만, 큰 틀에서 공통적으로,
- "메시지를 반복적으로 주고받으면서, 점점 더 나은 추정치를 얻는" 반복 복호 과정을 가짐
ㅇ 터보 코드 대비 LDPC 코드의 장점
- 높은 에러 성능을 보이기 위해 긴 인터리버를 요구하지 않음
. LDPC 코드 자체의 램덤성 때문에, 주파수 인터리버 불필요
- 더 나은 블록 에러 성능을 보임
. 버스트 오류 정정에 강함
- 더 낮은 BER에서 에러 최저치를 보임
- 복호가 트렐리스 기반으로 이루어지지 않아, 에러 전파가 되지 않는 등
ㅇ 터보 코드 대비 LDPC 코드의 단점
- 블록길이가 작을때에는, 부호화시 복잡도가 더 큼
. LDPC 코드는 블록 길이가 작을 때, 터보 코드보다 부호화 과정이 더 복잡해질 수 있음
4. LDPC의 표기
ㅇ 만일, 어떤 선형 부호가, (r,s) Gallager Code 이면,
- 이의 패리티 검사 행렬의 요소값들이, 다음 구성을 보임
. 매 열(column) 마다 r개 만 `1`
. 매 행(row) 마다 s개 만 `1` 임
ㅇ 이때, r,s 갯수가 작을 경우에 (즉,`1`의 개수가 저 밀도 이면),
- 이를, LDPC 코드 라고 함
ㅇ 통상, r ≤ logn (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 그래프 상에서, 변수 노드(비트 노드)와 검사 노드(체크 노드)들이,
- 서로 추정값을 담은 메세지를 주고받으며, 송신 부호어를 확률적으로 추론하는 일련의 과정