Paul Siegel - US grants

The 1998 IEEE Information Theory Workshop is sponsored by the Information Theory Society of the IEEE will be held in San Diego, CA on February 8-11, 1998. The primary objective of the Workshop is to present new perspectives and results in a broad range of research areas in information and its applications. There will be six technical sessions, held serially covering the following topics: 1) Information Theory: 50 Years and Beyond, 2) Universal and Lossless Source Coding, 3) Channel Coding Applications, 4) CDMA, 5) Channel Coding Theory, and 6) Lossy Source Coding. Each session will include six invited speakers, each internationally recognized for contributions in the respective research areas. In addition, there will be a plenary lecture each morning, as well as a special evening lecture. There is also a session for contributed recent research results. The purpose of the award is to provide financial support from NSF for travel grants to U.S> scientists and engineers who could not otherwise attend the Workshop for lack of funding.

CCF-0829865
Code Representation and Performance of Graph-Based Decoding
PI: Paul H. Siegel, UC San Diego

Abstract: The discovery of channel codes that approach information-theoretic performance limits when paired with iterative graph-based decoding algorithms represents a major advance in coding theory and practice. Prime examples include turbo codes, low-density parity-check (LDPC) codes, and repeat-accumulate (RA) codes. These coding techniques and their variants have had a profound impact on data transmission applications, including deep space communications, digital video broadcasting, and mobile wireless telephony. They are also poised for use in other settings, such as high density digital data storage. What is common to these coding and decoding schemes is that their performance and implementation complexity depend not only on the code itself, but also on the choice of graphical representation of the code. This research studies the characteristics of code representations that influence the performance of iterative decoding algorithms, as well as methods for constructing the best representations.

The research has two major thrusts. The first is the examination of combinatorial and graphical properties of linear code representations that serve as figures of merit for iterative decoder performance on several types of channels having theoretical and practical significance. The understanding of these properties guides improved code design as well as the development of new graph-based decoding strategies. The second thrust is the analysis and enhancement of decoders based upon linear programming. The research studies the adaptive introduction of constraints to reduce decoder complexity and to improve performance. It also considers new linear programming algorithms that exploit sparse code representations. A dynamic interplay between these two research thrusts is achieved by studying the relationship between iterative and linear programming decoders, as well as their application to equalization and detection for channels with memory.

Non-volatile data storage devices, particularly those based upon NAND flash memory and emerging phase-change memory (PCM) technologies, are revolutionizing the way we access and manipulate information. They have many attractive features compared to magnetic hard disk drives, including their compactness, shock resistance, and faster data access. Flash memory is now preferred in portable consumer electronics, and high performance solid-state drives (SSDs) are being introduced in mobile computing, enterprise storage, data warehousing, and data-intensive computing applications. Accordingly, there is a surge in interest in the refinement, development, and expanded commercial use of these non-volatile memory technologies. On the other hand, these technologies present major challenges in the areas of device reliability, endurance, and energy efficiency. These challenges can be overcome, in part, through innovative coding and data handling techniques, which is the subject of this research project. Specifically, the problems addressed include: (1) the design of efficient, error-resilient rewriting codes for single-level cell (SLC) flash memories using write-once memory (WOM) coding techniques; (2) the design of non-binary rewriting codes for multi-level cell (MLC) flash memories, as well as codes that tolerate asymmetric cell-level transitions and writing errors; (3) the development of coding techniques that mitigate the effects of heat accumulation in PCMs; and (4) the design of error-correcting codes for PCMs with stuck cells.

The research involves the information-theoretic analysis of flash memory and PCM channel models, the development of novel coding schemes, and system performance evaluation. A unique aspect of the project is the use of the facilities of the Non-Volatile Systems Laboratory at UC San Diego, providing an experimental platform for device characterization and empirical performance comparisons of new coding techniques and architectures.

The primary objective is to further the development of a vertical vision for research on the role of non-volatile memory technologies in data-intensive computing systems. It is essential that researchers at each level of the system stack be aware of the needs, challenges, and opportunities associated with the other levels. The workshop will give researchers in relevant fields the opportunity to gain a broader understanding of what is needed to move NVM-based storage technology forward, to learn from each other, and to establish relationships and collaborations that will provide the basis for further scientific and engineering advances.

