Codificação de fonte por intercalação

Prévia do material em texto

Apêndice A
CODIFICAÇÃO DE FONTE POR INTERCALAÇÃO
Trabalho de Conclusão de Curso
Engenharia de Telecomunicações
Nadja Juliana da Silva Lima
Orientador: Prof. Márcio José de Carvalho Lima
Universidade de Pernambuco
Escola Politécnica de Pernambuco
Graduação em Engenharia de Telecomunicações
NADJA JULIANA DA SILVA LIMA
CODIFICAÇÃO DE FONTE POR INTERCALAÇÃO
Monografia apresentada como requisito parcial para obtenção do diploma de Bacharel em Engenharia de Telecomunicações pela Escola Politécnica de Pernambuco – Universidade de Pernambuco.
Recife, Junho de 2013.
A minha avó, que acreditou que o sonho era possível.
Agradecimentos
“Eu não me orgulho de ser forte ou capaz. Se eu não acreditar em mim e nos meus sonhos nada mais faz sentido. Então, mesmo com dúvidas, tento. Se der errado tento de novo, até cansar. Porque a vida é uma tentativa diária. 
Me orgulho de ser humana, de ter a capacidade de me emocionar, me doar, chorar, sentir e, também, fraquejar. Me orgulho por ter entendido que não faço nada, nada, nada sozinha. É que a gente precisa, sim, do outro pra viver. E é aí que exercitamos uma das coisas mais bonitas dessa vida: a humildade.” (Clarissa Corrêa)
Inicialmente, agradeço a Deus.
Agradeço a Bruno Silva pela força e companheirismo diários, pelo ombro amigo nas dificuldades e pelos aplausos a cada acerto; a minha família, que é o meu porto seguro; Aos meus amigos que estiveram comigo durante esses anos mesmo que a distância, mas sempre tiveram uma palavra amiga quando precisei; Às minhas madrinhas Giciléa Brito e Elisabeth Carvalho pelo apoio durante a minha vida, sem esse apoio grande parte disso não seria possível; Ao professor Márcio Lima pela orientação neste trabalho, por ter acreditado que o trabalho poderia ser feito e por toda sua dedicação. Agradeço principalmente a minha Avó Josefa Juliana (In Memoriam) por acreditar em mim, nos meus sonhos, acreditar que era possível, por todo o investimento que ela fez na minha educação e sem ela nada disso seria possível, e onde quer que ela esteja sei que está feliz por mim e por tudo que conquistei. A todos, muito obrigada!
Nadja Juliana da Silva Lima
Resumo
Uma nova de codificação de entropia é estudada. Este trabalho aborda problema da compressão de dados e descreve algumas técnicas de compressão conhecidas, objetivando compará-las à nova técnica estudada. Será realizado o estudo de um novo codificador de entropia baseado no algoritmo de classificação por intercalação (do inglês, Sorting by Merging Coding), denominado Codificação de Fonte com Intercalação (CFI – do inglês, Merge Source Coding). O CFI é comparado com o codificador Aritmético considerando os parâmetros: redundância, tempo total de execução e tempo de execução por símbolo. Para essa comparação são utilizadas algumas das principais coleções de arquivos padrão na avaliação de desempenho de algoritmos de compressão: Calgary Corpus, Canterburry Corpus, Artificial Corpus, Large Corpus, Miscellaneous Corpus, CCITT Corpus. O Codificador de Fonte com Intercalação codifica cada símbolo, independentemente da fonte e com baixa redundância. Essa nova abordagem é estática, e necessita armazenar o número de ocorrências de cada símbolo antes de codificar as posições, porém pode ser adaptável no sentido de variar o comprimento da sequência codificada e é também universal. Será estudado em fontes binárias, podendo ser aplicada para codificar fontes D-árias e fontes de Markov.
Abstract
A new entropy coding is studied. This paper addresses problem of data compression and describes some known compression techniques, aiming to compare them to the new technique studied. There will be the study of a new entropy encoder algorithm based on merge sort (Sorting by Merging Coding), called Source Coding with Interleaving (CFI). The CFI is compared with the encoder Arithmetic considering parameters: redundancy, total execution time and execution time per symbol. Used for this comparison are some of the major collections of files in standard performance evaluation of compression algorithms: Calgary Corpus, Canterbury Corpus, Artificial Corpus, Large Corpus, Corpus Miscellaneous, CCITT Corpus. Source Encoder encodes each symbol with Override, regardless of source and low redundancy. This new approach is static and need to store the number of occurrences of each symbol before encoding positions, but can be adapted in order to vary the length of the code sequence and is also universal. Sources will be studied in binary and can be applied to encode D-ary sources and Markov sources.
Sumário
	
