ES2203938T3 - Decodificacion viterbi de salida en lista de codigo de redundancia ciclica externa para una señal de proporcion multiple. - Google Patents

Abstract

Un procedimiento y un aparato para decodificar un cuadro de datos digitales codificados de multivelocidad el cual contiene información redundante proporcionada para validar la operación de decodificado. Se recibe un cuadro de datos el cual contiene bits de información y bits de control de redundancia cíclica (CRC). De acuerdo con la invención, se decodifica el cuadro recibido y se realiza un control para verificar si los bits CRC corresponden correctamente con los bits de la información decodificada. Si el cuadro decodificado supera el proceso de prueba CRC, el cuadro decodificado se facilita al usuario. Sin embargo, si el cuadro decodificado no supera la prueba CRC, entonces se realiza al menos un proceso adicional de decodificado a la recepción del cuadro. En la primera realización ejemplar de la presente invención, en caso de no superarse la prueba CRC, los datos se decodifican utilizando un decodificador trellis (224) y se seleccionan los datos que producen la siguiente ruta más probable a través del trellis. En una segunda realización ilustrativa, si no se supera la prueba CRC, el decodificador trellis (224) identifica a continuación todas las rutas que tienen métricas dentro de un umbral predeterminado de una métrica asociada con la ruta óptima a través del trellis. La prueba CRC se realiza a continuación sobre el cuadro decodificado con relación a las rutas por debajo de la óptima (comenzando con la ruta más probable). Si alguna de estas rutas supera la prueba de CRC, los bits de información son sacados por el decodificador (224). Si no, se declara un error.

Description

Decodificación Viterbi de salida en lista de código de redundancia cíclica externa para una señal de proporción múltiple.

Antecedentes de la invención 1. Campo de la invención

La presente invención esta relacionada con el procesamiento de la señal digital. Más particularmente esta relacionada con un método y dispositivo novedoso y mejorado para decodificar una trama de datos digitales que contiene bits redundantes de control y por otro lado la información la cual se conoce propiamente como los datos.

2. Descripción del arte relacionado

Tal como la tecnología de comunicación sin cable ha ido avanzando, los usuarios han venido demandando en los servicios proporcionados una mayor calidad de transmisión. Uno de los medios de proporcionar superior calidad de transmisión para dar servicio de comunicación sin cable involucran el uso de técnicas de la transmisión digital. En el arte son conocidas varias técnicas de modulación digital las cuales incluyen el acceso múltiple por diferenciación de código (AMDC), el acceso múltiple por división en el tiempo (AMDT) y el acceso múltiple por división de frecuencia (AMDF).

La técnica de modulación por espectro ensanchado de AMDC tiene significativas ventajas sobre otras técnicas de modulación digital. El uso de las técnicas de AMDC en sistemas de comunicación de acceso múltiple se descubre en la Patente U.S. No 4.901.307, titulada " SISTEMA DE COMUNICACIÓN DE ACCESO MÚLTIPLE POR ESPECTRO ENSANCHADO USANDO REPETIDORES TERRESTRES O DE SATELITE ", asignado al derechohabiente de la presente invención, e incorporado aquí como referencia. El uso de las técnicas AMDC en sistemas de comunicación de acceso múltiple es además publicado en la Patente U.S. No 5.103.459, titulada " SISTEMA Y METODO PARA GENERAR FORMAS DE ONDA DE SEÑAL EN UN SISTEMA DE TELEFONIA CELULAR AMDC", asignado al derechohabiente de la presente invención, e incorporado aquí como referencia. El método de proporcionar comunicación digital sin hilos usando AMDC fue estandarizado por la Asociación de la Industria de las Telecomunicaciones (AIT) en el documento TIA/EIA/IS-95-A Estándar de Compatibilidad Estación Móvil- Estación Base para un Sistema Celular de Banda Ancha de Espectro Ensanchado de Doble Modo (de aquí en adelante IS-95).

Debido a que cada usuario de transmisión contribuye a incrementar el ruido en otro usuario del sistema de comunicación AMDC, la capacidad de un sistema AMDC se maximiza teniendo como base que cada usuario transmita sólo los datos que sean necesarios. Un medio muy efectivo de reducir la capacidad de carga de un usuario sin reducir la calidad de servicio de este, es mediante la velocidad de transmisión de datos variable, en donde la velocidad de transmisión de datos del usuario varía con el tiempo. Un método para proporcionar velocidad variable de datos de voz codificados se describe en la Patente U.S. No 5.414.796 titulada " DECODIFICADOR DE SEÑALES VOCALES DE VELOCIDAD VARIABLE" asignado al derechohabiente de la presente invención, e incorporado aquí como referencia.

Para proteger errores inducidos en el canal, en los sistemas de comunicación sin cable, se emplean técnicas de corrección de errores. Un método de detección y corrección de errores inducidos en el canal es por medio de un decodificador de convolución. Un decodificador de Viterbi es un tipo especifico de decodificador convolucional que tiene significativas ventajas sobre otros sistemas de corrección de errores. Un método y un dispositivo para realizar la decodificación de Viterbi de datos de velocidad variable se describen en detalle en WO95/8888 titulada " DECODIFICADOR DE VITERBI PARA DATOS EN SERIE DE VELOCIDAD VARIABLE EN SISTEMAS AMDC "asignado al derechohabiente de la presente invención, e incorporado aquí como referencia.

La implementación de un decodificador de Viterbi con una lista-de-dos modificada Algoritmo de Viterbi con Salida de Lista (LOVA) usada para decodificar tramas de datos con velocidad de transferencia variable en acceso múltiple por división de código (AMDC) en estaciones móviles esta descrita en el documento de S. Czaja y J. Roberston, "Decodificador de Viterbi de Velocidad de datos Variable con algoritmo LOVA modificado", de 1995 IEEE TENCON (Conferencia Internacional IEE Región 10 de Microelectrónica y VLSI, acta 2000 de Microelectrónica de Asia-Pacífico en Hong Kong, del 6 al 10 de Noviembre de 1995 paginas 472-475). Se describe la decodificación de código convolucional K=9, velocidad = ½ para tramas de velocidad de datos total, medio, un cuarto y un octavo. El decodificador de Viterbi es una parte de un procesador de banda-base de un AMDC usado en el terminal móvil de un sistema de comunicación celular y personal de un IS-95.

EP-A 0 751 625 describe un método y su correspondiente circuito, para decodificar los datos recibidos de un canal de comunicación. El método incluye los pasos de recepción de una señal modulada que transporta bloques de datos codificados que tienen datos y campos de síndrome de datos; determinación de transición y métrica de trayectoria para los bloques de datos codificados, en donde las métricas de trayectoria están solo determinadas para una trayectoria de Máxima Verisimilitud (ML) y una segunda mejor trayectoria de máxima verisimilitud; decodificación del bloque de datos codificados realizando una operación total o parcial de trazado hacia atrás de las métricas de la trayectoria de mejor máxima verisimilitud y la trayectoria de segunda mejor máxima verisimilitud, en donde en una traza hacia atrás completa de las trayectorias de Máxima Verisimilitud se obtienen primera y segunda pluralidades obtenidas de los bits detectados que representan respectivamente el campo de datos y el campo de datos de síndrome, y desde la segunda mejor trayectoria ML se obtienen terceras y cuartas pluralidades de los bits detectados representando respectivamente el campo de datos y el campo de datos de síndrome; determinando un síndrome para la primera pluralidad de los bits detectados y comparándolo con un determinado síndrome de la segunda pluralidad; Cuando hay coincidencia se sacan fuera la primera pluralidad de los datos de la trama recibida. Si no se encuentra la coincidencia, se determina un síndrome de la tercera pluralidad de los bits detectados y esta es comparada con la cuarta pluralidad de los bits detectados. Cuando hay coincidencia se sacan fuera la tercera pluralidad de los bits detectados como una trama de datos recibidos.

No obstante, permanece una necesidad en el arte de sistemas y técnicas que además mejore en las ganancias de codificación que ofrece la técnica de modulación AMDC y por lo tanto alcance incrementos en la capacidad de carga.

Resumen de la invención

La presente invención es un método y un dispositivo novedoso y mejorado para decodificar una trama de datos digitales que contiene información redundante proporcionada para validar la operación de decodificación. La presente invención mejora la ganancia de descodificación en sistemas AMDC y aumenta el rendimiento de capacidad de carga del sistema. En la presente invención, se proporciona una trama de datos la cual contiene bits de información y bits de chequeo de redundancia cíclica (CRC ). La trama recibida es decodificada y es acompañada de una comprobación la cual determina si los bits de CRC se corresponden correctamente con los bits de información decodificados. Si la trama decodificada pasa el proceso de prueba de CRC, la trama decodifica se proporciona al usuario. Sin embargo, si la trama decodificada no pasa la prueba de CRC, entonces se realiza por lo menos un proceso adicional de decodificación en la trama recibida.

