Algoritmos de reconstrução de sinal e correcção de erros

Abstract

Este trabalho situa-se na intersecção de três áreas: os códigos de controlo de erros, os métodos numéricos e o processamento de sinal (em especial no que diz respeito às técnicas de reconstrução de sinal e interpolação). Procura-se explorar as relações entre estes temas, desenvolvendo o potencial da interpolação e reconstrução de sinal no contexto da descodificação de códigos reais. Os códigos reais diferem dos tradicionais, formulados em termos de corpos finitos, pelo facto de se basearem no corpo real ou no corpo complexo, e por recorrerem a técnicas clássicas de processamento digital de sinal, como a FFT. Têm vantagens sobre os códigos tradicionais no que diz respeito à utilização de aritmética real, à possibilidade de utilização de processadores de sinal, à inexistência de restrições quanto aos tamanhos de bloco, e à tolerância a ruído de fundo. A desvantagem principal é a existência de erros de arredondamento e as dificuldades numéricas decorrentes. Neste trabalho examinam-se as alternativas de descodificação de códigos reais. Exploram-se duas formulações do problema, uma no domínio do tempo e outra no domínio da frequência, que conduzem a matrizes de tamanho mínimo para cada problema. Às equações obtidas foram aplicados de forma sistemática um conjunto de métodos directos, iterativos e semi-iterativos. Os resultados permitiram identificar a estratégia óptima de descodificação de códigos reais, que se concluiu depender criticamente dos detalhes do problema. A forma como a natureza do padrão de erros, o número total de erros, a redundância do código e o tamanho do bloco determinam a natureza do descodificador óptimo é estudada.

The subject of this work belongs to the intersection of three areas: error control coding, numerical methods and signal processing (particularly signal reconstruction and interpolation). The work seeks to explore the connections among these areas, in reference to the decoding of real number codes. Real number codes differ from the usual error control codes mainly in what concerns the underlying algebraic fields: real number codes depend on the real or complex fields, whereas traditional codes rely on finite (or Galois) fields. The advantages of real number codes include the convenience of using real arithmetic, the possibility of DSP-based implementation, the lack of restrictions regarding block size, and the tolerance to low-level noise. The main disadvantage is the existence of round off error, and the consequent numerical difficulties. This work examines several alternative ways of decoding real number codes. It explores two approaches to the problem, one in the time domain, the other in the frequency domain, both leading to minimum dimension equations. To the equations that follow from each of these formulations a number of iterative, noniterative and semi-iterative algorithms are systematically applied. The results reveal crucial information concerning the optimum decoding strategy for real number codes, and how the error pattern, the total number of errors, the code rate, and the block size determine the nature of the optimal decoding algorithm.