Probabilidade Condicional, Huffman E RLE

Arquivo com dados

O arquivo gerado é um vetor de 1000 elementos, cada elemento assume apenas 2 valores, 127 ou 128.

A estrutura do algoritmo segue a lógica do grafo da Figura 1 1.

Figura 1 1: Grafo da lógica de randomização dos elementos.

Para criar este vetor foi utilizado parte do código disponibilizado pelo professor, “aula5_GeraRandomCondicional”, que gera um vetor uns e zeros aleatórios seguindo a lógica do grafo acima, a única modificação foi adicionar 127 a todos elementos.

Bitplanes

O vetor obtido agora é formado por elementos que em decimal valem 127 e 128. Estes valores podem ser representados em binário por elementos de 8 bits, respectivamente 01111111 e 10000000.

Para separar em bitplanes, utilizou-se a mesma técnica usada na Atividade_N1, através da função bitget() do Matlab.

Através dela obtivemos os 8 bitplanes do vetor.

Corridas de 0s e 1s

Utilizando os bitplanes obtidos anteriormente e a função freq(), também usada na Atividade_NP1, obtemos os dados necessários para fazer a análise estatística das corridas.

Abaixo seguem os histogramas obtidos, o primeiro é o equivalente para cada um dos bitplanes desde o bit menos significativo até o bit 7, ou seja, todos os bitplanes menos significativos antes do 8º apresentam as mesmas quantidades de tuplas, apenas o 8º bitplane apresenta quantidade diferente das tuplas.

Figura 3 1: Histograma das corridas presentes nos bitplanes 1 ao 7.

Figura 3 2histograma das corridas presentes no bitplane 8.

Realizando o cálculo da entropia de cada bitplane, concluímos que ela é igual para todos os bitplanes, seu valor é de 3,7088.

Podemos então representar os bitplanes com 4 bits apenas.

Codificação RLE

Após realizarmos a análise estatitica, concluímos que a codificação RLE é viável, visto o elevado número de corridas de 0s e 1s.

Utilizando os algoritmos tabela_RLE_prob() e codifica_RLE obtemos versões dos bitplanes codificadas em RLE, onde cada tipo de corrida é representado por um símbolo, neste caso um valor decimal.

Após realizar a codificação, os arquivos de 1000 elementos passaram a ter somente 322 elementos cada.

Portanto obtivemos uma redução de 67,8% (100%- 322/1000.100%).

É importante observar que esta redução é resultante apenas do número de elementos do vetor.

Huffman

Para codificar com Huffman eliminamos os 4 bitplanes menos significativos, ficando apenas com os 8 mais significativos.

Como percebeu-se através da análise