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

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

מבוא לא פורמלי

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

שנתיים מאוחר יותר, ב-1950, הציג ריצ'רד המינג גישה אחרת להגדרת קודים מתקני שגיאות. המינג רצה שתמיד יהיה אפשר לפענח את מילת הקוד, בהינתן והתווך מוגבל בכמות הביטים שהוא משבש - כאילו היה התווך יריב זדוני בעל היכולת לשבש כמות כלשהי של הביטים המשודרים, במידה לבלבל את הצדדים המתקשרים כמה שאפשר. בגישה זו, במקום לנסות ולמזער את הסתברות השגיאה של המפענח, קוד במובן המינג מנסה להגדיל את המרחק בין כל שתי מילות קוד. בהכללה גסה, ניתן לחשוב על הגישה של המינג כגישת "המקרה הגרוע" (Worst Case) ועל הגישה של שאנון כגישת "המקרה הממוצע" (Average Case).

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

קודים במובן של המינג

הגדרה

במובן של המינג, אנחנו מתעלמים לחלוטין משלבי הקידוד והפענוח ופשוט חושבים על הקוד כעל אוסף של מילים. כך למשל התמונה של פונקציית הקידוד של קוד במובן שאנון היא קוד במובן של המינג. ובאופן פורמלי, אם $\Sigma$ הוא אלפבית (קבוצה סופית של סימנים), קוד $C$ הוא תת-קבוצה של אוסף המילים באורך $n$, כלומר $C\subseteq \Sigma ^{n}$. אף על פי שגודל האלפבית אינו חייב להיות בינארי, עדיין המונח ביט משמש כשם לתו כללי ב-$\Sigma$. כדי למדוד את איכותו של הקוד, נעזרים בכמה פרמטרים של הקוד:

• גודל הבלוק (block size) הוא בכמה ביטים נעזרנו לקידוד. תחת הסימונים מעלה זהו $n$.
• מימד הקוד (dimension) הוא כמה ביטים אפקטיביים של מידע קודדנו. כאינטואיציה לקראת ההגדרה, נחשוב למשל על קוד שגודלו הוא $|C|=|\Sigma |^{k}$ עבור איזשהו $k$ שלם, ניתן אז לזהות את הקוד עם אוסף כל המילים באורך $k$ (כקבוצות): $C\simeq \Sigma ^{k}$, ולחשוב על הזיהוי הזה כפונקציית קידוד. לכן ניתן להגיד שהקוד מקודד $k$ ביטים באופן אפקטיבי. באופן מדויק יותר, יוגדר קצב הקוד כ- $k=\log _{|\Sigma |}|C|$. פרמטר דומה הוא הקצב (rate): $R=k/n$, המודד את היחס בין כמה ביטים אפקטיביים קודדנו, לעומת כמה ביטים נשלחו בפועל.
• מרחק הקוד (distance) מודד כמה רחוקות מילות הקוד זו מזו. זהו מרחק המינג (Hamming Distance) המינימלי בין כל שתי מילות קוד. ובמדויק: $d=\min \nolimits _{x\neq y\in C}\Delta (x,y)$ כש-$\Delta (x,y)$ הוא מרחק המינג בין $x$ ו-$y$, כלומר בכמה ביטים $x$ ו-$y$ שונים זה מזה. באופן דומה לסימון עבור קצב, נהוג להגדיר גם מרחק יחסי: $\delta =d/n$.
• גודל האפלבית הוא גודל האלפבית מעליו הקוד מוגדר. נסמן את גודל האלפבית כ-$q=|\Sigma |$.

נהוג לקרוא לקוד בעל גודל בלוק $n$, קצב $k$, מרחק $d$, וגודל אלפבית $q$, קוד $\mathbf {[n,k,d]_{q}}$.

דוגמאות בסיסיות

• קוד פשוט הוא חזרה על כל ביט מספר מסוים של פעמים. בעוד קוד זה יכול לזהות ולתקן שגיאות מול ערוץ במובן של שאנון, המבצע מחיקות אקראיות (שכן ההסתברות שכל החזרות ימחקו הוא קטן בהינתן מספר גדול מספיק של חזרות), מול ערוץ במובן של האמינג הוא גרוע למדי, שכן כדי להרוס את הקידוד, מספיק ליריב זדוני למחוק את כל החזרות של ביט בודד. עבור 3 חזרות הקוד הוא: $C=\{(x_{1},x_{1},x_{1},\ldots ,x_{k},x_{k},x_{k})\;\vert \;x_{1},\ldots ,x_{k}\in \Sigma \}$. זהו קוד $[3k,k,3]_{|\Sigma |}$.
• קוד פשוט נוסף הוא הוספת ספרת ביקורת. מקרה פרטי מעניין שלו הוא הוספת ביט זוגיות - בהינתן מילה בינארית באורך $k$ נוסיף לה ביט נוסף שיגרום לXOR של כל הביטים להיות 0. כלומר הקוד הוא $C=\{(x_{1},\ldots ,x_{k+1})\in \{0,1\}^{k+1}\;\vert \;x_{1}\oplus \ldots \oplus x_{k+1}=0\}$. זהו קוד $[k+1,k,2]_{2}$.

