Kada i zašto je nastala teorija kodiranja. Teorija kodiranja. Vrste kodiranja. Kodiranje. Osnovni koncepti

Teorija kodiranja – proučavanje svojstava kodova i njihove prikladnosti za postizanje zadanog cilja. Kodiranje informacija je proces njihove transformacije iz oblika pogodnog za izravnu upotrebu u oblik pogodan za prijenos, pohranu, automatsku obradu i očuvanje od neovlaštenog pristupa. Glavni problemi teorije kodiranja uključuju pitanja kodiranja jedan na jedan i složenost implementacije komunikacijskog kanala u zadanim uvjetima. U tom smislu, teorija kodiranja uglavnom razmatra sljedeća područja: kompresiju podataka, naprijed ispravljanje pogrešaka, kriptografiju, fizičko kodiranje, otkrivanje i ispravljanje pogrešaka.

Format

Tečaj se sastoji od 10 akademskih tjedana. Za uspješno rješavanje većine zadataka iz testova dovoljno je savladati gradivo izneseno na predavanjima. Seminari se bave i složenijim zadacima koji mogu zainteresirati slušatelja koji je već upoznat s osnovama.

Program tečaja

Abecedno kodiranje. Dovoljni uvjeti za jednoznačno dekodiranje: ujednačenost, prefiks, sufiks. Prepoznavanje posebnosti: Markovljev kriterij. Procjena duljine dvosmislene riječi koja se može dekodirati.
Kraft-McMillanova nejednakost; postojanje prefiksnog koda s zadanim skupom duljina riječi; posljedica univerzalnosti prefiksnih kodova.
Kodovi minimalne redundantnosti: Izjava problema, Huffmanov teorem o redukciji.
Zadatak ispravljanja i otkrivanja pogrešaka. Geometrijska interpretacija. Vrste pogrešaka. metrika Hamminga i Levenshteina. kodna udaljenost. Glavni zadaci teorije kodova za ispravljanje pogrešaka.
Varshamov-Tenengolts kodovi, algoritmi za ispravljanje pojedinačnih pogrešaka ispuštanja i umetanja simbola.
Najjednostavnije granice za parametre zamjenskih kodova za ispravljanje pogrešaka: sferne granice pakiranja, Singletonove granice, Plotkinove granice.
Ugrađivanje metričkih prostora. Lema o broju vektora u euklidskom prostoru. Granica Elias-Bassalygo.
Linijski kodovi. Definicije. Generiranje i provjera matrica. Odnos između udaljenosti koda i matrice provjere. granica Varshamov-Gilbert. sustavno kodiranje. Dekodiranje sindroma. Hammingovi kodovi.
Preostali kod. Granica Greismer-Solomon-Stiffler.
Složenost problema dekodiranja linearnih kodova: problem NCP-a (problem o najbližoj kodnoj riječi).
Reed-Solomon kodovi. Berlekamp-Welch algoritam dekodiranja.
Reed-Muller kodovi: kodna udaljenost, algoritam većinskog dekodiranja.
Varijante generalizacija Reed-Mullerove konstrukcije. Lema Lipton-DeMillo-Schwartz-Zippel. Pojam algebrogeometrijskih kodova.
Grafovi proširenja. Vjerojatnostni dokaz postojanja ekspandera. Kodovi temeljeni na bipartitnim grafovima. Kodna udaljenost kodova na temelju ekspandera. Sipser-Spielman algoritam dekodiranja.
Shanonovi teoremi za model vjerojatnosti kanala.
Aplikacije koda za ispravljanje pogrešaka. Randomizirani protokol u komunikacijskoj složenosti. McElieceova kriptoshema. Homogeni (pseudo-slučajni) skupovi temeljeni na kodovima, njihova primjena na derandomizaciju u MAX-SAT problemu.

Iz Wikipedije, slobodne enciklopedije

teorija kodiranja- znanost o svojstvima kodova i njihovoj prikladnosti za postizanje cilja.

Opće informacije

Kodiranje je proces pretvaranja podataka iz oblika prikladnog za trenutnu upotrebu u oblik pogodan za prijenos, pohranu, automatsku obradu i očuvanje od neovlaštenog pristupa. Glavni problemi teorije kodiranja su pitanja kodiranja jedan-na-jedan i složenost implementacije komunikacijskog kanala pod zadanim uvjetima:86. U tom smislu, teorija kodiranja uglavnom razmatra sljedeća područja:18:

Kompresija podataka

Ispravljanje pogreške naprijed

Kriptografija

Kriptografija (od drugog grč. κρυπτός - skriveno i γράφω - pišem), ovo je područje znanja o metodama za osiguranje povjerljivosti (nemogućnost čitanja informacija strancima), integriteta podataka (nemogućnost neprimjetne promjene informacija), autentifikacije (provjera autentičnosti ili drugih svojstava objekta), kao i nemogućnost odbijanja autorstva

04.04.2006. Leonid Černjak Kategorija:Tehnologije

"Otvoreni sustavi" Stvaranje računala bilo bi nemoguće da, istovremeno s njihovom pojavom, nije nastala teorija kodiranja signala Teorija kodiranja? - jedno od onih područja matematike koje je bitno utjecalo na razvoj računarstva.

"otvoreni sustavi"

Stvaranje računala bilo bi nemoguće da, istovremeno s njihovom pojavom, nije stvorena teorija kodiranja signala.

Teorija kodiranja jedno je od onih područja matematike koje je značajno utjecalo na razvoj računarstva. Njegov djelokrug se proteže na prijenos podataka stvarnim (ili bučnim) kanalima, a predmet je osiguravanje točnosti prenesenih informacija. Drugim riječima, proučava kako najbolje spakirati podatke tako da se, nakon signaliziranja, korisne informacije mogu pouzdano i jednostavno izvući iz podataka. Ponekad se teorija kodiranja miješa s enkripcijom, ali to nije točno: kriptografija rješava inverzni problem, cilj joj je otežati izdvajanje informacija iz podataka.

Potreba za kodiranjem podataka prvi put se pojavila prije više od sto pedeset godina, nedugo nakon izuma telegrafa. Kanali su bili skupi i nepouzdani, zbog čega je zadatak minimiziranja troškova i povećanja pouzdanosti prijenosa telegrama bio hitan. Problem je postao još akutniji u vezi s polaganjem transatlantskih kabela. Od 1845. u upotrebu su ušle posebne šifrarke; uz njihovu pomoć, telegrafisti su ručno "komprimirali" poruke, zamjenjujući uobičajene nizove riječi kraćim kodovima. Istodobno, za provjeru ispravnosti prijenosa počeo se koristiti paritet, metoda kojom se također provjeravala ispravnost unosa bušenih kartica u računalima prve i druge generacije. Da biste to učinili, posebno pripremljena kartica s kontrolnim zbrojem umetnuta je u zadnji ulazni špil. Ako ulazni uređaj nije bio vrlo pouzdan (ili je špil bio prevelik), mogla bi doći do pogreške. Kako bi se to ispravilo, postupak unosa se ponavljao sve dok se izračunati kontrolni zbroj ne podudara s iznosom pohranjenim na kartici. Ne samo da je ova shema nezgodna, ona također propušta dvostruke greške. Razvojem komunikacijskih kanala bio je potreban učinkovitiji mehanizam kontrole.

