Low-density parity-check code

Códigos Low-Density-Parity-Check (ou Códigos de verificação de paridade de baixa densidade, em português), também conhecidos como LDPC ou Códigos de Gallager, são códigos corretores de erro lineares. Códigos LDPC são códigos capazes de se aproximar da capacidade do canal (dada pelo Teorema de Shannon-Hartley), fazendo com que o ruído esperado se aproxime arbitrariamente do limite de Shannon para canais binários de apagamento. Códigos LDPC são construídos a partir de grafos bipartidos esparsos.

A nomeação Códigos de Gallager é dada em honra a Robert G. Gallager, quem introduziu o conceito de códigos de verificação de paridade de baixa densidade em sua tese de doutorado no MIT em 1960.

História

Os códigos LDPC foram introduzidos por Gallager em 1963, porém foram negligenciados após sua publicação dados requerimentos inacessíveis sobre a capacidade dos decodificadores. Redescobertos em 1993, os códigos LDPC viram grandes avanços recentemente, ultrapassando o desempenho dos populares Códigos Turbo para altas taxas de transmissão.

Funcionamento

Os códigos LDPC são gerados por uma matriz esparsa de verificação de paridade. Esta matriz pode ser gerada aleatoriamente, desde que satisfaça as condições que caracterizam a matriz como esparsa.

O grafo abaixo ilustra um fragmento de código LDPC. Nesse grafo, n nós de variáveis na parte superior estão conectados a n−k nós de cheque na parte inferior. Os bits de uma palavra válida, quando colocados sobre os T sobre o grafo, satisfazem as restrições. As restrições estabelecem que todas as linhas conectadas a nós de variáveis (caixa com um símbolo '=') devem ter o mesmo valor, enquanto todos os valores conectados aos nós de cheque (caixa com um símbolo '+') devem ter soma par (ou seja, devem apresentar paridade 0).

Ignorando as linhas saindo da imagem à esquerda e à direita, a figura apresenta 8 possíveis sequências que satisfazem as condições, ou seja, são palavras válidas do fragmento de código (000000, 011001, 110010, 101011, 111100, 100101, 001110, 010111). O código apresentado, portanto, é capaz de representar mensagens de 3 bits codificadas em 6 bits. A redundância é utilizada para possibilitar a detecção e recuperação de erros no canal. Este código compõe um código linear (6, 3) com n = 6 e k = 3.

A matriz de paridade H que representa o fragmento de grafo é dada por

$\mathbf {H} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}.$

Nesta matriz, cada linha representa um dos nós de restrição de paridade, enquanto cada coluna representa um nó de variável, ou seja, um bit da palavra transmitida.

Neste exemplo, as 8 palavras do código podem ser obtidas pondo a matriz de checagem de paridade H na forma ${\begin{bmatrix}-P^{T}|I_{n-k}\end{bmatrix}}$ através de operações elementares sobre as linhas, efetuadas em módulo 2:

$\mathbf {H} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\0&1&1&0&1&0\\\end{pmatrix}}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&1&1&0&1&0\\0&0&1&1&0&1\\\end{pmatrix}}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&1&1&0&1&0\\1&1&0&0&0&1\\\end{pmatrix}}.$

A partir desta matriz, a matriz geradora G pode ser obtida transformando-a na forma ${\begin{bmatrix}I_{k}|P\end{bmatrix}}$ (note que no caso especial em que se trata de um código binário, $P=-P$):

$\mathbf {G} ={\begin{pmatrix}1&0&0&1&0&1\\0&1&0&1&1&1\\0&0&1&1&1&0\\\end{pmatrix}}.$

Multiplicando cada uma das 8 possíveis sequências binárias de 3 bits pela matriz geradora G, todas as palavras válidas podem ser obtidas. Por exemplo, a palavra para a sequência '101' é obtida da seguinte forma:

${\begin{pmatrix}1&0&1\\\end{pmatrix}}\cdot {\begin{pmatrix}1&0&0&1&0&1\\0&1&0&1&1&1\\0&0&1&1&1&0\\\end{pmatrix}}={\begin{pmatrix}1&0&1&0&1&1\\\end{pmatrix}}.$