Ön ek kodu - Prefix code

Bir önek kodu , sistemde , sistemdeki herhangi bir başka kod sözcüğünün bir öneki (başlangıç ​​bölümü) olan tam bir kod sözcüğü olmamasını gerektiren, "ön ek özelliği" ne sahip olmasıyla ayırt edilen bir kod sistemi türüdür . Sabit uzunluklu kod için önemsiz bir şekilde doğrudur, bu nedenle değişken uzunluklu kodda sadece dikkate alınması gereken bir noktadır .

Örneğin, {9, 55} kod sözcüklerine sahip bir kod önek özelliğine sahiptir; {9, 5, 59, 55} içeren bir kod, "5", "59" ve ayrıca "55" önekidir. Bir önek kodu, benzersiz bir şekilde kodu çözülebilir bir koddur : tam ve doğru bir sıra verildiğinde, bir alıcı, kelimeler arasında özel bir işaretleyici gerektirmeden her kelimeyi tanımlayabilir. Bununla birlikte, önek kodları olmayan benzersiz bir şekilde kodu çözülebilir kodlar vardır; örneğin, bir ön ek kodunun tersi hala benzersiz bir şekilde kodu çözülebilir (bu bir son ek kodudur), ancak mutlaka bir önek kodu değildir.

Ön kodlar, önek içermeyen kodlar , ön ek koşul kodları ve anlık kodlar olarak da bilinir . Huffman kodlaması , önek kodlarının türetilmesi için birçok algoritmadan sadece biri olmasına rağmen , kod bir Huffman algoritması tarafından üretilmediğinde bile, önek kodlarına yaygın olarak "Huffman kodları" olarak da atıfta bulunulmaktadır. Terimi virgül içermeyen kod bazen de önek içermeyen kodları ile eşanlamlı olarak uygulanır ama çoğu matematiksel kitap ve makalelerin (örneğin) bir virgülle serbest kod anlamında kullanılır kendi kendine senkronize kodu , önek kodlarının bir alt sınıfını.

Önek kodlarını kullanarak, bir mesaj, mesajdaki kelimeleri çerçevelemek için herhangi bir bant dışı işaret veya (alternatif olarak) kelimeler arasında özel işaretler olmaksızın, birleştirilmiş kod kelimeleri dizisi olarak iletilebilir . Alıcı, geçerli kod sözcüklerini oluşturan dizileri tekrar tekrar bularak ve çıkararak mesajın kodunu açık bir şekilde çözebilir. Bu, önek özelliğinden yoksun kodlarda genellikle mümkün değildir, örneğin {0, 1, 10, 11}: Bir kod sözcüğünün başında "1" okuyan bir alıcı, bunun tam kod sözcüğü olup olmadığını bilemez " 1 "veya yalnızca" 10 "veya" 11 "kod sözcüğünün ön eki; bu nedenle "10" dizisi tek bir kod sözcüğü olarak veya "1" ardından "0" sözcüklerinin birleştirilmiş hali olarak yorumlanabilir.

Değişken uzunluklu Huffman kodları , ülke arama kodları , ISBN'lerin ülke ve yayıncı bölümleri , UMTS W-CDMA 3G Kablosuz Standardında kullanılan İkincil Eşitleme Kodları ve çoğu bilgisayar mikro mimarisinin komut setleri (makine dili) önek kodlarıdır.

Ön kodlar, hata düzeltme kodları değildir . Uygulamada, bir mesaj ilk olarak bir önek koduyla sıkıştırılabilir ve daha sonra iletimden önce kanal kodlamasıyla (hata düzeltme dahil) tekrar kodlanabilir .

Benzersiz olarak kodu çözülebilen herhangi bir kod için, aynı kod kelime uzunluklarına sahip bir ön ek kodu vardır. Kraft'ın eşitsizliği , benzersiz bir şekilde kodu çözülebilir bir kodda mümkün olan kod kelime uzunluğu kümelerini karakterize eder .

Teknikler

Kodu her kelime aynı uzunluğa sahip, kod bir adlandırılır sabit uzunluklu kod ya da bir blok kodu (bu terim yine de blok kodu da sabit boyutlu için kullanılan hata düzeltme kodları olarak kanal kodlama ). Örneğin, ISO 8859-15 harfleri her zaman 8 bit uzunluğundadır. UTF-32 / UCS-4 harfleri her zaman 32 bit uzunluğundadır. ATM hücreleri her zaman 424 bit (53 bayt) uzunluğundadır. Sabit uzunluktaki k bitlerinin sabit uzunluklu bir kodu, kaynak sembollerine kadar kodlayabilir . ${\ displaystyle 2 ^ {k}}$

Sabit uzunluklu bir kod, zorunlu olarak bir önek kodudur. En uzun öneklerin uzunluğunu karşılamak için sabit sembolleri daha kısa öneklere doldurarak herhangi bir kodu sabit uzunlukta bir koda dönüştürmek mümkündür. Alternatif olarak, bu tür doldurma kodları, otomatik düzeltme ve / veya senkronizasyona izin veren artıklık sağlamak için kullanılabilir. Bununla birlikte, sabit uzunluktaki kodlamalar, bazı kelimelerin diğerlerine göre iletilme olasılığının çok daha yüksek olduğu durumlarda verimsizdir.

Kesilmiş ikili kodlama , n simge sayısının ikinin üssü olmadığı durumlarla başa çıkmak için sabit uzunlukta kodların basit bir genellemesidir . Kaynak sembollerine k ve k +1 uzunluğunda kod sözcükleri atanır , burada k , 2 ^k <n ≤ 2 ^{k + 1} olacak şekilde seçilir .

