Teorema de codificação de canal ruidoso - Noisy-channel coding theorem

Teoria da informação
Entropia Entropia diferencial Entropia condicional Entropia conjunta Informação mútua Informação mútua condicional Entropia relativa Taxa de entropia Limitando a densidade de pontos discretos Teoria da informação de comprimento de bloco finito
Propriedade de equipartição assintótica Teoria de taxa de distorção
Teorema de codificação de fonte de Shannon Capacidade do canal Teorema de codificação de canal ruidoso Teorema de Shannon-Hartley
v t e

Na teoria da informação , o teorema de codificação de canal ruidoso (às vezes teorema de Shannon ou limite de Shannon ), estabelece que para qualquer determinado grau de contaminação de ruído de um canal de comunicação , é possível comunicar dados discretos ( informação digital ) quase sem erros até uma taxa máxima computável através do canal. Este resultado foi apresentado por Claude Shannon em 1948 e foi baseado em parte no trabalho anterior e nas idéias de Harry Nyquist e Ralph Hartley .

O limite de Shannon ou capacidade de Shannon de um canal de comunicação refere-se à taxa máxima de dados sem erros que podem teoricamente ser transferidos pelo canal se o link estiver sujeito a erros de transmissão de dados aleatórios, para um determinado nível de ruído. Foi descrito pela primeira vez por Shannon (1948) e, pouco depois, publicado em um livro de Shannon e Warren Weaver intitulado The Mathematical Theory of Communication (1949). Isso fundou a disciplina moderna da teoria da informação .

Visão geral

Declarado por Claude Shannon em 1948, o teorema descreve a máxima eficiência possível dos métodos de correção de erros versus níveis de interferência de ruído e corrupção de dados. O teorema de Shannon tem aplicações abrangentes em comunicações e armazenamento de dados . Este teorema é de importância fundamental para o campo moderno da teoria da informação . Shannon deu apenas um esboço da prova. A primeira prova rigorosa para o caso discreto deve-se a Amiel Feinstein em 1954.

O teorema de Shannon afirma que, dado um canal ruidoso com capacidade de canal C e informação transmitida a uma taxa R , então, se existem códigos que permitem que a probabilidade de erro no receptor seja arbitrariamente pequena. Isto significa que, teoricamente, é possível transmitir informações quase sem erro em qualquer taxa inferior a uma limitação de velocidade, C . ${\ displaystyle R <C}$

O inverso também é importante. Se , uma probabilidade de erro arbitrariamente pequena não é alcançável. Todos os códigos terão uma probabilidade de erro maior do que um certo nível mínimo positivo, e esse nível aumenta à medida que a taxa aumenta. Portanto, não é possível garantir que as informações sejam transmitidas de forma confiável através de um canal a taxas além da capacidade do canal. O teorema não aborda a rara situação em que a taxa e a capacidade são iguais. ${\ displaystyle R> C}$

A capacidade do canal pode ser calculada a partir das propriedades físicas de um canal; para um canal de banda limitada com ruído gaussiano, usando o teorema de Shannon-Hartley . ${\ displaystyle C}$

Esquemas simples como "enviar a mensagem 3 vezes e usar o melhor esquema de votação 2 de 3 se as cópias forem diferentes" são métodos de correção de erros ineficientes, incapazes de garantir assintoticamente que um bloco de dados pode ser comunicado sem erros. Técnicas avançadas, como códigos Reed-Solomon e, mais recentemente, códigos de verificação de paridade de baixa densidade (LDPC) e códigos turbo , chegam muito mais perto de atingir o limite teórico de Shannon, mas a um custo de alta complexidade computacional. Usando esses códigos altamente eficientes e com o poder de computação dos processadores de sinais digitais de hoje , agora é possível chegar muito perto do limite de Shannon. Na verdade, foi mostrado que os códigos LDPC podem atingir 0,0045 dB do limite de Shannon (para canais binários de ruído gaussiano branco aditivo (AWGN), com comprimentos de bloco muito longos).

