Quando e perché è nata la teoria dei codici. Teoria della codifica. Tipi di codifica. Codifica. Concetti basilari

Teoria dei codici: lo studio delle proprietà dei codici e della loro idoneità al raggiungimento di un determinato obiettivo. La codificazione delle informazioni è il processo della loro trasformazione da un modulo conveniente per l'uso diretto in un modulo conveniente per la trasmissione, l'archiviazione, l'elaborazione automatica e la conservazione da accessi non autorizzati. I principali problemi della teoria della codifica includono i problemi della codifica 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, rilevamento e correzione degli errori.

Formato

Il corso si compone di 10 settimane accademiche. Per risolvere con successo la maggior parte dei compiti dei test, è sufficiente padroneggiare il materiale raccontato nelle lezioni. I seminari trattano anche compiti più complessi che possono interessare un ascoltatore che abbia già familiarità con le basi.

Programma del corso

1. Codifica alfabetica. Condizioni sufficienti per una decodifica univoca: uniformità, prefisso, suffisso. Riconoscimento dell'unicità: il criterio di Markov. Una stima della lunghezza di una parola ambiguamente decodificabile.
2. Disuguaglianza di Kraft-McMillan; l'esistenza di un codice prefisso con un dato insieme di lunghezze di parole; corollario dell'universalità dei codici prefissi.
3. Codici di ridondanza minima: affermazione del problema, teorema di riduzione di Huffman.
4. Il compito di correggere e rilevare gli errori. Interpretazione geometrica. Tipi di errore. Metriche di Hamming e Levenshtein. codice distanza. Principali compiti della teoria dei codici di correzione degli errori.
5. Codici Varshamov-Tenengolts, algoritmi per la correzione di singoli errori di eliminazione e inserimento di simboli.
6. I limiti più semplici per i parametri dei codici di correzione degli errori di sostituzione: limiti di impacchettamento sferico, limiti di Singleton, limiti di Plotkin.
7. Incorporamento di spazi metrici. Lemma sul numero di vettori nello spazio euclideo. Confine Elias-Bassalygo.
8. Codici di linea. Definizioni. Generazione e controllo di matrici. Relazione tra la distanza del codice e la matrice di controllo. Confine Varshamov-Gilbert. codifica sistematica. Decodifica della sindrome. Codici di Hamming.
9. Codice rimanente. Confine Greismer-Solomon-Stiffler.
10. La complessità del problema della decodifica dei codici lineari: problema NCP (problema sulla parola di codice più vicina).
11. Codici Reed-Solomon. Algoritmo di decodifica Berlekamp-Welch.
12. Codici Reed-Muller: distanza del codice, algoritmo di decodifica della maggioranza.
13. Varianti di generalizzazioni della costruzione di Reed-Muller. Lemma di Lipton-DeMillo-Schwartz-Zippel. Il concetto di codici algebrogeometrici.
14. Grafici di estensione. Dimostrazione probabilistica dell'esistenza di espansori. Codici basati su grafi bipartiti. Codice distanza dei codici basati su espansioni. Algoritmo di decodifica Sipser-Spielman.
15. Teoremi di Shannon per un modello di canale probabilistico.
16. Applicazioni di codice di correzione degli errori. Protocollo randomizzato nella complessità della comunicazione. Schema crittografico McEliece. Insiemi omogenei (pseudo-casuali) basati su codici, loro applicazioni alla derandomizzazione nel problema MAX-SAT.

Da Wikipedia, l'enciclopedia libera

teoria dei codici- la scienza delle proprietà dei codici e della loro idoneità al raggiungimento dell'obiettivo.

Informazione Generale

La codifica è il processo di conversione dei dati da un modulo conveniente per l'uso diretto in un modulo conveniente per la trasmissione, l'archiviazione, l'elaborazione automatica e la conservazione da accessi non autorizzati. I principali problemi della teoria della codifica includono i problemi della codifica uno-a-uno e la complessità dell'implementazione di un canale di comunicazione in determinate condizioni:86. A questo proposito, la teoria dei codici considera principalmente le seguenti aree:18:

Compressione dati

Correzione degli errori in avanti

Crittografia

