Teoria e kodeve. Teoria e kodimit

Nga Wikipedia, Enciklopedia e Lirë

teoria e kodimit- shkenca e vetive të kodeve dhe përshtatshmërisë së tyre për arritjen e qëllimit.

Informacion i pergjithshem

Kodimi është procesi i konvertimit të të dhënave nga një formë e përshtatshme për përdorim të drejtpërdrejtë në një formë të përshtatshme për transmetim, ruajtje, përpunim automatik dhe ruajtje nga aksesi i paautorizuar. Problemet kryesore të teorisë së kodimit përfshijnë çështjet e kodimit një-me-një dhe kompleksitetin e zbatimit të një kanali komunikimi në kushte të dhëna:86. Në këtë drejtim, teoria e kodimit kryesisht merr në konsideratë fushat e mëposhtme:18:

Kompresimi i të dhënave

Korrigjimi i gabimit përpara

Kriptografia

Kriptografia (nga greqishtja tjetër. κρυπτός - të fshehura dhe γράφω - Unë shkruaj), kjo është një fushë njohurish rreth metodave për sigurimin e konfidencialitetit (pamundësia e leximit të informacionit për të huajt), integriteti i të dhënave (pamundësia e ndryshimit të padukshëm të informacionit), vërtetimi (autentikimi i autorësisë ose vetive të tjera të një objekti), si dhe pamundësia e refuzimit të autorësisë

04/04/2006 Leonid Chernyak Kategoria:Teknologjitë

“Sistemet e hapura” Krijimi i kompjuterëve do të ishte i pamundur nëse njëkohësisht me paraqitjen e tyre nuk do të krijohej teoria e kodimit të sinjalit.Teoria e kodimit është një nga ato fusha të matematikës që ndikoi dukshëm në zhvillimin e informatikës.

"Sistemet e hapura"

Krijimi i kompjuterëve do të ishte i pamundur nëse, njëkohësisht me paraqitjen e tyre, nuk do të ishte krijuar teoria e kodimit të sinjalit.

Teoria e kodimit është një nga ato fusha të matematikës që ka ndikuar dukshëm në zhvillimin e informatikës. Shtrirja e tij shtrihet në transmetimin e të dhënave përmes kanaleve reale (ose të zhurmshme), dhe objekti është të sigurojë korrektësinë e informacionit të transmetuar. Me fjalë të tjera, ai studion mënyrën më të mirë për të paketuar të dhënat në mënyrë që pas sinjalizimit, informacioni i dobishëm të mund të nxirret nga të dhënat në mënyrë të besueshme dhe të lehtë. Ndonjëherë teoria e kodimit ngatërrohet me enkriptimin, por kjo nuk është e vërtetë: kriptografia zgjidh problemin e kundërt, qëllimi i saj është të vështirësojë nxjerrjen e informacionit nga të dhënat.

Nevoja për të koduar të dhënat u ndesh për herë të parë më shumë se njëqind e pesëdhjetë vjet më parë, menjëherë pas shpikjes së telegrafit. Kanalet ishin të shtrenjta dhe jo të besueshme, gjë që e bëri detyrën e minimizimit të kostos dhe rritjen e besueshmërisë së transmetimit të telegramit urgjente. Problemi është përkeqësuar nga shtrimi i kabllove transatlantike. Që nga viti 1845, librat e kodeve speciale kanë hyrë në përdorim; me ndihmën e tyre, telegrafistët "kompresuan" manualisht mesazhet, duke zëvendësuar sekuencat e zakonshme të fjalëve me kode më të shkurtra. Në të njëjtën kohë, për të kontrolluar korrektësinë e transferimit, filloi të përdoret pariteti, metodë e cila u përdor edhe për të kontrolluar korrektësinë e hyrjes së kartave të grushta në kompjuterët e gjeneratës së parë dhe të dytë. Për ta bërë këtë, një kartë e përgatitur posaçërisht me një shumë kontrolli u fut në kuvertën e fundit të hyrjes. Nëse pajisja hyrëse nuk ishte shumë e besueshme (ose kuverta ishte shumë e madhe), atëherë mund të ndodhte një gabim. Për ta korrigjuar atë, procedura e hyrjes u përsërit derisa shuma e llogaritur e kontrollit të përputhej me shumën e ruajtur në kartë. Kjo skemë jo vetëm që është e papërshtatshme, por gjithashtu nuk ka gabime të dyfishta. Me zhvillimin e kanaleve të komunikimit, kërkohej një mekanizëm më efektiv kontrolli.

Zgjidhja e parë teorike për problemin e transmetimit të të dhënave përmes kanaleve të zhurmshme u propozua nga Claude Shannon, themeluesi i teorisë së informacionit statistikor. Shannon ishte një yll i kohës së tij, ai ishte një nga elita akademike amerikane. Si student i diplomuar në Vannevar Bush, në vitin 1940 ai mori çmimin Nobel (për të mos u ngatërruar me çmimin Nobel!), dhënë shkencëtarëve nën moshën 30 vjeç. Ndërsa ishte në Bell Labs, Shannon shkroi "A Mathematical Theory of Message Transmission" (1948), ku tregoi se nëse gjerësia e brezit të kanalit është më e madhe se entropia e burimit të mesazhit, atëherë mesazhi mund të kodohet në mënyrë që të jetë transmetohet pa vonesa të panevojshme. Ky përfundim përmbahet në një nga teoremat e vërtetuara nga Shannon, kuptimi i tij zbret në faktin se nëse ekziston një kanal me gjerësi bande të mjaftueshme, një mesazh mund të transmetohet me disa vonesa kohore. Përveç kësaj, ai tregoi mundësinë teorike të transmetimit të besueshëm në prani të zhurmës në kanal. Formula C = W log ((P+N)/N), e gdhendur në një monument modest të Shannon, i instaluar në qytetin e tij të lindjes në Michigan, krahasohet në vlerë me formulën E = mc 2 të Albert Ajnshtajnit.

Puna e Shannon shkaktoi shumë kërkime të mëtejshme në fushën e teorisë së informacionit, por ato nuk kishin asnjë aplikim praktik inxhinierik. Kalimi nga teoria në praktikë u bë i mundur nga përpjekjet e Richard Hamming, kolegut të Shannon në Bell Labs, i cili fitoi famë për zbulimin e një klase kodesh që u quajtën "kodet e Hamming". Ekziston një legjendë që shqetësimi i punës me kartat me grushta në makinën llogaritëse të stafetës Bell Model V në mesin e viteve 40 nxiti shpikjen e kodeve të tyre Hamming. Atij iu dha kohë për të punuar në makinë gjatë fundjavave kur nuk kishte operatorë, dhe ai vetë duhej të merrej me të dhëna. Sido që të jetë, por Hamming propozoi kode të afta për të korrigjuar gabimet në kanalet e komunikimit, duke përfshirë linjat e transmetimit të të dhënave në kompjuterë, kryesisht midis procesorit dhe kujtesës. Kodet Hamming u bënë dëshmi se si mund të realizoheshin në praktikë mundësitë e treguara nga teoremat e Shannon-it.

Hamming botoi letrën e tij në vitin 1950, megjithëse raportet e brendshme e datojnë teorinë e tij të kodimit në vitin 1947. Prandaj, disa besojnë se Hamming, jo Shannon, duhet të konsiderohet babai i teorisë së kodimit. Sidoqoftë, në historinë e teknologjisë është e kotë të kërkosh të parën.