Prvo teorijsko rješenje problema prijenosa podataka preko bučnih kanala predložio je Claude Shannon, utemeljitelj teorije statističkih informacija. Shannon je bio zvijezda svog vremena, bio je jedan od američke akademske elite. Kao diplomirani student na Vannevar Bushu, 1940. godine dobio je Nobelovu nagradu (ne brkati s Nobelovom nagradom!), dodijeljenu znanstvenicima mlađim od 30 godina. Dok je bio u Bell Labsu, Shannon je napisao "Matematičku teoriju prijenosa poruka" (1948.), gdje je pokazao da ako je propusnost kanala veća od entropije izvora poruke, onda se poruka može kodirati tako da će biti prenijeti bez nepotrebnog odgađanja. Ovaj zaključak sadržan je u jednom od teorema koje je dokazao Shannon, a njegovo značenje se svodi na činjenicu da ako postoji kanal s dovoljnom širinom pojasa, poruka se može prenijeti s određenim vremenskim kašnjenjem. Osim toga, pokazao je teorijsku mogućnost pouzdanog prijenosa u prisutnosti šuma u kanalu. Formula C = W log ((P+N)/N), uklesana na skromnom spomeniku Shannon, postavljenom u njegovom rodnom gradu u Michiganu, uspoređuje se po vrijednosti s formulom Alberta Einsteina E = mc 2 .

Shannonov rad potaknuo je mnoga daljnja istraživanja u području teorije informacija, ali nisu imala praktičnu inženjersku primjenu. Prijelaz s teorije na praksu bio je moguć zahvaljujući naporima Richarda Hamminga, Shannonovog kolege u Bell Labsu, koji je stekao slavu otkrivanjem klase kodova koji su se nazvali "Hammingovi kodovi". Postoji legenda da je neugodnost rada s bušenim karticama na relejnom stroju za računanje Bell Model V sredinom 40-ih potaknula izum njihovih Hammingovih kodova. Dobio je vremena za rad na stroju vikendom kada nije bilo operatera, a on se sam morao petljati s unosom. Bilo kako bilo, ali Hamming je predložio kodove koji mogu ispraviti pogreške u komunikacijskim kanalima, uključujući linije prijenosa podataka u računalima, prvenstveno između procesora i memorije. Hammingovi kodovi postali su dokaz kako se mogućnosti na koje ukazuju Shannonovi teoremi mogu realizirati u praksi.

Hamming je objavio svoj rad 1950., iako interna izvješća datiraju njegovu teoriju kodiranja u 1947. Stoga neki vjeruju da Hamminga, a ne Shannon, treba smatrati ocem teorije kodiranja. Međutim, u povijesti tehnologije beskorisno je tražiti prvo.

Sigurno je samo da je Hamming prvi predložio "kodove za ispravljanje pogrešaka" (Error-Correcting Code, ECC). Moderne modifikacije ovih kodova koriste se u svim sustavima za pohranu podataka i za razmjenu između procesora i RAM-a. Jedna od njihovih varijanti, Reed-Solomon kodovi, koriste se u CD-ovima, omogućujući reprodukciju snimki bez škripe i šumova koji bi mogli uzrokovati ogrebotine i čestice prašine. Postoje mnoge verzije kodova temeljenih na Hammingu, razlikuju se po algoritmima kodiranja i broju bitova za provjeru. Takvi su kodovi dobili poseban značaj u vezi s razvojem komunikacija dubokog svemira s međuplanetarnim stanicama, na primjer, postoje Reed-Mullerovi kodovi, gdje postoje 32 kontrolna bita za sedam informacijskih bita, odnosno 26 za šest.

Među najnovijim ECC kodovima treba spomenuti kodove LDPC (Low-Density Parity-check Code). Naime, oni su poznati već tridesetak godina, ali poseban interes za njih otkriven je upravo posljednjih godina, kada se počela razvijati televizija visoke razlučivosti. LDPC kodovi nisu 100% pouzdani, ali se stopa pogreške može podesiti na željenu razinu, uz maksimalno korištenje propusnosti kanala. “Turbo kodovi” su im bliski, učinkoviti su u radu s objektima koji se nalaze u dubokom svemiru i s ograničenom propusnošću kanala.

Ime Vladimira Aleksandroviča Kotelnikova čvrsto je upisano u povijest teorije kodiranja. Godine 1933. u "Materialima o radijskim komunikacijama za Prvi svesavezni kongres o tehničkoj rekonstrukciji komunikacija" objavio je djelo "O širini pojasa? Eter? i? žice? Ime Kotelnikova, kao ravnopravno, uključeno je u naziv jednog od najvažnijih teorema u teoriji kodiranja. Ovaj teorem definira uvjete pod kojima se odaslani signal može vratiti bez gubitka informacija.

Ovaj teorem se naziva različito, uključujući i "WKS teorem" (kratica WKS preuzeta je od Whittaker, Kotelnikov, Shannon). U nekim se izvorima koriste i Nyquist-Shannonov teorem uzorkovanja i Whittaker-Shannon teorem uzorkovanja, a u domaćim sveučilišnim udžbenicima najčešće se nalazi jednostavno "Kotelnikovov teorem". Zapravo, teorem ima dužu povijest. Njegov prvi dio dokazao je 1897. godine francuski matematičar Emile Borel. Edmund Whittaker dao je svoj doprinos 1915. Japanac Kinnosuki Ogura objavio je 1920. godine ispravke Whittakerovih istraživanja, a 1928. Amerikanac Harry Nyquist doradio je principe digitalizacije i rekonstrukcije analognog signala.