Crittografia (da altro greco. κρυπτός - nascosto e γράφω - scrivo), questo è un campo di conoscenza sui metodi per garantire la riservatezza (l'impossibilità di leggere le informazioni a estranei), l'integrità dei dati (l'impossibilità di modificare in modo impercettibile le informazioni), l'autenticazione (autenticazione della paternità o di altre proprietà di un oggetto), così come l'impossibilità di rifiutare la paternità

04/04/2006 Leonid Chernyak Categoria: Tecnologie

"Sistemi aperti" La creazione di computer sarebbe impossibile se, contemporaneamente alla loro comparsa, non fosse stata creata la teoria della codifica dei segnali.La 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, contemporaneamente alla loro comparsa, non fosse stata creata la teoria della codifica dei segnali.

La teoria dei codici è una di quelle aree della matematica che ha influenzato notevolmente lo sviluppo dell'informatica. Il suo scopo si estende alla trasmissione di dati su canali reali (o rumorosi) e l'oggetto è garantire la correttezza delle informazioni trasmesse. In altre parole, studia il modo migliore per imballare i dati in modo che, dopo la segnalazione, le informazioni utili possano essere estratte dai dati in modo affidabile e semplice. A volte la teoria della codifica viene confusa con la crittografia, ma questo non è vero: la crittografia risolve il problema inverso, il suo obiettivo è rendere difficile l'estrazione di informazioni dai dati.

La necessità di codificare i dati è stata incontrata per la prima volta più di centocinquanta 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 dei telegrammi. Il problema è stato aggravato dalla posa di cavi transatlantici. Dal 1845 sono entrati in uso libri di codici speciali; con il loro aiuto, i telegrafisti hanno "compresso" manualmente i messaggi, sostituendo sequenze di parole comuni con codici più brevi. Parallelamente, per verificare la correttezza del trasferimento, si iniziò ad utilizzare la parità, metodo che serviva anche per verificare la correttezza dell'input delle schede perforate nei computer di prima e seconda generazione. Per fare ciò, una carta appositamente preparata con un checksum è stata inserita nell'ultimo mazzo di input. Se il dispositivo di input non era molto affidabile (o il deck era troppo grande), potrebbe verificarsi un errore. Per correggerlo, la procedura di inserimento è stata ripetuta fino a quando il checksum calcolato non corrispondeva all'importo memorizzato sulla carta. Non solo questo schema è scomodo, ma manca anche di doppi falli. Con lo sviluppo dei canali di comunicazione è stato necessario un meccanismo di controllo più efficace.

La prima soluzione teorica al problema della trasmissione di dati su canali rumorosi è stata proposta da Claude Shannon, il fondatore della teoria dell'informazione statistica. Shannon era una star del suo tempo, faceva parte dell'élite accademica statunitense. Come studente laureato alla 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 ai Bell Labs, Shannon scrisse "A Mathematical Theory of Message Transmission" (1948), dove mostrò che se la larghezza di banda del canale è maggiore dell'entropia della sorgente del messaggio, allora il messaggio può essere codificato in modo che sarà trasmessa senza indebito ritardo. Questa conclusione è contenuta in uno dei teoremi dimostrati da Shannon, il suo significato si riduce al fatto che se c'è un canale con banda sufficiente, un messaggio può essere trasmesso con alcuni ritardi temporali. Inoltre, ha mostrato la possibilità teorica di una trasmissione affidabile in presenza di rumore nel canale. La formula C = W log ((P+N)/N), scolpita su un modesto monumento a Shannon, installato nella sua città natale nel Michigan, viene confrontata in valore con la formula di Albert Einstein E = mc 2 .

Il lavoro di Shannon ha dato origine a molte ulteriori ricerche nel campo della teoria dell'informazione, ma non hanno avuto applicazioni ingegneristiche pratiche. Il passaggio dalla teoria alla pratica è stato reso possibile dagli sforzi di Richard Hamming, collega di Shannon ai Bell Labs, che è diventato famoso per aver scoperto una classe di codici che è stata chiamata "codici di Hamming". C'è una leggenda secondo cui l'inconveniente di lavorare con le schede perforate sulla calcolatrice a relè Bell Model V a metà degli anni '40 ha spinto l'invenzione dei loro codici Hamming. Gli veniva concesso il tempo di lavorare sulla macchina nei fine settimana quando non c'erano operatori e lui stesso doveva armeggiare con l'input. Comunque sia, Hamming ha proposto codici in grado di correggere gli 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 divennero la prova di come le possibilità indicate dai teoremi di Shannon potessero essere realizzate nella pratica.

Hamming pubblicò il suo articolo nel 1950, sebbene i rapporti interni facciano risalire la sua teoria della codifica al 1947. Pertanto, alcuni credono che Hamming, non Shannon, dovrebbe essere considerato il padre della teoria dei codici. Tuttavia, nella storia della tecnologia è inutile cercare il primo.

È solo certo che fu Hamming a proporre per primo i "codici di correzione degli errori" (Error-Correcting Code, ECC). Le moderne modifiche di questi codici sono utilizzate in tutti i sistemi di archiviazione dati e per lo scambio tra il processore e la RAM. Una delle loro varianti, i codici Reed-Solomon, sono utilizzati nei CD, consentendo di riprodurre le registrazioni senza scricchiolii e rumori che potrebbero causare graffi e particelle di polvere. Esistono molte versioni di codici basati su Hamming, differiscono negli algoritmi di codifica e nel numero di bit di controllo. Tali codici hanno acquisito un significato speciale in connessione con lo sviluppo delle comunicazioni nello spazio profondo con stazioni interplanetarie, ad esempio ci sono codici Reed-Muller, dove ci sono 32 bit di controllo per sette bit di informazione o 26 per sei.

Tra gli ultimi codici ECC, vanno citati i codici LDPC (Low-Density Parity-check Code). In effetti, sono conosciuti da circa trent'anni, ma un interesse particolare per loro è stato scoperto proprio negli ultimi anni, quando ha iniziato a svilupparsi la televisione ad alta definizione. I codici LDPC non sono affidabili al 100%, ma il tasso di errore può essere regolato al livello desiderato, sfruttando al massimo la larghezza di banda del canale. I "Codici Turbo" sono vicini a loro, sono efficaci quando si lavora con oggetti situati nello spazio profondo e con larghezza di banda del canale limitata.

Il nome di Vladimir Alexandrovich Kotelnikov è saldamente iscritto nella storia della teoria dei codici. Nel 1933, in "Materials on Radio Communications for the First All-Union Congress on the Technical Reconstruction of Communications", pubblicò l'opera "Sulla larghezza di banda? Ether? e? fili? Il nome di Kotelnikov, da pari a pari, è incluso nel nome di uno dei più importanti teoremi della teoria dei codici. Questo teorema definisce le condizioni in cui il segnale trasmesso può essere ripristinato senza perdita di informazioni.

Questo teorema è stato chiamato in vari modi, incluso il "teorema WKS" (l'abbreviazione WKS è tratta da Whittaker, Kotelnikov, Shannon). In alcune fonti vengono utilizzati sia il teorema di campionamento di Nyquist-Shannon che il teorema di campionamento di Whittaker-Shannon e nei libri di testo universitari nazionali si trova più spesso 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 contribuito nel 1915. Nel 1920, il giapponese Kinnosuki Ogura pubblicò correzioni alla ricerca di Whittaker e nel 1928 l'americano Harry Nyquist perfezionò i principi della digitalizzazione e della ricostruzione del segnale analogico.

Claude Shannon(1916 - 2001) fin dai suoi 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, presso il quale si laureò nel 1940, conseguendo 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 sfociarono nella teoria dell'informazione. Nel 1948, Shannon pubblicò l'articolo "Mathematical Theory of Communication", in cui furono formulate le idee di base dello scienziato, in particolare la determinazione della quantità di informazioni attraverso l'entropia, e propose anche un'unità di informazione che determina la scelta di due opzioni altrettanto probabili, cioè quella che poi è stata chiamata un po'. Nel 1957-1961, Shannon pubblicò lavori che dimostrarono il teorema del throughput per i canali di comunicazione rumorosi, che ora porta il suo nome. Nel 1957, Shannon divenne professore al Massachusetts Institute of Technology, da dove si ritirò 21 anni dopo. In un "meritato riposo" Shannon si dedicò completamente alla sua antica passione per la giocoleria. Ha costruito diverse macchine da giocoleria e ha persino creato una teoria generale della giocoleria.

Riccardo Hamming(1915 - 1998) ha iniziato la sua formazione presso l'Università di Chicago, dove ha conseguito una laurea nel 1937. Nel 1939 ha conseguito un master presso l'Università del Nebraska e un dottorato in matematica presso l'Università dell'Illinois. Nel 1945, Hamming iniziò a lavorare al Progetto Manhattan, un massiccio sforzo di ricerca del governo per costruire la bomba atomica. Nel 1946, Hamming si unì ai Bell Telephone Laboratories, dove lavorò con Claude Shannon. Nel 1976, Hamming ha ricevuto una cattedra presso la Naval Postgraduate School di Monterey, in California.

L'opera che lo rese famoso, uno studio fondamentale sul rilevamento degli errori e sui codici di correzione, fu pubblicata da Hamming nel 1950. Nel 1956, è stato coinvolto nello sviluppo di 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 contributi di Hamming nel campo dell'informatica, l'IEEE ha istituito una Distinguished Service Medal for Computer Science and Systems Theory a lui intitolata.

Vladimir Kotelnikov(1908 - 2005) nel 1926 entrò nel Dipartimento di ingegneria elettrica della Scuola tecnica superiore di Mosca intitolata a NE Bauman (MVTU), ma si laureò al Moscow Power Engineering Institute (MPEI), che si separò dall'MVTU come istituto indipendente . Durante i suoi studi post-laurea (1931-1933), Kotelnikov formulò e dimostrò matematicamente con precisione il "teorema di riferimento", che in seguito prese il suo nome. Dopo essersi diplomato alla scuola di specializzazione nel 1933, Kotelnikov, continuando a insegnare all'Istituto di ingegneria energetica di Mosca, andò a lavorare presso l'Istituto centrale di ricerca delle comunicazioni (TsNIIS). Nel 1941, V. A. Kotelnikov formulò una posizione chiara sui requisiti che un sistema matematicamente indecifrabile dovrebbe soddisfare e fu data una prova dell'impossibilità di decifrarlo. Nel 1944 Kotelnikov assunse la carica di professore, preside della facoltà di ingegneria radiofonica dell'MPEI, dove lavorò 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

Teoria della codifica. Tipi di codifica Concetti di base della teoria della codifica In precedenza, gli strumenti di codifica svolgevano un ruolo ausiliario e non erano considerati un argomento separato di studio matematico, ma con l'avvento dei computer la situazione è cambiata radicalmente. La codifica permea letteralmente la tecnologia dell'informazione ed è una questione centrale nella risoluzione di una varietà di compiti di programmazione (praticamente tutti): ۞ rappresentare dati di natura arbitraria (ad esempio numeri, testo, grafica) nella memoria del computer; ۞ protezione delle informazioni da accessi non autorizzati; ۞ Garantire l'immunità ai disturbi durante la trasmissione dei dati attraverso i canali di comunicazione; ۞ compressione delle informazioni nei database. La teoria dei codici è una branca della teoria dell'informazione che studia come i messaggi possono essere identificati con i segnali che li rappresentano. Compito: coordinare la fonte di informazioni con il canale di comunicazione. Oggetto: informazione discreta o continua fornita al consumatore attraverso una fonte di informazione. La codifica è la trasformazione delle informazioni in una formula conveniente per la trasmissione su uno specifico canale di comunicazione. Un esempio di codifica in matematica è il metodo delle coordinate introdotto da Cartesio, che consente di studiare oggetti geometrici attraverso la loro espressione analitica sotto forma di numeri, lettere e loro combinazioni - formule. Il concetto di codifica significa la trasformazione dell'informazione in una forma conveniente per la trasmissione su uno specifico canale di comunicazione. La decodifica è il ripristino del messaggio ricevuto dal modulo codificato in un modulo accessibile al consumatore.

Argomento 5.2. Codifica alfabetica Nel caso generale, il problema della codifica può essere rappresentato come segue. Siano dati due alfabeti A e B, costituiti da un numero finito di caratteri: e. Gli elementi dell'alfabeto sono chiamati lettere. Un insieme ordinato nell'alfabeto A sarà chiamato parola, dove n =l()=| |. , il numero n indica il numero di lettere nella parola ed è chiamato lunghezza della parola, La parola vuota è indicata: Per la parola, la lettera a1, è chiamata inizio, o prefisso, della parola, la lettera an è la fine, o suffisso, della parola. e le parole possono essere combinate. Per fare ciò, il prefisso della seconda parola deve seguire immediatamente il suffisso della prima, mentre nella nuova parola perdono naturalmente il loro status, a meno che una delle parole non sia vuota. Si denota il composto di parole e, inoltre si denota il composto di n parole identiche. L'insieme di tutte le parole non vuote dell'alfabeto A è indicato da A*: l'insieme A è chiamato alfabeto dei messaggi e l'insieme B è chiamato alfabeto di codifica. L'insieme delle parole composte dall'alfabeto B sarà indicato con B*.

Indichiamo con F la mappatura delle parole dall'alfabeto A all'alfabeto B. Quindi la parola è chiamata il codice della parola. La codifica è un modo universale per visualizzare le informazioni durante la loro memorizzazione, trasmissione ed elaborazione sotto forma di un sistema di corrispondenze tra elementi di messaggio e segnali con cui questi elementi possono essere riparati. Pertanto, un codice è una regola per la trasformazione inequivocabile (cioè, la funzione) di un messaggio da una forma di rappresentazione simbolica (l'alfabeto originale A) a un'altra (l'alfabeto oggetto B), di solito senza alcuna perdita di informazioni. Il processo di conversione delle parole F: A* B*→ dell'alfabeto originale A nell'alfabeto B è chiamato codifica delle informazioni. Il processo di riconversione di una parola è chiamato decodifica. Pertanto, la decodifica è l'inverso di F, cioè F1. in una parola Poiché per qualsiasi codifica deve essere eseguita un'operazione di decodifica, la mappatura deve essere invertibile (una biiezione). Se |B|= m, allora F è chiamato codifica mimica, il caso più comune è B = (0, 1) codifica binaria. È questo il caso che viene considerato di seguito. Se tutte le parole del codice hanno la stessa lunghezza, il codice viene chiamato uniforme o blocco. La codifica alfabetica (o lettera per lettera) può essere specificata da una tabella di codici. Alcune sostituzioni serviranno come codice o funzione di codifica. Poi dove, . Tale codifica lettera per lettera è indicata come un insieme di codici elementari. La codifica alfabetica può essere utilizzata per qualsiasi insieme di messaggi. Pertanto la codifica alfabetica è la più semplice e può sempre essere inserita su alfabeti non vuoti. . Molti codici di lettere

ESEMPIO Si danno gli alfabeti A = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) B = (0, 1). Quindi la tabella di codifica può essere una sostituzione: . Questa è una codifica BCD, è uno a uno e quindi decodificabile. Tuttavia, lo schema non è uno a uno. Ad esempio, l'insieme di sei 111111 può corrispondere sia alla parola 333 e 77, sia a 111111, 137, 3311 o 7111 più qualsiasi permutazione. Uno schema di codifica alfabetico è chiamato prefisso se il codice elementare di una lettera non è un prefisso del codice elementare di un'altra lettera. Uno schema di codifica alfabetico si dice separabile se una parola composta da codici elementari si decompone in codici elementari in un modo univoco. La codifica alfabetica con uno schema separabile consente la decodifica. Si può dimostrare che lo schema del prefisso è separabile. Affinché uno schema di codifica alfabetico sia separabile, le lunghezze dei codici elementari devono soddisfare una relazione nota come disuguaglianza di Macmillan. La disuguaglianza di Macmillan Se lo schema di codifica alfabetico

è separabile, vale la seguente disuguaglianza. il codice elementare della lettera a è il prefisso del codice elementare della lettera b. Argomento 5.3. Codifica di ridondanza minima In pratica è importante che i codici dei messaggi siano il più brevi possibile. La codifica alfabetica è adatta a qualsiasi messaggio, ma se non si sa nulla dell'insieme di tutte le parole dell'alfabeto A, allora è difficile formulare con precisione il problema di ottimizzazione. Tuttavia, in pratica sono spesso disponibili informazioni aggiuntive. Ad esempio, per i messaggi presentati in linguaggio naturale, tali informazioni aggiuntive possono essere la distribuzione di probabilità dell'occorrenza delle lettere nel messaggio. Allora il problema della costruzione di un codice ottimo acquisisce un'esatta formulazione matematica e una soluzione rigorosa.

Sia fornito uno schema di codifica alfabetico separabile. Quindi anche qualsiasi schema in cui l'insieme ordinato è una permutazione dell'insieme ordinato sarà separabile. In questo caso, se le lunghezze dell'insieme elementare di codici sono uguali, la loro permutazione nello schema non influisce sulla lunghezza del messaggio codificato. Nel caso in cui le lunghezze dei codici elementari siano diverse, la lunghezza del codice del messaggio dipende direttamente da quali codici elementari corrispondono a quali lettere e dalla composizione delle lettere nel messaggio. Dato un messaggio specifico e uno schema di codifica specifico, è possibile scegliere una tale permutazione di codici, in cui la lunghezza del codice del messaggio sarà minima. Un algoritmo per l'assegnazione di codici elementari, in cui la lunghezza di un codice di messaggio fisso S sarà minima per uno schema fisso: ۞ ordina le lettere in ordine decrescente del numero di occorrenze; ۞ ordina i codici elementari in ordine crescente di lunghezza; ۞ inserire i codici secondo le lettere nell'ordine prescritto. Sia dato l'alfabeto e le probabilità di occorrenza delle lettere nel messaggio:

Dove pi è la probabilità di apparizione della lettera ai, e le lettere con probabilità zero di apparire nel messaggio sono escluse e le lettere sono ordinate in ordine decrescente della probabilità del loro messaggio di occorrenza, che è designato e definito come ESEMPIO. Per uno schema di codifica alfabetico separabile A=(a,b), B=(0,1), sotto la distribuzione di probabilità, il costo di codifica è, e sotto la distribuzione di probabilità, il costo di codifica è

Argomento 5.4. Codifica di Huffman Questo algoritmo è stato inventato nel 1952 da David Huffman. Argomento 5.5. Codifica aritmetica Come nell'algoritmo di Huffman, tutto inizia con una tabella di elementi e le relative probabilità. Supponiamo che l'alfabeto di input sia composto da soli tre elementi: a1, a2 e a3, e allo stesso tempo P(a1) = 1/2 P(a2) = 1/3 P(a3) = 1/6 Supponiamo anche di aver bisogno per codificare la sequenza a1, a1, a2, a3 . Dividiamo l'intervallo , dove p è un numero fisso, 0<р<(r­1)/2r, а "мощностная" граница где Tr(p)=­p logr(p/(r­ 1))­(1­р)logr(l­ p), существенно улучшена. Имеется предположение, чт о верхняя граница полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir(п,[ рп])~пТ r(2р).Доказательство или опровержение этого предположения ­ одна из центральны х задач теории кодирования. Большинство конструкций помехоустойчивых кодов являются эффективными, когда длин а пкода достаточновелика. В связи с этим особое значение приобретают вопросы, связанны е со сложностью устройств,осуществляющих кодирование и декодирование (кодера и деко дера). Ограничения на допустимый типдекодера или его сложность могут приводить к увел ичению избыточности, необходимой для обеспечениязаданной помехоустойчивости. Напр., минимальная избыточность кода в В n 2, для к­рого существует декодер,состоящий из регист

ra shift e un elemento maggioritario e correggendo un errore, ha un ordine (confronta con (2)). Come matematico i modelli di codificatore e decodificatore sono generalmente considerati da un circuito di elementi funzionali e la complessità è intesa come il numero di elementi nel circuito. Per classi note di codici di correzione degli errori, è stato fatto uno studio di possibili algoritmi per K. e D. e sono stati ottenuti limiti superiori sulla complessità dell'encoder e del decoder. Si trovano anche alcune relazioni tra la velocità di codifica, l'immunità al rumore della codifica e la complessità del decodificatore (vedi ). Un'altra direzione di ricerca nella teoria dei codici è legata al fatto che molti risultati (ad esempio il teorema di Shannon e la (3)) non sono "costruttivi", ma sono teoremi sull'esistenza di sequenze infinite di codici (Kn). a riguardo, si stanno compiendo sforzi Per provare questi risultati nella classe di tali sequenze di codici (Kn), per kp esiste una macchina di Turing che riconosce che una parola arbitraria di lunghezza l appartiene ad un insieme nel tempo che ha un lento ordine di crescita rispetto a l (es. llog l). Alcune nuove costruzioni e metodi per la derivazione dei limiti sviluppati nella teoria dei codici hanno portato a progressi significativi in ​​questioni che a prima vista sono molto lontane dai tradizionali problemi della teoria dei codici. Qui dobbiamo evidenziare l'uso del codice massimo con la correzione di un errore nel metodo ottimale sintomo-ottimo per realizzare le funzioni dell'algebra della logica mediante circuiti di contatto; il miglioramento fondamentale del limite superiore per la densità di impaccamento di un spazio euclideo ridimensionale per sfere uguali; sull'uso della disuguaglianza (1) nella stima della complessità dell'implementazione mediante formule di una classe di funzioni dell'algebra della logica. Le idee ei risultati della teoria dei codici trovano il loro ulteriore sviluppo nei problemi di sintesi di circuiti autocorrettivi e circuiti affidabili da elementi inaffidabili. Lett.: Shannon K., Opere di teoria dell'informazione e cibernetica, trad. dall'inglese, M., 1963; Berlekamp E., Teoria algebrica dei codici, trad. dall'inglese, M., 1971; Peterson, W., Weldon, E., Codici di correzione degli errori, trad. dall'inglese, 2a ed., M., 1976; Discrete Mathematics and Mathematical Questions of Cybernetics, vol.1, M., 1974, sezione 5; Bassalygo L.A., Zyablov V.V., Pinsker M.S., "Problemi di trasmissione delle informazioni", 1977, vol.13, n.3, p. 517; [In] VM Sidelnikov, "Mat. Sat.", 1974, v. 95, c. 1, pag. 148 58. V. I. Levenshtein.

Enciclopedia matematica. - M.: Enciclopedia sovietica. I. M. Vinogradov. 1977-1985.  CODIFICA ALFABETICA  SPAZIO COEUCLIDANO Vedi anche in altri dizionari:  DECODING - vedi Coding and Decoding ... Enciclopedia della Matematica  Coding Audio - Questo articolo dovrebbe essere wikiified. Per favore, formattalo secondo le regole per la formattazione degli articoli. La base della codifica del suono utilizzando un PC è il processo di conversione delle vibrazioni dell'aria in vibrazioni elettriche ... Immagini del codice Wikipedia), eseguito secondo la definizione. regole, la totalità di k ryh naz. cifra K., ... ... Enciclopedia filosofica  CODIFICA DELLE INFORMAZIONI - stabilire una corrispondenza tra elementi del messaggio e segnali, con l'aiuto del quale questi elementi possono essere corretti. Sia B un insieme di elementi del messaggio, A un alfabeto con simboli, Sia chiamata una sequenza finita di simboli. in una parola in ... ... Enciclopedia fisica  CODIFICA OTTIMALE - (in psicologia ingegneristica) (ing. codifica ottimale) la creazione di codici che garantiscono la massima velocità e affidabilità di ricezione ed elaborazione di informazioni su un oggetto controllato da un operatore umano (vedi Ricezione informazioni, Decodifica). Il problema del K. o. ... ... Grande enciclopedia psicologica  DECODING (in engineering psicologia) - (decodifica in inglese) l'operazione finale del processo di ricezione delle informazioni da parte di un operatore umano, consistente nella ricrittografia dei parametri caratterizzanti lo stato dell'oggetto di controllo, e traducendoli nell'immagine dell'oggetto controllato ( vedi Coding ... ... Grande enciclopedia psicologica

 Decodifica - ripristino di un messaggio codificato dai segnali trasmessi e ricevuti (vedi Codifica) ... Dizionario di Economia e Matematica  CODIFICA - CODIFICA. Una delle fasi della generazione del parlato, mentre la "decodifica" è la ricezione e l'interpretazione, il processo di comprensione di un messaggio vocale. Vedi psicolinguistica... Un nuovo dizionario di termini e concetti metodologici (teoria e pratica dell'insegnamento delle lingue)  CODING - (codifica inglese). 1. Trasformazione di un segnale da una forma di energia a un'altra 2. Trasformazione di un sistema di segnali o segni in altri, spesso chiamato anche "transcodifica", "cambio di codice" (per discorso, "traduzione"). 3. K. (mnemonico) ... ... Grande enciclopedia psicologica  Decodifica - Questo articolo riguarda il codice nella teoria dell'informazione, per altri significati di questa parola, vedere codice (disambiguazione). Il codice è una regola (algoritmo) per abbinare ogni messaggio specifico a una combinazione di simboli (caratteri) (o segnali) rigorosamente definita. Chiamato anche codice... ... Codifica ottimale Lo stesso messaggio può essere codificato in diversi modi. Un codice codificato in modo ottimale è quello in cui viene impiegato il tempo minimo per la trasmissione del messaggio. Se la trasmissione di ogni carattere elementare (0 o 1) richiede lo stesso tempo, allora il codice ottimale sarà quello che avrà la lunghezza minima possibile. Esempio 1. Sia una variabile casuale X(x1,x2,x3,x4,x5,x6,x7,x8) avente otto stati con una distribuzione di probabilità Per codificare un alfabeto di otto lettere con un codice binario uniforme, abbiamo bisogno di tre caratteri: questo 000, 001, 010, 011, 100, 101, 110, 111 Per rispondere se questo codice è valido o meno, è necessario confrontarlo con il valore ottimale, ovvero determinare l'entropia

Determinata la ridondanza L con la formula L=1H/H0=12,75/3=0,084, vediamo che è possibile ridurre la lunghezza del codice dell'8,4%. La domanda sorge spontanea: è possibile comporre un codice in cui ci saranno, in media, meno caratteri elementari per lettera. Tali codici esistono. Questi sono i codici ShannonFano e Huffman. Il principio di costruzione dei codici ottimali: 1. Ogni carattere elementare deve portare la massima quantità di informazioni, per questo è necessario che i caratteri elementari (0 e 1) nel testo codificato compaiano in media con la stessa frequenza. L'entropia in questo caso sarà massima. 2. È necessario che alle lettere dell'alfabeto primario, che hanno una probabilità maggiore, siano assegnate parole in codice più brevi dell'alfabeto secondario.

Per analizzare le diverse fonti di informazione, nonché i canali della loro trasmissione, è necessario disporre di una misura quantitativa che consenta di stimare la quantità di informazioni contenute nel messaggio e veicolate dal segnale. Tale misura fu introdotta nel 1946 dallo scienziato americano C. Shannon.

Inoltre, assumiamo che la fonte dell'informazione sia discreta, emettendo una sequenza di messaggi elementari (i,), ciascuno dei quali è selezionato da un insieme discreto (alfabeto) a, a 2 ,...,d A; aè il volume dell'alfabeto della fonte di informazione.

Ogni messaggio elementare contiene determinate informazioni come insieme di informazioni (nell'esempio in esame) sullo stato della fonte di informazioni in questione. Per quantificare la misura di questa informazione, il suo contenuto semantico, così come il grado di importanza di questa informazione per il suo destinatario, non è importante. Nota che prima di ricevere un messaggio, il destinatario ha sempre incertezza su quale messaggio io sia. tra tutti gli sarà dato. Tale incertezza è stimata utilizzando la probabilità a priori P(i,) della trasmissione del messaggio i,. Concludiamo che una misura quantitativa oggettiva dell'informazione contenuta in un messaggio elementare di fonte discreta è data dalla probabilità di scegliere un dato messaggio e determina cc in funzione di questa probabilità. La stessa funzione caratterizza il grado di incertezza che ha il destinatario dell'informazione riguardo allo stato della sorgente discreta. Si può concludere che il grado di incertezza sulle informazioni attese determina i requisiti per i canali di trasmissione delle informazioni.

In generale, la probabilità Papà,) la scelta della fonte di qualche messaggio elementare i, (di seguito lo chiameremo simbolo) dipende dai simboli scelti in precedenza, cioè è una probabilità condizionata e non coinciderà con la probabilità a priori di tale scelta.

Tim che ^ Papà:) = 1, dal momento che tutto io formo un gruppo completo di eventi

gyi), e la scelta di questi simboli viene effettuata utilizzando alcune dipendenze funzionali J(a,)= P(a,) = 1, se la scelta del simbolo da parte della fonte è determinata a priori, J(a,)= un „ a P(a t ,a)- la probabilità di tale scelta, quindi la quantità di informazioni contenuta in una coppia di simboli è uguale alla somma della quantità di informazioni contenute in ciascuno dei simboli i e i. Questa proprietà di una misura quantitativa di informazioni è chiamata additività .

crediamo che Papà,)- la probabilità condizionata di scegliere il carattere i, dopo tutti i caratteri che lo precedono, e Papà,,i,) è la probabilità condizionata di scegliere il simbolo i; dopo i, e tutti i precedenti, ma, dato che P (a 1, a 1) \u003d P (a) P(i,|i y), si può scrivere la condizione di additività

