“Teoria dell'informazione e della codifica. Teorema diretto di Shannon per una sorgente di forma generale

Per utilizzo efficace canale (aumentando il fattore di carico λ→1), è necessario coordinarlo con la fonte di informazione in ingresso. Tale adattamento è possibile sia per i canali senza interferenza che con interferenza, in base ai teoremi di codifica dei canali proposti da Shannon.

Teorema di codifica per un canale privo di interferenze.

Se la sorgente del messaggio ha una capacità [bit/sec] e il canale di comunicazione ha una capacità [bit/sec], è possibile codificare il messaggio in modo tale da trasmettere informazioni sul canale di comunicazione a una velocità media, arbitrariamente vicino al valore, ma non superarlo.

Shannon propose anche un metodo per tale codifica, chiamato codifica ottimale. L'idea di tale codifica è stata successivamente sviluppata nei lavori di Fano e Huffman. Attualmente tali codici sono ampiamente utilizzati nella pratica (codificazione efficiente e ottimale).

Teorema di codifica diretta di Shannon per un canale rumoroso.

Per qualsiasi prestazione della sorgente del messaggio [bit/sec] inferiore al throughput [bit/sec], esiste un metodo di codifica che consente la trasmissione di tutte le informazioni create dalla sorgente del messaggio con una probabilità di errore arbitrariamente piccola ε.

Teorema della codifica inversa per un canale rumoroso.

Non esiste un metodo di codifica che consenta di trasmettere le informazioni con una certa probabilità di errore se la prestazione della fonte del messaggio è maggiore larghezza di banda canale.

La dimostrazione del teorema di codifica per un canale con rumore è matematicamente piuttosto lunga, quindi ci limiteremo ad una trattazione generale degli aspetti fisici della stessa. applicazione pratica:

1. Il teorema stabilisce limite teorico possibile efficienza del sistema con trasmissione affidabile delle informazioni. Dal teorema consegue che l'interferenza nel canale non impone restrizioni sulla precisione della trasmissione. Le restrizioni vengono imposte solo sulla velocità di trasmissione alla quale è possibile ottenere un'affidabilità di trasmissione arbitrariamente elevata.

Allo stesso tempo, l'affidabilità canale discretoè solitamente stimato dal valore della probabilità di ricezione errata di un simbolo. Minore è la probabilità di errore, maggiore è l'affidabilità del canale. L'affidabilità, a sua volta, caratterizza l'immunità al rumore sistema informativo.

La velocità di trasferimento delle informazioni caratterizza l'efficienza del sistema.

2. Il teorema non affronta la questione dei modi per costruire codici che assicurino la trasmissione ideale specificata. Dopo aver dimostrato la possibilità fondamentale di tale codifica, ha mobilitato gli sforzi degli scienziati per sviluppare codici specifici.

3. A qualsiasi velocità finita di trasmissione delle informazioni, fino al throughput, una probabilità di errore arbitrariamente piccola si ottiene solo con un aumento illimitato della durata delle sequenze di caratteri codificate. Pertanto una trasmissione senza errori in presenza di interferenze è possibile solo teoricamente. Garantire la trasmissione di informazioni con una probabilità di errore molto bassa e con un'efficienza piuttosto elevata è possibile durante la codifica di sequenze di caratteri estremamente lunghe.

Teorema diretto di Shannon per la sorgente vista generale Da non confondere con gli altri teoremi di Shannon.

Teoremi di Shannon per una sorgente generale descrivere le possibilità di codificare una fonte generale utilizzando codici separabili. In altre parole, vengono descritte le massime capacità di codifica senza perdite ottenibili.

Teorema diretto

Quando applicato alla codifica lettera per lettera, il teorema diretto può essere formulato come segue:

Per dimostrare il teorema si esaminano le caratteristiche del codice Shannon-Fano. Questo codice soddisfa le condizioni del teorema e ha le proprietà indicate.

Teorema inverso

Il teorema inverso limita il rapporto di compressione massimo ottenibile con la codifica senza perdita di dati. Quando applicato alla codifica lettera per lettera, descrive la limitazione sulla lunghezza media parola in codice per qualsiasi codice separabile.

