Códigos de Golomb

Códigos de Golomb-Rice pode ser pensado como códigos que indicam um número da posição do compartimento ( q ) {\displaystyle (q)} , e o deslocamento no interior do comprimento ( r ) {\displaystyle (r)} . A figura acima mostra a posição q {\displaystyle q} e deslocamento r {\displaystyle r} para a codificação de N {\displaystyle N} número inteiro usando parâmetro de Golomb-Rice M {\displaystyle M} .

Os códigos de Golomb, ou ainda a codificação de Golomb, é um conjunto de códigos livres de prefixo que podem ser utilizados na compressão de dados em substituição ao código de huffman, apresentando resultados ótimos para determinadas distribuições de probabilidade dos símbolos codificados. O método foi desenvolvido por Solomon W. Golomb em 1966.[1][2][3]

Os códigos de Golomb se aplicam a todo número n {\displaystyle n} inteiro e não negativo, e dependem de um parâmetro b {\displaystyle b} que deve ser previamente computado para que o código seja adequado aos dados. Desse parâmetro depreendemos mais duas grandezas q {\displaystyle q} e r {\displaystyle r} :

q = ⌊ n − 1 b ⌋ , r = n − q b − 1 {\displaystyle q=\left\lfloor {\frac {n-1}{b}}\right\rfloor ,r=n-qb-1}

das quais o código será construído. Da grandeza q {\displaystyle q} produzimos o prefixo, que será q + 1 {\displaystyle q+1} codificado em unário, enquanto a segunda parte será codificada com ⌊ l o g 2 b ⌋ {\displaystyle \lfloor log_{2}b\rfloor } bits para os menores valores e ⌈ l o g 2 b ⌉ {\displaystyle \lceil log_{2}b\rceil } bits para os maiores valores. Assim, para b = 3 {\displaystyle b=3} temos 1 ,   2 {\displaystyle 1,~2} e 3 {\displaystyle 3} como os valores possíveis de r {\displaystyle r} , que serão codificados como 0 ,   10 {\displaystyle 0,~10} e 11 {\displaystyle 11} ( 0 {\displaystyle 0} tem ⌊ l o g 2 3 ⌋ = 1 {\displaystyle \lfloor log_{2}3\rfloor =1} bits e 10 {\displaystyle 10} e 11 {\displaystyle 11} têm ambos ⌈ l o g 2 3 ⌉ = 2 {\displaystyle \lceil log_{2}3\rceil =2} bits). Para b = 5 {\displaystyle b=5} teremos os valores 00 ,   01 ,   100 ,   101 {\displaystyle 00,~01,~100,~101} e 110 {\displaystyle 110} . A tabela abaixo ilustra os códigos de Golomb para b = 3 {\displaystyle b=3} e b = 5 {\displaystyle b=5} :

n 1 2 3 4 5 6 7 8 9 10
b = 3 {\displaystyle b=3} 0/0 0/10 0/11 10/0 10/10 10/11 110/0 110/10 110/11 1110/0
b = 5 {\displaystyle b=5} 0/00 0/01 0/100 0/101 10/110 10/00 10/01 10/100 10/101 110/110

Com os dados apropriados, os códigos de Golomb podem ser mais fáceis de gerar e tão eficientes quanto os códigos de Huffman. Pode ser demonstrado que para dados onde a probabilidade de cada símbolo n {\displaystyle n} respeita a fórmula: P ( n ) = ( 1 − p ) n − 1 p {\displaystyle P(n)=(1-p)^{n-1}p} para 0 ≤ p ≤ 1 {\displaystyle 0\leq p\leq 1} o código de Golomb será ótimo se b {\displaystyle b} for escolhido tal que

( 1 − p ) b + ( 1 − p ) b + 1 ≤ 1 < ( 1 − p ) b − 1 + ( 1 − p ) b . {\displaystyle (1-p)^{b}+(1-p)^{b+1}\leq 1<(1-p)^{b-1}+(1-p)^{b}.} SALOMON, David (2000), Data Compression, páginas 53 e 54.

Aplicações

O padrão JPEG-LS de compressão de imagens sem perdas utiliza os códigos de Golomb para representar os valores de diferença entre as previsões e os valores reais dos pixels.

Ver também

Notas e referências

  1. ↑ Golomb, S. W. (1966). «Run-Length Encodings». IEEE Transactions on Information Theory. IT-12(3): 399-401  in SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer. ISBN 0-387-95045-1 
  2. ↑ Introdução à Teoria da Informaçâo
  3. ↑ Codificador Distribuído de Vídeo com Complexidade Variável a Partir de Codificação em Resolução Espacial Mista

Bibliografia

  1. ↑ SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer. ISBN 0-387-95045-1 
Ícone de esboço Este artigo sobre informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.
  • v
  • d
  • e
  • Portal da matemática
  • Portal das tecnologias de informação