Introduciamo la notazione Papà) = P p P (ar) \u003d D e riscrivere la condizione (5.1):

crediamo che R, O* 0. Usando l'espressione (5.2), determiniamo la forma della funzione (р (R). Differenziando, moltiplicando per R* 0 e denota RO = R, annotare

Si noti che la relazione (5.3) è soddisfatta per qualsiasi R f O u^^O. Tuttavia, questo requisito porta alla costanza dei lati destro e sinistro della (5.3): Pq>"(P)= Ar"(/?) - A - cost. Veniamo quindi all'equazione Pc> "(P) = A e dopo l'integrazione otteniamo

Teniamo conto che riscriveremo

Di conseguenza, al soddisfacimento di due condizioni sulle proprietà di J(a,), è risultato che la forma della dipendenza funzionale J(a,) sulla probabilità di scegliere un simbolo in fino a un coefficiente costante A definito in modo univoco

Coefficiente A interessa solo la scala e determina il sistema di unità per misurare la quantità di informazioni. Dal momento che ln[P] F 0, allora ha senso scegliere Per Os in modo che una misura della quantità di informazioni J(a) era positivo.

Aver accettato K=-1, annota

Ne consegue che l'unità della quantità di informazione è uguale all'informazione che si è verificato un evento la cui probabilità è uguale a Me. Tale unità di quantità di informazioni è chiamata unità naturale. Più spesso si presume che A= -, allora

