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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

יתירות היא מונח בתורת המידע המתואר על ידי היחס בין האנטרופיה של , והערך המרבי האפשרי .[1][2]

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

הגדרה כמותית[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

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

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

באופן משלים ליתירות יחסית, היעילות מוגדרת על ידי , כך ש

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

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Here it is assumed are the sets on which the probability distributions are defined.
  2. ^ MacKay, David J.C. (2003). "2.4 Definition of entropy and related functions". Information Theory, Inference, and Learning Algorithms. Cambridge University Press. עמ' 33. ISBN 0-521-64298-1. The redundancy measures the fractional difference between H(X) and its maximum possible value,