Turbo Kodlama ve İteratif Kod Çözme
- Ortaya koyan
- Claude Berrou, Alain Glavieux, and Punya Thitimajshima
- Yıl
- 1993
- Tür
- iterative error-correcting code
- Aile
- Coding theory
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Berrou, Glavieux ve Thitimajshima tarafından 1993 yılında tanıtılan Turbo kodlar, kanal kodlama tarihinde bir dönüm noktasıdır.
Shannon limiti—güvenilir iletişim için teorik sınır—yakınında, daha önce pratik karmaşıklıkla imkansız olduğu düşünülen bir başarıyı, 0,5 dB içinde performans sergilerler. Turbo kodlar, bir ara-dizici (interleaver) ile birleştirilmiş evrişimsel kodlar (convolutional codes) ve olasılık yayılımı (belief propagation) yoluyla iteratif kod çözme kullanır. 3G (UMTS) sistemlerinde benimsenmişlerdir ve LDPC kodlarla birlikte 4G/5G sistemlerinde önemlerini korumaktadırlar.
Yöntemin mantığı
Standart hata düzeltme kodları veriyi korumak için fazlalık (redundancy) ekler ancak tipik olarak karmaşık kod çözme gerektirir (örneğin, kod uzunluğuyla üstel olarak büyüyen maksimum olabilirlik). Turbo kodlar problemi tersine çevirir: paralel olarak basit kodlayıcılar (iki veya daha fazla evrişimsel kod) kullanır, bunlar rastgele olmayan bir ara-dizici ile ayrılır ve kod çözücüler iteratif olarak bilgi alışverişinde bulunur. Ara-dizici, bir kod için zor olan hataların diğer kod için muhtemelen kolay olmasını sağlar (permütasyon nedeniyle), böylece iteratif iyileştirme gerçek mesaja yakınsar. Bu 'turbo etkisi' (adı buradan gelir) tek geçişli kod çözmeye göre üstel olarak daha iyi performans üretir ve teorik sınıra yaklaşır.
Tarih
Turbo kodlar ICC 1993'te duyuruldu ve kodlama teorisi topluluğunu neredeyse Shannon performansıyla şok etti. 1990'ların sonlarında 3G (UMTS, cdma2000) benimsenmesinin ana itici gücü oldular. Turbo kodları anlamak, iteratif kod çözmenin daha geniş bir teorisine ve klasik kodların anlaşılmasında bir rönesansa yol açtı (örneğin, Hamming kodlarının iteratif yapıya sahip olduğu gösterildi). 2000'lerde, LDPC kodları (Gallager, 1962 tarafından yeniden keşfedildi) karşılaştırılabilir performans ve daha basit mimari ile rakipler olarak ortaya çıktı. Polar kodlar (Arikan, 2009) sınırlı durumda teorik olarak en uygun olanı sundu. Modern standartlar (5G NR) her üç aileyi de destekler; turbo kodlar eski teknoloji olsa da yaygın olarak uygulanmaktadır.
Ne zaman kullanılır?
Turbo kodlar, derin solma (deep-fading) veya gürültülü kanallarda, güçlü hata düzeltmenin gerektiği yerlerde (örneğin, uydu, derin uzay, su altı) üstünlük sağlar. Düşük bit hata oranlarının (BER < 10^-6) kritik olduğu ve gecikmenin iteratif kod çözmeye izin verdiği (birkaç milisaniye) durumlarda turbo kodlama kullanın. Turbo kodlar, hız kritik uygulamalar veya çok kısa paketler için daha az uygundur (ara-dizici ve kod çözücü durumu aşırı yükü domine eder). LDPC ve polar kodların (biraz daha iyi performans, daha basit) yükselişiyle birlikte, turbo kodlar artık birçok yeni standardda eski teknoloji (legacy) olarak kabul edilse de, uyumluluk katmanlarında hala kullanılmaktadır.
Sınırlar ve dikkat edilmesi gerekenler
- İteratif kod çözme gecikme getirir (uzun ara-diziciler için on milisaniyeler)
- Performans ara-dizici tasarımına duyarlıdır; kötü bir seçim turbo etkiyi zayıflatır
- Çok düşük BER'lerde hatalar kümelenme eğilimindedir (hata zemini - error floor); azaltmak için kod uyarlaması gerektirir
- Kod çözme karmaşıklığı bilgi uzunluğuyla orantılıdır (üstel değil, ancak yine de yüksektir)
- Kısa paketler ara-dizici aşırı yükünden ve yakınsama için yetersiz iterasyon derinliğinden muzdariptir
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Pratik karmaşıklıkla Shannon limitinin 0,5 dB'i içinde performans
- Eşik fenomeni olmadan (klasik kodların aksine) geniş bir sinyal-gürültü oranı aralığında iyi çalışır
- İteratif kod çözme, her iterasyonda performansı iyileştirir, iterasyon sayısı aracılığıyla hız kontrolüne izin verir
- Ayrılabilir tasarım: herhangi bir evrişimsel kod kullanılabilir, bu da esneklik sağlar
- Ara-dizici sayesinde darbe hatalarına (burst errors) karşı dayanıklıdır
Uygulama alanları
- 3G/4G hücresel (UMTS, LTE): turbo kodların neredeyse Shannon performansı sağladığı yukarı ve aşağı bağlantı trafik kanalları
- Uydu iletişimi: derin uzay görevleri (örneğin, Mars gezginleri) aşırı gürültüden güvenilir veri kurtarma için turbo kodları kullanır
- Askeri güvenli iletişim: karıştırmaya eğilimli ortamlarda güçlü hata düzeltme ile şifreli veri iletimi
- Kablosuz sensör ağları: düşük güçlü düğümler, güvenilir çoklu atlamalı iletim için kısa turbo kodları kullanır
- Tıbbi telemetri: gürültülü kablosuz bağlantılar üzerinden kritik hasta verilerini ileten biyomedikal cihazlar
Nasıl çalışır?
Nasıl çalışır?
Bilgi bitleri, özdeş evrişimsel kodlayıcılar (RSC: özyinelemeli sistematik evrişimsel) kullanılarak iki paralel kod kelimesine kodlanır.
İki kodlayıcı arasında, rastgele olmayan bir bit ara-dizici bilgi dizisini permüte eder. Bu, aynı bilgi için iki kod kelimesinin farklı ağırlık dağılımlarına sahip olmasını sağlar.
Kodlanmış bitler (her iki kodlayıcıdan sistematik ve parite) kanal üzerinden iletilir ve gürültü ile bozulur.
İç bilgi (bileşen kod çözücü 2'den kod çözücü 1'e geri beslemesi yapılan dışsal bilgi) önceki kod çözme turlarında işlenmiş olmuştur, bu nedenle bileşen kod çözücüler yinelemeli olarak ortak inançlarını paylaşır ve geliştirirler.
Sabit sayıda iterasyondan (örneğin, 8-20) sonra, olasılık oranının eşiklenmesiyle son bir sert karar verilir. Yakınsama 'turbo uçurumu' (turbo cliff) ile izlenebilir: SNR kritik bir eşiği geçtiğinde ve iterasyon yakınsamaya başladığında performans keskin bir şekilde düşer.
Sık yapılan hatalar
- Belirlenmiş veya çok kısa bir ara-dizici kullanmak; rastgelelik iteratif kazanç için esastır
- Sabit iterasyon sayısının optimal olduğunu varsaymak; performans SNR'ye göre değişir; uyarlanabilir iterasyon sayısı daha iyidir
- Hata zeminini ihmal etmek; turbo kodlar bir eşik sergileyebilir (turbo uçurumu), bunun altında performans hızla bozulur
- Turbo kodları çok kısa bilgi bloklarına (<100 bit) uygulamak; göreceli aşırı yük karşılanamaz hale gelir
- İteratif kod çözmede geri besleme gecikmesini hesaba katmamak; kod çözücüler arasında tutarlı zamanlama gereklidir
Sık sorulan sorular
Turbo kodlardaki 'turbo' nedir?
Adı, her kod çözücünün bir sonraki kod çözücü için sinyali 'güçlendirdiği' turbo motora benzeyen iteratif kod çözme sürecine atıfta bulunur. İterasyon başına üstel performans kazancı bazen turbo etkisi olarak adlandırılır. Gerçek turboşarjlarla ilgisi yoktur.
Ara-dizici neden bu kadar önemlidir?
Ara-dizici, ikinci kod çözücüye ulaşmadan önce ilk kod çözücüden gelen hata desenlerindeki korelasyonları bozar. Olmadan, her iki kod çözücü de tekrar tekrar aynı hataları yapardı. İyi bir ara-dizici, bir kod çözücüden gelen hataların rastgele dağılmasını sağlar, ikinci kod çözücüye taze bir bakış açısı kazandırır ve üretken iterasyona olanak tanır.
Turbo uçurumu nedir?
Turbo kodlar keskin bir eşik sergiler: kritik bir SNR'nin altında, iteratif kod çözme yakınsamada başarısız olur ve BER düşüktür. Eşiğin üzerinde, BER keskin bir şekilde düşer. Bu turbo uçurumudur. Sistem tasarımı için SNR, uçurumun güvenli bir şekilde üzerinde olmalıdır; hemen altında çalışmak, görünüşte iyi SNR'ye rağmen feci bir arızaya neden olur.
Kaç iterasyon gereklidir?
Tipik turbo kod çözücüler 8-20 iterasyon kullanır; daha fazla iterasyon performansı iyileştirir ancak gecikmeyi artırır. Yüksek SNR'de, az sayıda iterasyon yeterlidir (yakınsama hızlıdır). Düşük SNR'de, daha fazla iterasyon gerekir. Uyarlanabilir iterasyon (yakınsamayı kontrol et, bittiğinde erken dur) gecikme ve performansı dengeler.
İlgili yöntemler
Kaynaklar
Berrou, C., Glavieux, A., & Thitimajshima, P. (1993). Near Shannon limit error-correcting coding and decoding: Turbo-codes. In Proceedings of the IEEE International Conference on Communications (ICC), 1064-1070.
DOI kaynağını açKopyalandı.Richardson, T. J., & Urbanke, R. L. (2002). 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ı.