Traditional single-track magnetic and optical disk storage technologies have reached their density limits. To continue the historical trend of exponentially increasing storage density, two-dimensional (2D) storage techniques, wherein bits are written and/or read in 2D blocks, are being developed by industry. These 2D storage systems suffer from 2D intersymbol interference (ISI) due to the low-pass nature of the read/write system. The 2D-ISI can be modeled as two-dimensional convolution of the input block with a finite-extent 2D blurring function, or "mask", followed by additive noise.
The well-known Viterbi algorithm (VA) provides the maximum likelihood sequence estimate (MLSE) for detection of 1D sequences on 1D ISI channels. The problem in two (or higher) dimensions is considerably more difficult, due in part to the lack of a natural order in 2D as opposed to 1D. Relatively speaking, the 2D problem is not as well understood, and the performance of known methods is less than satisfactory. In recent publications, we describe 2D ISI equalization algorithms, based on zig-zag scanning of the corrupted 2D data, that substantially outperform all previously published work, and that come very close to the 2D-MLSE bound, the theoretically best attainable performance in terms of minimal bit error rate for a given signal-to-noise (SNR) ratio. Also, we have demonstrated that the 2D correlation present in many data files can be exploited by the 2D equalizer to achieve even further performance gains. To build on these promising preliminary results, we propose to develop a theoretical framework for efficient design and optimization of two and higher-dimensional ISI equalization algorithms, for both independent and correlated data, with both binary and non-binary ("M-ary") symbols.
The proposed research employs a unified approach to MLSE for independent and correlated binary and M-ary multi-dimensional data; problems are addressed by designing, analyzing and demonstrating iterative algorithms based on the turbo principle, a concept borrowed from the iterative turbo decoding algorithm that has revolutionized the field of channel coding. The PIs have a number of promising preliminary results that serve to point out additional promising areas of investigation; these preliminary results include:
An iterative row-column soft-decision feedback algorithm for 2D-ISI reduction in 2D binary data, which outperforms the best previously published result by about 0.4 dB at high SNR.
A zig-zag 2D ISI equalization algorithm, which, when concatenated with the row-column algorithm, outperforms the best previously published result by about 0.7 dB at high SNR, and comes within 0.2 dB of the 2D MLSE performance bound.
An algorithm for joint Markov random field estimation and 2D ISI equalization, which achieves up to 2 dB SNR gains over 2D ISI equalization alone, when the original 2D binary source is correlated.
The proposed iterative algorithms use both row-column and zig-zag maximum-a-posteriori (MAP) detectors which exchange soft estimates, resulting in significantly improved data estimates compared to previously proposed row-column iterative algorithms. The benefits of adding additional scan orders to the iterative algorithm will be explored, for both 2D and 3D ISI, and for both correlated and non-correlated source data. Iterative detection will be combined with iterative decoding of low-density parity-check (LDPC) codes to perform joint decoding and detection in 2D and 3D ISI. New complexity reduction techniques will be investigated to handle multi-dimensional ISI for sources with M-ary symbols.
Broader impacts of the proposal: The proposed project addresses the problem of decoding and detection in multi-dimensional ISI. As such, it combines techniques from the two related yet distinct fields of expertise of the project's co-PIs: image processing (Sivakumar) and communications (Belzer). This yields a good synergy between problem formulations and known solution techniques between the two fields.
The proposed research will produce a class of iterative algorithms for ML solutions to the multidimensional ISI equalization problem, thereby significantly improving storage densities and data rates for magnetic and optical storage. The project will also benefit the emerging technology of holographic storage, wherein lasers are used to store bits in stacks of 2D pages, leading to intra-page 2D ISI, and, at higher densities, 3D ISI due to inter-page interference. The project will result in advances in error control coding for 2D and 3D storage channels, thereby enabling further increases in storage density. Finally, we expect that the novel complexity reduction techniques we propose to develop for M-ary multi-dimensional ISI channels will also be of use on 1D ISI channels, which occur in a wide variety of telecommunication applications.
The educational impact of this project will be the recruitment and training of undergraduate and graduate students. The project will support two full-time graduate students and about two undergraduate students per year, for three years. In addition, new knowledge created during this project will be integrated into the PIs' graduate courses in Estimation Theory, Channel Coding and Digital Communications.
This research project involves equalization and error control coding for two and three dimensional (2D and 3D) mass storage systems. To continue the historical trend of exponentially increasing storage density, two-dimensional (2D) storage techniques, wherein bits are written in 2D blocks (rather than 1D tracks), are being developed by industry for magnetic and optical disks, and also for newer 3D technologies like holographic storage. These new multi-dimensional storage techniques promise density and data rate increases of more than an order of magnitude over current state of the art. But 2D and 3D storage systems suffer from 2D and 3D intersymbol interference (ISI) due to the low-pass nature of the read/write system; specifically, 2D ISI occurs when signals from bits surrounding the target bit interfere with the target bit's signal during writing and reading of the disk. 2D-ISI can be modeled as 2D convolution (or filtering) of the input data with a finite-extent 2D blurring mask, followed by additive noise. Without effective equalization, 2D and 3D ISI will cause unacceptably high bit error rates (BERs) in next-generation magnetic and optical storage systems. Multi-dimensional ISI equalization is thus a key enabling technology for such systems. The project's major outcomes are summarized below. 1) In a 2007 journal article, the co-PIs and their student describe an iterative row-column soft decision feedback equalizer for reduction of 2D-ISI on binary images; when the source image is blurred with the 2 x 2 averaging mask, the equalizer achieves performance within 0.6 dB of (i.e., requires just 100.06 = 1.15 times more signal power than) the theoretical optimum, when the bit error rate (BER) is 2 x 10-5. This performance was 0.3 dB better than (i.e., required 0.3 dB less signal power than) that of the previous state of the art at the time. When the source image is blurred with the 3 x 3 averaging mask, the equalizer performs within 1.2 dB of the theoretical optimum. 2) The pixels in digital photographs are highly correlated within any given small neighborhood. In a 2008 journal article, the co-PIs and their student describe how to exploit this correlation when source images are transmitted over 2D-ISI channels, in order to reduce the signal power required to attain a given BER after equalization. We model the correlation as a first-order 2D Markov random field (MRF), and process the received image with a joint MRF detector and 2D-ISI detector; the 2D-ISI detector is described in item 1 above. On natural binary source images, the combined MRF detector/equalizer performs up to 1.5 dB better than (i.e., requires about 10-0.15 = 70% of the signal power of) the 2D ISI equalizer alone; performance gains of up to 2.5 dB are seen with synthetic images. 3) In a 2010 conference paper the co-PIs and their student propose computational complexity reduction and performance enhancement schemes for our previously published iterative row-column soft decision feedback algorithm described in item 1 above. For complexity reduction, we propose sorting and truncation of the soft decision feedback probability configurations. On 3×3 ISI channels, this technique reduces computational complexity by more than 95% with only marginal performance loss. This complexity-reduction technique is generalizable to other equalizer designs described in items 4 and 5 below. A journal article based on this paper is currently under preparation. 4) In a 2010 journal article, the co-PIs and their students consider design of a 2D-ISI equalizer that scans the blurred image in four different zigzag scanning orders. Weighted reliability information about the detected bits is exchanged between the four zigzag detectors, and between the row and column detectors described in item 1 above, until the system convergences to a final estimate of the original source image. The optimized system actually attains the theoretical optimum performance for the 2x2 averaging mask, and performs within 1 dB of optimum for the 3x3 averaging mask. To the best of our knowledge, this work represents the new state-of-the-art for equalization of 2D-ISI channels with 2x2 or 3x3 masks on the convolution-plus-noise channel, compared to previous work published in the open literature. 5) In two 2011 conference papers, the co-PIs and their student propose an improved version of the zigzag/row-column equalizer in 4 above. The improved version jointly estimates bits over small blocks of the received image, instead of assuming that the estimated bits are statistically independent. For the 3x3 averaging mask, the joint zigzag-row-column equalizer performs within 0.2 dB of the theoretical optimum, a 0.8 dB improvement over the equalizer in 4 above. A simplified row-column equalizer using joint estimation performs within 0.5 dB of optimum, yet requires only 1% of the computational complexity of the joint zigzag-row-column algorithm. A journal article based on this work has been submitted. This project provided financial support for five Ph.D. students, four M.S. students, and four summer undergraduate research students.