Claude Shannon(1916. - 2001.) od školskih godina pokazuje podjednak interes za matematiku i elektrotehniku. Godine 1932. upisao je Sveučilište u Michiganu, 1936. - na Massachusetts Institute of Technology, na kojem je diplomirao 1940. godine, stekavši dvije diplome - magistrirao elektrotehniku i doktorirao matematiku. Godine 1941. Shannon se pridružila Bell Laboratories. Ovdje je počeo razvijati ideje koje su kasnije rezultirale teorijom informacija. Godine 1948. Shannon je objavio članak "Matematička teorija komunikacije", gdje su formulirane osnovne ideje znanstvenika, posebice određivanje količine informacija putem entropije, a također je predložio jedinicu informacije koja određuje izbor dva jednako vjerojatne opcije, odnosno ono što je kasnije nazvano bit . U 1957-1961, Shannon je objavio radove koji su dokazali teorem propusnosti za bučne komunikacijske kanale, koji sada nosi njegovo ime. Godine 1957. Shannon je postao profesor na Massachusetts Institute of Technology, s kojeg se povukao 21 godinu kasnije. Na "zasluženom odmoru" Shannon se potpuno posvetio svojoj staroj strasti za žongliranjem. Izgradio je nekoliko strojeva za žongliranje i čak stvorio opću teoriju žongliranja.

Richard Hamming(1915. - 1998.) školovanje je započeo na Sveučilištu u Chicagu, gdje je 1937. godine diplomirao. Godine 1939. magistrirao je na Sveučilištu Nebraska i doktorirao matematiku na Sveučilištu Illinois. Godine 1945. Hamming je počeo raditi na Projektu Manhattan, golemom vladinom istraživačkom naporu za izradu atomske bombe. Godine 1946. Hamming se pridružio Bell Telephone Laboratories, gdje je radio s Claudeom Shanonom. Godine 1976. Hamming je dobio katedru na Pomorskoj poslijediplomskoj školi u Montereyu u Kaliforniji.

Rad koji ga je proslavio, temeljna studija o otkrivanju pogrešaka i kodovima za ispravljanje, objavio je Hamming 1950. godine. Godine 1956. sudjelovao je u razvoju jednog od ranih velikih računala IBM 650. Njegov rad je postavio temelje za programski jezik koji je kasnije evoluirao u programske jezike visoke razine. U znak priznanja za Hammingov doprinos području računalne znanosti, IEEE je ustanovio Medalju za izuzetne usluge za računalne znanosti i teoriju sustava nazvanu po njemu.

Vladimir Kotelnikov(1908. - 2005.) 1926. godine upisao je elektrotehnički odsjek Moskovske Više tehničke škole po imenu NE Bauman (MVTU), ali je diplomirao na Moskovskom energetskom institutu (MPEI), koji se odvojio od MVTU-a kao samostalni institut. . Dok je studirao na postdiplomskom studiju (1931.-1933.), Kotelnikov je matematički precizno formulirao i dokazao "referentni teorem", koji je kasnije dobio ime po njemu. Nakon što je 1933. završio postdiplomski studij, Kotelnikov je ostao predavati na Moskovskom elektroenergetskom institutu i otišao je raditi u Središnji istraživački institut za komunikacije (TsNIIS). Godine 1941. V. A. Kotelnikov je formulirao jasan stav o zahtjevima koje matematički nedešifrirajući sustav treba zadovoljiti i dan je dokaz o nemogućnosti dešifriranja. Godine 1944. Kotelnikov je preuzeo mjesto profesora, dekana Radiotehničkog fakulteta MPEI, gdje je radio do 1980. godine. Godine 1953., u dobi od 45 godina, Kotelnikov je odmah izabran za redovitog člana Akademije znanosti SSSR-a. Od 1968. do 1990. V. A. Kotelnikov je također bio profesor, voditelj odjela na Moskovskom institutu za fiziku i tehnologiju.

Rođenje teorije kodiranja

Teorija kodiranja. Vrste kodiranja Osnovni pojmovi teorije kodiranja Ranije su alati za kodiranje imali pomoćnu ulogu i nisu se smatrali zasebnim predmetom matematičkog proučavanja, ali s pojavom računala situacija se radikalno promijenila. Kodiranje doslovno prožima informacijsku tehnologiju i središnje je pitanje u rješavanju raznih (praktički svih) programskih zadataka: ۞ predstavljanje podataka proizvoljne prirode (na primjer, brojevi, tekst, grafika) u memoriji računala; ۞ zaštita informacija od neovlaštenog pristupa; ۞ Osiguravanje otpornosti na buku tijekom prijenosa podataka komunikacijskim kanalima; ۞ kompresija informacija u bazama podataka. Teorija kodiranja je grana teorije informacija koja proučava kako se poruke mogu identificirati sa signalima koji ih predstavljaju. Zadatak: Koordinirati izvor informacija s komunikacijskim kanalom. Predmet: diskretne ili kontinuirane informacije koje se potrošaču dostavljaju putem izvora informacija. Kodiranje je transformacija informacija u formulu prikladnu za prijenos preko određenog komunikacijskog kanala. Primjer kodiranja u matematici je koordinatna metoda koju je uveo Descartes, a koja omogućuje proučavanje geometrijskih objekata kroz njihov analitički izraz u obliku brojeva, slova i njihovih kombinacija – formula. Koncept kodiranja znači pretvorbu informacija u oblik pogodan za prijenos preko određenog komunikacijskog kanala. Dekodiranje je vraćanje primljene poruke iz kodiranog oblika u oblik koji je dostupan potrošaču.

Tema 5.2. Abecedno kodiranje U općem slučaju, problem kodiranja se može prikazati na sljedeći način. Neka su date dvije abecede A i B koje se sastoje od konačnog broja znakova: i. Elementi abecede nazivaju se slovima. Uređeni skup u abecedi A zvati će se riječju, gdje je n =l()=| |. , broj n pokazuje broj slova u riječi i naziva se duljina riječi, prazna riječ se označava: Za riječ, slovo a1, naziva se početak ili prefiks riječi, slovo an je završetak ili postfiks riječi. , a Riječi se mogu kombinirati. Da biste to učinili, prefiks druge riječi mora odmah slijediti postfiks prve, dok u novoj riječi prirodno gube status, osim ako je jedna od riječi prazna. Složenica riječi i označava se, osim toga, označava se složenica od n identičnih riječi. Skup svih nepraznih riječi abecede A označava se s A*: Skup A naziva se abeceda poruka, a skup B naziva se kodna abeceda. Skup riječi sastavljenih u abecedi B označit će se s B*.