Así que de acuerdo con un primer aspecto de la presente invención aquí se proporciona un dispositivo que determina la velocidad de transferencia de los datos contenidos en una trama de datos que contiene datos digitales codificados a una o a una pluralidad de diferentes velocidades de transferencia de datos, los cuales datos digitales comprenden bits de información y bits de comprobación asociados, constando el dispositivo de: medios de combinado para combinar los datos digitales de una trama de datos dependiendo de cada una de las diferentes velocidades de transferencia de datos para producir datos combinados; medios de descodificación convolucional para decodificar los datos combinados mediante la identificación de un camino optimo a través del cual producir la descodificación de los datos; medios de validación para validar los datos decodificados, representando los dichos bits de información y los bits de comprobación asociados, usando los bits de comprobación y poniendo en la salida una indicación de la validez de los datos; caracterizado en que los medios de descodificación convolucional se organizan para identificar las trayectorias subóptimas a través de las cuales tener una métrica respectiva dentro de un umbral predeterminado de una métrica correspondiente a la trayectoria optima y a los correspondientes datos decodificados de salida para cada uno de las trayectorias subóptimas identificadas; los medios de validación están dispuestos para validar los datos decodificados para cada una de las trayectorias subóptimas y para poner en la salida una indicación de la validez de los datos de salida; y la velocidad de transferencia de los datos para la trama es seleccionada como la correspondiente al camino por el que los medios de validación han puesto la indicación de salida valida.

De acuerdo con un segundo aspecto de la presente invención aquí se proporciona un sistema para la determinación la velocidad de transferencia de datos de una trama de datos que contiene datos digitales codificados a una o a una pluralidad de diferentes velocidades de transferencia de datos, los cuales datos digitales comprenden bits de información y bits de comprobación asociados, comprendiendo el sistema el dispositivo de acuerdo al primer aspecto de la presente invención.

De acuerdo a un tercer aspecto de la presente invención aquí se proporciona un método para determinar una pluralidad de diferentes velocidades de transferencia de datos, los cuales datos digitales comprenden bits de información y bits de comprobación asociados, comprendiendo el método:

la combinación de los datos digitales de una trama de datos dependiendo de cada una de las velocidades de transferencia de datos para producir los datos combinados; la descodificación convolucional de los datos combinados mediante la identificación de una trayectoria optima a través de la cual producir los datos decodificados; la validación de los datos decodificados como representación de los dichos bits de información y los bits asociados de comprobación, usando los bits de comprobación asociados y poniendo en la salida una indicación de la validez de los datos; caracterizados por: la identificación de trayectorias sub-óptimas a través de las cuales tener una métrica tener una métrica respectiva dentro de un umbral predeterminado de una métrica correspondiente a la trayectoria optima y a los correspondientes datos decodificados de salida para cada uno de las trayectorias sub-óptimas identificadas; la validación de los datos decodificados para cada una de las trayectorias sub-óptimas identificadas y puesta en la salida de una indicación de la validez de los datos de salida; y la selección de velocidad de transferencia de los datos para la trama como es la correspondiente al camino por el cual los medios de validación pusieron la indicación de salida valida.

En el primer ejemplo de realización de la presente invención, los datos se decodifican usando un decodificador convolucional y los datos que producen el camino más probable a través de la convolución son seleccionados. Entonces se realiza una comprobación de CRC de los datos de la trama decodificada. Si la comprobación de CRC falla, el decodificador de convolución determina un segundo camino mas probable a través de la convolución seleccionada. Entonces, por segunda vez se realiza la comprobación de CRC de los datos de la trama decodificada. Si la trama decodificada pasa la prueba de CRC, los bits de información son entregados en la salida por decodificador. Sin embargo, si el test de CRC de la trama decodificada falla, entonces el decodificador de convolución selecciona el siguiente camino más probable a través de la convolución seleccionada. Este proceso se repite hasta que la comprobación de CRC se pasa satisfactoriamente o hasta que después de un predeterminado numero de intentos de descodificación han sido hechos sin éxito y el decodificador declara que no es posible decodificar la trama y es declarado un borrado de trama.

En una realización ilustrativa segunda, los datos son decodificados usando un decodificador convolucional y los datos que producen el camino más probable a través de la convolución son seleccionados. Entonces se realiza una comprobación de CRC de los datos de la trama decodificada. Si la comprobación de CRC falla, el decodificador de convolución identifica entonces caminos que tienen métricas dentro de un predeterminado umbral de una métrica asociada con el camino optimo a través del decodificador. Entonces se realiza en la trama decodificada un test de CRC con respecto a los caminos sub-óptimos que se encontraron. Si uno de los caminos pasa el test de CRC, los bits de información correspondiente al camino más probable son puestos en la salida por el decodificador. Si no, se declara un error. En la implementación preferente, el decodificador es realizado con un decodificador de Viterbi y la métrica usada es la métrica de Yamamoto.

Breve descripción de los dibujos

Las características, objetivos, y ventajas de la presente invención serán más evidentes a partir de la descripción detallada puesta mas adelante cuando es tomada en conjunción con los dibujos en los que los caracteres de referencia se corresponden a lo largo de ella y en donde:

Fig. 1 es un ejemplo de un sistema de transmisión el cual transmite tramas de datos que contienen un conjunto de bits de CRC y otra conjunto de bits de información;

Fig. 2A-2D son ilustraciones de ejemplos de estructuras de tramas de velocidad de transferencia de datos variables de realizaciones de la presente invención;

Fig. 3 es un ejemplo de implementación de un decodificador acorde con una realización de la presente invención;

Fig. 4 es un diagrama de bloques del primer ejemplo de realización del sistema de decodificación de la presente invención;

Fig. 5 es un diagrama de flujo describiendo el método de decodificación de datos del primer ejemplo de realización;

Fig. 6 es una ilustración de las transiciones de estado de un decodificador convolucional;

Fig. 7 es una ilustración de las trayectorias seleccionadas en las transiciones de estado del decodificador convolucional de la Fig. 6;

Fig. 8 es una ilustración de una selección de trayectoria a través de en decodificador convolucional;

Fig. 9 es una ilustración de un codificador que tiene cuatro posibles estados;

Fig. 10 es un diagrama de bloques de un decodificador de convolución del primer ejemplo de realización;

Fig. 11 es una ilustración de la mejor trayectoria a través de la convolución y la trayectoria seleccionada por el calculo de diferencia de valores asociados con esta trayectoria;

Fig. 12 es una ilustración de la segunda mejor trayectoria seleccionada de acuerdo con la primera realización;

Fig. 13 es una ilustración de la primera y segunda trayectorias seleccionadas a través de la convolución y la trayectoria seleccionada por el calculo de diferencia de valores asociados con el proceso de selección de la tercera trayectoria;

Fig. 14 ilustra el dispositivo del segundo ejemplo de realización del sistema de decodificación de la presente invención;

Fig. 15 es un diagrama de flujo ilustrando el método del segundo ejemplo de realización de la presente invención;

Fig. 16. es un diagrama de flujo el cual ilustra la técnica de umbral para seleccionar trayectorias sub-óptimas de acuerdo con la realización de la presente invención; y

Fig. 17 es una ilustración de un diagrama de convolución de trayectorias establecidas mediante el método de decodificación del segundo ejemplo de realización de la presente invención.

Descripción detallada de las realizaciones preferidas

Se describirán ahora realizaciones ilustrativas y aplicaciones ejemplares con referencia a los dibujos que se acompañan para revelar las ventajosas enseñanzas de la presente invención.

A pesar de que la presente invención esta descrita aquí con referencia a ilustrativas realizaciones para aplicaciones particulares, se debe entender que la invención no esta limitada por esto. Aquellos que tienen la habilidad ordinaria en el arte y acceso a las enseñanzas proporcionadas aquí dentro, reconocerán modificaciones adicionales, aplicaciones, y realizaciones dentro del alcance de eso y en campos adicionales en los que la presente invención podría ser de utilidad significativa.

Refiriéndose a la Fig. 1, la fuente de datos 2, proporciona tramas de datos digitales. En la realización del ejemplo, la fuente de datos 2 proporciona una trama cada 20 ms, a través de las realizaciones de la presente invención son igualmente aplicables a otras velocidades de transferencia de datos. En la realización del ejemplo la fuente de datos 2 es un codificador de velocidad variable, un ejemplo del cual esta descrito en la anteriormente mencionada Patente U.S. 5.414.796.

