August 19, 2005

NSF Funds Four UC San Diego Research Projects In
Information Theory With Potential Real-World Applications

By Doug Ramsey

Four of the 27 grants awarded this summer in a special National Science Foundation (NSF) competition were submitted by experts on information theory at UCSD. The grants will fund theoretical research with potential real-world applications in digital communications, information storage and circuit design.

NSF launched the Theoretical Foundations (TF) grant program this year to support university research on fundamental issues of information science and technology, both within computation and communications and at the interface between these and other disciplines. NSF has earmarked more than $1.2 million over three years for the four UCSD projects.

“Information theory is an area where our Electrical and Computer Engineering department excels, so it was gratifying to see that NSF officials saw the merit in these four faculty research proposals,” said Frieder Seible, Dean of UCSD’s Jacobs School of Engineering.

Information theory as first propounded by mathematician Claude Shannon fifty years ago has been a central area of research at UCSD. One of its earliest electrical-engineering faculty members – Irwin Jacobs – went on to found Linkabit and QUALCOMM, two companies that applied the concepts of information theory to digital communications.

“These awards say something about the strength of UCSD in the areas of information theory and coding theory,” said Paul Siegel, director of the university’s Center for Magnetic Recording Research (CMRR). “In particular, the Jacobs School has become a world leader in applications of those theories to real-world areas through CMRR, the Center for Wireless Communications, and other campus research units.”

Siegel and fellow ECE professor Jack Wolf shared in the largest of the four grants to UCSD faculty. Their $455,205 award was also the second largest among the 27 projects approved nationwide to date. The electrical engineers will investigate "Capacity-Approaching Coding and Detection for Page-Oriented Digital Recording Channels."

As high-density disk drives are miniaturized to fit into consumer electronics devices such as digital cameras and iPods, magnetic recording technology faces fundamental physical limits on storage density and data transfer rates. “It is vital to pursue new approaches to high-capacity digital information storage,” said Siegel, “and many of these approaches use page-oriented reading and writing, in contrast to today's track-oriented methods.” Examples of page-oriented storage include recording on nanoscale patterned media, multi-beam two-dimensional optical recording, and optical holographic recording. Siegel and Wolf will study theoretical limits on the storage capacity of page-oriented technologies, as well as the signal processing and coding algorithms needed to achieve those limits in practice.

Jacobs School professor Alon Orlitsky’s study ‘predicting the unlikely’ receives NSF support

Professor Alon Orlitsky, who holds a joint appointment in ECE and the Computer Science and Engineering (CSE) department, will study “Predicting the Unlikely: Theory, Algorithms, and Applications.” His $262,974 award will fund research on so-called large-alphabet probability problems (such as language modeling for compression, speech recognition and data mining) where the number of possible outcomes is large compared to the size of the observed data sample. Orlitsky hopes to improve on existing algorithms such as Good-Turing which are effective in some applications and not in others. “My goal is to produce estimation algorithms that perform well in practice and also have provable optimality properties,” said Orlitsky. “This will involve addressing problems that are both theoretical -- for example the data size required to estimate the underlying distribution to within a given confidence level -- and computational, regarding the complexity and sequentiality of the derived algorithms.”

Also holding joint appointments in ECE and CSE, as well as in the Math department, professor Alexander Vardy will work on "Next Generation Decoders for Reed-Solomon Codes." This work will build upon his previous research that was selected by the IEEE Information Theory Society as the top publication in information theory of the past two years [see Related Links]. In that article Vardy developed -- jointly with Ralf Koetter of the University of Illinois at Urbana-Champaign -- an improved decoding algorithm for Reed-Solomon error-correcting codes that are used today in communication and storage devices ranging from computer hard drives to deep-space probes. Vardy will now receive $260,702 for his part of the new collaborative research, jointly with Caltech professor Robert McEliece and with Zhongfeng Wang of Oregon State University.

"Having proved that Reed-Solomon codes can correct many more errors than previously thought possible, we plan a broad line of attack to achieve much better performance with the same codes," said Vardy. "Our investigation will range from basic theory to the first-ever VLSI implementation of a soft-decision Reed-Solomon decoder. The results of our research could have far-reaching applications in communications and storage."

The NSF has also awarded $235,752 for professor Ian Galton’s investigation into "Signal Processing Enhanced DACs for Wideband Communication Systems." DACs are digital-to-analog circuits, which figure prominently in communication systems based on digital signal processing (DSP) that often require certain high-performance analog circuit blocks as well. As circuit designers strive to keep up with Moore’s Law, however, they are forced to make technology trade-offs that favor digital over analog circuitry.

“There is a fundamental disconnect between the requirements of present and future high-performance communications and the evolution of the semiconductor electronics industry,” argued Galton. “We hope to address an important aspect of this problem by developing DSP enhancement techniques that enable high-resolution, high-bandwidth DACs which are critical components in wideband transmitters.” The project will address some of the key distortions caused by digital-to-analog component mismatches, with a final goal of developing a proof-of-principle in the form of a CMOS integrated circuit prototype with record-setting performance. The prototype development process will provide feedback to guide theoretical work on the DAC problem.

Several of the UCSD academics receiving NSF Theoretical Foundations grants are also involved in an effort to build an information-theory research group within the California Institute for Telecommunications and Information Technology (Calit2). The institute’s UCSD Division is directed by long-time information theory researcher and electrical engineering professor Ramesh Rao.

Media Contact: Doug Ramsey, (858) 822-5825