Luận án tiến sĩ new direction on low complexity implementation of probabilistic gradient descent bitflipping decoder

Luận án tiến sĩ khám phá hướng mới trong triển khai giải mã bitflipping với độ phức tạp thấp, sử dụng phương pháp gradient descent xác suất hiệu quả.

• Tác giả: Le Trung Khoa
• Người hướng dẫn: Prof. David Declercq, Université de Cergy Pontoise
• Trường học: Université de Cergy Pontoise
• Chuyên ngành: Sciences et Technologies de l'Information et de la Communication
• Đề tài: New Direction on Low Complexity Implementation of Probabilistic Gradient Descent Bit-Flipping Decoder
• Loại tài liệu: thèse
• Năm xuất bản: 2017
• Địa điểm: Cergy

Mục lục chi tiết

• 1. Introduction
• 1.1. Context and motivations
• 1.2. Main contributions and thesis outline
• 2. Hard decision decoders
• 2.1. Low-Density Parity-Check codes and channel models
• 2.1.1. Low-Density Parity-Check codes
• 2.1.2. LDPC decoding concepts
• 2.1.3. The channel models of LDPC decoding
• 2.1.4. Quasi-cyclic Low-Density Parity-Check codes
• 2.2. Bit-Flipping-based Decoders
• 2.2.1. Energy computation in BF decoders
• 2.2.3. Probabilistic Bit Flipping
• 2.3. Other Diversities of Hard decision Decoders
• 2.3.1. Gallager-A/Gallager-B decoders
• 2.3.2. Majority voting decoder
• 2.3.3. Differential Decoders
• 2.3.4. The noise-aided BF decoders
• 2.3.4.1. Noisy Gradient Descent Bit-Flipping decoding algorithm
• 2.3.4.2. Probabilistic Gradient Descent Bit-Flipping decoding algorithm
• 2.5. Hardware complexity of BF-based decoders
• 3. Theoretical analysis of Probabilistic Gradient Descent Bit Flipping
• 3.2. Markov Chain representation of the decoding process
• 3.2.1. Markov Chain of hard decision decoding process
• 3.2.2. Markov chain representation: GDBF and PGDBF illustrations
• 3.1. Error patterns
• 3.1.1. Weight-1 and weight-2
• 3.1.2. Weight-3 error pattern
• 3.1.3. Weight-4 error pattern
• 3.3. Frame Error Rate Evaluation
• 3.3.1. Markov Chain, algebraic and graph-theoretic considers
• 3.3.2. Classification of the states
• 3.3.3. Frame Error Rate Computation
• 3.3.4. Performance of Probabilistic Gradient Descent Bit Flipping Decoder
• 3.3.4.1. The asymptotic decoding performance of PGDBF
• 3.3.4.2. The decoding performance of PGDBF in finite number of iteration
• 4. Efficient hardware implementation of Probabilistic Gradient Descent Bit Flipping
• 4.2. The statistical analysis of PGDBF decoder
• 4.2.1. Error-floor analysis
• 4.3. The optimized hardware implementation
• 4.3.1. PGDBF global architecture
• 4.3.2. Implementation of the perturbation block
• 4.3.2.1. Cyclically-shift truncated sequences
• 4.3.2.2. Initialization with Linear Feedback Shift Register
• 4.3.2.3. Initialization with The Intrinsic-Valued Random Generator
• 4.3.3. The optimized architecture of the maximum finder
• 4.4. PGDBF Synthesis Results
• 5. A Quasi-Cyclic friendly architecture for LDPC decoders : the Variable-Node Shift Architecture
• 5.2. The Variable-Node Shift Architecture
• 5.2.1. The Conventional Architecture of QC-LDPC decoders
• 5.2.2. The Variable-Node Shift Architecture for QC-LDPC decoders
• 5.3. The Variable-Node Shift Architecture for edge-type memory LDPC decoders: flooding MS and layered MS implementation illustrations
• 5.4. The Variable-Node Shift Architecture for node-type memory LDPC decoders: GDBF implementation illustration
• 5.5. The advantages of VNSA-based LDPC decoders with different type of VNUs
• 5.6. Implementations of PGDBF with Variable-Node Shift Architecture
• 5.6.1. The implementation of PGDBF with Variable-Node Shift Architecture
• 5.6.2. An imprecise implementation of PGDBF with Variable-Node Shift Architecture
• 5.7. The synthesis results and decoding performance
• 6. Conclusion and perspectives
• appendix
• A. Some LDPC codes used in the thesis
• A.1. The Tanner QC-LDPC code (dv, dc) = (3, 6), R = 0.2
• A.2. The QC-LDPC code (dv, dc) = (3, 6), R = 0.3
• A.3. The QC-LDPC code (dv, dc) = (4, 8), R = 0.2
• B. Min Sum decoding algorithms in flooding and layered scheduling
• B.1. Flooding Min Sum decoding algorithm
• B.2. Layered Min Sum decoding algorithm
• B.3. 3 weight-20 codewords in Tanner code
• Bibliography

