חסם פלוטקין

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

במקרים בהם $2d>n$, חסם זה לרוב הדוק יותר מחסם המינג הרגיל.

טענת החסם

יהי $\ C$ קוד מאורך $\ n$ ובעל מרחק קוד $\ d$.

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

הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle M\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor }

כאשר הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \left\lfloor ~\right\rfloor } היא פונקציית הערך השלם.

הוכחה

נסמן ב-הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \ d(x,y)} את מרחק המינג בין המילים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x,y} . (כלומר, מספר המקומות בהם שונות שתי המילים) הוכחת החסם מתבססת על הערכת הסכום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{x,y \in C} d(x,y)} בשתי דרכים שונות:

מצד אחד, יש $M$ אפשרויות בחירה עבור המילה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x} , ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ M-1} אפשרויות בחירה עבור המילה $\ y$. לכן, קיימים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ M(M-1)} צמדי מילים. מאחר שהמרחק בין כל שתי מילות קוד הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ d} לפחות, נסיק:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{x,y \in C} d(x,y) \geq M(M-1) d }

מצד שני, נתבונן במטריצה $\ A$ מגודל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ M \times n} אשר שורותיה הן כל מילות הקוד של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ C} . נסמן ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i} את מספר האפסים בעמודה ה-i של $\ A$. עמודה זו מכילה, אם כן, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ M-s_i} אחדים. כל בחירה של 0 ושל 1 בעמודה זו תורמת 2 לסכום המרחקים הכולל. לכן:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{x,y \in C} d(x,y) = \sum_{i=1}^n 2s_i (M-s_i)}

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

$M$ זוגי

במקרה זה, ערכו המקסימלי של כל איבר בסכום מימין מימין מתקבל עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i = M/2} , ולכן:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M(M-1) d \leq \frac{1}{2} n M^2}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M \leq \frac{2d}{2d-n}}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M \leq 2 \lfloor \frac{d}{2d-n} \rfloor }

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} אי-זוגי

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^n 2s_i (M-s_i)}

אשר ערכו מקסימלי כאשר $s_{i}={\frac {M\pm 1}{2}}$ לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i} , ולכן:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{x,y \in C} d(x,y) \leq \frac{1}{2} n (M^2-1)}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 מספר שלם:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M \leq \lfloor \frac{2d}{2d-n} - 1 \rfloor = \lfloor \frac{2d}{2d-n} \rfloor -1 \leq 2 \lfloor \frac{d}{2d-n} \rfloor }

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

ראו גם

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