Elias gamma coding

קוד גמא של אליאס או קוד גמא אליאס היא קוד אוניברסלי המקודד מספרים חיוביים שפותח על ידי פיטר אליאס. קוד זה משמש בעיקר כשמקודדים מספרים שלהם אין גבול עליון מוגדר מראש.

מיקוד[עריכה]

למיקוד מספר x ≥ 1:

נגדיר $N=\lfloor \log _{2}x\rfloor$ כחזקה הגבוהה ביותר של 2 שהוא מכיל, כך ש-2^N ≤ x < 2^N+1.
נכתוב $N$ ביטים של אפסים.
נוסיף את הצורה הבינארית של $x$ , מספר בינארי באורך $(N+1)$ ביטים.

בשיטה שקולה להסביר את אותה תהליך:

נקודד את $N$ בחישוב אונירי; כלומר, כ- $N$ אפסים ואחריהם אחד.
נוסיף את הספרות הבינאריות שנותרו של $x$ לייצוג זה של $N$ .

כדי לייצג מספר $x$ , קוד גמא אליאס (γ) משתמש ב- $2\lfloor \log _{2}(x)\rfloor +1$ ביטים.

הקוד מתחיל (החלוקה של האפשרות לקוד נוספת לבהירות):

מספר	בינארי	קוד γ	הסתברות מושרה
1 = 2⁰ + 0	`1`	`1`	1/2

2 = 2¹ + 0	`1 0`	`0 1 0`	1/8
3 = 2¹ + 1	`1 1`	`0 1 1`	1/8

4 = 2² + 0	`1 00`	`00 1 00`	1/32
5 = 2² + 1	`1 01`	`00 1 01`	1/32
6 = 2² + 2	`1 10`	`00 1 10`	1/32
7 = 2² + 3	`1 11`	`00 1 11`	1/32

8 = 2³ + 0	`1 000`	`000 1 000`	1/128
9 = 2³ + 1	`1 001`	`000 1 001`	1/128
10 = 2³ + 2	`1 010`	`000 1 010`	1/128
11 = 2³ + 3	`1 011`	`000 1 011`	1/128
12 = 2³ + 4	`1 100`	`000 1 100`	1/128
13 = 2³ + 5	`1 101`	`000 1 101`	1/128
14 = 2³ + 6	`1 110`	`000 1 110`	1/128
15 = 2³ + 7	`1 111`	`000 1 111`	1/128

16 = 2⁴ + 0	`1 0000`	`0000 1 0000`	1/512
17 = 2⁴ + 1	`1 0001`	`0000 1 0001`	1/512

פענוח[עריכה]

לפענח מספר שלם מקודד בקוד גמא אליאס:

קרא וספור אפסים מהזרם עד שתגיע לאחד הראשון. קרא לספירה זו של אפסים N.
תחשב את האחד שהתקבל כספרה הראשונה של המספר השלם, עם ערך של 2^N, קרא את הספרות הנותרות N של המספר השלם.

שימושים[עריכה]

קידוד גמא משמש ביישומים שבהם הערך המקודד הגדול ביותר אינו ידוע מראש, או לדחיסת נתונים בהם ערכים קטנים שכיחים הרבה יותר מערכים גדולים.

קידוד גמא יכול להיות יעיל יותר במצבים אלה. למשל, בטבלה לעיל, אם נבחר לאחסן מספר קטן כמו 5 בגודל קבוע של 8 ביטים, הבינארי שיתקבל יהיה 00000101, בעוד שהגרסה בגודל משתנה של קוד γ תהיה 00 1 01, ותזדקק ל-3 ביטים פחות. מנגד, ערכים גדולים יותר, כמו 254 שמאוחסנים בגודל קבוע של 8 ביטים, יהיו 11111110 בעוד שהגרסה בגודל משתנה של קוד γ תהיה 0000000 1 1111110, ותזדקק ל-7 ביטים נוספים.

קוד גמא הוא חלק בונה בקוד דלתא של אליאס.

הכללות[עריכה]

קוד גמא אינו מקודד אפס או מספרים שליליים. דרך אחת לטפל באפס היא להוסיף 1 לפני המיקוד ואז להוריד 1 אחרי הפענוח. דרך אחרת היא להקדים את כל קוד שאינו אפס ב-1 ואז לקודד אפס כ-0 בודד.

דרך אחת לקודד את כל המספרים היא להגדיר התאמה חד-חד-ערכית, שממפה מספרים שלמים (0, -1, 1, -2, 2, -3, 3, ...) ל-(1, 2, 3, 4, 5, 6, 7, ...) לפני המיקוד. בתוכנה, זה נעשה בקלות ביותר על ידי מיפוי קלטים חיוביים לפלטים אי-זוגיים, וקלטים שליליים לפלטים זוגיים, כך שהביט הכי פחות משמעותי הופך לביט סימן הפוך: הפענוח נכשל (פונקציה "\begin{cases}" לא מוכרת): {\displaystyle \begin{cases} x \mapsto 2x+1 & \text{כש~} x \geq 0 \\ x \mapsto -2x & \text{כש~} x < 0 \\ \end{cases}}

קוד גולומב אקספוננציאלי מכליל את קוד גמא למספרים שלמים עם חלוקת כוח מישורית יותר, כפי שקוד גולומב מכליל את הקוד האונירי. הוא כולל חלוקה של המספר במחלק חיובי, בדרך כלל חזקה של 2, כתיבת קוד גמא לאחד פחות מהמנה, וכתיבת השארית בקוד בינארי רגיל.