臺灣博碩士論文加值系統

在本篇論文中，提出了一個適用於IEEE 802.11n 標準的低密度奇偶檢查碼之解碼器，以及一個能進行軟性判決(Soft-Decision)之解調變器。可支援所需的四種編碼率，並且也能夠處理四種解調變的類型，在標準所規定之各個調變-編碼組合(Modulation Coding Scheme, MCS)情況下，滿足資料傳輸速度的需求。同時依照標準的設計流程，從解碼器規格與相關研究的研讀，功能的模擬，架構的設計，到實際電路的設計與運用場效可程式邏輯閘陣列(Field-Programmable Gate Array, FPGA)的實做和驗證。

為了要達到高資料傳輸速度的要求，針對幾個解碼演算法做了研究與討論，考量到奇偶檢查矩陣的構成和解碼收斂的速度，本篇論文採用”分層信賴度傳遞演算法”(Layered Belief Propagation Algorithm, LBPA)來進行解碼。此外，由於所需要儲存的訊息(Message)跟一般常用的演算法不同，它也可以節省一些記憶體的使用，再加上引用最小集合演算法(Min Sum Algorithm)，在犧牲可以接受的效能損失情形下，達到簡化大量運算複雜度與節省硬體消耗的目的。

在解碼效能模擬部分，我們利用可加性白色高斯雜訊 (Additive White Gaussian Noise)通道當做我們的通道模型。在解碼效能最差，也就是利用64-QAM作調變，而使用編碼率是5/6的情形下，本解碼器可以在信號雜訊比(Signal to Noise Ratio, SNR)還不到14.5dB時，將位元錯誤率(Bit Error Rage)降至10-6以下。而另一方面，在解碼效能最佳，也就是利用BPSK作調變，而使用編碼率是1/2的情形下，本解碼器可以將位元錯誤率降至10-6以下，而此時所需的信號雜訊比大約是3.75dB。

本論文提出的低密度奇偶檢查碼之解碼器與能進行軟性判決之解調變器，是用以Xilnix Virtex-4 XC4VLX60-Ff668為FPGA模組的展示電路板來實現，經過驗證，其最大的操作頻率是116.15MHz，同時可提供的資料傳輸速度在不同的編碼率的情況下，確實都可以滿足IEEE 802.11n標準的需求。

In this thesis, standard specification study, functional simulation, architecture design and circuit design along with FPGA implementation of a multiple coding rates LDPC decoder for IEEE 802.11n communication systems is presented.

In order to achieve the high data rate requirement, several decoding algorithms are discussed. As considering the construction of the parity check matrices and the decoding convergence speed, we chose "Layered Belief Propagation Algorithm" as decoding algorithm. Besides, it can also save some memory resources since the messages need to store are less than the conventional decoding algorithm "Log-Likelihood Ratio Sum Product Algorithm". Furthermore, the use of min sum algorithm sacrifices acceptable performance loss but reduces the large computational complexity while doing the update the messages during the iterative decoding
process. In addition to processing different modulation types, a soft de-mapper is also constructed to provide log likelihood ratio for LDPC decoder to do the decoding procedure.

In system performance simulation, we apply the additive white Gaussian noise (AWGN) as the channel impairments to estimate our decoding performance under several different modulation types and coding rates. In the worst case of the system simulation which is under 64-QAM and coding rate 5/6, the BER is under 10-6 at SNR less than 14.5dB. On the other hands, the system simulation with BPSK modulation and coding rate 1/2 is the best case whose BER is under 10-6 at SNR about 3.75dB.

The proposed LDPC decoder and soft de-mapper are implemented by FPGA system broad whose FPGA model is Virtex-4 XC4VLX60-FF668. The maximum clock frequency can reach 116.15MHz and the estimated maximum data rates for different coding rates all meet the data rate requirement of the specification.

