Teorema di Shannon diretto per una sorgente generale. Teoremi di codifica di base

Codifica delle informazioni

Concetti basilari

I teoremi di codifica dei messaggi di Shannon sono stati menzionati sopra. È intuitivamente chiaro che la codifica è un'operazione di conversione delle informazioni in una forma necessaria per la successiva elaborazione (trasmissione tramite un canale di comunicazione, memorizzazione nella memoria di un sistema informatico, utilizzo per il processo decisionale, ecc.). È anche chiaro che quando si costruisce un qualsiasi sistema informativo è impossibile fare a meno della codifica: qualsiasi rappresentazione dell'informazione implica l'uso di alcuni codici. Pertanto, analizzeremo ulteriormente in dettaglio i fondamenti teorici della codifica dell'informazione.

Permettere UN- alfabeto arbitrario. Elementi dell'alfabeto UN sono chiamate lettere (o simboli), e le sequenze finite composte da lettere sono chiamate parole in UN... In questo caso, si considera che in qualsiasi alfabeto ci sia una parola vuota che non contiene lettere.

Parola α 1 è chiamato l'inizio (prefisso) di una parola α se c'è una parola α 2, tale che α = α 1 α 2; mentre la parola α 1 è chiamato l'inizio proprio della parola α , Se α 2 non è una parola vuota. La lunghezza della parola è il numero di lettere nella parola (una parola vuota ha una lunghezza di 0). Registrazione α 1 α 2 denota la connessione (concatenazione) di parole α 1 e α 2. Parola α 2 è chiamato la desinenza (suffisso) della parola α se c'è una parola α 1 tale che α = α 1 α 2; mentre la parola α 2 chiama la fine della propria 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 dell'insieme C in una varietà di parole dell'alfabeto B sono chiamati D-codificando il set C(in D= 2 la codifica sarà binaria). La mappatura inversa è chiamata decodifica. Ecco alcuni esempi di codifiche.

1. Codifica di un insieme di 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ù breve che soddisfa la condizione

È ovvio che B 1 = 1, 2io (n) – 1 ≤ n < 2io (n) e quindi

