Saltar a contenido

Rice Code

Los Rice Codes, desarrollado inicialmente por Robert Rice, y más tarde por Pen-Shu y Warner Miller, son un subconjunto específico de la familia de los Golomb Codes, en que el parámetro \(M\) es una potencia de 2. Esto los hace convenientes, ya que puede ser implementado eficientemente utilizando operaciones a nivel de bits.

Definición

Dada una constante \(M\), cualquier número \(N\) puede ser representado como un cociente \(Q\) y un resto \(R\), donde:

\[N = Q * M + R\]

Para codificar \(N\) en Rice Code, se debe hacer lo siguiente:

  1. Fijar el valor de M como \(2^K\), donde \(K\) es una constante fijada a conveniencia.

  2. Encontrar para \(N\): a. Cociente: Q = \(\lfloor(N/M)\rfloor\). b. Resto: \(R = N \bmod M\).

  3. Generar la palabra codificada. Tendrá el formato <cociente codificado><resto codificado>, donde: a. Cociente codificado es la codificación unaria del cociente b. Resto codificado es la codificacion binara de los últimos \(K\) bits de \(N\).

Para decodificar se siguen los mismos pasos pero de forma inversa:

  1. Decodificar la parte unaria (\(Q\)) contando la cantidad de 1's.

  2. Ignorar el primer 0.

  3. Interpretar los últimos \(K\) bits como binario.

Implementación

A continuación se presentan implementaciones en C++ de codificación y decodificación.

Encode:

/* Rice [en]coder
 * Demonstration code by Emil Mikulic, 2002.
 * http://purl.org/net/overload
 *
 * $Id: encode.c,v 1.2 2002/12/10 14:56:55 emikulic Exp $
 */
FILE *fp;
unsigned char buff = 0;
int filled = 0;

// almacena bits en un buffer
void put_bit(unsigned char b) { 
    buff = buff | ((b & 1) << filled);
    filled++;
}

void rice_code(unsigned char x, int k) {
    // m = 2^k
    int m = 1 << k; 
    // cociente
    int q = x / m; 
    int i;

    // ingresa los bits del cociente formando un codigo unario
    for (i=0; i<q; i++) { 
        put_bit(1); 
    }
    // bit diferenciador del unario
    put_bit(0); 

    // escribe el resto(ultimos k bits) como binario despues del cociente
    for (i=k-1; i>=0; i--) { 
        put_bit((x >> i) & 1 );
    }
}

Decode:

/* Rice [de]coder
 * Demonstration code by Emil Mikulic, 2002.
 * http://purl.org/net/overload
 *
 * $Id: decode.c,v 1.2 2002/12/10 14:56:22 emikulic Exp $
 */
FILE *fin, *fout;
unsigned char buff;
int done = 0, filled = 0;

// obtener bit mas significativo
unsigned char get_bit(void) {
    unsigned char tmp;
    // si no hay buffer retornar 0
    if (!filled) { 
        if (!fread(&buff, 1, 1, fin)) {
            done = 1;
            return 0;
        }
        filled = 8;
    }

    // obtiene un bit del buffer
    tmp = buff & 1;
    // correr el buffer un bit, para que esté listo para obtener el siguiente bit
    buff = buff >> 1; 
    // reajustar tamaño del buffer
    filled--; 

    return tmp; 
}

int main() {
    while (true) {
        int m = 1 << k;
        int q = 0;
        int x, i;

        // obtener cociente
        while (get_bit()) { 
            q++;
        }
        // numero decodificado sin el resto
        x = m * q; 

        // agregar el resto obteniendo los bits correspondientes
        for (i=k-1; i>=0; i--) { 
            x = x | (get_bit() << i);
        }
        // si no queda buffer, terminar
        if (done) 
            break;  
    }

    cout << x << endl;
}

Ejemplo

Los Rice Codes de los primeros 10 números, con \(K = 2\), es decir \(M = 4\), son:

Valor Cociente Resto Rice Code
0 0 0 0 00
1 0 1 0 01
2 0 2 0 10
3 0 3 0 11
4 1 0 10 00
5 1 1 10 01
6 1 2 10 10
7 1 3 10 11
8 2 0 110 00
9 2 1 110 01
10 2 2 110 10

Aplicaciones

La codificación Rice se han utilizado principalmente en compresión de audio, imágenes, video y electrocardiogramas. En la mayoría de los casos, los datos de entrada se transforman primero y luego los coeficientes de la transformada se cuantifican. Los coeficientes cuantificados suelen seguir una distribución geométrica, para la cual los Rice codes pueden proporcionar códigos cortos con longitudes cercanas a los códigos Huffman.

Referencias