News Release

Alon Orlitsky: Predicting the unlikely

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.

CMRR director Paul Siegel

"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."

ECE professor Jack Wolf

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.

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."

ECE and CSE professor           Alexander Vardy

"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."

[Vardy's collaborator, Caltech's McEliece, delivered the 2005 Shannon Memorial Lecture at UCSD; to view a webcast of his presentation, click here.]

ECE professor Ian Galton

"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.