Sistema y procedimiento para comprimir un flujo de datos de valores enteros.

Procedimiento para la codificación entrópica de datos de pares de tirada/valor de datos que corresponden a un flujo de datos de valores enteros

, en el que cada tirada se codifica en una de tres maneras, comprendiendo dicho procedimiento:

clasificar cada una de dichas tiradas en función de su longitud siendo o 1, corta o larga;

si la tirada es 1, seleccionar un primer código con una longitud de 1;

si la tirada se clasifica como corta, seleccionar un primer código con una primera longitud predeterminada, cada primer código de primera longitud predeterminada teniendo un preámbulo para distinguir las otras clasificaciones de tirada, y teniendo un valor en función de la longitud de la tirada;

si la tirada se clasifica como larga, seleccionar un primer código con una segunda longitud predeterminada, cada primer código de segunda longitud predeterminada teni

endo un preámbulo para distinguir las otras clasificaciones de tirada, y teniendo un valor en función de la longitud de la tirada; y emitir el primer código seleccionado a un canal, en el que la primera longitud predeterminada es n + 1 bits, el primer código con la primera longitud predeterminada se selecciona a partir de una primera tabla de código, el primer código con la primera longitud predeterminada tiene el preámbulo para el primer bit y cuyo valor para los n bits restantes se basa en la duración de la tirada, la segunda longitud predeterminada es n + 1 + M bits, el primer código con la segunda longitud predeterminada se selecciona a partir de una segunda tabla de códigos, el primer código con la segunda longitud predeterminada teniendo el preámbulo para los primeros n + 1 bits y cuyo valor para los M bits restantes se basa en la longitud de la tirada.

Tipo: Patente Internacional (Tratado de Cooperación de Patentes). Resumen de patente/invención. Número de Solicitud: PCT/US2009/063526.

Solicitante: APPLE INC..

Nacionalidad solicitante: Estados Unidos de América.

Dirección: 1 INFINITE LOOP CUPERTINO CA 95014-2084 ESTADOS UNIDOS DE AMERICA.

Inventor/es: OSLICK,MITCHELL.

Fecha de Publicación: .

Clasificación Internacional de Patentes:

  • SECCION H — ELECTRICIDAD > CIRCUITOS ELECTRONICOS BASICOS > CODIFICACION, DECODIFICACION O CONVERSION DE CODIGO,... > Conversión de un código, en el cual la información... > H03M7/40 (Conversión en, o a partir de códigos la longitud variable, p. ej. código Shanno-Fano, código Huffman, código Morse)
  • SECCION H — ELECTRICIDAD > CIRCUITOS ELECTRONICOS BASICOS > CODIFICACION, DECODIFICACION O CONVERSION DE CODIGO,... > Conversión de un código, en el cual la información... > H03M7/46 (Conversión en o a partir de códigos de coordenada diferencial, es decir, por representación del número de dígitos consecutivos o grupos de dígitos del mismo tipo con ayuda de una palabra código y de un dígito representativo de este tipo)

PDF original: ES-2546542_T3.pdf

 

google+ twitter facebook

Fragmento de la descripción:

Sistema y procedimiento para comprimir un flujo de datos de valores enteros.

ANTECEDENTES 5

Se conocen varios esquemas de codificación para codificar flujos de bits de valores enteros, en los cuales los flujos de bits pueden representar, por ejemplo, vídeos, imágenes, y demás. Los esquemas de codificación conocidos implican generalmente la codificación de longitud de tirada, codificación de longitud variable, codificación diferencial, y diversas combinaciones de los mismos. 10

Se sabe que la codificación de longitud de tirada, si bien es útil para la compresión de datos que presenta una uniformidad significativa, es generalmente ineficaz donde los valores de datos son propensos a diferir de un al siguiente. En esta segunda situación, es común entre los esquemas de compresión conocidos el conmutar de forma adaptativa entre la codificación de longitud de tirada y algún otro tipo de codificación, en el que la conmutación 15 generalmente se maneja en el decodificador por información anexa asociada con el flujo de bits, o por cálculo; esto o bien reduce la eficiencia de compresión o aumenta la carga computacional, respectivamente.

El documento EP 1 004 975 A2 divulga un conjunto de palabras de código de compresión de ocho bits que se utilizan en el comienzo de una tirada de datos que comprende un recuento de píxeles y uno o más valores de color, 20 los primeros cuatro bits de la primera palabra siendo utilizados para especificar el formato de los bytes en la siguiente secuencia de datos y si los siguientes píxeles se van a imprimir como la superposición o como el fondo, y los últimos cuatro bits siendo utilizados para especificar sugerencias de impresión.

Es común entre los esquemas de compresión que utilizan codificación tanto de longitud de tirada como diferencial, 25 llevar a cabo la codificación diferencial antes de la codificación de longitud de tirada, cuyo orden requiere que el codificador calcule una diferencia, y el decodificador calcule una suma (es decir, reconstruir el valor de datos) para cada valor de datos en el flujo de bits.