El codificador de voz de la patente U.S 5.414.796, selecciona una velocidad para codificar una trama de muestras de voz digitalizada basada en la energía de las muestras en la trama. Esto reduce el número de bits mandados cuando el usuario no está hablando, lo cual como se describió anteriormente minimiza el ruido producido por el usuario hacia otro usuario del sistema de comunicación AMDC. Debe hacerse notar que las realizaciones de la presente invención son igualmente aplicables a fuentes de datos de velocidad fija. Además, las realizaciones de la presente invención no son solo aplicables a las transmisiones de voz, son igualmente aplicables a otras transmisiones de información digital tales como facsímil, vídeo, u otros datos digitalizados.

Las tramas de bits de información desde la fuente de datos 2 se proporcionan a un formateador de tramas 4. En la realización del ejemplo, el formateador de tramas 4 consiste en un generador de CRC 6 y un generador de bit de cola 8. El generador de CRC genera un conjunto de bits de comprobación redundante de acuerdo con la información proporcionada por los bits de las tramas que llegan de la fuente de datos 2 y añade los bits redundantes a la trama. Las realizaciones de la presente invención son aplicables a otros generadores de bits de comprobación redundante, el diseño y la implementación de bits de paridad o de bit de redundancia son bien conocidos en el arte. Una realización ejemplar del generador de CRC 6 esta descrita en la anteriormente mencionada Patente U.S. 5.414.796 y ha sido estandarizada en IS-95. Debe de ser notado que las realizaciones de la presente invención son igualmente aplicables a otros generadores de bit redundante como se entendería por un entendido en el arte.

Las tramas comprendiendo bits de información y bits de CRC se proporcionan a un generador de bit de cola el cual genera un conjunto de bits de cola y añade estos bits a la trama. El propósito de estos bits de cola es forzar al codificador 10 a un predeterminado estado cuando la trama que pasa a través de él ha finalizado. En la realización del ejemplo el generador de cola 8 genera un conjunto de bits de cola con valor cero forzando así la salida del codificador 10 al estado cero.

Refiriéndonos ahora a las Figs. 2A-2D, son ejemplos ilustrados de distintos formatos de trama de acuerdo a las realizaciones de la presente invención. Estos formatos de trama están referidos a los formatos de trama múltiple opción 2 según se estandarizaron en estándar IS-95. Es fácilmente comprensible para una persona experta en el arte, que las realizaciones de la presente invención son igualmente aplicables para la decodificación de datos transmitidos usando otros formatos de trama.

En la realización del ejemplo, la fuente de datos 2 proporciona datos a cuatro velocidades de transferencia de datos diferentes. Refiriéndonos a la Fig. 2A, si la fuente de datos 2 proporciona una trama consistente en 267 bits de información, mandados como velocidad completa de trama, entonces el generador de CRC 6 de acuerdo con los bits de información genera 12 bits de chequeo de redundancia cíclica CRC (indicados por F) y los añade a la trama. El generador de cola 8 genera 8 bits de cola (indicados por T) de valor cero y los añade a la trama. Al comienzo de la trama se proporciona un bit de reserva (indicado por R) el cual puede ser usado por ejemplo para el control de la potencia en la transmisión.

Refiriéndonos a la Fig. 2B, si la fuente de datos 2 proporciona una trama consistente en 125 bits de información, mandados como velocidad mitad de trama, entonces el generador de CRC 6 de acuerdo con los bits de información genera 10 bits de chequeo de redundancia cíclica CRC (indicados por F) y los añade a la trama. El generador de cola 8 genera 8 bits de cola (indicados por T) de valor cero y los añade a la trama. Al comienzo de la trama se proporciona un bit de reserva (indicado por R) el cual puede ser usado por ejemplo para el control de la potencia en la transmisión.

Refiriéndonos a la Fig. 2C, si la fuente de datos 2 proporciona una trama consistente en 55 bits de información, mandados como velocidad un cuarto de trama, entonces el generador de CRC 6 de acuerdo con los bits de información genera 8 bits de chequeo de redundancia cíclica CRC (indicados por F) y los añade a la trama. El generador de cola 8 genera 8 bits de cola (indicados por T) de valor cero y los añade a la trama. Al comienzo de la trama se proporciona un bit de reserva (indicado por R) el cual puede ser usado por ejemplo para el control de la potencia en la transmisión.

\newpage

Refiriéndonos a la Fig. 2D, si la fuente de datos 2 proporciona una trama consistente en 21 bits de información, mandados como velocidad un octavo de trama, entonces el generador de CRC 6 de acuerdo con los bits de información genera 6 bits de chequeo de redundancia cíclica CRC (indicados por F) y los añade a la trama. El generador de cola 8 genera 8 bits de cola (indicados por T) de valor cero y los añade a la trama. Al comienzo de la trama se proporciona un bit de reserva (indicado por R) el cual puede ser usado por ejemplo para el control de la potencia en la transmisión.

La salida de las tramas desde el formateador de tramas (4) se entregan a un codificador (10). En la realización del ejemplo el codificador (10) es un codificador convolucional de velocidad ½ con longitud de contención nueve (K = 9). El diseño y la implementación de un codificador convolucional es bien conocido en el arte. Los símbolos codificados por el codificador (10) son proporcionados al dispositivo de entrelazado (12).

En la realización del ejemplo, el dispositivo de entrelazado (12) proporciona selectivamente redundancia en la trama, por eso los datos de símbolo ocupan la capacidad total de la trama. Si la trama es menor que la de velocidad completa, entonces el dispositivo de entrelazado (12) proporciona duplicación de símbolos. De esta manera si la velocidad es de velocidad mitad, el dispositivo de entrelazado proporciona redundancia de velocidad 2 conteniendo en cada trama una copia original simple de estos símbolos y un duplicado de estos símbolos. Si la trama es de velocidad un cuarto, el dispositivo de entrelazado (12) proporciona redundancia de velocidad (4) conteniendo en cada trama una copia original simple de estos símbolos y tres copias del original de estos símbolos y si la trama es de velocidad un octavo, el dispositivo de entrelazado (12) proporciona redundancia de velocidad 8 conteniendo en cada trama siete copias del original de estos símbolos. Después de la repetición de los símbolos ellos son parcheados mediante borrado en la salida de dos de cada seis símbolos para obtener un número de símbolos igual al que se describe en el estándar IS-95. El dispositivo de entrelazado (12), reordena entonces los símbolos de acuerdo a un formato de reordenamiento predeterminado. En la realización del ejemplo el dispositivo de entrelazado (12) proporciona redundancia y reordenamiento de las tramas tal como se describe en el estándar IS-95.

Los símbolos revisados se proporcionan al modulador (14) el cual modula los símbolos de acuerdo a un determinado formato. En la realización del ejemplo, el modulador (14) es un modulador AMDC como el que se describe en detalle en las anteriormente mencionadas Patentes Nos 4.901.307, y 5.103.459. Los datos modulados de la trama se proporcionan a un transmisor (16) el cual convierte y amplifica la trama y la trasmite a través de la antena (20).

Refiriéndonos a la Fig. 3, una señal transmitida por el sistema de transmisión (1) de la Fig. 1, es recibida por la antena (49) y proporcionada al receptor (RCVR) (50). El receptor (50) convierte, filtra y amplifica la señal recibida y la proporciona al demodulador (52). El demodulador (52) demodula la señal recibida de acuerdo con un formato de desmodulación predeterminado. En la realización del ejemplo, el demodulador (52) es un demodulador AMDC como el que se describe en detalle en las anteriormente mencionadas Patentes Nos 4.901.307, y 5.103.459.

La trama demodulada de los datos proporcionados al desentrelazador (54) que reordena los datos de símbolos software dentro de la trama de acuerdo con un formato predeterminado de reordenamiento y añade ceros en donde los símbolos fueron borrados en el proceso de transmisión y así obtener un formato modificado. El formato modificado de los datos de símbolo por decisión software se proporciona al sistema de decodificación (56). El sistema de decodificación (56) decodifica los datos y los proporciona al receptor de datos (58). El receptor de datos (58) puede proporcionar un post procesamiento de los datos de la trama decodificada. Por ejemplo, si el dato es un dato de voz comprimido, el receptor de datos (58) convierte los parámetros de voz en muestras de voz digitalizadas de acuerdo con un formato de expansión predeterminado tal cual está descrito en la Patente U.S. 5.414796.

