Saltar a contenido

Elias Gamma

Introducción

Elias Gamma es un tipo de codificación creada por Peter Elias en 1955. Igual que otras codificaciones, como Elias Delta, se basa en códigos unario y binario. El propósito de este código es el poder transformar la representación entera de un número a su forma binaria agregando una forma de decodificación del número al inicio del mismo.

Teoría

Con este código representamos un número \(N\) en una cantidad de \(2 \lfloor\lg N\rfloor + 1\) \(bits\). El espacio que ocupa lo podemos dividir en dos partes que usan \(\lfloor\lg N\rfloor + 1\) y $ \lfloor\lg N\rfloor$ bits:

  • La primera hace referencia a la representación unaria del número \(N\) en
  • binario, la segunda parte. De esta manera, se escriben \(\lfloor\lg N\rfloor\)
  • bits en 0, seguidos de un bit en \(1\).
  • La segunda parte representa la cantidad de bits utilizados por la parte binaria.

Implementación

Codificación

  1. Primero obtenemos \(k\), la mayor potencia de 2 que no puede representar a nuestro número \(N\), es decir, el truncamiento de \(k=\lfloor\lg N\rfloor\)
  2. Luego, comenzamos la codificación agregando \(k\) ceros concatenados con un 1, es decir, \(0^k1\)

  3. Por último, transformamos a su forma binaria el resto, \(x=N - 2^k\), y lo concatenamos a la codificación con un largo de \(k\) bits, obteniendo finalmente \(0^k1\{0,1\}^k\).

    Ejemplos

    N k 0k1 x codificación
    1 0 1 0 1
    3 1 01 1 011
    5 2 001 01 00101
    11 3 0001 011 0001011
    37 5 000001 00101 00000100101
    163 7 00000001 0100011 000000010100011

Decodificación

  1. Iniciamos leyendo los ceros hasta encontrar un 1, así obtenemos el valor \(k\)
  2. Luego, leemos los \(k\) siguientes bits, y los que serán interpretados en su forma decimal, \(x\)

  3. Por último, hacemos la siguiente suma \(2^k+x\) dándonos así el valor N

    Ejemplos

    Elias gamma 0k1 2k x N
    010 01 2 0 ➜ 0 2
    00111 001 4 11 ➜ 3 7
    0001101 0001 8 101 ➜ 5 13
    000011101 00001 16 1101 ➜ 13 29
    00000111101 000001 32 11101 ➜ 29 61
    0000001001001 0000001 64 001001 ➜ 9 73

Código

#include <iostream>
#include <vector>
#include "math.h"

using namespace std;

class eliasDelta
{
    private:

        //Codificación parte binaria
        unsigned* binary(unsigned n,unsigned k){

            unsigned* bin = new unsigned[k];

            for(int i = k-1; i >= 0; i--){

                bin[i] = (n >> (k-1-i)) & 1;
            }

            return bin;
        }

        //Codificación parte unaria
        unsigned* unary(unsigned k){

            unsigned* uni = new unsigned[k+1];

            for(int i = 0; i < k; i++){

                uni[i] = 0;
            }
            uni[k] = 1;

            return uni;
        }

        //Unión partes unaria y binaria
        unsigned* merge(unsigned* uni, unsigned* bin,unsigned k){

            unsigned* gamma = new unsigned[2*k +1];
            unsigned cont=0;

            for(int i = 0; i < k+1; i++){

                gamma[i] = uni[i];
            }
            for (int i = 0; i < k; i++) {

                gamma[i + k+1] = bin[i-cont];
            }

            return gamma;
        }

        //Decodificación 
        unsigned EGDecoding(unsigned* arry){

            unsigned i=0,k=0,num=0;

            while(arry[i] == 0){
                k++;
                i++;
            }

            while (i < 2*k+1){

                num = num << 1;

                if (arry[i]==1)
                {
                    num = num | 1;
                }
                i++;
            }
           return num;
        }

    public:

        unsigned* encoding(unsigned n){

            unsigned k = log2(n);
            unsigned* uni = unary(k);
            unsigned x = n - pow(2, k);
            unsigned *bin = binary(x, k);

            return merge(uni, bin, k);
        }

        unsigned decoding(unsigned* arry){

            return EGDecoding(arry);
        }
};

Referancias