Por lo tanto, es deseable usar un esquema de codificación que pueda eliminar o por lo menos mitigar estas 30 limitaciones conocidas.

BREVE DESCRIPCIÓN DE LOS DIBUJOS

La FIG. 1 ilustra un procedimiento para codificar un flujo de datos de valores enteros de acuerdo con una realización de la presente invención.

La FIG. 2 ilustra un procedimiento de codificación de una lista de pares de tirada/valor de datos de acuerdo con una realización de la presente invención. 40

La FIG. 3 ilustra un flujo de datos de valores enteros a modo de ejemplo, y sus tiradas asociadas.

La FIG. 4 ilustra un sistema de codificador-decodificador de acuerdo con una realización de la presente invención. 45

DESCRIPCIÓN DETALLADA

Las realizaciones de la presente invención reducen el tamaño y la complejidad de los flujos de bits asociados a datos codificados mediante el uso de un nuevo esquema de compresión. Un codificador entrópico recibe una lista de 50 pares de tirada/valor de datos y codifica entrópicamente por separado las tiradas y los valores de datos, seleccionando sus palabras de código según longitud y magnitud, respectivamente, y concatena los pares de palabras de código resultantes - la palabra de código de valor de datos primero - en un flujo de bits codificados. El esquema de codificación reduce el tamaño y la complejidad de un flujo de bits codificados, cuyo flujo de bits puede representar imágenes, vídeos, y demás. Por lo tanto, el flujo de bits puede ser transmitido utilizando menos ancho 55 de banda y se puede disminuir la carga computacional tanto en el codificador como en el decodificador.

La FIG. 1 ilustra un procedimiento de codificar un flujo de bits de acuerdo con una realización de la presente invención. Según la realización, el procedimiento puede escanear un conjunto de valores de datos en un sentido de escaneo predeterminado (cuadro 100) . El procedimiento puede convertir valores de datos del conjunto en una 60 secuencia de pares de tirada/valor de datos (cuadro 110) . En el bloque 120, el procedimiento puede seleccionar una palabra de código en función de un valor de una tirada. Del mismo modo, en el cuadro 130, el procedimiento puede seleccionar una palabra de código en función de un valor de un valor de datos. El procedimiento puede realizar ya sea la etapa 120 o la etapa 130 o ambos. El procedimiento puede concatenar los datos codificados de tirada/valor de datos en parejas de datos codificados (cuadro 140) . A partir de entonces, los datos podrán ser procesados adicionalmente para transmisión.

Más específicamente, en el bloque 100, el procedimiento puede escanear un conjunto de datos de origen de acuerdo con un sentido de escaneo, cuyos datos de origen representan, por ejemplo, una imagen, un vídeo, y 5 demás. El procedimiento puede acomodar conjuntos de datos de una variedad de tamaños y configuraciones. Se apreciará que los conjuntos multi-dimensionales de números enteros pueden ser considerados como un conjunto lineal cuando se consideran según una dirección de escaneo y, por lo tanto, la presente discusión se dirige a un caso de conjunto lineal.

10 En el bloque 110, el conjunto unidimensional de valores de datos se puede convertir, utilizando la codificación por longitud de tirada, en una lista de pares de tirada de tirada/valor de datos, donde un número entero (comúnmente, el primer número entero) en el par es la longitud de la tirada, y otro número entero (comúnmente, el segundo número entero) es el valor de los datos que comprenden la tirada correspondiente. Por ejemplo, y como se muestra en la FIG. 3, si el conjunto unidimensional consta de 10 elementos - {0, 0, 0, 3, 3, 2, 2, 2, 2, 2} - esos 10 elementos se 15 convertirían en los siguientes pares: { (3, 0) , (2, 3) , (5, 2) }. Los pares resultantes indican que el conjunto original constaba de tres valores iguales a 0, dos valores iguales a 3, y cinco valores iguales a 2, y en ese orden.

En una realización, la lista resultante de pares de tirada/valor de datos se puede codificar en diferencia, en el bloque 110, en una lista de pares de diferencia de tirada/valor de datos. Volviendo al ejemplo del conjunto de 10 elementos 20 utilizado anteriormente, la lista resultante de pares de diferencia de tirada/valor de datos consta de { (3, +1) , (2, +3) , (5, -1) }, en el que [0 - (-1) = 1], [3 - 0, = +3], y [2 - 3 = -1]. En circunstancias normales la diferencia de valor de datos no será cero, ya que ello implicaría una continuación de la tirada anterior; mediante el tratamiento del valor de tirada anterior de la tirada inicial como -1 (como se muestra en el ejemplo anterior) , se puede garantizar una diferencia de valor de datos distinta de cero (a menos que una tirada se divide en sub-tiradas, como se detalla en este 25 documento) .