Per qualsiasi codice separabile con lunghezze w 1 ,w 2 ,...,w K la lunghezza media del messaggio è maggiore o uguale all'entropia della sorgente U, normalizzato al logaritmo binario del numero di lettere D nell'alfabeto del codificatore:

Letteratura

• Gabidulin, E. M., Pilipchuk, N. I.§3.4 Teoremi di Shannon per la sorgente // Lezioni frontali sulla teoria dell'informazione. - M.: MIPT, 2007. - pp. 49-52. - 214 pag. - ISBN 5-7417-0197-3

Fondazione Wikimedia. 2010.

Scopri cos'è il "teorema diretto di Shannon per una fonte di forma generale" in altri dizionari:

Da non confondere con gli altri teoremi di Shannon. I teoremi di Shannon per una fonte generale descrivono le possibilità di codificare una fonte generale utilizzando codici separabili. In altre parole si descrivono le massime possibilità realizzabili... ... Wikipedia

Wikipedia ha articoli su altre persone con questo cognome, vedi Shannon. Claude Elwood Shannon Claude Elwood Shannon ... Wikipedia

Claude Elwood Shannon (nato il 30 aprile 1916, Petoskey, Michigan, Michigan, USA, morto il 24 febbraio 2001, Medford, Massachusetts, USA) matematico e ingegnere elettrico americano, uno dei creatori della teoria matematica... ... Wikipedia

Claude Elwood Shannon (nato il 30 aprile 1916, Petoskey, Michigan, Michigan, USA, morto il 24 febbraio 2001, Medford, Massachusetts, USA) matematico e ingegnere elettrico americano, uno dei creatori della teoria matematica... ... Wikipedia

- (Inglese Claude Elwood Shannon; nato il 30 aprile 1916, Petoskey, Michigan, Michigan, USA, morto il 24 febbraio 2001, Medford, Massachusetts, USA) Matematico e ingegnere elettrico americano, uno dei creatori della teoria matematica dell'informazione, in . .. ...Wikipedia

Claude Elwood Shannon (nato il 30 aprile 1916, Petoskey, Michigan, Michigan, USA, morto il 24 febbraio 2001, Medford, Massachusetts, USA) matematico e ingegnere elettrico americano, uno dei creatori della teoria matematica... ... Wikipedia

Claude Elwood Shannon (nato il 30 aprile 1916, Petoskey, Michigan, Michigan, USA, morto il 24 febbraio 2001, Medford, Massachusetts, USA) matematico e ingegnere elettrico americano, uno dei creatori della teoria matematica... ... Wikipedia

Claude Elwood Shannon (nato il 30 aprile 1916, Petoskey, Michigan, Michigan, USA, morto il 24 febbraio 2001, Medford, Massachusetts, USA) matematico e ingegnere elettrico americano, uno dei creatori della teoria matematica... ... Wikipedia

Programma del corso

"Teoria dell'informazione e dei codici"

Le lezioni si tengono al 4° anno, VII semestre,

51 ore, docente professore associato

Il concetto di informazione, entropia. Sistemi di comunicazione. Fonti discrete. Descrizione della fonte utilizzando processo casuale. Indipendenza statistica. Fonti Markov. Ergodicità. Ergodicità della sorgente Bernoulli.

Derivazione della formula dell'entropia (secondo Fadeev). L'informazione reciproca e le sue proprietà. Proprietà dell'entropia. Teorema su valore massimo entropia. Entropia per unità di tempo della sorgente del messaggio.

Il problema di codificare una sorgente discreta con codici uguale lunghezza. Velocità di codifica. Insiemi ad alta probabilità. Teoremi diretti e inversi per codificare una sorgente discreta con codici di uguale lunghezza.