Índice de Figuras
Figura 1: Variação da Entropia H(P) em função da probabilidade P.	13
Figura 2: Diagrama de estados para fonte de Markov de segunda ordem.	16
Figura 3: Árvore do exemplo de código de Huffman Binário.	20
Figura 4: Representação gráfica da codificação aritmética com expansão após cada iteração descrita no Exemplo 8.	25
Figura 5: Sequência S de comprimento |S| = 42 separada em dois conjuntos A e B, de acordo com os respectivos símbolos emitidos por uma fonte binária.	34
Índice de Tabelas
Tabela 1: Exemplo de códigos binários.	9
Tabela 2: Codificação binária dos dígitos decimais.	11
Tabela 3: Probabilidade de símbolos de uma fonte qualquer.	14
Tabela 4: Exemplo de um código de comprimento médio l = 5.	17
Tabela 5: Exemplo construção código Shannon-Fano.	22
Tabela 6: Exemplo de intercalação binária (KNUTH, 1998).	32
Tabela 7: Arquivos da Base de Dados Calgary Corpus. Entropia expressa em bits/símbolo o Total Teórico em bits, o Comprimento Total em bits, a Redundância em bits/símbolo, o Tempo Total em milissegundos e o Tempo por Símbolo em nanossegundos/símbolo.	42
Tabela 8: Arquivos da Base de Dados Canterbury Corpus. Entropia expressa em bits/símbolo, o Total Teórico em bits, o Comprimento Total em bits, a Redundância em bits/símbolo, o Tempo Total em milissegundos e o Tempo por Símbolo em nanossegundos/símbolo.	45
Tabela 9: Arquivos da Base de Dados Artificial Corpus. Entropia expressa em bits/símbolo, o Total Teórico em bits, o Comprimento Total em bits, a Redundância em bits/símbolo, o Tempo Total em milissegundos e o Tempo por Símbolo em nanossegundos/símbolo.	46
Tabela 10: Arquivos da Base de Dados Miscellaneous Corpus. Entropia expressa em bits/símbolo, o Total Teórico em bits, o Comprimento Total em bits, a Redundância em bits/símbolo, o Tempo Total em milissegundos e o Tempo por símbolo em nanossegundos/símbolo.	47
Tabela 11: Arquivos da Base de Dados Large Corpus. Entropia expressa em bits/símbolo, o Total Teórico em bits, o Comprimento Total em bits, a Redundância em bits/símbolo, o Tempo Total em milissegundos e o Tempo por Símbolo em nanossegundos/símbolo.	47
Tabela 12: Arquivos da Base de Dados CCITT Corpus. Entropia expressa em bits/símbolo, o Total Teórico em bits, o Comprimento Total em bits, a Redundância em bits/símbolo, o Tempo Total em milissegundos e o Tempo por símbolo em nanossegundos/símbolo.	48
Tabela 13: Arquivos da base de dados CCITT – codificação e decodificação. Total Teórico expresso em bits, Tempo Total em milissegundos e Tempo por símbolo em nanossegundos/símbolo.	49
Tabela 14: Valores médios dos testes realizados para as coleções de arquivos.	49
Tabela 15: Ganhos dos valores médios dos testes realizados para as seis coleções de arquivos.	50
Tabela de Símbolos e Siglas
S – Fonte discreta que emite sequências de símbolos de um alfabeto fixo A = {a1, a2,..., ak}, obedecendo a uma distribuição de probabilidade fixa P(a1), P(a2),..., P(ak).
Bx(n) – Código Binário(ou representação de número inteiro na base x).
Lx(n) – Comprimento da representação Bx(n).
P(an) – Distribuição de Probabilidade.
H (S) – Entropia dos símbolos de uma fonte com distribuição de probabilidade P.
I (an) – Medida deinformação de um símbolo.
R – Redundância.
iii
Capítulo 1
Introdução
O objetivo deste trabalho é estudar um novo codificador de entropia baseado no algoritmo de intercalação. Esta introdução apresenta uma explicação do cenário de compressão de dados, a motivação para estudar esses tópicos, os objetivos específicos do estudo e como este trabalho foi organizado.
Caracterização do Problema 
O campo da compressão de dados é chamado frequentemente de codificação de fonte ou codificação de entropia (códigos compactos). A representação compacta é o resultado do processo de converter uma sequência de dados da entrada (a fonte de dados ou os dados armazenados) em outra sequência de dados de saída (uma sequência de palavras-código).
Existem várias definições de redundância contidas em um dicionário, aquela que é reconhecida pelo senso comum se refere a excesso, repetição excessiva ou pleonasmo. Do ponto de vista da Teoria da Informação a redundância é a repetição de informações, cuja função é a de proteger as mensagens de qualquer sistema de comunicação contra possíveis falhas. A redundância está presente tanto na interação cotidiana de duas pessoas, quanto na transmissão de dados de telecomunicações (EPSTEIN, 1988). Relevância está associada ao fornecimento de informação, regularmente, de forma efetiva e eficiente, capaz de eliminar informação não relevante, pois “se não é relevante, não é informação” e a traduz como “uma medida de contato efetivo entre a fonte e o destinatário” (SARACEVIC, 1970).
O codificador de fonte procura reduzir ao máximo a informação redundante no sinal de forma a ser utilizado o menor número de bits na representação sem perder informação significativa (CARVALHO, 2003).
Representação Compacta
Embora a distribuição de probabilidade da fonte não seja conhecida, é utilizada nessas aplicações o uso de modelos de distribuição, como por exemplo as fontes independentes e identicamente distribuídas (i.i.d.), fontes de Markov, para estimar o comportamento da distribuição. Objetiva-se utilizar o modelo de fonte para comprimir os dados como se a distribuição de probabilidade dos símbolos que compõem a mensagem fossem conhecidos previamente, para encontrar um esquema universal de compressão sem perdas que aproxime a entropia da fonte, para uma distribuição de probabilidade gerada em uma fonte qualquer.
Quando um alfabeto finito de símbolos de uma fonte qualquer deve ser codificado e forem conhecidas as probabilidades dos símbolos, usa-se os códigos de Huffman (HUFFMAN, 1945) e Shannon-Fano (SHANNON e W. WEAVER, 1963). Para um alfabeto de símbolos arbitrários, onde as probabilidades dos símbolos não são conhecidas e nem se pode adequá-las, faz-se necessário o uso de outras técnicas. Deseja-se representar um símbolo arbitrário de forma tão compacta quanto possível; definindo um algoritmo simples para codificação de cada símbolo em uma sequência de bits na saída e recuperar o símbolo sem ambiguidade, a partir de uma sequência de bits de entrada, mesmo que esse símbolo não tenha ocorrido anteriormente na sequência. Códigos que apresentam essas propriedades são geralmente conhecidos como Códigos Universais (do inglês, Universal Codes). (RISSANEN, 1984).
Algoritmos para Codificação de Fonte
Atualmente, a Codificação de Huffman e a Codificação Aritmética são os dois principais algoritmos de codificação de Entropia. Estes dois códigos englobam os fundamentos teóricos para os demais esquemas de compressão.
O algoritmo de Huffman atribui a cada símbolo ai com probabilidade P(ai), de uma fonte S, uma sequência única de bits de comprimento aproximadamente log (1/ P(ai)) bits, arredondando para cima ou para baixo para o próximo número inteiro de bits. A escolha do arredondamento depende de todas as probabilidades P(ai) e é feita utilizando o algoritmo de construção da Árvore de Huffman. Se todas as probabilidades do símbolo for 1/2k, em que k é um número inteiro positivo, o resultado da codificação minimiza o comprimento médio (TOMIC, 2007).
Uma pequena desvantagem do código de Huffman é sua sub-otimalidade no caso em que as probabilidades dos símbolos da fonte possuem uma forma mais geral. O código de Huffman é especialmente ineficiente nos casos em que uma das probabilidades é muito próxima de um, e assim, precisaria somente uma fração mínima de bits para esse símbolo sendo atribuído a este único bit na codificação, fazendo com que a codificação exceda a entropia por uma relação arbitrária (TOMIC, 2007). 
Uma segunda desvantagem do código de Huffman é um grande aumento no overhead nos registradores (processamento ou armazenamento) da codificação, reduzindo seu desempenho, quando as probabilidades da fonte variam com o tempo (para manter a máxima redundância). Além da penalidade da velocidade nesse caso, para fontes que variam suas probabilidades rapidamente, mesmo o algoritmo adaptativo de Huffman é incapaz de construir a exata estatística necessária sobre as extensões dos símbolos de entrada para a codificação ótima (TOMIC, 2007).
A codificação Aritmética como um método teórico remete ao trabalho se Shannon (SHANNON e W. WEAVER, 1963). Baseia-se na ideia de que a probabilidade cumulativa da mensagem pode ser usada para identificar a mensagem. Apesar de melhorias durante décadas, sua principal desvantagem era a exigência de uma precisão aritmética de mesma dimensão dos dados de saída, ou seja, as divisões e as multiplicações teriam de manipular milhares de bits por muito tempo. Permanecendo por muitos anos como comentário de Abramson (ABRAMSON, 1963) e uma curiosidade acadêmica (MOFFAT, NEAL e WITTEN, 1998) até que em 1976 quando o investigador Rissanen (RISSANEN, 1976) da IBM propôs uma maneira de fazer a aritmética de o algoritmo trabalhar dentro da precisão da máquina (16, 32 ou 64 bits), evitando assim o overhead, praticamente independente do comprimento dos dados, com uma penalidade na taxa de compressão para uma precisão truncada (SAID, 2003). Durante a década seguinte, o algoritmo evoluiu rapidamente, principalmente com as melhorias da velocidade obtidas com somente uma pequena perda adicional na eficiência da compressão, como no Qcoder da IBM (PENNEBAKER e MITCHELL, 1988), e as variantes adaptáveis mais rápidas e flexíveis. Em 1990,o codificador aritmético tomou o lugar do algoritmo de Huffman, sendo usado em diversas aplicações.
No entanto, ao passo que o codificador aritmético alcance taxas de compressão desejadas, esta “melhor compressão” requer ainda multiplicações no codificador e divisões no decodificador para cada símbolo processado, fazendo-o mais lento do que o codificador estático de Huffman, especialmente na codificação. O codificador aritmético compartilha com codificador de Huffman a desvantagem da lenta adaptabilidade a fontes que variam suas probabilidades rapidamente com o tempo (TOMIC, 2006).
Objetivos e Metas
Este trabalho tem como proposta a comparação entre esquemas de codificação de fonte (codificador de entropia). O objetivo principal será utilizar os algoritmos de intercalação (Merge algorithm (KNUTH, 1998)), que realizam comparações para ordenar duas listas distintas sem a necessidade de conhecer as distribuições de probabilidade, aplicados a um codificador de fonte. O codificador de fonte com intercalação codifica cada símbolo de uma sequência de símbolos, independente da fonte e com baixa redundância, sendo este método estático e necessita armazenar, consequentemente, o número de ocorrências de cada símbolo antes de codificar as posições, porém pode ser adaptável no sentido de variar o comprimento das sequências codificadas e é também universal (LIMA, 2007).
Para avaliar a codificação de fonte com intercalação, será estudado a codificação aritmética, esta utilizado pelos codificadores presentes no sistema de televisão digital brasileiro (CARVALHO, 2003). A codificação aritmética tem como objetivo transformar cada símbolo de uma fonte em uma palavra código de comprimento equivalente a sua quantidade de informação I em bits,que nem sempre é um número inteiro, se baseando em projetar as probabilidades dos símbolos em um intervalo real unitário ([0;1)). Serão realizados testes com a implementação do codificador de fonte com intercalação, mostrando desempenho e redundância e fazendo comparações com o codificador aritmético.
Com estes testes será mostrado que a codificação de fonte com intercalação é mais eficiente no sentido de tempo de codificação se comparado aos clássicos (codificador aritmético), e que pode vir a ser utilizado em situações reais, visto que se tem uma vasta gama de possíveis aplicações.
Metodologia
Serão utilizados aplicativos para desenvolvimento de programas, para compilação dos codificadores, de intercalação utilizando o Visual Studio C/C++ 2005®, para implementação dos codificadores na linguagem C/C++.
Para avaliar o codificador de intercalação será feita uma comparação entre os dois métodos implementados, aplicando algumas das principais coleções de arquivos utilizadas como padrão para avaliar desempenho de algoritmos de compressão. Serão utilizadas as seguintes coleções:
Calgary Corpus (The Canterbury Corpus, 2001);
Canterbury Corpus (The Canterbury Corpus, 2001);
Artificial Corpus (The Canterbury Corpus, 2001);
Large Corpus (The Canterbury Corpus, 2001);
Miscellaneous Corpus (The Canterbury Corpus, 2001);
CCITT Corpus (C.C.I.T.T. Et Télégraphic).
As comparações irão levar em consideração os seguintes parâmetros de desempenho:
Redundância, em bits/símbolo;
Tempo total de execução, que é o tempo que o método gasta para compactar e/ou descompactar, em milissegundos;
Tempo de execução por símbolo, que é o tempo gasto para compactar e/ou descompactar cada símbolo, em nano segundos/símbolos.
Observação
O codificador de fonte com intercalação estudado apresenta desempenho superior ao codificador de fonte aritmético, definido na literatura. É demonstrado que o codificador analisado se comportou em relação aos tempos de codificação/decodificação mais rápido, assim diminuindo os atrasos de transmissão em relação à fonte codificada com o algoritmos aritmético, mantendo a qualidade do que se quer transmitir.
Dessa forma, este estudo consolida o esquema de codificação de fonte com intercalação (LIMA, 2007), abrindo novas perspectivas para área, a saber:
Codificação de fontes D-árias;
Codificação de Fontes de Markov;
Análise de esquemas de codificação com intercalação;
Análise do desempenho do codificador para tipos de informações específicas, e.g., áudio e vídeo.
Organização do texto
O Capítulo 2 introduz definições básicas usadas ao longo do desenvolvimento deste trabalho, conceitos de teoria da informação. Em seguida, no Capítulo 3, serão apresentados os principais codificadores de entropia, a classificação destes codificadores, e será dada maior ênfase ao codificador aritmético que será utilizado para a comparação com um novo código proposto. Finalmente, são apresentados a teoria e o desenvolvimento do codificador de fonte proposto, introduzindo o algoritmo de merge (intercalação) e a codificação de entropia baseada no algoritmo de merge. 
No Capitulo 4 são mostrados os resultados dos testes realizados com a implementação do esquema proposto, mostrando desempenho e redundância. Os testes fazem a comparação do algoritmo de codificação aritmética com o novo esquema. Fontes binárias foram implementadas para situar a codificação proposta em relação aos codificadores clássicos.
Por fim, no Capítulo 5 tem-se a conclusão do trabalho com as considerações finais e sugestões para trabalhos futuros.
Capítulo 1 – Introdução
Capítulo 2
Conceitos de Teoria da Informação
Para entender codificação de fonte (codificação de entropia - projeto de um código de tamanho variável tal que o tamanho médio da palavra do código se aproxima da entropia da fonte discreta sem memória.), inicialmente será realizada uma breve apresentação de alguns conceitos importantes de Teoria da Informação (disciplina centrada à volta de uma abordagem matemática comum ao estudo do armazenamento e manipulação da informação.) e a apresentação de alguns códigos clássicos, enfatizando o codificador aritmético que será utilizado no desenvolvimento desse trabalho como a validação de uma nova proposta para os codificadores de entropia.
Conceitos e Definições
Teoria da Informação
A Teoria da Informação responde a duas questões fundamentais da teoria da comunicação: Qual a compressão de dados final e qual taxa de transmissão da comunicação (COVER e THOMAS, 2006).
No inicio dos anos 1940 pensava-se ser impossível o envio de informações a uma taxa positiva com probabilidade de erro desprezível. Shannon surpreendeu provando que a probabilidade de erro pode ser quase zero para todas as taxas de transmissão abaixo da capacidade do canal. A capacidade do canal pode ser calculada a partir das características do ruído do mesmo. Shannon argumentou ainda que processos aleatórios, como músicas ou um discurso, tem informação mensurada por quantidade e que, atingido o valor máximo para essa quantidade de informação não poderá ser comprimido. Este fato, é chamado de Entropia, e argumentou-se que se a entropia da fonte é menor do que a capacidade do canal, assim, uma comunicação livre de erros pode ser alcançada.
A teoria da informação hoje representa os pontos extremos do conjunto de todos os possíveis esquemas de comunicação. Um dos extremos é o mínimo de compressão de dados e no outro extremo é a transmissão máxima, conhecida como capacidade do canal. Então, todos os esquemas de modulação e compressão de dados se situam entre estes limites.
A teoria da informação também sugere meios para alcançar estes limites da comunicação. No entanto, esquemas de comunicação ideal podem vir a ser impraticáveis computacionalmente. Progressos em circuitos integrados e projetos de código garantem evoluções para se alcançar o que é proposto pelo teorema de Shannon. 
Fontes de Informação sem Memória
O modelo mais simples para uma fonte de informação sem memória, numa perspectiva probabilística é simplesmente uma variável aleatória (FIGUEIREDO, 2007). Por “sem memória” entende-se que a propriedade de um simbolo gerado é independente dos demais gerados anteriormente.
Dessa forma, considere uma fonte discreta S que emite simbolos a partir de um alfabeto finito A = {a1, a2, a3,..., ak}. Este alfabeto é composto por simbolos sucessivos selecionados de acordo com alguma distribuição de probabilidades fixa P(a1), P(a2),..., P(ak). Define-se então a fonte S como uma variável aleatória que toma valores em A. Dada a ausência de memória, cada símbolo é uma amostra desta variável aleatória, gerada de modo independente das outras amostras (FIGUEIREDO, 2007).
Pode-se calcular a média de informação fornecida por uma fonte de informação sem memória, como se segue: Se ocorre símbolo xi, obtém-se uma quantidade de informações igual
 bits,
