DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

TITLE: "Advances in Information Recording"
EDITORS: Paul H. Siegel, Emina Soljanin, Adriaan J. van Wijgngaarden, and Bane Vasic

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.


It is widely known that, over the past 40 years, the pace of progress in information storage technology has rivaled that seen in semiconductor-based computing technology. In commercially-available hard disk drives using magnetic recording, the highest areal density - the number of bits of information stored per unit of area - has sky-rocketed from 100 kilobits per square inch in 1965 to 180 gigabits per square inch in 2007. This represents a 1.8 million-fold increase. With the latest "perpendicular" magnetic recording technology, a single 3.5-inch drive can provide a terabyte of information storage for a desktop computer, with maximum data transfer rates that approach 900 megabits per second.

This impressive technological progress, coupled with an equally remarkable reduction in the cost of storage, has had a significant impact in consumer electronics, as well. Personal audio and video players the size of a deck of cards now boast 1.8-inch disk drives capable of storing up to 100 gigabytes of multimedia information. Similarly, in the realm of optical recording, removable storage devices such as Compact Disc (CD), Digital Versatile Disc (DVD), and Blue-ray Disc (BD) drives for audio and video applications reflect enormous technological strides. Today, a dual-layer BD disk can store 50 gigabytes of information and transfer data at 54 megabits per second. Recently, non-volatile solid-state memory technology has experienced significant improvements, as well. The latest 1.8-inch flash memory devices can store as much as 32 gigabytes of data, and these "flash drives" are finding widespread use in a number of portable storage applications. In an apparently endless synergistic cycle, remarkable multidisciplinary advances in data storage technology, such as those mentioned above, are enabling more complex and sophisticated information-based applications, while imaginative new developments in computing, business, entertainment, science, and transportation are continuing to demand practical storage devices with increased capacity, performance, and space efficiency.

The question is how future demands for information storage will be met. Nearterm improvements in recording media, read-write transducers, mechanical interfaces, and signal processing techniques are expected to double or triple areal densities. To reach higher densities, researchers are exploring more complex recording approaches, such as heat-assisted magnetic recording and magnetic bit-patterned media recording, which offer the prospect of an order of magnitude increase in areal density over conventional techniques. Beyond that, however, novel information recording methods that differ more radically from those of the present day will likely be required.

Therefore, researchers are investigating more exotic techniques, such as holographic optical recording, thermo-mechanical recording with arrays of nanoscale probes, and molecular-scale electronic memory cells built from layered nanowires. Efforts are even being made to devise storage devices that are inspired by biomolecular mechanisms observed in living cells. As noted by Matt Ridley in his book Genome, the principles underlying natural data storage are as old as the time "when life divided the labour between two separate activities: chemical work and information storage, metabolism and replication." Uncovering and exploiting these principles is another compelling research direction that is very relevant to the field of information recording.

With this as background, we come to the theme underlying this volume, namely, that information theory, including the related disciplines of communication theory and coding theory, has played an important role in the evolution of information storage technology, and it will continue to do so, independent of the physical recording mechanism. Information-theoretic considerations can guide the development of useful mathematical models for the underlying data storage and retrieval process. Analysis of these models can then provide insights into fundamental limits on achievable storage densities and data transfer rates. These insights, in turn, can serve as the impetus for the invention of new communication and coding techniques that make it possible for practical systems to approach or achieve the fundamental limits.

The collection of peer-reviewed articles in this volume evolved from the DIMACS Working Group and DIMACS Workshop on Theoretical Advances in Information Recording held at Rutgers University, Piscataway, NJ, on March 22-24, 2004 and March 25-26, 2004, respectively. These meetings were part of a series of workshops organized under the auspices of the "DIMACS 2001-2005 Special Focus on Computational Information Theory and Coding," a program funded by the National Science Foundation. The DIMACS working group and workshop successfully brought together experts in information storage from a range of different fields. The working group comprised 11 keynote presentations and was attended by 27 participants. The two-day DIMACS workshop consisted of 10 invited presentations with 24 participants. The lists of presentations given at these two events are included at the end of this volume.

