¿Qué es el algoritmo de Viterbi y cómo se aplica a las comunicaciones inalámbricas CDMA / 3G / 4G?

Answer 1

Agregando a la respuesta de Jesse / Sridhar, y buscando las aplicaciones CDMA en particular, parece que Viterbi es un algoritmo especialmente eficiente para enviar transmisiones de manera algo robusta sobre canales ruidosos, esencialmente, un tipo útil de código convolucional de corrección de errores.

Ningún canal de comunicación es perfecto, por lo que cada forma estandarizada de comunicación electrónica tiene algún tipo de forma de detectar y resolver errores en los mensajes que provienen de ese canal. En realidad, hay una manera de calcular cuánta información “clara” puede enviar a través de un canal “ruidoso” (el límite de Shannon en la capacidad del canal).

Debido a que las diferentes aplicaciones tendrán una potencia computacional variable disponible (desde su teléfono celular hasta su tarjeta de red, etc.), así como diferentes perfiles de ‘ruido’ del canal, existen algoritmos especializados para cada contexto.

Lo que dice Jesse sobre los diagramas de trellis es especialmente relevante aquí: cuando un objeto físico recibe la comunicación (posiblemente ruidosa), puede determinar si la comunicación se corrompió de alguna manera al ver si la secuencia de salida es incluso posible en el esquema de codificación convolucional. Luego puede usar el algoritmo de Viterbi para resolver rápidamente desde la señal del canal codificado hasta la señal original decodificada, buscando la comunicación válida ‘más cercana’ (en el sentido de máxima probabilidad) que podría haberse enviado.

Para ciertas aplicaciones (códigos de restricción cortos y la disponibilidad de hardware paralelo), Viterbi es la solución más barata / más rápida.

Más información aquí:
http://en.wikipedia.org/wiki/Con…

Answer 2

Para agregar a la respuesta de Jesse, el problema general al que es aplicable el algoritmo de Viterbi tiene las siguientes características:
1. Obtiene una secuencia ordenada (generalmente por tiempo) de observaciones.
2. Tiene un conjunto de probabilidades (probabilidades de emisión) que mapean cualquier observación a los estados. P (s, o) es la probabilidad de que ocurra dado que viste o.
3. Usted sabe la probabilidad de transiciones de estado: cuán probable es que el estado actual sea s cuando el último fue s`.

Usando el algoritmo de Viterbi, puede averiguar cuál fue la secuencia más probable de estados. es decir, alguna versión de lo que realmente sucedió.

No estoy seguro de cómo se aplica a CDMA, pero el esquema de codificación podría prestarse a las propiedades 2 y 3 anteriores. Intuitivamente tiene mucho sentido para el reconocimiento de voz.

Esta es una explicación súper clara: http://www.cs.ubc.ca/~murphyk/Ba …

Answer 3

Además de lo anterior, en el nivel más básico, el algoritmo y la teoría de la codificación se remontan al trabajo original de Claude Shannon en “The Mathematical Theory of Communication” publicado por Bell Labs. En él sentó las bases teóricas básicas sobre las que se basan todas las tecnologías y comunicaciones digitales modernas. En esencia, todo se reduce a crear un límite estricto a la cantidad de información que se puede enviar a través de un canal de comunicación y la rapidez con que se puede hacer. El algoritmo de Viterbi, que se puede llamar un código convolucional, mejoró la velocidad a la que la información podría ser empujada a través de un canal y obviamente tiene una aplicación directa en las comunicaciones celulares. En realidad, puede leer el texto de Viterbi y Omura “Principios de comunicación y codificación digital” (1979) de forma gratuita en línea o adquirir la edición económica que le pedí a Dover Publications para que la reimprima hace unos años. Es sorprendentemente accesible dado lo que muchos considerarían un tema difícil. El texto de Bernard Sklar sobre comunicaciones también hace un trabajo razonable al cubrir algunos de los conceptos básicos, según recuerdo.