Kdaj in zakaj je nastala teorija kodiranja. Teorija kodiranja. Vrste kodiranja. Kodiranje. Osnovni koncepti

Teorija kodiranja - preučevanje lastnosti kod in njihove primernosti za doseganje danega cilja. Kodiranje informacij je proces njihovega preoblikovanja iz oblike, primerne za neposredno uporabo, v obliko, ki je primerna za prenos, shranjevanje, samodejno obdelavo in zaščito pred nepooblaščenim dostopom. Glavni problemi teorije kodiranja vključujejo vprašanja kodiranja ena proti ena in kompleksnost implementacije komunikacijskega kanala v danih pogojih. V zvezi s tem teorija kodiranja obravnava predvsem naslednja področja: stiskanje podatkov, popravljanje napak naprej, kriptografija, fizično kodiranje, odkrivanje in popravljanje napak.

Format

Tečaj je sestavljen iz 10 akademskih tednov. Za uspešno reševanje večine nalog iz testov je dovolj, da obvladamo snov, ki je bila povedana na predavanjih. Seminarji obravnavajo tudi zahtevnejše naloge, ki lahko zanimajo poslušalca, ki že pozna osnove.

Program tečaja

1. Abecedno kodiranje. Zadostni pogoji za nedvoumno dekodiranje: enotnost, predpona, končnica. Prepoznavanje edinstvenosti: Markovljev kriterij. Ocena dolžine dvoumno dekodljive besede.
2. Kraft-McMillanova neenakost; obstoj predpone z danim nizom dolžin besed; posledica univerzalnosti predponskih kod.
3. Kode minimalne redundance: Izjava problema, Huffmanov redukcijski izrek.
4. Naloga popravljanja in odkrivanja napak. Geometrijska interpretacija. Vrste napak. Hammingova in Levenshteinova metrika. kodna razdalja. Glavne naloge teorije kod za popravljanje napak.
5. Varshamov-Tenengoltsove kode, algoritmi za popravljanje posameznih napak pri izpuščanju in vstavljanju simbolov.
6. Najpreprostejše meje za parametre nadomestnih kod za popravljanje napak: sferične meje pakiranja, meje Singletona, Plotkinove meje.
7. Vdelava metričnih prostorov. Lema o številu vektorjev v evklidskem prostoru. Meja Elias-Bassalygo.
8. Linijske kode. Definicije. Ustvarjanje in preverjanje matrik. Razmerje med razdaljo kode in kontrolno matriko. Meja Varshamov-Gilbert. sistematično kodiranje. Dekodiranje sindroma. Hammingove kode.
9. Preostala koda. Meja Greismer-Solomon-Stiffler.
10. Kompleksnost problema dekodiranja linearnih kod: problem NCP (problem o najbližji kodni besedi).
11. Reed-Solomon kode. Berlekamp-Welch dekodirni algoritem.
12. Reed-Mullerjeve kode: kodna razdalja, algoritem večinskega dekodiranja.
13. Variante posplošitve Reed-Mullerjeve konstrukcije. Lema Lipton-DeMillo-Schwartz-Zippel. Pojem algebrogeometričnih kod.
14. Grafi razširitve. Verjetnostni dokaz obstoja ekspanderjev. Kode, ki temeljijo na dvodelnih grafih. Kodna razdalja kod na osnovi ekspanderjev. Sipser-Spielmanov algoritem dekodiranja.
15. Shannonovi izreki za verjetnostni model kanala.
16. Programi za odpravljanje napak kode. Naključni protokol v komunikacijski kompleksnosti. McElieceova kriptoshema. Homogeni (psevdo-naključni) nizi, ki temeljijo na kodah, njihove aplikacije za derandomizacijo v problemu MAX-SAT.

Iz Wikipedije, proste enciklopedije

teorija kodiranja- znanost o lastnostih kod in njihovi primernosti za doseganje cilja.

Splošne informacije

Kodiranje je proces pretvorbe podatkov iz oblike, ki je primerna za takojšnjo uporabo, v obliko, ki je primerna za prenos, shranjevanje, samodejno obdelavo in zaščito pred nepooblaščenim dostopom. Glavni problemi teorije kodiranja so vprašanja individualnega kodiranja in kompleksnosti izvedbe komunikacijskega kanala pod danimi pogoji:86. V zvezi s tem teorija kodiranja obravnava predvsem naslednja področja:18:

Stiskanje podatkov

Naprej popravek napak

Kriptografija

Kriptografija (iz druge grščine. κρυπτός - skrito in γράφω - pišem), to je področje znanja o metodah zagotavljanja zaupnosti (nezmožnost branja informacij zunanjim osebam), integritete podatkov (nemogoče neopazno spreminjanje informacij), avtentikacije (avtentikacija avtorstva ali drugih lastnosti predmeta), pa tudi nemožnost zavrnitve avtorstva

04.04.2006 Leonid Černjak Kategorija:Tehnologije

"Odprti sistemi" Ustvarjanje računalnikov bi bilo nemogoče, če hkrati z njihovim pojavom ne bi nastala teorija kodiranja signalov. Teorija kodiranja? - eno tistih področij matematike, ki je pomembno vplivala na razvoj računalništva.

"Odprti sistemi"

Ustvarjanje računalnikov bi bilo nemogoče, če ne bi hkrati z njihovim pojavom nastala teorija kodiranja signalov.

Teorija kodiranja je eno tistih področij matematike, ki je izrazito vplivala na razvoj računalništva. Njegov obseg sega na prenos podatkov po resničnih (ali hrupnih) kanalih, predmet pa je zagotoviti pravilnost posredovanih informacij. Z drugimi besedami, preučuje, kako najbolje zapakirati podatke, tako da se lahko koristne informacije, ko so signalizirane, iz podatkov zanesljivo in enostavno izvlečejo iz podatkov. Včasih teorijo kodiranja zamenjujejo s šifriranjem, vendar to ne drži: kriptografija rešuje inverzno težavo, njen cilj je otežiti pridobivanje informacij iz podatkov.

S potrebo po kodiranju podatkov smo se prvič srečali pred več kot sto petdesetimi leti, kmalu po izumu telegrafa. Kanali so bili dragi in nezanesljivi, zaradi česar je bila naloga zmanjšanja stroškov in povečanja zanesljivosti prenosa telegramov nujna. Problem je postal še bolj pereč v povezavi s polaganjem čezatlantskih kablov. Od leta 1845 so se začele uporabljati posebne šifrantke; z njihovo pomočjo so telegrafisti ročno »stisnjali« sporočila, pri čemer so običajna zaporedja besed zamenjali s krajšimi kodami. Hkrati se je za preverjanje pravilnosti prenosa začela uporabljati pariteta, metoda, s katero so preverjali tudi pravilnost vnosa luknjanih kartic v računalnikih prve in druge generacije. Da bi to naredili, je bila v zadnji vhodni sklop vstavljena posebej pripravljena kartica s kontrolno vsoto. Če vhodna naprava ni bila zelo zanesljiva (ali je bil krov prevelik), bi lahko prišlo do napake. Da bi ga popravili, smo postopek vnosa ponavljali, dokler se izračunana kontrolna vsota ne ujema z zneskom, shranjenim na kartici. Ne samo, da je ta shema neprijetna, ampak tudi pogreša dvojne napake. Z razvojem komunikacijskih kanalov je bil potreben učinkovitejši nadzorni mehanizem.