La Fig. 4 ilustra el sistema de decodificación (56) del dispositivo de la primera realización del ejemplo de la presente invención y la Fig. 5 lo acompaña mediante un diagrama de flujo que ilustra la realización del primer método de la presente invención. Como se ilustra en las Figs. 4 y 5, en el bloque (250), la trama de los datos de símbolo modificada por el software que llega desde el dispositivo de desentrelazado (54) (de la Fig. 3) es proporcionada y almacenada en la memoria intermedia de tramas (220) (de la Fig. 4).

Entonces, en el bloque (252), se combinan los símbolos en el combinador de símbolos (222) de acuerdo con la hipótesis de velocidad actual. El proceso de combinación tiene la ventaja del hecho de que las velocidades mas bajas que la de velocidad completa tienen redundancia en los datos de símbolo transmitidos y por eso puede llegarse a una estimación mejor de los datos de símbolo transmitidos mediante la suma de energía de todas las copias redundantes de ese símbolo. El proceso de generación de una estimación mejorada del símbolo se describe en detalle en WO 95/8888.

En la realización del ejemplo la hipótesis del primer test es que es que la trama fue transmitida a velocidad completa. Bajo la hipótesis de la velocidad completa, no existe repetición de símbolos y por eso no se realizan combinaciones de datos de símbolo. En el bloque (254) los datos desde el combinador de símbolos (222) se proporcionan a un decodificador de Viterbi modificado (224). En la realización del ejemplo, el decodificador de Viterbi modificado (224) es un decodificador de Viterbi pero alguien experto en el arte, apreciará que son igualmente aplicables otras formas de decodificadores convolucionales. El diseño e implementación de un decodificador de Viterbi son conocidos en el arte y una implementación específica de un decodificador de Viterbi está descrita en WO 95/8888.

El decodificador de Viterbi modificado (224) computa y calcula en la trama la información de los bits transmitidos y también los bits de CRC y proporciona el CRC calculado de la trama al subsistema de comprobación de CRC (232). En el bloque (256), el subsistema de comprobación de CRC (232) genera un conjunto de bits redundantes a partir de los bits de información decodificados como fue descrito con referencia al generador de CRC (6). El subsistema de comprobación de CRC (232) compara los bits de CRC generados mediante el calculo de los bits de información con el CRC generado de los bits redundantes del decodificador de Viterbi modificado (224). El resultado de la comparación es proporcionado al procesador de control (230) el cual determina si la prueba de comprobación de CRC se ha pasado con éxito.

Si se ha pasado la prueba de CRC en el bloque (258), entonces el método continúa con el bloque (266). En el bloque (266), la calculadora de tasa de error de símbolo (SER) (228) calcula el símbolo de error de velocidad de transferencia de datos para la trama decodificada. La calculadora de SER (228) genera una decisión hardware calculada mediante los datos de símbolo recibidos o de una decisión hardware calculada desde el decodificador de Viterbi modificado (224). Entonces la calculadora de símbolo de tasa de error (228) recibe los datos decodificados de la trama desde el decodificador de Viterbi modificado (224) y codifica la trama usando la misma operación de codificación que la que fue realizada por el codificador (10) (Fig. 1) para generar un conjunto de datos de símbolo re-codificados. Los datos de símbolo re-codificados son comparados símbolo a símbolo mediante una decisión hardware y el numero de discrepancias entre los dos conjuntos de datos símbolos es el símbolo de tasa de error que se proporciona al selector (250) en el bloque (268).

En esta realización, la memoria intermedia de salida (226) proporciona los datos de símbolo decodificados al selector (250) solo después de que la comprobación de CRC haya sido pasada con éxito para la descodificación de la velocidad de la hipótesis. En una realización preferente, el decodificador de Viterbi modificado (224) proporciona datos de métrica al selector (250) que le asisten en la selección de la velocidad. Los datos de métrica proporcionados pueden ser un bit simple de métrica de Yamamoto o una métrica total.

Si la prueba de CRC falla en el bloque (258), entonces en el bloque (260) del procesador de control (230) incrementa un contador del número de intentos hechos en la descodificación de la trama bajo la hipótesis de la velocidad actual. En el bloque máximo número de intentos de decodificación (262) el procesador de control (230) determina si el número de intentos en la decodificación de la trama ha alcanzado un predeterminado número de intentos máximo para decodificar la trama con la hipótesis de la velocidad de transferencia de datos actual. Si se ha alcanzado el máximo numero de intentos, entonces el método procede a que el bloque indicador de borrado de salida (264) y el procesador de control (230) proporcionen una señal al selector (250) indicando que la trama no puede ser decodificada bajo la hipótesis de la velocidad de transferencia de datos actual.

Si en el bloque de control (262), no se ha alcanzado el número máximo de intentos para decodificar la trama con la hipótesis de la velocidad de transferencia de datos actual, entonces el procesador de control (230), proporciona un mensaje al decodificador de Viterbi modificado (224) para que incremente su contador de trayectorias (i) en uno. Entonces en el bloque (254), el decodificador de Viterbi modificado (224) busca el iésimo mejor camino a través de la convolución. El método procede al bloque (256) y repite el proceso descrito previamente.

En el bloque (270), el procesador de control (230) determina si todas las posibles velocidades han sido probadas. Si no es así, entonces el método procede al bloque (272), el cual selecciona la próxima velocidad ha ser probada entonces el método procede al bloque (252) y se prueba la siguiente hipotética velocidad. En respuesta a una señal del procesador de control (230), la memoria intermedia de tramas (220) proporciona los datos de trama al combinador de símbolos (222). El procesador de control (230), proporciona una señal indicativa de la velocidad hipotética que ha de ser probada por el combinador de símbolos (222). En el bloque (252), el combinador de símbolos (222) combina los datos de símbolo de acuerdo ha la velocidad hipotética que va a ser probada. El método continúa con el bloque (254) y procede como se describió anteriormente.

Si en el bloque (270), han sido probadas todas las velocidades, entonces en el bloque (274) el selector (250) determina la velocidad más probable a la cual los datos fueron transmitidos y proporciona los correspondientes datos de esa velocidad en el bloque (276). El selector (250) puede decidir borrar la trama debido a medidas de mala calidad. En la realización del ejemplo, el selector (250) determina la velocidad basándose en la tasa de error de los símbolos de las diferentes tramas decodificadas y de los valores de los datos de la métrica.

Se puede emplear un gran número de métodos para realizar la búsqueda de una trayectoria adicional de la primera realización del ejemplo. De cualquier forma la mayoría de los métodos requieren una gran cantidad de memoria para almacenamiento. En un método preferido de la primera realización el ejemplo, se aplica un método que reduce la cantidad de memoria y el tiempo para la búsqueda de la trayectoria. Por ejemplo, un método podría ser el decodificar todas las trayectorias con una cierta métrica del umbral de la mejor trayectoria que se ha encontrado mientras que se corría el decodificador de Viterbi modificado (224).

Lo primero un breve estudio de la operación de descodificación convolucional se presenta en las Figs. 6,7 y 8. La Fig. 6 muestra una transición de estados posible con longitud de contención tres (K = 9). El número de estados posibles (S) en un decodificador convolucional es dado por la ecuación:

S=2^{k-1}

\newpage

Así, en la Fig. 6 hay cuatro estados ya que k=3. Refiriéndonos a la Fig. 9, el estado del decodificador puede ser definido por los valores de los bits en los puntos (300) al (310). Hay cuatro de tales estados. Cuando el próximo bit se mueve al punto (300), el valor del punto (300) se mueve al punto (310) y el valor del punto (310) será desechado.

Asociado con cada estado hay un estado métrico el cual esta inversamente relacionado con la probabilidad de la secuencia de supervivencia del estado en un determinado momento, por eso la métrica mas alta se correspondo con el menos probable de la probabilidad. En la Fig. 6 la métrica de estado para cada uno de los estados está en paréntesis encima del estado inicial. En adición hay una métrica de ramificación asociada que está inversamente relacionada con la probabilidad de transición de un estado a un tiempo N a otro estado al tiempo N+1. Por eso por ejemplo mirando al estado inicial 01 (punto (290))si el próximo bit que entre al codificador es un cero, entonces el estado del codificador al tiempo N+1 será 00 (punto (292)). Mientras que, si el estado inicial es 01 (punto (290))y el próximo bit que entra al decodificador es un uno, entonces el estado del codificador al tiempo N+1 será 10 (punto (294)).

