Præfiks kode - Prefix code

En præfiks-kode er en type kodesystem , der adskiller sig ved dets besiddelse af "præfiks-egenskaben", hvilket kræver, at der ikke er noget helt kodeord i systemet, der er et præfiks (indledende segment) af noget andet kodeord i systemet. Det er trivielt sandt for kode med fast længde, så kun et overvejelsespunkt i kode med variabel længde .

For eksempel har en kode med kodeord {9, 55} præfiksegenskaben; en kode bestående af {9, 5, 59, 55} ikke, fordi "5" er et præfiks for "59" og også af "55". En præfiks kode er en entydig dekodbar kode : givet en komplet og nøjagtig sekvens kan en modtager identificere hvert ord uden at kræve en særlig markør mellem ord. Der er dog unikt dekodbare koder, der ikke er præfiks koder; for eksempel er bagsiden af ​​en præfiks-kode stadig entydigt dekodbar (det er en suffiks-kode), men det er ikke nødvendigvis en præfiks-kode.

Præfiks koder er også kendt som præfiks-fri koder , præfiks betingelseskoder og øjeblikkelige koder . Selvom Huffman-kodning kun er en af ​​mange algoritmer til at udlede præfiks-koder, kaldes præfiks-koder også bredt som "Huffman-koder", selv når koden ikke blev produceret af en Huffman-algoritme. Udtrykket kommafri kode anvendes undertiden også som et synonym for præfiks-fri koder, men i de fleste matematiske bøger og artikler (f.eks.) Bruges en komma-fri kode til at betyde en selvsynkroniseringskode , en underklasse af præfiks-koder.

Ved hjælp af præfikskoder kan en meddelelse transmitteres som en sekvens af sammenkædede kodeord uden markører uden for båndet eller (alternativt) specielle markører mellem ord for at indramme ordene i meddelelsen. Modtageren kan afkode meddelelsen utvetydigt ved gentagne gange at finde og fjerne sekvenser, der danner gyldige kodeord. Dette er generelt ikke muligt med koder, der mangler præfiksegenskaben, for eksempel {0, 1, 10, 11}: en modtager, der læser et "1" i starten af ​​et kodeord, ved ikke, om det var det komplette kodeord " 1 "eller blot præfikset for kodeordet" 10 "eller" 11 "; så strengen "10" kunne fortolkes enten som et enkelt kodeord eller som sammenkædning af ordene "1" og derefter "0".

Huffman-koder med variabel længde, landekaldekoder , land- og udgiverdele af ISBN'er , de sekundære synkroniseringskoder, der bruges i UMTS W-CDMA 3G Wireless Standard, og instruktionssættene (maskinsprog) for de fleste computermikroarkitekturer er præfiks-koder.

Præfiks-koder er ikke fejlkorrektionskoder . I praksis kan en meddelelse først komprimeres med en præfiks-kode og derefter kodes igen med kanalkodning (inklusive fejlkorrektion) inden transmission.

For enhver entydig dekodbar kode er der en præfiks-kode, der har de samme kodeordlængder . Krafts ulighed karakteriserer de sæt kodeordlængder, der er mulige i en unik dekodbar kode.

Teknikker

Hvis hvert ord i koden har samme længde, kaldes koden en fastlængdekode eller en blokkode (selvom udtrykket blokkode også bruges til fejlkorrigeringskoder i fast størrelse i kanalkodning ). For eksempel er ISO 8859-15 bogstaver altid 8 bit lange. UTF-32 / UCS-4 bogstaver er altid 32 bit lange. ATM-celler er altid 424 bits (53 bytes) lange. En kode med fast længde på k- bit med fast længde kan kode op til kildesymboler. ${\ displaystyle 2 ^ {k}}$

En kode med fast længde er nødvendigvis en præfiks-kode. Det er muligt at omdanne en hvilken som helst kode til en kode med fast længde ved at polere faste symboler til de kortere præfikser for at imødekomme længden af ​​de længste præfikser. Alternativt kan sådanne polstringskoder anvendes til at indføre redundans, der muliggør autokorrektion og / eller synkronisering. Imidlertid er kodninger med fast længde ineffektive i situationer, hvor nogle ord er meget mere tilbøjelige til at blive transmitteret end andre.

Afkortet binær kodning er en ligetil generalisering af koder med fast længde til at håndtere tilfælde, hvor antallet af symboler n ikke er en styrke på to. Kildesymboler tildeles kodeord med længden k og k +1, hvor k vælges således, at 2 ^k <n ≤ 2 ^{k + 1} .

