Concetti di base sulla codifica. Fondamenti di teoria dell'informazione e codifica. Classificazione dei metodi di codifica

04.04.2006 Leonid Chernyak Categoria: Tecnologia

"Sistemi aperti" La creazione di computer sarebbe stata impossibile se la teoria della codifica dei segnali non fosse stata creata contemporaneamente al "loro aspetto. Teoria della codifica" è una di quelle aree della matematica che hanno influenzato in modo significativo lo sviluppo dell'informatica.

"Sistemi aperti"

La creazione di computer sarebbe stata impossibile se la teoria della codifica dei segnali non fosse stata creata contemporaneamente al loro aspetto.

La teoria dei codici è una di quelle aree della matematica che hanno influenzato notevolmente lo sviluppo dell'informatica. Il suo scopo si estende alla trasmissione di dati tramite canali reali (o rumorosi) e l'oggetto è quello di garantire la correttezza delle informazioni trasmesse. In altre parole, apprende come impacchettare meglio i dati in modo che dopo che un segnale sia stato trasmesso, le informazioni utili possano essere estratte in modo affidabile e semplice dai dati. A volte la teoria della codifica è confusa con la crittografia, ma questo non è vero: la crittografia risolve il problema opposto, il suo scopo è quello di rendere difficile ottenere informazioni dai dati.

La necessità di codificare i dati è stata incontrata per la prima volta oltre 150 anni fa, poco dopo l'invenzione del telegrafo. I canali erano costosi e inaffidabili, il che rendeva urgente il compito di ridurre al minimo i costi e aumentare l'affidabilità della trasmissione di telegrammi. Il problema è stato ulteriormente aggravato dalla posa di cavi transatlantici. Dal 1845 sono entrati in uso libri di codice speciali; sono stati usati dagli operatori del telegrafo per "comprimere" manualmente i messaggi, sostituendo le sequenze di parole comuni con codici più brevi. Allo stesso tempo, il controllo di parità ha iniziato a essere utilizzato per verificare la correttezza della trasmissione, un metodo che è stato utilizzato per verificare la correttezza dell'inserimento di schede perforate anche nei computer di prima e seconda generazione. Per questo, una carta appositamente preparata con un checksum è stata inserita nel mazzo da inserire. Se il dispositivo di input non era molto affidabile (o il deck era troppo grande), potrebbe verificarsi un errore. Per correggerlo, la procedura di iscrizione è stata ripetuta fino a quando il checksum calcolato corrispondeva a quello memorizzato sulla carta. Questo schema non solo è scomodo, ma manca anche doppi errori. Con lo sviluppo di canali di comunicazione, era necessario un meccanismo di controllo più efficace.

La prima soluzione teorica al problema della trasmissione dei dati su canali rumorosi è stata proposta da Claude Shannon, il fondatore della teoria statistica dell'informazione. Shannon era la star del suo tempo, era una delle élite accademiche statunitensi. Come studente laureato di Vannevar Bush, nel 1940 ricevette il Premio Nobel (da non confondere con il Premio Nobel!), Assegnato a scienziati di età inferiore ai 30 anni. Mentre era al Bell Labs, Shannon scrisse The Mathematical Theory of Message Transmission (1948), dove mostrò che se la larghezza di banda di un canale è superiore all'entropia della fonte del messaggio, allora il messaggio può essere codificato in modo che venga trasmesso senza indebito ritardo. Questa conclusione è contenuta in uno dei teoremi dimostrati da Shannon, il cui significato si riduce al fatto che se esiste un canale con una larghezza di banda sufficiente, il messaggio può essere trasmesso con alcuni ritardi. Inoltre, ha mostrato la possibilità teorica di una trasmissione affidabile in presenza di rumore nel canale. La formula C \u003d W log ((P + N) / N), scolpita su un modesto monumento a Shannon, eretta nella sua città natale nel Michigan, viene confrontata in valore con la formula E di Albert Einstein E \u003d mc 2.

I lavori di Shannon fornirono cibo per molte ulteriori ricerche nel campo della teoria dell'informazione, ma non avevano alcuna applicazione pratica di ingegneria. Il passaggio dalla teoria alla pratica è stato reso possibile dagli sforzi di Richard Hamming, un collega dei Bell Labs di Shannon che è diventato famoso per aver scoperto una classe di codici che sono diventati chiamati "codici di Hamming". C'è una leggenda secondo cui l'invenzione dei loro codici Hamming è stata provocata dall'inconveniente di lavorare con le schede perforate sulla calcolatrice a relè Bell Modello V a metà degli anni '40. Gli veniva dato il tempo di lavorare sulla macchina nei fine settimana quando non c'erano operatori e doveva armeggiare lui stesso con l'input. Comunque sia, ma Hamming ha proposto codici che possono correggere errori nei canali di comunicazione, comprese le linee di trasmissione dei dati nei computer, principalmente tra il processore e la memoria. I codici di Hamming forniscono prove di come le possibilità evidenziate dai teoremi di Shannon possano essere concretamente realizzate.

Hamming pubblicò il suo articolo nel 1950, anche se la sua teoria dei codici risale al 1947 in rapporti interni. Pertanto, alcuni credono che Hamming dovrebbe essere considerato il padre della teoria dei codici, e non Shannon. Tuttavia, nella storia della tecnologia è inutile cercare il primo.

Quel che è certo è che Hamming è stato il primo a proporre il codice di correzione degli errori (ECC). Modifiche moderne di questi codici vengono utilizzate in tutti i sistemi di archiviazione dei dati e per lo scambio tra il processore e la memoria principale. Una delle loro varianti, i codici Reed-Solomon sono utilizzati nei CD, consentendo di riprodurre dischi senza scricchiolii e rumori che potrebbero causare graffi e particelle di polvere. Esistono molte versioni dei codici, costruite "basate su" Hamming, differiscono per gli algoritmi di codifica e il numero di bit di controllo. Tali codici hanno acquisito particolare importanza in relazione allo sviluppo di comunicazioni spaziali a lunga distanza con stazioni interplanetarie, ad esempio ci sono codici Reed-Muller, dove ci sono 32 bit di controllo per sette bit di informazioni o 26 per sei.

