חסם סינגלטון

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

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

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

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

ראו גם
 חסם פלוטקין
 חסם האמינג

הערות שוליים

קטגוריה:תורת הקודים