LDPC   Low Density Parity Check Code   저밀도 패리티 검사 코드

1. LDPC (Low Density Parity Check Code)

  ㅇ 1962년 R. Gallager에 의해 제안되었으나, 1990년대 후반에 상용화 측면에서 재발견됨
     - 당시로써는 복호의 계산복잡도가 너무 컸으나, 1990년대 중반 다시 주목을 받게됨

  ㅇ 즉, 터보 코드의 반복 복호(Iterative Decoding) 기술을 토대로 재평가 됨
     - 블록 길이가 충분히 큰 경우에,
     - 샤논 한계(채널 용량)에 근접한 성능(0.1 dB 차이)을 보이나, 
     - 터보 코드 보다, 복호 복잡성이 상대적으로 낮음을 알게 됨


2. LDPC의 특징

  ㅇ 특수한 형태를 갖는 선형 블록 코드의 일종
     - `패리티 검사 행렬`의 요소 값들 중 극소수 만 `1` 임 (sparse) 
     - 이를두고, 저 밀도 라고 불리움 (low density)

     * 이러한 저 밀도 특성이, 복호 복잡성 감소, 좋은 거리 특성을 강화함

  ㅇ 복호가 각 비트 마다 MAP 판정규칙을 기반으로 수행됨

  ㅇ 터보 코드 처럼 `반복 복호 (Iterative Decoding)` 기술을 사용
     - 코드 길이를 크게함에 따라 오류정정능력은 커지나,
     - 비트 당 계산복잡도는 크게 변하지 않음


3. 터보 코드 대비 장단점

  ㅇ 터보코드 대비 장점
     - 높은 에러 성능을 보이기 위해 긴 인터리버를 요구하지 않음
        . LDPC 코드 자체의 램덤성 때문에, 주파수 인터리버 불필요
     - 더 나은 블록 에러 성능을 보임
        . 버스트 오류 정정에 강함
     - 더 낮은 BER에서 에러 최저치를 보임
     - 복호가 트렐리스 기반으로 이루어지지 않아, 에러 전파가 되지 않는 등

  ㅇ 터보코드 대비 단점
     - 블록길이가 작을때에는, 부호화시 복잡도가 더 큼


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의 표현

  ㅇ 행렬 표현 방식

  ㅇ 그래프 표현 방식
     - Tanner 그래프라는 표현 기법을 통해, 꽤 낮은 복잡도를 갖게되는 복호 알고리즘의 실마리 제공