Është e sigurt vetëm se ishte Hamming ai që propozoi i pari "kodet e korrigjimit të gabimeve" (Error-Corecting Code, ECC). Modifikimet moderne të këtyre kodeve përdoren në të gjitha sistemet e ruajtjes së të dhënave dhe për shkëmbimin midis procesorit dhe RAM-it. Një nga variantet e tyre, kodet Reed-Solomon, përdoren në CD, duke lejuar që regjistrimet të luhen pa kërcitje dhe zhurma që mund të shkaktojnë gërvishtje dhe grimca pluhuri. Ka shumë versione të kodeve të bazuara në Hamming, ato ndryshojnë në algoritmet e kodimit dhe numrin e biteve të kontrollit. Kode të tilla kanë marrë një rëndësi të veçantë në lidhje me zhvillimin e komunikimeve në hapësirë të thellë me stacionet ndërplanetare, për shembull, ekzistojnë kodet Reed-Muller, ku ka 32 bit kontrolli për shtatë bit informacioni, ose 26 për gjashtë.

Ndër kodet e fundit ECC, duhen përmendur kodet LDPC (Kodi i kontrollit të barazisë me densitet të ulët). Në fakt, ata njihen prej rreth tridhjetë vitesh, por interesi i veçantë për ta u zbulua pikërisht në vitet e fundit, kur filloi të zhvillohej televizioni me rezolucion të lartë. Kodet LDPC nuk janë 100% të besueshme, por shkalla e gabimit mund të rregullohet në nivelin e dëshiruar, duke përdorur gjerësinë e brezit të kanalit në maksimum. "Turbo Codes" janë afër tyre, ato janë efektive kur punoni me objekte të vendosura në hapësirë të thellë dhe me gjerësi të kufizuar të kanalit.

Emri i Vladimir Alexandrovich Kotelnikov është gdhendur fort në historinë e teorisë së kodimit. Në vitin 1933, në "Materiale mbi komunikimet radiofonike për Kongresin e Parë Gjithë Bashkimit për Rindërtimin Teknik të Komunikimeve", ai botoi veprën "Për gjerësinë e brezit? Eter? dhe telat? Emri i Kotelnikov, si i barabartë, përfshihet në emrin e një prej teoremave më të rëndësishme në teorinë e kodimit. Kjo teoremë përcakton kushtet në të cilat sinjali i transmetuar mund të rikthehet pa humbje informacioni.

Kjo teoremë është quajtur ndryshe, duke përfshirë "teoremën WKS" (shkurtesa WKS është marrë nga Whittaker, Kotelnikov, Shannon). Në disa burime, përdoren si teorema e kampionimit Nyquist-Shannon ashtu edhe teorema e kampionimit Whittaker-Shannon, dhe në tekstet shkollore universitare vendase, thjesht "teorema e Kotelnikov" gjendet më shpesh. Në fakt, teorema ka një histori më të gjatë. Pjesa e parë e tij u vërtetua në 1897 nga matematikani francez Emile Borel. Edmund Whittaker kontribuoi në 1915. Në vitin 1920, japonezi Kinnosuki Ogura botoi korrigjime në kërkimin e Whittaker dhe në 1928, amerikani Harry Nyquist rafinoi parimet e dixhitalizimit dhe rindërtimit të sinjalit analog.

Claude Shannon(1916 - 2001) që nga vitet e tij shkollore tregoi interes të njëjtë për matematikën dhe inxhinierinë elektrike. Në 1932, ai hyri në Universitetin e Miçiganit, në 1936 - në Institutin e Teknologjisë të Massachusetts, nga i cili u diplomua në 1940, duke marrë dy diploma - një diplomë master në inxhinieri elektrike dhe një doktoraturë në matematikë. Në vitin 1941, Shannon u bashkua me Bell Laboratories. Këtu ai filloi të zhvillojë ide që më vonë rezultuan në teorinë e informacionit. Në vitin 1948, Shannon botoi artikullin "Teoria Matematikore e Komunikimit", ku u formuluan idetë themelore të shkencëtarit, në veçanti, përcaktimi i sasisë së informacionit përmes entropisë, dhe gjithashtu propozoi një njësi informacioni që përcakton zgjedhjen e dy. opsione po aq të mundshme, domethënë, ajo që më vonë u quajt pak . Në 1957-1961, Shannon botoi vepra që vërtetonin teoremën e xhiros për kanalet e zhurmshme të komunikimit, të cilat tani mbajnë emrin e tij. Në vitin 1957, Shannon u bë profesor në Institutin e Teknologjisë në Masaçusets, nga ku doli në pension 21 vjet më vonë. Në një "pushim të merituar" Shannon iu përkushtua plotësisht pasionit të tij të vjetër për xhonglimin. Ai ndërtoi disa makina mashtrimi dhe madje krijoi një teori të përgjithshme të mashtrimit.

Richard Hamming(1915 - 1998) filloi shkollimin në Universitetin e Çikagos, ku mori një diplomë bachelor në 1937. Në vitin 1939 ai mori një diplomë master në Universitetin e Nebraskës dhe një doktoraturë në matematikë nga Universiteti i Illinois. Në vitin 1945, Hamming filloi të punojë në Projektin Manhattan, një përpjekje masive kërkimore e qeverisë për të ndërtuar bombën atomike. Në vitin 1946, Hamming iu bashkua Bell Telephone Laboratories, ku punoi me Claude Shannon. Në vitin 1976, Hamming mori një karrige në Shkollën Pasuniversitare Detare në Monterey, Kaliforni.

Puna që e bëri atë të famshëm, një studim themelor i kodeve të zbulimit dhe korrigjimit të gabimeve, u botua nga Hamming në 1950. Në vitin 1956, ai u përfshi në zhvillimin e një prej mainframe-ve të hershme IBM 650. Puna e tij hodhi themelet për një gjuhë programimi që më vonë u zhvillua në gjuhë programimi të nivelit të lartë. Në njohje të kontributit të Hamming në fushën e shkencës kompjuterike, IEEE themeloi një Medalje të Shquar të Shërbimit për Shkencën Kompjuterike dhe Teorinë e Sistemeve të quajtur pas tij.

Vladimir Kotelnikov(1908 - 2005) në 1926 ai hyri në Fakultetin e Inxhinierisë Elektrike të Shkollës së Lartë Teknike të Moskës me emrin N. E. Bauman (MVTU), por u diplomua në Institutin e Inxhinierisë së Energjisë në Moskë (MPEI), i cili u nda nga Shkolla e Lartë Teknike e Moskës si një institut i pavarur. Ndërsa studionte në shkollën pasuniversitare (1931-1933), Kotelnikov formuloi dhe vërtetoi me saktësi matematikisht "teoremën e referencës", e cila më vonë u emërua pas tij. Pas mbarimit të shkollës pasuniversitare në 1933, Kotelnikov, duke mbetur mësimdhënës në Institutin e Inxhinierisë së Energjisë në Moskë, shkoi për të punuar në Institutin Qendror të Kërkimit të Komunikimeve (TsNIIS). Në 1941, V. A. Kotelnikov formuloi një pozicion të qartë mbi kërkesat që duhet të plotësonte një sistem matematikisht i padeshifrueshëm dhe u dha një provë për pamundësinë e deshifrimit të tij. Në vitin 1944, Kotelnikov mori detyrën e profesorit, dekanit të fakultetit radioinxhinierik të MPEI, ku punoi deri në vitin 1980. Në vitin 1953, në moshën 45-vjeçare, Kotelnikov u zgjodh menjëherë anëtar i plotë i Akademisë së Shkencave të BRSS. Nga viti 1968 deri në 1990, V. A. Kotelnikov ishte gjithashtu profesor, drejtues i një departamenti në Institutin e Fizikës dhe Teknologjisë në Moskë.

