הצגת המקור של הדף "חסם סינגלטון"

ב[[תורת הקודים]], '''חסם סינגלטון''' הוא [[חסם (מתמטיקה)|חסם]] בסיסי המתאר עבור [[קוד תיקון שגיאות]] <math>\ C</math> את הקשר בין [[מרחק קוד|מרחק הקוד]] ([[מרחק המינג]] בין שתי המילים הקרובות ביותר) ובין אורך מילות הקוד ומספרן. החסם קרוי על שם ריצ'רד סינגלטון שפרסם אותו ואת מושג הקודים מופרדים מקסימלית ב-1964{{הערה|1={{cite journal | author=R.C. Singleton | title=Maximum distance q-nary codes | journal=IEEE Trans. Inf. Theory | volume=10 | pages=116–118 | year=1964 | doi=10.1109/TIT.1964.1053661 }} }}.
==הגדרת החסם והוכחתו==
לכל קוד לתיקון שגיאות <math>\ C</math> המכיל <math>\ M</math> מילות קוד שונות באורך <math>\ n</math> מעל אלפבית <math>\mathbb F</math> בגודל <math>\ q</math>, ובעל מרחק קוד <math>\ d</math> מתקיים:
<center><math>d \le n - \lceil \log_q M \rceil +1</math>.</center>

עבור [[קוד ליניארי]], <math>k= \lceil \log_q M\rceil</math> ולכן לכל קוד ליניארי <math>\ C=[n,k]</math> מתקיים:
<center><math>d\le n-k+1</math>.</center>

===הוכחת החסם===
החסם נובע מכך שכדי לקודד <math>\ M</math> מילים שונות באורך <math>\ n'</math> מעל אלפבית <math>\mathbb F</math> נדרש כי <math>\ q^{n'} \geq M </math>. אם מביטים על אוסף כלל המילים בקוד <math>\ C</math> כאשר מכל מילה מתעלמים מ-<math>\ d-1</math> האותיות הראשונות (כלומר, ה[[מוספית|סיפא]] של המילה באורך <math>\ n'=n-(d-1)</math> אותיות), עדיין יהיו כל <math>\ M</math> הסיפאות שונות זו מזו, כיוון ש[[מרחק קוד|מרחק הקוד]] <math>\ C</math> הוא לפחות <math>\ d</math>. מתקבל כי <math>\ q^{n - d +1} \geq M </math>.

==קודי MDS==
קוד בו מתקיים השוויון בחסם סינגלטון נקרא קוד מופרד מקסימלית (MDS - Maximum Distance Separable). דוגמאות לקודים מסוג זה:
* הקוד המלא (כלל המרחב <math>\mathbb F^n</math>) <math>[n,n,1]</math>
* [[קוד חזרות|קוד החזרות]] <math>[n,1,n]</math>
* [[קוד ריד-סולומון]] <math>[n,k,n-k+1]</math>

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

==הערות שוליים==
{{הערות שוליים}}
{{קצרמר|מדעי המחשב}}

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