Il problema di codificare una sorgente con codici di lunghezza diversa. Costo della codifica. Codici inequivocabilmente decifrabili. Codici prefisso. Codificazione lettera per lettera. Condizione necessaria e sufficiente per la decifrabilità univoca di un codice. Codici completi. Teorema per la codifica di una sorgente discreta con codici di lunghezza diversa. Algoritmi per la costruzione di codici ottimi (Fano, Shannon, Huffman). Costruzione di un codice ottimo binario con distribuzione eguale delle probabilità di input. L'applicazione della teoria dell'informazione porta a dimostrare i limiti inferiore e superiore per la complessità dell'implementazione Funzioni booleane in alcune classi di sistemi di controllo. Un metodo per costruire un codice ottimale a condizione che la distribuzione di probabilità delle lettere di origine sia sconosciuta. Teorema di Markov sulla decifrabilità unica di un codice. Algoritmi adattativi per la compressione dell'informazione.

Canale discreto senza memoria. Binario canale simmetrico. La velocità di trasmissione delle informazioni nel canale. Capacità del canale. Canale espanso e sua capacità. Modelli decisivi e raggruppamenti di osservazioni. Possibilità di trasmissione errata delle informazioni. Disuguaglianza di Feinstein. Teorema diretto per la codifica dei canali senza memoria. Disuguaglianza di Fano. Teorema dell'elaborazione dell'informazione. Inversione del teorema della codifica.

Teoria della codifica resistente al rumore. Criterio di massima verosimiglianza. Distanza del codice. Codici di parità. Generativo e controllare le matrici. Sindrome. Algoritmo di decodifica per codici di controllo di parità. Codici lineari e il loro algoritmo di decodifica. Hamming legato. Codice di Hamming. Codici ciclici. Codifica e decodifica di codici ciclici.

LETTERATURA

1. Gallagher R. Teoria dell'informazione e connessione affidabile., M., Sov. Radio, 1979.

2. Krichevsky E. Lezioni su teoria e informazione, Novosibirsk, NSU, 1966.

3. Kolesnik V., Poltyrev G. Corso di teoria dell'informazione, Nauka, 1982.

4. Fainstein A. Fondamenti di teoria dell'informazione, M., IL, 1960.

5. Peterson V., Weldon F. Codici di correzione degli errori, M., Mir, 1976.

6. Teoria algebrica dei codici di Berlekamp, ​​M., Mir, 1971.

La capacità informativa dei canali discreti (4.4) e la capacità dei canali continui (4.7) caratterizza le loro massime capacità come mezzo di trasmissione delle informazioni. Essi sono rivelati nei teoremi fondamentali della teoria dell'informazione, noti come teoremi fondamentali della codifica di Shannon. In relazione ad un canale discreto si legge:

Teorema 4.4.1. (Teorema della codifica diretta per DKBP.) Per un canale discreto senza memoria a velocità di codice R, al di sotto della capacità informativa, esiste sempre un codice per il quale la probabilità media di errore tende a zero all'aumentare della lunghezza della parola del codice.

Nel caso di un canale continuo, è formulato come

Teorema 4.4.2. (Teorema della codifica diretta per il canale AWGN). Su un canale AWGN con larghezza di banda illimitata, le informazioni possono essere trasmesse con una probabilità di errore arbitrariamente bassa se la velocità di trasmissione è inferiore alla larghezza di banda.

Il teorema inverso afferma:

Teorema 4.4.3. Alla velocità di trasmissione
, maggiore capacità del canale di comunicazione C, nessun codice fornirà una probabilità arbitrariamente piccola di errore di decodifica, ad es. trasmissione del messaggio assolutamente affidabile.

Va notato che se il teorema inverso viene dimostrato per un modello arbitrario di canale di comunicazione, quello diretto viene dimostrato solo per tipi specifici di canali.

I risultati dei teoremi di codifica per un canale rumoroso sono alquanto inaspettati. A prima vista, infatti, sembra che la riduzione della probabilità di errori nella trasmissione dei messaggi richieda una corrispondente riduzione della velocità di trasmissione e che quest'ultima debba tendere a zero insieme alla probabilità di errori. Questa conclusione, in particolare, deriva dal considerare la ritrasmissione multipla di simboli su un canale come un modo per ridurre la probabilità di errori nella trasmissione del messaggio. In questo caso, in presenza di interferenze nel canale di comunicazione, è possibile garantire che la probabilità di errore nella trasmissione del messaggio tende a zero solo se la velocità di trasmissione tende a zero.

