Alexander Vardy - US grants

University of Illinois, Champaign-Urbana Alexander Vardy RIA: Channel Codes for Digital Communications and Storage Systems Reliable transmission and storage of information requires the use of error correcting channel codes to protect the data against errors introduced by the channel noise or imperfections of the recording medium. Error correcting codes are implemented in most of the modern communications and storage systems ranging from household compact-disc players through telephone line modems, computer memories, and mobile radio networks to satellite and deep space communications. In this project we investigate two general types of error correcting codes, known as block and lattice codes, using a novel dynamical approach. Since a block code is essentially subset of finite field, while a lattice is a discrete collection of dimensional real points with certain prescribed distance properties, they have been conventionally treated as geometric or algebraic entities. However, as is just now being realized, block and lattice codes may as well be regarded as dynamical systems. The latter approach has several profound advantages over the conventional practice. One of the objectives is to exploit these advantages in an attempt to find new codes, better than presently known. Another objective is to provide bounds on the decoding complexity and develop more efficient maximum-likelihood decoders, which substantially advance the current performance achievable for a given decoder complexity. Furthermore, we study the precise trade-off between complexity and performance in block and lattice error correcting codes, from both theoretical and practical standpoints. Progress along these lines would enable the designer of a communication system to obtain larger coding gains for the same bandwidth, power, and complexity constraints. Also treated are modulation codes for input constrained channels used to encode information into a particular set of sequences admitted by the channel. These codes have widespread use in a variety of information storage applications, such as magnetic or magneto-optic recording systems. New multi-dimensional modulation codes are currently being developed for the emerging technology of holographic storage. Most of the modulation codes in use today are constructed using tools from symbolic dynamics. Taking the point of view of block codes as dynamical systems makes it natural to consider applying results from algebraic coding theory for the design of modulation codes. We will use this approach to develop more efficient encoders for high order spectral null codes and multidimensional modulation codes for holographic recording. The possibility of integrating a prescribed error correcting capability within such modulation encoders will also be studied.

NCR-9501345 Alexander Vardy The first focus of this research is on decoding of trellis codes. The work will attempt to establish new lower bounds on the trellis complexity of linear codes, to investigate the asymptotic trellis complexity of linear codes, to find the optimal sectionalization of a given trellis, to tabulate bounds on the trellis complexity for all of the best-known linear codes, and to extrapolate the results to lattices and sphere packings. The second activity is the development of novel data transmission techniques suited to specific channels of practical importance and extending beyond the classical error control approach. Guided by the general principle that the channel structure should be taken into account in a well-designed communication system, the following channels will be considered: bursty intersymbol interference channels, such as present day digital voice transmission, both twisted pair and wireless, and emerging digital subscriber loops; maximum a posteriori likelihood channels characterized by a nonuniform a priori distribution on the set of possible messages, arising in fixed rate quantization without entropy coding; channels characterized by an arbitrary specified set of most likely error patterns, such as those arising in concatenated coding, logic networks, and man-made noise environments; and channels characterized by subjective distortion criteria, rather than the overall system BER, such as those arising in speech and image coding. NCR-9502582 Konstantopoulos, Takis This is a proposal about the development of a rigorous approach toward network management and performance analysis for high-speed networks considering local and global aspects of a network management system. Local aspects include the design of flow controllers at the edges of the network that take into account the provision of quality of service and the interaction between users in a network switch. The investigator will extend recently develop ed techniques that are based on the so-called reflection mapping, develop testing techniques and simulations, and compare these to existing schemes. The investigator will also study traffic modeling. He will develop rigorous methods for validating self-similar traffic processes arising from the operation of an integrated services high-speed networks and use such models in establishing performance analysis methods. Studying the global aspects of a management system involves using a macroscopic picture of the network currently being developed by the investigator. The picture strips out the minutiae of the operation of the network, while retaining its dynamic character (it is not static). The investigator proposes the use of such a picture by a network management system in order to predict, prevent, and correct undesirable behavior that might lead to degradation of services across the network.