Prvo teoretično rešitev problema prenosa podatkov po hrupnih kanalih je predlagal Claude Shannon, ustanovitelj teorije statističnih informacij. Shannon je bil zvezda svojega časa, bil je eden od ameriške akademske elite. Kot podiplomski študent pri Vannevarju Bushu je leta 1940 prejel Nobelovo nagrado (ne mešati z Nobelovo nagrado!), ki so jo podeljevali znanstvenikom, mlajšim od 30 let. V laboratoriju Bell Labs je Shannon napisal "Matematično teorijo prenosa sporočil" (1948), kjer je pokazal, da če je pasovna širina kanala večja od entropije vira sporočila, je mogoče sporočilo kodirati tako, da bo posredovano brez nepotrebnega odlašanja. Ta zaključek je vsebovan v enem od izrekov, ki jih je dokazal Shannon, njegov pomen pa je v tem, da če obstaja kanal z zadostno pasovno širino, se sporočilo lahko odda z nekaj časovnimi zamiki. Poleg tega je pokazal teoretično možnost zanesljivega prenosa ob prisotnosti hrupa v kanalu. Formulo C = W log ((P+N)/N), izklesano na skromnem spomeniku Shannonu, nameščenemu v njegovem domačem kraju v Michiganu, po vrednosti primerjamo s formulo Alberta Einsteina E = mc 2 .

Shannonovo delo je povzročilo številne nadaljnje raziskave na področju teorije informacij, vendar niso imele praktične inženirske uporabe. Prehod iz teorije v prakso je bil omogočen s prizadevanji Richarda Hamminga, Shannonovega kolega pri Bell Labsu, ki je slavo pridobil z odkritjem razreda kod, ki se je imenoval "Hammingove kode". Obstaja legenda, da je neprijetnost pri delu z luknjanimi karticami na relejskem računskem stroju Bell Model V sredi 40-ih spodbudila izum njihovih Hammingovih kod. Dobil je čas za delo na stroju ob vikendih, ko ni bilo upravljavcev, sam pa se je moral poigravati z vnosom. Kakorkoli že, Hamming je predlagal kode, ki lahko popravljajo napake v komunikacijskih kanalih, vključno z vodovi za prenos podatkov v računalnikih, predvsem med procesorjem in pomnilnikom. Hammingove kode so postale dokaz, kako je mogoče v praksi uresničiti možnosti, ki jih kažejo Shannonovi izreki.

Hamming je svoj prispevek objavil leta 1950, čeprav notranja poročila njegovo teorijo kodiranja datirajo v leto 1947. Zato nekateri menijo, da je treba Hamminga in ne Shannon šteti za očeta teorije kodiranja. Vendar pa je v zgodovini tehnologije neuporabno iskati prvega.

Gotovo je le, da je bil Hamming tisti, ki je prvi predlagal "kode za popravljanje napak" (Error-Correcting Code, ECC). Sodobne modifikacije teh kod se uporabljajo v vseh sistemih za shranjevanje podatkov in za izmenjavo med procesorjem in RAM-om. Ena od njihovih različic, kode Reed-Solomon, se uporablja na CD-jih, kar omogoča predvajanje posnetkov brez škripanja in hrupa, ki bi lahko povzročil praske in prašne delce. Obstaja veliko različic kod, ki temeljijo na Hammingu, razlikujejo se po algoritmih kodiranja in številu kontrolnih bitov. Takšne kode so pridobile poseben pomen v povezavi z razvojem komunikacij v globokem vesolju z medplanetarnimi postajami, na primer obstajajo kode Reed-Muller, kjer je 32 kontrolnih bitov za sedem informacijskih bitov ali 26 za šest.

Med najnovejšimi kodami ECC je treba omeniti kode LDPC (Low-Density Parity-check Code). Pravzaprav so znani že približno trideset let, a posebno zanimanje zanje so odkrili ravno v zadnjih letih, ko se je začela razvijati televizija visoke ločljivosti. Kode LDPC niso 100-odstotno zanesljive, vendar je mogoče stopnjo napake prilagoditi na želeno raven, hkrati pa v največji možni meri izkoristiti pasovno širino kanala. "Turbo kode" so jim blizu, učinkovite so pri delu s predmeti, ki se nahajajo v globokem vesolju in z omejeno pasovno širino kanala.

Ime Vladimirja Aleksandroviča Kotelnikova je trdno vpisano v zgodovino teorije kodiranja. Leta 1933 je v "Materiali o radijskih komunikacijah za prvi vseslovenski kongres o tehnični rekonstrukciji komunikacij" objavil delo "O pasovni širini? Eter? in? žice? Ime Kotelnikova je kot enakovredna vključeno v ime enega najpomembnejših izrekov v teoriji kodiranja. Ta izrek opredeljuje pogoje, pod katerimi se lahko preneseni signal obnovi brez izgube informacij.

Ta izrek je bil imenovan različno, vključno z "WKS izrek" (okrajšava WKS je vzeta iz Whittaker, Kotelnikov, Shannon). V nekaterih virih se uporabljata tako izrek o vzorčenju Nyquist-Shannon kot izrek o vzorčenju Whittaker-Shannon, v domačih univerzitetnih učbenikih pa najpogosteje najdemo preprosto "Kotelnikov izrek". Pravzaprav ima izrek daljšo zgodovino. Njegov prvi del je leta 1897 dokazal francoski matematik Emile Borel. Edmund Whittaker je prispeval leta 1915. Leta 1920 je Japonec Kinnosuki Ogura objavil popravke Whittakerjeve raziskave, leta 1928 pa je Američan Harry Nyquist izpopolnil principe digitalizacije in rekonstrukcije analognega signala.

