臺灣博碩士論文加值系統

低密度同位檢查碼 (low-density parity-check code, LDPC code) 具有接近Shannon理論極限的錯誤更正效能。但相較於其他錯誤更正碼，LDPC碼的編碼與解碼通常需要更多的耗電與處理時間，使得它的實際應用受到限制。在本論文中，我們針對設計有效率的LDPC碼系統提出了以下技術：一、低時間延遲的編碼方式；二、數種用於解碼的技巧，如減少節點運算的方法、智慧型的排程、提早停止解碼的條件等；三、具有實作考量的碼結構。
首先，我們針對許多最新通訊標準採用的雙對角 (dual-diagonal) LDPC碼，提出有效率的編碼演算法。我們提出的編碼方式採用雙向的同位位元 (parity bit) 更正，可分離編碼過程中的資料相依性，以達到更高的產量、更低的時間延遲與更好的硬體利用率。
其次，為了減少LDPC解碼器的耗電量與計算時間延遲，我們提出了減少節點運算的方法與智慧型動態排程策略。我們提出的運算減少方法包含了一自動調整的停止條件與一節點停用機制。此節點停用機制可以更準確地判斷節點的可靠度。在另一方面，我們提出了兩種動態解碼排程策略。相較於傳統排程方法，第一種策略以較不貪婪的演算法來選擇下一個要更新的訊息 (message)。此作法用更少的訊息運算量有效地降低了error floor。第二種策略在排序與選擇下一待更新的訊息時，使用了不同的衡量標準，兼具了訊息差值 (residual) 以外的考量。此種排程策略在可達到的錯誤率與所需訊息運算量上，都優於傳統排程方法。
接著，我們設計了數種低複雜度的解碼提早停止條件。利用雙對角碼的結構特性，我們提出的提早偵測解碼成功的機制，可以排除非必要的解碼迴圈 (iteration)。此機制減少了可解碼區塊的平均解碼迴圈數，而不會損失錯更正效能。此外，我們也提出了兩種解碼失敗的提早終止機制。第一種機制利用解碼器中的syndrome檢查功能來偵測無法解碼的區塊。第二種機制利用相鄰解碼迴圈產生的hard decision來追蹤解碼狀況並偵測解碼失敗的收斂。這些機制均可在損失很少或不損失錯誤更正效能的情況下，有效地節省解碼迴圈數。
最後，我們針對較長碼長的應用，提出了一種有利於實作的結構化LDPC碼。我們修改漸進式邊增長 (progressive edge-growth) 演算法來建構所提出之多層次類循環 (hierarchical quasi-cyclic) 碼。藉由在同位檢查矩陣中加入有利於實作的兩層結構，只需要少量的第二層子矩陣，就可以改善類循環碼的錯誤更正效能。此外，類循環碼的解碼器架構經修改後可用於解碼所提出之結構化碼，以達到更好的錯誤率與更快的解碼速度。

For error correction in communication systems, low-density parity-check (LDPC) codes have been shown to have near-Shannon-limit performance. However compared with other error correction codes, encoding and decoding LDPC codes always require considerable power and processing time which would limit their practical use. In this thesis, the following techniques are proposed for efficient LDPC coding systems: 1) low-latency encoding, 2) decoding with node operation reduction, intelligent scheduling, and early stopping criteria, and 3) code structure with implementation benefits.
First, an efficient encoding algorithm is proposed for dual-diagonal LDPC codes, which are adopted by many next generation communication standards. The proposed two-way parity bit correction encoding scheme breaks up the data dependency within the encoding process to achieve higher throughput, lower latency, and better hardware utilization.
Next, to reduce the power consumption and computation latency of LDPC decoders, a node operation reduction scheme and intelligent dynamic scheduling strategies are presented. The proposed operation reduction scheme consists of an adaptive stopping criterion and a node deactivation mechanism. The node deactivation mechanism improves the accuracy of node reliability estimation. On the other hand, two dynamic scheduling strategies for LDPC decoders are proposed. The first strategy improves the conventional scheduling algorithms by selecting the next message to update less greedily. The less-greedy scheduling effectively lowers the error floor with fewer message updates. The second strategy orders and selects the next message to update using a different metric with considerations beyond the residuals of messages. This farsighted scheduling strategy outperforms the conventional scheduling algorithms in terms of achievable error rate and required number of message updates.
Furthermore, several low-complexity early stopping criteria for LDPC decoders are presented. An early detection mechanism for successful decoding is proposed to eliminate unnecessary iterations by exploiting the structure of dual-diagonal codes. Average number of decoding iterations for decodable blocks can be reduced without error performance degradation. On the other hand, two types of early termination mechanisms are proposed for unsuccessful decoding. In the first mechanism, the syndrome-check block in the decoder is utilized to detect undecodable blocks. In the second mechanism, the hard decisions made during consecutive iterations are used to monitor the decoding status and detect the convergence of unsuccessful decoding. These mechanisms can achieve significant iteration saving with less or no error performance loss.
Finally, we propose a class of implementation-friendly structured LDPC codes for long code length applications. A modified progressive edge-growth algorithm is used to construct the proposed hierarchical quasi-cyclic (H-QC) codes. By adding implementation-friendly two-level hierarchy with limited types of second-level submatrices in the parity check matrix, error performance is improved substantially over QC codes. We also show that QC-based decoder architecture can be easily applied to H-QC decoders to achieve better coding gain and higher throughput performance.