considerando uma fonte binária.
A probabilidade de isso acontecer é apenas P(Si), de modo que a quantidade média de informação obtida por símbolo, a partir da fonte é
	bits,
em que o somatório indica uma soma entre os q símbolos da fonte S. Esta quantidade é chamada a entropia H (S) da fonte de memória zero. 
	bits/símbolo.
Classificação dos Códigos
Os códigos de fonte discreta sem memória são classificados da seguinte forma:
Códigos de Tamanho Fixo: São códigos de tamanho fixo, como o próprio nome diz, é aquele cujo tamanho do código é fixo (HSU, 2006). Os códigos 1 e 2 da Tabela 1 são códigos de tamanho fixo com tamanho 2.
Tabela 1: Exemplo de códigos binários.
	xi
	Código 1
	Código 2
	Código 3
	Código 4
	Código 5
	Código 6
	x1
	00
	00
	0
	0
	0
	1
	x2
	01
	01
	1
	10
	01
	01
	x3
	00
	10
	00
	110
	011
	001
	x4
	11
	11
	11
	111
	0111
	0001
Códigos de Tamanho Variável: Como o próprio nome indica, são códigos cujo tamanho não é fixo. Exceto os códigos 1 e 2 da Tabela 1, os demais são códigos de tamanho variável.
Códigos Distintos: São códigos onde cada palavra codificadaé distinguível das demais. Todos os códigos da Tabela 1 são distintos, exceto o código 1.
Códigos de Prefixo Livre: Em um código de prefixo livre, nenhuma palavra-código é um prefixo de outra palavra-código. Os códigos 2, 4 e 6 da Tabela 1 são códigos de prefixo livre.
Códigos Unicamente Decodificáveis: Para cada sequência de fonte de comprimento finito a sequência de palavras do código correspondente é diferente das palavras de um código correspondente a qualquer outra sequência de fonte. Os códigos 2, 4 e 6 da Tabela 1 são códigos unicamente decodificáveis, não sendo a condição de prefixo livre necessária para que o código seja unicamente decodificável. O código 5 não satisfaz a condição de prefixo livre, mas é unicamente decodificável.
Existe uma classe especial de códigos que satisfaz uma restrição chamada condição de prefixação, estes são chamados de códigos sem prefixos ou códigos instantâneos. Nestes códigos nenhuma palavra do código é o prefixo de qualquer outra palavra do código (ABRANTES, 2003). 
Código Instantâneo: Um código unicamente decodificável é chamado de instantâneo se o final de qualquer palavra-código for reconhecido sem examinar os códigos subsequentes. Códigos instantâneos possuem a propriedade previamente mencionada de que nenhuma palavra-código é um prefixo de outra. Por essa razão, códigos de prefixo livre são, algumas vezes, chamados de códigos instantâneos (HSU, 2006). Os códigos Shannon-Fano e Huffman são exemplos de códigos de fonte sem prefixo.
Códigos Ótimos: Um código é dito ótimo se ele for instantâneo e possuir um tamanho L mínimo para uma dada fonte com uma dada probabilidade associada a símbolos da fonte (HSU, 2006).
Medida de Informação
Definição 1.1 Considere uma fonte discreta S, representada por A, com alfabeto {a1, a2, a3,..., ak}. O conteúdo de informação de um símbolo ak representado por I(xi), é definido por 
;
unidades de informação. Onde, P(xi) é a probabilidade da ocorrência do símbolo xi (HSU, 2006).
A escolha de uma base para o logaritmo define a unidade, que utiliza-se para informações, então tem-se:
 (HARTLEY, 1928).
Se for escolhido um logaritmo na base 2, a unidade de informação resultante é chamado bit.
 bits.
Se utilizado o logaritmo natural, a unidade de informação resultante é chamado o nat (uma contração da unidade natural).
 nats.
Para o logaritmo para a base 10, a unidade de informação é o Hartley. Foi R. V. Hartley (HARTLEY, 1928) quem sugeriu pela primeira vez o uso de uma medida de informação logarítmica (ABRAMSON, 1963),
 	Hartleys.
Segundo Lima (LIMA, 2007), a quantidade de informação de uma mensagem M = x1x2... xt, com símbolos independentes, é dada pela soma da quantidade de informação das palavras que a compõe, isto é,
.
Exemplo 1: Tem-se como exemplo de medida de informação a representação binária de um número conforme mostrada na Tabela 2:
Tabela 2: Codificação binária dos dígitos decimais.
	Dígitos Decimais
	Representação Binária
	0
	0
	1
	1
	2
	10
	3
	11
	4
	100
	5
	101
	6
	110
	7
	111
	8
	1000
	9
	1001
Calculando-se o valor de I(u), tem-se:
.
Portanto, obtém-se 4 bits de informação, quando se escolhe dez alternativas equiprováveis.
Entropia
Definição 1.2 Entropia é a quantidade de informação obtida por símbolo de uma fonte sem memória.
 bits/símbolo;
que pode ser interpretada como a incerteza que um observador tem, sobre qual será o símbolo emitido, antes de saber qual símbolo foi de fato emitido pela fonte. A entropia H(S) pode ser interpretada como uma medida de incerteza sobre o valor de uma variável aleatória S (LIMA, 2007).
Observação: Entropia H(X) de uma variável aleatória discreta X define-se por
 bit/símbolo;
em que, é o valor esperado da variável aleatória discreta X, em que por convenção no limite quando P(xi) → 0,
;
pois, xlogx → 0 conforme x → 0, ou seja, este termo do somatório pode ser desprezado.
	Com isto, observa-se que a entropia máxima ocorre quando as probabilidades são equiprováveis: quanto maior for à diferença entre as probabilidades, ou seja, menor será a entropia, e esta é a situação de maior incerteza.
No caso particular de uma das probabilidades ser 100%, a entropia será zero. Weaver (WEAVER, 1949) nota, em complemento a ideia de Shannon, que a entropia também aumenta quanto maior for à quantidade de possibilidades, i.e., tomando-se dois conjuntos de possibilidades equiprováveis, a entropia será maior no conjunto de possibilidades numerosas (PINEDA, 2006), como ilustrado na Figura 1. Ele afirma, também, que os eventos de uma fonte de informação discreta são os símbolos que ela gera, e define a entropia de uma fonte discreta por
 ;
em que fi, frequência média do estado i, relaciona-se com a entropia pela equação 
;
em que m é o número médio de símbolos produzidos por segundo. Weaver, também deduz a fórmula da entropia para longas sequências de símbolos independentes, que é válida para qualquer fonte. Toma-se numa sequência composta de N símbolos, e Pi a probabilidade do símbolo i, com entropia . Esta sequência terá alta probabilidade de conter ocorrências de cada símbolo proporcionais às suas probabilidades individuais, ou seja, PiN. Assim sendo, a probabilidade desta sequência em particular é
.
Logo, tem-se
;
;
.
Figura 1: Variação da Entropia H(P) em função da probabilidade P.
Com este conceito, pode-se definir a quantidade de informação transmitida e os limites de compressão dessa informação.
Exemplo 2: Tem-se:
;
a entropia de S será 
 bits/símbolo,
ou seja, teremos 1,75 bits de informação a cada símbolo da fonte sem memória.
Redundância
Definição 1.3 Segundo Salomon (SALOMON, 2006), redundância é a diferença entre a máxima entropia possível do conjunto de símbolos (P(ai) = P) e sua entropia real. Assim, 
.
Para dados inteiramente comprimidos (nenhuma redundância) tem-se,
.
Em outras palavras, redundância é tudo aquilo que não é fundamental para o entendimento de uma mensagem.
Segundo Shannon (SHANNON e W. WEAVER, 1963), uma mensagem de k símbolos pode, em média, ser comprimida em bits. Shannon prova também que codificadores assintoticamente ótimos (codificadores de entropia) existem, mas não mostra como construí-los.
Exemplo 3: Considere a fonte indicada na Tabela 3:
Tabela 3: Probabilidade de símbolos de uma fonte qualquer.
	Símbolo da Fonte
	Representação binária
	Probabilidade
	Comprimento
	s1
	0
	1/2
	l1
	s2
	10
	1/4
	l2
	s3
	110
	1/8
	l3
	s4
	111
	1/8
	l4
 bits/simbolo.
Cada símbolo: , αi inteiro.
É possível alcançar o limite inferior de 1,75 bits/símbolo, tem-se
;
 bits/símbolo.
