חסם פלוטקין הוא חסם על גודלו של קוד בינארי מאורך ומרחק קוד המקיים . חסם זה נקרא על שם מוריס פלוטקין.
במקרים בהם , חסם זה לרוב הדוק יותר מחסם המינג הרגיל.
טענת החסם
יהי קוד מאורך ובעל מרחק קוד .
מספר המילים M בקוד מקיים:
כאשר היא פונקציית הערך השלם.
הוכחה
נסמן ב- את מרחק המינג בין המילים . (כלומר, מספר המקומות בהם שונות שתי המילים) הוכחת החסם מתבססת על הערכת הסכום בשתי דרכים שונות:
- מצד אחד, יש אפשרויות בחירה עבור המילה , ו- אפשרויות בחירה עבור המילה . לכן, קיימים צמדי מילים. מאחר שהמרחק בין כל שתי מילות קוד הוא לפחות, נסיק:
- מצד שני, נתבונן במטריצה מגודל אשר שורותיה הן כל מילות הקוד של . נסמן ב- את מספר האפסים בעמודה ה-i של . עמודה זו מכילה, אם כן, אחדים. כל בחירה של 0 ושל 1 בעמודה זו תורמת 2 לסכום המרחקים הכולל. לכן:
נחלק את המשך ההוכחה לשני מקרים:
זוגי
במקרה זה, ערכו המקסימלי של כל איבר בסכום מימין מימין מתקבל עבור , ולכן:
- לכן, משילוב החסמים התחתון והעליון, נקבל:
- ושוויון זה שקול לאי השוויון:
- ומאחר ש-M זוגי, נוכל להסיק:
אי-זוגי
במקרה זה לעומת זאת, מקבל הסכום:
- אשר ערכו מקסימלי כאשר לכל , ולכן:
- ושנית, באמצעות שילוב אי השיוויונים מתקבל:
- ומבידוד M, נקבל:
- ומאחר ש-M מספר שלם:
בשני המקרים, קיבלנו את טענת החסם.
ראו גם