1 Introduction
1.1 Overview of Error Control Coding
1.1.1 Error Control Coding in Communication Systems
1.1.2 Classification of Error Control Coding
1.2 Motivation of the Thesis
1.3 Organization of the Thesis
2 LDPC Codec overview for 802.11n
2.1 Low-Density Parity Check Codes
2.1.1 Introduction of Block Codes
2.1.2 Regular and Irregular LDPC Codes
2.2 LDPC Decoder Specification for 802.11n
2.3 LDPC Encoding Algorithm
2.3.1 Classification of Encoding Algorithms
2.3.2 Encoder Architecture for 802.11n
2.4 Message Passing Algorithm
2.4.1 Tanner Graph
2.4.2 Message Passing Algorithm of Bit Node
2.4.3 Message Passing Algorithm of Check Node
2.5 LDPC Decoding Algorithm
2.5.1 Sum Product Algorithm in the Probability Domain
2.5.2 Sum Product Algorithm in the Log Domain
2.5.3 Layered Belief Propagation Algorithm
2.5.4 Min-Sum Algorithm
3 Architecture Design
3.1 Conventional Design
3.1.1 Fully Parallel Architecture
3.1.2 Serial Architecture
3.1.3 Partial Parallel Architecture
3.2 Proposed LDPC Decoder Architecture
3.2.1 Design Issues
3.2.2 Memory Banks of L(Qi)s (Message) and L(rj,i )s (Extrinsic Information)
3.2.3 Log-Likelihood Ratio Storage Processor
3.2.4 Bit Node Unit (BNU)
3.2.5 Check Node Unit (CNU)
3.2.6 Iterative Decoding Procedures
3.3 Soft De-mapper Architecture
3.3.1 Soft De-mapping Algorithm
3.3.2 Simplified Estimation
4 Functional Simulation
4.1 Design Flow
4.2 Environment of System Simulation
4.2.1 Channel Model
4.2.2 Estimation of Iteration Times
4.3 Floating-Point Simulation
4.4 Fixed-Point Simulation
4.4.1 Word-length Determination
4.4.2 Floating-Point and Fixed-Point Comparisons
5 Circuit Design
5.1 Soft De-mapper
5.2 Multiple Code Rate of LDPC Decoder
5.2.1 Memory Banks of Message and Extrinsic Information
5.2.2 Log-Likelihood Ratio Storage Processor
5.2.3 Bit Node Unit (BNU)
5.2.4 Check Node Unit (CNU)
6 Implementation and Measurements
6.1 FPGA Implementation
6.1.1 Specification of FPGA System Board
6.1.2 Reduced Version for FPGA Implementation
6.1.3 FPGA Emulation and Verification of Reduced Version
6.2 Performance Measurement
7 Discussions and Conclusions
7.1 Discussions
7.2 Future Works
7.3 Conclusions