Označimo sa F preslikavanje riječi iz abecede A u abecedu B. Tada se riječ naziva kodom riječi. Kodiranje je univerzalni način prikazivanja informacija tijekom njihove pohrane, prijenosa i obrade u obliku sustava korespondencije između elemenata poruke i signala s kojima se ti elementi mogu fiksirati. Dakle, kod je pravilo za nedvosmislenu transformaciju (tj. funkciju) poruke iz jednog oblika simboličkog prikaza (izvorna abeceda A) u drugi (abeceda objekta B), obično bez ikakvog gubitka informacija. Proces pretvaranja F: A* B*→ riječi izvorne abecede A u abecedu B naziva se informacijsko kodiranje. Proces vraćanja riječi naziva se dekodiranje. Dakle, dekodiranje je obrnuto od F, tj. F1. u riječ Budući da se za bilo koje kodiranje mora izvesti operacija dekodiranja, preslikavanje mora biti inverzibilno (bijekcija). Ako je |B|= m, tada se F naziva mimičkim kodiranjem, a najčešći slučaj je B = (0, 1) binarno kodiranje. Upravo je ovaj slučaj razmatran u nastavku. Ako sve kodne riječi imaju istu duljinu, tada se kod naziva uniformni ili blok. Abecedno (ili slovo po slovo) kodiranje može se odrediti pomoću tablice kodova. Neka zamjena poslužit će kao funkcija koda ili kodiranja. Onda gdje,. Takvo kodiranje slovo po slovo označava se kao skup elementarnih kodova. Abecedno kodiranje može se koristiti za bilo koji skup poruka. Stoga je alfabetsko kodiranje najjednostavnije i uvijek se može unijeti na nepraznim alfabetima. . Mnogi slovni kodovi

PRIMJER Neka su dane abecede A = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) B = (0, 1). Tada tablica kodiranja može biti zamjena: . Ovo je BCD kodiranje, jedan-na-jedan je i stoga dekodirano. Međutim, shema nije jednoznačna. Na primjer, skup od šest 111111 može odgovarati i riječi 333 i 77, kao i 111111, 137, 3311 ili 7111 plus bilo koja permutacija. Abecedna shema kodiranja naziva se prefiks ako osnovni kod jednog slova nije prefiks elementarnog koda drugog slova. Za alfabetsku shemu kodiranja kaže se da je odvojiva ako se bilo koja riječ sastavljena od elementarnih kodova razlaže u elementarne kodove na jedinstven način. Abecedno kodiranje s odvojivom shemom omogućuje dekodiranje. Može se dokazati da je shema prefiksa odvojiva. Da bi abecedna shema kodiranja bila odvojiva, duljine elementarnih kodova moraju zadovoljiti relaciju poznatu kao Macmillanova nejednakost. Macmillanova nejednakost Ako je alfabetska shema kodiranja

je odvojiv, onda vrijedi sljedeća nejednakost. elementarni kod slova a je prefiks elementarnog koda slova b. Tema 5.3. Minimalno redundantno kodiranje U praksi je važno da kodovi poruka budu što kraći. Abecedno kodiranje je prikladno za sve poruke, ali ako se ništa ne zna o skupu svih riječi abecede A, teško je precizno formulirati problem optimizacije. Međutim, u praksi su često dostupne dodatne informacije. Na primjer, za poruke predstavljene na prirodnom jeziku, takve dodatne informacije mogu biti distribucija vjerojatnosti pojavljivanja slova u poruci. Tada problem konstruiranja optimalnog koda dobiva točnu matematičku formulaciju i rigorozno rješenje.

Neka je dana neka odvojiva abecedna shema kodiranja. Tada će svaka shema u kojoj je uređeni skup permutacija uređenog skupa također biti odvojiva. U ovom slučaju, ako su duljine elementarnog skupa kodova jednake, tada njihova permutacija u shemi ne utječe na duljinu kodirane poruke. U slučaju da su duljine elementarnih kodova različite, tada duljina koda poruke izravno ovisi o tome koji elementarni kodovi odgovaraju kojim slovima, te o sastavu slova u poruci. S obzirom na određenu poruku i specifičnu shemu kodiranja, moguće je odabrati takvu permutaciju kodova, u kojoj će duljina koda poruke biti minimalna. Algoritam za dodjelu elementarnih kodova, u kojem će duljina fiksnog koda poruke S biti minimalna za fiksnu shemu: ۞ sortirajte slova silaznim redoslijedom prema broju pojavljivanja; ۞ sortirati elementarne kodove uzlaznim redoslijedom duljine; ۞ stavite šifre u skladu sa slovima propisanim redoslijedom. Neka se zadaju abeceda i vjerojatnosti pojavljivanja slova u poruci:

Gdje je pi vjerojatnost pojavljivanja slova ai, a slova s nultom vjerojatnošću pojavljivanja u poruci su isključena i slova su poređana silaznim redoslijedom vjerojatnosti njihovog pojavljivanja poruka, koja je označena i definirana kao PRIMJER. Za odvojivu alfabetsku shemu kodiranja A=(a,b), B=(0,1), pod distribucijom vjerojatnosti, trošak kodiranja je, a pod distribucijom vjerojatnosti, trošak kodiranja je

Tema 5.4. Huffmanovo kodiranje Ovaj algoritam izumio je 1952. David Huffman. Tema 5.5. Aritmetičko kodiranje Kao i kod Huffmanovog algoritma, sve počinje s tablicom elemenata i odgovarajućim vjerojatnostima. Pretpostavimo da se ulazna abeceda sastoji od samo tri elementa: a1, a2 i a3, au isto vrijeme P(a1) = 1/2 P(a2) = 1/3 P(a3) = 1/6 Pretpostavimo i da nam je potrebno za kodiranje sekvence a1, a1, a2, a3 . Podijelimo interval , gdje je p neki fiksni broj, 0<р<(r1)/2r, а "мощностная" граница где Tr(p)=p logr(p/(r 1))(1р)logr(l p), существенно улучшена. Имеется предположение, чт о верхняя граница полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir(п,[ рп])~пТ r(2р).Доказательство или опровержение этого предположения одна из центральны х задач теории кодирования. Большинство конструкций помехоустойчивых кодов являются эффективными, когда длин а пкода достаточновелика. В связи с этим особое значение приобретают вопросы, связанны е со сложностью устройств,осуществляющих кодирование и декодирование (кодера и деко дера). Ограничения на допустимый типдекодера или его сложность могут приводить к увел ичению избыточности, необходимой для обеспечениязаданной помехоустойчивости. Напр., минимальная избыточность кода в В n 2, для крого существует декодер,состоящий из регист

