פענוח רשימה

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

המושג הוצג לראשונה בידי פיטר אליאס ב-1957^[1].

השימוש הראשון של פענוח רשימה בתיאוריה של מדעי המחשב נמצא בידי עודד גולדרייך ולאוניד לוין ב-1989, כשבנו אלגוריתם לפענוח רשימה של קוד האדאמרד (אנ'), והשתמשו בו כדי לבנות מכל פונקציה חד-כיוונית, פונקציה חד-כיוונית עם סיבית קשה^[2]^[3]. מאז נמצאו שימושים רבים לפענוח רשימה בבניית מערכות הוכחה הסתברותיות^[4]^[5], בדרנדומיזציה^[6] ועוד.

הגדרה עריכה

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

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

חסם ג'ונסון עריכה

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

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

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

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

ראו גם עריכה

קישורים חיצוניים עריכה

הערות שוליים עריכה

^ Elias, Peter (1957). List Decoding for Noisy Channels.
^ O. Goldreich, L. Levin, "A hard-core predicate for all one-way functions", In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing (STOC), 1989
^ A. Akavia, S. Goldwasser and S. Safra, "Proving hard-core predicates using list decoding," 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., Cambridge, MA, USA, 2003, pp. 146-157, doi: 10.1109/SFCS.2003.1238189.
^ R. Raz & S. Safra (1997). A Sub-Constant Error-Probability Low-Degree Test and a Sub-Constant Error-Probability PCP Characterization of NP. In Proc. 29th ACM Symp. on Theory of Computing, 475–484.
^ Impagliazzo, Russell & Jaiswal, Ragesh & Kabanets, Valentine. (2009). Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification. SIAM J. Comput.. 39. 564-605. 10.1137/070683994.
^ Luca Trevisan. Extractors and pseudorandom generators.Journal of the ACM, 48(4):860–879,2001.

[1] Elias, Peter (1957). List Decoding for Noisy Channels.

[2] O. Goldreich, L. Levin, "A hard-core predicate for all one-way functions", In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing (STOC), 1989

[3] A. Akavia, S. Goldwasser and S. Safra, "Proving hard-core predicates using list decoding," 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., Cambridge, MA, USA, 2003, pp. 146-157, doi: 10.1109/SFCS.2003.1238189.

[4] R. Raz & S. Safra (1997). A Sub-Constant Error-Probability Low-Degree Test and a Sub-Constant Error-Probability PCP Characterization of NP. In Proc. 29th ACM Symp. on Theory of Computing, 475–484.

[5] Impagliazzo, Russell & Jaiswal, Ragesh & Kabanets, Valentine. (2009). Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification. SIAM J. Comput.. 39. 564-605. 10.1137/070683994.

[6] Luca Trevisan. Extractors and pseudorandom generators.Journal of the ACM, 48(4):860–879,2001.

[1]

[2]

[3]

[4]

[5]

[6]