9415860 Zeger The goal of the project is to develop effective joint source-channel coding techniques. The main objectives are to achieve a deep theoretical understanding of combined source-channel codes and to develop practical algorithms that can effectively be used in real applications such as low-bandwidth video compression and low-delay speech coding. Very narrow bandwidth transmission channels, such as mobile cellular telephony, require efficient coding schemes to protect the transmitted source information from the corruptive effects of channel errors. Some previous work on joint source-channel coding has yielded limited success at protecting source coded information. In particular, low complexity techniques are needed for low delay real time implementations. This project will investigate channel coding techniques for source coding applications with an emphasis on image, video, and speech coding applications. A summary of the topics to be investigated is: Classes of low-complexity redundancy free codes for discrete memoryless channels; error control coding will be incorporated into the source code design and the index assignment problem will be addressed for codes with redundancy. High resolution quantizer theory will be studied for sources transmitting across noisy channels. Some preliminary results give useful formulas for randomized index assignments, but a much stronger theory is needed for optimal index assignment. Lattice codes will be studied both for quantization and channel coding. A goal will be to develop efficient encoding algorithms for lattice source codes (respectively, decoding algorithms for channel codes). Preliminary results so far have yielded very fast algorithms for the Leech lattice, as well as some of the best-known low dimensional lattices. Efficient decoding techniques will be developed for channel codes in Euclidean space using specific source coding information. In particular, trellis decoding algorithms and theory will be studied for unequal input probabilities and unequal error protection. This is currently an unsolved problem though extensions of techniques from traditional decoding algorithms have yielded some limited preliminary success. ***

This project studies the theory of multidimensional channels and investigates effective coding techniques for such channels. The coding techniques are of three types: error-correction channel coding, constrained coding, and joint source-channel coding. Emphasis is placed on applications to two-dimensional magnetic and optical recording as well as three-dimensional holographic storage. These are the storage devices of the future. An important application of this research within the next few years is the storage of massive amounts of
still imagery and video on two-dimensional media. This will likely extend to three-dimensional and four-dimensional (the fourth dimension is wavelength) devices over the next 5 to 10 years. Such multidimensional devices will require a shift in paradigm, since most of the existing theory for
error-correcting codes, constrained codes, and source-channel codes was developed in the context of one-dimensional applications. There is much to be gained by coding for multidimensional channels, but the problems associated with such channels are considerably more challenging than their one-dimensional
counterparts.

Interesting technical problems arise due to the spatially dependent nature of errors in multidimensional storage media. New error-correcting codes and interleaving techniques are needed to effectively protect data stored on such media. The physical properties of optical and holographic recording channels call for a new theory of constrained coding in multiple dimensions. New joint source-channel coding techniques and theory are needed to maximize the recovered source fidelity for images and video stored on multidimensional
devices while keeping the storage density as high as possible. Inparticular, the storage capacity of multidimensional devices can be greatly increased at the expense of a less reliable recovery of the stored imagery/video than is current practice for the storage of data. This project studies the tradeoff
between increased storage capacity and quantitative loss in fidelity of the reproduced source signal. The main topics being investigated for multidimensional channels are: (1) Error-correcting codes, (2)
Interleaving techniques, (3) Soft-decision decoding, (4) Capacity computation for constrained channels, (5)~Encoders and decoders for specific constraints, (6) Joint source-channel coder design.

This project studies the theory of multidimensional
channels and develop effective coding techniques for such
channels. The coding techniques investigated are of three
types: error-correction channel coding, constrained coding,
and joint source-channel coding. Emphasis is placed on
applications to two-dimensional magnetic and optical
recording as well as three-dimensional holographic
recording. These are the storage devices of the future.

The investigation involves code design, theoretical analysis,
and computer simulation.

The main topic areas investigated for multidimensional
channels are:

Interleaving techniques in two and three dimensions
Multidimensional codes correcting cluster errors
Constrained coding and defect avoidance for
multidimensional media - Progressive source coding for
multidimensional channels - Index assignment for
multidimensional channels