Lindja e teorisë së kodimit

04/04/2006 Leonid Chernyak Kategoria:Teknologjitë

"Sistemet e hapura"

Krijimi i kompjuterëve do të ishte i pamundur nëse, njëkohësisht me paraqitjen e tyre, nuk do të ishte krijuar teoria e kodimit të sinjalit.

Lindja e teorisë së kodimit

"Qëllimi i këtij kursi është t'ju përgatisë për të ardhmen tuaj teknike."

Hej Habr. Ju kujtohet artikulli fantastik "Ju dhe puna juaj" (+219, 2442 faqeshënues, 394 mijë lexime)?

Kështu që Hamming (po, po, kodet e Hamming vetë-kontrolluese dhe vetëkorrigjuese) ka një libër të tërë të shkruar bazuar në leksionet e tij. Ne e përkthejmë, sepse njeriu e thotë mendjen e tij.

Ky libër nuk ka të bëjë vetëm me IT-në, ky është një libër për mënyrën e të menduarit të njerëzve tepër të lezetshëm. “Nuk është vetëm një ngarkesë e të menduarit pozitiv; ai përshkruan kushtet që rrisin shanset për të bërë një punë të madhe.”

Ne kemi përkthyer tashmë 28 (nga 30) kapituj. Dhe ne po punojmë për botimin "në letër".

Teoria e kodimit - I

Pasi kemi shqyrtuar kompjuterët dhe si funksionojnë ata, tani do të shqyrtojmë çështjen e përfaqësimit të informacionit: si kompjuterët përfaqësojnë informacionin që duam të përpunojmë. Kuptimi i çdo karakteri mund të varet nga mënyra se si përpunohet, makina nuk ka asnjë kuptim specifik për bitin e përdorur. Kur diskutuam historinë e softuerit në Kapitullin 4, ne morëm parasysh disa gjuhë programimi sintetike, në të cilat kodi i instruksionit të ndalimit ishte i njëjtë me kodin e udhëzimeve të tjera. Kjo situatë është tipike për shumicën e gjuhëve, kuptimi i udhëzimit përcaktohet nga programi përkatës.

Për të thjeshtuar problemin e përfaqësimit të informacionit, merrni parasysh problemin e transferimit të informacionit nga një pikë në tjetrën. Kjo pyetje lidhet me çështjen e ruajtjes së informacionit. Problemet e transmetimit të informacionit në kohë dhe hapësirë janë identike. Figura 10.1 tregon një model tipik të transferimit të informacionit.

Figura 10.1

Në anën e majtë të figurës 10.1 është burimi i informacionit. Kur shqyrtojmë modelin, natyra e burimit nuk është e rëndësishme për ne. Mund të jetë një grup karakteresh alfabetike, numra, formula matematikore, nota muzikore, simbole me të cilat mund të përfaqësojmë lëvizjet e vallëzimit - natyra e burimit dhe kuptimi i karaktereve të ruajtura në të nuk është pjesë e modelit të transmetimit. Ne konsiderojmë vetëm burimin e informacionit, me një kufizim të tillë, fitohet një teori e fuqishme, e përgjithshme, e cila mund të shtrihet në shumë fusha. Është një abstraksion nga shumë aplikacione.

Kur Shannon krijoi teorinë e informacionit në fund të viteve 1940, mendohej se ajo duhej të quhej teori e komunikimit, por ai këmbënguli në termin informacion. Ky term është bërë një shkak i vazhdueshëm i rritjes së interesit dhe zhgënjimit të vazhdueshëm në teori. Hetuesit donin të ndërtonin "teori informacioni" të tëra, ata degjeneruan në teori për grupin e personazheve. Duke iu rikthyer modelit të transferimit, ne kemi një burim të dhënash që duhet të kodohen për transferim.

Enkoderi përbëhet nga dy pjesë, pjesa e parë quhet kodues burimi, emri i saktë varet nga lloji i burimit. Burimet e llojeve të ndryshme të të dhënave korrespondojnë me lloje të ndryshme të koduesve.

Pjesa e dytë e procesit të kodimit quhet kodimi i kanalit dhe varet nga lloji i kanalit për transmetimin e të dhënave. Kështu, pjesa e dytë e procesit të kodimit përputhet me llojin e kanalit të transmetimit. Kështu, kur përdoren ndërfaqe standarde, të dhënat nga burimi së pari kodohen sipas kërkesave të ndërfaqes, dhe më pas sipas kërkesave të kanalit të transmetimit të të dhënave të përdorur.

Sipas modelit, në figurën 10.1, lidhja e të dhënave është subjekt i "zhurmës ekstra të rastësishme". E gjithë zhurma në sistem është bashkuar në këtë pikë. Supozohet se koduesi i merr të gjitha simbolet pa shtrembërim, dhe dekoderi kryen funksionin e tij pa gabime. Ky është një idealizim, por për shumë qëllime praktike është afër realitetit.

Faza e dekodimit gjithashtu përbëhet nga dy faza: kanal - standard, standard - marrës i të dhënave. Në fund të transferimit, të dhënat i transferohen konsumatorit. Përsëri, ne nuk e konsiderojmë se si konsumatori i interpreton këto të dhëna.

Siç u përmend më herët, një sistem i transmetimit të të dhënave, si mesazhet telefonike, radio, programet televizive, përfaqëson të dhënat si një grup numrash në regjistrat e një kompjuteri. Përsëri, transmetimi në hapësirë nuk është i ndryshëm nga transmetimi në kohë ose ruajtja e informacionit. A keni informacion që do t'ju nevojitet pas njëfarë kohe, atëherë ai duhet të kodohet dhe ruhet në burimin e ruajtjes së të dhënave. Nëse është e nevojshme, informacioni deshifrohet. Nëse sistemi i kodimit dhe i dekodimit është i njëjtë, ne i transmetojmë të dhënat përmes kanalit të transmetimit të pandryshuara.

Dallimi themelor midis teorisë së paraqitur dhe teorisë së zakonshme në fizikë është supozimi se nuk ka zhurmë në burim dhe marrës. Në fakt, gabimet ndodhin në çdo pajisje. Në mekanikën kuantike, zhurma ndodh në çdo fazë sipas parimit të pasigurisë, dhe jo si kusht fillestar; në çdo rast, koncepti i zhurmës në teorinë e informacionit nuk është i barabartë me konceptin analog në mekanikën kuantike.
Për saktësi, ne do të shqyrtojmë më tej formën binare të paraqitjes së të dhënave në sistem. Format e tjera përpunohen në mënyrë të ngjashme, për thjeshtësi nuk do t'i shqyrtojmë.

Le të fillojmë me sistemet me karaktere të koduara me gjatësi të ndryshueshme, si në kodin klasik Morse të pikave dhe vijave, në të cilin karakteret që shfaqen shpesh janë të shkurtër dhe karakteret e rralla janë të gjata. Kjo qasje ju lejon të arrini efikasitet të lartë të kodit, por vlen të përmendet se kodi Morse është tresh, jo binar, pasi përmban një karakter hapësinor midis pikave dhe një vize. Nëse të gjithë karakteret në kod janë të së njëjtës gjatësi, atëherë një kod i tillë quhet bllok.