Pertanto, siamo arrivati ​​a un'unità binaria della quantità di informazioni che contiene un messaggio sul verificarsi di uno di due eventi ugualmente probabili ed è chiamata "bit". Questa unità è molto diffusa grazie all'uso di codici binari nella tecnologia delle comunicazioni. Scegliendo la base del logaritmo nel caso generale, otteniamo

dove il logaritmo può essere con base arbitraria.

La proprietà di additività della misura quantitativa delle informazioni permette, sulla base dell'espressione (5.9), di determinare la quantità di informazioni in un messaggio costituito da una sequenza di caratteri. La probabilità che una fonte scelga una tale sequenza viene presa tenendo conto di tutti i messaggi precedentemente disponibili.

La misura quantitativa delle informazioni contenute nel messaggio elementare a (, non dà un'idea della quantità media di informazioni J(A) emesso dalla sorgente quando viene selezionato un messaggio elementare anno Domini

La quantità media di informazioni caratterizza la fonte di informazioni nel suo insieme ed è una delle caratteristiche più importanti dei sistemi di comunicazione.

Definiamo questa caratteristica per una fonte discreta di messaggi indipendenti con l'alfabeto A. Indica con SUL) la quantità media di informazioni per carattere ed è l'aspettativa matematica di una variabile casuale L - la quantità di informazioni contenute in un carattere selezionato casualmente un

La quantità media di informazioni per simbolo è chiamata entropia della fonte di messaggi indipendenti. L'entropia è un indicatore dell'incertezza media a priori nella scelta del simbolo successivo.

Segue dall'espressione (5.10) che se una delle probabilità Papà)è uguale a uno (quindi tutti gli altri sono uguali a zero), quindi l'entropia della fonte di informazione sarà uguale a zero - il messaggio è completamente definito.

L'entropia sarà massima se le probabilità a priori di tutti i simboli possibili sono uguali A, cioè. RA() = 1 /A, poi

Se la fonte seleziona indipendentemente simboli binari con probabilità P, = P(ax) e P 2 \u003d 1 - P, quindi sarà l'entropia per carattere

Sulla fig. 16.1 mostra la dipendenza dell'entropia di una sorgente binaria dalla probabilità a priori di scegliere tra due simboli binari, questa figura mostra anche che l'entropia è massima in R, = R 2 = 0,5

1 o 1 dvd - e in unità binarie log 2 2 = 1-

Riso. 5.1. Dipendenza dall'entropia a K = 2 sulla probabilità di sceglierne uno

Entropia delle fonti con scelta equiprobabile dei simboli, ma con differenti dimensioni degli alfabeti A, aumenta logaritmicamente con la crescita A.

Se la probabilità di scegliere i simboli è diversa, l'entropia della sorgente diminuisce io(A) rispetto al massimo possibile H(A) psh = tronco d'albero A.

Maggiore è la correlazione tra i simboli, minore è la libertà di scegliere i simboli successivi e minori informazioni ha un simbolo appena selezionato. Ciò è dovuto al fatto che l'incertezza della distribuzione condizionale non può superare l'entropia della loro distribuzione incondizionata. Denota l'entropia della sorgente con memoria e alfabeto A attraverso H(AA"), e l'entropia della sorgente senza memoria, ma nello stesso alfabeto - attraverso SUL) e dimostrare la disuguaglianza

