Kod med variabel längd - Variable-length code

I kodningsteori en varierbar längd kod är en kod som mappar källsymboler till ett variabelt antal bitar.

Variabel-längdkoder kan tillåta källor som ska komprimeras och dekomprimeras med noll fel ( förlustfri datakompression ) och ändå läsas tillbaka symbol för symbol. Med rätt kodningsstrategi kan en oberoende och identiskt fördelad källa komprimeras nästan godtyckligt nära dess entropi . Detta står i kontrast till kodningsmetoder med fast längd, för vilken datakomprimering endast är möjlig för stora datablock, och varje komprimering bortom logaritmen för det totala antalet möjligheter kommer med en begränsad (men kanske godtyckligt liten) sannolikhet för att misslyckas.

Några exempel på kända strategier för variabel längd är Huffman-kodning , Lempel – Ziv-kodning , aritmetisk kodning och kontextanpassad kodning med variabel längd .

Koder och deras tillägg

Förlängningen av en kod är mappning av källsekvenser med begränsad längd till bitsträngar med begränsad längd, som erhålls genom att för varje symbol för källsekvensen sammanfoga motsvarande kodord producerat av den ursprungliga koden.

Med hjälp av termer från formell språkteori är den exakta matematiska definitionen följande: Låt och var två ändliga uppsättningar, kallade käll- respektive målalfabet. En kod är en total funktion kartläggning varje symbol från en sekvens av symboler över , och en utvidgning av en homomorfism av in , vilket naturligtvis mappar varje sekvens av källsymboler till en sekvens av målsymboler, hänvisas till som dess förlängning . ${\ displaystyle S}$ ${\ displaystyle T}$ ${\ displaystyle C: S \ till T^{*}}$ ${\ displaystyle S}$ ${\ displaystyle T}$ ${\ displaystyle C}$ ${\ displaystyle S^{*}}$ ${\ displaystyle T^{*}}$

Klasser av koder med variabel längd

Koder med variabel längd kan strikt kapslas i ordning efter minskande generalitet som icke-singulara koder, unikt avkodbara koder och prefixkoder. Prefixkoder är alltid unikt avkodbara, och dessa är i sin tur alltid icke-singular:

Icke-enskilda koder

En kod är icke-singular om varje källsymbol mappas till en annan icke-tom bitsträng, dvs mappningen från källsymboler till bitsträngar är injektiv .

Till exempel kartläggning är inte icke-singulär eftersom både "a" och "b" karta till samma bit strängen "0"; varje förlängning av denna mappning kommer att generera en förlustfri (icke-förlustfri) kodning. Sådan singulär kodning kan fortfarande vara användbar när viss förlust av information är acceptabel (till exempel när sådan kod används vid ljud- eller videokomprimering, där en förlustig kodning blir ekvivalent med källkvantisering ). ${\ displaystyle M_ {1} = \ {\, a \ mapsto 0, b \ mapsto 0, c \ mapsto 1 \, \}}$
Kartläggningen är dock icke-singular; dess förlängning kommer att generera en förlustfri kodning, vilket kommer att vara användbart för allmän dataöverföring (men den här funktionen krävs inte alltid). Observera att det inte är nödvändigt att den icke-singulära koden är mer kompakt än källan (och i många applikationer är en större kod användbar, till exempel som ett sätt att upptäcka och/eller återställa från kodnings- eller överföringsfel, eller i säkerhetsapplikationer för att skydda en källa från oupptäckt manipulering). ${\ displaystyle M_ {2} = \ {\, a \ mapsto 1, b \ mapsto 011, c \ mapsto 01110, d \ mapsto 1110, e \ mapsto 10011, f \ mapsto 0 \}}$

Unikt avkodbara koder

En kod är unikt avkodbar om dess tillägg är icke-singular (se ovan). Huruvida en given kod är unikt avkodbar kan avgöras med Sardinas – Patterson -algoritmen .

