פענוח רשימה

בתורת הקודים, קוד לתיקון שגיאות נקרא ניתן לפענוח רשימה (List Decodable) אם בהינתן מילת קוד מורעשת, ניתן לשחזר ממנה רשימה קצרה של מילות קוד אפשריות כך שמובטח שאחת מהן היא מילת הקוד המקורית. זאת בהשוואה למובן הרגיל של פענוח, פענוח יחיד (Unique Decoding), בו משוחזרת מילת קוד אחת שחייבת להיות מילת הקוד המקורית. פענוח רשימה מאפשר פענוח גם בהינתן מספר גדול יותר של שגיאות מאשר שפענוח יחיד היה מאפשר, שיכול להגיע כמעט עד למרחק הקוד ממש. לפענוח רשימה שימושים רבים במדעי המחשב התאורטיים ובקריפטוגרפיה.

המושג הוצג לראשונה בידי פיטר אליאס ב-1957תבנית:הערה.

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

הגדרה

נאמר ש$C\subseteq {\mathrm{\Sigma }}^n$, קוד $[n,k{]}_q$ מעל אלפבית $\mathrm{\Sigma }$ בגודל $q$ הוא $(\rho ,L)$-ניתן-לפענוח-רשימה אם לכל $w\in {\mathrm{\Sigma }}^n$ מתקיים שמספר מילות הקוד הקרובות אל $w$ עד כדי מרחק $\rho n$, הוא לכל היותר $L$, כלומר: $|\{x\in C|d(x,w)\le \rho n\}|\le L$, כאשר $d(x,w)$ הוא מרחק המינג (Hamming Distance) בין $x$ ו$w$.

לדוגמה, כל קוד $[n,k,\delta n{]}_q$ הוא $(\frac{\delta }{2},1)$-ניתן-לפענוח-רשימה.

חסם ג'ונסון

ראינו אם כן שניתן להפוך כל קוד עם מרחק יחסי $\delta$ לקוד הניתן-לפענוח-רשימה עם אורך רשימה קצר (אורך הרשימה היה אחד, למעשה), אך מספר השגיאות שיכולנו לתקן היה רק $\frac{\delta }{2}$. חסם ג'ונסון (Johnson Bound) מבטיח חסם טוב יותר על מספר השגיאות, בעוד משמר את אורך הרשימה קטן (פולינומי ב$n$).

טענה (חסם ג'ונסון). בהינתן קוד $C\subseteq {\mathrm{\Sigma }}^n$ עם מרחק יחסי $\delta$, $C$ הוא $(\rho ,L)$-ניתן-לפענוח-רשימה עבור $\rho =1-\sqrt{1-\delta }$ ו$L=n$.

שימו לב שהחסם המובטח על מספר השגיאות אותן ניתן לתקן תמיד גדול יותר מהחסם הטריוויאלי של $\frac{\delta }{2}$.

חסם ג'ונסון אינו מבטיח את החסם הטוב ביותר. למשל, תוצאה מיידית של האלגוריתם של גולדרייך-לוין (שהוזכר מעלה) היא שניתן לקבל פענוח רשימה לקוד האדאמרד אפילו כמעט עד כדי המרחק של הקוד (שהוא $\frac{1}{2}$). ובמדויק, לכל פולינום $p$, קוד האדאמרד הוא $(\frac{1}{2}-\frac{1}{p(n)},poly(n))$-ניתן-לפענוח-רשימה.

ראו גם

• קוד לתיקון שגיאות
• סיבית קשה

קישורים חיצוניים

• מאמר סקירה על פענוח רשימה
• הוכחה של חסם ג'ונסון
• עוד על הקשר בין פענוח רשימה ודרנדומיזציה