¿Cuántos errores se pueden corregir cuando la distancia de Hamming de un código de bloque es 18?
Usa codificación aleatoria;
La longitud de la palabra clave tiende al infinito;
Usa máxima verosimilitud. Algoritmo de decodificación.
El código seleccionado aleatoriamente es un buen código con una alta probabilidad. Para la decodificación de máxima probabilidad de códigos aleatorios, la complejidad de decodificación G está relacionada exponencialmente con el número de bits de información transmitidos, es decir, G=exp(NR). El límite superior de la tasa de error de bits de los códigos aleatorios es PE ~ G-EB (R)/R A medida que la longitud del código N se acerca al infinito, la complejidad de la decodificación aumenta exponencialmente, lo que indica que los códigos aleatorios no son prácticos en los sistemas reales.
Debido a que se ha demostrado que el teorema de codificación de canales no es constructivo, no se proporciona ningún método de codificación para construir un código de corrección de errores cercano al límite de capacidad de Shannon. La construcción de un código de corrección de errores cercano al límite de capacidad de Shannon se ha convertido en un punto de investigación para muchos académicos y gradualmente ha formado una rama importante de la teoría de la información: la teoría de la codificación de canales.
En términos de métodos de construcción, los códigos de corrección de errores se pueden dividir en dos categorías: códigos de bloque y códigos convolucionales. Desde la década de 1950 hasta la de 1960, la gente estudiaba principalmente códigos de bloques lineales. Este tipo de codificación se basa en la teoría de grupos y la teoría de campos en álgebra, utiliza varios métodos algebraicos para diseñar códigos de corrección de errores y estudia los algoritmos de decodificación correspondientes.
El primer código de bloque fue el código Hamming descubierto en 1950, que podía corregir un solo error. El artículo de Hanmming R.W "Códigos de detección y corrección de errores" publicado en 1950 fue el primer artículo que amplió el estudio de la teoría de la codificación para considerar la corrección de errores individuales en las computadoras. Código Hamming (7, 4), la tasa de código es 4/7, requiere 3 bits de supervisión, la tasa de código es baja, la capacidad de corrección de errores es limitada y solo puede corregir un único error.
Meter (abreviatura de metro)) Golay propuso un código Galay con mejor rendimiento para superar las deficiencias del código Hamming. Golay descubrió dos códigos, uno es el código binario de Golay, que es un grupo de 12 bits de datos y 11 dígitos de control, y puede corregir tres errores. El segundo tipo es el código Golay ternario, que utiliza números ternarios como campo de operación, 6 símbolos de datos y 5 símbolos de verificación como grupo, y puede corregir 2 errores.
Los principios básicos de ambos códigos son los mismos. Dividen los símbolos Q en un grupo cada k y luego obtienen n-k símbolos Q como símbolos de verificación redundantes mediante codificación. Finalmente, el símbolo de verificación y el símbolo de información forman un subsímbolo codificado con N Q símbolos, y la tasa de codificación es r = k/n.
En 1954, Mueller propuso a Reed. Código de Muller (código RM) del álgebra de lógica booleana. Es superior al código Hamming y al código Gray porque puede cambiar el tamaño de la palabra clave y las capacidades de corrección de errores. Es un nuevo código de bloque obtenido por Reed basado en Muller. Es el código de bloque más importante después del código Gray.
Siguiendo el código RM, Prange propuso el concepto de códigos cíclicos en 1957. El código cíclico es en realidad un tipo de código de bloque, pero su palabra de código tiene características de cambio cíclico, es decir, los bits de la palabra de código después del cambio cíclico siguen siendo las palabras de código en el conjunto de palabras de código. Esta estructura de bucle aumenta en gran medida la gama de diseño de palabras de código y simplifica enormemente la estructura de codificación y decodificación.
Un subconjunto muy importante de códigos cíclicos es el código BCH (Bose Chuadhuri Hocquen em) propuesto por Hocquenghem en 1959 y los grupos de investigación Bose y Ray-Chuadhuri en 1960. La longitud de la palabra clave del código CH es n=qm-1, donde m es un número entero. La capacidad de corrección de errores del código BCH binario (q=2) está limitada a t (2m-1).
En 1960, Reed y Solomon ampliaron el código BCH a no binario (Q) 2, dando como resultado el código RS (Reed. Solomon). La mayor ventaja del código RS es que sus características no binarias pueden corregir errores de ráfaga y fusión, y también pueden corregir errores aleatorios.
Sin embargo, no fue hasta que Berlekamp dio un algoritmo de decodificación muy efectivo en 1967 que los códigos RS aparecieron en sistemas reales como reproductores de CD, reproductores de DVD y el estándar CDPD (Cellular Digital Packet Data).
Estos son los códigos de bloqueo comentados anteriormente. Los códigos de bloque tienen algunas deficiencias y sus aplicaciones son limitadas. En primer lugar, debe transmitirse cuadro por cuadro y decodificarse cuadro por cuadro. Cuando el cuadro es largo, provocará un cierto retraso. En segundo lugar, para una decodificación precisa, se requiere una sincronización de cuadros precisa. La mayoría de los códigos de bloque requieren una salida de decisión difícil del demodulador, lo que provocará algunos errores de decisión y afectará el rendimiento. Además, el método de decodificación de códigos de bloque generalmente adopta decodificación lógica de números grandes y decodificación de detección de errores, y la complejidad de la decodificación tiene una relación exponencial con la longitud del código. Cuanto mayor es la longitud del código, mayor es la complejidad de la decodificación y la tendencia ascendente es muy rápida, por lo que básicamente no es práctico.
En 1955, Elias y otros propusieron por primera vez códigos convolucionales. Los códigos convolucionales no separan los datos en diferentes grupos, sino que agregan bits de verificación al flujo de datos de entrada a través de un registro de desplazamiento. Cada salida de N bits es una combinación lineal de la entrada actual de K bits y los M bits en el registro. El número total de bits generados cada vez está relacionado con la longitud de restricción K, y su velocidad de código es la relación entre los bits de datos K y los bits de salida N dentro de un intervalo de codificación.
La diferencia entre códigos convolucionales y códigos de bloque es que introduce registros en el proceso de codificación, aumenta la correlación entre símbolos y puede obtener una codificación mayor que los códigos de bloque con la misma ganancia, pero esta correlación también. aumenta la complejidad del análisis y diseño de códigos convolucionales.
Con la profundización de la investigación sobre códigos convolucionales, han aparecido algoritmos de decodificación de secuencia, algoritmos de decodificación de umbral y algoritmos de decodificación de Viterbi en los algoritmos de decodificación de códigos convolucionales.
Con la aparición del algoritmo de decodificación de Viterbi, los códigos convolucionales se han convertido gradualmente en un punto caliente en la investigación y la aplicación de la tecnología TCM (modulación de codificación enrejada) que ha establecido aún más el dominio de los códigos convolucionales en las aplicaciones de códigos de corrección de errores. estado, especialmente en los sistemas de comunicación.