ra pomak i jedan većinski element i ispravljanje jedne greške, ima red (usporedi s (2)). Kao matematički Modeli kodera i dekodera obično se razmatraju iz sklopa funkcionalnih elemenata, a složenost se shvaća kao broj elemenata u krugu. Za poznate klase kodova za ispravljanje pogrešaka rađena je studija mogućih algoritama za K. i D. te su dobivene gornje granice složenosti kodera i dekodera. Neki odnosi su također pronađeni između brzine kodiranja, otpornosti kodiranja na buku i složenosti dekodera (vidi ). Drugi smjer istraživanja u teoriji kodiranja vezan je uz činjenicu da mnogi rezultati (na primjer, Shanonov teorem i granica (3)) nisu "konstruktivni", već su teoremi o postojanju beskonačnih nizova (Kn) kodova. s obzirom, ulažu se napori Kako bi se dokazali ovi rezultati u klasi takvih nizova (Kn) kodova, za kp postoji Turingov stroj koji prepoznaje da proizvoljna riječ duljine l pripada skupu u vremenu koji ima spor redoslijed rasta s obzirom na l (npr. llog l). Neke nove konstrukcije i metode za izvođenje granica razvijene u teoriji kodiranja dovele su do značajnog napretka u pitanjima koja su na prvi pogled vrlo daleko od tradicionalnih problema teorije kodiranja. Ovdje treba istaknuti korištenje maksimalnog koda s ispravkom jedne pogreške u simptomatično optimalnoj metodi realizacije funkcija algebre logike kontaktnim krugovima; temeljno poboljšanje gornje granice za gustoću pakiranja re-dimenzionalni euklidski prostor jednakim kuglicama; o korištenju nejednakosti (1) u procjeni složenosti implementacije formulama jedne klase funkcija algebre logike. Ideje i rezultati teorije kodiranja nalaze svoj daljnji razvoj u problemima sinteze samoispravljajućih sklopova i pouzdanih sklopova iz nepouzdanih elemenata. Lit .: Shannon K., Radovi o teoriji informacija i kibernetici, trans. s engleskog, M., 1963.; Berlekamp E., Algebarska teorija kodiranja, trans. s engleskog, M., 1971.; Peterson, W., Weldon, E., Kodovi za ispravljanje pogrešaka, trans. s engleskog, 2. izd., M., 1976.; Diskretna matematika i matematička pitanja kibernetike, vol. 1, M., 1974., odjeljak 5; Bassalygo L. A., Zyablov V. V., Pinsker M. S., "Problemi prijenosa informacija", 1977, vol. 13, br. 3, str. 517; [U] V. M. Sidelnikov, "Mat. Sat.", 1974, v. 95, c. 1, str. 148 58. V. I. Levenshtein.

Matematička enciklopedija. - M.: Sovjetska enciklopedija. I. M. Vinogradov. 1977-1985.  ALFABEDIČNO KODIRANJE  KOEUKLIDSKI PROSTOR Vidi i u drugim rječnicima:  DEKODIRANJE - vidi Kodiranje i dekodiranje ... Enciklopedija matematike  Audio kodiranje - Ovaj članak treba wikiificirati. Molimo, formatirajte ga prema pravilima za oblikovanje članaka. Osnova kodiranja zvuka pomoću osobnog računala je proces pretvaranja zračnih vibracija u električne vibracije... Wikipedia kodne slike), izveden prema definiciji. pravila, ukupnost k ryh naz. šifra K., ... ... Filozofska enciklopedija  KODIRANJE INFORMACIJA - uspostavljanje korespondencije između elemenata poruke i signala, uz pomoć kojih se ti elementi mogu fiksirati. Neka je B skup elemenata poruke, A abeceda sa simbolima, Neka se nazove konačni niz simbola. jednom riječju u ... ... Fizička enciklopedija  OPTIMALNO KODIRANJE - (u inženjerskoj psihologiji) (eng. optimal coding) stvaranje kodova koji osiguravaju maksimalnu brzinu i pouzdanost primanja i obrade informacija o objektu kojim upravlja ljudski operater (vidi Prijem informacija, dekodiranje). Problem K. o. ... ... Velika psihološka enciklopedija  DEKODIRANJE (u inženjerskoj psihologiji) - (englesko dekodiranje) konačna operacija procesa primanja informacija od strane ljudskog operatera, koja se sastoji u ponovnom šifriranju parametara koji karakteriziraju stanje kontrolnog objekta, i njihovo prevođenje u sliku kontroliranog objekta (vidi Kodiranje ... ... Velika psihološka enciklopedija

 Dekodiranje – obnavljanje poruke kodirane odaslanim i primljenim signalima (vidi Kodiranje) ... Ekonomsko-matematički rječnik  KODIRANJE – KODIRANJE. Jedna od faza generiranja govora, dok je "dekodiranje" recepcija i interpretacija, proces razumijevanja govorne poruke. Vidi psiholingvistika... Novi rječnik metodičkih pojmova i pojmova (teorija i praksa nastave jezika)  KODIRANJE - (englesko kodiranje). 1. Transformacija signala iz jednog oblika energije u drugi 2. Transformacija jednog sustava signala ili znakova u druge, što se često naziva i "transkodiranje", "promjena koda" (za govor, "prijevod"). 3. K. (mnemotehnika) ... ... Velika psihološka enciklopedija  Dekodiranje - Ovaj je članak o kodu u teoriji informacija, za druga značenja ove riječi pogledajte kod (višeznačna odrednica). Kod je pravilo (algoritam) za usklađivanje svake određene poruke sa strogo definiranom kombinacijom simbola (znakova) (ili signala). Također se naziva kod... ... Optimalno kodiranje Ista poruka može se kodirati na različite načine. Optimalno kodirani kod je onaj u kojem se minimalno vrijeme troši na prijenos poruke. Ako prijenos svakog elementarnog znaka (0 ili 1) traje isto vrijeme, tada će optimalan kod biti onaj koji će imati najmanju moguću duljinu. Primjer 1. Neka postoji slučajna varijabla X(x1,x2,x3,x4,x5,x6,x7,x8) koja ima osam stanja s distribucijom vjerojatnosti Za kodiranje abecede od osam slova ujednačenim binarnim kodom potrebna su nam tri znakovi: Ovaj 000, 001, 010, 011, 100, 101, 110, 111 Da biste odgovorili je li ovaj kod dobar ili ne, potrebno ga je usporediti s optimalnom vrijednošću, odnosno odrediti entropiju

Odredivši redundanciju L formulom L=1H/H0=12,75/3=0,084, vidimo da je moguće smanjiti duljinu koda za 8,4%. Postavlja se pitanje: je li moguće sastaviti šifru u kojoj će u prosjeku biti manje elementarnih znakova po slovu. Takvi kodovi postoje. To su kodovi ShannonFano i Huffman. Princip konstruiranja optimalnih kodova: 1. Svaki elementarni znak mora nositi maksimalnu količinu informacija, za to je potrebno da se elementarni znakovi (0 i 1) u kodiranom tekstu pojavljuju u prosjeku jednako često. Entropija će u ovom slučaju biti maksimalna. 2. Potrebno je da se slovima primarne abecede, koja imaju veću vjerojatnost, dodijele kraće kodne riječi sekundarne abecede.

Za analizu različitih izvora informacija, kao i kanala njihovog prijenosa, potrebno je imati kvantitativno mjerilo koje bi omogućilo procjenu količine informacija sadržanih u poruci i nošenih signalom. Takvu je mjeru 1946. uveo američki znanstvenik C. Shannon.

Nadalje, pretpostavljamo da je izvor informacija diskretan, dajući niz elementarnih poruka (i,), od kojih je svaka odabrana iz diskretnog ansambla (abecede) a, a 2,...,d A; Do je volumen abecede izvora informacija.

Svaka elementarna poruka sadrži određene informacije kao skup informacija (u primjeru koji se razmatra) o stanju dotičnog izvora informacija. Za kvantificiranje mjere ove informacije nije važan njezin semantički sadržaj, kao ni stupanj važnosti te informacije za primatelja. Imajte na umu da prije primanja poruke primatelj uvijek nije siguran koja sam poruka. od svih mogućih bit će mu dano. Ova nesigurnost se procjenjuje korištenjem prethodne vjerojatnosti P(i,) prijenosa poruke i,. Zaključujemo da je objektivna kvantitativna mjera informacije sadržane u elementarnoj poruci diskretnog izvora postavljena vjerojatnošću odabira dane poruke i određuje cc kao funkciju te vjerojatnosti. Ista funkcija karakterizira stupanj nesigurnosti koji primatelj informacije ima u pogledu stanja diskretnog izvora. Može se zaključiti da stupanj neizvjesnosti o očekivanim informacijama određuje zahtjeve za kanalima prijenosa informacija.

Općenito, vjerojatnost Godišnje,) izbor izvora neke elementarne poruke i, (u nastavku ćemo je zvati simbolom) ovisi o prethodno odabranim simbolima, t.j. je uvjetna vjerojatnost i neće se podudarati s apriornom vjerojatnošću takvog izbora.

