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. ↑ == Referências em contribuições recentes ==

    Olá, Low-density parity-check code. Boas-vindas à Wikipédia! Alerto que algumas contribuições que realizou não possuem fontes confiáveis e independentes, conforme orienta a política de verificabilidade da Wikipédia, por isso seu texto foi removido, modificado ou marcado com o uso de predefinições (como {{sem-fontes}} e {{carece de fontes}}). Para adicionar referências é necessário colocar <ref>referência</ref> após sua edição, substituindo o termo referência pela bibliografia ou ligação de onde obteve a informação que adicionou, de acordo com as orientações de formatação do livro de estilo. Encontre fontes: Google (N • L • A • I • WP refs)  • ABW  • CAPES.

    Por favor, leia com atenção as políticas e regulamentos apresentados acima, assim seu esforço aqui terá um bom resultado. Se, ao ler a política, lhe surgir alguma dúvida, por favor deixe-me uma mensagem em minha página de discussão e quando eu puder lhe responderei, ou então, pode consultar algum membro do programa de tutoria ou um administrador da Wikipédia. Também pode utilizar o assistente para a criação de artigos, que o guiará passo a passo no processo de criação. Saudações e boa sorte em suas edições.

  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=31600990"