הצגת המקור של הדף "חסם פלוטקין"

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

במקרים בהם <math>2d > n</math>, חסם זה לרוב הדוק יותר מ[[חסם המינג]] הרגיל.

== טענת החסם ==
יהי <math>\ C</math> קוד מאורך <math>\ n</math> ובעל מרחק קוד <math>\ d</math>.

מספר המילים M בקוד <math>\ C</math> מקיים:
:<math> M \leq 2 \left\lfloor\frac{d}{2d-n}\right\rfloor </math>
 
כאשר <math> \left\lfloor ~ \right\rfloor</math> היא [[פונקציית הערך השלם]].

== הוכחה ==
נסמן ב-<math>\ d(x,y)</math> את [[מרחק המינג]] בין המילים <math>\ x,y</math>. (כלומר, מספר המקומות בהם שונות שתי המילים) הוכחת החסם מתבססת על הערכת הסכום <math>\sum_{x,y \in C}  d(x,y)</math> בשתי דרכים שונות:

:מצד אחד, יש <math> M</math> אפשרויות בחירה עבור המילה <math>\ x</math>, ו-<math>\ M-1</math> אפשרויות בחירה עבור המילה <math>\ y</math>. לכן, קיימים <math>\ M(M-1)</math> צמדי מילים. מאחר שהמרחק בין כל שתי מילות קוד הוא <math>\ d</math> לפחות, נסיק:
<div style="text-align: left;">
<math> \sum_{x,y \in C} d(x,y) \geq M(M-1) d </math>
</div>

:מצד שני, נתבונן במטריצה <math>\ A</math> מגודל <math>\ M \times n</math> אשר שורותיה הן כל מילות הקוד של <math>\ C</math>. נסמן ב-<math>s_i</math> את מספר האפסים בעמודה ה-i של <math>\ A</math>. עמודה זו מכילה, אם כן, <math>\ M-s_i</math> אחדים. כל בחירה של 0 ושל 1 בעמודה זו תורמת 2 לסכום המרחקים הכולל. לכן:
<div style="text-align: left;">
<math> \sum_{x,y \in C} d(x,y) = \sum_{i=1}^n 2s_i (M-s_i)</math>
</div>

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

=== <math>M</math> זוגי ===
במקרה זה, ערכו המקסימלי של כל איבר בסכום מימין מתקבל עבור <math>s_i = M/2</math>, ולכן:
<div style="text-align: left;">
<math> \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</math>
</div>

:לכן, משילוב החסמים התחתון והעליון, נקבל:
<div style="text-align: left;">
<math> M(M-1) d \leq  \frac{1}{2} n M^2</math>
</div>

:ושוויון זה שקול לאי השוויון:
<div style="text-align: left;">
<math> M \leq \frac{2d}{2d-n}</math>
</div>

:ומאחר ש-M זוגי, נוכל להסיק:
<div style="text-align: left;">
<math> M \leq 2 \lfloor \frac{d}{2d-n} \rfloor </math>
</div>

=== <math>M</math> אי-זוגי ===
במקרה זה לעומת זאת, מקבל הסכום:
<div style="text-align: left;">
<math>\sum_{i=1}^n 2s_i (M-s_i)</math>
</div>

:אשר ערכו מקסימלי כאשר <math>s_i = \frac{M \pm 1}{2}</math> לכל  <math>\ i</math>, ולכן:
<div style="text-align: left;">
<math> \sum_{x,y \in C} d(x,y) \leq \frac{1}{2} n (M^2-1)</math>
</div>

:ושנית, באמצעות שילוב אי השוויונים מתקבל:
<div style="text-align: left;">
<math> M(M-1) d \leq \frac{1}{2} n (M^2-1) = \frac{1}{2} n (M-1)(M+1) </math>
</div>

:ומבידוד M, נקבל:
<div style="text-align: left;">
<math> M \leq  \frac{n}{2d-n} = \frac{2d}{2d-n} - 1</math>
</div>

:ומאחר ש-M מספר שלם:
<div style="text-align: left;">
<math> M \leq \lfloor \frac{2d}{2d-n} - 1 \rfloor = \lfloor \frac{2d}{2d-n} \rfloor -1 \leq 2 \lfloor \frac{d}{2d-n} \rfloor </math>
</div>

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

==ראו גם==
* [[חסם סינגלטון]]
* [[חסם האמינג]]

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