Declaração matemática

O modelo matemático básico para um sistema de comunicação é o seguinte:

${\ displaystyle {\ xrightarrow [{\ text {Message}}] {W}} {\ begin {array} {| c | } \ hline {\ text {Codificador}} \\ f_ {n} \\\ hline \ end {array}} {\ xrightarrow [{\ mathrm {Codificado \ na seqüência superior}}] {X ^ {n}}} { \ begin {array} {| c | } \ hline {\ text {Canal}} \\ p (y | x) \\\ hline \ end {array}} {\ xrightarrow [{\ mathrm {Recebido \ em cima da sequência}}] {Y ^ {n}} } {\ begin {array} {| c | } \ hline {\ text {Decodificador}} \\ g_ {n} \\\ hline \ end {array}} {\ xrightarrow [{\ mathrm {Estimado \ em cima da mensagem}}] {\ hat {W}}}}$

Uma mensagem W é transmitida através de um canal ruidoso usando funções de codificação e decodificação. Um codificador mapeia W em uma sequência predefinida de símbolos de canal de comprimento n . Em seu modelo mais básico, o canal distorce cada um desses símbolos independentemente dos outros. A saída do canal –a sequência recebida– é alimentada em um decodificador que mapeia a sequência em uma estimativa da mensagem. Nesta configuração, a probabilidade de erro é definida como:

${\ displaystyle P_ {e} = {\ text {Pr}} \ left \ {{\ hat {W}} \ neq W \ right \}.}$

Teorema (Shannon, 1948):

1. Para cada canal discreto sem memória, a capacidade do canal é definida em termos de informação mútua ,${\ displaystyle I (X; Y)}$

${\ displaystyle \ C = \ sup _ {p_ {X}} I (X; Y)}$

tem a seguinte propriedade. Para qualquer e , para grande o suficiente , existe um código de comprimento e taxa e um algoritmo de decodificação, de modo que a probabilidade máxima de erro de bloco seja .${\ displaystyle \ epsilon> 0}$${\ displaystyle R <C}$${\ displaystyle N}$${\ displaystyle N}$${\ displaystyle \ geq R}$${\ displaystyle \ leq \ epsilon}$

2. Se uma probabilidade de erro de bit for aceitável, taxas de até são alcançáveis, onde${\ displaystyle p_ {b}}$${\ displaystyle R (p_ {b})}$

${\ displaystyle R (p_ {b}) = {\ frac {C} {1-H_ {2} (p_ {b})}}.}$

e é a função de entropia binária${\ displaystyle H_ {2} (p_ {b})}$

${\ displaystyle H_ {2} (p_ {b}) = - \ left [p_ {b} \ log _ {2} {p_ {b}} + (1-p_ {b}) \ log _ {2} ( {1-p_ {b}}) \ direita]}$

3. Para qualquer um , taxas maiores que não são alcançáveis.${\ displaystyle p_ {b}}$${\ displaystyle R (p_ {b})}$

(MacKay (2003), p. 162; cf Gallager (1968), ch.5; Cover e Thomas (1991), p. 198; Shannon (1948) thm. 11)

Esboço da prova

Tal como acontece com os vários outros resultados importantes na teoria da informação, a prova do teorema da codificação do canal ruidoso inclui um resultado de realizabilidade e um resultado inverso correspondente. Esses dois componentes servem para limitar, neste caso, o conjunto de taxas possíveis nas quais alguém pode se comunicar através de um canal ruidoso, e a correspondência serve para mostrar que esses limites são estreitos.

Os esboços a seguir são apenas um conjunto de muitos estilos diferentes disponíveis para estudo em textos de teoria da informação.

Capacidade de realização para canais discretos sem memória

Esta prova particular de realizabilidade segue o estilo de provas que fazem uso da propriedade de equipartição assintótica (AEP). Outro estilo pode ser encontrado em textos de teoria da informação usando expoentes de erro .

