Truncated binary encoding

קידוד בינארי מקוצר (Truncated binary encoding) הוא שיטה לקידוד אנטרופיה, המשמשת בדרך כלל להתפלגויות הסתברות אחידות עם אלפבית סופי. הוא מאופיין על ידי אלפבית מסוים שגודלו הכולל הוא מספר n. הוא נחשב לצורה קלושה יותר כללית של קידוד בינארי כאשר n אינו חזקת שניים.

אם n הוא חזקת שניים, אז הערך המקודד עבור 0 ≤ x < n הוא הקוד הבינארי הפשוט עבור x באורך log₂(n). אחרת, נסמן k = floor(log₂(n)), כך ש-2^k < n < 2^k+1 ונגדיר u = 2^k+1 − n.

קידוד בינארי מקוצר משייך ל-u סימנים הראשונים קודי מילות באורך k ואז משייך את n − u הסימנים הנותרים ל-n − u קודי המילות האחרונים באורך k + 1. מכיוון שכל קודי המילות באורך k + 1 מורכבים מקוד מילה לא משויך באורך k עם "0" או "1" מוספים, הקוד הנוצר הוא קוד קידום.

היסטוריה

משמש מאז לפחות 1984, קודי פייז-אין, הידועים גם כ-קודי כלכלה, נקראים גם קידוד בינארי מקוצר.

דוגמה עם n = 5

לדוגמה, עבור האלפבית {0, 1, 2, 3, 4}, n = 5 ו-2² ≤ n < 2³, לכן k = 2 ו-u = 2³ − 5 = 3. קידוד בינארי מקוצר משייך ל-u סימנים ראשונים קודי מילות באורך 2, 00, 01, ו-10, ואז משייך ל-n − u סימנים אחרונים קודי מילות באורך 3, 110 ו-111.

במונחים מספריים, כדי לשלוח ערך x, כאשר 0 ≤ x < n, ויש 2^k ≤ n < 2^k+1 סימנים, יש u = 2^k+1 − n הכנסות לא משומשות כאשר גודל האלפבית מעוגל לחזקת השניים הקרובה ביותר. התהליך לקודד את המספר x בבינארי מקוצר הוא: אם x קטן מ-u, קודד אותו ב-k סיביות בינאריות; אם x גדול או שווה ל-u, קודד את הערך x + u ב-k + 1 סיביות בינאריות.

דוגמה עם n = 10

דוגמה נוספת, קידוד של אלפבית בגודל 10 (בין 0 ל-9) דורש 4 סיביות, אך יש 2⁴ − 10 = 6 קודים שאינם בשימוש, לכן ערכי קלט קטנים מ-6 מסירים את הסיבית הראשונה, בעוד שערכי קלט גדולים או שווים ל-6 מוסטים ב-6 לסוף המרחב הבינארי. (דפוסים שאינם בשימוש אינם מוצגים בטבלה זו.)

ערך קלט	הסט	ערך הסט	בינארי סטנדרטי	בינארי מקוצר
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

כדי לפענח, קרא את ה-k סיביות הראשונות. אם הן מקודדות ערך קטן מ-u, הפענוח הסתיים. אחרת, קרא סיבית נוספת והורד את u מהתוצאה.

דוגמה עם n = 7

כאן מקרה יותר קיצוני: עם n = 7 החזקה הבאה של 2 היא 8, לכן k = 2 ו-u = 2³ − 7 = 1:

ערך קלט	הסט	ערך הסט	בינארי סטנדרטי	בינארי מקוצר
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

דוגמה זו האחרונה מדגימה שסיבית בינארית מובילה אינה מצביעה תמיד על קוד קצר; אם u < 2^k, קודים ארוכים מסוימים יתחילו בסיבית 0.

אלגוריתם פשוט

יצר את הקידוד הבינארי המקוצר עבור ערך x, 0 ≤ x < n, כאשר n > 0 הוא גודל האלפבית שמכיל את x. n אינו חייב להיות חזקת שניים.

string TruncatedBinary (int x, int n)
{
	// הגדר את k = floor(log2(n)), כלומר, k כך ש-2^k <= n < 2^(k+1).
	int k = 0, t = n;
	while (t > 1) { k++;  t >>= 1; }

	// הגדר את u למספר קודי המילות שאינם בשימוש = 2^(k+1) - n.
	int u = (1 << k + 1) - n;

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

רוטינת ה-Binary היא הסברית; בדרך כלל רק ה-len סיביות ימניות ביותר של המשתנה x רצויות. כאן אנו פשוט מפיקים את הקוד הבינארי עבור x באמצעות len סיביות, ממלאים עם אפסים בסדר גבוה אם נדרש.

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;
}

על היעילות

אם n אינו חזקת שניים, וסימנים באורך k-סיביות נצפים בהסתברות p, אז (k + 1)-סיביות סימנים נצפים בהסתברות 1 − p. נוכל לחשב את מספר הסיביות המצופה לסמל $b_{e}$ כדלקמן

$b_{e}=pk+(1-p)(k+1).$

קידוד גולמי של הסמל מכיל $b_{u}=k+1$ סיביות. אז ניתן להגדיר את חיסכון המקום היחסי s (ראו יחס דחיסת נתונים) של הקידוד כדלקמן

$s=1-{\frac {b_{e}}{b_{u}}}=1-{\frac {pk+(1-p)(k+1)}{k+1}}.$

כאשר מפשטים את הביטוי הזה, זה מוביל ל

$s={\frac {p}{k+1}}={\frac {p}{b_{u}}}.$

זה מצביע על כך שיעילות יחסית של קידוד בינארי מקוצר עולה ככל שההסתברות p של סימנים באורך k-סיביות עולה, ואורך סיביות סמל הקידוד הגולמי $b_{u}$ יורד.

ראו גם

• חוק בנפורד
• קידוד גולומב

הערות שוליים

תבנית:Reflist

---

 Facebook Page

🐤 Twitter Follow us on Twitter !

Read or create/edit this page in another language

• Truncated binary encoding in English