Upload
ngotram
View
215
Download
0
Embed Size (px)
Citation preview
Teoria da Informação
Ementa • Conceitos e Medidas da Informação • Modelo Fonte-Canal • Codificação da Fonte • Compressão de dados • Bases algébricas para detecção e correção de erros • Códigos de Bloco e Polinomiais • Criptografia
Bibliografia Livro Texto WELLS, RICHARD. Applied Coding and Information Theory for Engineers Livros Complementares GALLAGER. Information theory and reliable communication CSISZAR, ELIAS. Topics on Information Theory LATHI. Random Signal and Information Theory HAMMING. Coding and Information Theory BLAHUT. Principles and Practice of Information Theory
Provas • 09 de Outubro • 02 de Dezembro
A nota final será dada de acordo com a fórmula abaixo
522 21 MTPPNF ++
=
Onde NF = Nota Final Px = Prova x MT = Média dos Trabalhos
Homepage :www.ene.unb.br/juliana/cursos/teoriainf Material elaborado por Eduardo Wolsky e digitado por Rafael Oliveira em 03/07/2003
Primeira Aula 26/08/03
Imaginando uma moeda "desonesta" que tem uma probabilidade de
1/4 de cair como cara. Para um milhão de lançamentos quantos bits são necessários para transmitir os resultados?
À primeira vista acreditamos que sejam necessários 1.000.000 bits mas apenas 811.300 bits podem transmitir esta informação.
Pensando numa moeda mais viciada, com probabilidade de 1/1000 para cair cara, podemos enviar estas informações de várias maneiras possíveis. Eis algumas idéias:
a) Enviar somente o número do lançamento onde deu cara 20 bits por número x 1000 = 20.000 bits
b) Enviar o número relativo do lançamento onde deu cara 12 bits por número x 1000 = 12.000 bits
"Quanto menor a incerteza menor a quantidade de informação"
Imaginemos agora um dado com oito faces (D8) com as seguintes
probabilidades:
pA = 1/2 pB = 1/4 pC = 1/8
pD = 1/16 pE = 1/32 pF = 1/64
pG = 1/128 pH = 1/128
Para representar cada lançamento, como temos oito resultados,
seriam necessários três bits. Mas o número médio de bits por lançamento pode ser diminuído. Imagine a seguinte representação:
Evento Representação
A 0 B 10 C 110 D 1110 E 11110 F 111110 G 1111110 H 1111111
Em média, por lançamento, iríamos precisar de:
bits
çãorepresentanabitsdenúmeropH
Ann
98,17128
17128
1166415
3214
1613
812
411
21
=×+×+×+×+×+×+×+×=
×∑=
Sendo que esta é apenas uma representação. Outras podem ser
criadas com resultados melhores. Imagine agora como outro exemplo um dado de cinco lados (D5)
com suas respectivas probabilidades e três representações diferentes representados na tabela abaixo
Resultado Probab. Repres. A Repres. B Repres. C A 1/8 1111 11 110 B 1/8 1110 10 111 C 1/4 110 011 10 D 1/4 10 010 01 E 1/4 0 001 00
Para transmitir os resultados de um D5 seriam necessários 03 bits.
Vejamos quantos bits podemos "economizar" utilizando as representações A, B e C. Representação A
bits5,21412
413
414
814
81
=×+×+×+×+×
Representação B
bits75,23413
413
412
812
81
=×+×+×+×+×
Representação C
bits25,22412
412
413
813
81
=×+×+×+×+×
Conseguimos alcançar vários valores, mas como saber se o valor é
o menor possível? O número mínimo de bits necessários para representar os resultados pode ser obtido através da fórmula
∑=
−=j
inxx ii
ppXH 2log)(
Esta fórmula representa o valor da incerteza, só precisamos enviar
os dados que nos são incertos e a esta incerteza damos o nome de entropia cujo símbolo é H(X). Se o valor obtido for próximo ao encontrado utilizando-se a fórmula pode-se saber que a representação é boa.
Assim, no exemplo do D5 acima temos que sua entropia é de:
bits
ppXHn
xx ii
984375,10546875,00546875,009375,015625,025,0375,05,05,0
7128
17128
166415
3214
1613
812
411
21
128log128
1128log128
164log64132log
32116log
1618log
814log
412log
21
log)(
22222222
5
12
=+++++++=
+++++++=
+++++++=
−= ∑=
Vejamos agora um outro exemplo. Imagine um dado comum (D6)
honesto, ou seja, as probabilidades de cair em qualquer face são iguais e tem valor pn=1/6. O mínimo de bits necessário é:
bitsppXHn
xx ii584962501,26log
616log)( 2
6
12 ==−= ∑
=
Uma representação seria a seguinte:
Face Repres.
1 000 2 001 3 010 4 011 5 10 6 11
Que já é uma representação simplificada da óbvia. O número de bits
médio pode ser obtido simplesmente somando-se o valor de todos os bits e dividindo pelo número de possibilidades, isto é:
66,26
223333=
+++++
O valor é bastante aproximado do número mínimo de bits
necessários. Agora que obtivemos um pouco de experiência, podemos retomar o
problema da moeda cujas probabilidades estão ilustradas abaixo, assumindo que Cara = H (Head) e Coroa = T (Tail) teremos:
pH=1/4 pT=3/4
A entropia do evento é:
81127814,04log41
34log
43)( 22 =+=XH
Não podemos simplificar mais a representação de cada resultado
pois para cada um deles foi indicado um bit, 0 ou 1. Porém, podemos nos utilizar de uma outra artimanha. Agruparemos os resultados em grupos de quatro (valor escolhido arbitrariamente) e para cada um desses grupos daremos uma representação. Sabe-se que cada grupo tem uma probabilidade de ocorrer, logo, logicamente, os grupos com maior probabilidade serão representados por um menor número de bits.
Result. Probabilidade Valor Repres. A Repres. B TTTT pT ⋅ pT ⋅ pT ⋅ pT 81/256=0,316 0 0 TTTH 1000 101 TTHT 1001 100 THTT 1010 1101 HTTT
pT ⋅ pT ⋅ pT ⋅ pH 27/256=0,105
1011 1100 TTHH 110000 111000 THTH 110001 111001 HTTH 110010 111010 THHT 110011 111011 HTHT 11010 111111 HHTT
pT ⋅ pT ⋅ pH ⋅ pH 9/256=0,035
11011 1111001 THHH 111000 1111010 HTHH 111001 1111011 HHTH 111010 1111100 HHHT
pT ⋅ pH ⋅ pH ⋅ pH 3/256=0,0117
111011 1111101 HHHH pH ⋅ pH ⋅ pH ⋅ pH 1/256=0,004 1111 1111000
A representação A nos dá:
bits
bitsquatrocadaa
874023437,0
49609375,3256
14256
364256
952256
964256
2744256
811
=
=⋅
+⋅⋅
+⋅⋅
+⋅⋅
+⋅⋅
+⋅
A representação B nos dá:
bits
bitsquatrocadaa
862304687,0
44921875,3256
14256
347256
97256
965256
2724256
2723256
811
=
=⋅
+⋅⋅
+⋅
+⋅⋅
+⋅⋅
+⋅⋅
+⋅
Segunda Aula 28/08/03 Modelo Fonte/Canal
Dados x Informação x Conhecimento
• Os dados são qualquer fluxo entre fonte e destino • A Informação está associada ao processo da informação • O Conhecimento está associado ao processamento da informação
Tipos de Fontes Fonte Contínua: Associada ao sinal analógico Fonte Discreta: Associada ao sinal digital, transmite símbolos de um alfabeto fonte.
Alfabeto Uma fonte discreta possui um número finito de símbolos únicos. O
conjunto de símbolos é chamado de alfabeto-fonte. Exemplo 1 O conjunto das letras maiúsculas
A = {A, B, C, D,... Z} Exemplo 2 O conjunto das letras maiúsculas, minúsculas e numerais.
A = {A, B, C,... X, Y, Z, a, b, c,... x, y, z, 0, 1, 2,... 7, 8, 9}
O número de elementos de um alfabeto A é chamado de cardinalidade e designado por |A|. Um alfabeto de n letras sobre A é chamado um n-grama sobre A. A partir de um alfabeto podemos gerar um novo alfabeto pela construção de n-gramas sobre o alfabeto original obtendo um alfabeto extensão.
Seja A={a0, a1, a2,... am-1} onde |A| = m. Podemos gerar A2 contendo m2 2-gramas tal que A2={a0a0, a0a1, a0a2,... am-1am-1}. Generalizando, concatenando-se n letras de A obtemos o alfabeto An contendo mn n-gramas de A. Exemplo Considere o alfabeto A = {A, B, C,... Z}
• Podemos dizer que CARRUAGEM é um 9-grama sobre o alfabeto A. Considerando o alfabeto A3 = {AAA, AAB, AAC,... ZZZ}
• Podemos dizer que CAR RUA GEM é um 3-grama sobre o alfabeto A3. Considerando o alfabeto conjunto dos meios de transporte
• Podemos dizer que CARRUAGEM é um 1-grama
Associações ZA
O Alfabeto A foi associado ao conjunto dos inteiros
A B C ... X Y Z 0 1 2 ... 24 25 26
Quantidade de Informação Hartley escreveu em 1923 o arquivo que inaugurou a “Teoria da
Informação” Shannon em 1948 descobriu que a função log pode medir a
quantidade de Informação. Suponha E1 e E2 dois eventos com probabilidades de ocorrência p1 e
p2. É de se esperar que a quantidade de informação obtida pelo conhecimento da ocorrência de ambos os eventos possa se relacionar ao conhecimento individual da ocorrência de cada evento I(E1 E2) = I(E1) + I(E2), caso E1 e E2 sejam independentes.
)(log)( 2 EpEI −=
A equação acima nos dá a medida de informação resultante da
ocorrência de um determinado evento E com probabilidade p(E).
Entropia Dada uma variável aleatória x, a qual pode assumir um número finito
de valores possíveis xi, 1 ≤ i ≤ n, com probabilidades pi associadas a cada um
destes valores, e ∑ = 1ip , denominamos de entropia, designada por H(x), a esperança matemática para a quantidade de informação contida em um evento possível qualquer.
∑=i i
i ppxH 1log)( 2
"Quanto maior a probabilidade menor a incerteza!!!"
Propriedades
(1) H(p1, p2,... pn) é máxima quando p1 = p2 = ... = pn = n1 (probabilidades
equiprováveis);
(2) Seja π uma permutação qualquer sobre {1, 2,... n}, H(p1, p2,... pn) = H(pπ(1), pπ(2),... pπ(n));
(3) H(p1, p2, ... pn) ≥ 0 (Será igual a zero quando pi = 1 – quando não houver incerteza);
(4) H(p1, p2,... pn) = H(p1, p2,... pn, 0);
(5)
+++<
11
11
11111
n,...
n,
nH
n,...
n,
nH (Ao acrescentar-se um valor, a
incerteza aumenta);
(6) H(p1, p2,... pn) deve ser função contínua dos argumentos;
(7)
+
=
n,...
n,
nH
m,...
m,
mH
mn,...
mn,
mnH 111111111 ;
(8) Seja p = p1+ p2 + ... pn e q = q1+ q2 + ... qn e p + q = 1 temos que H(p1, p2,... pn, q1, q2,... qn) = H(p, q) + pH(p1, p2,... pn) + qH(q1, q2,... qn).
Exemplo
Considere o lançamento de uma moeda tal que pcara=p e pcoroa=1-p (Neste caso representamos a entropia por h(p) ao invés de H(p, 1-p)).
Segue que h(p) = -plog2p - (1-p)log2(1-p) Assumindo que h(0)=h(1)=0 Trace o gráfico de h(p), para p variando de 0 a 1. Sabemos que o gráfico atingirá seu valor máximo quando p=0,5
(Propriedade 1), assim h(0,5) = 0,5 log22 + 0,5 log22=1, já temos o valor de h(p) em três pontos. O suficiente para construirmos o seguinte gráfico:
Exemplo 2 Qual é a entropia de uma fonte de 4 símbolos com distribuição de
probabilidade PA = {0,5; 0,3; 0,15; 0,05} ?
bits
H
647596,1
216,04105,0521,05,0
05,01log05,0
15,01log15,0
3,01log3,02log5,0)05,0;15,0;3,0;5,0( 2222
=
+++=
+++=
Terceira Aula 02/09/03
Teorema
Para ∀ inteiro positivo n de distribuição de probabilidade P={p1, p2, p3, ... pn}, temos que H(p1, p2, p3, ... pn) ≤ log2n, prevalecendo a igualdade se e
somente se nin
pi ≤≤∀= 11 .
Entropia Conjunta Seja X um vetor aleatório, X=[A, B], onde A e B são variáveis
aleatórias, assumindo um número finito de valores possíveis ai e bj, respectivamente. Então, a entropia para o vetor X pode ser escrita como:
∑ ====−==
jijiji bBaApbBaApBAHXH
,2 ),(log),(),()(
Generalizando, se X = [X1, X2, X3,... Xn] então podemos escrever:
∑−==kji
kjikjin xxxpxxxpXXXXHXH...,
2321 ),...,(log),...,()...,,()(
Teorema Se x e y são duas variáveis aleatórias que assumem um número
finito de valores, então H(x,y) ≤ H(x) + H(y) com a igualdade prevalecendo se e somente se x e y forem independentes.
Entropia Condicional A incerteza acerca de X dado que Y=y pode ser definida como:
∑ ====−==i
ii yYxxpyYxxpyYXH )|(log)|()|( 2
A entropia condicional H(X|Y) chamada equivocação de X em relação a Y, será o valor médio esperado ponderado para todas as possíveis ocorrências de Y:
∑
∑
−=
−=
jijiji
jijijij
yxpyxp
yxpyxpypYXH
,2
,2
)|(log),(
)|(log)|()()|(
Teorema )|()()|()(),( YXHYHXYHXHYXH +=+= (1)
)|()()|()(),( abpapbapbpbap == (2)
Para provar (1) sabendo de (2)
)|()(
)|()(log)(
)|(log),()(log),(
)|()(log),(
),(log),(),(
2
, ,22
,2
,2
XYHXH
XYHxpxp
yxpyxpxpyxp
yxpxpyxp
yxpyxpYXH
iii
ji jijijiiji
jijiiji
jijiji
+=
+−=
−−=
−=
−=
∑
∑ ∑
∑
∑
Basta lembrar que se somarmos todas as probabilidades conjuntas
para um dos elementos teremos a probabilidade do outro. Então, para todos os valores de j possíveis:
∑∑ =
iii
jiiji xpxpxpyxp )(log)()(log),( 2
,2
De forma análoga pode-se provar que H(Y,X)=H (Y)-H(Y|X).
Exemplo Seja A uma fonte de informação com alfabeto A = {0, 1, 2, 3}. Seja
cada símbolo an igualmente provável e seja B = {0,1} um gerador de paridade com função
====
2ou 1 se ,13ou 0 se ,0
aaaa
bj
bitsbitBAHBHABH
bitsAHABHAHBAH
bitBH
bitsAH
22log5,021)|()(),(
2)()|()(),(
122log50,0)(
244log25,0)(
2
2
2
=⋅⋅+=+=
==+=
=⋅⋅=
=⋅⋅=
H(B | A) = 0 Uma vez que a incerteza de B dado A é obviamente
zero, que pode ser comprovado matematicamente:
0log025,041log125,04)|(log)|()()|( 22,
2 ⋅⋅⋅+⋅⋅⋅== ∑ji
jijij yxpyxpypYXH
Entropia de n-gramas e a Regra da Cadeia Suponha um n-grama (s0, s1,... sn-1) produzido pela fonte A. A
entropia do n-grama é dada por H(a0, a1,... an-1), onde os argumentos at indicam
que o símbolo de índice t é uma letra de A. H(a0, a1,... an-1) = H(a0) + H(a1, a2,... an-1 | a0) Repetindo o argumento teremos
H(a0, a1,... an-1) = H(a0) + H(a1 | a0) + H(a2 | a0, a1) + ... + H(an-1 | a0,... an-2)
Este resultado é conhecido como a regra da cadeia para a entropia.
∑−
=− ≤
1
0110 )(),...,(
n
iin aHaaaH
Com a igualdade valendo se e somente se todos os símbolos na
seqüência são independentes, neste caso, fonte é dita ser sem memória. Caso contrário a fonte é dita ser com memória ou makroviana.
Exemplo
Suponha uma fonte sem memória com A = {0,1} tendo símbolos equiprováveis emitindo 6 símbolos. Seguindo o sexto símbolo, suponha que um sétimo símbolo, soma módulo 2 (XOR) dos outros seis símbolos, seja transmitido. Qual a entropia do 7-grama?
Sabemos que:
)...|()...|()...|(),,|(),|()|()()...,,(
5064053042103102010
6210
aaaHaaaHaaaHaaaaHaaaHaaHaHaaaaH
++++++=
Como a fonte é sem memória, os primeiros seis símbolos da seqüência são independentes, portanto:
)...|()()()()()()()...,,( 5065432106210 aaaHaHaHaHaHaHaHaaaaH ++++++=
Como todos os eventos são equiprováveis H é máxima e, neste caso,
necessita de um bit para ser transmitida. O último termo é zero pois não há incerteza por este ser em função dos seis primeiros que, neste caso, foram dados. Assim:
bitsaaaaH 60111111)...,,( 6210 =++++++=
Quarta Aula 04/09/03
Codificação da Fonte Um codificador de fonte é um elemento de processamento de dados
que toma como entrada um n-grama de um alfabeto-fonte A e produz como saída um m-grama do alfabeto código B. Estes m-gramas são chamados palavras-código.
BAC →:
O codificador tem como objetivos processar a entrada de tal forma
que a informação média transmitida (ou armazenada) por uso do canal aproxime-se de H(A), encontrar códigos decodificáveis univocamente, isto é, para todo elemento de A haja apenas um B e vice-versa.
abCbaC )()( 1−⇒
Um codificador também deve encontrar códigos que possam ser
decodificados instantaneamente.
Exemplo Seja uma fonte de quatro símbolos A={a0, a1, a2, a3} que possuem
probabilidades PA={0,5; 0,3; 0,15; 0,05}. Seja C um codificador que mapeia os símbolos de A em strings de dígitos binários {0, 10, 110, 111} respectivamente. Qual é o número médio de palavras por símbolo? Qual a eficiência do codificador?
Com a codificação C teríamos um número médio de palavras por símbolos
bitsn 7,105,0315,033,025,01 =⋅+⋅+⋅+⋅=
A entropia (incerteza) da fonte original é dada por:
bitsAH 6477,105,01log05,0
15,01log15,0
3,01log3,0
5,01log5,0)( 2222 =+++=
Dado que a eficiência η é dada pela entropia dividida pelo número médio
de bits temos que:
%977,1
6477,1)(===
nAHη
Somente a título de curiosidade vamos repetir o exemplo acima no caso de uma codificação {00, 01, 10, 11}, teríamos obviamente um número médio de palavras por símbolo de 2 bits e a eficiência seria, neste caso:
%4,822
6477,1)(===
nAHη
Informação Mútua A quantidade de informação que a ocorrência de um evento Y=y
fornece a respeito da ocorrência de um evento X=x é dada por:
),()|(
)(log
),()()(log
)|()(log
)]|(log[)(log)|()(),(
2
2
2
22
XYIXYp
Yp
YXpYpXp
YXpXp
YXpXpYXIXIYXI
=
−=
−=
−=
−−−=−=
O valor esperado para I(X,Y) = I(Y,X).
Teorema Dadas duas variáveis aleatórias X e Y, podemos escrever que a
informação mútua ligando as duas variáveis será dada por:
)|()()|()(
),()()(),(
XYHYHYXHXH
YXHYHXHYXI
−=−=
−+=
Códigos de Comprimento Fixo Seja a seqüência SL = α1, α2, ... αL, com αi ∈ A, 1 ≤ i ≤ L e |A| = n
podemos, portanto, ter nL L-gramas diferentes. Se quiséssemos codificar estas seqüências usando palavras-código
de comprimento Λ sobre um alfabeto B de m símbolos,
nL
nm mL log≥
Λ⇒≥Λ
Exemplo
Considere |A| = 10. Codificando cada letra da fonte em um código
binário |B| = 2 qual será o valor de Λ, considerando L = 1?
3219,3
10log1
log
2
≥Λ
≥Λ
≥Λ nL m
Como o comprimento de uma palavra código deve ser um número inteiro
(obviamente) temos que Λ = 4 bits. Se escolhermos usar menos que logmn letras-código por letra-fonte,
então precisaríamos relaxar na nossa insistência em sempre sermos capazes de decodificar a seqüência fonte a partir da palavra-código.
Considere a variável aleatória X com espaço amostral X = {x1, x2},
p(x1) = p1 = 1/3 e p(x2) = p2 = 2/3. A entropia de X é dada por
bitsXH 918,032log
32
31log
31)( 22 =−−=
Vamos repetir o experimento L vezes para obter uma seqüência de L
variáveis aleatórias independentes, distribuídas identicamente. Portanto, existem 2L seqüências possíveis. Se o número de ocorrências de x1 em um determinada seqüência é k, a probabilidade da seqüência é kk pp −− 1
11 )1( uma
vez que existem )!(!
!KLK
LKL
−=
tais seqüências, suas probabilidades totais
são KLk ppKL −−
)1( 11
É importante observar que a probabilidade de uma ocorrência para qual k é significativamente diferente de Lp1 é muito pequena. Todas as seqüências típicas são mais ou menos equiprováveis a 2-LH(X) e o número total de seqüências típicas é de 2LH(X).
Podemos observar que
I(XL) ≅ LH(X), a medida que L cresce P(XL) ≅ 2-LH(X)
O número total de tais seqüências é MT ≅ 2LH(X)
Λ ≅ LH(X) bits por palavra código
Quinta Aula 09/09/03
Teorema
Seja S uma fonte sem memória de entropia H(S) e seja B um código de comprimento Λ sobre um alfabeto de m símbolos. Se pe é a probabilidade de ocorrência de uma seqüência de comprimento L da fonte não coberta pelo código então para qualquer δ > 0, se
msH
L 2log)( δ−
≥Λ
pe pode ser feito tão pequena quanto se queira.
I(BΛ)=I(SL)=LH(S)
Códigos de Comprimento Variável Seja uma fonte discreta sem memória A={a1, a2, ... an} com p(ai) = pi,
1 ≤ i ≤ n. Queremos codificar cada letra da fonte usando uma seqüência de letras de um alfabeto-código B={b1, b2,... bm} com |B|=m. Seja λ o comprimento da palavra-código utilizada para codificar a i-ésima letra de A, o comprimento médio das palavras-código será
∑=
=n
iiip
1λλ
Considere, por exemplo, um alfabeto-fonte de 4 símbolos com as
probabilidades mostradas na tabela abaixo, bem como quatro exemplos de codificação.
Letra p(ai) Cód. I Cód. II Cód. III Cód. IV
a1 0,5 0 0 0 0 a2 0,25 0 1 10 01 a3 0,125 1 00 110 011 a4 0,125 10 10 111 0111
É importante ressaltar que os códigos I e II não são univocamente
decodificáveis. Com os dados da tabela é possível calcular o comprimento médio das palavras-código:
Código I bits125,125,0125,025,05,02125,01125,0125,015,0 =+++=⋅+⋅+⋅+⋅=λ
Código II
bits25,125,025,025,05,02125,02125,0125,015,0 =+++=⋅+⋅+⋅+⋅=λ
Código III
bits75,1375,0375,05,05,03125,03125,0225,015,0 =+++=⋅+⋅+⋅+⋅=λ
Código IV
bits75,1375,0375,05,05,03125,03125,0225,015,0 =+++=⋅+⋅+⋅+⋅=λ
Código de Condição Prefixa ou Instantânea Este é o nome dado a um código quando se sabe
“instantaneamente” qual a letra do alfabeto imediatamente após a chegada do último bit referente a esta letra, não é necessário esperar pelo próximo bit.
Para quaisquer duas palavras ci e cj do código, ci não é prefixo de cj. A decodificação de um código de condição prefixa pode ser realizado por meio de uma árvore de decisão.
Abaixo temos o exemplo de uma árvore de decisão e sua respectiva tabela de codificação.
Palavra Código
a1 0 a2 10 a3 110 a4 111
Teorema da Codificação da Fonte Dada uma fonte S com entropia H(S) e um alfabeto código B com m
símbolos. Então qualquer código univocamente decodificável para esta fonte usando B terá comprimento médio cujo limite inferior é dado por:
msH
2log)(
≥λ
Além disso, existe um código instantâneo tendo comprimento médio satisfazendo:
1log
)(
2
+≤m
sHλ
Construção de Códigos de Condição Prefixa Codificação de Blocos Encurtados Seja um alfabeto fonte de n símbolos e um alfabeto-código de m
símbolos. Escolha r tal que mr ≥ n, de forma a podermos construir um código de
blocos de comprimento r capaz de representar todos os símbolos da fonte. Construa a árvore total (m1r). Elimine (mr-n) dos nós terminais
originais e encurte os nós correspondentes a estes nós, atendendo à condição prefixa.
Exemplo
Construa um código univocamente decodificável de condição prefixa supondo que n=5 e m=2 e todos os símbolos são equiprováveis.
Primeiramente temos que definir o comprimento r do código. Como mr ≥ n
assumimos que r = 3. Então construímos a árvore total conforme ilustrado abaixo.
Agora devemos eliminar mr-n dos nós que corresponde a 23-5 = 3 nós,
lembrando que os nós que levam a apenas um ramo podem ser eliminados, assim temos:
Na figura acima os nós marcados com vermelho foram os três nós
escolhidos para serem eliminados. O nó marcado de rosa pode ser eliminado porque não levava a lugar algum. E os nós marcados de verde foram eliminados porque o nó de origem levava apenas a um ramo (já se sabia que a informação era 011 quando recebemos o 0 pois nenhum outro código inicia-se com 0).
Assim podemos finalmente desenhar a árvore indicando seus símbolos e seus respectivos códigos:
Assim criamos um código univocamente decodificável e de condição pré-
fixa. Mas não há garantias que este código seja o ideal, por exemplo, se calcularmos o número médio de bits do código chegaremos ao valor de 2,6 bits (para eventos equiprováveis). Tomando aleatoriamente outros três nós para serem encurtados no
início do processo podemos obter outros números médios, por exemplo:
Desta maneira teremos um número médio de bits de 2,4, o que significa
que, para um evento equiprovável este exemplo é melhor que o primeiro.
Codificação de Huffman Vamos supor que S é uma fonte discreta, sem memória, sobre um
alfabeto de n símbolos e que C é um código C = {wi} sobre um alfabeto binário B={0,1}, 1 < i < n, cujas palavras-código tem comprimento médio λ(wi)= λ (i)
Lema
Para um alfabeto fonte com pelo menos dois símbolos, existe um código compacto onde existem pelo menos duas palavras-código que tem comprimento máximo λn=λn-1, cuja codificação é idêntica, exceto pelo último bit, que vale 1 para wn e 0 para wn-1.
Exemplo
Considere uma fonte de 5 símbolos distintos com as probabilidades associadas A={a1, a2, a3, a4, a5}, P={0,3; 0,25; 0,25; 0,1; 0,1}.
Começamos pelas duas palavras com menor probabilidade e a cada uma
associamos um bit (que será o último bit da representação). Para esse par de palavras somamos suas probabilidades e repetimos o primeiro passo, sendo as duas palavras agora representadas como uma única palavra. Assim temos a codificação de Huffman.
a1 (0,3) 0 (0,55) 0
a2 (0,25) 1 (1,00) a3 (0,25) 0 (0,45) 1 a4 (0,1) 0 (0,20) 1 a5 (0,1) 1
A codificação final deve ser “lida” de trás para frente, assim temos:
Palavra Códigoa1 0 a2 01 a3 10 a4 110 a5 111
Sexta Aula 11/09/03
Codificação Adaptativa Nem sempre a probabilidade dos símbolos da fonte são
estacionárias. Por exemplo, algoritmos de compressão de imagens são freqüentemente utilizados para comprimir tanto texto quanto imagens. Estas duas fontes de dados tem probabilidades de símbolos diferentes e estas probabilidades podem ser difíceis ou mesmo impossíveis de se obter antecipadamente. Para lidar com estes aspectos, modelos e métodos adaptativos de fonte foram desenvolvidos.
Parte-se de uma distribuição de probabilidades inicial, conforme se vai obtendo mais símbolos da fonte, vai-se atualizando a distribuição de probabilidades e a tabela de codificação. Aos símbolos com maiores contagens de ocorrências são atribuídas palavras-código curtas.
Um exemplo é codificação adaptativa de Huffman MNP5, utilizada em modems.
Codificação Preditiva Assume-se dispor de um processo para “prever” o próximo símbolo
a ser emitido pela fonte. Considere o caso binário, em que temos uma fonte S que emite símbolos pertencentes ao alfabeto A={0,1}
A fonte emite símbolos pn. Espera-se que, na maioria das vezes, o
preditor seja capaz de acertar os símbolos emitidos pela fonte. A saída será um sinal de erro en=(αn-pn) o qual será 0 se αn = pn e 1 caso contrário. Na decodificação utiliza-se o mesmo preditor utilizado na codificação que irá reproduzir as predições pn geradas na codificação, e a saída do codificador será pn + en = αn, reproduzindo a seqüência original da fonte.
O preditor pode ser fixo ou adaptativo. A saída de um bom preditor é uma seqüência altamente redundante (baixa entropia).
Códigos de Compressão Codificação Run-Lenght (Comprimento de Cadeia) Substitui-se ocorrências sucessivas de um mesmo símbolo por uma
codificação especial que indique o número de ocorrências daquele símbolo naquele ponto da mensagem.
Exemplo
ACBXXXXXXDEF pode ser codificado como ABC@X5DEF, considerando @ como caractere de escape. Observe como o número indica o número de vezes que o caractere foi repetido, isto é, no nosso caso ele apareceu uma vez e foi repetido cinco, totalizando seis vezes.
O caractere de escape deve ser escolhido com cuidado, ele deve ter uma probabilidade pequena, ou até mesmo nula, no alfabeto.
Codificação MNP Classe 5 Inicialmente, o fluxo de dados é submetido à codificação de
comprimento de cadeia. As seqüências de três ou mais caracteres repetidos são comprimidos pela inserção, após o terceiro caractere, do número de contagem de caracteres idênticos que se seguem. A contagem máxima aceita é de 255.
Em seguida é usado um procedimento adaptativo. Cada símbolo é codificado em duas partes:
• O cabeçalho de 3 bits, que indica o tamanho do corpo; • O corpo do código.
Para cada caractere há um contador. Se esse caractere aparece
mais vezes que um outro com codificação menor ele é “promovido” trocando sua codificação (como o método da bolha). Este é um ótimo exemplo de códigos adaptativos. Funciona melhor para mensagens longas.
Codificação para Fac-Símile (Fax) Cadeias de bits são codificadas em “run-lenght” e depois num
segundo nível de codificação (um código de Huffman modificado criado a partir da análise estatística de onze documentos). Este código representa cadeias de comprimentos na base 64, divididos em duas tabelas: códigos de terminação (códigos individuais que representam cadeias de comprimento até 63) e códigos de construção (representa valores múltiplos de 64).
A primeira cadeia de cada linha é sempre de brancos. É utilizado um código especial de fim de linha (EOL: End Of Line).
Exemplo
Imagine a seguinte linha (onde 0 representa branco e 1 representa preto)
63810433710
1...10...01...10...0
Como as cadeias tem comprimento na base 64 temos que representar cada cadeia como múltiplos de 64 + resto, isto é:
10 b = 0x64 + 10 37 p = 0x64 + 37 1043 b = 16x64 + 19 638 p = 9x64 + 62 Consultando as tabelas de códigos de terminação e construção,
obtemos que: 10 b = 00111 37 p = 000011010101 1043 b = 011010101 0001100 638 p = 01101000 000001100110 Acrescentando-se ao final o código de EOL (00000000001) temos:
[00111][000011010101][011010101][0001100][01101000][000001100110][00000000001]
A recomendação T4 também especifica outro tipo de codificação
padrão para equipamentos de fax do grupo 3 implementado na forma de codificação bidimensional. Após uma linha ter sido codificada normalmente, codifica-se as k – 1 linhas subseqüentes apenas com as diferenças em relação à linha de referência. k é estabelecido como 2 para resolução vertical normal e 4 para alta resolução.
Sétima Aula 16/09/03
Codificação Baseada em Dicionário Suponha um código de comprimento fixo baseado na segunda
edição do dicionário Aurélio.
1809 páginas 11 bits3 colunas 2 bits
Até 32 palavras por coluna 5 bits Apenas 18 bits são necessários para representar qualquer palavra!
Exemplo Vamos utilizar a codificação baseada em dicionário para codificar a
seguinte frase: “Um exemplo simples ilustrará melhor” Basta procurar por estas palavras no dicionário e dizer em qual
página, qual coluna e em qual palavra desta coluna a palavra aparece: “1735/3/3 740/1/19 1587/1/16 917/2/17 1207/1/1”
Construção Dinâmica do Dicionário Repita Palavra=Lê_Palavra(Entrada) // Lê a palavra da entrada Índice=Busca_Palavra(Dicionário) // Verifica no dicionário Se Índice=0 // Se não existir Escreve(Palavra,Saída) // Escreve palavra na saída Inclui(Palavra,Dicionário) // Inclui no dicionário Se não // Se existir Escreve(Índice,Saída) // Coloca o índice na saída Até Fim_Mensagem
Codificação de Lempel-Ziv Os algoritmos Lempel-Ziv comprimem pela construção de um
dicionário de seqüências previamente encontradas. Dada uma posição em um arquivo, olhe para a parte precedente do arquivo para encontrar a coincidência mais longa para a seqüência que começa na posição corrente, e gere algum código que se refira a esta coincidência.
As duas maiores variantes do algoritmo são descritas por ZIV e Lempel em dos artigos separados em 1977 e 1978 e são conhecidos por LZ77 e LZ78. O algoritmo LZ77 é a base dos formatos GZIP, ZIP, ARJ, LHA e ZOO, por exemplo, e baseia-se a idéia de janelas deslizantes. O algoritmo só procura
por coincidências numa janela de distância fixa para trás da posição corrente.
Exemplo No exemplo abaixo, a seqüência “janela” da janela futura é
codificada como 07f, significando que a seqüência inicia na posição 0 da janela de texto, tem comprimento 7 e a primeira letra após a mesma, na janela futura, é “f”.
Já o LZ78 é a base dos formatos Compress e GIF. A variante mais
utilizada é a LZW.
LZW A cada entrada do dicionário é dado um endereço m. Cada entrada
consiste num par ordenado <n, aj>, onde n é um endereço para outra entrada do dicionário (um ponteiro, que também funciona como a palavra-código a ser transmitida) e aj é um símbolo do alfabeto fonte A.
Inicialmente, para |A|=M, o algoritmo inicia pela construção das primeiras M+1 entradas no dicionário.
Endereço Entrada
0 0, null 1 0, a0 2 0, a1 ... ... M 0, aM-1
Criada a tabela, as seguintes instruções são interativamente
executadas pelo codificador:
Procure o próximo símbolo a da fonte; Se o par ordenado <n,a> já está no dicionário então n = endereço do dicionário da entrada <n,a> Se não Transmita n Crie uma nova entrada <n,a> no endereço m do dicionário m=m+1
n=endereço da entrada <0,a> do dicionário; Retorna ao início.
Exemplo
Uma fonte binária de informação emite a seqüência de símbolos 110 001 011 001 011 100 011 11 etc. Construa o dicionário de codificação e determine a seqüência de símbolos-código transmitidos.
Uma vez que a fonte é binária, o código original deverá conter somente a entrada nula e as entradas <0,0> e <0,1> nos endereços 0, 1 e 2 respectivamente. As
operações do codificador estão descritas na tabela abaixo.
Símb. n m TX Próximo n Entrada1 0 3 - 2 - 1 2 3 2 2 2, 1 0 2 4 2 1 2, 0 0 1 5 1 1 1, 0 0 1 6 - 5 - 1 5 6 5 2 5, 1 0 2 7 - 4 - 1 4 7 4 2 4, 1 1 2 8 - 3 - 0 3 8 3 1 3, 0 0 1 9 - 5 - 1 5 9 - 6 - 0 6 9 6 1 6, 0 1 1 10 1 2 1, 1 1 2 11 - 3 - 1 3 11 3 2 3, 1 0 2 12 - 4 - 0 4 12 4 1 4, 0 0 1 13 - 5 - 1 5 13 - 6 - 1 6 13 6 2 6, 1 1 2 14 - 3 - 1 3 14 - 11 -
O Dicionário do Codificador LZW é apresentado na tabela abaixo.
End. Entrada0 0, null 1 0, 0 2 0, 1 3 2, 1 4 2, 0 5 1, 0 6 5, 1 7 4, 1 8 3, 0 9 6, 0
10 1, 1 11 3, 1 12 4, 0 13 6, 1 14 ...
O decodificador, no receptor, também precisa construir um dicionário idêntico àquele do transmissor e precisa decodificar os símbolos de código recebidos. A operação do decodificador é governada pelas seguintes observações:
1. A recepção de alguma palavra-código significa que uma nova entrada de
dicionário deve ser construída; 2. O ponteiro n para esta nova entrada é o mesmo que a palavra-código
recebida; 3. O símbolo-fonte a para esta entrada ainda não é conhecido, uma vez que
ele é o símbolo raiz da próxima seqüência. Se o endereço desta entrada no dicionário é m, o decodificador só pode
construir um entrada parcial <n,?>, já que ele precisa esperar a próxima palavra-código recebida para encontrar o símbolo raiz a para esta entrada. Ele pode, entretanto, preencher o símbolo que falta a na entrada de dicionário anterior no endereço m – 1. Ele também pode decodificar a seqüência de símbolos-fonte associada com a palavra código recebida n.1
1 1 Digitado em 19/04/2003 por Rafael Oliveira
Oitava Aula 18/09/03
Codificação Aritmética O objetivo é obter efeito de codificação de bit fracionado. A
codificação aritmética começa pela atribuição, a cada elemento de A, de um subintervalo dos números reais 0 e 1. O comprimento do intervalo é igual às probabilidades dos símbolos.
O processo consiste em construir um intervalo de código que descreve unicamente um bloco de símbolos sucessivos da fonte.
Assuma que a Aai ∈ foi atribuído um intervalo Ii =[Sli, Shi]. Execute os seguintes passos:
j = 0 Lj = 0 Hj = 1 Repita ∆ = Hj - Lj Leia o próximo ai Lj+1 = Lj + ∆⋅Sli Hj+1 = Lj + ∆⋅Shi j = j + 1 até que ai tenha sido codificado
Exemplo Utilizando a codificação aritmética vamos codificar a palavra
“Compressão”. Utilizamos nos símbolos, a título de exemplo, somente as letras da palavra em questão, primeiro as vogais, depois as consoantes, em ordem alfabética. Poder-se-ia utilizar qualquer outra ordem, por exemplo, todas as letras do alfabeto e sua probabilidade de aparição na Língua Portuguesa.
Símb. Prob. Intervalo
A 0,1 [0,0; 0,1)E 0,1 [0,1; 0,2)O 0,2 [0,2; 0,4)C 0,1 [0,4; 0,5)M 0,1 [0,5; 0,6)P 0,1 [0,6; 0,7)R 0,1 [0,7; 0,8)S 0,2 [0,8; 1,0)
Símbolo Limite Inferior (Lj) Limite Superior (Hj) Delta (∆) C 0,4 0,5 0,1 O 0,42 0,44 0,02 M 0,430 0,432 0,002 P 0,4312 0,4314 0,0002 R 0,43134 0,43136 0,00002 E 0,431342 0,431344 0,000002 S 0,4313436 0,4313440 0,0000004 S 0,43134392 0,43134400 0,00000008 A 0,431343920 0,431343928 0,000000008 O 0,4313439216 0,4313439232 0,0000000016 É transmitido o último valor de Hj ou Lj. Para a decodificação utilizam-se os seguintes passos: L=0 H=1 ∆=H-L Repita Encontre i tal que
iILb∈
∆−
// Onde “b” é o código.
Mostre o símbolo ai H=L+∆⋅Shi // Os três passos seguintes são L=L+∆⋅Sli // úteis quando as probabilidades ∆=H-L // são complicadas Até que o último símbolo seja codificado
Exemplo Suponha que recebamos o código 0,4313439216, conhecendo a
tabela de intervalos vemos que o número recebido está entre 0,4 e 0,5, no intervalo do símbolo “C”.
Agora fazemos iILb∈
∆− . Sendo b o código, L o limite inferior (por
enquanto 0,4) e ∆ = H – L, no caso, 0,1 temos:
313439216,01,0
4,04313439216,0=
−
O novo b está entre 0,2 e 0,4, representando o símbolo “O” e assim por diante até obtermos a palavra completa.
Codificação do Canal
Canal de Informação É um processo estocástico ao qual temos associado:
• Um alfabeto de entrada A = {a0, a1, ... na} • Um alfabeto de saída B = {b0, b1, ... bn} • Uma distribuição de probabilidade P(B|A) que relaciona
os símbolos que saem do canal em função dos símbolos que entram.
Canal Discreto sem Memória As probabilidades atribuídas ao mesmo p(bj|ai), i=0, 1, 2, ... n e j = 0,
1, 2, ... m são independentes dos símbolos anteriores que foram transmitidos.
Canal Discreto com Memória Cada símbolo de saída pode depender não somente do
correspondente símbolo de entrada, mas também dos símbolos anteriores. É descrito por uma cadeia de Markov. Um exemplo são as máquinas de estados.
Relações do Canal Considerando um alfabeto de entrada A, com |A|=n e um alfabeto de
saída B, com |B| = m, a matriz de transição do canal P = [pij] = [p(bj | ai)], i = 0, 1, ... n-1 e j = 0, 1, ... m-1 coloca a distribuição de probabilidades do canal em forma matricial.
=
−−−−−
−
−
1|12|11|10|1
1|12|11|10|1
1|02|01|00|0
nmmmm
n
n
pppp
pppppppp
p
O somatório da coluna i corresponde à entrada ai. O somatório da linha j corresponde à entrada bj.
Como chegar nesta matriz não é o alvo do nosso curso. Vamos trabalhar sempre com a matriz sendo dada.
Exemplo
A = {0, 1} B = {x, y, z}
=
=
08,005,015,001505,08,0
|1|0
|1|0
|1|0
zz
yy
xx
pppppp
T
Repare que a soma das colunas é sempre igual a 1.
Nona Aula 23/09/03
Canal Discreto sem memória Propriedades:
1. ∑ ∑−
=
−
=
==1
0
1
0| 1)|(
m
j
m
jijij abpP
2. ∑∑∑∑−
=
−
=
−
=
−
=
==1
0
1
0
1
0
1
01),()()|(
n
i
m
jji
n
i
m
jiij bapapabp
3. Se pj|i é invariante no tempo, o canal é dito ser estacionári. 4. As distribuições de probabilidades p(bj) e p(ai) estão relacionadas pelo canal:
∑−
=
⋅=⇒=1
0|)()|()(
n
i
TAABBjiji PPPbpabpap
Exemplo
A = {0, 1} B = {b0, b1, b2}∗
=
80,005,015,015,005,080,0
|ABP
Calcule PB dado que PA é uniformemente distribuído. Sabendo que T
AABB PPP ⋅= | e uma vez que PA é uniformemente distribuído temos que:
=
++
+=
⋅
=
425,015,0425,0
4,0025,0075,0075,0
025,04,0
5,05,0
80,005,015,015,005,080,0
BP
∗ Veja que peculiar. A entrada tem cardinalidade 2 e a saída tem cardinalidade 3... É uma forma de se detectar erros, é chamado de decisão ampla ou soft decision.
Calcule agora H(A) e H(B). Como A é uniformemente distribuído sabemos que H(A) = 1. Vamos
provar através dos cálculos:
bitAH 15,0
1log5,05,0
1log5,0)( 22 =+=
Já H(B) não pode ter seu valor deduzido tão facilmente:
bitBH 464743854,1425,01log425,0
15,01log15,0
425,01log425,0)( 222 =++=
Exemplo
Considere o canal binário simétrico (CBS)
pqabpabppabpabp
PQapPap
BA
−=============
−=====
==
1)1|0()0|1()1|1()0|0(
1)1()0(}1,0{}1,0{
−
−=
pppp
T1
1
A matriz T é um exemplo de hard decision ou decisão restrita, quando
a cardinalidade de entrada é igual à cardinalidade de saída. Vamos calcular PB
PqQpabpapabpapbpPpQqabpapabpapbp
QpPqQqPp
QP
pqqp
PPP TAABB
+====+=====+====+=====
++
=
⋅
=⋅=
)0|1()0()1|1()1()1()0|0()0()1|0()1()0(
|
Sabendo que )()|()()|(),( iijjjiji apabpbpbapbap ⋅=⋅= e
conseqüentemente )(
)()|()|(
j
iijji bp
apabpbap
⋅= então...
QpPqQp
bpapabpbap
QqPpQq
bpapabpbap
QpPqPq
bpapabpbap
QqPpPp
PpQqpP
bpapabpbap
+=
==⋅==
===
+=
==⋅==
===
+=
==⋅==
===
+=
+=
==⋅==
===
)1()1()1|1()1|1(
)0()1()1|0()0|1(
)1()0()0|1()1|0(
)0()0()0|0()0|0(
“O alfabeto de saída deve ter cardinalidade maior ou igual o de entrada, senão haverá perda de informação.”
Revisando alguns conceitos
∑ ∑
∑ ∑−
=
−
=
−
=
−
=
=
=
−=−=
1
0
1
02
1
0
1
02
)()|(
log)|()(
)()|(
log)|()(
)|()()|()(),(
n
i
m
j i
jijij
n
i
m
j j
ijiji
apbap
bapbp
bpabp
abpap
ABHBHBAHAHBAI
Exemplo
canal do bits/uso 57566,0425,005,0log05,0
51,015,0log51,0
425,08,0log8,025,0
)()|(
log)|()(),(
]5,05,0[
]425,0150,0425,0[8,005,0
15,015,005,08,0
222
1
0
1
02
|
=
++⋅=
=
=
=
=
∑ ∑−
=
−
=
n
i
m
j j
ijiji
A
B
AB
bpabp
abpapBAI
P
P
P
Capacidade do Canal A informação mútua I(A,B) conecta as duas portas do canal e pode
ser interpretada como a informação transmitida pelo canal. Traduz a diferença
da incerteza sobre a fonte antes e depois da transmissão, portanto, a informação transmitida pelo canal depende da distribuição de probabilidades de A que é PA.
A Capacidade do canal é dada por:
),()( BAIApMAXC ⋅=
Canais Simétricos Toda coluna de PB|A é uma permutação da primeira coluna. Toda linha de PB|A é uma permutação da primeira linha. Para canais simétricos, a capacidade é atingida quando p(a) é
uniformemente distribuída.
Décima Aula 25/09/03
Exemplo 1
Calcule a Capacidade do QPSK (Phase Shift Key) considerando |A|=|B|=4.
=
950,0024,0024,0002,0024,0950,0002,0024,0024,0002,0950,0024,0002,0024,0024,0950,0
|ABP
Sabemos que ),()( BAIApMAXC ⋅= e sabemos que a capacidade é
atingida quando p(A) for uniformemente distribuída, o que significa que: PA = [0,25 0,25 0,25 0,25] Calculando PB temos que: PB = [0,25 0,25 0,25 0,25] Logo:
66,1]01,016,083,1[125,0
002,0log002,025,0
024,0log024,0225,0
950,0log950,025,04
)()|(
log)|()(),(
222
3
0
3
02
≅−−⋅=
+⋅+⋅⋅=
=∑ ∑
= =i j j
ijiji bp
abpabpapBAI
Exemplo 2
CBS (Canal Binário Simétrico)
−
−=
pppp
P AB 11
|
)|()()|()(),( ABHBHBAHAHBAI −=−=
É importante lembrar que como ),()( BAIApMAXC ⋅= , para um
vetor de saída B={0 1}, para atingir MAX p(B) (PB=[0,5 0,5] temos que H(B)=1 assim.
)(1...)(
)1(log)1(log
)|(log)|()|(),(
22
1
02
phCassim
phpppp
abpabpABHBAIn
jijij
−=
=−−−−=
−== ∑−
=
Algoritmo Arimoto-Blahut É baseado no fato de que a capacidade do canal pode ser limitada
tanto superior quanto inferiormente para algumas funções simples de PA. O Algoritmo recursivamente atualiza PA.
Seja |A|=N, |B|=M, F=[f0 f1 ... fN-1], ε = número inteiro positivo (é a
margem de precisão) Sejam i e j índices sendo que i ∈ [0, 1, ..., N-1] e j ∈ [0, 1, ..., M-1]
Inicialize
AABB
NA
PPPN
pN
pN
pP
⋅=
==== −
|
1101,...,1,1
Repita FimSe Fim
]1,...,1,0[ para
SenãoPare
então ε)( Se
Limitpper // U)]([log
LimitLower // )(log
]1,...,1,0[ para lnexp
Repita
|
2
2
||
AABB
iii
L
LU
iU
L
A
j j
ijiji
PPP
Nixpfp
ICII
fMÁXI
xIPFx
Nipp
pf
⋅=
−∈=
=<−
=
=⋅=
−∈
= ∑
Este algoritmo só precisa ser executado uma vez nos canais
simétricos. A entrada do Algoritmo é a matriz de transição PB|A e a saída é C, I(A,B) e PA.
Teorema do Canal Ruidoso
)()|(0 AHBAH ≤≤ Vimos que )(),...,,( 110 AnHAAAH n ≤− . Na transmissão de um bloco de
n símbolos o canal é usado n vezes. Como ),...,( 110 −nAAAH é a informação média contida num bloco de n símbolos, segue que a informação média por uso do canal é:
)(),...,( 110 AHn
AAAHR n ≤= −
Onde R é a taxa de entropia. Temos, portanto que )(AHR ≤ , como a
igualdade ocorrendo se e somente se todos os símbolos da seqüência são estatisticamente independentes.
Supondo CR ≤ , é possível ter uma transmissão sem perda de informação, isto é, com equivocação zero.
O processo de adicionar redundância a um bloco de símbolos transmitidos é chamado codificação do canal.
Teorema
Suponha R<C, onde C é a capacidade de um canal sem memória. Então para qualquer ε > 0 existe um comprimento de bloco n e um código de bloco de comprimento n e taxa de entropia R cuja probabilidade de erro de decodificação de bloco pe satisfaz pe < ε quando o código é usado neste canal.
Existe um taxa limite empírica para CBS:
(cutoff-rate) [ ])1(5,0log20 ppR −+−=→ Esta taxa somente é ultrapassada por códigos turbo (recentemente
criados, por volta de 1993).Material elaborado por Eduardo Wolsky e digitado por Rafael Oliveira em 03/07/2003