Teoria da Informação

Transcrição

Departamento de Engenharia Electrotécnica e de Computadores
Apontamentos de
Sílvio A. Abrantes
2003
1. Shannon e a Teoria da Informação
1.1. Introdução e perspectiva histórica
1.2. Medidas de informação: incerteza, entropia,
informação mútua média e capacidade de canal
1.3. Teorema da codificação de canal: ritmo de
informação, teorema da codificação de canal,
codificação de fonte, redundância
1.4. Teorema da codificação de fonte: códigos
unicamente descodificáveis, códigos de prefixação,
desigualdade de Kraft-McMillan, teorema da
codificação de fonte, extensões
1.5. Códigos de fonte para compressão de dados:
técnicas de compressão sem perdas, códigos
baseados em modelos estatísticos e em dicionários:
código de Shannon-Fano, código de Huffman,
código aritmético, código de Lempel-Ziv (L-Z)
1.6. Fontes e canais contínuos: entropia diferencial,
teorema da capacidade de canal (lei de
Shannon-Hartley), limite de Shannon, plano da
probabilidade de erro e plano da eficiência em
largura de banda
2. Codificação para correcção de
erros
2.1.
Introdução
2.2.
Técnicas ARQ
2.3.
Códigos de blocos
2.4.
Códigos cíclicos
2.5.
Códigos convolucionais
2.6.
Códigos entrelaçados e concatenados
!
!"!"! "#$%&'()*&!+!,+%-,+.$/01!2/-$3%/.1!
!"#$%&'(&')*+#$,&-.#'
)*/$#(0-.#'"'1"$21"3/%4&'5%2/6$%3&'
7'
421##&#!+!1!5+&%/1!'1!"#6&%71)*&!
!
!"#$%&'(&')*+#$,&-.#'
)*/$#(0-.#'"'1"$21"3/%4&'5%2/6$%3&'
8'
"#$%&'()*&!
!"#$!"#$%&'("$&)'*&'+#,-.%+&/0#$%$&'('))*+,#$-#+#$#./0,+,+"1)$0"#$1%20#'
,&%2' &,3)&2$ 0"#$ 3"$23"+!%1&' ,&%2' 1&2!&2$ /0'$ (1&.03#$ #1)$ -+,&(4-,1)$
5*),(1)$.1$-+16'(71$'$(1"-#+#891$.'$),)7'"#)$.'$(1"0&,(#8:');$
<$ 5+&%/1! '1! "#6&%71)*&$ %$ 0"#$ .,)(,-=,&#$ ('&7+#.#$ >$ ?1=7#$ .'$ 0"#$
#51+.#@'"$ "#7'"*7,(#$ (1"0"$ #1$ ')70.1$ .1$ &$,&4".&,".!#$ '$
,&.%3-)&/0#$ .#$ %.5#$,&/0#;$ A1"1$ 7#=2$ B1+&'('$ 0"#$ 6&2"' !"7$%+&$ -#+#$
#(7,?,.#.')$(1"1C$
• 15)'+?#8912$"'.,.#2$(1"-+'))91$'$#+"#3'&#"'&71$.'$.#.1)$
• 7'='(1"0&,(#8:')$
• ')7,"#891$
• 71"#.#$.'$.'(,):')$
• +'(1&D'(,"'&71$.'$-#.+:');$
E'=#7,?#"'&7'$>)$7'='(1"0&,(#8:')2$#$F'1+,#$.#$G&B1+"#891$
• B1+&'('H&1)$3%2!&2$-#+#$"'=D1+#+$#$"5%+%8.+%&$.#$(1"0&,(#8912$(1"$5#)'$
&1$')70.1$.#)$-1)),5,=,.#.')$'$=,",7#8:')$,&'+'&7')$>)$=',)$B4),(#);$
<$8&'/6/.1)*&$I.'$B1&7'$'$.'$(#&#=J$%$0"#$B1+"#$.'$"'=D1+#+$#$'B,(,K&(,#$.#$(1"0&,(#891;$
• "2!&6")"+"')%,%!"2$-#+#$'))#$'B,(,K&(,#2$'"$+'=#891$#1)$/0#,)$-1.'+'"1)$
(1"-#+#+$.,?'+)1)$),)7'"#);$
!"#$%&'(&')*+#$,&-.#'
)*/$#(0-.#'"'1"$21"3/%4&'5%2/6$%3&'
9'
"#$%&'()*&!
<$ F'1+,#$ .#$ G&B1+"#891$ %$ 0"#$ 7'1+,#$ ,&!",9!%+&$ /0'$ 7+#7#$ .'$ 7+K)$
(1&(',71)$5*),(1)C$
• <$,"*%*&'*&'%.5#$,&/0#:$
• <$+&3&+%*&*"$.'$0"$(#&#=$.'$(1"0&,(#8:')$7+#&)B'+,+$,&B1+"#891;$
• <$ +#*%5%+&/0#2$ (1"1$ "',1$ .'$ 07,=,3#+$ 1)$ (#&#,)$ (1"$ 71.#$ #$ )0#$
(#-#(,.#.';$
L)7')$7+K)$(1&(',71)$')791$=,@#.1)$-'=1$/0'$)'$-1.'$(D#"#+$1$$
!
"#$%#&'!()*+'&#*,'-!+'!"#$%.'!+'!/*0$%&'12$!3+#!45'**$*67!
91'1!(71!6&#$+!'+!/#6&%71)*&!+!(7!.1#1:!'+!.&7(#/.1)*&;!+</-$+!(71!
$=.#/.1!'+!.&'/6/.1)*&!$1:!>(+!1!/#6&%71)*&!,&'+!-+%!$%1#-7/$/'1!1$%10=-!
'&! .1#1:! 1! >(1:>(+%! %/$7&! /#6+%/&%! ?! .1,1./'1'+! '&! .1#1:! +! .&7! (71!
6%+>(@#./1! '+! +%%&-! 1%A/$%1%/17+#$+! ,+>(+#1! 1,+-1%! '1! ,%+-+#)1! '&!
%(B'&C!
!
• M$ #)-'(71$ 2-$3$"".*".!"$ $ .')7'$ 7'1+'"#$ %$ #$ 7+#&)",))91$ 2",' "$$#2$
#7+#?%)$ .'$ 0"$ (#&#=$ +0,.1)12$ 0"#$ (1&.,891$ /0'$ %$ 157,.#$ #7+#?%)$ .'$
(1.,B,(#891$#.'/0#.#;$
• <$ +#*%5%+&/0#$ %$ 0)#.#$ -#+#$ &*&3!&$$ #$ B1&7'$ '$ 1$ (#&#=$ -#+#$ #$ "*N,"#$
7+#&)B'+K&(,#$B,*?'=$.'$,&B1+"#891;$
!"#$%&'(&')*+#$,&-.#'
)*/$#(0-.#'"'1"$21"3/%4&'5%2/6$%3&'
:'
"#$%&'()*&!
$
<$F'1+,#$.#$G&B1+"#891$7'&7#$+')-1&.'+$#$-'+@0&7#)$.1$@%&'+1C$
$
• ;'<-"'='&'%.5#$,&/0#>'?#,#'&',"*%,#2>'
• @-&%2'20#'#2')%,%!"2'5-.*&,".!&%2'A'!$&.2,%220#'*"'%.5#$,&/0#>'
• @-&%2' 20#' #2' )%,%!"2' 5-.*&,".!&%2' A' "B!$&+/0#' *"' %.5#$,&/0#' *#' ,"%#'
&,6%".!">'
• ?#,#' =' <-"' 2"' *"1",' 3$#C"+!&$' *%23#2%!%1#2' #-' "<-%3&,".!#2' <-"' 2"'
&3$#B%,",'*"22"2')%,%!"2>'
• ;2' *%23#2%!%1#2' "' "<-%3&,".!#2' &+!-&%2' &3$#B%,&,D2"E' #-' .0#E' *"22"2'
)%,%!"2>'
!"#$%&'(&')*+#$,&-.#'
)*/$#(0-.#'"'1"$21"3/%4&'5%2/6$%3&'
;'
D+%-,+.$/01!2/-$3%/.1!
• O+'&P&(,1)$ +'"171)$ .#$ F'1+,#$ .#$ G&B1+"#891C$ .3'/E&! F&%-+! IQ#"0'=$
R1+)'2$STUVHSTUTJ;$
• <)$ -+,"',+#)$ 7'&7#7,?#)$ -#+#$ .'B,&,+$ 0"#$ "'.,.#$ .'$ ,&B1+"#891$ B1+#"$
B',7#)$-'=1)$7'W+,(1)$.#$(1"0&,(#891$GC!HI>(/-$$I7'='@+#B,#$'$(+,7%+,1)$.'$
XY/0,)7$ Z$ S[V\HS[VTJ$ '$ G1%$:+I$ IS[VTJ$ '$ -'=1$ ')7#74)7,(1$ JC! K/-2+%$
IS[V]J;$
• G1%$:+I$ .'B,&,0$ -'=#$ -+,"',+#$ ?'3$ #$ <-&.!%*&*"' *"' %.5#$,&/0#$ (1"1$
)#(&$%!,#$.1$&P"'+1$.'$)4"51=1)$10$"'&)#@'&);$
• M$ #))0&71$ )W$ 71"10$ #$ )0#$ B1+"#$ #(70#=$ #-W)$ 1)$ 7+#5#=D1)$ .'$ 8:1('+!
421##&#$ IS[\TJ2$ L/+#+%$ IS[\TJ$ '$ M&$+:#/N&0$ IS[\^J;$ _1)$ 7+K)$ B1,$
421##&#$ /0'"$ ')7#5'='('0$ 1)$ B0&.#"'&71)$ "#,)$ ,"-1+7#&7')$ '$
@'&%+,(1)$ .#$ 7'1+,#2$ &1$ )'0$ #+7,@1$ FGH"' I&!H",&!%+&)' GH"#$J' #5'
?#,,-.%+&!%#.F'I`'==$QY)7'"$F'(D&,(#=$a10+&#=2$a0=D1$b\T$'$M0705+1$b\TJ2$
(1&),.'+#.1$#$6&2"'.#$"1.'+&#$7'1+,#$.#$(1"0&,(#891;$
• _0+#&7'$#$Vc$d0'++#$R0&.,#=C$
e$HC!L/+#+%!I!;Q;<;J$'$OC!M&:7&E&%&66$I!;E;Q;Q;J$
<-+')'&7#+#"$,&.'-'&.'&7'"'&7'$#$)1=0891$-#+#$#=@0&)$-+15='"#)$+'=#(,1&#.1)$
(1"$#$,&B=0K&(,#$.1$+04.1$)15+'$1)$),&#,)$.'$+#.#+2$.'$"1.1$/0'$')7')$B1))'"$
(1&?'&,'&7'"'&7'$.'7'(7#.1)$(1"$?,)7#$>$'N#(7#$=1(#=,3#891$.1)$#?,:')$,&,",@1);$
e$8:1('+!421##&#$I!;Q;<;J$Z$(+,-71@+#B,#$
F'&.1$(1"'8#.1$-1+$(1&),.'+#+$#)$?#&7#@'&)$+'=#7,?#)$.'$"0,71)$),)7'"#)$.'$
(1"0&,(#8:')$&1?1)$&#$%-1(#$IOARfJ2$-+1(0+10$0"$"%71.1$@'+#=$.'$(1"-#+#891$
.1)$)'0)$"%+,71);$E'?'=#&.1$0"#$-'+('-891$&17*?'=$5#)'#.#$=#+@#"'&7'$'"$
(1&),.'+#8:')$D'0+4)7,(#)2$QD#&&1&$-+1(0+10$0"#$7'1+,#$5*),(#$-#+#$#$
(1"0&,(#891$#7+#?%)$.'$(#&#,)$+0,.1)1);$
• M07+#)$ (1&7+,50,8:')C$ G177/#E! IS[]gJ2$ K+/#-$+/#$ IS[]\J2$ K1#&$ IS[]V2$
S[hSJ2$ P:/1-$ IS[]\2$ S[hUJ2$ Q+%:+N17,$ IS[h\J2$ R1::1E+%$ IS[h]J2$ S/$+%A/$
IS[h^J2$ F1--+I$ IS[h[J2$ 8&0+%$ IS[^VJ2$ 4:+,/1#$ i$ L&:6$ IS[ÛJ2$ Q:12($$
IS[^^J;$
!"#$%&'(&')*+#$,&-.#'
)*/$#(0-.#'"'1"$21"3/%4&'5%2/6$%3&'
<'
D+%-,+.$/01!2/-$3%/.1!
H&%A+%$! L/+#+%$ IjAY5'+&'7,()C$ A1&7+1=$ #&.$ A1""0&,(#7,1&$ ,&$ 7D'$ <&,"#=$
#&.$7D'$R#(D,&'j2$S[\TJ$(1=1(10$#$)'@0,&7'$/0')791C$
K&*#' -,' +#.C-.!#' *"' 2%.&%2' 3#22L1"%2' <-"' .0#' 20#' *&' .#22&' "2+#)H&E' ,&%2' #' $-L*#'
M%."1%!91")NE'+#,#'='<-"'5&$",#2'&',")H#$'"2!%,&!%1&'*#2'1&)#$"2'3$"2".!"2'"'5-!-$#2'
*#'2%.&)'$"+"6%*#>'
L)7#"1)$&1$k"5,71$.#$G"#$%&'*&'K"!"+/0#2$1&.'$#)$)1=08:')$W-7,"#)$-#+#$')7'$
-+15='"#$'$107+1)$)'"'=D#&7')$)91$-+1(0+#.#);$
$
M$ 7+#5#=D1$ .'$ 421##&#$ ')7*$ "#,)$ +'=#(,1&#.1$ (1"$ 1$ /0'$ D#5,70#="'&7'$
#(D#"1)$ /0'$ %$ #$ +#,-.%+&/0#2$ 1&.'$ 1$ 3$#+"22&,".!#' *#' 2%.&)$ )'$ -1.'$
B#3'+$!&.!#'.#'",%22#$'+#,#'.#'$"+"3!#$;$
421##&#$(1=1(10$')7#$/0')791C$
K&*#'#'+#.C-.!#'*"',".2&(".2'3#22L1"%2'<-"'-,&'5#.!"'3#*"'3$#*-4%$'"'<-"'.0#'20#'
*&' .#22&' "2+#)H&E' +#,#' =' <-"' &2' ,".2&(".2' *"1"$0#' 2"$' $"3$"2".!&*&2' 3&$&' <-"'
,")H#$' !$&.2,%!&,' &' %.5#$,&/0#' .-,' *&*#' 2%2!",&' +#,' &2' 2-&2' )%,%!&/O"2' 5L2%+&2'
%."$".!"2>'
O#+#$7+#7#+$.')7'$-+15='"#$'"$7'+"1)$@'&%+,(1)$%$&'('))*+,1$
(1&('&7+#+"1H&1)$"#,)$&#$,&B1+"#891$/0'$&1)$),&#,)$
!"#$%&'(&')*+#$,&-.#'
)*/$#(0-.#'"'1"$21"3/%4&'5%2/6$%3&'
='
!
!"#"! "#$%$&'!$#!%()*+,&-.*!
!
•! !
"#$%&'%()!
•! !
*#'&+,-)!
•! !
"#.+&/)01+!/2'3)!/45-)!
•! !
6),)$-5)5%!5%!$)#)7!
"#$%$&!$&!%()*+,&-.*!
!
/()*+,&-.*! 8! '35+! )93-7+! 93%! 4! ,&+53(-5+! ,+&! 3/)! .+#'%! ,)&)! :%&!
'&)#:.%&-5+!,)&)!+!3'-7-()5+&;!
<+! 93%! &%:,%-')! =! /%5-5)! 5)! -#.+&/)01+! ,+5%/+:! $+#:-5%&)&! $*%'! 0*(1*'!
$#!2%'1&>!
•! ?@"A"BCDEF! 8! )! /%5-5)! 5)! -#.+&/)01+! %:'G! &%7)$-+#)5)! $+/! $%&'()'*+!
H%/!&%7)01+!=!/%#:)I%/!)!:%&!'&)#:/-'-5)J;!
•! KE<@*! 8! )! /%5-5)! 5)! -#.+&/)01+! 4! 3/)! -#5-$)01+! 5)! ,$-'(.+.'/ .'/
'0&1,2+!%L%&$-5)!,%7)!.+#'%!)+!!:%7%$$-+#)&!3/)!/%#:)I%/;!
!
•! M%! )! .+#'%! ,35%&! %:$+7N%&! 7-O&%/%#'%! %#'&%! /3-'):! /%#:)I%#:!
5-.%&%#'%:! !! +! 3'-7-()5+&! '%&G! /3-'):! 52O-5):! %/! &%7)01+! =!
/%#:)I%/!93%!O)-!:%&!%:$+7N-5);!
•! M%! #1+! N+3O%&! #%#N3/)! ,+::-P-7-5)5%! 5%! %:$+7N)! H! !! :Q! 3/)!
/%#:)I%/!,+::RO%7J!!!#1+!NG!-#$%&'%()!!!#1+!NG!-#.+&/)01+;!
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
1'
"#$%$&!$&!%()*+,&-.*!
!"#$%&%'"%'"&()*+#',-*"$(.*/.$"0+*1'1&/&%'%$2"
!"#$%&'()$*+$,*',-$./"#$%&'()$01*
!
= ! $%&" %! ! HS!!!23!!!!TJ!
%!
!
# ! = $ " %! # = $%&"
!
! ! ! ! !
! M%!
4!U!V!
!!
P-'!
!
! ! ! ! !
! !
4!U!%!
!!
#)'!
!
! ! ! ! !
! !
4!U!TS! !!
N)&'7%W!
?/! 5RI-'+! P-#G&-+! HS! %! TJ! ,+5%! '&)#:,+&')&! 3/)! -#.+&/)01+! :3,%&-+&! +3!
-#.%&-+&!)!T!P-'X!$+#:+)#'%!):!,&+P)P-7-5)5%:!5%!+$+&&Y#$-)!5%!$)5)!5RI-'+;!
*:')! /%5-5)! 7+I)&R'/-$)! 5%! -#.+&/)01+! 4! )! 2#-$)! .3#01+! 93%! :)'-:.)(! ):!
:%I3-#'%:!,&+,&-%5)5%:>!
TJ!
!/**!**5! ! ,)&)!5*"*2/**"*6!
H)!)3'+Z-#.+&/)01+!4!#1+Z#%I)'-O)J!
VJ!
!/*"*5! ! ,)&)!2/*"*6! !
H)!-#$%&'%()!)3/%#')!)!-#.+&/)01+J!
[J!
!/*7*!8! ! ,)&)!2/**9**28!
\J!
$+/!/%#:)I%#:!-#5%,%#5%#'%:!:/!%!;8!! H!!2+:/;80*<*2/28J!
!
# &' = $%& '
!
!
!
= $%& ' + $%& '
= #& + # ' !
%& %'
%&
%'
! H)!-#.+&/)01+!'+')7!4!)!:+/)!5):!-#.+&/)0]%:!-#5-O-53)-:J!
*^*_ÀE>!!%( =
!
a!
)
%! =
*
!
)
!
"#.+&/)01+!'&)#:,+&')5)!,%7+!5RI-'+!S>! # ( = ! $%& '
!
= ' !P-':!
)
!
"#.+&/)01+!'&)#:,+&')5)!,%7+!5RI-'+!T>! #! = ! $%& '
*
= (+ )! !P-':!
)
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
2'
3(1+*0%&!4*5!%()*+,&-.*!,6$%&7!
•! C3'+Z-#.+&/)01+! 8! 4! 5%.-#-5)! %/! '%&/+:! 5):! /%#:)I%#:! +3! :R/P+7+:!
-#5-O-53)-:;!
•! "#.+&/)01+! /45-)! H#(1+*0%&J! 8! 4! 5%.-#-5)! %/! '%&/+:! 5+! $+#b3#'+! 5):!
/%#:)I%#:!93%!)!.+#'%!,+5%!,&+53(-&;!
M%b)! 3/)! #$"-=* >/?@%=-'! A! $+/! B! :R/P+7+:! 5-.%&%#'%:! %! %:')'-:'-$)/%#'%!
-#5%,%#5%#'%:;!
•! c3)#5+!+!:R/P+7+!5%!+&5%/!8!4!'&)#:/-'-5+!)!-#.+&/)01+!'&)#:,+&')5)!4!
# ' = ! $%& ' %' !P-':;!
•! C! -#.+&/)01+! /45-)! )::+$-)5)! )+:! B! :R/P+7+:! 5)! .+#'%! A! 4! )! ,6$%&!
0*($#+&$&! 5):! )3'+Z-#.+&/)0]%:! 5%! $)5)! :R/P+7+;! C! %::)! -#.+&/)01+!
/45-)!,+&!:R/P+7+!5)!.+#'%!$N)/)Z:%!#(1+*0%&!%!5%:-I#)Z:%!,+&!CHAJ>!
!
!
(
(
' =!
' =!
) " * # = " %' # ' = ! " %' $%& ' %' ! P-':d:R/P+7+!
E!93%!4!93%!:-I#-.-$)!)!#(1+*0%&!5%!3/)!.+#'%Te!M-I#-.-$)!93%>!
D&4$%'* ")$* E$??'&$?* E%=F=%* G,'H* $* ?I&4$H$* G,=* '* #$"-=* /%J*
E%$>,K/%*'*?=L,/%M*=&*&N>/'*=?E=%'&$?*$4-=%*C*4/-?*>=*/"#$%&'()$*
E$%*?I&4$H$M*$,*OC*4/-?*",&'*&="?'L=&*>=*O*?I&4$H$?M*?=*O*#$%*
=H=F'>$P*
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
!-.,+,-&./01-2/2,-2&./,/,0123%45/,60,7.,85820./,,9:85;%,<,6095156/,4%3,3,=,4,$1,#+,0.,>70,4,<,/,;%182/120,60,?%$2@./11,
0, #, %, 1A.03%, 60, 082/6%8, /;088:B058, /%, 85820./C, -82/, 971DE%+, >70, 9%310;0, 7./, .0656/, >7/1252/25B/, 6%, &3/7, 60,
./-5/6&7/78,6%,85820./+,<,80.0$F/120,1/,9%3./,G,0123%45/,6/,H0%35/,6/,I19%3./DE%C,
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
3'
3(1+*0%&!
•! f)/+:!&%%:$&%O%&!)!.Q&/37)!5)!%#'&+,-)!$+/+!
(
! ! ) " %!+ %' +…+ %( # = !
!
" %' $%& ' %' !
HP-':d:R/P+7+J!
' =!
•! <+!$):+!5%!3/)!.+#'%!+3!/%#:)I%/!P-#G&-)!$+/!V!:)R5):!,+::RO%-:X!$+/!
,&+P)P-7-5)5%:!E!%!6.EX!)!%#'&+,-)!4!5%:-I#)5)!,+&!#HEJ!%!O)7%!
! ! #" 9 # = ) " 9+! ! 9 # = ! 9 $%& ' 9 ! "! ! 9 #$%& ' "! ! 9 # !
!
#"4#
!
(CK
(CJ
(C)
(C'
(C' (C)
(CJ
(CK
!
,
1:2;<9&/07805=/0$<:280"&:>;&/0
•! D%!/+5+!I%&)7X!$+/!3/!)7.)P%'+!5%!"!:R/P+7+:!'%/Z:%!
,
,
,
,
? $ ) " * # $ $%& ' ( ,
,
,
,
,
%,
,
%,
C!.+#'%!#1+!.+&#%$%!-#.+&/)01+X!%/! ,
_GL-/)!-#$%&'%()!+3!/GL-/)!7-P%&5)5%!5%!
/45-)!!!#1+!NG!-#$%&'%()!93)#'+!=!
%:$+7N)! !! '+5+:! +:! :R/P+7+:! :1+!
/%#:)I%/;!
%93-,&+OGO%-:!H#%#N3/!4!.)O+&%$-5+J;!
*L;>!)!.+#'%!,&+53(!$+#'-#3)/%#'%!+! ,
*L;>,
/%:/+!
%' =
:R/P+7+!
H'+5):!
):!
,&+P)P-7-5)5%:! 5+:! :R/P+7+:! :1+!
#37):!%L$%,'+!3/)X!3#-'G&-)J!
!"#$%&'(&')*+#$,&-.#'
!
! ) = )./L =
(
,
= %! #! + %' #' +…= (% ' # ' = $%& ' (
/"(%(&0'("'%*+#$,&-.#'
4'
3(1+*0%&!8!39#,0:*'!
,
3;3"<=>!?!
c3)7! 4! )! -#.+&/)01+! /45-)X! %/! P-':d$)&G$'%&X! 5)! 7R#I3)! ,+&'3I3%:)! HV[!
7%'&):J!:3,+#5+!$)5)!7%'&)!%93-,&+OGO%7e!
"#$! ) = ! $%&
!
= )+M' !%&'(!)*+,-*'.,! & !"#"$%&'()%*"+*!
'*
,
,
3;3"<=>!@!
<)!&%)7-5)5%!):!7%'&):!#1+!:1+!%93-,&+OGO%-:;!C5/-'-#5+!HCD_"@"<DE;;;J!93%!
):!7%'&):!+$+&&%/!$+/!):!,&+P)P-7-5)5%:!-#5-$)5):X!93)#'+!O)7%!)!%#'&+,-)e!
! CX!*X!EX!@>!! !
E!U!SXTS!
!
! gX!"X!<X!FX!M>!!
E!U!SXSh!
!
! 6X!DX!KX!AX!_X!`X!?>! E!U!SXSV!
! iX!jX!kX!cX!fX!^X!B>! E!U!SXST!
F;>!
,,
) = !") ' (+!( $%& ' (+! + M ' (+ (N $%& ' (+ (N + N ' (+ (' $%& ' (+ (' + N ' (+ (!$%& ' (+ (!# =
= *+O',P528Q;/3R;203
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
,
5'
3(1+*0%&!,A9%,&!
B#*+#,&!
3*="-%$E/'* ) " * # *>=*,&'*#$"-=*%=?E=/-'*?=&E%=* ( $ ) " * # $ $%& ' ( P*Q*F'H$%*
&J:/&$* '-/"L=.?=* 'E="'?* G,'">$* -$>'?* '?* ?'I>'?* >'* #$"-=* ?)$*
=G,/E%$FJF=/?P*
C#,*('1+&-.*!
C!5%/+#:'&)01+!P):%-)Z:%!#)!5%:-I3)75)5%!! $1 @ $ @ ! ! ;!M%b)! ( =
A&
X!%/!93%!
%&
R/!%!2/!:1+!,&+P)P-7-5)5%:!5-:$&%'):!OG7-5):X!-:'+!4X!
(
(
& =!
& =!
! ! %& + A& ) (,,,0,,, " %& = " A& = ! !
!
M%#5+!%#'1+! $1 @ $ @ ! ! X!'%&%/+:>!
!
!
$1
A& A&
$
! ! X!+3! ! %& $1 %& $ A& ! %& ! %& $1 A& !
%& %&
M+/)#5+!,)&)!'+5+:!+:!//>!
!
!
(
(
(
(
& =!
& =!
& =!
& =!
!" %& $1 %& $ " A& ! " %& ! " %& $1 A& !
(
(
& =!
& =!
_):! " A& ! " %& = ! ! ! = ( !%! $1 B = $1 ' $%& ' B ;!`+&')#'+X!
(
(
& =!
& =!
! $1 ' " %& $%& ' %& $ ! $1 ' " %& $%& ' A& !!
!
!!
(
) " * # $ !" %& $%& ' A& !
& =!
":'+!4!OG7-5+!,)&)!'+5+:!+:!O)7+&%:!5%!R/X!-#$73-#5+! A& =
!
!!
(
) " * # $ !" %& $%& '
& =!
!"#$%&'(&')*+#$,&-.#'
!
= $%& ' (
(
(
" %& = $%& ' ( ;!
!
!
!H,+&93%!#1+eJ;!
(
@PGP>P!
& =!
/"(%(&0'("'%*+#$,&-.#'
6'
39#,0:*D!
%()*+,&-.*!E*(1%$&!(5,&!%,&F#,!
$#!1#:#2%'.*!#!#,!1#91*!
B#:#2%'.*!H$+/!"#5%,%#5Y#$-)!%#'&%!MR/P+7+:J!
•! A-#N):!)$'-O):>! lhl!
•! `+#'+:!5%!%$&1>![lS!SSS!!!mSn!,+#'+:d7-#N)!!!!mSn!'!lhl!U![\o!mSS!,+#'+:!
•! "#.+&/)01+!/45-)!H%#'&+,-)J!/GL-/)>!
!
H`&%'+!%!i&)#$+X!&!U!n!#RO%-:!5%!73/-#p#$-)!,+&!q:,+'q!H#RO%-:!%93-,&+OGO%-:JJ!
,
,,
!
, ! $%& ' ! K = * ,P528,
HC!6+&%:!H!O%&/%7N+X!O%&5%X!)(37JJ!
,
!,.,=,K,',*,=,'),!,0123%45/,.RL5./S, ! $%& ' ! ') = )+MK ,P528,
,
•! */!$)5)!-/)I%/>!!
!
!!
!
!
`&%'+!r!i&)#$+>!
C!$+&%:>!
['[\o!mSS!U!T!S\n!nSS!P-':d-/)I%/!
\Xln!'![\o!mSS!U!T!mST!oh[!P-':d-/)I%/!
•! `&+b%$01+!5)!-/)I%/!!HlS!93)5&+:d:!!!Vl!-/)I%#:d:J!
!
!`&%'+!%!i&)#$+>!
!
!C!$+&%:>!
Vl!'!T!S\n!nSS!U!Vm!VVS!SSS!P-'d:!
Vl!'!T!mST!oh[!U!\S!S\o![TV!P-':d:!
!
B#91*!H7%'&):!%93-,&+OGO%-:J!
`+&'3I3Y:>!
V[!7%'&):!s!%:,)0+!"!)3'+Z-#.+&/)01+!/GL-/)!>! ! $%&
!
= )+MK !P-':!
')
t! $+/,&-/%#'+!/45-+!5%!$)5)!,)7)O&)!U!V[!
t! 6+#'%25+!5%!-#.+&/)01+!,+&!,)7)O&)!H%#'&+,-)J>!V[!'!\Xln!U!TSlX\!P-':d,)7)O&)!
S$&E'%'">$* @$&* ,&'* /&'L=&* '* 2%=-$* =* T%'"@$M* ,&'* >=?@%/()$* /&E%=??'*
!()KK((
* OOM! *E'H'F%'?P*
"=@=??/-'%/'*>=*
!(M+ )
F3::+>![[!7%'&):!s!%:,)0+!"![[!7+I![\!U![[!' lXT!U!TmnX[!P-':d,)7)O&)!!*UVWV*E'H'F%'?!
"#I7Y:>!Vm!7%'&):!s!%:,)0+!"!Vm!7+I!Vh!U!Vm!' \Xn!U!TV\Xn!P-':d,)7)O&)!!*XY5Y*E'H'F%'?!
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
7'
G&+&E1#+%H&-.*!$#!E&(&%'!
6+#:-5%&%/+:!3/!$)#)7!$+/!B!%#'&)5):!:%7%$$-+#)5):!5%!3/!)7.)P%'+!^!%!O!
:)R5):! :%7%$$-+#)5):! 5%! 3/! )7.)P%'+! u;! `+5%/+:! %#$)&)&! )! :)R5)! 5+! $)#)7!
$+/+!)!O%&:1+!&3-5+:)!5)!%#'&)5);!
v!$+:'3/%!$)&)$'%&-()&!+!$)#)7!5%!53):!/)#%-&):>!
•! )'&)O4:!5+!>/'L%'&'*>=*-%'"?/()$!!
•! )'&)O4:!5)!&'-%/K*>=*E%$4'4/H/>'>=?*>=*-%'"?/()$!H+3!&'-%/K*>$*@'"'HJ!
!
01
06
09
08
23415067
/
/
/
23485087
/
/
/
0:
"
41
46
49
48
4; !
"#$%&$'$!()!*&$+,#-./!(/!0$+$1!
# 9 " D! T @! #
% 9" D T @ #
! '
U %"E T * #V = %
%
…
%
' 9 " D! T @( #
9" D C T @! # $
9" D' T @' # … 9 " D C T @' # &
&!
&
…
…
…
&
9 " D' T @( # … 9" D C T @( # (
9 " D' T @! #
…
2$*&#3!()!4&/5$5#1#($(),!()!*&$+,#-./!(/!0$+$1!
•! <%:')! /)'&-(! $)5)! 7-#N)! %:'G! )::+$-)5)! )+! $+&&%:,+#5%#'%! :R/P+7+! 5%!
%#'&)5)! %! $)5)! $+73#)! %:'G! )::+$-)5)! )+! $+&&%:,+#5%#'%! :R/P+7+! 5%!
:)R5);!
•! C!:+/)!5+:!%7%/%#'+:!5%!$)5)!7-#N)!4!T>!
" 9" D ' T @& # = ! !
'
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
8'
I%,0:%)%E&-.*!$#!E&(&%'!$%'E+#1*'!
E*,0*'1*'!
,
wS
,HwSxLSJ!
L S!
WS!
wT
L T!
WT!
,HwVxLSJ
wV
!
!! !"0'+3&+"%'2"#'3+&4$2"%$"3+'(2&,-*5"
!
C! /)'&-(! 5%! '&)#:-01+! I7+P)7! 4! -I3)7! )+! ,&+53'+! 5):! /)'&-(%:! 5%!
'&)#:-01+!-#5-O-53)-:;!
67)'41/8!
!
#(+' (+* (+M$
[ %"F T * #] = %
&!
(+)
(+M
(+!
'
(
!
!!!
# (+J (+) $
[ %"E T F #] = %% (+M (+M && !
%'(+N (+* &(
#(+J' (+*K $
&!
' (+MJ (+)) (
[ %"E T * #] = [ %"F T * #] ' [ %"E T F #] = %
!! !"0'+3&+"%$"6#"%&'7+'#'"%$"0+*1'1&/&%'%$2"%$"3+'(2&,-*5#
!
C:! ,&+P)P-7-5)5%:! $+#5-$-+#)-:! 9 " D ' @& # ! H:/! y! %#'&)5)a! ;8! y! :)R5)J! :1+!
-I3)-:!=!:+/)!5):!,&+P)P-7-5)5%:!)::+$-)5):!)+:!5-O%&:+:!z'&)b%$'+:{!5%!
:/!,)&)!;8;!
!
,
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
9:'
I%,0:%)%E&-.*!$#!E&(&%'!$%'E+#1*'!
E*,0*'1*'D!#9#,0:*!
89$#0/*":*#"*"%&'7+'#'"%$"0+*1'1&/&%'%$2"%$"3+'(2&,-*5":*#*"
2&#0/&)&:'+"*":'('/":*#0*23*"2$76&(3$;"
,
wS
,HwSxLSJ!
L S!
WS!
wT
L T!
WT!
,HwVxLSJ
wV
!
!! gG!5+-:!,%&$3&:+:!5%!:5!,)&)!;5>!LS!!"!wS!"!WS!!%!LS!!"!wT!"!WS!
!
!! %" D( T @( # = %" G( T @( # %" D( T G( # + %" G! T @( # %" D( T G! # !
!"""#"""$ !"""#"""
$
@( " G( " D(
@( " G! " D(
!! gG!5+-:!,%&$3&:+:!5%!:6!,)&)!;5>!:6!!"!Z5!"!;5!!%!:6!!"!Z6!"!;5*
!
!!! !
% " D( T @! # = %" G( T @! # %" D( T G( # + %" G! T @! # %" D( T G! # !
!! gG!'&Y:!,%&$3&:+:!5%!:5!,)&)!;6>!
!
LS!!"!wS!"!WTX!LS!!"!w6!"!W6!%!!L5!!"!wV!"!W6!
%" D! T @( # !4!)!:+/)!5):!,&+P)P-7-5)5%:!)::+$-)5):!)+:!'&Y:!,%&$3&:+:X!
%'$;!
9!&),:1*$(/!;#+$1!,)&#$!/!0$+$1!5#+<&#/!,)%:#+*)8!
,HWSxLSJ
LS
WS
,HWTxLSJ
,HWSxLTJ
LT
WT
,HWTxLTJ
!
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
99'
3(1+*0%&!G*($%E%*(&:!
C5/-')/+:!93%!NG!5+-:!)$+#'%$-/%#'+:X!A!%![X!$+/!B!,+::-P-7-5)5%:!,)&)!A!
%! O! ,)&)! [;! M%b)! %" @& + D ' # ! )! ,&+P)P-7-5)5%! $+#b3#')! 5)! +$+&&Y#$-)! " @& + D ' # ! %!
%" D ' T @& # !)!,&+P)P-7-5)5%!$+#5-$-+#)7!5%! D ' !+$+&&%&!5)5+! @& !'%&!+$+&&-5+;!
!
01
06
09
08
23415067
23485087
/
/
/
/
/
/
0:
"
41
46
49
48
4; ,
•! C!%#'&+,-)!$+#5-$-+#)7!5%![!5)5)!)!+$+&&Y#$-)! @& !4!5%.-#-5)!$+/+!
!
C
!
' =!
% " D ' T @& #
) "E T @& # = " %" D ' T @& # $%& '
C
= !" %" D ' T @& # $%& ' %" D ' T @& # =
' =!
!
= ) #' %" D! T @& #+ %" D' T @& #+% + %" D C T @& # $(
C:!,&+P)P-7-5)5%:!$+#5-$-+#)-:!%#O+7O-5):!:1+!):!5+:!&)/+:!93%!:)%/!5%! @& ;!
•! C!%#'&+,-)!$+#5-$-+#)7!5%![!5)5+!A!4!5%.-#-5)!$+/+!)!/45-)!,+#5%&)5)!
5%! ) "E T @& # !,)&)!'+5+:!+:!O)7+&%:!5%! @& >!
(
) "E T * # = " %" @& # ) "E T @& # =
!
& =!
( C
!!
="-%$E/'**@$">/@/$"'H!
= !"" %" @& # %" D ' T @& # $%& %" D ' T @& #
& =! ' =!
•! C!%#'&+,-)!$+#b3#')!5%!A!%![!4!5)5)!,+&!
!
( C
) " * + E # = "" %" @& + D ' # $%& '
& =! ' =!
!
!!
%" @& + D ' #
="-%$E/'**@$"8,"-'!
•! `&+O)Z:%!93%! ) " * + E # $ ) " * # + ) "E # ;!
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
91'
3(1+*0%&!G*($%E%*(&:!
3"4*R,'H* N* '* %=H'()$* ="-%=* '* ="-%$E/'* @$"8,"-'* ) " * + E # * =* '* ="-%$E/'*
@$">/@/$"'H* ) "E T * # \*
JKD! 6+/+! %" @& + D ' # = %" @& # %" D ' T @& # !H&%I&)!5%!i)W%:J!%#'1+!
( C
) " * + E # = "" %" @& # %" D ' T @& # $%& '
& =! ' =!
!
=
%" @& # %" D ' T @& #
( C
( C
& =! ' =!
& =! ' =!
!
= !"" % " @& # % " D ' T @& # $%& ' %" @& # ! "" %" @& # %" D ' T @& # $%& ' %" D ' T @& #
!
_):!
•! !
C
C
" %" @& # %" D ' T @& # $%& ' %" @& # = %" @& # $%& ' %" @& # " %" D ' T @& # = %" @& # $%& ' %" @& # !
' =!
' =!
!"
"#""
$
!
•! !
( C
(
& =! ' =!
& =!
!"" %" @& # %" D ' T @& # $%& ' %" D ' T @& # = " %" @& # ) "E T @& # = ) "E T * # !
(
!!! !
) " * + E # = !" %" @& # $%& ' %" @& # + ) "E T * # =
& =!
!
= ) " * # + ) "E T * #
•! !M%!+:!:R/P+7+:!.+&%/!-#5%,%#5%#'%:!!! ) " * + E # = ) " * # + ) "E # !
•! D+!/%:/+!/+5+!:%!,&+O)&-)!93%! ) " * + E # = ) "E # + ) " * T E # ;!
•! 6+/+! ) " * + E # $ ) " * # + ) "E #
!
) " * T E # $ ) " * # !%! ) "E T * # $ ) "E # !
•! 6+/+!:%!OYX!)!%#'&+,-)!5%!:R/P+7+:!5%,%#5%#'%:!4!/%#+&!93%!)!%#'&+,-)!
5%!:R/P+7+:!-#5%,%#5%#'%:;!
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
92'
3(1+*0%&!E*($%E%*(&:D!5,!#9#,0:*!
?/)!.+#'%!,&+53(!'&Y:!:R/P+7+:X!CX!i!%!6X!$+/!):!:%I3-#'%:!,&+P)P-7-5)5%:>!
!
{%" * = !#+ %" * = H#+ %" * = I #} = )+
O !J ' *
+ + ,!
- 'N 'N 'N .
!0
D'0
H0
I0
!0
(,
)QM,
!QM,
@&0
H0
!Q',
!Q',
(,
,
I0
!Q',
'QM,
!Q!(,
,
0
0
%JD'K@&L0
,
3"4*]=-=%&/"=*'*="-%$E/'*>'*#$"-=M* ) " * # M*=*'?*="-%$E/'?* ) "E T * # *=* ) " * + E # P*
JKD!C:!,&+P)P-7-5)5%:!$+#b3#'):! %" @& + D ' # = %" @& # %" D ' T @& # !O)7%/>!
,
D'0
0
0
%J@&MD'L0
!0
H0
I0
,
!0
(,
)Q!M,
!Q!M,
@&0
H0
KQ'N,
KQ'N,
(,
,
I0
!Q'N,
)Q!*M,
!Q!*M,
6+/+! %" D ' # = " %" @& + D ' # !!
&
{%"E = !#+ %"E = H#+ %"E = I #} = )+
! !J ' *
+ + ,
- * 'N 'N .
C::-/X! ) "E # = ) "! *+!J 'N + ' 'N# = !+ 'O !P-':d:R/P+7+!
HU ) " * # J!
C!%#'&+,-)!$+#5-$-+#)7! ) "E T * # :%&G!/%#+&;!D%!.)$'+>!
!
!
) "E T * = !# = ) "(+ ) M+! M# = (+ N' !
!
!
) "E T * = H# = ) "! '+! '+ (# = ! !
!
!
) "E T * = I # = ) "! '+ ' M+! !(# = !+*J !
!
!
) "E T * # =
O
!J
'
' (+ N' + '! + '!+*J = (+O* !P-':d:R/P+7+!
'N
'N
'N
`+&')#'+X!)!="-%$E/'*@$"8,"-'!O)7%! ) " * + E # = !+ 'O + (+O* = '+ '' !P-':d:R/P+7+;!
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
93'
3L5%2*E&-.*!#,!
E&(&%'!$%'E+#1*'!E*,!+5M$*!!
6+#:-5%&%/+:!+!$)#)7!5-:$&%'+!5+!5-)I&)/)!:%I3-#'%>!
!
01
06
09
08
23415067
/
/
/
23485087
0:
/
/
/
"
41
46
49
48
4; ,
•! C!="-%$E/'*>'*#$"-=!5%!/%#:)I%#:X!C+A0X!5%,%#5%!),%#):!5)!.+#'%!^;!^*'*/"@=%-=K'*
=&*%=H'()$*'*:/X!-:'+!4X!%/!&%7)01+!)!93%!:R/P+7+!:%&G!'&)#:/-'-5+;!
•! C!="-%$E/'*>'*?'I>'!5+!$)#)7X!C+[0!8!93%!4!%93-O)7%#'%!)!3/)!#+O)!.+#'%!8!5%,%#5%!
5)!.+#'%!^!%!5+:!%&&+:!5%!'&)#:/-::1+;!^*'*/"@=%-=K'*=&*%=H'()$*'$*?I&4$H$*G,=*?=%J*
%=@=4/>$X! #+! $):+! 5%! 3/)! 5)5)! .+#'%! 5%! /%#:)I%#:! %! 5%! 3/! 5)5+! $)#)7! 5%!
$+/3#-$)01+;!
•! 6+#N%$%#5+! ):! %:')'R:'-$):! 5)! .+#'%! 5%! /%#:)I%#:!%!5+!$)#)7!&3-5+:+!$+#N%$%Z:%!)!
="-%$E/'*@$"8,"-'X!C+AM[0;!^*'*/"@=%-=K'*?$4%=*'*-%'"?&/??)$*>=*:/*=*'*%=@=E()$*>=*
;8P!
•! M3,+#N)/+:!93%!$+#N%$%/+:!:/*!H-:'+!4X!:)P%/+:!93%!:R/P+7+!.+-!%#O-)5+J>!
( (
!
) "E T * # = !"" 9 " @& # 9 " D ' T @& #$%& ' 9" D ' T @& # * D"-%$E/'*@$">/@/$"'H!!
& =! ' =!
^* '* /"@=%-=K'* >=* %=@=4=%* ;8* G,'">$* :/* * N* ="F/'>$M* /?-$* NM* N* '* /"@=%-=K'* &N>/'* >$*
=&/??$%*=&*%=H'()$*'$*G,=*?=%J*%=@=4/>$P*
•! M3,+#N)/+:!93%!$+#N%$%/+:!;8!H-:'+!4X!:)P%/+:!93%!:R/P+7+!.+-!&%$%P-5+J>!
( (
!
) " * T E # = ! "" 9 " D ' # 9 " @& T D ' #$%& ' 9 " @& T D ' # * D"-%$E/'*@$">/@/$"'H;!
' =! & =!
^*'*/"@=%-=K'*?$4%=*:/*-=%*?/>$*="F/'>$*G,'">$*?=*%=@=4=*;8M*$,*'*/"@=%-=K'*&N>/'*
>$* %=@=E-$%* >'* &="?'L=&* =&* %=H'()$* '$* G,=* #$/* %='H&="-=* ="F/'>$P* 2$%* $,-%'?*
E'H'F%'?M* N* '* /"@=%-=K'* ?$4%=* '* ="-%'>'* G,=* %=?-'* >=E$/?* >'* ?'I>'* -=%* ?/>$*
$4?=%F'>'P*
C! ) " * T E # ! $N)/)Z:%! =G,/F$@'()$* >$* @'"'H>! 4! )! /%5-5)! 5)! -#.+&/)01+!
E=%>/>'!5%O-5+!)+!$)#)7;!
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
94'
/()*+,&-.*!,N15&!,6$%&!
•! C!%#'&+,-)! ) " * # !&%,&%:%#')!)!-#$%&'%()!z)!,&-+&-{!:+P&%!)!%#'&)5)!5+!$)#)7!&(1#'!
5%!+P:%&O)&/+:!)!:)R5);!
•! C! %#'&+,-)! $+#5-$-+#)7! ) " * T E # ! &%,&%:%#')! )! -#$%&'%()! z)! ,+:'%&-+&-{! :+P&%! )!
%#'&)5)!5+!$)#)7!$#0*%'!5%!+P:%&O)&/+:!)!:)R5);!v!)!-#$%&'%()!&%/)#%:$%#'%!:+P&%!+!
)$+#'%$-/%#'+!^!),Q:!:%!$+#N%$%&!+!)$+#'%$-/%#'+!u;!
•! C! 5-.%&%#0)! ) " * # ! ) " * T E # ! 5%O%! %#'1+! :%&! )! -#$%&'%()! :+P&%! )! %#'&)5)! 93%!
%7-/-#)/+:!+P:%&O)#5+!)!:)R5);!
!!
c3%&!5-(%&!93%! ) " * # ! ) " * T E # !'&)53(!)!%=>,()$*>=*/"@=%-=K'!:+P&%!^!93%!
I)#N)/+:!,%7)!+P:%&O)01+!5%!u;!
2$%* =:=&EH$M* ?=* >=E$/?* >'* $4?=%F'()$* >=* [* @$"-/",'%&$?* =:'@-'&="-=* @$&* '?*
&=?&'?* >_F/>'?* G,=* -I"`'&$?* ?$4%=* '* ="-%'>'* AM* ="-)$* ")$* %=>,K/&$?* /"@=%-=K'*
"="`,&'1* ) " * # ! ) " * T E # = ( P*
•! |!5-.%&%#0)! ) " * # ! ) " * T E # !$N)/)Z:%!/"#$%&'()$*&_-,'*&N>/'!%#'&%!)!%#'&)5)!^!
%!)!:)R5)!u;!`+5%!:%&!-#'%&,&%')5)!$+/+!3/!I)#N+!5%!-#.+&/)01+!:+P&%!^X!93%!#1+!
'%&R)/+:!:%!#1+!$+#N%$Y::%/+:!u;!
!
! ! !
# " * WE # = ) " * # ! ) " * T E # !
•! c3)#'+!/)-+&!.+&! ) " * T E # !/%#+&!4! # " * WE # ;!D)R!:%!7N%!$N)/)&!=G,/F$@'()$;!
•! ?/)!5%'%&/-#)5)!+$+&&Y#$-)! D ' !,+5%!'+&#)&!)!5%$-:1+!:+P&%!)!+$+&&Y#$-)! @& !)-#5)!
/)-:!-#$%&')!H # " @& W D ' # < ( Ja!+!$+#N%$-/%#'+!5)!5-:'&-P3-01+!5%!,&+P)P-7-5)5%:!5%!u!
)b35)!)!&%53(-&!%::)!-#$%&'%()!H # " * WE # ) ( J;!
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
95'
/()*+,&-.*!,N15&!,6$%&!
t! !"#$%&'()$*&_-,'*&N>/'!%#'&%!)!%#'&)5)!^!%!)!:)R5)!u!5+!$)#)7>!
# " * WE # = ) " * # ! ) " * T E # =
!
!
(
( C
!
!
!
= " 9 " @& #
! "" 9 " D ' # 9 " @& T D ' #$%& '
9 " @& T D ' #
$%& ' 9 " @& # & =! ' =!
& =!
!
C
_):! %" @& # = " %" @& + D ' # X!7+I+!
' =!
( C
# " * WE # = "" 9 " @& + D ' # #%$%& '
'
& =! ' =!
!
!
9 " @& + D ' # $
!
+ $%& '
9 " @& #
9" D ' # &
(
( C
9 " @& + D ' #
= "" 9 " @& + D ' #$%& '
=
9
"
@
#
9
"
D
#
&
'
& =! ' =!
!""#""
$
=
!
# " @& + D ' #
( C
= "" 9 " @& + D ' # # " @& + D ' #
& =! ' =!
t!
# " @& + D ' # !4!!)!-#.+&/)01+!/2'3)!%#'&%!)!%#'&)5)! @& !%!)!:)R5)! D ' X!
!
! ! # " @& + D ' # = $%& '
9 " @& + D ' #
9 " @& # 9 " D ' #
= $%& '
9 " D ' T @& #
9" D ' #
= $%& '
9 " @& T D ' #
9 " @& #
;!
C! /"#$%&'()$* &_-,'* &N>/'! # " * WE # 4! )! /45-)! 5):! -#.+&/)0]%:! /2'3):!
%#'&%!):!5-O%&:):!%#'&)5):!%!:)R5):;!
t! `&+O)Z:%!')/P4/!93%! # " * WE # = ) "E # ! ) "E T * # ;!
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
96'
/()*+,&-.*!,N15&!,6$%&D!5,!#9#,0:*!
?/)! .+#'%! ^! ,&+53(! :R/P+7+:! $+/! ,&+P)P-7-5)5%:! {! '+! *+! J} X! +:! 93)-:!
)'&)O%::)/!3/!$)#)7!$+/!)!/)'&-(!5%!,&+P)P-7-5)5%:!5%!'&)#:-01+!
!
! ! ! ! !
#' * ( ! * $
%! * ' * ( & ;!
%
&
%' ( ! * ' *&(
C! -#$%&'%()! 93%! '%/+:! :+P&%! +:! :R/P+7+:! ,&+53(-5+:! ,%7)! .+#'%! ^! 4!
/%#:3&GO%7>! ) " * # = ) (! '+! *+! J ) = !+)J !P-':d:R/P+7+;!
2P1* '0*]=*G,'"-$*%=>,K/&$?*'*/"@=%-=K'*?$4%=*A*$4?=%F'">$*'*?'I>'*[\*
*
40*S'H@,H=*'*=G,/F$@'()$*>$*@'"'H*=*'*/"#$%&'()$*&_-,'* # " @' + D! # P*
$%&! +7!<.=>?! % " D ' # =
" %" @& # %" D ' T @& # !
&
!
!
)) M M *
!! { %" D! #+ % " D' #+ % " D* #} = + + + , !
- O !K !K .
) "E # = ) ( ) O+M !K+M !K ) = !+MM !%&'()(@A%?B?!
) "E T * # = " %" @& # ) "E T @& # =
!
!
&
! / ' !0 ! /! ' 0 ! / ! '0
= ) 1 +(+ 2 + ) 1 + +( 2 + ) 1 (+ + 2 = (+O'
' 3 * *4 * 3* * 4 J 3 * *4
!
C!-#.+&/)01+!/2'3)!/45-)!O)7%X!,+&')#'+X! # " * W E # = !+MM ! (+O' = (+ J* !P-':d:R/P+7+;!
":'+!:-I#-.-$)!93%!)!+P:%&O)01+!5)!:)R5)!5+!$)#)7!P)-L+3!)!-#$%&'%()!5%! ) " * # = !+ )J !
,)&)!TX\m!Z!SXm[!U!SXn[!P-':d:R/P+7+;!
PJ! 6+/+! # " * W E # = ) "E # ! ) "E T * # = ) " * # ! ) " * T E # X! $+#$73R/+:! 93%! )! %93-O+$)01+!
5%O-5)!)+!$)#)7!4! ) " * E # = ) " * # ! # " * W E # = (+K* !!P-':d:R/P+7+;!
M%&G!93%!)!+P:%&O)01+!5+!:R/P+7+! D! !)b35)!)!5%$-5-&!:%!+!:R/P+7+! @' !.+-!%/-'-5+!
,%7)!.+#'%e!f)/+:!O%&>!
!
!
# " @' + D! # = $%& '
% " D! T @' #
*
= $%& ' = !(+ )' !%&'()(@A%?B?!
%" D! #
)
6+#$73-Z:%!93%!%:')!+P:%&O)01+!%:,%$R.-$)!)3/%#')!)!-#5%.-#-01+!:+P&%! @' ;!
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
97'
/()*+,&-.*!#!#(1+*0%&D!
$#)%(%-O#'!#!+#:&-O#'!%,0*+1&(1#'!!
,
*+,E,X,B/35RB058,/$0/2Y35/8,;%.,%;%33Z1;5/8,@&,0,D'M, & = !+'+CCC+ ( ,,0,, ' = !+'+CCC+ C ,
,
,
5=/0<.<;;P:.&/,",
%,N/;&>O860*,
%,N/;&>O8&-0*080E,
!63*<&()*+#',-*"
=()*+#',-*"#>36'!
,
O>;&/-0<.<;;P:.&/-,",
#"@ & # = ! $%& ' %"@& #,
8(3+*0&',
#"@ & WD ' # = $%& '
%"@& +D ' #
%"@ & #%"D ' #
,
=()*+#',-*"#>36'"#?%&'!
"519%3./DE%,.<65/#,
,
(
)"* # = " %"@& ##"@& # = ,
(
( C
#"*WE # = " " %"@& +D ' ##"@& WD ' # = ,
&=! ' =!
&= !
= ! " %"@ & #$%& ' %"@& # ,
& =!
( C
= " " %"@& + D ' #$%&'
& =! '=!
%"@& + D ' #
%"@ & #%"D ' #
,
,
•! ) " * + E # = ) " * # + ) "E T * # = ) "E # + ) " * T E # !
•! ) " * + E # $ ) " * # + ) "E # !
•! ) " * T E # $ ) " * # !
•! ) "E T * # $ ) "E # !
•! # " * WE # = ) " * # ! ) " * T E # = ) "E # ! ) "E T * # !
•! # " * WE # = ) " * # + ) "E # ! ) " * + E # !
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
98'
/()*+,&-.*!,N15&!,6$%&P!#(1+*0%&'!
E*($%E%*(&%'!#!$%&F+&,&!$#!Q#((!
v! /3-'+! .G$-7! 5%! %:')P%7%$%&! ):! &%7)0]%:! %#'&%! ):! 5-.%&%#'%:! %#'&+,-):!
$+#5-$-+#)-:! %! %#'&%! %:'):! %! )! -#.+&/)01+! /2'3)! /45-)! :%! 3:)&/+:! +!
:%I3-#'%!5-)I&)/)!5%!f%##>!
["\#
["\T]#
["]#
I"\+]#
["]T\#
["\+]#
!
F%,%'%/Z:%! )93-! ):! &%7)0]%:! bG! $+#N%$-5):;! E&)! $+#.-&/%Z):! $+/! +!
5-)I&)/)}!
•! ) " * + E # = ) " * # + ) "E T * # = ) "E # + ) " * T E # !
•! ) " * + E # $ ) " * # + ) "E # !
•! ) " * T E # $ ) " * # !
•! ) "E T * # $ ) "E # !
•! # " * WE # = ) " * # ! ) " * T E # = ) "E # ! ) "E T * # !
•! # " * WE # = ) " * # + ) "E # ! ) " * + E # !
,
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
1:'
/()*+,&-.*!,N15&!,6$%&!
C!-#.+&/)01+!/2'3)!/45-)!4!:%/,&%!#1+!#%I)'-O)>!
B#*+#,&!
a=8'* A[* $* @$"8,"-$* >/?@%=-$* >$?* E'%=?* +:/M;80P* 3* /"#$%&'()$* &_-,'*
&N>/'* ="-%=* A* =* [* ?'-/?#'K* !+Ab[0* !* 5M* =&* G,=* '* /L,'H>'>=* ?c* N*
?'-/?#=/-'*00'*:*=*;*#$%=&*=?-'-/?-/@'&="-=*/">=E=">="-=?P*
C#,*('1+&-.*!
!`&+O%/+:!93%!.!+Ab[0*"*5;!M)P%/+:!93%! $%& ' / = $1 / $%& ' 8 >!
! # " * WE # = ! $%& 8"" %" @& + D ' #$1
&
'
% " @& T D ' #
% " @& #
= $%& 8"" %" @& + D ' #$1
&
'
% " @& #
!
%" @& T D ' #
!6+/+! $1( $ ( ! ! >!
# %" @& #
$
! # " * + E # $ $%& 8"" %" @& + D ' # %
! !& = $%& 8"" #' %" @& # % " D ' # ! %" @& + D ' # $( =
%' %" @& T D ' # &(
& '
& '
!
!
#
$
%
&
%
! = $%& 8 " % " @& # " % " D ' # ! "" % " @& + D ' # & = ( !
% &
&
'
& '
!
"
#"
$
!
"
#"
$
!"
"
#""
$
%
&
!
'
(
!
!
! ! # " * WE # $ ( !
<+'%Z:%!93%! # " * + E # = ( !??=! $1( $ ( ! ! ! !! ( = ! ! !!??=! %" @# = % " @ T D # !
!!:%!:!%!;!.+&%/!%:')'-:'-$)/%#'%!-#5%,%#5%#'%:X!
@PGP>P*
C#,*('1+&-.*!&:1#+(&1%2&D!
M%#5+! # " * + E # = ) " * # + ) "E # ! ) " * + E # ! %! ) " * + E # $ ) " * # + ) "E # X! %#'1+!
#%$%::)&-)/%#'%!
# " * + E # ) ( ;! M%! A! %! [! .+&%/! %:')'-:'-$)/%#'%!
-#5%,%#5%#'%:X!%#'1+! ) " * + E # = ) " * # + ) "E # !! # " * + E # = ( ;!! @PGP>P*
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
19'
/()*+,&-.*!,N15&!,6$%&!
6+/+!!HAa[J!"!S!%!!HAa[J!U!CHAJ!Z!CHAx[J!!!
5467!!!546R77!
H%X!')7!$+/+!)#'%:X!gH^J!U!gH^xuJ!''#!^!%!u!.+&%/!%:')'-:'-$)/%#'%!-#5%,%#5%#'%:J!
*:')! 5%:-I3)75)5%! /+:'&)! 93%! :%! $+7+$)&/+:! &%:'&-0]%:! )! 3/! $+#b3#'+! ^!
H.)(%#5+Z+!5%,%#5%&!5%!+3'&):!+$+&&Y#$-):J!>/&/",/&$?*'*?,'*="-%$E/';!
v!+!93%!)$+#'%$%!$+/!):!7R#I3):!H,+&'3I3Y:X!.&)#$Y:X!%'$;J;!
`+&!%L%/,7+!%/!-#I7Y:!HVm!7%'&):!/)-:!%:,)0+J>!
•! G*$%)%E&-.*!7%'&)!)!7%'&)X!$+#:-5%&)#5+!$)5)!7%'&)!%93-,&+OGO%7>!
M1+!,&%$-:+:! ! $%& ' 'N = )+NJ !5RI-'+:!P-#G&-+:d$)&G$'%&;! H%#'&+,-)!/GL-/)J!
•! G*$%)%E&-.*!7%'&)!)!7%'&)!'%#5+!%/!$+#')!):!,&+P)P-7-5)5%:!&%7)'-O):!5%!
+$+&&Y#$-)>!
M1+!,&%$-:+:!\XS[!5RI-'+:!P-#G&-+:d$)&G$'%&;! !
!
H%#'&+,-)!$+#5-$-+#)7J!
•! G*$%)%E&-.*!,)7)O&)!)!,)7)O&)!'%#5+!%/!$+#')!)!.&%93Y#$-)!&%7)'-O)!5):!
,)7)O&):>!
MQ!:1+!,&%$-:+:!TXmm!5RI-'+:!P-#G&-+:d$)&G$'%&;!
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
!
H%#'&+,-)!$+#5-$-+#)7J!
11'
/()*+,&-.*!,N15&!,6$%&!#!E&0&E%$&$#!$#!
E&(&:!
!
! ! ! ! ! ! # " * WE # = ) " * # ! ) " * T E # !
!
+!
!
!
6=>?9@AB!"B!C9=>6!
0
0
0
0
Q0/0&:.8;28B/0=R7&/0-<";80
/0$<:280780&:$<;=/ST<0*0
+!
6DEAF9GBHI9!
Q0/0&:.8;28B/0=R7&/0-<";80/0$<:280
789<&-0780-80<"-8;O/;0/0-/,7/07<0./:/6M0E0
C!5-.%&%#0)!%#'&%!%:'):!53):!93)#'-5)5%:!4!)!/"#$%&'()$*&_-,'*&N>/'*8!4!
3/)!/%5-5)!5)!-#.+&/)01+!93%!,)::+3!)'&)O4:!5+!$)#)7;!
!*
R,'"-$*&'/$%*#$%*'*=G,/F$@'()$*&="$%*N*'*
G,'"-/>'>=*>=*/"#$%&'()$*G,=*E'??'*'-%'FN?*>$*@'"'HP*
]=#/"/()$1*
!
C!@'E'@/>'>=*>$*@'"'H!4!+!O)7+&!&J:/&$!5)!-#.+&/)01+!/2'3)!/45-);!
I- = ./L # " * WE # !HP-':d:R/P+7+J!
9* " @#
f-:'+! +! $)#)7! :%&! .-L+! )! /)L-/-()01+! 5%O%! .)(%&Z:%! &%7)'-O)/%#'%! =:!
,&+P)P-7-5)5%:!!5)!.+#'%;!
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
12'
39#,0:*!$#!E&0&E%$&$#!$#!E&(&:!
'()*+,-#.$!C+=+B!%&=-,&?!(&AD',&*?!3EF&=+,4!(4AA.',&*!*G+==.BHI!F<C7!
%"( T !# = %"! T (# = 9 !%! %"( T (# = %"! T !# = ! ! 9 ;!
(
!^4
/
/ (
4
\
]
4
!
/
!^4
/ !
,
6+/+! # " * WE # = ) "E # ! ) "E T * # !O)/+:!$)7$37)&!%:'):!%#'&+,-):>!
C! %#'&+,-)! CH[J! 4! /GL-/)! 93)#5+! ):! :)R5):! :1+! %93-,&+OGO%-:! !! %#'&)5):!
%93-,&+OGO%-:;!<%::%!$):+!CH[J!U!T!P-'d:R/P+7+;!
(
) "E * # = " % " @& # ) "E @& # = %" * = (# ) "E * = (# + %" * = !# ) "E * = !# =
& =!
= %" * = (# ) "! ! 9+ 9 # + % " * = !# ) " 9+! ! 9 # = #" 9#
!"#"$
!"#"$
#" 9 #
!
#" 9 #
!
C!$),)$-5)5%!O)7%X!,+&')#'+X! I- = ! ! #" 9# X!-:'+!4>!
S'E'@/>'>=*>$*@'"'H*4/"J%/$*?/&N-%/@$!" I- = ! + 9 $%& ' 9 + "! ! 9#$%& ' "! ! 9# !
!
, I-,
!,
,
_0, %"( T !# = % "! T (# = (+M +, 582%, <+, 6/6/, 7./,
(CK,
60203.51/6/, 8/:6/, "!, %7, (#, 20.%8, M(`, 60,
43%P/P5$56/608, 60, /;032/3.%8, 1/, 0123/6/,
30/$.0120,01B5/6/, !,/,;/4/;56/60,6%,;/1/$,<,
17$/, !, 10880, ;/8%, %, ;/1/$, 1E%, 803B0, 4/3/,
1/6/S, P/82/, a6052/3, 7./, .%06/, /%, /3a, 1%,
608251%C,
(CJ,
(C),
(C',
(, (C', (C) (CJ, (CK, !, 9
,
,
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
13'
39#,0:*!$#!E&0&E%$&$#!$#!E&(&:!
'()*+,-#/$!C?AJ=&*+KL?!M&+!(+'DB&'.!
,
%8,=,(
%8,=,(+(!,
%80=,(+!,
"
gG! [! $)#)-:! %#O+7O-5+:>! $)#)7! ):$%#5%#'%X! $)#)7! )! P+&5+! %! $)#)7!
5%:$%#5%#'%;! `)&)! 5%'%&/-#)&! )! $),)$-5)5%! 5+! :-:'%/)! I7+P)7! '%/+:! 5%!
,&-/%-&+! $)7$37)&! )! /)'&-(! 5%! ,&+P)P-7-5)5%:! 5%! '&)#:-01+! I7+P)7!
/37'-,7-$)#5+!):!/)'&-(%:!5%!,&+P)P-7-5)5%!5%!'&)#:-01+!-#5-O-53)-:>!
!
#(+OO (+(!$ #!+( ( $ #(+O (+! $ # (+KO' (+!(K$
U %"E T * #V = %
&%
&%
&=%
&!
' (+(! (+OO ( ' ( !+( ( ' (+! (+O ( ' (+!(K (+KO'(
E!5-)I&)/)!5%!'&)#:-01+!I7+P)7!5%:'%!$)#)7!iM6!4>!
(+KO'
(/
\
(+!(K
!/
/ (
]
(+!(K
(+KO'
/ !
!
C!$),)$-5)5%!5+!:-:'%/)!I7+P)7!4X!,+&')#'+>!
!
I- = ! + (+KO'$%& ' (+KO' + (+!(K$%& ' (+!(K = (+M! !P-'d:R/P+7+!
HC:!,&+P)P-7-5)5%:!N-,Q'%:%!:1+!/3-'+!/)-:!%7%O)5):!93%!#3/!$):+!&%)7;!
@+/)&)/Z:%!,)&)!:-/,7-.-$)&!+:!$G7$37+:J;!
!"#$%&'(&')*+#$,&-.#'
/"(%(&0'("'%*+#$,&-.#'
14,
1.3.
Teorema da codificação de canal
•
Ritmo de informação
•
1
Ritmo (ou taxa) de informação
• Se a fonte de entropia H(X) emitir uma sequência de n 1 símbolos a
informação total a ser transferida é de nH ( X ) bits.
• Se a fonte produzir r símbolos/s a duração da sequência de n símbolos é
n/r segundos.
• Portanto, a informação deve ser transferida à razão média de:
R=
informação total nH ( X )
=
= rH ( X ) bits/s
duração total
nr
Esta é a taxa de informação da fonte.
Se a fonte produzir símbolos com diferentes durações τ i (segundos) o ritmo,
ou taxa, de informação pode ser calculado alternativamente como
R=
H (X )
τ
bits/s
em que τ é a duração média de cada símbolo,
M
τ = P1τ1 + P2τ 2 + ... + PM τ M = ∑ Piτ i .
i =1
2
O teorema da codificação de canal
(aplicado a canais discretos sem memória)
A entropia representa a informação esperada por cada símbolo de fonte.
• Se tivermos duas fontes com iguais entropias, aquela que produzir mais
símbolos por unidade de tempo vai colocar mais exigências no sistema de
comunicações.
(imagine duas pessoas a ler o mesmo texto escrito numa língua que domina mal.
Uma delas lê depressa. Qual é a que entende melhor?)
• O ritmo de informação mede a quantidade de informação produzida
num certo intervalo de tempo.
• Existem limitações físicas fundamentais à transferência de informação
(ruído, largura de banda, …), que se reflectem na capacidade do canal:
• A capacidade do canal (em bits/s) mede a quantidade de informação
que um canal pode transferir por unidade de tempo.
Shannon relacionou estes dois conceitos através do teorema da codificação
de canal, também chamado Teorema Fundamental da Teoria da
Informação:
Dado um canal de capacidade C e uma fonte com ritmo de
informação R, então se R ≤ C existe uma técnica de codificação
tal que a saída da fonte pode ser transmitida através do canal
com uma frequência arbitrariamente pequena de erros, apesar
da presença de ruído.
Se R > C, não é possível a transmissão sem erros.
3
O teorema da codificação de canal
aplicado a canais discretos sem memória
(formulação alternativa)
Teorema:
“Uma fonte X de entropia H(X) produz símbolos à razão de um símbolo por
cada Ts segundos. Consideremos um canal discreto sem memória de
capacidade Cs (bits/símbolo!) e que seja usado uma vez em cada Tc
segundos. Então, se
H ( X ) Cs
≤
,
Ts
Tc
existe uma técnica de codificação dos símbolos da fonte que permite que os
símbolos transmitidos através do canal possam ser recuperados com uma
probabilidade de erro arbitrariamente pequena.
Se, pelo contrário,
H ( X ) Cs
, então não é possível transmitir os símbolos e
>
Ts
Tc
recuperá-los com uma probabilidade de erro arbitrariamente pequena.”
Conversão de Cs (bits/símbolo) em C (bits/s):
C=
Cs
Tc
4
Aplicação do “Teorema da Codificação do
Canal” a um canal binário simétrico
Considere-se uma fonte binária a gerar símbolos equiprováveis de duração
Ts segundos, ou seja, a produzi-los à taxa de r = 1 Ts símbolos por segundo.
Sendo os símbolos binários equiprováveis, a entropia da fonte vale H ( X ) = 1
bit/símbolo e a taxa de informação da fonte é R = rH ( X ) = 1 Ts bits/s.
1 símbolo em
Ts segundos
1 dígito binário em
Tc segundos
capacidade por unidade
de tempo = Cs/Tc bits/s
(r=1/Ts)
Fonte
binária
Codificador de
canal binário
rH(X) bits/s
Canal binário
simétrico
Rc=k/n
O codificador (de canal!) produz um símbolo binário em cada Tc segundos, o
qual é transmitido através de um canal binário simétrico (BSC) – que,
portanto, é usado uma vez em cada Tc segundos. Assim, a capacidade do
canal por unidade de tempo é C = Cs Tc bits/s.
De acordo com o teorema da codificação do canal, terá de ser
H ( X ) Cs
⇒
≤
Ts
Tc
Mas
1 Cs
≤
Ts Tc
⇒
Tc
≤ Cs
Ts
Tc
= Rc (taxa do código, ver a seguir), pelo que
Ts
Rc ≤ Cs
Como a capacidade do canal BSC é Cs = 1 − Ω( p) :
Rc ≤ 1 − Ω( p)
(canal BSC)
5
Aplicação do “Teorema da Codificação do
Canal” a um canal binário simétrico
(contin.)
Porque é que
Tc
= Rc ?
Ts
Antes da codificação
Ts
k=4
Duração do bloco: 4Ts
Tc
n=7
Duração do bloco: 7Tc
Depois da codificação
À razão
k
= Rc chama-se taxa do código.
n
Como a duração dos blocos é a mesma:
kTs = nTc
ou, neste caso,
4Ts = 7Tc ⇒ Tc Ts = 4 7 = Rc
Em resumo, temos duas maneiras de exprimir o teorema da codificação de
canal:
• Com a capacidade expressa em bits/símbolo, Cs:
Rc ≤ Cs
• Com a capacidade expressa em bits/s, C:
R = rH ( X ) ≤ C
bits/s
bits/símbolo
C = Cs Tc
6
1.#.
Teorema da codificação de fonte
!
!
Redundância
!
códigos unicamente descodificáveis
!
códigos sem prefixos
!
desigualdade de <raft-McMillan
!
extensões
Codificação de fonte
@ueremos transformar as mensagens de uma fonte num conjunto de símbolos de
modo que seja Eocupado menos espaçoF ou que a informação da fonte Edemore
menos tempo a ser transmitidaF. @ueremos fazê-lo sem perdas: a operação inversa de
descodificação ou descompressão deve dar origem exactamente às mesmas
mensagens originais. Ora,
!
A caracterização de uma fonte discreta é fácil se os símbolos forem
independentes e equiprováveis (a entropia é máxima).
!
Essa caracterização já é mais difícil se os símbolos não forem independentes (a
probabilidade de um símbolo depende dos símbolos passados e a entropia é
menor).
!
Shannon provou que, se dividirmos a mensagem em blocos de letras ou palavras
(no caso de texto), podemos calcular a entropia de cada bloco (U símbolo) pela
mesma fórmula usada com símbolos independentes e assim aproximar-nos da
entropia da fonte, considerando os blocos muito compridos.
Existe alguma relação entre a entropia e o n*mero médio de dígitos bin2rios por
símbolo necessário para codificar uma mensagemV Sim, existeW
!
A questão está em descobrir como codificar eficientemente os símbolos da fonte,
tendo cada um uma certa probabilidade de ocorrer.
No caso dos símbolos da fonte não serem equiprov2veis o código óptimo tem em
conta as diferentes probabilidades de ocorrência usando palavras com
comprimentos vari2veis.
!
Convém agrupar os símbolos da fonte antes de codificar ou comprimir.
Teorema da /odifi/ação de fonte
1
.epresentação de símbolos por dígitos
binários8 dois exemplos:
!" "#$%&'( )* *+,-*.*- ,/0 12 3*,4(+ 5 67 5 89 : ;< +=0>/4/+
!
Precisaríamos de log9 50 U 5,62 dígitos binários_símbolo. A codificação faz-se atribuindo um
número binário com 6 dígitos a cada símbolo (desperdiçando 26 - 50 U 14 números binários).
!
Mas em 50 caracteres existem 503 U 125 000 grupos diferentes possíveis de 3 caracteres. Por
outro lado 17 dígitos binários podem ser combinados de 131 072 maneiras diferentes (217).
! Se dividirmos o texto em blocos de 3 caracteres sucessivos poderemos atribuir a
cada bloco um número binário de 17 dígitos.
Se tivessemos representado cada carácter por 6 dígitos binários precisávamos de 18 dígitos
binários por cada grupo de 3 caracteres, em vez de 17.
Conclusão: agrupando os símbolos a compressão ou codificação é mais eficiente.
#" ?'@4A+ BCD 4*3-(+ 5 *+E(F/G
!
Codificação letra a letra, consideradas equiprováveis:
São precisos 4,76 dígitos binários_carácter
!
Codificação letra a letra tendo em conta as probabilidades relativas de ocorrência:
!
Codificação palavra a palavra tendo em conta a frequência relativa das palavras:
Shannon calculou a entropia do inglês entre 0,6 e 0,13 bits_carácter.
1
In J. R. Pierce, EAn Introduction to Information TheoryF, 2ª edição, Dover, 1980.
2
.edund<ncia
!
A influência entre símbolos reduz a entropia.
Exemplo: linguagem, textos escritos: cada letra depende da(s) precedente(s) ou até das
palavras anteriores, devido a regras impostas pela linguagem.
A seguir à letra H vem sempre I.
!
A influência mútua reduz a incerteza, logo, reduz a quantidade de informação.
Trata-se de uma fonte redundante: significa qe há símbolos produzidos pla font qe não
são absolutament essenciais para a transmssão da informação.
!
A redundância de uma sequência de símbolos mede-se em função da redução de
entropia ocorrida:
%&'()'*)+,-: E = 1 −
H (Al B)
H (B)
HCADBE — supondo símbolos dependentes
HCBE — supondo símbolos independentes
Num exemplo anterior em que H(A l B) = 0,9328 bits_símbolo e H(B ) = 1,287
bits_símbolo existe uma redundância na informação da fonte de E U 27,5n.
!
Numa comunicação eficiente a redundância é indesejável (a mesma informação
poderá ser transmitida usando menos símbolos).
MAS ... ajuda a resolver ambiguidades se a mensagem for recebiga com errus.
!
A codificação para transmissão óptima pretende:
! reduzir a redundância EineficienteF
→
códigos de fonte (compressão)
! acrescentar redundância EeficienteF
→
códigos de canal
3
Codificação de fonte
Consideremos uma fonte discreta de entropia HCBE a gerar símbolos à cadência
de r símbolos_s. O ritmo de informação é, como se sabe, R = rH ( B ) bits_s.
. /& 0(,/&123/ +3',4,+-1 &/5&/ /627383/ -51-9:/ '& '6;,53/ 7,)<1,3/=
."mbolos
discretos 4
0onte
discreta
!"gitos bin+rios
2odificador
de fonte
R G rHCBE bits-s
2ana3 sem
ru5do
rb binits-s
.5annon mostrou 8ue a informação proveniente de 8ual8uer fonte
discreta sem memória pode ser codificada como d"gitos bin+rios e
transmitida através de um canal sem ru"do ? taxa bin+ria de r b ≥ R d"gitos
bin+rios-sA Bão é poss"vel fazD-lo a uma taxa inferior F rb < R GA
Esta é uma manifestação do famoso Eteorema da codificação de fonteF, de
Shannon, demonstrado mais adiante.
OBS: Aos dígitos binários vamos passar a chamar binits, para evitar confusões com a
unidade de informação EbitF. Só lhes deveremos chamar bits se não houver
ambiguidades de interpretação.
4
!
ponte de M símbolos equiprováveis produzidos ao ritmo r → R = r log M
Todos os símbolos transportam a mesma quantidade de informação.
!
ponte de símbolos com diferentes probabilidades Pi → R = rH ( B ) < r log M
!
A transmissão eficiente requer um processo de +3',4,+->?3 que tenha em conta a
quantidade variável de informação por símbolo.
R G r HCBE
Honte discreta
sem memIria
rbΩ( p ) ≤ rb
Jodificador de
fonte bin+rio
r q s"mbolos-s
rb q binits-s
Jonverte os s"mbolos da fonte em palavras de cIdigo
constitu"das por ni d"gitos bin+rios produzidos a uma taxa rb
•
O codificador comporta-se como uma fonte binária com entropia Ω(p) e taxa de
informação rb Ω( p ) ≤ rb log 2 = rb binits_s.
•
O comprimento médio das palavras de código é igual a N = " Pi ni .
M
i =1
A codificação não gera informação adicional nem destrói a informação @. o
código for decifrável de uma única maneira, sem ambiguidades Ccódigos unicamente
decifr2veis ou descodific2veisE. Nesse caso as taxas de informação à entrada e saída
do codificador são iguais:
rH ( B ) = rb Ω( p ) ≤ rb
!
rb ≥ rH ( B )
e
H (B ) ≤
rb
=N
r
CTeorema da codificação de fonteE
5
Codificação de fonte e ritmo de
informação8 um exemplo
Uma fonte emite r U 2000 símbolos_s seleccionados de um alfabeto de M U 4
elementos, com as probabilidades de ocorrência indicadas. Se quisermos codificar
estes símbolos através de dígitos binários qual é o número mínimo de binits que
podemos transmitir por unidade de tempoV
xi
Pi
Ii
A
1_2
1
B
1_4
2
C
1_8
3
D
1_8
3
R.: A entropia desta fonte vale
H( B ) =
1
2
×1 +
1
4
× 2 + 18 × 3 + 18 × 3 = 1, 75 bits_símbolo
(o máximo seria log M G 9)
A respectiva taxa de informação vale R U 2000 × 1,75 U 3500 bits_s
Uma codificação de fonte apropriada permitirá transmitir a informação da fonte
a uma taxa binária rb ! 3500 binits_s. Não é possível transmitir com menos dígitos
binários por unidade de tempo.
Repare-se nas dimensões que nos aparecem neste exemplo:
srt — símbolos_s
sRt — bits_s
srbt — binits_s
6
Teorema da codificação da fonte e
desigualdade de >raft
"
Num código binário unicamente descodificável é condição necessária que os
comprimentos ni das palavras respeitem a desigualdade (ver Anexo 1)
M
K = " 2− ni ≤ 1
CDesigualdade de KraftE
i =1
! Se o alfabeto do código tiver tamanho D a desigualdade de <raft é
M
K = " D − ni ≤ 1
i =1
"
.
O teorema da codificação da fonte, de Shannon, estabelece que, com códigos
binários unicamente descodificáveis, o comprimento médio N é limitado por
H(B ) ≤ N < H( B) + ε
ε > 0, arbitrariamente pequeno
! Com codificação óptima: N = H (B ) . Na prática: N > H( B ) .
! A eficiência da codificação mede-se calculando a razão
entropia da fonte
comprimento médio das palavras de código
! A eficiência é igual a
R r/H ( B ) H ( B )
=
=
≤ 1.
rb
N
r/ N
! Codificação mais simples: código de comprimento fixo (exemplo: ASCII).
Neste caso a desigualdade de <raft toma a forma K = M.2
!
N ≥ log 2 M
!
eficiência =
−N
≤1
H(B ) H(B )
≤
N
log M
! Para aumentar a eficiência é preciso diminuir o comprimento médio N , o que se
consegue com os códigos de comprimento vari2vel:
Aos símbolos que ocorrem com mais frequência devem corresponder palavras de
código mais curtas que as que correspondem aos símbolos mais raros.
7
Codificação binária de uma
fonte discreta sem memória
@A@MCDO8 fonte discreta sem memória produzindo 4 símbolos A, B, C e D com
probabilidades 1_2, 1_4, 1_8 e 1_8, respectivamente.
Temos muitas possibilidades de codificação. Eis quatro possíveis:
J&
K&
AB',;3 C
AB',;3 CC
AB',;3 CCC
AB',;3 CD
A
1_2
00
0
0
0
B
1_4
01
1
01
10
C
1_8
10
10
011
110
D
1_8
11
11
0111
111
N
2,0
1,25
1,875
1,75
K
1,0
1,5
0,9375
1,0
(comprimento fixo)
("comma code") ("tree code")
!
v(w) U 1,75 bits_símbolo (exemplo anterior)
!
Código I:
Eficiência U
!
Código II:
N U 1,25 x H(B), K U 2-1 y 2-1 y 2-2 y 2-2 U 1,5 z 1 ! não é unicamente
H(B )
= 88n
N
(ex.:10011 pode ser BAABB ou CABB ou CAD, etc.)
!
Código III:
{ unicamente decifrável (cada palavra começa por 0).
Eficiência U
!
Código I|:
decifrável.
H(B )
= 93n
N
Nenhuma palavra de código aparece como o prefixo de outra palavra de
código. { um código óptimo para esta fonte porque N U H(B) e K U 1.
Eficiência U
H (B )
= 100n
N
(Exemplo: 110010111 ↔ CABD)
8
Códigos unicamente descodificáveis
código unicamente
para cada sequência de fonte de comprimento finito a
descodific2vel
sequência de letras de código que lhe corresponde é diferente
da sequência de letras de código correspondente a qualquer
outra sequência de fonte.
Existe uma classe especial de códigos unicamente descodificáveis que satisfaz
uma restrição chamada condição de prefixação. Chamar-lhes-emos códigos sem
prefixos:
código sem prefixos
{ um código no qual nenhuma palavra de código é o
(código instantâneo)
prefixo de qualquer outra palavra de código.
Seja xi G Cxi,T, ... , xi,niE a palavra de código de ordem i. @ualquer sequência
constituída por uma parte inicial de xi (isto é, (xi,T, ... , xi,k),
k ! ni) chama-se um
prefixo de xi.
Para descodificar uma sequência de palavras de código gerada por um código
sem prefixos começa-se no princípio de cada palavra e descodifica-se uma a uma.
Sabemos que chegámos ao fim de cada palavra porque essa palavra de código não é
prefixo de qualquer outra (veja-se o anterior código I|, por exemplo).
9:
Códigos sem prefixos
"epresentação gráfica através de "árvores"
A 0
B 10
C 110
D 111
Nós de 3ª ordem
Nós terminais
Nós de 2ª ordem
Nós de 1ª ordem
10
0
0
0
Raíz
110
0
111
1
1
1
Nós
intermédios
!
Num código sem prefixos as palavras de código terminam sempre nos nós terminais.
!
Para descodificar, o receptor "sobe pela árvore", desde a raiz.
!
Para que N — número médio de dígitos binários por símbolo de fonte — seja minimizado
convém escolher as palavras de código de tal maneira que cada ramo que sai de um nó seja
equiprovável (idealmente).
Exemplo: Código de Shannon-pano.
!
Se cada ramo for equiprovável e o código tiver um alfabeto de D elementos, então
−
P(ai ) = D ni
ai q símbolo da fonte
ni q comprimento da palavra de código correspondente
Exemplos de códigos de fonte sem prefixos:
E
@F-))3)GH-)3
E
I(442-)"
99
Teorema da codificação de fonte, de
Hhannon8 demonstração
Teorema8 Dada uma fonte B com entropia HCBE e dado um alfabeto de código com
D símbolos, é possível atribuir palavras de código às letras da fonte de tal maneira
que a ,/')&FL/ )* E-*M&J(FL/ N +(3&+M*&3( e o comprimento médio das palavras de
código, N , satisfaV
N<
H( B )
+1
log D
Para qualquer conWunto %'&,(0*'3* )*+,/)&M&,#.*4 de palavras de código temXse
também
N≥
H( B )
log D
Demonstração8
H( B )
, ou H(B ) − N log D ≤ 0 .
log D
Sejam P(a1), P(a2) ... P(aM) as probabilidades das letras da fonte e sejam n1, ..., nM os
comprimentos das palavras de código respectivas:
Mostremos que N ≥
M
M
1
H ( B ) − N log D = " P (ai )log
− " P(ai )ni log D =
P
a
(
)
i
i =1
i =1
−
D ni
= " P (ai )log
P (ai )
i =1
M
Como log V ≤ ( V − 1) log e para z z 0, então
≤1 $
1 $$
#!
"#"
!
"#"
−
D ni
−
H ( B ) − N log D ≤ log e" P (ai )s
− 1t = log e % " D ni − " P(ai ) &
%
&
P (ai )
i
i
i
%'
&(
! H ( B ) − N log D ≤ 0
A igualdade verifica-se para
−
P(ai ) = D ni
1#i#M
(Continua)
91
(Contin.)
Provemos agora que N <
H( B )
+1 :
log D
−n
Como ni tem de ser inteiro poderemos aproximar P(ai ) = D i escolhendo ni
como o inteiro que satisfaz
D − ni ≤ P(ai ) < D − ni +1
1#i#M
(*)
Somando em i:
"D
−ni
i
!
≤ " P (ai ) = 1
(<raft...)
i
existe um código sem prefixos com estes comprimentos.
@uanto ao 2~ membro de (*), tomemos logaritmos:
log P(ai ) < (− ni + 1)log D
Multiplicando por P(ai) e somando em i:
#
$
" P(ai )log P(ai ) < " P(ai )log D −n +1 = %" P(ai )(−ni + 1) & log D =
i
i
%""
"&"""
'
'
i
(
i
−H ( B )
#
$
%
&
= % −" P (ai )ni + " P (ai ) & log D
% i
&
i &"
%"&"'
%
"
'
%
&
1
−N
'
(
! − H ( B ) < (− N + 1) log D
ou
N<
H(B )
+1
log D
!
−
H (B )
< −N + 1
log D
c.q.d.
92
Kgrupamentos de símbolos de fontes
(MextensõesO)
Seja HCBE a entropia de uma fonte discreta B que gera símbolos independentes
retirados de um alfabeto com M símbolos. Agrupando os símbolos de B em grupos de
Y símbolos obtemos um conjunto aumentado, BY, de MY símbolos chamado Eextensão
de ordem YF de B. A entropia da nova fonte BY está relacionada com a entropia de B
através de
H ( B Y ) = YH ( B )
• Exemplo Z.9 de Haykin, \] edição Cp2g. ^_Èa
As probabilidades dos símbolos de uma fonte ternária (MG`) são
P0 = 1 4
P1 = 1 4
P2 = 1 2
A entropia desta fonte vale H (1 4,1 4,1 2) = 1,5 bits_símbolo. Uma extensão de
segunda ordem produz nove (M9) símbolos com as seguintes probabilidades:
Símbolos de B9
σ0
σ1
σ2
σ3
σ4
σ5
σ6
σ7
σ8
Sequências
correspondentes
de símbolos de
B
p(σ i ),
xbxb
xbxT
sbs9
xTxb
xTxT
xTx9
x9xb
x9xT
x9x9
1 16
1 16
18
1 16
1 16
18
18
18
14
i = 0,1,(8
A entropia da fonte aumentada vale, portanto,
8
H ( B ) = −" p (σ i )log p (σ i ) = 3 ,
2
i =0
que é precisamente igual ao dobro de HCBE, como se esperava.
93
!p#i%&'(o & +,o-te0 &ume-t&3&04 &tr&670 3e e8te-09e0 ou
&:rup&me-to0 3e 0;m<o#o0
Admitamos que os símbolos de BY são codificados usando um código
unicamente descodificável. Se N Y for o comprimento médio, por símbolo de BY, das
respectivas palavras de código, N = N Y Y representa o comprimento médio por
símbolo de B. O Teorema da Codificação de Fonte indica que
H (B Y)
H (B Y)
≤ NY <
+1
log 2 D
log 2 D
Como H ( B Y ) = YH ( B ) , poderemos escrever
YH ( B )
YH ( B )
H (B )
H (B )
≤ NY <
+1 !
≤ NY Y <
+1 Y
log 2 D
log 2 D
log 2 D
log 2 D
isto é,
H (B )
H (B )
≤N<
+1 Y
log 2 D
log 2 D
Se não se tivesse feito um agrupamento antes da codificação (ou seja, se Y = 1 ),
teríamos
H (B )
H (B )
≤N<
+ 1,
log 2 D
log 2 D
que representa um intervalo maior para o comprimento médio das palavras de código.
Caso de fontes bin2riasa
Passamos a ter expressões simplificadas:
H ( B Y ) ≤ N Y < H ( B Y ) +1
H (B ) ≤ N < H (B ) +1 Y
94
Codificação de fonte8
considerações diversas
!
Embora não possamos controlar a estatística da fonte de informação, a
codificação de fonte deve obedecer ao seguinte (como nos códigos de Morse,
vuffman, etc.):
Aos símbolos mais frequentes devem corresponder palavras de
código curtasd aos símbolos menos frequentes devem corresponder
palavras compridas.
!
Entropia de fonte binária U 1 bit_símbolo se os símbolos forem equiprováveis.
!
Se os símbolos não forem equiprov2veis a informação média por símbolo é
inferior a um e a fonte apresenta redundencia.
!
A codificação da fonte reduz essa redundância por forma a aumentar a eficiência
da comunicação.
!
A codificação faz-se agrupando a sequência de dígitos binários da fonte em
blocos de n símbolos, passando a formar um novo conjunto de 2 n símbolos.
!
A probabilidade de cada um dos 2 n novos símbolos é calculada e atribui-se a
palavra de código mais curta ao novo símbolo mais provável, e assim por diante:
palavras mais compridas correspondem a símbolos menos frequentes.
Ao conjunto de 2 n novos símbolos chama-se extensão de ordem n da fonte
binária.
95
@xemplo de codificação de fonte binária
com extensões de QR e SR ordem
i
1
2
i
1
2
3
4
i
1
2
3
4
5
6
7
8
(1)
Si
P # S i(1) $ Palavras de
'
(
A
B
(2)
Si
0,9
0,1
(3)
N=
código
0,81
0,09
0,09
0,01
0
10
110
111
de
P # S i(3) $ Palavras
código
'
(
AAA
AAB
ABA
BAA
ABB
BAB
BBA
BBB
H(B ) = 0,469 bits_símbolo
0
1
P # S i(2) $ Palavras de
'
(
AA
AB
BA
BB
Si
ponte original:
código
0,729
0,081
0,081
0,081
0,009
0,009
0,009
0,001
0
100
101
110
11100
11101
11110
11111
N1
= 1,0 binit
1
Extensão de 2ª ordem
N2
N=
= 0,645 binits
2
Extensão de 3ª ordem
N3
= 0,5333 binits
N=
3
2n
n
N n = " Ni P #% Si( ) $& —
'
(
i =1
comprimento médio das palavras de código para a
extensão de ordem n.
N=
Nn
n
—
número médio de símbolos de código por símbolo de
fonte.
n ↑ ! N =
Nn
↓
n
!
menor taxa de símbolos
(Continua)
96
@xemplo de codificação de fonte binária
com extensões de QR e SR ordem
@xemplo com modulação CH> binária8
−5
! Potência recebida U 10 W
−8
Energia de bit: E b = 10 h
! Taxa da fonte U 1000 símbolos_s !
!
N 0 = 10 −9 W HV (densidade espectral de potência do ruído branco)
Se a potência de emissão for fixa a energia de símbolo pode ser aumentada
usando uma extensão porque a taxa de símbolos passa a ser menor.
Em PS< binário a probabilidade de erro sem codificação é
. 2Eb
PB = i,,
- N0
+
).
)
*
Substituindo valores e consultando uma tabela da função @, teremos:
. 2 × 10 −8
PB = i,
, 10 −9
-
+
) = i 20 = 3,9.10 −6
)
*
(
)
Usemos agora extensões:
−8
−8
! Extensão de 2ª ordem ! 645 símbolos_s ! Eb = 1, 55.10 h ! P B = 1,3.10
−10
! Extensão de 3ª ordem ! 533,3 símbolos_s ! PB = 4,5.10
A323 /& 9JK
97
1.#. "ódi&os de fonte para compressão de
dados
!
técnicas de compressão sem perdas
!
códigos baseados em modelos estatísticos e em
dicionários
!
código de Shannon-:ano
!
código de ;uffman
!
código aritmético
!
códigos de >empel-?iv (>?77 e >?78)
Compressão de dados
Técnicas de compressão sem perdas
!odelos estat*sticos
-écnicas baseadas em
dicion2rios
Exemplos de cJdigos
4 56annon-8ano
4 ?empel-Aiv C?A DDE
4 9uffman
4 ?empel-Aiv C?A DFE
4 <odificação aritmética
4 ?empel-Aiv-Gelc6 C?AGE
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
4
<ompressão L !odelização N <odificação
5e o modelo não fornecer probabilidades correctas o codificador comprime
poucoO por muito eficiente Pue seQaR
!odelo estat*stico
5*mbolos
Sados de
entrada
Trobabilidades
!odelo
5*mbolos
codificados
<odificador
<ompressão adaptativa genérica
5*mbolos
?U s*mbolo
de entrada
<odifica
s*mbolo
5*mbolos
Actualiza
modelo
codificados
!odelo
Sescompressão adaptativa genérica
5*mbolos
codificados
?U s*mbolo
codificado
Sescodifica
s*mbolo
Actualiza
modelo
5*mbolos
descodificados
!odelo
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
5
1orquê métodos de compressão
adaptativos?
4
9uffman Cest2ticoE: as estat*sticas da fonte tUm de ser passadas ao
programa de expansão CdescodificaçãoER
!
Essa informação é um Xover6eadYO Pue tanto pode ser pePueno como
muit*ssimo grande Cdepende do rigor do modeloER
4
Zum modelo adaptativo não se passa informação estat*stica ao
descodificador
!
não 62 Xover6eadYR
!as[ de in*cio o codificador est2 X\s escurasYO isto éO não con6ece as
estat*sticas da fonte porPue ainda não começou a determin2-lasR
!
Isto Puer dizer Pue:
de in&'io 'om*rime ma- os dados mas /0ai me-1orando 'om o 2em*o34
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
6
!arcos 6istJricos
1952: SR AR 9uffmanO XA met6od for t6e construction of
minimum redundanc^ codesYO Troceedings of t6e
I_EO 5etembro de àbcR
1977: dR Aiv e AR ?empelO XA universal algorit6m for
sePuential data compressionYO IEEE -ransactions on
Information -6eorÔ !aio de àDDR
1978: dR Aiv e AR ?empelO X<ompression of individual
sePuences via variable rate codingYO IEEE
-ransactions on Information -6eorÔ 5etembro de
àDFR
1984: -R Gelc6O XA tec6niPue for 6ig6-performance data
compressionYO IEEE <omputerO dun6o de àFeR
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
7
O artigo (comprimido) de David =uffman
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
8
?m exemplo simples de compressão
Um texto é codificado em ASCII (8 bitsJletra, de acordo com a tabela seguinte).
Suponhamos que a frequência relativa com que os caracteres ocorrem é representada pelo
seguinte histograma. Os caracteres mais frequentes são as minúsculas, o espaço e o retorno ao
início de linha (Rcarriage returnS, CR).
Uerificou-se que 96X do texto é constituído por 31 caracteres (letras minúsculas, espaços,
vírgulas, etc.).
"
Cada um desses 31 caracteres pode ser representado por 5 bits. A 32ª palavra de 5 bits (11111)
pode ser uma RflagS indicando que a seguir vem um carácter que não é um dos 31 anteriores.
"
Cada um desses outros caracteres é representado por 5 ^ 8 _ 13 bits.
"
Comprimento médio das palavras do código: N = 0,96 × 5 + 0, 04 ×13 = 5,32 bits
(em vez dos 8 originais).
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
9
Código de Channon-Fano
No Código de Shannon-:ano as palavras a codificar devem ser ordenadas por
ordem decrescente de probabilidades. Suponhamos, por exemplo, que temos as
palavras x!, x", x#, x$, x% e x&, 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, obteremos o seguinte:
Símbolo
Probabilidade
de ocorrência
Construção das
palavras de código
Palavras de
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
P(x5)
0,07
1
1
1
0
1110
P(x4)
0,03
1
1
1
1
1111
110
Gntropia da fonteH
6
H ( ' ) = −# Pi log Pi =
i =1
= −(0, 4 log 2 0, 4 + 0, 2 log 2 0, 2 + +0, 2 log 2 0, 2 + 0,1log 2 0,1 + 0, 07 log 2 0, 07 + 0, 03log 2 0, 03) =
= 2, 21 bitsJsímbolo
Comprimento médio das palavras de códigoH
N = 2 × 0,4 + 2 × 0,2 + 2 × 0,2 + 3 × 0,1 + 4 × 0,07 + 4 × 0,03 =
= 2,3 dígitos binários J símbolo
Gficiência do código _
!"#$%& (& )*+#$,&-.#
Entropia da fonte
H(' ) 2,21
=
=
= 96X
2,3
comprimento médio das palavras de código
N
/0(%1#2 (" +#*3"
:
Código de =uffman binário
Este código de fonte é óptimo no sentido de que o número médio de dígitos
binários necessário para representar o símbolo da fonte é mínimo.
Uamos usar o código de ;uffman com uma fonte que produz oito símbolos:
P(x1) _ 0,50
P(x2) _ 0,02
P(x3) _ 0,03
P(x4) _ 0,04
P(x5) _ 0,10
P(x6) _ 0,04
P(x7) _ 0,12
P(x8) _ 0,15
1assos a tomar para construir a árvore do código Cver exemploEH
!' Ordenar as mensagens por ordem decrescente de probabilidades.
x(
x)
x*
x+
x,
x-
x.
x/
"' Agrupar as duas mensagens com as probabilidades mais baixas e somar estas
probabilidades.
Agrupamos x/ e x. no nó a, cu>a soma de probabilidades dB C,C+. De um con>unto de oito
probabilidades passBmos a ter um con>unto de -G(H* probabilidades.
#' Repetir o passo anterior para o novo conjunto de probabilidades, até chegar à raiz da árvore.
..( Agrupamos x, e x- no nó b, cu>a soma de probabilidades dB C,C). De um con>unto de sete
probabilidades passBmos a ter um con>unto de seis probabilidadesI C,+C, C,(+, C,(/, C,(C, C,C)
Jnó bK e C,C+ Jnó aK.
../
Agora agrupamos os nós a e b, produLindo o nó c. Depois agrupamos x+ e x*, produLindo o nó
d, e assim por diante, gerando os nós e e f e chegando finalmente à raiL.
$' 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ó.
Por exemplo, ao ramo que vai do nó a para o nó c atribuamosRlhe o bit (.
%' Determinar as palavras de código percorrendo a árvore da raiz para a copa.
Por exemplo, ao símbolo x* corresponde a palavra de código binBria ((C.
A entropia da fonte vale H(') _ 2,21 bitsJsímbolo e N = 2,26 . Se tomássemos
palavras de código de igual comprimento necessitaríamos de 3 binitsJsímbolo. Assim
2,21
bastou tomar 2,26 binitsJsímbolo " Eficiência =
_ 97,3X.
2,26
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
;
K árvore do exemplo de
código de =uffman binário
x1
Probabilidade
0,50
x8
0,15
x7
Arvore
)
)
)
0,12
!
x5
0,10
Palavras de código
)
e
0,28
!
d
)
f
!
1,00
!))
!!)
0,50
0,22
!!!
!
x4
0,04
)
!
x6
0,04
x3
0,03
x2
0,02
!)!))
b
)
0,08
)
!
c
!
0,13
!)!)!
a
!)!!)
0,05
!)!!!
Repare-se que no código de ;uffman a codificação se faz em direcção à raiz da
árvore, ao contrário do código de Shannon-:ano j mas a formação das palavras de
código faz-se no sentido contrário.
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
<=
Código de =uffman não binário
Se o código não for binário (D k 2) é preciso proceder a um agrupamento inicial
de mensagens de acordo com o seguinte procedimento1:
Sendo M o tamanho do alfabeto da fonte e D o tamanho do alfabeto
do código, agrupam-se primeiro as 2 + ( M − 2) mod( D − 1)
mensagens menos prováveis.
( ( M − 2) mod( D − 1) é o resto da divisão de MR/ por DR()
GLGM1NOH ! O P, " O R
Probabilidade
a1
Palavras de código
Arvore
0,4
)
)
a2
0,3
a3
0,2
a4
0,05
a5
0,03
a6
0,02
!
!
"
)
1,0
!
"!
"
)
!
")
0,3
"")
0,05
""!
Agrupamento prévio das 2 ^ 4 mod 2 _ 2
mensagens menos prováveis
O agrupamento prévio diminui o valor de N pois assim há menos palavras
compridas (duas de 3 dígitos ternários em vez de três (D_3)).
1
A justificação pode encontrar-se em R. G. Gallager, Information Theory and Reliable
Communication (miley, 1968), Sec. 3.4.
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
<<
Klgo mais sobre o código de =uffman
Sedução da variUncia
!
Se ao formar um novo conjunto de probabilidades decrescentes houver
probabilidades iguais as que resultam de agrupamentos devem ser colocadas o
mais alto possível. Desse modo reduz-se a variância V dos comprimentos ni das
palavras de código. No entanto o comprimento médio N mantém-se.
M
Uariância _ V = E $ ni2 % − N 2 , com E $ ni2 % = # Pi ni2
& '
& '
i =1
A variância mínima tem vantagens:
!
o ritmo de produção de bits é mais uniforme (o que é conveniente para o preenchimento de
RbuffersS)p
!
há uma maior imunidade (resistência) a erros do canal, na descodificação.
Kumento da eficiência da codificação não binária com agrupamento
prévio
!
O agrupamento prévio de símbolos na codificação de ;uffman não-binária
aumenta a sua eficiência pois baixa o comprimento médio N , dado que assim as
palavras mais compridas são em menor número.
Kplicações
!
O código de ;uffman é usado em equipamento comercial 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.
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
<4
Codificação aritmética
!
Dizemos que um codificador é óptimo quando permite comprimir os dados
gerados por uma determinada fonte com o número mínimo possível de bits.
!
Apesar de os códigos de ;uffman serem muito eficientes na maioria das
aplicações, só são óptimos num reduzido número de casos (quando a
probabilidade de ocorrência de cada símbolo for uma potência inteira de 1J2).
!
A codificação aritmética surgiu em 1976 com Rissanen. Esta técnica de
codificação permite gerar códigos óptimos se as diversas probabilidades de
ocorrência forem conhecidas rigorosamente.
!
r necessária uma correcta modelização da fonte
(como já acontecia na codificação de ;uffman).
!
O código gerado por um codificador aritmético representa um número real: o
codificador faz corresponder a uma qualquer sequência de símbolos (cada um
com a sua probabilidade) um número real superior ou igual a 0 e inferior a 1.
!
O intervalo de 0 a 1 é inicialmente dividido em tantos intervalos quantos os
símbolos diferentes produzidos pela fonte, de tamanhos proporcionais às
probabilidades de ocorrência respectivas.
!
Consoante o símbolo que for sendo gerado assim o respectivo intervalo vai sendo
subdividido proporcionalmente.
!
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 de entre os que
podem ser representados pelo menor número de bits (se a codificação for
binária).
!
r necessário acrescentar um símbolo especial ao conjunto de símbolos da fonte
para assinalar o fim da sequência.
O melhor é vermos um exemplo…
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
<5
Codificação aritméticaH introdução
fma fonte produz os s*mbolos A e g com as probabilidades hOi e hOeO
respectivamenteR
W Ao s*mbolo A vamos associar o intervalo semifec6ado de h a hOi
CexclusivéE e a g vamos associar o intervalo semifec6ado de hOi a `:
A
h
g
`
hOi
W 5e cada um dos intervalos for dividido noutros dois com a mesma
proporção Cihj e ehjE obtemos Puatro intervalos mais pePuenosO [0p0,36[ O
[0,36p 0,6[ O [0,6p0,84[ e [0,84p1[ :
AA
Ag
gA
gg
`
h
hOixhOiLhOki
hOi
hOiNhOixhOeLhOFe
W Trosseguindo a subdivisão obter*amos oito intervalos ainda mais
pePuenos:
h
AAA
AAg
hOcìh
AgA
hOki
Agg
gAA
hObhe
hOi
gAg
hODee
ggA
hOFe
ggg
`
hOaki
W l mensagem AAA corresponde o intervalo de h a hOcì Ccom largura igual
a p( A)3 = 0,216 EO a gAg corresponde o intervalo de hODee até hOFe Ccom
largura 0, 84 − 0,744 = p(B)p(A)p(B) = 0,096 EO e por a* adianteR
4 Tara codificar a mensagem AAA sJ temos Pue escol6er um número dentro
do intervalo correspondenteO e de preferUncia um Pue seQa representado
pelo menor número de bits:
h
AAg
AAA
hOcìh
AgA
hOki
Agg
hObhe
gAA
hOi
gAg
hODee
ggA
hOFe
ggg
`
hOaki
`nF
cnF
enF
anì
bnF
inF
DnF
`bnì
hOhh`
hOh`h
hO`hh
hO`hh`
hO`h`
hO``h
hO```
hO````
hh`
h`h
`hh
`hh`
`h`
``h
```
````
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
<6
Codificação aritmética X exemplo Y
<CaE L hOe
<C=E L hOkb
<C'E L hOcb
5ePuUncia a codificar: a c b a a b
h
a
hOe
b
hODb
c
`
XaY
hOì
h
hOk
hOe
XcY
hOk
hOke
hOkDb
hOe
XbY
hOkbe
hOkiicb
hOkDb
hOke
XaY
hOkebi
hOkbhb
hOke
hOkbe
XaY
hOke
hOkecce
hOkeec
hOkebi
XbY
hOkeec
hOkecce
o cJdigo deve ser um número real inclu*do no intervalo phOkecceq hOkeecpR
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
<7
Codificação aritmética X exemplo Z
Carácter
1robabilidade
[ama de valores
Espaço
A
B
C
E
;
>
R
U
0,1
0,1
0,1
0,1
0,1
0,1
0,2
0,1
0,1
t0,0 p 0,1t
t0,1 p 0,2t
t0,2 p 0,3t
t0,3 p 0,4t
t0,4 p 0,5t
t0,5 p 0,6t
t0,6 p 0,8t
t0,8 p 0,9t
t0,9 p 1,0t
<odificação de XgA_<A rE?9AY:
Carácter
\alor inferior
\alor superior
Nargura do
intervalo
0,0
1,0
1,0
B
0,2
0,3
10-1
A
0,21
0,22
10-2
R
0,218
219
10-3
C
0,2183
0,2184
10-4
A
0,21831
0,21832
10-5
Espaço
0,21831
0,218311
10-6
U
0,2183109
0,218311
10-7
E
0,21831094
0,21831095
10-8
>
0,218310946
0,218310948
2x10-9
;
0,218310947
0,2183109472
2x10-10
A
0,21831094702
0,21831094704
2x10-11
RBARCA UE>;AS _ 0,21831094702 (por exemplo).
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
<8
1rocedimento de descodificação
1) Subtrair o valor inferior do intervalo da letrap
2) Dividir pela largura desse intervalop
3) O resultado indica a nova letrap
4) Repetir
Exemplo abaixo:
0, 21831094702 " B →
0, 21831094702 − 0,2
= 0,1831094702 " A
0,1
Sescodificação de hOc`Fk`haeDhc:
]^mero
codificado
Carácter
\alor inferior
\alor superior
Nargura do
intervalo
0,21831094702
B
0,2
0,3
0,1
0,1831094702
A
0,1
0,2
0,1
0,831094702
R
0,8
0,9
0,1
0,31094702
C
0,3
0,4
0,1
0,1094702
A
0,1
0,2
0,1
0,094702
Espaço
0,0
0,1
0,1
0,94702
U
0,9
1,0
0,1
0,4702
E
0,4
0,5
0,1
0,702
>
0,6
0,8
0,2
0,510
;
0,5
0,6
0,1
0,10
A
0,1
0,2
0,1
0,0
0,21831094702 _ RBARCA UE>;AS
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
<9
Codificação aritmética X exemplo P
"odificação
CihjE
sh L h
hOi
hOa
CkhjE
ak
CihjE
hOa
hOai
C`hjE
CkhjE
a`
hOaki
hOa
hOacì
hOakce
hOaki
ac
hOa
hOacFh
hOacì
hOakce
a`
ac
hOacì
`
hOai
a`
hOa
`
hOacDek
hOacbeF
hOacFh
4escodificação
Ai L hOacDekh
h
h
Ab
h
Ae
h
h
h
hOi
hOa
`
hOi
hOa
`
hOi
hOa
`
hOa
`
hOi
hOa
`
hOi
hOa
`
hOi
Ac
Ak
A`
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
>&?(& (#
("2@#(%+%@&(#$
ak
a`
a`
ac
a`
ac
<:
_nconvenientes dos códigos estatísticos
!
r preciso conhecer a estatística da fonte. Para texto vulgar as frequências de
ocorrência conhecidas bastariamp para texto mais especializado (reservas de
avião, cotações da Bolsa, etc.) essas estatísticas não permitiriam uma codificação
muito eficiente. Usando técnicas adaptativas consegue-se uma compressão de
cerca de 43X em inglês vulgar* com código de ;uffman.
!
Em mensagens de texto a codificação não tem em conta a dependência entre
letras (por exemplo, entre q e u) pois apenas são codificadas letras individuais.
!
O facto das palavras de código terem comprimento variável põe problemas na
transmissão pois a fonte está a gerar símbolos a uma taxa constante e o
codificador produz símbolos a uma taxa variável. O emissor terá, pois, de possuir
um buffer para obviar a este problema.
O código de ;uffman é uma abordagem de codificação estatística. Uma
alternativa que remedeia algumas das suas deficiências é a abordagem com
dicionBrios, de que os algoritmos de ]empelRîv (>-?) são exemplos. Nesses casos
constrói-se gradualmente um dicionário, ou livro de código, isto é, usa-se um
algoritmo adaptativo.
*
R. Gitlin, J. ;ayes e S. meinstein, "Data Communications Principles", Plenum Press, 1992.
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
<;
Codificação Nabb
Usa-se uma janela de observação de comprimento fixo que desliza ao longo da
mensagem a comprimir. r composta por duas partes:
!
corpo (da janela)
Contém vários milhares de caracteres (8192, por exemplo)
!
/look1a2ead buffer6
Bastante mais pequeno (10 a 20 caracteres, ou até mais)
Xo Pue acabou de acontecerY
Xo Pue est2 a acontecerY
Z-8 caracteres
8
Cor*o da Dane-a
/>oo?@a1ead =Affer4
danela deslizante
Passos a dar na codificação<
Y. compara-se o conteúdo do corpo da janela com o conteúdo do buffer e verifica-se
se existe algum padrão ou sequência de símbolos igual. Esse padrão é substituído
na saída do codificador por um apontador constituído por um trio de elementos
< i, >, a > que na maior parte dos casos ocupa menos espaço que o padrão
repetido:
i : disttncia Cou offse2E do in*cio do XbufferY ao in*cio do padrão igualq especifica uma de
N − F posiçues na Qanela e pode ser hR
D : comprimento do padrãoq tem um valor entre h e F − 1 R
a : primeiro car2cter Pue Q2 não faz parte do padrão repetidoR v o prJximo s*mbolo a
codificarR
Z. Desloca-se a janela para a frente de > + 1 caracteres.
A inclusão do próprio carácter a no apontador é para que a codificação prossiga
mesmo que não haja padrão repetido. Nesse caso o apontador é (0, 0, a) .
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
4=
NabbH n^mero de bits do apontador
O número de bits necessários para representar cada apontador é sempre o
mesmo:
!
O primeiro elemento (dist`ncia) requer $log2 (N − F )% bitsp
!
o segundo elemento (comprimento) requer $log2 F % bitsp
!
o terceiro (símbolo da fonte) requer $log2 M % bits, em que M é o tamanho do
alfabeto da fonte.
Para representar cada apontador são precisos, no total,
$log2 (N − F )% + $log2 F% + $log2 M % bits
!
Exemplo com uma janela deslizante com N = 24 e F = 8
comprimento L D
R R R
A 5 - I x o w < o ! E w - f S o O
w - f S o O w -
R R R
disttncia L i
(o símbolo y representa um espaço)
Ao olhar para o lookRahead buffer verifica-se que o padrão R y TUDO,y S, de
sete caracteres, já apareceu antes, concretamente seis caracteres atrás. Como a seguir
vem o carácter T, R y TUDO,y S será codificado como (6, 7, T).
Número de bits de cada apontador (vamos supor que M _ 50):
$log2 (N − F )% + $log2 F% + $log2 M % = $log2 16 % + $log2 8 % + $log2 50 % = 13
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
4<
Descodificação Nabb
A janela deslizante tem o mesmo tamanho N que foi usado na codificação mas,
em vez de se procurar uma correspondência entre corpo de janela e lookRahead buffer
copia-se da própria janela para a saída do descodificador o padrão indicado pelo
apontador.
Suponhamos que o apontador é (3, 5, EK quando, num determinado momento da
codificação, a janela deslizante estiver preenchida como na figura:
[
[ E g A < g < A ? ? ? [
CkO bO EE
*+,+ -./0+-121034 + 35+673-+4 8#9 %9 E):
A sequência …EBACBCA já está na saída do descodificador. Ora (3, 5, EK está
a apontar para a terceira letra (a partir do fim) e corresponde a uma sequência de
cinco letras seguida da letra E. Então na saída vão surgindo sucessivamente as
seguintes letras:
1. …EBACBCA
;
2. …EBACBCA
B*
3. …EBACBCA
BC<
Neste momento já temos três caracteres a partir do B inicial. Ainda faltam dois:
4. …EBACBCA
BCA;
5. …EBACBCA
BCAB*
Só falta o carácter seguinte, E:
6. …EBACBCA
!"#$%& (& )*+#$,&-.#
BCABC=
/0(%1#2 (" +#*3"
44
Nimitações de Nabb
Y. Se no lookRahead buffer não houver nenhuma sequência que RcaseS com o
conteúdo da janela o carácter a codificar é, mesmo assim, representado por um
apontador constituído pelo trio de elementos habitual (distância, comprimento e
carácter seguinte)p nesse caso a codificação de um carácter necessitará de mais
bits que o próprio carácter não codificado.
Exemplo: se a Qanela tiver ez b^tes Cde F bitsE com um =Affer de ì b^tes e se
cada car2cter não codificado for representado por ` b^te serão necess2rios `c
bits Cdis2En'iaE mais e bits C'om*rimen2oE mais F bits C'arF'2erEO isto éO ce bits para
representar um car2cter Pue inicialmente sJ ocupava F bits: o codificador em vez
de comprimir expandiu{{
Z. A janela só observa o que é recente (porque o seu tamanho é finito): >?77 é mais
eficiente a comprimir padrões iguais próximos uns dos outros (isto é, que estejam
na janela e no buffer) do que padrões iguais que estejam longe.
P. O tamanho limitado do buffer restringe o tamanho dos padrões que se comparam,
que não podem ser maiores que o buffer. Mas às vezes as equivalências são mais
compridas pelo que se perde eficiência.
Uma solução possível: aumentar os tamanhos da janela e do buffer, mas nesse
caso serão precisos mais bits para representar a distância e o comprimento, além de
que a codificação será mais lenta (mais comparações terão de ser feitas entre as
sequências da janela e do buffer).
;á que estabelecer um compromisso entre, por um lado, os valores de N e : e,
por outro, a eficiência e a velocidade de compressão.
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
45
Codificação Nabd
Existem imensas variantes do código >?* e já conhecemos a >?77. A variante que a seguir se
apresenta, seguindo Gitlin et al., é devida aos próprios "inventores", Jacob ?iv e Abraham >empel
(1978).
Na sequência de saída da fonte vamos procurar uma sequência de símbolos que ainda não
tenha sido encontrada antes. Esta sequência é codificada usando sequências que já foram
encontradas antes e que, por isso, já foram guardadas num livro de código, ou dicionBrio.
O algoritmo compreende-se melhor com um exemplo:
Suponhamos que a sequência original (na fonte) era
!!))!!)))!)!)!!))!))!!!!))!
Percorrendo a sequência da esquerda para a direita e admitindo que no nosso livro de código
já estão guardados os símbolos C e (, obteríamos a seguinte segmentação:
!!J))J!!)J))!J)!J)!!J))!)J)!!!J!)J)!
O livro de código, inicializado com os símbolos 0 e 1, vai conter os seguintes símbolos, com a
numeração indicada:
0
1
11
00
110
001
01
011
0010
0111
10
1
2
3
4
5
6
7
8
9
10
11
A sequência a transmitir será a seguinte: "! !) #) $! !! >! &) ?! ") !!'
Cada inteiro é representado por um bloco de dígitos binários cujo tamanho depende do
tamanho do livro de código. Na prática são normalmente usados blocos de 12 bits (isto é, 4096
entradas no livro de código).
Uma sequência nova termina sempre em 0 ou em 1. Consequentemente, apenas 1 bit é
necessário para representar os fins de cada palavra de código, isto é, as palavras de código são
representadas por 12^1_13 bits.
No algoritmo >?78 palavras de código de comprimento fixo representam um número variável
de símbolos de saída da fonte. Isto é o inverso do algoritmo de codificação de ;uffman e é muito
adequado para transmissão síncrona.
*
Uer, por exemplo, T. Bell, J. Cleary e I. mitten, "Text Compression", Prentice-;all, 1990.
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
46
Código Nabd
Gxemplo
Consideremos a seguinte passagem literária:
":oi ele que rapou avaramente a sopeira. E já espreitava a porta, esperando a portadora dos
pitéus, a rija moça de peitos trementes, que enfim surgiu, mais esbraseada, abalando o sobrado—e
pousou sobre a mesa uma travessa a transbordar de arroz com favas. }ue desconsolo~ Jacinto, em
Paris, sempre abominara favas~…Tentou todavia uma garfada tímida—e de novo aqueles seus
olhos, que o pessimismo enevoara, luziram, procurando os meus. Outra larga garfada, concentrada,
com uma lentidão de frade que se regala. Depois um brado:
—•ptimo~…Ah, destas favas, sim~ Oh que favas~ }ue delícia~"
Suponhamos que o livro de código já contém todas as letras, maiúsculas e
minúsculas, espaço e todos os sinais de pontuação. A segmentação do texto seria
assim:
":oJi JelJe JquJe rJapJouJ aJvaJraJmeJntJe aJ sJopJeiJra.J EJ jJá JesJprJeitJavJa Ja pJorJtaJ,
JespJerJanJdoJ a JpoJrtJadJoraJ dJosJ pJitJéuJs,J a rJijJa mJoçJa dJe pJeitoJs JtrJemJenJteJs, JqueJ eJnfJimJ
suJrgJiuJ, mJaiJs eJsbJrasJeaJdaJ, aJbaJlaJndJo Jo sJobJradJo—Je poJusJou JsobJreJ a mJesaJ uJmaJ
tJravJessJa aJ trJansJboJrdJarJ deJ arJroJz JcoJm JfaJvasJ. J}uJe dJescJonJsolJo~J JJacJinJtoJ, eJm PJariJs,
sJempJre JabJomJinaJra JfavJasJ~…JTeJntoJu JtodJaviJa uJma JgaJrfJadaJ tíJmiJda—Je dJe nJovJo
aJquelJes JseJus JolJhoJs, qJueJ oJ peJssJimiJsmJo eJneJvoJaraJ, lJuzJirJamJ, pJrocJurJandJo oJs mJeuJs.J
OJutJra lJargJa gJarfJada,J cJoncJentJradaJ, cJom JumJa lJentiJdãJo dJe fJradeJ qJue Jse JregJalJa.J
DJepJoiJs uJm bJradoJ:
J—•JptJimoJ~…AJh,J desJtasJ fJavaJs, siJm~J OhJ quJe faJvas~J }Jue dJelíJciJa~J"
Cada nova sequência será codificada em duas palavras que já existem no livro
de código, a última das quais faz parte do livro inicial. Repare-se, por curiosidade,
como é codificada a palavra favas, que aparece quatro vezes.
Com o código >?78 consegue-se uma compressão de aproximadamente 55X em
inglês vulgar (em português não se conhecem dados). Em texto mais estruturado —
linguagens de programação, por exemplo — pode-se atingir maiores compressões.
Como já se disse antes, com o código de ;uffman consegue-se chegar a 43X.
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
47
Codificação Nabd X um exemplo
5ensa&em a codificar6
Entrada
|ndice
A
`
hA
g
c
hg
<
k
h<
AA
e
À
AAg
b
eg
Ag
i
`g
<<
D
k<
AAgA
F
bA
<<A
a
DA
AAA
`h
eA
g<
``
c<
7a8da do codificador6
!"#$%& (& )*+#$,&-.#
AAAABAB//AABA//AAAAB/
Talavra de cJdigo
<A 6B <B 5/ 7A 9A 6A 4/
/0(%1#2 (" +#*3"
48
Trogramas ou formatos de compressão
Zome
Ambiente
<o!TA<- fnix
5}
Algoritmo
<oment2rio
9uffman adaptativo ?entoO patenteado
<Tn! e
!5-So5
9uffman est2ticoO
ordem h
In*cio anos Fhq
compressão compar2vel
a <o!TA<-
A_<
T<
?ADFncompress
<omprime e arPuiva
?9arc
T<n!ac
?ADD
Xfree~areY
A_d
T<n!ac
?ADD
!el6or Pue ?9arc
<T-
!ac
?A
SE8?A-E
?ADD N 9uffman
Tara substituir ?AGR
!uito popularR
Autor: T6il zatzR
TzAITO zip
SE8?A-E
Autor: T6il zatz
?ADD
Tara substituir 'om*ress
Autores: dean-?oup
•aill^ e !ar€ Adler
bzip
<odificação
aritmética
Autor: dulian 5e~ard
bzipc
9uffman N
transformada de
gurro~s-G6eeler
5ucessor de bzip
Autor: dulian 5e~ard
CàaiE
gzip
Gindo~sO
!acO
?inuxO[
C<ontinuaE
!"#$%& (& )*+#$,&-.#
/0(%1#2 (" +#*3"
49
Trogramas ou formatos de compressão
C<ontRE
Zome
<ompan6ia
Algoritmo
<oment2rio
!ZT-b
!icrocom
variante dintmica
de 9uffman
!odems
recRbis
<<I--nI-f
?AG
!odemsq mel6or Pue
!ZT-b
•RDc`
<<I--nI-f
AST<!
<ompressão de voz
?T<
<ompressão de voz
5tuffIt
GinO !acO ?inux ?A
ftilit2rio de
compressão
GinAip
GinO !acO ?inux zip
ftilit2rio de
compressão
<ompuserve
?AG
Tara imagens
Xbit-mappedY
dTE•
I5on<<I--
S<-n9uffman
Tara imagens fixas
!TE•
I5on<<I--
Adobe
Acrobat
Adobe
•I8
!"#$%& (& )*+#$,&-.#
Tara imagens mJveis
?AG
/0(%1#2 (" +#*3"
8ic6eiros Rpdf
4:
1.#.
"ontes e canais cont+nuos
!
entropia diferencial
!
teorema da capacidade
Shannon-4artley)
!
limite de Shannon
!
plano da probabilidade de erro
!
plano da eficiência espectral
de
canal
(lei
de
!ontes contínuas
!
Uma fonte de informação contínua produz sinais vari-veis no tempo, x(t).
!
O conjunto de sinais possíveis é considerado como um con1unto de formas de
onda geradas por um determinado processo aleatório (suposto ergódico).
Suponhamos que o processo aleatório tem uma largura de banda finita. Então
x(t) pode ser completamente caracterizado em termos de valores amostra periódicos.
Em qualquer instante a colecção de valores amostra possíveis constitui uma vari-vel
aleatória 6 descrita pela sua função densidade de probabilidade, p(x).
No caso das fontes contínuas a quantidade média de informação por amostra de
x(t) mede-se através da função entropia diferencial:
∞
h(6 ) =
!
p( x)log 2
−∞
1
dx
p(x)
(Entropia de fonte contínua)
" #$%&'()* +),#&#$-)*. !"#$ *%)$/# ' 0#1 2*.'& 345)3' 0# %"&$ ,'& 13*
,1$67' +#$0)+*+# +# (&'8*8).)+*+# /*100)*$* (ver Anexo 2)9
1
max h( 6 ) = log 2 2 πeS
2
p6 ( 6 )
em que S = E?6@A (variância)
/on0es e 2anais 2on03n4os
2
!ontes e canais contínuos
A transferência de informação num canal contínuo toma a forma de transmissão
de sinal: a fonte emite um sinal x(t) que, após corrupção por ruído de transmissão,
aparece no destino como um outro sinal, y(t).
A informação mútua média é definida como
I(6 RD ) = !
∞
!
p 6D (x, y)log 2
−∞
p 6 (xS y)
dx dy
p 6 ( x)
I(6RD) mede a transferência de informação por amostra de y(t) no destino. Tal
como no caso discreto também aqui se verifica que I(6 RD ) ≥ 0 (e I(6 RD ) = 0 se o
ruído for tão elevado que y(t) não está relacionado com x(t).
A informação mútua média está relacionada com a entropia diferencial através
de
I(6 RD ) = h(D ) − h(DS 6 ) = h(6 ) − h(6SD )
em que h?6A representa a entropia diferencial da fonte, h?DA representa a entropia
diferencial do destino, h(6SD) é a equivocação e h(DS6) representa a entropia
diferencial do "ruído", como se verá.
h(6SD ) = !
∞
!
−∞
h(DS 6 ) = !
∞
!
−∞
1
p 6D (x, y)log2
dx dy = !
p6 (xS y)
1
p 6D (x, y)log2
dx dy = !
pD (yS x)
∞
!
pD (y) p 6 (xS y)log 2
1
dx dy
p 6 (xS y)
p 6 (x )pD (ySx )log 2
1
dx dy
pD (yS x)
−∞
∞
!
−∞
3
Capacidade de canais contínuos
Sabe-se, da teoria das probabilidades, que se D X aFYb, em que F e D são
1
" D −b# 1
' = p F (G ). Assim, se o canal
variáveis aleatórias, então pD (y) = pF %
a $ a & a
introduzir ruído gaussiano aditivo independente, tal que y(t) X x(t) Y n(t), então
pD ( y S x) = pD ( x + n) = pN ( y − x) = pN (n)
e portanto
∞
∞
1
1
h(D S 6 ) = ! ! p 6 ( x) pD ( y S x)log 2
dx dy = ! p N (n)log 2
dn = h( N )
p
y
x
p
n
(
S
)
(
)
D
N
−∞
−∞
Isto é, a entropia diferencial condicional de D, dado 6, não depende de p6(x) e é igual
à entropia diferencial de N. Podemos, então escrever:
I(6 RD ) = h(D ) − h( N)
A transferência m-xima de informação por amostra de y(t) obtém-se
maximizando I(6RD). Esta maximização é equivalente à maximização de h(D), logo D
deve ser uma variável aleatória gaussiana. Como N também é gaussiana, 6 deve
também ser gaussiana.
Se o canal tiver uma largura de banda fixa B então a sua saída, y(t), é um sinal
de banda limitada que pode ser completamente definido por amostras Dk, k X 1,2,…,
obtidas à taxa de Nyquist, fs X 2B amostras_s. Definindo
2
[
Cs = max I(6 RD) = max I(6RD) : a gaussiana E(6 ) = S
p 6 (x )
]
bits _ amostra
a taxa m-xima de transferência de informação, em bits_s, é então
C = 2 BCs bits_s
(capacidade de um canal contínuo de banda limitada)
4
Capacidade do canal 1234
Consideremos um canal contínuo de banda limitada afectado de ruído gaussiano
branco aditivo (canal AbGN).
5ropriedades7
— o sinal de entrada, x(t), tem banda limitada e uma potência média fixa,
S = E?6@A.
— a transmissão não sofre distorção na largura de banda B do canal (a menos de
atenuação…)
— o ruído aditivo que contamina a saída do canal tem função densidade de
probabilidade gaussiana com média nula e potência média N = NoB
— o sinal e o ruído são independentes:
[ 2 ]= σ 2y = S + N
y(t) = x(t) + n(t) ( E D
! A entropia diferencial condicional h(DS6) X h(N) pode calcular-se a partir de
2
pN(n), sendo σ n = N :
p n ( n) =
1
2πσ n2
−
n2
2
e 2σ n
∞
(
h(D S 6) = h(N) =
!
−∞
log 2
(
pn (n)log 2
1
n2
= log 2 2 πN +
log 2 e
pn (n)
2N
1
1
1
dn = log 2 2π N + log 2 e = log 2 (2 πeN )
2
2
pn (n)
! O valor máximo de h(D) é igual a
1
1
log 2 2πeσ y2 = log 2 2πe( S + N )
2
2
(Continua)
5
Capacidade do canal 1234
(Contin.)
Podemos então calcular a capacidade de um canal AWGN:
1
! h(DS 6 ) = log 2 (2 πeN )
2
! max h(D ) =
p 6 ( x)
1
log2 2 πe(S + N )
2
Cs = max I( 6RD ) = max[h(D)] − h(DS 6 ) =
p 6 ( x)
!
=
p6 (x )
1
1
S#
1
"
log2 2 πe(S + N ) − log 2 2 πeN = log 2 % 1+ ' bits _ amostra
$
2
2
N&
2
! Capacidade do canal em bits_s:
S#
"
C = B log 2 % 1 + '
$
N&
Esta expressão traduz o Teorema da capacidade de canal ou lei de
ShannonRHartley, que é um dos mais famosos e importantes resultados da Teoria da
Informação:
S#
"
Não é possível transmitir sem erros a um ritmo superior a C = B log 2 % 1 + ' bitsUs
$
N&
através de um canal com largura de banda B e relação sinalRruído SUN.
6
8mplicações do teorema da capacidade de
canal
! Um sistema ideal com largura de banda infinita tem uma capacidade de canal
finita:
"
S#
S #
"
C = B log 2 %1 + ' = B log 2 %1 +
'=
N&
N
B
$
0 &
$
B "
S #
=
ln %1 +
'
N0 B &
ln 2 $
Se B → ∞, S N 0 B → 0 . Mas
C∞ = lim C ≈
B →∞
. Portanto,
B S
1 S
S
=
= 1,44
ln 2 N 0 B ln 2 N 0
N0
! Existe um valor limite de Eb_NW ?limite de ShannonA abaixo do qual não pode
haver comunicação sem erros, qualquer que seja o ritmo de transmissão.
Sendo T a duração de cada bit, Eb a sua energia e R X 1_T bits_s, então
S Eb T Eb R
=
=
N N0 B N0 B
Mas R ! C
Se B → ∞ (
(
(
"
E R#
S#
"
C = B log 2 %1 + ' = B log 2 %1 + b '
N&
N0 B &
$
$
"
E R#
R C
≤ = log 2 %1 + b '
B B
N0 B &
$
"
E R # Eb R
ln %1 + b '
N0 B & N0 B
"
E R#
R
≤ log 2 %1 + b ' = $
≈
ln
2
ln 2
B
N
B
0
$
&
Portanto,
Eb
≥ ln 2 = 0, 693 → −1, 59dB
N0
?limite de ShannonA
7
Capacidade de canais contínuos
Capacidade do canal em função da largura de banda
C (bits_s)
1,44 S_No
S_No
S_No
B (4z)
O limite de Shannon
C_B (bits_s_4z)
RXC
30
20
Região com R m C
10
Região com R n C
1
-10
0
10
20
30
40
Eb_N0 (dB)
:;<=>
0,1
8
Capacidade de canal 1234 com largura
de banda finita
Temos
"
E R#
R C
S#
"
≤ = log 2 %1 + ' = log 2 %1 + b ' , donde se tira
B B
N&
N0 B &
$
$
Eb 2 R B − 1
≥
N0
R B
(R_B é a eficiência espectral)
Consideremos agora a seguinte situação com codificação de canal:
R bits_s
1UT X R_Rc
oonte
Codificador
de canal
Canal
Rc X k_n
B ≥ YU@T
Para que não haja interferência intersimbólica é preciso que B ≥ 1_2T, ou seja,
B≥
1
R
=
2T 2 Rc
ou
R
≤ 2 Rc
B
Se queremos aumentar a eficiência espectral teremos de aumentar a taxa do código.
Eb 22 Rc − 1
≥
2 Rc
N0
Assim:
-.emp1os2
Rc = YU@
(
Eb
≥ 0 dB
N0
Rc = YUZ
(
Eb
≥ −0,55 dB
N0
Rc = YU[
(
Eb
≥ −0,82 dB
N0
q medida que a taxa de código diminui mais nos podemos aproximar do limite de
Shannon (-1,59 dB).
9
Capacidade de um canal afectado de
ruído gaussiano colorido
! #enchimento de água1
ramos tratar do caso mais geral de ruído colorido.
H(f)
x(t)
;(t)
6uído colorido
n(t)
• Admitamos que o sinal de entrada x(t ) tem uma potência média P fixa e que
S 6 ( f ) é a sua densidade espectral de potência:
∞
P=
!S
6
( f )df
−∞
• O ruído gaussiano estacionário colorido tem média nula e S N ( f ) é a sua
densidade espectral de potência.
• H ( f ) é a função de transferência do canal.
]ual é a capacidade deste canal^ E qual é a densidade espectral de potência do
sinal de entrada, S 6 ( f ) , que maximiGa a informação m`tua média^
Os resultados, obtidos com o método dos multiplicadores de aagrange, são os
seguintes, sendo K uma constante:
SN ( f )
,
)K −
2
S6 ( f ) = +
H( f )
)0
*
f ∈F
outros
∞
" H( f ) 2 #
1
' df
C = ! log 2 % K
% SN ( f ) '
2 −∞
$
&
10
! #enchimento de água1
(cont.)
Para valores especificados de P, S N ( f ) e H ( f ) a constante K é a solução da
equação seguinte:
P=
! S 6 ( f )df =
f ∈F
#
"
% K − S N ( f ) 'df
! % H( f ) 2 '
f ∈F $
&
O conjunto F = { f : f1 ≤ f ≤ f 2 } representa a gama de valores de frequência
S (f)
para os quais a constante K é superior a N 2 .
H( f )
Estas considerações conduzem à chamada dinterpretação do enchimento de
-guae:
SB(f)/|H(f)|2
= = áreas sombreadas
<
SX(f) invertido
-f2
-f1
f1
f2
f
t como se estivéssemos a uencherv de água (ou melhor, de potência de x(t)) o
2
gráfico de S N ( f ) H ( f ) : onde houver umenosv ruído (nos vales) coloca-se mais
potência de sinal de entrada, onde houver mais ruído coloca-se menos potência.
11
Exemplo )* Canal com ruído AW5N (o ruído é branco)
SN ( f ) =
N0
2
,1 0 ≤ f c − B 2 ≤ f ≤ f c + B 2
H( f ) = +
*0 outros
(canal ideal)
fc + B 2
Da expressão da potência, P = 2
! (K − N 0 2)df , tiramos o valor de K:
fc − B 2
K=
P + N0B
2B
A capacidade deste canal obtém-se imediatamente:
1
C = 2×
2
fc + B 2
!
fc −B 2
2
H( f )
2K
log 2 K
df = B log 2
SN ( f )
N0
Substituindo o valor de K obtido atrás chegamos à expressão já conhecida do
teorema de Shannon-4artley:
2
C = B log 2
P + N0B
"
P #
2B
''
= B log 2 %%1 +
N
B
N0
0 &
$
12
Exemplo ;* <S> com interferência NEXD (EnearFend crosstalkI)
SX(t)
H(f)
Jinha KSJ
SB(t)
HBEXT(f)
SX(t)
• Normalmente H NE6T ( f ) = β f 3 2 , em que β é uma característica dos cabos
telefónicos.
2
• S N ( f ) = H NE6T ( f ) S 6 ( f )
A única restrição a impor é que a densidade espectral de potência de x(t ) seja
não-negativa. Substituindo valores chega-se à constante K,
2
"
H NE6T ( f ) #'
%
K = 1+
S ( f ),
2
' 6
%
H
(
f
)
&
$
e daí à capacidade do lacete de assinante (DSw) afectado de ucrosstalxv do tipo
NEaT:
1
C=
2
2
"
#
H( f )
%
'df
! log 2 %1 + H
2'
NE6T ( f ) &
f ∈F
$
(F é o conjunto das frequências positivas e negativas para as quais S 6 ( f ) > 0 )
13
5lano da probabilidade de erro
! t o lugar geométrico dos pontos de funcionamento disponíveis para um
determinado tipo de modulação ou codificação.
! Cada curva está associada à largura de banda mínima exigida.
O funcionamento do sistema é caracterizado por um ponto no plano da
probabilidade de erro, para um determinado tipo de modulação escolhido e para a
razão Eb_No disponível.
?'3(&'3)00'09
!
Em funcionamento:
1 y Entre PB e Eb_No
(com B fixo)
!
Só na fase de projecto
2 y Entre PB e B
3 y Entre B e Eb_No
(com Eb_No fixo)
(com PB fixo)
O compromisso 1 só envolve variação de potência. Os restantes envolvem
mudanças nos tipos de modulação e codificação.
14
Capacidade de canal gaussiano e
eficiência espectral de modulações
15
Anexo 1
Desigualdade de Kraft (ou de Kraft-McMillan)
Teorema: Se os inteiros n1, n2, ..., nM satisfazem a desigualdade
M
∑ D−n
i
≤1
i =1
então existe um código sem prefixos com um tamanho de alfabeto D cujos comprimentos de
palavras são esses inteiros.
Inversamente: os comprimentos de qualquer código sem prefixos satisfazem a desigualdade.
O teorema não diz que qualquer código cujos comprimentos satisfazem a
desigualdade é um código sem prefixos. O que o teorema diz é que existe um certo
código sem prefixos e que tem esses comprimentos.
Arvore cheia (com D=2)
4ª ordem
D4 nós
3ª ordem
D3 nós
2ª ordem
D-3
D-2
Nós de 1ª ordem
D2 nós
D nós
D-1
•
Existem Dn nós de ordem n
•
De cada nó de ordem i saem D ramos ligados a D nós de ordem i+1.
•
De cada um dos D nós de ordem 1 sai uma fracção D-1 dos nós de ordem i ≥ 1.
•
De cada um dos D2 nós de ordem 2 sai uma fracção D-2 dos nós de ordem i ≥ 2.
Genericamente: De cada um dos Di nós de ordem i sai uma fracção D-i dos nós de ordem maior ou
igual a i.
Anexos
1
Desigualdade de Kraft
Fracção
D-n2 x3 x4
Sejam n1≤ n2 ≤ ... ≤ nM um conjunto de M
x2
Fracção D-n1
inteiros que satisfazem a desigualdade de
Kraft.
x1
Suponhamos que a árvore ao lado tem
ordem n igual ao maior inteiro nM.
Nó de ordem n1
Demonstração do teorema:
1 — Tomemos um nó qualquer de ordem n1 (x1, por exemplo) como o primeiro nó terminal da
árvore de código. Todos os nós de cada ordem ≥ n1 estão ainda disponíveis para nós
terminais,
excepto uma fracção D
− n1
(nós que saem de x1)
2 — A seguir tomemos outro qualquer nó de ordem n2 (x2, por exemplo). Todos os nós de cada
ordem ≥ n2 estão ainda disponíveis para nós terminais,
excepto a fracção D
− n1
+ D − n2
(nós que saem de x1 e x2)
3 — Continuando dessa maneira, depois da atribuição do nó terminal de ordem k na árvore de
código, todos os nós da árvore cheia, de cada ordem ≥ nk, estão ainda disponíveis
excepto a fracção D
− n1
+D
− n2
+…+ D
− nk
k
= ∑ D − ni
i =1
k
4 — Por hipótese
∑ D−n
i
< 1 , para i < M ⇒ há sempre um nó disponível para servir como nó
i =1
terminal ⇒ existe um código sem prefixos.
Inversamente: A árvore de código de um código sem prefixos está contida numa árvore cheia
⇒ um nó terminal de ordem ni dá origem a uma fracção D − ni dos nós terminais da árvore
cheia. Como os conjuntos dos nós terminais da árvore cheia que derivam dos nós terminais da
árvore de código são disjuntos, conclui-se que essas fracções somadas são ≤ 1, c.q.d.
Anexos
2
Anexo 2
Valor máximo da entropia diferencial
Teorema
∞
O valor máximo da entropia diferencial h (Y) = −
∫ p(y)log
2
p(y) dy para todas as escolhas de
−∞
funções densidade de probabilidade satisfazendo
∞
∫y
2
p(y)dy = σ 2
(a)
−∞
é unicamente atingido pela função densidade de probabilidade gaussiana
1
ϕ (y) =
e tem o valor h(Y) =
2 πσ
2
e
−
y2
2σ
2
(b)
1
log 2 (2 πe σ 2 ).
2
Demonstração (de acordo com R. G. Gallager, Information Theory and Reliable Communication
(Wiley, 1968))
Seja p(y) uma fdp arbitrária satisfazendo (a) e seja ϕ(y) a fdp gaussiana de (b). Então
∞
∞
2


1
y
2
p(y)log
dy
=
p(
y)
log
2
πσ
+
log
e
2
2  dy =
∫
2
∫  2
ϕ
(y)
2
σ

−∞
−∞
= log 2 2 πσ 2 +
σ2
1
log 2 e = log 2 (2 πeσ 2 )
2
2σ
2
Portanto,
1
h(Y) − log 2 (2 πe σ 2 ) =
2
∞
∫ p(y)log
−∞
ϕ ( y)
2
p(y)
dy
Como log 2 z ≤ ( z − 1)log 2 e , então
∞
 ϕ (y) 
1
h(Y) − log 2 (2 πe σ 2 ) ≤ log 2 e ∫ p(y)
− 1 dy = 0
2
p(
y)


−∞
A igualdade obtém-se apenas sse
ϕ (y)
p( y)
= 1 para todos os y,
Anexos
c.q.d.
3
Resumo do Capítulo 1
Neste capítulo foram estabelecidos três limites fundamentais em diferentes aspectos de um
sistema de comunicações digitais através do teorema da codificação da fonte, do teorema da
codificação de canal e do teorema da capacidade do canal, todos devidos a Claude Shannon.
O teorema da codificação da fonte fornece-nos um padrão pelo qual podemos medir a
informação proveniente de uma fonte discreta sem memória. Diz-nos o teorema que podemos tornar
o número médio de elementos binários (binits) por símbolo da fonte tão pequeno como, mas não
menor que, a entropia da fonte medida em bits. A entropia de uma fonte é uma função das
probabilidades dos símbolos que a fonte produz. Visto a entropia ser uma medida de incerteza, é
máxima quando a distribuição de probabilidades associadas gera a máxima incerteza, ou seja,
quando os símbolos são equiprováveis.
Os objectivos do teorema da codificação da fonte são perseguidos e aproximados se, antes da
codificação, os símbolos produzidos pela fonte forem agrupados em blocos de N símbolos –
teremos então uma extensão de ordem N – e se os códigos forem de comprimento variável. Destes
só nos interessam códigos unicamente descodificáveis, em especial um seu subconjunto, o dos
códigos sem prefixos, definidos através de árvores. Ambos obedecem à desigualdade de
Kraft-McMillan, que relaciona entre si os comprimentos de cada palavra de código. Os códigos de
Shannon-Fano e Huffman são dois exemplos de códigos sem prefixos cujo comprimento médio das
palavras de código se aproxima da entropia da fonte.
Uma outra abordagem foi feita através da codificação aritmética, embora também baseada em
modelos probabilísticos da fonte, tal como os dois códigos precedentes; completamente diferente
são as codificações de Lempel-Ziv (LZ77 e LZ78). Nesta última, por exemplo, vai-se construindo
um dicionário à medida que a codificação se realiza.
O teorema da codificação de canal é o resultado mais surpreendente e talvez o mais
importante da Teoria da Informação. Por exemplo, para um canal binário simétrico (BSC), o
teorema da codificação de canal diz-nos que para qualquer taxa de informação menor ou igual à
capacidade do canal existem códigos tais que a probabilidade de erro média é tão pequena quanto
quisermos. Um canal binário simétrico é a forma mais simples de um canal discreto sem memória;
é simétrico se a probabilidade de se receber um 1 se se tiver enviado um 0 for igual à probabilidade
de se receber um 0 se se tiver enviado um 1. Esta probabilidade, chamada probabilidade de
transição, define univocamente a capacidade do canal.
O terceiro teorema de Shannon, provavelmente o mais famoso, é o teorema da capacidade do
canal, ou lei de Shannon-Hartley, e aplica-se a canais contínuos. Diz-nos o teorema que em
qualquer canal de comunicação limitado em potência existe uma velocidade máxima de transmissão
de informação sem erros, dependente da largura de banda do canal e da relação sinal-ruído. Esta
velocidade, ou taxa, máxima chama-se capacidade do canal e mede-se em bits/s. Se o sistema
funcionar a uma taxa superior à capacidade do canal está condenado a uma probabilidade de erro
elevada, independentemente do receptor ou da técnica de transmissão usada.
A codificação de canal (ou codificação com controlo de erros), referida no teorema da
codificação de canal, vai ser objecto do nosso estudo em seguida.
Resumo
2

Teoria da Informação

Transcrição

Documentos relacionados

MATEMÁTICA - UFJF/SIGA

Newsletter codificacao #2

Newsletter codificacao #4

contacte-nos - bizaffairs.pt

Método AASHTO-93 - departamento de transportes da ufpr

Matemática

Aditamento 16 - CCOMGEx

Lista de exercícios – Mais circuitos I 1

Matemática - Escola Virtual

resoluções ufrgs mat 2010