Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
Princípios de Comunicações
Prof. Rodrigo C. de Lamare
CETUC, PUC-Rio
mailto:[email protected]
V. Introdução à teoria da informação
A. Introdução
B. Fontes de informação e entropia
C. Codificação de fonte
D. Capacidade do canal
E. Codificação de canal
A. Introdução
o Neste capítulo, são estudadas noções de teoria da informação.
o A teoria da informação trata da modelagem matemática e da análise de sistemas de comunicações.
o Em particular, são examinados os limites fundamentais de compressão, a capacidade dos canais, e a confiabilidade da transmissão de sinais digitais.
o A teoria da informação é um ramo da teoria da probabilidade, que foi estabelecida por Claude Shannon em 1948.
C. E. Shannon: "A mathematical theory of communication." Bell System Technical Journal, vol. 27, pp. 379–423 and 623–656, July and October 1948
B. Fontes de informação e entropia
o Considere uma fonte discreta ilustrada por
o Considere a definição de uma alfabeto para essa fonte como
𝜉 = {𝑠0, 𝑠1, … , 𝑠𝐾 − 1} com probabilidades 𝑃(𝑠 = 𝑠𝑘) = 𝑝𝑘, 𝑘 = 0,1, … , 𝐾 − 1
o Esse conjunto de probabilidades deve satisfazer o seguinte:
fonte discreta sem memória
Fonte𝑠𝑘
1
0
k 1pK
k
Informação
o Dado um evento 𝑠 = 𝑠𝑘 que ocorre com probabilidade 𝑝𝑘, a quantidade de informação é descrita por
k
kp
1log)I(s
Informação (continuação)
o A informação usando logaritmo na base 2 é definida por
1K,0,1,kfor ),(plog
bits p
1log)I(s
k2
k
2k
Exemplo 1
Calcule a quantidade de informação quando 𝑝𝑘 = ½
Solução:
𝐼 𝑠𝑘 = log 21
𝑝𝑘= − log 2 𝑝𝑘
= − log 2 ½ = 1 bit
Propriedades
i) 𝐼(𝑠𝑘) = 0 quando 𝑝𝑘 = 1
Se há certeza quanto a um resultado de um evento então não há informação a obter.
ii) 𝐼(𝑠𝑘) ≥ 0 para 0 ≤ 𝑝𝑘 ≤ 1
A ocorrência de um evento fornece alguma informação ou não mas nunca gera perda de informação.
iii) 𝐼(𝑠𝑘) > 𝐼(𝑠𝑖) para 𝑝𝑘 < 𝑝𝑖
Quanto menos provável for um evento maior será o ganho de informação quando ele ocorre.
iv) 𝐼(𝑠𝑘𝑠𝑖) = 𝐼(𝑠𝑘) + 𝐼(𝑠𝑖) se 𝑠𝑘 e 𝑠𝑖 são estatisticamente independentes.
Entropia
o A entropia é definida como o conteúdo médio de informação por símbolo
de uma fonte discreta sem memória conforme descrito por
em que 𝜉 é o alfabeto
𝐼(𝑠𝑘) é o conteúdo de informação,
𝑝𝑘 é a probabilidade de símbolo para 𝑘 = 0,1, … , 𝐾 − 1
e a entropia depende apenas das probabilidades dos símbolos de 𝜉.
bits, p
1logp
)I(sp)]E[I(s) H(ξ
1K
0k k
2k
1K
0k
kkk
Propriedades da entropia
o Considere uma fonte discreta sem memória definida anteriormente.
o A entropia 𝐻(𝜉) desta fonte é limitada por
o Propriedades:
i) 𝐻(𝜉) = 0 se e somente se 𝑝𝑘 = 1 (sem incerteza)
ii) 𝐻(𝜉) = log2 𝐾 se e somente se 𝑝𝑘 =1
𝐾para todos os 𝑘 (máxima
incerteza)
Klog)H(0 2
Demonstração
o Como 𝑝𝑘 ≤ 1 cada termo de 𝑝𝑘 log2 (1/𝑝𝑘) em 𝐻(𝜉) é sempre nãonegativo. Logo, tem-se
𝐻(𝜉) ≥ 0
o Considerando que 𝑝𝑘 log2 (1/𝑝𝑘) = 0 se pk = 0 ou pk = 1 tem-se que𝐻(𝜉) = 0 se 𝑝𝑘 = 1 para qualquer k e probabilidades remanescentes𝑝𝑗 = 0, para 𝑗 ≠ 𝑘.
o Isto completa primeira parte da demonstração que
𝐻(𝜉) ≥ 0
Demonstração (continuação)
o Para obter o limitante superior 𝐻(𝜉) ≤ log2𝐾 adota-se a seguinteestratégia:
o Considere a desigualdade log 𝑥 ≤ 𝑥 − 1, 𝑥 ≥ 0
o Considere 2 distribuições de probabilidade dadas por {𝑝0, 𝑝1, … , 𝑝𝐾 − 1} e{𝑞0, 𝑞1, … , 𝑞𝐾 − 1} e o alfabeto 𝜉 = {𝑠0, 𝑠1, … , 𝑠𝐾 − 1} de uma fonte discretasem memória.
y = x-1
y = log x
Demonstração (continuação)
o Pode-se escrever a seguinte expressão usando o logaritmo natural:
o Usando a desigualdade log 𝑥 ≤ 𝑥 − 1, tem-se
k
kK
k
k
K
k k
kk
p
qp
p
qp
1
0
1
0 2
2 loglog
1log
1K
0k
1K
0k
kk
2
1K
0k
kk
2
k
k1K
0k
k
1K
0k 2k
k2k
0pqlog
1
pqlog
1
1p
qp
log
1
p
qlogp
Demonstração (continuação)
o Logo, tem-se
o Para qk = pk=0 tem-se
o Para qk = 1/K, k =0,1, ..., K-1 (símbolos equiprováveis) tem-se
1K
0k k
k2k 0
p
qlogp
1K
0k k
k2k 0
p
qlogp
1K
0k
2
k
2k logp
1logp K
Demonstração (continuação)
o Como a entropia de uma fonte discreta sem memória com símbolos equiprováveis é dada por
o Conclui-se a segunda parte da prova, ou seja,
𝐻(𝜉) ≤ log2𝐾
o A igualdade é obtida apenas para símbolos equiprováveis, o que justifica o seu uso em sistemas de transmissão digital.
1K
0k
2
1
0
2
k
2k loglog1
q
1logq)( KK
KH
K
k
Exemplo 2
Considere uma fonte binária simétrica com símbolos 𝑠𝑘 , 𝑘 = 0,1 eprobabilidades 𝑝0 e 𝑝1 = 1 − 𝑝0
a) Calcule a entropia da fonte
b) Esboce H(𝑝0)
Solução:
a) O cálculo da entropia da fonte é dado por
bits )p(1)logp(1plogpplogpplogp
p
1logp
p
1logp
p
1logp)(H
020020121020
1
21
0
2
1K
0k
0
k
2k
)p(1)logp(1plogp)p(H 0200200
b) O esboço de H(𝑝0) pode ser obtido da seguinte forma.
quando 𝑝0 = 0 −> 𝐻(𝜉) = 0 (𝑥 log 𝑥 −> 0 quando 𝑥 −> 0)
quando 𝑝0 = 1 −> 𝐻(𝜉) = 0
𝐻(𝜉) é máximo (𝐻(𝜉) = 1) quando 𝑝0 = 𝑝1 = 1/2
0 0.5 1
1H(p0)
p0
Extensão de uma fonte discreta sem memória
o Em teoria da informação e sistemas de comunicações, é útil considerarblocos de símbolos ao invés de símbolos individuais.
o Considere um bloco com 𝑛 símbolos e 𝐾 o número de símbolos no alfabeto ξda fonte.
o Pode-se interpretar cada bloco como um conjunto de símbolos produzido poruma fonte estendida com um alfabeto 𝜉𝑛 que tem 𝐾𝑛 blocos distintos.
o A entropia de uma fonte estendida é dada por
𝐻(𝜉𝑛) = 𝑛 𝐻(𝜉)
DMS DMS
n
sk𝑠𝑘1
𝑠𝑘2 …
𝑠𝑘𝑛
Entropia conjunta
o Considere um bloco de símbolos organizados em um vetor
𝒔 = 𝑠1 𝑠2 … 𝑠𝑛 𝑇
o A entropia conjunta é descrita por
𝐻 𝒔 = σ𝑝 𝒔 log1
𝑝 𝒔
= σ𝑖1 𝑖2 … 𝑖𝑛 𝑝 𝑠1 𝑠2… 𝑠𝑛 log
1
𝑝 𝑠1 𝑠2 … 𝑠𝑛
o Como estamos lidando com uma fonte discreta sem memória os símbolos da fonte são estatisticamente independentes .
o Portanto, as probabilidades envolvidas em 𝑝 𝒔 são desacopladas e 𝑝 𝒔 é igual ao produto das probabilidades
𝑝 𝒔 = 𝑝 𝑠1 𝑝(𝑠2)…𝑝(𝑠𝑛)
o Logo, a entropia conjunta pode ser reescrita como
𝐻 𝒔 = σ𝑝 𝒔 log1
𝑝 𝒔= 𝐻 𝜉𝑛
= σ𝑖1 𝑖2 … 𝑖𝑛 𝑝 𝑠1 𝑠2… 𝑠𝑛 log
1
𝑝 𝑠1 𝑠2 … 𝑠𝑛
= σ𝑖1 𝑖2 … 𝑖𝑛 𝑝 𝑠1 𝑝(𝑠2)…𝑝(𝑠𝑛) log1
𝑝 𝑠1 𝑝 𝑠2 …𝑝 𝑠𝑛
= σ𝑖1 𝑝 𝑠𝑖1 log1
𝑝 𝑠𝑖1σ𝑖2 𝑝 𝑠𝑖2 log
1
𝑝 𝑠𝑖2…σ𝑖𝑛 𝑝 𝑠𝑖𝑛 log
1
𝑝 𝑠𝑖𝑛
= 𝑛σ𝑖1 𝑝 𝑠𝑖1 log1
𝑝 𝑠𝑖1= nH 𝜉
o Desta forma, a entropia da fonte estendida é descrita por
𝐻(𝜉𝑛) = 𝑛 𝐻(𝜉)
Exemplo 3
Considere uma fonte discreta sem memória com alfabeto 𝜉 = {𝑠0, 𝑠1, 𝑠2} eprobabilidades dos símbolos 𝑝0 = 1/4, 𝑝1 = 1/4 and 𝑝2 = 1/2 . Para umaextensão desta fonte com um bloco de 2 símbolos tem-se
O alfabeto 𝜉2 = {𝜎0, 𝜎1, 𝜎2, 𝜎3, 𝜎4, 𝜎5, 𝜎6, 𝜎7, 𝜎8} corresponde à sequência 𝜉2 =
{𝑠0𝑠0, 𝑠0𝑠1, 𝑠0𝑠2, 𝑠1𝑠0, 𝑠1𝑠1, 𝑠1𝑠2, 𝑠2𝑠0, 𝑠2𝑠1, 𝑠2𝑠2} com probabilidades 𝑝0 =1/16, 𝑝1 = 1/16, 𝑝2 = 1/8 , 𝑝3 = 1/16 , 𝑝4 = 1/16 , 𝑝5 = 1/8 , 𝑝6 = 1/8 , 𝑝7 = 1/8
e 𝑝8 = 1/4.
a) Calcule a entropia da fonte
b) Calcule a entropia da fonte estendida.
DMS DMS DMSsk 𝑠𝑘1𝑠𝑘2
Solução:
a)
bits 2
3 2log
2
14log
4
14log
4
1
p
1logp
p
1logp
p
1logp
p
1logp)(H
222
2
22
1
21
0
2
1K
0k
0
k
2k
b)
3bits2
32)nH()H(ξ
or
bits 34log4
18log
8
18log
8
18log
8
116log
16
116log
16
1
8log8
116log
16
116log
16
1
p
1logp)H(ξ
2
222222
222
8
0k k
2k
2
C. Codificação de fonte
o Codificação de fonte corresponde à compressão de dados, e a teoria da informação descreve os limites fundamentais da compressão de dados.
o Shannon estabeleceu o limite fundamental que corresponde à entropia da fonte em 1948 através do teorema da codificação da fonte.
o Nesta seção, são examinadas técnicas de codificação de fonte sem perdas, que não resultam em perda da informação.
o As técnicas de quantização vistas no capítulo anterior são técnicas de codificação de fonte com perdas.
o Codificação de fonte é o processo de representar dados gerados por uma fonte discreta sem memória de forma eficiente.
o Neste contexto, o conhecimento da estatística da fonte pode ajudar na codificação e aumentar a eficiência do código produzido.
o Na nossa exposição, vamos usar as seguintes suposições:
o Uso de palavras-código binárias.
o O código da fonte é unicamente decodificável.
o A fonte tem um alfabeto com K símbolos, ou seja, 𝜉 = {𝑠0, 𝑠1, … , 𝑠𝐾−1 }.
o O k-ésimo símbolo 𝑠𝑘 ocorre com probabilidade 𝑝𝑘, 𝑘 = 0,1,… , 𝐾 − 1.
o O código binário 𝒄𝑘 usado para o símbolo 𝑠𝑘 tem comprimento 𝑙𝑘 em bits.
o Um esquema geral de codificação de fonte é ilustrado abaixo.
o O comprimento médio da palavra-código é descrito por
em que a quantidade acima corresponde ao número médio de bits usado para codificar os símbolos da fonte.
Fonte discreta sem memória
Codificador de fonte
bits lpl1K
0k
kk
𝑠𝑘 𝒄𝑘
𝑙𝑘 bits
o Eficiência da codificação de fonte:
em que lmin é o menor valor possível da palavra-código.
o Como obter lmin?
O primeiro teorema de Shannon “Teorema da codificação de fonte”
,min
l
l
Teorema de codificação de fonte
o Dada uma fonte discreta sem memória com entropia 𝐻(𝜉) , ocomprimento médio da palavra-código para qualquer esquema decodificação sem perdas é limitado por
o A entropia H(ξ) é o limite fundamental de compressão, ou seja, o limitepara o número médio de bits por símbolo da fonte requerido pararepresentar uma fonte discreta sem memória.
• Em um esquema de codificação de fonte, quando 𝑙𝑚𝑖𝑛 = 𝐻 𝜉 a eficiência é descrita por
)(Hl
𝜂 =𝐻 𝜉
ҧ𝑙
Shannon, Claude Elwood (July 1948). "A Mathematical Theory of Communication" (PDF). Bell System Technical Journal. 27 (3): 379–423.
https://en.wikipedia.org/wiki/Claude_Elwood_Shannonhttps://web.archive.org/web/19980715013250/http:/cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdfhttps://en.wikipedia.org/wiki/Bell_System_Technical_Journal
Exemplo 4
Considere os seguintes símbolos e probabilidades associadas com um fonte discreta sem memória e os códigos empregados.
a) Calcule a entropia da fonte
b) Determine o comprimento médio da palavra-código e a eficiência do código
Símbolos da fonte Probabilidades Código
𝑠0 0.5 0
𝑠1 0.25 10
𝑠2 0.15 110
𝑠3 0.1 111
Solução:
a) 𝐻 𝜉 = σ𝑘=0𝐾−1𝑝𝑘𝑙𝑜𝑔2
1
𝑝𝑘= 0.5 × 1 + 0.25 × 2 + 0.15 × 𝑙𝑜𝑔2
1
0.15+ 0.1 ×
𝑙𝑜𝑔2 10 = 1.7427 bits
b)
ҧ𝑙 = σ𝑘=0𝐾−1𝑝𝑘𝑙𝑘 = 0.5 × 1 + 0.25 × 2 + 0.15 × 3 + 0.1 × 3 = 1.75 bits
𝜂 =𝐻 𝜉
ҧ𝑙= 99.59 %
Codificação de prefixo
o Como as fontes costumam exibir algum tipo de redundância, é possível aumentar a eficiência da transmissão através de compressão da dados.
o A compressão de dados ou codificação pode ser de dois tipos:
o Sem perdas -> sem perda de informação
o Com perdas -> com perda de informação
o A codificação de prefixo pode obter um comprimento médio de palavra-código ҧ𝑙 arbitrariamente próximo da entropia 𝐻 𝜉 .
o Considere uma fonte discreta sem memória com alfabeto 𝜉 =𝑠0, 𝑠1, … , 𝑠𝐾−1 e probabilidades 𝑝0, 𝑝1, … , 𝑝𝐾−1 .
o Supõe-se que as palavras-código são unicamente decodificáveis e a seguinte condição de prefixo:
o Qualquer sequência que contenha a parte inicial da palavra-código é um prefixo.
𝑐𝑘1 𝑐𝑘2𝑐𝑘𝑖𝑘 𝑐𝑘𝑖+1 𝑐𝑘𝑖+2
𝑐𝑘𝑙𝑘… ...
𝑖𝑘
𝑙𝑘
Prefixo com comprimento 𝑖𝑘 bits
Palavra-código com comprimento 𝑙𝑘 bits
Exemplo 5
Considere os seguintes símbolos e probabilidades associadas com uma fonte discreta sem memória e os códigos usados.
Analise os códigos e determine se eles são códigos de prefixo.
Símbolos da fonte
Probabilidades Código A Código B Código C
𝑠0 0.5 0 0 0
𝑠1 0.25 1 10 01
𝑠2 0.15 00 110 011
𝑠3 0.1 11 111 0111
Solução:
O código A não é um código de prefixo porque o bit 0, a palavra-código para 𝑠0, é um prefixo de 00, a palavra-código para 𝑠2.
Da mesma forma, a palavra-código para 𝑠1, o bit 1, é um prefixo de 11, a palavra-código para 𝑠3.
Por razões similares, o código C também não é um código de prefixo.
O código B é um código de prefixo porque todos os prefixos das palavras-código são únicos, o que facilita a decodificação.
Decodificação de códigos de prefixo
• O decodificador de códigos de prefixo inspeciona o início da sequência e decodifica uma palavra-código a cada instante de tempo.
• Especificamente, emprega-se uma árvore de decisão para o código B descrito por
𝑠0
𝑠1
𝑠2
𝑠3
0
0
0
1
1
1
Estado inicial
Propriedades
i) Códigos unicamente decodificáveis
ii) Desigualdade de Kraft-McMillan
𝑘=0
𝐾−1
2−𝑙𝑘 ≤ 1
Supondo-se palavras-código binárias, os comprimentos das palavras-código devem sempre satisfazer a desigualdade acima.
Exemplo 6
Considere os seguintes símbolos e códigos produzidos por uma fonte discreta sem memória .
Descreva em detalhes a decodificação da sequência s = {1 0 1 1 1 1 1 0 0 0}
Símbolo da fonte
Código
𝑠0 0
𝑠1 10
𝑠2 110
𝑠3 111
Solução:
A sequência s = {1 0 1 1 1 1 1 0 0 0} produz a sequência de símbolos descrita por
𝑠1𝑠3𝑠2𝑠0𝑠0
A decodificação pode ser feita inspecionando-se a sequência de bits e identificando-se as palavras-código na tabela.
DecoderSequência Símbolos
Desigualdade de Kraft-McMillan
o Considere uma fonte discreta sem memória com alfabeto 𝜉 =𝑠0, 𝑠1, … , 𝑠𝐾−1 e probabilidades 𝑝0, 𝑝1, … , 𝑝𝐾−1 .
o Suponha que dispõe-se 𝐾 palavras-código binárias 𝒄𝑘 , 𝑘 = 0,1, … , 𝐾 − 1com comprimentos 𝑙0, 𝑙1, … , 𝑙𝐾−1 .
o Os comprimentos das palavras-código devem satisfazer a desigualdade de Kraft-McMillan
𝑘=0
𝐾−1
2−𝑙𝑘 ≤ 1
o A desigualdade mostra que pode-se construir um código de prefixo 𝒄𝑘 , 𝑘 = 0,1, … , 𝐾 − 1, com comprimentos −log2 𝑝𝑘.
Implicações da desigualdade de Kraft-McMillan
o O comprimento médio da palavra-código ҧ𝑙 é limitado por
𝐻 𝜉 ≤ ҧ𝑙 < 𝐻 𝜉 + 1
o O limitante inferior é satisfeito com igualdade se 𝒄𝑘 é produzido pela fonte com probabilidade
𝑝𝑘 = 2−𝑙𝑘 ,
em que 𝑙𝑘 é o comprimento da palavra-código designada. Isso nos leva a códigos ditos ótimos.
o Logo, tem-se
𝑘=0
𝐾−1
2−𝑙𝑘 =
𝑘=0
𝐾−1
𝑝𝑘 = 1
Códigos de prefixo ótimos
o Escolhendo-se códigos com uma relação específica entre suas probabilidades e comprimentos, obtém-se códigos de prefixo ótimos que resultam em
ҧ𝑙 =
𝑘=0
𝐾−1
𝑝𝑘 𝑙𝑘 → 𝐻 𝜉
o Para códigos de prefixo ótimos, a desigualdade de Kraft-McMillan mostra que o comprimento médio da palavra-código é dado por
ҧ𝑙 =
𝑘=0
𝐾−1
𝑝𝑘 𝑙𝑘 =
𝑘=0
𝐾−1
2−𝑙𝑘 𝑙𝑘 =
𝑘=0
𝐾−1𝑙𝑘2𝑙𝑘
o A entropia da fonte para 𝑙𝑘 = log2 2𝑙𝑘 é descrita por
𝐻 𝜉 =
𝑘=0
𝐾−11
2𝑙𝑘log2 2
𝑙𝑘 =
𝑘=0
𝐾−1𝑙𝑘2𝑙𝑘
= ҧ𝑙
o Nesse caso especial, tem-se 𝐻 𝜉 = ҧ𝑙, o que verifica novamente o limitante inferior.
o A verificação do limitante superior de 𝐻 𝜉 ≤ ҧ𝑙 < 𝐻 𝜉 + 1 pode ser feita examinando-se como o código pode ser casado a uma fonte arbitrária.
o Isso pode ser feito através de um código estendido.
o Considere ഥ𝑙𝑛 como o comprimento médio de uma palavra-código associada a um código estendido com 𝑛 símbolos, o que resulta em
𝐻 𝜉𝑛 ≤ ҧ𝑙𝑛 < 𝐻 𝜉𝑛 + 1
o Substituindo-se a relação da entropia de um código estendido na relação acima, obtém-se
𝑛𝐻 𝜉 ≤ ҧ𝑙𝑛 < 𝑛𝐻 𝜉 + 1
o Dividindo-se a expressão anterior por 𝑛, chega-se a
𝐻 𝜉 ≤ҧ𝑙𝑛
𝑛< 𝐻 𝜉 +
1
𝑛
o Calculando-se o limite quando 𝑛 → ∞, tem-se
lim𝑛 →∞
ҧ𝑙𝑛𝑛= 𝐻 𝜉
o Isso indica que com 𝑛 suficientemente grande, tem-se
ҧ𝑙 → 𝐻 𝜉
o Entretanto, essa abordagem implica em um aumento do custo computacional da decodificação.
Codificação de Huffman
o Ideias Básicas:
o Associar cada símbolo a um código (sequência de bits) aproximadamente igual em comprimento ao conteúdo de informação no símbolo.
o Substituir o conjunto de estatísticas (probabilidades) da fonte por um segundo conjunto mais simples.
o A codificação de Huffman requer as estatísticas da fonte, que podem ser obtidas off-line, e se aproxima da entropia da fonte.
o A codificação de Huffman pode ser adaptada às fontes estendidas.
Huffman, D. (1952). "A Method for the Construction of Minimum-Redundancy Codes" (PDF). Proceedings of the IRE. 40 (9): 1098–1101
https://en.wikipedia.org/wiki/David_A._Huffmanhttp://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdfhttps://en.wikipedia.org/wiki/Proceedings_of_the_IRE
Algoritmo de Huffman
i) Símbolos da fonte são listados em ordem decrescente de probabilidade.
ii) Os 2 símbolos com menores probabilidades são designados com 0 ou 1.
iii) Esses 2 símbolos são combinados em um novo símbolo com probabilidade igual à soma das probabilidades originais.
iv) O novo símbolo é listado com os símbolos remanescentes e suas probabilidades.
v) O procedimento é repetido até que apenas 2 símbolos chegam encontrados.
O código de Huffman é a sequência de 0s and 1s lida de trás para frente obtida pelos símbolos.
O código de Huffman não é único mas converge para a entropia 𝐻 𝜉
Exemplo 7
Cinco (5) símbolos de um alfabeto de uma fonte discreta sem memória e suas probabilidades são mostrados abaixo.
a) Construa o código de Huffman.
b) Calcule a entropia, o comprimento médio da palavra-código e a eficiência.
Símbolos da fonte Probabilidades
𝑠0 0.4
𝑠1 0.2
𝑠2 0.2
𝑠3 0.1
𝑠4 0.1
Solução:
a) Símbolos Estágio I Estágio II Estágio III Estágio IV
𝑠0 0.4 0.4 0.4 0.6
𝑠1 0.2 0.2 0.4 0.4
𝑠2 0.2 0.2 0.2
𝑠3 0.1 0.2
𝑠4 0.1
0
1
0
1
0
1
0
1
Símbolo da fonte
Probabilidades Códigos
𝑠0 0.4 00
𝑠1 0.2 10
𝑠2 0.2 11
𝑠3 0.1 010
𝑠4 0.1 011
b) O comprimento médio da palavra-código é
ҧ𝑙 = σ𝑘=0𝐾−1𝑝𝑘 𝑙𝑘 = 0.4 × 2 + 0.2 × 2 + 0.2 × 2 + 0.1 × 3 + 0.1 × 3 = 2.2 bits
A entropia é dada por
𝐻 𝜉 = σ𝑘=0𝐾−1𝑝𝑘𝑙𝑜𝑔2
1
𝑝𝑘
= 0.4 log2 1/0.4 +0.2 log2 1/0.2 + 0.2 log2 1/0.2 +0.1 log2(1/
Outras técnicas de codificação de fonte
o Codificação de Lempel-Ziv: universal, usado no ZIP e técnicas de compressão de arquivos.
o Codificação aritmética: usada em imagens e vídeos.
o Técnicas híbridas que misturam códigos de Huffman e as abordagens acima.
D. Capacidade do canal
o Nesta seção, examina-se como calcular a capacidade do canal e váriasimplicações do teorema da capacidade do canal de Shannon.
o Em particular, estuda-se o limite fundamental de quanta informação pode ser transmitida através de um canal dados parâmetros-chave.
o São apresentados modelos matemáticos de canais discretos e contínuos e explicações de como esses modelos descrevem canais realistas.
o O conceito de informação mútua é introduzido e sua relação com entropia e a capacidade do canal para canais discretos e contínuos é discutida.
Canais discretos sem memória
o Canais de comunicações representam o meio físico pelo qual os sinais sãotransmitidos.
o Em particular, canais de comunicações introduzem distorções deamplitude e fase nos sinais transmitidos.
o A modelagem dos canais de comunicações é fundamental porque elespodem ser simulados e as suas capacidades podem ser calculadas.
o Nesta seção, são descritos canais discretos sem memória usando osconceitos de probabilidade, variáveis aleatórias e fontes discretas semmemória.
o Considere um modelo de um canal discreto sem memória (DMC) como
𝒳
𝑋0𝑋1⋮
𝑋𝐽−1
ൢ
𝑌0𝑌1⋮
𝑌𝐾−1
𝒴
o O modelo pode ser escrito como
𝑦 = x + n,
em que n representa o ruído.
o O modelo é discreto porque 𝑦 e 𝑥 recebem valores discretos.
𝑝 𝑦𝑘|𝑥𝑗
𝑥 𝑦
AlfabetoAlfabeto
A descrição matemática de canais discretos sem memória (DMCs) inclui:
o Os alfabetos de entrada e saída descritos por
𝒳 = 𝑋0, 𝑋1, … , 𝑋𝐽−1 e 𝒴 = 𝑌0, 𝑌1, … , 𝑌𝐾−1
o O conjunto de probabilidades de transição dados por
𝑝 𝑦𝑘|𝑥𝑗 = P 𝑦𝑘 = 𝑌𝑘 𝑥𝑗 = 𝑋𝑗 , para todos 𝑗 𝑒 𝑘
em que 0 ≤ 𝑝 𝑦𝑘|𝑥𝑗 ≤ 1 para todos 𝑗 e 𝑘.
o O canal pode ser completamente caracterizado por um conjunto de probabilidades de transição descritas por
𝑷 =
𝑝 𝑦0|𝑥0 𝑝 𝑦1|𝑥0 … 𝑝 𝑦𝐾−1|𝑥0𝑝 𝑦0|𝑥1
⋮𝑝 𝑦1|𝑥1 …⋮ ⋱
𝑝 𝑦𝐾−1|𝑥1⋮
𝑝 𝑦0|𝑥𝐽−1 𝑝 𝑦1|𝑥𝐽−1 … 𝑝 𝑦𝐾−1|𝑥𝐽−1
o Uma propriedade chave que se aplica ao conjunto de probabilidades de transição é descrita por
𝑘=0
𝐾−1
𝑝 𝑦𝑘|𝑥𝑗 = 1, para todos 𝑗
o A entrada 𝑥 do DMC é modelada pela probabilidade
𝑝 𝑥𝑗 = 𝑃 𝑥𝑗 = 𝑋𝑗 , 𝑗 = 0,1, … , 𝐽 − 1
em que 𝑃 𝑥𝑗 = 𝑋𝑗 é a probabilidade de um evento.
o A fdp conjunta da entrada 𝑥 e da saída 𝑦 do DMC é dada por
𝑝 𝑥𝑗 , 𝑦𝑘 = 𝑃 𝑥𝑗 = 𝑋𝑗 , 𝑦𝑘 = 𝑌𝑘
= 𝑃 𝑦𝑘 = 𝑌𝑘|𝑥𝑗 = 𝑋𝑗 𝑃 𝑥𝑗 = 𝑋𝑗= 𝑝 𝑦𝑘|𝑥𝑗 𝑝 𝑥𝑗
o A pdf conjunta é chave pois ela contém as probabilidades de transição e de entrada.
o A saída do canal é descrita pela pdf dada por
𝑝 𝑦𝑘 = 𝑃 𝑦𝑘 = 𝑌𝑘
= σ𝑗=0𝐽−1𝑃 𝑦𝑘 = 𝑌𝑘|𝑥𝑗 = 𝑋𝑗 𝑃 𝑥𝑗 = 𝑋𝑗
= σ𝑗=0𝐽−1
𝑝 𝑦𝑘|𝑥𝑗 𝑝 𝑥𝑗 , 𝑘 = 0,1, … , 𝐾 −1
o Com essas quantidades matemáticas que constituem a estrutura dos DMCs é possível caracterizar completamente os canais.
Exemplo 8
Considere um canal binário simétrico com 𝐽 = 𝐾 = 2.
Como o canal é simétrico a probabilidade de receber 1 se 0 foi transmitidoé a mesma probabilidade de receber 0 se 1 foi transmitido. Isto éconhecido como probabilidade de erro condicional e descrita como 𝑝.
a) Descreva em um diagrama o canal binário simétrico e todas as suas probabilidades.
b) Calcule as probabilidades de entrada, transição e saída.
a) O canal binário simétrico (BSC) deste problema lida com J = 2 entradas,𝑥0 = 0 e 𝑥1 = 1.
Há também 𝐾 = 2 saídas, 𝑦0 = 0 e 𝑦1 = 1. O BSC pode ser ilustrado como
𝑥0 = 0
𝑥1 = 1
𝑦0 = 0
𝑦1 = 1
1 − 𝑝
1 − 𝑝
𝑝𝑝
b) As probabilidades de entrada são descritas por
𝑝 𝑥0 = 𝑃(𝑥0 = 0)
𝑝 𝑥1 = 𝑃(𝑥1 = 1)
As probabilidades de transição são descritas por𝑝 𝑦0|𝑥0 = 1 − 𝑝
𝑝 𝑦1|𝑥1 = 1 − 𝑝
𝑝 𝑦1|𝑥0 = 𝑝
𝑝 𝑦0|𝑥1 = 𝑝
As probabilidades de saída são descritas por
𝑝 𝑦0 = σ𝑗=0𝐽−1𝑝 𝑦0|𝑥𝑗 𝑝 𝑥𝑗 = 𝑝 𝑦0|𝑥0 𝑝 𝑥0 + 𝑝 𝑦0|𝑥1 𝑝 𝑥1 = 1 − 𝑝 𝑝 𝑥0 + 𝑝𝑝 𝑥1
𝑝 𝑦1 =
𝑗=0
𝐽−1
𝑝 𝑦1|𝑥𝑗 𝑝 𝑥𝑗 = 𝑝 𝑦1|𝑥0 𝑝 𝑥0 + 𝑝 𝑦1|𝑥1 𝑝 𝑥1 = 𝑝𝑝 𝑥0 + 1 − 𝑝 𝑝 𝑥1
𝑥0 = 0
𝑥1 = 1
𝑦0 = 0
𝑦1 = 1
1 − 𝑝
1 − 𝑝
𝑝𝑝
Informação mútua
o Considere um DMC e a entropia associada ao alfabeto de entrada 𝐻 𝒳 , que mede a incerteza sobre a entrada 𝑥.
o Uma questão importante para DMCs é como medir 𝐻 𝒳 quando seobserva 𝑦 ?
o Pode-se investigar isso examinando-se o conceito de entropiacondicional.
DMC
𝑝 𝑦𝑘|𝑥𝑗
𝑥 𝑦
𝒳 𝒴
o A entropia condicional para uma dada saída 𝑌𝑘 é descrita por
𝐻 𝒳|𝑦𝑘 = 𝑌𝑘 =
𝑗=0
𝐽−1
𝑝 𝑥𝑗|𝑦𝑘 log21
𝑝 𝑥𝑗|𝑦𝑘
o Se o valor médio de 𝐻 𝒳|𝑦𝑘 = 𝑌𝑘 for calculado então obtém-se a entropia condicional
𝐻 𝒳|𝒴 = σ𝑘=0𝐾−1𝐻 𝒳|𝑦𝑘 = 𝑌𝑘 𝑝 𝑦𝑘
= σ𝑘=0𝐾−1σ𝑗=0
𝐽−1𝑝 𝑥𝑗|𝑦𝑘 𝑝 𝑦𝑘 log21
𝑝 𝑥𝑗|𝑦𝑘
= σ𝑘=0𝐾−1σ𝑗=0
𝐽−1𝑝 𝑥𝑗 , 𝑦𝑘 log21
𝑝 𝑥𝑗|𝑦𝑘
o A entropia condicional 𝐻 𝒳|𝒴 mede a incerteza do canal após a observação da saída 𝑦.
o A informação mútua mede a incerteza sobre a entrada 𝑥 do DMC ao observar a saída 𝑦 do DMC.
o A informação mútua é definida por
𝐼 𝒳,𝒴 = 𝐻 𝒳 − 𝐻 𝒳|𝒴 ,
em que 𝐻 𝒳 mede a incerteza sobre a entrada 𝑥 e 𝐻 𝒳|𝒴 mede a incerteza do DMC após a observação da saída 𝑦 do DMC.
o Há uma equivalência de informação mútua se trocarmos a entrada pela saída do DMC, o que resulta em
𝐼 𝒴,𝒳 = 𝐻 𝒴 − 𝐻 𝒴|𝒳 ,
Propriedades
i) A informação mútua 𝐼 𝒳,𝒴 é simétrica, ou seja,
𝐼 𝒳,𝒴 = 𝐼 𝒴,𝒳
ii) A informação mútua é sempre não negativa, ou seja,
𝐼 𝒳,𝒴 ≥ 0
iii) A informação mútual 𝐼 𝒳, 𝒴 é relacionada à entropia conjunta da entrada e da saída do canal por
𝐼 𝒳,𝒴 = 𝐻 𝒳 + 𝐻 𝒴 − 𝐻 𝒳,𝒴 ,
𝐻 𝒳,𝒴 =
𝑘=0
𝐾−1
𝑗=0
𝐽−1
𝑝 𝑥𝑗 , 𝑦𝑘 log21
𝑝 𝑥𝑗 , 𝑦𝑘
Ilustração𝐻 𝒳,𝒴
𝐻 𝒳𝐼 𝒳,𝒴
𝐻 𝒴
𝐻 𝒴|𝒳𝐻 𝒳|𝒴
Capacidade de DMCs
o Considere um DMC e a entropia associada com o alfabeto de entrada 𝐻 𝒳 , que mede a incerteza sobre a entrada 𝑥.
o A informação mútua da entrada 𝑥 e da saída 𝑦 do canal é dada por
𝐼 𝒳,𝒴 =
𝑗=0
𝐽−1
𝑘=0
𝐾−1
𝑝 𝑦𝑘 , 𝑥𝑗 log2𝑝 𝑥𝑗|𝑦𝑘
𝑝 𝑥𝑗
=
𝑗=0
𝐽−1
𝑘=0
𝐾−1
𝑝 𝑦𝑘 , 𝑥𝑗 log2𝑝 𝑦𝑘|𝑥𝑗
𝑝 𝑦𝑘
DMC
𝑝 𝑦𝑘|𝑥𝑗
𝑥 𝑦
𝒳 𝒴
o A fdp conjunta das variáveis da entrada e saída do canal é dada por
𝑝 𝑦𝑘 , 𝑥𝑗 = 𝑝 𝑦𝑘|𝑥𝑗 𝑝 𝑥𝑗
o As probabilidades na saída podem ser calculadas por
𝑝 𝑦𝑘 =
𝑗=0
𝐽−1
𝑝 𝑦𝑘|𝑥𝑗 𝑝 𝑥𝑗 , 𝑘 = 0,1, … , 𝐾 −1
o Para calcular a informação mútua 𝐼 𝒳,𝒴 , é necessário obter as probabilidades da entrada do canal
𝑝 𝑥𝑗 , 𝑗 = 0,1, … , 𝐽 − 1
o A capacidade do DMC pde ser calculada maximizando-se a informação mútua 𝐼 𝒳,𝒴 sujeito a restrições apropriadas em 𝑝 𝑥𝑗 .
o O cálculo da capacidade pode ser formulado como a seguinte otimização:
𝐶 = max𝑝 𝑥𝑗
𝐼 𝒳, 𝒴 bits/uso do canal ou bits / transmissão
sujeito a 𝑝 𝑥𝑗 , for all 𝑗 e σ𝑗=0𝐽−1𝑝 𝑥𝑗 = 1
o A otimização envolve a maximização de 𝐼 𝒳,𝒴 ajustando-se as variáveis 𝑝 𝑥1 , 𝑝 𝑥2 , … , 𝑝 𝑥𝐽−1 sujeito a restrições apropriadas.
Exemplo 9
Considere o BSC ilustrado por
a) Calcule a capacidade do canal.
b) Mostre como a capacidade varia com 𝑝 usando um esboço.
𝑥0 = 0
𝑥1 = 1
𝑦0 = 0
𝑦1 = 1
1 − 𝑝
1 − 𝑝
𝑝𝑝
a) Considere o BSC.
Sabe-se que a entropia 𝐻 𝒳 é maximizada quando 𝑝 𝑥0 = 𝑝 𝑥1 =1
2, em
que 𝑥0 e 𝑥1 são 0 e 1, respectivamente.
A informação mútua 𝐼 𝒳,𝒴 é maximizada de forma similar conforme
𝐶 = 𝐼 𝒳,𝒴 quando 𝑝 𝑥0 = 𝑝 𝑥1 =1
2,
em que
𝑝 𝑦0|𝑥0 = 1 − 𝑝 = 𝑝 𝑦1|𝑥1𝑝 𝑦1|𝑥0 = 𝑝 = 𝑝 𝑦0|𝑥1
𝑥0 = 0
𝑥1 = 1
𝑦0 = 0
𝑦1 = 1
1 − 𝑝
1 − 𝑝
𝑝𝑝
Substituindo-se as probabilidades de transição em 𝐼 𝒳,𝒴 , obtém-se
𝐼 𝒳,𝒴 = σ𝑗=0𝐽−1σ𝑘=0
𝐾−1𝑝 𝑦𝑘 , 𝑥𝑗 log2𝑝 𝑦𝑘|𝑥𝑗
𝑝 𝑦𝑘
Com 𝐽 = 𝐾 = 2 e fazendo-se 𝑝 𝑥0 = 𝑝 𝑥1 =1
2, tem-se
𝐶 = max𝑝 𝑥𝑗
σ𝑗=01 σ𝑘=0
1 𝑝 𝑦𝑘 , 𝑥𝑗 log2𝑝 𝑦𝑘|𝑥𝑗
𝑝 𝑦𝑘
= 𝑝 𝑦0, 𝑥0 log2𝑝 𝑦0|𝑥0𝑝 𝑦0
+ 𝑝 𝑦0, 𝑥1 log2𝑝 𝑦0|𝑥1𝑝 𝑦0
+𝑝 𝑦1, 𝑥0 log2𝑝 𝑦1|𝑥0𝑝 𝑦1
+ 𝑝 𝑦1, 𝑥1 log2𝑝 𝑦1|𝑥1𝑝 𝑦1
= 𝑝 𝑦0|𝑥0 𝑝 𝑥0 log2𝑝 𝑦0|𝑥0
𝑝 𝑦0+ 𝑝 𝑦0|𝑥1 𝑝 𝑥1 log2
𝑝 𝑦0|𝑥1
𝑝 𝑦0
+𝑝 𝑦1|𝑥0 𝑝 𝑥0 log2𝑝 𝑦1|𝑥0
𝑝 𝑦1+ 𝑝 𝑦1|𝑥1 𝑝 𝑥1 log2
𝑝 𝑦1|𝑥1
𝑝 𝑦1
=1−𝑝
2log2 2(1 − 𝑝) +
𝑝
2log2 2𝑝 +
𝑝
2log2 2𝑝 +
1−𝑝
2log2 2(1 − 𝑝)
= 1 + plog2 𝑝 + (1 − 𝑝) log2(1 − 𝑝)
b) Usando a definição de entropia e suas relações matemáticas chega-se à capacidade do canal BSC
𝐶 𝑝 = 1 − 𝐻(𝑝),
em que H p = −plog2 𝑝 − 1 − 𝑝 log2 1 − 𝑝 .
A capacidade do canal varia com 𝑝 de uma forma convexa como mostrado abaixo.
𝑝
𝐶(𝑝)
0.5 1
0.5
1
Quando 𝑝 = 0, 𝐶 atinge o seu valor máximo de 1 bit/ uso do canal
Quando 𝑝 =1
2, 𝐶 atinge seu valor
mínimo de 0 bit/ uso do canal (canal inutilizado)
Entropia diferencial e informação mútua para variáveis contínuas
o Os conceitos anteriores envolvendo fontes e canais podem serestendidos para variáveis contínuas.
o Considere uma variável aleatória 𝑥 com fdp 𝑝𝑥(𝑋), a entropia diferencialé descrita por
ℎ 𝑥 = න−∞
∞
𝑝𝑥 𝑋 log21
𝑝𝑥(𝑋)𝑑𝑋
o Como no caso discreto visto anteriormente, a entropia diferencialdepende apenas da fdp da variável aleatória 𝑥.
Exemplo 10
Calcule a entropia diferencial de uma variável aleatória com distribuição uniforme descrita por
𝑝𝑥 𝑋 = ቐ1
𝑎, 0 < 𝑋 < 𝑎
0, caso contrário
1
𝑎
𝑎 𝑋
𝑝𝑥 𝑋
Solução:
ℎ 𝑥 = න−∞
∞
𝑝𝑥 𝑋 log21
𝑝𝑥(𝑋)𝑑𝑋
= 0𝑎 1
𝑎log2 𝑎 𝑑𝑋
= log2 𝑎 bits
Note que log2 𝑎 < 0 para 𝑎 < 1.
A entropia de uma variável aleatória contínua pode ser negativadiferentemente do caso de uma variável aleatória discreta.
Exemplo 11
Calcule a entropia diferencial de uma variável aleatória com distribuição Gaussiana descrita por
𝑝𝑥 𝑋 =1
2𝜋𝜎2𝑒−𝑋2
2𝜎2
𝑋
𝑝𝑥 𝑋
Solução:
h 𝑥 = ∞−∞
𝑝𝑥 𝑋 ln1
𝑝𝑥(𝑋)𝑑𝑋 (nats)
= ∞−−∞𝑝𝑥 𝑋 ln 𝑝𝑥(𝑋) 𝑑𝑋
= ∞−−∞𝑝𝑥 𝑋 −
𝑋2
2𝜎2− ln 2𝜋𝜎2 𝑑𝑋
=1
2ln 2𝜋𝜎2 +
1
2
𝐸 𝑥2
𝜎2
=1
2ln 2𝜋𝜎2 +
1
2ln e
=1
2ln 2𝜋𝑒𝜎2 nats
Mudando-se a base do logaritmo de ln para log2 , tem-se
h 𝑥 =1
2log2 2𝜋𝑒𝜎
2 bits
Entropia diferencial condicional e conjunta: extensão para vetores
o Pode-se estender a definição da entropia diferencial para vetores aleatórios.
o A entropia diferencial conjunta para um vetor aleatório 𝒙 = 𝑥1 … 𝑥𝑛 𝑇 é definida por
ℎ 𝒙 = න−∞
∞
𝑝𝒙 𝑿 log21
𝑝𝒙(𝑿)𝑑𝑿
o A entropia diferencial condicional de 2 variáveis 𝑥 e 𝑦 é descrita por
ℎ 𝑥 𝑦 = න−∞
∞
න−∞
∞
𝑝𝑥,𝑦 𝑋, 𝑌 log21
𝑝𝑥(𝑋|𝑌)𝑑𝑋𝑑𝑌
o Como tem-se 𝑝𝑥 𝑋 𝑌 = 𝑝𝑥,𝑦 𝑋, 𝑌 /𝑝𝑦(𝑌), pode-se escrever
ℎ 𝑥 𝑦 = ℎ 𝑥, 𝑦 − ℎ(𝑦)
Exemplo 12
Calcule a entropia diferencial de um vetor Gaussiano 𝒙 = 𝑥1 … 𝑥𝑛 𝑇 cuja fdp conjunta é descrita por
𝑝𝒙 𝑿 =1
2𝜋𝑛2 det(𝑲)
𝑒−12 𝑿−𝒎𝑥
𝑇𝑲−1(𝑿−𝒎𝑥)
Solução:
ℎ 𝒙 = ∞−∞
𝑝𝒙 𝑿 ln1
𝑝𝒙(𝑿)𝑑𝑿 (nats)
= ∞−−∞
𝑝𝒙 𝑿 −1
2𝑿 −𝒎𝑥
𝑇𝑲−1 𝑿 −𝒎𝑥 − ln 2𝜋𝑛
2 det 𝑲1
2 𝑑𝑿
=1
2E 𝒙 −𝒎𝑥
𝑇𝑲−1 𝒙 −𝒎𝑥 +1
2ln 2𝜋 𝑛 det 𝑲
=1
2𝑡𝑟 𝑲𝑲−1 +
1
2ln 2𝜋 𝑛 det 𝑲
=1
2𝑛 ln 𝑒 +
1
2ln 2𝜋 𝑛 det 𝑲
=1
2ln 𝑒𝑛 +
1
2ln 2𝜋 𝑛 det 𝑲
=1
2ln 2𝜋𝑒 𝑛 det 𝑲
Mudando-se a base do logaritmo, chega-se a
ℎ 𝒙 =1
2log2 2𝜋𝑒
𝑛 det 𝑲 bits
Informação mútua
o Considere um par de variáveis aleatórias 𝑥 e 𝑦 que podem representar a entrada e a saída de um canal de comunicações.
o A informação mútua entre 𝑥 e 𝑦 é definida por
𝐼 𝑥, 𝑦 = ∞−∞
∞−∞
𝑝𝑥,𝑦 𝑋, 𝑌 log2𝑝𝑥(𝑋|𝑌)
𝑝𝑥(𝑋)𝑑𝑋𝑑𝑌,
em que 𝑝𝑥,𝑦 𝑋, 𝑌 é a fdp conjunta de 𝑥 e 𝑦 , e 𝑝𝑥(𝑋|𝑌) é fdp condicional de 𝑥sujeito a 𝑦 = 𝑌.
Canal
𝑥 𝑦
o A entropia diferencial condicional de 2 variáveis 𝑥 e 𝑦 é descrita por
ℎ 𝑥 𝑦 = න−∞
∞
න−∞
∞
𝑝𝑥,𝑦 𝑋, 𝑌 log21
𝑝𝑥(𝑋|𝑌)𝑑𝑋𝑑𝑌
o Como tem-se 𝑝𝑥 𝑋 𝑌 = 𝑝𝑥,𝑦 𝑋, 𝑌 /𝑝𝑦(𝑌), pode-se escrever
ℎ 𝑥 𝑦 = ℎ 𝑥, 𝑦 − ℎ(𝑦)
o Essas relações são úteis para calcular a informação mútua em situaçõespráticas.
Propriedades da informação mútua
i) 𝐼 𝑥, 𝑦 = 𝐼 𝑦, 𝑥 (simetria)
ii) 𝐼 𝑥, 𝑦 ≥ 0 (não negatividade)
iii) 𝐼 𝑥, 𝑦 = ℎ 𝑥 − ℎ 𝑥 𝑦
= ℎ 𝑦 − ℎ(𝑦|𝑥)
o São propriedades semelhantes às propriedades com variáveis discretas.
Exemplo 13
Calcule a informação mútua entre a entrada 𝑥 e a saída 𝑦 do canal
quando ambos 𝑥 e 𝑦 são variáveis aleatórias Gaussianas com média zero e variância 𝜎2 e a matriz covariância de 𝒖 = 𝑥 𝑦 𝑻 é dada por
𝑲 = 𝐸 𝒖 −𝒎𝑢 𝒖 −𝒎𝑢𝑇 =
𝜎2 𝜌𝜎2
𝜌𝜎2 𝜎2,
em que 𝒎𝑢 é o vetor média de 𝒖.
Canal
𝑥 𝑦
Solução:
As entropias diferenciais da entrada 𝑥 e da saída 𝑦 do canal são
ℎ 𝑥 =1
2log2 2𝜋𝑒 𝜎
2 = ℎ(𝑦)
A entropia diferencial conjunta é dada por
ℎ 𝑥, 𝑦 = ∞−∞
∞−∞
𝑝𝑥,𝑦 𝑋, 𝑌 log21
𝑝𝑥(𝑋|𝑌)𝑑𝑋𝑑𝑌
=1
2log2 2𝜋𝑒
2 det 𝑲
=1
2log2 2𝜋𝑒
2σ4(1 − 𝜌2)
Desta forma, a informação mútua é descrita por
𝐼 𝑥, 𝑦 = ℎ 𝑥 − ℎ 𝑥 𝑦
= ℎ 𝑥 + ℎ 𝑦 − ℎ(𝑥, 𝑦)
=1
2log2 2𝜋𝑒 𝜎
2 +1
2log2 2𝜋𝑒 𝜎
2 −1
2log2 2𝜋𝑒
2σ4(1 − 𝜌2)
=1
2log2 (1 − 𝜌
2),
em que ℎ 𝑥 𝑦 = ℎ 𝑥, 𝑦 − ℎ(𝑦)
Capacidade de canais Gaussianos
o A capacidade de canais Gaussianos é obtida pela maximização dainformação mútua entre a entrada e a saída do canal.
• Neste caso, é preciso considerer todas as possibilidades da entrada que sastisfazem a restrição de potência 𝑃.
• Matematicamente, a capacidade de canais Gaussianos com restrição de potência 𝑃 é descrita por
𝐶 = max𝑝𝑥(𝑋)
𝐼 𝑥, 𝑦
sujeito a 𝐸 𝑥2 ≤ 𝑃
Channel
𝑥 𝑦
Teorema da capacidade do canal (Shannon, 1948)
A capacidade de um canal contínuo com largura de faixa limitada a 𝐵 Hzperturbado por ruído aditivo Gaussiano branco (AWGN) com densidade
espectral de potência𝑁0
2é dada por
𝐶 = 𝐵 log2 1 +𝑃
𝑁0𝐵, bits/ s
em que 𝑃 é a potência média de transmissão.
Esse teorema mostra que dados 𝑃 e 𝐵 pode-se transmitir informação a umataxa de 𝐶 bits por segundo.
Cálculo da capacidade
o Para obter a capacidade é preciso resolver o problema de otimização
𝐶 = max𝑝𝑥(𝑋)
𝐼 𝑥, 𝑦
subject to 𝐸 𝑥2 ≤ 𝑃
o Considera-se primeiro o modelo do canal descrito por
𝑦 = 𝑥 + 𝑛,
em que 𝑛 é AWGN com média zero e variância 𝜎2.
o Em seguida, desenvolve-se a expressão da informação mútua:
𝐼 𝑥, 𝑦 = ℎ 𝑦 − ℎ(𝑦|𝑥)
o A expressão da informação mútua pode ser simplificada conforme
𝐼 𝑥, 𝑦 = ℎ 𝑦 − ℎ(𝑦|𝑥)
= ℎ 𝑦 − ℎ(𝑥 + 𝑛|𝑥)
= ℎ 𝑦 − ℎ(𝑛|𝑥)
= ℎ 𝑦 − ℎ 𝑛 ,
o que leva em consideração que 𝑥 e n são estatisticamente independentes.
o Em seguinda, é preciso calcular as entropias diferenciais ℎ 𝑦 e ℎ 𝑛 .
o A entropia diferencial do ruído AWGN é descrita por
ℎ 𝑛 =1
2log2 2𝜋𝑒𝜎
2
o Depois, calcula-se a variância de 𝑦, que é dada por
𝜎𝑦2 = 𝐸 𝑦2
= 𝐸 𝑥 + 𝑛 2 = 𝐸 𝑥2 + 𝐸 𝑛2 = 𝑃 + 𝜎2
o A entropia diferencial de 𝑦 é expressa por
ℎ 𝑦 =1
2log2 2𝜋𝑒𝜎𝑦
2
=1
2log2 2𝜋𝑒 𝑃 + 𝜎
2
o A capacidade é o valor máximo da informação mútua sujeito a restriçãode potência, que é levada em conta em ℎ 𝑦 , e resulta em
Ct = max 𝐼 𝑥, 𝑦 = ℎ 𝑦 − ℎ 𝑛
=1
2log2 2𝜋𝑒 𝑃 + 𝜎
2 −1
2log2 2𝜋𝑒𝜎
2
=1
2log2
𝑃+𝜎2
𝜎2
=1
2log2 1 +
𝑃
𝜎2bits / transmissão
o Nota-se que a maximização de ℎ 𝑦 requer que 𝑦 seja Gaussiana poisvariáveis aleatórias Gaussianas têm a maior entropia diferencial.
o A capacidade também pode ser expressa por unidade de tempoconsiderando que 𝐾 amostras são transmitidas em 𝑇 segundos, queresultam em
C =K
TCt =
K
T
1
2log2 1 +
𝑃
𝜎2
=2BT
T
1
2log2 1 +
𝑃
𝜎2
= 𝐵 log2 1 +𝑃
𝑁0𝐵bits / second
o Na expressão acima, derivada por Shannon, emprega-se K = 2BTamostras, em que 𝐵 é a largura de faixa.
Implicações do teorema da capacidade do canal
o Em um sistema ideal, transmite-se à taxa 𝑅𝑏 = 𝐶 bits /s.
o Se levarmos em conta 𝑃 = 𝐸𝑏𝐶, em que 𝐸𝑏 é a energia transmitida porbit, tem-se
𝐶
𝐵= log2 1 +
𝑃
𝑁0𝐵= log2 1 +
𝐸𝑏𝐶
𝑁0𝐵
o A eficiência espectral é a razão da energia do bit pela densidadespectral de potência dada por
𝐸𝑏
𝑁0=
2𝐶𝐵−1𝐶
𝐵
𝐸𝑏
𝑁0(dB)
𝑅𝑏𝐵
𝑅𝑏 < 𝐶
𝑅𝑏 > 𝐶
i) Quando 𝐶
𝐵→ ∞
𝐸𝑏
𝑁0se aproxima de
𝐸𝑏𝑁0 ∞
= lim𝐵→∞
𝐸𝑏𝑁0
=1
log2 𝑒= 0,693 or −1.6 dB
O limite da capacidade é descrito por
𝐶∞ = lim𝐵→∞
C =P
N0log2e Limite de Shannon
Demonstração
Como log2 1 + 𝑥 = 𝑥 𝑙𝑜𝑔2 1 + 𝑥1
𝑥 e lim𝑥→∞
1 + 𝑥1
𝑥 = 𝑒, tem-se
𝐶
𝐵= log2 1 +
𝑃
𝑁0𝐵
=𝐶
𝐵
𝐸𝑏
𝑁0log2 1 +
𝐶
𝐵
𝐸𝑏
𝑁0
𝑁0𝐵
𝐶𝐸𝑏
Pode-se simplificar a relação acima como
𝐸𝑏𝑁0
log2 1 +𝐶
𝐵
𝐸𝑏𝑁0
𝑁0𝐵𝐶𝐸𝑏
= 1
Se 𝐶
𝐵→ ∞ então óbtém-se
𝐸𝑏𝑁0
=1
log2e= 0,693
ii) Limitante da capacidade 𝑅𝑏 = 𝐶
• Quando 𝑅𝑏 ≤ 𝐶 → transmissão livre de erros é possível
• Quando 𝑅𝑏 > 𝐶 → transmissão livre de erros não é possível
𝐸𝑏
𝑁0(dB)
𝑅𝑏𝐵
𝑅𝑏 < 𝐶
𝑅𝑏 > 𝐶
E. Codificação de canal
o Nesta seção, estuda-se codificação de canal, o teorema da codificação decanal de Shannon e suas implicações.
o Em particular, examina-se o limite fundamental de como transmitir informação de forma confiável em canal dados alguns parâmetros-chave.
o Um modelo matemático de um sistema de comunicações digitais é apresentado e discute-se como a codificação de canal pode beneficiá-lo.
o O teorema da codificação de canal é apresentado e são examinadas suas implicações em termos de probabilidade de erro e como torna-la pequena.
Modelo de comunicações digitais
• Comunicações digitais em um canal com capacidade 𝐶 envolve muitas operações como codificação de fonte, codificação de canal, modulação e decodificação.
FonteCodif. de
fonteCodif. de
canal
Canal
Decod. de canal
Decod. de fonte
Modulador
Demodulador
𝒔 𝒎 𝒄
𝒚ෞ𝒎 ො𝒄
o Confiabilidade é um objetivo importante em comunicações digitais que é medida em termos de probabilidade de erro de símbolo 𝑃𝑒.
o Para conseguir transmissões confiáveis é preciso empregar codificaçãode canal.
𝑃𝑒
𝑆𝑁𝑅 (dB)
10−1
10−2
10−3
10−4
10−5
Tx Rx
o Codificação de canal aumenta a resistência do sistema contra erros de canal em comunicações digitais.
o A ideia básica de codificação de canal é introduzir redundância.
o A mensagem 𝒎 com 𝑘 bits é mapeada em uma palavra-código 𝒄 com 𝑛bits, que é então transmitida.
o Essa redundância se traduz em uma taxa de código dada por
𝑅 =𝑘
𝑛, 0 < 𝑅 < 1
Codificadorde canal
𝒎 𝒄
1 × 𝑘 1 × 𝑛
o A receptor deve lidar com ruído (AWGN e outros) e com a tarefa de decodificação do canal.
o Questão fundamental:
o Há um esquema de codificação que permite transmissão de mensagens com probabilidade de erro menor do que um número pequeno positivo 𝜖 ?
CanalDecod.
de canalDemodulador
𝒚 ෝ𝒄Receptor
Teorema da codificação de canal (Shannon, 1948)
Para um canal discreto sem memória com capacidade 𝐶 que transmiteinformação a uma taxa 𝑅 ≤ 𝐶 há um esquema de codificação em que aprobabilidade de erro pode se tornar arbitrariamente pequena, ou seja,
𝑃𝑒 ≤ 𝜖 + 2−𝑛𝑅 𝐼 𝑥,𝑦 −𝛿−𝑅 ,
que pode ser feito arbitrariamente pequeno se 𝑅 < 𝐼 𝑥, 𝑦 ou de formaequivalente 𝑅 ≤ C para 𝜖 e 𝛿 pequenos
Para 𝑛 → ∞ com 𝑅 fixo, tem-se𝑃𝑒 ≤ 𝜖
Essa parte é conhecida como alcançabilidade.
Por outro lado, se 𝑅 > 𝐶 não há um esquema de codificação de canal capaz deobter 𝑃𝑒 arbitrariamente pequena.
Interpretação do teorema
o Para uma taxa de código 𝑅 ≤ 𝐶 pode-se transmitir informação com 𝑃𝑒arbitrariamente pequena.
o O teorema considera códigos aleatóriosmas códigos de canal modernos podemalcançar a capacidade.
o Alternativamente, um projetista podeusar taxas mais baixas e se aproximar do limite de Shannon.
𝑅
𝑃𝑒
𝜖
1𝐶
Channel capacity
𝑆𝑁𝑅
𝑃𝑒
𝜖
Limite de Shannon
−1.6 𝑑𝐵
Implicações do teorema de codificação de canal
o Considere um código de repetição usado para transmissão digital em umcanal BSC com probabilidade de erro 𝑝 = 10−2.
o Para o canal BSC com 𝑝 = 10−2 a capacidade é descrita por
𝐶 = 1 − 𝑝 log2 𝑝 − 1 − 𝑝 log2 1 − 𝑝
= 0.9192
o Usando o teorema da codificação de canal, sabe-se que para 𝜖 > 0 e 𝑅 <0.9192 há um código de canal com 𝑛 suficientemente grande, taxa decódigo 𝑅 e algoritmo de decodificação que resulta em
𝑃𝑒 ≤ 𝜖
Ilustração
• Para 𝜖 = 10−8, tem-se
𝑅
𝑃𝑒
𝜖 = 10−8
1𝐶
Capacidade do canal
Exemplo 14
Considere um código de repetição e transmissão de dados pelo canal BSC com 𝑝 = 10−2 que funciona da seguinte forma:
o Cada bit da mensagem 𝒎 é repetido múltiplas vezes.
o Para cada bit (0 ou 1) repete-se o bit 𝑛 vezes, em que 𝑛 = 2𝑚 + 1 e 𝑛 sãointeiros ímpares.
A decodificação deste código emprega a lógica da maioria que funciona da seguinte maneira:
o Se o número de 1s ≥ número de 0s → o decodificador decide em favor de 1
o Se o número de 1s < número de 0s → o decodificador decice em favor de 0
a) Calcule a probabilidade de erro de símbolo 𝑃𝑒 e explique sua importância.
b) Esboce a 𝑃𝑒 para 𝑅 = 1,1
3,1
5,1
7,1
9,1
11usando 𝜖 = 10−8.
Solução:
a) A probabilidade de erro de símbolo é descrita por
𝑃𝑒 =
𝑖=𝑚+1
𝑛𝑛𝑖𝑝𝑖 1 − 𝑝 𝑛−𝑖 ,
em que 𝑝 é a probabilidade do canal BSC.
A probabilidade de erro 𝑃𝑒 é frequentemente usada como figura de méritoe medida contra a razão sinal-ruído (SNR).
b) O desempenho do código de repetição é ilustrado pela probabilidade de erro 𝑃𝑒 versus a taxa do código 𝑅.
Taxa do código (R) Probabilidade de erro 𝑃𝑒1 10−2
1
33 × 10−4
1
510−6
1
74 × 10−7
1
910−8
1
115 × 10−10
𝑅
𝑃𝑒
𝜖 = 10−8
1𝐶
10−2