חסם סינגלטון

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

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

לכל קוד לתיקון שגיאות $C$ המכיל $M$ מילות קוד שונות באורך $n$ מעל אלפבית $\mathbb{𝔽}$ בגודל $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}^{\prime }$ מעל אלפבית $\mathbb{𝔽}$ נדרש כי ${q}^{n^{\prime }}\ge M$. אם מביטים על אוסף כלל המילים בקוד $C$ כאשר מכל מילה מתעלמים מ-$d-1$ האותיות הראשונות (כלומר, הסיפא של המילה באורך ${n}^{\prime }=n-(d-1)$ אותיות), עדיין יהיו כל $M$ הסיפאות שונות זו מזו, כיוון שמרחק הקוד $C$ הוא לפחות $d$. מתקבל כי ${q}^{n-d+1}\ge M$.

קודי MDS

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

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

ראו גם

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

הערות שוליים

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