Tuttavia, il teorema di codifica mostra che in linea di principio è possibile trasmettere ad una velocità arbitrariamente vicina a C, ottenendo una probabilità di errore arbitrariamente piccola. Sfortunatamente i teoremi, pur indicando l’esistenza fondamentale di un codice resistente agli errori, non forniscono una ricetta per trovarlo. Possiamo solo notare che per questo è necessario utilizzare codici lunghi. Inoltre, man mano che la velocità di trasmissione si avvicina al throughput e diminuisce la probabilità di errori, il codice diventa più complesso a causa dell'aumento della lunghezza dei blocchi, il che porta ad una forte complicazione dei dispositivi di codifica e decodifica, nonché ad un ritardo nella l'output delle informazioni durante la decodifica. I metodi di codifica attualmente utilizzati, che verranno discussi più avanti, non realizzano le potenziali capacità del sistema di comunicazione. L'unica eccezione sono i codici turbo aperti di recente.

1Questo risultato è valido per qualsiasi canale simmetrico.

Codifica delle informazioni

Concetti basilari

I teoremi di Shannon sulla codifica dei messaggi sono stati menzionati sopra. È intuitivamente chiaro che la codifica è l'operazione di conversione delle informazioni nella forma richiesta per la successiva elaborazione (trasmissione su un canale di comunicazione, archiviazione in memoria sistema informatico, utilizzo per il processo decisionale, ecc.). È anche chiaro che quando si costruisce un sistema informativo è impossibile fare a meno della codifica: qualsiasi presentazione di informazioni implica l'uso di qualche tipo di codice. Pertanto, analizzeremo ulteriormente in dettaglio base teorica codifica delle informazioni.

Permettere UN– alfabeto arbitrario. Elementi dell'alfabeto UN sono chiamate lettere (o simboli), e le sequenze finite composte da lettere sono chiamate parole UN. Si ritiene che in ogni alfabeto ci sia una parola vuota che non contiene lettere.

Parola α 1 è chiamato l'inizio (prefisso) di una parola α , se la parola esiste α 2, tale che α = α 1 α 2; allo stesso tempo la parola α 1 è chiamato l'inizio proprio di una parola α , Se α 2 non è una parola vuota. La lunghezza della parola è il numero di lettere nella parola (una parola vuota ha lunghezza 0). Documentazione α 1 α 2 indica la connessione (concatenazione) di parole α 1 e α 2. Parola α 2 è chiamata la desinenza (suffisso) di una parola α , se la parola esiste α 1, tale che α = α 1 α 2; allo stesso tempo la parola α 2 è chiamata la desinenza propria di una parola α , Se α 1 non è una parola vuota. Una parola vuota è per definizione considerata l'inizio e la fine di qualsiasi parola α .

Considera l'alfabeto B = {0, 1, …, D– 1), dove D≥ 2 e un insieme arbitrario C. Visualizzazione arbitraria di un insieme C in molte parole dell'alfabeto B chiamato D-ary set di codifica C(A D= 2 la codifica sarà binaria). La mappatura inversa è chiamata decodifica. Diamo esempi di codifiche.

1. Codifica dell'insieme dei numeri naturali, in cui il numero N= 0 corrisponde alla parola e(0) = 0 e il numero N ≥ 1 parola binaria

e(N) = B 1 B 2 … b l (N)

la lunghezza più piccola che soddisfa la condizione

E' ovvio B 1 = 1, 2l (N) – 1 ≤ N < 2l (N) e quindi