Tra i codici ECC più recenti ci sono i codici LDPC (Low-Density Parity-Check Code). In effetti, sono noti da trent'anni, ma uno speciale interesse per loro è stato rivelato proprio negli ultimi anni, quando la televisione ad alta definizione ha iniziato a svilupparsi. I codici LDPC non sono precisi al 100%, ma il tasso di errore può essere regolato al livello desiderato e la larghezza di banda viene utilizzata il più possibile. Accanto a loro ci sono "Turbo Code", sono efficaci quando si lavora con oggetti situati nello spazio profondo e con larghezza di banda del canale limitata.

Il nome di Vladimir Aleksandrovich Kotelnikov è saldamente inscritto nella storia della teoria dei codici. Nel 1933, in "Materiali sulle comunicazioni radio per il Primo Congresso dell'Unione Europea sulla ricostruzione tecnica delle comunicazioni", pubblicò il lavoro "Sulla larghezza di banda dell'etere?" e? filo? " Il nome di Kotelnikov, in egual misura, è incluso nel titolo di uno dei teoremi più importanti della teoria dei codici. Questo teorema definisce le condizioni in cui il segnale trasmesso può essere ripristinato senza perdita di informazioni.

Questo teorema è chiamato con vari nomi, incluso il "teorema di WKS" (l'abbreviazione WKS è presa da Whittaker, Kotelnikov, Shannon). Alcune fonti usano sia il teorema di campionamento di Nyquist-Shannon sia il teorema di campionamento di Whittaker-Shannon, e nei libri di testo universitari russi, il più comune è semplicemente il "teorema di Kotelnikov". In effetti, il teorema ha una storia più lunga. La sua prima parte fu dimostrata nel 1897 dal matematico francese Emile Borel. Edmund Whittaker ha dato il suo contributo nel 1915. Nel 1920, il giapponese Kinnosuki Ogura pubblicò emendamenti alla ricerca di Whittaker e nel 1928 l'americano Harry Nyquist perfezionò i principi della digitalizzazione e del recupero di un segnale analogico.

Claude Shannon (1916 - 2001) dagli anni scolastici ha mostrato uguale interesse per la matematica e l'ingegneria elettrica. Nel 1932 entrò all'Università del Michigan, nel 1936 - presso il Massachusetts Institute of Technology, dal quale si laureò nel 1940, ottenendo due lauree - un master in ingegneria elettrica e un dottorato in matematica. Nel 1941, Shannon si unì ai Bell Laboratories. Qui iniziò a sviluppare idee che in seguito portarono alla teoria dell'informazione. Nel 1948, Shannon pubblicò un articolo "Teoria matematica della comunicazione", in cui venivano formulate le idee di base dello scienziato, in particolare, la determinazione della quantità di informazioni attraverso l'entropia, e propose anche un'unità di informazioni che determina la scelta di due opzioni ugualmente probabili, cioè quella che in seguito fu chiamata un po ' ... Nel 1957-1961, Shannon pubblicò articoli in cui dimostrò il teorema sulla capacità di canali di comunicazione rumorosi, che ora porta il suo nome. Nel 1957, Shannon divenne professore presso il Massachusetts Institute of Technology, da cui si ritirò 21 anni dopo. Durante il "meritato pensionamento" Shannon si arrese completamente alla sua passione di lunga data per la giocoleria. Ha costruito diverse macchine da giocoliere e persino sviluppato una teoria generale di giocoleria.

Richard Hamming (1915 - 1998) iniziò la sua formazione all'Università di Chicago, dove si laureò nel 1937. Nel 1939, ha conseguito un master presso l'Università del Nebraska e il dottorato in matematica presso l'Università dell'Illinois. Nel 1945, Hamming iniziò a lavorare come parte del Progetto Manhattan, un progetto di ricerca governativa su larga scala per creare la bomba atomica. Nel 1946, Hamming si unì ai Bell Telephone Laboratories, dove lavorò con Claude Shannon. Nel 1976, Hamming ricevette una cattedra alla Naval Graduate School di Monterey, in California.

Il lavoro che lo ha reso famoso, lo studio fondamentale del rilevamento degli errori e dei codici di correzione, è stato pubblicato da Hamming nel 1950. Nel 1956, ha lavorato su uno dei primi mainframe IBM 650. Il suo lavoro ha gettato le basi per un linguaggio di programmazione che in seguito si è evoluto in linguaggi di programmazione di alto livello. In riconoscimento dei risultati raggiunti da Hamming nell'informatica, l'IEEE ha istituito la Distinguished Service Medal for Informatics and Systems Theory, che ha preso il suo nome.

Vladimir Kotelnikov (1908 - 2005) nel 1926 entrò nella Facoltà di Ingegneria Elettrica della Scuola Tecnica Superiore di Mosca intitolata a N.E.Bauman (MVTU), ma si laureò al Moscow Power Engineering Institute (MEI), che si separò dalla MVTU come istituto indipendente. Durante i suoi studi post-laurea (1931-1933) Kotelnikov formulò matematicamente e dimostrò il "teorema del conteggio", che in seguito prese il suo nome. Dopo essersi diplomato alla scuola di specializzazione nel 1933, Kotelnikov, pur continuando a insegnare al Moscow Power Engineering Institute, andò a lavorare presso il Central Scientific Research Institute of Communications (TsNIIS). Nel 1941, V.A.Kotelnikov formulò una chiara dichiarazione di quali requisiti un sistema matematicamente indecifrabile deve soddisfare e fu data una prova dell'impossibilità della sua decodifica. Nel 1944, Kotelnikov ha assunto la posizione di professore, decano della facoltà di ingegneria radio di MPEI, dove ha lavorato fino al 1980. Nel 1953, all'età di 45 anni, Kotelnikov fu immediatamente eletto membro a pieno titolo dell'Accademia delle scienze dell'URSS. Dal 1968 al 1990, V.A.Kotelnikov è stato anche professore, capo di un dipartimento dell'Istituto di fisica e tecnologia di Mosca.

La nascita della teoria dei codici

Coding. Concetti basilari.

Vari metodi di codifica sono stati ampiamente utilizzati nella pratica umana da tempo immemorabile. Ad esempio, la notazione posizionale decimale è un modo per codificare i numeri naturali. Un altro modo di codificare i numeri naturali sono i numeri romani, e questo metodo è più visivo e naturale, anzi, dito - I, cinque - V, due dita - X. Tuttavia, con questo metodo di codifica, è più difficile eseguire operazioni aritmetiche su grandi numeri, quindi è stato soppiantato dal metodo codifica basata sulla notazione decimale posizionale. Da questo esempio, possiamo concludere che vari metodi di codifica hanno caratteristiche specifiche inerenti solo a loro, che, a seconda degli obiettivi di codifica, possono essere sia un vantaggio di un particolare metodo di codifica sia il suo svantaggio.

I metodi di codifica numerica degli oggetti geometrici e la loro posizione nello spazio sono ampiamente noti: coordinate cartesiane e coordinate polari. E questi metodi di codifica differiscono nelle loro caratteristiche specifiche intrinseche.

Fino al 20 ° secolo, i metodi e gli strumenti di codifica avevano un ruolo di supporto, ma con l'avvento dei computer la situazione è cambiata radicalmente. La codifica è ampiamente utilizzata nella tecnologia dell'informazione ed è spesso un problema centrale nella risoluzione di una varietà di problemi come:

- presentazione di dati di natura arbitraria (numeri, testo, grafica) nella memoria del computer;

- trasmissione ottimale dei dati sui canali di comunicazione;

- protezione delle informazioni (messaggi) da accessi non autorizzati;

- garantire l'immunità al rumore durante la trasmissione dei dati attraverso i canali di comunicazione;

- compressione delle informazioni.

Dal punto di vista della teoria dell'informazione, la codifica è un processo di confronto inequivocabile dell'alfabeto della fonte del messaggio e un certo insieme di simboli condizionali, effettuato secondo una certa regola, e un codice (alfabeto del codice) è un insieme completo (insieme) di vari simboli condizionali (simboli di codice) che possono essere utilizzati per codifica del messaggio originale e che sono possibili con la regola di codifica fornita. Il numero di diversi simboli di codice che compongono l'alfabeto del codice è chiamato il volume del codice o il volume dell'alfabeto del codice. Ovviamente, il volume dell'alfabeto in codice non può essere inferiore al volume dell'alfabeto del messaggio originale da codificare. Pertanto, la codifica è la trasformazione del messaggio originale in una raccolta o sequenza di simboli di codice che rappresentano il messaggio trasmesso sul canale di comunicazione.

La codifica può essere numerica (digitale) e non numerica, a seconda del tipo in cui sono rappresentati i simboli del codice: numeri in qualsiasi sistema numerico o altri oggetti o segni, rispettivamente.

Nella maggior parte dei casi, i simboli di codice sono una raccolta o una sequenza di alcuni dei componenti più semplici, ad esempio una sequenza di numeri in simboli di codice di un codice numerico, che sono chiamati elementi di un simbolo di codice. La posizione o il numero ordinale di un elemento in una parola in codice è determinato dalla sua posizione.

Il numero di elementi di un carattere di codice utilizzato per rappresentare un carattere dell'alfabeto dell'origine del messaggio originale è chiamato valore del codice. Se il valore del codice è lo stesso per tutti i simboli dell'alfabeto del messaggio originale, il codice viene chiamato uniforme, altrimenti - irregolare. Il numero di elementi inclusi nel simbolo del codice viene talvolta chiamato lunghezza del simbolo del codice.

Dal punto di vista della ridondanza, tutti i codici possono essere suddivisi in codici non ridondanti e codici ridondanti. Nei codici ridondanti, il numero di elementi dei simboli di codice può essere ridotto a causa dell'uso più efficiente degli elementi rimanenti, nei codici non ridondanti, la riduzione del numero di elementi nei simboli di codice è impossibile.

I problemi di codifica in assenza di interferenze e in loro presenza sono significativamente diversi. Pertanto, viene fatta una distinzione tra codifica efficace (entropia) e codifica corretta (correzione errori). Con una codifica efficiente, il compito è ottenere la rappresentazione dei caratteri alfabetici della fonte del messaggio con il numero minimo di elementi simbolo del codice in media per un carattere dell'alfabeto della fonte del messaggio riducendo la ridondanza del codice, il che porta ad un aumento della velocità di trasmissione del messaggio. E con la codifica correttiva (correzione degli errori), il compito è ridurre la probabilità di errori nella trasmissione dei simboli dell'alfabeto originale rilevando e correggendo gli errori introducendo un'ulteriore ridondanza del codice.

Un compito separato di codifica è proteggere i messaggi da accessi non autorizzati, distorsione e distruzione. Con questo tipo di codifica, i messaggi vengono codificati in modo tale che anche dopo averli ricevuti, un utente malintenzionato non sarebbe in grado di decodificarli. Il processo di questo tipo di codifica dei messaggi si chiama crittografia (o crittografia) e il processo di decodifica si chiama decrittografia (o decrittografia). Il messaggio codificato stesso è chiamato crittografato (o semplicemente crittografia) e il metodo di codifica utilizzato è chiamato cifratura.

Molto spesso, i metodi di codifica si distinguono in una classe separata, che consente di costruire (senza perdita di informazioni) codici di messaggio che hanno una lunghezza inferiore rispetto al messaggio originale. Tali tecniche di codifica sono chiamate tecniche di compressione o di impacchettamento dei dati. La qualità della compressione è determinata dal rapporto di compressione, che di solito viene misurato in percentuale e che mostra quanto del messaggio codificato è più corto dell'originale.

Nell'elaborazione automatica delle informazioni utilizzando un computer, di norma viene utilizzata la codifica numerica (digitale) e, naturalmente, si pone la questione di giustificare il sistema numerico utilizzato. In effetti, con una diminuzione della base del sistema numerico, l'alfabeto degli elementi dei simboli di codice viene semplificato, ma i simboli di codice vengono allungati. D'altra parte, maggiore è la base del sistema numerico, minore è il numero di cifre richieste per rappresentare un simbolo di codice e, di conseguenza, meno tempo per la sua trasmissione, ma con la crescita della base del sistema numerico, i requisiti per i canali di comunicazione e i mezzi tecnici per riconoscere i segnali elementari corrispondente a vari elementi dei simboli del codice. In particolare, il codice di un numero scritto nel sistema binario è in media circa 3,5 volte più lungo del codice decimale. Poiché in tutti i sistemi di elaborazione delle informazioni è necessario memorizzare grandi matrici di informazioni sotto forma di informazioni numeriche, uno dei criteri essenziali per la scelta dell'alfabeto degli elementi dei simboli del codice numerico (ovvero la base del sistema numerico utilizzato) è di ridurre al minimo il numero di elementi elettronici nei dispositivi di archiviazione, nonché il loro semplicità e affidabilità.

Quando si determina il numero di elementi elettronici necessari per fissare ciascuno degli elementi dei simboli di codice, è necessario procedere dal presupposto praticamente giustificato che ciò richiede il numero di elementi elettronici più semplici (ad esempio transistor) pari alla base del sistema numerico un'... Quindi per l'archiviazione in alcuni dispositivi nsaranno necessari elementi di carattere di codice Melementi elettronici:

M \u003d a n. (2.1)

Il maggior numero di numeri distinti che possono essere registrati in questo dispositivo N:

N \u003d a n.

Prendendo il logaritmo di questa espressione e esprimendola n noi abbiamo:

n\u003d ln N / ln un.

Trasformazione dell'espressione (2.1) nel modulo

M= a ∙ln N / ln un'(2.2)

è possibile determinare a quale base dei logaritmi un'quantità di elementi Msarà minimo per un dato N... Differenziando da un'funzione M \u003d f (a)e equiparando la sua derivata a zero, otteniamo:

Ovviamente, per ogni finito un'

ln N / ln 2 a ≠ 0

e quindi

ln a -1 = 0,

da dove a \u003d e ≈ 2.7.

Dato che il radix può essere solo un numero intero, allora eè scelto uguale a 2 o 3. Ad esempio, impostiamo la capacità massima del dispositivo di archiviazione N\u003d 10 6 numeri. Quindi, per diverse basi dei sistemi di numerazione ( e) quantità di elementi ( M) in un dispositivo di memorizzazione di questo tipo, conformemente all'espressione (2.2), quanto segue (tabella 2.1):

Tabella 2.1

e
M	39,2	38,2	39,2	42,9		91,2

Pertanto, se procediamo dalla minimizzazione della quantità di apparecchiature, i più vantaggiosi saranno i sistemi numerici binari, ternari e quaternari, che sono vicini in questo parametro. Ma poiché l'implementazione tecnica dei dispositivi che operano nel sistema numerico binario è molto più semplice, i più diffusi nella codifica numerica sono i codici basati sul sistema numerico di base 2.

Parlando in generale, codifica - qualsiasi trasformazione di un messaggio in un segnale stabilendo una corrispondenza reciproca tra loro. In senso stretto codifica - trasformazione di un messaggio discreto in una sequenza di simboli di codice secondo una determinata regola. L'insieme di tutte le sequenze di codici ( codice combinazioni o parole), possibile per una determinata regola di codifica, moduli codice... La regola di codifica può essere espressa da una tabella di codici con l'alfabeto dei messaggi codificati e le corrispondenti combinazioni di codici. Viene chiamato l'insieme di simboli che compongono le sequenze di codici alfabeto di codicee il loro numero (dimensione dell'alfabeto codice) è codice di base.