Vetia e parë e domosdoshme e dukshme e kodit është aftësia për të deshifruar pa mëdyshje një mesazh në mungesë të zhurmës, të paktën kjo duket të jetë një veti e dëshirueshme, megjithëse në disa situata kjo kërkesë mund të neglizhohet. Të dhënat nga kanali i transmetimit i shfaqen marrësit si një rrjedhë prej 0 dhe 1.

Dy karaktere ngjitur do t'i quajmë zgjerim të dyfishtë, tre karaktere ngjitur një zgjerim të trefishtë dhe në përgjithësi nëse dërgojmë N karaktere marrësi sheh shtesat në kodin bazë të N karaktereve. Marrësi, duke mos ditur vlerën e N, duhet ta ndajë rrymën në blloqe transmetimi. Ose, me fjalë të tjera, marrësi duhet të jetë në gjendje të zbërthejë rrjedhën në një mënyrë unike në mënyrë që të rindërtojë mesazhin origjinal.

Konsideroni një alfabet me një numër të vogël karakteresh; zakonisht alfabetet janë shumë më të mëdha. Alfabetet e gjuhëve fillojnë nga 16 deri në 36 karaktere, duke përfshirë shkronjat e mëdha dhe të vogla, numrat, shenjat, shenjat e pikësimit. Për shembull, në një tabelë ASCII, 128 = 2^7 karaktere.
Konsideroni një kod të veçantë të përbërë nga 4 karaktere s1, s2, s3, s4

s1 = 0; s2 = 00; s3 = 01; s4 = 11.

Si duhet të interpretojë marrësi shprehjen e mëposhtme të marrë

Si s1s1s4 ose si s2s4?

Ju nuk mund t'i përgjigjeni pa mëdyshje kësaj pyetjeje, ky kod definitivisht nuk është i deshifruar, prandaj është i pakënaqshëm. Nga ana tjetër, kodi

s1 = 0; s2 = 10; s3 = 110; s4 = 111

Dekodon mesazhin në një mënyrë unike. Le të marrim një varg arbitrar dhe të shqyrtojmë se si marrësi do ta deshifrojë atë. Duhet të ndërtoni një pemë dekoduese sipas formës në Figurën 10.II. Linjë

1101000010011011100010100110 …

Mund të ndahet në blloqe karakteresh

110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110, …

Sipas rregullit të mëposhtëm për ndërtimin e një peme dekoduese:

Nëse jeni në majë të pemës, atëherë lexoni karakterin tjetër. Kur arrini një gjethe të pemës, ju e konvertoni sekuencën në një karakter dhe ktheheni përsëri në fillim.

Arsyeja pse ekziston një pemë e tillë është se asnjë personazh nuk është parashtesë e një tjetri, kështu që ju gjithmonë e dini se kur të ktheheni në majën e pemës së dekodimit.

Është e nevojshme t'i kushtohet vëmendje sa vijon. Së pari, dekodimi është një proces rreptësisht i transmetimit në të cilin çdo bit ekzaminohet vetëm një herë. Së dyti, protokollet zakonisht përfshijnë karaktere që shënojnë fundin e procesit të dekodimit dhe janë të nevojshme për të treguar fundin e mesazhit.

Mospërdorimi i karakterit pasues është një gabim i zakonshëm në hartimin e kodit. Natyrisht, mund të sigurohet një mënyrë e përhershme e deshifrimit, në të cilin rast simboli përfundimtar nuk është i nevojshëm.

Figura 10.II

Pyetja tjetër janë kodet për dekodimin e transmetimit (të menjëhershëm). Merrni parasysh kodin që është marrë nga hartëzimi i mëparshëm i karaktereve

s1 = 0; s2 = 01; s3 = 011; s4 = 111.

Supozoni se kemi një sekuencë 011111...111 . Mënyra e vetme për të deshifruar tekstin e mesazhit është të gruponi pjesët nga fundi në 3 në grup dhe të zgjidhni grupet me zerat kryesore përpara njëshit, pastaj mund të deshifroni. Një kod i tillë është i dekodueshëm në një mënyrë unike, por jo në çast! Për të deshifruar, duhet të prisni deri në fund të transferimit! Në praktikë, kjo qasje e nivelon shpejtësinë e dekodimit (teorema e McMillan), prandaj, është e nevojshme të kërkohen metoda të dekodimit të menjëhershëm.

Konsideroni dy mënyra për të koduar të njëjtin karakter, Si:

s1 = 0; s2 = 10; s3 = 110; s4=1110, s5=1111,

Pema e dekodimit për këtë metodë është paraqitur në figurën 10.III.

Figura 10.III

Mënyra e dytë

s1 = 00; s2 = 01; s3 = 100; s4=110, s5=111,

Pema dekoduese e këtij kujdesi është paraqitur në figurën 10.IV.

Mënyra më e dukshme për të matur cilësinë e kodit është gjatësia mesatare për disa grupe mesazhesh. Për ta bërë këtë, është e nevojshme të llogaritet gjatësia e kodit të secilit simbol, shumëzuar me probabilitetin përkatës të shfaqjes pi. Kjo do t'ju japë gjatësinë e të gjithë kodit. Formula për gjatësinë mesatare të kodit L për një alfabet me karakter q është si më poshtë

Ku pi është probabiliteti i shfaqjes së karakterit si, li është gjatësia përkatëse e karakterit të koduar. Për një kod efikas, vlera e L duhet të jetë sa më e vogël. Nëse P1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/16 dhe p5 = 1/16, atëherë për kodin #1 marrim vlerën e gjatësisë së kodit

Dhe për kodin #2

Vlerat e marra tregojnë preferencën për kodin e parë.
Nëse të gjitha fjalët në alfabet kanë të njëjtën probabilitet të ndodhjes, atëherë kodi i dytë është më i preferuar. Për shembull, me pi = 1/5, gjatësia e kodit #1

Dhe gjatësia e kodit #2

Ky rezultat tregon preferencën për kodin 2. Kështu, gjatë dizajnimit të kodit "të mirë", duhet të merret parasysh probabiliteti i shfaqjes së karaktereve.

Figura 10.IV

Figura 10.V

Merrni parasysh pabarazinë e Kraft, e cila përcakton vlerën kufi të gjatësisë së kodit të karakterit li. Sipas bazës 2, pabarazia paraqitet si

Kjo pabarazi thotë se nuk mund të ketë shumë karaktere të shkurtra në alfabet, përndryshe shuma do të jetë mjaft e madhe.

Për të vërtetuar pabarazinë e Kraft-it për çdo kod të shpejtë unik të dekodueshëm, ne ndërtojmë një pemë dekoduese dhe zbatojmë metodën e induksionit matematik. Nëse pema ka një ose dy gjethe, siç tregohet në figurën 10.V, atëherë nuk ka dyshim se pabarazia është e vërtetë. Më tej, nëse pema ka më shumë se dy gjethe, atëherë pemën me gjatësi m e ndajmë në dy nënpemë. Sipas parimit të induksionit, supozojmë se pabarazia është e vërtetë për secilën degë me lartësi m -1 ose më pak. Sipas parimit të induksionit, zbatimi i pabarazisë në secilën degë. Le të shënojmë gjatësitë e kodeve të degëve K" dhe K"". Kur dy degë të pemës bashkohen, gjatësia e secilës rritet me 1, prandaj, gjatësia e kodit përbëhet nga shumat K'/2 dhe K' '/2,