io(n) = + 1 =] registro ( n + 1)[,

dove [ X] e ] X[indica, rispettivamente, l'intero più grande non eccedente X, e il più piccolo intero maggiore di X... Parola e(n) è detta notazione binaria del numero n, e questa codifica è una rappresentazione di numeri in un sistema di numeri binari. Questa codifica è uno a uno, poiché per n 1 ≠ n 2 parole e(n 1) e e(n 2) sono diversi. La tabella 5.1 mostra la rappresentazione dei primi 16 numeri naturali nel sistema binario.

Tabella 5.1

codifica e(n)

n	e(n)	n	e(n)	n	e(n)	n	e(n)

2. Codifica dei primi 2 K numeri naturali, per i quali ogni numero n (0 ≤ n < 2K) la parola

e k(n) = 0K – io (n) e(n),

dove entrata 0 K – io (n) denota una parola composta da K – io(n) zeri, e(n) - rappresentazione numerica n nel sistema numerico binario 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 con numeri naturali. In questo caso, codificare le lettere dell'alfabeto UN può essere impostato in sequenza D-parole personali V = {v io, io= 1, 2, ...), dove v io c'è l'immagine di una lettera un io... Tali sequenze di parole (dall'insieme V) sono chiamati codici (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 …un ik corrisponde alla parola v io 1 v io 2 …v iki si chiama codifica lettera per lettera.

Nel passaggio dalla codifica uno a uno delle lettere dell'alfabeto alla codifica lettera per lettera delle parole dell'alfabeto, la proprietà dell'uno a uno potrebbe non essere preservata. Ad esempio la codifica e(n) non conserva questa proprietà, ma la codifica e k(n) lo salva. I codici separabili mantengono la proprietà uno a uno. Il codice V = {v io, io= 1, 2, ...) si dice separabile se da ciascuna uguaglianza della forma

v io 1 v io 2 …v iki = v j 1 v j 2 …v jl

segue che io = K e v io 1 = v j 1 , v io 2 = v j 2 , … , v iki = v jl... I codici separabili sono indicati anche come codici decodificati in modo univoco.

I codici prefisso appartengono alla classe dei codici separabili. Il codice V = {v io, io= 1, 2, ...) si chiama prefisso se nessuna parola v k non è l'inizio (prefisso) di nessuna parola v l, io ≠ K... Se ogni parola del codice del prefisso viene sostituita dal suo inizio più piccolo, che non è l'inizio di altre parole del codice, anche il codice risultante avrà un prefisso. Questa operazione è denominata troncamento del prefisso.

Per codice arbitrario V composto da parole diverse, puoi costruire un albero del codice. È un grafo orientato che non contiene cicli, in cui il vertice β 1 connesso al vertice β 2 con un 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 del codice coincide con l'insieme dei vertici terminali (vertici da cui non derivano spigoli) dell'albero del codice.

Teoremi di codifica di base

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

Teorema 5.1. La disuguaglianza del mestiere. Per l'esistenza di un codice decodificato in modo univoco (separabile) contenente n parole in codice nel set (0, 1, D- 1) con lunghezze n 1 , n 2 , …, n N, è necessario e sufficiente per la disuguaglianza

Prova. Immagina di avere un albero del codice per un codice prefisso. La radice dell'albero del codice è di livello 0, i nodi associati alla radice sono di livello 1 e così via. Possibile numero di vertici per K-esimo livello è indicato come D k... ogni picco K-esimo livello genera esattamente D n – K picchi n-esimo livello.

n 1 ≤ n 2 ≤…≤ n N = n.

Ovviamente, il codice di lunghezza K proibisce esattamente D n – K eventuali picchi finali (picchi dell'ultimo livello). Quindi tutte le parole del codice del prefisso vietano i vertici finali. Poiché il numero totale di vertici finali è D n, quindi la disuguaglianza

,

da cui segue che

Quindi, la disuguaglianza di Kraft è dimostrata.

Come risultato della dimostrazione del Teorema 5.1, si conclude che ci sono almeno codici prefisso che sono codici decodificabili in modo univoco con le lunghezze delle parole del codice n 1 , n 2 , …, n N soddisfare la disuguaglianza di Kraft. Il seguente teorema, chiamato affermazione di McMillan, generalizza questa conclusione a tutti i codici decodificati in modo univoco.

Teorema 5.2. Disuguaglianza di McMillan. Ogni codice decodificato in modo univoco soddisfa la disuguaglianza Craft.

Prova. Alziamo la somma alla potenza l:

. (5.1)

Permettere un k- il numero di combinazioni che contengono l parole in codice con lunghezza totale K... Allora l'espressione (6.1) può essere rappresentata come

,

dove l max - la lunghezza massima del messaggio contenente l parole in codice. Se il codice è decodificato in modo univoco, allora tutte le sequenze da l codici di lunghezza totale K sono diversi. Visto che c'è tutto D k possibili sequenze, allora un k ≤ D k poi

Perché lÈ il numero di codici indipendenti utilizzati per costruire tutte le possibili sequenze di lunghezza non superiore a l massimo Così l ≤ l max e ... E da ciò segue che

Poiché il ragionamento di cui sopra è valido per ogni codice decodificato in modo univoco, 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 del codice sorgente I. Per qualsiasi sorgente discreta senza memoria X con alfabeto finito ed entropia h(X) esiste D-ary prefisso codice in cui la lunghezza media del codeword soddisfa la disuguaglianza

. (5.2)

Prova. Prima di tutto, chiariamo che una sorgente discreta senza memoria è descritta da un modello che non tiene conto delle connessioni tra i simboli del messaggio. Dimostriamo ora il membro sinistro della disuguaglianza (6.2):

Per questo, usiamo la definizione di entropia e la disuguaglianza di Kraft:

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

.

Quindi, per ogni termine, scegliamo il più piccolo intero n io al quale

Poiché la disuguaglianza di Kraft è preservata per questa scelta, è possibile costruire il codice del prefisso corrispondente. Perché n ioÈ il più piccolo intero, quindi per n io- 1 è vero

Pertanto, il teorema I di codificazione della sorgente è dimostrato. Determina che la lunghezza media di una parola di codice non può essere inferiore all'entropia della sorgente del messaggio. Si noti che nella dimostrazione del teorema abbiamo usato la stessa notazione della considerazione della disuguaglianza di Kraft.

Teorema 5.4. Teorema del codice sorgente II. Per la lunghezza del blocco l esiste D-ary codice del prefisso in cui la lunghezza media del codeword 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 da l caratteri. Per dimostrare il teorema, puoi usare il teorema di codifica sorgente I:

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

1 | |

Programma del corso

"Teoria dell'informazione e dei codici"

Le lezioni si tengono nel 4° anno, VII-semestre,

51 ore, professore assistente

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

Derivazione della formula dell'entropia (secondo Fadeev). Informazione reciproca e sue proprietà. Proprietà di entropia. Il teorema sul valore massimo dell'entropia. Entropia per unità di tempo della sorgente del messaggio.

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

Il problema di codificare una sorgente con codici di lunghezza disuguale. Costo di codifica. Codici decifrati in modo univoco. Codici prefisso. Codifica lettera per lettera. Condizione necessaria e sufficiente per la decodifica univoca del codice. Codici completi. Un teorema per codificare una sorgente discreta con codici di lunghezza diversa. Algoritmi per la costruzione di codici ottimi (Fano, Shannon, Huffman). Costruzione di un codice binario ottimo con distribuzione equiprobabile delle probabilità di input. Applicazione dei risultati della teoria dell'informazione nella dimostrazione dei limiti inferiori e superiori per la complessità della realizzazione di 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 decodifica univoca di un codice. Algoritmi adattativi per la compressione delle informazioni.

Canale discreto senza memoria. Canale binario bilanciato. Velocità di trasferimento delle informazioni nel canale. Canale di banda. Canale esteso e sua larghezza di banda. Schemi decisivi e raggruppamenti di osservazioni. La probabilità di trasmissione errata delle informazioni. La disuguaglianza di Feinstein. Teorema diretto di codificare un canale senza memoria. La disuguaglianza di Fano. Teorema dell'elaborazione delle informazioni. Inversione del teorema della codifica.

La teoria della codifica a correzione di errori. Criterio di massima verosimiglianza. Distanza del codice. Codici di parità. Matrici generative e di controllo. Sindrome. Algoritmo di decodifica per codici di controllo di parità. Codici lineari e loro algoritmo di decodifica. Confine di Hamming. Codice Hamming. Codici ciclici. Codifica e decodifica cicliche.

LETTERATURA

1. Gallagher R. Teoria dell'informazione e comunicazione 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, Science, 1982.

4. Feinstein A. Fondamenti della teoria dell'informazione, M., IL, 1960.

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

6. Bärlekamp, ​​​​Teoria della codifica algebrica, M., Mir, 1971.

Il lavoro è stato aggiunto al sito site: 2016-03-30

; color: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5. Codifica delle informazioni

; color: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5.1. Concetti di base

I teoremi di codifica dei messaggi di Shannon sono stati menzionati sopra. È intuitivamente chiaro che la codifica è un'operazione di conversione delle informazioni in una forma necessaria per la successiva elaborazione (trasmissione tramite un canale di comunicazione, memorizzazione nella memoria di un sistema informatico, utilizzo per il processo decisionale, ecc.). È anche chiaro che quando si costruisce un qualsiasi sistema informativo è impossibile fare a meno della codifica: qualsiasi rappresentazione dell'informazione implica l'uso di alcuni codici. Pertanto, analizzeremo ulteriormente in dettaglio i fondamenti teorici della codifica dell'informazione.

Lascia che A - alfabeto arbitrario. Elementi dell'alfabeto UN sono chiamate lettere (o simboli), e le sequenze finite composte da lettere sono chiamate parole in UN ... In questo caso, si considera che in qualsiasi alfabeto ci sia una parola vuota che non contiene lettere.

Parola α 1 chiamato l'inizio (prefisso) di una parolaα se c'è una parolaα 2 tale che α = α 1 α 2; inoltre, la parola α 1 chiamato l'inizio stesso della parolaα se α 2 Non è una parola vuota. La lunghezza della parola è il numero di lettere nella parola (una parola vuota ha una lunghezza di 0). Registrazioneα 1 α 2 denota la connessione (concatenazione) di paroleα 1 e α 2. Parola α 2 chiamato la desinenza (suffisso) di una parolaα se c'è una parolaα 1, tale che α = α 1 α 2; inoltre, la parola α 2 chiamato la propria fine della 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 dell'insieme C in una varietà di parole dell'alfabeto B chiama D -codificando il set C (per D = 2 la codifica sarà binaria). La mappatura inversa è chiamata decodifica. Ecco alcuni esempi di codifiche.

1. Codifica di un insieme di 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ù breve che soddisfa la condizione

Ovviamente b 1 = 1, 2 l (n) - 1 ≤ n< 2 l (n ) e quindi

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

dove [x] e] x [indica, rispettivamente, l'intero più grande non eccedente X , e il più piccolo intero maggiore di X. La parola e (n ) è detta notazione binaria del numero n , e questa codifica è una rappresentazione di numeri in un sistema di numeri binari. Questa codifica è uno a uno, poiché per n 1 ≠ n 2 parole e (n 1) ed e (n 2 ) sono diversi. La tabella 5.1 mostra la rappresentazione dei primi 16 numeri naturali nel sistema binario.

"xml: lang =" ru-RU "lang =" ru-RU "> Tabella 5.1

"xml: lang =" ru-RU "lang =" ru-RU "> Codifica"xml: lang =" en-US "lang =" en-US "> e"xml: lang =" ru-RU "lang =" ru-RU "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" ru-RU "lang =" ru-RU ">)

"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)	"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)	"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)	"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)
"xml: lang =" en-US "lang =" en-US "> 0	"xml: lang =" en-US "lang =" en-US "> 0	"xml: lang =" en-US "lang =" en-US "> 4	"xml: lang =" en-US "lang =" en-US "> 100	"xml: lang =" en-US "lang =" en-US "> 8	"xml: lang =" en-US "lang =" en-US "> 1000	"xml: lang =" en-US "lang =" en-US "> 12	"xml: lang =" en-US "lang =" en-US "> 1100
"xml: lang =" en-US "lang =" en-US "> 1	"xml: lang =" en-US "lang =" en-US "> 1	"xml: lang =" en-US "lang =" en-US "> 5	"xml: lang =" en-US "lang =" en-US "> 101	"xml: lang =" en-US "lang =" en-US "> 9	"xml: lang =" en-US "lang =" en-US "> 1001	"xml: lang =" en-US "lang =" en-US "> 13	"xml: lang =" en-US "lang =" en-US "> 1101
"xml: lang =" en-US "lang =" en-US "> 2	"xml: lang =" en-US "lang =" en-US "> 10	"xml: lang =" en-US "lang =" en-US "> 6	"xml: lang =" en-US "lang =" en-US "> 110	"xml: lang =" en-US "lang =" en-US "> 10	"xml: lang =" en-US "lang =" en-US "> 1010	"xml: lang =" en-US "lang =" en-US "> 14	"xml: lang =" en-US "lang =" en-US "> 1110
"xml: lang =" en-US "lang =" en-US "> 3	"xml: lang =" en-US "lang =" en-US "> 11	"xml: lang =" en-US "lang =" en-US "> 7	"xml: lang =" en-US "lang =" en-US "> 111	"xml: lang =" en-US "lang =" en-US "> 11	"xml: lang =" en-US "lang =" en-US "> 1011	"xml: lang =" en-US "lang =" en-US "> 15	"xml: lang =" en-US "lang =" en-US "> 1111