Tóm tắt

I. Gradient Descent và Bitflipping trong giải mã LDPC

Gradient Descent và Bitflipping là hai khái niệm trung tâm trong nghiên cứu về giải mã LDPC. Gradient Descent Bit-Flipping (GDBF) là một thuật toán giải mã quyết định cứng, trong khi Probabilistic Gradient Descent Bit-Flipping (PGDBF) thêm yếu tố xác suất vào quá trình này. PGDBF đạt được hiệu suất giải mã vượt trội so với các phương pháp Bit-Flipping truyền thống, gần với hiệu suất của các bộ giải mã quyết định mềm. Phân tích chuỗi Markov cho thấy PGDBF thoát khỏi các trạng thái bẫy, giúp cải thiện khả năng hội tụ.

1.1. Phân tích chuỗi Markov

Phân tích chuỗi Markov được sử dụng để mô hình hóa quá trình giải mã của PGDBF. Kết quả cho thấy việc thêm yếu tố xác suất giúp PGDBF thoát khỏi các trạng thái bẫy, từ đó cải thiện hiệu suất giải mã. Phương pháp này cũng dự đoán được tỷ lệ lỗi khung (Frame Error Rate) dựa trên số lần lặp và mẫu lỗi cụ thể.

1.2. Hiệu suất giải mã

PGDBF đạt hiệu suất giải mã tốt hơn so với GDBF và các phương pháp Bit-Flipping khác. Đặc biệt, PGDBF gần với hiệu suất của các bộ giải mã quyết định mềm, điều này làm nổi bật giá trị thực tiễn của phương pháp này trong các ứng dụng Machine Learning và Data Science.

II. Tối ưu hóa và hiệu quả tính toán

Việc triển khai phần cứng của PGDBF đòi hỏi sự tối ưu hóa để giảm thiểu độ phức tạp. Các phương pháp tạo tín hiệu xác suất được đề xuất nhằm giảm chi phí phần cứng mà vẫn đảm bảo hiệu suất giải mã. Kết quả tổng hợp cho thấy PGDBF triển khai với các phương pháp này chỉ cần thêm một lượng nhỏ độ phức tạp so với GDBF.

2.1. Tạo tín hiệu xác suất

Các phương pháp tạo tín hiệu xác suất như Linear Feedback Shift Register (LFSR) và Intrinsic-Valued Random Generator (IVRG) được đề xuất để giảm thiểu độ phức tạp phần cứng. Các phương pháp này dựa trên phân tích thống kê để xác định các đặc điểm quan trọng của chuỗi ngẫu nhiên nhị phân.

2.2. Kiến trúc phần cứng

Kiến trúc phần cứng của PGDBF được tối ưu hóa để giảm thiểu độ phức tạp. Kiến trúc Variable-Node Shift Architecture (VNSA) được đề xuất để triển khai PGDBF trên các mã LDPC quasi-cyclic (QC-LDPC), giúp giảm độ phức tạp phần cứng mà vẫn duy trì hiệu suất giải mã cao.

III. Ứng dụng thực tiễn và triển vọng

PGDBF có tiềm năng ứng dụng rộng rãi trong các lĩnh vực như Machine Learning, Neural Networks, và Data Science. Phương pháp này không chỉ cải thiện hiệu suất giải mã mà còn giảm thiểu độ phức tạp phần cứng, làm cho nó trở thành một giải pháp hấp dẫn cho các hệ thống thực tế.

3.1. Ứng dụng trong Machine Learning

PGDBF có thể được áp dụng trong các mô hình Machine Learning để cải thiện hiệu suất và độ chính xác. Việc giảm thiểu độ phức tạp phần cứng cũng làm cho PGDBF trở thành một lựa chọn hấp dẫn cho các ứng dụng thời gian thực.

3.2. Triển vọng nghiên cứu

