Shannon's stellingen over het coderen van een informatietransmissiekanaal. Shannon's directe stelling voor een bron van algemene vorm

Coderingsinformatie

Basisconcepten

De stellingen van Shannon over het coderen van berichten zijn hierboven vermeld. Het is intuïtief duidelijk dat codering de handeling is waarbij informatie wordt omgezet in de vorm die nodig is voor daaropvolgende verwerking (overdracht via een communicatiekanaal, opslag in het geheugen computersysteem, gebruik voor besluitvorming, enz.). Het is ook duidelijk dat bij het bouwen van een informatiesysteem Het is onmogelijk om zonder codering te doen: elke presentatie van informatie impliceert het gebruik van een soort codes. Daarom zullen we het verder in detail analyseren theoretische grondslagen coderen van informatie.

Laten A– willekeurig alfabet. Alfabetelementen A worden letters (of symbolen) genoemd, en eindige reeksen bestaande uit letters worden woorden genoemd A. Er wordt aangenomen dat er in elk alfabet een leeg woord is dat geen letters bevat.

Woord α 1 wordt het begin (voorvoegsel) van een woord genoemd α , als het woord bestaat α 2, zodanig dat α = α 1 α 2; tegelijkertijd het woord α 1 wordt gebeld eigen begin woorden α , Als α 2 is geen loos woord. De woordlengte is het aantal letters in het woord (een leeg woord heeft lengte 0). Dossier α 1 α 2 geeft de verbinding (aaneenschakeling) van woorden aan α 1 en α 2. Woord α 2 wordt de uitgang (achtervoegsel) van een woord genoemd α , als het woord bestaat α 1, zodanig dat α = α 1 α 2; tegelijkertijd het woord α 2 wordt de juiste uitgang van een woord genoemd α , Als α 1 is geen leeg woord. Een leeg woord wordt per definitie beschouwd als het begin en einde van elk woord α .

Denk eens aan het alfabet B = {0, 1, …, D– 1), waar D≥ 2, en een willekeurige set C. Willekeurige weergave van een set C in veel woorden in het alfabet B genaamd D-ary set-codering C(bij D= 2 codering zal binair zijn). De inverse mapping wordt decodering genoemd. Laten we voorbeelden van coderingen geven.

1. Coderen van de set natuurlijke getallen, waarin het getal N= 0 komt overeen met het woord e(0) = 0, en het getal N ≥ 1 binair woord

e(N) = B 1 B 2 … b l (N)

de kleinste lengte die aan de voorwaarde voldoet

Dat is duidelijk B 1 = 1, 2l (N) – 1 ≤ N < 2l (N) en daarom

