Error Correction Systems for Nano-Scale Fault-Tolerant Memories

纳米级容错存储器的纠错系统

• 批准号: 0634969
• 负责人: Bane Vasic
• 金额: $ 30万
• 依托单位: University of Arizona
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-10-01 至 2010-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0634969&HistoricalAwards=false
• 关键词: Error; Correction; Systems; Nano; Scale

In the proposed research, highly reliable memories made of unreliable components will be developedand characterized in terms of their complexity and ability to retain the stored information. The main challenge is that in nano-scale systems both the storage elements and logic gates are faulty. It is in contrast to the state-ofthe- art systems where only the memory elements are considered unreliable while error correction encoders and decoders are assumed to be made of reliable logic gates.The set of problems that will be addressed in this research can be condensed into the following question:given n memory cells and m universal logic gates which fail following a known random mechanism, what is the optimal memory architecture which stores the maximum number of information bits for the longest period of time with arbitrary low probability of error? This complex problem can be divided and reformulated in many ways, but, interestingly, even some of the most fundamental questions related to this problem are still unanswered. The most important question is related to the following two fundamentally different approaches in fault-tolerant memories: (i) To improve reliability, the logic gate resources may be invested into a von Neumann multiplexing scheme. In this way, one can build highly redundant reliable networks that simulate the function of universal logic gates, and then use such better gates to build an error correction encoder and decoder. (ii)Alternatively, the logic gate resources may be invested into building a more powerful error correcting code (i.e.,decoder) capable of handling both memory elements as well as logic gates errors. Which of these twoapproaches is optimal for a given failure mechanism? On a broad scale, is it better to deal with a reliability issue on a device or on a system level?Intellectual Merit:The unique feature of the nano-systems that both the storage elements and logic gates are unreliable makes the problem of ensuring fault-tolerance theoretically very important, because the process of error correction is not error-free as assumed in classical information theory. Making error correcting codes stronger and transmitters and receivers more complex will not necessarily improve the performance of a system. It is likely that for a given failure mechanism, there is a trade off between receiver complexity and its performance.Our approach to developing fault-tolerant memory architectures is based on a method developed byTaylor and refined by Kuznetsov. Taylor and Kuznetsov (TK) showed that memory systems have nonzerocomputational (storage) capacity, i.e. the redundancy necessary to ensure reliability grows asymptoticallylinearly with the memory size. Two fundamental open problems that will be addressed in this research aredetermining storage capacity of nano-scale memories and the development of capacity approaching fault-tolerant architectures. The equivalence of the restoration phase in the TK method and faulty Gallager-B algorithm (as explained in Project Description), will enable us to tackle these and other important problems in reliable storage on unreliable media using the large body of knowledge in codes on graphs and iterative decoding gained in the past decade.Broader Impact:This program will contribute significantly to the evolution of data storage technologies and the informationinfrastructure in the United States of America and abroad. Another important aspect is the establishment of atight interdisciplinary integration of knowledge in coding and signal processing, and nano-scale devices andsubsystems into programs benefiting undergraduate and graduate students at the University of Arizona and theindustrial technical research community.

在拟议的研究中，将开发由不可靠组件制成的高度可靠的存储器，并根据其复杂性和保留存储信息的能力来表征。主要挑战是在纳米级系统中，存储元件和逻辑门都会出现故障。它与最先进的系统形成鲜明对比，在最先进的系统中，只有存储元件被认为是不可靠的，而纠错编码器和解码器被认为是由可靠的逻辑门组成的。本研究将解决的一系列问题可以浓缩为以下问题：给定 n 个存储单元和 m 个通用逻辑门，它们按照已知的随机机制发生故障，在最长的时间内存储最大数量的信息位的最佳存储架构是什么？ 任意低概率的错误？这个复杂的问题可以通过多种方式进行划分和重新表述，但有趣的是，甚至与这个问题相关的一些最基本的问题仍然没有答案。最重要的问题与容错存储器中的以下两种根本不同的方法有关：（i）为了提高可靠性，可以将逻辑门资源投入冯诺依曼复用方案。通过这种方式，我们可以构建高度冗余的可靠网络来模拟通用逻辑门的功能，然后使用这种更好的门来构建纠错编码器和解码器。 (ii)或者，可以将逻辑门资源投入到构建能够处理存储器元件以及逻辑门错误的更强大的纠错码（即，解码器）。对于给定的故障机制，这两种方法中哪一种是最佳的？从更广泛的层面来看，是在设备层面还是在系统层面处理可靠性问题更好？ 智力优点：纳米系统独特的存储元件和逻辑门都不可靠的特性使得理论上确保容错的问题变得非常重要，因为纠错过程并不是经典信息论中假设的无差错。使纠错码变得更强以及使发射机和接收机更加复杂并不一定会提高系统的性能。对于给定的故障机制，接收器复杂性与其性能之间可能存在权衡。我们开发容错存储器架构的方法基于泰勒开发并由库兹涅佐夫改进的方法。 Taylor 和 Kuznetsov (TK) 表明，内存系统具有非零计算（存储）容量，即确保可靠性所需的冗余随着内存大小渐近线性增长。本研究将解决的两个基本开放问题是确定纳米级存储器的存储容量和开发接近容错架构的容量。 TK 方法中的恢复阶段和有缺陷的 Gallager-B 算法（如项目描述中所述）的等效性将使我们能够利用过去十年中获得的图代码和迭代解码方面的大量知识来解决不可靠介质上可靠存储的这些问题和其他重要问题。 更广泛的影响：该计划将为美国数据存储技术和信息基础设施的发展做出重大贡献 美国和国外。另一个重要方面是将编码和信号处理以及纳米级设备和子系统方面的知识建立紧密的跨学科整合，使亚利桑那大学和工业技术研究界的本科生和研究生受益。