[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Matrix Merging Scheme and Efficient Decoding Techniques for Reconfigurable QC-LDPC Decoders

  • Published:
Journal of Signal Processing Systems Aims and scope Submit manuscript

Abstract

Many recent reconfigurable/multi-mode quasi-cyclic low density parity check (QC-LDPC) decoder designs have shown appealing implementation results in the literature. However, most of them are based on datapath multiplexing techniques with ad hoc matrix arrangement. There is still room for further interconnection reduction, throughput enhancement, and a more sophisticated early termination scheme. In this paper, we will focus on these issues and present a two-level design approach, which optimizes the design at (1) matrix merging level, and (2) module design level. First, direct multiplexing datapaths between multiple modes leads to great overhead on wiring complexity. In order to mitigate this problem, we merge multiple parity check matrices by proposing an efficient algorithm at matrix merging level, which helps to minimize multiplexer and wiring overhead. Second, for efficient decoding issues, we propose two design techniques at module design level. One is data wrapping scheme. It enhances the decoding throughput by using the data-wrapped memory with the proposed reconfigurable data-switching circuits (R-DSC) to conquer the data alignment problem and achieve multi-mode reconfigurability. The other is the adaptive early termination (AET) scheme. It can save the unnecessary decoding procedures under both high-SNR and low-SNR regions. Finally, to verify our design approach, we implement a triple-mode LDPC decoder chip which is compatible to IEEE 802.11n standard by using UMC 90 nm CMOS technology. This chip only occupies 3.32 mm2 and features high core utilization up to 70% with low power dissipation of 135.3 mW. The prototyping chip not only validates the proposed approach, but also outperforms the state-of-the-art QC-LDPC decoders for IEEE 802.11n systems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
Figure 11
Figure 12
Figure 13
Figure 14
Figure 15
Figure 16
Figure 17
Figure 18
Figure 19

Similar content being viewed by others

Notes

  1. This proof is similar to the one presented in [30].

  2. It can be shown that if an alternative base matrix is chosen as the unchanged one, the total differences are still minimized while the resulting permutation of matrices may vary.

  3. Other parameters of this estimation are: 8 iterations, code rate = 1/2, codeword length = 24p, and 2p cycles per iteration.

  4. The d is bounded by d ≤ p, where d = p implies a fully-parallel design.

  5. To our best knowledge, there are not yet other AET schemes published. The comparison here only focuses on the traditional ET and the proposed AET scheme.

References

  1. Gallager, R. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21–28.

    Article  MathSciNet  MATH  Google Scholar 

  2. MacKay, D. J. C. (1999). Good error-correcting codes based on very sparse matrices. IEEE Transactions on Information Theory, 45(2), 399–431.

    Article  MathSciNet  MATH  Google Scholar 

  3. MacKay, D. J. C., & Neal, R. M. (1997). Near Shannon limit performance of low density parity check codes. Electronics Letters, 33(6), 457–458.

    Article  Google Scholar 

  4. Blanksby, A. J., & Howland, C. J. (2002). A 690-mW 1-Gb/s 1024-b, rate-1/2 low-density parity-check code decoder. IEEE Journal of Solid-State Circuits, 37(3), 404–412.

    Article  Google Scholar 

  5. Mansour, M. M., & Shanbhag, N. R. (2003). High-throughput LDPC decoders. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 11(6), 976–996.

    Article  Google Scholar 

  6. Hocevar, D. E. (2004). A reduced complexity decoder architecture via layered decoding of LDPC codes. In Proceedings of IEEE Workshop on Signal Processing Systems (SiPS) (pp. 107–112).

  7. Shimizu, K., Ishikawa, T., Togawa, N., Ikenaga, T., & Goto, S. (2005). Partially-parallel LDPC decoder based on high-efficiency message-passing algorithm. In Proceedings of IEEE International Conference on Computer Design (ICCD) (pp. 503–510).

  8. Kang, S.-H., & Park, I.-C. (2006). Loosely coupled memory-based decoding architecture for low density parity check codes. IEEE Transactions on Circuits and Systems I: Regular Papers, 53(5), 1045–1056.

    Article  MathSciNet  Google Scholar 

  9. Darabiha, A., Carusone, A. C., & Kschischang, F. R. (2008). Block-interlaced LDPC decoders with reduced interconnect complexity. IEEE Transactions on Circuits and Systems II: Express Briefs, 55(1), 74–78.

    Article  Google Scholar 

  10. Mohsenin, T., Truong, D., & Baas, B. M. (2009). Multi-split-row threshold decoding implementations for LDPC codes. In Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS) (pp. 2449–2452).

  11. Karkooti, M., Radosavljevic, P., & Cavallaro, J. R. (2006). Configurable, high throughput, irregular LDPC decoder architecture: Tradeoff analysis and implementation. In Proceedings of IEEE international conference on Application-specific Systems, Architectures and Processors (ASAP) (pp. 360–367).

  12. Rovini, M., Gentile, G., Rossi, F., & Fanucci, L. (2007). A scalable decoder architecture for IEEE 802.11n LDPC codes. In Proceedings of IEEE Global Telecommunications Conference (GLOBECOM) (pp. 3270–3274).

  13. Gunnam, K., Choi, G., Wang, W., & Yeary, M. (2007). Multi-rate layered decoder architecture for block LDPC codes of the IEEE 802.11n wireless standard. In Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS) (pp. 1645–1648).

  14. Shih, X.-Y., Zhan, C.-Z., Lin, C.-H., & Wu, A.-Y. (2008). An 8.29 mm2 52 mW multi-mode LDPC decoder design for mobile WiMAX system in 0.13 μm CMOS process. IEEE Journal of Solid-State Circuits, 43(3), 672–683.

    Article  Google Scholar 

  15. Liu, C.-H., Yen, S.-W., Chen, C.-L., Chang, H.-C., Lee, C.-Y., Hsu, Y.-S., et al. (2008). An LDPC decoder chip based on self-routing network for IEEE 802.16e applications. IEEE Journal of Solid-State Circuits, 43(3), 684–694.

    Article  Google Scholar 

  16. Park, I.-C., & Kang, S.-H. (2005). Scheduling algorithm for partially parallel architecture of LDPC decoder by matrix permutation. In Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS) (pp. 5778–5781).

  17. Zhan, C.-Z., Shih, X.-Y., & Wu, A.-Y. (2008). High-performance scheduling algorithm for partially parallel LDPC decoder. In Proceedings of IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP) (pp. 3177–3180).

  18. IEEE (2009). IEEE standard 802.11n-2009, part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications—Amendment 5: Enhancements for higher throughput.

  19. Tanner, R. M., Sridhara, D., Sridharan, A., Fuja, T. E., & Costello, D. J., Jr. (2004). LDPC block and convolutional codes based on circulant matrices. IEEE Transactions on Information Theory, 50(12), 2966–2984.

    Article  MathSciNet  Google Scholar 

  20. Fossorier, M. P. C. (2004). Quasi-cyclic low-density parity-check codes from circulant permutation matrices. IEEE Transactions on Information Theory, 50(8), 1788–1793.

    Article  MathSciNet  Google Scholar 

  21. Tanner, R. M. (1981). A recursive approach to low complexity codes. IEEE Transactions on Information Theory, IT-27(5), 533–547.

    Article  MathSciNet  Google Scholar 

  22. Fossorier, M. P. C., Mihaljević, M., & Imai, H. (1999). Reduced complexity iterative decoding of low-density parity-check codes based on belief propagation. IEEE Transactions on Communications, 47(5), 673–680.

    Article  Google Scholar 

  23. Howland, C. J., & and Blanksby, A. J. (2001). Parallel decoding architectures for low density parity check codes. Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS), 4, 742–745.

    Google Scholar 

  24. Cocco, M., Dielissen, J., Heijligers, M., Hekstra, A., & Huisken, J. (2004). A scalable architecture for LDPC decoding. Design, Automation and Test in Europe (DATE) Conference and Exhibition Proceedings, 3, 88–93.

    Article  Google Scholar 

  25. Zhong, H., & Zhang, T. (2005). Block-LDPC: A pratical LDPC coding system design approach. IEEE Transactions on Circuits and Systems I: Regular Papers, 52(4), 766–775.

    Article  MathSciNet  Google Scholar 

  26. Shih, X.-Y., Zhan, C.-Z., & Wu, A.-Y. (2008). A 7.39 mm2 76 mW (1944, 972) LDPC decoder chip for IEEE 802.11n applications. In Proceedings of IEEE Asian Solid-State Circuits Conference (A-SSCC) (pp. 301–304).

  27. Shih, X.-Y., Zhan, C.-Z., & Wu, A.-Y. (2009). A real-time programmable LDPC decoder chip for arbitrary QC-LDPC parity check matrices. In Proceedings of IEEE Asian Solid-State Circuits Conference (A-SSCC) (pp. 369–372).

  28. Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2, 83–97.

    Article  MathSciNet  Google Scholar 

  29. Flood, M. M. (1956). The traveling-salesman problem. Operations Research, 4(1), 61–75.

    Article  MathSciNet  Google Scholar 

  30. Munkres, J. (1957). Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1), 32–38.

    Article  MathSciNet  MATH  Google Scholar 

  31. Shao, R. Y., Lin, S., & Fossorier, M. P. C. (1999). Two simple stopping criteria for turbo decoding. IEEE Transactions on Communications, 47(8), 1117–1120.

    Article  MATH  Google Scholar 

  32. Chen, Y.-H., Chen, Y.-J., Shih, X.-Y., & Wu, A.-Y. (2009). A channel-adaptive early termination strategy for LDPC decoders. In Proceedings of IEEE Workshop on Signal Processing Systems (SiPS) (pp. 226–231).

Download references

Acknowledgements

This work was partially supported by the National Science Council of Taiwan under Grant NSC 96-2220-E-002-011. The authors would like to thank Yu-Hsin Chen and Yi-Ju Chen for simulation codes of the adaptive early termination, Jen-Yang Wen for partial RTL coding of the triple-mode LDPC decoder design as well as discussions on the data wrapping scheme, and Ching-Da Chan from National Chip Implementation Center (CIC) for advices during the back-end stage.

Author information

Authors and Affiliations

  1. Graduate Institute of Electronics Engineering, National Taiwan University, 10617, Taipei City, Taiwan

    Min-An Chao, Xin-Yu Shih & An-Yeu (Andy) Wu

Authors
  1. Min-An Chao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xin-Yu Shih
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. An-Yeu (Andy) Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Min-An Chao.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chao, MA., Shih, XY. & Wu, AY.(. Matrix Merging Scheme and Efficient Decoding Techniques for Reconfigurable QC-LDPC Decoders. J Sign Process Syst 68, 183–202 (2012). https://doi.org/10.1007/s11265-011-0597-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11265-011-0597-7

Keywords

Search

Navigation