חסם סינגלטון

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

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

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

לכל קוד לתיקון שגיאות המכיל מילות קוד שונות באורך מעל אלפבית בגודל , ובעל מרחק קוד מתקיים:

.

עבור קוד לינארי, ולכן לכל קוד לינארי מתקיים:

.

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

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

קודי 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.svg ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.