חסם פלוטקין

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

במקרים בהם , חסם זה לרוב הדוק יותר מחסם המינג הרגיל.

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

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


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

 הוכחה 
נסמן ב- את מרחק המינג בין המילים . (כלומר, מספר המקומות בהם שונות שתי המילים) הוכחת החסם מתבססת על הערכת הסכום  בשתי דרכים שונות:

מצד אחד, יש  אפשרויות בחירה עבור המילה , ו- אפשרויות בחירה עבור המילה . לכן, קיימים  צמדי מילים. מאחר שהמרחק בין כל שתי מילות קוד הוא  לפחות, נסיק:

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

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

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

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

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

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

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

אשר ערכו מקסימלי כאשר  לכל  , ולכן:

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

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

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

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

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

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