Teorema është vërtetuar.

Konsideroni vërtetimin e teoremës së Macmillan-it. Le të zbatojmë pabarazinë e Kraft-it në kodet e dekodueshme jo-streamwise. Vërtetimi bazohet në faktin se për çdo numër K > 1, fuqia e n-të e numrit është sigurisht më e madhe se një funksion linear i n, ku n është një numër mjaft i madh. Ngrini pabarazinë e Kraft-it në fuqinë e n-të dhe përfaqësoni shprehjen si një shumë

Ku Nk është numri i karaktereve me gjatësi k, përmbledhja fillon me gjatësinë minimale të paraqitjes së karakterit të n-të dhe përfundon me gjatësinë maksimale prej nl, ku l është gjatësia maksimale e karakterit të koduar. Nga kërkesa unike e dekodimit rrjedh se. Shuma paraqitet si

Nëse K > 1, atëherë është e nevojshme të vendoset n mjaft e madhe që pabarazia të bëhet false. Prandaj k<= 1; теорема Макмиллана доказана.

Le të shqyrtojmë disa shembuj të aplikimit të pabarazisë së Kraft. A mund të ketë një kod të dekodueshëm në mënyrë unike me gjatësi 1, 3, 3, 3? Po sepse

Po gjatësitë 1, 2, 2, 3? Llogaritni sipas formulës

Pabarazia u shkel! Ka shumë karaktere të shkurtra në këtë kod.

Kodet e pikave (kodet e presjeve) janë kode që përbëhen nga karakteret 1, që mbarojnë me karakterin 0, me përjashtim të karakterit të fundit, i cili përbëhet nga të gjitha. Një nga rastet e veçanta është kodi

s1 = 0; s2 = 10; s3 = 110; s4 = 1110; s5= 11111.

Për këtë kod, marrim një shprehje për pabarazinë e Kraft

Në këtë rast arrijmë barazi. Është e lehtë të shihet se për kodet e pikave, pabarazia e Kraft degjeneron në një barazi.

Kur ndërtoni kodin, duhet t'i kushtoni vëmendje shumës së Kraft. Nëse shuma Kraft fillon të kalojë 1, atëherë ky është një sinjal për të përfshirë një simbol me një gjatësi të ndryshme në mënyrë që të zvogëlohet gjatësia mesatare e kodit.

Duhet të theksohet se pabarazia e Kraft nuk thotë se ky kod është i dekodueshëm në mënyrë unike, por se ekziston një kod me simbole të një gjatësie të tillë që është i dekodueshëm në mënyrë unike. Për të ndërtuar një kod unik të dekodueshëm, mund të caktoni gjatësinë përkatëse në bit li si një numër binar. Për shembull, për gjatësitë 2, 2, 3, 3, 4, 4, 4, 4 marrim pabarazinë e Kraft

Prandaj, një kod i tillë unik i rrjedhës së dekodueshme mund të ekzistojë.

s1 = 00; s2 = 01; s3 = 100; s4 = 101;

S5 = 1100; s6 = 1101; s7 = 1110; s8 = 1111;

Dua t'i kushtoj vëmendje asaj që ndodh në të vërtetë kur shkëmbejmë ide. Për shembull, në këtë moment në kohë, unë dua të transferoj një ide nga koka ime në tuajën. Po them disa fjalë përmes të cilave besoj se do të arrini ta kuptoni (të merrni) këtë ide.

Por kur më vonë dëshironi t'ia përcillni këtë ide mikut tuaj, pothuajse me siguri do të thoni fjalë krejtësisht të ndryshme. Në realitet, kuptimi ose kuptimi nuk përfshihet në ndonjë fjalë të veçantë. Unë kam përdorur disa fjalë, por ju mund të përdorni fjalë krejtësisht të ndryshme për të përcjellë të njëjtën ide. Kështu, fjalë të ndryshme mund të përcjellin të njëjtin informacion. Por, sapo t'i thoni bashkëbiseduesit se nuk e kuptoni mesazhin, atëherë si rregull, bashkëbiseduesi do të marrë një grup të ndryshëm fjalësh për të përcjellë kuptimin, të dytin apo edhe të tretën. Kështu, informacioni nuk përmbahet në një grup fjalësh specifike. Pasi të keni marrë fjalë të caktuara, atëherë bëni një punë të shkëlqyer për t'i përkthyer fjalët në idenë që bashkëbiseduesi dëshiron t'ju përcjellë.

Mësojmë të zgjedhim fjalë në mënyrë që të përshtatemi me bashkëbiseduesin. Në një farë kuptimi, ne zgjedhim fjalët sipas mendimeve tona dhe nivelit të zhurmës në kanal, megjithëse një krahasim i tillë nuk pasqyron saktësisht modelin që përdor për të përfaqësuar zhurmën në procesin e dekodimit. Në organizatat e mëdha, një problem serioz është pamundësia e bashkëbiseduesit për të dëgjuar atë që thotë personi tjetër. Në postet e larta, punonjësit dëgjojnë "atë që duan të dëgjojnë". Në disa raste, duhet ta keni parasysh këtë kur ngjiteni në shkallët e korporatës. Përfaqësimi i informacionit në një formë formale është një pasqyrim i pjesshëm i proceseve të jetës sonë dhe ka gjetur aplikim të gjerë përtej kufijve të rregullave formale në aplikacionet kompjuterike.

Vazhdon...

Kush dëshiron të ndihmojë me përkthimin, paraqitjen dhe botimin e librit - shkruaj në një personal ose email [email i mbrojtur]

Meqë ra fjala, ne kemi nisur edhe përkthimin e një libri tjetër të lezetshëm -

Për të analizuar burime të ndryshme informacioni, si dhe kanalet e transmetimit të tyre, është e nevojshme të kemi një masë sasiore që do të bënte të mundur vlerësimin e sasisë së informacionit që përmban mesazhi dhe që transmetohet nga sinjali. Një masë e tillë u prezantua në vitin 1946 nga shkencëtari amerikan C. Shannon.

Më tej, supozojmë se burimi i informacionit është diskret, duke dhënë një sekuencë mesazhesh elementare (i,), secila prej të cilave zgjidhet nga një ansambël (alfabet) diskret a, a 2,...,d A; teështë vëllimi i alfabetit të burimit të informacionit.

Çdo mesazh elementar përmban informacione të caktuara si një grup informacioni (në shembullin në shqyrtim) për gjendjen e burimit të informacionit të konsideruar. Për të përcaktuar masën e këtij informacioni, përmbajtja e tij semantike, si dhe shkalla e rëndësisë së këtij informacioni për marrësin e tij, nuk është e rëndësishme. Vini re se përpara se të marrë një mesazh, marrësi ka gjithmonë pasiguri se cili mesazh jam unë. nga të gjitha të mundshmet do t'i jepet atij. Kjo pasiguri vlerësohet duke përdorur probabilitetin paraprak P(i,) të transmetimit të mesazhit i,. Ne konkludojmë se një masë objektive sasiore e informacionit që përmbahet në një mesazh elementar të një burimi diskret përcaktohet nga probabiliteti i zgjedhjes së një mesazhi të caktuar dhe përcakton cc në funksion të kësaj probabiliteti. I njëjti funksion karakterizon shkallën e pasigurisë që ka marrësi i informacionit në lidhje me gjendjen e burimit diskret. Mund të konkludohet se shkalla e pasigurisë për informacionin e pritur përcakton kërkesat për kanalet e transmetimit të informacionit.

