קוד LDPC

איור של קוד LDPC

בתורת המידע קוד Low-Density Parity-Check) LDPC) הוא קוד תיקון שגיאות ליניארי, המשמש להעברת מידע מעל ערוץ רועש, הקוד מיוצר באמצעות גרף דו-צדדי דליל.

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

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

יישומים

• 10GBase-T Ethernet (802.3an)
• G.hn/G.9960 (ITU-T Standard for networking over power lines, phone lines and coaxial cable)
• DVB-S2 (Digital video broadcasting)
• WiMAX (IEEE 802.16e standard for microwave communications)

ראו גם

• תורת הקודים
• תורת הגרפים
• קוד ליניארי

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

• The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, discusses LDPC codes in Chapter 47.
• Tutorial on LDPC codes and Gallager's original paper (re-typeset)
• [1] LDPC Codes: An Introduction
• LDPC codes and performance results
• Online density evolution for LDPC codes
• LDPC Codes – a brief Tutorial (by Bernhard Leiner, 2005)

• מימושים עבור מקודד, מפענח וסימולציה של קוד LDPC:
  • Binary LDPC codes in C
  • Binary LDPC codes for Python (core algorithm in C)
  • LDPC codes over GF(q) in MATLAB
  • LDPC encoder and LDPC decoder in MATLAB

הערות שוליים

1. Sarah J. Johnson, [http://sigpromu.org/sarah/SJohnsonLDPCintro.pdf Introducing Low-Density Parity-Check Codes] (ארכיון)

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