New Angles on the Multi-Dimensional Intersymbol Interference Problem

传统的单轨磁盘和光盘存储技术已经达到了它们的密度极限。为了延续存储密度呈指数增长的历史趋势，工业正在开发二维(2D)存储技术，其中在2D块中写入和/或读出位。由于读/写系统的低通特性，这些2D存储系统遭受2D码间干扰(ISI)。2D-ISI可以被建模为具有有限范围2D模糊函数的输入块的二维卷积，然后是加性噪声。著名的维特比算法(VA)为1D ISI信道上的1D序列检测提供了最大似然序列估计(MLSE)。二维(或更高)维度的问题要困难得多，部分原因是与一维相比，二维没有自然的顺序。相对而言，2D问题还没有被很好地理解，已知方法的性能也不太令人满意。在最近的出版物中，我们描述了基于对被破坏的2D数据的Z字形扫描的2D ISI均衡算法，其性能大大优于所有先前发表的工作，并且非常接近2D-MLSE界限，在给定的信噪比下，理论上可以达到的最小误码率性能。此外，我们还证明了2D均衡器可以利用存在于许多数据文件中的2D相关性来实现进一步的性能提升。为了建立在这些有希望的初步结果的基础上，我们建议建立一个理论框架来有效地设计和优化二维和高维ISI均衡算法，对于独立和相关的数据，使用二进制和非二进制(M-ary)符号。所提出的研究对独立和相关的二进制和M-ary多维数据采用统一的最大似然估计方法；通过设计、分析和演示基于Turbo原则的迭代算法来解决问题，迭代Turbo译码算法的概念借用了迭代Turbo译码算法，该算法已经彻底改变了信道编码领域。PIs有一些有希望的初步结果，这些结果有助于指出其他有希望的调查领域；这些初步结果包括：用于2D二进制数据的2D-ISI降低的迭代行-列软判决反馈算法，其在高信噪比时比先前公布的最好结果高约0.4dB.Z字形2D ISI均衡算法，当与行-列算法级联时，在高信噪比时，其性能比先前公布的最佳结果高约0.7dB，并且在2D MLSE性能界限的0.2db以内。用于联合马尔可夫随机场估计和2D ISI均衡的算法，其在单独的2D ISI均衡的基础上获得高达2dBSNR的增益，当原始2D二进制源相关时，所提出的迭代算法同时使用行-列检测器和Z字形最大后验概率(MAP)检测器来交换软估计，与先前提出的行-列迭代算法相比，显著改善了数据估计。对于2D和3D ISI，以及对于相关和不相关的源数据，将探索向迭代算法添加额外扫描顺序的好处。迭代检测将与低密度奇偶校验(LDPC)码的迭代译码相结合，在2D和3D ISI中执行联合译码和检测。将研究新的降低复杂度的技术来处理具有M元符号的信源的多维ISI。建议的广泛影响：拟议的项目解决了多维ISI的解码和检测问题。因此，它结合了项目合作绩效信息系统两个相关但截然不同的专业领域的技术：图像处理(Sivakumar)和通信(Belzer)。所提出的研究将为多维ISI均衡问题的ML解产生一类迭代算法，从而显著提高磁存储和光存储的存储密度和数据速率。该项目还将使新兴的全息存储技术受益，其中激光用于在2D页面堆叠中存储比特，从而导致页面内2D ISI，以及由于页面间干扰而在更高密度下存储3D ISI。该项目将在2D和3D存储通道的差错控制编码方面取得进展，从而进一步提高存储密度。最后，我们希望为多进制多维ISI信道开发的新的降低复杂性的技术也将在一维ISI信道上使用，这种信道出现在广泛的电信应用中。该项目的教育影响将是招收和培养本科生和研究生。该项目将每年资助两名全日制研究生和大约两名本科生，为期三年。此外，在这个项目期间创造的新知识将被纳入私人投资促进机构的估计理论、信道编码和数字通信的研究生班。

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 manydata 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 investigatedto 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.