Në përgjithësi, probabiliteti P(a,) zgjedhja e burimit të ndonjë mesazhi elementar i, (në tekstin e mëtejmë do ta quajmë simbol) varet nga simbolet e zgjedhura më parë, d.m.th. është një probabilitet i kushtëzuar dhe nuk do të përkojë me probabilitetin apriori të një zgjedhjeje të tillë.

Tim se ^ P(a:) = 1, pasi të gjitha unë formojnë një grup të plotë ngjarjesh

gyi), dhe zgjedhja e këtyre simboleve kryhet duke përdorur disa varësi funksionale J(a,)= P(a,) = 1, nëse zgjedhja e simbolit nga burimi është përcaktuar a priori, J(a,)= a "a P(a t,a)është probabiliteti i një zgjedhjeje të tillë, atëherë sasia e informacionit që përmban një çift simbolesh është e barabartë me shumën e sasisë së informacionit që përmban secili prej simboleve i dhe i. Kjo veti e masës sasiore të informacionit quhet aditivitet. .

Ne besojmë se P(a,)- probabiliteti i kushtëzuar i zgjedhjes së karakterit i, pas të gjithë karaktereve që i paraprijnë, dhe P(a,,i,) është probabiliteti i kushtëzuar i zgjedhjes së simbolit i; pas i, dhe të gjitha ato të mëparshme, por, duke pasur parasysh këtë P (a 1, a 1) \u003d P (a) P(i,|i y), mund të shkruhet kushti i aditivitetit

Ne prezantojmë shënimin P(a) = P p P (ar) \u003d Q dhe rishkruani kushtin (5.1):