Introducendo la notazione P(aa") per la probabilità condizionata di scegliere il simbolo a,(/ = 1, 2, A) supponendo che il simbolo sia stato precedentemente selezionato ajij =1,2,A) e omettendo le trasformazioni, scriviamo senza prove

che prova la disuguaglianza (5.13).

L'uguaglianza in (5.13) o (5.14) si ottiene quando

Ciò significa che la probabilità condizionata di scegliere un simbolo è uguale alla probabilità incondizionata di sceglierlo, il che è possibile solo per fonti senza memoria.

È interessante notare che l'entropia del testo in russo è di 1,5 unità binarie per carattere. Allo stesso tempo, con lo stesso alfabeto K= 32 con la condizione di simboli indipendenti ed equiprobabili H(A) tp = 5 binari per carattere. Pertanto, la presenza di collegamenti interni ha ridotto l'entropia di circa 3,3 volte.

Una caratteristica importante di una sorgente discreta è la sua ridondanza p e:

La ridondanza della fonte di informazione è una quantità adimensionale all'interno di . Naturalmente, in assenza di ridondanza p u = 0.

Per trasmettere una certa quantità di informazioni da una fonte che non ha correlazioni tra i simboli, con uguale probabilità di tutti i simboli, il numero minimo possibile di simboli trasmessi /7 min: /r 0 (/7 0 R (L max)) è obbligatorio. Per trasmettere la stessa quantità di informazioni da una fonte con entropia (i simboli sono interconnessi e non egualmente probabili), è richiesto un numero medio di simboli n = n„H(A) m JH(A).

Una sorgente discreta è anche caratterizzata da prestazioni, che sono determinate dal numero di simboli per unità di tempo v H:

Se prestazioni io(A) definisci in unità binarie e il tempo in secondi, quindi SUL) -è il numero di unità binarie al secondo. Per le sorgenti discrete che producono sequenze di caratteri stazionarie di lunghezza sufficientemente grande /?, vengono introdotti i seguenti concetti: sequenze tipiche e atipiche di caratteri sorgente, in cui tutte le sequenze di lunghezza P. Tutte le sequenze tipiche NlMl (A) fonte a P-»oo hanno approssimativamente la stessa probabilità di occorrenza