קודים ליניאריים

ערך מורחב – קוד ליניארי

קודים מעניינים יותר יתקבלו אם נעניק לאלפבית מבנה כלשהו. בפרט, אם נחשוב על האלפבית כשדה סופי: $\Sigma =\mathbb {F} _{q}$, יקבל $\Sigma ^{n}$ מבנה טבעי של מרחב וקטורי. קוד $C\subseteq \mathbb {F} _{q}^{n}$ נקרא קוד ליניארי אם הוא תת מרחב ליניארי של $\mathbb {F} _{q}^{n}$. על אף שבמבט ראשוני נראה שהגדרה זו היא ספציפית למדי ומגבילה, רוב הקודים הטובים הידועים הם למעשה קודים ליניאריים. נשים לב לנקודות הבאות:

• המימד של קוד ליניארי (כקוד) שווה למימד שלו כמרחב וקטורי.
• מאחר שקוד ליניארי סגור תחת חיסור, ומאחר ומרחק המינג נשמר תחת חיסור, המרחק של קוד ליניארי שווה למשקל המינג (מספר הביטים שאינם אפס, או באופן שקול מרחק המינג ממילת האפס; מסומן ב-$wt(\cdot )$) המינימלי של מילת קוד שאינה מילת האפס:

$d=\min _{x\neq y\in C}\Delta (x,y)=\min _{x\neq y\in C}\Delta (x-y,y-y)=\min _{x\neq y\in C}\Delta (x-y,0)=\min _{z\in C}wt(z)$

אם כך, קוד ליניארי טוב הוא כזה שבו כל מילת קוד מזכירה את 0 מעט מאוד פעמים. דוגמה טבעית לאוסף כזה של אובייקטים הוא פולינומים. זהו הרעיון הבסיסי מאחורי קוד ריד-סולומון. אם נסמן את איברי השדה $\mathbb {F} _{q}=\{\alpha _{1},\ldots ,\alpha _{q}\}$, ונבחר פרמטר $k$, קוד ריד-סולומון יוגדר כך:

$RS_{k}=\{(p(\alpha _{1}),\ldots ,p(\alpha _{q}))\;\vert \;p{\mbox{ is a polynomial of degree at most }}k-1\}$

עובדה ידועה על פולינומים מעל שדות היא שכל פולינום ממעלה לכל היותר $k-1$, יש לכל היותר $k-1$ אפסים, ועל כן זהו קוד $[q,k,q-k+1]_{q}$.

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

קודים במובן של שאנון

הגדרה

המודל עליו מסתכל שאנון בהגדרתו מורכב משלושה שלבים:

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

אם כן, קוד מוגדר על ידי זוג פונקציות $(E,D)$ כש$E\colon {\mathcal {X}}^{k}\to {\mathcal {X}}^{n}$ היא פונקציית קידוד הלוקחת הודעה באורך $k$ מעל אלפבית ${\mathcal {X}}$, ומחזירה הודעה באורך $n$ מעל אותו האלפבית, ו$D\colon {\mathcal {Y}}^{\ast }\to {\mathcal {X}}^{k}$ היא פונקציית פענוח הלוקחת הודעה באורך כלשהו (שכן הערוץ עלול לשנות את אורך ההודעה) מעל אלפבית ${\mathcal {Y}}$ (שכן הערוץ עלול להוציא סימנים הלקוחים מאלפבית אחר) ומחזירה את ההערכה שלה למה הייתה המחרוזת המקורית שנשלחה. באופן דומה לקודים במובן המינג, קצב הקוד (rate) נתון על ידי $R=k/n$.

ערוץ מוגדר על ידי אוסף התפלגויות הנתמכות מעל ${\mathcal {Y}}^{\ast }$, אחת לכל הודעה אפשרית ב${\mathcal {X}}^{n}$. בהינתן הודעה $x$ ב${\mathcal {X}}^{n}$, הערוץ פולט הודעה ב${\mathcal {Y}}^{\ast }$ הנדגמת מההתפלגות של $x$. בהינתן ערוץ, נרצה להגדיר את הקיבולת (Capacity) שלו, מדד של כמות המידע שהערוץ מסוגל להעביר מבלי לפגום בו. ישנן שתי דרכים להגדיר קיבולת:

• הגדרה כקצב המקסימלי: נאמר שקצב מסוים $0\leq R\leq 1$ הוא בר-השגה (achievable), אם קיימת משפחה אינסופית של קודים, שכל קוד בה הוא עם קצב לפחות $R$, ובנוסף ההסתברות שפונקציית הקידוד מבצעת בו שגיאה הולך וקטן עד ששואף ל-0. אם כך, קיבולת הערוץ תוגדר על ידי הקצב המקסימלי שהוא בר-השגה:

