חסם פלוטקין

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

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

טענת החסם

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

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

$M\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor$

כאשר $\left\lfloor ~\right\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)\geq 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)\leq \sum _{i=1}^{n}2{\frac {M}{2}}(M-{\frac {M}{2}})={\frac {1}{2}}nM^{2}$

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

$M(M-1)d\leq {\frac {1}{2}}nM^{2}$

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

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

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

$M\leq 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)\leq {\frac {1}{2}}n(M^{2}-1)$

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

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

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

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

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

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

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

ראו גם

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