12. Codificaci贸n de canal

En este cap铆tulo presentamos los conceptos b谩sicos de codificaci贸n de canales, tambi茅n conocido como Forward Error Correction (FEC), el l铆mite de Shannon, los c贸digos Hamming, los turbo c贸digos y los c贸digos LDPC. La codificaci贸n de canal es un 谩rea enorme dentro de las comunicaciones inal谩mbricas y es una rama de la 鈥渢eor铆a de la informaci贸n鈥, que es el estudio de la cuantificaci贸n, almacenamiento y comunicaci贸n de la informaci贸n.

驴Por qu茅 necesitamos codificaci贸n de canales?

Como aprendimos en el capitulo Ruido y dB, los canales inal谩mbricos son ruidosos y los s铆mbolos transmitidos no llegan perfectamente al receptor. Si ha realizado un curso de redes, es posible que ya conozca las comprobaciones de redundancia c铆clica (CRC), las cuales detectan errores en el receptor final. El prop贸sito de la codificaci贸n de canales es detectar y corregir errores en el receptor. Si dejamos cierto margen de error, entonces podremos transmitir con un esquema de modulaci贸n de orden superior, por ejemplo, sin tener un enlace roto. Como ejemplo visual, considere las siguientes constelaciones que muestran QPSK (izquierda) y 16QAM (derecha) bajo la misma cantidad de ruido. QPSK proporciona 2 bits por s铆mbolo, mientras que 16QAM es el doble de la velocidad de datos a 4 bits por s铆mbolo. Pero observe c贸mo en la constelaci贸n QPSK los s铆mbolos tienden a no pasar el l铆mite de decisi贸n del s铆mbolo, o el eje x y el eje y, lo que significa que los s铆mbolos se recibir谩n correctamente. Mientras tanto, en el gr谩fico 16QAM, hay superposici贸n en los grupos y, como resultado, habr谩 muchos s铆mbolos recibidos incorrectamente.

Comparing noisy QPSK and 16QAM to demonstrate why forward error correction, a.k.a. channel coding, is needed

Un CRC fallido generalmente resulta en una retransmisi贸n, al menos cuando se usa un protocolo como TCP. Si Alice le est谩 enviando un mensaje a Bob, preferir铆amos no tener que hacer que Bob le env铆e un mensaje a Alice solicitando la informaci贸n nuevamente. El prop贸sito de la codificaci贸n de canales es transmitir redundancia de la informaci贸n. La redundancia es un mecanismo de seguridad que reduce la cantidad de paquetes err贸neos, retransmisiones o datos perdidos.

Discutimos por qu茅 necesitamos codificaci贸n de canal, as铆 que veamos d贸nde ocurre en la cadena de transmisi贸n-recepci贸n:

The wireless communications transmit receive chain showing both sides of a transceiver

Observe que hay m煤ltiples pasos de codificaci贸n en la cadena de transmisi贸n-recepci贸n. La codificaci贸n fuente, es nuestro primer paso, no es lo mismo que la codificaci贸n de canal; La codificaci贸n de fuente est谩 destinada a comprimir los datos que se transmitir谩n tanto como sea posible, al igual que cuando se comprime un archivo para reducir el espacio ocupado. Es decir, la salida del bloque de codificaci贸n de origen debe ser m谩s peque帽a que la entrada de datos, pero la salida de la codificaci贸n del canal ser谩 mayor que su entrada porque se agrega redundancia.

Tipos de C贸digos

Para realizar la codificaci贸n de canal utilizamos un 鈥渃贸digo de correcci贸n de errores鈥. Este c贸digo nos dice, dados los bits que tenemos que transmitir, 驴qu茅 bits transmitimos realmente? El c贸digo m谩s b谩sico se llama 鈥渃odificaci贸n de repetici贸n鈥, y es cuando simplemente repites un bit N veces seguidas. Para el c贸digo de repetici贸n 3, se transmitir铆a cada bit tres veces:

  • 0 000

  • 1 111

El mensaje 10010110 se transmite como 111000000111000111111000 despu茅s de la codificaci贸n del canal.

Algunos c贸digos funcionan en 鈥渂loques鈥 de bits de entrada, mientras que otros utilizan un enfoque de flujo. Los c贸digos que funcionan en bloques con datos de una longitud definida, se denominan 鈥渃贸digos de bloque鈥, mientras que los c贸digos que funcionan en un flujo de bits, donde la longitud de los datos es arbitraria, se denominan 鈥渃贸digos convolucionales鈥. Estos son los dos tipos principales de c贸digos. Nuestro c贸digo de repetici贸n 3 es un c贸digo de bloque donde cada bloque tiene tres bits.

