Código con baja densidad de controles de paridad

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 22 de mayo de 2020; las comprobaciones requieren 7 ediciones .

El código de verificación de paridad de baja densidad ( código LDPC del inglés. Código de verificación de paridad de baja densidad, código LDPC, código de baja densidad ) es un código utilizado en la transmisión de información, un caso especial de un código lineal de bloque con paridad controlar. Una característica es la baja densidad de elementos significativos de la matriz de verificación , por lo que se logra la relativa simplicidad de la implementación de herramientas de codificación.

También llamado código Gallagher , en honor al autor del primer trabajo sobre el tema de los códigos LDPC.

Antecedentes

En 1948, Shannon publicó su trabajo sobre la teoría de la transmisión de información. Uno de los resultados clave del trabajo es el teorema de transmisión de información para un canal ruidoso , que indica la posibilidad de minimizar la probabilidad de un error de transmisión en el canal eligiendo una longitud de palabra clave suficientemente grande: una unidad de información transmitida en el canal . 1] .

Al transmitir información, su flujo se divide en bloques de cierta longitud (la mayoría de las veces), que el codificador convierte (codifica) en bloques llamados palabras clave. Las palabras clave se transmiten por el canal, posiblemente con distorsión. En el lado receptor, el decodificador convierte las palabras clave en un flujo de información, corrigiendo (si es posible) los errores de transmisión.

El teorema de Shannon establece que, bajo ciertas condiciones, la probabilidad de un error de decodificación (es decir, la incapacidad del decodificador para corregir un error de transmisión) puede reducirse eligiendo una palabra clave más larga. Sin embargo, este teorema (y el trabajo en general) no muestra cómo elegir una gran longitud, sino más bien cómo organizar eficazmente el proceso de codificación y decodificación de información con una gran longitud de palabras clave. Si suponemos que el codificador y el decodificador tienen algunas tablas de correspondencia entre el bloque de información de entrada y la palabra de código correspondiente, dichas tablas ocuparán mucho espacio. Para un canal simétrico binario sin memoria (en pocas palabras, la entrada del codificador es un flujo de ceros y unos) el número de bloques diferentes es 2 n , donde n es el número de bits (ceros o unos) que serán convertido en una palabra de código. Para 8 bits, estos son 256 bloques de información, cada uno de los cuales contendrá la palabra de código correspondiente. Además, la palabra de código suele ser más larga, ya que contiene bits adicionales para proteger contra errores de transmisión de datos. Por lo tanto, uno de los métodos de codificación es el uso de una matriz de verificación, que permite decodificar la palabra clave en una sola operación matemática (multiplicar una fila por una matriz). De manera similar, cada matriz de verificación corresponde a una matriz generadora , de manera similar, por una operación de multiplicar una fila por una matriz que genera una palabra de código.

Por lo tanto, para palabras de código relativamente cortas, los codificadores y decodificadores pueden simplemente almacenar todas las opciones posibles en la memoria, o incluso implementarlas en forma de un circuito semiconductor. Para una palabra de código más grande, es más eficiente almacenar el generador y la matriz de paridad. Sin embargo, con longitudes de bloque de varios miles de bits, almacenar matrices con un tamaño, respectivamente, en megabits , ya se vuelve ineficiente. Una de las formas de solucionar este problema es utilizar códigos con baja densidad de controles de paridad, cuando el número de unidades en la matriz de control de paridad es relativamente pequeño, lo que permite organizar el proceso de almacenamiento de la matriz de manera más eficiente o directa. implementar el proceso de decodificación utilizando un circuito semiconductor.

El primer trabajo sobre este tema fue 1963 Low-Density Parity-Check Codes de Robert Gallagher [2] (que se fundó en su tesis doctoral de 1960 ). En el trabajo, el científico describió los requisitos para tales códigos, describió posibles métodos de construcción y métodos para su evaluación. Por lo tanto, los códigos LDPC a menudo se denominan códigos Gallagher. En la literatura científica rusa , los códigos también se denominan códigos de baja densidad o códigos con una baja densidad de controles de paridad.

Sin embargo, debido a la dificultad de implementar codificadores y decodificadores, estos códigos no se utilizaron y fueron olvidados hasta que se redescubrió el trabajo de Gallagher en 1996 [3] [4] . Con el desarrollo de las tecnologías de las telecomunicaciones, ha vuelto a aumentar el interés por transmitir información con el mínimo de errores. A pesar de la complejidad de implementación en comparación con el código turbo , la falta de barreras de uso (sin protección de patentes) hizo que los códigos LDPC fueran atractivos para la industria de las telecomunicaciones y, de hecho, se convirtieron en el estándar de facto. En 2003, el código LDPC, en lugar del código turbo, pasó a formar parte del estándar de transmisión de datos por satélite DVB-S2 para la televisión digital. Una sustitución similar ha tenido lugar en el estándar DVB-T2 para la radiodifusión de televisión digital terrestre [5] .

