חסם סינגלטון

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

הגדרת החסם והוכחתו

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

$d\leq n-\lceil \log _{q}M\rceil +1$.

עבור קוד ליניארי, $k=\lceil \log _{q}M\rceil$ ולכן לכל קוד ליניארי $\ C=[n,k]$ מתקיים:

$d\leq 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). דוגמאות לקודים מסוג זה:

• הקוד המלא (כלל המרחב $\mathbb {F} ^{n}$) $[n,n,1]$
• קוד החזרות $[n,1,n]$
• קוד ריד-סולומון $[n,k,n-k+1]$

ראו גם

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

הערות שוליים

ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.