l(N) = + 1 = ]log( N + 1)[,

Dove [ X] E ] X[ denota il numero intero più grande che non supera X e il più piccolo intero maggiore di X. Parola e(N) è chiamata notazione binaria di un numero N, e questa codifica è la rappresentazione dei numeri in sistema binario Resa dei conti. Questa codificaè uno a uno perché quando N 1 ≠ N 2 parole e(N 1) e e(N 2) diverso. La Tabella 5.1 mostra la rappresentazione dei primi 16 numeri naturali nel sistema numerico binario.

Tabella 5.1

Codifica e(N)

N	e(N)	N	e(N)	N	e(N)	N	e(N)

2. Codifica del primo 2 K numeri naturali, per cui ciascun numero N (0 ≤ N < 2K) corrisponde alla parola

e k(N) = 0K – l (N) e(N),

dove voce 0 K – l (N) denota una parola composta da K – l(N) zeri, e(N) – rappresentazione di un numero N nel sistema di numeri binari discusso sopra. Questa codifica è per i primi 16 numeri naturali ( K= 4) è riportato nella tabella 5.2.

Tabella 5.2

Codifica e k(N)

N	e k(N)	N	e k(N)	N	e k(N)	N	e k(N)

Permettere UN = {un io, io= 1, 2, ...) – un alfabeto finito o numerabile, le cui lettere sono numerate numeri naturali. In questo caso, la codifica delle lettere dell'alfabeto UN può essere specificato in sequenza D-parole letterali V = {v i, io= 1, 2, …), dove v i c'è l'immagine di una lettera un io. Tali sequenze di parole (dal set V) sono detti codici (dell'alfabeto UN). Se viene fornito il codice V alfabeto UN, quindi la codifica delle parole, in cui ogni parola un io 1 un io 2 …e non lo so corrisponde alla parola v i 1 v i 2 …va bene, è chiamata codifica lettera per lettera.

Quando si passa dalla codifica uno a uno delle lettere dell'alfabeto alla codifica lettera per lettera delle parole dell'alfabeto, la proprietà del carattere uno a uno potrebbe non essere preservata. Ad esempio, la codifica e(N) non salva questa proprietà e codifica e k(N) lo salva. La proprietà uno-a-uno è preservata da codici separabili. Codice V = {v i, io= 1, 2, …) è detto separabile se da ciascuna uguaglianza della forma

v i 1 v i 2 …va bene = vj 1 vj 2 …vjl

segue quello l = K E v i 1 = vj 1 , v i 2 = vj 2 , … , va bene = vjl. I codici separabili sono anche detti codici univocamente decodificabili.

I codici prefisso appartengono alla classe dei codici separabili. Codice V = {v i, io= 1, 2, …) è chiamato prefisso se non è una parola vk non è l'inizio (prefisso) di alcuna parola v l, l ≠ K. Se ogni parola di un codice prefisso viene sostituita dal suo inizio più piccolo, che non è l'inizio di altre parole in codice, anche il codice risultante sarà un prefisso. Questa operazione è chiamata troncamento del codice prefisso.

Per codice arbitrario V, consiste in parole diverse, puoi creare un albero del codice. Questo è un grafico diretto che non contiene cicli, in cui il vertice β 1 collegato in alto β 2 bordo diretto da β 1 a β 2 se e solo se β 2 = β 1 B, Dove B Î B = {0, 1, …, D – 1}, D≥ 2. Per i codici prefisso (e solo per essi), l'insieme delle parole in codice coincide con l'insieme dei vertici finali (vertici da cui non si originano spigoli) albero dei codici.

Teoremi di base della codifica

Le proprietà dei codici utili per la loro applicazione pratica sono determinate dai teoremi fondamentali della codifica.

Teorema 5.1. La disuguaglianza di Kraft. Per l'esistenza di un codice univocamente decodificabile (separabile) contenente N parole in codice nell'insieme (0, 1, D– 1) con lunghezze N 1 , N 2 , …, nN, è necessario e sufficiente affinché la disuguaglianza sussista

Prova. Immaginiamo di avere un albero di codici per un codice prefisso. La radice dell'albero del codice forma il livello 0, i vertici associati alla radice formano il livello 1, ecc. Possibile numero di vertici per K-esimo livello che denotiamo come Non so. Ogni picco K il livello viene generato esattamente Dn – K picchi N-esimo livello.