2. Codifica dei primi 2 K numeri naturali, per i quali ogni numero n (0 ≤ n< 2 k ) la parola

e k (n) = 0 k - l (n) e (n),

dove notazione 0 k - l (n) denota una parola composta da k - l (n) zeri, e (n ) - rappresentazione numerica n nel sistema numerico binario discusso sopra. Questa codifica per i primi 16 numeri naturali ( K = 4) è riportato nella tabella 5.2.

"xml: lang =" ru-RU "lang =" ru-RU "> Tabella 5."xml: lang =" en-US "lang =" en-US "> 2

"xml: lang =" ru-RU "lang =" ru-RU "> Codifica"xml: lang =" en-US "lang =" en-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" ru-RU "lang =" ru-RU "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" ru-RU "lang =" ru-RU ">)

"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)	"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)	"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)	"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)
"xml: lang =" en-US "lang =" en-US "> 0	"xml: lang =" en-US "lang =" en-US "> 0000	"xml: lang =" en-US "lang =" en-US "> 4	"xml: lang =" en-US "lang =" en-US "> 0100	"xml: lang =" en-US "lang =" en-US "> 8	"xml: lang =" en-US "lang =" en-US "> 1000	"xml: lang =" en-US "lang =" en-US "> 12	"xml: lang =" en-US "lang =" en-US "> 1100
"xml: lang =" en-US "lang =" en-US "> 1	"xml: lang =" en-US "lang =" en-US "> 0001	"xml: lang =" en-US "lang =" en-US "> 5	"xml: lang =" en-US "lang =" en-US "> 0101	"xml: lang =" en-US "lang =" en-US "> 9	"xml: lang =" en-US "lang =" en-US "> 1001	"xml: lang =" en-US "lang =" en-US "> 13	"xml: lang =" en-US "lang =" en-US "> 1101
"xml: lang =" en-US "lang =" en-US "> 2	"xml: lang =" en-US "lang =" en-US "> 0010	"xml: lang =" en-US "lang =" en-US "> 6	"xml: lang =" en-US "lang =" en-US "> 0110	"xml: lang =" en-US "lang =" en-US "> 10	"xml: lang =" en-US "lang =" en-US "> 1010	"xml: lang =" en-US "lang =" en-US "> 14	"xml: lang =" en-US "lang =" en-US "> 1110
"xml: lang =" en-US "lang =" en-US "> 3	"xml: lang =" en-US "lang =" en-US "> 0011	"xml: lang =" en-US "lang =" en-US "> 7	"xml: lang =" en-US "lang =" en-US "> 0111	"xml: lang =" en-US "lang =" en-US "> 11	"xml: lang =" en-US "lang =" en-US "> 1011	"xml: lang =" en-US "lang =" en-US "> 15	"xml: lang =" en-US "lang =" en-US "> 1111

