Clasificación principal de codificación fuente
El código LT (Luby Transform) propuesto por M. Luby es el primer código fuente práctico. Es un código no sistemático construido sobre la base de gráficos bipartitos dispersos irregulares. El algoritmo de codificación es el siguiente:
1. Suponiendo que el número de símbolos de entrada es , el codificador primero selecciona un número entero en el rango de 1 ~ que obedece a una determinada distribución como el grado del símbolo codificado
2. Seleccione aleatoria y uniformemente símbolos de todos los símbolos de entrada como símbolos de nodo vecino del símbolo de codificación
3. XOR este símbolo de entrada para obtener un símbolo de codificación
Todos los símbolos de codificación se generan de forma independiente mediante este proceso.
El código LT se decodifica mediante un método iterativo. En cada paso de la decodificación, el decodificador busca símbolos con grado 1 en el conjunto de símbolos codificados para recuperar directamente los símbolos de entrada a los que están conectados, y luego aplica XOR a estos símbolos de entrada con los símbolos codificados conectados a ellos y el resultado reemplaza el original. El valor del símbolo de codificación se elimina una vez completado, la relación de conexión entre ellos y el grado del símbolo de codificación se modifica en consecuencia. Repita el proceso anterior hasta que no queden símbolos con grado 1. La decodificación se realiza correctamente si se recuperan todos los símbolos de entrada; de lo contrario, la decodificación falla.
La complejidad aritmética promedio de codificar y decodificar el símbolo de unidad del código LT (operación de símbolo XOR) es ambas, que es mucho menor que la del código RS clásico (el código RS es). En promedio, el extremo receptor solo necesita recibir un poco más que los símbolos de codificación () para decodificar exitosamente con una probabilidad de.
La parte fraccionaria de la relación entre el número de símbolos de codificación necesarios para una decodificación exitosa y los símbolos de entrada originales se denomina sobrecarga de decodificación. El código LT en realidad reduce la complejidad de codificación y decodificación al aumentar ligeramente cierta sobrecarga de decodificación (la sobrecarga de decodificación del código RS es 0). El código Raptor es una versión mejorada del código LT. Primero precodifica la información original y luego utiliza un código LT debilitado para codificar los datos y enviarlos. El código LT debilitado puede recuperar la mayoría de los símbolos con una alta probabilidad, mientras que los símbolos restantes dependen de la precodificación para recuperarse. Al optimizar conjuntamente las velocidades de código y los parámetros de estas dos partes de la codificación, Raptor puede lograr una mayor tasa de éxito de decodificación con la misma sobrecarga de decodificación.
La complejidad aritmética promedio de codificar y decodificar el símbolo de unidad del código Raptor es , donde está la sobrecarga de decodificación. Por lo tanto, la complejidad unitaria de codificación y decodificación del código Raptor tiene una relación lineal con la longitud del código, lo cual es una mejora con respecto a la relación logarítmica del código LT. Si el algoritmo de codificación del código LT se mantiene sin cambios y solo se cambia el algoritmo de decodificación, y se usa un decodificador llamado RU para reemplazar el decodificador BP usado en el código LT, se genera un nuevo tipo de código fuente, llamado código RU. Necesita volver a optimizar la distribución del grado de codificación de acuerdo con las características del decodificador RU. Dado que el decodificador RU utiliza un algoritmo similar a la eliminación gaussiana, puede obtener una tasa de éxito de decodificación mucho mayor que la decodificación BP. Como precio, su complejidad aumenta. Sin embargo, se puede lograr un buen compromiso entre la complejidad y la tasa de éxito de la decodificación optimizando el diseño mediante la generación de triangulación matricial y distribución de grados.