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:

  1. Initiera stegräknaren C = 1, K  är koden för numret (inledningsvis tom).
  2. 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).
  3. Lägg till mottaget till början K .
  4. Låt M  vara antalet bitar som skrivs i det andra steget. Konvertera M till binär.
  5. 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.
  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:

  1. Räkna antalet Från 1 bitar till den första nollbiten.
  2. Om C = 0 är det kodade värdet 0 . Om inte, gå till steg 3.
  3. Kassera från K dessa C -enheter och följande 0 . Skriv ner det nya värdet på K.
  4. Ställ in variabeln N = 1. Ange stegräknaren P = C  - 1.
  5. Om P = 0, så är N  det önskade talet. Om inte, gå till steg 6.
  6. Läs de första N bitarna från K. Skriv ett nytt värde till K utan att läsa N bitar.
  7. Lägg till 1 i början av läsposten (till exempel läs 00, mottagen: 100).
  8. Konvertera det mottagna värdet till decimalsystemet (eller originalet, om känt) - det nya värdet på variabeln N .
  9. 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