Intellectual Merit: This workshop will address fundamental problems in the science, engineering, and application of high-performance data storage systems based upon non-volatile memories.

Broader Impact: The exchange of knowledge and the generation of novel ideas that result from the workshop will have significant impact on the computing and data storage industries, both vitally important to the national economy. The educational component of the workshop will benefit student researchers, as well as more senior participants.

Advances in data storage technology have been crucial to the evolution of the modern information age, enabling and accelerating the invention of new information-related applications in consumer entertainment, personal and business computing, enterprise data management, and scientific research. Recently, high capacity solid-state drives (SSDs) based upon NAND flash memory technology have begun attracting significant attention and finding broader use in many of these applications. SSDs have a number of advantages compared to conventional disk and tape drives, including better shock resistance, reduced power consumption, no moving parts, and faster data access. Although they remain less competitive in some storage applications with respect to cost per bit, overwrite constraints, and product lifetime limitations, it is becoming increasingly clear that continuing advances in the technology of SSDs and other non-volatile memories (NVMs) are setting the stage for a revolution in how computer systems and applications access and manipulate persistent data. Improved flash memories ? along with emerging technologies such as phase-change memories (PCM), spin-torque transfer memories (STTM), and the memristor ? are driving designers to rethink how they integrate these and other storage devices into future computing systems, how operating systems manage data, and how applications create and process information electronically. Realizing the full potential of these technologies is an exciting and important challenge with enormous societal consequences.

The proposed workshop is a sequel to the Non-volatile Memories Workshops that were held on the campus of the University of California, San Diego in April 2010 and March 2011, respectively. Archival websites from these workshops may be found at http://nvmw.ucsd.edu/. The primary objective has been to further the development of a ?vertical? vision for research on the role of NVM technologies in data intensive computing systems. It is essential that researchers at each level of the system ?stack? be aware of the needs, challenges, and opportunities associated with the other levels. The workshop will give researchers in relevant fields the opportunity to gain a broader understanding of what is needed to move NVM-based storage technology forward, to learn from each other, and to establish relationships and collaborations that will provide the basis for further scientific and engineering advances. This will be accomplished through a wide-ranging program containing a half-day tutorial sesssion, two keynote addresses, and contributed technical presentations covering important topics related to: NVM device technologies, data recording and recovery techniques, system architectures and software design, and future NVM applications in personalized health, green computing, and enterprise-scale information management. Open registration for the entire workshop is intended to encourage broader participation by interested individuals from academia, industry, and government. The technical program is structured to provide a unique educational opportunity, particularly for students and researchers who are new to the area.

Intellectual Merit: This workshop will address fundamental problems in the science, engineering, and application of high-performance data storage systems based upon non-volatile memories. This includes the study of nano-scale physical phenomena that permit storage of information; the development of coding algorithms for reliable, persistent, and secure data storage; the analysis of system architectures for data intensive computing; and the conception of new paradigms for non-volatile storage of data in a variety of applications.

Broader Impact: The exchange of knowledge and the generation of novel ideas that result from the workshop will have significant impact on the computing and data storage industries, both vitally important to the national economy. The educational component of the workshop will benefit students and postdoctoral researchers, as well as more senior participants. An archival website will provide a lasting record of the workshop proceedings and a resource for the scientific community and general public.

