border=0

Alfabetyske net-unifere binêre kodearring fan sinjalen fan deselde termyn. Prefix-koades

As de namme neamt, wurde de tekens fan it primêre alfabet (bygelyks Russysk) kodearje fan kombinaasjes fan karakters fan it binêre alfabet (ie, 0 en 1), yn 'e lingte fan' e koades en yn 'e mande mei de trochgeande tiidrek fan in aparte koade, kin ferskille. De duraasjes fan 'e eleminêre sinjalen binne deselde (τ 0 = τ 1 = τ). Fansels, foar it oerdragen fan ynformaasje, yn trochferwizings per primêre alfabet, is de tiid K (A, 2 ) ∙ τ nedich . Sa kin de opdracht fan it optimisearjen fan net-unifoarmige kodearing as folgjend formulearre wurde: konstruearje in kodearringskema wêryn de totale duration fan de koades yn 'e oerdracht (of it totaal oantal coden by opslach) fan it berjocht it lytste wêze soe. Wat makket sa'n optimisaasje mooglik? Fansels sil de totale duration fan it berjocht minder wurde as de neikommende oanpak is: dy fan it primêre alfabet, dy't faker yn it berjocht fûn wurde, wurde lytsere koades yn 'e lingte oanwiisd, en foar dyjingen dy't de relatyf frekwinsje lytser binne - lannen. Mei oare wurden: Codes fan karakters fan it primêr alfabet, de kâns dat it opkommen is heger yn it berjocht, moat boud wurde fan it lytste mooglike oantal elementêre sinjalen en >

Parallel is it probleem foar ûnderskiedende koades te beheljen . Stel dan dat de folgjende folchoarder fan elemintêre sinjalen ûntfongen binne oan 'e útfier fan' e encoder:

00100010000111010101110000110

Hoe kin it dekodearre wurde? As de koade unifoarmich wie, soe it opjûne apparaat gewoan de opjûne (fêste) nûmer fan eleminêre sinjalen (bygelyks 5, lykas yn 'e Bodo-koade) te fertsjinjen en har yn oerienkomme mei de koade-tabel. Wannear't net-unifoarmige kodearring brûkt wurde, kinne twa oanwizen mooglik meitsje dat de koade ferskille.

De earste is om in spesjale kombinaasje fan elementêre sinjalen te brûken, dy't troch de decodearster as in skiedingskermen ynterpretearre wurdt . De twadde is yn gebrûk fan prefix-koades. Lit ús yn 't detail detailearje elk fan' e oanpak.

Unjildich delimearre koade

Wy akseptearje dat de skieding fan yndividuele letterkoades de sesje 00 is (teken fan it ein fan it karakter), en it wurd skieding fan wurden sil 000 wêze (it teken fan it ein fan it wurd is in romte). De folgjende koade geboutsregels binne fanselssprekkend:

De koade fan it teken fan it ein fan it karakter kin opnommen wurde yn 'e koade fan' e letter, omdat it net apart is (dus is de koade fan alle letters mei 00 ende);

Koade letters net twa or mear nullen yn 'e rige yn' e midden (oars sille se as it ein fan it karakter bepaald wurde);

De letterkoade (útsein de romte) moat altyd begjinne mei 1;

Wurd wurding ( 000 ) is altyd foarôfgeand fan in teken fan it ein fan it karakter; Yn dit gefal wurdt de sesje 00000 ynfierd (i.e., as oan 'e ein fan' e koade de kombinaasje ... 000 of ... 0000 is fûn, se binne net as wurdekselektor ferwachte); Dêrom kinne letterkoades mei 0 of 00 (oant it teken fan it ein fan it karakter) einigje.

Yn oerienstimming mei de neamde regels meitsje wy in koade-tabel oan. 3.1 foar brieven fan it Russyske alfabet, basearre op it earder jûn (tabel 2.1.) Wichtichheid fan it ferskinen fan yndividuele letters.

No, brûk de formule (A.11), kinne jo de gemiddelde lingte fan de koade K ( r, 2) fine, foar dizze kodingsmetoade:

Wat de Russyske taal, lykas bedoeld yn paragraaf 2.3, I 1 ( r ) = 4.356 bits is, is de redundans fan dizze koade neffens (3.5):

Dit betsjut dat mei dizze kodiermetoade sa'n 14% mear ynformaasje oerjûn wurde as it orizjinele berjocht befettet. Ferlykbere berekkeningen foar de Ingelske taal jouwe de wearde fan K ( e, 2) = 4.716, dat as ik 1 ( e ) = 4,036 bits foar de redundancy fan de koade Q ( e , 2) = 0.168 liedt.

Tabel 3.1.

As jo ​​ien fan 'e opsjes foar binêre net-unifoarmige kodearring beskôgje, sille wy probearje om antwurden op' e neikommende fragen te finen: is sa'n kodearring mooglik sûnder it gebrûk fan in karakter skiedingstaal? Is der de effektive (optimale) manier foar unjildige binêre kodearring?

It essinsje fan it earste probleem is om sa'n fariant te finen fan 'e berjochtkodearring, wêrtroch't de folgjende útwikseling fan elke yndividuele karakter fan it (dus decodearring) unwifellich is sûnder spesjale tekenteknearjende yndikators. De meast ienfâldige en brûkbere koades fan dit type binne de saneamde prefix-koades dy't de folgjende betingst befetsje (Fano kondysje):

In unjildich koade kin allinich dekodeard wurde as none fan 'e koades folslein mei it begjin (foarkar *) fan elk oare lingte koade falt.

* Yn de taalwittenskip betsjut de term "prefix" "prefix".

Bygelyks as der koade 110 is, dan kinne de koade 1, 11, 1101, 110101 , ensfh. Net foarkomme. As de Fano-kondysje befrediget, dan as it lêzen (dekodearjen) it kodearre berjocht trochgean mei de koade-tabel, kinne jo altyd spesifisearje wêr't ien koade einiget en de oare begjint.





Sjoch ek:

A.2. Tafoeging en ferdieling fan kâns

Haadstik 8. De formalisearring fan 'e presintaasje fan algoritme

Besykje fragen en taken

Struktureelteorem

Foarbyld 7.9

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ edudocs.fun