הצגת המקור של הדף "פענוח רשימה"

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

המושג הוצג לראשונה בידי [[פיטר אליאס]] ב-1957{{הערה|Elias, Peter (1957). List Decoding for Noisy Channels.}}.

השימוש הראשון של פענוח רשימה בתיאוריה של [[מדעי המחשב]] נמצא בידי [[עודד גולדרייך]] ו[[לאוניד לוין]] ב-1989, כשבנו אלגוריתם לפענוח רשימה של [[קוד האדאמרד]] {{אנ|Hadamard Code}}, והשתמשו בו כדי לבנות מכל [[פונקציה חד-כיוונית]], פונקציה חד-כיוונית עם [[סיבית קשה]]{{הערה|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.}}. מאז נמצאו שימושים רבים לפענוח רשימה בבניית [[משפט PCP|מערכות הוכחה הסתברותיות]]{{הערה|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.}} ועוד.

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

לדוגמה, כל קוד <math>[n,k, \delta n]_q</math> הוא <math>\left(\frac \delta 2, 1\right)</math>-ניתן-לפענוח-רשימה.

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

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

שימו לב שהחסם המובטח על מספר השגיאות אותן ניתן לתקן תמיד גדול יותר מהחסם הטריוויאלי של <math>\frac \delta 2</math>.

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

== ראו גם ==
* [[קוד לתיקון שגיאות]]
* [[סיבית קשה]]

== קישורים חיצוניים==
* [https://madhu.seas.harvard.edu/papers/2000/ifip.pdf מאמר סקירה על פענוח רשימה]
* [https://sites.math.rutgers.edu/~sk1233/courses/codes-S16/lec7.pdf הוכחה של חסם ג'ונסון]
* [https://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Lecture5.pdf עוד על הקשר בין פענוח רשימה ודרנדומיזציה]

== הערות שוליים ==
{{הערות שוליים|יישור=שמאל}}

[[קטגוריה:קודים לאיתור שגיאות ולתיקונן]]