Levenshtein kode

Levenshtein-koden  er en universel kode , der giver dig mulighed for at kode ikke-negative heltal . Det blev opfundet af Vladimir Levenshtein .

Nulkode er " 0  "; for at indkode et positivt tal, bruges følgende algoritme:

  1. Initialiser trintælleren C = 1, K  er nummerets kode (indledningsvis tom).
  2. Skriv den binære kode for det kodede tal uden det "højeste" 1 (skriv f.eks. tallet 1100 som 100; tallet 100 som 00).
  3. Tilføj modtaget til begyndelsen K .
  4. Lad M  være antallet af bit skrevet i andet trin. Konverter M til binær.
  5. Hvis M ikke er tom, så er C = C + 1, og gentag algoritmen fra trin 2 for den resulterende M. Ellers gå til trin 6.
  6. Skriv C stykker af enheder og 0 i begyndelsen af ​​K -koden (for eksempel hvis tælleren C \u003d 2, K \u003d 0 011, får: 110 0 011) - Levenshtein-koden.

Levenshtein-koden for de første 24 numre ville se sådan ud:

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

Lad K være  en Levenshtein-kode. For at dekryptere Levenshtein-koden skal du:

  1. Tæl tallet Fra 1 bit til den første nulbit.
  2. Hvis C = 0, så er den kodede værdi 0 . Hvis ikke, gå til trin 3.
  3. Kassér disse C - enheder og de følgende 0 fra K. Skriv den nye værdi af K ned.
  4. Indstil variablen N = 1. Indtast trintælleren P = C  - 1.
  5. Hvis P = 0, så er N  det ønskede tal. Hvis ikke, gå til trin 6.
  6. Læs de første N bits fra K. Skriv en ny værdi til K uden at læse N bit.
  7. Tilføj 1 til begyndelsen af ​​den læste post (for eksempel læst 00, modtaget: 100).
  8. Konverter den modtagne værdi til decimalsystemet (eller originalen, hvis den er kendt) - den nye værdi af variablen N .
  9. P = P  - 1. Gentag fra trin 5.

I Levenshtein-kodning er et positivt tal altid 1 bit mere end i omega Elias-kodning . Nul kan dog kodes af Levenshtein-kode, mens det med Elias omega-kodning er nødvendigt at omdesigne alle cifre på en sådan måde, at nul repræsenteres af én.


Links

Kilde