חסם סינגלטון

בתורת הקודים, חסם סינגלטון הוא חסם בסיסי המתאר עבור קוד תיקון שגיאות $ \ 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] $

ראו גם

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

הערות שוליים

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