Códigos Golomb

Los códigos de Golomb son una familia de códigos de entropía . El código Golomb también puede significar uno de los representantes de esta familia.

Considere una fuente que genera independientemente números enteros no negativos con probabilidades , donde es un número positivo arbitrario que no excede 1, es decir, una fuente descrita por una distribución geométrica . Si un entero positivo es tal que $i$ ${\displaystyle P(i)=(1-p)p^{i))$ $pags$ $metro$

p^{m}={\frac{1}{2))

entonces el código carácter por carácter óptimo (es decir, el código que asocia cada carácter codificado con una determinada palabra clave) para tal fuente será un código construido de acuerdo con el procedimiento propuesto por Solomon Golomb , según el cual, para cualquier número codificado , con una palabra de código conocida, una notación unaria de un número y un codificado de acuerdo con el procedimiento descrito a continuación, el resto de la división : $norte$ $metro$ $q=\left[{\frac {n}{m}}\right]$ $r$ ${\frac{n}{m))$

Si es una potencia de 2, entonces el código restante es una representación binaria del número , colocado en bits. $metro$ $r$ $\log_2(m)$
Si no es una potencia de 2, se calcula el número . Más lejos: $metro$ $b=\lceil \log _{2}(m)\rceil$

Si , el código restante es una representación binaria del número , colocado en bits,

r<2^{b}-m

r

{\ estilo de visualización b-1}

de lo contrario, el resto se codifica mediante la notación binaria del número , colocado en bits.

r

r+2^{b}-m

b

Más tarde, R. Gallagher y D. Van Voorhees demostraron que el código propuesto por Golomb es óptimo no solo para un conjunto discreto de valores que satisfacen el criterio anterior, sino también para cualquiera en el que se cumpla la doble desigualdad . $pags$ $pags$

{\displaystyle p^{m}+p^{m+1}\leq 1<p^{m}+p^{m-1))

donde es un entero positivo. Como para cualquier siempre hay como máximo un valor que satisface la desigualdad anterior, el procedimiento de codificación de una fuente geométrica propuesto por S. Golomb resulta óptimo para cualquier valor de . $metro$ $pags$ $metro$ $pags$

Una versión extremadamente fácil de implementar, pero no siempre óptima, del código Golomb en el caso de que sea una potencia de 2 se denomina código Rice. $metro$

Ejemplo

Vamos , se requiere codificar el número . ${\ estilo de visualización p = 0,85}$ ${\ estilo de visualización n = 13}$

El valor que satisface la doble desigualdad de Gallagher-Van Voorhees . $metro=4$

De acuerdo con el procedimiento de codificación descrito anteriormente, la palabra clave correspondiente al número codificado 13 se construye como una representación unaria del cociente n/m:

q=\left[{\frac {n}{m}}\right]=\left[{\frac {13}{4}}\right]=3

(código unario , es decir, q ceros seguidos de uno), ${\ estilo de visualización 0001}$

y resto codificado

{\ estilo de visualización r = 1}

(código , es decir, el propio resto, escrito en bits). ${\ estilo de visualización 01}$ $\lceil \log _{2}(m)\rceil$

Palabra de código resultante

{\ estilo de visualización 0001 | 01}

Véase también

código Golomb exponencial

Enlaces

SO Golomb. Codificaciones de longitud de ejecución // IEEE Trans. inf. teor. - 1966. - Nº 3, IT-12 . - Pág. 399-401.
R. G. Gallager, D. C. Van Voorhis. Códigos fuente óptimos para alfabetos enteros distribuidos geométricamente // IEEE Trans. inf. teor. - 1975. - Nº 2, IT-21 . - Pág. 228-230.
R. R. Rice, J. R. Plaunt. Codificación adaptativa de longitud variable para la compresión eficiente de datos de televisión de naves espaciales // IEEE Trans. en Comunidad. - 1971. - vol. 16(9). - Pág. 889-897.
2.3 Códigos de Golomb / Amir Said, sobre la determinación de códigos de prefijo parametrizados óptimos para la codificación de entropía adaptativa. HPL-2006-74

métodos de compresión

Teoría

Información	Propio Mutual entropía Entropía condicional Complejidad Redundancia
Unidades	Un poco natural Picar Hartley Fórmula Hartley

sin pérdidas

Compresión de entropía	Sistemas numéricos asimétricos Algoritmo de Huffman Algoritmo de Huffman adaptativo Algoritmo de Shannon-Fano Algoritmo de Shannon Codificación aritmética ( intervalo ) Códigos Golomb Delta código universal Elías fibonacci
Métodos de diccionario	RLE Desinflar LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zestándar )
Otro	RLE CTW BWT MTF ppm DMC

Audio

Teoría	Circunvolución PCM alias Muestreo Teorema de Kotelnikov
Métodos	LPC LAR LSP WLPC CELP ACELP Una ley ley μ ADPCM MDCT Transformada de Fourier modelo psicoacústico
Otro	Compresor de sonido Compresión de voz Codificación de banda

Imágenes

Términos	espacio de color píxel Submuestreo de saturación Artefactos de compresión
Métodos	RLE DPCM fractales ondícula EZW ALCOHOL LP Deberes PCL
Otro	tasa de bits Imagen de prueba estándar PSNR cuantización

Video

Términos	Características del vídeo Cuadro Tipos de cuadros Calidad de video
Métodos	Compensación de movimiento Deberes cuantización ondícula
Otro	Códec de vídeo Tasa de teoría de la distorsión CBR ABR VBR