Nghiên cứu trong tương lai có thể tập trung vào việc mở rộng ứng dụng của PGDBF trong các lĩnh vực khác như Statistical Methods và Computational Efficiency. Việc tối ưu hóa thêm các phương pháp tạo tín hiệu xác suất cũng là một hướng nghiên cứu tiềm năng.

Trích đoạn nội dung tài liệu

THÈSE présentée à l'Université de Cergy Pontoise École Nationale Supérieure de l'Électronique de ses Applications pour obtenir le grade de : Docteur en Science de l'Université de Cergy Pontoise Spécialité : Sciences et Technologies de l'Information et de la Communication Par LE TRUNG Khoa Équipes d'accueil : Équipe Traitement des Images et du Signal (ETIS)  CNRS UMR 8051 École Nationale Supérieure de l'Électronique et de ses Applications Titre de la thèse New Direction on Low Complexity Implementation of Probabilistic Gradient Descent Bit-Flipping Decoder Soutenue le 03/05/2017 devant la commission d'examen composée de : Emmanuel Boutillon Professeur, Lab-STICC, Université Bretagne Sud Rapporteur Chris Winstead Professeur, Utah University, USA Rapporteur Christophe Jégo Professeur, IMS, Institut Polytechnique de Bordeaux Examinateur Charly Poulliat Professeur, INP-ENSEEIHT Toulouse Examinateur Valentin Savin Dr., CEA-LETI, MINATEC, Grenoble Examinateur Fakhreddine Ghaari MCF, Université de Cergy Pontoise Encadrant David Declercq Professeur, ENSEA, Université de Cergy Pontoise Directeur de thèse Dành cho Ba Má thân yêu của con, Ba Lê Trung Nhân và Má Nguyễn Thị Kim Chấn Dành cho Chị và các em, Dành cho vợ và con gái yêu dấu, Cho tình thương của bố, mẹ dành cho con Cho tình yêu của Chị và các em, Cho tình yêu của Vợ và con To my parents, To my brothers and sisters, To my wife and daughter, For your love, À mes parents, À mes frères et soeurs, À ma femme et ma pettite fille, Acknowledgment I would like to express my deep gratitude to my advisors, Prof. David Declercq and Assoc. Fakhreddine Ghaari, for their continuously guidance, support and corrections throughout the duration of my PhD work. In particular, I would like to thank them for believing in my potential and agreeing to become my doctoral advisors, for providing meaningful ideas, for initiating fruitful collaborations with partners which enabled me to nish my thesis successfully.

I would like to thank Prof. Emmanuel Boutillon and Prof. Chris Winstead for acting as my thesis reviewers, Prof. Christophe Jégo for serving as the president of the PhD committee and Prof.

Charly Poulliat, Dr. Valentin Savin for being the ex- aminers. The comments and corrections from the committee helped me signicantly improve my thesis as well as my future career. During my PhD study, I had the opportunities of doing some research visits to Error Correction Coding Laboratory in University of Arizona, USA, under super- vision of Prof.

I would like to thank him for all of his supports, for providing me with very interesting ideas and discussions. I want to thank Xin Xiao, Nithin, Mohsen for discussing with me. For the research visit to University Po- litehnica Timisoara, Romania, I would like to thank Oana Boncalo and Alexandru Amaricai for their help and discussions. I extend my thanks to all the colleagues in ETIS, ENSEA for their friendship, funs and encouragements especially Lam Nguyen, Hong Phan, Diouf Madiagne, Alexandre Marcastel.

and Truong Nguyen-Ly from CEA-LETI, Grenoble. The administrate assistant of our laboratory, Annick Bertinoti, and administrative assis- tant of the doctoral school, Emmanuelle Travet, Naima Chalabi, were always very helpful. Many thanks go to them for taking care of the administrative issues. I would like to express my sincere gratitude to my colleagues in University of Technology (Bach Khoa University), Viet Nam National University Ho Chi Minh City, especially Ho Trung My, Huynh Thu, Hoang Trang, Do Hong Tuan, Duong Hoai Nghia for encouraging me to pursue the PhD study.

Last, but not least, my profound gratitude to my family, especially my beloved parents, Le Trung Nhan and Nguyen Thi Kim Chan, my brothers and sisters, Thanh Huong, Ngoc Lan, Minh Tuong, Trung Nghia, my wife, Van Nga and especially my lovely daughter, Sophie Vinh An, for their moral supports and encouragement throughout my life. They have inspired me and given me strength throughout my whole life. Cergy - France, May 2017 LE TRUNG KHOA i Author's publications related to the PhD Published papers [J1] K. Vasi¢, Ecient Hardware Implemen- tation of Probabilistic Gradient Descent Bit-Flipping, IEEE Transactions on Circuits and Systems I: Regular Papers , vol.