Adem谩s, estos c贸digos de correcci贸n de errores no se utilizan 煤nicamente en la codificaci贸n de canales para enlaces inal谩mbricos. 驴Alguna vez almacen贸 informaci贸n en un disco duro o SSD y se pregunt贸 c贸mo es posible que nunca haya errores de bits al volver a leer la informaci贸n? Escribir y luego leer de memoria es similar a un sistema de comunicaci贸n. Los controladores de disco duro/SSD tienen correcci贸n de errores incorporada. Es transparente para el sistema operativo y puede ser propietario ya que todo est谩 integrado en el disco duro/SSD. Para medios port谩tiles como CD, la correcci贸n de errores debe estar estandarizada. Los c贸digos Reed-Solomon eran comunes en los CD-ROM.

Code-Rate

Toda correcci贸n de errores incluye alguna forma de redundancia. Eso significa que si queremos transmitir 100 bits de informaci贸n, tendremos que enviar m谩s de 100 bits. 鈥渃ode-rate鈥 es la relaci贸n entre el n煤mero de bits de informaci贸n y el n煤mero total de bits enviados (es decir, informaci贸n m谩s bits de redundancia). Volviendo al ejemplo de codificaci贸n de repetici贸n 3, si tengo 100 bits de informaci贸n, podemos determinar lo siguiente:

  • 300 bits son enviados

  • 脷nicamente 100 bits representan la informaci贸n

  • Code-rate = 100/300 = 1/3

El code-rate siempre ser谩 menor que 1, ya que existe un equilibrio entre redundancia y rendimiento. Un code-rate m谩s baja significa m谩s redundancia y menos rendimiento.

Modulaci贸n y codificaci贸n

En el capitulo Modulaci贸n Digital abordamos el ruido en esquemas de modulaci贸n. Con una SNR baja, necesita un esquema de modulaci贸n de orden bajo (por ejemplo, QPSK) para lidiar con el ruido, y con una SNR alta puede usar modulaci贸n como 256QAM para obtener m谩s bits por segundo. La codificaci贸n de canales es la misma; desea velocidades de c贸digo m谩s bajas con SNR bajas, y con SNR altas puede usar una velocidad de c贸digo de casi 1. Los sistemas de comunicaciones modernos tienen un conjunto de esquemas combinados de modulaci贸n y codificaci贸n, llamados MCS. Cada MCS especifica un esquema de modulaci贸n y un esquema de codificaci贸n que se utilizar谩n en niveles SNR espec铆ficos.

Las comunicaciones modernas cambian de forma adaptativa el MCS en tiempo real seg煤n las condiciones del canal inal谩mbrico. El receptor env铆a informaci贸n sobre la calidad del canal al transmisor. Se deben compartir comentarios antes de que cambie la calidad del canal inal谩mbrico, lo que podr铆a ser del orden de mili segundos (ms). Este proceso adaptativo conduce a comunicaciones con el mayor rendimiento posible y es utilizado por tecnolog铆as modernas como LTE, 5G y WiFi. A continuaci贸n se muestra una visualizaci贸n de una torre de telefon铆a m贸vil que cambia el MCS durante la transmisi贸n a medida que cambia la distancia del usuario a la c茅lula.

Modulation and coding scheme (MCS) visualized using a cellular base station where each ring represents the boundary of a MCS scheme to operate without error

Cuando se utiliza MCS adaptativo, si se grafica el rendimiento sobre la SNR, se obtiene una curva en forma de escalera como la del siguiente gr谩fico. Los protocolos como LTE suelen tener una tabla que indica qu茅 MCS debe usarse y en qu茅 SNR.

Plot of throughput over SNR for various modulation and coding schemes (MCS), leading to a staircase or step shape

Codigo Hamming

Veamos c贸digos de correcci贸n de errores simples. El C贸digo Hamming fue el primer c贸digo no trivial desarrollado. A finales de la d茅cada de 1940, Richard Hamming trabajaba en los Laboratorios Bell, utilizando una computadora electromec谩nica que utilizaba cinta de papel perforada. Cuando se detectaran errores en la m谩quina, 茅sta se detendr铆a y los operadores tendr铆an que arreglarlos. Hamming se sinti贸 frustrado por tener que reiniciar sus programas desde cero debido a errores detectados. Dijo: 鈥淢aldita sea, si la m谩quina puede detectar un error, 驴por qu茅 no puede localizar la posici贸n del error y corregirlo?鈥. Pas贸 los siguientes a帽os desarrollando el C贸digo Hamming para que la computadora pudiera hacer exactamente eso.

