En prefikskode er en kode , vanligvis en kode med variabel lengde , med "prefiksegenskapen": ingen kodeord er et prefiks til noe annet kodeord i settet. En tag med kodeordene {0, 10, 11} har prefiksegenskapen; en kode {0, 1, 10, 11} har det ikke, fordi "1" prefikser både "10" og "11".
Prefikskoder er også kjent som ingen prefikskoder og øyeblikkelige koder . Selv om Huffman-koding bare er en av mange algoritmer for å få prefikskoder, kalles prefikskoder også Huffman-koder , selv når koden ikke ble generert med en Huffman-algoritme.
Ved å bruke prefikskoder kan en melding overføres som en sekvens av sammenkoblede kodeord, uten noe utenfor båndet signal for å skille ordene i meldingen. Mottakeren kan entydig dekode meldingen ved gjentatte ganger å finne og fjerne prefiksene som danner et gyldig kodeord. Dette er ikke mulig med koder som ikke har prefiksegenskapen, som i eksemplet med {0, 1, 10, 11}: en mottaker som leser en "1" i begynnelsen av et kodeord vil ikke vite om dette er komplett kodeord "1" eller hvis det bare er kodeordprefikset "10" eller "11".
Huffman-kodene med variabel lengde , internasjonale telefonkoder , lands- og utgiverdeler av ISBN og sekundære tidskoder som brukes i den trådløse 3G UMTS W -CDMA -standarden er prefikskoder. Prefikskoder er også en form for entropikoding som brukes i tapsfri datakomprimering .
Prefikskoder er ikke feilkorrigerende koder . I praksis kan en melding først komprimeres med en prefikskode, og deretter krypteres på nytt (med feilrettingskode) før overføring.
Teknikkene for å bygge en prefikskode kan være enkle, eller ganske kompliserte.
Hvis hvert ord i koden har samme lengde, kalles koden en kode med fast lengde . For eksempel er ISO 8859-15 bokstaver alltid 8 biter lange. UTF-32/UCS-4 bokstaver er alltid 32 biter lange. ATM-pakker er alltid 424 biter lange. Prefikser kan ikke eksistere i en kode med fast lengde. Dessverre er koding med fast lengde ineffektiv i situasjoner der noen ord er mye mer sannsynlig å bli overført enn andre.
Noen koder med variabel lengde markerer slutten på et kodeord med et spesielt symbol. Dette er litt analogt med punktum på slutten av en setning; markerer hvor en setning slutter og den neste begynner. Hvis hvert kodeord ender på et spesialsymbol, og spesialsymbolet ikke vises i kodeordet, er det en kode uten prefiks. Imidlertid sender moderne kommunikasjonssystemer alt som sekvenser av "0" og "1" - å legge til et tredje symbol ville være dyrt, og å bruke det bare på slutten av ord ville være ineffektivt. Morsekode er et hverdagslig eksempel på en kode med variabel lengde med et spesielt symbol. Lange pauser mellom bokstaver, og enda lengre pauser mellom ord, hjelper folk å gjenkjenne hvor en bokstav (eller ord) slutter, og den neste begynner.
Huffman - koding er en mer sofistikert teknikk for å bygge prefikskoder med variabel lengde. Huffman-kodealgoritmen tar som input frekvensene som kodeordene skal ha, og konstruerer en prefikskode som minimerer den vektede gjennomsnittslengden til kodeordene.
Krafts ulikhet karakteriserer settene med kodeordlengder som er mulige i en prefikskode.
UTF-8- systemet for koding av Unicode - tegn med mellom én og fire byte per tegn kan sees på som en form for prefikskoding, det samme kan VCR Plus+-kodene og telefonlandskodesystemet for internasjonal telefoni.
Vanlige brukte teknikker for å konstruere prefikskoder inkluderer Shannon–Fano- koding , Huffman-koding og universelle koder med Elias delta-koding, Elias gamma- koding, Elias omega - koding , Fibonacci-koding og Levenshtein-koding .