Multidimensional storage devices require a completely new
theory and new technical breakthroughs, since most of the
existing theory for error-correcting codes, constrained
codes, and source-channel codes was developed in the context
of one-dimensional applications. The problems associated
with multidimensional channels are usually much more
challenging than their one-dimensional counterparts.

In particular, interesting technical problems arise due to
the spatially dependent nature of errors and constraints in
multidimensional recording media. New error-correcting codes
and interleaving techniques are needed to effectively
protect data stored on such media. The study of constrained
coding for multidimensional channels is still in its infancy
, and needs substantial further research to blossom into a
theory. Joint source-channel coding techniques are needed
to maximize the recovered source fidelity for images and
video stored on multidimensional devices.

Abstract
--------

Digital communication, embodied in such applications as cell phones and wireless Internet, by now pervades our daily lives, while digital storage devices, such as CDs, DVDs, and computer disk drives, have become the principal means of preserving our information. In the "information age" in which we all now live, the need for reliable transmission and storage of digital data is of paramount importance. What makes such reliable transmission and storage possibles are error-correcting codes, first conceived by Claude Shannon over 50 years ago. Indeed, as you are reading these lines, millions of error-correcting codes are decoded every minute, using efficient algorithms implemented in custom VLSI circuits. At least 75% of these circuits decode Reed-Solomon codes, invented by Irving Reed and Gustave Solomon in the 1960s. In the four decades since their invention, Reed-Solomon codes have been extensively studied and ingenious decoding algorithms for these codes have been developed. What has been realized only recently, however, is that Reed-Solomon codes can correct many more errors than previously thought possible! In a series of theoretical breakthroughs, Sudan, Guruswami-Sudan, and Koetter-Vardy have made state-of-the-art Reed-Solomon decoders out of date. At least in principle, we can now achieve much better performance with the same codes. The goal of this project is to follow-up on this exciting recent work and to follow this line of research through to its ultimate potential, in theory as well as in practice.

In order to attain this goal, we plan a broad line of attack. On one hand, the proposed investigation will address deep theoretical questions. Can one exceed the Guruswami-Sudan decoding radius? What is the optimal multiplicity assignment for algebraic soft-decision decoding? How can iterative decoding methods be applied to Reed-Solomon codes? On the other hand, we intend to go all the way to the first-ever VLSI implementation of a soft-decision Reed-Solomon decoder. The proposed VLSI architecture aims for high speed and low power dissipation. Thus complexity considerations, inherently motivated by the practice of VLSI design, will be paramount throughout our investigation. Specifically, The main topics to be investigated are: (1) Multivariate interpolation decoding beyond the Guruswami-Sudan radius; (2) Probabilistic model and multiplicity assignment schemes for algebraic soft-decision decoding; (3) Iterative methods for soft decision decoding of Reed-Solomon codes; (4) Analytic bounds on the performance of maximum-likelihood and suboptimal decoders; and (5) Complete VLSI implementation of a state-of-the-art soft-decision Reed-Solomon decoder in an FPGA and/or ASIC.

This project studies the emerging field of network coding in several new directions. Network coding offers the promise of improved performance over conventional network routing techniques, by allowing network nodes to mathematically combine information prior to retransmission. Over the next decade, it has the potential to become a pervasive technology that could radically change the way information is communicated. In particular, network coding principles can significantly impact the next-generation wireless, ad hoc, and sensor networks, in terms of both energy efficiency and throughput.

While most of the existing network coding theory assumes error-free links, in practice these links are usually noisy. In fact, error-correction coding for such noisy links is sub-optimal when it is separated from network coding --- to maximize the throughput of a network, channel and network coding must be
combined. Thus, one of the main research topics studied in this project is joint network and channel coding. The project focuses on the following subtopics: (i) Reverse concatenation of network and channel coders (ii) Joint network/channel coding at the node level (ii) Global network/channel coding at the network level The second main research topic is broadcast-mode network coding. This concerns applications in ad hoc wireless networks. Subtopics include: (i) Linear network coding (ii) Network capacity (iii) Iterative design
of broadcast-mode network codes.

Abstract
--------

