הדגימה היא אחד מהשלבים החשובים ביותר בעיבוד ספרתי של אותות. האותות בטבע הם לרוב רציפים או אנלוגים כגון אותות דיבור הנקלטים במיקרופון של טלפון סלולרי או האותות החשמלים הנפלטים ממוח האדם למשל בבדיקת EEG. לצורך עיבודם בצורה ספרתית על ידי מחשב או מעגל משולב ספרתי, יש צורך להפכם לסדרות מספרים או אותות ספרתיים ופעולה זו מבוצעת על ידי דגימת האותות.
דחיסת מידע
חוק שאנון-הארטלי
בתורת האינפורמציה, חוק שאנון הוא משפט המגדיר את קיבול הערוץ של ערוץ תקשורת החשוף לרעש גאוסי, והוא נקרא על שם קלוד שאנון. קיבול ערוץ הוא קצב הנתונים המרבי שבו ניתן לשדר מידע באופן אמין. עבור המקרה הנפוץ של ערוץ שבו מתווסף רעש גאוסי קיים קשר בין קיבול הערוץ לבין רוחב הסרט בו נעשה שימוש ויחס האות לרעש בערוץ:
formula_1
כאשר C קיבול הערוץ, W - רוחב הסרט ו-S/N יחס האות לרעש.
משמעות המשפט היא שקצב המידע (זאת אומרת הקצב לאחר קיזוז ביטי תיקון השגיאות) המרבי שניתן להשיג על ידי קידוד הולך וגדל ככל שרוחב הסרט בו ניתן להשתמש גדול יותר וככל שהספק הרעש הנלווה לערוץ קטן ביחס להספק האות המשודר. בקיום תקשורת בכל קצב מתחת לקצב זה ניתן להשיג הסתברות שגיאה קטנה כרצוננו על ידי קידוד חבילות מידע גדולות ודחיסתן.
חוק שאנון נובע ממשפט כללי יותר של שאנון המגדיר את קיבול הערוץ של ערוץ רועש כלשהו. משפט זה נחשב למשפט היסודי של תורת האינפורמציה. הוא הוכח על ידי שאנון בשנת 1948 והפתיע את קהילת הנדסת מערכות התקשורת. רק לאחר כ-50 שנות מחקר בתורת הקודים, התגלו קודים מעשיים המשיגים ביצועים הקרובים לקיבול הערוץ הגאוסי.
לחוק זה יש שימוש בתחומים פיזיקה ותקשורת מחשבים, כאשר הוא משמש לחישוב מקסימום המהירות של מעבר מידע או אנרגיה בתווך כלשהו תוך התחשבות בהפרעות (רעשים).
קוד תיקון שגיאות
קוד תיקון שגיאות הוא קוד בעל מספר תכונות שמאפשרות לשלוח באמצעותו אוסף של נתונים דרך ערוץ תקשורת רועש, ולנטרל במידה מסוימת את השפעת רעשי הרקע על המידע המתקבל. קודי התיקון פועלים על ידי הגדלת ההבדל בין המילים השונות בקוד, וכך הקטנת הסיכוי שרעש חיצוני יגרום לקליטת מילה השונה מהמילה שנשלחה. כאשר ההבדל בין מילות הקוד גדול במיוחד ניתן אפילו לתקן שגיאות, כל עוד מספר השגיאות קטן מספיק.
מבוא לא פורמלי.
המוטיבציה המקורית לבניית קודים לתיקון שגיאות הייתה לצורך תקשורת מעל ערוץ רועש. בעת שליחת מידע על פני תווך פיזי כלשהו (למשל, כבל), עלולות לקרות שגיאות כתוצאה מתופעות פיזיקליות כלשהן (למשל, ביט כלשהו עלול להחליף את ערכו, או להמחק). על בעיה זו ניסה להתגבר קלוד שאנון בשני מאמרים משנת 1948 בהם הוא הציג את המונח של קוד לתיקון שגיאות (יחד עם הנחת היסודות של תורת האינפורמציה). שאנון הציע לקודד את ההודעה בהודעה ארוכה יותר, כך שאם נשלח את ההודעה הארוכה לאורך התווך במקום את ההודעה המקורית, נוכל לפענח ממנה את ההודעה המקורית, גם אם התווך ישבש את ההודעה ששודרה. אם כך, קוד במובן זה נתון על ידי פונקציית קידוד ופונקציית פענוח. שאנון חשב על התווך (במונחים של שאנון: ערוץ או Channel) כעל אובייקט אקראי, המשבש כל ביט בהסתברות ידועה מראש, וחיפש קודים עבורם ההסתברות שהתווך ישבש את ההודעה כל כך עד שפונקציית הפענוח תכשל היא נמוכה.
שנתיים מאוחר יותר, ב-1950, הציג ריצ'רד המינג גישה אחרת להגדרת קודים מתקני שגיאות. המינג רצה שתמיד יהיה אפשר לפענח את מילת הקוד, בהינתן והתווך מוגבל בכמות הביטים שהוא משבש - כאילו היה התווך יריב זדוני בעל היכולת לשבש כמות כלשהי של הביטים המשודרים, במידה לבלבל את הצדדים המתקשרים כמה שאפשר. בגישה זו, במקום לנסות ולמזער את הסתברות השגיאה של המפענח, קוד במובן המינג מנסה להגדיל את המרחק בין כל שתי מילות קוד. בהכללה גסה, ניתן לחשוב על הגישה של המינג כגישת "המקרה הגרוע" (Worst Case) ועל הגישה של שאנון כגישת "המקרה הממוצע" (Average Case).
אינטואיציה עבור שני המובנים של קוד - המגיעה ממבט תאורטי יותר - היא שקוד לתיקון שגיאות מפזר את האינפורמציה של מילה על פני הרבה ביטים, כך שכל ביט נושא כמות קטנה יותר של מידע. באופן אינטואיטיבי, גם אם יימחקו כמה ביטים הנושאים אינפורמציה קטנה כל אחד מהם, עדיין המידע יהיה קריא, ואף אינפורמציה לא תאבד. אינטואיציה זו מסבירה אולי איך מצאו קודים לתיקון שגיאות הרבה שימושים ועניין רב גם מחוץ לתחום של תקשורת מחשבים, תופעה הנראית מפתיעה ממבט ראשון.
קודים במובן של המינג.
הגדרה.
במובן של המינג, אנחנו מתעלמים לחלוטין משלבי הקידוד והפענוח ופשוט חושבים על הקוד כעל אוסף של מילים. כך למשל התמונה של פונקציית הקידוד של קוד במובן שאנון היא קוד במובן של המינג. ובאופן פורמלי, אם formula_1 הוא אלפבית (קבוצה סופית של סימנים), קוד formula_2 הוא תת-קבוצה של אוסף המילים באורך formula_3, כלומר formula_4. אף על פי שגודל האלפבית אינו חייב להיות בינארי, עדיין המונח ביט משמש כשם לתו כללי ב-formula_1. כדי למדוד את איכותו של הקוד, נעזרים בכמה פרמטרים של הקוד:
נהוג לקרוא לקוד בעל גודל בלוק formula_3, קצב formula_8, מרחק formula_24, וגודל אלפבית formula_25, קוד formula_26.
קודים ליניאריים.
קודים מעניינים יותר יתקבלו אם נעניק לאלפבית מבנה כלשהו. בפרט, אם נחשוב על האלפבית כשדה סופי: formula_32, יקבל formula_33 מבנה טבעי של מרחב וקטורי. קוד formula_34 נקרא קוד ליניארי אם הוא תת מרחב ליניארי של formula_35. על אף שבמבט ראשוני נראה שהגדרה זו היא ספציפית למדי ומגבילה, רוב הקודים הטובים הידועים הם למעשה קודים ליניאריים. נשים לב לנקודות הבאות:
אם כך, קוד ליניארי טוב הוא כזה שבו כל מילת קוד מזכירה את 0 מעט מאוד פעמים. דוגמה טבעית לאוסף כזה של אובייקטים הוא פולינומים. זהו הרעיון הבסיסי מאחורי קוד ריד-סולומון. אם נסמן את איברי השדה formula_37, ונבחר פרמטר formula_8, קוד ריד-סולומון יוגדר כך:
עובדה ידועה על פולינומים מעל שדות היא שכל פולינום ממעלה לכל היותר formula_39, יש לכל היותר formula_39 אפסים, ועל כן זהו קוד formula_41.
באופן דומה מוגדרים קודים ליניאריים טובים נוספים, כדוגמת קוד אדמר (הבנוי מכל הפונקציות הליניאריות) או קוד ריד-מולר (הבנוי מכל הפולינומים במספר משתנים וממעלה חסומה).
קודים במובן של שאנון.
הגדרה.
המודל עליו מסתכל שאנון בהגדרתו מורכב משלושה שלבים:
אם כן, קוד מוגדר על ידי זוג פונקציות formula_42 כשformula_43 היא פונקציית קידוד הלוקחת הודעה באורך formula_8 מעל אלפבית formula_45, ומחזירה הודעה באורך formula_3 מעל אותו האלפבית, וformula_47 היא פונקציית פענוח הלוקחת הודעה באורך כלשהו (שכן הערוץ עלול לשנות את אורך ההודעה) מעל אלפבית formula_48 (שכן הערוץ עלול להוציא סימנים הלקוחים מאלפבית אחר) ומחזירה את ההערכה שלה למה הייתה המחרוזת המקורית שנשלחה. באופן דומה לקודים במובן המינג, קצב הקוד (rate) נתון על ידי formula_13.
ערוץ מוגדר על ידי אוסף התפלגויות הנתמכות מעל formula_50, אחת לכל הודעה אפשרית בformula_51. בהינתן הודעה formula_16 בformula_51, הערוץ פולט הודעה בformula_50 הנדגמת מההתפלגות של formula_16. בהינתן ערוץ, נרצה להגדיר את הקיבולת (Capacity) שלו, מדד של כמות המידע שהערוץ מסוגל להעביר מבלי לפגום בו. ישנן שתי דרכים להגדיר קיבולת:
ממשפט הקידוד מעל ערוץ, שתי ההגדרות שלעיל שקולות.
משפט הערוץ הרועש של שאנון.
שאנון התעניין בחישוב הקיבולת של ערוץ, והצליח לחשב את הקיבולת של ערוץ סימטרי בינארי. משפט הערוץ הרועש של שאנון קובע כי לכל formula_64, הקיבולת של הערוץ הבינארי formula_65 הוא formula_75, כשformula_76 היא אנטרופיית שאנון של משתנה מקרי ברנולי עם הסתברות formula_66:
שימושים.
בתקשורת מחשבים.
קודים לתיקון שגיאות מאפשרים תקשורת אמינה מעל ערוץ רועש, על ידי קידוד ההודעה לפני שליחתה, ופענוח ההודעה (המורעשת) בהגעתה ליעד. לשימוש פרקטי, נרצה קודים לתיקון שגיאות בעלי קידוד ופענוח מהירים, ובעלי קצב גבוה. דוגמה בסיסית לקודים שכאלו הם קודי Longitual/Vertical Redundancy Check) LRC/VRC). בקודים אלו, נכתוב את המידע בצורת טבלה, כך שכבכל תא בטבלה ישב אחד מהביטים של ההודעה המקורית, ונוסיף סיבית זוגיות לכל שורה (בLRC) או עמודה (בVRC). בקודים אלו ניתן לזהות לכל היותר שגיאה אחת בכל שורה/עמודה (בLRC/VRC; בהתאמה), אך לא לתקן אותה. היתרון שלהם לעומת זאת הוא שהם יעילים ומאפשרים מימוש קל ומהיר בחומרה. ניתן לשלב בין שיטות אלה, בקוד VLRC, שם נשלח את ביט הבקרה לכל שורה ולכל עמודה. כעת ניתן לזהות עד 3 שגיאות, ואף לתקן שגיאה בודדת, באמצעות הצלבת השורה והעמודה שבהן התגלו שגיאות. שיטה זו שימושית ביותר בבדיקת קבוצה (Group Testing).
שיטות פופולריות נוספות לקידוד הן סיכום ביקורת (checksum) וCRC, בהן משורשרת לסוף ההודעה תוצאת פונקציה כלשהי של ההודעה. בעת הפענוח מחשבים את אותה הפונקציה על ההודעה שהגיעה, ומשווים זאת עם התוצאה הנתונה. הפונקציה נבחרת כך ששינויים רדנומיים בהודעה יגרמו לפלט הפונקציה להשתנות, וכך נוכל לזהות (אך לא בהכרח לתקן) שגיאות בעת העברת ההודעה בהסתברות טובה. יתרונם הגדול של שיטות אלו הוא פשטותם, ויעילותם הגבוהה.
שיטות מתקדמות יותר כוללות קודי קונבולוציה, וקודי LDPC.
במסדי נתונים.