Códigos LDPC

Los códigos LDPC se describen mediante una matriz de paridad de baja densidad que contiene principalmente ceros y un número relativamente pequeño de unos. Por definición, si cada fila de la matriz contiene exactamente y cada columna contiene exactamente unos, entonces el código se llama regular (de lo contrario, irregular ). En el caso general, el número de unos en la matriz tiene el orden de , es decir, crece linealmente con un aumento en la longitud del bloque de código (el número de columnas de la matriz de verificación). $k<n$ ${\ estilo de visualización j<r}$ ${\ estilo de visualización O \ izquierda (n \ derecha)}$

Se suelen considerar matrices de gran tamaño. Por ejemplo, el trabajo de Gallagher en la sección de resultados experimentales utiliza números "pequeños" de filas n=124, 252, 504 y 1008 filas (el número de columnas de la matriz de control es ligeramente mayor). En la práctica, se utilizan matrices con una gran cantidad de elementos, de 10 a 100 mil filas. Sin embargo, el número de unos por fila o columna sigue siendo bastante pequeño, normalmente menos de 10. Se ha observado que los códigos con el mismo número de elementos por fila o columna, pero con un tamaño mayor, tienen un mejor rendimiento.

Una característica importante de la matriz de códigos LDPC es la ausencia de ciclos de cierto tamaño. Un ciclo de longitud 4 se entiende como la formación de un rectángulo en la matriz de control, en cuyas esquinas hay unidades. La ausencia de un ciclo de longitud 4 también se puede determinar a través del producto escalar de las columnas (o filas) de la matriz. Si cada producto escalar por pares de todas las columnas (o filas) de la matriz no es más de 1, esto indica la ausencia de un ciclo de longitud 4. Los ciclos de mayor longitud (6, 8, 10, etc.) pueden ser determina si se construye un grafo en la matriz de verificación , con vértices cuyas aristas son todas las conexiones posibles de vértices paralelos a los lados de la matriz (es decir, líneas verticales u horizontales). El ciclo mínimo de esta columna será el ciclo mínimo de la matriz de verificación del código LDPC. Obviamente, el ciclo tendrá una longitud de al menos 4, no 3, ya que las aristas del gráfico deben ser paralelas a los lados de la matriz. En general, cualquier ciclo en este grafo tendrá una longitud par, el tamaño mínimo es 4, y el tamaño máximo no suele importar (aunque, obviamente, no es más que el número de nodos del grafo, es decir, n ×k).

La descripción del código LDPC es posible de varias formas:

matriz de cheques
gráfica bipartita
otra forma grafica
formas especiales

El último método es una designación convencional para un grupo de representaciones de código que se construyen de acuerdo con reglas-algoritmos dadas, de modo que para reproducir el código nuevamente, es suficiente conocer solo los parámetros de inicialización del algoritmo y, por supuesto , el propio algoritmo de construcción. Sin embargo, este método no es universal y no puede describir todos los códigos LDPC posibles.

El método de especificar un código mediante una matriz de verificación generalmente se acepta para códigos lineales, cuando cada fila de la matriz es un elemento de un determinado conjunto de palabras de código. Si todas las filas son linealmente independientes, las filas de la matriz se pueden considerar como la base del conjunto de todos los vectores de código del código. Sin embargo, el uso de este método crea dificultades para representar la matriz en la memoria del codificador: es necesario almacenar todas las filas o columnas de la matriz como un conjunto de vectores binarios, por lo que el tamaño de la matriz se vuelve igual a bits . . ${\ estilo de visualización j \ veces k}$

Una forma gráfica común es representar el código como un gráfico bipartito. Comparemos todas las filas de la matriz con los vértices inferiores del gráfico y todas las columnas con los vértices superiores, y conectemos los vértices superior e inferior del gráfico si hay unidades en la intersección de las filas y columnas correspondientes. $k$ $k$ $norte$

Otros métodos gráficos incluyen transformaciones de gráficos bipartitos que ocurren sin cambiar realmente el código en sí. Por ejemplo, puede representar todos los vértices superiores del gráfico como triángulos y todos los vértices inferiores como cuadrados y luego organizar los bordes y vértices del gráfico en una superficie bidimensional en un orden que sea conveniente para la comprensión visual de la estructura del código. Por ejemplo, tal representación se usa como ilustraciones en libros de David McKay.