誌謝 i
摘要 iii
Abstract v
Contents vii
List of Figures xiii
List of Tables xvii
Chapter 1 Introduction 1
1.1 Overview of LDPC Codes 1
1.2 Encoding 3
1.3 Decoding 4
1.4 Code Structure 8
1.5 Contributions and Organizations of This Thesis 9
Chapter 2 Low-Latency Encoding Algorithm for Dual-Diagonal Codes Based on Two-Way Parity Bit Correction 11
2.1 Motivation 11
2.2 Dual-Diagonal LDPC Codes 13
2.3 Proposed Encoding Procedure 14
2.3.1 Encoding Concept 14
2.3.2 Proposed Encoding Scheme 16
2.3.3 Encoding Example 18
2.4 Proposed Encoder Architecture 19
2.4.1 Parallel Architecture 19
2.4.2 Serial Architecture 21
2.4.3 Analysis of Hardware Complexity and Encoding Latency 22
2.5 Implementation Results 24
2.5.1 Results of The Proposed Encoder Architecture 24
2.5.2 Results of Multi-Rate Encoder 27
2.5.3 Encoder Performance Comparison 28
2.6 Summary 32
Chapter 3 Decoding with Reduced Node Operations and Intelligent Scheduling 33
3.1 Node Operation Reduced Decoding 33
3.1.1 Motivation 33
3.1.2 Stopping Criterion with an Adaptive Threshold 35
3.1.3 Proposed Node Deactivation Technique 38
3.1.4 Performance 41
3.1.5 Summary 44
3.2 Less-Greedy and Farsighted Dynamic Scheduled Decoding 45
3.2.1 Existing Decoding Schedules 45
3.2.2 Proposed Dynamic Scheduling Strategies 46
3.2.3 Simulation Results 58
3.2.4 Complexity Analysis 63
3.2.5 Summary 64
Chapter 4 Stopping Criteria for Successful and Unsuccessful Decoding 65
4.1 Early Detection of Successful Decoding for Dual-Diagonal Codes 65
4.1.1 Motivation 65
4.1.2 Proposed Early Detection Mechanism for Successful Decoding 67
4.1.3 Simulation Results 68
4.1.4 Summary 70
4.2 Early Termination of Unsuccessful Decoding 71
4.2.1 Motivation 71
4.2.2 Proposed Syndrome-Based Early Termination 71
4.2.3 Proposed Hard-Decision-Based Early Termination 75
4.2.4 Simulation Results and Discussion 77
4.2.5 Complexity Analysis 87
4.2.6 Summary 90
Chapter 5 Design of Long Length Codes with Performance and Implementation Considerations 93
5.1 Hierarchical Quasi-Cyclic Codes 93
5.2 Code Construction 96
5.3 Decoder Implementation Issues 97
5.4 Simulation Results 101
5.5 Summary 103
Chapter 6 Conclusions and Future Work 105
6.1 Conclusions 105
6.2 Future Work 107
Bibliography 109

