חסם פלוטקין

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

טענת החסם[עריכת קוד מקור | עריכה]

יהי קוד מאורך ובעל מרחק קוד .

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

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

הוכחה[עריכת קוד מקור | עריכה]

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

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

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

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

זוגי[עריכת קוד מקור | עריכה]

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

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

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

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

אי-זוגי[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

ראו גם[עריכת קוד מקור | עריכה]