Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/17953
Title: | Distance properties of convolutional codes over Z pr |
Other Titles: | Propriedades das distâncias dos códigos convolucionais sobre Z pr |
Author: | Toste, Marisa Lapa |
Advisor: | Pinto, Maria Raquel Rocha Avelli, Diego Oscar Napp |
Keywords: | Corpos finitos Dualidade (Matemática) Convoluções (Matemática) Matemática Anéis (Álgebra) Teoria de codificação |
Defense Date: | 2016 |
Publisher: | Universidade de Aveiro |
Abstract: | Nesta tese consideramos códigos convolucionais sobre o anel polinomial
[ ] r p
′ D , onde p é primo e r é um inteiro positivo. Em particular, focamo-nos
no conjunto das palavras de código com suporte finito e estudamos as suas
propriedades no que respeita às distâncias. Investigamos as duas
propriedades mais importantes dos códigos convolucionais, nomeadamente, a
distância livre e a distância de coluna.
Começamos por analisar e solucionar o problema de, dado um conjunto de
parâmetros, determinar a distância livre máxima possível que um código
convolucional sobre [ ] r p
′ D pode atingir. Com efeito, obtemos um novo limite
superior para esta distância generalizando os limites obtidos no contexto dos
códigos convolucionais sobre corpos finitos. Além disso, mostramos que esse
limite é ótimo, no sentido em que não pode ser melhorado. Para tal,
apresentamos construções de códigos convolucionais (não necessariamente
livres) que permitem atingir esse limite, para um certo conjunto de parâmetros.
De acordo com a literatura chamamos a esses códigos MDS.
Definimos também distâncias de coluna de um código convolucional. Obtemos
limites superiores para as distâncias de coluna e chamamos MDP aos códigos
cujas distâncias de coluna atingem estes limites superiores. Além disso,
mostramos a existência de códigos MDP. Note-se, porém, que os códigos
MDP apresentados não são completamente gerais pois os seus parâmetros
devem satisfazer determinadas condições.
Finalmente, estudamos o código dual de um código convolucional definido em
(( )) r p
′ D . Os códigos duais de códigos convolucionais sobre corpos finitos
foram exaustivamente investigados, como é refletido na literatura sobre o
tema. Estes códigos são relevantes pois fornecem informação sobre a
distribuição dos pesos do código e é neste sentido a inclusão deste assunto no
âmbito desta tese. Outra razão importante para o estudo de códigos duais é a
sua utilidade para o desenvolvimento de algoritmos de descodificação quando
consideramos um erasure channel. Nesta tese são analisadas algumas
propriedades fundamentais dos duais. Em particular, mostramos que códigos
convolucionais definidos em (( )) r p
′ D admitem uma matriz de paridade. Para
além disso, apresentamos um método construtivo para determinar um
codificador de um código dual.
keywords
Convolutional codes, finite rings, free distance, column distance, MDS, MDP,
dual code
abstract
In this thesis we consider convolutional codes over the polynomial ring [ ] r p
′ D ,
where p is a prime and r is a positive integer. In particular, we focus in the
set of finite support codewords and study their distances properties. We
investigate the two most important distance properties of convolutional codes,
namely, the free distance and the column distance.
First we address and fully solve the problem of determining the maximum
possible free distance a convolutional code over [ ] r p
′ D can achieve, for a
given set of parameters. Indeed, we derive a new upper bound on this distance
generalizing the Singleton-type bounds derived in the context of convolutional
codes over finite fields. Moreover, we show that such a bound is optimal in the
sense that it cannot be improved. To do so we provide concrete constructions
of convolutional codes (not necessarily free) that achieve this bound for any
given set of parameters. In accordance with the literature we called such codes
Maximum Distance Separable (MDS).
We define the notion of column distance of a convolutional code. We obtain
upper-bounds on the column distances and call Maximum Distance Profile
(MDP) the codes that attain the maximum possible column distances.
Furthermore, we show the existence of MDP codes. We note however that the
MDP codes presented here are not completely general as their parameters
need to satisfy certain conditions.
Finally, we study the dual code of a convolutional code defined in (( )) r p
′ D .
Dual codes of convolutional codes over finite fields have been thoroughly
investigated as it is reflected in the large body of literature on this topic. They
are relevant as they provide value information on the weight distribution of the
code and therefore fit in the scope of this thesis. Another important reason for
the study of dual codes is that they can be very useful for the development of
decoding algorithms of convolutional codes over the erasure channel. In this
thesis some fundamental properties have been analyzed. In particular, we
show that convolutional codes defined in (( )) r p
′ D admit a parity-check matrix.
Moreover, we In this thesis we consider convolutional codes over the polynomial ring [ ] r p ′ D , where p is a prime and r is a positive integer. In particular, we focus in the set of finite support codewords and study their distances properties. We investigate the two most important distance properties of convolutional codes, namely, the free distance and the column distance. First we address and fully solve the problem of determining the maximum possible free distance a convolutional code over [ ] r p ′ D can achieve, for a given set of parameters. Indeed, we derive a new upper bound on this distance generalizing the Singleton-type bounds derived in the context of convolutional codes over finite fields. Moreover, we show that such a bound is optimal in the sense that it cannot be improved. To do so we provide concrete constructions of convolutional codes (not necessarily free) that achieve this bound for any given set of parameters. In accordance with the literature we called such codes Maximum Distance Separable (MDS). We define the notion of column distance of a convolutional code. We obtain upper-bounds on the column distances and call Maximum Distance Profile (MDP) the codes that attain the maximum possible column distances. Furthermore, we show the existence of MDP codes. We note however that the MDP codes presented here are not completely general as their parameters need to satisfy certain conditions. Finally, we study the dual code of a convolutional code defined in (( )) r p ′ D . Dual codes of convolutional codes over finite fields have been thoroughly investigated as it is reflected in the large body of literature on this topic. They are relevant as they provide value information on the weight distribution of the code and therefore fit in the scope of this thesis. Another important reason for the study of dual codes is that they can be very useful for the development of decoding algorithms of convolutional codes over the erasure channel. In this thesis some fundamental properties have been analyzed. In particular, we show that convolutional codes defined in (( )) r p ′ D admit a parity-check matrix. Moreover, we provide a constructive method to explicitly compute an encoder of the dual code. |
Description: | Doutoramento em Matemática e Aplicações |
URI: | http://hdl.handle.net/10773/17953 |
Appears in Collections: | UA - Teses de doutoramento DMat - Teses de doutoramento |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
TESE Marisa toste.pdf | 651.28 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.