顧孟愷臺灣大學：資訊工程學研究所黎煥昇Li, Huan-ShengHuan-ShengLi2007-11-262018-07-052007-11-262018-07-052005http://ntur.lib.ntu.edu.tw//handle/246246/53974Gallager’s Low-Density Parity-Check (LDPC) codes have recently received a lot of attention because of their excellent performance and low decoding complexity. Since that the hardware complexity is lower than that of Turbo codes, LDPC codes have been widely considered as next-generation error-correcting codes for many real-word applications. The quality of LDPC code is crucial in determining the coding gain and implementation complexity of LDPC hardware decoders. Regular quasi-cyclic LDPC codes are used due to its friendliness to hardware implementation. This thesis presented a genetic algorithm (GA) based regular quasi-cyclic LDPC code search algorithm with hardware and coding gain considerations. Hardware constraint, average girth and bit error rate simulation are used as criterions to select the best code candidates in GA algorithm. An efficient LDPC matrix representation is proposed for the GA algorithm. The results show that our algorithm can efficiently pick hardware implementation friendly LDPC codes with good coding gain performance.ABSTRACT 1 1. INTRODUCTION 2 1.1. DIGITAL COMMUNICATION SYSTEM OVERVIEW 2 1.2. LOW DENSITY PARITY CHECK CODE 3 1.2.1. LDPC Code Construction 3 1.2.2. Encoding 5 1.2.3. Girth 6 1.2.4. Minimum Distance 7 1.2.5. Decoding 7 1.3. REGULAR QUASI-CYCLIC LDPC CODE 8 1.3.1. Regular Quasi-cyclic LDPC Code Construction 8 1.3.2. The Upper Bound of Girth 9 1.3.3. The Upper Bound of Minimum Distance 11 1.3.4. Redundant Check 12 2. RELATED WORKS 15 2.1. ALGEBRAIC CONSTRUCTED LDPC CODE 15 2.2. DVB-S2 LDPC CODE 16 2.3. RATE-COMPATIBLE LDPC CODE 18 2.4. CONVOLUTIONAL LDPC CODE 20 3 HARDWARE ISSUES 21 3.1 THE HARDWARE ARCHITECTURE OF LDPC DECODER 21 3.2 OVERLAPPED DECODING ALGORITHM 22 3.3 MULTITHREAD DECODING ALGORITHM 25 3.3.1 Scalable Factor Effect 25 4 HARDWARE-AWARE GA-BASED LDPC CODE SEARCH 27 4.1 GENETIC ALGORITHM OVERVIEW 27 4.2 GA-BASED LDPC CODE SEARCH 29 4.2.1 GA Encoding 29 4.2.2 Population 29 4.2.3 Hardware-oriented Constraint 30 4.2.3.1 Overlapped Decoding Constraint 30 4.2.3.2 Multithread Decoding Constraint 31 4.2.4 Performance-oriented Constraint 31 4.2.4.1 Average Girth 31 4.2.4.2 Bit Error Rate 32 4.2.5 Crossover 32 4.2.6 Mutation 32 4.2.7 Two Phases Section Strategy 32 4.2.8 GA Code Search Procedure 33 5 SIMULATION RESULTS 35 5.1 SIMULATION 1 35 5.2 SIMULATION 2 36 5.3 SIMULATION 3 37 5.4 SIMULATION 4 38 5.5 SIMULATION 5 39 5.6 SIMULATION 6 40 5.7 SIMULATION 7 41 5.8 SIMULATION 8 42 6 CONCLUSION AND FURTURE WORK 43 7 APPENDIX 44 7.1 PARAMETERS OF ALGEBRAIC CONSTRUCTED QC CODE 44 7.2 GA CODE SEARCH SIMULATED PROGRAM 46 7.2.1 Flow Chart of GA Code Search 46 7.2.2 Module Description 47 7.3 BRUTE FORCE CODE SEARCH SIMULATED PROGRAM 50 7.3.1 Flow Chart of Brute Force Code Search 50 7.3.2 Module Description 51 REFERENCE 521787206 bytesapplication/pdfen-US類迴旋低密度奇偶校驗碼圍長基因演算法重疊解碼多重執行緒解碼QC-LDPCGirthGAOverlapped decodingMultithread decodingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53974/1/ntu-94-R92922084-1.pdf