1.5: Teoría de la codificación

En la mente de muchas personas, los “códigos” y la “criptografía” están inextricablemente vinculados, y pueden ser difíciles de decirte la diferencia. Sin embargo, los dos temas son muy diferentes, al igual que las matemáticas involucradas en ellos.

La teoría de codificación es el estudio de la codificación de información en diferentes símbolos. Cuando alguien usa un código en un intento de hacer un mensaje que solo ciertas otras personas pueden leer, esto se convierte en criptografía. Los criptógrafos estudian estrategias para asegurar que un código sea difícil de “romper” para quienes no tienen alguna información adicional. En la teoría de la codificación, ignoramos la cuestión de quién tiene acceso al código y qué tan secreto puede ser. En cambio, una de las principales preocupaciones se convierte en nuestra capacidad para detectar y corregir errores en el código.

Los códigos se utilizan para muchos fines en los que la información no pretende ser secreta. Por ejemplo, los programas informáticos se transforman en largas cadenas de datos binarios, que una computadora reinterpreta como instrucciones. Cuando envía una foto por mensaje de texto a un amigo, la información de píxeles y color se convierte en datos binarios para ser transmitidos a través de ondas de radio. Cuando escuchas un archivo.mp3, las frecuencias de sonido de la música se han convertido en datos binarios que tu computadora decodifica de nuevo en frecuencias de sonido.

La codificación electrónica siempre está sujeta a interferencias, lo que puede provocar errores. Incluso cuando un mensaje codificado se graba físicamente en un dispositivo (como un dvd), los arañazos pueden hacer que algunas partes del código sean ilegibles. A la gente no le gusta cuando sus películas, música o aplicaciones se congelan, se estrellan o se saltan algo. Para evitar este problema, los ingenieros utilizan códigos que permiten a nuestros dispositivos detectar y corregir automáticamente errores menores que se puedan introducir.

En la teoría de la codificación, aprendemos a crear códigos que permitan la detección y corrección de errores, sin requerir una memoria excesiva o capacidad de almacenamiento. Aunque la teoría de la codificación no es un foco de este curso, los diseños pueden ser utilizados para crear buenos códigos. Aprenderemos a hacer códigos a partir de diseños, y qué hace que estos códigos sean “buenos”.

Ejemplo\(\PageIndex{1}\)

Supongamos que tenemos una cadena de información binaria, y queremos que la computadora la almacene para que podamos detectar si ha surgido algún error. Hay dos símbolos que necesitamos codificar: 0 y 1. Si solo usamos 0 para 0 y 1 para 1, nunca sabremos si se ha volteado un bit (de 0 a 1 o viceversa). Si usamos 00 para 0 y 01 para 1, entonces si se voltea el primer bit sabremos que hubo un error (porque el primer bit nunca debería ser 1), pero no notaremos si el segundo fue volteado. Si usamos 00 para 0 y 11 para 1, entonces podremos detectar un error, siempre y cuando como máximo se voltee un bit, ya que voltear un bit de cualquiera de las dos palabras de código dará como resultado 01 o 10, ninguna de las cuales es una palabra de código válida. Así, este código nos permite detectar un error. No nos permite corregir un error, pues aun sabiendo que un solo bit ha sido volteado, no hay manera de saber si un 10 surgió de un 00 con el primer bit volteado, o de un 11 con el segundo bit volteado. Necesitaríamos un código más largo para poder corregir errores.

Después de nuestro estudio de la teoría de la codificación, deberías ser capaz de resolver problemas como:

• Dado un código, ¿cuántos errores se pueden detectar?
• Dado un código, ¿cuántos errores se pueden corregir?
• Construir algunos códigos pequeños que permitan la detección y corrección de pequeños números de errores.

Ejercicio\(\PageIndex{1}\)

¿Se te ocurre un interesante problema de conteo que no sabrías resolver?