New Angles on the Multi-Dimensional Intersymbol Interference Problem

Washington State University, Pullman WA

Investigators

Abstract

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.