Iterative Decoding of Turbo Product Codes (TPCs) Using the Chase-Pyndiah Turbo Decoder

Abstract

The ground breaking error correction codes that could achieve low bit error rates (near Shannon’s limit) were Turbo Codes (TCs) introduced by Berrou, Glavieux in 1993. The encoders for these outstanding codes were created by parallel concatenation of two recursive systematic convolutional codes separated by an interleaver. For decoding TCs Log-MAP algorithm could be used due to its gain in computational speed and improvement in precision. The only problem with turbo coding and decoding is that, the choice of interleaver for the encoder may cause an error floor due to their inherent poor distance properties. Turbo product codes (TPCs) are powerful linear block codes formed by combining more than one simple linear block codes. They classify under serially concatenated codes however unlike TCs they do not rely on an interleaver and hence they have no error floor problem. TPCs which date as early as 1954, are multi-dimensional codes that are constructed by two or more linear block codes also known as component codes. The product code is obtained by placing (k1k2) information bits in an array with k1 rows and k2 columns. Important parameters of a product code are the length of the codeword (n), the length of the information (k) and the minimum distance (d). Turbo product decoding is possible using either hard or soft decoding. In hard decision decoding, the input must be a binary sequence, whereas in soft decision decoding the values are immediately processed by the decoder to gauge a code sequence. A SISO decoder can be utilized to generate the soft decision decoder outputs. Some of the soft decoding algorithms include: the maximum a posteriori probability (MAP) algorithm, Chase-Pyndiah iterative decoder, symbol based MAP algorithm, the Soft Output Viterbi Algorithm, sliding‐window based MAP decoder, and the forward recursion based MAP decoder. The work presented in this thesis presents the bit-error-rate (BER) versus signal-to-noise-ratio (SNRdB) for soft decision (SD) decoding. The modulation type is BPSK and encoded symbols are transmitted over AWGN and Rayleigh fading channels. For SD the Chase-Pyndiah decoding algorithm was simulated to lower the bit error rate from iteration to iteration. We assumed an information array of (4×4) and the coded array had dimensions (7×7) for the first code, and an information array of (11×11) and the coded array had dimensions (15×15) for the second one. BER results were obtained as ensemble average of many runs (repetitions). Simulation results indicate that the SD with Chase-Pyndiah algorithm provides nearly 1.1dB lower BER in comparison to the uncoded BPSK over AWGN channel for (7,4)2 and 2.6dB when using the (15,11)2 at target BER of 10-3. For flat fading Rayleigh channel, the simulation achieved at around 18dB SNR value for the (7,4)2 TPC and at 15dB for the (15,11)2 at target BER of 10-3, whereas the uncoded BPSK could achieve the same target BER beyond 20dB. Keywords: Turbo product codes, Iterative decoding, Chase-Pyndiah algorithm.

ÖZ: Shannon sınırının yakınında düşük bit hata oranlarına ulaşabilen hata düzeltme kodları, 1993 yılında Berrou ve Glavieux tarafından önerilen Turbo Kodlar (TC) idi. Bu seçkin kodlar için kodlayıcılar, bir serpiştirici ile ayrılmış iki ardışık sistematik evrişimsel kodun paralel birleştirilmesi ile oluşturulmaktaydı. TC'lerin şifresini çözmek için hesaplama hızındaki kazanç ve hassaslığı artırması nedeniyle Log-MAP algoritması kullanılabilir. Turbo kodlama ve kod çözme ile ilgili tek problem, kodlayıcıdaki serpiştirici seçimine bağlı olarak, serpiştiricinin içsel zayıf mesafe özelliklerinden dolayı bir hata zeminine neden olabilmesidir. Turbo çarpım kodları (TPC'ler) birden fazla basit, doğrusal blok kodunu birleştirerek oluşturulan güçlü doğrusal blok kodlarıdır. TPCler sıralı olarak birleştirilmiş kodlar altında sınıflandırırlar, ancak TC'lerin aksine bir kodlayıcıya dayanmazlar ve dolayısıyla hata zemini problemleri yoktur. 1954 yılına kadar uzanan TPC'ler, bileşen kodları olarak da bilinen iki veya daha fazla doğrusal blok kodla oluşturulmuş çok boyutlu kodlardır. Çarpım kodu, (k1×k2) bilgi bitlerini k1 satır ve k2 sütunları içeren bir diziye yerleştirerek elde edilir. Bir çarpım kodunun önemli parametreleri, bilginin uzunluğu (n), kod sözcüğünün uzunluğu (k) ve en ufak mesafe (d) dir. Turbo çarpım kodlarının çözümü, sert veya yumuşak kod çözme yöntemleri kullanarak gerçekleştirilebilir. Sert karar tabanlı çözme işleminde girdi ikili bir dizi olmalı, yumuşak kararlı çözücülerde ise değerler bir kod sırasını ölçmek için kod çözücü tarafından hemen işlenmelidir. Yumuşak kararlı kod çözücünün çıktılarını üretmek için bir SISO kod çözücü kullanılabilir. Yumuşak kod çözme algoritmalarından bazıları şunlardır: en büyük sonsal olasılık (MAP) algoritması, Chase-Pyndiah iteratif kod çözücüsü, sembol tabanlı MAP algoritması, yumuşak çıkışlı Viterbi algoritması, kayan-pencere tabanlı MAP dekoder ve ileri yineleme tabanlı MAP dekoder. Bu çalışmada, yumuşak kararlı (SD) bir kod çözücü için farklı sinyal / gürültü oranlarında (SNRs) bit hata oranları (BERs) hesaplanmıştır. Modülasyon tipi olarak BPSK kullanılmış ve kodlanmış sembollerin AWGN ve düz sönümlemeli Rayleigh kanalları üzerinden iletimi yapılmıştır. Benzetimler esnasında farklı iterasyonlardaki bit-hata-oranını düşürebilmek için Chase-Pyndiah şifre çözme algoritması kullanılmıştır. Bilgi dizisinin (4×4) olduğu ilk kod için kodlanmış dizinin boyutları (7×7) ve bilgi dizisinin (11×11) olduğu ikinci kod için kodlanmış dizinin boyutu (15×15) idi. Bit-hata-oranı sonuçları, çok sayıdaki benzetimin toplam ortalaması olarak elde edilmiştir. Simülasyon sonuçları göstermiştir ki iteratif Chase-Pyndiah şifre çözme algoritması kullanılıp, AWGN kanalı üzerinde (7,4)2 TPC kodlu veri iletimi gerçekleştirildiğinde 10-3 hedef BER şifrelenmemiş BPSKye göre 1.1dB daha önce sağlanmıştır. (15,11)2 kodlu veri iletimi için ise bu değer 2.6dB daha önce sağlanabilmektedir. Düz sönümlemeli Rayleigh kanalı üzerinde 10-3 hedef BER (7,4)2 ve (15,11)2 TPC kodlu veri iletimleri için sırası ile 18dB ve 15dB de elde edilirken kodlanmamış BPSK aynı hedef bit-hata-oranını ancak 20dBden sonar sağlayabilmektedir. Anahtar Kelimeler: Turbo çarpım kodları, iteratif kod çözücüsü, Chase-Pyndiah algoritması.