Tim taj ^ Godišnje:) = 1, budući da svi i čine kompletnu grupu događaja

gyi), a izbor ovih simbola provodi se pomoću neke funkcionalne ovisnosti J(a,)= P(a,) = 1, ako je izbor simbola prema izvoru a priori određen, J(a,)= a „ a P(a t ,a)- vjerojatnost takvog izbora, tada je količina informacija sadržana u paru simbola jednaka zbroju količine informacija sadržanih u svakom od simbola i i i. Ovo svojstvo kvantitativne mjere informacije naziva se aditivnost .

Vjerujemo u to Godišnje,)- uvjetna vjerojatnost odabira znaka i, nakon svih znakova koji mu prethode, i Godišnje,,i,) je uvjetna vjerojatnost odabira simbola i; nakon i, i svih prethodnih, ali, s obzirom na to P (a 1, a 1) \u003d P (a) P(i,|i y), uvjet aditivnosti se može napisati

Uvodimo notaciju Godišnje) = P p P (ar) \u003d Q i prepiši uvjet (5.1):

Vjerujemo u to R, O* 0. Pomoću izraza (5.2) određujemo oblik funkcije (r (R). Razlikovanjem, množenjem po R* 0 i označava RO = R, Zapiši

Zapazimo da je relacija (5.3) zadovoljena za bilo koje R f O u^^O. Međutim, ovaj zahtjev dovodi do konstantnosti desne i lijeve strane (5.3): Pq>"(P)= Ar"(/?) - Za - konst. Tada dolazimo do jednadžbe PC> "(P) = DO a nakon integracije dobivamo

Uzmimo u obzir da ćemo prepisati

Slijedom toga, pod ispunjenjem dva uvjeta o svojstvima J(a,), pokazalo se da je oblik funkcionalne ovisnosti J(a,) o vjerojatnosti odabira simbola a t do konstantnog koeficijenta DO jedinstveno definirana

Koeficijent DO utječe samo na ljestvicu i određuje sustav jedinica za mjerenje količine informacija. Od ln[P] F 0, onda ima smisla odabrati To Os tako da je mjera količine informacija J(a) bio pozitivan.

Prihvativši K=-1, zapiši

Iz toga slijedi da je jedinica količine informacija jednaka informaciji da se dogodio događaj čija je vjerojatnost jednaka Mi. Takva jedinica količine informacija naziva se prirodna jedinica. Češće se pretpostavlja da DO= -, dakle

Tako smo došli do binarne jedinice količine informacija koja sadrži poruku o nastanku jednog od dva jednako vjerojatna događaja i naziva se „bit“. Ova jedinica je raširena zbog korištenja binarnih kodova u komunikacijskoj tehnologiji. Odabirom baze logaritma u općem slučaju dobivamo

gdje logaritam može biti s proizvoljnom bazom.

Svojstvo aditivnosti kvantitativne mjere informacije omogućuje, na temelju izraza (5.9), određivanje količine informacija u poruci koja se sastoji od niza znakova. Vjerojatnost da izvor odabere takav slijed uzima se u obzir uzimajući u obzir sve prethodno dostupne poruke.

Kvantitativna mjera informacija sadržanih u elementarnoj poruci a (, ne daje predstavu o prosječnoj količini informacija J(A) izdaje izvor kada je odabrana jedna elementarna poruka a d

Prosječna količina informacija karakterizira izvor informacija u cjelini i jedna je od najvažnijih karakteristika komunikacijskih sustava.

Definirajmo ovu karakteristiku za diskretni izvor neovisnih poruka s abecedom DO. Označiti sa NA) prosječna količina informacija po znaku i matematičko je očekivanje slučajne varijable L - količina informacija sadržana u slučajno odabranom znaku a

Prosječna količina informacija po simbolu naziva se entropijom izvora neovisnih poruka. Entropija je pokazatelj prosječne apriorne nesigurnosti pri odabiru sljedećeg simbola.

Iz izraza (5.10) proizlazi da ako je jedna od vjerojatnosti Godišnje) je jednaka jedan (dakle, svi ostali su jednaki nuli), tada će entropija izvora informacija biti jednaka nuli - poruka je potpuno definirana.