Kartläggningen är unikt avkodbar (detta kan demonstreras genom att titta på uppföljningen efter varje målbitsträng på kartan, eftersom varje bitsträng avslutas så snart vi ser en 0-bit som inte kan följa någon befintlig kod för att skapa en längre giltig kod på kartan, men startar otvetydigt en ny kod). ${\ displaystyle M_ {3} = \ {\, a \ mapsto 0, b \ mapsto 01, c \ mapsto 011 \, \}}$
Tänk igen på koden från föregående avsnitt. Denna kod är inte unikt avkodbar, eftersom strängen 011101110011 kan tolkas som sekvensen av kodord 01110 - 1110 - 011 , men också som sekvensen av kodorden 011 - 1 - 011 - 10011 . Två möjliga avkodningar av denna kodade sträng ges således av cdb och babe . En sådan kod är dock användbar när uppsättningen av alla möjliga källsymboler är fullständigt känd och ändlig, eller när det finns begränsningar (till exempel en formell syntax) som avgör om källelement i detta tillägg är acceptabla. Sådana begränsningar möjliggör avkodning av det ursprungliga meddelandet genom att kontrollera vilka av de möjliga källsymbolerna som är mappade till samma symbol som är giltiga enligt dessa begränsningar. ${\ displaystyle M_ {2}}$

Prefixkoder

En kod är en prefixkod om ingen målbitsträng i mappningen är ett prefix för målbitsträngen för en annan källsymbol i samma mappning. Detta innebär att symboler kan avkodas omedelbart efter att hela deras kodord har tagits emot. Andra vanliga namn för detta koncept är prefixfri kod , momentan kod eller kontextfri kod .

Exempelkartläggningen i föregående stycke är inte en prefixkod eftersom vi inte vet efter att ha läst bitsträngen "0" om den kodar en "a" källsymbol, eller om det är prefixet för kodningarna för "b" eller "c" symboler. ${\ displaystyle M_ {3}}$
Ett exempel på en prefixkod visas nedan.

Symbol	Kodord
a	0
b	10
c	110
d	111

Exempel på kodning och avkodning:

aabacdab → 00100110111010 → | 0 | 0 | 10 | 0 | 110 | 111 | 0 | 10 | → aabacdab

Ett specialfall av prefixkoder är blockkoder . Här måste alla kodord ha samma längd. De senare är inte särskilt användbara i samband med källkodning , men fungerar ofta som felkorrigerande koder i samband med kanalkodning .

Ett annat specialfall med prefixkoder är mängdkoder med variabel längd , som kodar godtyckligt stora heltal som en sekvens av oktetter-dvs varje kodord är en multipel av 8 bitar.

Fördelar

Fördelen med en variabel längdkod är att osannolika källsymboler kan tilldelas längre kodord och sannolikt källsymboler kan tilldelas kortare kodord, vilket ger en låg förväntad kodordlängd. För exemplet ovan, om sannolikheterna för (a, b, c, d) var , skulle det förväntade antalet bitar som används för att representera en källsymbol med koden ovan vara: ${\ displaystyle \ textstyle \ left ({\ frac {1} {2}}, {\ frac {1} {4}}, {\ frac {1} {8}}, {\ frac {1} {8} }\höger)}$

{\ displaystyle 1 \ times {\ frac {1} {2}}+2 \ times {\ frac {1} {4}}+3 \ times {\ frac {1} {8}}+3 \ times {\ frac {1} {8}} = {\ frac {7} {4}}}

.

Som entropin hos denna källa är 1.7500 bitar per symbol, komprimerar denna kod källan så mycket som möjligt, så att källan kan återvinnas med noll fel.

Anteckningar

^ ^a ^b Denna kod är baserad på ett exempel som finns i Berstel et al. (2009), exempel 2.3.1, sid. 63.

Referenser

Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Koder och automat . Encyclopedia of Mathematics and its Applications. 129 . Cambridge: Cambridge University Press . ISBN 978-0-521-88831-8. Zbl 1187.94001 . Utkast tillgängligt online

[:0-1] Denna kod är baserad på ett exempel som finns i Berstel et al. (2009), exempel 2.3.1, sid. 63.

Languages

In other projects