Digital communication, embodied in such applications as cell phones and wireless Internet, by now pervades our daily lives, while digital storage devices, such as CDs, DVDs, and computer disk drives, have become the principal means of preserving our information. In the "information age" in which we all now live, the need for reliable transmission and storage of digital data is of paramount importance. What makes such reliable transmission and storage possibles are error-correcting codes, first conceived by Claude Shannon over 50 years ago. Indeed, as you are reading these lines, millions of error-correcting codes are decoded every minute, using efficient algorithms implemented in custom VLSI circuits. At least 75% of these circuits decode Reed-Solomon codes, invented by Irving Reed and Gustave Solomon in the 1960s. In the four decades since their invention, Reed-Solomon codes have been extensively studied and ingenious decoding algorithms for these codes have been developed. What has been realized only recently, however, is that Reed-Solomon codes can correct many more errors than previously thought possible! In a series of theoretical breakthroughs, Sudan, Guruswami-Sudan, and Koetter-Vardy have made state-of-the-art Reed-Solomon decoders out of date. At least in principle, we can now achieve much better performance with the same codes. The goal of this project is to follow-up on this exciting recent work and to follow this line of research through to its ultimate potential, in theory as well as in practice.

In order to attain this goal, we plan a broad line of attack. On one hand, the proposed investigation will address deep theoretical questions. Can one exceed the Guruswami-Sudan decoding radius? What is the optimal multiplicity assignment for algebraic soft-decision decoding? How can iterative decoding methods be applied to Reed-Solomon codes? On the other hand, we intend to go all the way to the first-ever VLSI implementation of a soft-decision Reed-Solomon decoder. The proposed VLSI architecture aims for high speed and low power dissipation. Thus complexity considerations, inherently motivated by the practice of VLSI design, will be paramount throughout our investigation. Specifically, The main topics to be investigated are: (1) Multivariate interpolation decoding beyond the Guruswami-Sudan radius; (2) Probabilistic model and multiplicity assignment schemes for algebraic soft-decision decoding; (3) Iterative methods for soft decision decoding of Reed-Solomon codes; (4) Analytic bounds on the performance of maximum-likelihood and suboptimal decoders; and (5) Complete VLSI implementation of a state-of-the-art soft-decision Reed-Solomon decoder in an FPGA and/or ASIC.

Error-correcting codes, studied in a branch of science and engineering known as coding theory, safeguard data against the adverse effects of noise and enable reliable storage and communication of information. Such codes pervade our daily lives, with applications ranging from computer hard-disks and UPS bar-codes to cell phones and the Internet to deep space communication. One of the most fundamental questions in coding theory is the following: What is the largest possible fraction of errors that a code of information rate R can correct? Recent theoretical breakthroughs provide a complete answer to this question, namely that the ultimate error-correction radius of 1-R can be reached (by codes over sufficiently large alphabets). Moreover, it can be reached constructively with polynomial-time list decoding, via codes closely related to Reed-Solomon codes, which are ubiquitous in practice.

From a practical standpoint, this promises a factor of two improvement over classical error-correction algorithms that are in widespread use today. While this is extremely encouraging, numerous challenges must be overcome in order to bring the theoretical promise of the recent results to practice. This project, led by a multi-disciplinary team, involves an integrated collection of research activities targeted at progress towards the long term goal of attaining the fundamental limit of error-correction. At the theoretical end, the goals include improving the complexity of the decoding algorithms as one approaches the optimal error-correction radius of 1-R, and devising faster algorithms and heuristics for the key steps involved in algebraic list decoding. The project also studies methods to reap the practical benefits of combining the new codes with soft-decision decoding, putting to use the ample amount of probabilistic symbol reliability estimates often available to decoders. Furthermore, the research lays the groundwork for eventual implementation of such algorithms in high-speed/low-power VLSI, thereby enabling the potential deployment of the new codes in a broad range of communication and storage systems. On the education front, the project provides a stimulating research environment for graduate students, encouraging team-work across university boundaries and collaboration across disciplines (computer science, communication theory, and VLSI design).