Fontes de Markov
A fonte sem memória considerada até agora é muito restrita para algumas aplicações. Um tipo mais geral de fonte de informação, do que a fonte sem memória, é aquele em que a ocorrência de um símbolo s pode depender de um número finito de m símbolos precedentes. Essa fonte, chamada fonte de Markov, dá origem ao alfabeto S e o conjunto de probabilidades condicionais, 
;
para i = 1, 2, . . . , qi e jp = 1, 2, . . . , q, onde i é o instante de tempo de emissão de determinado símbolo e j refere-se aos instantes de tempo de um passado recente.
Para uma fonte de Markov, sabe-se a probabilidade de emissão de um determinado símbolo se os m símbolos que o precedem forem conhecidos. Em qualquer momento, por isso, serão chamados os m símbolos anteriores ao estado da fonte de Markov naquele momento. Uma vez que existem q possíveis símbolos, uma fonte de Markov terá qm estados possíveis. Um modo prático para ilustrar o comportamento de uma fonte de Markov é através do uso de um diagrama de estado, como mostrado na Figura 2. Em um diagrama de estado que representa cada um dos qm possíveis estados de origem por círculos com os valores dos estados e as possíveis transições de estado para estado por setas.
Exemplo 4: Considere-se uma fonte de Markov de segunda ordem (probabilidade do símbolo emitido num instante i, dado todo o passado, for apenas função de um passadorecente de duração q=2) com o alfabeto binário S = {0, 1}. Assume-se as probabilidades condicionais por símbolo,
;
;
.
Então, como q é igual a 2 e assumiu-se uma fonte de Markov de segunda ordem, tem-se quatro estados da fonte (00, 01, 10, 11). Os estados possíveis da fonte são indicados por quatro pontos na Figura 2 . As transições de estado possíveis são indicadas pelas setas de estado para estado, com a probabilidade de uma transição mostrada por um número associado com cada seta. Por exemplo, estando em estado de 00, pode-se ir para os estados 01 ou 00, mas não aos estados 10 ou 11. A probabilidade de permanecer no estado 00 é mostrado como 0,8, e a probabilidade de ir ao estado 01 é mostrado como 0,2.
Figura 2: Diagrama de estados para fonte de Markov de segunda ordem.
Desigualdade de Kraft-MacMillan
Num código binário unicamente decodificável é condição necessária que os comprimentos ni das palavras respeitem a desigualdade,
.
Se o alfabeto do código tiver tamanho D a desigualdade será
(ABRANTES, 2003).
Note que a desigualdade garante a existência de um código decodificável instantâneo com tamanhos de palavra de código que satisfazem a desigualdade. Porém, não mostra como obter estas palavras código e não diz, também, que todo código que satisfaz a desigualdade é automaticamente unicamente decodificável (HSU, 2006).
Exemplo 5: Codificação de uma fonte decimal em uma fonte binária instantânea, ou seja,
;
.
Suponha que se deseja codificar os símbolos da fonte em palavras-código curtas (esses símbolos pode ser os mais prováveis de ocorrer).
Faça:
Se for requerido que as oito palavras restantes tenham o mesmo comprimento l, então:
;
;
.
Portanto, não é possível encontrar um código se l ≤ 5.
A desigualdade de Kraft-McMillian nos diz que é possível achar um código com l = 5, porém não diz como construir o código, ver Tabela 4.
Tabela 4: Exemplo de um código de comprimento médio l = 5.
	Símbolo da Fonte
	Código Binário
	0
	0
	1
	10
	2
	11000
	3
	11001
	4
	11010
	5
	11011
	6
	11100
	7
	11101
	8
	11110
	9
	11111
Capítulo 2 – Conceitos de Teoria da Informação
Capítulo 3
Códigos de Fonte
A Codificação de Fonte é um processo que visa reduzir o máximo possível à informação redundante da sequência de informação em sua saída, esta sequência é obtida a partir do processamento de um sinal de entrada.
Segundo Castro e Castro (CASTRO e CASTRO), o processamento do sinal analógico é realizado nas seguintes etapas:
Amostragem: É o processo no qual um sinal continuo no tempo se transforma em um sinal discreto no tempo;
Quantização: É o processo através do qual o sinal discreto no tempo, contínuo em amplitude, é transformado em um sinal discreto em amplitude. Ou seja, dado um sinal discreto no tempo m(n) no instante n, o sinal quantizado mq(n) assumirá um dos M possíveis valores, chamados de níveis de quantização. Quanto menor o número de níveis de quantização utilizados para representar o sinal m(n), menos fiel será a representação;
Codificação: É o processo onde cada um dos M possíveis valores do sinal quantizado mq(n) é mapeado em uma sequência (ou bloco) de bits. Cada elemento será mapeado, de acordo com o código adotado, e associado a um número representado por N bits;
Compressão: É o processo onde cada uma das M sequências de N bits terão seu número de bits N reduzido para um valor menor como decorrência da eliminação de informações redundantes.
Para a codificação de fonte, neste trabalho é dado destaque aos itens 3 e 4, por sua importância na redução de informação redundante.
O projeto de um código de tamanho variável, tal que, o tamanho médio da palavra de código se aproxima da entropia da fonte discreta sem memória é geralmente chamado de codificação de entropia. Neste trabalho, serão mostrados alguns códigos de Entropia, onde se dará maior ênfase ao Código Aritmético que será utilizado para comparação com um novo código, o código de fonte por intercalação.
Código de Huffman
O Código de Huffman é utilizado para codificar uma fonte de forma a obter uma compactação ótima dentro de certos critérios. A construção desse código foi desenvolvida por David Huffman (HUFFMAN, 1945), que utilizou a estrutura de árvore binária, originando um código binário. Supõe-se que é conhecida a frequência de cada símbolo emitido pela fonte. Deseja-se atribuir uma palavra-código a cada símbolo, de modo a representá-lo da forma mais compacta possível. O código de Huffman atribui uma palavra-código de comprimento inteiro.
O código de Huffman utiliza uma árvore estritamente binária, denominada árvore de Huffman, que é construída a partir das probabilidades de ocorrência de símbolos na mensagem a ser codificada. A árvore de Huffman é composta de ramos rotulados, e serão utilizados na determinação de cada código. O processo de construção de uma árvore de Huffman, será mostrado no Exemplo 6.
Este código de fonte é ótimo no sentido de que o número médio de dígitos necessários para representar o símbolo da fonte é mínimo (ABRANTES, 2003). A otimalidade do código ocorre quando cada símbolo possuir probabilidade da forma , com k ≥ 0, onde m é o número de ramos que cada nó pode possuir na árvore de Huffman e k é o número de símbolos da fonte.
	Este código em alfabetos binários é ótimo para fontes fixas que geram símbolos com probabilidades com valores da forma , com k ≥ 1.
Exemplo 6: (ABRANTES, 2003) Considerando uma fonte que produz oito símbolos:
						
						
Deve-se seguir os seguintes passos para construir a árvore do código:
Ordenar as mensagens por ordem decrescente de probabilidades.
x1	x8	x7	x5	x4	x6	x3	x2
Agrupar as duas mensagens com as probabilidades mais baixas e somar estas probabilidades.
Agrupa-se x2 e x3 no nó a cuja soma de probabilidades dá 0,05. De um conjunto de oito probabilidades passando a ter um conjunto de 6+1=7 probabilidades.
Repetir o passo anterior para o novo conjunto de probabilidades, até chegar à raiz da árvore.
Da copa para a raiz arbitrar o bit 1 (ou 0) para os ramos que partem do nó de menor probabilidade e o bit 0 (ou 1) para os que partem do outro nó.
Determinar as palavras de código percorrendo a árvore da raiz para a copa.
Figura 3: Árvore do exemplo de código de Huffman Binário. 
A entropia da fonte vale:
 bits/símbolo.
O comprimento médio das palavras é:
2,26 digitos binários/símbolos.
A eficiência do código = .
O código de Huffman é usado em equipamentos comerciais de compressão de dados para reduzir o número de bits transmitidos permitindo, portanto, reduzir o tempo de transmissão. Um exemplo concreto é o equipamento de fax.
Código de Shannon-Fano
A codificação de Shannon-Fano é um método de estatístico de compressão sem perda de dados que gera códigos de tamanho variável para cada símbolo dos conjunto de dados a ser comprimido de acordo com sua probabilidade de ocorrência. Este método foi descrito em 1948 por Claude Shannon em seu famoso artigo "A Mathematical Theory of Communication" e atribuído a Robert Fano. O método é anterior ao de codificação de Huffman, e apesar de bastante eficiente e prático, gera resultados sub-ótimos. 
Neste código as palavras a serem codificadas devem ser ordenadas por ordem decrescente de probabilidades. Um código eficiente pode ser obtido pelo seguinte procedimento, chamado de algoritmo de Shannon-Fano (HSU, 2006):
Liste os símbolos da fonte em ordem decrescente de probabilidade;
Particione o conjunto em dois subconjuntos que possuam probabilidades mais próximas possíveis, de forma que a soma das probabilidades dos símbolos individuais se aproximem de 50% em cada subconjunto, e associe “0” ao subconjunto superior e “1” ao subconjunto inferior;
Continue esse processo, cada vez particionando os subconjuntos que possuam as probabilidades mais próximas possíveis até que não possa ser realizado nenhum particionamento.
Exemplo 7: (ABRANTES, 2003) Supondo que se tem as palavras x1, x2, x3, x4, x5 e x6, que ocorrem com as seguintes probabilidades:P(x1)= 0,1		P(x2)= 0,2		P(x3)= 0,2
P(x4)= 0,03		P(x5)= 0,07		P(x6)= 0,4
Ordenando os símbolos e dividindo-os sucessivamente em dois grupos de probabilidades aproximadas, obtém-se conforme a Tabela 5:
Tabela 5: Exemplo construção código Shannon-Fano.
	Símbolo
	Probabilidade de ocorrência
	Construção das palavras do código
	Palavras do código
	P(x6)
	0,4
	0
	0
	
	
	00
	P(x2)
	0,2
	0
	1
	
	
	01
	P(x3)
	0,2
	1
	0
	
	
	10
	P(x1)
	0,1
	1
	1
	0
	
	110
	P(x5)
	0,07
	1
	1
	1
	0
	1110
	P(x4)
	0,03
	1
	1
	1
	1
	1111
A entropia da fonte é calculada como:
bits/símbolo.
 O comprimento médio das palavras do código será:
;
onde, é o número de bits que representa cada símbolo, então:
;
 digitos binários/símbolo.