La probabilità totale di occorrenza di tutte le sequenze atipiche tende a zero. In accordo con l'uguaglianza (5.11), assumendo che la probabilità di sequenze tipiche /N rm (A), l'entropia della sorgente è logN TIin (,4) e quindi

Considera la quantità e la velocità di trasmissione delle informazioni su un canale discreto con rumore. In precedenza, abbiamo considerato le informazioni prodotte da una fonte discreta sotto forma di una sequenza di caratteri (i,).

Supponiamo ora che l'informazione di origine sia codificata e rappresenti una sequenza di simboli di codice (B, (/ = 1,2,..T - code base), è coerente con un canale di trasmissione di informazioni discreto, all'uscita del quale compare una sequenza di simboli

Assumiamo che l'operazione di codifica sia uno a uno, in base alla sequenza di caratteri (B,) si può ripristinare in modo univoco la sequenza (i,), cioè tramite i simboli del codice è possibile ripristinare completamente le informazioni di origine.

Tuttavia, se consideriamo i caratteri di escape |?. j e inserire i simboli (/>,), quindi, a causa della presenza di interferenza nel canale di trasmissione delle informazioni, il ripristino è impossibile. Entropia della sequenza di output //(/?)

può essere maggiore dell'entropia della sequenza di input H(B), ma la quantità di informazioni per il destinatario non è aumentata.