En los c贸digos Hamming, se agregan bits adicionales, llamados bits de paridad o bits de verificaci贸n, a la informaci贸n para lograr redundancia. Todas las posiciones de bits que son potencias de dos son bits de paridad: 1, 2, 4, 8, etc. Las otras posiciones de bits son para informaci贸n. La tabla debajo de este p谩rrafo resalta los bits de paridad en verde. Cada bit de paridad 鈥渃ubre鈥 todos los bits donde el AND bit a bit de la paridad y la posici贸n del bit no son cero, marcados con una X roja debajo. Si queremos utilizar un bit de datos, necesitamos los bits de paridad que lo cubren. Para poder subir al bit de datos d9, necesitamos el bit de paridad p8 y todos los bits de paridad que le preceden, por lo que esta tabla nos indica cu谩ntos bits de paridad necesitamos para una determinada cantidad de bits. Este patr贸n contin煤a indefinidamente.

Hamming code pattern showing how parity bit coverage works

Los c贸digos Hamming son c贸digos de bloque, por lo que operan con N bits de datos a la vez. Entonces, con tres bits de paridad podemos operar en bloques de cuatro bits de datos a la vez. Representamos este esquema de codificaci贸n de errores como Hamming(7,4), donde el primer argumento son los bits totales transmitidos y el segundo argumento son los bits de datos.

Example of Hamming 7,4 which has three parity bits

Las siguientes son tres propiedades importantes de los c贸digos Hamming:

  • El n煤mero m铆nimo de cambios de bits necesarios para pasar de cualquier palabra de c贸digo a cualquier otra palabra de c贸digo es tres

  • Puede corregir errores de un bit.

  • Puede detectar pero no corregir errores de dos bits.

Algor铆tmicamente, el proceso de codificaci贸n se puede realizar mediante una multiplicaci贸n matricial simple, utilizando lo que se denomina 鈥渕atriz generadora鈥. En el siguiente ejemplo, el vector 1011 son los datos a codificar, es decir, la informaci贸n que queremos enviar al receptor. La matriz 2D es la matriz generadora y define el esquema de c贸digo. El resultado de la multiplicaci贸n proporciona la palabra clave a transmitir.

Matrix multiplication used to encode bits with a generator matrix, using Hamming codes

El objetivo de profundizar en los c贸digos Hamming era dar una idea de c贸mo funciona la codificaci贸n de errores. Los c贸digos de bloque tienden a seguir este tipo de patr贸n. Los c贸digos convolucionales funcionan de manera diferente, pero no entraremos en detalles aqu铆; a menudo utilizan decodificaci贸n estilo Trellis, que se puede mostrar en un diagrama similar a este:

A trellis diagram or graph is used within convolutional coding to show connection between nodes

Decodificaci贸n Soft vs Hard

Recuerde que en el receptor la demodulaci贸n se produce antes de la decodificaci贸n. El demodulador puede decirnos su mejor estimaci贸n sobre qu茅 s铆mbolo se envi贸, o puede generar el valor 鈥渟oft鈥. Para BPSK, en lugar de decirnos 1 o 0, el demodulador puede decir 0,3423 o -1,1234, cualquiera que sea el valor 鈥渟oft鈥 del s铆mbolo. Normalmente, la decodificaci贸n est谩 dise帽ada para utilizar valores hard o soft.

  • Soft decision decoding 鈥 usa los valores soft

  • Hard decision decoding 鈥 usa 煤nicamente el 1鈥檚 y el 0鈥檚

El software es m谩s robusto porque utiliza toda la informaci贸n a su disposici贸n, pero tambi茅n es mucho m谩s complicado de implementar. Los c贸digos Hamming de los que hablamos usaban decisiones hard, mientras que los c贸digos convolucionales tienden a usar decisiones soft.

Limite de Shannon

El l铆mite de Shannon o capacidad de Shannon es una teor铆a incre铆ble que nos dice cu谩ntos bits por segundo de informaci贸n libre de errores podemos enviar:

C = B \cdot log_2 \left( 1 + \frac{S}{N}   \right)

  • C 鈥 Capacidad de Canal [bits/sec]

  • B 鈥 Ancho de Banda del canal [Hz]

  • S 鈥 Potencia promedio de la se帽al recivida [watts]

  • N 鈥 Potencia promedio del ruido [watts]

Esta ecuaci贸n representa lo mejor que puede hacer cualquier MCS cuando opera a una SNR lo suficientemente alta como para estar libre de errores. Tiene m谩s sentido trazar el l铆mite en bits/seg/Hz, es decir, bits/seg por cantidad de espectro:

\frac{C}{B} = log_2 \left( 1 + \mathrm{SNR}   \right)

con SNR en t茅rminos lineales (no dB). Sin embargo, al trazarlo, generalmente representamos la SNR en dB por conveniencia:

Plot of the Shannon Limit in bits per second per Hz over SNR in dB