Regole di codifica elementi del messaggio - regole di registrazione numeri diversi in
sistema numerico -ary. Distinguere binario (
) e multiposizione (
-personale,
)codici. Lunghezza della parola chiave - il numero di cifre al suo interno . Per trasmettere messaggi in codice binario, è sufficiente avere solo due segnali diversi. Quindi i simboli e può essere trasmesso da oscillazioni di frequenze diverse o da impulsi di corrente di diversa polarità. Distanza di Hamming tra due parole in codice e si trovano in due fasi. Aggiungi le parole di ricerca bit per bit in
sistema numerico -ary senza trasferimento al bit più significativo ( aggiunta modulo base di codice
indicato da  ). I valori risultanti vengono aggiunti a
-sistema numerico

, (1.1)

dove e - con lo stesso nome (
s) bit di parole in codice e , rispettivamente. Così,
,
,
e
a
... Per il codice binario, la distanza è uguale al numero di cifre in cui le parole e sono diversi. Distanza codice - il valore più piccolo per questo codice ... NEL equidistante Nel codice, le distanze tra due parole qualsiasi sono le stesse. Il numero di elementi diversi da zero della codeword è uguale al suo peso .

1.2. Classificazione dei metodi di codifica

In fig. 1.1 viene fornita la classificazione dei metodi di codifica ... Uno dei suoi compiti è coordinare l'alfabeto del messaggio con l'alfabeto del canale. Ogni insieme di messaggi può essere codificato in diversi modi. Il codice migliore soddisfa i requisiti:

1) il destinatario può recuperare il messaggio sorgente inviato sulla linea di comunicazione;

2) per rappresentare un messaggio, in media, è richiesto il numero minimo di caratteri.

Il primo requisito è soddisfatto reversibile codici. In essi, tutte le parole in codice sono diverse e sono associate in modo univoco ai messaggi corrispondenti. Economicoi codici soddisfano il secondo requisito.

Figura. 1.1. Classificazione dei metodi di codifica

La proposta efficace(statistico) la codifica serve ad aumentare la velocità di trasmissione delle informazioni e ad avvicinarla al massimo possibile - la larghezza di bandacanale di comunicazione. Accordo prestazioni alla fontemessaggi da canale di banda È una delle attività di codifica più importanti.

I codici sono primario(semplice o primitivo) e anti-jamming... I codici semplici sono costituiti da tutte le parole in codice possibili con un determinato metodo di codifica. La conversione di un carattere della parola in codice in un altro a causa dell'azione dell'interferenza dà una nuova parola in codice. Si verifica un errore che non può essere rilevato. Nei codici di correzione degli errori, viene utilizzata solo una parte del numero totale di parole in codice possibili. Le parole usate sono chiamate consentito, il riposo - proibito... La codifica anti-jamming migliora la fedeltà della trasmissione dei messaggi.

