Polar code decoding with soft decision algorithms

Abstract

Shannon'un haberleşmenin matematiksel teorisini anlattığı ünlü makalesi ile birlikte doğan bilgi teorisi kapsamında Shannon tarafından çizilen performans sınırlarına ulaşmak için çok sayıda kanal kodu geliştirilmiştir. Başlangıçta, kanal kodları ikili vektör alt uzayları, yani blok kodları kullanılarak oluşturulur ve bu kodların performansları bilgisayar simülasyonları ile ölçülmştür. İyi simülasyon sonuçlarına sahip kodlar pratik iletişim sistemlerine uyarlanmıştır.Farklı bir kanal kodu sınıfı olarak, evrişim kodları 1955 yılında Elias tarafından keşfedilmiştir. Evrişimli kodlar, kodlama ve kod çözme işlemlerinde blok kodlara göre temel farklılıklar gösterir. 1993'te turbo kodlar, paralel sıralı evrişim kodları olarak tanıtıldı. Turbo kodların şaşırtıcı performansı kanal kodlama toplumunda bir kilometre taşı olmuştur ve araştırmacılar arasında sıralı kodların tasarımına büyük ilgi duymuştur. Tasarlanan kodlar, turbo kodların üstün performansının arkasındaki ana nedenlerden biri olan yinelemeli bir şekilde çözülür.Araştırmacılar arasında 2000 yıllarındaki ortak fikir, yinelenebilir şekilde deşifre edilmiş birleştirilmiş kodların uzun yıllar üstesinden gelinmeyecek kodlar olmasıydı. 2009 yılında Erdal Arıkan tarafından kutup kodları tanıtıldı. Kutupsal kodlar bilgi teorisi kavramları kullanılarak tasarlanmıştır ve performansları matematiksel olarak kanıtlanmıştır. Kutupsal kodlar, önemsiz olmayan bir şekilde tasarlanan tek kanallar olarak kabul edilebilir ve kanal kodlama alanında bir atılım olarak düşünülebilir. Bu doktora tezinde, kutupsal kodların yumuşak karar tabanlı algoritmalarla çözümlenmesi incelenmiştir. Yumuşak karar temelli algoritmalardan biri olan karar yayılım algoritması ayrıntılı olarak literatürde incelenmiştir. Kutup kodları, karar yayılma algoritması kullanılarak çözülebilir. İletişim sistemleri için kod çözme gecikmesi kritik bir konudur. Kod çözme gecikmesi paralel işlemciler kullanılarak azaltılabilir. Bu bağlamda, karar yayılım algoritması paralel işleme operasyonları için uygundur. Literatürde, karar yayılma algoritması ile kodu çözülen kutup kodlarının, ardışık giderim algoritması tarafından kodu çözülen kutup kodlarından daha kötü performans gösterdiği belirtilmektedir. Bu tezde, karar yayılma algoritması tarafından çözülen kutup kodlarının performansını artırmayı hedefledik. Performans iyileştirmesi elde edildiği takdirde, inanç yayılma algoritmasının paralel işleme özelliğine uygunluğu öne çıkacaktır. Karar yayılma algoritmasında güvenilmez olasılıkların yayılması kutupsal kodların performansını kötüleştirir. İletilerin güvenilirliğini arttırmak için yapay olarak üretilen zayıf gürültü sinyallerini kullandık. Simülasyon sonuçlarından, alıcaya gelen sinyale zayıf gürültü eklenmesinin, karar yayılma algoritması tarafından çözülen kutup kodlarının performansını arttırdığı görülmektedir. Önerilen yaklaşım, gürültü destekli karar yayılımına dayalı liste, yani Na-BPL, kutupsal kod çözücü olarak adlandırılabilir. Önerilen yaklaşımla, karar yayılımı kod çözücüleri ile kutupsal kod performansının, en gelişmiş ardışık giderim liste kutup çözücüleri performansına yaklaştığı görülmektedir. Kutupsal kodların sistematik versiyonları da karar yayılma algoritmasına uygulanmıştır. Sistematik kodlama, ardışık giderim kutupsal kod çözücüsüne fazladan ek yükler getirir. Öte yandan, karar yayılma algoritması ile kullanıldığında, kod çözücü kısmında fazladan ek yük görülmez. Bu şekilde, kutupsal karar yayılım kod çözücülerinin performansını daha da geliştiriyoruz. Ayrıca, Na-BPL ile sistematik polar kodlar kullanıldığında, daha iyi kod çözme performansı elde edilir. Bölünmüş kanal kapasitelerinin doğru hesaplanması, kutupsal kod performansını etkileyen kritik bir konudur. Kutupsal kodlarının tasarımı için genetik algoritmayı da dikkate aldık. Tezde, genetik algoritma ile tasarlanan kutupsal kodların, mükemmel bilgi tabanlı erken tespit yöntemi kullanan Na-BPL ile çözüldüğünde, gelişmiş performans elde edildiği ve elde edilen performansın, en son teknolojiye sahip kutupsal kod çözücünün, yani CRC ile desteklenmiş SCL kutupsal kod çözücü performansından sadece 0.1dB uzakta olduğu belirtilmiştir. Na-BPL kod çözücü mükemmel bilgi tabanlı erken tespit yöntemi kullanılmadığında CRC ile desteklenmiş SCL kod çözücüyle yarışamıyor fakat hata düzeltme performansı SCL kod çözücünün performansına kıyasla ileridedir.