Sia A = (a i, i = 1, 2, ...) è un alfabeto finito o numerabile, le cui lettere sono numerate con numeri naturali. In questo caso, codificare le lettere dell'alfabeto UN può essere impostato in sequenza Parole D -arie V = (vi i, i = 1, 2, ...), dove v i c'è l'immagine di una lettera un io ... Tali sequenze di parole (dall'insieme V ) sono chiamati codici (alfabeto UN ). Se viene fornito il codice V dell'alfabeto A , quindi la codifica delle parole in cui ogni parola a i 1 a i 2 ... a ik corrisponde alla parola v io 1 v io 2 ... v ik si chiama codifica lettera per lettera.

Nel passaggio dalla codifica uno a uno delle lettere dell'alfabeto alla codifica lettera per lettera delle parole dell'alfabeto, la proprietà dell'uno a uno potrebbe non essere preservata. Ad esempio la codifica e (n ) non conserva questa proprietà, ma la codifica e k (n ) lo salva. I codici separabili mantengono la proprietà uno a uno. Il codice V = (vi io, io = 1, 2, ...) si dice separabile se da ciascuna uguaglianza della forma

v io 1 v io 2… v ik = v j 1 v j 2… v jl

ne segue che l = k e v i 1 = v j 1, v i 2 = v j 2,…, v ik = v jl ... I codici separabili sono indicati anche come codici decodificati in modo univoco.

