חסם פלוטקין

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

חסם פלוטקין הוא חסם על גודלו של קוד בינארי מאורך \ 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} n M^2

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

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

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

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