Mediante la introducción de reglas adicionales para la visualización gráfica y la construcción del código LDPC, es posible lograr que el código reciba ciertas propiedades durante el proceso de construcción. Por ejemplo, si usamos un gráfico cuyos vértices son solo las columnas de la matriz de control, y las filas están representadas por poliedros construidos sobre los vértices del gráfico, entonces seguir la regla "dos poliedros no comparten un borde" nos permite deshacerse de los ciclos de longitud 4.

Cuando se utilizan procedimientos especiales de construcción de código, se pueden utilizar sus propios métodos de representación, almacenamiento y procesamiento (codificación y decodificación).

Construcción de código

Actualmente, se utilizan dos principios para construir una matriz de verificación de código. El primero se basa en generar una matriz de verificación inicial utilizando un generador pseudoaleatorio. Los códigos obtenidos de esta forma se denominan aleatorios ( en inglés random-like codes ). El segundo es el uso de métodos especiales basados, por ejemplo, en grupos y campos finales . Los códigos obtenidos por estos métodos se denominan códigos estructurados . Son los códigos aleatorios los que muestran mejores resultados en la corrección de errores, sin embargo, los códigos estructurados permiten utilizar métodos para optimizar los procedimientos de almacenamiento, codificación y decodificación, así como obtener códigos con características más predecibles.

En su trabajo, Gallagher optó por utilizar un generador de números pseudoaleatorios para crear una matriz de comprobación inicial de pequeño tamaño con características específicas y luego aumentar su tamaño duplicando la matriz [6] y utilizando el método de mezclar filas y columnas para obtener librarse de ciclos de cierta duración.

En 2003, James McGowan y Robert Williamson propusieron una forma de eliminar ciclos de la matriz de un código LDPC y, por lo tanto, fue posible generar primero una matriz con características dadas (n, j, k) y luego eliminar ciclos de ella. Esto es lo que sucede en el esquema Ozarov-Weiner [7] .

En 2007, se publicó un artículo en la revista "IEEE Transactions on Information Threory" sobre el uso de campos finitos para construir códigos LDPC cuasicíclicos para canales de ruido gaussiano blanco aditivo y canales de borrado binario.

Para aumentar la dimensión del código, se puede utilizar un producto final múltiple de generar matrices [6] .

Decodificación

Como para cualquier otro código lineal, la propiedad de ortogonalidad de las matrices de verificación generadora y transpuesta se utiliza para decodificar:

G\odot H^{T}=0

donde es la matriz generadora, y es la matriz de control , es el símbolo de la multiplicación módulo 2 (si se obtiene como elemento de la matriz resultante un número que es múltiplo de 2, entonces se escribe cero en su lugar). Entonces, para cada palabra de código recibida sin errores, la relación $GRAMO$ $H$ $\odot$

s=v\odot H^{T}=0

y para la palabra de código recibida con un error:

s=v\odot H^{T}\neq 0

donde es el vector aceptado, es el síndrome . Si después de multiplicar la palabra de código recibida por la matriz de paridad transpuesta se obtiene cero, el bloque se considera recibido sin errores. De lo contrario, se utilizan métodos especiales para localizar el error y corregirlo. Para un código LDPC, los métodos de corrección estándar resultan demasiado lentos: se clasifican como problemas NP-completos que, dada la gran longitud del bloque, no se pueden aplicar en la práctica. En su lugar, utilizan el método de decodificación iterativa probabilística, que corrige una gran proporción de errores más allá de la mitad de la distancia del código [8] . $v$ $s$

Considere [9] un canal simétrico sin memoria con entrada y ruido gaussiano aditivo . Para la palabra de código recibida , se necesita encontrar el vector más probable correspondiente , tal que ${\ estilo de visualización \ pm a}$ ${\ estilo de visualización \ sigma ^ {2} = 1}$ $y$ $X$

H\odot x=0\mod 2

