יתירות (תורת האינפורמציה)

יתירות הוא מונח בתורת המידע המתואר על ידי היחס בין האנטרופיה $H(X)$ של $X$, והערך המרבי האפשרי $\log (|{𝒜}_X|)$.תבנית:הערהתבנית:הערה

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

הגדרה כמותית

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

$r=\underset{n\to \mathrm{\infty }}{\lim }\frac{1}{n}H(M_1,M_2,\dots M_n),$

הגבול, כאשר n שואף לאינסוף, האנטרופיה המשוקללת של n הסימבולים הראשונים מחולק על ידי n. בתורת המידע נפוץ לדבר על "קצב" או "אנטרופיה" של שפה. זה מתאים, לדוגמה, כאשר מקור המידע הוא "פרוזה בשפה האנגלית". הקצב של המקור (חסר הזיכרון) הוא פשוט $H(M)$ משום שבהגדרה אין תלות הדדית בין הודעות רצופות של מקור נטול זיכרון.

את הקצב המוחלט של שפה או מקור הוא פשוט

$R=\log |𝕄|,$

שהוא הלוגריתם של גודל מרחב ההודעות, או ה"אלפבית". (נוסחה זו נקראת לעיתים פונקציית הארטלי.)

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

יתירות מוחלטת ניתנת להגדרה על ידי:

$D=R-r,$

כלומר ההבדל בין הקצב המוחלט לקצב.

היחס $\frac{D}{R}$ נקרא יתירות יחסית ונותן את יחס הדחיסה המקסימלי כאשר מבוטא על ידי האחוז בו ניתן להפחית את גודל הקובץ.

באופן משלים ליתירות יחסית, היעילות מוגדרת על ידי $\frac{r}{R},$, כך ש $\frac{r}{R}+\frac{D}{R}=1$.

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

קישורים חיצוניים

• תבנית:MathWorld