l(N) = + 1 = ]log( N + 1)[,

Waar [ X] En ] X[ geeft het grootste gehele getal aan dat niet groter is dan X, en het kleinste gehele getal groter dan X. Woord e(N) wordt de binaire notatie van een getal genoemd N, en deze codering is de weergave van getallen in binair systeem Afrekening. Deze codering is één-op-één, want wanneer N 1 ≠ N 2 woorden e(N 1) en e(N 2) anders. Tabel 5.1 toont de weergave van de eerste 16 natuurlijke getallen in het binaire getallenstelsel.

Tabel 5.1

Codering e(N)

2. Coderen van de eerste 2 k natuurlijke getallen, waarvoor elk getal N (0 ≤ N < 2k) komt overeen met het woord

e k(N) = 0k – l (N) e(N),

waar invoer 0 is k – l (N) geeft een woord aan dat bestaat uit k – l(N) nullen, e(N) – weergave van een getal N in het hierboven besproken binaire getalsysteem. Deze codering geldt voor de eerste 16 natuurlijke getallen ( k= 4) wordt gegeven in tabel 5.2.

Tabel 5.2

Codering e k(N)

Laten A = {een ik, i= 1, 2, ...) is een eindig of telbaar alfabet, waarvan de letters zijn genummerd met natuurlijke getallen. In dit geval de codering van de letters van het alfabet A kan per volgorde worden gespecificeerd D-letterlijke woorden V = {v ik, i= 1, 2, …), waarbij v ik er is een afbeelding van een brief een ik. Dergelijke reeksen woorden (uit de set V) worden codes genoemd (van het alfabet A). Als de code wordt gegeven V alfabet A, dan de codering van woorden, waarin elk woord een ik 1 een ik 2 …een ik komt overeen met het woord v ik 1 v ik 2 …v ik, heet letter-voor-letter codering.

Bij de overstap van één-op-één-codering van letters van het alfabet naar letter-voor-letter-codering van woorden in het alfabet, blijft de eigenschap van één-op-één mogelijk niet behouden. Coderen bijvoorbeeld e(N) slaat niet op dit pand en codering e k(N) slaat het op. De één-op-één-eigenschap wordt bewaard door scheidbare codes. Code V = {v ik, i= 1, 2, …) wordt scheidbaar genoemd als van elke gelijkheid van de vorm

v ik 1 v ik 2 …v ik = v j 1 v j 2 …vjl

daar volgt het uit l = k En v ik 1 = v j 1 , v ik 2 = v j 2 , … , v ik = vjl. Scheidbare codes worden ook wel uniek decodeerbare codes genoemd.

Prefixcodes behoren tot de klasse van scheidbare codes. Code V = {v ik, i= 1, 2, …) wordt voorvoegsel genoemd als er geen woord is vk is niet het begin (voorvoegsel) van welk woord dan ook vl, l ≠ k. Als elk woord van een voorvoegselcode wordt vervangen door het kleinste begin, dat niet het begin is van andere codewoorden, dan zal de resulterende code ook een voorvoegsel zijn. Deze bewerking wordt voorvoegselcodeafkapping genoemd.

Voor willekeurige code V bestaande uit verschillende woorden, kun je een codeboom bouwen. Dit is een gerichte grafiek die geen cycli bevat, waarbij het hoekpunt β 1 aangesloten op de bovenkant β 2 rand gericht van β 1 tot β 2 als en slechts als β 2 = β 1 B, Waar B Î B = {0, 1, …, D – 1}, D≥ 2. Voor prefixcodes (en alleen daarvoor) valt de set codewoorden samen met de set eindhoekpunten (hoekpunten waar geen randen vandaan komen) van de codeboom.

Basiscoderingsstellingen

Eigenschappen van codes die nuttig zijn voor hun praktische toepassing, worden bepaald door de basiscoderingsstellingen.

Stelling 5.1. De ongelijkheid van Kraft. Voor het bestaan ​​van een uniek decodeerbare (scheidbare) code die bevat N codewoorden in de set (0, 1, D– 1) met lengtes N 1 , N 2 , …, n N, is het noodzakelijk en voldoende om de ongelijkheid in stand te houden

Bewijs. Laten we ons voorstellen dat we een codeboom hebben voor een prefixcode. De wortel van de codeboom vormt niveau 0, de hoekpunten die bij de wortel horen vormen niveau 1, enz. Mogelijk aantal hoekpunten per k-de niveau dat we aanduiden als Dk. Elke piek k niveau spawnt precies Dn – k pieken N-de niveau.

N 1 ≤ N 2 ≤…≤ n N = N.

Uiteraard het codewoord van lengte k verbiedt precies Dn – k mogelijke eindhoekpunten (hoekpunten van het laatste niveau). Dan verbieden alle codewoorden van de prefixcode de eindhoekpunten. Omdat het totale aantal eindhoekpunten is Dn, dan is de ongelijkheid waar

,

waaruit dat volgt

De ongelijkheid van Kraft is dus bewezen.

Als resultaat van het bewijs van Stelling 5.1 wordt geconcludeerd dat er op zijn minst prefixcodes zijn die uniek decodeerbare codes zijn met codewoordlengtes N 1 , N 2 , …, n N, waarmee de ongelijkheid van Kraft wordt bevredigd. De volgende stelling, de verklaring van McMillan genoemd, generaliseert deze conclusie voor alle uniek decodeerbare codes.

Stelling 5.2. McMillans ongelijkheid. Elke uniek decodeerbare code voldoet aan de ongelijkheid van Kraft.

Bewijs. Laten we de som verheffen tot een macht L:

. (5.1)

Laten Een k– aantal combinaties met L codewoorden met totale lengte k. Dan kan uitdrukking (6.1) worden weergegeven als

,

Waar L maximaal – maximale lengte berichten bevatten L codewoorden. Als de code uniek decodeerbaar is, dan komen alle reeksen uit L codewoorden van totale lengte k zijn verschillend. Omdat er alleen maar Dk mogelijke reeksen dus Een k ≤ Dk en dan

Omdat L is het aantal onafhankelijke codewoorden dat wordt gebruikt om alle mogelijke reeksen met een maximale lengte te construeren L maximaal Dat is waarom L ≤ L maximaal en . En hieruit volgt dat

Omdat de bovenstaande redenering geldt voor elke uniek decodeerbare code, en niet alleen voor prefixcodes, is de bewering van McMillan bewezen.

De volgende stellingen hebben betrekking op de entropie van een berichtenbron en de gemiddelde lengte van een codewoord.

Stelling 5.3. Broncoderingsstelling I. Voor elke discrete bron zonder geheugen X met eindig alfabet en entropie H(X) bestaat D-ichny voorvoegselcode, waarin de gemiddelde codewoordlengte voldoet aan de ongelijkheid

. (5.2)

Bewijs. Laten we eerst uitleggen dat een discrete bron zonder geheugen wordt beschreven door een model dat geen rekening houdt met de verbindingen tussen berichtsymbolen. Laten we het nu bewijzen linkerkant ongelijkheden (6.2):

Om dit te doen, gebruiken we de definitie van entropie en de ongelijkheid van Kraft:

Om de rechterkant van ongelijkheid (6.2) te bewijzen, herschrijven we de ongelijkheid van Kraft in de volgende vorm:

.

Vervolgens kiezen we voor elke term het kleinste gehele getal n ik, waarbij

Omdat de ongelijkheid van Kraft bij deze keuze hetzelfde blijft, kunnen we de overeenkomstige prefixcode construeren. Omdat n ik is het kleinste gehele getal, dan voor n ik– 1 is eerlijk

Aldus is de broncoderingsstelling I bewezen. Het bepaalt dat de gemiddelde lengte van een codewoord niet kleiner kan zijn dan de entropie van de berichtenbron. Merk op dat het bewijs van de stelling dezelfde notatie gebruikte als bij het beschouwen van de ongelijkheid van Kraft.

Stelling 5.4. Broncoderingsstelling II. Voor bloklengte L bestaat D-aire prefixcode waarin de gemiddelde lengte van een codewoord per teken voldoet aan de ongelijkheid

,

Waar .

Bewijs. Hier blokken met karakters en H(X 1 , X 2 , …, X L) is de entropie van de berichtenbron per blok L karakters. Om de stelling te bewijzen, kun je de broncoderingsstelling I gebruiken:

Bovendien, aangezien de minimaal haalbare lengte van een codewoord per symbool de waarde is, geldt wanneer D= 2 coderedundantie kan worden bepaald met de formule .

Cursus programma

"Informatie- en coderingstheorie"

Colleges worden gegeven in het 4e jaar, VII semester,

51 uur, docent universitair hoofddocent

Het concept van informatie, entropie. Communicatiesystemen. Discrete bronnen. Beschrijving van de bron die gebruikt wordt willekeurig proces. Statistische onafhankelijkheid. Markov-bronnen. Ergodiciteit. Ergodiciteit van de Bernoulli-bron.

Afleiding van de entropieformule (volgens Fadeev). Wederzijdse informatie en de eigenschappen ervan. Eigenschappen van entropie. Stelling over maximale waarde entropie. Entropie per tijdseenheid van de berichtbron.

Het probleem van het coderen van een discrete bron met codes gelijke lengte. Coderingssnelheid. Hoge waarschijnlijkheidssets. Directe en inverse stellingen voor het coderen van een discrete bron met codes van gelijke lengte.

Het probleem van het coderen van een bron met codes van ongelijke lengte. Coderingskosten. Ondubbelzinnig ontcijferbare codes. Voorvoegselcodes. Codering per letter. Een noodzakelijke en voldoende voorwaarde voor de unieke ontcijferbaarheid van een code. Volledige codes. Stelling voor het coderen van een discrete bron met codes van ongelijke lengte. Algoritmen voor het construeren van optimale codes (Fano, Shannon, Huffman). Constructie van een binaire optimale code met een gelijke waarschijnlijkheidsverdeling van invoerkansen. Toepassing van de informatietheorie resulteert in het bewijzen van onder- en bovengrenzen voor de complexiteit van het implementeren van Booleaanse functies in sommige klassen van besturingssystemen. Een methode voor het construeren van een optimale code onder de voorwaarde dat de waarschijnlijkheidsverdeling van bronletters onbekend is. Markovs stelling over de unieke ontcijferbaarheid van een code. Adaptieve algoritmen voor informatiecompressie.

Discreet kanaal zonder geheugen. Binair symmetrisch kanaal. De snelheid van informatieoverdracht in het kanaal. Kanaalcapaciteit. Uitgebreid kanaal en zijn capaciteit. Doorslaggevende patronen en groeperingen van observaties. Mogelijkheid tot foutieve overdracht van informatie. Feinsteins ongelijkheid. Directe stelling voor kanaalcodering zonder geheugen. Fano's ongelijkheid. Informatieverwerkingsstelling. Inversie van de coderingsstelling.

Theorie geluidswerende codering. Criterium voor maximale waarschijnlijkheid. Codeer afstand. Pariteitscodes. Generatief en matrices controleren. Syndroom. Decoderingsalgoritme voor pariteitscontrolecodes. Lineaire codes en hun decoderingsalgoritme. Hamming gebonden. Hamming-code. Cyclische codes. Coderen en decoderen van cyclische codes.

LITERATUUR

1. Gallagher R. Informatietheorie en betrouwbare verbinding., M., Sov. Radio, 1979.

2. Krichevsky E. Lezingen over theorie en informatie, Novosibirsk, NSU, 1966.

3. Kolesnik V., Poltyrev G. Cursus informatietheorie, Nauka, 1982.

4. Fainstein A. Fundamentals of Information Theory, M., IL, 1960.

5. Peterson V., Weldon F. Foutcorrectiecodes, M., Mir, 1976.

6. Berlekamp Algebraïsche coderingstheorie, M., Mir, 1971.

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5. Informatiecodering

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5.1. Basisconcepten

De stellingen van Shannon over het coderen van berichten zijn hierboven vermeld. Het is intuïtief duidelijk dat codering de handeling is waarbij informatie wordt omgezet in de vorm die nodig is voor daaropvolgende verwerking (overdracht via een communicatiekanaal, opslag in het geheugen van een computersysteem, gebruik voor besluitvorming, enz.). Het is ook duidelijk dat het bij het bouwen van welk informatiesysteem dan ook onmogelijk is om zonder codering te doen: elke presentatie van informatie impliceert het gebruik van een soort codes. Daarom zullen we vervolgens de theoretische grondslagen van informatiecodering in detail analyseren.

Laat A elk alfabet. Alfabetelementen A worden letters (of symbolen) genoemd, en eindige reeksen bestaande uit letters worden woorden genoemd A . Er wordt aangenomen dat er in elk alfabet een leeg woord is dat geen letters bevat.

Woord α 1 wordt het begin (voorvoegsel) van een woord genoemdα , als het woord bestaatα 2 zodat α = α 1 α 2 ; in dit geval het woord α 1 heet het juiste begin van een woordα als α 2 is geen leeg woord. De woordlengte is het aantal letters in het woord (een leeg woord heeft lengte 0). Dossierα 1 α 2 duidt een verbinding (aaneenschakeling) van woorden aanα 1 en α 2. Woord α 2 heet het einde (achtervoegsel) van een woordα , als het woord bestaatα 1 zodanig dat α = α 1 α 2 ; in dit geval het woord α 2 heet de juiste uitgang van een woordα als α 1 is geen leeg woord. Een leeg woord wordt per definitie beschouwd als het begin en einde van elk woordα .

Denk eens aan het alfabet B = (0, 1, …, D 1), waarbij D ≥ 2, en een willekeurige set C . Willekeurige weergave van een set C in veel woorden in het alfabet B heet D -ary set-codering C (bij D = 2 codering zal binair zijn). De inverse mapping wordt decodering genoemd. Laten we voorbeelden van coderingen geven.

1. Coderen van de set natuurlijke getallen, waarin het getal N = 0 komt overeen met het woord e (0) = 0, en getal n ≥ 1 binair woord

e (n) = b 1 b 2 … b l (n)

de kleinste lengte die aan de voorwaarde voldoet

Het is duidelijk dat b 1 = 1, 2 l (n) 1 ≤ n< 2 l (n ) en daarom

l(n) = + 1 = ]log(n + 1)[,

waarbij [ x ] en ] x [ geeft het grootste gehele getal aan dat niet groter is dan X , en het kleinste gehele getal groter dan X. Woord e(n ) wordt de binaire notatie van een getal genoemd N , en deze codering is een weergave van getallen in het binaire getalsysteem. Deze codering is één-op-één, want wanneer n 1 ≠ n 2 woorden e (n 1) en e (n 2 ) zijn verschillend. Tabel 5.1 toont de weergave van de eerste 16 natuurlijke getallen in het binaire getallenstelsel.

" xml:lang="ru-RU" lang="ru-RU">Tabel 5.1

" xml:lang="ru-RU" lang="ru-RU"> Codering" xml:lang="en-US" lang="en-US">e" xml:lang="ru-RU" lang="ru-RU">(" xml:lang="en-US" lang="en-US">n" xml:lang = "ru-RU" lang = "ru-RU">)

2. Coderen van de eerste 2 k natuurlijke getallen, waarvoor elk getal n (0 ≤ n< 2 k ) komt overeen met het woord

e k (n) = 0 k l (n) e (n),

waarbij de invoer 0 k l (n) is betekent een woord bestaande uit k l (n) nullen, e (n ) getalweergave N in het hierboven besproken binaire getalsysteem. Deze codering geldt voor de eerste 16 natuurlijke getallen ( k = 4) wordt gegeven in tabel 5.2.

" xml:lang="ru-RU" lang="ru-RU">Tabel 5." xml:lang="en-US" lang="en-US">2

" xml:lang="ru-RU" lang="ru-RU"> Codering" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="ru-RU" lang="ru-RU">(" xml:lang="en-US" lang="en-US">n" xml:lang = "ru-RU" lang = "ru-RU">)

Laat A = ( a ik , ik = 1, 2, ...) een eindig of telbaar alfabet, waarvan de letters zijn genummerd met natuurlijke getallen. In dit geval de codering van de letters van het alfabet A kan per volgorde worden gespecificeerd D-aire woorden V = (v i, i = 1, 2, …), waarbij v i er is een afbeelding van een brief een ik . Dergelijke reeksen woorden (uit de set V ) worden codes genoemd (van het alfabet A ). Als code V van alfabet A wordt gegeven , dan de codering van woorden, waarin elk woord a ik 1 een ik 2 … een ik komt overeen met het woord v ik 1 v ik 2 … v ik , heet letter-voor-letter codering.

Bij de overstap van één-op-één-codering van letters van het alfabet naar letter-voor-letter-codering van woorden in het alfabet, blijft de eigenschap van één-op-één mogelijk niet behouden. Coderen bijvoorbeeld e(n ) behoudt deze eigenschap niet, maar de codering e k (n ) slaat het op. De één-op-één-eigenschap wordt bewaard door scheidbare codes. Code V = ( v ik , ik = 1, 2, …) wordt scheidbaar genoemd als van elke gelijkheid van de vorm

v ik 1 v ik 2 … v ik = v j 1 v j 2 … v jl

hieruit volgt dat l = k en v i 1 = v j 1, v i 2 = v j 2, …, v ik = v jl . Scheidbare codes worden ook wel uniek decodeerbare codes genoemd.

Prefixcodes behoren tot de klasse van scheidbare codes. Code V = ( v ik , ik = 1, 2, …) wordt voorvoegsel genoemd als er geen woord is vk is niet het begin (voorvoegsel) van welk woord dan ook v l , l ≠ k . Als elk woord van een voorvoegselcode wordt vervangen door het kleinste begin, dat niet het begin is van andere codewoorden, dan zal de resulterende code ook een voorvoegsel zijn. Deze bewerking wordt voorvoegselcodeafkapping genoemd.

Voor willekeurige code V bestaande uit verschillende woorden, kun je een codeboom bouwen. Dit is een gerichte grafiek die geen cycli bevat, waarbij het hoekpuntβ 1 verbonden met de bovenkantβ2 rand van af gerichtβ 1 tot β 2 , als en slechts alsβ 2 = β 1 b, waarbij b  B = (0, 1, …, D 1), D ≥ 2. Voor prefixcodes (en alleen daarvoor) valt de set codewoorden samen met de set eindhoekpunten (hoekpunten waar geen randen vandaan komen) van de codeboom.

5.2. Basiscoderingsstellingen

De eigenschappen van codes die nuttig zijn voor hun praktische toepassing worden bepaald door de basiscoderingsstellingen.

Stelling 5.1. De ongelijkheid van Kraft.Voor het bestaan ​​van een uniek decodeerbare (scheidbare) code die bevat N codewoorden in de set (0, 1, D 1) met lengtes n 1, n 2, …, n N , is het noodzakelijk en voldoende om de ongelijkheid in stand te houden

Bewijs. Laten we ons voorstellen dat we een codeboom hebben voor een prefixcode. De wortel van de codeboom vormt niveau 0, de hoekpunten die bij de wortel horen vormen niveau 1, enz. Mogelijk aantal hoekpunten per k -de niveau dat we aanduiden als Dk. Elk hoekpunt k niveau spawnt precies D n k hoekpunten van het n-de niveau.

n 1 ≤ n 2 ≤…≤ n N = n .

Uiteraard het codewoord van lengte k verbiedt precies D n k mogelijke eindhoekpunten (hoekpunten van het laatste niveau). Dan verbieden alle codewoorden van de prefixcode de eindhoekpunten. Omdat het totale aantal eindhoekpunten is Dn , dan is de ongelijkheid waar

waaruit dat volgt

De ongelijkheid van Kraft is dus bewezen.

Als resultaat van het bewijs van Stelling 5.1 wordt geconcludeerd dat er op zijn minst prefixcodes zijn die uniek decodeerbare codes zijn met codewoordlengtes n 1, n 2, …, n N , waarmee de ongelijkheid van Kraft wordt bevredigd. De volgende stelling, de verklaring van McMillan genoemd, generaliseert deze afleiding naar alle uniek decodeerbare codes.

Stelling 5.2. McMillans ongelijkheid.Elke uniek decodeerbare code voldoet aan de ongelijkheid van Kraft.

Bewijs. Laten we de som verheffen tot een macht L:

. (5.1)

Laat A k aantal combinaties met L codewoorden met totale lengte k . Dan kan uitdrukking (6.1) worden weergegeven als

waar Lmax maximale lengte van een bericht met daarin L codewoorden. Als de code uniek decodeerbaar is, dan komen alle reeksen uit L codewoorden van totale lengte k zijn verschillend. Omdat er alleen maar Dk mogelijke reeksen dus A k ≤ D k en dan

Sinds L dit is het aantal onafhankelijke codewoorden dat wordt gebruikt om alle mogelijke reeksen met een maximale lengte te construeren Lmax. Daarom L ≤ Lmax En. En hieruit volgt dat

Omdat de bovenstaande redenering geldt voor elke uniek decodeerbare code, en niet alleen voor prefixcodes, is de bewering van McMillan bewezen.

De volgende stellingen hebben betrekking op de entropie van een berichtbron en de gemiddelde lengte van een codewoord.

Stelling 5.3. Broncoderingsstelling I. Voor elke discrete bron zonder geheugen X met eindig alfabet en entropie H(X) bestaat D -aire prefixcode waarin de gemiddelde codewoordlengte voldoet aan de ongelijkheid

. (5.2)

Bewijs. Laten we eerst uitleggen dat een discrete bron zonder geheugen wordt beschreven door een model dat geen rekening houdt met de verbindingen tussen berichtsymbolen. Nu bewijzen we de linkerkant van ongelijkheid (6.2):

Om dit te doen, gebruiken we de definitie van entropie en de ongelijkheid van Kraft:

Om de rechterkant van de ongelijkheid (6.2) te bewijzen, herschrijven we de ongelijkheid van Kraft in de volgende vorm:

Vervolgens kiezen we voor elke term het kleinste gehele getal n ik, waarbij

Omdat de ongelijkheid van Kraft bij deze keuze hetzelfde blijft, kunnen we de overeenkomstige prefixcode construeren. Omdat n ik is het kleinste gehele getal, dan voor n ik 1 waar

Dan

Dus de broncoderingsstelling I bewezen. Het bepaalt dat de gemiddelde lengte van een codewoord niet kleiner kan zijn dan de entropie van de berichtbron. Merk op dat het bewijs van de stelling dezelfde notatie gebruikte als bij het beschouwen van de ongelijkheid van Kraft.

Stelling 5.4. Broncoderingsstelling II. -aire prefixcode waarin de gemiddelde lengte van een codewoord per teken voldoet aan de ongelijkheid

Waar.

Bewijs. Hier blokken met karakters en H (X 1, X 2, …, XL L ) is de entropie van de berichtbron per blok L karakters. Om de stelling te bewijzen, kunt u de broncoderingsstelling gebruiken I:

Broncoderingsstelling II stelt ons in staat te stellen dat er zulke codeermethoden bestaan ​​voor een bericht dat voldoende lang is, zodat de gemiddelde lengte van het codewoord willekeurig dicht bij de waarde kan worden gebracht. Wanneer inderdaad L  ∞, HL (X)  H , waarbij H entropie van de berichtbron per teken, geldt de volgende ongelijkheid:

, (5.3)

Waar. Dit kan ook als volgt worden geïnterpreteerd: voor elk willekeurig klein aantalε , bestaat er een werkwijze voor het coderen van blokken die symbolen bevatten waarin aan ongelijkheid (5.3) wordt voldaan voor de gemiddelde lengte van een codewoord per symbool.

Bovendien, aangezien de minimaal haalbare lengte van een codewoord per symbool de waarde is, en wanneer D = 2 coderedundantie kan worden bepaald met de formule.

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5.3. Optimale codering

Het probleem bij het construeren van een optimale code is het vinden van positieve gehele getallen n 1, n 2, …, n N , waardoor de gemiddelde lengte van het codewoord wordt geminimaliseerd, afhankelijk van de ongelijkheid van Kraft:

Bij het construeren van codes in het geval van een alfabet EEN = ( a ik , ik = 1, 2, …, N ) met een bekende waarschijnlijkheidsverdeling P = ( p ik, ik = 1, 2, …, N ) zonder verlies van algemeenheid kunnen we aannemen dat de letters van het alfabet A zijn genummerd in afnemende volgorde van hun kansen, d.w.z. p 1 ≥ p 2 ≥ … ≥ p N . Bovendien zullen we alleen rekening houden met binaire codes.

Er zijn twee bekende methoden (Fano en Shannon) voor het construeren van codes die bijna optimaal zijn. De werkwijze van Fano is als volgt. De lijst met letters, geordend in aflopende volgorde van waarschijnlijkheden, is verdeeld in twee opeenvolgende delen, zodat de som van de waarschijnlijkheden van de daarin opgenomen letters zo min mogelijk van elkaar verschillen. De letters uit het eerste deel krijgen het symbool 0 toegewezen, en de letters uit het tweede deel krijgen het symbool 1. Doe vervolgens hetzelfde met elk van de resulterende delen, als deze het volgende bevatten: ten minste, twee brieven. Het proces gaat door totdat de hele lijst is verdeeld in delen die elk één letter bevatten. Als resultaat van dit proces wordt aan elke letter een reeks symbolen toegewezen die aan die letter zijn toegewezen. Het is gemakkelijk in te zien dat de resulterende code een voorvoegsel is.

De methode van Shannon is alleen toepasbaar als alle kansen positief zijn. Het bestaat uit het feit dat de brief een ik , die een waarschijnlijkheid heeft p ik > 0, de volgorde van n ik = ] log (1/ p i )[ de eerste cijfers na het breukpunt van de ontbinding van een getal in een oneindige breuk (voor a 1 we nemen aan dat q 1 = 0). Sinds wanneer l > k (vanwege het feit dat p l ≤ p k ) n l ≥ n k en dan is de op deze manier verkregen code een voorvoegsel. Op basis van de verkregen prefixcode wordt een ingekorte prefixcode geconstrueerd, die het resultaat is van codering met behulp van de Shannon-methode.

Laat er bijvoorbeeld een reeks letters zijn EEN = ( een 1 , een 2 , een 3 , een 4 , een 5 , een 6 , een 7 ) met kansverdeling P = (0,2, 0,2, 0,19, 0,12, 0,11, 0,09, 0,09). Laten we letters coderen met behulp van de Fano-methode.

1. Laten we de lijst in twee delen verdelen, zodat de som van de kansen van de letters die erin zijn opgenomen zo min mogelijk van elkaar verschillen:

A 1 = ( een 1 , een 2 , een 3 ), P 1 = (0,2, 0,2, 0,19);

A 2 = (een 4, een 5, een 6, een 7), P 2 = (0,12, 0,11, 0,09, 0,09).

2. Laten we het symbool 0 toewijzen aan de letters uit het eerste deel, en het symbool 1 aan de letters van het tweede deel:

EEN 1 = (een 1/0, een 2/0, een 3/0) ;

Een 2 = (een 4/1, een 5/1, een 6/1, een 7/1).

3. Herhaal opeenvolgend gespecificeerde acties voor elk onderdeel afzonderlijk. IN als resultaat krijgen we:

EEN 1 1 = (een 1/00);

A 121 = (a 2/010);

EEN 122 = (een 3/011);

EEN 211 = (een 4/100);

EEN 212 = (een 5/101);

EEN 221 = (een 6/110);

Een 222 = (een 7/111).

Voor elke letter rechts van de schuine streep worden de door de codering verkregen codewoorden weergegeven. In dit geval toont de volgorde van de indices van de resulterende lijsten met één letter de volgorde waarin de oorspronkelijke lijst met groepen in delen is opgesplitst.

Het codeerproces met behulp van de Fano-methode wordt handig weergegeven in de vorm van een tabel. Voor het beschouwde voorbeeld is dit weergegeven in Tabel 5.3.

" xml:lang="ru-RU" lang="ru-RU">Tabel 5.3

" xml:lang="ru-RU" lang="ru-RU"> Codering met behulp van de Fano-methode

Laten we de gemiddelde lengte van het codewoord bepalen:

Laten we nu de codering uitvoeren met behulp van de methode van Shannon. Het codeerproces wordt gegeven in Tabel 5.4.

" xml:lang="ru-RU" lang="ru-RU">Tabel 5.4

" xml:lang="ru-RU" lang="ru-RU"> Codering met behulp van de Shannon-methode

Net als in het vorige geval vinden we de gemiddelde lengte van het codewoord:

.

Zoals u kunt zien, kwamen de resultaten van het coderen met behulp van de Fano- en Shannon-methoden wat betreft het minimaliseren van de gemiddelde codelengte vrijwel overeen. Daarom worden deze methoden vaak als één beschouwd (in de formulering van Fano) en de Shannon-Fano-methode genoemd.

In 1952 stelde David Huffman een optimale prefixcoderingsmethode voor discrete bronnen voor, die, in tegenstelling tot de Shannon- en Fano-methoden, in de praktijk nog steeds wordt gebruikt. D. Huffman bewees dat de gemiddelde lengte van een codewoord verkregen met zijn methode minimaal zal zijn. Huffman-codering gebeurt in drie stappen.

1. Volgorde: letters zijn gerangschikt in aflopende volgorde van hun waarschijnlijkheid.

2. Reductie: twee letters met de laagste waarschijnlijkheid worden gecombineerd tot één met een totale waarschijnlijkheid; de lijst met letters wordt opnieuw gerangschikt volgens stap 1; het proces gaat door totdat alle letters tot één zijn gecombineerd. In dit geval is het mogelijk om de lengte van codewoorden gelijk te maken met behulp van de volgende strategie: als verschillende letters dezelfde waarschijnlijkheid hebben, worden die twee letters die voorheen het minste aantal combinaties hadden, gecombineerd (hoewel dit geen invloed heeft op de gemiddelde codelengte).

3. Codering: vanaf de laatste combinatie wordt het symbool 0 opeenvolgend toegewezen aan één component van de samengestelde letter, en het symbool 1 aan de tweede; het proces gaat door totdat alle originele letters zijn gecodeerd.

Laten we coderen met behulp van de Huffman-methode voor de set die wordt beschouwd in de voorbeelden van het gebruik van de Fano- en Shannon-methoden.

1. Eerste lijst met lettersA = { A1 , A2 , A3 , A4 , A5 , A6 , A7 ) is al besteld, sindsdienP = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}.