Claude Shannon(1916 - 2001) je že od šolskih let pokazal enako zanimanje za matematiko in elektrotehniko. Leta 1932 se je vpisal na univerzo v Michiganu, leta 1936 - na Massachusetts Institute of Technology, kjer je diplomiral leta 1940 in prejel dve diplomi - magistriral iz elektrotehnike in doktoriral iz matematike. Leta 1941 se je Shannon pridružila Bell Laboratories. Tu je začel razvijati ideje, ki so kasneje nastale v informacijski teoriji. Leta 1948 je Shannon objavil članek "Matematična teorija komunikacije", kjer so bile oblikovane osnovne ideje znanstvenika, zlasti določanje količine informacij z entropijo, in predlagal tudi informacijsko enoto, ki določa izbiro dveh enako verjetne možnosti, torej tisto, kar so kasneje imenovali bit . V letih 1957-1961 je Shannon objavil prispevke, ki so dokazal izrek o prepustnosti za hrupne komunikacijske kanale, ki zdaj nosi njegovo ime. Leta 1957 je Shannon postal profesor na Massachusetts Institute of Technology, s katerega se je 21 let pozneje upokojil. Na "zasluženem počitku" se je Shannon popolnoma posvetil svoji stari strasti do žongliranja. Zgradil je več strojev za žongliranje in ustvaril celo splošno teorijo žongliranja.

Richard Hamming(1915 - 1998) se je začel izobraževati na Univerzi v Chicagu, kjer je leta 1937 diplomiral. Leta 1939 je magistriral na Univerzi v Nebraski in doktoriral iz matematike na Univerzi v Illinoisu. Leta 1945 je Hamming začel delati na projektu Manhattan, obsežnem vladnem raziskovalnem prizadevanju za izdelavo atomske bombe. Leta 1946 se je Hamming pridružil Bell Telephone Laboratories, kjer je delal s Claudom Shannon. Leta 1976 je Hamming dobil stolček na podiplomski šoli za mornarico v Montereyu v Kaliforniji.

Hamming je leta 1950 objavil delo, zaradi katerega je postal slaven, temeljna študija o odkrivanju in popravljanju napak. Leta 1956 je sodeloval pri razvoju enega od zgodnjih velikih računalnikov IBM 650. Njegovo delo je postavilo temelje za programski jezik, ki se je kasneje razvil v programske jezike visoke ravni. Kot priznanje za Hammingov prispevek na področju računalništva je IEEE ustanovil medaljo za ugledne službe za računalništvo in teorijo sistemov, poimenovano po njem.

Vladimir Kotelnikov(1908 - 2005) je leta 1926 vstopil na oddelek za elektrotehniko Moskovske višje tehnične šole po imenu NE Bauman (MVTU), vendar je postal diplomant Moskovskega elektroenergetskega inštituta (MPEI), ki se je od MVTU ločil kot samostojen inštitut. . Kotelnikov je med študijem na podiplomskem študiju (1931-1933) matematično natančno oblikoval in dokazal "referenčni izrek", ki je bil kasneje poimenovan po njem. Po končani podiplomski šoli leta 1933 je Kotelnikov, ki je ostal poučeval na Moskovskem elektrotehničnem inštitutu, šel delati na Centralni raziskovalni inštitut za komunikacije (TsNIIS). Leta 1941 je V. A. Kotelnikov oblikoval jasno stališče o zahtevah, ki jih mora izpolnjevati matematično nedešifrirani sistem, in podan je bil dokaz o nemožnosti dešifriranja. Leta 1944 je Kotelnikov prevzel mesto profesorja, dekana fakultete za radiotehniko MPEI, kjer je delal do leta 1980. Leta 1953 je bil Kotelnikov pri 45 letih takoj izvoljen za rednega člana Akademije znanosti ZSSR. Od leta 1968 do 1990 je bil V. A. Kotelnikov tudi profesor, predstojnik oddelka na Moskovskem inštitutu za fiziko in tehnologijo.

Rojstvo teorije kodiranja

Teorija kodiranja. Vrste kodiranja Osnovni pojmi teorije kodiranja Prej so imela orodja za kodiranje pomožno vlogo in niso bila obravnavana kot ločen predmet matematičnega preučevanja, s prihodom računalnikov pa se je situacija korenito spremenila. Kodiranje dobesedno prežema informacijsko tehnologijo in je osrednje vprašanje pri reševanju različnih (praktično vseh) programskih nalog: ۞ predstavljanje podatkov poljubne narave (na primer številk, besedila, grafike) v računalniškem pomnilniku; ۞ zaščita informacij pred nepooblaščenim dostopom; ۞ Zagotavljanje odpornosti proti hrupu med prenosom podatkov po komunikacijskih kanalih; ۞ stiskanje informacij v bazah podatkov. Teorija kodiranja je veja teorije informacij, ki preučuje, kako je mogoče sporočila identificirati s signali, ki jih predstavljajo. Naloga: Uskladiti vir informacij s komunikacijskim kanalom. Predmet: diskretne ali neprekinjene informacije, posredovane potrošniku prek vira informacij. Kodiranje je pretvorba informacij v formulo, ki je primerna za prenos po določenem komunikacijskem kanalu. Primer kodiranja v matematiki je koordinatna metoda, ki jo je uvedel Descartes, ki omogoča preučevanje geometrijskih objektov skozi njihov analitični izraz v obliki številk, črk in njihovih kombinacij - formul. Koncept kodiranja pomeni preoblikovanje informacij v obliko, ki je primerna za prenos po določenem komunikacijskem kanalu. Dekodiranje je obnovitev prejetega sporočila iz kodirane oblike v obliko, dostopno potrošniku.

Tema 5.2. Abecedno kodiranje V splošnem primeru lahko problem kodiranja predstavimo na naslednji način. Naj sta podani dve abecedi A in B, sestavljeni iz končnega števila znakov: in. Elementi abecede se imenujejo črke. Urejeni niz v abecedi A se imenuje beseda, kjer je n =l()=| |. , številka n kaže število črk v besedi in se imenuje dolžina besede, prazna beseda je označena: Za besedo se črka a1 imenuje začetek ali predpona besede, črka an je konec ali postfiks besede. , Besede pa je mogoče kombinirati. Za to mora predpona druge besede takoj slediti postfiksu prve, medtem ko v novi besedi seveda izgubijo status, razen če je bila ena od besed prazna. Zloženka besed in je označena, poleg tega je označena zloženka n enakih besed. Množico vseh nepraznih besed abecede A označimo z A*: množico A imenujemo sporočilna abeceda, množico B pa kodirna abeceda. Nabor besed, sestavljenih v abecedi B, bo označen z B*.

