低密度奇偶校验码应用于存储系统的关键技术研究

发布时间：2018-06-08 19:49

本文选题：高密度光存储系统 + 固态硬盘　；参考：《华中科技大学》2013年博士论文

【摘要】：随着社会的发展和进步,信息技术的发展速度也越来越快,尤其是互联网的快速发展和个人数码产品的广泛应用使得人们获取信息的方式由最早的纸记笔录方式发展到数年前的多媒体时代,再演变到现在每个人都是信息发布源的“自媒体”时代。信息的爆炸式增长也对信息的存储造成了巨大的压力,这种压力来自两方面,一是飞速增长的信息量对存储容量的要求越来越高,二是数据本身的价值越来越高,甚至远远超过信息存储媒介的价值,因此对存储系统可靠性的要求也越来越高。随着人们对大容量存储系统的可靠性提出了新的要求,原有的各种编码技术开始捉襟见肘。光盘和磁介质硬盘中的里德·索罗门码(Reed-Solomon Codes, RS)、单层单元固态硬盘中的循环检验码(Bose-Chaudhuri-Hocquenghem Codes, BCH)以及分布式存储系统中的纠删码均已经到达或接近其极限,迫切需要一种新的编码。低密度奇偶校验码(Low-density Parity-check Codes, LDPC)虽然有着已知最接近香农限的纠错能力,但因其编译码过程比较复杂,在其发现初期并未进入实际应用领域。而随着近年来半导体技术的飞速发展,人们已经可以实现基于超大规模集成电路的LDPC码编译码工作,因此继实际应用于通信领域后,LDPC码必将在存储领域得到广泛应用。本文正是基于这种考虑,对LDPC码在各种存储环境下的应用展开了前瞻性研究。目前,光存储系统虽然面临硬盘存储系统的严峻挑战但仍然凭借自己批量复制成本极低、保存时间长达百年并且不存在误删除可能性的优势,在存储市场仍然占据着一席之地。由于新一代高密度光盘存储系统的数据密度远远高于DVD等早期低密度光存储系统,因此广泛用于光盘的RS码在将不能很好的满足新一代高密度光盘的应用；而随机构造型LDPC码可以通过计算机筛选最优的构造矩阵,因此可以代替RS码更好地为人们提供基于高密度光存储系统的可靠存储服务,本论文首先对高密度光存储中应用随机构造LDPC码的可行性及其实用性进行了深入论证,说明随机构造的LDPC码确实可以用于高密度光盘存储系统,并且能够有效提高高密度光盘存储系统的可靠性和有效存储容量。固态硬盘则是近年来迅速兴起的新型硬盘,凭借其高速度、高IOPS以及完全抗震等传统磁介质硬盘无法实现的特性很快的占领了一部分商用存储系统和个人存储系统的市场。但是,由于固态硬盘存储介质自身的特点,它存在着耐久度不高、读写不对称等致命缺陷。代数结构的非随机构造LDPC码则因其编译码开销较小,能提供极佳的纠错能力,大码长的编译码,因此非常适合应用于固态硬盘。本论文从构造适合固态硬盘存储系统的代数结构非随机LDPC码的角度对固态硬盘存储系统进行了深入研究,并得出可以通过缩短技术以牺牲一定码率为代价构造出适合固态硬盘存储系统的合理构造的准循环LDPC码以帮助提高固态硬盘的可靠性。此外,本文还针对固态硬盘存储系统面临的另一大挑战——耐久度不高的问题,提出通过细粒度数据重构的方式有效延长多级单元(Multi Level Cell, MLC)和三级单元(Trinary Level Cell, TLC)固态硬盘的使用寿命。分布式存储系统是存储系统发展史上的一大突破,它不仅将磁盘阵列(Redundant Array Of Independent Disks, RAID)的优点——基于廉价桌面硬盘搭建高性能高可靠性的存储系统——进一步发扬光大,还可以通过网络将不同的存储子系统相互连接,甚至可以搭建基于广域网的高性能存储系统。但是,以往对分布式存储的研究主要集中于可靠性方面,对分布式存储的效率和经济价值的研究较少。相对于目前广泛应用于分布式存储系统中的水平纠删码和垂直纠删码,LDPC码有着纠错能力更强并且译码工作是线性时间开销等特点,因此同样非常适合成为新一代分布式存储系统的纠错码。本文在对LDPC码进行深入研究后,将其应用领域延伸至分布式存储系统,首先研究了适合分布式存储系统的LDPC码分块方法,随后提出由于纠删码策略和复制策略的综合成本不同,可以由分布式存储子系统通过博弈的方法优化存储策略,并在通过博弈论的数学方法证明夏普里值的存在性后,给出了分布式存储系统LDPC码纠删策略和复制策略之间的纳什均衡解。综上所述,本文系统地研究了LDPC码应用于存储领域中的各项关键技术,解决了LDPC码在光存储、固态硬盘存储和分布式存储系统中的应用难题,并取得了实质性进展,进一步扩展了LDPC码的应用范围。
[Abstract]:With the development and progress of the society, the development of information technology is becoming faster and faster. In particular, the rapid development of the Internet and the wide application of personal digital products make people get information from the earliest form of paper record to the multimedia times a few years ago. The explosive growth of information has also caused enormous pressure on the storage of information. This pressure comes from two aspects. One is that the rapid growth of information is becoming more and more demanding for storage capacity. The two is that the value of the data itself is higher and higher, even far more than the value of the information storage medium, so the storage system is reliable. The demand for sex is getting higher and higher.
As people put forward new requirements for the reliability of large capacity storage systems, the original coding techniques begin to be difficult. Reid Soromenma (Reed-Solomon Codes, RS) in disk and magnetic media hard disk, cyclic test code (Bose-Chaudhuri-Hocquenghem Codes, BCH) in single layer solid state hard disk and distributed storage system The erasure codes in the system have reached or close to their limits, and there is an urgent need for a new code. Low-density Parity-check Codes (LDPC) has the error correction ability known closest to Shannon limit, but its coding and decoding process is complex and has not entered the actual application field at the beginning of its occurrence. With the rapid development of semiconductor technology, LDPC code encoding and decoding based on large scale integrated circuits can be realized, so LDPC code will be widely used in the storage field after application in the field of communication. This paper is based on this consideration, the application of LDPC code in various storage environments is prospectively studied.
At present, although the optical storage system is facing the severe challenge of the hard disk storage system, it still has the advantage of saving time for a hundred years and does not have the possibility of deleting it, and still occupies a place in the storage market. The data density of the new generation of high-density optical disk storage system is far higher than DVD and so on. The early low density optical storage system, so the RS code widely used in optical disk will not satisfy the application of the new generation of high-density optical disk, while the mechanism modeling LDPC code can screen the optimal structure matrix by computer, so it can replace the RS code to provide people with the reliable storage service based on the high density optical storage system better. In this paper, the feasibility and practicability of the random construction of LDPC codes in high-density optical storage are discussed in this paper. It shows that the random structure of LDPC code can be used in the high density optical disk storage system and can effectively improve the reliability and effective storage capacity of the high-density optical disk storage system.
Solid-state hard disk is a new type of hard disk which has springing up rapidly in recent years. With its high speed, high IOPS and completely aseismic traditional magnetic medium hard disk can not realize the characteristics quickly occupy a part of the commercial storage system and personal storage system market. However, because of the characteristics of the solid hard disk storage medium itself, it has a durability. The non random structural LDPC code of algebraic structure is very suitable for application to solid state hard disk because of its low coding and decoding overhead, which can provide excellent error correction ability and large code length. Therefore, this paper is based on the construction of the solid hard disk storage system for the algebraic structure of the non random LDPC code. The storage system has been studied deeply, and the quasi cyclic LDPC code which is suitable for the solid state hard disk storage system can be constructed by shortening the technology at the cost of a certain bit rate to help improve the reliability of the solid disk. In addition, this paper also aims at another challenge facing the solid-state hard disk storage system - durability. The high problem is to prolong the service life of the Multi Level Cell (MLC) and the three stage unit (Trinary Level Cell, TLC) solid state hard disk by means of fine grained data reconfiguration.
Distributed storage system is a breakthrough in the history of storage system development. It not only makes the advantages of disk array (Redundant Array Of Independent Disks, RAID) - based on cheap desktop hard disk to build high performance and high reliability storage system - further development, and can also connect different storage subsystems to each other through the network. It can even build a high performance storage system based on wide area network. However, the previous research on distributed storage is mainly focused on reliability, and there are few studies on the efficiency and economic value of distributed storage. Compared with the horizontal erasure code and vertical erasure code widely used in distributed storage systems, LDPC codes have a correction. More error ability and decoding work are linear time overhead and so on, so it is also very suitable for a new generation of distributed storage system error correction code. After the in-depth study of LDPC code, this paper extends its application field to distributed storage system. First, the LDPC code block method suitable for distributed storage system is studied. Due to the different comprehensive cost of erasure code and replication strategy, the distributed storage subsystem can optimize the storage strategy by game method, and after proving the existence of SHARP in SHARP through game theory, the Nash equilibrium solution between the erasure strategy of the distributed storage system and the replication strategy is given.
To sum up, this paper systematically studies the key technologies used in the storage field of LDPC code, and solves the problem of application of LDPC code in optical storage, solid-state hard disk storage and distributed storage system. It has made substantial progress and further expanded the application model of LDPC code.
【学位授予单位】：华中科技大学
【学位级别】：博士
【学位授予年份】：2013
【分类号】：TP333

【相似文献】