Código de bloque

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 15 de enero de 2019; las comprobaciones requieren 2 ediciones .

Un código de bloque  es un tipo de codificación de canal en informática. Aumenta la redundancia del mensaje para que el receptor pueda descifrarlo con un error mínimo (teóricamente cero), siempre que la tasa de transferencia de información (la cantidad de información transmitida en bits por segundo) no supere el rendimiento del canal .

La característica principal de un código de bloque es que es un código de canal de longitud fija (a diferencia de un esquema de codificación de fuente de datos como la codificación de Huffman , y en contraste con los métodos de codificación de canal como la codificación convolucional (codificación "convolucional")). Normalmente, un sistema de codificación de bloques toma una palabra de código W de k dígitos como entrada y la convierte en una palabra de código C(W) de n dígitos . Esta palabra clave se llama bloque.

La codificación de bloques fue el principal tipo de codificación utilizado en los primeros sistemas de comunicación móvil.

Formal definición

Un código de bloque es un código que codifica secuencias de conjuntos de caracteres del alfabeto S en palabras de código, convirtiendo cada carácter de S por separado. Sea  una sucesión de números naturales , cada uno menor que |S| . Si alguna palabra W del alfabeto S se escribe como , entonces la palabra código correspondiente a W , a saber, C(W) , será: .

[n, d]

La compensación entre la eficiencia (tasa de información más alta) y las capacidades de aplicación de parches también se puede ver cuando se intenta establecer una longitud de palabra clave fija y una capacidad de aplicación de parches fija (representada por la distancia de Hamming d ) y maximizar la cantidad total de palabras clave. [n, d]  es el número máximo de palabras clave para una determinada longitud de palabra clave n y distancia de Hamming d .

Normas de información

Cuando C  es un código de doble bloque que consta de palabras clave A de n bits de longitud , la norma de información de C se define como:

.

En el caso de que los primeros k bits de la palabra clave sean bits de información independientes, la norma de información se verá así:

.

Empaquetaduras esféricas y celosías

Los códigos de bloque están relacionados con el problema del empaquetamiento esférico, que ha llamado la atención en los últimos años. En dos dimensiones, es fácil visualizarlo tomando un puñado de monedas idénticas y alineándolas sobre la mesa en forma de hexágono, como en un panal. Sin embargo, en grandes dimensiones, los códigos de bloque no se pueden visualizar tan fácilmente. El fuerte código Golay utilizado en las comunicaciones en el espacio profundo utiliza 24 dimensiones. Si se usa binario (como se hace habitualmente), las medidas se refieren a la longitud de la palabra clave como se define anteriormente.

La teoría de la codificación utiliza el modelo de esfera N-dimensional. Por ejemplo, cuántas monedas se pueden colocar en un círculo sobre la superficie de una mesa, o en 3 dimensiones, cuánta canica se puede colocar en un globo. Otras consideraciones entran en la elección de un código. Por ejemplo, un hexágono colocado en una caja rectangular delimitada dejará un espacio vacío en las esquinas. A medida que aumentan las dimensiones, el porcentaje de espacio vacío se vuelve más pequeño. Pero en ciertas dimensiones, todo el lugar está lleno, y estos códigos son los llamados códigos perfectos. Pero hay muy pocos de ellos.

Otro elemento que a menudo se pasa por alto es la cantidad de vecinos que puede tener una sola palabra clave. Nuevamente, usaremos monedas como ejemplo. Primero los apilamos en una cuadrícula rectangular. Cada moneda tendrá 4 vecinos cercanos (y 4 en las esquinas más alejadas). En el hexágono, cada moneda tendrá 6 vecinos cercanos. A medida que aumentamos el número de dimensiones, el número de vecinos cercanos crece muy rápidamente.

El resultado es también un aumento en el número de rutas en las que el ruido obligaría al receptor a elegir un vecino; de ahí el error. Esta es una limitación fundamental de los códigos de bloque y, de hecho, de todos los códigos. Puede ser más difícil que un solo vecino cause un error, pero la cantidad de vecinos puede ser lo suficientemente grande como para que la probabilidad total de error sea realmente posible.

Literatura