חסם סינגלטון

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בתורת הקודים, חסם סינגלטון הוא חסם בסיסי המתאר עבור קוד תיקון שגיאות \ C את הקשר בין מרחק הקוד (מרחק המינג בין שתי המילים הקרובות ביותר) ובין אורך מילות הקוד ומספרן. החסם קרוי על שם ריצ'רד סינגלטון שפרסם אותו ואת מושג הקודים מופרדים מקסימלית ב-1964[1].

הגדרת החסם והוכחתו[עריכת קוד מקור | עריכה]

לכל קוד לתיקון שגיאות \ C המכיל \ M מילות קוד שונות באורך \ n מעל אלפבית \mathbb F בגודל \ q, ובעל מרחק קוד \ d מתקיים:

d \le n - \lceil \log_q M \rceil +1.

עבור קוד לינארי, k= \lceil \log_q M\rceil ולכן לכל קוד לינארי \ C=[n,k] מתקיים:

d\le n-k+1.

הוכחת החסם[עריכת קוד מקור | עריכה]

החסם נובע מכך שכדי לקודד \ M מילים שונות באורך \ n' מעל אלפבית \mathbb F נדרש כי \ q^{n'} \geq M . אם מביטים על אוסף כלל המילים בקוד \ C כאשר מכל מילה מתעלמים מ-\ d-1 האותיות הראשונות (כלומר, הסיפא של המילה באורך \ n'=n-(d-1) אותיות), עדיין יהיו כל \ M הסיפאות שונות זו מזו, כיוון שמרחק הקוד \ C הוא לפחות \ d. מתקבל כי \ q^{n - d +1} \geq M .

קודי MDS[עריכת קוד מקור | עריכה]

קוד בו מתקיים השוויון בחסם סינגלטון נקרא קוד מופרד מקסימלית (MDS - Maximum Distance Separable). דוגמאות לקודים מסוג זה:

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ R.C. Singleton (1964). "Maximum distance q-nary codes". IEEE Trans. Inf. Theory 10: 116–118. doi:10.1109/TIT.1964.1053661. 
P Computer-science.png ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.