Distinguere encoder (programmatori informatici) per fonte informazioni e per canalecomunicazione. Il compito del primo è quello di rappresentare i messaggi economicamente (nel senso del numero medio minimo di caratteri), e il compito del secondo è quello di garantire una trasmissione affidabile dei messaggi.

decodificaconsiste nel ripristinare il messaggio dai simboli di codice ricevuti. Decodificatore ( decoder) insieme alle forme dell'encoder codec. Di solito un codec è un dispositivo logico.

Primitivo (surplus) la codifica viene utilizzata per abbinare l'alfabeto della sorgente con l'alfabeto del canale. Poi ridondanza di fonti(vedi clausola 2.1) formata l'uscita e l'ingresso dell'encoder sono uguali. Questa codifica viene anche utilizzata per crittografare le informazioni trasmesse e aumentare la stabilità del sistema di sincronizzazione. In quest'ultimo caso, la regola di codifica viene scelta in modo tale che la probabilità di comparsa all'uscita dell'encoder di una lunga sequenza consistente solo di o solo da era minimo. Viene chiamato un codificatore simile scrambler (dalla parola inglese crscramble - mescolare).

Il ripristino del messaggio trasmesso nel ricevitore è sempre approssimativo. Vengono chiamate alcune delle informazioni richieste per garantire l'accuratezza del recupero richiesta essenziale. Compressione (compressione) messaggi(dati) - rimozione completa o parziale da esso (loro) ridondante informazione. La soluzione a questo problema è stata raggiunta economico codifica. La compressione dei dati consente di risparmiare spazio di archiviazione e larghezza di banda. Con una codifica economica, la ridondanza della sorgente formata dall'uscita dell'encoder è inferiore a quella all'ingresso dell'encoder. La codifica economica viene utilizzata nei computer. I sistemi operativi contengono programmi di compressione dei dati ( compressori dinamici e software di archiviazione). Quindi lo standard
sul modemper la comunicazione tra computer sulla rete telefonica pubblica è inclusa la compressione del numero di procedure di elaborazione dei dati (vedere Appendice).

Anti-jamming (eccesso) viene utilizzata per rilevare e correggere errori che si verificano quando un messaggio viene trasmesso su un canale. Quindi la ridondanza della sorgente formata dall'uscita dell'encoder è maggiore della ridondanza della sorgente all'ingresso dell'encoder. Questa codifica è comune in vari sistemi di comunicazione, durante l'archiviazione e la trasmissione di dati in reti di computer, in apparecchiature audio e video digitali.

Il numero di bit in diverse parole chiave del codice può essere uguale o diverso. Di conseguenza, distinguere uniformee irregolare codici. L'uso di codici uniformi semplifica la costruzione di dispositivi automatici di stampa diretta e non richiede il trasferimento di caratteri di separazione tra parole di codice. Numero di cifre in qualsiasi parola in codice uniforme - codice testimone... Per un codice uniforme, il numero di possibili combinazioni è
.

Esempio 1.2.1.Il codice uniforme primitivo usato in telegrafia è il codice Baudot con elementi binari in ogni parola (

). Conteggio parole totale
... Questo è sufficiente per la codifica
lettere dell'alfabeto russo, ma non abbastanza per trasmettere un messaggio contenente lettere, numeri e vari segni convenzionali (punto, virgola, addizione, moltiplicazione, ecc.). Quindi è possibile applicare il "Codice internazionale n. 2" (МТК-2) con il principio del registro. È la stessa cosa
una parola in codice elementare può essere utilizzata fino a tre volte, a seconda della posizione del registro: russo, latino e digitale. Il numero totale di segni diversi è
che è sufficiente per codificare il telegramma. Consigliato per il trasferimento dei dati
codice elemento МТК-5 .

NEL codici irregolarile parole in codice differiscono non solo nella disposizione dei caratteri, ma anche nel loro numero. Questi codici richiedono separatori speciali che indicano la fine di uno e l'inizio di un'altra parola in codice, oppure sono costruiti in modo tale che nessuna parola in codice sia l'inizio di un'altra. Prefisso (irriducibile) i codici soddisfano l'ultima condizione. Si noti che il codice uniforme è irriducibile.

