הצגת המקור של הדף "קוד תיקון שגיאות"

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

== מבוא לא פורמלי ==
המוטיבציה המקורית לבניית קודים לתיקון שגיאות הייתה לצורך תקשורת מעל ערוץ רועש. בעת שליחת מידע על פני [[תווך]] פיזי כלשהו (למשל, [[כבל תקשורת|כבל]]), עלולות לקרות שגיאות כתוצאה מתופעות פיזיקליות כלשהן (למשל, [[סיבית|ביט]] כלשהו עלול להחליף את ערכו, או להמחק). על בעיה זו ניסה להתגבר [[קלוד שאנון]] בשני מאמרים משנת 1948 בהם הוא הציג את המונח של '''קוד לתיקון שגיאות''' (יחד עם הנחת היסודות של [[תורת האינפורמציה]])<ref>{{צ-מאמר|שם=A Mathematical Theory of Communication|קישור=https://ieeexplore.ieee.org/document/6773024|כתב עת=Bell System Technical Journal|שנת הוצאה=1948-07|עמ=379–423|כרך=27|doi=10.1002/j.1538-7305.1948.tb01338.x|מחבר=C. E. Shannon}}</ref><ref>{{צ-מאמר|שם=A Mathematical Theory of Communication|קישור=https://ieeexplore.ieee.org/document/6773067|כתב עת=Bell System Technical Journal|שנת הוצאה=1948-10|עמ=623–656|כרך=27|doi=10.1002/j.1538-7305.1948.tb00917.x|מחבר=C. E. Shannon}}</ref>. שאנון הציע '''לקודד''' את ההודעה בהודעה ארוכה יותר, כך שאם נשלח את ההודעה הארוכה לאורך התווך במקום את ההודעה המקורית, נוכל '''לפענח''' ממנה את ההודעה המקורית, גם אם התווך ישבש את ההודעה ששודרה. אם כך, קוד במובן זה נתון על ידי '''פונקציית קידוד''' ו'''פונקציית פענוח'''. שאנון חשב על התווך (במונחים של שאנון: '''ערוץ''' או Channel) כעל אובייקט אקראי, המשבש כל ביט בהסתברות ידועה מראש, וחיפש קודים עבורם ההסתברות שהתווך ישבש את ההודעה כל כך עד שפונקציית הפענוח תכשל היא נמוכה.

שנתיים מאוחר יותר, ב-1950, הציג [[ריצ'רד המינג]] גישה אחרת להגדרת קודים מתקני שגיאות<ref>{{צ-מאמר|שם=Error Detecting and Error Correcting Codes|קישור=https://ieeexplore.ieee.org/document/6772729|כתב עת=Bell System Technical Journal|שנת הוצאה=1950-04|עמ=147–160|כרך=29|doi=10.1002/j.1538-7305.1950.tb00463.x|מחבר=R. W. Hamming}}</ref>. המינג רצה שתמיד יהיה אפשר לפענח את מילת הקוד, בהינתן והתווך מוגבל בכמות הביטים שהוא משבש - כאילו היה התווך יריב זדוני בעל היכולת לשבש כמות כלשהי של הביטים המשודרים, במידה לבלבל את הצדדים המתקשרים כמה שאפשר. בגישה זו, במקום לנסות ולמזער את הסתברות השגיאה של המפענח, קוד במובן המינג מנסה להגדיל את ה'''מרחק''' בין כל שתי מילות קוד. בהכללה גסה, ניתן לחשוב על הגישה של המינג כגישת "המקרה הגרוע" (Worst Case) ועל הגישה של שאנון כגישת "המקרה הממוצע" (Average Case).

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

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

נהוג לקרוא לקוד בעל גודל בלוק <math>n</math>, קצב <math>k</math>, מרחק <math>d</math>, וגודל אלפבית <math>q</math>, '''קוד''' <math>\mathbf{[n, k, d]_q}</math>.

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

=== קודים ליניאריים ===
{{הפניה לערך מורחב|קוד ליניארי}}
קודים מעניינים יותר יתקבלו אם נעניק לאלפבית מבנה כלשהו. בפרט, אם נחשוב על האלפבית כ[[שדה סופי]]: <math>\Sigma = \mathbb{F}_q</math>, יקבל <math>\Sigma^n</math> מבנה טבעי של [[מרחב וקטורי]]. קוד <math>C \subseteq \mathbb F_q^n</math> נקרא '''קוד ליניארי''' אם הוא [[תת מרחב|תת מרחב ליניארי]] של <math>\mathbb F_q^n</math>. על אף שבמבט ראשוני נראה שהגדרה זו היא ספציפית למדי ומגבילה, רוב הקודים הטובים הידועים הם למעשה קודים ליניאריים. נשים לב לנקודות הבאות:
* המימד של [[קוד ליניארי]] (כקוד) שווה ל[[ממד (אלגברה ליניארית)|מימד]] שלו כמרחב וקטורי.
* מאחר שקוד ליניארי [[סגירות (אלגברה)|סגור]] תחת [[חיסור]], ומאחר ומרחק המינג [[שמורה (מתמטיקה)|נשמר]] תחת חיסור, המרחק של קוד ליניארי שווה ל'''[[משקל המינג]]''' (מספר הביטים שאינם אפס, או באופן שקול מרחק המינג ממילת האפס; מסומן ב-<math>wt(\cdot)</math>) המינימלי של מילת קוד שאינה מילת האפס:
{{יישור טקסט|שמאל|<math> 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) </math>}}

אם כך, קוד ליניארי טוב הוא כזה שבו כל מילת קוד מזכירה את 0 מעט מאוד פעמים. דוגמה טבעית לאוסף כזה של אובייקטים הוא [[פולינום|פולינומים]]. זהו הרעיון הבסיסי מאחורי קוד [[ריד-סולומון]]. אם נסמן את איברי השדה <math>\mathbb F_q = \{\alpha_1, \ldots, \alpha_q\}</math>, ונבחר פרמטר <math>k</math>, קוד ריד-סולומון יוגדר כך:

{{יישור טקסט|שמאל|<math> RS_k = \{(p(\alpha_1), \ldots, p(\alpha_q)) \; \vert \; p \mbox{ is a polynomial of degree at most } k-1\} </math>}}

עובדה ידועה על פולינומים מעל שדות היא שכל פולינום ממעלה לכל היותר <math>k-1</math>, יש לכל היותר <math>k-1</math> אפסים, ועל כן זהו קוד <math>[q, k, q-k+1]_q</math>.

באופן דומה מוגדרים קודים ליניאריים טובים נוספים, כדוגמת [[קוד אדמר]] {{אנ|Hadamard code}} (הבנוי מכל [[פונקציה ליניארית|הפונקציות הליניאריות]]) או [[קוד ריד-מולר]] {{אנ|Reed-Muller code}} (הבנוי מכל הפולינומים במספר משתנים וממעלה חסומה).

== קודים במובן של שאנון ==
=== הגדרה ===
המודל עליו מסתכל שאנון בהגדרתו מורכב משלושה שלבים:
* השולח בוחר הודעה באקראי, מקודד אותה בעזרת פונקציית קידוד כלשהי, ושולח את ההודעה המקודדת מעל ערוץ.
* הערוץ משבש את ההודעה, בצורה אקראית כלשהי, המוגדרת על ידי הערוץ.
* המקבל קורא את ההודעה שיצאה מהערוץ, ומנסה לפענח אותה בעזרת פונקציית פענוח כלשהי.
[[קובץ:Channel_model.svg|מרכז|700px]]

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

'''ערוץ''' מוגדר על ידי אוסף התפלגויות הנתמכות מעל <math>\mathcal Y^\ast</math>, אחת לכל הודעה אפשרית ב<math>{\mathcal X}^n</math>. בהינתן הודעה <math>x</math> ב<math>{\mathcal X}^n</math>, הערוץ פולט הודעה ב<math>\mathcal Y^\ast</math> הנדגמת מההתפלגות של <math>x</math>. בהינתן ערוץ, נרצה להגדיר את ה'''קיבולת''' (Capacity) שלו, מדד של כמות המידע שהערוץ מסוגל להעביר מבלי לפגום בו. ישנן שתי דרכים להגדיר קיבולת:
* הגדרה כקצב המקסימלי: נאמר שקצב מסוים <math>0 \leq R \leq 1</math> הוא '''בר-השגה''' (achievable), אם קיימת משפחה אינסופית של קודים, שכל קוד בה הוא עם קצב לפחות <math>R</math>, ובנוסף ההסתברות שפונקציית הקידוד מבצעת בו שגיאה הולך וקטן עד ש[[גבול של סדרה|שואף]] ל-0. אם כך, קיבולת הערוץ תוגדר על ידי הקצב המקסימלי שהוא בר-השגה:
{{יישור טקסט|שמאל|<math> C = \sup \{0 \leq R \leq 1 \; \vert \; R \mbox{ is achievable}\} </math>}}
* הגדרה ככמות המידע שהערוץ משאיר: עבור פונקציית קידוד כלשהי <math>E</math>, נסמן ב<math>X_E</math> את ה[[משתנה מקרי|משתנה המקרי]] שמתקבל מקידוד הודעה אקראית וב<math>Y_E</math> את פלט הערוץ על <math>X_E</math>. עבור שני משתנים אקראיים בדידים <math>Z_1, Z_2</math> נסמן ב<math>I(Z_1 ; Z_2)</math> את ה'''[[אינפורמציה הדדית|אינפורמציה ההדדית]]''' שלהם, מדד לכמות המידע ששניהם חולקים. קיבולת הערוץ תוגדר כך:
{{יישור טקסט|שמאל|<math> C = \max_E \{I(X_E ; Y_E)\} </math>}}

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

=== דוגמאות לערוצים ===
* ה'''ערוץ הסימטרי הבינארי''' (Binary Symmetric Channel), הנתון על ידי פרמטר <math>0 \leq p < 1/2</math> ומסומן <math>BSC_p</math>, מבצע פעולת החלפה עבור כל ביט. כלומר, עבור כל ביט בנפרד ובאופן בלתי תלוי, מחליף אותו (ממיר 0 ב-1, ו1 ב0) בהסתברות <math>p</math>.
* '''ערוץ מחיקה בינארי''' (Binary Erasure Channel), הנתון על ידי פרמטר <math>0 \leq p < 1</math> ומסומן <math>BEC_p</math>, מוחק כל ביט בהסתברות <math>p</math>, וכותב במקומו סימן כלשהו המסמן את המחיקה. לרוב סימן זה מסומן ב<math>?</math>.
* '''ערוץ השמטה בינארי''' (Binary Deletion Channel), הנתון על ידי פרמטר <math>0 \leq p < 1</math>, משמיט כל ביט בהסתברות <math>p</math>. על כן, אורך הפלט של הערוץ אינו קבוע ובוודאי אינו בהכרח האורך של הקלט המקורי של הערוץ, מה שמקשה מאוד על האנליזה של ערוץ זה. הבעיה של לקבוע את הקיבולת של ערוץ זה היא בעיה פתוחה<ref>{{צ-מאמר|מחבר=Mitzenmacher, Michael|שם=A survey of results for deletion channels and related synchronization channels|כתב עת=Probab. Surveys 6 (2009)|עמ=1-33|doi=10.1214/08-PS141|קישור=https://projecteuclid.org/euclid.ps/1247144661}}</ref>.

=== משפט הערוץ הרועש של שאנון ===
שאנון התעניין בחישוב הקיבולת של ערוץ, והצליח לחשב את הקיבולת של ערוץ סימטרי בינארי. '''משפט הערוץ הרועש של שאנון''' קובע כי לכל <math>0 \leq p < 1/2</math>, הקיבולת של הערוץ הבינארי <math>BSC_p</math> הוא <math>1 - H(p)</math>, כש<math>H(p)</math> היא [[אנטרופיה (סטטיסטיקה)|אנטרופיית שאנון]] של [[משתנה מקרי ברנולי]] עם הסתברות <math>p</math>:
{{יישור טקסט|שמאל|<math> H(p) = -p\log_2(p) - (1-p)\log_2(1-p) </math>}}

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

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

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

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

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

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

בעיה בסיסית ב[[סיבוכיות תקשורת]] היא השוואה בין מחרוזות. בבעיה זאת, [[אליס ובוב|אליס]] מקבלת מחרוזת אחת, בוב מקבל מחרוזת שנייה, ואליס ובוב רוצים - בעזרת תקשורת מינימלית ביניהם - לדעת האם שתי המחרוזות שוות. פתרון טריוויאלי יהיה שאליס תשלח את המחרוזת שלה לבוב, ובוב ישווה ביניהם. אך פתרון זה דורש כמות גדולה של תקשורת בין אליס ובוב (למעשה, פתרון זה הוא אופטימלי ללא שימוש ברנדומיות<ref>{{צ-ספר|שם=Communication Complexity: and Applications|קישור=https://www.cambridge.org/core/product/identifier/9781108671644/type/book|מו"ל=Cambridge University Press|שנת הוצאה=2020-01-31|ISBN=978-1-108-67164-4|מהדורה=|מחבר=Anup Rao, Amir Yehudayoff|מקום הוצאה=|עמ=22, משפט 1.14}}</ref>). אך בהינתן ולאליס ולבוב יש גישה לאקראיות פומבית, כל אחד מהם יכול לקודד את המחרוזת שלו עם קוד לתיקון שגיאות (אותו הקוד עבור אליס ובוב) ולהתייחס לאקראיות הפומבית כאינדקס של ביט בקוד. אליס תשלח לבוב רק את הביט שבאותו האינדקס בקידוד שלה, ובוב ישווה בין הביט שבאותו האינדקס בקידוד שלו עצמו ובין הביט שהגיע מאליס. הוא יקבע שהמחרוזות שוות אם הביטים שהושוו אכן שווים. אם המחרוזות שהיו לאליס ובוב מלכתחילה היו שוות, גם הקידודים שלהם יהיו שווים ובוב תמיד יצדוק. אחרת, ההסתברות של בוב לענות נכונה היא לפחות המרחק (היחסי) של הקוד. אם אליס ובוב יבחרו קוד עם מרחק גדול, ההסתברות שלהם להצליח תהיה גדולה, בעוד רק ביט אחד נשלח.

קודים הם האובייקט הבסיסי בהרבה בניות של [[משפט PCP|מערכות הוכחה הסתברותיות]] (Probabilistically Checkable Proofs){{הערה|S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems.Journal of the ACM, 45(3):501–555, 1998.}}{{הערה|S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization ofNP.Journal of the ACM, 45(1):70–122, 1998}}. בתחום של [[קושי קירוב]] (השקול לבניית מערכות הוכחה הסתברותיות{{הערה|U. Feige, S. Goldwasser, L. Lov ́asz, S. Safra, and M. Szegedy. Approximating clique is almost NP-complete.Journal of the ACM, 43(2):268–292, 1996}}), קודים משמשים לרוב כ"גדאדג'טים" ב[[רדוקציה חישובית|רדוקציות]] של קושי קירוב אופטימלי{{הערה|Johan Håstad. 2001. Some optimal inapproximability results. J. ACM 48, 4 (July 2001), 798–859. DOI:https://doi.org/10.1145/502090.502098}}{{הערה|Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. 2007. Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? SIAM J. Comput. 37, 1 (April 2007), 319–357. DOI:https://doi.org/10.1137/S0097539705447372}}.

ב[[דרנדומיזציה]], קודים משמשים לבנייה של אובייקטיביים פסאודו-רנדומיים כמו [[מחלץ רדנומיות|מחלצי רדנומיות]] (Randomness Extractors) {{אנ|Randomness Extractor}}{{הערה|Luca Trevisan. Extractors and pseudorandom generators.Journal of the ACM, 48(4):860–879,2001.}} ו[[התפלגויות עם הטיה קטנה]] (Small-Bias Distributions){{אנ|Small-bias sample space}}{{הערה|Naor, Joseph & Naor, Moni. (2001). Small-Bias Probability Spaces: Efficient Constructions and Applications. SIAM Journal on Computing. 22. 10.1145/100216.100244.}}{{הערה|A. Ben-Aroya and A. Ta-Shma, "Constructing Small-Bias Sets from Algebraic-Geometric Codes," 2009 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, GA, 2009, pp. 191-197, doi: 10.1109/FOCS.2009.44.}}. ידועים גם קשרים בין קודים לאובייקטים פסאודו-רנודמיים נוספים, למשל [[גרף מרחיב|גרפים מרחיבים]]{{הערה|M. Sipser and D. A. Spielman. Expander codes.IEEE Trans. Inform. Theory,42(6,part 1):1710–1722, 1996. Codes and complexity. MR1465731 (98d:94031)}}.

==ראו גם==
*[[תורת הקודים]]

== לקריאה נוספת ==
* להוכחות של הטענות המוזכרות על קידוד ערוץ של שאנון, ראו פרק 5 בסיכומי ההרצאות ה{{קישור כללי|כתובת=http://web.stanford.edu/class/ee376a/files/scribes/lecture_notes.pdf|הכותב=|כותרת=אלו|אתר=|תאריך=}}.

==קישורים חיצוניים==
* {{MathWorld}}

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{ערך טוב}}
[[קטגוריה:קודים לאיתור שגיאות ולתיקונן]]
[[קטגוריה:תורת הקודים]]
[[קטגוריה:תקשורת מחשבים]]