Kod prefiksowy

Ten artykuł od 2021-02 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Kod prefiksowy lub przedrostkowy (ang. prefix code) – kod, w którym żadne ze słów kodowych nie jest przedrostkiem innego słowa; taki kod jest jednoznacznie dekodowalny. Dodatkowo każdy kod prefiksowy można reprezentować w formie drzewa (dla kodów dwójkowych to drzewo binarne).

Dzięki tej cesze kody są jednoznacznie identyfikowane, nie ma potrzeby wstawiania dodatkowych informacji np. o tym, gdzie kończy się słowo kodowe (jest to jednoznaczne) albo jaką ma długość (długość każdego słowa kodowego jest znana z góry). Stosując kody prefiksowe, można uzyskać maksymalny stopień upakowania danych w różnych metodach kompresji.

Dla przykładu weźmy kod niebędący prefiksowym: literze „a” odpowiada bit 0, literze „b” odpowiada bit 1, zaś literze „c” dwa bity 01 – kod litery „a” jest prefiksem kodu litery „c”. Przy takim przyporządkowaniu nie można jednoznacznie stwierdzić, co oznacza np. komunikat 0110 – może to być zarówno „cba”, jak i „abba”.

Zmieniając kod na prefiksowy: „a” – 0, „b” – 10, „c” – 11, ten sam komunikat ma jednoznaczną interpretację, tj. „aca”.

Zobacz też