È conveniente rappresentare la struttura del codice nel modulo contare(albero del codice), in cui da ciascuno nodo il numero di rami viene emesso uguale alla base del codice (per codice binario, ad esempio, significa un passo avanti , dimettiti - ).

Esempio 1.2.2.Il codice Morse è un tipico esempio di codice binario non uniforme ... Contiene simboli e vengono utilizzati solo in due combinazioni: come singolo ( e ) o come triplo (
e
). Segnale corrispondente , viene chiamato punto e
- trattino. Simbolo utilizzato come carattere che separa punto da trattino, punto da punto e trattino da trattino. L'aggregato
usato come segno di separazione di codeword.

Shannon e Fano hanno proposto un semplice algoritmo per ottenere codici di prefisso non uniformi. Algoritmo Shannon-Fano per codice binario - il seguente. I simboli dell'alfabeto sorgente sono scritti in ordine senza aumentare le probabilità del loro verificarsi. Quindi i personaggi vengono divisi in parti in modo che le somme delle probabilità dei simboli in ciascuna di queste parti siano approssimativamente le stesse. Tutti i simboli
oh (
oh) le parti sono accreditate () come
th carattere della parola in codice. Ciascuno di
x parti (se ne contiene di più
th simbolo) sono divisi in due, se possibile, parti ugualmente probabili. La stessa regola di codifica si applica a loro. Il processo viene ripetuto fino a quando non contiene ciascuna delle parti ottenute
al simbolo. La divisione in parti con "probabilità approssimativamente uguali" non è sempre una procedura inequivocabile. Gli errori di codifica possono essere ridotti e il codice reso più efficiente passando dalla codifica carattere per carattere alla codifica delle sequenze di caratteri del messaggio allargando l'alfabeto (vedi clausola 4.2).

Esempio 1.2.3.Lascia l'alfabeto
la fonte è composta da personaggi ,
... Le probabilità dell'apparizione di simboli all'uscita della sorgente, rispettivamente, sono
,
,
,
,
e
... La procedura di Shannon-Fano per la costruzione di un codice irregolare senza ingrandire l'alfabeto della fonte è riportata in Tabella. 1.1 .

Tabella 1.1 Codifica sorgente con il metodo Shannon-Fano

		Selezione di caratteri di codice non uniforme

Sul
al quinto stadio, dividiamo l'insieme di simboli per parti: e
; sul
ohm - e
; sul
mangiare -
e
; sul
ohm - e ,e ... Ai simboli sorgente più probabili verranno assegnate parole chiave di lunghezza inferiore ... Costruito un prefisso. Lunghezza media della parola chiave (numero medio di simboli di codice per simbolo di fonte)
.

I codici anti-jam sono blocco e continuo... Nella codifica a blocchi, la sequenza di caratteri sorgente è suddivisa in segmenti. Ogni segmento corrisponde a una determinata sequenza (blocco) di simboli di codice - una parola di codice. L'insieme di parole in codice possibile con un determinato metodo di codifica costituisce un codice a blocchi. NEL uniforme (irregolare), la lunghezza del blocco è costante (variabile). I codici anti-jam sono generalmente uniformi.

I codici di blocco sono separabile e inseparabile... In codice diviso
lunghezza i personaggi possono essere divisi in base al loro scopo in informazione(portando informazioni sul messaggio) e
verifica... Velocità del codice
... Il numero totale di parole nel codice è
, e
- il numero di parole consentite. I simboli informativi e di controllo non possono essere distinti in codici inseparabili. Ad esempio, questi sono codici con peso costantee codici basati su matrici Hadamard(vedi clausola 6.3). Nel codice binario con peso costante, le parole chiave contengono lo stesso numero ... Nel codice telegrafico standard numero 3, ciascuno di essi ne contiene tre e quattro .

I codici separabili sono lineare e non lineare... In codici lineari, la somma sopra
(vedi (1.1))
x di tutte le parole in codice forma una parola in codice dello stesso codice. Si chiama il codice lineare sistematicose il primo i caratteri di uno dei suoi codici sono informativi e il resto
- verifica. Sottoclasse di codici lineari - codici ciclici(vedi p. 6.5). In essi, tutti gli insiemi formati dalla permutazione ciclica dei simboli in qualsiasi parola in codice sono parole in codice dello stesso codice. Questa proprietà semplifica la creazione di un codec, soprattutto durante il rilevamento e la correzione di singoli errori. Esempi di codici ciclici sono i codici Hamming, i codici Bose-Chowdhury-Hockingham (codici BCH) e altri. Esempio di codice binario non lineare - Codice Berger (vedi paragrafo 1.4) . In esso, i caratteri di controllo sono formati dalla notazione binaria del numero in una sequenza di simboli informativi.

La codifica e la decodifica continue vengono eseguite su una sequenza continua di simboli senza dividerla in blocchi. Tra quelli continui, il più comunemente usato codici convoluzionali(vedi clausola 6.8).

Distinguere i canali di comunicazione con indipendente e errori di raggruppamento... Di conseguenza, i codici di correzione degli errori possono essere suddivisi in classe: correzione di bug indipendenti e correzione pacchi errori. Esistono molti codici efficienti per risolvere quest'ultimo. In pratica, è più opportuno utilizzare codici che correggano errori indipendenti, insieme a interleaver(errori di decorrelazione). Quindi i simboli della parola in codice non vengono trasmessi in sequenza, ma vengono mescolati con i simboli di altre parole in codice. Se l'intervallo tra i caratteri di ciascuna parola di codice è maggiore della "memoria" del canale, gli errori all'interno di una parola diventeranno indipendenti. Ciò consente l'uso di codici che correggono errori indipendenti.

L'appendice illustra i principi di costruzione di codici e compressione dei dati sull'esempio delle reti di computer.