2. Laten we de letters combinerenA6 EnA7 in één briefA1 met waarschijnlijkheid0.18 Enopnieuw ordenenlijst:

P1 = {0.2, 0.2, 0.19, 0.18, 0.12, 0.11}, A1 = { A1 , A2 , A3 , A1 , A4 , A5 }.

3. Herhaal stap 2 totdat er nog één letter in de lijst overblijft:

P2 = {0.23, 0.2, 0.2, 0.19, 0.18}, A2 = { A2 , A1 , A2 , A3 , A1 };

P3 = {0.37, 0.23, 0.2, 0.2}, A3 = { A3 , A2 , A1 , A2 };

P4 = {0.4, 0.37, 0.23}, A4 = { A4 , A3 , A2 };

P5 = {0.6, 0.4}, A5 = { A5 , A4 };

P6 = {1}, A6 = { A6 }.

4. Laten we gepast zijnbinaircodessymbolen:

A6 : A5 = 0, A4 = 1;

A5 : A3 = 00, A2 = 01;

A4 : A1 = 10, A2 = 11;

A3 : A3 = 000, A1 = 001;

A2 : A4 = 010, A5 = 011;

A1 : A6 = 0010, A7 = 0011.

Zo worden aan de beginletters de volgende binaire codes toegewezen:A1 = 10, A2 = 11, A3 = 000, A4 = 010, A5 = 011, A6 = 0010, A7 = 0011, wat een gemiddelde codelengte oplevert die kleiner is dan in het geval van Fano- en Shannon-codering.

