Construction and decoding of convolutional codes over the erasure channel

编码理论是使用纠错码处理数据传输过程中的纠错。纠错码的原理是增加消息的冗余度，以便能够纠正传输错误或重建丢失的数据。该项目的目的是开发最大距离轮廓(MDP)卷积码在擦除信道上的新结构和高效译码算法。当使用该信道时，发送的码元要么被正确接收，要么丢失。此外，还应考虑MDP卷积码的特殊子类，即反向MDP卷积码和完全MDP卷积码。这些码具有附加的特性，这些特性对于译码是有利的。在这个项目的第一部分，我想开发反向MDP和完全MDP卷积码的一般结构，其中对于完全MDP卷积码，人们必须首先证明它们对于所有码参数的存在性。到目前为止，MDP卷积码只有在大域上的构造，这使得译码算法非常复杂。在本课题的第二部分中，我计划通过两种方式来研究MDP卷积码的高效译码算法：第一，通过考虑奇偶校验矩阵；第二，通过使用卷积码的系统论表示。对于第二种方法，我将利用每个卷积码可以用有限域上的线性系统来描述，最后，我将研究这类MDP卷积码是否能够在无记忆的q元擦除信道上达到香农容量，即目标是找到可能具有较大传输速率和可能较小差错概率的码。当使用上述信道时，来自具有Q个元素的有限域的码元被发送，并且码元的擦除概率与先前的码元无关。

Coding theory is dealing with error correction during data transmission using error correcting codes. The principle of an error correcting code is to add redundancy to a message, in order to make it possible to correct transmission errors or to reconstruct lost data.The aim of the project is to develop new constructions and efficient decoding algorithms for maximum distance profile (MDP) convolutional codes over the erasure channel. When using this channel, a transmitted symbol is either received correctly or gets lost. Moreover, special subclasses of MDP convolutional codes, the reverse-MDP and complete-MDP convolutional codes should be considered. These codes have additional properties, which are of advantage for decoding. The motivation for this project is provided by the necessity for decoding with least possible delay in applications like internet traffic and in particular, video streaming.In the first part of the project, I want to develop general constructions for reverse-MDP and complete-MDP convolutional codes, where for complete-MDP convolutional codes, one has to prove their existence for all code parameters first. Up to now there are only constructions for MDP convolutional codes over fields of large size, which makes decoding algorithms very complex. Therefore, another aim is to develop constructions of MDP convolutional codes for small field sizes and to obtain a bound for the necessary field size such that a MDP convolutional code exists.In the second part of the project, I plan to approach the development of efficient decoding algorithms for MDP convolutional codes over the erasure channel in two ways: firstly, by considering the parity-check matrix and secondly, by using the systems-theoretic representation of a convolutional code. For the second way, I will use that each convolutional code could be described by a linear system over a finite field.Finally, I will investigate if the class of MDP convolutional codes is capable to achieve Shannon capacity over the q-ary erasure channel without memory, i.e. the aim is to find codes with possibly large transmission rates and possibly small error probabilities. When using the above channel, symbols from a finite field with q elements are transmitted and the erasure probability of a symbols is independent of previous symbols.