[1]R. G. Gallager, “Low density parity check codes,” IRE Trans. Inform. Theory, vol. IT-8, pp. 21–28, Jan. 1962.
[2]D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electron. Lett., vol. 32, no. 18, pp. 1645–1646, Aug. 1996. Reprinted Electron. Lett., vol. 33, no. 6, pp. 457–458, Mar. 1997.
[3]“IEEE Standard for Information technology--Telecommunications and information exchange between systems--Local and metropolitan area networks--Specific requirements Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 5: Enhancements for Higher Throughput,” IEEE Std 802.11n-2009 (Amendment to IEEE Std 802.11-2007 as amended by IEEE Std 802.11k-2008, IEEE Std 802.11r-2008, IEEE Std 802.11y-2008, and IEEE Std 802.11w-2009), Oct. 2009.
[4]“IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Broadband Wireless Access Systems,” IEEE Std 802.16-2009 (Revision of IEEE Std 802.16-2004), May 2009.
[5]“IEEE Standard for Information technology--Telecommunications and information exchange between systems--Local and metropolitan area networks--Specific requirements Part 3: Carrier Sense Multiple Access with Collision Detection (CSMA/CD) Access Method and Physical Layer Specifications - Section Four, ” IEEE Std 802.3-2008 (Revision of IEEE Std 802.3-2005), Dec. 2008.
[6]“IEEE Standard for Information technology - Telecommunications and information exchange between systems - Local and metropolitan area networks - Specific requirements. Part 15.3: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for High Rate Wireless Personal Area Networks (WPANs) Amendment 2: Millimeter-wave-based Alternative Physical Layer Extension,” IEEE Std 802.15.3c-2009 (Amendment to IEEE Std 802.15.3-2003), Oct. 2009.
[7]“IEEE Standard for Local and Metropolitan Area Networks Part 20: Air Interface for Mobile Broadband Wireless Access Systems Supporting Vehicular Mobility - Physical and Media Access Control Layer Specification,” IEEE Std 802.20-2008, Aug. 2008.
[8]European Telecommunications Standards Institude (ETSI), “Digital video broadcasting (dvb) second generation framing structure for broadband satellite applications, EN 302 307 V1.1.1.” [Online]. Available: www.dvb.org
[9]W. Zhang, Y. Guan, W. Liang, D. He, F. Ju, and J. Sun, “An Introduction of the Chinese DTTB Standard and Analysis of the PN595 Working Modes,” IEEE Trans. Broadcast., vol. 53, pp. 8–13, Mar. 2007.
[10]W. E. Ryan, “An introduction to LDPC codes,” in CRC Handbook for Coding and Signal Processing for Recording Systems, B. Vasic and E. M. Kurtas, Eds. Boca Raton, FL: CRC, 2005.
[11]X.-Y. Hu, E. Eleftheriou, and D-M. Arnold, “Regular and irregular progressive edge-growth Tanner graphs,” IEEE Trans. Inform. Theory, vol. 51, pp. 386–398, Jan. 2005.
[12]H. Chen and Z. Cao, “A modified PEG algorithm for construction of LDPC codes with strictly concentrated check-node degree distributions,” in Proc. IEEE Wireless Communications and Networking Conference (WCNC 2007), pp. 564–568, Mar. 2007.
[13]T. Richardson, “Error floors of LDPC codes,” in Proc. 41st Annual Allerton Conf. Commun., Control Comp., Monticello, IL, pp. 1426–1435, Oct. 2003.
[14]T. J. Richardson and R. L. Urbanke, “Efficient encoding of low-density parity-check codes,” IEEE Trans. Inform. Theory, vol.47, pp. 638–656, Feb. 2001.
[15]Z. Cai, J. Hao, P.H. Tan, S. Sun, and P.S. Chin, “Efficient encoding of IEEE 802.11n LDPC codes,” Electron. Lett., vol. 42, no. 25, pp. 1471–1472, Dec. 2006.
[16]D.-U. Lee, W. Luk, C. Wang, and C. Jones, “A flexible hardware encoder for low-density parity-check codes,” in Proc. IEEE Symp. Field-Programmable Custom Computing Machines (FCCM 2004), pp. 101–111, Apr. 2004.
[17]S. Kopparthi and D.M. Gruenbacher, “A high speed flexible encoder for low-density parity-check codes,” in Proc. IEEE Int. Midwest Symp. Circuits and Systems (MWSCAS 2006), pp. 347–351, Aug. 2006.
[18]Z. Khan and T. Arslan, “Pipelined implementation of a real time programmable encoder for low density parity check code on a reconfigurable instruction cell architecture,” in Proc. Design, Automation & Test in Europe Conference & Exhibition (DATE 2007), pp. 1–6, Apr. 2007.
[19]J. K. Kim, H. Yoo, and M. H. Lee, “Efficient encoding architecture for IEEE 802.16e LDPC codes,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E91-A, pp. 3607–3611, Dec. 2008.
[20]Y. Sun, M. Karkooti, and J. R. Cavallaro, “High Throughput, Parallel, Scalable LDPC Encoder/Decoder Architecture for OFDM Systems,” in Proc. IEEE Dallas/CAS Workshop on Design, Applications, Integration and Software, pp. 39–42, Oct. 2006.
[21]S. Kopparthi and D. M. Gruenbacher, “Implementation of a flexible encoder for structured low-density parity-check codes,” in Proc. IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PacRim 2007), pp. 438–441, Aug. 2007.
[22]C. Yoon, E. Choi, M. Cheong, and S.-K. Lee, “Arbitrary bit generation and correction technique for encoding QC-LDPC codes with dual-diagonal parity structure,” in Proc. IEEE Wireless Communications and Networking Conference, (WCNC 2007), pp. 662–666, Mar. 2007.
[23]C. Yoon, J.-E. Oh, M. Cheong, and S.-K. Lee, “A hardware efficient LDPC encoding scheme for exploiting decoder structure and resources,” in Proc. IEEE Vehicular Technology Conference (VTC 2007-Spring), pp. 2445–2449, Apr. 2007.
[24]F. Kienle and N. Wehn, “Low complexity stopping criterion for LDPC code decoders,” in Proc. IEEE Vehicular Technology Conference (VTC 2005-Spring), pp. 606–609, May-June 2005.
[25]T. Lehnigk-Emden, C. Brehm, T. Brack, N. Wehn, F. Berens, and C. Derdiyok, “Energy Consumption of Channel Decoders for OFDM-based UWB Systems,” in Proc. IEEE International Conference on Ultra-Wideband (ICUWB 2007), pp. 447–452, Sept. 2007.
[26]J. Li, X.-H. You, and J. Li, “Early stopping for LDPC decoding: convergence of mean magnitude (CMM),” IEEE Commun. Lett., vol. 10, no. 9, pp. 667–669, Sept. 2006.
[27]D. Shin, K. Heo, S. Oh, and J. Ha, “A stopping criterion for low-density parity-check codes,” in Proc. IEEE Vehicular Technology Conference (VTC 2007-Spring), pp. 1529–1533, Apr. 2007.
[28]D. Alleyne and J. Sodha, “On stopping criteria for low-density parity-check codes,” in Proc. International Symposium on Communication Systems, Networks and Digital Signal Processing (CSNDSP 2008), pp. 633–637, July 2008.
[29]E. Zimmermann, G. Fettweis, P. Pattisapu, and P. K. Bora, “Reduced complexity LDPC decoding using forced convergence,” in Proc. Int. Symp. Wireless Personal Multimedia Communications (WPMC 2004), vol. 3, pp. 243–246, Padova, Italy, Sept. 2004.
[30]A. Blad, O. Gustafsson, and L. Wanhammar, “Early decision decoding methods for low-density parity-check codes,” in Proc. Swedish System-on-Chip Conference, Tammsvik, Sweden, Apr. 2005.
[31]S.-C. Chou, M.-K. Ku, and C.-Y. Lin, “Switching activity reducing layered decoding algorithm for LDPC codes,” in Proc. IEEE International Symposium on Circuits and Systems (ISCAS 2008), pp. 528–531, May 2008.
[32]D. Levin, E. Sharon, and S. Litsyn, “Lazy scheduling for LDPC decoding,” IEEE Commun. Lett., vol. 11, no. 1, pp. 70–72, Jan. 2007.
[33]E. Cavus and B. Daneshrad, “A computationally efficient selective node updating scheme for decoding of LDPC codes,” in Proc. IEEE Military Communications Conference (MILCOM 2005), vol. 3, pp. 1375–1379, Oct. 2005.
[34]D. E. Hocevar, “A reduced complexity decoder architecture via layered decoding of LDPC codes,” in Proc. IEEE Workshop on Signal Processing Systems (SIPS 2004), pp. 107–112, Oct. 2004.
[35]J. Goldberger and H. Kfir, “Serial schedules for belief-propagation: analysis of convergence time,” IEEE Trans. Inform. Theory, vol. 54, pp. 1316–1319, Mar. 2008.
[36]A. I. V. Casado, M. Griot, and R. D. Wesel, “LDPC decoders with informed dynamic scheduling,” IEEE Trans. Commun., vol. 58, pp. 3470–3479, Dec. 2010.
[37]T. A. Feo and M. G. C. Resende, “Greedy randomized adaptive search procedures,” Journal of Global Optimization, vol. 6, pp. 109–133, 1995.
[38]Y. Li and W. E. Ryan, “Bit-reliability mapping in LDPC-coded modulation systems,” IEEE Commun. Lett., vol. 9, no. 1, pp. 1–3, Jan. 2005.
[39]Y.-H. Chen, Y.-J. Chen, X.-Y. Shih, and A.-Y. Wu, “A channel-adaptive early termination strategy for LDPC decoders,” in Proc. IEEE Workshop on Signal Processing Systems (SiPS 2009), pp. 226–231, Oct. 2009.
[40]C.-Y. Lin and M.-K. Ku, “Early detection of successful decoding for dual-diagonal block-based LDPC codes,” Electron. Lett., vol. 44, no. 23, pp. 1368–1370, Nov. 2008.
[41]R. Y. Shao, S. Lin, and M. P. C. Fossorier, “Two simple stopping criteria for turbo decoding,” IEEE Trans. Commun., vol. 47, pp. 1117–1120, Aug. 1999.
[42]D. J. C. MacKay, “Encyclopedia of sparse graph codes,” http://www.inference.phy.cam.ac.uk/mackay/codes/data.html.
[43]N. Miladinovic and M. Fossorier, “Systematic recursive construction of LDPC codes,” IEEE Commun. Lett., vol. 8, no. 5, pp. 302–304, May 2004.
[44]Y. Chen and K. K. Parhi, “Overlapped message passing for quasi-cyclic low-density parity check codes,” IEEE Trans. Circuits and Syst. I, vol. 51, pp. 1106–1113, June 2004.
[45]M. Karkooti and J.R. Cavallaro, “Semi-parallel reconfigurable architectures for real-time LDPC decoding,” in Proc. Int. Conf. Information Technology: Coding and Computing (ITCC), vol. 1, pp. 579–585, Apr. 2004.
[46]M. M. Mansour and N. R. Shanbhag, “Low-power VLSI decoder architectures for LDPC codes,” in Proc. Int. Symp. Low Power Electronics and Design (ISLPED 2002), pp. 284–289, Aug. 2002.
[47]K. Shimizu, T. Ishikawa, N. Togawa, T. Ikenaga, and S. Goto, “A parallel LSI architecture for LDPC decoder improving message-passing schedule,” in Proc. IEEE Int. Symp. Circuits and Systems (ISCAS 2006), pp. 5099–5102, May 2006.
[48]T. Ishikawa, K. Shimizu, T. Ikenaga, and S. Goto, “High-Throughput LDPC Decoder for Long Code-Length,” in Proc. Int. Symp. VLSI Design, Automation and Test, pp. 1–4, Apr. 2006.
[49]M. M. Mansour and N. R. Shanbhag, “High-throughput LDPC decoders,” IEEE Trans. VLSI Systems, vol. 11, pp. 976–996, Dec. 2003.
[50]Altera Corporation, http://www.altera.com.
[51]R. M. Neal, “Software for Low Density Parity Check Codes,” http://www.cs.toronto.edu/~radford/ftp/LDPC-2006-02-08/index.html.
[52]M. Yang, W. E. Ryan, and Y. Li, “Design of efficiently encodable moderate-length high-rate irregular LDPC codes,” IEEE Trans. Commun., vol.52, pp. 564–571, Apr. 2004.
[53]T. Brack, M. Alles T. Lehnigk-Emden, F. Kienle, N. Wehn, F. Berens, and A. Ruegg, “A survey on LDPC codes and decoders for OFDM-based UWB systems,” in Proc. IEEE Vehicular Technology Conference (VTC 2007-Spring), pp. 1549–1553, Apr. 2007.
[54]T. Tian, C. Jones, J. D. Villasenor, and R. D. Wesel, “Construction of irregular LDPC codes with low error floors,” in Proc. IEEE International Conference on Communications (ICC 2003), pp. 3125–3129, May 2003.
[55]R. M. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inform. Theory, vol. 27, pp. 533–547, Sept. 1981.
[56]I. Djurdjevic, J. Xu, K. Abdel-Ghaffar, and S. Lin, “A class of low-density parity-check codes constructed based on Reed-Solomon codes with two information symbols,” IEEE Commun. Lett., vol. 7, no. 7, pp. 317–319, July 2003.
[57]T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke, “Design of capacity-approaching irregular low-density parity-check codes,” IEEE Trans. Inform. Theory, vol. 47, pp. 619-637, Feb. 2001.
[58]S. Myung, K. Yang, and J. Kim, “Quasi-cyclic LDPC codes for fast encoding,” IEEE Trans. Inform. Theory, vol. 51, pp. 2894-2901, Aug. 2005.