An algebraic approach to convolutional codes

Abstract

Coding theory is concerned with digital communications. In every single communication is important that the correct message reaches the receiver, specially in a scenario where the communication channel is noisy. Thus, it is necessary to encode the message so possible errors can be detected and/or corrected by the receiver. So creating codes with a good e ciency and correctability is crucial. The existence of an algebraic structure proves the quality of these codes. In this thesis convolutional codes over the field F2 are studied. Different types of generator matrices are presented, and thus providing an algebraic approach to it, such as basic, reduced, minimal-basic and canonical matrices. The canonical generator matrices have nice properties, for example the predictable degree property, and an approach by valuation theory is given. Furthermore, quantum error-correcting codes are studied in order to give foundations to a future work on quantum convolutional codes. The description uses stabilizer codes. Also a criteria to determine if a set of errors is correctable is provided.

A teoria de códigos está ligada à comunicação digital. Em todas as comunicações é importante que a mensagem correta chegue ao recetor, especialmente num cenário onde o canal de comunicação apresenta ruído. Por isso, é necessário codificar a mensagem para que possíveis erros possam ser detetados e/ou corrigidos pelo recetor. É, pois, crucial criar códigos com uma boa eficiência e capacidade de correção. A existência de uma estrutura algébrica atesta a qualidade destes códigos. Nesta tese, códigos convolucionais sobre o corpo F2 são estudados. Diferentes tipos de matrizes são apresentadas, fornecendo assim uma abordagem algébrica, tais como básicas, reduzidas, básicasminimais e matrizes canónicas. As matrizes canónicas têm propriedades interessantes, por exemplo, a previsibilidade do grau, e uma caracterização através da "valuation theory" é feita. Além disso, uma descrição sobre códigos correctores de erros quânticos é feita a fim de fornecer alicerces para um futuro trabalho sobre códigos convolucionais quânticos. O estudo é feito pelos códigos estabilizadores. Também se fornece um critério para determinar se um conjunto de erros é corrigível.