La tasa de corrección de errores es engañosa

10

En la teoría de la codificación, "qué tan bueno es un código" significa cuántos errores de canal pueden corregirse, o mejor dicho, el nivel de ruido máximo con el que puede lidiar el código.

Para obtener mejores códigos, los códigos están diseñados con un alfabeto grande (en lugar de uno binario). Y luego, el código es bueno si puede manejar una gran cantidad de "símbolos" erróneos.

¿Por qué no se considera hacer trampa? Quiero decir, ¿no deberíamos preocuparnos solo por lo que sucede cuando "traducimos" cada símbolo en una cadena binaria? La "tasa de error de bit" es diferente de la tasa de "error de símbolo". Por ejemplo, la tasa de error de bit no puede superar 1/2 mientras que (si entiendo esto correctamente), con un alfabeto lo suficientemente grande, el error de símbolo puede subir a . ¿Es esto porque restringimos artificialmente el canal para que cambie solo "símbolos" en lugar de bits, o es porque el código es realmente mejor?1−ϵ

information-theory coding-theory Sonó.
fuente
1
¿Por qué se limitaría a los códigos binarios si su medio / tecnología de transmisión puede manejar muchos más?
Raphael
@Raphael Sería útil si pudieras justificar tu punto con algunos ejemplos prácticos de tecnologías de la vida real que manejan símbolos no binarios y publicar eso como respuesta.
Mohammad Alaggan
@ M.Alaggan: No soy un experto en esto; Me imagino que si puede codificar 0/1 en una portadora de ondas, también puede codificar muchos más símbolos, transmitiendo más información por intervalo de tiempo. Me sorprendería si la tecnología moderna no hiciera esto (piense en la multiplexación de código) pero no puedo nombrar un ejemplo concreto.
Raphael
@Raphael Creo que tiene razón, los canales de comunicación digital actuales sí funcionan con símbolos más grandes, pero no más de, digamos, 256 bits por símbolo (lo cual es bastante raro para la conexión inalámbrica, pero puede ser común para los cables). Pero el tamaño del símbolo está limitado a tamaños muy pequeños y no puede (prácticamente) crecer a voluntad.
Ran G.

Respuestas:

8

Muchos códigos ampliamente utilizados para datos binarios son códigos concatenados, que se componen mediante el uso de dos códigos de corrección de errores. El código interno está sobre un alfabeto binario, y el código externo está sobre un alfabeto cuyos símbolos corresponden a las palabras de código del código interno. Esto le permite utilizar la potencia superior de los tamaños de alfabeto más grandes para codificar mensajes binarios sin "hacer trampa".

La definición estándar de distancia mínima es natural cuando se consideran códigos concatenados, así como en la teoría de códigos sobre tamaños de alfabeto grandes. Solo sería "trampa" si usara estos números para comparar un código binario con un código de alfabeto grande que codifica la entrada binaria sin usar también un código interno; los teóricos de la codificación son lo suficientemente inteligentes como para no hacer esto (y creo que desde que se inventaron los códigos concatenados, los códigos de alfabeto grande a menudo se han usado junto con un código interno, pero los códigos de alfabeto grande también son muy buenos para corregir errores en canales con ráfagas). como CD, ya que una gran cantidad de errores de bits consecutivos solo afectará a unos pocos "símbolos").

Peter Shor
fuente
Peter, gracias por la respuesta. Para un código concatenado, ¿no es cierto que la tasa de error (bit) no puede exceder 1/2? así que este método solo nos permite acercarnos a 1/2 mientras mantenemos la decodificación eficiente, ¿verdad?
Ran G.
@Ran: para un código binario , la tasa de error de bits no puede exceder 1/2. Los códigos concatenados no necesitan ser binarios. Pero eso es quisquilloso; tu comentario es esencialmente correcto
Peter Shor