Huffman-kodning er en mere sofistikeret teknik til at konstruere præfiks-koder med variabel længde. Huffman-kodningsalgoritmen tager som input de frekvenser, som kodeordene skal have, og konstruerer en præfiks-kode, der minimerer det vægtede gennemsnit af kodeordets længder. (Dette er tæt knyttet til minimering af entropi.) Dette er en form for tabsfri datakomprimering baseret på entropikodning .

Nogle koder markerer slutningen af ​​et kodeord med et specielt "komma" symbol, der adskiller sig fra normale data. Dette er noget analogt med mellemrummet mellem ord i en sætning; de markerer, hvor et ord slutter, og et andet begynder. Hvis hvert kodeord ender i et komma, og kommaet ikke vises andetsteds i et kodeord, er koden automatisk præfiksfri. Imidlertid sender moderne kommunikationssystemer alt som sekvenser af "1" og "0" - det ville være dyrt at tilføje et tredje symbol, og det ville kun være ineffektivt at bruge det i enderne af ord. Morse-kode er et dagligdags eksempel på en kode med variabel længde med komma. De lange pauser mellem bogstaverne og de endnu længere pauser mellem ordene hjælper folk med at genkende, hvor et bogstav (eller ord) slutter, og det næste begynder. Tilsvarende bruger Fibonacci-kodning en "11" til at markere slutningen af ​​hvert kodeord.

Selvsynkroniseringskoder er præfiks-koder, der tillader rammesynkronisering .

Relaterede begreber

En suffikskode er et sæt ord, hvoraf ingen er et suffiks for nogen anden; ækvivalent et sæt ord, der er det modsatte af en præfiks-kode. Som med en præfiks kode er repræsentationen af ​​en streng som en sammenkædning af sådanne ord unik. En bifix-kode er et sæt ord, der både er et præfiks og en suffiks-kode. En optimal præfiks kode er en præfiks kode med minimal gennemsnitlig længde. Dvs. antage et alfabet af n symboler med sandsynligheder for en præfikskode C . Hvis C ' er en anden præfiks-kode og er længderne på kodeordene til C' , så . ${\ displaystyle p (A_ {i})}$${\ displaystyle \ lambda '_ {i}}$${\ displaystyle \ sum _ {i = 1} ^ {n} {\ lambda _ {i} p (A_ {i})} \ leq \ sum _ {i = 1} ^ {n} {\ lambda '_ { i} p (A_ {i})} \!}$

Præfiks koder, der er i brug i dag

Eksempler på præfiks koder inkluderer:

• Huffman-koder med variabel længde
• landekoder
• Chen – Ho-kodning
• landet og udgiverens dele af ISBN-numre
• de sekundære synkroniseringskoder, der bruges i UMTS W-CDMA 3G Wireless Standard
• VCR Plus + koder
• Unicode Transformation Format , især UTF-8- systemet til kodning af Unicode- tegn, som både er en præfiks-fri kode og en selvsynkroniseringskode
• mængde med variabel længde

Teknikker

Almindeligt anvendte teknikker til konstruktion af præfikskoder inkluderer Huffman-koder og de tidligere Shannon-Fano-koder og universelle koder såsom:

• Elias delta-kodning
• Elias gamma-kodning
• Elias omega kodning
• Fibonacci-kodning
• Levenshtein-kodning
• Unary kodning
• Golomb ris kode
• Straddling checkerboard (enkel kryptografiteknik, der producerer præfiks koder)
• Vbinær kodning

Bemærkninger

Referencer

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Koder og automater . Encyclopædi for matematik og dens anvendelser. 129 . Cambridge: Cambridge University Press . ISBN   978-0-521-88831-8 . Zbl   1187.94001 .
• Elias, Peter (1975). "Universal kodeordssæt og repræsentationer af heltalene". IEEE Trans. Inf. Teori . 21 (2): 194–203. doi : 10.1109 / tit.1975.1055349 . ISSN   0018-9448 . Zbl   0298.94011 .
• DA Huffman, "En metode til konstruktion af minimum-redundanskoder", Proceedings of the IRE, september 1952, s. 1098-1102 (Huffmans originale artikel)
• Profil: David A. Huffman , Scientific American , september 1991, s. 54-58 (Baggrundshistorie)
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest og Clifford Stein . Introduktion til algoritmer , anden udgave. MIT Press og McGraw-Hill, 2001. ISBN   0-262-03293-7 . Afsnit 16.3, s. 385–392.
•  Denne artikel indeholder  materiale fra det offentlige domæne fra dokumentet General Services Administration : "Federal Standard 1037C" .

eksterne links

• Koder, træer og præfiks ejendommen af Kona Macphee