Laten we de redundantie van de ontvangen codes bepalen. Om dit te doen, gaan we de entropie van de berichtbron bepalen:

.

Dan hebben de codes de volgende redundantie:

Fanocode: ;

Shannon-code: ;

Huffman-code: .

De redundantie van de Huffman-code is dus minimaal.

Om redundantie te verminderen, d.w.z. Om de gemiddelde lengte van een codewoord met één symbool te verminderen, kunt u blokcodering gebruiken, waarvan de reden wordt gegeven in de broncoderingsstellingII. In dit geval is het noodzakelijk om alle mogelijke lettergroepen te verkrijgen gegeven lengte, zoek de kansen van de groepen als de kansen dat de letters van de groep tegelijkertijd samen verschijnen, en voer de codering uit, waarbij je de groepen behandelt als symbolen van een nieuw alfabet.

PAGINA 43

De informatiecapaciteit van discrete (4.4) en de capaciteit van continue (4.7) kanalen karakteriseert hun maximale mogelijkheden als middel voor informatieoverdracht. Ze worden onthuld in de fundamentele stellingen van de informatietheorie, die bekend staan ​​als de fundamentele stellingen van de Shannon-codering. Met betrekking tot een discreet kanaal luidt het:

Stelling 4.4.1. (Directe coderingsstelling voor DKBP.) Voor een discreet kanaal zonder geheugen met codesnelheden R, kleiner dan de informatiecapaciteit, is er altijd een code waarvoor de gemiddelde foutwaarschijnlijkheid naar nul neigt naarmate de lengte van het codewoord toeneemt.

