Düşük Yoğunluklu Parite Kontrol Kodları (LDPC)
- Ortaya koyan
- Robert Gallager
- Yıl
- 1962
- Tür
- linear error-correcting code
- Aile
- Coding theory
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Robert Gallager tarafından 1962'de icat edilen ve 1990'larda MacKay tarafından yeniden keşfedilen LDPC kodları, seyrek parite kontrol matrisleri ile tanımlanan doğrusal hata düzeltme kodlarıdır.
İteratif inanç yayılımı kod çözme ile Shannon sınırına 0.4 dB içinde performans gösterirler ve modern kablosuz iletişim (WiFi-6, 5G NR, Dijital Televizyon Yayını) için standart haline gelmişlerdir. Turbo kodların aksine, LDPC kodları daha zarif bir grafik teorik yapısına ve daha olgun bir teorik analize sahiptir.
Yöntemin mantığı
Standart doğrusal kodlar, kod çözmeyi hesaplama açısından yoğun hale getiren yoğun parite kontrol matrisleri kullanır. LDPC kodları bunu tersine çevirir: parite kontrol matrisi seyrektir (girdilerin çoğu sıfırdır), bu nedenle her parite kontrolü yalnızca birkaç bitten oluşur. Alıcıda, değişken düğümler iletilen bitleri ve kontrol düğümleri parite kısıtlamalarını temsil eden iki parçalı bir grafik oluşturulur. Kod çözme, bu grafikte iteratif mesaj geçişi haline gelir: her değişken düğüm komşularından bilgi toplar, bit değeri hakkındaki inancını günceller ve rafine edilmiş tahminleri geri gönderir. Seyreklik, hızlı yakınsama ve Shannon'a yakın performansı garanti eder.
Tarih
Gallager, LDPC kodlarını 1962'de icat etti, ancak teori pratik uygulamaların gerisinde kaldı. 1995'te MacKay onları yeniden keşfetti ve simülasyonlar aracılığıyla Shannon'a yakın performanslarını gösterdi. 2000'lerde yapılan kapsamlı araştırmalar, verimli kodlama, kod çözme ve grafik oluşturma algoritmaları geliştirdi. LDPC kodları, daha iyi performansları ve daha temiz yapıları nedeniyle yeni sistemlerde turbo kodlardan daha yaygın hale gelerek WiFi-6 (802.11ax, 2021) ve 5G NR standardında (2018) kabul edildi.
Ne zaman kullanılır?
LDPC kodları, daha iyi performans ve daha basit mimarileri nedeniyle modern sistemlerde turbo kodlara tercih edilir. Geniş SNR aralıkları için LDPC kullanın (eşik uçurumu yok); düşükten yükseğe SNR'ye kadar iyi çalışırlar. LDPC, WiFi-6, uydu ve 5G NR için standarttır. Yalnızca eski uyumluluk turbo kodları gerektiriyorsa LDPC'den kaçının. LDPC, kod yapısı ayrılabilir olduğundan çok kısa paketler (>30 bit) için de uygundur.
Sınırlar ve dikkat edilmesi gerekenler
- Grafik yapısı ve matris depolama, çok uzun kodlar (>10k bit) için karmaşık hale gelir
- Performans, küçük ölçekli grafik yapılarına (çevre uzunlukları, absorbe edici kümeler) duyarlıdır; dikkatli tasarım gerektirir
- İnanç yayılımı döngülü grafik varsayar, ancak grafiklerde döngüler vardır; optimal çözüme yakınsama garanti edilmez
- Kod çözme gecikmesi (iterasyonlar), SNR ile logaritmik olarak artar; bazı klasik kodlar gibi sıfır gecikmeli değildir
- Mesajların nicemlenmesi (sabit noktalı donanımda) performansı etkiler; dikkatli bit tahsisi gerekir
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Shannon sınırına 0.4 dB içinde performans (turbo kodlardan biraz daha iyi)
- Turbo kodlara göre daha basit grafik teorik yapısı; daha temiz teorik analiz
- İteratif kod çözme, eşik benzeri davranışları önler (turbo kodların aksine)
- Grafik yapısı aracılığıyla esnek kod tasarımı; belirli uygulamalara uyum sağlamak kolaydır
- Verimli paralel kod çözme donanımı; mesaj geçişi VLSI/GPU uygulamalarına uygundur
- Hem uzun hem de orta derecede kısa kelimeler için iyi çalışır
Uygulama alanları
- WiFi-6 (802.11ax): LDPC'nin güvenilir veri iletimi sağladığı yüksek verimli kablosuz yerel alan ağları
- 5G NR: 4G'deki turbo kodların yerini alan hem veri hem de kontrol kanalları için kanal kodlaması
- Uydu iletişimi: dijital televizyon yayını (DVB-S2) ve uzun kelimeli LDPC kullanan derin uzay görevleri
- Güç hattı iletişimi (PLC): gürültülü elektrik şebekeleri üzerinden sağlam veri iletimi
- Flaş bellek sistemleri: sık yenileme nedeniyle aşınma olmadan NAND flaş depolama için hata düzeltme
Nasıl çalışır?
Nasıl çalışır?
Bilgi bitleri seyrek bir parite kontrol matrisi H kullanılarak kodlanır; kodlanmış bitler H*c = 0 (mod 2) denkleminin çözümüdür, burada c kelime (codeword) anlamına gelir.
Parite kontrol matrisi H, seyrek olacak şekilde yapılandırılmıştır (örneğin, her satır/sütun sabit düşük ağırlıkta 3-5'tir). Bu yapı, verimli kodlama için kullanılır.
Kodlanmış bitler gürültülü bir kanal üzerinden iletilir; alınan bitler yumuşak değerlerdir (olasılık oranları veya log-olasılık oranları).
İki parçalı bir grafik oluşturulur: sol düğümler = değişken düğümler (bitler), sağ düğümler = kontrol düğümleri (parite denklemleri). Kenarlar, değişkenleri yer aldıkları kontrollere bağlar.
İteratif inanç yayılımı: değişken düğümler kontrol düğümlerinden gelen mesajları toplar, bit tahminlerini günceller ve rafine edilmiş mesajları geri gönderir. İterasyonlardan sonra, sert kararlar verilir; parite kontrolleri sağlanırsa, kod çözme başarılı olur.
Sık yapılan hatalar
- Kısa döngülere sahip kötü tasarlanmış seyrek bir grafik kullanmak; kısa döngüler inanç yayılımının salınım yapmasına neden olur
- Yakınsama ötesinde aşırı iterasyon yapmak; gereksiz iterasyonlar iyileştirme olmadan güç israf eder
- Toplam-toplam kod çözmenin, toplam-çarpım kadar iyi olduğunu varsaymak; yaklaşımlar, özellikle düşük SNR'de performans kaybına neden olur
- Sonlu uzunluk etkilerini göz ardı etmek; asimptotik analiz için tasarlanmış grafikler kısa paketlerde yetersiz performans gösterebilir
- Donanım uygulamasında nicemlemeyi hesaba katmamak; kayan noktalı simülasyon, sabit noktalı gerçeklikten farklıdır
Sık sorulan sorular
LDPC kod çözmeyi genel doğrusal kodlara kıyasla bu kadar verimli kılan nedir?
Parite kontrol matrisinin seyreklik derecesi, her bitin yalnızca birkaç parite kontrolüne katıldığı anlamına gelir. Kod çözmede, iki parçalı grafik üzerindeki mesaj geçişi, kod uzunluğuna değil, kenar sayısına göre doğrusaldır. Yoğun kodlar için kod çözme, kod uzunluğuna göre kübik olan matris tersini gerektirirdi. Seyreklik, kod çözmeyi yarı-doğrusal ve uzun kodlar için pratik hale getirir.
Absorbe edici küme nedir ve neden önemlidir?
Absorbe edici küme, inanç yayılımı kod çözmesini tuzağa düşürerek doğru çözüme yakınsamayı engelleyebilen grafiğin küçük bir alt kümesidir. Bunlar, hata tabanının (düşük SNR'de BER'in üssel olmayan azalması) birincil kaynağıdır. Kod tasarımcıları, dikkatli grafik yapımı yoluyla kısa absorbe edici kümelerden kaçınırlar; analiz araçları (örneğin, durdurma kümesi analizi) sorunlu yapıları tanımlar.
LDPC, polar kodlarla nasıl karşılaştırılır?
Her ikisi de Shannon'a yakın performans gösterir. Polar kodlar, sonsuz kod uzunluğunda ardışık iptal kod çözme altında özyinelemeli bir yapıya ve kanıtlanabilir optimalliğe sahiptir. LDPC kodları daha esnektir ve ampirik olarak daha iyi sonlu uzunluk performansı gösterir. 5G NR, kontrol kanalları (kısa paketler) için polar kodları ve veri kanalları (uzun paketler) için LDPC'yi kullanır, her kodun güçlü yönlerinden yararlanır.
LDPC kodlarında grafik çevresi neden önemlidir?
Çevre, iki parçalı grafikteki en kısa döngünün uzunluğudur. Kısa döngüler (çevre < 6), inanç yayılımının ilişkili bilgileri kullanmasına (mesajlar geri döner) neden olarak performansı düşürür. Yüksek çevre kodları (çevre ≥ 6), korelasyonları daha iyi kırar. Kodlar genellikle seyreklik kısıtlamalarına tabi olarak çevreyi en üst düzeye çıkarmak için tasarlanır.
İlgili yöntemler
Kaynaklar
Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.
DOI kaynağını açKopyalandı.Richardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.
DOI kaynağını açKopyalandı.