Novel algorithm to construct QC-LDPC codes for high data rate applications
Abstract
A novel algorithm to construct highly sparse, quasi-cyclic low-density parity check codes with large girth and high code rates that can be employed in high data rate applications is proposed. In this paper, a sparse girth six base matrix is designed, which is then substituted by a difference exponent matrix derived from a basic exponent matrix based on the powers of a primitive element in a finite field Fq, to build long code-length and high code rate QC-LDPC codes. The proposed exponent matrix generation is a one-time procedure and hence, less number of computations is involved. According to the simulation results, the proposed QC-LDPC code with high code rate showed faster encoding-decoding speeds and reduced storage overhead compared to conventional LDPC, conventional QC-LDPC codes, and traditional RS codes. Simulation results showed that the QC-LDPC codes constructed using the proposed algorithm performed very well over AWGN channel. Hardware implementation of the proposed high rate QC-LDPC code (N = 1248, R = 0.9) in Software Defined Radio platform using the NI USRP 2920 hardware device displays very low bit error rates compared to conventional QC-LDPC codes and conventional LDPC codes of similar size and rate. Thus, from both the simulation and hardware implementation results, the proposed QC-LDPC codes with high code rate were found to be suitable for high data rate applications such as cloud data storage systems and 5G wireless communication systems.
Full Text:
PDFReferences
W. K. Lin, D. M. Chiu, Y. B. Lee, Erasure Code Replication Revisited, in: 4th International Conference on Peer-to-Peer Computing (P2P 2004), IEEE, Zurich,Switzerland, 2004, pp. 90–97.
H. Weatherspoon, J. Kubiatowicz, Erasure coding vs. replication: A quantitative comparison, in: International Workshop on Peer-to-Peer Systems (IPTPS), Vol. 1,2002
A. K. Mishra, J. L. Hellerstein, W. Cirne, and C. R. Das, “Towards characterizing cloud backend workloads: insights from google compute clusters,” ACM SIGMETRICS Performance Evaluation Review, vol. 37, no. 4, pp. 34–41, 2010.
C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li and S. Yekhanin, Erasure coding in Windows Azure storage, in Proc. of the 2012 USENIX Annual Technical Conference, 2012, pp. 15–26
Facebooks erasure coded hadoop distributed file system (hdfs-raid),https://github.com/facebook/hadoop-20.
S. Reed and G. Solomon. Polynomial codes over certain finite fields. Journal of the society for industrial and applied mathematics, 8(2):300–304, 1960.
Li and B. Li, “Erasure coding for cloud storage systems: a survey,” Tsinghua Science and Technology, vol. 18, no. 3, pp. 259–272, 2013.
Osama Khan, Randal Burns, James Plank, William Pierce, and Cheng Huang. 2012. Rethinking erasure codes for cloud file systems: Minimizing I/O for recovery and degraded reads. In Proceedings of the 10th USENIX Conference on File and Storage Technologies (FAST’12).
James Plank and Huang,Tutorial at USENIX FAST 2013 – “Erasure Coding for Storage Applications”,2013.
Plank, J. S., and Xu, L., 2006. Optimizing cauchy reed-solomon codes for fault-tolerant network storage applications. In Proceedings of the IEEE International Symposium on Network Computing and Applications
J. Blomer, M. Kalfane, M. Karpinski, R. Karp, M. Luby, and D. Zuckerman. An XOR-based erasure-resilient coding scheme. Technical Report TR-95-048, International Computer Science Institute, August 1995.
Benjamin G., Birger K., Nuno S., 2007. Exploring high performance distributed file storage using LDPC codes, Journal Parallel Computing Vol. 33, Issue 4-5.
A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran,“Network coding for distributed storage systems,” IEEE transactions on information theory, vol. 56, no. 9, pp. 4539–4551, 2010.
J. S. Plank and M. G. Thomason, “A practical analysis of low-density parity-check erasure codes for wide-area storage applications,” in 2004 International Conference on Dependable Systems and Networks (DSN), June 2004, pp. 115–124.
S. I. Park, H. M. Kim, Y. Wu and J. Kim, "A Newly Designed Quarter-Rate QC-LDPC Code for the Cloud Transmission System," in IEEE Transactions on Broadcasting, vol. 59, no. 1, pp. 155-159, March 2013
Park, G.S., Song, H. A novel hybrid P2P and cloud storage system for retrievability and privacy enhancement. Peer-to-Peer Netw. Appl. 9, 299–312 (2016).
Y.Wei, Y. W. Foo, K. C. Lim, and F. Chen, “The auto-configurable ldpc codes for distributed storage,” in 2014 IEEE 17th International Conference on Computational Science and Engineering, Dec 2014, pp. 1332–1338.
Y. Wei, F. Chen, and K. C. Lim, “Large LDPC codes for big data storage,” in Proceedings of the ASE BigData & SocialInformatics 2015. ACM, p. 1.,2015
Y. Wei and F. Chen, “expanCodes: Tailored LDPC codes for big data storage,” in 2016 IEEE 14th Intl Conf on Dependable,Autonomic and Secure Computing, 14th Intl Conf on Pervasive Intelligence and Computing, 2nd Intl Conf on Big Data Intelligence and Computing and Cyber Science and Technology Congress, Aug2016, pp. 620–625.
R. Gallager, “Low-density parity-check codes,” IRE Transactions on Information Theory, vol. 8, no. 1, pp. 21–28, Jan 1962.
D. J. C. MacKay, ” Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory,vol.45, no.2, pp. 399-431, Mar. 1999
S. Myung, K. Yang, and J. Kim, “Quasi-cyclic LDPC codes for fast encoding,” IEEE Transactions on Information Theory, vol. 51, no. 8,pp. 2894–2901, Aug. 2005.
M. P. Fossorier, “Quasi-cyclic low-density parity-check codes from circulant permutation matrices,” IEEE Trans. Inf. Theory, vol. 50, no. 8, pp. 1788–1793, Aug. 2004.
Salah Abdulghani Alabady,"Binary and Non-Binary Low Density Parity Check Codes: A Survey",International Journal of Information Engineering and Applications 2018; 1(3): 104-117
H. Dehghani, M. Ahmadi, S. Alikhani and R. Hasni, 2012. Calculation of Girth of Tanner Graph in LDPC Codes. Trends in Applied Sciences Research, 7: 929-934.
Amirzade, F., Alishahi, M.,(Rafsanjani) Sadeghi, M. (2019). An algebraic construction of QC-LDPC codes based on powers of primitive elements in a finite field and free of small etss. algebraic structures and their applications, 6(1), 129-140.
H. S. G. et al., "SpreadStore: A LDPC Erasure Code Scheme for Distributed Storage System," 2010 International Conference on Data Storage and Data Engineering, 2010, pp. 154-158.
Hitachi Vantara,Scale out S3 object storage platform, built on microservices architecture that can be deployed as software only or an appliance,Architecture fundamentals, hcp-for-cloud-scale-whitepaper.pdf,November 2021
H. Park, D. Lee and J. Moon, "LDPC Code Design for Distributed Storage: Balancing Repair Bandwidth, Reliability, and Storage Overhead," in IEEE Transactions on Communications, vol. 66, no. 2, pp. 507-520, Feb. 2018
S. Vafi and N. R. Majid, Combinatorial design-based quasi-cyclic LDPC codes with girth eight ,Digit Commun Netw. 4 (2018), 296– 300.
Ying Yu Tai, L. Lan, Lingqi Zeng, S. Lin and K. A. S. Abdel-Ghaffar, "Algebraic construction of quasi-cyclic LDPC codes for the AWGN and erasure channels," in IEEE Transactions on Communications, vol. 54, no. 10, pp. 1765-1774, Oct. 2006
V Bhuvaneshwari, C. Tharini, Novel construction of quasi-cyclic low-density parity-check codes with variable code rates for cloud data storage systems, ETRI Journal, Wiley Publications,08 November 2022, https://doi.org/10.4218/etrij.2021-0449
DOI: https://doi.org/10.31449/inf.v47i8.4937
This work is licensed under a Creative Commons Attribution 3.0 License.