Over the past 50 years, error-control coding has been employed with spectacular success by the communications and data storage industries to achieve performance trade-offs that would have been otherwise impossible. What has been recognized only recently, however, is that coding theory could be just as useful in applications other than communications and storage. In particular, this project is concerned with numerous problems that arise in the area of digital circuit design. The problems studied come from a wide spectrum of technologies, ranging from nanoscale circuits and memory chips to more conventional VLSI architectures. In each case, these problems are inherent to the physics of the underlying medium or system. In each case, the project aims to show that sophisticated coding --- based upon methods and ideas deeply rooted in algebraic and combinatorial coding theory --- offers a significant advantage, thereby enabling circuit designers to achieve system trade-offs that would have been otherwise impossible.

Specifically, the research carried out in this project can be roughly subdivided into the following four focus areas:

Development of new coding schemes for efficient addressing and
correction of manufacturing defects in next-generation memory
nano-devices, in particular the nano-wire crossbar;

Advanced coding techniques for high-density flash memories, based
upon ground-breaking recent ideas of floating codes and rank-modulation
coding;

Development of coding schemes to reduce power dissipation and to avoid
cross-talk in VLSI circiuts, with particular emphasis on both on-chip
and off-chip buses;

Applications to circuit design of the techniques developed in a range
of well-known combinatorial problems in coding theory, including
covering arrays, separating codes, intersecting codes, and qualitatively
independent set families.

Digital communication pervades our daily lives while digital storage devices have become the principal means of preserving our information. 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 recent invention of polar codes is, without doubt, the most original and profound development 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 deterministic and constructive solution to the problem posed by Shannon in 1948. Nevertheless, the impact of polar codes in practice has been, so far, negligible. The objective of this project is to advance the theory of polar codes on one hand, and to bring polar codes much closer to practice on the other hand. If successful, the outcome of this research is likely to become an enabling technology for numerous communications applications, both commercial and for national security.

In order to make polar codes practical, major obstacles must be resolved. The first key problem in the field is how to efficiently construct polar codes. This project aims to develop a linear-time construction algorithm, with explicit guarantees on the quality of its output. The investigators also study algebraic and combinatorial structure of polar codes, with the goal of developing a good analytical handle on the rate of channel polarization. Currently available empirical results indicate that the rate of channel polarization is too slow for many applications. Thus the investigators intend to drastically improve the performance of polar codes, at short to moderate code lengths, by introducing certain key modifications in the successive-cancellation decoding algorithm. One especially promising idea in this regard is list decoding. A concerted effort is devoted to the analysis of list decoding algorithms for polar codes. Furthermore, a full implementation of such decoding algorithms in high-speed and low-power VLSI is pursued. This part of the research involves algorithmic transformations for the key steps of the decoder, effective high-throughput design techniques, careful VLSI complexity/area analysis, and new computation scheduling ideas. Finally, applications of polar codes and channel polarization beyond point-to-point communications are considered. Such applications include multiple-access channels, relay channels, Slepian-Wolf coding, and information-theoretic security.

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.

The digital age is predicated on information being ubiquitous. The ability to access relevant data stored on remote servers "in the cloud" has become an indispensable resource in everyday lives. Numerous online services let users query public datasets for data items such as map directions, stock quotes, and flight prices, to name a few. Digital content providers also rely on user queries to identify the content desired by the user. Unfortunately, such queries have the potential to reveal highly-sensitive information *about the users*, thereby compromising their privacy. For example, institutional investors querying a stock-market database for the value of certain stocks may prefer not to reveal their interest in these stocks since it could influence their price. As another example, most people are deeply uncomfortable with exposing their media consumption diet to a centralized server that can be targeted by hacking or subpoena. It can be convincingly argued that access to such media consumption profiles can reveal the person's sexual orientation, political leanings, and cultural affiliations.

A great deal of research has been devoted to methods that guarantee the security and integrity of *the data*. Much less work, however, has been devoted to protecting the privacy of *the user*. Efficient and reliable retrieval of information from distributed databases, with information-theoretic guarantees of user privacy, is the focus of this project. The relevant area of research is known as private information retrieval. While most of the existing results in this area are theoretical, a major goal in this project is to bridge the gap between the theory of private information retrieval and the practice of distributed storage. As such, potential outcomes of this investigation may extend beyond the scope of academic research, contributing to new technologies and products.