The first three contributions in this collection explore extensions to presentday storage technologies. The paper by W.M. J. Coene and A.H. J. Immink describes modulation coding for a novel optical recording approach, known as "Two- Dimensional Optical Storage" or, simply, TwoDOS. In TwoDOS, bits are stored on a broad spiral consisting of multiple rows of bits arranged in a hexagonal lattice pattern. The bit rows in the spiral are recovered jointly using a multi-spot laser and a two-dimensional (2D) detection algorithm. The authors identify bit patterns which are most error-prone for this optical recording channel, and they then design modulation codes which avoid these bit patterns, so as to minimize the read-out errors.

The work by R. Radhakrishnan, B. Vasic, F. Erden and C. He introduces an enhanced magnetic recording technology called "Heat Assisted Magnetic Recording" or HAMR. The HAMR approach uses a laser to heat the recording medium during the write process, permitting the use of magnetic media that allow for significantly higher recording densities. The paper provides the concepts and mathematical model required for analysis of the HAMR system from a communication theory perspective.

The third contribution by A. Nayak, J.R. Barry, and S. W. McLaughlin explores bounds on the performance of timing recovery for channels with intersymbol interference (ISI). The authors derive the Cramer-Rao bound on timing estimation error variance for such channels in the presence of a frequency offset and a random walk timing component. The analysis also provides insight into new placement strategies for training symbols within a recorded sector of data. The next three articles explore the connections between data storage, information theory, and genetics. The work on macro-molecular data storage by M. Mansuripur and P. Khulbe presents preliminary results that demonstrate the potential for reliable, high-speed information recording and retrieval using macromolecular DNA sequences as the storage medium. G. Battail, in his contribution, draws on concepts from information theory to support the hypothesis that error correcting codes with "soft constraints" are used to encode genetic information, hence ensuring reliable transmission to next generation. The paper on data storage in cells, by O. Milenkovic, introduces a novel line of investigation for studying storage and processing of information in cells using a range of concepts and techniques drawn from information theory, coding theory, and computer science. The final contribution, by N. Kashyap and P. H. Siegel, describes a framework for using constrained coding techniques, whose development over the past few decades has been motivated largely by problems arising in information recording, to combat a certain nonlinear signal distortion that arises in high bit-rate, long haul optical fiber data transmission. The paper demonstrates the applicability of results and methods motivated by the study of information storage systems to other communication-theoretic settings.

The working group and workshop comprised several other presentations, some of which have been documented as papers elsewhere. Four presentations explored extensions to present-day storage technologies and achievable information rates for such systems. G. Cherubini of IBM Research, Zšurich, presented a nanotechnologybased approach for highly-parallel, ultra-dense data storage.1 E. Kurtas and R. Venkataramani of Seagate Research, Pittsburgh, Pennsylvania, reported on the capacity of magnetic recording channels, in particular, longitudinal and perpendicular systems. P. H. Siegel of the University of California, San Diego, California, presented information rates for two-dimensional recording technologies, such as holographic memories.2

Several presentations focused on coding for constrained systems, timing recovery and error control coding. B.H. Marcus of the University of British Columbia, Vancouver, gave an introductory presentation on optimal block-decodable encoders for constrained systems, and P. Chaichanavong of the University of California, San Diego, California, and T. L. Poo of Stanford University, Stanford, California, presented material on constrained systems with unconstrained positions.3 B. E. Moision of the Jet Propulsion Laboratory, Pasadena, California, presented material on coded modulation. K. R. Narayanan of Texas A&M University, College Station, Texas, presented a soft-input soft-output decoding algorithm for Reed-Solomon codes.4 N. Varnica of Harvard University, Cambridge, Massachusetts, presented an improved belief-propagation decoder for low-density parity-check codes based on channel information correction which can be utilized for any memoryless or intersymbol interference channel.5 W. Ryan of the University of Arizona, Tucson, Arizona presented an information-theoretic approach to obtaining optimal code rates for error control codes for a magnetic storage channel approximated by a Lorentzian model.6 J. R. Barry of Georgia Institute of Technology, Atlanta, Georgia, and A. Kavcic of Harvard University, Cambridge, Massachusetts, presented iterative methods that jointly perform the tasks of timing recovery and error control decoding.7