Huffman kodlaması , değişken uzunluklu önek kodları oluşturmak için daha karmaşık bir tekniktir. Huffman kodlama algoritması, kod kelimelerinin sahip olması gereken frekansları girdi olarak alır ve kod kelime uzunluklarının ağırlıklı ortalamasını en aza indiren bir önek kodu oluşturur. (Bu, entropiyi en aza indirmekle yakından ilgilidir.) Bu, entropi kodlamasına dayalı kayıpsız bir veri sıkıştırma biçimidir .

Bazı kodlar, bir kod sözcüğünün sonunu normal verilerden farklı olarak özel bir "virgül" simgesiyle işaretler. Bu, bir cümledeki sözcükler arasındaki boşluklara biraz benzer; bir kelimenin bittiği ve diğerinin başladığı yeri işaretlerler. Her kod sözcüğü virgülle bitiyorsa ve virgül bir kod sözcüğünde başka bir yerde görünmüyorsa, kod otomatik olarak öneksizdir. Bununla birlikte, modern iletişim sistemleri her şeyi "1" ve "0" dizileri olarak gönderir - üçüncü bir sembol eklemek pahalı olur ve onu yalnızca kelimelerin sonunda kullanmak verimsiz olur. Mors kodu , virgül içeren değişken uzunluklu bir kodun günlük bir örneğidir. Harfler arasındaki uzun duraklamalar ve kelimeler arasındaki daha da uzun duraklamalar, insanların bir harfin (veya kelimenin) nerede bittiğini ve diğerinin nerede başladığını anlamasına yardımcı olur. Benzer şekilde, Fibonacci kodlaması her kod sözcüğünün sonunu işaretlemek için bir "11" kullanır.

Kendi kendini senkronize eden kodlar , çerçeve senkronizasyonuna izin veren önek kodlarıdır .

Ilgili kavramlar

Son ek kodu , hiçbiri diğerinin son eki olmayan bir dizi sözcüktür; eşdeğer olarak, bir önek kodunun tersi olan bir dizi sözcük. Bir önek kodunda olduğu gibi, bir dizenin bu tür kelimelerin bir birleşimi olarak temsili benzersizdir. Bir BIFIX kodu , bir ön ek ve bir sonek kodu hem de kelime kümesidir. En uygun önek kodu , minimum ortalama uzunluğa sahip bir önek kodudur. Yani, bir ön ek kodu C için olasılıklara sahip n sembollü bir alfabe varsayalım . Eğer C ' bir çağrı kodu ve kod kelimeler ile uzunlukları olan C' , daha sonra . ${\ displaystyle p (A_ {i})}$${\ displaystyle \ lambda '_ {i}}$${\ displaystyle \ toplamı _ {i = 1} ^ {n} {\ lambda _ {i} p (A_ {i})} \ leq \ toplamı _ {i = 1} ^ {n} {\ lambda '_ { i} p (A_ {i})} \!}$

Bugün kullanımda olan ön kodlar

Önek kodlarının örnekleri şunları içerir:

• değişken uzunluklu Huffman kodları
• ülke arama kodları
• Chen – Ho kodlaması
• ISBN'lerin ülke ve yayıncı bölümleri
• UMTS W-CDMA 3G Kablosuz Standardında kullanılan İkincil Senkronizasyon Kodları
• VCR Plus + kodları
• Unicode Dönüşüm Formatı , özellikle hem önek içermeyen bir kod hem de kendi kendini senkronize eden bir kod olan Unicode karakterleri kodlamak için UTF-8 sistemi
• değişken uzunluklu miktar

Teknikler

Önek kodları oluşturmak için en sık kullanılan teknikler şunlardır Huffman kodları ve önceki Shannon-Fano kodları ve evrensel kodları gibi:

• Elias delta kodlama
• Elias gama kodlama
• Elias omega kodlama
• Fibonacci kodlaması
• Levenshtein kodlaması
• Tekli kodlama
• Golomb Pirinç kodu
• Straddling dama tahtası (önek kodları üreten basit şifreleme tekniği)
• Vbinary kodlama

Notlar

Referanslar

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Kodlar ve otomatlar . Matematik Ansiklopedisi ve Uygulamaları. 129 . Cambridge: Cambridge University Press . ISBN   978-0-521-88831-8 . Zbl   1187.94001 .
• Elias Peter (1975). "Evrensel kod sözcük kümeleri ve tamsayıların gösterimleri". IEEE Trans. Inf. Teori . 21 (2): 194–203. doi : 10.1109 / tit.1975.1055349 . ISSN   0018-9448 . Zbl   0298.94011 .
• DA Huffman, "Minimum fazlalık kodlarının oluşturulması için bir yöntem", IRE Bildirileri, Eylül 1952, s. 1098-1102 (Huffman'ın orijinal makalesi)
• Profil: David A. Huffman , Scientific American , Eylül 1991, s. 54–58 (Arka plan öyküsü)
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest ve Clifford Stein . Algoritmalara Giriş , İkinci Baskı. MIT Press ve McGraw-Hill, 2001. ISBN   0-262-03293-7 . Bölüm 16.3, sayfa 385–392.
•  Bu makale  , Genel Hizmetler Yönetimi belgesindeki kamu malı materyalleri içerir : "Federal Standart 1037C" .

Dış bağlantılar

• Kodlar, ağaçlar ve Kona Macphee'nin önek özelliği