Si ve los gr谩ficos de los l铆mites de Shannon en otros lugares que se ven un poco diferentes, probablemente est茅n usando un eje x de 鈥渆nerg铆a por bit鈥 o E_b/N_0, que no es m谩s que una alternativa al trabajo en SNR.

Podr铆a ayudar a simplificar las cosas darse cuenta de que cuando la SNR es bastante alta (por ejemplo, 10 dB o m谩s), el l铆mite de Shannon se puede aproximar como log_2 \left( \mathrm{SNR} \right), que es aproximadamente \mathrm{SNR_{dB}}/3 (explained here). Por ejemplo, a 24 dB SNR est谩s viendo 8 bits/seg/Hz, por lo que si tienes 1 MHz para usar, son 8 Mbps. Podr铆as estar pensando, 鈥渂ueno, ese es s贸lo el l铆mite te贸rico鈥, pero las comunicaciones modernas se acercan bastante a ese l铆mite, por lo que, como m铆nimo, te da una aproximaci贸n aproximada. Siempre puede reducir ese n煤mero a la mitad para tener en cuenta la sobrecarga de paquetes/tramas y el MCS no ideal.

El rendimiento m谩ximo de WiFi 802.11n que funciona en la banda de 2,4 GHz (que utiliza canales de 20 MHz de ancho), seg煤n las especificaciones, es de 300 Mbps. Obviamente, podr铆a sentarse justo al lado de su enrutador y obtener una SNR extremadamente alta, tal vez 60 dB, pero para ser confiable/pr谩ctico, es poco probable que el MCS de rendimiento m谩ximo (recuerde la curva de escalera desde arriba) requiera una SNR tan alta. Incluso puedes echarle un vistazo a MCS list for 802.11n. 802.11n llega hasta 64-QAM y, combinado con la codificaci贸n de canales, requiere una SNR de alrededor de 25 dB seg煤n this table. Eso significa que incluso a 60 dB SNR tu WiFi seguir谩 usando 64-QAM. Entonces, a 25 dB, el l铆mite de Shannon es aproximadamente 8,3 bits/seg/Hz, lo que, dados 20 MHz de espectro, es 166 Mbps. Sin embargo, cuando se tiene en cuenta MIMO, que cubriremos en un cap铆tulo futuro, se pueden ejecutar cuatro de esas transmisiones en paralelo, lo que da como resultado 664 Mbps. Si reduce ese n煤mero a la mitad, obtendr谩 algo muy cercano a la velocidad m谩xima anunciada de 300 Mbps para WiFi 802.11n en la banda de 2,4 GHz.

La prueba detr谩s del l铆mite de Shannon es bastante loca; Se trata de matem谩ticas que se ven as铆:

Example of the math involved in the Shannon Limit proof

Para m谩s informaci贸n, ver here.

C贸digos de 煤ltima generaci贸n

Actualmente, los mejores esquemas de codificaci贸n de canales son:

  1. Turbo c贸digos, utilizados en 3G, 4G, la nave espacial de la NASA.

  2. C贸digos LDPC, utilizados en DVB-S2, WiMAX, IEEE 802.11n.

Ambos c贸digos se acercan al l铆mite de Shannon (es decir, casi lo alcanzan bajo ciertas SNR). Los c贸digos Hamming y otros c贸digos m谩s simples no se acercan al l铆mite de Shannon. Desde el punto de vista de la investigaci贸n, no queda mucho margen de mejora en cuanto a los propios c贸digos. La investigaci贸n actual se centra m谩s en hacer que la decodificaci贸n sea m谩s eficiente desde el punto de vista computacional y adaptable a la retroalimentaci贸n del canal.

Low-density parity-check (LDPC) son una clase de c贸digos de bloques lineales altamente eficientes. Fueron presentados por primera vez por Robert G. Gallager en su tesis doctoral en 1960 en el MIT. Debido a la complejidad computacional en su implementaci贸n, 隆fueron ignorados hasta la d茅cada de 1990! Tiene 89 a帽os al momento de escribir este art铆culo (2020), todav铆a est谩 vivo y ha ganado muchos premios por su trabajo (d茅cadas despu茅s de haberlo hecho). LDPC no est谩 patentado y, por lo tanto, es de uso gratuito (a diferencia de los c贸digos turbo), por lo que se utiliz贸 en muchos protocolos abiertos.

Los turbo c贸digos se basan en c贸digos convolucionales. Es una clase de c贸digo que combina dos o m谩s c贸digos convolucionales m谩s simples y un entrelazador. La solicitud de patente fundamental para turbo c贸digos se present贸 el 23 de abril de 1991. Los inventores eran franceses, por lo que cuando Qualcomm quiso utilizar turbo c贸digos en CDMA para 3G, tuvo que crear un acuerdo de licencia de patente con France Telecom. La patente principal expir贸 el 29 de agosto de 2013.