ES2231844T3

ES2231844T3 - Descodificacion huffman de alta velocidad binaria.

Info

Publication number: ES2231844T3
Application number: ES97304069T
Authority: ES
Inventors: Jeffrey A. Hintzman; Brian R. Jung
Original assignee: Hewlett Packard Co
Current assignee: HP Inc
Priority date: 1996-06-19
Filing date: 1997-06-11
Publication date: 2005-05-16
Anticipated expiration: 2017-06-11
Also published as: US5818364A; EP0814614A2; DE69732271T2; JPH1075181A; EP0814614B1; DE69732271D1; SG73441A1; EP0814614A3

Abstract

SE SUMINISTRA UN DESCODIFICADOR DE HUFFMAN (300), DE ALTA VELOCIDAD DE BITS PARA UNA CORRIENTE COMPRIMIDA DE BITS DE DATOS. EN UNA REALIZACION EJEMPLAR, SE EXPLICA LA COMPRESION DE DATOS JPEG Y MPEG. UN REGISTRO DE DATOS DE ENTRADA, SOBREDIMENSIONADO (313) RECIBE PALABRAS DE DATOS DE ENTRADA, SECUENCIALES (BUS 200) A SER DESCODIFICADAS. CADA NUEVA PALABRA DE DATOS ES AÑADIDA A LOS DATOS QUE YA ESTAN EN EL REGISTRO DESPLAZANDO HACIA LA DERECHA LA NUEVA PALABRA DE DATOS EL NUMERO DE BITS DE DATOS VALIDOS EN EL REGISTRO. SE REALIZA UNA OPERACION OR LOGICA EN MODO DE BIT (315) PARA CARGAR UN REGISTRO DE DATOS OPERATIVOS (301). EL REGISTRO DE DATOS OPERATIVOS ES DESPLAZADA HACIA LA IZQUIERDA (317) EN BASE AL NUMERO DE BITS EN UN PAR DE COEFICIENTE DE PALABRA, DE CODIGO HUFFMAN, PREVIO. EL PAR MAS A LA IZQUIERDA DEL TAMAÑO APROPIADO ES SEPARADO PARA SU EXAMEN. LAS CADENAS DE BITS SEPARADAS SON EXAMINADAS COMO REPRESENTANTES DEL COEFICIENTE DEL PAR DE COEFICIENTE DE PALABRA DE CODIGO, PREVIO Y COMO PALABRA DE CODIGO ACTUAL. LA PALABRA DE CODIGO ES UTILIZADA PARA ACCEDER A UNA TABLA DE CONSULTA DE HUFFMAN (323). LA TABLA DE CONSULTA SUMINISTRA LONGITUD DE RECORRIDO DE CEROS, TAMAÑO DE COEFICIENTE Y LONGITUD DEL PAR DE COEFICIENTE DE PALABRA DE CODIGO QUE SE UTILIZA PARA EL SIGUIENTE DESPLAZAMIENTO A LA IZQUIERDA. CABECERA, MARCADOR E INFORMACION DE LIMITE DE BYTES (BUSES (202, 204) SON RELLENADAS SEPARADAMENTE (303, 305, RESPECTIVAMENTE) PARA CONSTRUIR PALABRAS DE LA MISMA ANCHURA QUE LAS PALABRAS DE LOS DATOS DE ENTRADA. EL DESPLAZAMIENTO SIMULTANEO EN PARALELO CON EL EXAMEN DE LAS PALABRAS DE DATOS PRESERVA LAS UBICACIONES RELATIVAS DE LA CABECERA/MARCADORES CON LOS DATOS.

Description

Descodificación Huffman de alta velocidad binaria.

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

La presente invención se refiere generalmente a la compresión y descompresión de datos usando codificación Huffman, particularmente a codificación Huffman en aplicaciones de imágenes fijas (JPEG: Joint Picture Expert Group) y videoimágenes (MPEG: Moving Picture Expert Group), y específicamente a descodificación Huffman de alta frecuencia de bits.

2. Descripción de la técnica relacionada

La compactación de datos, también denominada compresión de datos, para transmisión o almacenamiento a largo plazo, puede ser efectuada usando técnicas de codificación de longitud variable. Las cadenas de bits de datos de longitud fija son codificadas en cadenas de bits de longitud variable, con las cadenas de bits de datos, o palabras, ocurriendo más frecuentemente siendo representadas por palabras de código de menor longitud, reduciendo así las exigencias de tiempo de transmisión o de equipo de almacenamiento. Los datos comprimidos no pueden ser utilizados por un procesador de datos en esta forma compactada. Por tanto, son descodificados de vuelta a su forma de longitud fija, también conocido como descompresión.

Una forma de códigos de longitud variable, redundancia mínima fue propuesta por D.A. Huffman en un artículo titulado "Un método para la construcción de códigos de redundancia mínima", Memorias técnicas del IEEE, IRE, Volumen 40(9), páginas 1.098-1.101, derechos reservados 1.952.

En codificación y descodificación Huffman, los símbolos con probabilidades grandes de producirse obtienen códigos de longitudes menores en bits. La codificación Huffman es usada ampliamente porque proporciona una construcción directa recta, en árbol binario, y una longitud media óptima de palabras de código.

Diversas técnicas han sido desarrolladas para descodificar códigos Huffman. Básicamente, descodificar un flujo de códigos Huffman es efectuado siguiendo un árbol binario de descodificador. En general, estos motores de descompresión descodifican un código Huffman iterativamente, uno o dos bits a la vez usando lógica secuencial, o en paralelo, descodificando todo el código en un ciclo de reloj usando lógica combinatoria.

En la técnica de la reproducción tipográfica digital, ha sido adoptada una norma que usa códigos Huffman para compresión de datos. Esta norma fue propuesta por el Joint Picture Expert Group (JPEG) del Comité ANSI X3L2.8, publicada como: "Compresión y codificación digitales JPEG de imágenes fijas de tono de variación continua", Borrador ISO 10918, 1.991. Una norma similar fue propuesta por el Moving Picture Expert Group (MPEG), publicada como: ISO/IEC JTC1 CD 11172, "Codificación de imágenes cinematográficas y audioseñal asociada para soportes de almacenamiento digital hasta 1,5 megabits/segundo", International Organization for Standarization (ISO), 1.992 (conocida como "MPEG-1").

Para aplicaciones de alta frecuencia de bits, tales como impresoras tipográficas a todo color, transmisión de imágenes en color en faxes o transmisión de vídeo digital, etc., el diseño de un descodificador Huffman adecuado es crítico. Tanto la descodificación en serie como en paralelo son difíciles debido a la necesidad de un bucle de realimentación necesario para realinear el flujo de bits. El código de longitud variable debe ser descodificado en su cadena de datos original de longitud fija usando una tabla programable de consulta de código. Esta operación debe ser completada preferiblemente en un ciclo antes de que la palabra de código siguiente pueda ser descodificada, una tarea complicada por la naturaleza de longitud variable de cada palabra de código consecutiva. Además, para funcionar en frecuencias altas de reloj, la cantidad de lógica en el trayecto crítico debe ser minimizada.

Para la aplicación específica de datos JPEG/
MPEG, hay más complejidades además de la operación real de descodificación Huffman. Las palabras de código Huffman (limitadas a un máximo de 16 bits en la norma JPEG) son usadas para representar un par de datos de "longitud de secuencia limitada/coeficiente". La longitud de secuencia limitada (RLL: run-length limited) representa el número de coeficientes nulos consecutivos inmediatamente precedentes al coeficientes actual, que tiene un tamaño representativo del número de bits usados para codificar el dato de coeficiente real. Así, como se muestra en la Figura 1, cada palabra 103 de código Huffman de longitud variable es seguida por un valor de coeficiente 105 codificado en longitud variable, donde la palabra 103 de código Huffman expresa cuantos bits son usados para codificar el valor de coeficiente. Por ejemplo, el dato representado puede ser un valor de coeficiente de doce bits con signo, tal como un vector de estímulos de colores rojo, verde, azul ("RGB") o cian, magenta, amarillo, negro ("CMYK") para transformación cromática de un píxel de imagen, 8 bits por 8 bits. Cada palabra de código es un coeficiente que se transformó desde un píxel en la imagen. Los principios fundamentales de las construcciones tridimensionales para RGB (rojo, verde, azul) u otros sistemas tricromáticos son tratados en la literatura, tal como "Principios de la tecnología del color" de Billmeyer y Saltzman, John Wiley & Sons editores, Nueva York, 1.981 (2ª edición) y "Ciencia del color: conceptos y métodos, datos cuantitativos y fórmulas" de Wyszecki y Stiles, John Wiley & Sons editores, Nueva York, 1.982 (2a edición). Sin embargo, no es necesaria eexplicación adicional para un compresión de la presente invención por un experto en la técnica.

Añadiendo aún más complejidad, generalmente hay cabeceras y marcadores 107 de control incrustados en el flujo de datos JPEG/MPEG comprimido. Estos marcadores son modelos de datos reservados, o sea, cadenas particulares reservadas de unos y ceros, que están incrustados en límites de bytes en el flujo de datos. Ejemplos serían marcadores de COMIENZO DE EXPLORACIÓN, COMIENZO DE IMAGEN, FINAL DE IMAGEN Y RECOMIENZO. Así, un descodificador Huffman JPEG debe detectar la presencia de marcador y eliminar el marcador así como cualesquier bits de relleno que pueden haber sido añadidos para alinear el marcador con un límite de bytes.

En un descodificador Huffman JPEG estándar que usa una tabla de consulta de 2^{16} posiciones de memoria, los 16 bits máximos son usados como una dirección a la tabla de consulta que proporcionaría la secuencia y el tamaño para la palabra de código particular recibida. Sin embargo, esto requiere una memoria grande y lenta. En otras palabras, la posición y la longitud del código Huffman deben ser determinadas, seguidas por una tabla de consulta u otra operación de descodificación que comunicará la longitud de secuencia y el tamaño del coeficiente siguiente, seguidas por la extracción de esos datos y un desplazamiento subsiguiente para hallar la palabra de código siguiente para repetir la operación.

Para reducir el espacio de dirección, en la Patente de EE.UU. no 5.208.593, Tong y otros desarrollan un método que usa una serie de unos anteriores en la palabra de código para indexar a una memoria más pequeña. Añadir bits afecta negativamente a la relación de compresión. Para aumentar la velocidad, en la Patente de EE.UU. no 5.379.070, Retter y otros desarrollan una metodología de procesamiento en paralelo. Este método añade componentes de hardware caros.

Así, existe una necesidad de un método y arquitectura de descodificación Huffman de alta frecuencia de bits adecuado para la descompresión de datos JPEG/MPEG de un flujo de datos de bits como se muestra en la Figura 1.

El documento US-A-5 343 195 describe un descodificador de longitud variable que comprende una memoria intermedia, un registro de desplazamiento cilíndrico y una pluralidad de puertas lógicas tipo O que suministran señales a un elemento de retención, cuya salida está acoplada a la entrada de direcciones de una tabla de consulta. Esta combinación es tratada para proporcionar una aplicación rápida de palabras de código sucesivas de longitud variable a la tabla de consulta.

Sumario de la invención

En sus aspectos básicos, la presente invención proporciona un aparato de descodificador Huffman según la reivindicación 1.

En otro aspecto básico de la presente invención, se proporciona un método para descodificar un flujo de datos codificado según la reivindicación 5.

Una ventaja de la presente invención es que es minimizada la lógica requerida en el trayecto crítico de descodificación.

Otra ventaja de la presente invención es que un par de palabra de código-coeficiente es descodificado en cada ciclo de reloj.

Otra ventaja de la presente invención es que son aceptables las exigencias de memoria de acceso aleatorio para la implementación comercial.

Otra ventaja más de la presente invención es que los marcadores de control son detectados y afectados apropiadamente como sea necesario para conformidad con normas JPEG y MPEG.

Otras características y ventajas de la presente invención resultarán evidentes al considerar la explicación siguiente y los dibujos adjuntos, en los que las designaciones de referencias iguales representan características iguales en todos los dibujos.

Descripción breve de los dibujos

La Figura 1 es una representación esquemática de un flujo de datos JPEG comprimido.

La Figura 2 es un esquema de bloques de un descodificador Huffman de acuerdo con la presente invención.

Las Figuras 3A y 3B son un diagrama lógico esquemático en detalle del descodificador Huffman de acuerdo con la presente invención como se muestra en la Figura 2.

Debería comprenderse que los dibujos citados en esta memoria descriptiva no están dibujados a escala excepto si se advierte específicamente.

Descripción de la realización preferida

Ahora se hace referencia con detalle a una realización específica de la presente invención, que ilustra el modo óptimo considerado actualmente por los inventores para llevar a cabo la invención. Realizaciones alternativas también son descritas brevemente como sea aplicable. Es proporcionada una realización ejemplar en términos de la norma JPEG. Sin embargo, una persona experta en la técnica reconocerá que la invención también puede ser aplicada en descodificación MPEG u otra descodificación de datos. El uso de la realización ejemplar no pretende ser una limitación en el alcance de la invención como es expuesta por las reivindicaciones, ni debería ser implicada ninguna limitación tal.

Una realización ejemplar específica de la presente invención es mostrada en la Figura 2.

Funcionamiento general

A modo de una visión general, el flujo de datos JPEG comprimido es introducido en palabras de cadenas de 32 bits (un solo par de palabra de código Huffman-coeficiente, de longitud máxima), por el bus 200, dentro de un descodificador 201 de coeficientes. La información de límite de bytes, una palabra de cadena de 4 bits, es introducida por vía del bus 202 en un detector 203 de longitud de secuencia limitada (RLL). Palabras de cadenas de 4 bits de códigos de cabeceras/marcadores son introducidas por vía del bus 204 para descodificación en el detector 205 de marcadores. En general, solo un registro de desplazamiento de entrada es usado para la cadena de datos de entrada.

Al comienzo de una imagen son cargadas dos palabras de entrada de 32 bits. La magnitud de desplazamiento es puesta a cero al comienzo de una imagen, así que no es realizada operación de desplazamiento en el primer ciclo. En cada ciclo de reloj posterior, los datos son desplazados en el número de bits en un par anterior de palabra de código Huffman-coeficiente.

Entonces, una operación O lógica es usada para descodificación. Esta es una operación relativamente rápida puesto que suprime la necesidad de señalar en el subconjunto de datos donde empieza la palabra de código siguiente, acortando de tal modo el trayecto crítico. Sin embargo, el problema se convierte en como retener la información de límites de bytes puesto que la posición de esta información se perderá siempre que es realizada una operación de desplazamiento y O lógica con los datos de entrada existentes. La información de límites de bytes es evidentemente crítica cuando es encontrado una cabecera/marcador de flujo de datos, tal como el marcador JPEG de RECOMIENZO o FINAL DE IMAGEN. Por tanto, esto es atendido en la implementación de manejo en paralelo del detector 203 de longitud de secuencia limitada y del detector 205 de marcadores.

Datos de entrada-carga

Observando las Figuras 3A y 3B, es mostrada una realización específica de un descodificador Huffman 300 de alta velocidad de acuerdo con la presente invención, incluyendo una solución al dilema de mantener la información de límites de bytes y marcadores de flujo de datos en coincidencia apropiada. La lógica estándar es presentada como será reconocida por los expertos en la técnica. La propia técnica de descodificación Huffman emplea un esquema para acceder a una tabla de consulta basado en el número de unos anteriores en la palabra de código Huffman. Este método de descodificación es descrito por la Patente de EE.UU. no 4.899.149 (Kahan) y la Patente de EE.UU. no 5.208.593 (Tong). Así, la descripción siguiente se concentra en la descripción de la invención como se reivindica aquí.

La palabra de datos de entrada de 32 bits recibida por el bus 200 es cargada dentro de un registro Q 301 de datos, un registro de datos de 75 bits para el segmento del flujo de datos de entrada que es descodificado actualmente. Setenta y cinco bits son necesarios porque después del desplazamiento, los once bits más a la izquierda contienen el coeficiente sin signo procedente del par anterior de palabra de código-coeficiente. Además de este conjunto de once bits, son puestas en cola dos palabras completas de 32 bits procedentes del flujo actual de datos de entrada. Para descodificación de una palabra siguiente de código Huffman, es necesario extraer la palabra el código del flujo de datos en el registro Q 301. En la norma JPEG, esta palabra de código puede tener una longitud de hasta 16 bits. El par precedente de palabra de código-coeficiente puede tener una longitud de hasta 27 bits (o sea, 16 bits para la palabra de código y 11 bits para el coeficiente codificado). Así, en cualquier ciclo dado, es necesario tener un mínimo de 43 bits (16 bits + 27 bits) en el registro Q 301. Como cuarenta y tres es mayor que una longitud de palabra de datos de entrada de 32 bits, se ha determinado que es una implementación rápida poner en cola dos palabras de 32 bits.

Bits de información de cabeceras/marcadores/límites de bytes-carga

La información de cabeceras/marcadores y límites de bytes en el flujo de datos de entrada, entre las palabras de 32 bits, es detectada de una manera estándar como sería conocido en la técnica y separada como palabras de 4 bits en los buses 204, 202, respectivamente. Cada uno del detector 203 de longitud de secuencia limitada y del detector 205 de cabeceras/marcadores tiene entonces cada palabra respectiva de entrada de 4 bits ampliada a 32 bits por una inserción de siete ceros entre cada dos de los 4 bits en el hardware 303, 305 de "inserción de ceros", respectivamente.

En la realización ejemplar, marcadores definidos estándares JPEG de RECOMIENZO y FINAL DE IMAGEN son insertados dentro del flujo de datos JPEG comprimido en límites de bytes. Estos marcadores JPEG son detectados por un detector 205 de marcadores y 4 bits son extraídos para indicar en que límite de bytes en la palabra de entrada de 32 bits fue detectado el marcador. El propio marcador es eliminado del flujo de datos de entrada. Esta identificación de marcador de 4 bits es ampliada a 32 bits completos, para igualar a la palabra de datos de entrada, por la inserción de siete ceros entre cada dos de los 4 bits. La posición de bits de los bits de identificador de marcador se alinea así precisamente con el punto en la palabra de datos de entrada donde el marcador fue detectado y eliminado.

Una palabra de longitud de secuencia limitada de 32 bits, ampliada de modo similar, es cargada dentro de un registro R 307. La palabra ampliada de marcador de RECOMIENZO o FINAL DE IMAGEN, de 32 bits, es cargada dentro de un registro E 309. Ahora, los registros Q, R y E 301, 307, 309 pueden ser desplazados sincrónicamente tal que las posiciones de límites de bytes y de cabeceras/marcadores son conservadas en el mismo orden que fueron codificadas originalmente en los datos de entrada. O sea, cuando tienen lugar operaciones de desplazamiento subsiguientes explicadas en lo sucesivo, el registro Q 301 de flujo de datos de entrada, una palabra de límite de secuencia limitada en el registro R 307 y una palabra de marcador de RECOMIENZO o FINAL DE IMAGEN en el registro E 309 son desplazados conjuntamente y permanecen sincronizados entre sí.

Datos de entrada-descodificación

Una palabra posterior "siguiente" de datos de 32 bits del flujo de datos de entrada procedente del bus 200 es desplazada hacia la derecha (313) en una magnitud igual al número de bits de datos que estarán presentes en el registro 301 de datos de 75 bits después de que es procesada la operación "actual" de desplazamiento hacia la izquierda. Esto es como preparación para una operación O lógica por bits (315) dentro del registro Q 301. La operación de desplazamiento hacia la derecha (313) más la operación O lógica por bits (315) tiene el efecto neto de cargar la nueva palabra de datos de 32 bits en la posición apropiada inmediatamente a la derecha de todos los bits de datos actualmente en el registro Q 301.

Entonces, la palabra "siguiente" es sometida a la operación O lógica por bits (315) dentro del registro Q 301.

Entonces, el registro Q 301 llenado con 75 bits es desplazado hacia la izquierda en un registro 317 en el tamaño de la suma de la primera palabra de código más el coeficiente.

Entonces, son examinados los 27 bits más a la izquierda en el flujo de datos desplazados hacia la izquierda. De estos 27 bits, los 11 bits más a la izquierda en el registro 319 son el coeficiente del primer par de palabra de código- coeficiente. Los bits 63:48 contienen el código Huffman de longitud variable que según la norma JPEG puede tener una longitud de hasta 16 bits, suponiendo que el bit más a la izquierda del registro es el bit_{74} y el bit más a la derecha es el bit_{0}.

Descodificar el código Huffman usando la tabla de consulta produce la longitud de la palabra de código Huffman y del coeficiente sin signo combinados. En el ciclo siguiente de reloj, el registro Q 301 es desplazado hacia la izquierda en esta magnitud.

Después del desplazamiento hacia la izquierda, los 11 bits más a la izquierda del registro Q 301 contienen el coeficiente sin signo de longitud variable procedente del par anterior de palabra de código-coeficiente. El coeficiente sin signo de longitud variable puede tener cualquier longitud desde cero a once bits, el registro 327 de tamaño A de coeficiente contiene la longitud de este coeficiente. La unidad 331 de restaurar coeficiente toma el coeficiente sin signo y la longitud de coeficiente y produce el valor de coeficiente restaurado como una cantidad con signo de 12 bits extraída a la unidad 333 de codificación-descodificación Huffman.

Obsérvese que si el coeficiente es de longitud menor que 11 bits, la información está contenida en los bits más a la derecha de los 11 bits más a la izquierda del registro Q 301. Así, por medio de la lógica de Boole estándar, los datos de coeficiente codificado y de tamaño de coeficiente son usados entonces para restaurar el coeficiente codificado a una cantidad con signo de 12 bits (331) que es extraída (333) a la etapa siguiente del descodificador JPEG (no mostrado).

Los 16 bits más a la derecha son la palabra actual de código Huffman enviada a un generador 321 de direcciones para calcular la dirección para acceder a la tabla de consulta Huffman 323. La tabla 323 de consulta proporciona entonces la longitud 325 de secuencia de ceros (el número de ceros insertados en el coeficiente que deben ser reinsertados en los datos codificados) y el dato 327 de tamaño de coeficiente, así como la longitud total del par actual de palabra de código-coeficiente, igual a la cantidad siguiente de desplazamiento hacia la izquierda, 329. O sea, el número de posiciones para desplazar el registro 317 de desplazamiento hacia la izquierda para el ciclo siguiente de examen.

La tabla de consulta descodifica la palabra de código Huffman procedente del flujo de datos de entrada y proporciona tres valores:

(1) la longitud de secuencia de coeficientes nulos,

(2) la longitud del coeficiente codificado en longitud variable, y

(3) la suma de la longitud de la palabra de código Huffman y la longitud del coeficiente codificado.

El último valor es usado inmediatamente para desplazar hacia la izquierda el registro Q 301. La longitud del coeficiente codificado en longitud variable es usada para restaurar el coeficiente a su valor con signo de 12 bits. La información de longitud de secuencia es extraída directamente al descodificador 363 de longitud de secuencia retardada por el registro 325 de longitud A de secuencia y el registro 326 de longitud B de secuencia puesto que, en la implementación encauzada, la información de longitud de secuencia y de tamaño de coeficiente debe ser retardada para emparejarse con el coeficiente correcto procedente del registro 333 de codificación-descodificación Huffman.

Como los datos de entrada son de longitud variable, un registro 311 de bits válidos es usado para mantenerse al tanto de cuantos bits válidos están presentes en cada uno de los datos de registro Q 301, la información de límite de bytes del registro R 307 y la cabecera/marcador del registro E 309. Cuando bits son desplazados fuera de los registros 301, 307 y 309, el valor del desplazamiento (provisto por la tabla de consulta en cada ciclo) debe ser restado de la cuenta de bits válidos.

Cuando es cargada una nueva palabra de 32 bits de datos de entrada, entonces treinta y dos es sumado, en 312, a la cuenta de bits válidos. El control 314 de carga monitoriza el número de bits válidos de datos en el registro Q 301 y la cantidad de desplazamiento hacia la izquierda que será aplicado en el siguiente ciclo de reloj. Cuando el control 314 de carga calcula que el número de bits válidos de datos en el registro Q 301 será inferior a cuarenta y tres, emite una señal para cargar una palabra nueva de datos dentro del registro Q (o sea, si el número de bits válidos de datos menos la cantidad de desplazamiento es menor que cuarenta y tres, cargar una palabra nueva de datos).

Bits de información de cabeceras/marcadores/límites de bytes-descodificación

De la descripción anterior, ahora puede recordarse que palabras ampliadas de 32 bits de cabeceras/marcadores y de límites de bytes fueron creadas en el registro E 309 y el registro R 307, respectivamente, Estas cantidades de 32 bits son desplazadas hacia la derecha en los registros de desplazamiento 345, 343, respectivamente, y sometidas a la operación lógica O por bits en 347, 349, respectivamente, de la misma manera y en el mismo ciclo de reloj exactamente que su palabra aneja de datos de entrada en el registro Q 301. Entonces, cuando los datos están siendo desplazados hacia la izquierda (317), las palabras de cabeceras/marcadores de control y de límites de bytes son desplazados hacia la izquierda a través de los registros respectivos 351, 353 al mismo tiempo, manteniendo la posición relativa con ellos. Examinando los bits más a la izquierda de estos registros 351, 353, los ceros insertados en el registro E 309 y el registro R 307 pueden ser detectados (355) y desplazados hacia la izquierda (357) fuera del flujo de datos y las palabras de cabeceras/marcadores (356) y de límites de bytes (363) extraídas consiguientemente.

En resumen, la presente invención codifica así la secuencia, el tamaño del coeficiente y la suma del coeficiente y la longitud de palabra de código. Ese valor sale como la magnitud de desplazamiento que expresa la magnitud de desplazamiento para llegar a la palabra de código siguiente. Esto presenta una metodología más rápida para descodificar flujos de bits codificados Huffman JPEG puesto que la descodificación está ocurriendo cuando datos nuevos están siendo recibidos. Simultáneamente, los límites de bytes y las cabeceras/marcadores son rastreados apropiadamente por los circuitos 203, 205 imitando el manejo de datos en el descodificador Huffman 201. Una vez que un marcador de FINAL DE IMAGEN es detectado, el descodificador continúa procesando hasta que los datos recibidos son agotados.

La descripción anterior de la realización preferida de la presente invención ha sido presentada con fines de ilustración y descripción. No pretende ser exhaustiva o limitar la invención a la forma precisa descrita. Evidentemente, muchas modificaciones y variaciones serán evidentes para los practicantes expertos en esta técnica. De modo similar, cualesquier pasos de proceso descritos podrían ser intercambiables con otros pasos para conseguir el mismo resultado. La realización fue elegida y descrita para explicar óptimamente los principios de la invención y su aplicación práctica de modo óptimo para permitir de tal modo que otras personas expertas en la técnica comprendan la invención para diversas realizaciones y con diversas modificaciones como sean adecuadas para el uso particular considerado.

Claims

1. Un aparato de descodificador Huffman para descodificar un flujo de datos estándar JPEG (103, 105, 107) que tiene palabras (103) de código Huffman máximas de 16 bits en un formato de datos en pares de palabra de código Huffman-coeficiente, incluyendo además el flujo de datos códigos (107) de información de límites de bytes y códigos (107) de información de cabeceras/marcadores, incluyendo el aparato:

un bus (200) de entrada;

un registro (313) de desplazamiento hacia la derecha conectado al bus (200) de entrada para recibir al menos dos pares de palabra de código-coeficiente desde él;

medios (315) de operación O lógica por bits conectados a dicho registro (313) de desplazamiento hacia la derecha para recibir la salida de datos del registro de desplazamiento hacia la derecha desde él;

un registro (301) de datos de entrada conectado a los medios (315) de operación O lógica para recibir los datos de medios de operación O lógica de salida desde ellos;

un registro (317) de desplazamiento hacia la izquierda conectado al registro (301) de datos de entrada para recibir los datos de salida desde él;

medios (331, 333, 363) para extraer del registro (317) de desplazamiento hacia la izquierda una palabra de código y un coeficiente actuales para ser descodificados a partir de un par de palabra de código-coeficiente tal que son obtenidas una longitud de secuencia de coeficientes, una longitud de un coeficiente codificado en longitud variable y una suma de la longitud de una palabra de código más la longitud de un coeficiente codificado; y

medios de realimentación para desplazar hacia la izquierda los datos del registro (317) de desplazamiento hacia la izquierda en la magnitud de dicha suma para obtener una palabra y un coeficiente actuales siguientes para ser descodificados.

2. El aparato según la reivindicación 1, comprendiendo además:

medios (203) para recibir y rastrear los códigos de información de límites de bytes, incluyendo

medios (303) para rellenar los códigos de información de límites de bytes hasta la misma longitud en bits que el par de palabra de código-coeficiente, y

medios (353) para desplazar los códigos de información de límites de bytes sincrónicamente con los pares de palabra de código-coeficiente.

3. El aparato según la reivindicación 1, comprendiendo además:

medios (205) para recibir y rastrear los códigos de información de cabeceras/marcadores, incluyendo

medios (305) para rellenar los códigos de información de cabeceras/marcadores hasta la misma longitud en bits que el par de palabra de código-coeficiente, y

medios (351) para desplazar los códigos de información de cabeceras/marcadores sincrónicamente con los pares de palabra de código-coeficiente.

4. El aparato según la reivindicación 1, en el que el registro de entrada comprende:

un registro que tiene una capacidad de datos de al menos el doble de la anchura en bits del bus de entrada.

5. Un método para realizar la descodificación Huffman de un flujo de datos codificado, que tiene pares de palabra de código-coeficiente de una longitud máxima dada, recibiendo y almacenando conjuntos de datos de entrada en los que cada conjunto de datos tiene un número dado de bits, comprendiendo dicho método:

recibir pares secuenciales primero y segundo de palabra de código-coeficiente de dicho flujo de datos en un registro (313) de desplazamiento;

desplazar hacia la derecha dicho segundo par de palabra de código-coeficiente en el número de bits en dicho primer par de palabra de código-coeficiente;

realizar una operación O lógica sobre dicho primer par de palabra de código-coeficiente y dicho segundo par de palabra de código-coeficiente y almacenar el resultado en un registro (301) de datos que tiene una capacidad de datos de al menos el doble de dicha longitud máxima dada;

desplazar hacia la izquierda dicho resultado almacenado en un registro (317) de desplazamiento hacia la izquierda;

extraer un primer número predeterminado de bits más significativos del resultado almacenado en el registro (317) de desplazamiento hacia la izquierda como un valor de coeficiente y extraer un segundo número predeterminado de bits significativos del resultado almacenado en el registro (317) de desplazamiento hacia la izquierda como una palabra de código, con dichos números predeterminados primero y segundo siendo determinados con relación a dicha longitud máxima dada.

6. El método según la reivindicación 5, comprendiendo además el paso de:

repetir los pasos de la reivindicación 5 para cada par secuencial siguiente de palabra de código-coeficiente del flujo de datos hasta que el flujo es terminado.

7. El método según la reivindicación 5 o 6, comprendiendo además los pasos de:

recibir información de límites de bytes incrustada en el flujo de datos con un conjunto de datos anejos;

rellenar cada bit de la información de límites de bytes con una cadena de ceros entre los bits tal que la información de límites de bytes tiene una longitud en bits igual a la longitud del conjunto de datos de entrada;

desplazar hacia la derecha la información de límites de bytes simultáneamente con el conjunto de datos anejos;

extraer cada una de la cadena de ceros para reformular la información de límites de bytes en posición con el conjunto de datos descodificados.

8. El método según la reivindicación 5, 6 o 7, comprendiendo además los pasos de:

recibir la información de marcadores de control incrustada en el flujo de datos con un conjunto de datos anejos;

rellenar cada bit de la información de marcadores de control con una cadena de ceros entre los bits tal que la información de marcadores de control tiene una longitud en bits igual a la longitud del conjunto de datos de entrada;

desplazar hacia la derecha la información de marcadores de control simultáneamente con el conjunto de datos anejos;

extraer cada la de una cadena de ceros para reformular la información de marcadores de control en posición con el conjunto de datos descodificados.

9. El método según la reivindicación 5, 6, 7 o 8, comprendiendo además los pasos de:

en cada ciclo de reloj, desplazar los datos en el número total de bits en el par anterior de palabra de código-coeficiente.