Efficient decoding of polar codes

Abstract

Kapasiteye erişimi ilk defa matematiksel olarak ispatlabilen Polar Kodlar, düşükkarmaşıklıkta olan ardışık giderim (SC) yöntemi ile ikili ayrık hafızaya sahip olmayansimetrik kanallar için sunulmuş hata düzeltme kodlarıdırlar. Her ne kadar SC düşük birkarmaşıklığa sahip bir algoritma olsa da, hata yayılması probleminden dolayı iyiperformans gösterememektedir.Ne yazık ki, SC kod çözme işleminin sonlu çerçeve uzunluklarındaki hata düzeltmeperformansı, LDPC kodları gibi diğer modern kodlarınki kadar iyi değildir. Sonlu çerçeveuzunluğ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, temelkod çözücü olarak SC'yi kullanır, ancak aynı anda birden çok yolu keşfederek bir adaykod kelimesi sonuçlanacak şekilde performansını arttırır. SCL çözücüsünü kod çözmeişleminin hesaplama ve bellek karmaşıklıkları, basit SC kod çözücüsünden çok dahayüksektir. Kod çözme algoritmasının performansını arttırmak için döngüsel artıklıkkontrolü (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 üzerindegerçeklenmesi kolaydır ve paralel işleme işlemleri için uygundur. Daha sonra, önerilenağ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 biryö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 bitlerininyumuş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. Önerilenyumuşak kod çözme yaklaşımının, Arıkan'ın orijinal eserinde tanıtılan klasik ardışıkgiderim 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 giderimalgoritması kullanılarak sıralı bir şekilde çözülür. Kod çözme işleminin sıralı yapısı, hatayayı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 kodperformansı üzerindeki düşürücü etkilerini azaltmak için yöntemler öneriyoruz.Anahtar Kelimeler: Kutup kodları, özyinelemeli kod çözme, hızlı kod çözme, ardışıkgiderim kod çözücüsü, ardışık giderim algoritması, yumuşak kod çözme, sıralı kod çözme,hata yayılımı, ikili silme kanalı.

Polar Codes are the first mathematically provable capacity achieving error correctingcodes which have low complexity encoding and decoding algorithms. For the decoding ofpolar codes, as a preliminary decoding algorithm, the successive cancellation (SC)decoding algorithm is used. SC algorithm is a sequential decoding algorithm which suffersfrom error propagation. For this reason, SC algorithm does not show good performancefor moderate codeword lengths.Polar codes with SC decoding show worse performance than that of the modern channelcodes, such as LDPC and turbo codes. To improve the performances of the polar codesimproved versions of SC algorithm such as SC list (SCL) and SC stack are introduced inthe literature, and these algorithms show much better performance than that of the classicalSC decoding algorithm although they have larger complexity compared to SC. Besides,cyclic redundancy check codes are concatenated with polar codes which are decoded usingthe SCL algorithm, and such a concatenated system shows better performance than theother modern channel codes.In this thesis, we first propose a tree structure for the successive cancelation (SC) decodingof polar codes. The proposed structure is easy to implement in hardware and suitable forparallel processing operations. Next, using the proposed tree structure, we propose atechnique for the fast decoding of polar codes. With the proposed method, it is possible todecode 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. Theproposed high-speed decoding approach and its improved version are simulated oncomputer environment, and their BER performances are compared to the performance ofthe 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 bitsfor the determination of successor information bits. The proposed method can beconsidered for the construction of joint iterative communication systems exchanging softlikelihoods. It is shown that the proposed soft decoding approach shows betterperformance than the classical successive cancelation algorithm introduced in Arikan'soriginal work.As we know, polar codes are decoded in a sequential manner using successive cancelationalgorithm introduced by Arikan. The sequential nature of the decoding process suffersfrom error propagation. We inspect the effects of error propagation on the performance ofpolar codes and propose some methods to alleviate the degrading effects of errorpropagation on the code performance for short and long frame lengths.