Performance improvement methods for layered decoding of ldpc codes

Abstract

Düşük-yoğunluklu eşlik-denetim (LDPC) kodları doğrusal blok kodları arasındadır. İlk olarak 1960 yılında R. Gallager tarafından keşfedilmelerine rağmen uzun yıllar boyunca unutulmuş, 1996 yılında yapılan bir çalışma ile bilim dünyasının yeniden ilgisini çekmişlerdir. Yüksek hata başarımına sahip olmaları nedeni ile günümüzde modern iletişim ve depolama sistemlerinde hata düzeltici kodlar olarak yaygın bir biçimde kullanılmaktadırlar. LDPC kod çözücülerin çalışma prensibi Gallager tarafından ortaya atılan kanı yayılımına (Belief Propagation) dayanmaktadır. LDPC kodlarının çözümünde performans iyileştirme maksadıyla çeşitli yöntemler bulunmuş ve pratikte de uygulanmaktadır. Bu yöntemlerden biri de kodların turbo çözümleme ile çözülmesidir. Önerilen yöntem ile kod çözümlemede daha güvenilir mesajların düğümler arası geçirilmesi sayesinde hızlı bir şekilde yakınsama sağlanmaktadır. Katmanlı mimaride çözümleme olarak da adlandırılan yöntem ile normal modda gereken yineleme sayısının yarısında aynı başarım seviyesine ulaşmak mümkündür. Tez çalışmamızda katmanlı mimaride LDPC çözümlemede performans arttırıcı yeni yöntemler sunulmuştur. Yeni yöntemler birçok değişik uzunlukta ve hızda LDPC kodları üzerinde denenmiştir. Yapılan benzetim çalışmaları sonucunda, önerilen yöntemler en iyi performans artırımını kısa ve hızlı LDPC kodları üzerinde sağladığı gözlenmiştir. Önerilen yöntemlerin seçilen LDPC kodları üzerinde denenmesine ilaveten, OpenMP kullanarak LDPC çözümleme işlemi paralelleştirilmiş, 8-çekirdekli gerçek DSP donanımı üzerinde yapılan testlerde tek çekirdeğe göre 6 kattan fazla hızlanma elde edildiği raporlanmıştır. Anahtar sözcükler: Düşük-yoğunluklu eşlik-denetim, hata düzeltici kodlar, kanı yayılımı, katmanlı mimaride çözümleme, performans artırımı, DSP, paralelleştirme, OpenMP

Low-density parity-check (LDPC) codes are a special type of linear block codes. Although they were originally invented by R. Gallager in 1960, they have captured the attention of scientific community since its rediscovery in 1996. Due to their excellent correction capability, they have been adopted in many communications and storage systems for forward error correction. Gallager defined an iterative two-phase decoding algorithm referred to as `Belief Propagation` (BP). Much study has been conducted to improve the performance of LDPC decoding. Later, another scheduling, `Turbo Decoding Message Passing` (TDMP) is introduced as an alternative to his standard message passing algorithm. TDMP, also called layered decoding, has the advantage of converging faster than the standard BP because it uses more reliable information to update next set of values. Using layered decoding, it is possible to reduce the number of iterations by 50% without any performance degradation. In this thesis, we present several methods in order to improve layered decoding performance of LDPC codes. Methods proposed have been applied to several LDPC codes with different length and rate. According to our results, the biggest performance improvements are achieved when they are applied to small-length, high-rate codes. In addition to proposed methods, a simulation acceleration platform using OpenMP is also described where parallel decoding is implemented on a real multicore hardware platform, obtaining more than 6x speedup compared to single-core version. Keywords: Low-density parity-check, error correction codes, belief propagation, layered decoding, performance improvement, DSP, parallelization, OpenMP