LDPC codes: code construction and encoder hardware implementation

Abstract

Being the key factor for development as a society, electronic communications haveincreasingly became more and more the center of our day to day life. Consequently,methods and techniques that ensure reliable, safe and fast transmission ofinformation are becoming more and more essential. Digital Signal Processing, InformationTheory and Error Correction Codes are the research areas that study how toachieve such a goal. Many error correction codes have been presented in the pastbut in recent years a class of codes has imposed itself as the best candidate to solvethe problem, Low Density Parity Check (LDPC) Codes. LDPC codes are a class ofcodes that can achieve reliable communication while keeping the complexity of theencoder and decoder implementation controllable. The performances of LDPC codeshave been shown to be very close to the theoretical limit that a code can reach ina given channel, the channel capacity. However, implementation of LDPC codes ofvery good performance and at the same time, very low complexity, remains a challenge.There is always a need for smaller and faster communication devices with lowpower consumption and low cost, as a consequence, error correction modules must beimproved to meet these specifications covering at the same time all required functionalities.This thesis investigates various aspects of LDPC code construction/implementationthat can improve their performance and decrease their hardware implementation requirements.The main focus of the thesis is on code construction and encoder hardwareimplementation where either by adopting known code construction methods or bymodifying them, known encoding algorithms or by modifying them, and by proposingnew construction techniques, we always jointly consider the error-corrective capabilityof the constructed code and their complexity; since when real systems are designed,the choice of the code used cannot be based exclusively on the coding performancesbut also hardware requirements must be considered. Hence, it is important to developcodes that are capable of good performances without making the encoding anddecoding processes intractable from an implementation point of view.

Στα ψηφιακά συστήματα, η πληροφορία κωδικοποιείται σε ακολουθίες από 0και 1, που αντιστοιχούν στις δύο δυνατές καταστάσεις των τρανζίστορ, on - off, τα οποία λειτουργούν ως διακόπτες. Το πλεονέκτημα αυτό έχει επιφέρει σημαντικέςαλλαγές στον τρόπο επεξεργασίας της πληροφορίας. Η πληροφορία στη φύση παρουσιάζεται αποκλειατικά σε αναλογική μορφή, καθώς ο άνθρωπος μόνο αναλογικάσήματα μπορεί να αντιληφθεί. ´Ετσι λοιπόν, τα αναλογικά δεδομένα πρέπει να ψη-φιοποιηθούν, να μετατραπούν δηλαδή σε ακολουθίες από 0 και 1, ώστε ο δέκτης ναμην είναι υποχρεωμένος να κάνει μία εκτίμηση των άπειρων τιμών ενός αναλογικούσήματος, αλλά απλά να πάρει μία απόφαση μεταξύ των δύο διακριτών τιμών γιακάθε σήμα, 0 ή 1. Η διαδικασία αυτή καθιστά τα ψηφιακά σήματα πιο αξιόπισταγια τη μετάδοση πληροφορίας σε ένα ενθόρυβο περιβάλλον, καθώς μπορούν να ανι-χνεύονται σχεδόν τέλεια, όταν το επίπεδο του ϑορύβου δεν είναι ιδιαίτερα υψηλό,πράγμα που επιτρέπει την ανάκτηση των ψηφιακών στοιχείων, και μέσω των τεχνι-κών διόρθωσης λαθών είναι δυνατή η διόρθωση σφαλμάτων που συμβαίνουν κατά τημετάδοση.Η διατριβή επικεντρώνεται στην κατασκευή αποδοτικών κωδίκων LDPC και στη μελέτη της κωδικοποίησης για κώδικες LDPC. Συγκεκριμένα, στην παρούσα διατριβήακολουθείται μια σχεδιαστική μεθοδολογία βασισμένη στην από κοινού κατασκευήκαι υλοποίηση σε υλικό των κωδίκων LDPC και των κωδικοποιητών, αντίστοιχα.Στόχος είναι να αναπτυχθούν μεθοδολογίες κατασκευής κωδίκων LDPC με μεγάληικανότητα διόρθωσης λαθών, ιδιαίτερα σε χαμηλό BER , οι οποίοι ικανοποιούν προδιαγραφές συγκεκριμένων εφαρμογών, αλλά και να είναι κατάλληλοι για χρήση και σε άλλες εφαρμογές με παρόμοιες απαιτήσεις σε διορθωτική ικανότητα. Ταυτοχρόνως, υλοποιούνται σε υλικό διάφορες αρχιτεκτονικές κωδικοποιητών, οι οποίες επίσης ικανοποιούν ένα αρκετά μέγαλο εύρος από προδιαγραφές αρχιτεκτονικών, όπως υψηλό ρυθμό επεξεργασίας και μετάδοσης δεδομένων (Throughput rate), της τάξεως των πολλών Gbps, χαμηλή χρονική πολυπλοκότητα με μικρή επιφάνεια των κυκλωμάτων VLSI, χρήση μικρών μνημών και χαμηλή κατανάλωση ισχύος, αλλά και υποστήριξη κωδικοποίησης κωδίκων με πολλαπλούς ρυθμούς χρησιμοποιώντας είτε ένα μόνο κώδικα από τον οποίο παράγονται και άλλοι κώδικες με διαφορετικούς ρυθμούς, είτε χρησιμοποιώντας πολλούς κώδικες, ο καθένας από τους οποίουςυποστηρίζει ένα συγκεκριμένο ρυθμό. Στα πλαίσια της διατριβής, μελετούνται τα προβλήματα και η πολυπλοκότητα κωδικοποίησης κωδίκων LDPC μαζί με την διορθωτική ικανότητά τους. ´Εμφαση δίνεται στη κατασκευή και υλοποίηση των κωδίκων που ανήκουν στη κατηγορίατων QC-LDPC.