$C=\sup\{0\leq R\leq 1\;\vert \;R{\mbox{ is achievable}}\}$

• הגדרה ככמות המידע שהערוץ משאיר: עבור פונקציית קידוד כלשהי $E$, נסמן ב$X_{E}$ את המשתנה המקרי שמתקבל מקידוד הודעה אקראית וב$Y_{E}$ את פלט הערוץ על $X_{E}$. עבור שני משתנים אקראיים בדידים $Z_{1},Z_{2}$ נסמן ב$I(Z_{1};Z_{2})$ את האינפורמציה ההדדית שלהם, מדד לכמות המידע ששניהם חולקים. קיבולת הערוץ תוגדר כך:

$C=\max _{E}\{I(X_{E};Y_{E})\}$

ממשפט הקידוד מעל ערוץ, שתי ההגדרות שלעיל שקולות.

דוגמאות לערוצים

• הערוץ הסימטרי הבינארי (Binary Symmetric Channel), הנתון על ידי פרמטר $0\leq p<1/2$ ומסומן $BSC_{p}$, מבצע פעולת החלפה עבור כל ביט. כלומר, עבור כל ביט בנפרד ובאופן בלתי תלוי, מחליף אותו (ממיר 0 ב-1, ו1 ב0) בהסתברות $p$.
• ערוץ מחיקה בינארי (Binary Erasure Channel), הנתון על ידי פרמטר $0\leq p<1$ ומסומן $BEC_{p}$, מוחק כל ביט בהסתברות $p$, וכותב במקומו סימן כלשהו המסמן את המחיקה. לרוב סימן זה מסומן ב$?$.
• ערוץ השמטה בינארי (Binary Deletion Channel), הנתון על ידי פרמטר $0\leq p<1$, משמיט כל ביט בהסתברות $p$. על כן, אורך הפלט של הערוץ אינו קבוע ובוודאי אינו בהכרח האורך של הקלט המקורי של הערוץ, מה שמקשה מאוד על האנליזה של ערוץ זה. הבעיה של לקבוע את הקיבולת של ערוץ זה היא בעיה פתוחה.

משפט הערוץ הרועש של שאנון

שאנון התעניין בחישוב הקיבולת של ערוץ, והצליח לחשב את הקיבולת של ערוץ סימטרי בינארי. משפט הערוץ הרועש של שאנון קובע כי לכל $0\leq p<1/2$, הקיבולת של הערוץ הבינארי $BSC_{p}$ הוא $1-H(p)$, כש$H(p)$ היא אנטרופיית שאנון של משתנה מקרי ברנולי עם הסתברות $p$:

$H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)$

שימושים

בתקשורת מחשבים

קודים לתיקון שגיאות מאפשרים תקשורת אמינה מעל ערוץ רועש, על ידי קידוד ההודעה לפני שליחתה, ופענוח ההודעה (המורעשת) בהגעתה ליעד. לשימוש פרקטי, נרצה קודים לתיקון שגיאות בעלי קידוד ופענוח מהירים, ובעלי קצב גבוה. דוגמה בסיסית לקודים שכאלו הם קודי Longitual/Vertical Redundancy Check) LRC/VRC). בקודים אלו, נכתוב את המידע בצורת טבלה, כך שכבכל תא בטבלה ישב אחד מהביטים של ההודעה המקורית, ונוסיף סיבית זוגיות לכל שורה (בLRC) או עמודה (בVRC). בקודים אלו ניתן לזהות לכל היותר שגיאה אחת בכל שורה/עמודה (בLRC/VRC; בהתאמה), אך לא לתקן אותה. היתרון שלהם לעומת זאת הוא שהם יעילים ומאפשרים מימוש קל ומהיר בחומרה. ניתן לשלב בין שיטות אלה, בקוד VLRC, שם נשלח את ביט הבקרה לכל שורה ולכל עמודה. כעת ניתן לזהות עד 3 שגיאות, ואף לתקן שגיאה בודדת, באמצעות הצלבת השורה והעמודה שבהן התגלו שגיאות. שיטה זו שימושית ביותר בבדיקת קבוצה (Group Testing).

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

שיטות מתקדמות יותר כוללות קודי קונבולוציה, וקודי LDPC.

במסדי נתונים

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

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

במדעי המחשב התאורטיים

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

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

בדרנדומיזציה, קודים משמשים לבנייה של אובייקטיביים פסאודו-רנדומיים כמו מחלצי רדנומיות (Randomness Extractors) והתפלגויות עם הטיה קטנה (Small-Bias Distributions). ידועים גם קשרים בין קודים לאובייקטים פסאודו-רנודמיים נוספים, למשל גרפים מרחיבים.

ראו גם

• תורת הקודים

לקריאה נוספת

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

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

• קוד תיקון שגיאות, באתר MathWorld (באנגלית)

הערות שוליים

ערך טוב