Ambos os tipos de provas fazem uso de um argumento de codificação aleatório onde o livro de código usado através de um canal é construído aleatoriamente - isso serve para tornar a análise mais simples, enquanto ainda prova a existência de um código que satisfaça uma baixa probabilidade de erro desejada em qualquer taxa de dados abaixo do capacidade do canal .

Por um argumento relacionado ao AEP, dado um canal, strings de comprimento de símbolos de origem e strings de comprimento de saídas de canal , podemos definir um conjunto típico conjuntamente da seguinte maneira: ${\ displaystyle n}$${\ displaystyle X_ {1} ^ {n}}$${\ displaystyle n}$${\ displaystyle Y_ {1} ^ {n}}$

${\ displaystyle A _ {\ varepsilon} ^ {(n)} = \ {(x ^ {n}, y ^ {n}) \ in {\ mathcal {X}} ^ {n} \ times {\ mathcal {Y }} ^ {n}}$

${\ displaystyle 2 ^ {- n (H (X) + \ varepsilon)} \ leq p (X_ {1} ^ {n}) \ leq 2 ^ {- n (H (X) - \ varejpsilon)}}$

${\ displaystyle 2 ^ {- n (H (Y) + \ varepsilon)} \ leq p (Y_ {1} ^ {n}) \ leq 2 ^ {- n (H (Y) - \ varejpsilon)}}$

${\ displaystyle {2 ^ {- n (H (X, Y) + \ varepsilon)}} \ leq p (X_ {1} ^ {n}, Y_ {1} ^ {n}) \ leq 2 ^ {- n (H (X, Y) - \ varejpsilon)} \}}$

Dizemos que duas sequências e são conjuntamente típicas se estiverem no conjunto conjuntamente típico definido acima. ${\ displaystyle {X_ {1} ^ {n}}}$${\ displaystyle Y_ {1} ^ {n}}$

Passos

1. No estilo do argumento da codificação aleatória, geramos palavras-código aleatoriamente de comprimento n a partir de uma distribuição de probabilidade Q.${\ displaystyle 2 ^ {nR}}$
2. Este código é revelado ao remetente e ao destinatário. Também é assumido que se conhece a matriz de transição para o canal que está sendo usado.${\ displaystyle p (y | x)}$
3. Uma mensagem W é escolhida de acordo com a distribuição uniforme no conjunto de palavras-código. Ou seja ,.${\ displaystyle Pr (W = w) = 2 ^ {- nR}, w = 1,2, \ dots, 2 ^ {nR}}$
4. A mensagem W é enviada através do canal.
5. O receptor recebe uma sequência de acordo com ${\ displaystyle P (y ^ {n} | x ^ {n} (w)) = \ prod _ {i = 1} ^ {n} p (y_ {i} | x_ {i} (w))}$
6. Enviando essas palavras-código pelo canal, recebemos e decodificamos para alguma sequência de origem se houver exatamente 1 palavra-código que seja típica em conjunto com Y. Se não houver palavras-código comuns em conjunto, ou se houver mais de uma, um erro será declarado. Também ocorre um erro se uma palavra-código decodificada não corresponder à palavra-código original. Isso é chamado de decodificação de conjunto típica .${\ displaystyle Y_ {1} ^ {n}}$

A probabilidade de erro deste esquema é dividida em duas partes:

1. Primeiro, o erro pode ocorrer se nenhuma sequência X típica em conjunto for encontrada para uma sequência Y recebida
2. Em segundo lugar, o erro pode ocorrer se uma sequência X incorreta for conjuntamente típica com uma sequência Y recebida.

