Efficient decoding of polar codes

Abstract

Polar Codes are the first mathematically provable capacity achieving error correcting codes which have low complexity encoding and decoding algorithms. For the decoding of polar codes, as a preliminary decoding algorithm, the successive cancellation (SC) decoding algorithm is used. SC algorithm is a sequential decoding algorithm which suffers from error propagation. For this reason, SC algorithm does not show good performance for moderate codeword lengths. Polar codes with SC decoding show worse performance than that of the modern channel codes, such as LDPC and turbo codes. To improve the performances of the polar codes improved versions of SC algorithm such as SC list (SCL) and SC stack are introduced in the literature, and these algorithms show much better performance than that of the classical SC decoding algorithm although they have larger complexity compared to SC. Besides, cyclic redundancy check codes are concatenated with polar codes which are decoded using the SCL algorithm, and such a concatenated system shows better performance than the other modern channel codes. In this thesis, we first propose a tree structure for the successive cancelation (SC) decoding of polar codes. The proposed structure is easy to implement in hardware and suitable for parallel processing operations. Next, using the proposed tree structure, we propose a technique for the fast decoding of polar codes. With the proposed method, it is possible to decode all the information bits simultaneously at the same time, i.e., in parallel. Lastly, we introduce and improved version of the proposed high-speed decoding algorithm. The proposed high-speed decoding approach and its improved version are simulated on computer environment, and their BER performances are compared to the performance of the classical successive cancelation method. Furthermore, we introduce a new approach to the successive cancelation of polar codes. The proposed approach uses the soft likelihood ratios of the predecessor information bits for the determination of successor information bits. The proposed method can be considered for the construction of joint iterative communication systems exchanging soft likelihoods. It is shown that the proposed soft decoding approach shows better performance than the classical successive cancelation algorithm introduced in Arikan's original work. As we know, polar codes are decoded in a sequential manner using successive cancelation algorithm introduced by Arikan. The sequential nature of the decoding process suffers from error propagation. We inspect the effects of error propagation on the performance of polar codes and propose some methods to alleviate the degrading effects of error propagation on the code performance for short and long frame lengths.

Kapasiteye erişimi ilk defa matematiksel olarak ispatlanabilen Polar Kodlar, düşük karmaşıklıkta olan ardışık giderim (SC) yöntemi ile ikili ayrık hafızaya sahip olmayan simetrik kanallar için sunulmuş hata düzeltme kodlarıdırlar. Her ne kadar SC düşük bir karmaşıklığa sahip bir algoritma olsa da, hata yayılması probleminden dolayı iyi performans gösterememektedir. Ne yazık ki, SC kod çözme işleminin sonlu çerçeve uzunluklarındaki hata düzeltme performansı, LDPC kodları gibi diğer modern kodlarınki kadar iyi değildir. Sonlu çerçeve uzunluğu performansını iyileştirmek için, SC liste (SCL) kod çözme ve SC yığın kod çözme gibi daha gelişmiş algoritmalar yakın zamanda tanıtılmıştır. Bu algoritmalar, temel kod çözücü olarak SC'yi kullanır, ancak aynı anda birden çok yolu keşfederek bir aday kod kelimesi sonuçlanacak şekilde performansını arttırır. SCL çözücüsünü kod çözme işleminin hesaplama ve bellek karmaşıklıkları, basit SC kod çözücüsünden çok daha yüksektir. Kod çözme algoritmasının performansını arttırmak için döngüsel artıktık kontrolü (CRC) yardımı ile SCL yapısı (CRC-SCL) kullanılabilir. Bu tezde, öncelikle kutup kodlarının kod çözme işlemlerini ardışık giderim (SC) algoritması ile çözmek için bir ağaç yapısı öneriyoruz. Önerilen yapının donanım üzerinde gerçeklenmesi kolaydır ve paralel işleme işlemleri için uygundur. Daha sonra, önerilen ağaç yapısını kullanarak, kutup kodlarının hızlı bir şekilde çözülmesi için bir teknik öneriyoruz. Önerilen teknik ile tüm bilgi bitlerinin aynı anda, yani paralel olarak çözülmesi mümkündür. Son olarak, önerilen kod çözme algoritması hızını arttıracak bir yöntem sunulmuştur. Önerilen yüksek hızlı kod çözme yaklaşımın ve geliştirilmiş versiyonun, bilgisayar ortamında benzetimi yapılmış ve bit-hata oranı (BER) performansları, klasik ardışık giderim yönteminin performansıyla karşılaştırılmıştır. Ayrıca, kutup kodlarının art arda canlandırılmasına yeni bir yaklaşım getiriyoruz. Önerilen yaklaşım, ardışık bilgi bitlerinin belirlenmesi için önceki bilgi bitlerinin yumuşak olasılık oranlarını kullanmaktadır. Önerilen yöntem, yumuşak olasılıkları paylaşan ortak yinelemeli iletişim sistemlerinin kurulabilmesi için düşünülebilir. Önerilen yumuşak kod çözme yaklaşımının, Arıkan'ın orijinal eserinde tanıtılan klasik ardışık giderim algoritmasından daha iyi performans gösterdiği gösterilmiştir. Bildiğimiz gibi, polar kodları Arıkan'ın orijinal eserinde tanıtılan ardışık giderim algoritması kullanılarak sıralı bir şekilde çözülür. Kod çözme işleminin sıralı yapısı, hata yayılımından mustariptir. Bu çalışmada, hata yayılımının kutupsal kodların performansı üzerindeki etkilerini inceliyoruz ve kısa ve uzun veri blokları için hata yayılımının kod performansı üzerindeki düşürücü etkilerini azaltmak için yöntemler öneriyoruz. Anahtar Kelimeler: Kutup kodları, özyinelemeli kod çözme, hızlı kod çözme, ardışık giderim kod çözücüsü, ardışık giderim algoritması, yumuşak kod çözme, sıralı kod çözme, hata yayılımı, ikili silme kanalı.