El valor de la métrica de estado al tiempo N+1 es calculado por adición de la métrica de estado del estado inicial al tiempo N+1 con rama para la transición a tal estado. La rama que resulta con la métrica de estado mas baja es seleccionada y la otra rama que conduce a tal estado es desechada. En la Fig. 7 se ilustran las bifurcaciones seleccionadas de acuerdo con el estado y las métricas de rama de la Fig. 6. En el tiempo N+1, primero se muestra entre paréntesis la nueva métrica de estado calculada y después es mostrado el valor del estado desde el cual ha ocurrido la transición seleccionada.

Por ejemplo si uno quiere calcular la métrica de estado para el estado 00 en el tiempo N+1 (punto (292)), entonces hay dos caminos que llevan al estado 00. Nótese que esto es siempre el caso cuando se usa un codificador de velocidad 1/n o de un codificador basado en pinchar el chorro de datos de un codificador de velocidad 1/n. Una bifurcación llega desde el estado 01 (punto (290)). La métrica de estado en el estado 01 (punto (290)) es 6 y la métrica de bifurcación asociada para la transición al estado 00 (punto (292)) tiene el valor 10. Por consiguiente la métrica de estado en el punto 00 al tiempo N+1 (punto (292))podría tener 16 si la rama fuera seleccionada. Una segunda bifurcación llega desde el estado 00 (punto (291)). La métrica del estado 00 (punto (291)) es 4 y la métrica de bifurcación asociada para la transición al estado 00 (punto (292))tiene el valor 2. Por consiguiente la métrica de estado en el punto 00 al tiempo N+1 (punto (292)) podría tener 6 si la rama fuera seleccionada. Como 6 es menor que 16 se selecciona el camino desde el estado 00 (punto (291)) y al estado se le asigna la métrica 6.

La Fig. 8 ilustra un camino seleccionado a través de la convolución. Como los bits de cola se conocen, es conocido el estado final. Ya que en la realización del ejemplo los bits de cola son todos ceros, el estado final conocido es el estado cero. Como solo hay una trayectoria que lleva a este estado, la trayectoria seleccionada es la que lleva a este estado conocido. Una vez que la trayectoria es conocida los datos se colocan en la salida por medio de una operación de cambio hacia atrás en donde el decodificador traza hacia atrás a lo largo de la trayectoria seleccionada y pone en la salida los bits resultantes de la transición seleccionada. Por ejemplo, en la transición del estado 10 al estado 11, el bit de salida debe de ser el valor 1. Este es el método usado para seleccionar la mejor trayectoria a través de la convolución. La selección de una sub-optima trayectoria queda para ser discutida mas adelante mas profundamente.

El decodificador (224) de la realización del primer ejemplo de la presente invención se ilustra en la Fig. 10. El símbolo combinado desde el combinador de símbolos se proporciona desde la calculadora de métrica de bifurcación (350). El diseño e implementación de las calculadoras de métrica de bifurcación son bien conocidas en el arte. El elemento Selector por Comparación de Suma (ACS)(354), de acuerdo con las métricas de bifurcación de la calculadora de métrica de bifurcación (350), determina el valor de las métricas de estado como se describe arriba en referencia a las Figs. 10 y 11. Las métricas de estado calculadas nuevamente son almacenadas en la memoria de métrica de estado (352) y se proporciona una indicación de la bifurcación seleccionada a la memoria de encadenamiento hacia atrás (358). Cuando han sido calculadas para una trama todas las métricas de estado, el elemento de memoria de encadenamiento hacia atrás (358) bajo el control del elemento de control de encadenamiento hacia atrás (360), selecciona la trayectoria optima a través de la convolución como se describió arriba y pone los datos decodificados al elemento de comprobación de bit CRC (no mostrado).

Si el test de CRC falla, entonces se determina una segunda mejor trayectoria a través de la convolución. El algoritmo para buscar la mejor trayectoria a través de la convolución (es decir el algoritmo de Viterbi) es vuelto a correr. De cualquier manera, en adición con los pasos descritos arriba, y de acuerdo con una realización ilustrativa, una medida de la distancia entre la mejor trayectoria y la trayectoria rechazada en cada instante de tiempo es calculada y almacenada en el medio de Clasificación de diferencias (\Delta) 356. El valor de \Delta_{s,p} es el valor de la diferencia de la métrica en el estado (s) donde la trayectoria fue rechazada y el valor de la métrica en el estado (s) en la trayectoria seleccionada (p).

\Delta_{s,p} = métrica de estado en trayectoria rechazada - métrica de estado en trayectoria seleccionada

Ejemplos de valores de D_{s,p} (o \Delta_{s,p} )están ilustrados en la Fig. 11. Cada trayectoria está asociada con su valor D_{p} el cual esta medido relativo a la mejor trayectoria. El valor de D_{p} es dado por el D_{p} de la mejor trayectoria con el que esa trayectoria combina y las diferencias en el punto de unión D_{s,p}. De esta manera, el valor de D_{p} de la mejor trayectoria (es decir la salida del algoritmo de Viterbi) es cero.

Los medios de Clasificación D (356) determina el valor mas bajo de D o D_{min}. En el punto donde se ha encontrado el D_{min}, se realiza una operación (se corre el programa del algoritmo)de cambio hacia atrás para determinar la trayectoria que llega a este punto de divergencia. Refiriéndonos a la Fig. 12, se volvió a correr tal como fue descrito el proceso de calculo de la métrica de estado y los medios de clasificación D (356) encontró la mínima diferencia de trayectoria en el punto D_{5,1} (362). A partir del punto (362), la memoria de encadenamiento hacia atrás (358) bajo el control del controlador de encadenamiento hacia atrás 360 determina la segunda mejor trayectoria y la correspondiente secuencia de datos decodificados. Esto se obtiene reemplazando los primeros N+6 bits de datos en el dato correspondiente a la mejor trayectoria. En una realización preferida la operación de encadenamiento hacia atrás se trunca dentro de un pequeño factor de longitud al punto de divergencia de la trayectoria, porque raramente un evento de error es mas largo que el pequeño factor de longitud. En la Fig. 12 esto ocurre en el punto (364). El valor D_{p} de la segunda mejor trayectoria en la Fig. 12 es D_{p} = D_{5,1}.