• Pela aleatoriedade da construção do código, podemos assumir que a probabilidade média de erro calculada sobre todos os códigos não depende do índice enviado. Assim, sem perda de generalidade, podemos assumir W = 1.
• A partir do AEP conjunto, sabemos que a probabilidade de que nenhum X típico em conjunto exista vai para 0 à medida que n aumenta. Podemos limitar essa probabilidade de erro por .${\ displaystyle \ varepsilon}$
• Também a partir do AEP conjunto, sabemos a probabilidade de que um particular e o resultante de W = 1 sejam conjuntamente típicos é .${\ displaystyle X_ {1} ^ {n} (i)}$${\ displaystyle Y_ {1} ^ {n}}$${\ displaystyle \ leq 2 ^ {- n (I (X; Y) -3 \ varejpsilon)}}$

Definir: ${\ displaystyle E_ {i} = \ {(X_ {1} ^ {n} (i), Y_ {1} ^ {n}) \ in A _ {\ varejpsilon} ^ {(n)} \}, i = 1,2, \ pontos, 2 ^ {nR}}$

como o evento em que a mensagem i é típica em conjunto com a sequência recebida quando a mensagem 1 é enviada.

${\ displaystyle {\ begin {align} P ({\ text {error}}) & {} = P ({\ text {error}} | W = 1) \ leq P (E_ {1} ^ {c}) + \ sum _ {i = 2} ^ {2 ^ {nR}} P (E_ {i}) \\ & {} \ leq P (E_ {1} ^ {c}) + (2 ^ {nR} - 1) 2 ^ {- n (I (X; Y) -3 \ varejpsilon)} \\ & {} \ leq \ varejpsilon +2 ^ {- n (I (X; Y) -R-3 \ varejpsilon)} . \ end {alinhado}}}$

Podemos observar que à medida que vai para o infinito, se para o canal, a probabilidade de erro irá para 0. ${\ displaystyle n}$${\ displaystyle R <I (X; Y)}$

Finalmente, dado que o livro de código médio é mostrado como "bom", sabemos que existe um livro de código cujo desempenho é melhor do que a média e, portanto, satisfaz nossa necessidade de comunicação de probabilidade de erro arbitrariamente baixa através do canal ruidoso.

Converso fraco para canais discretos sem memória

Suponha um código de palavras-código. Seja W desenhado uniformemente sobre este conjunto como um índice. Deixe e ser as palavras-código transmitidas e as palavras-código recebidas, respectivamente. ${\ displaystyle 2 ^ {nR}}$${\ displaystyle X ^ {n}}$${\ displaystyle Y ^ {n}}$

1. ${\ displaystyle nR = H (W) = H (W | Y ^ {n}) + I (W; Y ^ {n})}$usando identidades envolvendo entropia e informação mútua
2. ${\ displaystyle \ leq H (W | Y ^ {n}) + I (X ^ {n} (W); Y ^ {n})}$ uma vez que X é uma função de W
3. ${\ displaystyle \ leq 1 + P_ {e} ^ {(n)} nR + I (X ^ {n} (W); Y ^ {n})}$pelo uso da Desigualdade de Fano
4. ${\ displaystyle \ leq 1 + P_ {e} ^ {(n)} nR + nC}$ pelo fato de que a capacidade é maximizada de informação mútua.

O resultado dessas etapas é isso . À medida que o comprimento do bloco vai ao infinito, obtemos que é limitado a 10 se R for maior que C - podemos obter taxas de erro arbitrariamente baixas apenas se R for menor que C. ${\ displaystyle P_ {e} ^ {(n)} \ geq 1 - {\ frac {1} {nR}} - {\ frac {C} {R}}}$${\ displaystyle n}$${\ displaystyle P_ {e} ^ {(n)}}$

Converso forte para canais discretos sem memória

Um forte teorema inverso, provado por Wolfowitz em 1957, afirma que,

${\ displaystyle P_ {e} \ geq 1 - {\ frac {4A} {n (RC) ^ {2}}} - e ^ {- {\ frac {n (RC)} {2}}}}$

para alguma constante positiva finita . Enquanto o inverso fraco afirma que a probabilidade de erro é limitada a zero conforme vai para o infinito, o inverso forte afirma que o erro vai a 1. Portanto, é um limite agudo entre comunicação perfeitamente confiável e completamente não confiável. ${\ displaystyle A}$${\ displaystyle n}$${\ displaystyle C}$