N 1 ≤ N 2 ≤…≤ nN = N.

Ovviamente, la parola in codice length K vieta esattamente Dn – K eventuali vertici finali (vertici dell'ultimo livello). Quindi tutte le parole in codice del codice prefisso vietano i vertici finali. Perché numero totale i vertici finali sono uguali Dn, allora la disuguaglianza è vera

,

da cui ne consegue che

Pertanto, la disuguaglianza di Kraft è dimostrata.

Come risultato della dimostrazione del Teorema 5.1, si conclude che esistono almeno codici prefisso che sono codici decodificabili in modo univoco con lunghezze di parola di codice N 1 , N 2 , …, nN, soddisfacendo la disuguaglianza di Kraft. Il seguente teorema, chiamato enunciato di McMillan, è generalizzabile questa conclusione per tutti i codici univocamente decodificabili.

Teorema 5.2. Disuguaglianza di McMillan. Ogni codice univocamente decodificabile soddisfa la disuguaglianza di Kraft.

Prova. Eleviamo la somma a una potenza l:

. (5.1)

Permettere A k– numero di combinazioni contenenti l parole in codice con lunghezza totale K. Allora l'espressione (6.1) può essere rappresentata come

,

Dove l massimo – lunghezza massima messaggi contenenti l parole in codice. Se il codice è decodificabile in modo univoco, tutte le sequenze da l parole in codice di lunghezza totale K sono diversi. Poiché c'è solo Non so sequenze possibili, quindi A k ≤ Non so poi

Perché lè il numero di parole in codice indipendenti utilizzate per costruire tutte le possibili sequenze di lunghezza non superiore l massimo Ecco perché l ≤ l massimo e . E da ciò ne consegue che

Poiché il ragionamento di cui sopra è valido per ogni codice univocamente decodificabile, e non solo per i codici prefisso, l’affermazione di McMillan è dimostrata.

I seguenti teoremi mettono in relazione l'entropia di una sorgente di messaggio e la lunghezza media di una parola in codice.

Teorema 5.3. Teorema della codifica della sorgente I. Per qualsiasi sorgente discreta senza memoria X con alfabeto finito ed entropia H(X) esiste D-ichny codice prefisso, in cui la lunghezza media della parola in codice soddisfa la disuguaglianza

. (5.2)

Prova. Innanzitutto chiariamolo fonte discreta senza memoria, è descritto da un modello che non tiene conto delle connessioni tra i simboli dei messaggi. Ora dimostriamo il lato sinistro della disuguaglianza (6.2):

Per fare ciò usiamo la definizione di entropia e la disuguaglianza di Kraft:

Per dimostrare il lato destro della disuguaglianza (6.2), riscriviamo la disuguaglianza di Kraft nella forma seguente:

.

Quindi scegliamo per ogni termine l'intero più piccolo no io, al quale

Poiché la disuguaglianza di Kraft rimane la stessa con questa scelta, possiamo costruire il codice del prefisso corrispondente. Perché no ioè l'intero più piccolo, quindi for no io– 1 è giusto

Pertanto il teorema I della codifica sorgente è dimostrato. Determina che la lunghezza media di una parola in codice non può essere inferiore all'entropia della fonte del messaggio. Si noti che la dimostrazione del teorema utilizza la stessa notazione utilizzata per considerare la disuguaglianza di Kraft.

Teorema 5.4. Teorema della codifica della sorgente II. Per la lunghezza del blocco l esiste D-ary codice prefisso in cui la lunghezza media di una parola in codice per carattere soddisfa la disuguaglianza

,

Dove .

Prova. Qui, blocchi di caratteri e H(X 1 , X 2 , …, X L) è l'entropia della sorgente del messaggio per blocco di l caratteri. Per dimostrare il teorema, puoi utilizzare il teorema della codifica sorgente I:

Inoltre, poiché la lunghezza minima ottenibile di una parola in codice per simbolo è il valore , allora quando D= 2 La ridondanza del codice può essere determinata dalla formula .

1 | |