S F označimo preslikavo besed iz abecede A v abecedo B. Takrat besedo imenujemo koda besede. Kodiranje je univerzalen način prikaza informacij med shranjevanjem, prenosom in obdelavo v obliki sistema korespondenc med elementi sporočila in signali, s katerimi je te elemente mogoče fiksirati. Tako je koda pravilo za nedvoumno transformacijo (tj. funkcijo) sporočila iz ene simbolne predstavitvene oblike (izvirna abeceda A) v drugo (predmetna abeceda B), običajno brez izgube informacij. Postopek pretvorbe F: A* B*→ besed prvotne abecede A v abecedo B se imenuje informacijsko kodiranje. Postopek pretvorbe besede nazaj se imenuje dekodiranje. Tako je dekodiranje obratno od F, tj. F1. v besedo Ker je za vsako kodiranje treba izvesti operacijo dekodiranja, mora biti preslikava inverzibilna (bijekcija). Če |B|= m, potem F imenujemo mimično kodiranje, najpogostejši primer je B = (0, 1) binarno kodiranje. Prav ta primer je obravnavan v nadaljevanju. Če imajo vse kodne besede enako dolžino, se koda imenuje enotna ali blok. Abecedno (ali črko za črko) kodiranje je mogoče določiti s kodno tabelo. Nekatera zamenjava bo služila kot koda ali funkcija kodiranja. Potem kje,. Takšno kodiranje po črkah je označeno kot niz osnovnih kod. Abecedno kodiranje se lahko uporablja za kateri koli niz sporočil. Tako je abecedno kodiranje najpreprostejše in ga je vedno mogoče vnesti v neprazne abecede. . Veliko črkovnih kod

PRIMER Naj so podane abecede A = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) B = (0, 1). Potem je lahko kodna tabela zamenjava: . To je kodiranje BCD, je ena proti ena in zato dekodirano. Vendar shema ni ena proti ena. Na primer, nabor šestih 111111 se lahko ujema z besedo 333 in 77, pa tudi z 111111, 137, 3311 ali 7111 in kakršno koli permutacijo. Abecedna kodna shema se imenuje predpona, če osnovna koda ene črke ni predpona osnovne kode druge črke. Za abecedno kodno shemo rečemo, da je ločljiva, če se katera koli beseda, sestavljena iz elementarnih kod, razgradi v elementarne kode na edinstven način. Abecedno kodiranje z ločljivo shemo omogoča dekodiranje. Lahko se dokaže, da je shema predpone ločljiva. Da je abecedna kodna shema ločljiva, morajo dolžine osnovnih kod izpolnjevati razmerje, znano kot Macmillanova neenakost. Macmillanova neenakost Če je shema abecednega kodiranja

je ločljiva, potem velja naslednja neenakost. osnovna koda črke a je predpona osnovne kode črke b. Tema 5.3. Minimalno redundantno kodiranje V praksi je pomembno, da so kode sporočil čim krajše. Abecedno kodiranje je primerno za vsa sporočila, če pa o nizu vseh besed abecede A ni nič znanega, je težko natančno formulirati problem optimizacije. Vendar pa so v praksi pogosto na voljo dodatne informacije. Na primer, za sporočila, predstavljena v naravnem jeziku, je lahko takšna dodatna informacija porazdelitev verjetnosti pojavljanja črk v sporočilu. Nato dobi problem izdelave optimalne kode natančno matematično formulacijo in strogo rešitev.

Naj bo podana neka ločljiva shema abecednega kodiranja. Potem bo vsaka shema, kjer je urejena množica permutacija urejene množice, prav tako ločljiva. V tem primeru, če so dolžine osnovnega niza kod enake, njihova permutacija v shemi ne vpliva na dolžino kodiranega sporočila. V primeru, da so dolžine osnovnih kod različne, je dolžina kode sporočila neposredno odvisna od tega, katere osnovne kode ustrezajo kateri črki, in od sestave črk v sporočilu. Glede na specifično sporočilo in določeno shemo kodiranja je mogoče izbrati takšno permutacijo kod, pri kateri bo dolžina kode sporočila minimalna. Algoritem za dodeljevanje elementarnih kod, pri katerem bo dolžina fiksne kode sporočila S minimalna za fiksno shemo: ۞ razvrsti črke v padajočem vrstnem redu glede na število pojavljanj; ۞ razvrsti osnovne kode v naraščajočem vrstnem redu dolžine; ۞ postavite kode v skladu s črkami v predpisanem vrstnem redu. Naj bo podana abeceda in verjetnosti pojava črk v sporočilu:

Kjer je pi verjetnost pojava črke ai, črke z ničelno verjetnostjo, da se bodo pojavile v sporočilu, so izključene in črke so razvrščene v padajočem vrstnem redu glede na verjetnost njihovega pojavljanja sporočila, ki je označeno in opredeljeno kot PRIMER. Za ločljivo abecedno kodno shemo A=(a,b), B=(0,1) je pri porazdelitvi verjetnosti strošek kodiranja, pri porazdelitvi verjetnosti pa je strošek kodiranja

Tema 5.4. Huffmanovo kodiranje Ta algoritem je leta 1952 izumil David Huffman. Tema 5.5. Aritmetično kodiranje Tako kot v Huffmanovem algoritmu se vse začne s tabelo elementov in pripadajočimi verjetnostmi. Recimo, da je vhodna abeceda sestavljena iz samo treh elementov: a1, a2 in a3, hkrati pa P(a1) = 1/2 P(a2) = 1/3 P(a3) = 1/6 Predpostavimo tudi, da potrebujemo za kodiranje zaporedja a1, a1, a2, a3. Razdelimo interval , kjer je p neko fiksno število, 0<р<(r­1)/2r, а "мощностная" граница где Tr(p)=­p logr(p/(r­ 1))­(1­р)logr(l­ p), существенно улучшена. Имеется предположение, чт о верхняя граница полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir(п,[ рп])~пТ r(2р).Доказательство или опровержение этого предположения ­ одна из центральны х задач теории кодирования. Большинство конструкций помехоустойчивых кодов являются эффективными, когда длин а пкода достаточновелика. В связи с этим особое значение приобретают вопросы, связанны е со сложностью устройств,осуществляющих кодирование и декодирование (кодера и деко дера). Ограничения на допустимый типдекодера или его сложность могут приводить к увел ичению избыточности, необходимой для обеспечениязаданной помехоустойчивости. Напр., минимальная избыточность кода в В n 2, для к­рого существует декодер,состоящий из регист

