Codi de verificació de paritat de baixa densitat

Exemple de diagrama de codificador LDPC.

En teoria de la informació, un codi de verificació de paritat de baixa densitat (amb acrònim anglès LDPC) és un codi lineal de correcció d'errors, un mètode per transmetre un missatge a través d'un canal de transmissió sorollós.[1][2] Un codi LDPC es construeix utilitzant un gràfic de Tanner escàs (subclasse del gràfic bipartit).[3] Els codis LDPC són codis que s'aproximen a la capacitat, el que significa que existeixen construccions pràctiques que permeten establir el llindar de soroll molt a prop del màxim teòric (el límit de Shannon) per a un canal simètric sense memòria. El llindar de soroll defineix un límit superior per al soroll del canal, fins al qual la probabilitat de pèrdua d'informació es pot fer tan petita com es desitgi. Utilitzant tècniques iteratives de propagació de creences, els codis LDPC es poden descodificar en un temps lineal a la seva longitud de bloc.

Els codis LDPC estan trobant un ús creixent en aplicacions que requereixen una transferència d'informació fiable i altament eficient a través d'enllaços restringits per l'amplada de banda o amb el canal de retorn restringit en presència de soroll corrupte. La implementació dels codis LDPC ha quedat endarrerida amb la d'altres codis, especialment els codis turbo. La patent fonamental dels codis turbo va caducar el 29 d'agost de 2013.[4][5]

Els codis LDPC també es coneixen com a codis Gallager, en honor a Robert G. Gallager, que va desenvolupar el concepte LDPC en la seva tesi doctoral a l'Institut Tecnològic de Massachusetts el 1960.[6][7] També s'ha demostrat que els codis LDPC tenen propietats combinatòries ideals. En la seva dissertació, Gallager va demostrar que els codis LDPC aconsegueixen el límit de Gilbert-Varshamov per a codis lineals sobre camps binaris amb alta probabilitat. L'any 2020 es va demostrar que els codis LDPC de Gallager aconsegueixen la capacitat de descodificació de llistes i també aconsegueixen l'enllaç Gilbert-Varshamov per a codis lineals sobre camps generals.[8]

El 2003, un codi LDPC d'estil d'acumulació de repeticions irregulars (IRA) va superar sis codis turbo per convertir-se en el codi de correcció d'errors del nou estàndard DVB-S2 per a la televisió digital.[9]

El 2008, LDPC va superar els codis turbo convolucionals com a sistema de correcció d'errors directes (FEC) per a l'estàndard ITU-T G.hn.[10]

Els codis LDPC també s'utilitzen per a Ethernet 10GBASE-T, que envia dades a 10 gigabits per segon mitjançant cables de parell trenat. A partir del 2009, els codis LDPC també formen part de l'estàndard Wi-Fi 802.11 com a part opcional de 802.11n i 802.11ac, a l'especificació PHY d'alt rendiment (HT).[11] LDPC és una part obligatòria de 802.11ax (Wi-Fi 6).

5G NR utilitza codi polar per als canals de control i LDPC per als canals de dades.[12]

Referències

  1. ↑ David J.C. MacKay (2003) Information theory, Inference and Learning Algorithms, CUP, ISBN 0-521-64298-1, (also available online)
  2. ↑ Todd K. Moon (2005) Error Correction Coding, Mathematical Methods and Algorithms. Wiley, ISBN 0-471-64800-0 (Includes code)
  3. ↑ Amin Shokrollahi (2003) LDPC Codes: An Introduction
  4. ↑ , US 5446747
  5. ↑ NewScientist, Communication speed nears terminal velocity, by Dana Mackenzie, 9 July 2005
  6. ↑ Larry Hardesty , 21-01-2010.
  7. ↑ [1] R. G. Gallager, “Low density parity check codes,” IRE Trans. Inf. Theory, vol. IT-8, no. 1, pp. 21- 28, Jan. 1962.
  8. ↑ [2] J. Moshieff, N. Resch, N. Ron-Zewi, S. Silas, M. Wootters, “Low-density parity-check codes achieve list-decoding capacity,” SIAM Journal on Computing, FOCS20-38-FOCS20-73.
  9. ↑ Presentation by Hughes Systems Arxivat 2006-10-08 a Wayback Machine.
  10. ↑ HomePNA Blog: G.hn, a PHY For All Seasons
  11. ↑ IEEE Standard, section 20.3.11.6 "802.11n-2009", IEEE, October 29, 2009, accessed March 21, 2011.
  12. ↑ «5G Channel Coding» (en anglès). https://accelercomm.com.+Arxivat de l'original el 6 desembre 2018. [Consulta: 6 gener 2019].