Advances in data storage technology have been crucial to the evolution of the modern information age, enabling and accelerating the invention of new information-related applications in consumer entertainment, personal and business computing, enterprise data management, and scientific research. High-capacity, non-volatile, solid-state drives (SSDs) are in the process of revolutionizing this world of data storage. SSDs have a number of advantages compared to conventional disk and tape drives, notably in shock resistance, reduced power consumption, and faster data access. Although currently less competitive in some storage applications with respect to cost per bit, write latency, and product lifetime, continuing advances in SSDs based upon several non-volatile memory (NVM) technologies are setting the stage for a revolution in how computer systems and applications access and manipulate persistent data. Improved flash memories - along with emerging technologies such as magnetic RAM (MRAM), phase-change memories (PCM), spin-torque transfer memories (STTM), resistive RAM (RRAM), and the memristor - are driving designers to rethink how they integrate storage devices into computing systems, how operating systems manage data, and how applications create and process information. Realizing the full potential of NVM technologies is an exciting and important challenge with enormous societal consequences. The proposed workshop is the fifth in the annual series of Non-volatile Memories Workshops (NVMWs) that have been held on the campus of the University of California, San Diego. The primary objective continues to be the development of a "vertical" vision for research on the role of NVM technologies in an ever-increasing number of application scenarios, ranging from data-intensive computing systems to super high-resolution video games. As the capabilities of NVM-based storage rapidly evolve, it is more critical than ever that researchers at each level of the system "stack" be aware of the needs, challenges, and opportunities associated with the other levels. The workshop provides researchers and practitioners the opportunity to gain a broader understanding of what is needed to accelerate the development and adoption of NVM-based storage technologies, and to establish relationships that will provide the basis for further advances. The workshop program includes a half-day tutorial session, two keynote addresses, approximately 32 technical presentations selected by an expert Program Committee, and a poster session. Topics addressed range from new NVM device technologies, data handling techniques, system architectures, and future NVM applications in areas such as distributed storage networks, neuromorphic computing, high-speed data caching, and speech recognition. Open registration for the entire workshop is intended to encourage broad participation from academia, industry, and government. The technical program is structured to provide a unique educational opportunity, particularly for students and researchers who are new to the area.

Intellectual Merit:
This workshop will address fundamental problems in the science, engineering, and application of high-performance data storage systems based upon non-volatile memories. This includes the study of nanoscale physical phenomena that permit storage of information; the development of coding algorithms for reliable, persistent, and secure data storage; the analysis of system architectures for data-intensive computing; and the conception of new paradigms for non-volatile storage of data in a variety of applications.

Broader Impacts:
The exchange of knowledge and the generation of novel ideas that result from the workshop will have significant impact on the computing and data storage industries, both vitally important to the national economy. The educational component of the workshop will benefit students and postdoctoral researchers, as well as more senior participants. An archival website will provide a lasting record of the workshop proceedings and a resource for the scientific community and general public.

During the information age, in which we now live, the need for reliable transmission and storage of digital data is of paramount importance.
What makes such reliable transmission and storage possible are error- correcting codes, first conceived by Claude Shannon over 50 years ago.
The discovery of the channel polarization phenomenon and the associated invention of polar coding is, without doubt, one of the most original and profound developments in the theory of error-correcting codes in the past decade. Polar codes provably achieve the capacity of any memoryless symmetric channel, with low encoding and decoding complexity, thereby providing the first constructive solution to the problem posed by Claude Shannon in 1948. This remarkable result has engendered enormous interest in harnessing the potential of polar coding in practice. The objective of this project is to advance the theory of polar codes and to bring these codes much closer to the practice of data storage. Thus the investigators study not only certain theoretical aspects of polar codes, but also their implementation in VLSI circuits and their incorporation in data-storage technologies. In view of the increasing demand for reliable, high-capacity data storage, driven by applications ranging from consumer electronics to massive data warehouses, this research has significant potential for economic and societal impact.


The present project addresses a number of fundamental problems related to channel polarization, polar code design methods, and performance of polar decoding algorithms. Specifically, the problems considered include the following:
(1) Polarization speed and polarization kernels for a variety of channels;
(2) Performance analysis of list-decoding algorithms for polar codes;
(3) Integration of polar codes into joint detection and decoding
architectures for magnetic recording channels;
(4) Design of non-binary polar codes for solid-state memories with
asymmetric errors and rewriting constraints;
(5) Realization of polar coding technology in high-speed,
low-power VLSI circuit implementations.
The resolution of these challenging problems requires new methods and ideas on the interface between information theory and coding. Understanding polar coding architectures for data-storage systems has implications for a broad range of communication channels. The results of this research are also relevant to other scientific disciplines and engineering technologies that are being revolutionized by the polarization phenomenon, including source coding, secure communications, network information theory, randomness extraction, and compressive sensing. On the other hand, hardware implementation fosters an interplay between algorithmic invention and VLSI design, pushing the frontiers of circuit technology. The project furthermore provides an excellent opportunity for graduate students to engage in multi-disciplinary research and to interact with partners in the data-storage industry.