Eficiência do código = .
Código Aritmético
O codificador aritmético para compressão de dados não é baseado em tabelas de símbolos. O codificador aritmético elimina a associação entre símbolos individuais e palavras-códigos de comprimento inteiro e, com isto, é capaz de praticamente igualar a entropia da fonte em todos os casos.
Esta técnica de codificação permite gerar códigos ótimos se as diversas probabilidades de ocorrência forem conhecidas rigorosamente, sendo então necessária uma correta modelização da fonte, como já ocorria na codificação de Huffman.
O código gerado por um codificador aritmético representa um número real: o codificador faz corresponder a uma sequência qualquer de símbolos (cada um com sua probabilidade) um número real no intervalo [0,1). Este intervalo é inicialmente dividido em tantos intervalos quanto forem os símbolos diferentes produzidos pela fonte, de tamanhos proporcionais às probabilidades de ocorrência respectivas.
Codificação e Decodificação
O método inicia com um intervalo [0,1), lê-se o arquivo símbolo a símbolo, e utiliza-se a probabilidade de cada símbolo para reduzir o intervalo. As iterações são realizadas para cada símbolo, sendo que, a cada símbolo o intervalo é reduzido ao subintervalo correspondente à probabilidade de ocorrência do símbolo processado, e uma nova projeção de probabilidade é executada no novo intervalo. O resultado final será um número real incluído no intervalo final (fechado à esquerda e aberto à direita). O número escolhido deverá ser um entre os que podem ser representados pelo menor número de bits.
Para conseguir a compressão, o algoritmo é projetado de tal forma que um símbolo de alta probabilidade reduz menos o intervalo que um símbolo de baixa probabilidade, com o resultado que os símbolos de alta probabilidade contribuem com poucos bits na saída (LIMA, 2007).
Exemplo 8: O Primeiro exemplo envolve uma fonte de três símbolos a1, a2 e a3, com as probabilidades P(a1)=0,4, P(a2)=0,5 e P(a3)=0,1, respectivamente. O intervalo [0,1) é dividido entre os três símbolos atribuindo a cada subintervalo proporcional a probabilidade. A ordem dos subintervalos não é importante. Serão considerados para este exemplo os subintervalos [0; 0,4), [0,4; 0,9) e [0,9; 1), para os três símbolos respectivamente. Para codificar a sequência a2 a2 a2 a3, começa-se com o intervalo [0,1).
Para calcular os intervalos será utilizada a fórmula:
.
Onde, e são os limites inferior e superior do intervalo e e são os limites inferior e superior dos caracteres definidos pela distribuição de probabilidade.
1º caractere: a2, subintervalo [0,4; 0,9). Intervalo inicial [0,1)
Temos que , e .
.
O novo intervalo será [0,4; 0,9).
2º caractere: a2, subintervalo [0,4; 0,9). Intervalo [0,4; 0,9).
.
O novo intervalo será [0,6; 0,85).
3º caractere: a2, subintervalo [0,4; 0,6). Intervalo [0,6; 0,85).
.
O novo intervalo será [0,7; 0,825).
4º caractere: a3, subintervalo [0,9; 1). Intervalo [0,6; 085).
. 
Então o código resultante é um número pertencente ao intervalo [0,8125; 0,8250), no exemplo o número poderia ser 0,8125.
A representação gráfica da codificação aritmética para este exemplo pode ser vista na Figura 4.
Figura 4: Representação gráfica da codificação aritmética com expansão após cada iteração descrita no Exemplo 8.
Com o Exemplo 8 fica claro o processo de codificação, conforme mostrado graficamente pela Figura 4, que mostra a redução dos intervalos devido a probabilidade de ocorrência de cada caractere.
 	Então pode-se resumir as principais etapas do codificador aritmético como:
O intervalo inicial é [0,1).
Repetir as duas etapas seguintes para cada símbolo a na sequência de entrada emitida pela fonte S:
Dividir o intervalo atual em subintervalos proporcionais às probabilidades dos símbolos;
Selecionar o subintervalo para a e defini-lo como o novo intervalo atual;
Quando a sequência de entrada for processada inteiramente desta maneira, a saída deve ser qualquer número real positivo que identifique o intervalo atual, isto é, um número real que pertença ao intervalo atual.
O decodificador trabalha de maneira oposta. Começa lendo os símbolos e os respectivos intervalos. Pode-se ver a codificação e a decodificação de uma sequência no Exemplo 9.
Exemplo 9: Tem-se três símbolos A, B e C, com as seguintes probabilidades P(A) = 0,4, P(B) = 0,35 e P(C) =0,25. Codificar a sequência ACBAAB.
Utilizaremos neste exemplo os seguintes subintervalos [0; 0,4), [0,4; 0,75) e [0,75; 1), para os símbolos respectivamente.
1º Caractere: A, subintervalo [0; 0,4). Intervalo inicial [0,1).
.
O novo intervalo será [0; 0,4).
2º Caractere: C, subintervalo [0,75; 1). Intervalo [0; 0,4).
.
O novo intervalo será [0,3; 0,4).
3º Caractere: B, subintervalo [0,4; 0,75). Intervalo [0,3; 0,4).
.
O novo intervalo será [0,34; 0,375).
Será realizado este calculo até o ultimo símbolo da sequência. Ao final tem-se o seguinte intervalo [0,3422; 0,3442).
Supondo que se tem o número 0,3422, que está dentro do intervalo [0,3422; 0,3442), o processo de decodificação será realizado da seguinte forma:
1ª Iteração: o valor 0,3422 está dentro do intervalo de A, [0; 0,4). Sendo assim o primeiro caractere recebido será A. 
2ª Iteração: Para saber qual o próximo caractere recebido faz-se,
.
	Então, tem-se
.
Que está no intervalo de C, [0,75; 1). Sendo assim, o próximo caractere recebido será C.
3ª Iteração: foi recebido o caractere C, o próximo será,
	Que está no intervalo de B, [0,4; 0,75). Então o próximo caractere recebido será B.
4ª Iteração: O próximo símbolo será A, devido a,
,
Que está no intervalo de A, [0; 0,4).
5ª Iteração: O próximo símbolo será A, devido a,
,
Que está no intervalo de A, [0; 0,4).
6ª Iteração: o próximo símbolo será B, devido a,
,
Que está no intervalo de B, [0,4; 0,75).
	Na descrição realizada sobre a codificação aritmética, foi considerada uma precisão infinita para os intervalos, ou seja, foi visto um processo de codificação cujo código gerado possui comprimento igual à soma dos logaritmos dos inversos das probabilidades, valor conhecido por comprimento ideal do código. Contudo, em aplicações praticas sabe-se que não é possível tal consideração, assim é realizado um truncamento na precisão, que acarreta diversos problemas que não serão abordados neste trabalho (SAID, 2003).
Codificação de fonte com Intercalação
Nesta seção apresenta-se uma nova técnica de codificação intitulada Codificação de Fonte com Intercalação (CFI).
Será utilizada esta nova proposta de codificação para uma comparação com as demais existentes, mais especificamente com a codificação aritmética que converte as probabilidades em palavras-código.
O CFI é uma nova técnica de codificação de entropia baseada em algoritmos de intercalação (do inglês, Sorting by Merging Algorithmic) (KNUTH, 1998), que codifica a posição de cada símbolo a partir da posição do símbolo anterior. Uma das principais características dessa nova codificação é que não se precisa conhecer as distribuições de probabilidade.
A ideia básica é a partir da posição de um símbolo anterior se conhecer a posição de um símbolo e a quantidade de bits necessários para armazenar esta posição.
Algoritmode Intercalação
O problema principal é determinar a melhor forma de ordenação para fundir dois conjuntos, A e B, através de comparações entre os elementos desses conjuntos.
Suponha dois conjuntos ordenados A e B, com m e n elementos respectivamente, da forma
;
e que os m + n elementos são distintos, ou seja, os elementos de A podem aparecem entre os elementos de B em maneiras distintas, assim os argumentos utilizados para os argumentos de classificação afirmam que pelo menos 
;				 (3.1)
comparações são requeridas para realizar a fusão dos conjuntos A e B (LIMA, 2007).
	Assim, pode-se definir a função M (m,n) que retorna o número mínimo das comparações necessárias para realizar a fusão dos dois conjuntos A e B, com m e n elementos respectivamente, da seguinte forma
, para m, n ≥1.		(3.2)
Onde se pode notar que o limite superior é dado pela comparação termo a termo dos dois conjuntos.
	Uma observação deve ser feita com respeito ao limite superior da equação (3.2). Se m = 1, o problema de intercalação é equivalente a um problema de inserção, em que há n + 1 lugares em que o elemento a1 pode ser encaixado em b1, ..., bn. A busca binária (do inglês, Binary Search Algorithm) é uma maneira simples de alcançar esse valor, partindo do pressuposto de que o vetor está ordenado é realizada sucessivas divisões do espaço de busca, comparando o elemento aos elementos da lista em que se pretende inserir (KNUTH, 1998).
	Para ilustrar a intercalação, considere as duas listas {147, 791, 801, 921} e {066, 567, 628}. Uma maneira de realizar esta intercalação é fazer a comparação termo a termo das duas listas, dessa forma, serão feitas inicialmente comparações entre os menores termos de cada lista:
;
obtendo
066 ;
então, 
066 147 ;
e assim por diante. Em caso de dois elementos serem iguais realiza-se uma escolha aleatória entre esses elementos das listas. Uma descrição detalhada desse processo é apresentada no algoritmo M e na Figura 4 (KNUTH, 1998).
	Algoritmo M – Este algoritmo une duas listas ordenadas e em uma única lista da seguinte forma:
Passo 1: [Iniciar] Ajuste , e.
Passo 2: [Achar o menor] Se , vá para o Passo 3, senão vá para o Passo 5.
Passo 3: [Saída xi] Ajuste , e . Se, retorne para o Passo 2.
Passo 4: [Transmitir yj, ..., yn] e termina o algoritmo.
Passo 5: [Saída yi] Ajuste , e . Se retorne para o Passo 2.
Passo 6: [Transmitir xj, ..., xn] Faça e termina o algoritmo.
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	 > 
	
	
	
	
	
	
	
	
	
	 ≤ 
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
 Algoritmo de Intercalação de x1 <x2 <... < xm com y1 <y2 <... < yn (KNUTH, 1998).
