Tiene corrección de errores sido "resuelto"?

Question

Recientemente me encontré Dan Piponi en el blog de Un Final a la Teoría de la Codificación , y me dejó muy confundido. La parte pertinente es:

Pero en los años sesenta, Robert Gallagher miró a la generación aleatoria dispersa con síndrome de matrices y se encontró que el resultado de los códigos, llamados de Baja Densidad de Comprobación de Paridad (LDPC) códigos, fueron buenos en el sentido de que permite la transmisión de mensajes en las tasas cerca de la tasa óptima encontrada por Shannon - el llamado límite de Shannon. Por desgracia, los equipos de el día no estaban a la tarea de encontrar la más probable elemento de M a partir de un elemento dado de C., Pero que ahora están. Ahora tenemos cerca de lo óptimo códigos de corrección de errores y el diseño de estos códigos es ridículamente simple. No había ninguna necesidad de utilizar exóticas matemáticas, matrices aleatorias son tan buenos como casi cualquier otra cosa. Los últimos cuarenta años de la teoría de la codificación ha sido, más o menos, un inútil excursión. Cualquier investigación adicional en el área sólo puede producir pequeñas mejoras.

En resumen, el orador señala que la tasa de códigos LDPC es muy cerca de la capacidad del canal-tan cerca que otras mejoras no valdría la pena el tiempo.

Entonces, mi pregunta es: ¿Qué hace la investigación moderna en la corrección de errores códigos de hacer? Me di cuenta de que Dan no mencionar lo que el canal de la tasa de códigos LDPC enfoque de la capacidad, así que tal vez existen canales que los códigos LDPC no funcionan bien? ¿Qué otras indicaciones que hace la moderna investigación en el campo de explorar?

Answer 1

Esto es cierto en gran medida en el sentido de que a largo códigos LDPC están dentro de una fracción de un dB del límite de Shannon en canal AWGN. Su diseño (por un proceso llamado densidad de la evolución - no me mires, yo no sé la de matemáticas) también parece ser relativamente simple. Depende estocástico de matemáticas frente al álgebra/combinatoria finita campos/anillos.

Mi limitada experiencia, sólo me permite hacer las siguientes observaciones:

