An FPGA implementation of successive cancellation list decoding for polar codes

Abstract

Kutupsal kodların ayrık hafızasız kanallarda asimtotik olarak kanal kapasitesine sıralı elemeli (SC) kodçözücü ile eriştiği kanıtlanmıştır. SC düşük karmaşıklı bri algoritmadır ve bu algoritma ile yüksek blok uzunluğunda kodlar kullanılmadığı taktirde azami ihtimaliyet tahmini (ML) performansı elde edilmez. SC algoritması, böl ve fethet yöntemini kullanarak ve derinlik öncelikli arama yaparak karar verir. SC algoritması ile liste yapısı (SCL) birlikte kullanılarak ML performansına yaklaşılır. SCL algoritması açgözlü demet araması yapar. Ancak, kutupsal kodların olası kod sözcüklerinin en yakın hamming uzaklığı ve dolayısıyla ML performansı yeterince iyi değildir. Bu durumun üstesinden gelmek için döngüsel artıklık denetimi ile SCL algoritması (CRC-SCL) birleştirilir. Bu sayede, kutupsal kodlar güncel haberleşme sistemlerinde kullanılan kodlar ile rekabet eder hale gelir. Biz bu tezde, yüksek karmaşıklıklı ve yavaş çalısan CRC-SCL ile düşük karmaşıklıklı ve hızlı çalışan SC algoritmalarını FPGA uygulaması ile birlikte kullanarak performans ve karmaşıklık arasında ödünleşim sağlıyoruz.

Polar Codes are the first asymptotically provably capacity achieving error correc-tion codes under low complexity successive cancellation (SC) decoding for binarydiscrete memoryless symmetric channels. Although SC is a low complexity algo-rithm, it does not provide as good performance as a maximum-likelihood (ML)decoder, unless sufficiently large code block is used. SC is a soft decision decod-ing algorithm such that it employs depth-first searching method with a divideand conquer approach to find a sufficiently perfect estimate of decision vector.Using SC with a list (SCL) improves the performance of SC decoder such thatit provides near ML performance. SCL decoder employs beam search method asa greedy algorithm to achieve ML performance without considering all possiblecodewords. The ML performance of polar codes is not good enough due to theminimum hamming distance of possible codewords. For the purpose of increas-ing the minimum distance, cyclic redundancy check aided (CRC-SCL) decodingalgorithm can be used. This algorithm makes polar codes competitive with stateof the art codes by exchanging complexity with performance. In this thesis,we present an FPGA implementation of an adaptive list decoder; consisting ofSC, SCL and CRC decoders to meet with the tradeoff between performance andcomplexity.