In het geval van een continu kanaal wordt dit als volgt geformuleerd

Stelling 4.4.2. (Directe coderingsstelling voor het AWGN-kanaal). Via een AWGN-kanaal met onbeperkte bandbreedte kan informatie worden verzonden met een willekeurig lage foutkans als de transmissiesnelheid lager is dan de bandbreedte.

De omgekeerde stelling luidt:

Stelling 4.4.3. Op baudrate
, hogere communicatiekanaalcapaciteit C, geen enkele code zal een willekeurig kleine kans op decoderingsfouten opleveren, d.w.z. absoluut betrouwbare berichtoverdracht.

Opgemerkt moet worden dat als de inverse stelling wordt bewezen voor een willekeurig model van een communicatiekanaal, de directe stelling alleen wordt bewezen voor specifieke soorten kanalen.

De resultaten van de coderingsstellingen voor een kanaal met ruis zijn enigszins onverwacht. Op het eerste gezicht lijkt het er inderdaad op dat het verminderen van de kans op fouten bij het verzenden van berichten een overeenkomstige verlaging van de overdrachtssnelheid vereist, en dat deze laatste samen met de kans op fouten naar nul zou moeten neigen. Deze conclusie volgt in het bijzonder uit het beschouwen van meervoudige hertransmissie van symbolen via een kanaal als een manier om de waarschijnlijkheid van fouten bij de berichtoverdracht te verminderen. In dit geval is het, in de aanwezigheid van interferentie in het communicatiekanaal, mogelijk om ervoor te zorgen dat de kans op fouten bij het verzenden van berichten alleen naar nul neigt als de transmissiesnelheid naar nul neigt.

