Study Of Dual Normalized Min-sum Algorithm And Its Partial Parallel Architecture

In communication systems, the noise of the channel introduces errors to the trans-mitted data, and channel coding can detect and correct errors in the transmitted data, sochannel coding can increase the reliability of the communication system. Low densi-ty parity check codes (LDPC codes) have been shown to approach Shannon’s limit inAWGN channel, and it is one of the most attractive field in channel coding. Though thetechniques of LDPC codes develop fast, many problems are still need to be solved suchas improving the decoding performance of fixed-point algorithms and make good tradeofamong decoder’s complexity and throughput.In this dissertation, we firstly give a review of research on LDPC. Based on that, wediscussed the topics around the decoding algorithm of LDPC code, parallel algorithms offinding the two smallest values and their hardware implementation, data packing schemein partial parallel decoders. Finally, a LDPC decoder is proposed which supports all themodes of2304bit LDPC codes in WiMAX. The main contributions of this dissertationare listed as following:1. The check node processing in Min-Sum algorithm is an approximation to thatin Sum Product algorithm, so Min-Sum algorithm has a performance loss. NormalizedMin-Sum algorithm can force the mean of check node results in Min-Sum algorithm e-qual to the mean of check node results in BP algorithm, so it has better BER performancethan Min-Sum algorithm. In this paper, we proposed a dual normalized min-sum algo-rithm which uses two normalized factors to further improve the BER performance ofthe Min-Sum algorithm, and the proposed algorithm has the same decoding complexi-ty as normalized Min-Sum algorithm. Simulation based LDPC wordlength optimizationmethod is improved, and the workload of simulation is saved.2. Algorithms of finding the two smallest values in a group are very important inMin-Sum and Min-Sum based algorithms. Parallel algorithms can find the two smallestvalues in one cycle, but they consume more chip size. Two parallel algorithms are pro-posed, one is the modified minimum-comparison sorting (MXS) approach, and the otheris new tree structure (NTS) approach. MXS approach simplifies the process of finding thesecond minimum value in minimum-comparison sorting approach, and it has the samecomputing latency as minimum-comparison sorting approach but has less hardware cost. NTS approach has a little increase in the complexity than MXS approach, but has muchless latency, so it makes good tradeof among the complexity and the speed.3. LDPC decoder using parallel processing unit can achieve high throughput. Lay-ered decoding approach saves the size of the memory bank and has higher decoding con-vergence speed. A new partial parallel LDPC decoder structure is proposed using parallelprocessing unit and layered approach. Compared to others, the proposed structure sup-ports larger range of throughput, and makes good tradeof between the complexity andthe throughput. A parallel DN-MS computing unit is also designed based on NTS ap-proach. In the proposed decoder, a new packing scheme for posterior probability data ofvariable node is proposed: the memory bank has several RAMs, and every RAM has onereading alignment unit and one connecting network. The proposed packing scheme haslarge bandwidth without accessing conflict, and its control unit and connecting networkhas low complexity. A pre-decoding decoder is proposed for the QC-LDPC codes whosebase matrix is an approximate lower triangular matrix. The proposed decoder could startthe decoding process before it gets the whole code word’s channel messages, and itachieves a high throughput.4. At last, a multi rate partial parallel QC-LDPC decoder is designed for all coderates of2304bit LDPC codes in WiMAX. At last, FPGA implementation results andlogic synthesis results are provided for the proposed decoder, and the results show thatthe decoder achieves a good tradeof between the complexity and the throughput.