definamos $f_{n}^{1}={1/{\mathord {\left(1+\exp \left(-2ay_{n}/{\mathord {\sigma ^{2))}\right) \Correcto)}}}$ ; ${\displaystyle f_{n}^{0}=1-f_{n}^{1))$ ; donde es el valor recibido del símbolo n de la palabra de código (que para un canal determinado tiene un valor arbitrario, generalmente dentro de ). $y_{n}$ ${\ estilo de visualización \ pm (a+3 \ sigma)}$
Usaremos la palabra "bit" para denotar elementos individuales del vector y la palabra "check" para denotar filas de la matriz de verificación . Indicar por el conjunto de bits que participarán en la verificación m-ésima. De manera similar, denotemos el conjunto de comprobaciones en las que participa el bit n. (Es decir, enumeramos los índices de elementos distintos de cero para cada fila y para cada columna de la matriz de verificación ). $X$ $H$ $N\left(m\right)\equiv \{n:H_{nm}=1\}$ $M\left(n\right)\equiv \{m:H_{nm}=1\}$ $H$
Inicializamos matrices y valores y respectivamente $q_{mn}^{0}$ ${\displaystyle q_{mn}^{1))$ $f_{n}^{0}$ ${\ Displaystyle f_ {n}^ {1}}$
(paso horizontal) $\delta q_{mn}=q_{mn}^{0}-q_{mn}^{1}$ $\delta r_{mn}=\prod \limits _{n'\in N(m)\backslash n}{\delta q_{mn'}}$ $r_{mn}^{0}={1 \over 2}\left({1+\delta r_{mn}}\right)$ $r_{mn}^{1}={1 \over 2}\left({1-\delta r_{mn}}\right)$
(Tono vertical) $q_{mn}^{0}=\alpha _{mn}f_{n}^{0}\prod \limits _{m'\in M\left(n\right)\backslash m}{r_ {m'n}^{0}}$ $q_{mn}^{1}=\alpha _{mn}f_{n}^{1}\prod \limits _{m'\in M\left(n\right)\backslash m}{r_ {m'n}^{1}}$ donde para cada uno y elegido da: $metro$ $norte$ ${\ estilo de visualización \ alfa _ {mn}}$ $q_{mn}^{0}+q_{mn}^{1}=1$ Ahora también actualizamos las "probabilidades pseudo-posteriores" de que los bits del vector tomen los valores 0 o 1: $X$ $q_{n}^{0}=\alpha _{n}f_{n}^{0}\prod \limits _{m\in M\left(n\right)}{r_{mn}^ {0}}$ $q_{n}^{1}=\alpha _{n}f_{n}^{1}\prod \limits _{m\in M\left(n\right)}{r_{mn}^ {una}}$ También, como antes, se elige de tal manera que $\alpha_{n}$ $q_{n}^{0}+q_{n}^{1}=1$

Estos valores se utilizan para recrear el vector x. Si el vector resultante satisface , entonces se interrumpe el algoritmo, de lo contrario se repiten los pasos horizontales y verticales. Si el algoritmo continúa hasta cierto paso (por ejemplo, 100), entonces se interrumpe y el bloque se declara aceptado con un error. $H\odot x=0\mod 2$

Se sabe que este algoritmo da el valor exacto del vector (es decir, coincidiendo con los métodos clásicos) si la matriz de verificación no contiene ciclos [10] . $X$ $H$

Notas

↑ Shannon CE Una teoría matemática de la comunicación // Bell System Technical Journal. - 1948 . - T. 27 . - S. 379-423, 623-656 .
↑ Gallager, R. G. Códigos de verificación de paridad de baja densidad . —Cambridge : MIT Press , 1963 . — Pág. 90.
↑ David JC MacKay y Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes", Electronics Letters, julio de 1996
↑ David JC Mackay. Teoría de la información, inferencia y algoritmos de aprendizaje . - COPA, 2003. - ISBN 0-521-64298-1 .
↑ Dra. Lin Nan Lee. Códigos LDPC, Aplicación a Sistemas de Comunicación de Próxima Generación // Conferencia Semestral de Tecnología Vehicular IEEE. - Octubre de 2003. Archivado desde el original el 8 de octubre de 2006.
↑ 1 2 Slyusar V. I. Síntesis de LDPC y códigos polares basados en el producto final de matrices.// Desarrollo de la Educación, la Ciencia y los Negocios: Resultados 2020: resúmenes de la Conferencia Internacional Científica y Práctica de Internet, 3 y 4 de diciembre de 2020. – Parte 2. - Págs. 393-396. [1] Archivado el 25 de enero de 2021 en Wayback Machine .
↑ Yu.V. Kosolapov. Sobre la aplicación del esquema Ozarov-Weiner para la protección de la información en los sistemas inalámbricos de transmisión de datos multicanal // Contrarrestación de la información frente a las amenazas terroristas: Revista científica y práctica. — 2007 . - N º 10 . - S. 111-120 . Archivado desde el original el 24 de junio de 2013.
↑ V. B. Afanasiev, D. K. Zigangirov "Sobre algunas construcciones de códigos de baja densidad con un componente de código Reed-Solomon"
↑ David JC MacKay, Radford M. Neal Near Shannon Limit Performance of Low Density Parity Check Codes . Consultado el 28 de agosto de 2008. Archivado desde el original el 17 de abril de 2007. (indefinido)
↑ J. Perla. Razonamiento Probabilístico en Sistemas Inteligentes: Redes de Inferencia Plausible. Morgan Kaufmann, San Mateo, 1988.