Saltar para o conteúdo

Low-density parity-check code

Origem: Wikipédia, a enciclopédia livre.

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[1] 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 em 1960.[2]

História

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

Funcionamento

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

O grafo abaixo ilustra um código LDPC. Nesse grafo, n nós de variáveis na parte superior estão conectados a n−k nós de restrição na parte inferior. Os bits de uma mensagem 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 restrição (caixa com um símbolo '+') devem ter soma par (ou seja, devem apresentar paridade 0).

A figura apresentada apresenta 8 possíveis sequências que satisfazem as condições, ou seja, são palavras válidas do 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.

Referências

  1. ↑ Amin Shokrollahi (2003) LDPC Codes: An Introduction
  2. ↑ Larry Hardesty (21 January 2010). «Explained: Gallager codes». MIT News. Consultado em 18 de agosto de 2010  Verifique data em: |data= (ajuda)
  3. ↑ Gallager, R. G., Low Density Parity Check Codes, Monograph, M.I.T. Press, 1963 [1]
  4. ↑ David J.C. MacKay and Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, July 1996
  5. ↑ Telemetry Data Decoding, Design Handbook
Obtida de "https://pt.wikipedia.org/w/index.php?title=Low-density_parity-check_code&oldid=31601037"