Abstract
Given the potential for bit flipping of data on a memory medium, a high-speed parallel Bose-Chaudhuri-Hocquenghem (BCH) error correction scheme with modular characteristics, combining logic implementation and a look-up table, is proposed. It is suitable for data error correction on a modern field programmable gate array full with on-chip embedded memories. We elaborate on the optimization method for each part of the system and analyze the realization process of this scheme in the case of the BCH code with an information bit length of 1024 bits and a code length of 1068 bits that corrects the 4-bit error.
摘要
鉴于存储介质上的数据存在位翻转的可能, 提出一种模块化的、 高速并行的 Bose–Chaudhuri–Hocquenghem (BCH) 纠错方案, 该方案结合了逻辑实现和查找表. 所提方案适用于具有片上嵌入式存储器的现场可编程门阵列的数据纠错. 详细阐述了系统各部分的优化方法, 并分析了该方案在 BCH 码信息位长度为 1024 位、 码长为 1068 位且可纠正 4 位错误情况下的实现过程.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ayinala M, Parhi KK, 2011. High-speed parallel architectures for linear feedback shift registers. IEEE Trans Signal Process, 59(9):4459–4469. https://doi.org/10.1109/TSR2011.2159495
Bellorado J, Kavcic A, 2010. Low-complexity soft-decoding algorithms for Reed-Solomon codes—part I: an algebraic soft-in hard-out chase decoder. IEEE Trans Inform Theory, 56(3):945–959. https://doi.org/10.1109/TIT.2009.2039073
Berlekamp E, 2015. Algebraic Coding Theory. World Scientific, London, UK.
Cho SG, Kim D, Choi J, et al., 2014. Block-wise concatenated BCH codes for NAND flash memories. IEEE Trans Commun, 62(4):1164–1177. https://doi.org/10.1109/TCOMM.2014.021514.130287
Hu GH, Sha J, Wang ZF, 2017. High-speed parallel LFSR architectures based on improved state-space transformations. IEEE Trans Very Large Scale Integr Syst, 25(3):1159–1163. https://doi.org/10.1109/TVLSI.2016.2608921
Jung J, Yoo H, Lee Y, et al., 2015. Efficient parallel architecture for linear feedback shift registers. IEEE Trans Circ Syst II, 62(11):1068–1072. https://doi.org/10.1109/TCSII.2015.2456294
Kim D, Narayanan KR, Ha J, 2018. Symmetric block-wise concatenated BCH codes for NAND flash memories. IEEE Trans Commun, 66(10):4365–4380. https://doi.org/10.1109/TCOMM.2018.2839606
Kim J, Sung W, 2012. Low-energy error correction of NAND flash memory through soft-decision decoding. EURASIP J Adv Signal Process, 2012(1):195. https://doi.org/10.1186/1687-6180-2012-195
Kumar HP, Sripati U, Shetty KR, 2012. High-speed and parallel approach for decoding of binary BCH codes with application to flash memory devices. Int J Electron, 99(5):683–693. https://doi.org/10.1080/00207217.2011.643498
Massey J, 1969. Shift-register synthesis and BCH decoding. IEEE Trans Inform Theory, 15(1):122–127. https://doi.org/10.1109/TIT.1969.1054260
Moon TK, 2005. Error Correction Coding: Mathematical Methods and Algorithms. John Wiley & Sons, Inc., Hoboken, USA.
Neubauer A, Freudenberger J, Kühn V, 2007. Coding Theory: Algorithms, Architectures, and Applications. John Wiley & Sons, Ltd., Chichester, UK.
Paar C, 1996. A new architecture for a parallel finite field multiplier with low complexity based on composite fields. IEEE Trans Comput, 45(7):856–861. https://doi.org/10.1109/12.508323
Pandian KKS, Ray KC, 2015. Five decade evolution of feedback shift register: algorithms, architectures and applications. Int J Commun Netw Distr Syst, 15(2–3):279. https://doi.org/10.1504/IJCNDS.2015.070974
Pei TB, Zukowski C, 1992. High-speed parallel CRC circuits in VLSI. IEEE Trans Commun, 40(4):563–657. https://doi.org/10.1109/26.141415
Shieh MD, Sheu MH, Chen CH, et al., 2001. A systematic approach for parallel CRC computations. J Inform Sci Eng, 17(3):445–461. https://doi.org/10.6688/JISE.2001.17.3.3
Unal B, Akoglu A, Ghaffari F, et al., 2018. Hardware implementation and performance analysis of resource efficient probabilistic hard decision LDPC decoders. IEEE Trans Circ Syst I, 65(9):3074–3084. https://doi.org/10.1109/TCSI.2018.2815008
Xu FX, Liu Y, Liu YQ, et al., 2013. Design and implementation of mode reconfigurable NAND flash error correcting system. J Centr South Univ Sci Technol, 44(5):1918–1925 (in Chinese).
Yang CG, Emre Y, Chakrabarti C, 2012. Product code schemes for error correction in MLC NAND flash memories. IEEE Trans Very Large Scale Integr Syst, 20(12):2302–2314. https://doi.org/10.1109/TVLSI.2011.2174389
Zhang M, Wu F, Xie CS, 2015. A novel optimization algorithm for Chien search of BCH codes in NAND flash memory devices. IEEE Int Conf on Networking, Architecture and Storage, p.106–111. https://doi.org/10.1109/NAS.2015.7255204
Zhang XM, 2019. A low-power parallel architecture for linear feedback shift registers. IEEE Trans Circ Syst II, 66(3):412–416. https://doi.org/10.1109/TCSII.2018.2860934
Zhang XM, Parhi KK, 2005. High-speed architectures for parallel long BCH encoders. IEEE Trans Very Large Scale Integr Syst, 13(7):872–877. https://doi.org/10.1109/TVLSI.2005.850125
Author information
Authors and Affiliations
Corresponding authors
Additional information
Project supported by the National Natural Science Foundation of China (No. 61973280) and the China Postdoctoral Science Foundation (No. 2019M661069)
Contributors
Yang LIU conceived the research and drafted the manuscript. Jie LI provided the theory analysis and the instruction. Debiao ZHANG and Kaiqiang FENG contributed to the analysis and manuscript preparation. Han WANG and Jinqiang LI performed the simulations. Yang LIU and Jie LI revised and finalized the paper.
Compliance with ethics guidelines
Yang LIU, Jie LI, Han WANG, Debiao ZHANG, Kaiqiang FENG, and Jinqiang LI declare that they have no conflict of interest.
Rights and permissions
About this article
Cite this article
Liu, Y., Li, J., Wang, H. et al. A BCH error correction scheme applied to FPGA with embedded memory. Front Inform Technol Electron Eng 22, 1127–1139 (2021). https://doi.org/10.1631/FITEE.2000323
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1631/FITEE.2000323
Key words
- Error correction algorithm
- Bose-Chaudhuri-Hocquenghem (BCH) code
- Field programmable gate array (FPGA)
- NAND flash