Polar codes have gained a lot of attention in recent years due to their capacity-achieving property and error-correction performance. They are currently used for control information in 5G NR networks. Decoding of polar codes can introduce various challenges, as their decoding is highly sequential leading in high latency and low throughput, thus an effective and efficient decoding implementation is crucial. In this paper, several decoding algorithms are proposed, including Successive Cancellation (SC) and Successive Cancellation List (SCL) decoding. Various implementations of a Successive Cancellation Decoder (SCD) are implemented and executed on a Field Programmable Gate Array (FPGA) device. The implementations aim to optimize the design, improving its throughput rate and resource utilization. The results prove that certain processes of the decoding algorithm can be parallelized, reducing the latency they introduce to the system significantly.
Polar codes have gained a lot of attention in recent years due to their capacity-achieving property and error-correction performance. They are currently used for control information in 5G NR networks. Decoding of polar codes can introduce various challenges, as their decoding is highly sequential leading in high latency and low throughput, thus an effective and efficient decoding implementation is crucial. In this paper, several decoding algorithms are proposed, including Successive Cancellation (SC) and Successive Cancellation List (SCL) decoding. Various implementations of a Successive Cancellation Decoder (SCD) are implemented and executed on a Field Programmable Gate Array (FPGA) device. The implementations aim to optimize the design, improving its throughput rate and resource utilization. The results prove that certain processes of the decoding algorithm can be parallelized, reducing the latency they introduce to the system significantly.
The focus of this thesis is the algorithms and hardware architectures for Polar decoders based on the 5G NR standard. First, we introduce polar codes and their key points such as their error correction capabilities. Many algorithms are studied, such as the Successive Cancellation (SC), Successive Cancellation List (SCL), Simplified Successive Cancellation (SSC), Simplified Successive Cancellation List (SSCL), and Sequence Repetition Successive Cancellation List (SR-List). For all algorithms studied, their hardware implementations are also explored, with emphasis in the comparison between them, especially what each algorithm or architecture is trying to improve based on the previous. This is crucial for the general understanding of the evolution of the polar decoding algorithms. In the end, a specific algorithm from those discussed is implemented on an FPGA, trying to make good decisions at the architecture, aiming for low latency. Finally, the results of the design are presented.
This thesis presents a comprehensive study on the hardware implementation of 5G polar decoders, focusing on development, operations, and performance optimization. Polar codes, a pivotal forward error correction technique in 5G communication, are analyzed for their error correction capabilities and efficiency. The research delves into various polar decoding algorithms, including Successive Cancellation (SC), Successive Cancellation List (SCL), and Successive Cancellation Stack (SCS) decodings. Each algorithm's implementation nuances are examined, highlighting their computational complexities and error correction performance. The work further explores FPGA-based implementations, detailing architecture designs that optimize resource utilization and processing speed. Specific emphasis is placed on bit and array length optimizations to enhance decoding efficiency. The thesis also includes a performance analysis comparing different decoding strategies, emphasizing their suitability for real-world 5G applications. Experimental results demonstrate the feasibility and advantages of the proposed hardware implementations, particularly in achieving the low latency and high throughput required for 5G applications. The findings suggest that polar decoders can meet the stringent requirements of next-generation wireless communication systems with proper optimization. Finally, we implement and execute a hardware architecture of the basic Successive Cancellation decoder on an FPGA, performing further optimizations to decrease resource usage and increase execution time without affecting the error correction performance.
Σε αυτή τη διπλωματική εργασία διερευνήθηκαν οι κώδικες διόρθωσης λαθών της κατηγορίας Polar. Αναλύθηκαν οι διαδικασίες που συνθέτουν τέτοιου είδους αλγόριθμους και συντέθηκαν κώδικες για κάποιους γνωστούς αλγόριθμους που ανήκουν σε αυτή την κατηγορία. Συγκεκριμένα υλοποιήθηκαν οι Successive Cancellation decoder (SC) και Successive Cancellation List decoder (SCL) βασισμένοι σε σύστημα που χρησιμοποιεί log-likelihoodratios (LLRs). H αρχιτεκτονική που δημιουργήθηκε ακολουθεί τη μορφή πλήρους δυαδικού δένδρου και για τους δύο αλγορίθμους. Mε χρήση του εργαλείου Catapult καταλήξαμε σε υλοποιήσεις για ASIC. Από τα αποτελέσματα της σύνθεσης καταλήγουμε σε συμπεράσματα για τις υλοποιήσεις.
This paper proposes an effective field-programmable gate array (FPGA) implementation of a successive-cancellation (SC) decoder for polar codes that have recently attracted attention as error-correcting codes adopted for 5G wireless systems. We focus on effective ways of partitioning the SC decoding procedure into combinational and sequential logic parts. It can be shown that the SC decoder of length N(= N1N2) can be divided into two parts: N1SC decoders of length N2and a single SC decoder of length N1. While the N1decoders in the first part can perform in parallel, the decoding procedure in the second part is performed sequentially, which causes a bottleneck due to a long latency. We present an SC decoder architecture in which the first part is implemented using sequential logic circuits, and the second part is implemented using only combinational logic circuits. The overall latency and clock frequency of the decoder are balanced by the divisor N1of N, and we show that an appropriate choice of N1yields an efficient implementation with a high throughput. We demonstrate an FPGA implementation of the decoder architecture for a 1024-bit-length polar code and show that our FPGA decoder can achieve three times higher throughput than the conventional sequential semi-parallel decoder without significantly increasing the hardware resources.
Polar codes are a family of error correcting codes that achieves the symmetric capacity of memoryless channels when the code length N tends to infinity. However, moderate code lengths are required in most of wireless digital applications to limit the decoding latency. In some other applications, such as optical communications or quantum key distribution, the latency introduced by very long codes is not an issue. The main challenge is to design codes with the best error correction capability, a tractable complexity and a high throughput. In such a context, SC decoding is an interesting solution because its performance improves with N while the computational complexity scales almost linearly. In this paper, we propose to improve the scalability of SC decoders thanks to four architectural optimizations. The resulting SC decoder is implemented on an FPGA device and favorably compares with state-of-the-art scalable SC decoders. Moreover, a 222polar code SC decoder is implemented on a Stratix-5 FPGA. This code length is twice larger than the ones achieved in previous works. To the best of our knowledge, this is the first architecture for which a N = 4 million bits polar code can be actually decoded on a reconfigurable circuit.
Η παρούσα διπλωματική εργασία εκπονήθηκε στο πλαίσιο των σπουδών μου στο Τμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών και έχει ως αντικείμενο τη μελέτη και βελτίωση της αποκωδικοποίησης πολικών κωδίκων στο πρότυπο 5G New Radio. Οι πολικοί κώδικες έχουν υιοθετηθεί από το 3GPP, χάρη στην υψηλή τους απόδοση με χαμηλούς ρυθμούς σφάλματος. Ωστόσο, οι παραδοσιακοί αλγόριθμοι αποκωδικοποίησης, όπως ο Successive Cancellation (SC) και ο Belief Propagation (BP), παρουσιάζουν περιορισμούς τόσο ως προς την επίδοση. Στόχος της εργασίας είναι η μελέτη και η υλοποίηση σε υλικό (hardware) ενός αποκωδικοποιητή Belief Propagation με εισαγωγή βαρών (Neural BP), ώστε να καταστεί δυνατή η εκπαίδευσή του με μεθόδους μηχανικής μάθησης και να βελτιωθεί η απόδοσή του σε σχέση με τον κλασικό BP. Παράλληλα, εξετάζεται η ενσωμάτωση του αποκωδικοποιητή στο πλαίσιο της προδιαγραφής 5G NR, με στόχο την επίτευξη υψηλής αξιοπιστίας και αποδοτικότητας. Η εργασία περιλαμβάνει θεωρητική ανάλυση, παρουσίαση του βασικού BP αλγορίθμου και του Neural BP, ανάπτυξη του μοντέλου σε Python, καθώς και πειραματικά αποτελέσματα που αποδεικνύουν τη βελτίωση της επίδοσης του προτεινόμενου αποκωδικοποιητή μετά την εισαγωγή και εκπαίδευση των βαρών.