Vasíc, Ecient realization of probabilistic gradient descent bit ipping de- coders, 2015 IEEE International Symposium on Circuits and Systems (IS- CAS), pp. Vasi¢, Hardware Optimization of the Perturbation for Probabilistic Gradient Descent Bit Flipping Decoders, 2017 IEEE International Symposium on Circuits and Systems (ISCAS) , May 2017 (accepted). Le , Approaching Maximum Likeli- hood Performance of LDPC Codes by Stochastic Resonance in Noisy Iterative Decoders, Information Theory and Applications Workshop (ITA 2016) , San Diego, CA, Feb. Participation to research projects The author participated to the research project Innovative Reliable Chip Designs from Low-Powered Unreliable Components (i-RISC), supported by the Euro- pean Commission under the Seventh Framework Programme (Grant agreement number 309129) and the research project Message passing Iterative Decoders based on Imprecise Arithmetic for Multi-Objective Power-Area-Delay Opti- mization (DIAMOND) supported by the Agence National de la Recherche (ANR) under the Franco-Romanian (ANR-UEFISCDI) Join Research Pro- gram.

iii Résumé L'algorithme de basculement de bits à descente de gradient probabiliste (Probabi- listic Gradient Descent Bit Flipping - PGDBF) est récemment introduit comme un nouveau type de décodeur de décision forte pour le code de contrôle de parité à faible densité (Low Density Parity Check - LDPC) appliqué au canal symétrique binaire. En suivant précisément les étapes de décodage du décodeur déterministe Gradient Descent Bit-Flipping (GDBF), le PGDBF intègre en plus la perturbation aléatoire dans l'opération de basculement des N÷uds de Variables (VNs) et produit ainsi une performance de décodage exceptionnelle qui est meilleure que tous les décodeurs à basculement des bits (Bit Flipping - BF) connus dans la littérature, et qui approche les performances du décodeur de décision souple. Nous proposons dans cette thèse plusieurs implémentations matérielles du PGDBF, ainsi qu'une analyse théorique de sa capacité de correction d'erreurs. Avec une analyse de chaîne de Markov du déco- deur, nous montrons qu'en raison de l'incorporation de la perturbation aléatoire dans le traitement des VNs, le PGDBF s'échappe des états de piégeage qui empêchent sa convergence.

De plus, avec la nouvelle méthode d'analyse proposée, la performance du PGDBF peut être prédite et formulée par une équation de taux de trames erro- nées en fonction du nombre des itérations, pour un motif d'erreur donné. L'analyse fournit également des explications claires sur plusieurs phénomènes de PGDBF tels que le gain de re-décodage (ou de redémarrage) sur un motif d'erreur reçu. La pro- blématique de l'implémentation matérielle du PGDBF est également abordée dans cette thèse. L'implémentation classique du décodeur PGDBF, dans laquelle un gé- nérateur de signal probabiliste est ajouté au-dessus du GDBF, est introduite avec une augmentation inévitable de la complexité du décodeur.

Plusieurs procédés de génération de signaux probabilistes sont introduits pour minimiser le surcoût maté- riel du PGDBF. Ces méthodes sont motivées par l'analyse statistique qui révèle les caractéristiques critiques de la séquence aléatoire binaire requise pour obtenir une bonne performance de décodage et suggérer les directions possibles de simplica- tion. Les résultats de synthèse montrent que le PGDBF déployé avec notre méthode de génération des signaux aléatoires n'a besoin qu'une très faible complexité sup- plémentaire par rapport au GDBF tout en gardant les mêmes performances qu'un décodeur PGDBF théorique. Une implémentation matérielle intéressante et particu- lière du PGDBF sur les codes LDPC quasi-cyclique (QC-LDPC) est proposée dans la dernière partie de la thèse.

En exploitant la structure du QC-LDPC, une nouvelle architecture pour implémenter le PGDBF est proposée sous le nom d'architecture à décalage des N÷uds de Variables (Variable-Node Shift Architecture - VNSA). En implémentant le PGDBF par VNSA, nous montrons que la complexité matérielle du décodeur est même inférieure à celle du GDBF déterministe tout en préservant la performance de décodage aussi élevée que celle fournie par un PGDBF théorique. Enn, nous montrons la capacité de cette architecture VNSA à se généraliser sur d'autres types d'algorithmes de décodage LDPC. v Abstract Probabilistic Gradient Descent Bit Flipping (PGDBF) algorithm have been recently introduced as a new type of hard decision decoder for Low-Density Parity-Check Code (LDPC) applied on the Binary Symmetric Channel.