[1] C. Shannon, ”Amathematicaltheoryofcommunication,” Bell System Technical Journal, vol. 27, pp. 379-423 and pp. 623-656, July, October 1948.
[2] R. G. Gallager, ”Low-density parity-check codes,” IRETrans. Inform. Theory, vol.IT-8, pp.21-28, Jan. 1962.
[3] R. G. Gallager, Low-DensityParity-CheckCodes, MIT Press, Cambridge, 1963.
[4] S. Lin and D. J. Costello, Error Control Coding, 2nd ed. Upper Saddle River, NJ: Prentice Hall, 2004.
[5] R. M. Tanner, ”A recursive approach to low complexity codes,” IEE Trans. Inform. Theory, pp. 533-547, Sept. 1981.
[6] D. J. C. MacKay and R. M. Neal, ”Near Shannon limit performance of low density parity check codes,” Electron.Lett.,32(18):1645-46,1996.
[7] M. Sipser and D. A. Spielman, ”Expander codes,” IEEE Trans. Inform. Theory, vol. 42, pp. 1710-1722, Nov. 1996.
[8]D. J. C. MacKay, ”Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, vol. 45, pp. 399-431, March 1999.
[9]M. G.Luby, M. Mitzenmacher, M. A. Shokollahi, and D. A. Spielman, ”Improved low-density parity check codes using irregular graphs,” IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 585-598, Feb. 2001.
[10] T. J. Richardson and R. L. Urbanke,”Efficient encoding of low-density parity check codes,” IEEETrans.Inform.Theory, vol. 47, no. 2, pp. 638-635, Feb. 2001.
[11] D. Haley, A. Grant, and J. Buetefuer, ”Iterative encoding of low-density parity check codes,” in Proc. IEEE GLOBECOM, Nov. 2002. vol. 2, pp. 1289-1293.
[12] D. E. Hocevar, ”A reduced complexity decoder architecture via layered decoding of LDPC codes,” in Proc. SIPS, 2004, pp. 107-112.
[13] J. Hagenauer, E. Offer,and L. Papke,”Iterative decoding of binary block and convolutional codes,” IEEE Trans. Inform. Theory, vol. 42, no. 2, pp. 429-445,
March1996.
[14] P. Radosavljevic, A. deBaynast, and J. R. Cavallaro, ”Optimized message passing schedules for LDPC decoding,” presented at the 39th Asilomar Conference on Signals, Systems and Computers, 2005, pp. 591-595.
[15] X. Y. Hu, E. Eleftheriou, D. M. Arnold, and A. Dholakia, ”Efficient implementation of the sum-product algorithm for decoding LDPC codes,” IEEE Global Telecomm. Conf., vol. 2, Nov. 2001, pp. 25-29.
[16] M. P. C. Fossorier, M. Mihaljevic, and H. Imai, ” Reduced complexity of low-density parity check codes based on belief propagation,” IEEE Trans. Comm., vol. 47, no. 5, pp. 673-680. May 1999.
[17] A. J. Blanksby and C. J. Howland, ”A690-mW1Gb/s1024-b,rate-1/2low-density parity-check code decoder,” IEEE JSSC, March 2002, pp. 404-412.
[18] S. Sivakumar, ”VLS Iimplementation of encoder and decoder for low-density parity check codes,” Masters Thesis, TexasA&MUniversity,Dec.2001.
[19] F. Kienle, T. Brack, and N. Wehn, ”A synthesizable IP core for DVB-S2 LDPC code decoding,” in Proc. DATE, 2005, pp. 100-105.
[20] EWC.(2005Dec.). HT PHY Specification. [Online].Available: http://www.enhancedwirelessconsortium.org/home/EWCPHY spec V127.pdf
[21] D. Chase, ”A class of algorithms for decoding block codes with channel measurement information,” IEEE Trans. Inform. Theory, vol. IT-18, pp. 170-182, Jan. 1972.
[22] F. Tosato and P. Bisaglia, ”Simplified soft-output demapper for binary interleaved COFDM with application to HIPERLAN/2,” Imaging Systems Laboratory, HP Laboratories Bristol, HPL-2001-246, October 10th, 2001.
[23] R. Pyndiah, A. Glavieux, A. Picart, and S. Jacq, ”Near optimum decoding of products codes,” in Proc. IEEE Global Telecommunication Conf., 1994, vol. 113.
[24] S. Haykin, Communication Systems, 4th ed., New York: John Wiley and Sons,
2001.
[25] P. Urard, E. Yeo, L. Paumier, P. Georgelin, T. Michel, V. Lebars, E. Lantreibecq, and B.Gupta, ”A 135Mb/s DVB-S2 compliant codec based on 64800b LDPC and BCH codes,” IEEE Int. Solid-State Circuit Conf. Dig Tech. Papers, 2005, pp. 446-447,609.
[26] T. Ishikawa, K. Shimizu, T. Ikenaga, and S. Goto, ”High-throughput decoder for low density parity check codes,” in Proc. Asia and South Pacific Conf., 2006, pp. 112-113.
[27] M. M. Mansour and N. R. Shanbhag, ”High-throughput LDPC decoders,” IEEE Trans. on VLSI systems, vol. 11, no. 6, pp. 976-996, Dec. 2003.
[28] Z. Cui and Z. Wang, ”A170Mbps(8176,7156)quasi-cyclic LDPC decoder implementation with FPGA,” in Proc. ISCAS, 2006, pp. 5095-5098