קוד תיקון שגיאות

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

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

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

אם האלפבית הוא שדה סופי (מבנה אלגברי), ניתן להתייחס למילים כוקטורים. קוד ליניארי הוא תת‑מרחב וקטורי. יתרון חשוב: מרחק הקוד שווה למשקל המילה הקצרה ביותר בתת‑המרחב, ולכן בנייה אלגברית עוזרת לבנות קודים טובים.
דוגמה מרכזית היא קוד ריד‑סולומון: בונים וקטורים על ידי הערכת פולינומים בנקודות שונות. פולינום ממעלה k-1 יכול להימשך לאפסים רק עד k-1 פעמים, ולכן קוד ריד‑סולומון מקבל מרחק שקשור לפרמטרים q ו‑k. קודים ליניאריים נוספים כוללים קודים מבוססי פולינומים מרובים וקודים ליניאריים פשוטים אחרים.

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

קיימים מודלים שונים לערוצים, למשל ערוץ שבו כל ביט משתבש בעצמאות בתאוצה p.

שאנון חישב את הקיבולת של ערוץ בינארי סימטרי. עבור הסתברות שיבוש p, הקיבולת היא 1 פחות האנטרופיה H(p). כלומר, יש גבול תאורטי למה שאפשר להעביר reliably.

בקודים פשוטים ונפוצים מוסיפים סיביות בקרה לשורות או לעמודות (LRC/VRC). אלה מזהים שגיאות בקלות, ולעתים מאפשרים לתקן שגיאה יחידה על ידי חיתוך שורות ועמודות. שיטות נוספות לזיהוי שגיאות הן checksum ו‑CRC, שמחשבים סכום או פונקציה על ההודעה ומשווים אותו בפענוח. שיטות מתקדמות יותר הן קודי קונבולוציה ו‑LDPC.

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

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

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

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

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

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

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

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

יש שיטות פשוטות שמוסיפות סיביות זוגיות לשורות או לעמודות. זה עוזר למצוא שורה או עמודה שבה יש שגיאה. יש גם שיטות כמו checksum ו‑CRC שבודקות אם ההודעה השתנתה.

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

קודים עוזרים בבדיקות קצרות ובבניית כלים מתמטיים חשובים.