חסם פלוטקין

חסם פלוטקין הוא חסם על גודלו של קוד בינארי מאורך $n$ ומרחק קוד $d$ המקיים $2d>n$. חסם זה נקרא על שם מוריס פלוטקין.

במקרים בהם $2d>n$, חסם זה לרוב הדוק יותר מחסם המינג הרגיל.

טענת החסם

יהי $C$ קוד מאורך $n$ ובעל מרחק קוד $d$.

מספר המילים M בקוד $C$ מקיים:

$M\le 2\lfloor \frac{d}{2d-n}\rfloor$

כאשר $\lfloor \rfloor$ היא פונקציית הערך השלם.

הוכחה

נסמן ב-$d(x,y)$ את מרחק המינג בין המילים $x,y$. (כלומר, מספר המקומות בהם שונות שתי המילים) הוכחת החסם מתבססת על הערכת הסכום $\sum _{x,y\in C}d(x,y)$ בשתי דרכים שונות:

מצד אחד, יש $M$ אפשרויות בחירה עבור המילה $x$, ו-$M-1$ אפשרויות בחירה עבור המילה $y$. לכן, קיימים $M(M-1)$ צמדי מילים. מאחר שהמרחק בין כל שתי מילות קוד הוא $d$ לפחות, נסיק:

$\sum _{x,y\in C}d(x,y)\ge M(M-1)d$

מצד שני, נתבונן במטריצה $A$ מגודל $M\times n$ אשר שורותיה הן כל מילות הקוד של $C$. נסמן ב-$s_i$ את מספר האפסים בעמודה ה-i של $A$. עמודה זו מכילה, אם כן, $M-s_i$ אחדים. כל בחירה של 0 ושל 1 בעמודה זו תורמת 2 לסכום המרחקים הכולל. לכן:

$\sum _{x,y\in C}d(x,y)=\sum _{i=1}^{n}2s_i(M-s_i)$

נחלק את המשך ההוכחה לשני מקרים:

$M$ זוגי

במקרה זה, ערכו המקסימלי של כל איבר בסכום מימין מימין מתקבל עבור $s_i=M/2$, ולכן:

$\sum _{x,y\in C}d(x,y)\le \sum _{i=1}^{n}2\frac{M}{2}(M-\frac{M}{2})=\frac{1}{2}n{M}^2$

לכן, משילוב החסמים התחתון והעליון, נקבל:

$M(M-1)d\le \frac{1}{2}n{M}^2$

ושוויון זה שקול לאי השוויון:

$M\le \frac{2d}{2d-n}$

ומאחר ש-M זוגי, נוכל להסיק:

$M\le 2\lfloor \frac{d}{2d-n}\rfloor$

$M$ אי-זוגי

במקרה זה לעומת זאת, מקבל הסכום:

$\sum _{i=1}^{n}2s_i(M-s_i)$

אשר ערכו מקסימלי כאשר $s_i=\frac{M\pm 1}{2}$ לכל $i$, ולכן:

$\sum _{x,y\in C}d(x,y)\le \frac{1}{2}n(M^2-1)$

ושנית, באמצעות שילוב אי השיוויונים מתקבל:

$M(M-1)d\le \frac{1}{2}n(M^2-1)=\frac{1}{2}n(M-1)(M+1)$

ומבידוד M, נקבל:

$M\le \frac{n}{2d-n}=\frac{2d}{2d-n}-1$

ומאחר ש-M מספר שלם:

$M\le \lfloor \frac{2d}{2d-n}-1\rfloor =\lfloor \frac{2d}{2d-n}\rfloor -1\le 2\lfloor \frac{d}{2d-n}\rfloor$

בשני המקרים, קיבלנו את טענת החסם.

ראו גם

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

חסם_פלוטקין13892376Q1476195