Como pode ser visto em Knuth (KNUTH, 1998), quando m ≈ n esse procedimento é a melhor maneira possível de fundir duas listas em um computador convencional. Por outro lado, quando m é muito menor do que n, é possível planejar outros algoritmos mais eficientes, embora mais complexos. O número de operações envolvidas no algoritmo M é essencialmente da ordem de m+n (KNUTH, 1998).
Algoritmo de Intercalação Binária
O procedimento adotado para este algoritmo tem as características já descritas na seção 3.4.1 e foi definido por Hwang e Lin (HWANG e LIN, 1972) (HWANG e LIN, 1971), é apresentado no Algoritmo H. Knuth (KNUTH, 1998) afirma que esse algoritmo é o mais eficiente para realizar intercalação.
Algoritmo H – Intercalação binária (do inglês, Binary Merging).
Passo 1: Caso m ou n forem zero, pare. Se m > n, faça e vá para o Passo 4. Caso contrário, faça .
Passo 2: Compare am e bn+1-2t. Se am for menor, faça e retorne para o Passo 1.
Passo 3: Usando busca binária (que requer exatamente mais t comparações), insira am em seu lugar apropriado entre {bn+1-2 t, ..., bn}. Se k for máximo tal que bk < am, faça e . Retorne ao Passo 1.
Passo 4: (Os passos 4 e 5 são semelhantes aos passos 2 e 3, invertendo os papéis de m e n, assim como a e b.) Se bn < a m+1-2 t, faça e retorne ao Passo 1.
Passo 5: Insira bn em seu lugar apropriado entre A. Se k for máximo tal que ak < bm faça e . Retorne ao passo 1.
Exemplo 10: Para exemplificar o algoritmo de intercalação binária (KNUTH, 1998), será mostrado o processo de intercalação da lista {087, 503, 512} com {061, 154, 170, 275, 426, 509, 612, 653, 677, 703, 765, 897, 908}.
1ª iteração
Passo 1: m = 3 e n = 13 m < n. Então,
.
Passo 2: a3 = 512 e b10 = 703 a3 < b10. Então,
.
Saída: 703 765 897 908.
2ª iteração
Passo 1: m = 3 e n = 9 m < n. Então,
.
Passo 2: a3 = 512 e b8 = 653 a3 < b8. Então,
.
Saída: 653 677 703 765 897 908.
3ª iteração
Passo 1: m = 3 e n = 7 m < n. Então,
.
Passo 2: a3 = 512 e b6 = 509 a3 > b6. 
Passo 3: Inserir am entre bk e bn, e n = 7, então a3 será inserido entre a6 e a7. 
- Ajusta-se: , 
Saída: 512 612 653 677 703 765 897 908.
E assim sucessivamente até todos os elementos estarem ordenados em uma sequência única, como mostra a Tabela 6. Os elementos comparados em cada etapa estão em negrito na tabela.
Tabela 6: Exemplo de intercalação binária (KNUTH, 1998).
Seja H(m,n) o número máximo de comparações requeridas pelo algoritmo H, de intercalação binária.
	Hwang e Lin provaram que 
. (3.3)
Este algoritmo, já descrito, nem sempre dá resultados ótimos, mas tem facilidade na implementação. 
Aplicando a Equação 3.3 ao exemplo descrito na Tabela 6, tem-se:
Pela Equação 3.2 o número mínimo de comparações necessárias para realizar a fusão das duas listas do exemplo é
.
Que contradiz as oito comparações que foram realizadas na Tabela 6. Isso se explica pela estrutura do algoritmo de intercalação binário. Como já foi citado, o algoritmo de intercalação comporta-se de maneira diferente dependendo dos valores de m e n, se m = 1 ele transforma-se em um algoritmo de inserção, assim, para o exemplo, a estrutura do algoritmo possibilitou um número comparações menor que o número estimado pelas equações 3.2 e 3.3 (LIMA, 2007).
CFI Para Fontes Binárias
Nesta seção será tratado o esquema de codificação de entropia baseada no algoritmo de intercalação binária de Hwang e Lin (HWANG e LIN, 1972) (HWANG e LIN, 1971) citado na seção anterior. 
A principal ideia deste codificador é a codificação de uma sequência de símbolos ordenando-os e fundindo-os numa sequência única (algoritmo de Merge). No caso mais simples, tem-se uma fonte discreta S emitindo sequências de símbolos de um alfabeto binário, A= {0, 1}, em que serão realizadas as comparações com as posições relativas de cada símbolo emitido pela fonte S. Será utilizado um exemplo para ilustrar esse agrupamento de posições dos símbolos.
Exemplo 11: (LIMA, 2007) Considere uma fonte binária qualquer E (A={0, 1}), em que é observada uma sequência de comprimento 42 emitida. Assim, considere que a sequência S observada na saída da fonte binária é
S= 000000000001000000000010000000100000000001,
de comprimento |S|=42.
Sendo característica comum a todos os codificadores estáticos, a primeira etapa do codificador proposto é contar a quantidade de “0” e “1” da fonte E. Seja m a quantidade de símbolos “0” e n a de símbolos “1”, tem-se que m = 38 e n = 4. A primeira etapa da codificação é dividir a sequência de entrada S em duas outras sequências, A e B, em que A contém as posições dos símbolos “0” e a sequência B contém as posições do símbolo “1”, como mostrado na Figura 5.
Figura 5: Sequência S de comprimento |S|=42 separada em dois conjuntos A e B,de acordo com os respectivos símbolos emitidos por uma fonte binária.
Algoritmo de Codificação de Fonte com Intercalação Binária – CFIB
Nesta seção será mostrado o Algoritmo de Codificação de Fonte com Intercalação Binária (CFIB).
Algoritmo de Codificação de Fonte com Intercalação Binária 
Passo 0: Inicializar i=0 e j=1.
Passo 1: Caso m e n forem zero, parar. Se m > n, fazer e ir para o Passo 4. Senão faça.
Passo 2: Verificar se existe um bit 1 entre os 2t próximos bits, para isso comparar ai com bj, em que . Se ai > bj, não existe um bit 1.
- Emitir 0;
- Ajustar ;
- Retornar ao Passo 1.
Passo 3: Caso contrario, usando a busca binária (que requer exatamente mais t comparações), localizar ai em seu lugar apropriado entre B (localizando a posição do bit 1), ou seja, achar k máximo tal que ak < bj entre os 2t bits e :
- Emitir 1;
- Informar a posição k do bit 1, emitindo a posição k em representação binária (B2(k)).
- Ajustar: , , e ;
- Retornar ao Passo 1.
Passo 4: (Os passos 4 e 5 são semelhantes aos passos 2 e 3, invertendo os papéis de m e n, assim como A e B.) Verificar se existe um bit 1 entre os 2t próximos bits, para isso comparar ai com bj, em que . Se bj > ai, não existe um bit 1:
- Emitir 0;
- Ajustar: ;
- Retornar ao Passo 1.
Passo 5: Caso contrário, localizar bj em seu lugar apropriado entre A (em que posição está o bit 1), ou seja, achar k máximo tal que bk < ai entre os 2t bits e:
- Emitir 1;
- Informar a posição k do bit 1, emitindo a posição k em representação binária (B2(k));
- Ajustar: , , ;
- Retornar ao Passo 1.
Será utilizado o Exemplo 12 para ilustrar a utilização do algoritmo citado.
Exemplo 12: (LIMA, 2007) Considere a fonte binária do Exemplo 11, assim como a etapa de codificação, divide-se a sequência de entrada S em duas outras sequências, A e B, em que cada uma contém as posições dos símbolos da sequência S para uma fonte binária. A sequência A contém as posições do símbolo 0 e a sequência B contém as posições dos símbolo 1, como mostrado no exemplo anterior.
Para a segunda etapa, aplica-se o algoritmo CFIB. Sabe-se que m = 38 e n = 4. Assim faça, i = 0 e j = 0, logo se tem:
Inicializar i = 0 e j = 1.
Iteração 1.
m = 38 e n = 4 m > n. Então,
Verificar se existe um bit 1 entre os 23 = 8 próximos bits.
Como e j = 1, tem-se b1 > a8, 12 > 8, logo não existe, assim:
- Emitir 0 e ajustar ;
Saída: 0.
Iteração 2.
m = 30 e n = 4 m > n. Então,
Verificar se existe um bit 1 entre os 22 = 4 próximos bits.
Como e j = 1, tem-se b1 < a12, 12 < 13, logo existe, assim:
- Emitir 1 e informar qual a posição do bit 1 entre os 22 bits, ou seja, a posição k = 3; assim emitindo B2(3) = 11;
- Ajustar: , , e .
Saída: 0111.
Iteração 3
m = 27 e n = 3 m > n. Então,
Verificar se existe um bit 1 entre os 23 = 8 próximos bits.
Como e j = 2, tem-se b2 > a19, 23 > 20, logo não existe, assim:
- Emitir 0 e ajustar .
Saída: 01110.
Continua-se o processo até que m = 0 e n = 0.
Ao final a sequência na saída será 011101101111001, com 15 bits, ocorrendo 15 comparações. O número máximo teórico de comparações é definido pela Equação 3.3, onde se tem:
Para decodificar esta sequência, é necessário que o codificador informe, além da sequência de saída, o comprimento de A ou de B, que é um número inteiro, visto que já se tem conhecimento do comprimento da sequência de entrada S. Então, serão acrescentados bits, antes da sequência codificada, que indicarão o comprimento de A ou B, e que poderá ser representado por qualquer esquema de codificação de números inteiros. Para este exemplo foi utilizado o código Fibonacci de Capocelli C(3) (LIMA, 2007), ou seja a representação do comprimento de B será BC(3)(4) = 01011 e a sequência emitida para decodificação será
E= 01011011101101111001.
Algoritmo de Decodificação de Fonte com Intercalação Binária – DFIB
O processo de decodificação segue o processo inverso ao do algoritmo CFIB. Se considerarmos uma sequência de entrada E’ da forma:
E’ = e’1 e’2 e’3...,
onde os valores de m e n são conhecidos.
	Algoritmo de Decodificação de fonte com Intercalação Binária – DFIB
Passo 0: Inicializar i = 1.
Passo 1: Caso m e n forem zero, parar. Se , e vai para o Passo 4. Senão, .
Passo 2: observar o i-ésimo bit na sequência de entrada. Se for zero:
- Emitir 2t bits 0;
- Ajustar;
- Retornar ao Passo 1.
Passo 3: Caso contrário,
- Observar os próximos t bits da sequência de entrada, que estão na representação na base 2 e representam a posição do bit 1 na sequência de saída;
	- Assim, emitir o valor da posição na representação unária, ou seja, BUnário (k);
	- Ajustar , e ;
	- Retornar ao Passo 1.
