קוד האפמן – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ביטול גרסה 18707276 של 79.178.201.110 (שיחה) |
אין תקציר עריכה |
||
שורה 4:
==גילוי הקוד==
בשנת [[1951]], במסגרת לימודיו לדוקטורט ב־[[MIT]], למד [[דייוויד האפמן]] קורס ב[[תורת האינפורמציה]] שהייתה אז בחיתוליה. המרצה בקורס [[רוברט פאנו]] הציע לתלמידים
==רקע==
שורה 12:
==תיאור פורמלי==
===תיאור הקוד===
קוד האפמן הוא [[קוד תחיליות]], כלומר מחרוזת ביטים שמייצגת אות לעולם אינה מהווה תחילית של מחרוזת המייצגת אות אחרת. קוד כזה מבטיח אפשרות יחידה לפיענוח, ויתירה מזאת, הפיענוח מהיר, שכן מספיק לעבור על הרצף המקודד פעם אחת
קוד מסוג זה ניתן לייצג על ידי [[עץ בינארי]], כאשר עלי העץ מייצגים את האותיות המקודדות, וצמתי העץ מסומנים ב-0 או 1. כאשר רוצים לפענח רצף ביטים כלשהו, הולכים על העץ על פי הביטים שנקלטים עד אשר מגיעים לעלה. האות המאוחסנת בעלה היא האות המפוענחת.
כאשר הקוד הוא אופטימלי, העץ יהיה עץ מלא. כלומר, לכל צומת שאינו עלה יהיו בדיוק שני בנים. לדוגמה, נניח כי בקוד כלשהו לשורש של העץ יש רק בן אחד, שאליו מובילה הקשת 0. פירוש הדבר הוא שבקוד לא יהיו כלל אותיות שקידודן מתחיל ב-1, וזהו
===תיאור הבעיה===
|