Para encontrar la mejor tercera trayectoria, se realiza por tercera vez el mismo proceso de calculo de métrica de estado y los valores D_{s,p} se calculan como se describió anteriormente pero esta vez son calculados para la selección de trayectoria relativa a la segunda mejor trayectoria, estos necesitan ser calculados solo en el caso por encima del tiempo en el que la segunda mejor trayectoria se fusiona con la mejor trayectoria. En otras palabras, la instancia de tiempo N+5 en las Figs. 12 y 13. Refiriéndonos a la Fig. 13. El elemento Selector por Comparación de Suma (ACS)(354) computa los valores necesarios de diferencia de trayectoria con la segunda trayectoria (D_{0,2}, D_{1,2}, D_{2,2}, D_{3,2} y D_{4,2}. Debe ser notado que algunas de estas métricas pueden haber sido calculados previamente pero deben ser consideradas de nuevo. Los valores por comparación no están basados en la distancia a la segunda mejor trayectoria sino a la distancia a la mejor trayectoria. De esta manera, los valores métricos proporcionados a los medios de Clasificación D (356) deben ser relativos a la mejor trayectoria a través de la convolución. Por ejemplo, para tener por comparación la diferencia métrica para la trayectoria designada con D_{4,2} debe ser calculado un valor D_{p} para esta trayectoria mediante la suma de D_{4,2} (la distancia a la segunda trayectoria)con D_{5,1} la distancia de la segunda trayectoria a la primera trayectoria. El elemento Selector por Comparación de Suma (ACS)(354) proporciona los valores calculados a los medios de clasificación D (356). Los medios de clasificación (356) entonces buscan la trayectoria tercera más cercana buscando los valores más pequeños de D_{p} para las trayectorias fusionada con la mejor y la segunda trayectoria.

En la realización ilustrativa, los medios de clasificación D (356) no almacenan todos los valores si solo los valores más pequeños M, donde M es el máximo número de trayectorias que han sido buscadas. Entonces para cada subsiguiente i-enésima mejor trayectoria solo un mínimo de valores M-i deben ser almacenados.

En una realización alternativa, el proceso de decodificación no se vuelve a correr para encontrar cada trayectoria sub-óptima, se prefiere almacenar las métricas de estado y rehusarlas para cada búsqueda de trayectoria. Esto reduce el número de cálculos pero incrementa la cantidad de memoria requerida. Debe ser recordado que los ejemplos ilustrados en las Figs. 11 a 13 están muy simplificadas por motivos de ilustración. En la realización del ejemplo, el tamaño de trama es de 288 bits de información y la longitud de código es nueve (K=9) lo que abarca 256 estados. Así que asumiendo que cada métrica de estado requiere un octeto de información, la memoria que se necesita para almacenar la métrica de estado para cada estado, asumiendo 5 bits de métrica de estado, se requerirá aproximadamente 74 kilo-octetos de memoria.

La Fig. 14 ilustra el dispositivo del segundo ejemplo de realización del sistema de decodificación (56) de la presente invención y la Fig. 15 proporciona un diagrama de flujo (500) acompañando la ilustración del método del segundo ejemplo de ilustración de la presente invención. En el bloque (550) la trama de los datos de símbolo revisados mediante software desde el dispositivo de des-entrelazado (54) es proporcionado y almacenado en la memoria intermedia de tramas (420).

Entonces en el bloque (552), los símbolos son combinados en el combinador de símbolos (422) en concordancia con hipótesis de la velocidad actual. El proceso de combinación se aprovecha del hecho de que para velocidades menores que la velocidad completa hay redundancia en los datos de símbolo transmitidos y por eso puede llegarse a una estimación mejor de los datos de símbolo transmitidos mediante la suma de la energía de todas las copias redundantes de esos símbolos. El proceso de generar una estimación mejorada de los símbolos es descrito en detalle en WO 95/8888.

En la realización del ejemplo primero prueba con la hipótesis de que la velocidad transmitida es la velocidad completa. Bajo la hipótesis de la velocidad completa, no existen símbolos de repetición y por eso no se realiza ninguna combinación de los símbolos. En el bloque (554), los datos desde el combinador de símbolos (422) son proporcionados a un decodificador de Viterbi modificado. En la realización del ejemplo, el decodificador modificado de Viterbi (424) es un decodificador de Viterbi pero una persona experta en el arte apreciará que es igualmente aplicable cualquier otro decodificador convolucional. El diseño e implementación de un decodificador de Viterbi es conocido en el arte y una implementación específica de un decodificador de Viterbi está descrita en WO 95/8888.

En la realización presente, el decodificador de Viterbi (424) incluye una calculadora de métrica de bifurcación (450). Los símbolos combinados desde el combinador de símbolos (422) esta provisto de una calculadora de métrica de bifurcación (450). El diseño e implementación de una calculadora de métrica de bifurcación es bien conocida en el arte. El elemento Selector por Comparación de Suma (ACS)(454), en concordancia con las métricas de bifurcación de la calculadora de métrica de bifurcación (450), determina los valores las métricas de estado como se describió anteriormente con referencia a las Figs. 6 y 7. La métrica de estado nuevamente calculada es entonces almacenada en la memoria de métrica de estado (452) y es proporcionada una indicación de la bifurcación seleccionada al elemento de memoria de encadenamiento hacia atrás (458). Cuando todas las métricas de estado han sido calculadas para la trama, el elemento de memoria de encadenamiento hacia atrás (458) bajo el elemento de control de encadenamiento hacia atrás (460), selecciona la trayectoria optima a través de la convolución como se describió anteriormente y las salidas de los datos decodificados hacia un elemento de comprobación de bit CRC (432). En el bloque (554), el contador i y el valor m son inicializados a 1. El número de veces que ha corrido el programa del decodificador se denomina por i y el número de trayectorias cuyo CRC ha sido chequeado se denomina por m.

El decodificador de Viterbi modificado (424) de este modo calcula una estimación de los bits de información transmitidos y los bits de CRC en la trama. En el bloque (556) el elemento de comprobación de bit CRC (432) genera un conjunto de bits redundantes a partir de los bits de información decodificados como fue descrito con referencia al generador de CRC (6) en la Fig. 1. El elemento de comprobación de bit CRC (432) compara los bits de CRC generados de los bits de información estimados con los estimados de los bits redundantes del decodificador de Viterbi modificado (424). El resultado de la comparación es proporcionado al procesador de control (434).

Si en el bloque de control (558) se pasa con éxito la prueba de CRC, el método sigue adelante por el bloque (570). En el bloque (570), la calculadora de tasa de error de símbolo (SER) (428) calcula la tasa de error de símbolo para la trama decodificada. La calculadora de SER (428) genera una decisión hardware evaluando los datos de símbolo recibidos o recibe la evaluación desde el decodificador de Viterbi modificado (424). Entonces la calculadora de tasa de error de símbolo (SER) (428) recibe los datos decodificados de la trama desde el decodificador de Viterbi modificado (424) y codifica la trama usando la misma operación de codificación que fue realizada por el decodificador (10) para generar un conjunto de re-codificados datos de símbolo. Los datos de símbolo re-codificados se comparan símbolo a símbolo con los datos de símbolo de decisión hardware y el número de discrepancias entre los dos conjuntos de símbolos es la tasa de error de símbolos que se proporciona al selector (430) en el bloque (570).

En la realización del ejemplo, la memoria intermedia de salida (426) proporciona los datos de símbolo decodificados al selector (430) solo después de que la prueba de CRC ha sido pasada con éxito para la descodificación con la velocidad de la hipótesis. En la realización preferida, el decodificador de Viterbi modificado (424) proporciona los datos métricos al selector (430) para ayudar en la selección de velocidad. El dato métrico proporcionado al selector puede ser una métrica de Yamamoto de bit único o una métrica total.

Si en el bloque (558) falla la prueba de CRC, entonces en el bloque (560) el decodificador de Viterbi modificado (424) en el combinador de símbolos (422) corre por segunda vez el programa para la velocidad de hipótesis dada. En esta ejecución del programa, se le dice al decodificador de Viterbi modificado que procese la trayectoria más probable encontrada por el decodificador de Viterbi en la ejecución previa del programa. El elemento Selector por Comparación de Suma (ACS)(454) a través de la convolución continua actualizando la memoria de métrica de estado (452) de acuerdo con la calculadora de métrica de bifurcación (450) pero además de este procedimiento de decodificación de Viterbi normalizado, los resultados de las métricas de todas las trayectorias que se confluyen con la trayectoria procesada (la mejor trayectoria en la segunda ejecución del decodificador) suministrados al ACS por la memoria intermedia de salida (426) se envían hacia el circuito de clasificación de diferencias (\Delta) (456). El control de encadenamiento hacia atrás (460) realiza una operación de encadenamiento hacia atrás para obtener la secuencia de datos asociada con esta trayectoria. Una operación de encadenamiento hacia atrás solo se realizará si la métrica de la trayectoria satisface algún umbral de criterio. Este criterio de umbral será explicado mas adelante. Las trayectorias encontradas en este procedimiento se almacenarán en la memoria intermedia de salida (426).

El bloque (562) mediante el comprobador de CRC (432) comprueba los CRCs de las trayectorias encontradas por el bloque 560 y las almacena en la memoria intermedia de salida (426). El resultado de la comprobación de CRC se envía al procesador de control (434) y es anotado por este. En el bloque (562) el procesador de control (434) incrementa el número de trayectorias encontradas m para esta velocidad de hipótesis. En el bloque (586) el procesador de control (434) incrementa el número de ejecuciones del programa i que ha realizado el decodificador de Viterbi modificado.

Si en el bloque de control (556); no se ha alcanzado todavía el número máximo de ejecuciones del programa, entonces el procesador de control (434) chequea en el bloque (582) si hay trayectorias que han sido ya encontradas y las cuales no han sido todavía procesadas por el decodificador de Viterbi (es decir trayectorias que se unen con él todavía no se han intentado encontrar). Si no hay tales trayectorias, en el bloque (584), el procesador de control (434) indica al selector (430) que no hay trayectorias que se puedan encontrar por el decodificador para esta velocidad de hipótesis.

Si en el bloque de control (582), todavía hay trayectorias que ya han sido encontradas y que el decodificador de Viterbi modificado (424) no ha procesado todavía, el decodificador continua con el bloque (556) para chequear si el CRC de la trayectoria i-enésima más probable, la cual todavía no ha sido procesada tiene un CRC correcto. Si el CRC falla en el bloque de control (558), el procesador de control (434) indica al decodificador de Viterbi modificado (424) que procese la i-enésima mejor trayectoria. Esto se hace en el bloque (560) como se describió antes.

Si en el bloque de control (582), no hay trayectorias que han sido ya encontradas pero no procesadas, el decodificador continúa en el bloque (584) indicando al selector (430) que no se pueden encontrar trayectorias para esa velocidad de hipótesis. Si en el bloque de control (556), ya ha sido alcanzado el número máximo de ejecución del programa, el procesador de control (434) chequea en el bloque (568) si ha sido encontrada por el comprobador de CRC (432) una trayectoria que pase con éxito el CRC. Si no hay tal trayectoria el método continúa en el bloque (584). Si hay una trayectoria que pase el CRC el método continúa en el bloque (570).

En el bloque (574), el procesador de control (434) determina si han sido probadas todas las velocidades posibles. Si no, el método continúa en el bloque (576) que selecciona la próxima velocidad a ser probada, y el método continúa en el bloque (552) y se prueba la siguiente velocidad hipotética. En respuesta a una señal del procesador de control (434), la memoria intermedia de entrada de trama (420) proporciona la trama de datos al combinador de símbolos (422). El procesador de control (434) proporciona una señal indicativa de la velocidad de hipótesis que se probará en el combinador de símbolos (422). En el bloque (552), el combinador de símbolos (422) combina los datos de símbolo de acuerdo con la velocidad de hipótesis que se va a probar. El método continúa en el bloque (554) y sigue como ha sido descrito arriba.

Si en el bloque (574), han sido probadas todas las velocidades, entonces el bloque (578) el selector (430) determina la velocidad más probable con la que los datos fueron transmitidos y proporciona el dato correspondiente de tal velocidad al bloque (580). El selector (430) puede decidir borrar la trama debido a una mala calidad de la medida. En la realización del ejemplo, el selector (430) determina la velocidad basándose en la tasa de error de símbolo de las diferentes tramas decodificadas y los valores de los datos medidos.

La Fig. 16 es un es un diagrama de flujo del método de la realización del segundo ejemplo el cual ilustra la técnica de umbral para seleccionar trayectorias sub-óptimas de acuerdo con la realización de la presente invención. Este diagrama de flujo ilustra solo la búsqueda de trayectoria para una velocidad de hipótesis dada. Las siguientes definiciones son útiles para facilitar la comprensión de la siguiente invención:

p - una trayectoria en la convolución, se dará por su secuencia de información;

Y_{p} - una métrica de la trayectoria p relativa a la mejor trayectoria;

I_{p} - el punto de divergencia más pequeño en la trayectoria p;

F - una matriz de datos de m trayectorias, que contienen su secuencia de información (p), su métrica (Y_{p}) y su punto de divergencia más pequeño en la trayectoria (I_{p});

\Delta(p) - un vector de métrica de Yamamoto de trayectorias que se juntan con la trayectoria (p);

\Delta_{i}(p) - el i-enésimo valor del vector \Delta(p);

t - umbral, todas las trayectorias consideradas que tienen una métrica menor que t;

q - trayectorias que divergen de otra trayectoria (p), estas trayectorias se almacenan en una matriz N;

T - una memoria temporal de trayectorias;

C - una memoria de trayectorias con un CRC correcto; y

"encadenamiento hacia atrás parcial" - es un encadenamiento hacia atrás de longitud finita desde un punto de divergencia. La secuencia de información de divergencia se obtiene cambiando solo este número finito de bits de salida de la trayectoria de la cual diverge.

Los dos principales parámetros de esta implementación son t, el umbral, y m, el número de veces que el mecanismo ACS (Selector por Comparación de Suma) es re-ejecutado. El parámetro n es generalmente pequeño y es del orden de 2 a 4.

Para la decodificación de una velocidad dada el procedimiento comienza en el bloque (610), donde el decodificador de Viterbi modificado (424) realiza una decodificación estándar. El ACSs (454) actualiza la las métricas de estado en la memoria (452) y pone en la salida los bits de decisión hacia la memoria de encadenamiento hacia atrás (458). El mecanismo de control de encadenamiento hacia atrás (460) realiza una operación de encadenamiento hacia atrás para sacar la secuencia de datos decodificados a una memoria en forma de matriz (F) situada en la memoria intermedia de salida (426). Hasta este momento ha sido utilizada una decodificación estándar de Viterbi como apreciará una persona experta en el arte. Hay dos métricas asociadas con la trayectoria mejor: la métrica relativa al mejor camino (Y_{p}), la cual es obviamente cero, y el punto de divergencia más pequeño (I_{p}), el cual es igual a la longitud de la trama. La importancia de estos dos parámetros se aclarará a continuación.

En el bloque (612), el procesador de control (434) identifica la primera trayectoria y sus parámetros en la memoria en forma de matriz (F) que está localizada en la memoria intermedia de salida (426). Esta trayectoria se representa por (p). En la primera ejecución del programa del decodificador, la trayectoria se considera la mejor trayectoria.

En el bloque (614), el CRC de la trayectoria identificada en el bloque (612) es chequeado por el mecanismo de CRC (432). Si el CRC pasa la prueba con éxito, el procedimiento continúa en el bloque (616), y la decodificación de la trama ha terminado. Aunque no están específicamente mostrados en la Fig. 16, otros datos concernientes a la trama deben ser sacados y calculados, como por ejemplo la tasa de error de símbolo (SER) (428) o la métrica de probabilidad de la trama decodificada.

Si la prueba de CRC en el bloque (614) no se pasa con éxito, el procesador de control (434) del bloque (618) vuelve a ejecutar el programa del decodificador (424) para encontrar una trayectoria que se junta con la trayectoria (p). El ACSs (454) realiza el cálculo y actualización de la memoria de métrica de estado (452) de todos los puntos (I_{p}) en la convolución. Además de la función usual de comparación y selección el ACS (454) de decodificador modificado (424) realiza una función extra. Esta es poner en su salida hacia el circuito de clasificación de diferencias (456) el valor de la métrica de Yamamoto para esa trayectoria, indicado por (q), que se junta con la trayectoria (p) en la convolución en cada índice (j) hasta el índice (I_{p}). La métrica total de la trayectoria (q) que se une con (p) en el índice (j) (1 j = I_{p}) es dada por Y_{q} = \Delta_{j}(p)+ Y_{p}. Si la métrica Y_{q} es menor que un umbral dado t, el control de encadenamiento hacia atrás (460) realiza un encadenamiento hacia atrás parcial en la convolución desde el índice j de la trayectoria (p) donde el bit de decisión de índice j es revocado. El resultado del procedimiento de encadenamiento hacia atrás concatenado con los bits de la trayectoria (p) para índices que son más grandes que j forman la nueva trayectoria q. Esta trayectoria (q) juntas con sus métricas relativas a la mejor trayectoria y al punto de divergencia I_{q}=j-1, son almacenados en la matriz (N) de la memoria intermedia de salida (426).

Después de realizar el encadenamiento hacia atrás parcial y obtener una nueva secuencia para ese umbral en el bloque (618), el procedimiento continúa en el bloque (620), En el bloque (620) el procesador de control (434) reconoce el emplazamiento de las secuencias en la memoria intermedia de salida (426). Una matriz (T) es definida como la unión de las previas m más probables trayectorias y las trayectorias nuevas encontradas, situadas en (N). La trayectoria más probable m de (T) está entonces definida como una nueva matriz (F).

El procedimiento continúa entonces en el bloque (622) en donde todas las nuevas trayectorias encontradas se chequean en el comprobador de CRC (432). Estando estos nuevos caminos en la memoria temporal de trayectorias (T) donde esta definida como una matriz (N). Si alguna de las trayectorias tiene un CRC correcto, la trayectoria y su métrica se mantienen en una matriz indicada por (C). Es obvio para una persona experta en el arte que los procedimientos realizados en el bloque (622) pueden ser realizados simultáneamente a los procedimientos realizados en el bloque (618). Es también obvio que las matrices denominadas por (T, F, N) y (C) no necesitan ser definidas como matrices distribuidas en la memoria, sino que están los punteros de las sucesiones almacenados en las memorias intermedias de salida. Estas matrices se definen por la explicación clara del procedimiento.

Si en el bloque (624) ha sido alcanzado el máximo número de ejecución del programa en el decodificador (m=1) o no hay mas secuencias para ser procesadas que cumplan el criterio de umbral ((F) está vacío), (434) el procesador de control continua en el bloque (628). Si en el bloque (628) no hay secuencias que tengan el CRC pasado con éxito, es decir la matriz (C) está vacía, el procesador de control (434) finaliza el proceso de decodificación para la velocidad de hipótesis actual e indica al selector (430) que no se encontraron mas secuencias. El procesador de control (434) puede sacar hacia el selector (430) los datos concernientes a la velocidad de hipótesis fallida, por ejemplo la métrica de probabilidad de la mejor trayectoria, para asistir al decodificador en esta decisión.

Si por otro lado (C) no esta vacía en el bloque (628), el proceso continúa en el bloque (630) donde el procesador de control (434) saca hacia el selector la trayectoria con la métrica más pequeña que haya pasado la prueba de CRC. El selector (430) puede ser suministrado también con otros datos concernientes a la trama decodificada, por ejemplo la tasa de error de símbolo desde (428) y la métrica de la trayectoria.

Si en el bloque (624), el decodificador no ha alcanzado todavía el máximo número de veces que se ha de correr el programa (m>1) y hay secuencias para ser procesadas ((F) no está vacío), el procesador de control (434) decrementa m y el procedimiento continua en el bloque (612) para continuar procesando la secuencia más probable siguiente (la primera secuencia en (F)).

La Fig. 17 es un diagrama de convolución de trayectorias establecidas mediante el método de decodificación del segundo ejemplo de realización de la presente invención. En la Fig. 17, la mejor trayectoria (la primera que es sacada por el decodificador de Viterbi (424), no la primera transmitida correctamente) esta pintado por la línea gruesa discontinua. El método puede ser ilustrado asumiendo que el CRC de la mejor trayectoria no es correcto. En la primera vez que se vuelve a correr el programa del decodificador, se encuentran tres trayectorias que tienen una métrica menor que la del umbral establecido. Sus puntos de divergencia son (i, j), y (k) y define las secuencias de información. Estas son trayectorias que divergen una vez de la mejor trayectoria. Suponemos que la trayectoria que diverge en el punto (j) tiene la métrica menor y que su CRC no es correcto. Buscando trayectorias que divergen de esa trayectoria, encontramos dos trayectorias que tienen una métrica menor que la del umbral. Estas trayectorias son j' y j'' . Ahora se vuelve a correr por segunda vez el programa del decodificador. Esta vez se examinan las trayectorias que divergen del camino con menor métrica fuera de conjunto de trayectorias (i, k), j' y j''. Suponemos que la trayectoria que diverge en el punto (k) tiene la métrica menor y que su CRC no es correcto. Se buscan ahora mas atrás trayectorias que divergen de (k). En el diagrama, hay tres trayectorias con una métrica menor que la del umbral, k, k' y k''.

Notar que el tiempo requerido para la búsqueda de trayectorias divergentes de una trayectoria dada no es constante ya que solo se necesita correr el decodificador desde el punto de divergencia. Los ciclos de decodificación para el ejemplo de arriba se pueden resumir en la siguiente tabla:

TABLA 1

Ciclos de decodificación	Ciclos CB
Algoritmo de Viterbi Ordinario (VA)	VA Ordinario
VA Ordinario + \Delta vector desde la mejor trayectoria	CB Parcial en i,j y k
VA a partir de j + \Delta vector desde trayectoria j	CB Parcial en j' y j''
VA a partir de k + \Delta vector desde trayectoria k	CB Parcial en k', k'' y k'''

Debe notarse que se pueden necesitar memorias intermedias adicionales para cada trayectoria en la cual se chequean trayectorias divergentes. Se necesitan memorias intermedias extras para las trayectorias divergentes. Estas memorias pueden ser rehusadas si no se comprueba el CRC. En el ejemplo de la Fig. 17, en las 9 trayectorias que fueron encontradas solo se corrió el programa 4 (n+2) veces. En las 9 trayectorias de mayor probabilidad que fueron encontradas, se garantiza solo en 4 (n+2) de ellas ser la más probable. Esta es una ventaja innovadora de la segunda realización respecto de la primera realización en donde el decodificador necesita volver a correr el programa al menos una vez (o dos en el caso de memoria de encadenamiento hacia atrás truncado) para cada trayectoria extra encontrada. En la segunda realización del ejemplo, el criterio de umbral nos permite encontrar, a veces, mas de una trayectoria para cada ejecución del decodificador y no esta limitado por la implementación del decodificador usar un encadenamiento hacia atrás truncado.

En el caso de un CRC muy fiable (muchos bits)el proceso de decodificación puede ser parado en la primera secuencia que se encuentre con un CRC correcto. En el caso de un CRC poco fiable, las trayectorias se encontraran en tanto que el tiempo lo permita (la llegada de la siguiente trama), y todas las trayectorias con un CRC correcto serán mantenidas y el decodificador decidirá sobre la trayectoria que tiene la métrica más pequeña con un CRC correcto.

La descripción previa de las realizaciones preferidas se proporciona para permitir a cualquier persona experta en el arte hacer o usar la presente invención. Modificaciones varias sobre estas realizaciones se podrán hacer fácilmente por alguien experto en el arte, y los principios genéricos definidos aquí pueden ser aplicables a otras realizaciones sin caer fuera del alcance de la presente invención tal como se determina por las siguientes reivindicaciones.

Claims (9)

1. Un dispositivo para determinar la velocidad de transferencia de una trama de datos que contiene datos numéricos codificados con una velocidad entre una pluralidad de velocidades de transferencia diferentes, los cuales datos numéricos comprenden bits de información y bits de control asociados, comprendiendo el dispositivo:

un medio de combinación (222,422) para combinar los datos numéricos de una trama de datos dependiendo de cada una de las velocidades de transferencia de datos para producir los datos combinados;

un medio de decodificación convolucional (224,424) para decodificar los datos combinados por medio de la identificación de una trayectoria optima para producir a través de la cual los datos decodificados;

medios de validación (232,432) para validar los datos decodificados, como representación de los dichos bits de información y los bits de control asociados, utilizando los bits de control asociados y produciendo una indicación de la validación de los datos;

caracterizado porque

el medio de decodificación convolucional (224,424) está organizado para identificar a través de él una trayectoria sub-optima que tiene una métrica respectiva dentro de un umbral predeterminado de una métrica correspondiente a la trayectoria optima y para entregar a la salida los datos decodificados correspondientes a cada una de las trayectorias sub-optimas identificadas;

el medio de validación (232,432) esta organizado para validar los datos decodificados para cada una de las trayectorias sub-optimas identificadas y para entregar en la salida una indicación de las validaciones de ellas; y

la velocidad de transferencia para la trama es seleccionada como la correspondiente a la trayectoria para la cual el medio de validación (232,432) entrega en la salida una indicación de validación.

2. El dispositivo de la reivindicación 1 en donde el dicho medio de validación (232,432) incluye medios que permiten el control de redundancia cíclica (CRC) de dichos bits de control con respecto a los dichos bits de información.

3. El dispositivo de la reivindicación 2 incluyendo además un medio que permite el control de redundancia cíclica de la dicha trayectoria sub-optima.

4. El dispositivo de cualquiera de las reivindicaciones precedentes en donde el dicho medio de decodificación (224,424) es un decodificador de Viterbi.

5. El dispositivo de cualquiera de las reivindicaciones precedentes en donde las dichas métricas son las métricas de Yamamoto.

6. Un sistema para determinar la velocidad de transferencia de una trama de datos conteniendo los datos numéricos codificados a una velocidad entre una pluralidad de velocidades de transferencia, los cuales datos numéricos comprenden bits de información y bits de control asociados, el sistema comprendiendo dispositivos tales como los reivindicados en cualquiera de las reivindicaciones precedentes.

7. Un método para determinar la velocidad de transferencia de una trama de datos conteniendo los datos numéricos codificados a una velocidad entre una pluralidad de velocidades de transferencia, los cuales datos numéricos comprenden bits de información y bits de control asociados, comprendiendo el método las operaciones consistentes en:

combinar los datos numéricos de una trama de datos dependiendo de cada una de las velocidades de transferencia para producir los datos combinados;

decodificar por convolución los datos combinados mediante identificación de una trayectoria optima para producir a través de la cual los datos decodificados;

validar los datos decodificados, como representación de los dichos bits de información y los dichos bits de control asociados, utilizando los bits de control asociados y entregando en la salida una indicación de la validación de los datos:

caracterizado porque las operaciones consisten en:

identificar a través de aquí las trayectorias sub-optimas que tienen métricas respectivas dentro de un umbral predeterminado de una métrica correspondiente a la trayectoria optima y entregar a la salida los datos decodificados correspondientes a cada uno de las trayectorias optimas identificadas;

validar los datos decodificados para cada una de las trayectorias sub-optimas identificadas y entregar a la salida una indicación de las validaciones de ellas; y

seleccionar la velocidad de la transferencia de datos para la trama como correspondiente a la trayectoria para la que fue puesta la indicación de validación.

8. El método de la reivindicación 7 en donde la validación de los datos decodificados comprende control de redundancia cíclica de los bits de control con respecto a los bits de información.

9. El método de la reivindicación 8 comprendiendo además control de redundancia cíclica para las trayectorias sub-optimas.