Insertion/Deletion Channels: Achievable Rates and Practical Coding Schemes

半个多世纪以来，各种数字通信技术得到了发展，以解决在不完美链路上的可靠传输问题。这些发展包括信息论、实用的信源和信道编码方案以及各种有效的调制技术。文献中广泛考虑了许多不同的渠道模型，设计的解决方案已被有效地投入实际使用；影响着我们今天生活的世界的方方面面。随机插入和/或删除除了其他更容易理解的信道损伤（例如噪声、符号间干扰等）之外，在许多现代数字通信系统中是最受关注的问题，包括记录信道、通过互联网传输、字符识别系统、秘密通信等等。插入/删除的存在往往是更有效可靠的通信和更高的记录面密度的瓶颈。尽管在过去的五十年里取得了许多进步，但带有删除/插入的频道仍然远远没有被完全理解。举一个简单的例子，一个二进制删除信道的容量仍然是未知的，并且没有实际的编码/解码方案的性能接近可用的理论界限。本项目从信息论的角度和信道编码的角度研究插入/删除信道。具体来说，它涉及到这些信道的新的信息理论结果和实用编码方案的发展，并扩展到具有符号间干扰，附加噪声和其他损伤的信道。考虑了容量逼近低密度奇偶校验（LDPC）和turbo编码方案。此外，还提出了一组涉及无线衰落信道上插入/删除的新问题，包括多输入多输出（MIMO）通信，并开发了解决方案。

For over half a century various digital communication techniques have been developed to address reliable transmission over imperfect links. These developments include information theory, practical source and channel coding schemes, and various effective modulation techniques. Many different channel models are considered in the literature extensively, and devised solutions have been put to efficient practical use; impacting all aspects of the world we live in today. Random insertions and/or deletions in addition to other, better understood, channel impairments (e.g. noise, intersymbol interference, etc.) are of utmost concern in many modern digital communication systems, including recording channels, transmissions through the Internet, character recognition systems, covert communications, and so on. The presence of insertions/deletions is often the bottleneck for more efficient reliable communications and higher areal densities in recording. Despite many advances over the past fifty years, channels with deletions/insertions are still far from being fully understood. To give a simple example, the capacity of a binary deletion channel is still unknown, and no practical coding/decoding schemes with performance close to available theoretical bounds are available. This project studies insertion/deletion channels from both an information theoretic point of view, and a channel coding perspective. Specifically, it involves development of novel information theoretic results and practical coding schemes for such channels, with extensions to channels with intersymbol interference, additive noise, and other impairments. Capacity approaching low density parity check (LDPC) and turbo coding schemes are considered. In addition, a new set of interesting problems involving insertions/deletions over wireless fading channels, including multi-input multi-output (MIMO) communications, are formulated, and solutions are developed.