De coderingsstelling laat echter zien dat het in principe mogelijk is om te zenden met een snelheid die willekeurig dichtbij ligt C, terwijl een willekeurig kleine foutkans wordt bereikt. Helaas geven de stellingen, hoewel ze het fundamentele bestaan ​​van een foutbestendige code aangeven, geen recept voor het vinden ervan. We kunnen alleen opmerken dat het hiervoor nodig is om lange codes te gebruiken. Bovendien, naarmate de transmissiesnelheid de doorvoer nadert en de kans op fouten afneemt, wordt de code complexer als gevolg van een toename van de lengte van de blokken, wat leidt tot een scherpe complicatie van de coderings- en decoderingsapparaten, evenals een vertraging in de uitvoer van informatie tijdens het decoderen. Momenteel gebruikte codeermethoden, die later zullen worden besproken, realiseren zich niet de potentiële mogelijkheden van het communicatiesysteem. De enige uitzondering vormen de onlangs geopende turbocodes.

1Dit resultaat geldt voor alle symmetrische kanalen.

Bereikte een mate van nabijheid tot het gemiddelde aantal k binaire tekens per letter van het bericht naar H kan zoveel als gewenst verder worden vergroot door over te gaan op het coderen van steeds langere blokken. Dit volgt uit de volgende algemene verklaring, die de fundamentele coderingsstelling wordt genoemd.

