Koden

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 oktober 2021; kontroller kräver 4 redigeringar .

En kod  är en en-till-en-mappning av en ändligt ordnad uppsättning tecken som tillhör ett ändligt alfabet till ett annat, inte nödvändigtvis ordnat, vanligtvis mer omfattande teckenuppsättning för kodning av överföring , lagring eller omvandling av information .

Kodning är omvandlingen av data genom att etablera en entydig betydelse mellan element [1] som inte tillhör ett enda alfabet, med samma serienummer. Till exempel morsekod : i den kommer en sekvens av punkter och streck att motsvara vilket tecken som helst. Binär kod : kombinationer av dess nollor och ettor har också en ordning.

En sekvens av elementärt kodade symboler kallas vanligtvis ett kodmeddelande eller ett kodmeddelande . Ibland kallas en sekvens av kodade symboler av känd längd ett kodord eller kodram .

Kodning

Processen att konvertera ett meddelande till en kombination av tecken i enlighet med koden kallas kodning , processen att återställa ett meddelande från en kombination av tecken kallas avkodning .

Kodträd

Kodträd används för att visuellt beskriva koder . Om varje nivå innehåller noder, där l är nivånumret (trädets rot är på nivå noll), kallas det komplett . Uppenbarligen kännetecknar värdet , som kallas trädets volym , det maximala antalet kodkombinationer som kan byggas med detta träd.

I teorin om att konstruera översättare beskriver ett sådant träd uppsättningen av alla möjliga slutledningskedjor från en formell grammatik .

Prefixkod

En prefixkod är en kod som inte har ett enda kodord som skulle vara ett prefix (början) av något annat kodord i den givna koden. Varje prefixkod är separerbar (det vill säga vilken sekvens av kodord som helst kan alltid otvetydigt delas upp i separata) [2] . Exempel på prefixkoder är Shannon- , Shannon-Fano- och Huffmankoderna .

Exempel

Enhetlig kodning: för ett alfabet med m 1 tecken används kodord med längd , där uppåt  är avrundning uppåt till ett högre heltal. I det här fallet förblir kodorden oanvända , och resten tilldelas symbolerna i det primära alfabetet. Baudot-koden har en fast längd på 5 tecken.

Prefixkoder: Shannon-Fano-koden  är den första oenhetliga kodningsalgoritmen. Huffman-koden  är en välkänd metod för att konstruera en optimal icke-uniform kod (ONC) med användning av träd. Aritmetisk kodning  är en generalisering av Huffman-koden.

Se även

Anteckningar

  1. ↑ Sådana element är unika tecken, eller beteckningar som skiljer sig från varandra, i sammanhanget för ett givet alfabet.
  2. ↑ Gabidulin E. M. , Pilipchuk N. I. Föreläsningar om informationsteori - MIPT , 2007. - S. 43-49. — 214 sid. — ISBN 978-5-7417-0197-3

Litteratur