Levenshtein kod
Levenshtein-koden är en universell kod som låter dig koda icke-negativa heltal . Det myntades av Vladimir Levenshtein .
Nollkod är "0"; för att koda ett positivt tal används följande algoritm:
- Initiera stegräknaren C = 1, K är koden för numret (inledningsvis tom).
- Skriv den binära koden för det kodade numret utan den "högsta" 1:an (skriv till exempel talet 1100 som 100; talet 100 som 00).
- Lägg till mottaget till början K .
- Låt M vara antalet bitar som skrivs i det andra steget. Konvertera M till binär.
- Om M inte är tomt, då C = C + 1, och upprepa algoritmen från steg 2 för den resulterande M. Annars går du till steg 6.
- Skriv C bitar av enheter och 0 i början av K -koden (till exempel om räknaren C \u003d 2, K \u003d 0 011, få: 110 0 011) - Levenshtein-koden.
Levenshtein-koden för de första 24 siffrorna skulle se ut så här:
0 0
1 10
2 110 0
3 110 1
4 1110 0 00
5 1110 0 01
6 1110 0 10
7 1110 0 11
8 1110 1000
9 1110 1001
10 1110 1 010
11 1110 1 011
12 1110 1 100
13 1110 1 101
14 1110 1 110
15 1110 1 111
16 11110 0 00 0000
17 11110 0 00 0001
18 11110 0 00 0010
19 11110 0 00 0011
20 11110 0 00 0100
21 11110 0 00 0101
22 11110 0 00 0110
23 11110 0 00 0111
24 11110 0 00 1000
Låt K vara en Levenshtein-kod. För att dekryptera Levenshtein-koden måste du:
- Räkna antalet Från 1 bitar till den första nollbiten.
- Om C = 0 är det kodade värdet 0 . Om inte, gå till steg 3.
- Kassera från K dessa C -enheter och följande 0 . Skriv ner det nya värdet på K.
- Ställ in variabeln N = 1. Ange stegräknaren P = C - 1.
- Om P = 0, så är N det önskade talet. Om inte, gå till steg 6.
- Läs de första N bitarna från K. Skriv ett nytt värde till K utan att läsa N bitar.
- Lägg till 1 i början av läsposten (till exempel läs 00, mottagen: 100).
- Konvertera det mottagna värdet till decimalsystemet (eller originalet, om känt) - det nya värdet på variabeln N .
- P = P - 1. Upprepa från steg 5.
I Levenshtein-kodning är ett positivt tal alltid 1 bit mer än i omega Elias-kodning . Noll kan dock kodas av Levenshtein-kod, medan med Elias omega-kodning är det nödvändigt att omdesigna alla siffror på ett sådant sätt att noll representeras av en.
Länkar
Källa