Stelling: Bij het coderen van een bericht dat is opgedeeld in N-letterblokken kunnen worden geselecteerd N groot genoeg om ervoor te zorgen dat het gemiddelde aantal k elementaire binaire signalen per letter origineel bericht was zo dichtbij H. Opmerking: zeer lang bericht van M letters kunnen worden gecodeerd

willekeurig dicht bij het nummer gebruiken M.H.(maar groter) aantal elementaire signalen, als dit bericht maar eerst voldoende wordt opgedeeld lange blokken van N letters en vergelijk individuele codes met hele blokken tegelijk. Blokcoderingsmethoden kunnen heel verschillend zijn (u kunt bijvoorbeeld de methoden van Shannon-Fano en Huffman gebruiken)

m-ary codes

De inhoud van de voorgaande paragrafen kan eenvoudig worden overgebracht naar de casus M-aire codes gebruiken M elementaire signalen. Dus bijvoorbeeld om te bouwen M-ary Shannon-Fano-codes, je hoeft alleen maar de groepen symbolen te splitsen, niet in 2, maar in M onderdelen, zo dicht mogelijk bij de totale waarschijnlijkheid, en voor constructie M-ary Huffman-code, is het noodzakelijk om de alfabetcompressiebewerking te gebruiken, waarbij elke keer niet twee worden samengevoegd, maar M letters van het originele alfabet die de laagste waarschijnlijkheid hebben.

