Codificación Huffman - Ejemplo del Drone

🏠 Índice Principal 📡 Morse en distintos idiomas

El Escenario

🛸 Drone de reparto autónomo: Un drone debe enviar su estado a la base de control cada segundo. Para ahorrar batería y no saturar la red de radio, necesita usar un código eficiente que aproveche que algunos estados son mucho más frecuentes que otros.

Estados del drone y sus probabilidades:

🟢

50%

Vuelo normal

🟡

Batería Baja

25%

Alerta media

🟠

Viento

12.5%

Condiciones adversas

🔴

Obstáculo

12.5%

Alerta crítica

🌳 Construcción del Árbol de Huffman

El algoritmo agrupa iterativamente los símbolos menos probables, construyendo el árbol desde las hojas hacia la raíz.

Paso 1: Unir los más raros

Agrupamos Viento (12.5%) y Obstáculo (12.5%) en la caja Alertas (suma 25%).
Asignamos 0 a Viento y 1 a Obstáculo.

Paso 2: Reordenar y unir

Nueva lista: OK (50%), Batería (25%), Alertas (25%).
Agrupamos Batería (25%) y Alertas (25%) en la caja Problemas (suma 50%).
Asignamos 0 a Batería y 1 a Alertas.

Paso 3: Raíz final

Solo quedan OK (50%) y Problemas (50%). Los unimos al 100%.
Asignamos 0 a OK y 1 a Problemas.

🌲 Árbol resultante

Representación visual del árbol binario:

                    [100%]
                   /      \
              0/        1\
                /          \
           🟢 OK        [Problemas]
           (50%)         50%
                        /    \
                   0/      1\
                    /        \
              🟡 Batería   [Alertas]
                (25%)        25%
                            /    \
                       0/      1\
                        /        \
                  🟠 Viento   🔴 Obstáculo
                    (12.5%)     (12.5%)

🔢 Códigos finales

Para obtener el código de cada estado, se lee el camino de bits desde la raíz hasta la hoja:

🟢

1 bit

🟡

2 bits

🟠

110

3 bits

🔴

111

3 bits

📊 Impacto práctico: El ahorro

❌ Código fijo tradicional

Para 4 estados necesitas al menos 2 bits (2² = 4 combinaciones).

2 bits/siempre

OK: 00, Batería: 01, Viento: 10, Obstáculo: 11. Todos cuestan lo mismo.

✅ Código Huffman

Ponderado por frecuencia: lo común es corto, lo raro es largo.

1.5 bits/prom

El 50% de los mensajes (OK) cuestan solo 1 bit.

Cálculo del ahorro

L_prom = (0.5 × 1) + (0.25 × 2) + (0.125 × 3) + (0.125 × 3) [bits/mensaje] = 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bits por mensaje

Ahorro = [(2 - 1.75) / 2] × 100 = 12.5% menos bits [%]

🔋 Impacto real en el drone:
• Menos bits transmitidos = menos tiempo de antena encendida = más batería disponible para volar.
• Canal más libre = otros drones del enjambre pueden transmitir sin colisiones.
• Si el drone envía estado 1 vez/seg durante 1 hora de vuelo, ahorra ~900 bits, equivalente a 15 minutos adicionales de vuelo.

💡 Aplicaciones reales de Huffman

🌐 Tecnologías que usan Huffman hoy:

ZIP / RAR: Compresión de archivos. Los caracteres más frecuentes del documento se representan con menos bits.
JPEG: Compresión de imágenes. Tras transformar la imagen, los coeficientes más comunes se codifican con Huffman.
MP3: Compresión de audio. Los valores de frecuencia más frecuentes usan códigos más cortos.
DEFLATE: Algoritmo que combina LZ77 + Huffman, usado en PNG, gzip, HTTP y zlib.
Protocolos de red: Muchos protocolos usan variantes de Huffman para reducir el overhead de cabeceras.

🧠 Conexión conceptual: El código Morse (1838), inventado empíricamente por Samuel Morse analizando imprentas, y Huffman (1952), formalizado matemáticamente por David Huffman en su tesis doctoral del MIT, aplican exactamente el mismo principio: asignar códigos más cortos a los símbolos más probables. La diferencia es que Huffman demostró que su algoritmo produce el código óptimo para símbolos individuales.

🏠 Índice Principal 📡 Morse en distintos idiomas