By following precisely the decoding steps of the deterministic Gradient Descent Bit-Flipping (GDBF) decoder, PGDBF additionally incorporates a random perturbation in the ipping operation of Variable Nodes (VNs) and produces an outstanding decoding performance which is better to all known Bit Flipping decoders, approaching the performance of soft decision decoders. We propose in this thesis several hardware implementations of PGDBF, together with a theoretical analysis of its error correction capability. With a Markov Chain analysis of the decoder, we show that, due to the incorporation of random perturbation in VN processing, the PGDBF escapes from the trapping states which prevent the convergence of decoder. Also, with the new proposed anal- ysis method, the PGDBF performance can be predicted and formulated by a Frame Error Rate equation as a function of the iteration, for a given error pattern.

The analysis also gives a clear explanation on several phenomenons of PGDBF such as the gain of re-decoding (or restarting) on a received error pattern. The implementa- tion issue of PGDBF is also addressed as a main part in this thesis. The conventional implementation of PGDBF, in which a probabilistic signal generator is added on top of the GDBF, is shown with an inevitable increase in hardware complexity. Several methods for generating the probabilistic signals are introduced which minimize the overhead complexity of PGDBF.

These methods are motivated by the statistical analysis which reveals the critical features of the binary random sequence required to get good decoding performance and suggesting the simplication directions. The synthesis results show that the implemented PGDBF with the proposed probabilistic signal generator method requires a negligible extra complexity with the equivalent decoding performance to the theoretical PGDBF. An interesting and particular im- plementation of PGDBF for the Quasi-Cyclic LDPC (QC-LDPC) is shown in the last part of the thesis. Exploiting the structure of QC-LDPC, a novel architecture to implement PGDBF is proposed called Variable-Node Shift Architecture (VNSA).

By implementing PGDBF with VNSA, it is shown that the decoder complexity is even smaller than the deterministic GDBF while preserving the decoding perfor- mance as good as the theoretical PGDBF. Furthermore, VNSA is also shown to be able to apply on other types of LDPC decoding algorithms. vii Contents 1 Introduction 1 1.1 Context and motivations .2 Main contributions and thesis outline. 3 2 Hard decision decoders 7 2.1 Low-Density Parity-Check codes and channel models .1 Low-Density Parity-Check codes .2 LDPC decoding concepts .3 The channel models of LDPC decoding .4 Quasi-cyclic Low-Density Parity-Check codes .2 Bit-Flipping-based Decoders .1 Energy computation in BF decoders .3 Probabilistic Bit Flipping .3 Other Diversities of Hard decision Decoders .1 Gallager-A/Gallager-B decoders .2 Majority voting decoder .3 Dierential Decoders .4 The noise-aided BF decoders .1 Noisy Gradient Descent Bit-Flipping decoding algorithm .2 Probabilistic Gradient Descent Bit-Flipping decoding algorithm 24 2.5 Hardware complexity of BF-based decoders.

28 3 Theoretical analysis of Probabilistic Gradient Descent Bit Flipping 29 3.2 Markov Chain representation of the decoding process .1 Markov Chain of hard decision decoding process .2 Markov chain representation: GDBF and PGDBF illustrations 31 3.1 Error patterns weight-1 and weight-2 .2 Weight-3 error pattern .3 Weight-4 error pattern .3 Frame Error Rate Evaluation .1 Markov Chain, algebraic and graph-theoretic considers .2 Classication of the states .3 Frame Error Rate Computation .4 Performance of Probabilistic Gradient Descent Bit Flipping Decoder .1 The asymptotic decoding performance of PGDBF .2 The decoding performance of PGDBF in nite number of it- eration. 45 4 Ecient hardware implementation of Probabilistic Gradient De- scent Bit Flipping 47 4.2 The statistical analysis of PGDBF decoder .2 Error-oor analysis .3 The optimized hardware implementation .1 PGDBF global architecture .2 Implementation of the perturbation block .1 Cyclically-shift truncated sequences .2 Initialization with Linear Feedback Shift Register .3 Initialization with The Intrinsic-Valued Random Gen- erator .3 The optimized architecture of the maximum nder .1 PGDBF Synthesis Results. 68 5 A Quasi-Cyclic friendly architecture for LDPC decoders : the Variable-Node Shift Architecture 69 5.