Passo 4: (Os passos 4 e 5 são semelhantes aos passos 2 e 3, invertendo os papéis de m e n, assim como A e B.) Observar o i-ésimo bit na sequência de entrada, se for 0:
- Emitir 2t bits 0;
- Ajustar ;
- Retornar ao passo 1.
Passo 5: Caso contrário,
- Observar se os próximos t bits da sequência de entrada, que estão na representação na base 2 e representam a posição do bit 1 na sequência de saída;
- Assim, emitir o valor da posição na representação unária, BUnário(k);
- Ajustar , e ;
- Retornar ao Passo 1.
Segue um exemplo da aplicação deste algoritmo na decodificação de uma sequência de entrada.
Exemplo 13: (LIMA, 2007) Inicialmente, considere a sequência de entrada E = 01011011101101111001. É conhecido que a sequência decodificada terá comprimento d = 42 e decodificando os primeiros bits da sequência E, ou seja 01011, sabe-se que . Eliminando os bits iniciais de indicação de n, tem-se:
E’ = 011101101111001.
Então:
Inicializar i = 0.
Iteração 1.
- Como 38 > 4, ;
- Observar o bit na posição , i.e, , na sequência E’, i.e., e’1;
- Como e’1 = 0:
	- Emitir 23 bits 0, assim a saída é 00000000;
	- Ajustar: .
Iteração 2.
- Como 30 > 4, ;
- Observar o bit na posição , i.e, , na sequência E’, i.e., e’2;
- Como e’2 = 1:
	- Observar os próximos t = 2 bits da sequência de entrada, a fim de localizar a posição do bit 1 entre os bits 0, i.e., que representa o número 3 na representação na base 2. Logo, o bit 1 está na posição 3 na sequência de saída.
	- Assim, emitir o valor da posição na representação unária, i.e., Bunário(3) = 0001. Assim, a saída é 00000000 0001.
	- Ajustar , e .
Iteração 3.
- Como 27 > 4, ;
- Observar o bit na posição , i.e, , na sequência E’, i.e., e’5;
- Como e’5 = 0:
	- Emitir 23 bits 0. Assim, a saída é 00000000 0001 00000000;
	- Ajustar .
Faz-se quantas Iterações forem necessárias até que m = 0 e n = 0. Quando isto ocorrer tem-se na saída
E = 00000000 0001 00000000 001 00000001 001.
Capítulo 3 – Códigos de Fonte 
55
Capítulo 4
Testes e Resultados
Neste capitulo, serão realizados testes para avaliar o desempenho do algoritmo CFIB em comparação ao Código Aritmético. Será mostrada a metodologia utilizada nos testes de comparação e os seus resultados.
Embora os testes realizados não caracterizem de forma definitiva o CFIB, os resultado indicam uma real possibilidade do uso desta para a construção de codificadores de baixa redundância (LIMA, 2007).
Metodologia
Para avaliar o desempenho do CFIB será feita uma comparação com o codificador aritmético descrito por Mohoney (MAHONEY), que é um método de codificação aritmética de ordem zero, foi modificado para ser estático, codificar fontes binárias e não ter acesso a disco, todo acesso a dados será realizado diretamente na memória do computador, para que não houvesse a influência do disco, latência de acesso, etc. Esta estratégia também foi utilizada para o CFIB.
Foram aplicadas algumas das principais coleções de arquivos, que possuem características diferentes em cada um deles e são utilizados como padrão para avaliação de desempenho de algoritmos de compressão. Cada arquivo é considerado uma fonte binária, para este caso, uma fonte de entropia binária. Escolheu-se as seguintes coleções (Corpora):
Calgary Corpus (The Canterbury Corpus, 2001);
Canterbury Corpus (The Canterbury Corpus, 2001);
ArtificialCorpus (The Canterbury Corpus, 2001);
Large Corpus (The Canterbury Corpus, 2001);
Miscellaneous Corpus (The Canterbury Corpus, 2001);
CCITT Corpus (C.C.I.T.T. Et Télégraphic).
As comparações consistem em contrastar e analisar os seguintes parâmetros de desempenho:
Redundância, em bits/símbolos;
Tempo total de execução, que é o tempo gasto para a compactação e/ou descompactação, em milissegundos;
Tempo de execução por símbolo, que é o tempo gasto para compactação e/ou descompactação de cada símbolo, em segundos/símbolos.
Os testes foram realizados em computadores com as seguintes configurações: Processador Pentium 4 de 3.2GHz, 512MB de memória RAM e sistema operacional Microsoft Windows XP. Utilizou-se o aplicativo Visual Studio C/C++2005® , ambiente de desenvolvimento de programas C/C++, para compilação dos codificadores, CFIB e Aritmético estático, implementados na linguagem em C/C++.
Análises e Resultados
Cada um dos dois métodos foi executado sobre cada arquivo da base de dados, onde foi medido o número de símbolos (símbolos 0 e 1), número de ocorrências dos símbolos, a entropia associada ao arquivo, total de bits teórico necessários para representação do arquivo, tamanho do arquivo comprimido (bits), redundância (bits/símbolo), tempo total de execução do arquivo (milissegundos) e tempo de execução por símbolos (nanossegundos/símbolos).
Para coleções de Arquivos Calgary Corpus (The Canterbury Corpus, 2001), em que foram analisados 26.011.944 símbolos em vários arquivos de diferentes distribuições de probabilidades. A CFIB apresentou redundância média de 0,01464 bits/símbolo e redundância mínima de 0,00404 bits/símbolo no arquivo chamado paper3, tempo total de codificação para esta coleção de 234 milissegundos e tempo de execução médio por símbolo de 9,00 nanossegundos/símbolos. Enquanto o codificador aritmético apresentou redundância média de 0,000004 bits/símbolo, tempo total de codificação da coleção de 1096 milissegundos e tempo médio de execução por símbolo de 42,13 nanossegundos/símbolos. Apesar do valor da redundância média do CFIB ter um valor acima do da codificação aritmética, o CFIB apresenta um tempo médio de execução por símbolo quase 5 vezes menor. Os resultados são mostrados na Tabela 7.
	Tabela 7: Arquivos da Base de Dados Calgary Corpus. Entropia expressa em bits/símbolo o Total Teórico em bits, o Comprimento Total em bits, a Redundância em bits/símbolo, o Tempo Total em milissegundos e o Tempo por Símbolo em nanossegundos/símbolo.
Para as coleções de arquivos Canterbury Corpus (The Canterbury Corpus, 2001), em que foram analisados 22.486.272 símbolos em vários arquivos de diferentes distribuições de probabilidades, em particular, o arquivo kennedy.xls foi comprimido a uma taxa média de 12,43 MB/s e decodificado a uma taxa média de 15,83 MB/s com o CFIB. A redundância média para este codificador foi 0,01524 bits/símbolo e apresentou redundância mínima de 0,00056 bits/símbolo no arquivo chamado cp.html. Enquanto no codificador aritmético o valor da redundância média foi bem inferior ao do CFIB, porém o tempo de execução total é 4 vezes maior. Este fato pode ser observado naTabela 8. 
Nota-se que em alguns casos o tempo de execução foi igual a zero, isto se deve a erros de aproximação gerados pelo uso da linguagem C/C++. No arquivo pic, nota-se que, apresentando uma característica desbalanceada entre os símbolos “0” e “1”, apresentou maior redundância após a codificação. Este fato é explicado pela natureza do Algoritmo de Intercalação Binária, já comentado em seções anteriores, pois o algoritmo reduz ao procedimento de intercalação usual para fontes balanceadas (m ≈ n, número de símbolos aproximadamente iguais).
As Tabela 9, Tabela 10 , Tabela 11 e Tabela 12 mostram os resultados dos testes para as coleções de arquivos Artificial Corpus (The Canterbury Corpus, 2001), Large Corpus (The Canterbury Corpus, 2001), Miscellaneous Corpus (The Canterbury Corpus, 2001) e CCITT Corpus (C.C.I.T.T. Et Télégraphic), respectivamente.
Para as coleções de arquivos Artificial Corpus, conforme mostrado na Tabela 9, vê-se que o codificador aritmético devido à insuficiência de símbolos no arquivo a.txt realizou a expansão do mesmo, ao contrario da compressão pretendida. Para esta coleção o CFIB foi mais eficiente em relação a velocidade, sendo quase 10 vezes mais rápido que o codificador aritmético.
Para as coleções de arquivos Large Corpus, mostrado na Tabela 11, tem-se uma redundância nula para o arquivo e.coli, devido a m ≈ n , levando o CFIB ao seu funcionamento ótimo.
Para as coleções de arquivos Miscellaneous Corpus, conforme a Tabela 10, tem-se o resultado em que foi analisado um arquivo com os primeiros 1 milhão de dígitos do número π, pi.txt, onde o codificador aritmético mostrou uma redundância com valor inferior ao CFIB, porém teve um tempo de execução por símbolo quase dez vezes maior.
Para as coleções de arquivos CCITT Corpus, com resultados mostrados na Tabela 12, obtém-se redundância média de 0,00121 bits/símbolo, em particular para os arquivos chamados baboon e bridge apresentando redundância negativa, codificando abaixo do limite de entropia. Isto é possível, devido à estrutura do algoritmo de intercalação binária, que dependendo dos seus valores de m e n (0’s e 1’s), opera com menor número de comparações do que o limite estipulado no capítulo anterior. Para esta coleção, a CFIB teve um tempo médio de execução por símbolo cerca de cinco vezes mais rápido que o codificador aritmético. Observa-se também um alto valor de redundância no arquivo ccitt44.pbm, que pode ser explicada pelo algoritmo de intercalação binária de Hwang e Lin (HWANG e LIN, 1972) nem sempre apresentarem resultados ótimos.
Um dos pontos principais no processo de compressão de dados é o tempo gasto na compressão/descompressão. A Tabela 13 mostra o tempo gasto em compressão/descompressão da coleção de arquivos CCITT Corpus para os dois métodos em questão, o CFIB e o aritmético, tempo já calculado pelo algoritmo em que foram implementados os codificadores. Analisando esta tabela pode-se notar que o CFIB é mais rápido que o aritmético na codificação/ decodificação, e apresentou uma redundância média de 1%.
Sendo assim, os resultados foram uniformes em todas as condições testadas, ou seja o CFIB mostrou desempenho superior à codificação aritmética estática em todos os arquivos testados, havendo uma mínima perda na eficiência da compressão. Enquanto o codificador aritmético apresenta redundância quase nula, o CFIB apresenta em média 1% de redundância conforme a Tabela 14 porém o tempo gasto para realizar a codificação/decodificação do codificador aritmético é muito maior que o gasto no CFIB, como mostrado na Tabela 15.
.
Tabela 8: Arquivos da Base de Dados Canterbury Corpus. Entropia expressa em bits/símbolo, o Total Teórico em bits, o Comprimento Total em bits, a Redundância em bits/símbolo, o Tempo Total em milissegundos e o Tempo por Símbolo em nanossegundos/símbolo.
			Tabela 9: Arquivos da Base de Dados Artificial Corpus. Entropia expressa em bits/símbolo, o Total Teórico em bits, o Comprimento Total em bits, a Redundância em bits/símbolo, o Tempo Total em milissegundos e o Tempo por Símbolo em nanossegundos/símbolo.
								Tabela 10: Arquivos da Base de Dados Miscellaneous Corpus. Entropia expressa em bits/símbolo, o Total Teórico em bits, o Comprimento Total em bits, a Redundância em bits/símbolo, o Tempo Total em milissegundos e o Tempo por símbolo em nanossegundos/símbolo.