Nel migliore dei casi, sono possibili relazioni uno-a-uno tra input e output e le informazioni utili non vanno perse; nel peggiore dei casi non si può dire nulla sui simboli di input dai simboli di output del canale di trasmissione delle informazioni, le informazioni utili sono completamente perse nel canale.

Stimiamo la perdita di informazioni in un canale rumoroso e la quantità di informazioni trasmesse su un canale rumoroso. Riteniamo che il carattere sia stato trasmesso correttamente se, con il carattere trasmesso 6, viene ricevuto

simbolo bj con lo stesso numero (/= J). Quindi per un canale ideale senza rumore, scriviamo:

Per simbolo bj-all'uscita del canale per disuguaglianze (5.21)

l'incertezza è inevitabile. Possiamo presumere che le informazioni nel simbolo b io non viene trasmesso completamente e parte di esso viene perso nel canale a causa di interferenze. Sulla base del concetto di misura quantitativa dell'informazione, assumeremo che l'espressione numerica dell'incertezza che si verifica all'uscita del canale dopo aver ricevuto il simbolo ft ; :

e determina la quantità di informazioni perse nel canale durante la trasmissione.

Fissaggio ft. e facendo la media (5.22) su tutti i possibili simboli, otteniamo la somma

che determina la quantità di informazioni perse nel canale quando si trasmette un simbolo elementare su un canale senza memoria quando si riceve un simbolo bj(t).

