Algoritmo de programación dinámica que calcula la secuencia de estados más probable (el camino de estados de máxima verosimilitud) en un trellis de estado finito, acumulando recursivamente métricas de camino aditivas y reteniendo un único camino superviviente por estado en cada paso temporal; ampliamente usado para detección de secuencia ML en códigos convolucionales y canales finito‑estado.

Principio

Aprovechando la estructura markoviana (de estados finitos) del trellis, el algoritmo de Viterbi evita la enumeración exponencial de secuencias de estados: en cada paso computa métricas de rama, las suma a las métricas de camino previas y mantiene solo el mejor camino entrante por estado, con complejidad lineal en la longitud de la secuencia y proporcional al número de estados.

Demostración

Situación: Decodificar un código convolucional tasa 1/2 con longitud de restricción K que genera 2^(K−1) estados de trellis. Reconocimiento: representación en trellis de las transiciones de estado y métricas de rama provenientes de evidencia dura o blanda. Acción: recorrer el trellis, actualizar métricas de camino, almacenar supervivientes, realizar traceback tras la terminación o usar ventana deslizante para emitir bits decodificados. Consecuencia: el algoritmo devuelve la secuencia ML (óptima en secuencia) bajo el modelo de canal y código supuesto, con coste computacional que escala linealmente con la longitud de trama pero exponencialmente con la memoria del codificador (número de estados).

Aplicación incorrecta

Emplear el algoritmo de Viterbi cuando el objetivo es obtener probabilidades MAP bit‑por‑bit (minimizar la tasa de error por bit) en lugar de ML de secuencia, o interpretar la salida de Viterbi como fiabilidades de bit sin un procesado de salida blanda adicional. El error semántico es confundir la optimalidad por secuencia con la optimalidad por bit y usar supervivientes duros como medidas probabilistas.

Consecuencia

La decodificación Viterbi ofrece la secuencia de estados ML para modelos de estado finito y por tanto minimiza la probabilidad de error de secuencia bajo esas suposiciones; es eficiente para conteos de estado moderados y es fundamental en muchos receptores. Sus limitaciones incluyen memoria y computación crecientes con el número de estados, latencia por traceback y ausencia de salidas blandas directas (resuelto por variantes SOVA/BCJR) cuando se requieren confiabilidades bit‑a‑bit.

Inversión

Cuando se requiere minimizar la probabilidad de error por bit o disponer de información posterior blanda para procesamiento iterativo posterior, son preferibles algoritmos que calculan posteriores por símbolo/bit (BCJR) o variantes Viterbi con salida blanda (SOVA). Para canales con memoria extremadamente larga, el espacio de estados del trellis puede volverse impracticable y son necesarias aproximaciones como estados truncados o ventanas deslizantes.

Límite

Claramente dentro: detección de secuencias o decodificación para códigos convolucionales y canales de estado finito representables por un trellis con número de estados manejable. Caso límite: Viterbi truncado o con ventana deslizante que reduce la explosión de estados a costa de la optimalidad. Claramente fuera: detectores símbolo‑a‑símbolo que no usan la memoria del trellis y algoritmos que calculan completos posteriores (BCJR) cuando se requieren posteriores por bit.

Tensión semántica

Optimalidad de secuencia frente a optimalidad por bit y complejidad frente a precisión: Viterbi ofrece una solución ML de secuencia eficiente pero no minimiza la tasa de error por bit ni provee directamente información posterior; obtener otras métricas o salidas blandas exige algoritmos distintos o extendidos con mayor coste.

Síntesis

El algoritmo de Viterbi es el método canónico y eficiente para obtener el camino de estados ML en modelos de estado finito: convierte la búsqueda exponencial de secuencias en una recursión por pasos, pero su uso requiere que la optimalidad a nivel de secuencia y la complejidad de estados disponibles compensen la ausencia de información posterior por bit.