Tabela 11: Arquivos da Base de Dados Large Corpus. Entropia expressa em bits/símbolo, o Total Teórico em bits, o Comprimento Total em bits, a Redundância em bits/símbolo, o Tempo Total em milissegundos e o Tempo por Símbolo em nanossegundos/símbolo.
Tabela 12: Arquivos da Base de Dados CCITT Corpus. Entropia expressa em bits/símbolo, o Total Teórico em bits, o Comprimento Total em bits, a Redundância em bits/símbolo, o Tempo Total em milissegundos e o Tempo por símbolo em nanossegundos/símbolo.Tabela 13: Arquivos da base de dados CCITT – codificação e decodificação. Total Teórico expresso em bits, Tempo Total em milissegundos e Tempo por símbolo em nanossegundos/símbolo.
Tabela 14: Valores médios dos testes realizados para as coleções de arquivos.
Tabela 15: Ganhos dos valores médios dos testes realizados para as seis coleções de arquivos.
	Coleção
	Número de símbolos 
	Ganho
	
	
	Codificador
	Decodificador
	Calgary
	26.011.944
	4,68
	4,75
	Canterburry
	22.486.272
	3,75
	4,72
	Artificial
	2.400.008
	7,80
	-
	Large
	89.275.856
	6,52
	5,34
	Miscellaneous
	8.000.000
	7,64
	6,32
	CCITT
	51.676.312
	5,03
	3,79
Capítulo 4 – Testes e Resultados 
Capítulo 5
Conclusão e Trabalhos Futuros
Neste capítulo tem-se a apresentação das conclusões após a realização dos testes e analise dos seus resultados, assim como a apresentação de sugestões para continuidade deste estudo em trabalhos futuros.
Conclusões
O codificador de fonte procura reduzir ao máximo a informação redundante no sinal de forma a ser utilizado o menor número de bits na representação sem perder informação significativa. Embora existam alguns métodos de codificação eficientes, há uma necessidade de se buscar novos métodos que otimizem cada vez mais as compressões.
A TV digital é um exemplo da aplicação de codificação de fonte, que é responsável pela conversão e compressão dos sinais de áudio e vídeo em feixes denominados de fluxos elementares de informação. No codificador a entrada será o sinal digital não comprimido, será realizada a compressão e gerado como saída um fluxo elementar de informação que é fornecido ao multiplexador do sistema. Na recepção, a entrada do decodificador será este fluxo elementar, será realizada sua decodificação e disponibiliza para apresentação o sinal comprimido. Então, nesse processo de codificação/decodificação gera um atraso na transmissão, principalmente quando comparado à transmissão analógica. Porém, mesmo com o atraso as imagens chegam bem mais nítidas e o áudio com melhor definição. Para este exemplo, tem-se necessidade de buscar formas de codificação de fonte que mantenham a qualidade o melhor possível, mas que diminuam este tempo gastos em codificação/decodificação, minimizando o “delay” da transmissão/recepção.
Então na comparação das codificações aritmética e CFIB, obteve-se pontos positivos para a CFIB. Mesmo apresentando um valor de redundância de 1% esta codificação apresenta uma maior eficiência com taxas médias de codificação de 25,71 MB/s e de decodificação de 23,65 MB/s. Indicando que a CFIB é um esquema de codificação de fonte que tem potencial para competir com codificações já existentes em situações reais, como no caso da TV digital citado.
Trabalhos Futuros
O estudo dos codificadores de fonte é uma área em que ainda se tem muito a estudar, sendo muito promissora.
Como sugestões para continuidade do estudo de codificadores de fonte com intercalação, tem-se:
- CFI para Fontes D-Árias
A estratégia utilizada para estende o codificador com intercalação para fontes D-Árias é realizar D - 1 codificações de fontes binárias. Mais especificamente seria agrupar as posições dos símbolos de uma sequência com D símbolos distintos em D conjuntos linearmente ordenados e, em seguida, fundi-los dois a dois formando uma hierarquia até que reste apenas um conjunto (LIMA, 2007).
- CFI para Fontes de Markov
As fontes Markovianas são aquelas que a geração de um símbolo depende da geração dos símbolos anteriores. A importância de uma cadeia de fonte de Markov está em que se um símbolo é um evento futuro, então a probabilidade condicional deste evento dada à história passada depende somente do passado imediato e não do passado distante (LIMA, 2007).
A estratégia para estender o codificador com intercalação binária pra fontes de Markov é semelhante as fontes D-Árias. Onde serão realizadas 2m codificações de fontes binárias. Será agrupado as posições dos símbolos de uma sequência com m símbolos anteriores (memória) iguais e, em seguida, serão agrupados em uma única sequência, não sendo necessária a hierarquia.
Outras sugestões das muitas existentes são:
Investigação do comportamento assintótico da Codificação de Fonte com Intercalação;
Investigação do comportamento da Codificação de Fonte com Intercalação na compressão de dados, como arquivos de imagens ou arquivos de texto;
Utilizar outros algoritmos de intercalação na construção de outros codificadores;
Capítulo 5 – Conclusões e Trabalhos Futuros
Aplicação deste tipo de codificação em situações reais.
Plan1
	A	B	Saída
	087	503	512	061	154	170	275	426	509	612	653	677	703	765	897	908
	087	503	512	061	154	170	275	426	509	612	653	677	703	765	897	908
	087	503	512	061	154	170	275	426	509	612	653	677	703	765	897	908
	087	503	512	061	154	170	275	426	509	612	653	677	703	765	897	908
	087	503	061	154	170	275	426	509	512	612	653	677	703	765	897	908
	087	503	061	154	170	275	426	509	512	612	653	677	703	765	897	908
	087	061	154	170	275	426	503	509	512	612	653	677	703	765	897	908
	087	061	154	170	275	426	503	509	512	612	653	677	703	765	897	908
	061	087	154	170	275	426	503	509	512	612	653	677	703	765	897	908
Plan2
Plan3
Plan1
	A	B	Saída
	087	503	512	061	154	170	275	426	509	612	653	677	703	765	897	908
	087	503	512	061	154	170	275	426	509	612	653	677	703	765	897	908
	087	503	512	061	154	170	275	426	509	612	653	677	703	765	897	908
	087	503	512	061	154	170	275	426	509	612	653	677	703	765	897	908
	087	503	061	154	170	275	426	509	512	612	653	677	703	765	897	908
	087	503	061	154	170	275	426	509	512	612	653	677	703	765	897	908
	087	061	154	170	275	426	503	509	512	612	653	677	703	765	897	908
	087	061	154	170	275	426	503	509	512	612	653	677	703	765	897	908
	061	87	154	170	275	426	503	509	512	612	653	677	703	765	897	908
tabela 4.1
	Arquivos	Número de símbolos	Número de Ocorrências	Entropia (bits/simb.)	Total Teórico (bits)	Comprimento Total (bits)	CFIB	C. F. Aritmética
	0	1	Redundância (bits/simb.)	Tempo Total (milissegundos)	Tempo por Simbolo (nano segundos/simb.)	Redundância (bits/simb.)	Tempo Total (milissegundos)	Tempo por Simbolo (nano segundos/simb.)
	bib	890,088	508,394	381,694	0.985334	877,034	890,088	0.01488	15	16.85	0.000007	47	52.80
	book1	6,150,168	3,384,401	2,765,767	0.992689	6,105,204	6,150,160	0.00736	47	7.64	0.000000	266	43.25
	book2	4,886,848	2,672,411	2,214,437	0.993655	4,855,841	4,886,848	0.00639	47	9.61	0.000001	219	44.81
	geo	819,200	587,678	231,522	0.858996	703,690	719,568	0.02257	0	0.00	0.000010	47	57.37
	news	3,016,872	1,673,681	1,343,191	0.991326	2,990,704	3,016,872	0.00875	16	5.30	0.000003	140	46.40
	obj1	172,032	112,666	59,366	0.929604	159,922	166,080	0.03851	16	93.00	0.000038	16	93.00
	obj2	1,974,512	1,153,633	820,879	0.979415	1,933,867	1,974,120	0.02081	15	7.59	0.000003	78	39.50
	paper1	425,288	234,237	191,051	0.992549	422,119	425,288	0.00751	15	35.27	0.000021	16	37.62
	paper2	657,592	356,872	300,720	0.994734	654,129	657,592	0.00529	15	22.81	0.000011	32	48.66
	paper3	372,208	200,001	172,207	0.995974	370,709	372,208	0.00404	0	0.00	0.000008	16	42.98
	paper4	106,288	58,072	48,216	0.993788	105,628	106,288	0.00625	0	0.00	0.000038	0	0.00
	paper5	95,632	53,529	42,103	0.989678	94,645	95,632	0.01043	0	0.00	0.000032	0	0.00
	paper6	304,840	171,527	133,313	0.988634	301,375	304,840	0.01150	0	0.00	0.000030	15	49.20
	pic	4,105,728	3,788,021	317,707	0.392885	1,613,079	1,726,888	0.07056	32	7.79	0.000007	94	22.89
	progc	316,888	184,171	132,717	0.980897	310,834	316,888	0.01947	0	0.00	0.000016	16	50.49
	progl	573,168	332,233	240,935	0.981620	562,633	573,168	0.01872	0	0.00	0.000012	31	54.08
	progp	395,032	236,691	158,341	0.971435	383,748	395,032	0.02940	0	0.00	0.000010	16	40.50
	trans	749,560	431,726	317,834	0.983281	737,028	749,152	0.01645	16	21.34	0.000005	47	62.70
tabela 3
	C. F. Aritmética	Tempo por Simbolo	52.8	43.25	44.81	57.37	46.4	93	39.5	37.62	48.66	42.98	0	0	49.2	22.89	50.49