Private information retrieval (PIR), conceived in the seminal papers of Chor, Goldreich, Kushilevitz, and Sudan over 20 years ago, has been traditionally studied in theoretical computer science and cryptography, with emphasis on the complexity of the communication between the user and the servers that store the database. While major breakthroughs have been achieved in this area over the years, the prevailing paradigm has always been that of replicating the database on several non-communicating servers. Such replication leads to a significant storage overhead, which is undesirable. Moreover, motivated by advances in coding for distributed storage, it was recently recognized that if database replication is replaced by *database coding*, the full power of coding-theoretic methods can be brought to bear on the problem. While extremely promising, this line of research is still in its infancy. The goal of this project is to follow-up on the database coding idea, and follow it through to its ultimate potential. In pursuit of this goal, the following questions are addressed:

(1) What is the information-theoretic capacity of PIR? That is, what is the maximum amount of information that can be privately retrieved per downloaded bit, under various scenarios?

(2) What is the optimal storage overhead of PIR? Can we achieve both privacy and efficient communication (on the download and upload) without replicating the stored data even once?

(3) How can both privacy and download efficiency be maintained in the presence of impediments such as malicious or colluding servers, unsynchronized data, and/or communication errors?

(4) Codes for distributed storage systems tolerate and repair node failures while making the data available to several users at once. How can we combine PIR protocols with such coding?

(5) What is the best possible tradeoff between the various desirable PIR features, such as download efficiency, storage overhead, and resilience to errors/collusions/node-failures?

This proposal is a natural outgrowth of the research recently carried out by the PIs and others in this area. Prior related work will provide a springboard for rapid progress toward the ambitious research objectives of this project. Knowledge, techniques, and qualitative insights gained through this investigation are expected to contribute to the foundations of the field, and to help bridge the gap between the theory of PIR and the practice of distributed storage.

New information-storage technologies are needed to accommodate the growing deluge of data being collected and generated by modern society. In the past decade, several experiments have demonstrated that deoxyribonucleic acid (abbreviated DNA) – the molecule that carries the genetic information of living organisms – is a potentially viable storage medium. DNA-based storage would have many attractive features: unprecedented data density, a recording format that will not become obsolete, archival durability over thousands of years, and easy data replication. On the other hand, DNA storage requires fundamentally new methods for encoding data into DNA sequences to make the storage process efficient and reliable. The aim of the project is two-fold: (1) to understand the mathematical limits on the efficiency, reliability, and information density of DNA-based storage, and (2) to develop novel data-encoding and decoding algorithms to help achieve those limits. The project will provide a stimulating research opportunity for undergraduate and graduate students, encouraging teamwork across university boundaries and collaboration across disciplines.<br/><br/>The project focuses on coding methods that address critical problems in the key stages of the DNA storage process: efficient synthesis of DNA sequences, stable retention of stored sequences, and reliable data retrieval and reconstruction. Specific objectives are: (1) establish fundamental information-theoretic limits on the storage capacity of DNA using mathematical abstractions of the DNA recording process, (2) develop source coding techniques to minimize the time needed to encode data into synthesized arrays of DNA sequences, (3) design coding algorithms to efficiently enforce constraints on the allowed nucleotide patterns in synthesized DNA sequences to ensure their long-term retention, and (4) develop reconstruction algorithms and error-correcting codes that can recover a set of DNA sequences from an unordered collection of copies that may be corrupted by insertions, deletions, and substitutions of nucleotides. The project develops tools to address classical problems in coding theory and information theory that underlie many aspects of the research. These include the construction of optimal codes for finite-state communication channels with symbol costs, the design of optimal short-length codes that correct multiple insertion and deletion errors, the development of efficient coding techniques that asymptotically approach the capacity of a communication channel with deletion errors, and the analysis of algorithms and codes that enable reconstruction of a sequence from multiple noisy observations, either exactly or within a small list of candidate sequences.<br/><br/>This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.