Kesilmiş ikili kodlama - Truncated binary encoding

Kesilmiş ikili kodlama , tipik olarak sonlu bir alfabe ile tek tip olasılık dağılımları için kullanılan bir entropi kodlamasıdır . Toplam boyutu n olan bir alfabe ile parametrelendirilir . Bu biraz daha fazla genel formudur ikili kodlama zaman , n , bir değil iki gücü .

Eğer n, daha sonra iki güç ≤ 0 kodlanmış değer x < n için basit bir ikili kod x uzunluk log 2 ( n ). Aksi halde 2 k < n < 2 k +1 olacak şekilde k = kat( log 2 ( n ) ) ve u = 2 k +1 - n olsun .

İkili kodlama atar ilk kesildi u uzunluğu sembolleri kod sözcüklerini k ve atar kalan N - u semboller geçen N - u kod kelimeleri uzunluğu k + 1 uzunluğunun her kod sözcükleri için k + 1 uzunluğunun bir atanmamış kod sözcüğü oluşur k "0" veya "1" eklendiğinde ortaya çıkan kod bir önek kodudur .

n = 5 ile örnek

Örneğin, {0, 1, 2, 3, 4} alfabesi için, n = 5 ve 2 2 ≤ n < 2 3 , dolayısıyla k = 2 ve u = 2 3 - 5 = 3. Kesik ikili kodlama ilkini atar. u tüm uzunlukları 2 olan 00, 01 ve 10 kod sözcüklerini sembolize eder, ardından son n - u simgelerini 110 ve 111 kod sözcüklerini, uzunluğu 3 olan son iki kod sözcüklerini atar .

Örneğin, n 5 ise, düz ikili kodlama ve kesik ikili kodlama aşağıdaki kod sözcüklerini tahsis eder . Gösterilen rakamlarvurdu kesilmiş ikili dosyada iletilmez.

Kesilmiş
ikili		 kodlama standart
ikili
0 0 0 0 0
1 0 0 1 1
2 0 1 0 2
KULLANILMAMIŞ 0 1 1 3
KULLANILMAMIŞ 1 0 0 4
KULLANILMAMIŞ 1 0 1 5/kullanılmamış
3 1 1 0 6/kullanılmamış
4 1 1 1 7/ KULLANILMAMIŞ

Basit ikili kodlama kullanarak n'yi kodlamak 3 bit alır , bu nedenle 2 3 - n = 8 - 5 = 3 kullanılmaz.

Sayısal olarak, 0 ≤ x < n ve 2 k ≤ n < 2 k +1 sembolün olduğu bir x değeri göndermek için , alfabe boyutu yukarı yuvarlandığında u = 2 k + 1 − n kullanılmayan girişler vardır. ikinin en yakın kuvvetine. x sayısını kırpılmış ikili olarak kodlama işlemi şöyledir: x , u'dan küçükse , onu k ikili bit olarak kodlayın . Eğer X daha büyüktür ya da eşit u değeri kodlayan x + u içinde k + 1 ikili bitler.

n = 10 ile örnek

Başka bir örnek, 10 boyutunda (0 ile 9 arasında) bir alfabeyi kodlamak için 4 bit gerekir, ancak 2 4 − 10 = 6 kullanılmayan kod vardır, bu nedenle 6'dan küçük giriş değerleri ilk biti atılırken, giriş değerleri bundan büyük veya ona eşitken 6'ya kadar, ikili alanın sonuna 6 ile kaydırılır. (Kullanılmayan desenler bu tabloda gösterilmemiştir.)

Giriş
değeri		 Ofset Ofset
değeri		 Standart
İkili		 Kesilmiş
İkili
0 0 0 0000 000
1 0 1 0001 001
2 0 2 0010 010
3 0 3 0011 011
4 0 4 0100 100
5 0 5 0101 101
6 6 12 0110 1100
7 6 13 0111 1101
8 6 14 1000 1110
9 6 15 1001 1111

Kodu çözmek için ilk k biti okuyun . u değerinden daha küçük bir değeri kodlarlarsa , kod çözme tamamlanır. Aksi takdirde, ek bir bit okuyun ve sonuçtan u çıkarın.

n = 7 ile örnek

İşte daha uç bir durum: n = 7 ile 2'nin bir sonraki kuvveti 8'dir, yani k = 2 ve u = 2 3 - 7 = 1:

Giriş
değeri		 Ofset Ofset
değeri		 Standart
İkili		 Kesilmiş
İkili
0 0 0 000 00
1 1 2 001 010
2 1 3 010 011
3 1 4 011 100
4 1 5 100 101
5 1 6 101 110
6 1 7 110 111

Bu son örnek, baştaki sıfır bitinin her zaman bir kısa kodu göstermediğini gösterir; eğer u <2 k , bazı uzun kodlar sıfır bit ile başlayacak.

Basit algoritma

x , 0 <= x < n değeri için kesilmiş ikili kodlamayı oluşturun; burada n > 0, x içeren alfabenin boyutudur . n'nin ikinin kuvveti olması gerekmez. 

string TruncatedBinary (int x, int n)
{
	// Set k = floor(log2(n)), i.e., k such that 2^k <= n < 2^(k+1).
	int k = 0, t = n;
	while (t > 1) { k++;  t >>= 1; }

	// Set u to the number of unused codewords = 2^(k+1) - n.
	int u = (1 << k+1) - n;

	if (x < u)  return Binary(x, k); 
        else  return Binary(x+u, k+1));
}

Rutin İkili açıklayıcıdır; genellikle x değişkeninin en sağdaki len bitleri istenir. Burada, x için ikili kodun çıktısını len bitlerini kullanarak , gerekirse yüksek dereceli 0'larla doldururuz . 

string Binary (int x, int len)
{
	string s = "";
	while (x != 0) {
		if (even(x))  s = '0' + s;
		else  s = '1' + s;
		x >>= 1;
	}
	while (s.Length < len)  s = '0' + s;
	return s;
}

verimlilik hakkında

Eğer , n iki güç değildir ve k bit sembollerin olasılığı ile gözlenir p , k + 1 bit sembollerin olasılık ile gözlenir 1 - p . Sembol başına beklenen bit sayısını şu şekilde hesaplayabiliriz :

.

Sembolün ham kodlaması bitlerdir. Ardından , kodlamanın göreli alan tasarrufu s (bkz. Data_compression_ratio ) şu şekilde tanımlanabilir:

.

Basitleştirildiğinde, bu ifade şuna yol açar:

.

Bu , k bitlik simgelerin olasılığı p arttıkça ve simge başına ham kodlama bitleri azaldıkça , kırpılmış ikili kodlamanın göreli etkinliğinin arttığını gösterir .

Ayrıca bakınız