ra premik in en večinski element ter popravi eno napako, ima vrstni red (primerjaj z (2)). Kot matematično Modeli kodirnikov in dekoderjev se običajno obravnavajo iz vezja funkcionalnih elementov, kompleksnost pa se razume kot število elementov v vezju. Za znane razrede kod za popravljanje napak je bila narejena študija možnih algoritmov za K. in D. ter pridobljene zgornje meje kompleksnosti kodirnika in dekoderja. Nekaj ​​razmerij najdemo tudi med hitrostjo kodiranja, odpornostjo na hrup kodiranja in kompleksnostjo dekodirnika (glej ). Druga smer raziskovanja v teoriji kodiranja je povezana z dejstvom, da številni rezultati (na primer Shanonov izrek in vezana (3)) niso »konstruktivni«, temveč so izreki o obstoju neskončnih zaporedij (Kn) kod. Glede na to, si prizadevamo dokazati te rezultate v razredu takšnih zaporedij (Kn) kod, za kp obstaja Turingov stroj, ki prepozna, da poljubna beseda dolžine l pripada časovnemu nizu, ki ima počasen vrstni red rasti glede na l (npr. llog l). Nekatere nove konstrukcije in metode za izpeljavo meja, razvite v teoriji kodiranja, so privedle do pomembnega napredka pri vprašanjih, ki so na prvi pogled zelo daleč od tradicionalnih problemov teorije kodiranja. Tu je treba opozoriti na uporabo maksimalne kode s popravkom ene napake pri simptomatično optimalni metodi realizacije funkcij algebre logike s kontaktnimi vezji; temeljno izboljšanje zgornje meje za gostoto pakiranja ponovno dimenzionalni evklidski prostor z enakimi kroglicami; o uporabi neenakosti (1) pri ocenjevanju kompleksnosti implementacije s formulami enega razreda funkcij algebre logike. Ideje in rezultati teorije kodiranja najdejo svoj nadaljnji razvoj v problemih sinteze samopopravljajočih se vezij in zanesljivih vezij iz nezanesljivih elementov. Lit .: Shannon K., Dela o informacijski teoriji in kibernetiki, prev. iz angleščine, M., 1963; Berlekamp E., Algebraična teorija kodiranja, prev. iz angleščine, M., 1971; Peterson, W., Weldon, E., Kode za popravljanje napak, prev. iz angleščine, 2. izd., M., 1976; Diskretna matematika in matematična vprašanja kibernetike, letnik 1, M., 1974, oddelek 5; Bassalygo L. A., Zyablov V. V., Pinsker M. S., "Problemi prenosa informacij", 1977, letnik 13, št. 3, str. 517; [V] V. M. Sidelnikov, "Mat. Sat.", 1974, v. 95, c. 1, str. 148 58. V. I. Levenshtein.

Matematična enciklopedija. - M.: Sovjetska enciklopedija. I. M. Vinogradov. 1977-1985.  ABECEDNIČNO KODIRANJE  KOEVKLIDANSKI PROSTOR Glej tudi v drugih slovarjih:  DEKODIRANJE – glej Kodiranje in dekodiranje ... Enciklopedija matematike  Zvočno kodiranje – ta članek je treba wikiificirati. Prosimo, da ga formatirate v skladu s pravili oblikovanja člankov. Osnova zvočnega kodiranja z uporabo osebnega računalnika je proces pretvorbe zračnih vibracij v električne vibracije ... Wikipedia kodne slike), izveden v skladu z definicijo. pravila, celota k ryh naz. šifra K., ... ... Filozofska enciklopedija  KODIRANJE INFORMACIJ - vzpostavitev korespondence med elementi sporočila in signali, s pomočjo katerih je mogoče te elemente fiksirati. Naj bo B množica sporočilnih elementov, A abeceda s simboli, Naj se pokliče končno zaporedje simbolov. z eno besedo v ... ... Fizična enciklopedija  OPTIMALNO KODIRANJE - (v inženirski psihologiji) (eng. optimal coding) ustvarjanje kod, ki zagotavljajo maksimalno hitrost in zanesljivost sprejemanja in obdelave informacij o objektu, ki ga upravlja človeški operater (glejte Sprejem informacij, dekodiranje). Problem K. o. ... ... Velika psihološka enciklopedija  DEKODIRANJE (v inženirski psihologiji) - (angleško dekodiranje) končna operacija postopka sprejemanja informacij s strani človeškega operaterja, ki sestoji iz ponovnega šifriranja parametrov, ki označujejo stanje kontrolnega objekta in njihovo prevajanje v podobo nadzorovanega predmeta (glej Kodiranje ... ... Velika psihološka enciklopedija

 Dekodiranje - obnovitev sporočila, kodiranega s posredovanimi in sprejetimi signali (glej Kodiranje) ... Ekonomsko-matematični slovar  KODIRANJE - KODIRANJE. Ena od stopenj generiranja govora, medtem ko je "dekodiranje" sprejem in interpretacija, proces razumevanja govornega sporočila. Glej psiholingvistika... Nov slovar metodoloških izrazov in pojmov (teorija in praksa poučevanja jezikov)  KODIRANJE - (angleško kodiranje). 1. Preoblikovanje signala iz ene oblike energije v drugo 2. Preoblikovanje enega sistema signalov ali znakov v druge, kar pogosto imenujemo tudi "transkodiranje", "sprememba kode" (za govor "prevajanje"). 3. K. (mnemonika) ... ... Velika psihološka enciklopedija  Dekodiranje - Ta članek govori o kodi v teoriji informacij, za druge pomene te besede glej koda (razen dvoumnosti). Koda je pravilo (algoritem) za ujemanje posameznega sporočila s strogo določeno kombinacijo simbolov (znakov) (ali signalov). Imenuje se tudi koda... ... Optimalno kodiranje Isto sporočilo je mogoče kodirati na različne načine. Optimalno kodirana koda je tista, pri kateri se za prenos sporočila porabi najmanj časa. Če prenos vsakega osnovnega znaka (0 ali 1) traja enak čas, bo optimalna koda tista, ki bo imela najmanjšo možno dolžino. Primer 1. Naj obstaja naključna spremenljivka X(x1,x2,x3,x4,x5,x6,x7,x8), ki ima osem stanj z verjetnostno porazdelitvijo. Za kodiranje abecede osmih črk z enotno binarno kodo potrebujemo tri znaki: Ta 000, 001, 010, 011, 100, 101, 110, 111 Če želite odgovoriti, ali je ta koda dobra ali ne, jo morate primerjati z optimalno vrednostjo, torej določiti entropijo

Ko določimo redundanco L po formuli L=1H/H0=12,75/3=0,084, vidimo, da je možno dolžino kode zmanjšati za 8,4%. Postavlja se vprašanje: ali je mogoče sestaviti kodo, v kateri bo v povprečju manj osnovnih znakov na črko. Takšne kode obstajajo. To sta kodi ShannonFano in Huffman. Načelo sestavljanja optimalnih kod: 1. Vsak elementarni znak mora vsebovati maksimalno količino informacij, za to je potrebno, da se elementarni znaki (0 in 1) v kodiranem besedilu pojavljajo v povprečju enako pogosto. Entropija bo v tem primeru največja. 2. Treba je, da se črkam primarne abecede, ki imajo večjo verjetnost, dodelijo krajše kodne besede sekundarne abecede.

Za analizo različnih virov informacij, pa tudi kanalov njihovega prenosa, je potrebno imeti kvantitativno merilo, ki bi omogočilo oceno količine informacij, ki jih vsebuje sporočilo in jih prenaša signal. Tak ukrep je leta 1946 uvedel ameriški znanstvenik C. Shannon.

Nadalje predpostavljamo, da je vir informacij diskreten in daje zaporedje elementarnih sporočil (i,), od katerih je vsako izbrano iz diskretnega ansambla (abecede) a, a 2,...,d A; Za je obseg abecede vira informacij.

Vsako osnovno sporočilo vsebuje določene informacije kot niz informacij (v obravnavanem primeru) o stanju zadevnega vira informacij. Za kvantificiranje mere te informacije ni pomembna njena semantična vsebina, pa tudi stopnja pomembnosti te informacije za prejemnika. Upoštevajte, da je prejemnik pred prejemom sporočila vedno v negotovosti, katero sporočilo sem. med vsemi možnimi mu bo dana. Ta negotovost je ocenjena z uporabo predhodne verjetnosti P(i,) prenosa sporočila i,. Sklepamo, da je objektivno kvantitativno merilo informacij, ki jih vsebuje elementarno sporočilo diskretnega vira, določeno z verjetnostjo izbire danega sporočila in določa cc kot funkcijo te verjetnosti. Ista funkcija označuje stopnjo negotovosti, ki jo ima prejemnik informacije glede stanja diskretnega vira. Sklepamo lahko, da stopnja negotovosti glede pričakovanih informacij določa zahteve po kanalih za prenos informacij.

Na splošno verjetnost P(a,) izbira vira nekega elementarnega sporočila i, (v nadaljevanju ga bomo imenovali simbol) je odvisna od prej izbranih simbolov, t.j. je pogojna verjetnost in ne bo sovpadala z a priori verjetnostjo takšne izbire.

Tim to ^ P(a:) = 1, saj vsi tvorijo popolno skupino dogodkov

gyi), izbira teh simbolov pa se izvede z uporabo neke funkcionalne odvisnosti J(a,)= P(a,) = 1, če je izbira simbola z virom vnaprej določena, J(a,)= a „a P(a t,a)- verjetnost takšne izbire, potem je količina informacij, ki jih vsebuje par simbolov, enaka vsoti količine informacij, vsebovanih v vsakem od simbolov i in i. Ta lastnost kvantitativne mere informacije se imenuje aditivnost .