Facendo la media della somma (5.23) su tutti i piedi, otteniamo il valore Z?), che indichiamo con n(in/in- Determina la quantità di informazioni perse durante la trasmissione di un carattere su un canale senza memoria:

dove P^bjbjj- probabilità congiunta di un evento che, una volta trasmesso

simbolo B. ci vorrà il simbolo B T .

H [con/ dipende dalle caratteristiche della fonte di informazione su

ingresso del canale V e sulle caratteristiche probabilistiche del canale di comunicazione. Secondo Shannon nella teoria della comunicazione statistica n(in/in si chiama inaffidabilità del canale.

Entropia condizionale MP/B, entropia di una sorgente discreta

all'ingresso del canale H(W) ed entropia E ^B) alla sua uscita non può essere

negativo. In un canale privo di interferenze, inaffidabilità del canale

n(v/v = 0. In accordo con (5.20), notiamo che H^v/v^

e l'uguaglianza avviene solo quando l'input e l'output del canale sono statisticamente indipendenti:

I simboli di uscita non dipendono dai simboli di ingresso, nel caso di un canale interrotto o di un'interferenza molto forte.

Come prima, per le sequenze tipiche, possiamo scrivere

dire che in assenza di interferenza, la sua inaffidabilità

Sotto le informazioni trasmesse in media sul canale J[ b/ per simbolo comprendiamo la differenza tra la quantità di informazioni all'ingresso del canale J(B) e informazioni perse nel canale /?).

Se la fonte di informazione e il canale sono privi di memoria, allora

L'espressione (5.27) determina l'entropia dei simboli di uscita del canale. Alcune delle informazioni all'uscita del canale sono utili e il resto è falso, poiché è generato da un'interferenza nel canale. Notiamolo n[v/ 2?) esprime informazioni sull'interferenza nel canale e la differenza i(d)-I(d/d) - informazioni utili che sono passate attraverso il canale.

Si noti che la stragrande maggioranza delle sequenze formate all'uscita del canale sono atipiche e hanno una probabilità totale molto piccola.

Di norma, viene preso in considerazione il tipo più comune di interferenza: il rumore additivo. N(t); Il segnale all'uscita del canale ha la forma:

Per i segnali discreti, il rumore equivalente, che segue da (5.28), ha una struttura discreta. Il rumore è una sequenza casuale discreta simile alle sequenze dei segnali di ingresso e di uscita. Indichiamo i simboli dell'alfabeto del rumore additivo in un canale discreto come C1 = 0, 1,2, T- uno). Probabilità di transizione condizionali in un tale canale

Perché E (^B/?) E (B) quindi, di conseguenza, l'informazione della sequenza di uscita del canale discreto #(/) relativa all'ingresso B(t) o vice versa E (B) - H ^ in / in) (5).

In altre parole, le informazioni trasmesse sul canale non possono superare le informazioni al suo ingresso.

Se l'ingresso del canale riceve una media xk simboli in un secondo, quindi è possibile determinare la velocità media di trasferimento delle informazioni su un canale con rumore:

dove Н(В) = V k J(B,B^ - prestazioni della sorgente all'ingresso del canale; n (in / in) \u003d Da U a n (in, in) ~ inaffidabilità del canale per unità di tempo; H (B) = V k H^B^- l'andamento della fonte formata dall'uscita del canale (emettendo parte dell'informazione utile e parte della falsa); H ^ in / B ^ \u003d U a 1 / (in / in)- la quantità di informazioni false,

creato interferenza nel canale per unità di tempo.

I concetti della quantità e della velocità di trasmissione delle informazioni su un canale possono essere applicati a varie sezioni del canale di comunicazione. Questa potrebbe essere la sezione "ingresso codificatore - uscita decodificatore".

Si noti che, espandendo la sezione del canale in esame, non è possibile superare la velocità su nessuna delle sue parti componenti. Qualsiasi trasformazione irreversibile porta alla perdita di informazioni. Le trasformazioni irreversibili includono non solo l'impatto dell'interferenza, ma anche il rilevamento, la decodifica con codici con ridondanza. Ci sono modi per ridurre la perdita di ricezione. Questa è "reception in generale".

Si consideri la larghezza di banda di un canale discreto e il teorema di codifica ottimale. Shannon ha introdotto una caratteristica che determina le velocità di trasferimento di informazioni massime possibili su un canale con proprietà note (rumore) sotto una serie di restrizioni sull'insieme dei segnali di ingresso. Questa è la larghezza di banda del canale C. Per un canale discreto

dove il massimo è custodito da possibili sorgenti di ingresso V dato Vk e il volume dell'alfabeto dei caratteri di input T.

Sulla base della definizione del throughput di un canale discreto, scriviamo

Si noti che C = 0 con ingresso e uscita indipendenti (alto livello di rumore nel canale) e, di conseguenza,

in assenza di interferenze di disturbo sul segnale.

Per canale simmetrico binario senza memoria

Riso. 5.2.

Grafico della dipendenza della capacità del canale binario dal parametro R mostrato in fig. 5.2. A R= 1/2 larghezza di banda del canale C = 0, entropia condizionale

//(/?//?) = 1. Interesse pratico

il grafico rappresenta a 0

Il teorema fondamentale di Shannon sulla codifica ottimale è legato al concetto di capacità. La sua formulazione per un canale discreto è la seguente: se le prestazioni della sorgente del messaggio SUL) inferiore alla larghezza di banda del canale C:

esiste un metodo di codifica e decodifica ottimale, in base al quale la probabilità di errore o inaffidabilità del canale n[a!A j può essere arbitrariamente piccolo. Se

non ci sono tali modi.

Secondo il teorema di Shannon, il valore finito CONè il valore limite della velocità di trasferimento di informazioni senza errori sul canale. Ma per un canale rumoroso, i modi per trovare il codice ottimale non sono indicati. Tuttavia, il teorema ha cambiato radicalmente le opinioni sulle possibilità fondamentali della tecnologia di trasmissione dell'informazione. Prima di Shannon, si credeva che in un canale rumoroso fosse possibile ottenere una probabilità di errore arbitrariamente piccola riducendo a zero la velocità di trasferimento delle informazioni. Questo è, ad esempio, un aumento della fedeltà della comunicazione a causa della ripetizione dei caratteri in un canale senza memoria.

Sono note diverse dimostrazioni rigorose del teorema di Shannon. Il teorema è stato dimostrato per un canale discreto senza memoria mediante codifica casuale. In questo caso si considera l'insieme di tutti i codici scelti casualmente per una data sorgente e un dato canale e si afferma il fatto dell'avvicinamento asintotico allo zero della probabilità media di decodifica errata su tutti i codici con un aumento illimitato della durata di la sequenza dei messaggi Pertanto, viene dimostrato solo il fatto dell'esistenza di un codice che fornisce la possibilità di una decodifica senza errori, ma non viene proposto un metodo di codifica univoco. Allo stesso tempo, nel corso della dimostrazione, diventa ovvio che, pur mantenendo l'uguaglianza delle entropie dell'insieme della sequenza di messaggi e del corrispondente insieme di parole in codice uno a uno utilizzato per la trasmissione, l'insieme V dovrebbe essere introdotta una ridondanza aggiuntiva per aumentare la dipendenza reciproca della sequenza dei simboli del codice. Questo può essere fatto solo espandendo l'insieme di sequenze di codici da cui vengono selezionate le parole di codice.

Nonostante il teorema di codifica principale per i canali rumorosi non indichi modi univoci di scelta di un codice particolare e siano anche assenti nella dimostrazione del teorema, si può dimostrare che la maggior parte dei codici scelti casualmente, quando si codifica un messaggio sufficientemente lungo sequenze, superano leggermente la probabilità media di decodifica errata. Tuttavia, le possibilità pratiche della codifica in blocchi lunghi sono limitate a causa delle difficoltà nell'implementazione di sistemi di memoria e nell'elaborazione logica di sequenze di un numero enorme di elementi di codice, nonché a un aumento del ritardo nella trasmissione e nell'elaborazione delle informazioni. Di particolare interesse, infatti, sono i risultati che consentono di determinare la probabilità di decodifica errata per valori finiti della durata P blocchi di codice utilizzati. In pratica, sono limitati a valori di ritardo moderati e ottengono un aumento della probabilità di trasmissione con un utilizzo incompleto della larghezza di banda del canale.