פתיחת התפריט הראשי

חסם סינגלטון

בתורת הקודים, חסם סינגלטון הוא חסם בסיסי המתאר עבור קוד תיקון שגיאות את הקשר בין מרחק הקוד (מרחק המינג בין שתי המילים הקרובות ביותר) ובין אורך מילות הקוד ומספרן. החסם קרוי על שם ריצ'רד סינגלטון שפרסם אותו ואת מושג הקודים מופרדים מקסימלית ב-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. 
  ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.