Vanwege het belang van Huffman-codes zullen we dieper op dit onderwerp ingaan. Alfabetcompressie, waarin M letters worden vervangen door één leidt tot een afname van het aantal letters door m − 1. Dus wat betreft de constructie M-ary-code is uiteraard vereist, zodat de reeks compressies ons naar het alfabet leidt M letters (overeenkomend M code signalen), dan is het noodzakelijk dat het nummer N letters van het originele alfabet kunnen in de vorm worden weergegeven N=M+S(m − 1), waar S-geheel aantal compressies.

Dit kan altijd worden bereikt door, indien nodig, nog een paar “fictieve letters” aan het oorspronkelijke alfabet toe te voegen, waarvan de waarschijnlijkheid gelijk wordt geacht aan 0. Hierna wordt de constructie M-ary Huffman-code wordt op precies dezelfde manier geproduceerd als in het geval van binaire code.

Voorbeeld: In het geval van een alfabet van 6 letters met waarschijnlijkheden 0 : 4; 0: 2; 0: 2; 0: 1; 0: 05; 0: 05.Voor constructie ternair Huffman-code, moeten we nog een fictieve letter met een nulwaarschijnlijkheid aan ons alfabet toevoegen en verder gaan zoals aangegeven in de tabel:

code-matching N letters van het alfabet N reeksen van ontvangende elementaire signalen M mogelijke waarden.

Deze verklaring ( ∗ ) werd voor het eerst bewezen in 1949 door de Amerikaanse wetenschapper L. Craft en werd later gegeneraliseerd door B. Macmillan, vandaar de ongelijkheid ( ∗ ) wordt vaak de Kraft-MacMillan-ongelijkheid genoemd. Met behulp van de ongelijkheid ( ∗ ) kunt u het volgende resultaat krijgen:

Stelling: belangrijkste coderingsstelling voor M-aire codes. Voor elke codeermethode die gebruikt wordt M-min code gemiddeld getal k elementaire signalen per letter van het bericht kunnen nooit kleiner zijn dan de verhoudingslog H m, Waar H- entropie van één berichtletter. Het kan echter altijd willekeurig dicht bij deze waarde worden gemaakt als u blokken codeert die lang genoeg zijn N brieven

Gevolg: Als een communicatielijn binnen een bepaalde tijdseenheid kan zenden L elementaire signalen ontvangen M verschillende betekenissen, dan de snelheid berichtoverdracht Door

snelheid, zo dicht mogelijk bij v(maar minder v) is mogelijk. Grootte C=L loggen M hangt alleen af ​​van de kenmerken van de communicatielijnen, in die tijd, als een teken H karakteriseert de verzonden boodschap. Grootte C geeft aan grootste aantal eenheden informatie die per tijdseenheid via een communicatielijn kunnen worden verzonden. Het heet doorvoer communicatie lijnen.