Códigos de Golomb

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 em 1966. Os códigos de Golomb se aplicam a todo número inteiro e não negativo, e dependem de um parâmetro que deve ser previamente computado para que o código seja adequado aos dados. Desse parâmetro depreendemos mais duas grandezas e : das quais o código será construído. Da grandeza produzimos o prefixo, que será codificado em , enquanto a segunda parte será codificada com bits para os menores valores e bits para os maiores valores. Assim, para temos e como os valores possíveis de , que serão codificados como e ( tem bits e e têm ambos bits). Para teremos os valores e . A tabela abaixo ilustra os códigos de Golomb para e : 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 respeita a fórmula: para o código de Golomb será ótimo se for escolhido tal que