Teorema de codificação de canal para canais sem memória não estacionários

Assumimos que o canal não tem memória, mas suas probabilidades de transição mudam com o tempo, de uma forma conhecida tanto no transmissor quanto no receptor.

Então, a capacidade do canal é dada por

${\ displaystyle C = \ lim \ inf \ max _ {p ^ {(X_ {1})}, p ^ {(X_ {2})}, ...} {\ frac {1} {n}} \ soma _ {i = 1} ^ {n} I (X_ {i}; Y_ {i}).}$

O máximo é atingido na capacidade de atingir distribuições para cada canal respectivo. Ou seja, onde está a capacidade do i ésimo canal. ${\ displaystyle C = \ lim \ inf {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} C_ {i}}$${\ displaystyle C_ {i}}$

Esboço da prova

A prova é executada quase da mesma maneira que a do teorema da codificação de canal. A capacidade de realização decorre da codificação aleatória com cada símbolo escolhido aleatoriamente da distribuição de alcance de capacidade para aquele canal específico. Argumentos de tipicidade usam a definição de conjuntos típicos para fontes não estacionárias definidas no artigo de propriedade de equipartição assintótica .

O tecnicismo de lim inf entra em jogo quando não converge. ${\ displaystyle {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} C_ {i}}$

Taxa de codificação de canal no regime de comprimento de bloco finito

A teoria da informação de comprimento de bloco finito investiga a taxa máxima de codificação de canal alcançável em um determinado comprimento de bloco e probabilidade de erro no regime de comprimento de bloco finito (regime não assintótico). A taxa de codificação de canal máxima alcançável com dada probabilidade de erro de bloco e comprimento de bloco (para canais binários de ruído gaussiano branco aditivo (AWGN), com comprimentos de bloco curtos), aproximada por Polyanskiy , Poor e Verdú (PPV) em 2010, é dada por ${\ displaystyle \ left ({\ bar {R}} \ right)}$${\ displaystyle \ left (\ epsilon \ right)}$${\ displaystyle \ left (n \ right)}$

${\ displaystyle {\ bar {R}} \ approx C - {\ sqrt {\ frac {V} {n}}} Q ^ {- 1} \ left (\ epsilon \ right)}$

onde é o inverso da função de distribuição cumulativa gaussiana complementar , é a capacidade do canal e é uma característica do canal referida como dispersão do canal. ${\ displaystyle Q ^ {- 1}}$ ${\ displaystyle C}$${\ displaystyle V}$

Veja também

• Propriedade de equipartição assintótica (AEP)
• A desigualdade de Fano
• Teoria de taxa de distorção
• Teorema de codificação de fonte de Shannon
• Teorema de Shannon-Hartley
• Código turbo

Notas

Referências

• Cover TM , Thomas JA, Elements of Information Theory , John Wiley & Sons , 1991. ISBN  0-471-06259-6
• Fano, RA , Transmissão de informações; uma teoria estatística das comunicações , MIT Press , 1961. ISBN  0-262-06001-9
• Feinstein, Amiel , "Um novo teorema básico da teoria da informação", IEEE Transactions on Information Theory , 4 (4): 2-22, 1954.
• MacKay, David JC , Information Theory, Inference, and Learning Algorithms , Cambridge University Press , 2003. ISBN  0-521-64298-1 [online grátis]
• Shannon, CE , A Mathematical Theory of Communication . The Bell System Technical Journal 27,3: 379–423, 1948.
• Shannon, CE , A Mathematical Theory of Communication Urbana, IL: University of Illinois Press, 1948 (reimpresso em 1998).
• Wolfowitz, J. , " A codificação de mensagens sujeitas a erros fortuitos ", Illinois J. Math. , 1: 591–606, 1957.

links externos

• Sobre a lei de Shannon e Shannon
• Teorema da codificação do canal barulhento de Shannon