The working group also included a presentation by P. Winkler of Bell Laboratories and Institute for Advanced Study, Princeton, New Jersey on a combinatorial analysis of statistical facts about the human genome and a presentation by C. Rose of Rutgers University, Piscataway, New Jersey on the efficiency of communicating over interstellar distances using electromagnetic radiation versus transporting physical artifacts with inscribed information.

It is a great pleasure to acknowledge Fred Roberts, Director of DIMACS, and Mel Janowitz, Associate Director of DIMACS, for creating and maintaining the excellent infrastructure for the working group and workshop, and Robert Calderbank, Chris Rose, Amin Shokrollahi, Emina Soljanin and Sergio VerdŽu for organizing the Special Focus on Computational Information Theory and Coding. We are grateful to Linda Casals, Sarah Donnelly, Christine Houck, Jessica Herold and Maria Mercado of DIMACS for their assistance during the workshop organization, and to Sergei Gelfand and Christine Thivierge of the American Mathematical Society for their assistance in the preparation of this volume. We are indebted to the National Science Foundation for the financial support of the workshop and to the American Mathematical Society for publishing this volume. Finally, we wish to thank the authors for their outstanding contributions and their cooperation in the reviewing process.

Paul H. Siegel
Emina Soljanin
Adriaan J. van Wijngaarden
Bane Vasic

1 E. Eleftheriou, T. Antonakopoulos, G.K. Binnig, G. Cherubini et al., "Millipede - a MEMSbased scanning-probe data-storage system," IEEE Trans. Mag., vol. 39, no. 2, pp. 938-945, Mar. 2003.
2 J. Chen and P.H. Siegel, "On the symmetric information rate of two-dimensional finite-state ISI channels," IEEE Trans. Inf. Theory, vol. 52, no. 1, pp. 227-236, Jan. 2006.
3 T. L. Poo, P. Chaichanavong and B. H. Marcus, "Tradeoff functions for constrained systems with unconstrained positions," IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1425-1449, Apr. 2006.
4 J. Jiang and K. R. Narayanan, "Iterative soft-input soft-output decoding of Reed-Solomon codes by adapting the parity-check matrix," IEEE Trans. Inf. Theory, vol. 52, no. 8, pp. 3746-3756, Aug. 2006.
5 N. Varnica, M.P. Fossorier and A. Kavcic, "Augmented belief propagation decoding of low-density parity check codes," IEEE Trans. Commun., vol. 55, no. 7, pp. 1308-1317, July 2007.
6 S. Yang, A. Kavcic, and W. Ryan, "Optimizing the bit aspect ratio of a recording system using an information-theoretic criterion," IEEE Trans. Magn., vol. 39, no. 5, pp. 2228-2230, Sept. 2003.
7 W. Zeng, A. Kavcic, and R. Motwani, "Extraction of timing error parameters from readback waveforms," IEEE Trans. Magn., vol. 42, no. 2, pp. 194-199, Feb. 2006.


Foreword                                                 vii

Preface                                                   ix

Modulation Coding for a Two-Dimensional Optical
  Storage Channel
    W. M. J. Coene and A. H. J. Immink                     1

Characterization of Heat-Assisted Magnetic Recording
    R. Radhakrishnan, B. Vasic, F. Erden, and C. He       23

Cramer-Rao Bound for Timing Recovery on Channels with
  Inter-symbol Interference
    A. R. Nayak, J. R. Barry, and S.W. McLaughlin         41

Macro-Molecular Data Storage With Petabyte/cm3 Density,
  Highly Parallel Read/Write Operations, and Genuine
  3D Storage Capability
    M. Mansuripur and P. Khulbe                           63

Can We Explain the Faithful Communication of Genetic
    G. Battail                                            79

Data Storage and Processing in Cells: An Information
  Theoretic Approach
    O. Milenkovic                                        105

Ghostbusting: Coding for Optical Communications
    N. Kashyap and P. H. Siegel                          147

List of Working Group Presentations                      163

List of Workshop Presentations                           165

Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on January 25, 5008.