To verjamemo P(a,)- pogojna verjetnost izbire znaka i po vseh znakih pred njim in P(a,,i,) je pogojna verjetnost izbire simbola i; za i in vsemi prejšnjimi, vendar glede na to P (a 1, a 1) \u003d P (a) P(i,|i y), lahko zapišemo pogoj aditivnosti

Uvedemo zapis P(a) = P p P (ar) \u003d Q in prepiši pogoj (5.1):

To verjamemo R, O* 0. Z izrazom (5.2) določimo obliko funkcije (р (R). Z razlikovanjem, množenjem z R* 0 in označuje RO = R, zapisati

Upoštevajte, da je relacija (5.3) izpolnjena za katero koli R f O u^^O. Vendar ta zahteva vodi do konstantnosti desne in leve strani (5.3): Pq>"(P)= Ar"(/?) - do - konst. Potem pridemo do enačbe PC> "(P) = TO in po integraciji dobimo

Upoštevajmo, da bomo prepisali

Posledično se je ob izpolnjevanju dveh pogojev za lastnosti J(a,) izkazalo, da je oblika funkcionalne odvisnosti J(a,) o verjetnosti izbire simbola a t do konstantnega koeficienta TO enolično opredeljeno

koeficient TO vpliva le na lestvico in določa sistem enot za merjenje količine informacij. Od ln[P] F 0, potem je smiselno izbrati Za Os, tako da je merilo količine informacij J(a) je bil pozitiven.

Po sprejetju K=-1, zapiši

Iz tega sledi, da je enota količine informacij enaka informaciji, da se je zgodil dogodek, katerega verjetnost je enaka jaz. Takšna enota količine informacij se imenuje naravna enota. Pogosteje se domneva, da TO= - torej

Tako smo prišli do binarne enote količine informacij, ki vsebuje sporočilo o nastopu enega od dveh enako verjetnih dogodkov in se imenuje »bit«. Ta enota je zelo razširjena zaradi uporabe binarnih kod v komunikacijski tehnologiji. Z izbiro osnove logaritma v splošnem primeru dobimo

kjer je lahko logaritem s poljubno osnovo.

Lastnost aditivnosti kvantitativne mere informacije omogoča, da na podlagi izraza (5.9) določimo količino informacij v sporočilu, sestavljenem iz zaporedja znakov. Verjetnost, da vir izbere takšno zaporedje, se upošteva ob upoštevanju vseh prej razpoložljivih sporočil.

Kvantitativno merilo informacij, ki jih vsebuje osnovno sporočilo a (, ne daje pojma o povprečni količini informacij J (A), ki ga izda vir, ko je izbrano eno osnovno sporočilo a d

Povprečna količina informacij označuje vir informacij kot celoto in je ena najpomembnejših značilnosti komunikacijskih sistemov.

Definirajmo to lastnost za diskretni vir neodvisnih sporočil z abecedo TO. Označi z NA) povprečna količina informacij na znak in je matematično pričakovanje naključne spremenljivke L - količina informacij, ki jih vsebuje naključno izbran znak a

Povprečna količina informacij na simbol se imenuje entropija vira neodvisnih sporočil. Entropija je pokazatelj povprečne a priori negotovosti pri izbiri naslednjega simbola.

Iz izraza (5.10) sledi, da če je ena od verjetnosti P(a) je enaka ena (torej so vsi ostali enaki nič), potem bo entropija vira informacij enaka nič - sporočilo je popolnoma definirano.

Entropija bo največja, če so predhodne verjetnosti vseh možnih simbolov enake TO, tj. R(a() = 1 /TO, potem

Če vir neodvisno izbere binarne simbole z verjetnostjo P, = P(a x) in P 2 \u003d 1 - P, potem bo entropija na znak

Na sl. 16.1 prikazuje odvisnost entropije binarnega vira od apriorne verjetnosti izbire izmed dveh binarnih simbolov, ta slika tudi kaže, da je entropija največja pri R, = R 2 = 0,5

1 o 1 dvd - in v binarnih enotah log 2 2 = 1-

riž. 5.1. Entropijska odvisnost pri K = 2 o verjetnosti izbire enega od njih

Entropija virov z enako verjetno izbiro simbolov, vendar z različnimi velikostmi abeced DO, logaritemsko narašča z rastjo TO.

Če je verjetnost izbire simbolov drugačna, potem entropija vira pade jaz (A) glede na možni maksimum H(A) psh = dnevnik TO.

Večja kot je korelacija med simboli, manj svobode pri izbiri naslednjih simbolov in manj informacij ima novo izbrani simbol. To je posledica dejstva, da negotovost pogojne porazdelitve ne more preseči entropije njihove brezpogojne porazdelitve. Entropijo vira označite s spominom in abecedo TOčez H(AA"), in entropija vira brez spomina, vendar v isti abecedi - skozi NA) in dokaži neenakost

Z uvedbo zapisa P(aa") za pogojno verjetnost izbire simbola a,(/ = 1, 2, DO) ob predpostavki, da je simbol predhodno izbran ajij =1,2,DO) in izpustimo transformacije, pišemo brez dokaza

kar dokazuje neenakost (5.13).

Enakost v (5.13) ali (5.14) je dosežena, ko

To pomeni, da je pogojna verjetnost izbire simbola enaka brezpogojni verjetnosti njegove izbire, kar je možno le pri virih brez spomina.

Zanimivo je, da je entropija besedila v ruščini 1,5 binarne enote na znak. Hkrati z isto abecedo K= 32 s pogojem neodvisnih in enako verjetnih simbolov H(A) tp = 5 binarnih na znak. Tako je prisotnost notranjih povezav zmanjšala entropijo za približno 3,3-krat.

Pomembna značilnost diskretnega vira je njegova redundanca p in:

Odvečnost vira informacij je brezdimenzionalna količina znotraj . Seveda je v odsotnosti redundance p u = 0.

Za prenos določene količine informacij iz vira, ki nima korelacije med simboli, z enako verjetnostjo vseh simbolov, najmanjše možno število prenesenih simbolov /7 min: /r 0 (/7 0 R (L max)) je potrebno. Za prenos enake količine informacij iz vira z entropijo (simboli so medsebojno povezani in neenako verjetni) je potrebno povprečno število simbolov n = n„H(A) m JH(A).

Za diskretni vir je značilna tudi zmogljivost, ki je določena s številom simbolov na enoto časa v H:

Če uspešnost jaz (A) definiraj v binarnih enotah, nato pa čas v sekundah NA) - je število binarnih enot na sekundo. Za diskretne vire, ki proizvajajo stacionarna zaporedja znakov dovolj velike dolžine /?, se uvedejo naslednji koncepti: tipična in netipična zaporedja izvornih znakov, v katera so vsa zaporedja dolžin P. Vsa tipična zaporedja NlMl (A) vir na P-»oo imajo približno enako verjetnost pojava

Skupna verjetnost pojava vseh atipičnih zaporedij se nagiba k nič. V skladu z enakostjo (5.11), ob predpostavki, da je verjetnost tipičnih zaporedij /N rm (A), entropija vira je logN TIin (,4) in nato

Upoštevajte količino in hitrost prenosa informacij po diskretnem kanalu s šumom. Prej smo obravnavali informacije, ki jih je ustvaril diskretni vir v obliki zaporedja znakov (i,).

Zdaj predpostavimo, da so izvorne informacije kodirane in predstavljajo zaporedje kodnih simbolov (b, (/ = 1,2,..T - kodna baza), je skladna z diskretnim kanalom za prenos informacij, na izhodu katerega se pojavi zaporedje simbolov

Predvidevamo, da je operacija kodiranja ena proti ena - po zaporedju znakov (b,) lahko enolično obnovimo zaporedje (i,), t.j. s kodnimi simboli je možno v celoti obnoviti izvorne informacije.

Vendar, če upoštevamo ubežne znake |?. j in vhodnih simbolov (/>,), potem je zaradi prisotnosti motenj v kanalu za prenos informacij obnovitev nemogoča. Entropija izhodnega zaporedja //(/?)

je lahko večja od entropije vhodnega zaporedja H(B), vendar se količina informacij za prejemnika ni povečala.

V najboljšem primeru so možne razmerja ena proti ena med vhodom in izhodom in se koristne informacije ne izgubijo; v najslabšem primeru o vhodnih simbolih iz izhodnih simbolov kanala za prenos informacij ne moremo ničesar reči, koristne informacije se v kanalu popolnoma izgubijo.

Ocenimo izgubo informacij v šumnem kanalu in količino informacij, ki se prenašajo po šumnem kanalu. Štejemo, da je bil znak pravilno poslan, če je s posredovanim znakom 6 sprejet

simbol bj z isto številko (/= j). Nato za idealen kanal brez šuma zapišemo:

Po simbolu bj-na izhodu kanala zaradi neenakosti (5.21)

negotovost je neizogibna. Domnevamo lahko, da so podatki v simbolu b i se ne prenese v celoti in del se izgubi v kanalu zaradi motenj. Na podlagi koncepta kvantitativnega merila informacije bomo domnevali, da je numerični izraz negotovosti, ki se pojavi na izhodu kanala po prejemu simbola ft ; :

in določa količino izgubljenih informacij v kanalu med prenosom.

Pritrditev ft. in s povprečenjem (5.22) po vseh možnih simbolih dobimo vsoto

ki določa količino izgubljenih informacij v kanalu pri prenosu osnovnega simbola po kanalu brez pomnilnika ob sprejemu simbola bj(t).

Pri povprečenju vsote (5.23) po vseh ft dobimo vrednost Z?), ki jo označimo z n(v/v- Določa količino izgubljenih informacij pri prenosu enega znaka po kanalu brez spomina:

kje P^bjbjj- skupna verjetnost dogodka, ki ob prenosu

simbol b. prevzel bo simbol b t .

V [w/ odvisno od značilnosti vira informacij o

kanalski vhod V in o verjetnostnih značilnostih komunikacijskega kanala. Po Shannon v teoriji statistične komunikacije n (v/in se imenuje nezanesljivost kanala.

Pogojna entropija HB/B, entropija diskretnega vira

na vhodu kanala V (Š) in entropijo IN ^B) na njegovem izhodu ne more biti

negativno. V kanalu brez motenj nezanesljivost kanala

n(v/v = 0. V skladu z (5.20) ugotavljamo, da H^v/v^

in enakost nastopi le, če sta vhod in izhod kanala statistično neodvisna:

Izhodni simboli niso odvisni od vhodnih simbolov - v primeru pokvarjenega kanala ali zelo močnih motenj.

Kot prej, za tipična zaporedja lahko pišemo

reči, da je v odsotnosti motenj njegova nezanesljivost

Pod informacijami, ki se v povprečju prenašajo po kanalu J[ b/ na simbol razumemo razliko med količino informacij na vhodu kanala J(B) in informacije izgubljene v kanalu /?).

Če sta vir informacij in kanal brez pomnilnika, potem

Izraz (5.27) določa entropijo izhodnih simbolov kanala. Del informacij na izhodu kanala je uporaben, preostanek pa napačen, saj nastane zaradi motenj v kanalu. Naj opozorimo na to n[v/ 2?) izraža informacijo o motnjah v kanalu, razlika i(d)-I(d/d) pa je koristna informacija, ki je prešla skozi kanal.

Upoštevajte, da je velika večina zaporedij, ki nastanejo na izhodu kanala, netipičnih in imajo zelo majhno skupno verjetnost.

Praviloma se upošteva najpogostejša vrsta motenj - aditivni šum. N(t); Signal na izhodu kanala ima obliko:

Za diskretne signale ima enakovredni šum, ki izhaja iz (5.28), diskretno strukturo. Šum je diskretno naključno zaporedje, podobno zaporedju vhodnih in izhodnih signalov. Označimo simbole abecede aditivnega šuma v diskretnem kanalu kot C1 = 0, 1,2, T- ena). Pogojne prehodne verjetnosti v takem kanalu

Ker IN (^B/?) In (B) potem posledično informacije o izhodnem zaporedju diskretnega kanala #(/) glede na vhod B(t) ali obratno In (B) - H ^ v / v) (5).

Z drugimi besedami, informacije, ki se prenašajo po kanalu, ne morejo preseči informacij na njegovem vhodu.

Če kanalski vhod prejme povprečje x k simbolov v eni sekundi, potem je mogoče določiti povprečno hitrost prenosa informacij po kanalu s šumom:

kje Н(В) = V k J(B,B^ - zmogljivost vira na vhodu kanala; n (in / in) \u003d U do n (in, in) ~ nezanesljivost kanala na enoto časa; H (B) = V k H^B^- zmogljivost vira, ki ga tvori izhod kanala (oddaja del koristnih in del napačnih informacij); H ^ in / B ^ \u003d U do 1 / (in / in)- količino napačnih informacij,

ustvarjene motnje v kanalu na enoto časa.

Koncepti količine in hitrosti prenosa informacij po kanalu se lahko uporabljajo za različne odseke komunikacijskega kanala. To je lahko razdelek "vhod kodirnika - izhod dekoderja".

Upoštevajte, da z razširitvijo odseka obravnavanega kanala ni mogoče preseči hitrosti na katerem koli njegovem sestavnem delu. Vsaka nepovratna preobrazba vodi v izgubo informacij. Nepovratne transformacije vključujejo ne le vpliv motenj, temveč tudi odkrivanje, dekodiranje s kodami z redundanco. Obstajajo načini za zmanjšanje izgube prejema. To je "sprejem na splošno".

Upoštevajte pasovno širino diskretnega kanala in optimalni kodirni izrek. Shannon je predstavil lastnost, ki določa največje možne hitrosti prenosa informacij po kanalu z znanimi lastnostmi (šum) pod številnimi omejitvami na ansambel vhodnih signalov. To je pasovna širina kanala C. Za diskretni kanal

kjer je maksimum varovan z možnimi vhodnimi viri V dano Vk in glasnost abecede vhodnih znakov T.

Na podlagi definicije prepustnosti diskretnega kanala zapišemo

Upoštevajte, da je C = 0 z neodvisnim vhodom in izhodom (visoka raven hrupa v kanalu) in s tem

v odsotnosti motenj na signalu.

Za binarni simetrični kanal brez pomnilnika

riž. 5.2.

Graf odvisnosti zmogljivosti binarnega kanala od parametra R prikazano na sl. 5.2. Pri R= 1/2 pasovne širine kanala C = 0, pogojna entropija

//(/?//?) = 1. Praktični interes

graf predstavlja 0

Shannonov temeljni izrek o optimalnem kodiranju je povezan s konceptom zmogljivosti. Njegova formulacija za diskretni kanal je naslednja: če je zmogljivost vira sporočila NA) manjša od pasovne širine kanala C:

obstaja metoda optimalnega kodiranja in dekodiranja, pri kateri je verjetnost napake ali nezanesljivosti kanala n[a!A j je lahko poljubno majhen. Če

takih načinov ni.

V skladu s Shannonovim izrekom je končna vrednost Z je mejna vrednost hitrosti prenosa informacij brez napak po kanalu. Toda za hrupni kanal načini iskanja optimalne kode niso navedeni. Vendar je izrek korenito spremenil poglede na temeljne možnosti tehnologije prenosa informacij. Pred Shannon je veljalo, da je v šumnem kanalu mogoče doseči poljubno majhno verjetnost napake z zmanjšanjem hitrosti prenosa informacij na nič. To je na primer povečanje zvestobe komunikacije zaradi ponavljanja znakov v kanalu brez spomina.

Znanih je več strogih dokazov Shannonovega izreka. Za diskretni kanal brez spomina je bil izrek dokazan z naključnim kodiranjem. V tem primeru se upošteva nabor vseh naključno izbranih kod za dani vir in dani kanal in uveljavlja dejstvo asimptotičnega pristopa k ničli povprečne verjetnosti napačnega dekodiranja po vseh kodah z neomejenim podaljšanjem trajanja zaporedje sporočil. Tako je dokazano le dejstvo obstoja kode, ki zagotavlja možnost dekodiranja brez napak, ni pa predlagana nedvoumna metoda kodiranja. Hkrati pa med dokazovanjem postane očitno, da ob ohranjanju enakosti entropij ansambla zaporedja sporočil in ustreznega niza kodnih besed ena proti ena, uporabljenih za prenos, ansambel V treba je uvesti dodatno redundanco za povečanje medsebojne odvisnosti zaporedja kodnih simbolov. To je mogoče storiti le z razširitvijo nabora kodnih zaporedij, iz katerih so izbrane kodne besede.

Kljub temu, da glavni kodirni izrek za šumne kanale ne navaja nedvoumnih načinov izbire določene kode in jih tudi ni v dokazu izreka, se lahko pokaže, da je večina naključno izbranih kod pri kodiranju dovolj dolgega sporočila zaporedja, nekoliko presegajo povprečno verjetnost napačnega dekodiranja. Vendar pa so praktične možnosti kodiranja v dolgih blokih omejene zaradi težav pri implementaciji pomnilniških sistemov in logične obdelave zaporedij velikega števila kodnih elementov, pa tudi zaradi povečanja zamude pri prenosu in obdelavi informacij. Pravzaprav so še posebej zanimivi rezultati, ki omogočajo določitev verjetnosti napačnega dekodiranja za končne vrednosti trajanja P uporabljeni kodni bloki. V praksi so omejeni na zmerne vrednosti zakasnitve in dosežejo povečanje verjetnosti prenosa z nepopolno uporabo pasovne širine kanala.