I codici prefisso appartengono alla classe dei codici separabili. Il codice V = (vi io, io = 1, 2, ...) si chiama prefisso se nessuna parola v k non è l'inizio (prefisso) di nessuna parola v l, l ≠ k ... Se ogni parola del codice del prefisso viene sostituita dal suo inizio più piccolo, che non è l'inizio di altre parole del codice, anche il codice risultante avrà un prefisso. Questa operazione è denominata troncamento del prefisso.

Per codice arbitrario V composto da parole diverse, puoi costruire un albero del codice. È un grafo orientato che non contiene cicli, in cui il vertice 1 collegato alla parte superiore 2 bordo diretto da 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 del codice coincide con l'insieme dei vertici terminali (vertici da cui non derivano spigoli) dell'albero del codice.

5.2. Teoremi di codifica di base

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

Teorema 5.1. La disuguaglianza del mestiere.Per l'esistenza di un codice decodificato in modo univoco (separabile) contenente n parole in codice nel set (0, 1, D - 1) con lunghezze n 1, n 2, ..., n N , è necessario e sufficiente per la disuguaglianza

Prova. Immagina di avere un albero del codice per un codice prefisso. La radice dell'albero del codice è di livello 0, i nodi associati alla radice sono di livello 1 e così via. Possibile numero di vertici per K -esimo livello è indicato come D k. Ogni vertice k -esimo livello genera esattamente D n - k vertici dell'n -esimo livello.

n 1 ≤ n 2 ≤… ≤ n N = n.

