Insertion/Deletion Channels: Achievable Rates and Practical Coding Schemes

半个多世纪以来，已经开发了各种数字通信技术来解决在不完美链路上的可靠传输。这些发展包括信息理论，实用的信源和信道编码方案，以及各种有效的调制技术。许多不同的渠道模型在文献中被广泛考虑，设计的解决方案已被有效地实际使用;影响我们今天生活的世界的各个方面。除了其他更好理解的信道损伤（例如，噪声、符号间干扰等）之外，随机插入和/或删除也是可能的。在许多现代数字通信系统中，包括记录信道、通过因特网的传输、字符识别系统、隐蔽通信等，插入/删除的存在常常是更有效可靠的通信和更高的记录面密度的瓶颈。尽管在过去的50年中取得了许多进展，但具有缺失/插入的通道仍然远未被完全理解。举一个简单的例子，二进制删除信道的容量仍然是未知的，没有实际的编码/解码方案的性能接近可用的理论界限。本计画从资讯论的观点与通道编码的观点来研究插入/删除通道。具体而言，它涉及到开发新的信息理论的结果和实际的编码方案，这样的信道，扩展到信道与符号间干扰，加性噪声，和其他损害。考虑容量接近低密度奇偶校验（LDPC）和涡轮编码方案。此外，一组新的有趣的问题，涉及插入/删除无线衰落信道，包括多输入多输出（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.