הצגת המקור של הדף "קוד קונבולוציה"

ב[[תקשורת]], '''קוד קונבולוציה''' הוא סוג של [[קוד לתיקון שגיאות]] שיוצר בדיקות זוגיות באמצעות [[קונבולוציה]] של [[פולינום]] עם זרם הנתונים. פיענוחם של קודי-קונבולוציה אפשרי בעזרת פרישת סריג פיענוח, לפי [[אלגוריתם ויטרבי]]. אלגוריתם זה מאפשר פיענוח [[נראות מרבית]] בצורה "רכה" (soft-decision) ב[[סיבוכיות]] סבירה.

יכולת זו הקנתה לקודי הקונבולוציה את יתרונם הגדול על-פני קודי הבלוק, שפוענחו באופן מסורתי באופן "קשה" (hard-decoding), שמשיג ביצועים נחותים מול פיענוח "רך". יתרון זה הפך אותם פופולריים במיוחד, אף שהיום הם נחשבים 'פחותים' מול קודי בלוק חזקים כדוגמת [[LDPC]].

קודי קונבולוציה מאופיינים על-פי רוב בשלושה גדלים מרכזיים: n,k,K. להבדיל מקודי בלוק, ל-n,k אין משמעות של גודל הבלוק או של גודל המילה, מאחר שהמידע מקודד (ומפוענח) באופן זרמי ורציף. בכל זאת, n,k הם גודלי הבסיס המאפיינים את קצב המקודד, ו-K (מכונה "Constraint Length") הוא עומק הזיכרון של המקודד.

טכניקה נפוצה לייצר קוד קונבולוציה בקצב גבוה מ-0.5 היא [[ניקוב (קוד לתיקון שגיאות)|לנקב]] קוד נתון בקצב 0.5, פשוט על ידי קידוד זרם המידע בקצב 0.5 ו'מחיקת' חלק מזרם המידע היוצא. כך למשל, קידוד מידע בקצב 0.5 ואז 'מחיקה' של 3 ביטים מכל 14 תייצר קוד בקצב 7/11.

== היסטוריה ==
קודי קונבולוציה הוצגו לראשונה בשנת [[1955]] על ידי פיטר אליאס. ב-[[1967]] [[אנדרו ויטרבי]] הציג אלגוריתם לפיענוח קודים אלו באופן המשיג את ביצועי מפענח ה[[נראות מרבית|נראות המרבית]] (Maximum Likelihood) ב[[סיבוכיות]] סבירה, באמצעות סריג (trellis) אינווריאנטי בזמן. אלגוריתם זה נקרא [[אלגוריתם ויטרבי]], ומאוחר יותר נודעה לו משמעות רחבה יותר בכמה נושאים נוספים. מאוחר יותר פותחו אלגוריתם נוספים מבוססי סריג דומה, הבולט שבהם הוא [[BCJR]].

כיום, קודי קונבולוציה נמצאים בשימוש במערכות תקשורת רבות, לרבות תקשורת [[לוויין|לוויינים]], שידורי [[סלולר]] ועוד רבים. פעמים רבות קודי קונבולוציה משמשים כאחד הרכיבים בשרשרת קודים לתיקון שגיאות, לרוב בסמוך ל[[קוד ריד-סולומון]] (RS). בתקופה שלפני גילוי [[קוד טורבו|קודי הטורבו]], שילוב זה בין קודי קונבולוציה ובין קודי RS היה הקרוב ביותר להשיג את [[חסם שאנון]] להעברת אינפורמציה בערוץ.

== קידוד ופיענוח ==
[[קובץ:Conv Coder 213.png|ממוזער|שמאל|250px|סכמטיקה של קידוד קונבולוציה]]
=== קצב 0.5 - קידוד 'קלאסי' ===
קוד 'קלאסי' בקצב 0.5 מוגדר על ידי שני פולינומים, <math> p_1(D)</math> ו-<math> p_2(D)</math>.

הבסיס של מקודד קונבולוציה מורכב מ-(K-1) [[אוגר (מחשבים)|אוגרים]], כאשר כל אחד אוגר ביט אחד. יחד עם ביט המידע הנוכחי, בכל רגע נתון האוגרים מכילים את K הביטים האחרונים שהתקבלו בזרם המידע. בכל נקודת זמן מחשבים את תוצאת הקונבולוציה בין כל אחד מהפולינומים לבין K הביטים הללו. למשל, עבור פולינום <math>\ p_1(D)=1+D+D^4</math>, תוצאת הקונבולוציה של הפולינום בזמן <math>\ n</math> תהיה שווה ל-<math>\ x[n] \oplus x[n-1] \oplus x[n-4]</math>.

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

למשל, עבור זרם מידע <math>\ x[n]</math> ופולינומים:

<math>\ p_1(D)=1+D+D^3</math>

<math>\ p_2(D)=1+D^2+D^5</math>

נקבל שני מוצאי ערוץ בכל נקודת זמן:

<math> y[m]=x[n] \oplus x[n-1] \oplus x[n-3]</math>

<math> y[m+1]=x[n] \oplus x[n-2] \oplus x[n-5]</math>.

כך, נשים לב שעבור כל ביט בזרם הכניסה יתקבלו שני ביטים בזרם המוצא - כלומר אכן קיבלנו יתירות של קצב 0.5.

=== קידוד 'קלאסי' כללי ===
במצב הכללי, כלומר עבור קוד קונבולוציה קלאסי עם פרמטרים n,k, נגדיר מטריצה <math> G \in M_{kxn}</math> שבה <math>\ G_{i,j}</math> הוא פולינום המתאר את התלות של המוצא ה-j של המקודד בזרם-הכניסה ה-i.

=== ניקוב ===
כאמור לעיל, דרך פרקטית יותר לייצר קוד קונבולוציה בקצב גבוה מ-0.5 היא על ידי הגדרת תבנית ניקוב על קוד בקצב 0.5. כלומר, בהינתן קוד בקצב 0.5, תבנית ניקוב בעלת d מחיקות מתוך r איברים תייצר קוד שקול בקצב <math>\ \frac{1}{2 \cdot \frac{d}{r}} = \frac{r}{2\cdot d}</math>.

=== פיענוח ===
פיענוחם של קודי קונבולוציה נעשה פשוט יחסית עם פרסומו של [[אלגוריתם ויטרבי]], המאפשר פיענוח "קשה" או "רך". פיתוח משמעותי שנעשה לו, [[BCJR]], מאפשר להוציא גם מוצאים רכים מהמפענח, כלומר על כל ביט במוצא מתקבלת גם הערכה של אמינות הביט.

== קישורים חיצוניים ==
* [https://www.mathworks.com/help/comm/ref/convolutionalencoder.html מידע באתר MATLAB]

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