Teoria dei codici: studio delle proprietà dei codici e della loro idoneità al raggiungimento di un determinato obiettivo. La codifica delle informazioni è il processo di trasformazione da un modulo conveniente per l'uso diretto in un modulo conveniente per la trasmissione, l'archiviazione, l'elaborazione automatica e la protezione da accessi non autorizzati. I principali problemi della teoria dei codici includono i problemi del codice uno a uno e la complessità dell'implementazione di un canale di comunicazione in determinate condizioni. A questo proposito, la teoria della codifica considera principalmente le seguenti aree: compressione dei dati, correzione degli errori in avanti, crittografia, codifica fisica, rilevazione e correzione degli errori.

Formato

Il corso prevede 10 settimane accademiche. Per risolvere con successo la maggior parte dei compiti dai test, è sufficiente padroneggiare il materiale descritto nelle lezioni. I seminari affrontano anche problemi più complessi che possono interessare un ascoltatore che ha già familiarità con le basi.

Programma del corso

1. Codifica alfabetica. Condizioni sufficienti per la decodifica inequivocabile: uniformità, prefisso, suffisso. Riconoscimento inequivocabile: test di Markov. Stima della lunghezza di una parola decodificata in modo ambiguo.
2. Disuguaglianza tra artigianato e macmillan; l'esistenza di un prefisso con una data serie di lunghezze di parole; una conseguenza dell'universalità dei codici prefissi.
3. Codici con ridondanza minima: affermazione del problema, teorema di riduzione di Huffman.
4. Il compito di correggere e rilevare errori. Interpretazione geometrica. Tipi di errori. Metriche di Hemming e Levenshtein. Distanza codice. I principali compiti della teoria dei codici di correzione degli errori.
5. Codici di Varshamov-Tenengolts, algoritmi per la correzione di singoli errori di abbandono e inserimento di caratteri.
6. I limiti più semplici per i parametri dei codici che correggono gli errori di sostituzione: i limiti dell'imballaggio sferico, Singleton, Plotkin.
7. Incorporamento di spazi metrici. Lemma sul numero di vettori nello spazio euclideo. Confine Elijes-Bassalygo.
8. Codici lineari. Definizioni. Matrici generative e di controllo. Collegamento della distanza del codice con la matrice di parità. Confine di Varshamov-Gilbert. Codifica sistematica. Decodifica della sindrome Codici di Hamming.
9. Codice residuo. Il confine di Greismer-Solomon-Stiffler.
10. La complessità del problema di decodifica per i codici lineari: problema NCP (Problema della parola chiave più vicina).
11. Codici Reed-Solomon. Algoritmo di decodifica di Berlekamp-Welch.
12. Codici Reed-Muller: distanza del codice, algoritmo di decodifica maggioritaria.
13. Varianti di generalizzazioni della costruzione Reed-Muller. Lemma di Lipton-DeMillo-Schwarz-Zippel. Il concetto di codici geometrici algebrici.
14. Grafici di espansione. Prova probabilistica dell'esistenza di espansori. Codici basati su grafici bipartiti. Distanza del codice dei codici basati sull'espansore. Algoritmo di decodifica Sipser-Spielman.
15. Teoremi di Shannon per un modello di canale probabilistico.
16. Allegati di codici di correzione degli errori. Un protocollo randomizzato nella complessità della comunicazione. Cryptoscheme di McEliece. Insiemi omogenei (pseudo-casuali) basati su codici, le loro applicazioni alla derandomizzazione nel problema MAX-SAT.

È una branca della teoria dell'informazione che studia i modi per identificare i messaggi con segnali che li riflettono. Il compito della teoria dei codici è di abbinare la fonte di informazioni con il canale di comunicazione.

L'oggetto della codifica è l'informazione sia discreta che continua che arriva al consumatore attraverso la fonte di informazione. Il concetto di codifica significa convertire le informazioni in una forma che è conveniente per la trasmissione su un canale di comunicazione specifico.

L'operazione inversa - decodifica - consiste nel ripristinare il messaggio ricevuto dalla forma codificata a quella generalmente accettata, disponibile per il consumatore.

Esistono diverse direzioni nella teoria dei codici:

• codifica statica o efficiente;
• codifica immune al rumore;
• codici correttivi;
• codici ciclici;
• codici aritmetici.

Con l'avvento dei sistemi di controllo, in particolare dei computer, il ruolo della codifica è notevolmente aumentato e modificato, poiché senza codifica il trasferimento di informazioni è impossibile. Di recente, in connessione con lo sviluppo di sistemi di telecomunicazione e l'uso diffuso della tecnologia informatica per l'elaborazione e la memorizzazione di informazioni, è sorta una nuova area di conoscenza: la sicurezza delle informazioni.

La codifica è un modo universale di visualizzare informazioni durante la sua memorizzazione, elaborazione e trasmissione sotto forma di un sistema di corrispondenze tra segnali ed elementi di messaggio, con la quale questi elementi possono essere riparati.

Il codice è una regola per la trasformazione inequivocabile di un messaggio da una forma simbolica di un messaggio a un altro, di solito senza alcuna perdita di informazioni.

Se tutte le parole di codice hanno la stessa lunghezza, il codice viene chiamato uniforme o blocco.

Per alfabeto astratto intendiamo un insieme discreto di simboli ordinati.

Codifica alfabetica. Alfabetico, ad es. lettera per lettera, la codifica può essere impostata dalla tabella dei codici. Il codice di conversione effettivo è una sostituzione.

Dove l'alfabeto A, l'insieme di parole composto nell'alfabeto B. L'insieme di codici lettera è chiamato insieme di codici elementari. La codifica alfabetica può essere utilizzata per qualsiasi set di messaggi.

L'elaborazione dei dati informatici si basa sull'uso del codice binario. Questo metodo di codifica universale è adatto a qualsiasi dato, indipendentemente dalla sua origine e contenuto.