1. La longitud de los bloques de un código LDPC debe ser relativamente grande. Este es uno de los motivos por los que no fueron elegidos para LTE estándar (Europa/Asia 4G celular estándar). Mi entendimiento sobre el `mejor' código en un canal de radio es (como una función de la cuadra longitud): menos de 100 bits => el uso de una expresión algebraica bloque de código, entre 40 y 400 bits => el uso de un código convolucional, 300-20000 bits => el uso de un turbo código de 5000 bits+ => el uso de un código LDPC (los intervalos se superponen como soy no dispuesto a apostar que la fortuna de la familia en uno de ellos). Si mal no recuerdo esta es la forma en que se hace en LTE, excepto que en ese celular estándar el más largo bloque de datos ha 6144 bits (por lo manejan con un turbo código).
2. El diseño de un código LDPC necesidades a tener en cuenta es que por lo general no es práctico en base a un azar Tanner gráfico de la prescripción de la distribución del peso. En particular, cuando se supone que debe ser utilizado en un dispositivo de mano. El problema de enrutamiento de la creencia algoritmo de propagación se convierte en prohibitivo de otra manera. Así que los códigos LDPC especificado para la radio estándares de comunicación de un par de años atrás (DVB-S/T2 en Europa, Mediaflo en los estados unidos) fueron diseñados en torno a un particular de la decodificación de los circuitos, o más bien el Curtidor gráficos tuvo que venir de un determinado tipo de familia. Nunca he sido realmente la velocidad de estos aspectos, por lo que algunos de progreso se haya realizado.
3. Cuanto más alto es el orden de modulación se utiliza hay más problemas y consideraciones que deben ser tomadas en cuenta. No es enteramente obvio que debemos atenernos a los códigos LDPC basado en bits solo en ese caso, ya que el canal que va a crear dependencias entre los LLRs de bits individuales. Pero el BP algoritmo se vuelve muy complicado, si queremos alimentar a algo distinto de LLRs de bits individuales.
4. Deshacerse de los errores de los pisos es todavía un reto. Por desgracia, no estoy a la velocidad con que cualquiera de los dos. Posibles soluciones implican el uso de catenated código con un peso ligero algebraicas exterior código de manejo de los errores residuales.

Advertencia: sólo he estudiado este curiosamente (suficiente para implementar un código LDPC y analizar algunos de ellos). Estos son los recuerdos y las impresiones del lugar de los hechos. Usted puede obtener las actas de las reuniones pertinentes del grupo de trabajo encargado de este dentro de LTE en las páginas web de 3GPP (=third generation partnership project).

Otros tipos de códigos seguirá siendo útil para fines específicos. No hay ningún sustituto para RS (o AG, si usted necesita más bloques), cuando sólo se han duro byte errores. LDPC (y Turbo) códigos están diseñados con suaves errores de bit (=estimaciones de la confiabilidad de bits) en mente. Esto es una suposición válida en la comunicación inalámbrica. También la red de codificación que parece ser un tema candente en la actualidad. Allí el código que opera en el nivel de paquetes de datos que puede o no puede llegar a todos. También buscar Raptor código, si este tipo de problemas son de interés para usted.

Algebraicas teoría de la codificación no está muerto aún, pero sí concentrarse en los problemas de otros que el diseño de los ECCs para la transmisión masiva de datos. Una expresión algebraica de la maquinaria rendimiento código LDPC diseños garantizados, tienen muy bajos de error de pisos (= alto mínimo de la distancia de Hamming) puede ser por ahí, pero no sé lo que sería.

Answer 2

Para hacer corta una historia larga: No, no hay ningún final a la teoría de la codificación! Sí, existen muchos códigos, en los que va a operar (al menos para los simples modelos de canal) en el plazo de una fracción de la dB del límite de Shannon. Para mencionar algunos: turbo-códigos, códigos LDPC, y otros.

Recientemente, Arikan inventó los llamados "polar" códigos que son (en teoría) probada para alcanzar el límite de Shannon infinitamente largo palabras de código. Estos son los primeros códigos, por lo que dicha prueba está dado. La decodificación de estos polar códigos se realiza mediante (por ejemplo) sucesivos de cancelación de interferencia (SIC) decodificador o en la creencia de propagación (BP) en el descodificador.

El inconveniente de polar códigos se basa en su código de construcción, es decir, encontrar la posición de los llamados "congelado bits" (código de posiciones de bits). Por BEC y BSC canales, esto se puede solucionar en un corto período de tiempo. (Por supuesto, sólo para finito de código longitudes de palabra!) Para otros modelos de canal con un binario de entrada y salida continua de distribución, el hallazgo de los congelados de las posiciones no es trivial!

Para resumir todo: En mi opinión, ahora tenemos un código (código polar), que se ha demostrado que para alcanzar el límite de Shannon infinitamente largo palabras de código. Pero, en la práctica, el código necesita una gran palabra de código longitudes para acercarse a la interpretación de otros códigos (LDPC y otros). En (por ejemplo) la comunicación inalámbrica, la gran palabra de código longitudes de no uso, como el cambio de canal durante el tiempo y los retrasos en un CUESTIONARIO son cada vez más grandes. Por lo tanto, bastante buena códigos para los pequeños códigos de palabra de longitud (en la práctica) es necesario.

Mis 2 centavos.

Answer 3

Yo no puedo decir que soy un experto en la corrección de errores, pero sé algunas cosas.

Si recuerdo correctamente, la decodificación de un LDPC puede ser muy difícil si usted desea operar cerca de su capacidad máxima en un canal ruidoso con gran ancho de banda. Y la latencia puede ser un problema si usted necesita usar mucho los códigos.

También, si mal no recuerdo, LDPC son buenas para el uniforme de ruido, pero el ruido no es siempre uniforme. En muchos canales, el ruido viene en ráfagas, por lo que hay un reto en el diseño de esquemas de corrección de error que de manera eficiente proteger contra las ráfagas de ruido.

Y, por supuesto, las matemáticas involucradas en el diseño de ECC se aplica a tareas distintas de la comunicación a través de un canal. Algunos problemas matemáticos puede ser configurado de forma que puedan resolverse directamente por los diversos tipos de códigos. También, yo creo mucho en el desarrollo de los eficientes finito campo de la aritmética y el polinomio de algoritmos fue motivado por la investigación eficiente de corrección de errores.