Construction and decoding of convolutional codes over the erasure channel

编码理论是利用纠错码处理数据传输过程中的纠错问题。纠错码的原理是给报文增加冗余，以便能够纠正传输错误或重建丢失的数据。该项目的目的是为擦除信道上的最大距离轮廓（MDP）卷积码开发新的结构和有效的解码算法。当使用这个信道时，发送的符号要么被正确接收，要么丢失。此外，还应考虑MDP卷积码的特殊子类，即逆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.