Codifica del testo

I testi sono sequenze di caratteri inclusi in un certo alfabeto. La codifica del testo si riduce alla codifica binaria dell'alfabeto sulla base della quale è costruita. La codifica byte più comunemente usata dell'alfabeto. In questo caso, la cardinalità massima dell'alfabeto è di 256 caratteri. Un tale alfabeto può contenere due serie di caratteri alfabetici (ad esempio, russo e latino), numeri, punteggiatura e segni matematici, uno spazio e un piccolo numero di caratteri aggiuntivi. Un esempio di tale alfabeto è il codice ASCII.

Tuttavia, l'insieme limitato di codici a 256 caratteri non soddisfa più le crescenti esigenze della comunicazione internazionale. Il sistema universale di codifica dei caratteri a 16 bit UNICODE sta guadagnando popolarità.

La potenza dell'alfabeto nel sistema di codifica UNICODE è 216 \u003d 65 536 codici diversi, di cui 63 484 codici corrispondono ai caratteri della maggior parte degli alfabeti, e i restanti 2048 codici sono divisi a metà e formano una tabella di 1024 colonne x 1024 linee. Ci sono oltre un milione di celle in questa tabella che possono contenere oltre un milione di caratteri diversi. Questi sono simboli di lingue "morte", nonché simboli che non hanno contenuto lessicale, puntatori, segni, ecc. Per scrivere questi caratteri extra è necessaria una coppia di parole a 16 bit (16 bit per il numero di riga e 16 bit per il numero di colonna).

Pertanto, il sistema UNICODE è un sistema di codifica universale per tutti i simboli dei sistemi di scrittura nazionali e ha la capacità di espandersi in modo significativo.

Codifica delle immagini

Disegni, immagini, foto sono codificati in formato raster... In questa vista, ogni immagine è una tabella rettangolare di punti colorati. Il colore e la luminosità di ogni singolo punto sono espressi in forma numerica, che consente di utilizzare il codice binario per rappresentare dati grafici.

È consuetudine rappresentare immagini in bianco e nero in scala di grigi, per questo viene utilizzato il modello GreyScale. Se la luminanza di un punto è codificata in un byte, è possibile utilizzare 256 toni di grigio diversi. Questa precisione è coerente con la sensibilità dell'occhio umano e le capacità della tecnologia di stampa.

Quando si codificano le immagini a colori, viene applicato il principio di decomposizione del colore in componenti; per questo viene utilizzato il modello RGB. L'immagine a colori sullo schermo si ottiene mescolando tre colori di base: rosso (rosso, R), blu (blu, B) e verde (verde, G).

Ogni pixel sullo schermo è composto da tre elementi ravvicinati che si illuminano con questi colori.

I display a colori che utilizzano questo principio sono chiamati monitor RGB.

Un codice colore pixel contiene informazioni sulla proporzione di ciascun colore di base.

schema di formazione del colore

Se tutti e tre i componenti hanno la stessa intensità (luminosità), è possibile ottenere 8 colori diversi dalle loro combinazioni (23):

			Marrone

Formazione di colori con profondità colore a 24 bit:

Maggiore è la profondità del colore, più ampia è la gamma di colori disponibili e più accurata è la loro rappresentazione nell'immagine digitalizzata. Un pixel con una profondità di bit uguale a uno ha solo 2 (nella prima potenza) possibili stati - due colori: bianco o nero. Un pixel con una profondità di 8 bit ha 28 o 256 possibili valori di colore. Un pixel con una profondità di 24 unità ha 224 gradi) o 16,7 milioni di valori possibili. Si ritiene che le immagini a 24 bit contenenti 16,7 milioni di colori riproducano accuratamente i colori del mondo che ci circonda. In genere, la risoluzione in bit è specificata nell'intervallo da 1 a 48 bit / pixel.

Quando si stampa su carta, viene utilizzato un modello di colore leggermente diverso: se il monitor emette luce, la tinta è stata ottenuta a seguito dell'aggiunta di colori, quindi le vernici assorbono la luce, i colori vengono sottratti. Pertanto, le vernici ciano (C), magenta (M) e giallo (Giallo, Y) vengono utilizzate come principali. Inoltre, a causa dell'imperfezione dei coloranti, di solito viene aggiunto un quarto: nero (nero, K). Per memorizzare informazioni su ogni colore, e in questo caso, viene utilizzato più spesso 1 byte. Questo sistema di codifica si chiama CMYK.

Una rappresentazione cromatica più grossolana utilizza un numero inferiore di bit. Ad esempio, la codifica della grafica a colori con numeri a 16 bit si chiama High Color. In questo caso, a ciascun colore vengono assegnate cinque cifre.

Codifica audio e video

Le ultime tecniche per lavorare con le informazioni sonore sono arrivate alla tecnologia informatica. Un metodo di codifica analitica applicabile a qualsiasi segnale audio si basa sulla conversione da analogico a digitale. Il segnale analogico originale è rappresentato come una sequenza di segnali digitali registrati in codice binario. Il bit di conversione determina la quantità di dati corrispondente a un singolo segnale digitale. Durante la riproduzione audio, eseguire la conversione inversa da digitale ad analogico.

Questo metodo di codifica contiene un errore, quindi il segnale riprodotto è leggermente diverso dall'originale.

Il metodo di codifica della sintesi tabulare è applicabile solo a un brano musicale. Campioni (campioni) di suoni di vari strumenti musicali sono memorizzati in tabelle preparate. I codici numerici definiscono lo strumento, la nota e la durata.

Quando si codifica un segnale video, è necessario registrare una sequenza di immagini (fotogrammi) e suoni (traccia audio). Il formato di registrazione video consente di includere entrambi i flussi di dati in una sequenza digitale.