Since the born of the field of information theory with the publication of Shannon's famous paper, a mathematical theory of communication, numerous channel codes have been developed to achieve the performance limits drawn by Shannon. Initially, the channel codes are constructed using the binary vector subspaces, i.e., block codes, and the performances of these codes are measured via computer simulations. The codes that show good simulation results are adapted in practical communication systems. A different class of channel codes, convolutional codes are discovered in 1955 by Elias. Convolutional codes show basic differences in encoding and decoding operations than block codes. In 1993, turbo codes, parallel concatenated convolutional codes, are introduced. The astonishing performance of turbo codes is considered as a milestone in channel coding society, and a huge interest for the design of concatenated codes aroused among researchers. The designed codes are decoded in an iterative manner, which was one of the main reasons behind the superior performance of turbo codes. The common idea in the years of 2000 among the researchers was that iteratively decodable concatenated codes was the codes not to be overcame for long years. In 2009 polar codes are introduced by Erdal Arıkan. Polar codes are designed using the concepts of information theory, and their performances are proven mathematically. Polar codes can be considered as the only codes designed in a non-trivial manner, which can be considered as a breakthrough in channel coding field. In this doctoral thesis, the decoding of polar codes with soft decision based algorithms is studied. The belief propagation algorithm, which is one of the soft decision based algorithms, has been investigated in details literature. Polar codes can be decoded using belief propagation algorithm. For communication systems decoding latency is a critical issue. Decoding latency can be reduced using parallel processors. Belief propagation algorithm is suitable for parallel processing operations. It is indicated in the literature that polar codes decoded by belief propagation algorithm show worse performance than the polar codes decoded by successive cancelation decoding algorithm. In this thesis, we aim to improve the performance of polar codes decoded by belief propagation algorithm so that once it is achieved, the suitability for parallel processing property of the belief propagation algorithm can gain significance. The propagation of the unreliable probabilities in belief propagation algorithm worsens the performance of polar codes. To improve the reliability of propagating messages, we made use of the artificially generated weak noise signals. It is seen from the simulation results that the addition of weak noise to the received signal enhances the performance of polar codes decoded by belief propagation algorithm. The proposed approach can be named as noise-aided belief propagation based list, i.e., Na-BPL, polar decoder. With the proposed method, it is seen that the performance of polar codes with belief propagation decoders employing perfect knowledge based early termination approaches to the performance of state-of-the-art successive cancelation list polar decoders. The systematic versions of polar codes are also considered with belief propagation algorithm. The systematic encoding brings extra overheads to the successive cancellation polar decoder. On the other hand, when it is used with belief propagation algorithm, the extra overhead is not seen at the decoder part. In this way, we further improve the performance of the polar belief propagation decoders. Besides, when systematic polar codes are used with Na-BPL, better decoding performance is obtained. Accurate calculation of splitted channel capacities is a critical issue affecting the performance of polar codes. We considered the genetic algorithm for the design of polar codes. It is indicated in the thesis that when the polar codes designed with genetic algorithm is decoded using Na-BPL, improved performance is achieved, and the obtained performance is only 0.1 dB away from the performance of state-of-the-art polar decoder, i.e., CRC aided SCL polar decoder, when perfect knowledge based early termination is employed. And it is seen that without perfect knowledge based early termination, Na-BPL cannot overcome CRC aided SCL polar decoder, however, its error correction performance is better than SCL.