Ovviamente, il codice di lunghezza K proibisce esattamente D n - k eventuali picchi finali (picchi dell'ultimo livello). Quindi tutte le parole del codice del prefisso vietano i vertici finali. Poiché il numero totale di vertici finali è D n , quindi la disuguaglianza

da cui segue che

Quindi, la disuguaglianza di Kraft è dimostrata.

Come risultato della dimostrazione del Teorema 5.1, si conclude che ci sono almeno codici prefisso che sono codici decodificabili in modo univoco con le lunghezze delle parole del codice n 1, n 2, ..., n N soddisfare la disuguaglianza di Kraft. Il seguente teorema, chiamato affermazione di McMillan, generalizza questa conclusione a tutti i codici decodificati in modo univoco.

Teorema 5.2. Disuguaglianza di McMillan.Ogni codice decodificato in modo univoco soddisfa la disuguaglianza Craft.

Prova. Alziamo la somma alla potenza L:

. (5.1)

Lascia che A k - il numero di combinazioni che contengono l parole in codice con lunghezza totale K ... Allora l'espressione (6.1) può essere rappresentata come

dove L max - la lunghezza massima di un messaggio contenente l parole in codice. Se il codice è decodificato in modo univoco, allora tutte le sequenze da l codici di lunghezza totale K sono diversi. Visto che c'è tutto D k possibili sequenze, allora A k ≤ D k e poi

Dal momento che L È il numero di codici indipendenti utilizzati per costruire tutte le possibili sequenze di lunghezza non superiore a Lmax. Pertanto, L ≤ L max e. E da ciò segue che

Poiché il ragionamento di cui sopra è valido per ogni codice decodificato in modo univoco, 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 del codice sorgente IO. Per qualsiasi sorgente discreta senza memoria X con alfabeto finito ed entropia H (X) esiste D -ary prefisso codice in cui la lunghezza media del codeword soddisfa la disuguaglianza

. (5.2)

Prova. Prima di tutto, chiariamo che una sorgente discreta senza memoria è descritta da un modello che non tiene conto delle connessioni tra i simboli del messaggio. Dimostriamo ora il membro sinistro della disuguaglianza (6.2):

Per questo, usiamo la definizione di entropia e la disuguaglianza di Kraft:

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

Quindi, per ogni termine, scegliamo il più piccolo intero n io per cui

Poiché la disuguaglianza di Kraft è preservata per questa scelta, è possibile costruire il codice del prefisso corrispondente. Perché n io È il più piccolo intero, quindi per n io - 1

Poi

Quindi il teorema del codice sorgente io dimostrato. Determina che la lunghezza media di una parola di codice non può essere inferiore all'entropia della sorgente del messaggio. Si noti che nella dimostrazione del teorema abbiamo usato la stessa notazione della considerazione della disuguaglianza di Kraft.

Teorema 5.4. Teorema del codice sorgente II. Per un blocco di lunghezza L esiste D -ary codice del prefisso in cui la lunghezza media del codeword 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 da l caratteri. Per dimostrare il teorema, puoi usare il teorema del codice sorgente IO:

Teorema del codice sorgente II permette di affermare che esistono metodi di codifica tali per un messaggio sufficientemente lungo che la lunghezza media della codeword può essere arbitrariamente avvicinata al valore. Infatti, per L  ∞, H L (X)  H, dove H È l'entropia della sorgente del messaggio per un simbolo, la disuguaglianza è vera?

, (5.3)

dove. Questo può anche essere interpretato come segue: per qualsiasi numero arbitrariamente piccoloε , esiste un metodo per codificare blocchi contenenti simboli, in cui la disuguaglianza (5.3) è soddisfatta per la lunghezza media di una parola di codice per simbolo.

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

; color: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5.3. Codifica ottimale

Il compito di costruire un codice ottimo è trovare interi positivi n 1, n 2, ..., n N minimizzando la lunghezza media della parola in codice, a condizione che la disuguaglianza di Kraft sia soddisfatta:

Quando si costruiscono codici nel caso dell'alfabeto A = (a io, io = 1, 2, ..., N ) con una distribuzione di probabilità nota P = (p io, io = 1, 2, ..., N ) senza perdita di generalità, possiamo assumere che le lettere dell'alfabeto UN sono numerati in ordine decrescente di probabilità, ad es. p 1 ≥ p 2 ≥… ≥ p N ... Inoltre, prenderemo in considerazione solo codici binari.

Esistono due metodi noti (di Fano e Shannon) per la costruzione di codici prossimi all'ottimale. Il metodo di Fano è il seguente. L'elenco delle lettere, ordinato in ordine di probabilità decrescente, è diviso in due parti consecutive in modo che le somme delle probabilità delle lettere incluse in esse differiscano il meno possibile l'una dall'altra. Alle lettere della prima parte viene assegnato il carattere 0 e alle lettere della seconda parte viene assegnato il carattere 1. Inoltre, lo stesso viene fatto con ciascuna delle parti ricevute, se contiene almeno due lettere. Il processo continua finché l'intero elenco non viene suddiviso in parti contenenti una lettera ciascuna. Ogni lettera è associata a una sequenza di caratteri assegnati come risultato di questo processo a questa lettera. È facile vedere che il codice risultante ha un prefisso.

Il metodo di Shannon è applicabile solo quando tutte le probabilità sono positive. Consiste nel fatto che la lettera un io con probabilità p io > 0, una sequenza da n i =] log (1 / p i ) [le prime cifre dopo la virgola nell'espansione del numero in una frazione infinita (per a 1 assumiamo che q 1 = 0). Dal momento che a l> k (a causa del fatto che p l ≤ p k) n l ≥ n k e quindi viene prefissato il codice così ottenuto. Sulla base del codice prefisso ottenuto, viene costruito un codice prefisso troncato, che è il risultato della codifica con il metodo Shannon.

Ad esempio, lascia che ci sia una serie di lettere A = (un 1, un 2, un 3, un 4, un 5, un 6, un 7 ) con la distribuzione di probabilità P = (0,2, 0,2, 0,19, 0,12, 0,11, 0,09, 0,09). Eseguiamo la codifica delle lettere utilizzando il metodo Fano.

1. Dividi l'elenco in due parti in modo che le somme delle probabilità delle lettere incluse in esse differiscano il meno possibile l'una dall'altra:

A 1 = (a 1, a 2, a 3), P 1 = (0.2, 0.2, 0.19);

A 2 = (a 4, a 5, a 6, a 7), P 2 = (0,12, 0,11, 0,09, 0,09).

2. Assegniamo il simbolo 0 alle lettere della prima parte, e il simbolo 1 alle lettere della seconda parte:

Un 1 = (un 1/0, un 2/0, un 3/0);

Un 2 = (un 4/1, un 5/1, un 6/1, un 7/1).

3. Ripetiamo i passaggi precedenti in sequenza per ciascuna delle parti separatamente. V di conseguenza otteniamo:

A 1 1 = (a 1/00);

A 121 = (a 2/010);

A 122 = (a 3/011);

Un 211 = (un 4/100);

A 212 = (a 5/101);

A 221 = (a 6/110);

A 222 = (a 7/111).

I codici risultanti sono mostrati per ogni lettera a destra della barra. In questo caso, l'ordine degli indici degli elenchi di una lettera ottenuti mostra la sequenza di suddivisione dell'elenco originale di gruppi in parti.

Il processo di codifica Fano è convenientemente formattato sotto forma di tabella. Per l'esempio considerato, è mostrato nella tabella 5.3.

"xml: lang =" ru-RU "lang =" ru-RU "> Tabella 5.3

"xml: lang =" ru-RU "lang =" ru-RU "> codifica Fano

"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0.20	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 00
"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 2	"xml: lang =" ru-RU "lang =" ru-RU "> 0.20		"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 010
"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 3	"xml: lang =" ru-RU "lang =" ru-RU "> 0.19			"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 011
"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 4	"xml: lang =" ru-RU "lang =" ru-RU "> 0.12	"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 100
"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 5	"xml: lang =" ru-RU "lang =" ru-RU "> 0.11			"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 101
"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 6	"xml: lang =" ru-RU "lang =" ru-RU "> 0.09		"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 110
"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 7	"xml: lang =" ru-RU "lang =" ru-RU "> 0.09			"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 111

Determiniamo la lunghezza media del codeword:

Ora eseguiamo la codifica Shannon. Il processo di codifica è mostrato nella tabella 5.4.

"xml: lang =" ru-RU "lang =" ru-RU "> Tabella 5.4

"xml: lang =" ru-RU "lang =" ru-RU "> codifica Shannon

"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" en-US "lang =" en-US "> n; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" en-US "lang =" en-US "> q; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" ru-RU "lang =" ru-RU "> Codice"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" ru-RU "lang =" ru-RU "> Codice troncato"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i
"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" en-US "lang =" en-US ">] 2.321… [= 3	"xml: lang =" en-US "lang =" en-US "> 0	000	000
a 2	] 2.321… [= 3	0.2	001	001
a 3	] 2.395… [= 3	0.4	011	01
a 4	] 3.058… [= 4	0,59	1001	100
a 5	] 3.183… [= 4	0.71	1011	101
a 6	] 3.472… [= 4	0,82	1101	110
a 7	] 3.472… [= 4	0,91	1110	111

Come nel caso precedente, troviamo la lunghezza media del codeword:

.

Come puoi vedere, i risultati della codifica con i metodi Fano e Shannon in termini di minimizzazione della lunghezza media del codice praticamente coincidevano. Pertanto, questi metodi sono spesso considerati come uno (nella formulazione di Fano) e chiamati metodo Shannon-Fano.

Nel 1952, David Huffman propose un metodo di codifica ottimale del prefisso per sorgenti discrete, che, contrariamente ai metodi di Shannon e Fano, è ancora utilizzato nella pratica. D. Huffman ha dimostrato che la lunghezza media di una parola in codice, ottenuta con il suo metodo, sarà minima. La codifica di Huffman viene eseguita in tre passaggi.

1. Ordinamento: le lettere sono disposte in ordine decrescente di probabilità.

2. Riduzione: due lettere con la probabilità più bassa vengono combinate in una con la probabilità totale; l'elenco delle lettere viene riordinato secondo il passaggio 1; il processo continua finché tutte le lettere non vengono combinate in una. In questo caso, è possibile ottenere l'equalizzazione delle lunghezze delle parole in codice utilizzando la seguente strategia: se più lettere hanno le stesse probabilità, vengono combinate quelle due che in precedenza hanno avuto il minor numero di unioni (sebbene ciò non influenzano la lunghezza media del codice).

3. Codifica: a partire dall'ultima unione, a un componente della lettera composta viene assegnato in sequenza il simbolo 0 e il secondo - il simbolo 1; il processo continua fino a quando tutte le lettere originali sono codificate.

Eseguiamo la codifica di Huffman per l'insieme considerato negli esempi di applicazione dei metodi Fano e Shannon.

1. Elenco delle lettere originaliUN = { un1 , un2 , un3 , un4 , un5 , un6 , un7 ) è già ordinato poichéP = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}.

