LDPC
LDPC matrix에 대한 사전 정보
https://github.com/kirlf/csp-modeling/blob/master/ldpc/ldpc.ipynb
A fast reconstruction of the parity-check matrices of LDPC codes in a noisy environment
LDPC 코드를 공부해볼 기회가 생겨 조사를 하였다.
목표는 LDPC 코드의 parity check matrix (PCM) 인 H matrix를 찾아내는 것이다. 입력은 충분히 많은 LDPC 코드 워드 (code word)이고, 해당 코드워드의 길이(n)와 데이터 비트가 차지하는 비트수(k)를 알고있다고 가정한다. 모든 코드는 binary vector이며 패리티 검사 행렬 H의 원소도 전부 이진수이다.
(n,k) LDPC 코드 y는 총 n개의 비트로 이루어져 있으며, 그중 첫 k개가 정보비트(message bit)이고 나머지 n-k개가 패리티 검사 비트(parity check bit)이다. 코드워드는 Hy=0 를 만족하도록 parity bit이 생성되며, Hy가 0이 아니면 코드워드 y에 에러가 있다고 판단한다. Hy=0이므로 y는 H의 null space에 속하고, H의 row vector들은 code word vector space(C)의 orthogonal complement(Cㅗ)에 속한다. parity bit는 generator matrix(G)를 사용해 생성하며, k 비트의 정보비트(m)를 받아 mG = y로 구한다. 이때 G는 앞부분이 k by k 단위행렬(I) 이며 뒷부분이 패리티를 만드는 k by n-k 행렬(P)인 [I | P] 형태이다. 정보비트는 건드리지 않고 패리티 비트만 더 추가하여 n bit 코드워드를 만든다.
## noise가 없는 경우 code word만 이용해 H matrix를 찾아내기 위해서는 Hy=0 임을 이용한다. parity check bit은 k개의 메세지 비트의 선형 조합으로 이루어지며 G와 곱으로 만들어지므로 코드 위드 벡터들의 차원은 많아야 k이다. 메세지 비트가 골고루 사용된다면 코드워드 벡터 공간의 차원은 k라고 볼 수 있다. 따라서 코드 워드를 모은 행렬은 rank가 k이고, ECO(elementary column operation)을 적용하면 0 column이 n-k개 나타난다. 이때 코드워드 행렬 A의 특정 column이 zero vector가 나오게 하는 ECO 행렬의 해당 column, q가 parity check vector의 후보이다. 이는 PCM인 H의 각 row r이 ry=0 를 만족함을 보면 r과 q가 같은 space에 속한다는 것을 알 수 있다. ECO matrix의 column들이 이루는 공간도 n-k 차원이고, H의 차원도 n-k이므로 두 행렬은 transpose했을 시 동일한 image를 가진다. 또는, H에 ERO(elementary row operation)을 수행하면 ECO 행렬을 전치시킨 것이 나온다.
noise가 없는 경우 code word를 모은 행렬 A와 ECO행렬 Q 사이에 다음과 같은 관계가 성립하도록 ECO를 수행할 수 있다.
ECO를 binary matrix에 빠르게 적용할 수 있는 코드 https://gist.github.com/popcornell/bc29d1b7ba37d824335ab7b6280f7fec
각 행렬을 자세히 풀어쓰면 다음과 같다.
ECO 행렬 Q를 두 부분으로 나누어서 보면, 0행렬을 만드는데 대응되는 Q2행렬이 Cㅗ를 이루는걸 알 수 있다. Q2의 column space는 code word와 내적이 0이며 차원이 n-k이므로 Cㅗ와 동일한 공간이다.
따라서 해당 Q2를 transpose한 것이 H matrix와 동등하다고 할 수 있다. 동등하다는 것은 H matrix의 row space와 같은 space를 span하며, gauss elimination을 적용하면 같게 만들 수 있음을 의미한다.
우리가 구한 QT는 sparse하지 않을 수 있기에 sparse하게 만들어주는 작업인 sparsifying 을 해주어야 한다. 여기에는 여러 방법이 있지만 해당 논문에서는 아래와 같은 방법을 사용한다.
noise가 있는 경우
noise로 인해 코드워드에 noise bit이 추가되므로 코드워드 행렬의 차원이 k보다 커질 수 있다. 여기에 ECO를 적용하면 lower triangular matrix(LTM)이 만들어지며, 0 column이 없을 수 있다. 이 문제와 타협하기 위해 noise가 충분히 작다면 적절한 threshold를 정하여 1의 개수가 그것보다 작으면 0행렬로 보자. 마찬가지로 code word matrix에 연산 후 column을 0에 가깝게 만드는 대응되는 ECO행렬의 column들이 parity check vector후보라고 볼 수 있다.
다만 이때 구해진 벡터들이 parity check vector라고 100% 확신할 수는 없다.
Simulated annealing sparsifying code https://github.com/LuisRusso-INESC-ID/SPCM/blob/master/src/main.c
C로 구현된 LDPC 생성 및 연산 코드 모듈 https://github.com/LuisRusso-INESC-ID/SPCM?tab=readme-ov-file
댓글남기기