קוד קונבולוציה

בתקשורת, קוד קונבולוציה הוא סוג של קוד לתיקון שגיאות שיוצר בדיקות זוגיות באמצעות קונבולוציה של פולינום עם זרם הנתונים. פיענוחם של קודי-קונבולוציה אפשרי בעזרת פרישת סריג פיענוח, לפי אלגוריתם ויטרבי. אלגוריתם זה מאפשר פיענוח ניראות מרבית בצורה "רכה" (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 היה הקרוב ביותר להשיג את חסם שאנון להעברת אינפורמציה בערוץ.

קידוד ופיענוח

סכמטיקה של קידוד קונבולוציה

קצב 0.5 - קידוד 'קלאסי'

קוד 'קלאסי' בקצב 0.5 מוגדר על ידי שני פולינומים, $p_{1}(D)$ ו-$p_{2}(D)$.

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

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

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

$\ p_{1}(D)=1+D+D^{3}$

$\ p_{2}(D)=1+D^{2}+D^{5}$

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

$y[m]=x[n]\oplus x[n-1]\oplus x[n-3]$

$y[m+1]=x[n]\oplus x[n-2]\oplus x[n-5]$.

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

קידוד 'קלאסי' כללי

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

ניקוב

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

פיענוח

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

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

• מידע באתר MATLAB

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

25819353קוד קונבולוציה