2. Combina le lettereun6 eun7 in una letteraun1 con probabilità0.18 eriordinareelenco:

P1 = {0.2, 0.2, 0.19, 0.18, 0.12, 0.11}, UN1 = { un1 , un2 , un3 , un1 , un4 , un5 }.

3. Ripetere il passaggio 2 finché nell'elenco non è rimasta solo una lettera:

P2 = {0.23, 0.2, 0.2, 0.19, 0.18}, UN2 = { un2 , un1 , un2 , un3 , un1 };

P3 = {0.37, 0.23, 0.2, 0.2}, UN3 = { un3 , un2 , un1 , un2 };

P4 = {0.4, 0.37, 0.23}, UN4 = { un4 , un3 , un2 };

P5 = {0.6, 0.4}, UN5 = { un5 , un4 };

P6 = {1}, UN6 = { un6 }.

4. Assegniamobinariocodicisimboli:

un6 : un5 = 0, un4 = 1;

un5 : un3 = 00, un2 = 01;

un4 : un1 = 10, un2 = 11;

un3 : un3 = 000, un1 = 001;

un2 : un4 = 010, un5 = 011;

un1 : un6 = 0010, un7 = 0011.

Pertanto, alle lettere originali vengono assegnati i seguenti codici binari:un1 = 10, un2 = 11, un3 = 000, un4 = 010, un5 = 011, un6 = 0010, un7 = 0011, che fornisce una lunghezza media del codice inferiore a quella della codifica Fano e Shannon.

Definiamo la ridondanza dei codici ricevuti. Per fare ciò, troviamo l'entropia della sorgente del messaggio:

.

Quindi i codici hanno la seguente ridondanza:

Codice Fano:;

Codice Shannon:;

Codice di Huffman:.

Pertanto, la ridondanza del codice di Huffman è minima.

Per ridurre la ridondanza, ad es. riducendo la lunghezza media di una parola in codice di un simbolo, è possibile utilizzare la codifica a blocchi, la cui motivazione è fornita nel teorema della codifica sorgenteII... In questo caso è necessario ottenere tutti i possibili gruppi di lettere di una data lunghezza, trovare le probabilità dei gruppi, come le probabilità di comparsa congiunta delle lettere del gruppo contemporaneamente, ed eseguire la codifica, considerando la gruppi come simboli del nuovo alfabeto.

PAGE 43