Advances in data storage technology have been crucial to the evolution of the modern information age, enabling and accelerating the invention of new information-related applications in consumer entertainment, personal and business computing, enterprise data management, and scientific research. High-capacity, non-volatile, solid-state drives (SSDs) are in the process of revolutionizing this world of data storage. SSDs have a number of advantages compared to conventional disk and tape drives, notably in shock resistance, reduced power consumption, and faster data access. Although currently less competitive in some storage applications with respect to cost per bit, write latency, and product lifetime, continuing advances in SSDs based upon several non-volatile memory (NVM) technologies are setting the stage for a revolution in how computer systems and applications access and manipulate persistent data. Improved flash memories - along with emerging technologies such as magnetic RAM (MRAM), phase-change memories (PCM), spin-torque transfer memories (STTM), resistive RAM (RRAM), and the memristor - are driving designers to rethink how they integrate storage devices into computing systems, how operating systems manage data, and how applications create and process information. Realizing the full potential of NVM technologies is an exciting and important challenge with enormous societal consequences. The proposed workshop is the sixth in the annual series of Non-volatile Memories Workshops (NVMWs) that have been held on the campus of the University of California, San Diego. The primary objective continues to be the development of a "vertical" vision for research on the role of NVM technologies in an ever-increasing number of application scenarios, ranging from data-intensive computing systems to super high-resolution video games. As the capabilities of NVM-based storage rapidly evolve, it is more critical than ever that researchers at each level of the system "stack" be aware of the needs, challenges, and opportunities associated with the other levels. The workshop provides researchers and practitioners the opportunity to gain a broader understanding of what is needed to accelerate the development and adoption of NVM-based storage technologies, and to establish relationships that will provide the basis for further advances. The workshop program includes a half-day tutorial session, two keynote addresses, approximately 45 technical presentations selected by an expert Program Committee, and a poster session. Open registration for the entire workshop is intended to encourage broad participation from academia, industry, and government. The technical program is structured to provide a unique educational opportunity, particularly for students and researchers who are new to the area. The exchange of knowledge and the generation of novel ideas that result from the workshop will have significant impact on the computing and data storage industries, both vitally important to the national economy. The educational component of the workshop will benefit students and postdoctoral researchers, as well as more senior participants. An archival website will provide a lasting record of the workshop proceedings and a resource for the scientific community and general public

This workshop will address fundamental problems in the science, engineering, and application of high-performance data storage systems based upon non-volatile memories. This includes the study of nanoscale physical phenomena that permit storage of information; the development of coding algorithms for reliable, persistent, and secure data storage; the analysis of system architectures for data-intensive computing; and the conception of new paradigms for non-volatile storage of data in a variety of applications. The program will reflect the latest advances in device technology, data encoding, system architecture, and storage applications. The Workshop will provide a unique forum for the exchange of recent results and novel ideas relating to research, development, and application of non-volatile memory systems.
.

Magnetic media and flash memories are currently the main platforms used for mass data storage. As the need for storage capacity grows, new methods are being explored to increase the density in such media, and new nano-scale technologies, such as memristor-based memories, are being developed. This project concerns the analysis of fundamental limits on the information storage capability of these emerging storage technologies, as well as the design of coding schemes to approach those limits. The theoretical component of the project requires new approaches in information theory and discrete mathematics, while the development of new coding techniques extends the reach of the theory into practice, hastening the evolution of new commercial technologies. The project provides a stimulating research environment for graduate students, and contributes to curriculum development in electrical engineering and computer science.

In the domain of magnetic storage, the research addresses lower and upper bounds on the capacity of grain and Ising channels; the construction of codes that correct errors in these channels; and the extension of these results to non-binary channel models. The research on multilevel flash memories involves computing bounds on the capacity of the one-dimensional inter-cell interference channel; constructing codes that combat inter-cell interference in one, two, and three dimensions; and designing codes that mitigate the wear of cells and the erase-program asymmetry in flash memories. For memristor-based memories, research topics include the design of two-dimensional codes with weight constraints on the rows and columns; the design of fast methods for overwriting a two-dimensional weight-constrained array onto another constrained array; and the study of the notion of Hamming connectedness of constraints.