Design and Construction of Algebraic Codes for Enhancing Information Integrity in Data Storage Systems

Abstract

Data storage devices have become ubiquitous in present day information driven society. It is essential that storage devices exhibit very high levels of data integrity. Therefore, data integrity is a fundamental aspect of storage, security and reliability. NAND and NOR Flash memories [Chen, Y. 2008], [Mielke, N et al. 2008], [Gal, E. et al. 2005], [Jiang, A et al. 2010] are widely used for data storage because of their compactness and low power consumption. Data stored in non-volatile memory is usually critical to proper system operation, and corruption of data can lead to system failure. Hence data corruption is a major concern in applications that rely on nonvolatile memory for long-term data storage. Many techniques have been employed to improve the reliability of these devices. These techniques can be divided into two categories. In the first approach, improvements are carried out in the fabrication process to reduce the Raw Bit Error Rate (RBER). The second option is to use Error Correction Techniques to improve the RBER level to levels that are deemed acceptable to most users [Sun, F. et al. 2007], [Sun,F et al. 2006], [Chen, Y. and Parhi, K. 2004], [Mielke, N. et al. 2008]. Error Control Code (ECC) techniques (i.e., techniques capable of detecting and correcting errors in processed and stored data by using redundant bits in addition to information bits according to a given coding strategy) [Pless, V. and Huffman, W.C. 1998] have been commonly used at board level for many years to enhance the reliability of memory systems [Bertozzi, D. et al. 2005]. However, as memory chips become denser, they also become more prone to errors, as a consequence of both the reduced cell size and the increased cell count within a single die. Moreover, read and write operations are made more critical by both technology scaling down and higher speed requirements. On the other hand, higher and higher reliability is required for storage systems in a large variety of applications. Generally high storage density is achieved by reducing the size of the elementary memory cell. However, for non-volatile memories, some physical phenomena makesv an aggressive reduction of the memory cell size difficult [Atwood, G. et al. 1997], [Wang, Z. and Karpovsky, M. 2011]. An alternative solution to reduce the cost per bit and increase the storage density is to adopt the multilevel approach. It consists of placing a multiplicity of charge amount in the floating gate, thus allowing the cell to store more than one bit. However, the multilevel storage requires the consideration of three basic issues: (i) accuracy of write operation (necessary to place the correct amount of charge of the floating gate). (ii) precision of the charge sensing (required to discriminate the different threshold voltages). (iii) stability of charge over an extended time period. Although Multi Level Cell (MLC) memory has higher density than Single Level Cell (SLC) memory, MLC is more vulnerable to errors because small fluctuation of the charge amount in the floating gate and slight variation of gate voltage result in misreading of stored data [Sun, F. et al. 2007], [Sun,F et al. 2006], [Maeda, Y et al. 2009], [Lin, H et al. 2002], [Ankolekar, P. P et al.2010]. ECC is a cost effective method to enhance the integrity of data storage systems. Very stringent values of application BER, which would ordinarily require complex and expensive fabrication techniques as well as expensive materials, can be met very easily by employing ECC. Storage devices characterized by high RBER values can be made to yield application BERs as small as desired by the use of suitable ECC techniques. The fraction of erroneous bits that remain uncorrected after applying ECC constitute the uncorrectable bit error rate (UBER). UBER is a useful reliability metric for data storage devices and is used to specify the data corruption rate in the information given to the user after correction by ECC algorithms. ECC algorithms can also correct errors that may manifest at any later stage during the life of the device. Hence use of ECC techniques has been widely accepted by the semiconductor manufacturing industry to enhance the RBER to levels demanded by applications. In this thesis, we have made an attempt to synthesize a number of codes for use in data storage systems with error correcting capability exceeding the state of art asvi specified in the industry documentation. In the initial part of the thesis, the focus is on the synthesis of codes for enhancing data integrity in flash memories composed of SLCs. While studying the flash memory organization, two memory models, namely Memory model 1 and Memory model 2 are identified and the codes are synthesized separately for these memory models. As compared to the current standard, [Mehnert, A. 2008] where six bits in errors can be corrected over a span of 4096 information bits (one sector), we propose codes that can correct up to nine bits in error per sector. The various generator polynomials are computed. As the performance of the error control code improves with increase in length, we were motivated to consider the combination of two sectors to constitute the information block. For this scenario, we propose codes that can correct up to eighteen bits in error over a span of 8192 bits (two sectors). Further, using Memory model 2, we have synthesized and proposed codes that can correct up to eighteen bits in errors per sector. The performance of these codes is quantified by computing values of the probability of decoding error. To summarize, the main objective of this work has been to design, construct and synthesize a large group of codes which can be used to enhance the data integrity levels associated with flash memory devices so as to make them useful in a wider class of applications. With a view to make these synthesized codes, readily acceptable to industry, we have strictly adhered to the memory architecture specified in the literature.