Mesazhet nga alfabeti burimor shkruhen në rend zbritës të probabilitetit të ndodhjes së tyre. Më pas, ato ndahen në dy pjesë në mënyrë që probabilitetet totale të mesazheve në secilën prej këtyre pjesëve të jenë sa më afër të jetë e mundur. Mesazheve të pjesës së parë u caktohet 0 si karakteri i parë, dhe mesazheve të pjesës së dytë caktohet 1 (është e mundur anasjelltas). Pastaj secila nga këto pjesë (nëse përmban më shumë se një mesazh) ndahet në dy pjesë të mundshme të barabarta dhe simboli i dytë për të parën prej tyre është 0, dhe për të dytën - 1. Ky proces përsëritet derisa të mos ketë më një mesazh në një kohë. Për shembullin e dhënë në tabelë. 1 në fazën e parë të ndarjes së pjesës së parë do të ketë një mesazh A 1 me probabilitet P(A 1)=0.4, në pjesën e dytë - mesazhet e mbetura me probabilitet total P Σ ( A 2 -A 6)=0,6. Le t'i atribuojmë mesazhin A 1 karakter është 0, dhe pjesa tjetër e mesazheve kanë 1 si karakterin e parë.
Tabela 1. Kodimi arbitrar i mesazhit
Në fazën e dytë, ne ndajmë mesazhet ( A 2 ,A 3 ,A 4 ,A 5 ,A 6) në dy pjesë po aq të mundshme, duke përfshirë pjesën e parë të mesazhit A 2, dhe në pjesën e dytë - mesazhe ( A 3 ,A 4 ,A 5 ,A 6). Le t'i atribuojmë mesazhin A 2 pasi karakteri i dytë është 0, dhe pjesa tjetër e mesazheve janë 1, etj. Si rezultat, arrijmë te kodi TE 2, dhënë në tabelë. 2.
Tabela 2. Kodimi i mesazheve duke përdorur kodin Shannon-Fano
Kodi nga ndërtimi i tij plotëson vetinë e prefiksit. Prandaj, sekuenca e mësipërme e simboleve binare " L
” deshifrohet pa mëdyshje: ( A 1 ,A 1 ,A 4 ,A 1 ,A 1 ,A 1 ,A 6 ,A 1). Numri mesatar i karaktereve për mesazh, duke marrë parasysh probabilitetet e tyre 
=0,4*1+0,3*2+0,3*4=2,2, d.m.th. e tejkalon pak entropinë e burimit të mesazhit.
2.4. Gjatësia mesatare e fjalës së koduar
Procedura Shannon-Fano nuk minimizon domosdoshmërisht 
, meqenëse arritja e një vlere të madhe të vetë-informacionit mesatar në një shkronjë kodi mund të çojë në një zgjedhje të varfër për shkronjat pasuese të kodit. Nëse kjo ndarje mund të llogaritet në mënyrë që grupet të jenë saktësisht të njëjta në çdo fazë të ndarjes, atëherë probabilitetet e shkronjave burimore dhe gjatësisë fjalë kodike do të kufizohet nga barazia
(2)
Kufizimet në gjatësinë e fjalëve kodike të kodit të parashtesave jepen nga pabarazia e Kraft dhe teorema e kodimit burimor.
Teorema 1.(Pabarazia e Kraft-it). Nëse numrat e plotë ( 
) kënaq pabarazinë
(3)
atëherë ka një kod që ka vetinë e një parashtese me një alfabet të vëllimit D, gjatësitë e fjalëve kodike në të cilat janë të barabarta me këta numra. Në të kundërt, gjatësia e fjalëve kodike të çdo kodi që imponon vetinë e prefiksit plotëson pabarazinë (3). Teorema nuk thotë se çdo kod me gjatësinë e fjalës së koduar që kënaq (3) është prefiks. Kështu, për shembull, grupi i fjalëve kodike binare (0; 00; 11) plotëson (3), por nuk ka vetinë e prefiksit. Teorema thotë se ekziston një kod prefiks me gjatësi të tilla, për shembull kodi (0; 10; 11) . Jo çdo kod unik i deshifrimit ka vetinë e një prefiksi, për shembull, kodi K3 në Tabelë. 3. Në të, çdo fjalë e koduar është një parashtesë e çdo fjale kode më të gjatë. Në të njëjtën kohë, deshifrimi i paqartë është i parëndësishëm, pasi simboli 0 përcakton gjithmonë fillimin e një fjale kodi të re. Kodet që kanë vetinë e një parashtese ndryshojnë, megjithatë, nga kodet e tjera të dekodueshme në mënyrë unike në atë që fundi i fjalës kodike mund të njihet gjithmonë, kështu që dekodimi mund të kryhet pa vonuar sekuencën e vëzhguar të fjalëve kodike (kodi K4, Tabela 3 ). Për këtë arsye, kodet e parashtesave quhen ndonjëherë kode flash.
Tabela 3. Kodet unike të dekodueshme
Meqenëse gjatësia e fjalëve të kodit të çdo kodi të dekodueshëm në mënyrë unike plotëson (3) dhe ne mund të ndërtojmë kodi i prefiksit për çdo grup gjatësish që kënaq (3), atëherë çdo kod i dekodueshëm në mënyrë unike mund të zëvendësohet me një kod prefiks pa ndryshuar gjatësinë e fjalëve të kodit. Kështu, teorema 2 e mëposhtme për kodimin e burimit në lidhje me gjatësinë mesatare të fjalës së koduar propozohet si për kodet e dekodueshme në mënyrë unike ashtu edhe për nënklasën e kodeve të prefiksit.
Informacion është një grup informacioni që i nënshtrohet ruajtjes, transmetimit, përpunimit dhe përdorimit në veprimtarinë njerëzore.
Ndryshimi i karakteristikave të mediumit që përdoret për të përfaqësuar informacionin quhet sinjal , dhe vlera e kësaj karakteristike, e lidhur me një shkallë të caktuar matjeje, quhet parametri i sinjalit .
Të dallojë dy lloje sinjalesh (dhe për këtë arsye dy lloje mesazhesh ): e vazhdueshme dhe diskrete.
Për të siguruar thjeshtësinë dhe besueshmërinë e njohjes diskrete të sinjalit ( shenjat ), këshillohet që numri i tyre të zvogëlohet në minimum. Si rregull, ata përdorin funksionin e përfaqësimit të karaktereve origjinale në një alfabet tjetër me një numër më të vogël karakteresh, të quajtur simbolet . Kur shënoni këtë operacion, përdoret i njëjti term - " kodimi ».
Informacionet e veta
Sasia e informacionit që mbart një letër x i alfabet, le ta quajmë informacionin e vet
të përfshira në x i dhe shënojnë 
.
.
formula e Shannon-it
Le të mesatarizojmë informacionin tonë, d.m.th. Le të llogarisim sasinë mesatare të informacionit të bartur nga një karakter i alfabetit 
:
.
Sasia mesatare e informacionit, për shkak me një shkronjë, thirri entropia alfabeti (ose burimi) dhe është caktuar H:
-
formula e Shannon-it
.
Është e qartë se mesatare 1 sasia e informacionit në gjatësinë e mesazhit n llogaritur me formulën:
.
Koment.Sasia e informacionit i atribuohet vetë mesazhit.
Koment. Entropia është një karakteristikë e burimit të mesazhit (alfabeti).
formula e Hartley-t
Në ekuiprobabiliteti personazhet e alfabetit 
, nga formula e Shannon-it marrim: .
-
formula e Hartley-t
.
Njësitë e informacionit
Njësia e informacionit për element të mesazhit (njësia e entropisë) quhet pak .
Konsideroni një alfabet me simbole po aq të mundshme, entropia e të cilit është e barabartë me 1: 
. Meqenëse rrjedh nga këtu 
, atëherë është e qartë se 1 bit është sasia e informacionit që përmbahet në një mesazh binar (alfabet (0,1)) me gjatësi 1.
Në vijim, në shprehjet për I dhe H do të përdorim gjithmonë logaritme me bazën 2.
Vetitë e entropisë
1. Entropia N- madhësia
- jo negative(N 0) ,
-
kufizuar,
Këto veti rrjedhin nga fakti se të gjithë përbërësit e tij kanë të njëjtat cilësi. 
.
2. Entropia e barabartë me zero nëse probabiliteti i njërit prej simboleve është 1. Në këtë rast, ata flasin për një burim krejtësisht determinist dhe mungesën e pasigurisë në të, pasi vëzhguesi e di për mesazhin e burimit përpara momentit të vëzhgimit të tij.
3. Gjithashtu mund të tregohet se entropia është maksimumi nëse të gjithë karakteret e alfabetit janë njëlloj të mundshëm, d.m.th. N max = log m. Kështu, për të gjetur vlerën maksimale të mundshme të entropisë (për një numër fiks simbolesh), përdoret formula e Hartley-t.
4. Me interes të veçantë janë mesazhet binare, duke përdorur alfabeti binar(0,1). Qe kur m= 2 probabilitete të karaktereve të alfabetit fq 1 1 dhe fq 2 1, atëherë mund të vendosim fq 1 = fq Dhe fq 2 = 1-fq. Atëherë entropia përcaktohet nga relacioni
Duke klikuar në butonin "Shkarko arkivin", do të shkarkoni skedarin që ju nevojitet plotësisht pa pagesë.
Përpara shkarkimit këtë skedar mbani mend ato ese të mira, teste, punime afatgjata, teza, artikuj dhe dokumente të tjera që nuk janë kërkuar në kompjuterin tuaj. Kjo është puna juaj, ajo duhet të marrë pjesë në zhvillimin e shoqërisë dhe të përfitojë njerëzit. Gjeni këto vepra dhe dorëzojini ato në bazën e njohurive.
Ne dhe të gjithë studentët, studentët e diplomuar, shkencëtarët e rinj që përdorin bazën e njohurive në studimet dhe punën e tyre do t'ju jemi shumë mirënjohës.
Për të shkarkuar një arkiv me një dokument, futni një numër pesëshifror në fushën më poshtë dhe klikoni butonin "Shkarko arkivin"
Dokumente të ngjashme
Numri total mesazhe që nuk përsëriten. Llogaritja e shpejtësisë së transmetimit të informacionit dhe kapacitetit të kanalit të komunikimit. Përcaktimi i tepricës së mesazhit dhe kodimi optimal. Procedura për ndërtimin e një kodi optimal duke përdorur metodën Shannon-Fano.
puna e kursit, shtuar 17.04.2009
Përshkrimi dhe veçoritë e disa algoritmeve të arkivimit. Ndërtimi i kodit Huffman. Algoritmi dinamik për ndërtimin e kodit Huffman. Rikuperimi i kundërt i tekstit. Metodat e kodimit të informacionit me dy faza. Zbatim praktik Algoritmi LZ77.
puna e kursit, shtuar 24.12.2012
Vlerësimi i kompleksitetit llogaritës të programit. Zbatimi i algoritmit të kodimit të informacionit Huffman. Kodimi i testimit kodi binar dhe në pemën Huffman. Kodi binar i karakterit. Simboli dhe shpeshtësia e paraqitjes së tij në tekst. Llogaritja e kompleksitetit të algoritmit.
test, shtuar 16.12.2012
Përcaktimi i sasisë mesatare të informacionit. Varësia ndërmjet simboleve të matricës së probabilitetit të kushtëzuar. Kodimi duke përdorur metodën Shannon-Fano. Kapaciteti i kanalit të komunikimit. Efikasiteti i kodimit të mesazheve duke përdorur metodën e D. Huffman, karakteristikat e kodit.
test, shtuar 05/04/2015
Përkufizimi i koncepteve të kodit, kodimi dhe dekodimi, llojet, rregullat dhe detyrat e kodimit. Zbatimi i teoremave të Shannon-it në teorinë e komunikimit. Klasifikimi, parametrat dhe ndërtimi i kodeve rezistente ndaj zhurmës. Metodat për transmetimin e kodeve. Një shembull i ndërtimit të një kodi Shannon.
puna e kursit, shtuar 25.02.2009
Analiza e efektivitetit të metodave të kodimit. Madhësia mesatare e një biti dhe gjatësia mesatare e një fjale kodi. Kodimi i Huffman. Kodimi i informacionit duke përdorur metodën Shannon-Fano. Ndërtimi pema e kodit Për metoda të ndryshme kodimi.
test, shtuar 15.10.2013
Kodimi dhe dekodimi, konvertimi mesazh diskret V sinjal diskret. Ndërtimi modeli matematik kodi i korrigjimit. Matrica gjeneruese e kodit të informacionit. Struktura modulare programet. Specifikimi për modulet e softuerit.
puna e kursit, shtuar 28.11.2014
Në shembujt e kodimit të mësipërm, të gjitha fjalët e koduara kishin të njëjtën gjatësi. Megjithatë, kjo nuk është një kërkesë e detyrueshme. Për më tepër, nëse probabilitetet e shfaqjes së mesazheve ndryshojnë dukshëm nga njëra-tjetra, atëherë është më mirë që mesazhet me probabilitet të lartë të ndodhin të kodohen me fjalë të shkurtra, dhe mesazhe të rralla të kodohen me fjalë më të gjata. Si rezultat, teksti i kodit do të bëhet mesatarisht më i shkurtër në kushte të caktuara.
Një tregues i ekonomisë ose efikasitetit të një kodi jo uniform nuk është gjatësia e fjalëve kodike individuale, por gjatësia e tyre "mesatare", e përcaktuar nga barazia:
ku është fjala kod me të cilën është koduar mesazhi, a është gjatësia e tij, është probabiliteti i mesazhit dhe është numri total i mesazheve burimore. Për shkurtësi në shkrimin e formulave, mund të përdoren shënimet e mëposhtme: 
Dhe 
. Vini re se përcaktimi i gjatësisë mesatare të kodimit nga thekson faktin se kjo vlerë varet si nga burimi i mesazheve ashtu edhe nga metoda e kodimit.
Kodi më ekonomik është ai me gjatësinë mesatare më të vogël. Le të krahasojmë, duke përdorur shembuj, kosto-efektivitetin e metodave të ndryshme të kodimit të të njëjtit burim.
Lejo që burimi të përmbajë 4 mesazhe me probabilitete. Këto mesazhe mund të kodohen me fjalë kodike me gjatësi konstante dhe me dy karaktere në alfabet 
në përputhje me tabelën e kodeve.
Natyrisht, për të përfaqësuar (transmetuar) çdo sekuencë, mesatarisht, do të kërkohen 2 karaktere për mesazh. Le të krahasojmë efektivitetin e një kodimi të tillë me kodimin e përshkruar më sipër me fjalë me gjatësi të ndryshueshme. Tabela e kodeve për këtë rast mund të ketë formën e mëposhtme.
Në këtë tabelë, ndryshe nga ajo e mëparshme, mesazhet më të shpeshta janë të koduara me një karakter binar. Për opsionin e fundit të kodimit kemi
ndërsa për një kod uniform gjatësia mesatare (është e njëjtë me gjatësinë totale të fjalëve të koduara). Nga shembulli i konsideruar është e qartë se kodimi i mesazheve me fjalë me gjatësi të ndryshme mund të japë një rritje të konsiderueshme (pothuajse të dyfishtë) në efikasitetin e kodimit.
Kur përdorni kode të pabarabarta, lind një problem, të cilin do ta shpjegojmë duke përdorur shembullin e tabelës së kodit të fundit. Le të përdorim këtë tabelë për të koduar një sekuencë mesazhesh 
, si rezultat i së cilës shndërrohet në vijim tekst binar: 010110. Karakteri i parë i mesazhit origjinal është deshifruar në mënyrë unike - kjo. Megjithatë, fillon pasiguria e mëtejshme: ose 
. Këto janë vetëm disa nga opsionet e mundshme për dekodimin e sekuencës origjinale të karaktereve.
Duhet të theksohet se paqartësia e dekodimit të fjalëve u shfaq pavarësisht se kushti i dekodimit të qartë të shenjave (injektiviteti i hartës së kodit) është i plotësuar.
Thelbi i problemit është pamundësia e identifikimit të paqartë të fjalëve të kodit. Për ta zgjidhur atë, do të ishte e nevojshme të ndahej një fjalë kodi nga një tjetër. Sigurisht, kjo mund të bëhet, por vetëm duke përdorur ose një pauzë midis fjalëve, ose një shenjë të veçantë ndarëse, e cila kërkon një përcaktim të veçantë kodi. Të dyja mënyrat, së pari, kundërshtojnë metodën e kodimit të fjalëve të përshkruara më sipër duke bashkuar kodet e karaktereve që formojnë një fjalë dhe, së dyti, do të çojnë në një zgjatje të konsiderueshme të tekstit të kodit, duke mohuar avantazhet e përdorimit të kodeve me gjatësi të ndryshueshme.
Zgjidhja e këtij problemi është të jesh në gjendje të zgjedhësh fjalë kodike individuale në çdo tekst kodi pa përdorur kufizues të veçantë. Me fjalë të tjera, është e nevojshme që kodi të plotësojë kërkesat e mëposhtme: çdo sekuencë e karaktereve të kodit mund të ndahet në mënyrë unike në fjalë kodike. Kodet për të cilat kërkesa e fundit të kënaqur, quhen të dekodueshëm në mënyrë unike (nganjëherë quhen kode pa presje).
Le të shohim kodin (skema e kodimit alfabetik) 
, të specifikuar nga tabela e kodeve
dhe fjalë të ndryshme të përbëra nga kode elementare.
Përkufizimi. Një kod thuhet se është i dekodueshëm në mënyrë unike nëse
domethënë, çdo fjalë e përbërë nga kode elementare mund të zbërthehet në mënyrë unike në kode elementare.
Nëse tabela e kodit përmban të njëjtat fjalë kodi, domethënë nëse
atëherë kodi padyshim nuk është i dekodueshëm në mënyrë unike (qarku nuk është i ndashëm). Kode të tilla nuk konsiderohen më tej.
Konsideroni një grup mesazhesh për ta me probabilitetet përkatëse Çdo mesazh duhet të përfaqësohet me një fjalë kodi të përbërë nga simbole të njëpasnjëshme që i përkasin një alfabeti të caktuar. Le të shënojmë me numrin e simboleve të ndryshme në alfabet, me numrin e simboleve në fjalën e kodit që korrespondon me mesazhin. Numri mesatar i simboleve për mesazh është, sipas përkufizimit,
Detyra jonë e parë është të gjejmë një kufi më të ulët për
Insekt. 2.8 ne pamë se entropia e një grupi mesazhesh është sasia mesatare e informacionit që kërkohet për të identifikuar në mënyrë unike një mesazh nga ky ansambël. Në të njëjtin seksion pamë se simbolet mbartin mesatarisht shuma maksimale informacion kur ato janë po aq të mundshme. Kjo vlerë maksimale është kapaciteti i alfabetit të kodit. Për më tepër, barazitë (2.100) dhe (2.105) tregojnë se varësia statistikore e një simboli të caktuar nga ato të mëparshme nuk mund të rrisë sasinë mesatare të informacionit për këtë simbol. Mbi këtë bazë mund të konkludojmë se
Nga e marrim?
d.m.th., numri mesatar i simboleve për mesazh nuk mund të jetë më i vogël se entropia e grupit të mesazheve pjesëtuar me xhiros alfabeti. Një provë e drejtpërdrejtë e këtij rezultati është dhënë në seksion. 3.5.
Arsyetimi i përdorur për të nxjerrë këtë kufi të poshtëm na lejon të propozojmë Rregulla të përgjithshme duke ndërtuar fjalë kodike me një gjatësi mesatare mjaftueshëm afër këtij kufiri. Rregulli i parë është që në secilën nga pozicionet e fjalëve të koduara, simbolet e ndryshme të alfabetit duhet të përdoren me probabilitete të barabarta, në mënyrë që të maksimizohet sasia mesatare e informacionit të dhënë prej tyre. Rregulli i dytë është se probabilitetet e ndodhjes
Karakteret në çdo pozicion të fjalës së koduar duhet të jenë të pavarura nga të gjithë karakteret e mëparshme. Nëse këto rregulla ndiqen saktësisht, atëherë gjatësia mesatare e fjalëve kodike të gjeneruara do të jetë e barabartë me vlerën minimale të përcaktuar nga formula (3.3). Ne do të shohim, megjithatë, se vetëm në raste të veçanta simbolet mund të përdoren me probabilitete të barabarta dhe të bëhen të pavarura nga të gjitha simbolet e mëparshme. Këto rregulla për ndërtimin e grupeve të fjalëve kodike shpjegohen më së miri duke përdorur shembujt specifikë të mëposhtëm. Procedura e kodimit e përdorur është e ngjashme me atë të propozuar për herë të parë nga Shannon.
