Etuliitekoodi

Etuliitekoodi koodausteoriassa  on koodi , jossa on muuttuvapituinen sana, jolla on seuraava ominaisuus ( Fanon ehdon täyttyminen ): jos koodi sisältää sanan a , niin mille tahansa ei-tyhjälle merkkijonolle b , sana ab ei olemassa koodissa. Vaikka etuliitekoodi koostuu eripituisista sanoista, nämä sanat voidaan kirjoittaa ilman erotusmerkkiä.

Esimerkiksi koodi, joka koostuu sanoista 0, 10 ja 11, on etuliite, ja viesti 01001101110 voidaan jakaa sanoiksi ainutlaatuisella tavalla:

0 10 0 11 0 11 10

Koodi, joka koostuu sanoista 0, 10, 11 ja 100, ei ole etuliite, ja sama viesti voidaan tulkita monella tavalla.

0 10 0 11 0 11 10 0 100 11 0 11 10

Määritelmä

Ns. "etuliitteet" voidaan saada hylkäämällä peräkkäin koodiyhdistelmän viimeinen merkki. Esimerkiksi koodiyhdistelmässä 11101101 etuliitteet ovat 11101101, 1110110, 111011, 11101, 1110, 111, 11, 1.

Joko näin:

Kirjoitamme kaikki koodiyhdistelmät ilman etunollia: 0 //etuliite //yksi //10 <- kommentoi (sulje pois) niitä, jotka ovat muiden alkua //yksitoista 100 //etuliite 101 //kommentoimatonta koodia - etuliitekoodin etuliitteet. 110 111 ... //olkoon se kaikki kolmibittiset yhdistelmät.

Tuloksena oleva koodisekvenssi (0, 100, 101, 110, 111) vastaa etuliitettä Huffman-koodisekvenssi .

Jos koodiyhdistelmien välissä ei ole välilyöntejä tai muita välimerkkejä, niin yhdistelmän 111011101 yksiselitteistä dekoodausta varten mikään koodiyhdistelmistä ei voi olla esitetty luetelluilla vaihtoehdoilla (etuliitteillä). Koodia kutsutaan etuliitteeksi, jos mikään sen yhdistelmistä ei ole saman koodin toisen yhdistelmän etuliite. Sitä koodiyhdistelmän osaa, joka täydentää itse yhdistelmän etuliitettä, kutsutaan jälkiliitteeksi. Etuliitekoodit voidaan esittää visuaalisesti koodipuiden avulla. Jos mikään koodipuun solmu ei ole annetun koodin solmu, sillä on etuliitteen ominaisuudet. Puun solmuja, jotka eivät liity muihin, kutsutaan lehtisolmuiksi. Niitä vastaavat yhdistelmät ovat etuliitekoodiyhdistelmiä.

Esimerkkejä

Mikä tahansa kiinteäpituinen sanakoodi on ilmeisesti etuliitekoodi. Tarkastellaanpa joitain ei-triviaaleja esimerkkejä.

• Puhelinnumerot kiinteässä verkossa.
• UTF-8 .
• Huffman - koodia käytetään tietojen pakkaamiseen .
• Pascalin ja muiden kielten syntaksi LL(1) -syntaksilla (olettaen, että lekseemi on symboli ja operaattori on sana ). Siksi Pascal-kääntäjän ei tarvitse palauttaa luettuja merkkejä streamiin tai tallentaa niitä pinoon määrittääkseen operaattorin tyypin .

Morsekoodi ei ole etuliite. Pisteen ja viivan lisäksi se sisältää myös erotinmerkin - viivan pituisen tauon .

Katso myös

• Kraft-McMillan epätasa-arvo