Ne besojmë se R, O* 0. Duke përdorur shprehjen (5.2), përcaktojmë formën e funksionit (р (R). Duke diferencuar, shumëzuar me R* 0 dhe duke treguar RO = R, shkruani

Vini re se relacioni (5.3) është i kënaqur për cilindo R f O u^^O. Sidoqoftë, kjo kërkesë çon në qëndrueshmërinë e anëve të djathtë dhe të majtë të (5.3): Pq>"(P)= Ar"(/?) - tek - konst. Pastaj vijmë te ekuacioni Pc> "(P) = TE dhe pas integrimit marrim

Le të kemi parasysh se do të rishkruajmë

Rrjedhimisht, me plotësimin e dy kushteve mbi vetitë e J(a,), rezultoi se forma e varësisë funksionale J(a,) mbi probabilitetin e zgjedhjes së një simboli një t deri në një koeficient konstant TE të përcaktuara në mënyrë unike

Koeficient TE ndikon vetëm në shkallë dhe përcakton sistemin e njësive për matjen e sasisë së informacionit. Që nga ln[P] F 0, atëherë ka kuptim të zgjedhësh Për Os në mënyrë që një masë e sasisë së informacionit J(a) ishte pozitive.

Duke pranuar K=-1, shkruani

Nga kjo rrjedh se njësia e sasisë së informacionit është e barabartë me informacionin që ka ndodhur një ngjarje, probabiliteti i së cilës është i barabartë me Unë. Një njësi e tillë e sasisë së informacionit quhet njësi natyrore. Më shpesh supozohet se TE= -, atëherë

Kështu, arritëm në një njësi binare të sasisë së informacionit që përmban një mesazh për shfaqjen e një prej dy ngjarjeve po aq të mundshme dhe quhet "bit". Kjo njësi është e përhapur për shkak të përdorimit të kodeve binare në teknologjinë e komunikimit. Zgjedhja e bazës së logaritmit në rastin e përgjithshëm, marrim

ku logaritmi mund të jetë me bazë arbitrare.

Vetia e aditivitetit të masës sasiore të informacionit bën të mundur, në bazë të shprehjes (5.9), të përcaktohet sasia e informacionit në një mesazh të përbërë nga një sekuencë karakteresh. Probabiliteti që një burim të zgjedhë një sekuencë të tillë merret duke marrë parasysh të gjitha mesazhet e disponueshme më parë.

Masa sasiore e informacionit të përmbajtur në mesazhin elementar a (, nuk jep një ide për sasinë mesatare të informacionit J(A) lëshohet nga burimi kur zgjidhet një mesazh elementar a d

Sasia mesatare e informacionit karakterizon burimin e informacionit në tërësi dhe është një nga karakteristikat më të rëndësishme të sistemeve të komunikimit.

Le ta përcaktojmë këtë karakteristikë për një burim diskrete mesazhesh të pavarura me alfabet TE. Shënoni me NË) sasia mesatare e informacionit për karakter dhe është pritshmëria matematikore e një ndryshoreje të rastësishme L - sasia e informacionit që përmban një karakter i zgjedhur rastësisht A

Sasia mesatare e informacionit për simbol quhet entropia e burimit të mesazheve të pavarura. Entropia është një tregues i pasigurisë mesatare a priori kur zgjedh karakterin tjetër.

Nga shprehja (5.10) rezulton se nëse një nga probabilitetet P(a)është e barabartë me një (prandaj, të gjithë të tjerët janë të barabartë me zero), atëherë entropia e burimit të informacionit do të jetë e barabartë me zero - mesazhi është plotësisht i përcaktuar.

Entropia do të jetë maksimale nëse probabilitetet paraprake të të gjitha simboleve të mundshme janë të barabarta TE, d.m.th. R(a() = 1 /TO, Pastaj

Nëse burimi zgjedh në mënyrë të pavarur simbolet binare me probabilitet P, = P(a x) dhe P 2 \u003d 1 - P, atëherë entropia për karakter do të jetë

Në fig. 16.1 tregon varësinë e entropisë së një burimi binar nga probabiliteti a priori i zgjedhjes nga dy simbole binare, kjo figurë tregon gjithashtu se entropia është maksimale në R, = R 2 = 0,5

1 o 1 dvd - dhe në njësi binare log 2 2 = 1-

Oriz. 5.1. Varësia e entropisë në K = 2 mbi probabilitetin e zgjedhjes së njërit prej tyre

Entropia e burimeve me zgjedhje të barabartë simbolesh, por me madhësi të ndryshme alfabetesh TE, rritet logaritmikisht me rritjen TE.

Nëse probabiliteti i zgjedhjes së simboleve është i ndryshëm, atëherë entropia e burimit bie I(A) në raport me maksimumin e mundshëm H(A) psh = log TE.

Sa më i madh të jetë korrelacioni midis simboleve, aq më pak liri për të zgjedhur simbolet e mëvonshme dhe aq më pak informacion ka një simbol i zgjedhur rishtazi. Kjo për faktin se pasiguria e shpërndarjes së kushtëzuar nuk mund të tejkalojë entropinë e shpërndarjes së tyre të pakushtëzuar. Shënoni entropinë e burimit me kujtesë dhe alfabet TE përmes H(AA"), dhe entropia e burimit pa memorie, por në të njëjtin alfabet - përmes NË) dhe vërtetojnë pabarazinë

Duke futur shënimin P(aa") për probabilitetin e kushtëzuar të zgjedhjes së simbolit a,(/ = 1, 2, TE) duke supozuar se simboli është zgjedhur më parë ajij =1,2,TE) dhe duke lënë jashtë transformimet, shkruajmë pa prova

që vërteton pabarazinë (5.13).

Barazia në (5.13) ose (5.14) arrihet kur

Kjo do të thotë që probabiliteti i kushtëzuar i zgjedhjes së një simboli është i barabartë me probabilitetin e pakushtëzuar të zgjedhjes së tij, gjë që është e mundur vetëm për burimet pa kujtesë.

Është interesante se entropia e tekstit në Rusisht është 1.5 njësi binare për karakter. Në të njëjtën kohë, me të njëjtin alfabet K= 32 me kushtin e simboleve të pavarura dhe ekuiprobabile H(A) tp = 5 binare për karakter. Kështu, prania e lidhjeve të brendshme reduktoi entropinë me afërsisht 3.3 herë.

Një karakteristikë e rëndësishme e një burimi diskret është teprica e tij p dhe:

Teprica e burimit të informacionit është një sasi pa dimension brenda . Natyrisht, në mungesë të tepricës p u = 0.

Për të transmetuar një sasi të caktuar informacioni nga një burim që nuk ka korrelacione midis simboleve, me një probabilitet të barabartë të të gjitha simboleve, numri minimal i mundshëm i simboleve të transmetuara /7 min: /r 0 (/7 0 R (L max)) nevojitet. Për të transmetuar të njëjtën sasi informacioni nga një burim me entropi (simbolet janë të ndërlidhura dhe të pabarabarta), kërkohet një numër mesatar simbolesh n = n„H(A) m JH(A).

Një burim diskret karakterizohet gjithashtu nga performanca, e cila përcaktohet nga numri i simboleve për njësi të kohës v H:

Nëse performanca I(A) Përcaktoni në njësi binare, dhe kohën në sekonda, atëherë NË) -është numri i njësive binare për sekondë. Për burimet diskrete që prodhojnë sekuenca të palëvizshme të karaktereve me gjatësi mjaftueshëm të madhe /?, futen konceptet e mëposhtme: sekuenca tipike dhe atipike të karaktereve burimore, në të cilat të gjitha sekuencat e gjatësisë P. Të gjitha sekuencat tipike NlMl (A) burim në P-»oo kanë përafërsisht të njëjtën probabilitet të ndodhjes

Probabiliteti total i shfaqjes së të gjitha sekuencave atipike priret në zero. Në përputhje me barazinë (5.11), duke supozuar se probabiliteti i sekuencave tipike /N rm (A), entropia e burimit është logN TIin (,4) dhe më pas

Merrni parasysh sasinë dhe shpejtësinë e transmetimit të informacionit në një kanal të veçantë me zhurmë. Më parë, ne konsideruam informacionin e prodhuar nga një burim diskret në formën e një sekuence karakteresh (i,).

Tani supozoni se informacioni i burimit është i koduar dhe përfaqëson një sekuencë të simboleve të kodit (b, (/ = 1,2,..T - baza e kodit), është në përputhje me një kanal diskrete të transmetimit të informacionit, në daljen e të cilit shfaqet një sekuencë simbolesh

Supozojmë se operacioni i kodimit është një me një - sipas renditjes së karaktereve (b,) mund të rivendoset në mënyrë unike sekuenca (i,), d.m.th. Me anë të simboleve të kodit është e mundur të rivendosni plotësisht informacionin burimor.

Megjithatë, nëse marrim parasysh personazhet e arratisjes |?. j dhe simbolet hyrëse (/>,), atëherë, për shkak të pranisë së ndërhyrjes në kanalin e transmetimit të informacionit, rikuperimi është i pamundur. Entropia e sekuencës së daljes //(/?)

mund të jetë më e madhe se entropia e sekuencës hyrëse H(B), por sasia e informacionit për marrësin nuk u rrit.

Në rastin më të mirë, marrëdhëniet një-për-një midis hyrjes dhe daljes janë të mundshme dhe informacioni i dobishëm nuk humbet; në rastin më të keq, nuk mund të thuhet asgjë për simbolet hyrëse nga simbolet dalëse të kanalit të transmetimit të informacionit. informacioni i dobishëm humbet plotësisht në kanal.

Le të vlerësojmë humbjen e informacionit në një kanal me zhurmë dhe sasinë e informacionit të transmetuar në një kanal me zhurmë. Konsiderojmë se karakteri është transmetuar saktë nëse me karakterin e transmetuar 6 është marrë

simbol bj me të njëjtin numër (/= j). Pastaj për një kanal ideal pa zhurmë, ne shkruajmë:

Me simbol bj-në daljen e kanalit për shkak të pabarazive (5.21)

pasiguria është e pashmangshme. Mund të supozojmë se informacioni në simbol b i nuk transmetohet plotësisht dhe një pjesë e tij humbet në kanal për shkak të ndërhyrjeve. Bazuar në konceptin e masës sasiore të informacionit, do të supozojmë se shprehja numerike e pasigurisë që ndodh në daljen e kanalit pas marrjes së simbolit ft; :

dhe përcakton sasinë e informacionit të humbur në kanal gjatë transmetimit.

Rregullimi ft . dhe duke marrë mesataren (5.22) mbi të gjitha simbolet e mundshme, marrim shumën

i cili përcakton sasinë e informacionit të humbur në kanal kur transmetohet një simbol elementar mbi një kanal pa memorie kur merr një simbol bj(t).

Kur mesatarizojmë shumën (5.23) mbi të gjitha ft, marrim vlerën Z?), të cilën e shënojmë me n(në/në- Ai përcakton sasinë e informacionit të humbur kur transmetohet një karakter në një kanal pa memorie:

Ku P^bjbjj- probabiliteti i përbashkët i një ngjarjeje që, kur transmetohet

simbol b. do të marrë simbolin b t .

H [w/ varet nga karakteristikat e burimit të informacionit mbi

hyrje kanali NË dhe mbi karakteristikat probabilistike të kanalit të komunikimit. Sipas Shannon në teorinë e komunikimit statistikor n(në/në quhet mosbesueshmëria e kanalit.

Entropia e kushtëzuar HB/B, entropia e një burimi diskret

në hyrjen e kanalit H(W) dhe entropisë DHE ^ B) në daljen e tij nuk mund të jetë

negativ. Në një kanal pa ndërhyrje, mosbesueshmëria e kanalit

n(v/v = 0. Në përputhje me (5.20), vërejmë se H^v/v^

dhe barazia ndodh vetëm kur hyrja dhe dalja e kanalit janë statistikisht të pavarura:

Simbolet e daljes nuk varen nga simbolet hyrëse - rasti i një kanali të prishur ose ndërhyrje shumë e fortë.

Si më parë, për sekuencat tipike, ne mund të shkruajmë

për të thënë se në mungesë të ndërhyrjes, mosbesueshmëria e saj

Sipas informacionit të transmetuar mesatarisht në kanal J[ b/ për simbol kuptojmë ndryshimin midis sasisë së informacionit në hyrjen e kanalit J(B) dhe informacioni i humbur në kanalin /?).

Nëse burimi i informacionit dhe kanali janë pa memorie, atëherë

Shprehja (5.27) përcakton entropinë e simboleve dalëse të kanalit. Një pjesë e informacionit në daljen e kanalit është e dobishme, dhe pjesa tjetër është e rreme, pasi krijohet nga ndërhyrja në kanal. Le të theksojmë se n[v/ 2?) shpreh informacion për ndërhyrjen në kanal, dhe ndryshimin i(d)-I(d/d) - informacion i dobishëm që ka kaluar nëpër kanal.

Vini re se shumica dërrmuese e sekuencave të formuara në daljen e kanalit janë atipike dhe kanë një probabilitet total shumë të vogël.

Si rregull, merret parasysh lloji më i zakonshëm i ndërhyrjes - zhurma shtesë. N(t); Sinjali në daljen e kanalit ka formën:

Për sinjalet diskrete, zhurma ekuivalente, që vjen nga (5.28), ka një strukturë diskrete. Zhurma është një sekuencë e rastësishme diskrete, e ngjashme me sekuencat e sinjaleve hyrëse dhe dalëse. Le të shënojmë simbolet e alfabetit të zhurmës shtesë në një kanal diskret si C1 = 0, 1,2, T- 1). Probabilitetet e tranzicionit të kushtëzuar në një kanal të tillë

Sepse DHE (^ B/?) Dhe (B) pastaj, rrjedhimisht, informacioni i sekuencës së daljes së kanalit diskret #(/) në lidhje me hyrjen B(t) ose anasjelltas Dhe (B) - H ^ në / në) (5).

Me fjalë të tjera, informacioni i transmetuar në kanal nuk mund të tejkalojë informacionin në hyrjen e tij.

Nëse hyrja e kanalit merr një mesatare x k simbolet në një sekondë, atëherë është e mundur të përcaktohet shpejtësia mesatare e transferimit të informacionit në një kanal me zhurmë:

Ku Н(В) = V k J(B,B^ - performanca e burimit në hyrjen e kanalit; n (në / në) \u003d U në n (në, në) ~ mosbesueshmëria e kanalit për njësi të kohës; H (B) = V k H^B^- performanca e burimit të formuar nga dalja e kanalit (duke dhënë një pjesë të informacionit të dobishëm dhe një pjesë të rreme); H ^ in / B ^ \u003d U deri në 1 / (në / in)- sasia e informacionit të rremë,

krijoi ndërhyrje në kanal për njësi të kohës.

Konceptet e sasisë dhe shpejtësisë së transmetimit të informacionit përmes një kanali mund të zbatohen në seksione të ndryshme të një kanali komunikimi. Ky mund të jetë seksioni "hyrja e koduesit - dalja e dekoderit".

Vini re se, duke zgjeruar seksionin e kanalit në shqyrtim, është e pamundur të tejkalohet shpejtësia në asnjë nga pjesët përbërëse të tij. Çdo transformim i pakthyeshëm çon në humbjen e informacionit. Transformimet e pakthyeshme përfshijnë jo vetëm ndikimin e ndërhyrjes, por edhe zbulimin, dekodimin me kode me tepricë. Ka mënyra për të reduktuar humbjen e pranimit. Kjo është "pritja në përgjithësi".

Merrni parasysh gjerësinë e brezit të një kanali diskret dhe teoremën optimale të kodimit. Shannon prezantoi një karakteristikë që përcakton shpejtësinë maksimale të mundshme të transferimit të informacionit mbi një kanal me veti të njohura (zhurmë) nën një numër kufizimesh në grupin e sinjaleve hyrëse. Kjo është gjerësia e brezit të kanalit C. Për një kanal diskret

ku maksimumi ruhet nga burimet e mundshme hyrëse NË dhënë Vk dhe vëllimi i alfabetit të karaktereve hyrëse T.

Bazuar në përcaktimin e xhiros së një kanali diskret, ne shkruajmë

Vini re se C = 0 me hyrje dhe dalje të pavarur (niveli i lartë i zhurmës në kanal) dhe, në përputhje me rrethanat,

në mungesë të interferencës së interferencës në sinjal.

Për kanal simetrik binar pa memorie

Oriz. 5.2.

Grafiku i varësisë së kapacitetit të kanalit binar nga parametri R treguar në fig. 5.2. Në R= 1/2 e gjerësisë së brezit të kanalit C = 0, entropia e kushtëzuar

//(/?//?) = 1. Interes praktik

grafiku paraqet 0

Teorema themelore e Shannon-it mbi kodimin optimal lidhet me konceptin e kapacitetit. Formulimi i tij për një kanal diskret është si vijon: nëse performanca e burimit të mesazhit NË) më pak se gjerësia e brezit të kanalit C:

ekziston një metodë e kodimit dhe dekodimit optimal, sipas së cilës probabiliteti i gabimit ose mosbesueshmërisë së kanalit n[a!A j mund të jetë arbitrarisht i vogël. Nëse

nuk ka mënyra të tilla.

Në përputhje me teoremën e Shannon-it, vlera e fundme MEështë vlera kufi e shkallës së transferimit të informacionit pa gabime mbi kanal. Por për një kanal të zhurmshëm, mënyrat për të gjetur kodin optimal nuk tregohen. Megjithatë, teorema ndryshoi rrënjësisht pikëpamjet mbi mundësitë themelore të teknologjisë së transmetimit të informacionit. Para Shannon-it, besohej se në një kanal të zhurmshëm ishte e mundur të merrej një probabilitet i vogël gabimi arbitrarisht duke ulur shkallën e transferimit të informacionit në zero. Kjo është, për shembull, një rritje në besnikërinë e komunikimit si rezultat i përsëritjes së karaktereve në një kanal pa kujtesë.

Janë të njohura disa prova rigoroze të teoremës së Shannon-it. Teorema u vërtetua për një kanal diskrete pa memorie me kodim të rastësishëm. Në këtë rast, grupi i të gjitha kodeve të zgjedhura rastësisht për një burim të caktuar dhe një kanal të caktuar merret parasysh dhe fakti i qasjes asimptotike në zero të probabilitetit mesatar të dekodimit të gabuar mbi të gjitha kodet, pohohet me një rritje të pakufizuar në kohëzgjatjen e sekuenca e mesazheve. Kështu, vërtetohet vetëm fakti i ekzistencës së një kodi që ofron mundësinë e dekodimit pa gabime, megjithatë, nuk propozohet një metodë e paqartë kodimi. Në të njëjtën kohë, gjatë provës, bëhet e qartë se duke ruajtur barazinë e entropive të ansamblit të sekuencës së mesazheve dhe grupit përkatës një-për-një të fjalëve kodike të përdorura për transmetim, ansambli NË duhet futur tepricë shtesë për të rritur varësinë reciproke të sekuencës së simboleve të kodit. Kjo mund të bëhet vetëm duke zgjeruar grupin e sekuencave të kodit nga të cilat zgjidhen fjalët e kodit.

Përkundër faktit se teorema kryesore e kodimit për kanalet e zhurmshme nuk tregon mënyra të qarta të zgjedhjes së një kodi të caktuar dhe ato gjithashtu mungojnë në vërtetimin e teoremës, mund të tregohet se shumica e kodeve të zgjedhura rastësisht, kur kodojnë mesazhe mjaft të gjatë sekuencat, pak tejkalojnë probabilitetin mesatar të dekodimit të gabuar. Sidoqoftë, mundësitë praktike të kodimit në blloqe të gjata janë të kufizuara për shkak të vështirësive në zbatimin e sistemeve të memories dhe përpunimit logjik të sekuencave të një numri të madh elementësh kodi, si dhe për shkak të rritjes së vonesës në transmetimin dhe përpunimin e informacionit. Në fakt, me interes të veçantë janë rezultatet që bëjnë të mundur përcaktimin e probabilitetit të dekodimit të gabuar për kohëzgjatje të fundme. P blloqe kodi të përdorura. Në praktikë, ato janë të kufizuara në vlera të moderuara të vonesës dhe arrijnë një rritje të probabilitetit të transmetimit me përdorim jo të plotë të gjerësisë së brezit të kanalit.