Entropija će biti maksimalna ako su prethodne vjerojatnosti svih mogućih simbola jednake DO, tj. R(a() = 1 /DO, zatim

Ako izvor neovisno bira binarne simbole s vjerojatnostima P, = P(a x) i P 2 \u003d 1 - P, tada će entropija po znaku biti

Na sl. 16.1 prikazuje ovisnost entropije binarnog izvora o apriornoj vjerojatnosti izbora između dva binarna simbola, ova slika također pokazuje da je entropija maksimalna na R, = R 2 = 0,5

1 o 1 dvd - i u binarnim jedinicama log 2 2 = 1-

Riža. 5.1. Entropijska ovisnost pri K = 2 o vjerojatnosti odabira jednog od njih

Entropija izvora s jednako vjerojatnim izborom simbola, ali s različitim veličinama abecede DO, raste logaritamski s rastom DO.

Ako je vjerojatnost odabira simbola drugačija, onda entropija izvora pada ja (A) u odnosu na mogući maksimum H(A) psh = zapisnik DO.

Što je korelacija između simbola veća, to je manja sloboda odabira sljedećih simbola i manje informacija ima novoodabrani simbol. To je zbog činjenice da nesigurnost uvjetne distribucije ne može premašiti entropiju njihove bezuvjetne distribucije. Entropiju izvora označite pamćenjem i abecedom DO preko H(AA"), i entropija izvora bez pamćenja, ali po istoj abecedi - kroz NA) i dokazati nejednakost

Uvođenjem oznake P(aa") za uvjetnu vjerojatnost odabira simbola a,(/ = 1, 2, DO) pod pretpostavkom da je simbol prethodno odabran ajij =1,2,DO) a izostavljajući transformacije, pišemo bez dokaza

što dokazuje nejednakost (5.13).

Jednakost u (5.13) ili (5.14) postiže se kada

To znači da je uvjetna vjerojatnost odabira simbola jednaka bezuvjetnoj vjerojatnosti njegovog odabira, što je moguće samo za izvore bez memorije.

Zanimljivo je da je entropija teksta na ruskom jeziku 1,5 binarnih jedinica po znaku. U isto vrijeme, s istom abecedom K= 32 uz uvjet neovisnih i jednako vjerojatnih simbola H(A) tp = 5 binarnih po znaku. Dakle, prisutnost unutarnjih veza smanjila je entropiju za približno 3,3 puta.

Važna karakteristika diskretnog izvora je njegova redundancija p i:

Suvišnost izvora informacija je bezdimenzionalna veličina unutar . Naravno, u nedostatku redundancije p u = 0.

Za prijenos određene količine informacija iz izvora koji nema korelacije između simbola, s jednakom vjerojatnošću svih simbola, minimalni mogući broj prenesenih simbola /7 min: /r 0 (/7 0 R (L max)) je potrebno. Za prijenos iste količine informacija iz izvora s entropijom (simboli su međusobno povezani i nejednako vjerojatni), potreban je prosječan broj simbola n = n„H(A) m JH(A).

Diskretni izvor također karakterizira performanse koje su određene brojem simbola po jedinici vremena v H:

Ako izvedba ja (A) definirati u binarnim jedinicama, a zatim vrijeme u sekundama NA) - je broj binarnih jedinica u sekundi. Za diskretne izvore koji proizvode stacionarne nizove znakova dovoljno velike duljine /?, uvode se sljedeći koncepti: tipični i atipični nizovi izvornih znakova, u koje svi nizovi duljine P. Sve tipične sekvence NlMl (A) izvor na P-»oo imaju približno istu vjerojatnost pojave

Ukupna vjerojatnost pojave svih atipičnih sekvenci teži nuli. U skladu s jednakošću (5.11), uz pretpostavku da je vjerojatnost tipičnih sekvenci /N rm (A), entropija izvora je logN TIin (,4) i tada

Uzmite u obzir količinu i brzinu prijenosa informacija preko diskretnog kanala sa šumom. Prije smo razmatrali informacije koje proizvodi diskretni izvor u obliku niza znakova (i,).

Pretpostavimo sada da je izvorna informacija kodirana i predstavlja slijed kodnih simbola (b, (/ = 1,2,..T - kodna baza), u skladu je s diskretnim kanalom za prijenos informacija, na čijem se izlazu pojavljuje niz simbola

Pretpostavljamo da je operacija kodiranja jedan-na-jedan - nizom znakova (b,) može se jedinstveno vratiti niz (i,), t.j. pomoću kodnih simbola moguće je potpuno vratiti izvornu informaciju.

Međutim, ako uzmemo u obzir escape znakove |?. j i ulaznih simbola (/>,), tada je, zbog prisutnosti smetnji u kanalu za prijenos informacija, oporavak nemoguć. Entropija izlaznog niza //(/?)

može biti veća od entropije ulaznog niza H(B), ali se količina informacija za primatelja nije povećala.

U najboljem slučaju mogući su odnosi jedan-na-jedan između ulaza i izlaza i ne gube se korisne informacije, u najgorem slučaju ne može se ništa reći o ulaznim simbolima iz izlaznih simbola kanala za prijenos informacija, korisne informacije potpuno su izgubljene u kanalu.

Procijenimo gubitak informacija u bučnom kanalu i količinu informacija prenesenih preko šumnog kanala. Smatramo da je znak ispravno prenesen ako je s prenesenim znakom 6 primljen

simbol bj s istim brojem (/= j). Zatim za idealan kanal bez šuma pišemo:

Po simbolu bj-na izlazu kanala zbog nejednakosti (5.21)

neizvjesnost je neizbježna. Možemo pretpostaviti da su informacije u simbolu b i ne prenosi se u potpunosti i dio se gubi u kanalu zbog smetnji. Na temelju koncepta kvantitativne mjere informacije, pretpostavit ćemo da je numerički izraz nesigurnosti koji se javlja na izlazu kanala nakon primanja simbola ft ; :

i određuje količinu izgubljenih informacija u kanalu tijekom prijenosa.

Učvršćivanje ft. i usrednjavanjem (5.22) po svim mogućim simbolima dobivamo zbroj

koji određuje količinu izgubljene informacije u kanalu prilikom prijenosa elementarnog simbola preko kanala bez memorije prilikom primanja simbola bj(t).

Usrednjavanjem zbroja (5.23) po svim ft dobivamo vrijednost Z?), koju označavamo sa n(u/u- Određuje količinu izgubljenih informacija prilikom prijenosa jednog znaka preko kanala bez memorije:

gdje P^bjbjj- zajednička vjerojatnost događaja koji, kada se prenese

simbol b. to će uzeti simbol b t .

H [w/ ovisi o karakteristikama izvora informacija o

kanalski ulaz V te o vjerojatnostim karakteristikama komunikacijskog kanala. Prema Shanonu u teoriji statističke komunikacije n(u/in naziva se nepouzdanost kanala.

Uvjetna entropija HB/B, entropija diskretnog izvora

na ulazu kanala V (Š) i entropija I ^B) na svom izlazu ne može biti

negativan. U kanalu bez smetnji, nepouzdanost kanala

n(v/v = 0. U skladu s (5.20) primjećujemo da H^v/v^

a jednakost se događa samo kada su ulaz i izlaz kanala statistički neovisni:

Izlazni simboli ne ovise o ulaznim simbolima - u slučaju pokvarenog kanala ili vrlo jakih smetnji.

Kao i prije, za tipične sekvence možemo pisati

reći da u nedostatku smetnji, njegova nepouzdanost

Pod informacijama prosječno proslijeđenim putem kanala J[ b/ po simbolu razumijemo razliku između količine informacija na ulazu kanala J(B) i informacije izgubljene u /? kanalu).

Ako su izvor informacija i kanal bez memorije, onda

Izraz (5.27) određuje entropiju izlaznih simbola kanala. Dio informacija na izlazu kanala je koristan, a ostatak je lažan, jer nastaje interferencijom u kanalu. Zabilježimo to n[v/ 2?) izražava informaciju o smetnji u kanalu, a razlika i(d)-I(d/d) - korisna informacija koja je prošla kroz kanal.

Imajte na umu da je velika većina sekvenci formiranih na izlazu kanala netipične i imaju vrlo malu ukupnu vjerojatnost.

U pravilu se uzima u obzir najčešća vrsta smetnji - aditivni šum. N(t); Signal na izlazu kanala ima oblik:

Za diskretne signale, ekvivalentni šum, koji slijedi iz (5.28), ima diskretnu strukturu. Šum je diskretni slučajni niz sličan nizovima ulaznih i izlaznih signala. Označimo simbole abecede aditivne buke u diskretnom kanalu kao C1 = 0, 1,2, T- jedan). Uvjetne prijelazne vjerojatnosti u takvom kanalu

Jer I (^B/?) I (B) zatim, posljedično, informacije o izlaznom nizu diskretnog kanala #(/) u odnosu na ulaz B(t) ili obrnuto I (B) - H ^ u / u) (5).

Drugim riječima, informacija koja se prenosi preko kanala ne može premašiti informaciju na njegovom ulazu.

Ako ulaz kanala primi prosjek x k simbola u jednoj sekundi, tada je moguće odrediti prosječnu brzinu prijenosa informacija preko kanala sa šumom:

gdje N(V) = V k J(B,B^ - performanse izvora na ulazu kanala; n (u / u) \u003d U do n (u, u) ~ nepouzdanost kanala u jedinici vremena; H (B) = V k H^B^- performanse izvora formirane izlazom kanala (daje dio korisnih i dio lažnih informacija); H ^ in / B ^ \u003d U do 1 / (in / in)- količina lažnih informacija,

stvorene smetnje u kanalu u jedinici vremena.

Koncepti količine i brzine prijenosa informacija preko kanala mogu se primijeniti na različite dijelove komunikacijskog kanala. Ovo može biti odjeljak "ulaz kodera - izlaz dekodera".

Imajte na umu da je proširenjem dijela kanala koji se razmatra nemoguće prekoračiti brzinu na bilo kojem od njegovih sastavnih dijelova. Svaka nepovratna transformacija dovodi do gubitka informacija. Nepovratne transformacije uključuju ne samo utjecaj smetnji, već i detekciju, dekodiranje kodovima s redundantnošću. Postoje načini da se smanji gubitak primanja. Ovo je "recepcija općenito".

Razmotrimo širinu pojasa diskretnog kanala i optimalni teorem kodiranja. Shannon je uveo karakteristiku koja određuje maksimalne moguće brzine prijenosa informacija preko kanala s poznatim svojstvima (šum) uz niz ograničenja na ansambl ulaznih signala. Ovo je širina pojasa kanala C. Za diskretni kanal

gdje je maksimum čuvan mogućim ulaznim izvorima V dano Vk i glasnoća abecede ulaznih znakova T.

Na temelju definicije propusnosti diskretnog kanala pišemo

Imajte na umu da je C = 0 s neovisnim ulazom i izlazom (visoka razina šuma u kanalu) i, sukladno tome,

u nedostatku smetnji na signalu.

Za binarni simetrični kanal bez memorije

Riža. 5.2.

Grafikon ovisnosti kapaciteta binarnog kanala o parametru R prikazano na sl. 5.2. Na R= 1/2 propusnosti kanala C = 0, uvjetna entropija

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

graf predstavlja 0

Shannonov temeljni teorem o optimalnom kodiranju povezan je s konceptom kapaciteta. Njegova formulacija za diskretni kanal je sljedeća: ako je izvedba izvora poruke NA) manje od propusnosti kanala C:

postoji metoda optimalnog kodiranja i dekodiranja, prema kojoj je vjerojatnost pogreške ili nepouzdanosti kanala n[a!A j može biti proizvoljno mali. Ako

ne postoje takvi načini.

U skladu sa Shannonovim teoremom, konačna vrijednost S je granična vrijednost brzine prijenosa informacija bez grešaka preko kanala. Ali za bučni kanal, načini pronalaženja optimalnog koda nisu naznačeni. Međutim, teorem je radikalno promijenio poglede na temeljne mogućnosti tehnologije prijenosa informacija. Prije Shannon, vjerovalo se da je u bučnom kanalu moguće dobiti proizvoljno malu vjerojatnost pogreške smanjenjem brzine prijenosa informacija na nulu. To je, na primjer, povećanje vjernosti komunikacije kao rezultat ponavljanja znakova u kanalu bez memorije.

Poznato je nekoliko rigoroznih dokaza Shannonovog teorema. Teorem je dokazan za diskretni kanal bez memorije slučajnim kodiranjem. U ovom slučaju razmatra se skup svih nasumično odabranih kodova za dati izvor i zadani kanal te se potvrđuje činjenica asimptotičkog pristupa nuli prosječne vjerojatnosti pogrešnog dekodiranja svih kodova uz neograničeno povećanje trajanja slijed poruke. Dakle, dokazuje se samo činjenica postojanja koda koji pruža mogućnost dekodiranja bez pogrešaka, ali se ne predlaže jednoznačna metoda kodiranja. U isto vrijeme, tijekom dokaza postaje očito da, uz održavanje jednakosti entropija ansambla niza poruke i jedan-na-jedan odgovarajućeg skupa kodnih riječi korištenih za prijenos, cjelina V treba uvesti dodatnu redundantnost kako bi se povećala međusobna ovisnost slijeda kodnih simbola. To se može učiniti samo proširenjem skupa kodnih sekvenci iz kojih se biraju kodne riječi.

Unatoč činjenici da glavni teorem kodiranja za bučne kanale ne ukazuje na jednoznačne načine odabira određenog koda te ih također nema u dokazu teorema, može se pokazati da većina nasumično odabranih kodova, kada se kodira dovoljno duga poruka sekvence, neznatno premašuju prosječnu vjerojatnost pogrešnog dekodiranja . Međutim, praktične mogućnosti kodiranja u dugim blokovima ograničene su zbog poteškoća u implementaciji memorijskih sustava i logičke obrade nizova velikog broja elemenata koda, kao i zbog povećanja kašnjenja u prijenosu i obradi informacija. Zapravo, od posebnog su interesa rezultati koji omogućuju određivanje vjerojatnosti pogrešnog dekodiranja za konačne vrijednosti trajanja P korišteni blokovi koda. U praksi su ograničeni na umjerene vrijednosti kašnjenja i postižu povećanje vjerojatnosti prijenosa uz nepotpuno korištenje propusnosti kanala.