Al hacer la codificación por longitud de tirada antes de la codificación de por diferencia, se tiene que calcular una diferencia (codificador) o suma (decodificador) solamente una vez por tirada, en lugar de una vez por cada valor de datos. Esta distinción de orden puede ser especialmente valiosa en el decodificador, donde no sólo reduce la 30 cantidad de cálculo requerido, sino que también elimina cualquier secuencia asociada, permitiendo que varios de los valores de los datos idénticos de una tirada sean emitidos simultáneamente.

Tal como descrito anteriormente, los principios de la presente invención encuentran aplicación tanto con valores de datos diferenciales como con valores de datos no diferenciales. Por lo tanto, a menos que se especifique a 35 continuación, la discusión que sigue se refiere a los "valores de datos" en un sentido genérico,... [Seguir leyendo]

 


Reivindicaciones:

1. Procedimiento para la codificación entrópica de datos de pares de tirada/valor de datos que corresponden a un flujo de datos de valores enteros, en el que cada tirada se codifica en una de tres maneras, comprendiendo dicho 5 procedimiento:

clasificar cada una de dichas tiradas en función de su longitud siendo o 1, corta o larga;

si la tirada es 1, seleccionar un primer código con una longitud de 1; 10

si la tirada se clasifica como corta, seleccionar un primer código con una primera longitud predeterminada, cada primer código de primera longitud predeterminada teniendo un preámbulo para distinguir las otras clasificaciones de tirada, y teniendo un valor en función de la longitud de la tirada;

si la tirada se clasifica como larga, seleccionar un primer código con una segunda longitud predeterminada, cada primer código de segunda longitud predeterminada teniendo un preámbulo para distinguir las otras clasificaciones de tirada, y teniendo un valor en función de la longitud de la tirada; y

emitir el primer código seleccionado a un canal, en el que la primera longitud predeterminada es n + 1 bits, el 20 primer código con la primera longitud predeterminada se selecciona a partir de una primera tabla de código, el primer código con la primera longitud predeterminada tiene el preámbulo para el primer bit y cuyo valor para los n bits restantes se basa en la duración de la tirada,

la segunda longitud predeterminada es n + 1 + M bits, el primer código con la segunda longitud 25 predeterminada se selecciona a partir de una segunda tabla de códigos, el primer código con la segunda longitud predeterminada teniendo el preámbulo para los primeros n + 1 bits y cuyo valor para los M bits restantes se basa en la longitud de la tirada.

2. El procedimiento de la reivindicación 1, en el que la longitud de la tirada corta es mayor que 1 y menor o igual a 30 2n, y la longitud de la tirada larga es mayor que 2n.

3. El procedimiento de la reivindicación 1 en el que:

para tiradas clasificadas como cortas, el preámbulo del primer código es un bit '0' y el valor de los n bits 35 restantes es el código binario para uno menos la longitud de la tirada; y

para tiradas clasificadas como largas, el preámbulo del primer código es n + 1 bits '0' y el valor de los M bits restantes es el código binario para uno menos la longitud de la tirada.

4. El procedimiento de la reivindicación 1 que comprende además dividir una tirada en dos o más sub-tiradas cuando la longitud de una tirada es mayor que 2M, en el que:

la longitud de cada una de las sub-tiradas es inferior o igual a 2M;

el valor de datos asociado con la primera sub-tirada es igual al valor de datos asociado con la tirada; y 45

el valor de datos asociado a cada sub-tirada después de la primera sub-tirada es cero.

5. El procedimiento de la reivindicación 1 que comprende además:

clasificar cada valor de datos en función de su magnitud; 50

si el valor de datos se clasifica como pequeño, seleccionar un segundo código que comprende k + 2 bits a partir de una tercera tabla de códigos, el segundo código seleccionado teniendo un preámbulo predeterminado para el primer bit y cuyo valor para los k + 1 bits restantes se basa en el valor de datos;

si el valor de datos se clasifica como grande, seleccionar un segundo código que comprende N + 1 bits a 55 partir de una cuarta tabla de códigos, el segundo código seleccionado teniendo un preámbulo predeterminado para el primer bit y cuyo valor para los N bits restantes se basa en el valor de datos y en N; y

emitir el segundo código seleccionado al canal.

6. Un sistema para la codificación entrópica de una lista de datos de pares de tirada/valor de datos correspondientes a un flujo de datos de valores enteros, en el que cada tirada se codifica de una de tres maneras, en el que el sistema está configurado para llevar a cabo el procedimiento de acuerdo con cualquiera de las reivindicaciones 1 a 5.

7. Un medio legible por ordenador codificado con un conjunto de instrucciones que, cuando se realiza por un ordenador, lleva a cabo el procedimiento de cualquiera de las reivindicaciones 1 a 5.