UNIVERSIDADE ESTADUAL PAULISTA "JÚLIO DE MESQUITA FILHO" CAMPUS DE SÃO JOÃO DA BOA VISTA DÉBORA BEATRIZ CLARO ZANITTI Codificação e Decodificação de Códigos Matriciais MDS via Matrizes Superregulares para Correção de Erros em Rajada São João da Boa Vista 2021 DÉBORA BEATRIZ CLARO ZANITTI Codificação e Decodificação de Códigos Matriciais MDS via Matrizes Superregulares para Correção de Erros em Rajada Trabalho de Graduação apresentado ao Conselho de Curso de Graduação em Engenharia Eletrônica e de Telecomunicações do Campus de São João da Boa Vista, Universidade Estatual Paulista "Júlio de Mesquita Filho", como parte dos requisitos para obtenção do diploma de Graduação em Engenharia Eletrônica e de Telecomunicações . Orientador: Profa. Dra. Cintya Wink de Oliveira Benedito São João da Boa Vista 2021 Z31c Zanitti, Débora Beatriz Claro Codificação e decodificação de códigos matriciais MDS via matrizes superregulares para correção de erros em rajada / Débora Beatriz Claro Zanitti. -- São João da Boa Vista, 2021 84 p. : il., tabs. Trabalho de conclusão de curso (Bacharelado - Engenharia de Telecomunicações) - Universidade Estadual Paulista (Unesp), Câmpus Experimental de São João da Boa Vista, São João da Boa Vista Orientadora: Cintya Wink de Oliveira Benedito 1. Códigos corretores de erros (Teoria da informação). 2. Codificação. 3. Teoria da informação. 4. Galois, Teoria de. 5. Telecomunicações. I. Título. Sistema de geração automática de fichas catalográficas da Unesp. Biblioteca do Câmpus Experimental de São João da Boa Vista. Dados fornecidos pelo autor(a). Essa ficha não pode ser modificada. UNIVERSIDADE ESTADUAL PAULISTA “JÚLIO DE MESQUITA FILHO” CÂMPUS EXPERIMENTAL DE SÃO JOÃO DA BOA VISTA GRADUAÇÃO EM ENGENHARIA ELETRÔNICA E DE TELECOMUNICAÇÕES TRABALHO DE CONCLUSÃO DE CURSO CODIFICAÇÃO E DECODIFICAÇÃO DE CÓDIGOS MATRICIAIS MDS VIA MATRIZES SUPERREGULARES PARA CORREÇÃO DE ERROS EM RAJADA Aluno: Débora Beatriz Claro Zanitti Orientadora: Profª. Drª. Cintya Wink de Oliveira Benedito Banca Examinadora: - Cintya Wink de Oliveira Benedito (Orientadora) - Antonio Aparecido de Andrade (Examinador) - Grasiele Cristiane Jorge (Examinadora) A ata da defesa com as respectivas assinaturas dos membros encontra-se no prontuário do aluno (Expediente nº 009/2020) AGRADECIMENTOS Primeiramente a Deus. À minha mãe, Aurora Rosângela Claro, que nunca mediu esforços para me apoiar e incentivar durante todas as etapas da minha vida. Às minhas irmãs, Camila e Marina, que sempre foram inspirações de mulheres e exemplos de dedicação para mim. Aos demais familiares, que sempre estiveram ao meu lado, por todo carinho e compreensão. À minha orientadora, Profa. Dra. Cintya Wink de Oliveira Benedito, por toda compreensão, disposição, conhecimento, paciência, amizade e confiança durante os anos de iniciação científica. Que com o brilho nos olhos ao compartilhar sua pesquisa na área de teoria da codificação fez com que eu me apaixonasse também. Aos professores da banca examinadora, Prof. Dr. Antonio Aparecido de Andrade e Profa. Dra. Grasiele C. Jorge , pela disponibilidade e cuidado que depositaram ao aceitarem avaliar este trabalho. A todos os professores e funcionários da Unesp de São João da Boa Vista pelos ensinamentos e conselhos. Aos meus amigos, Amanda Belchior, Ana Letícia Coradi, Angélica Braga, Caio Andrade, Caio Grilo, Gabriela Prestes, Julia Duarte, Leonardo Marques, Letícia Dal’Cól, Luis Chiang, Vinícius Rosa, que tornaram a caminhada mais leve e divertida, me proporcionando momentos inesquecíveis. Ao Allan Di Cunto D’Ávila de Almeida, por todo carinho, amizade e, principalmente, companhei- rismo em mais uma etapa. À FAPESP, pelo auxílio financeiro proveniente do Processo 2017/17948-8. E a todas as pessoas que de alguma forma contribuíram para a realização deste trabalho. Este trabalho contou com o apoio da seguinte entidade: processo nº 2017/17948-8, Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) RESUMO Este trabalho de conclusão de curso apresenta uma construção de códigos matriciais MDS (Maximum Distance Separable) com o objetivo de abordar uma estratégia de correção de erros em rajada nestes códigos. Para obter um código com esta propriedade, a matriz de verificação de paridade é construída utilizando matrizes superregulares, em especial as matrizes de Vandermonde e as matrizes de Cauchy, e a matriz companheira de Frobenius obtida através de um polinômio primitivo sobre Fq[x]. A partir desta construção, apresenta-se um algoritmo de decodificação para correção de uma rajada de erros em códigos matriciais MDS com parâmetros [m + k, k,m + 1] sobre Fbq, do qual b refere-se ao comprimento da rajada de erro, para todo m ≥ 2 e de até duas rajadas de erros em códigos matriciais MDS com parâmetros [m + k, k,m + 1] sobre Fbq, para todo m ≥ 4. Além disso são apresentados alguns exemplos para correção de três rajadas de erros. Os códigos matriciais são códigos corretores de erros bidimensionais que possuem como principal característica a habilidade de corrigir erros em rajada (burst of errors), ou seja, erros que ocorrem em bits consecutivos. Já os códigos de máxima distância de separação, MDS, são códigos em que a distância mínima é a máxima possível. Essa característica é importante pois na teoria da codificação a distância mínima está relacionada com a capacidade de correção de erros do código, além de fornecer proteção máxima contra falhas de um dispositivo para uma dada quantidade de redundância. O algoritmo proposto é uma generalização do algoritmo apresentado por [CARDELL, CLIMENT e REQUENA 2013]. PALAVRAS-CHAVE: Codificação. Decodificação. Códigos Matriciais MDS. Matrizes Superregula- res. Erros em Rajadas. ABSTRACT This work presents a construction of MDS Array Codes (Maximum Distance Separable Array Codes) in order to approach a burst correction strategy in these codes. To obtain a code with this property, the parity check matrix is constructed using superregular matrices, in particular Vandermonde matrices and Cauchy matrices, and the Frobenius companion matrix obtained through a primitive polynomial over Fq[x]. Based on this construction, a decoding algorithm is presented to correct a burst of errors in MDS array codes with parameters [m+ k, k,m+ 1] over Fbq, where b refers to the length of the error burst, for all m ≥ 2 and up to two bursts of errors in MDS array codes with parameters [m+ k, k,m+ 1] over Fbq, for all m ≥ 4. In addition, some examples are presented to correct three bursts of errors. Array codes are two-dimensional error correction codes whose main characteristic is the ability to correct burst errors, that is, errors that occur in consecutive bits. The Maximum Distance Separable codes, MDS, are codes in which the minimum distance is the maximum possible. This characteristic is important because, in coding theory, the minimum distance is related to the error correction capacity of the code in addition to providing maximum protection against failures of a device for a given amount of redundancy. The proposed algorithm is a generalization of the algorithm presented by [CARDELL, CLIMENT e REQUENA 2013]. KEYWORDS: Encoding. Decoding. MDS Array Codes. Superregular Matrices. Burst Errors. LISTA DE ILUSTRAÇÕES Figura 1 Sistema de comunicação digital básico. . . . . . . . . . . . . . . . . . . . . . . 12 Figura 2 Sistema de armazenamento distribuído. . . . . . . . . . . . . . . . . . . . . . 13 Figura 3 Palavra-código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Figura 4 Código matricial unidimensional. . . . . . . . . . . . . . . . . . . . . . . . . . 49 Figura 5 Código matricial bidimensional. . . . . . . . . . . . . . . . . . . . . . . . . . 50 Figura 6 Código matricial bidimensional A(3, 3). . . . . . . . . . . . . . . . . . . . . . 51 Figura 7 Código matricial bidimensional A(3, 6). . . . . . . . . . . . . . . . . . . . . . 51 Figura 8 Paridades diagonais para um código A(5, 5). . . . . . . . . . . . . . . . . . . 52 Figura 9 Exemplo de codificação para um código A(5, 5). . . . . . . . . . . . . . . . . 52 Figura 10 Código matricial [25, 16]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Figura 11 Detecção de 1, 2 e 3 erros em códigos matriciais. . . . . . . . . . . . . . . . . 54 Figura 12 Rajada de erro na primeira linha do código. . . . . . . . . . . . . . . . . . . . 55 Figura 13 Rajada de erro na terceira linha do código. . . . . . . . . . . . . . . . . . . . . 55 Figura 14 Exemplo de coordenadas para código matricial. . . . . . . . . . . . . . . . . . 56 Figura 15 Código matricial A(5, 7). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Figura 16 Decodificação do código matricial A(5, 7). . . . . . . . . . . . . . . . . . . . . 57 LISTA DE TABELAS Tabela 1 – Tabela para adição em Z2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Tabela 2 – Tabela para multiplicação em Z2 . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Tabela 3 – Adição módulo-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Tabela 4 – Multiplicação módulo-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Tabela 5 – Adição módulo-7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Tabela 6 – Multiplicação módulo-7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Tabela 7 – Lista de polinômios primitivos . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Tabela 8 – Representação dos elementos de F24 gerados por p(x) = x4 + x3 + 1 . . . . . . . 23 Tabela 9 – Representação dos elementos de F25 gerados por p(x) = x5 + x3 + x2 + x+ 1 . 24 Tabela 10 – Representação dos elementos de F25 gerados por p(x) = x5 + x2 + 1 . . . . . . . 25 Tabela 11 – Representação dos elementos de F26 gerados por p(x) = x6 + x4 + x3 + x+ 1 . 26 Tabela 12 – Representação dos elementos de F23 gerados por p(x) = x3 + x2 + 1 . . . . . . . 29 Tabela 13 – Representação dos logaritmos de Zech . . . . . . . . . . . . . . . . . . . . . . . 30 Tabela 14 – Síndrome de erros da classe lateral. . . . . . . . . . . . . . . . . . . . . . . . . . 44 Tabela 15 – Isomorfismo φ : F24 −→ F2[C] . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 LISTA DE SÍMBOLOS α Elemento primitivo A Matriz superregular b Comprimento da rajada de erro e grau do polinômio primitivo c Palavra-código C Matriz companheira de Frobenius C Código d Distância mínima de Hamming dh Distância de Hamming e Vetor erro Fq Corpo finito G Matriz geradora de um código G Grupo H Matriz verificação de paridade I Matriz identidade k Dimensão do código m Variável auxiliar para geração de um código matricial MDS N Conjunto dos números naturais n Comprimento do código p Número primo p(x) Polinômio primitivo s Síndrome do código u Mensagem a ser codificada v Vetor de informação recebida W Peso de Hamming w Peso mínimo de Hamming Z Conjunto dos números inteiros SUMÁRIO 1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 CONCEITOS PRELIMINARES . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1 Estruturas Algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.1 Grupo, Corpo e Anéis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.2 Espaços Vetoriais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1.3 Corpo de Finitos e suas Extensões . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.4 Construção de Corpos de Galois . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.1.5 Logaritmo de Zech . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2 Matrizes Superregulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.2.1 Matriz de Vandermonde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2.2 Matriz de Cauchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3 CÓDIGOS CORRETORES DE ERROS . . . . . . . . . . . . . . . . . . . . . 34 3.1 Códigos de Bloco Lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.1.1 Códigos de Máxima Distância de Separação (MDS) . . . . . . . . . . . . . . . . 45 3.2 Códigos Matriciais Lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.2.1 Códigos Matriciais de Paridade . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4 CODIFICAÇÃO E DECODIFICAÇÃO DE CÓDIGOS MATRICIAIS MDS . 58 4.1 Codificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.2 Decodificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.2.1 Correção de Três Erros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 11 1 INTRODUÇÃO A teoria da codificação permeia o cotidiano sempre que se deseja transmitir ou receber uma informação, uma vez que, por melhor que seja um sistema de comunicação, ele sempre estará sujeito a ruídos ou a falhas, assim, a mensagem transmitida pode ter seu conteúdo comprometido devido a interferências no canal [RYAN e LIN 2009]. Os códigos corretores de erros estão presentes em inúmeras atividades diárias, dentre elas, os sistemas de comunicações digitais. Os exemplos mais evidentes incluem telefones celulares, televisão digital via satélite ou cabo, conexões de Internet sem fio via Wi-Fi e conexão de internet com fio via modem a cabo [VILLELA 2008, RYAN e LIN 2009]. Além dos sistemas digitais, os códigos corretores de erros também são amplamente utilizados em sistemas de armazenamento, incluindo unidades de disco magnético (“disco rígido”), unidades flash e sistemas de armazenamento distribuído. Ao receber um dado ele pode ser diferente daquele transmitido é, então, que se faz uso dos códigos corretores de erros, que buscam detectar e corrigir possíveis erros que ocorreram durante a transmissão de um dado [HUFFMAN e PLESS 2003]. A ideia básica de um código corretor de erro é de codificar uma informação acrescentando a ela, de maneira organizada, bits de redundâncias permitindo assim, ao receber tal informação, detectar e corrigir erros [VILLELA 2008]. Um sistema de comunicação digital, ou de armazenamento, pode ser esquematizado conforme apresentado na Figura 1. O codificador de fonte é um processador que converte os símbolos de informação da fonte em uma sequência alternativa de um alfabeto, buscando uma representação mais eficiente da informação, geralmente representado por um alfabeto q-ário. A função do codificador de canal é proteger os bits a serem transmitidos em um canal sujeito a ruído, distorção ou interferência, tornando-o um sistema mais confiável e seguro. Para isso é adicionado bits de paridade, ou redun- dância, aumentando o tamanho da mensagem a ser transmitida. Durante o processo de transmissão, a informação também passa pelo modulador que converte o sinal da saída do codificador de canal em uma forma de onda para a transmissão através do canal. Já o demodulador, partir do sinal recebido do canal, estima o sinal transmitido e converte para a sua versão digital. O decodificador de canal produz uma estimativa do sinal enviado pelo demodulador e, se for o caso, corrige possíveis erros, enquanto o decodificador de fonte estima a sequência enviada pela fonte, ou seja, a mensagem sem redundância. Durante todo o processo de transmissão de uma informação, os erros podem ocorrer tanto na codificação quanto na recepção do sinal, mas acontecem principalmente nos canais de transmissão, representados por canal de radiofrequência, canal de micro-ondas, cabos, circuito integrado digital, disco de armazenamento [VILLELA 2008]. Tais erros podem ocorrer de forma simples, somente um símbolo, ou em rajada, burst, que são erros em vários símbolos sucessivos. Portanto, decorre daí a necessidade de se estudar bons códigos corretores de erros que possibilitem recuperar a informação. Códigos corretores de erros na forma matricial são códigos lineares bidimensionais que possuem como principal característica a habilidade de corrigir erros em rajada [BLAUM, FARRELL e TILBORG 1998]. Códigos matriciais podem ser construídos, por exemplo, a partir de algum código de paridade simples, onde no caso de códigos binário, um bit é adicionado a palavra-código e este é simplesmente 12 Figura 1 – Sistema de comunicação digital básico. fonte: Próprio Autor. a soma módulo 2 dos bits de informação, ou de outros tipos de códigos, construídos em duas ou mais direções [BLAUM e FARRELL 1994]. Os códigos matriciais são conhecidos pela sua flexibilidade e facilidade de codificação e decodificação. Uma estratégia para obter bons códigos corretores de erros é que se obtenha códigos com a maior distância mínima possível. Códigos que possuem a propriedade de máxima distância de separação, ou seja, códigos em que a distância mínima é a máxima possível, são chamados de códigos MDS (Maximum Distance Separable) [ROMAN 1992]. Esta propriedade é importante na teoria da codificação pois a distância é definida como a diferenças de símbolos entre duas palavras-código, assim, quanto maior essa distância menor a probabilidade de se corrigir erroneamente para a palavra mais próxima. Códigos com esta propriedade fornecem proteção máxima contra falhas de um dispositivo para uma dada quantidade de redundância. Este trabalho aborda a codificação e decodificação dos códigos matriciais MDS. Tais códigos foram utilizados para correção de erros de apagamento como em gravações magnéticas [BLAUM, FARRELL e TILBORG 1998]. Porém, devido a sua capacidade de correção de rajadas de erros, estes códigos também têm se mostrado eficientes em aplicações recentes como em sistemas de armazenamento distribuído [DIMAKIS et al. 2010], para reparação eficiente de nós com falhas (apagamentos) [YE e BARG 2017] e também em reparos cooperativos [YE e BARG 2019]. Um sistema de armazenamento distribuído é composto por uma matriz de n discos com a mesma capacidade de armazenamento cada um. Desses n discos, k deles é destinados a armazenar os dados de origem, enquanto r deles contêm os dados de paridade que são calculados a partir dos dados de origem, recebendo o nome de discos de paridade, [YU, HOU e HAN 2020]. Assim, tem-se n = k + r, como mostra a Figura 2, onde D0, D1, . . ., Dk−1 refere-se aos discos de dados e C0, C1, . . ., Cr−1 aos discos de paridade. Este trabalho apresenta uma construção de códigos matriciais MDS. A codificação desses códigos se dá pela concepção da matriz verificação de paridade através das matrizes superregulares, que são aquelas onde todas suas submatrizes são não singulares e, neste trabalho, aborda-se como exemplo destas matrizes, as matrizes de Vandermonde e as matrizes de Cauchy. Outra matriz importante para essa construção são as matrizes companheiras de Frobenius, obtidas através de um polinômio primitivo 13 Figura 2 – Sistema de armazenamento distribuído. fonte: Próprio Autor. p(x) sobre Fq[x]. Na decodificação dos códigos matriciais MDS, são apresentados dois algoritmos, um para a correção de uma rajada de erro de comprimento b com parâmetros [m+ k, k,m+ 1] sobre Fb q, para todo m ≥ 2, e um capaz de corrigir até duas rajadas de erros em códigos matriciais MDS com parâmetros [m+ k, k,m+ 1] sobre Fbq, para todo m ≥ 4. Estes algoritmos são uma generalização do algoritmo apresentado por [CARDELL, CLIMENT e REQUENA 2013], do qual através dos estudos para generalização do algoritmo decodificador dos códigos matriciais MDS, foi possível apresentar exemplos com correção de três rajadas de erro. O presente trabalho está estruturado da seguinte forma. No Capítulo 2 abordamos os principais conceitos de álgebra abstrata, os quais auxiliarão no desenvolvimento do trabalho e que são indispen- sáveis para seu entendimento. Em especial serão apresentados os conceitos de extensões de Galois, logaritmo de Zech e de matrizes superregulares. No Capítulo 3 elucidamos os principais conceitos e resultados relacionados aos códigos corretores de erros de interesse neste trabalho, os códigos lineares e os códigos matriciais, assim como os códigos de máxima distância de separação (MDS). Para exemplificar os códigos matriciais e a correção de erros em rajada, será apresentado a codificação e decodificação de códigos matriciais de paridade. No Capítulo 4 apresentamos os códigos matriciais MDS, abordando uma estratégia de codificação e algoritmos de decodificação de até duas rajadas de erros. Além disso, apresentamos alguns exemplos de correção de três erros. E, por fim, no Capítulo 5 apresentamos as conclusões obtidas no desenvolvimento desde trabalho. 14 2 CONCEITOS PRELIMINARES Este trabalho tem como objetivo principal apresentar a codificação e decodificação de códigos matriciais MDS (Maximum Distance Separable) para correção de erros em rajada, e para tal é necessário fazer referência a alguns conceitos de álgebra abstrata. Este capítulo será de cunho leve com o intuito de indicar e exemplificar tópicos indispensáveis para a compreensão da construção de códigos e desenvolvimento do trabalho, as demonstrações matemáticas não são a prioridade. Na Seção 2.1, apresentamos conceitos de estruturas algébricas, tais como corpo e anéis, espaços vetoriais, extensão de Galois, polinômios primitivos e logaritmo de Zech. Já na Seção 2.2 introduzimos as matrizes superregulares, em especial as de Vandermonde e Cauchy. 2.1 ESTRUTURAS ALGÉBRICAS Nesta seção apresentamos conceitos e definições de estruturas algébricas como grupo, corpo e anéis. Além disso, apresentamos também manipulações e operações realizadas em um corpo. Os conceitos e resultados apresentados nesta seção podem ser encontrados em [RYAN e LIN 2009, DOMINGUES e IEZZI 1982, HUBER 1990, LIDL e NIEDERREITER 1986, BENEDITO 2010]. 2.1.1 Grupo, Corpo e Anéis Definição 2.1.1 Um grupo é um conjunto não vazio G com uma operação binária “ * ”, de modo que os seguintes axiomas sejam satisfeitos: 1. Fechamento da operação: qualquer que sejam a e b ∈ G, têm-se que a ∗ b também ∈ G; 2. Associatividade: qualquer que sejam a, b e c ∈ G tem-se: (a ∗ b) ∗ c = a ∗ (b ∗ c); 3. Elemento Identidade: existe um elemento e ∈ G tal que para qualquer elemento a de G tem-se: a ∗ e = e ∗ a = a; 4. Elemento Inverso: para qualquer elemento a ∈ G, existe um outro elemento a′ ∈ G tal que a ∗ a′ = a′ ∗ a = e. O grupo G com operação “*” é denotado por (G, ∗) e é dito abeliano ou comutativo se, para quaisquer elementos a e b ∈ G, tiver a ∗ b = b ∗ a. Definição 2.1.2 Um grupo G pode ser finito ou infinito, e o número total de elementos de G determina sua ordem. 15 Exemplo 2.1.1 Sejam o conjunto dos números inteiros representado por Z e a operação de adição “+”. Para ser denotado como um grupo, deve-se satisfazer todos os axiomas da Definição 2.1.1: 1. Fechamento da operação: para a e b ∈ Z, tem que a+ b ∈ Z; 2. Associatividade: (a+ b) + c = a+ (b+ c), para todo a, b e c ∈ Z; 3. Elemento Identidade: 0 ∈ Z tal que, a+ 0 = 0 + a = a, para todo a ∈ Z; 4. Elemento Inverso: para todo a ∈ Z, existem −a ∈ Z tal que, a+ (−a) = (−a) + a = 0; 5. Comutatividade: a+ b = b+ a, para todo a, b ∈ Z. Assim, o conjunto Z é um grupo comutativo. Exemplo 2.1.2 Considere o subconjunto dos inteiros dado por Z2 = {0, 1} e a operação adição “+”. A tabela da operação é dada por Tabela 1 – Tabela para adição em Z2 + 0 1 0 0 1 1 1 0 Esta operação binária é chamada de adição módulo-2, ou alternativamente referida como (mod 2). Para qualquer inteiro i é possível construir um grupo de ordem i com operação binária módulo-i. Definição 2.1.3 Seja A um conjunto não vazio com duas operações binárias, adição “+” e multipli- cação “·”, sobre ele. A será denominado anel se satisfazer os seguintes axiomas: 1. (A,+) é um grupo abeliano; 2. (A, ·) é associativa: se a, b, c ∈ A, então a · (b · c) = (a · b) · c; 3. A multiplicação é distributiva em relação a adição, ou seja, se a, b, c ∈ A, então a · (b+ c) = a · b+ a · c, e também, (a+ b) · c = a · c+ b · c. Um anel A com as operações adição “+” e multiplicação “·” é denotado por (A,+, ·). Definição 2.1.4 Nas condições descritas na Definição 2.1.3, tem-se que 1. A é dito um anel comutativo quando a multiplicação do anel A satisfazer a · b = b · a, para todo a, b ∈ A; 2. A é dito um anel com unidade quando a multiplicação admitir um elemento neutro, 1, em que 1 ∈ A, tal que a · 1 = 1 · a = a, para todo a ∈ A; 16 3. A é dito um anel comutativo com unidade quando a multiplicação é comutativa e possui unidade. Definição 2.1.5 Sejam A e B dois anéis com elementos identidades 1A e 1B, respectivamente. Uma aplicação φ : A −→ B é um homomorfismo de anéis de A em B se satisfaz as seguintes condições: 1. φ(x+ y) = φ(x) + φ(y), para todo x, y ∈ A; 2. φ(xy) = φ(x)φ(y), para todo x, y ∈ A; 3. φ(1A) = 1B. Definição 2.1.6 É chamado de monomorfismo um homomorfismo injetor e de isomorfismo um homo- morfismo bijetor. Os isomorfismos de um anel A sobre si mesmo são chamados de automorfismos. Definição 2.1.7 Seja F um conjunto não vazio para o qual são definidas duas operações binárias, adição “+” e multiplicação “·”. O conjunto F com estas duas operações é um corpo se: 1. for um anel comutativo com unidade onde todo elemento é não inversível; 2. A multiplicação é distributiva em relação à adição, ou seja, dado quaisquer elementos a, b e c ∈ F, tem-se a · (b+ c) = a · b+ a · c. Denota-se um corpo F por (F,+, ·). O número de elementos de um corpo pode ser finito ou infinito, denotando-se por ordem a quantidade de elementos de um corpo. Definição 2.1.8 Um corpo F com uma quantidade finita de elementos q é chamado de corpo finito e será denotado por Fq. Exemplo 2.1.3 No Exemplo 2.1.2 viu-se que Z2 = {0, 1} é um grupo comutativo em relação a adição. Através da tabela para a multiplicação é dada por Tabela 2 – Tabela para multiplicação em Z2 · 0 1 0 0 0 1 0 1 Assim, a multiplicação módulo-2 verifica-se como um corpo finito, sendo 0 elemento neutro na adição e 1 elemento neutro na multiplicação. Se ao invés de Z2 = {0, 1} tivesse Zp = {0, 1, 2, ..., p − 1} com p um número inteiro primo, também teríamos um corpo finito chamado corpo primo Fp = Zp. A seguir apresentamos um exemplo para F3 = Z3 e F7 = Z7. 17 Exemplo 2.1.4 Para o caso de p = 3 e p = 7, tem-se Z3 = {0, 1, 2} e Z7 = {0, 1, 2, 3, 4, 5, 6} respectivamente. Nota-se que as operações são fechadas no corpo, ou seja, o resultado deve estar contido no conjunto. A seguir apresenta-se as tabelas de adição e multiplicação para Z3 e Z7. Tabela 3 – Adição módulo-3 + 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 Tabela 4 – Multiplicação módulo-3 · 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 Observa-se que na Tabela 3 referente a adição, tem-se 2 + 1 = 3 ≡ 0 (mod 3), e o mesmo ocorre na multiplicação. E, na Tabela 4, referente a multiplicação tem-se 2 · 2 = 4 ≡ 1 (mod 3). Além disso, nota-se que todos os elementos possuem elemento inverso aditivo e multiplicativo, comprovando assim que Z3 é um corpo. O mesmo ocorre para Z7. Tabela 5 – Adição módulo-7 + 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 2 3 4 5 6 0 2 2 3 4 5 6 0 1 3 3 4 5 6 0 1 2 4 4 5 6 0 1 2 3 5 5 6 0 1 2 3 4 6 6 0 1 2 3 4 5 Tabela 6 – Multiplicação módulo-7 · 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 2 0 2 4 6 1 3 5 3 0 3 6 2 5 1 4 4 0 4 1 5 2 6 3 5 0 5 3 1 6 4 2 6 0 6 5 4 3 2 1 É importante salientar que as tabelas de adição também são usadas para a subtração, assim como as tabelas da multiplicação são usadas para a divisão, para isso basta encontrar o elemento inverso para cada operação. Por exemplo, no Exemplo 2.1.4 se deseja subtrair 4 de 2, o primeiro passo deve ser encontrar inverso de 4 na Tabela 3, ou seja, o número que somado a 4 obtêm-se 0, sendo ele 3, e somar este valor a 2. Assim 2− 4 = 2 + (−4) = 2 + 3 = 5. Para a divisão o processo é análogo. Supondo que se queira dividir 5 por 3, na Tabela 6 deve- se procurar o inverso multiplicativo de 3, ou seja, o número que multiplicado por 3 obtêm-se 1, encontrando 5, assim 5 3 = 5 · (3−1) = 5 · 5 = 25 ≡ 4 (mod 7). 2.1.2 Espaços Vetoriais Nesta seção, apresentamos outro sistema algébrico, denominado espaço vetorial. Um tipo espe- cial de espaço vetorial desempenha um papel importante nos códigos corretores de erro, os quais estudaremos no Capítulo 3. 18 Definição 2.1.9 Sejam dados um corpo F, cujo elementos são chamados de escalares, e um conjunto V, cujos elementos serão chamados de vetores. Diremos que V é um espaço vetorial sobre F se existirem uma operação de adição em V e uma multiplicação dos elementos de V por escalares, possuindo as seguintes propriedades: 1. A adição é comutativa. 2. Para qualquer elemento a de F e qualquer elemento v de V, a · v é um elemento de V. 3. Para quaisquer elementos u e v de V e quaisquer elementos a e b de F, verifica-se a propriedade distributiva. 4. Para qualquer elemento v de V e quaisquer elementos a e b de F, verifica-se a propriedade associativa. 5. Seja 1 o elemento identidade de F. Então para qualquer elemento v de V 1 · v = v. O espaço vetorial sobre o corpo F2 tem um papel importante na teoria de codificação. Considere a sequência ordenada de n componentes [a0, a1, . . . , an−1] do qual cada elemento ai, para i = 0, . . . , n− 1, é um elemento do corpo F2, ou seja, ai = 0 ou ai = 1, comumente denotada como representação binária ou bits.Esta sequência é geralmente chamada de n-upla sobre F2, e uma vez que há duas possibilidades para ai, podemos definir 2n n-uplas distintas. Seja Vn o conjunto destas n-uplas. Defini-se a adição em Vn para u = [u0, u1, . . . , un−1] e v = [v0, v1, . . . , vn−1] como u + v = u = [u0 + v0, u1 + v1, . . . , un−1 + vn−1], (2.1) onde a soma módulo-2 também é uma n-upla sobre Vn. O produto escalar de uma n-upla de Vn e um elemento a de F2 é dado por a · [v0, v1, . . . , vn−1] = [a · v0, a · v1, . . . , a · vn−1] (2.2) onde a · vi é a multiplicação módulo-2. Exemplo 2.1.5 Seja n = 3. O espaço vetorial V3, de todas as 3-uplas sobre F2, consiste de 23 = 8 vetores dado por V3 = {000, 001, 010, 011, 100, 101, 110, 111}. Se somarmos quaisquer dois vetores como [001] e [101] obtemos outra 3-upla [001] + [101] = [100]. Se V for um espaço vetorial sobre um corpo F, um subconjunto S de V também poderá ser um espaço vetorial se seguir as condições impostas no Teorema 2.1.1. 19 Teorema 2.1.1 Seja S um subconjunto não vazio do espaço vetorial V sobre o corpo F. S é um subespaço de V se as seguintes condições são satisfeitas 1. Para dois quaisquer vetores u e v de S, u + v também é um vetor de S. 2. Para qualquer elemento a de F e qualquer vetor u de S, a · u pertence a S. Definição 2.1.10 Sejam v1, v2, . . . , vk k vetores de um espaço vetorial V sobre um corpo F. Sejam a1, a2, . . . , ak k escalares de F. A soma a1v1 + a2v2 + . . .+ akvk é chamada de combinação linear de v1, v2, . . . , vk. Definição 2.1.11 Um conjunto de vetores v1, v2, . . . , vk de um espaço vetorial V sobre um corpo F é linearmente independente se e somente se existirem k escalares não todos nulos a1, a2, . . . , ak tais que a1v1 + a2v2 + . . .+ akvk = 0. Exemplo 2.1.6 Os vetores [011], [010], [001] são linearmente independentes uma vez que 1 · [011] + 1 · [010] + 1 · [001] = [000] Um conjunto de vetores gera um espaço vetorial V se qualquer vetor de V é uma combinação linear de todos os vetores do conjunto. Em qualquer espaço vetorial ou subespaço vetorial existe pelo menos um conjunto B de vetores linearmente independentes que geram o espaço. Este conjunto é denominado por base do espaço vetorial. O número de vetores da base define a dimensão do espaço vetorial. 2.1.3 Corpo de Finitos e suas Extensões Os corpos finitos são de importância prática em muitas áreas, em especial na área da teoria da codificação [RYAN e LIN 2009]. Os corpos finitos são também chamados de corpos de Galois, em homenagem ao matemático francês Évariste Galois. Tem-se que para um grupo finito expresso pelo conjunto {0, 1, 2, 3, . . . , p− 1}, no qual p é um número primo, tem-se um corpo finito denotado por Fp = Zp. Para este corpo, ressalta-se que quaisquer operações realizadas são fechadas, devido a isto, utiliza-se de operações em (mod p), sendo o elemento neutro da adição e multiplicação 0 e 1, respectivamente. A partir de qualquer corpo finito Fp é possível construir uma extensão deste corpo. Para isso, seja b um inteiro positivo, tem-se que Fpb é um corpo denominado extensão de Galois que contém Fp como subcorpo. Códigos com símbolos no corpo binário F2 ou nas suas extensões F2b são comumente usados em transmissões digitais e sistemas de armazenamento, sendo que neste trabalho, visamos aplicações neste segundo caso. Com o intuito de facilitar a nomenclatura, tomamos q = pb e então Fq = Fpb . 20 Seja a um elemento não nulo de Fq, tem-se que as potências a1 = a, a2 = a · a, a3 = a · a · a, . . ., também pertencem ao corpo Fq. Como dito anteriormente, as operações de um corpo são fechadas, logo, para um corpo finito, todas as potências não podem ser distintas, existindo assim um ponto onde há repetição das potências. Sejam l, k inteiros tais que al = ak, tem-se al−k = 1, concluindo-se que para qualquer elemento diferente de zero de Fq, existe um inteiro positivo n tal que an = 1. Definição 2.1.12 Seja a um elemento não nulo pertencente à Fq. O menor inteiro positivo n, tal que an = 1, é chamado de ordem do elemento. Teorema 2.1.2 Seja a um elemento não nulo pertencente ao corpo finito Fq, então aq−1 = 1. Um polinômio p(x) ∈ Fq[x] pode ser expresso da seguinte forma p(x) = p0 + p1x+ p2x 2 + . . .+ pnx n, (2.3) onde p0, ..., pn ∈ Fq. O grau do polinômio é dado pela maior potência de x onde seu respectivo coeficiente não é nulo e um polinômio é dito mônico se o coeficiente para a maior potência for 1. Sejam a(x) = a0 + a1x+ . . .+ anx n e b(x) = b0 + b1x+ ...+ bmx m polinômios em Fq[x], com m ≤ n. A adição de a(x) e b(x) é realizada simplesmente adicionando os coeficientes de mesma potência em x, como segue a(x) + b(x) = (a0 + b0) + (a1 + b1)x+ ...+ (am + bm)x m + (am+1 + 0)xm+1 + ...+ (an + 0)xn, e o produto é dado por a(x) · b(x) = c0 + c1x+ ...+ cn+mx n+m, onde ck = ∑ i+j=k, 0≤i≤n,0≤j≤m ai · bj, para 0 ≤ k ≤ n + m. Para divisão, quando a(x) é dividido por b(x), obtemos um par único de polinômios sobre Fq, q(x) e r(x), de modo que a(x) = q(x) · b(x) + r(x), com r(x) = 0 ou 0 ≤ ∂r < ∂b, onde os polinômios q(x) e r(x) são chamados de quociente e resto, respectivamente. Definição 2.1.13 Um polinômio p(x) de grau b sobre Fq é dito irredutível sobre Fq se não for divisível por nenhum polinômio sobre Fq que tenha grau menor que b e maior que zero. 21 Teorema 2.1.3 Qualquer polinômio irredutível p(x) sobre Fq com grau b divide xq b−1 − 1. Um conceito importante que será abordado é o de polinômio primitivo. Definição 2.1.14 Um polinômio primitivo é um polinômio que gera todos os elementos de um corpo de extensão a partir de um corpo base. Polinômios primitivos também são polinômios irredutíveis. Também podemos definir um polinômio primitivo como um polinômio irredutível p(x) de grau b sobre Fq se o menor inteiro positivo n para o qual p(x) divide xn − 1 for n = qb − 1. Definição 2.1.15 Um elemento α de um corpo finito Fq é chamado de elemento primitivo se Fq = {1, α, α2, . . . , αq−2}, (2.4) ou seja, se a ordem de α é q − 1. Não é fácil reconhecer polinômios primitivos, no entanto há tabelas disponíveis em livros listando alguns deles, como encontrado em [RYAN e LIN 2009], ou também podem ser encontrados utilizando ferramentas computacionais. Para um dado inteiro positivo b pode haver mais do que um polinômio irredutível de grau b. Na Tabela 7 estão listados alguns exemplos de polinômios primitivos para determinados valores de b, gerados através do software matemático MATLAB, os quais alguns deles serão utilizados futuramente para o desenvolvimento de exemplos. Tabela 7 – Lista de polinômios primitivos b 2 1 + x+ x2 3 1 + x+ x3 1 + x2 + x3 4 1 + x+ x4 1 + x3 + x4 5 1 + x2 + x5 1 + x3 + x5 1 + x+ x2 + x3 + x5 1 + x+ x2 + x4 + x5 1 + x+ x3 + x4 + x5 1 + x2 + x3 + x4 + x5 6 1 + x+ x6 1 + x+ x3 + x4 + x6 1 + x5 + x6 1 + x+ x2 + x5 + x6 1 + x2 + x3 + x5 + x6 1 + x+ x4 + x5 + x6 22 2.1.4 Construção de Corpos de Galois Nesta seção mostraremos como realizar a construção da extensão de um corpo de Galois Fp = {0, 1, 2, . . . , p− 1}, com p um número primo. Primeiramente, inicia-se selecionando um polinômio primitivo de grau b sobre Fp. Seja p(x) = p0 + p1x+ p2x 2 + . . .+ pb−1x b−1 + xb ∈ Fp[x]. (2.5) Desde que o grau de p(x) seja b, o polinômio terá b raízes, as quais não pertencem a Fp e sim à sua extensão, Fbp. Seja α uma raiz de p(x). Define-se a multiplicação “·” para introduzir uma sequência de potências de α como segue 0 · 0 = 0; 0 · 1 = 1 · 0 = 0; 0 · α = α · 0 = 0; 1 · 1 = 1; 1 · α = α · 1 = α; α2 = α · α; α3 = α · α · α; ... αj = α · α · ... · α (j vezes). Assim, 0 · αj = αj · 0 = 0; 1 · αj = αj · 1 = αj; αi · αj = αi · αj = αi+j. Uma vez que α é uma raiz de p(x), pode-se substituir na Equação 2.5 em x por α e obter p(α) = p0 + p1α + p2α 2 + . . .+ pb−1α b−1 + αb = 0. (2.6) Através do Teorema 2.1.3, sabe-se que p(x) divide xpb−1 − 1, então xp b−1 − 1 = p(x) · q(x). (2.7) Substituindo-se por α αp b−1 − 1 = p(α) · q(α) = 0 · q(α) = 0, (2.8) 23 e consequentemente, αp b−1 = 1. (2.9) Dessa forma, a partir de αi(pb−1), onde i = 1, 2, . . ., as potências passam a se repetir. Portanto, a sequência contém pb elementos distintos, incluindo o elemento neutro 0, ou seja, Fq = Fpb = {0, 1, α, . . . , αb−2}. (2.10) Essas raízes podem ser expressas tanto na forma polinomial quanto por uma representação vetorial, onde os coeficientes são alocados em um vetor conforme o grau de suas potências. Essa representação é utilizada especialmente em somas e será elucidada no exemplo a seguir. Exemplo 2.1.7 Seja F2 = {0, 1} um corpo finito. Deseja-se construir a extensão de Galois F24 de F2. Sabendo que b = 4, considere p(x) = 1 + x3 + x4 um polinômio primitivo de grau 4 em F2[x], dado pela Tabela 7. Se α é uma raiz primitiva de p(x), tem-se que p(α) = 1 + α3 + α4 = 0 =⇒ α4 = α3 + 1. Sabendo então que α4 = α3 + 1 e que pela Equação 2.9 tem-se α24−1 = 1 =⇒ α15 = 1, é possível construir toda a extensão F24 . Por exemplo, α5 = α · α4 = α · (1 + α3) = α + α4 = 1 + α + α3, α6 = α · α5 = α · (1 + α + α3) = α + α2 + α4 = 1 + α + α2 + α3, α7 = α · α6 = α · (1 + α + α2 + α3) = α + α2 + α3 + α4 = 1 + α + α2. Na Tabela 8 são apresentados todos os elementos de F24 . Tabela 8 – Representação dos elementos de F24 gerados por p(x) = x4 + x3 + 1 Representação por Potência Representação Polinomial Representação Vetorial 0 0 0 0 0 0 1 1 1 0 0 0 α α 0 1 0 0 α2 α2 0 0 1 0 α3 α3 0 0 0 1 α4 1 + α3 1 0 0 1 α5 1 + α + α3 1 1 0 1 α6 1 + α + α2 + α3 1 1 1 1 α7 1 + α + α2 1 1 1 0 α8 α + α2 + α3 0 1 1 1 Continuação na próxima página 24 Tabela 8 – Representação dos Elementos de GF (24) Representação por Potência Representação Polinomial Representação Vetorial α9 1 + α2 1 0 1 0 α10 α + α3 0 1 0 1 α11 1 + α2 + α3 1 0 1 1 α12 1 + α 1 1 0 0 α13 α + α2 0 1 1 0 α14 α2 + α3 0 0 1 1 Para multiplicar dois elementos αj e αi, basta conservar a base e somar seus expoentes, usando do fato de que α24−1 = α15 = 1. Por exemplo, α2 · α3 = α5 e α8 · α9 = α17 = α15 · α2 = 1 · α2 = α2. Para dividir αj por αi, basta multiplicar αj pelo inverso multiplicativo de αi, ou seja, α15−i. Por exemplo, α4 α12 = α4 · α15−12 = α4 · α3 = α7 Para realizar somas, pode-se usar suas representações polinomiais ou representações vetoriais. Por exemplo, α4 + α10 = (1 + α3) + (α + α3) = 1 + α = α12, 1 + α5 + α10 = 1 + (1 + α + α3) + (α + α3) = 0. E usando a representação vetorial tem-se, α4 + α10 = 1001 + 0101 = 1100 = α12, 1 + α5 + α10 = 1000 + 1101 + 0101 = 0000 = 0. Exemplo 2.1.8 Sejam os polinômios primitivos p(x) = 1+x+x2+x3+x5 e p(x) = 1+x2+x5 ∈ F2, retirados da Tabela 7. A partir deles é possível criar extensões de F25 que são apresentadas nas Tabelas 9 e 10, respectivamente. E seja p(x) = 1+ x+ x3 + x4 + x6 ∈ F2, também retirado da Tabela 7. Na Tabela 11, é apresentada a extensão F26 proveniente desse polinômio primitivo. Tabela 9 – Representação dos elementos de F25 gerados por p(x) = x5 + x3 + x2 + x+ 1 Representação por Potência Representação Polinomial Vetor 0 0 00000 1 1 10000 α α 01000 α2 α2 00100 α3 α3 00010 α4 α4 00001 Continuação na próxima página 25 Tabela 9 – Representação dos elementos de F25 Representação por Potência Representação Polinomial Vetor α5 α3 + α2 + α + 1 11110 α6 α4 + α3 + α2 + α 01111 α7 α4 + α + 1 11001 α8 α3 + 1 10010 α9 α4 + α 01001 α10 α3 + α + 1 11010 α11 α4 + α2 + α 01101 α12 α + 1 11000 α13 α2 + α 01100 α14 α3 + α2 00110 α15 α4 + α3 00011 α16 α4 + α3 + α2 + α + 1 11111 α17 α4 + 1 10001 α18 α3 + α2 + 1 10110 α19 α4 + α3 + α 01011 α20 α4 + α3 + α + 1 11011 α21 α4 + α3 + 1 10011 α22 α4 + α3 + α2 + 1 10111 α23 α4 + α2 + 1 10101 α24 α2 + 1 10100 α25 α3 + α 01010 α26 α4 + α2 00101 α27 α2 + α + 1 11100 α28 α3 + α2 + α 01110 α29 α4 + α3 + α2 00111 α30 α4 + α2 + α + 1 11101 α31 = 1 Tabela 10 – Representação dos elementos de F25 gerados por p(x) = x5 + x2 + 1 Representação por Potência Representação Polinomial Vetor 0 0 00000 1 1 10000 α α 01000 α2 α2 00100 α3 α3 00010 Continuação na próxima página 26 Tabela 10 – Representação dos elementos de F25 Representação por Potência Representação Polinomial Vetor α4 α4 00001 α5 α2 + 1 10100 α6 α3 + α 01010 α7 α4 + α2 00101 α8 α3 + α2 + 1 10110 α9 α4 + α3 + α 01011 α10 α4 + 1 10001 α11 α2 + α + 1 11100 α12 α3 + α2 + α 01110 α13 α4 + α3 + α2 00111 α14 α4 + α3 + α2 + 1 10111 α15 α4 + α3 + α2 + α + 1 11111 α16 α4 + α3 + α + 1 11011 α17 α4 + α + 1 11001 α18 α + 1 11000 α19 α2 + α 01100 α20 α3 + α2 00110 α21 α4 + α3 00011 α22 α4 + α2 + 1 10101 α23 α3 + α2 + α + 1 11110 α24 α4 + α3 + α2 + α 01111 α25 α4 + α3 + 1 10011 α26 α4 + α2 + α + 1 11101 α27 α3 + α + 1 11010 α28 α4 + α2 + α 01101 α29 α3 + 1 10010 α30 α4 + α 01001 α31 = 1 Tabela 11 – Representação dos elementos de F26 gerados por p(x) = x6 + x4 + x3 + x+ 1 Representação por Potência Representação Polinomial Vetor 0 0 000000 1 1 100000 α α 010000 α2 α2 001000 Continuação na próxima página 27 Tabela 11 – Representação dos elementos de F26 Representação por Potência Representação Polinomial Vetor α3 α3 000100 α4 α4 000010 α5 α5 000001 α6 α4 + α3 + α + 1 110110 α7 α5 + α4 + α2 + α 011011 α8 α5 + α4 + α2 + α + 1 111011 α9 α5 + α4 + α2 + 1 101011 α10 α5 + α4 + 1 100011 α11 α5 + α4 + α3 + 1 101011 α12 α5 + α3 + 1 100101 α13 α3 + 1 100100 α14 α4 + α 010010 α15 α5 + α2 001001 α16 α4 + α + 1 110010 α17 α5 + α2 + α 011001 α18 α4 + α2 + α + 1 111010 α19 α5 + α3 + α2 + α 011101 α20 α2 + α + 1 111000 α21 α3 + α2 + α 011100 α22 α4 + α3 + α2 001110 α23 α5 + α4 + α3 000111 α24 α5 + α3 + α + 1 110101 α25 α3 + α2 + 1 101100 α26 α4 + α3 + α 010110 α27 α5 + α4 + α2 001011 α28 α5 + α4 + α + 1 110011 α29 α5 + α4 + α3 + α2 + 1 101111 α30 α5 + 1 000000 α31 α4 + α3 + 1 100110 α32 α5 + α4 + α 010011 α33 α5 + α4 + α3 + α2 + α + 1 111111 α34 α5 + α2 + 1 101001 α35 α4 + 1 100010 α36 α5 + α 010001 α37 α4 + α3 + α2 + α + 1 111110 α38 α5 + α4 + α3 + α2 + α 011111 α39 α5 + α2 + α + 1 111001 α40 α4 + α2 + 1 101010 Continuação na próxima página 28 Tabela 11 – Representação dos elementos de F26 Representação por Potência Representação Polinomial Vetor α41 α5 + α3 + α 010101 α42 α3 + α2 + α + 1 111100 α43 α4 + α3 + α2 + α 011110 α44 α5 + α4 + α3 + α2 001111 α45 α5 + α + 1 110001 α46 α4 + α3 + α2 + 1 101110 α47 α5 + α4 + α3 + α 010111 α48 α5 + α3 + α2 + α + 1 111101 α49 α2 + 1 101000 α50 α3 + α 010100 α51 α4 + α2 001010 α52 α5 + α3 000101 α53 α3 + α + 1 110100 α54 α4 + α2 + α 011010 α55 α5 + α3 + α2 001101 α56 α + 1 110000 α57 α2 + α 011000 α58 α3 + α2 001100 α59 α4 + α3 000110 α60 α5 + α4 000011 α61 α5 + α4 + α3 + α + 1 110111 α62 α5 + α3 + α2 + 1 101101 α63 = 1 2.1.5 Logaritmo de Zech Um outro conceito que será utilizado neste trabalho é o de logaritmo de Zech, que será definido a seguir. No Capítulo 4, será apresentado um algoritmo de decodificação de códigos matriciais MDS, e esse logaritmo auxiliará nas manipulações em cálculos fundamentais para o algoritmo. Um estudo mais aprofundado sobre este logaritmo pode ser encontrado em [HUBER 1990]. Definição 2.1.16 Seja α um elemento primitivo de um corpo finito Fq, do qual q = pb. Para Fq = {0, 1, . . . , q − 2} ∪ {−∞} o logaritmo de Zech de n em relação à base α é definida pela equação Z(n) = logα(1 + αn) ⇐⇒ αZ(n) = 1 + αn, (2.11) o qual o resultado do logaritmo é limitado ao corpo. 29 A adição de potências de um elemento primitivo α pode ser realizada da maneira como foi apresentada no Exemplo 2.1.7, mas, alternativamente, pode-se utilizar o logaritmo de Zech para realizar esta operação. Sejam αx e αy elementos primitivos de Fq. Se z é o expoente da soma αx + αy, isto é, αx + αy = αz, então z = x+ Z(y − x) = y + Z(x− y). (2.12) A seguir, apresentamos algumas propriedades do logaritmo de Zech em um corpo finito Fq. 1. Z(q − 1− x) = Z(x)− x (mod q − 1), x 6= −∞; 2. Z(px) = p · Z(x) (mod q − 1); 3. Z(0) = −∞, para p = 2; 4. Z ( q−1 2 ) = −∞, para p 6= 2; 5. Z(−∞) = 0, para todos os primos. Para uma melhor ilustração do logaritmo de Zech, evidencia-se um exemplo. Exemplo 2.1.9 Seja α ∈ F23 uma raiz do polinômio primitivo p(x) = x3 + x2 + 1, contido na Tabela 7, tem-se que α3 + α2 + 1 = 0. Assim, obtém-se a Tabela 12 Tabela 12 – Representação dos elementos de F23 gerados por p(x) = x3 + x2 + 1 Representação por Potência Representação Polinomial 0 0 1 1 α α α2 α2 α3 1 + α2 α4 1 + α + α2 α5 1 + α α6 α + α2 α7 1 Através da Equação (2.11), obtém-se os logaritmos de Zech que são apresentados na Tabela 13 a seguir. 30 Tabela 13 – Representação dos logaritmos de Zech Logaritmo de Zech Z(−∞) = 0 Z(0) = −∞ Z(1) = 5 Z(2) = 3 Z(3) = 2 Z(4) = 6 Z(5) = 1 Z(6) = 4 Exemplificando para n = 4, temos αZ(4) = 1 + α4 = 1 + 1 + α + α2 = α + α2 = α6 =⇒ Z(4) = 6 2.2 MATRIZES SUPERREGULARES Nesta seção apresentamos o conceito de matrizes superregulares, em especial duas famílias desta classe de matrizes, as matriz de Vandermonde e as de Cauchy. As matrizes superregulares desempe- nham grande importância na construção dos códigos matriciais MDS que serão apresentados neste trabalho. Os conceitos apresentados nesta seção podem ser encontrados em [CARDELL, CLIMENT e REQUENA 2013, LACAN e FIMES 2003, ROTH e LEMPEL 1989, HUFFMAN e PLESS 2003, FIE- DLER 2010]. Definição 2.2.1 Uma matriz retangular A com elementos em um corpo finito Fq é chamada de matriz superregular se toda submatriz de A não for singular, ou seja, possuir todos os subdeterminantes diferentes de zero. Exemplo 2.2.1 Seja α ∈ F23 um elemento primitivo do polinômio primitivo p(x) = x3 + x2 + 1 ∈ F2[x] tal que α3 + α2 + 1 = 0, como mostrado no Exemplo 2.1.9. É possível verificar que a matriz A = [ 1 α α4 α2 ] é uma matriz superregular, uma vez que o seu determinante é dado por α2 − α5 = α4 6= 0, onde os cálculos foram realizados de acordo com a Tabela 12. A seguir, é apresentado um exemplo de uma matriz 4× 4, em que será necessário realizar o cálculo de nove determinantes para comprovar que é uma matriz superregular. 31 Exemplo 2.2.2 Seja o polinômio primitivo p(x) = x4 + x3 + 1 ∈ F2[x], apresentado na Tabela 7, e seja α ∈ F24 um elemento primitivo tal que α4 + α3 + 1 = 0 . Vamos mostrar que a matriz A =  α7 α2 α12 1 α α3 α4 α2 α11 α5 α2 α6 α7 α3 α6 α  , é uma matriz superregular. De fato, com o auxílio da Tabela 8 é possível obter os seguintes determi- nantes ∣∣∣∣∣ α7 α2 α α3 ∣∣∣∣∣ = α10 − α3 = α; ∣∣∣∣∣ α2 α12 α3 α4 ∣∣∣∣∣ = α6 − α15 = α8; ∣∣∣∣∣ α12 1 α4 α2 ∣∣∣∣∣ = α14 − α4 = α9; ∣∣∣∣∣ α α3 α11 α5 ∣∣∣∣∣ = α6 − α14 = α12; ∣∣∣∣∣ α3 α4 α5 α2 ∣∣∣∣∣ = α5 − α9 = α8; ∣∣∣∣∣ α4 α2 α2 α6 ∣∣∣∣∣ = α10 − α4 = α12; ∣∣∣∣∣ α11 α5 α7 α3 ∣∣∣∣∣ = α14 − α12 = α6; ∣∣∣∣∣ α5 α2 α3 α6 ∣∣∣∣∣ = α11 − α5 = α13; ∣∣∣∣∣ α2 α6 α6 α ∣∣∣∣∣ = α3 − α12 = α5. Como podemos observar no Exemplo 2.2.2, quando aumentamos a dimensão, as matrizes superre- gulares não são fáceis de se obterem, pois a quantidade de subdeterminantes que é preciso calcular para mostrar que a matriz é superregular aumenta consideravelmente. A seguir apresentamos duas construções de famílias de matrizes que possuem a propriedade de serem superregulares: as matrizes de Vandermonde e as matrizes de Cauchy. 2.2.1 Matriz de Vandermonde Definição 2.2.2 Uma matriz A é dita matriz de Vandermonde se todas as suas linhas estiverem em progressão geométrica. Sejam α1, ..., αn−k elementos não nulos de um corpo e sendoA uma matriz de dimensões (n−k)×k, 32 a forma geral de uma matriz de Vandermonde é definida por A =  1 1 ... 1 α1 α2 ... αn−k α2 1 α2 2 ... α2 n−k α3 1 α3 2 ... α3 n−k ... ... . . . ... αk−11 αk−12 ... αk−1n−k  . (2.13) A transposta de uma matriz de Vandermonde também é uma matriz de Vandermonde. Lema 2.2.1 Se A uma matriz de Vandermonde, então det A = ∏ 1≤i k. Figura 3 – Palavra-código fonte: Próprio Autor. Definição 3.1.1 Seja Fq um corpo finito com q elementos. Dizemos que C é um código de bloco linear de comprimento n e dimensão k sobre Fq se C é um subespaço vetorial de dimensão k de Fnq . Um código de bloco linear C é identificado pelos parâmetros [n, k]. Se c ∈ C, então c é chamada de uma palavra-código de C. A quantidade de palavras-código de um código com parâmetros [n, k] é qk. Se q = 2, este código é denominado como código binário, se q = 3 é um código ternário, e de um modo geral, para q um inteiro positivo qualquer tem-se um código q-ário. Exemplo 3.1.1 Seja C um código de bloco linear em F4 2 sobre F2 com parâmetros [4, 2] dado pelas palavras-código C = {0000, 1001, 0110, 1111}. Este código possui palavras-código com comprimento 35 n = 4 e dimensão k = 2, pois o código fonte, ou seja, a representação da informação em símbolos binários, possui dois bits de informação e foi codificado a partir dos vetores β = {1001, 1111}. Definição 3.1.2 Dados u = [u1, ..., un] e v = [v1, ..., vn] ∈ Fnq definimos a distância de Hamming d(u, v) entre u e v como o número de símbolos q-ários que se diferem estando na mesma posição. Definição 3.1.3 Seja C um código de bloco linear. A distância mínima de Hamming é definida como d = min{d(u, v); u, v ∈ C e u 6= v} Exemplo 3.1.2 Seja o código de bloco linear C = {0000, 1001, 0110, 1111} sobre F4 2. Assim, d(0000, 1001) = 2; d(0000, 0110) = 2; d(0000, 1111) = 4; d(1001, 0110) = 4; d(1001, 1111) = 2; d(0110, 1111) = 2. Logo, a distância mínima de Hamming deste código é d = 2. Propriedade 3.1.1 Dados três vetores u,v e w ∈ C, valem as seguintes propriedades: 1. Positividade: d(u, v) ≥ 0, valendo a igualdade se, e somente se, u = v. 2. Simetria: d(u, v) = d(v,u). 3. Desigualdade Triangular: d(u, v) ≤ d(u,w) + d(w, v). Definição 3.1.4 O peso de Hamming w(v) de um vetor é o número de coordenadas não nulas de v. O peso mínimo de Hamming w(C) de um código C é o menor peso das palavras-código. Exemplo 3.1.3 No código do exemplo anterior C = {0000, 0110, 1001, 1111} temos, w(0110) = 2; w(1001) = 2; w(1111) = 4. Logo, o peso mínimo deste código é w(C) = 2. Observe que pelos Exemplos 3.1.2 e 3.1.3, tem-se que a distância e o peso são iguais, d = w(C) = 2, isso ocorre, pois um código de bloco linear C segue o resultado. Teorema 3.1.1 Seja C um código linear e u, v ∈ C. Então, 36 1. d(u, v) = w(u− v); 2. d = w(C). Conhecendo a distância mínima d de um código de bloco linear, tal código C pode ser denotado pelos parâmetros [n, k, d]. Teorema 3.1.2 Um código de bloco de linear C com parâmetros dados por [n, k, d] possui capacidade de detectar (d− 1) erros e corrigir até bd−1 2 c. Definição 3.1.5 Seja Fq um corpo finito e C ⊂ Fnq um código de bloco linear com parâmetros [n, k, d] e qk palavras-código. Seja β = {g1, ..., gk} uma base de C e considere G a matriz cujas linhas são os vetores gi = {gi1, ..., gin}, i=1,...,k, ou seja, G =  g1 ... gk  =  g11 ... g1n ... . . . ... gk1 ... gkn  . (3.1) A matriz G é chamada de matriz geradora do código C. Exemplo 3.1.4 Como visto no Exemplo 3.1.1, β = {0110, 1001} forma uma base para o código linear C = {0000, 0110, 1001, 1111}. Assim, G = [ 0110 1001 ] , é a matriz geradora do código de bloco linear C. A codificação dos códigos de bloco lineares é realizada utilizando as matrizes geradoras da seguinte forma. Considere uma matriz G, k × n, cujas linhas são vetores linearmente independentes. Pode-se definir um código como a imagem da transformação linear f : Fkq −→ Fkq u 7−→ u ·G, (3.2) do qual f refere-se a forma como codificar as palavras. Seja u = [u0, u1, . . . , uk] ∈ Fkq a mensagem a ser codificada. A palavra-código, denotada por c, é designada por c = [c0, c1, . . . , cn−1] ∈ C ∈ Fnq e pode ser calculada através da Equação 3.3 c = u ·G, (3.3) da qual G é a matriz geradora do código C. Neste caso, u é considerado como a codificação de fonte e c como a codificação de canal. 37 Exemplo 3.1.5 Considere o problema trivial de um robô que deseja se movimentar nas direções norte, sul, leste e oeste. Uma codificação de fonte para este problema é: Norte −→ 10, Sul −→ 11, Leste −→ 00, Oeste −→ 01. Para a codificação de canal, considere a transformação linear f : F2 2 −→ F5 2 u 7−→ u ·G, onde G = [ 1 0 1 1 0 0 1 0 1 1 ] . Assim, [00] · [ 1 0 1 1 0 0 1 0 1 1 ] = [00000]; [01] · [ 1 0 1 1 0 0 1 0 1 1 ] = [01011]; [10] · [ 1 0 1 1 0 0 1 0 1 1 ] = [10110]; [11] · [ 1 0 1 1 0 0 1 0 1 1 ] = [11101]. Logo, C = {00000, 10110, 11101, 01011} é o código de bloco linear com parâmetros [5, 2, 3] para o problema. Exemplo 3.1.6 Seja C um código de bloco linear com parâmetros [5, 3] sobre F5 2. Para realizar a codificação, primeiramente é preciso construir a matriz geradora para este código. De acordo com o parâmetro estabelecido, a mensagem a ser codificada terá k = 3 bits de informação e após a codificação passará a ter n = 5 bits, resultando em 2 novos bits de paridade. Logo, a matriz geradora deverá ter 3 linhas e 5 colunas, com dimensão 3 × 5. Para tal, escolhe-se 3 vetores linearmente independente dentre os 25 vetores de F5 2 e constrói-se a matriz geradora G =  1 0 1 0 1 1 1 0 1 0 1 1 1 1 1  . 38 Suponha que deseja-se codificar a mensagem u = [101], para isto realiza-se o produto entre u e a matriz geradora obtendo-se c = [01010], como segue c = [101] ·  1 0 1 0 1 1 1 0 1 0 1 1 1 1 1  = 01010. Agora, suponha que que recebe-se v = [01111] e deseja-se decodificá-la, isto é, achar a palavra u de F3 2 da qual ela se origina. Para isto, precisa-se encontrar u tal que u ·G = [01111]. Então [u1 u2 u3] ·  1 0 1 0 1 1 1 0 1 0 1 1 1 1 1  = [01111], ou seja,  u1 + u2 + u3 = 0 u2 + u3 = 1 u1 + u3 = 1 u2 + u3 = 1 u1 + u3 = 1 obtendo-se a mensagem u = [110]. Definição 3.1.6 Diz-se que uma matriz geradora G de um código C está na forma padrão, ou sistemá- tica, se G = [Ik|P ], (3.4) em que Ik é uma matriz identidade de ordem k e P é uma matriz de ordem k × (n− k). Teorema 3.1.3 Dado um código C, existe um código C ′ com matriz geradora na forma padrão, com mesmo parâmetros de C. Assim, sabendo que a codificação foi realizada utilizando uma matriz geradora na sua forma padrão como em (3.4), é possível distinguir a mensagem enviada, uma vez que, ao estar nessa forma, a mensagem é alocada no início da palavra-código. Exemplo 3.1.7 Seja G uma matriz geradora de um código de bloco linear C sobre F5 2 dada como segue G =  1 0 0 1 1 1 1 0 0 0 1 1 1 0 1  . 39 É possível, através de G, obter-se uma matriz G′ na forma sistemática, apenas realizando operações entre suas linhas, como, por exemplo, somando-se a linha 2 à terceira linha e a linha 1 à segunda linha, obtendo-se G′ =  1 0 0 0 0 0 1 0 1 1 0 0 1 0 1  , que é a matriz geradora na forma padrão de um código de bloco linear C ′ equivalente, ou seja, com mesmos parâmetros. Se recebesse, por exemplo, a palavra-código [10101], sabemos que [101] foi enviada e o 01 ao final é a redundância. A partir de uma matriz geradora escrita na forma padrão, é possível definir uma matriz chamada de matriz controle de paridade que será fundamental no estudo da decodificação. Definição 3.1.7 Seja C um [n, k] código de bloco linear. Se G = [Ik|P ] é a matriz geradora de C na forma sistemática, então H = [−P t|In−k] (3.5) é a matriz controle de paridade de C, onde P t é a matriz transposta de P de ordem (n− k)× k. A matriz H é utilizada para decidir se uma palavra pertence ou não ao código. Como G ·H t = [Ik|P ] · [−P t|In−k] = −P + P = 0, (3.6) então c ·H t = 0, (3.7) para todo c ⊂ C. As linhas da matriz de verificação de paridade H são linearmente independentes, bem como a matriz geradoraG, portantoH é a matriz geradora de algum código, chamado de código dual denotado por C⊥. Proposição 3.1.1 Se G é a matriz geradora de um código de bloco linear C, então H é a matriz geradora do código dual C⊥. Teorema 3.1.4 Seja C um código linear com parâmetros [n, k, d], então 1. O código dual C⊥ tem comprimento n, dimensão n− k e distância mínima d⊥, ou seja, o código C⊥ possui parâmetros [n, n− k]; 2. A matriz geradora de C é a matriz verificação de paridade de C⊥, assim, a matriz verificação de paridade de C é a matriz geradora de C⊥; 3. C = (C⊥)⊥. Exemplo 3.1.8 Seja o código de bloco linear binário [7, 4] com matriz geradora 40 G =  1 0 0 0 1 1 1 0 1 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 0  . Uma vez que a matriz geradora deste código já esta na forma padrão como em (3.4) segue que a matriz controle de paridade será dada por H =  1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 1 0 0 0 1  . E, sejam os vetores v = [1100010] e v′ = [1010101]. Temos, v ·H t = [1100010] ·  1 1 1 1 0 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 1  = [000], v’ ·H t = [1010101] ·  1 1 1 1 0 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 1  = [011]. Logo, v ∈ C pois este resultou no vetor nulo e v’ /∈ C. Até o momento, foi estudado como realiza-se a codificação de uma mensagem que deseja-se trans- mitir, além de recuperá-la ao ser entregue ao destinatário, processo denominado como decodificação. Decodificação é o procedimento de detecção e correção de erros num determinado código, [VILLELA 2008]. Para entender como a correção de um erro é realizada, a seguir é definido o vetor erro. Definição 3.1.8 Seja C um código de bloco linear [n, k, d] com matriz controle de paridade H . Seja o vetor transmitido c ∈ C e v o vetor recebido após passar por um canal ruidoso. Então, o vetor erro ao se enviar c e receber v é dado por e = v− c. (3.8) Exemplo 3.1.9 Em um certo código de bloco linear C ∈ F2 se transmite a palavra c = [101101] e recebe a palavra v = [101011]. Então o erro ocorrido na transmissão é e = v− c = [101011]− [101101] = [000110]. 41 Note que o peso do vetor erro, ou seja, a quantidade de elementos não nulos, corresponde ao número de erros cometidos durante a transmissão da mensagem. Se H é a matriz verificação de paridade de um código de bloco linear C, e ·H t = (v− c) ·H t = v ·H t − c ·H t = v ·H t, (3.9) pois c ·H t = 0. É possível verificar se tal informação recebida pertence ao código através do produto entre v e H t, o qual denomina-se síndrome s = v ·H t. (3.10) Para conseguir realizar a correção do vetor recebido, é necessário que se encontre exatamente a posição onde este erro ocorreu. Seja C um código de bloco linear com distância mínima d ≥ 3 e seja e o vetor introduzido entre as palavras transmitidas c e recebida v. Se e ·H t = 0, (3.11) então v ∈ C e então tem-se que a mensagem recebida é pertencente ao código, ou seja, c = v. Se e ·H t 6= 0, (3.12) e houve apenas um erro, então e = [0, . . . , α, . . . , 0], (3.13) com α 6= 0 na i-ésima posição. Assim, e ·H t = α · hi, (3.14) do qual hi é a i-ésima coluna de H . Para o vetor recebido fazemos v ·H t = α · hi, (3.15) e então consideramos o vetor erro e como o vetor com todas as componentes nulas exceto a i-ésima que é α. Exemplo 3.1.10 Seja C um código de bloco linear [5, 2] com matriz verificação de paridade dada por H =  1 1 1 0 0 0 1 0 1 0 1 0 0 0 1  . Se v = [11001] é uma palavra recebida, então 42 s = v ·H t = [11001]  1 0 1 1 1 0 1 0 0 0 1 0 0 0 1  = [010] = 1 · h4. Logo, e = [00010] e, c= v - e= [10100] - [00010]= [10110]. A seguir, será enunciado o algoritmo decodificador para correção de um erro, para as definições e exemplificações tratadas até o presente momento. Algoritmo 3.1.1 Para decodificação e correção de 1 erro: Seja H a matriz verificação de paridade de um código C com d ≥ 3 e seja v um vetor recebido. 1. Calcular s = v ·H t; 2. Se s = 0, então a palavra recebida pertence ao código, e tem-se que v = c; 3. Se s 6= 0, verifique se existe s nas colunas de H; 4. Se existir i e α, tal que tem-se s = α · hi, do qual hi corresponde a uma coluna de H, então o erro é dado por e = [0, 0, . . . , α, . . . , 0] com α na i-ésima posição e as demais nulas, de modo que e tenha o mesmo tamanho do vetor recebido. Caso contrário, houve mais de um erro e o algoritmo para; 5. Corrija a palavra recebida através de c = v− e. Outra estratégia de decodificação que será tratada é a por classes laterais ou arranjo padrão. Esta técnica utiliza-se da decodificação por máxima verossimilhança, ou seja, corrige o vetor recebido v para a palavra-código c em que a distância é a menor possível, assim sendo, são próximas uma da outra. Definição 3.1.9 Seja C um código de bloco linear [n, k, d]. Para um vetor qualquer v ⊂ F n q , o conjunto v + c = {v + c | c ∈ C}, (3.16) é chamado de classe lateral de v. Exemplo 3.1.11 Considere o código de bloco linear C = {0000, 1011, 0101, 1110}. Tomando o vetor v = [1000] ∈ F4 2, obtemos a classe lateral, v + C = {1000, 0011, 1101, 0110}. O interesse nas classes laterais é porque todos os vetores dessa classe possuem a mesma síndrome. Observe que v ∈ v + C e chamamos v de líder da classe lateral. 43 Exemplo 3.1.12 Seja a matriz G geradora de um código de bloco linear C ⊂ F5 2 G = [ 1 0 1 1 0 1 0 1 ] . A matriz H controle de paridade para este código é H = [ 1 0 1 0 1 1 0 1 ] . Assim, as síndromes para v + C são [1000] ·  1 1 0 1 1 0 0 1  = [11], [0011] ·  1 1 0 1 1 0 0 1  = [11], [1101] ·  1 1 0 1 1 0 0 1  = [11], [0110] ·  1 1 0 1 1 0 0 1  = [11]. A partir desta propriedade, para a decodificação, basta calcular as síndromes de todos os líderes das classes laterais e então quando uma palavra for recebida basta calcular sua síndrome e comparar com uma tabela formada pelas síndromes dos líderes. A quantidade de síndromes e de líderes das classes laterais são dados por qn−k, (3.17) para um código C ∈ Fnq com parâmetros [n, k, d]. Exemplo 3.1.13 Seja a matriz verificação de paridade de um código de bloco linear C ⊂ F5 2 H =  1 1 1 0 0 1 0 0 1 0 1 1 0 0 1  . Para obter a tabela basta calcular a síndrome para cada líder, ou seja [00001] ·  1 1 1 1 0 1 1 0 0 0 1 0 0 0 1  = [001], [00010] ·  1 1 1 1 0 1 1 0 0 0 1 0 0 0 1  = [010], 44 [00100] ·  1 1 1 1 0 1 1 0 0 0 1 0 0 0 1  = [100], [01000] ·  1 1 1 1 0 1 1 0 0 0 1 0 0 0 1  = [101], [10000] ·  1 1 1 1 0 1 1 0 0 0 1 0 0 0 1  = [111], [00011] ·  1 1 1 1 0 1 1 0 0 0 1 0 0 0 1  = [011], [00110] ·  1 1 1 1 0 1 1 0 0 0 1 0 0 0 1  = [110]. Sendo assim, obtemos a Tabela 14. Tabela 14 – Síndrome de erros da classe lateral. Líder Síndrome 00000 000 00001 001 00010 010 00100 100 01000 101 10000 111 00011 011 00110 110 Agora, suponha que foi recebido v = [10011]. Então, v ·H t = [10010] ·  1 1 1 1 0 1 1 0 0 0 1 0 0 0 1  = [101]. Tomamos o erro como sendo o líder da classe com esta síndrome, ou seja, e = [01000]. 45 Logo, a palavra transmitida foi c = v− e = [10010]− [01000] = [11010]. A seguir é apresentado o algoritmo para a decodificação baseada em classe lateral. Algoritmo 3.1.2 Decodificação baseado em Classe Lateral: 1. Dada a matriz verificação de paridade, construa a tabela de síndrome referente ao líder da classe lateral. A tabela deve conter todas as qn−k possibilidades de síndrome; 2. Calcule s = v ·H t; 3. Busque na tabela das síndromes a obtida no passo anterior; 4. Faça e ser o líder da classe lateral; 5. Corrija a palavra recebida c = v− e. 3.1.1 Códigos de Máxima Distância de Separação (MDS) Nesta seção apresentamos os códigos de máxima distância de separação (MDS - Maximum Distance Separable), que são códigos em que a distância mínima é a máxima possível. Tal característica é importante pois na teoria da codificação a distância mínima está relacionada com a capacidade de correção de erros do código. Dessa forma, códigos com esta propriedade fornecem proteção máxima contra falhas de um dispositivo, para uma dada quantidade de redundância. Os conceitos, definições e exemplificação aqui abordados são encontrados em [ROMAN 1992,ROTH 2006,HUFFMAN e PLESS 2003]. Seja C um código de bloco linear de parâmetros [n, k, d]. Foi visto que qk representa o número de palavras-código em um código sobre Fnq . Pela Definição 3.1.3 tem-se que a distância mínima de um conjunto C de palavras de código de comprimento n é definido como d = min{d(u, v); u, v ∈ C e u 6= v}, (3.18) do qual d(u, v) é a distância de Hamming entre dois vetores de informação u e v. Nestas condições, a seguir é apresentado um limitante sobre o tamanho de códigos de bloco lineares C de comprimento n, dimensão k e distância mínima d conhecido como limitante de Singleton. Teorema 3.1.5 (Limitante de Singleton). Seja C um código de bloco linear de parâmetros [n, k, d] sobre um corpo finito Fq com q elementos. Para d ≤ n, tem-se que qk ≤ qn−d+1. (3.19) A partir da Equação 3.19 obtém-se k ≤ n− d+ 1 46 ou equivalentemente, d ≤ n− k + 1. (3.20) Definição 3.1.10 Um código de bloco linear C para o qual a igualdade é mantida no Limitante de Singleton é chamado de distância máxima separável, MDS. Ou equivalentemente, um código em que a igualdade em (3.20) é satisfeita. Nenhum código de bloco linear com comprimento [n, k] tem distância mínima maior que um código MDS com os mesmos parâmetros. O resultado a seguir apresenta algumas equivalências para mostrar que um código de bloco linear é MDS. Teorema 3.1.6 Seja C um código de bloco linear [n, k] sobre Fq, com k ≥ 1. Então, são equivalentes: 1. C é um código MDS. 2. Cada conjunto de coordenadas k é um conjunto de informações para C. 3. Se uma matriz geradora para C estiver na forma padrão G = [I|A], então toda submatriz quadrada de A é não singular. 4. C⊥ é um código MDS. 5. Cada conjunto de coordenadas n− k é um conjunto de informações para C⊥. No Capítulo 4, as equivalências 1. e 3. do Teorema 3.1.6 serão utilizadas para a construção de códigos matriciais MDS que é apresentada neste trabalho. A seguir, apresentamos e exemplificamos alguns casos em que C é um código MDS trivial sobre Fq: 1. C = Fnq é um código MDS trivial com distância mínima d = 1. Exemplo 3.1.14 Considere o espaço vetorial F3 2. Para C = F3 2, os elementos desse código são C = {000, 001, 010, 011, 100, 101, 110, 111}. Nesse caso, a distância mínima desse código é d = 1. 2. Códigos que possuem apenas duas palavras-código, sendo elas a palavra toda nula e a palavra toda com 1’s, são códigos MDS triviais, tendo a distância mínima d = n. Exemplo 3.1.15 Seja o código de bloco linear C ⊂ F3 2 de parâmetros [3, 1], também conhecido como código de repetição [3, 1]. As palavras-código de C são {000, 111}. Nesse caso, C é um código MDS trivial que possui distância mínima d = 3. Exemplo 3.1.16 Os códigos de Hamming formam uma classe de códigos lineares binários, do qual, para um inteiro r ≥ 2 existe um código de comprimento de bloco n = 2r − 1 e com dimensão k = 2r − r− 1, dado por [2r − 1, 2r − r− 1, 3] com distância mínima 3. Para o caso onde r = 2, tem-se um código MDS pois um código com parâmetros [3, 1, 3] recai no Exemplo 3.1.15. 47 3. Códigos com um único símbolo de paridade são códigos MDS triviais com distância mínima d = 2. Exemplo 3.1.17 Seja a transformação linear f : F2 2 −→ F3 2 com código de fonte dado por u = {00, 01, 10, 11}. Se G = [ 1 0 1 0 1 1 ] é uma matriz geradora então C = {000, 011, 101, 110} é um código MDS trivial. E, para este caso, tem-se d = 2. Um código C é dito um código MDS trivial sobre Fnq se, e somente se, C = Fnq . Analisando a matriz geradora, na forma padrão, como apresentado no item 3 do Teorema 3.1.6, é possível verificar o seguinte resultado sobre códigos binários. Teorema 3.1.7 Seja C um código binário [n, k, d]. 1. Se C é um código MDS, então C é trivial. 2. Se 3 ≤ d e 5 ≤ k, então k ≤ n− d− 1. 3.2 CÓDIGOS MATRICIAIS LINEARES Nesta seção apresentamos um estudo sobre uma subclasse dos códigos de bloco lineares, os códigos matriciais lineares. Tais códigos podem ser utilizados para correção de erros aleatórios ou para correção de erros em rajada (burst of errors), os quais serão definidos posteriormente, em uma dimensão e em duas dimensões. Os códigos matriciais possuem como principal característica a simplicidade e a flexibilidade. Além disso, por serem relativamente simples, possuem decodificação rápida e os principais campos de aplicação são em sistemas de comunicações e em sistemas de armazenamento, [GUIMARÃES 2003]. Vamos iniciar definindo uma rajada de erros de comprimento b. Definição 3.2.1 Um vetor erro e de comprimento n é chamado de erro em rajada de comprimento b se suas coordenadas não nulas são confinadas a b coordenadas consecutivas em e. Seja e = (0, 0, ..., 0, rajada b︷ ︸︸ ︷ 1, ∗, ..., ∗, 1, 0, ..., 0), (3.21) se a primeira entrada diferente de 0 da rajada estiver na coordenada i, dizemos que a rajada b começa na coordenada i e possui padrão de surto (bi = 1, bi+1, ..., bi+b−2, bi+b−1 = 1). Observação 3.2.1 Nem todas as posições em uma rajada são necessariamente um erro Exemplo 3.2.1 Seja o vetor erro e = [000011001100000] de comprimento n = 15, esse vetor é um erro em rajada de comprimento b = 6. 48 Um código é chamado de código corretor em rajada b se ele pode corrigir qualquer erro em rajada de comprimento máximo igual b, [BLAUM, FARRELL e TILBORG 1998]. Agora, seja um código de bloco linear C sobre Fnq , onde Fq é um corpo finito com q elementos, expresso através dos parâmetros [n, k, d], onde n é o comprimento do código, k é a dimensão e d é a distância mínima de Hamming, todos referidos por quantidade de símbolos q-ários. Se b > 0 um inteiro positivo tal que b divide k, podemos construir um código matricial linear sobre Fbq, com parâmetros [n′, k′, d′], do qual k′ = k b , n′ = n b e a distância mínima d′ é calculada considerando o código sobre Fbq, ou seja, nessas condições, temos um código parametrizado por quantidade de blocos de símbolos q-ários de comprimento b. Tais códigos podem ser especificados por sua matriz verificação de paridade H de dimensão (n′ − k′)b× n′b, gerando palavras-código de comprimento n′b, onde b torna-se o comprimento da rajada de erro. Observa-se que o limitante de Singleton apresentado no Teorema 3.1.5 continua válido para códigos matriciais lineares e, se a igualdade em (3.20) é alcançada, tem-se um código matricial linear MDS. A seguir apresentamos um exemplo genérico de códigos matriciais lineares, apenas para mostrar a sua relação com os códigos de bloco lineares. O Capítulo 4 será dedicado a apresentar uma estratégia de codificação e decodificação destes códigos que possuem a propriedade de ser MDS e que são capazes de corrigir erros em rajadas. Exemplo 3.2.2 Seja um código de bloco linear C sobre F2 com parâmetros [9, 3, 3], formado pe- las palavras-código C = {0000000000, 001000011, 010011010, 011011001, 100001101, 101001110, 110010111, 111010100}. Este código possui uma matriz geradora dada por, G =  1 0 0 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 1 1  . Como visto na Equação 3.5, a matriz verificação de paridade para este código é dada por H =  0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1  . Para um código matricial linear sobre F3 2, teríamos parâmetros [3, 1, 1]. Neste caso, a matriz ve- rificação de seria vista em blocos da seguinte forma como dado em (3.22), e assumiríamos as palavras-código na forma C = {000 000 000, 001 000 011, 010 011 010, 011 011 001, 100 001 101, 101 001 110, 110 010 111, 111 010 100}, com erros analisados em rajadas de comprimento b = 3. Porém, como a distância mínima considerando o código matricial é igual a 1, este código não é capaz 49 de detectar ou corrigir nenhuma rajada de erro de comprimento b = 3, H =  0 0 0 ... 1 0 0 ... 0 0 0 0 1 0 ... 0 1 0 ... 0 0 0 1 1 0 ... 0 0 1 ... 0 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0 0 ... 0 0 0 ... 1 0 0 0 1 1 ... 0 0 0 ... 0 1 0 1 0 1 ... 0 0 0 ... 0 0 1  . (3.22) A seguir, na Subseção 3.2.1 apresentamos os códigos matriciais de paridade de modo a exemplificar a correção de erros aleatórios e em rajada em códigos matriciais. 3.2.1 Códigos Matriciais de Paridade Os códigos matriciais de paridade podem ser obtidos de maneira unidimensional adicionando um único bit de paridade ao final do bloco de informação ou bidimensionais, construídos de diversas maneiras e formas, analisando a sua paridade, em linhas, colunas e diagonais. Para esta subseção as construções são realizadas em F2, abordando códigos matriciais binários. As principais referências utilizadas foram [BLAUM, FARRELL e TILBORG 1998, ROCHA, GUIMARÃES e FARRELL 2002, GUIMARÃES 2003]. Definição 3.2.2 Um código matricial de paridade A(n1, n2) consiste de todas matrizes n1 × n2 das quais todas as somas das linhas e todas as somas das colunas tem paridade par. Definição 3.2.3 Um código matricial de paridade unidimensional C com dígito único de paridade, é um código de bloco linear com parâmetros [n, n− 1, 2] = [k + 1, k, 2]. A dimensão k é definida da maneira usual, como o número de elementos de uma base, o com- primento n do código é o comprimento de suas palavras-código e d = 2 é a distância mínima de Hamming. Na Figura 4, esse código é exemplificado com o bit de paridade alocado na última posição do bloco de informação, onde usualmente são alocados, porém o dígito de paridade pode ser alocado em qualquer posição do bloco. Figura 4 – Código matricial unidimensional. fonte: Próprio Autor. 50 Seja u = [u0, u1, ..., un−2] uma mensagem a ser codificada. Então um bit simples de paridade v é adicionado para formar a palavra código c = [u0, u1, ..., un−2, v]. Este bit é simplesmente a soma módulo 2 dos n− 1 bits de informação, ou seja, v = u0 + u1 + ...+ un−2 (mod 2). (3.23) Exemplo 3.2.3 Um código matricial de paridade unidimensional C com parâmetros [4, 3] é um código em que as palavras-código são da forma c = [m0,m1,m2,m0 +m1 +m2]. Primeiramente, todas as combinações binárias para gerar este código são {000, 001, 010, 011, 100, 101, 110, 111}. Para cada uma dessas mensagens será adicionada uma paridade através da soma módulo 2 dos bits de informação, logo 0 + 0 + 0 = 0 −→ 0000; 1 + 0 + 0 = 1 −→ 1001; 0 + 0 + 1 = 1 −→ 0011; 1 + 0 + 1 = 0 −→ 1010; 0 + 1 + 0 = 1 −→ 0101; 1 + 1 + 0 = 0 −→ 1100; 0 + 1 + 1 = 0 −→ 0110; 1 + 1 + 1 = 1 −→ 1111. e portanto, C = {0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111}. Definição 3.2.4 Um código matricial de paridade bidimensional C nas linhas e colunas consiste na organização de um vetor informação em uma matriz, adicionando a ela paridades nas linhas e nas colunas. Como mostrado na Figura 5, este código pode ter formato quadrado ou retangular com parâmetros [n1n2, (n1−1)(n2−1), 4] = [(k1+1)(k2+1), k1k2, 4], podendo ser expresso também comoA(n1, n2), onde d = 4 é a distância mínima de Hamming do código. Figura 5 – Código matricial bidimensional. fonte: Próprio Autor. Para realizar a codificação destes códigos, primeiramente deve-se construir uma matriz de dimen- sões (n1− 1)× (n2− 1) com os bits de informação rearranjados. Posteriormente, é acrescentado tanto 51 uma nova coluna quanto uma nova linha a esta matriz, de maneira que ela fique com dimensões de n1 × n2. Nos códigos matriciais bidimensionais com dígitos de paridade nas linhas e nas colunas é adi- cionado ao final de cada linha e coluna a soma módulo dois dos bits de informação contidos nas respectivas linhas e colunas. Neste caso, as síndromes horizontal e vertical são dadas, respectivamente, por sh = n2−1∑ l=0 ai,l, para 0 ≤ i ≤ n1 − 1 (mod 2); (3.24) sv = n1−1∑ l=0 al,j , para 0 ≤ j ≤ n2 − 1 (mod 2). (3.25) Exemplo 3.2.4 Seja u = [1101] uma mensagem a ser codificada. Primeiramente deve-se organizá-la em uma matriz quadrada e adicionar suas paridades nas linhas e nas colunas, tornando-a uma palavra- código de um código matricial de paridade bidimensional de parâmetros [9, 4], ou equivalentemente, A(3, 3), como mostra a Figura 6. Figura 6 – Código matricial bidimensional A(3, 3). fonte: Próprio Autor. Exemplo 3.2.5 Agora, seja u = [1100110101] uma mensagem a ser codificada. Novamente deve-se organizá-la matricialmente em duas linhas adicionando suas paridades. Assim, tem-se um código matricial de paridade bidimensional A(3, 6), como mostrado na Figura 7. Figura 7 – Código matricial bidimensional A(3, 6). fonte: Próprio Autor. Em ambos os exemplos a capacidade de correção é de um erro, onde as correspondentes paridades de linha e coluna falham. Porém, é possível detectar dois ou até mesmo três erros, como será mostrado na decodificação de tais códigos. Outra maneira de realizar a codificação é através da adição dos bits de paridade nas diagonais. 52 Definição 3.2.5 SejaA(n, n−1) um código matricial de paridade bidimensional nas colunas. Um có- digo matricial de paridade diagonal é um códigoA(n, n), obtido a partir deA(n, n−1) adicionando as paridades na última coluna da matriz com a soma módulo 2 das diagonais. Exemplo 3.2.6 Seja u um vetor informação com 16 bits de informação, organizado em um código matricial bidimensional A(5, 4) com paridades na coluna. Para organizá-lo em um código matricial com paridades nas diagonais A(5, 5) basta realizar a soma módulo 2 de todas suas diagonais, mantendo a mesma quantidade de elementos na soma. Para o código da Figura Figura 8, as paridades diagonais são representadas pelos números 5, 10, 15, 20 e 25, e são obtidas da seguinte forma: • 5 é o dígito de paridade para 9, 13, 17 e 21; • 10 é o dígito de paridade para 1, 14, 18 e 22; • 15 é o dígito de paridade para 2, 6, 15, 19 e 23; • 20 é o dígito de paridade para 3, 7, 11, 20 e 24; • 25 é o dígito de paridade para 4, 8, 12 e 16. Figura 8 – Paridades diagonais para um código A(5, 5). fonte: Próprio Autor. Exemplo 3.2.7 Considerando um código C com parâmetros [25, 16], ou equivalentemente, A(5, 5), e a mensagem u = [1101001011001011] pertencente a este código. Primeiramente deve-se organizar a mensagem em uma matriz 4× 4 e adicionar a este os bits de paridade referente as colunas, ficando com dimensões 5× 4. Posteriormente, a última coluna é dedicada aos bits de paridade referente aos cálculos de paridades diagonais, como mostrado no Exemplo 3.2.6. Figura 9 – Exemplo de codificação para um código A(5, 5). fonte: Próprio Autor. 53 Até o momento introduzimos três tipo de codificação para códigos matriciais de paridade, sendo eles: codificação de códigos matriciais unidimensionais com adição de bit único de paridade, codifica- ção de códigos matriciais bidimensionais com adição de paridades nas linhas e colunas e codificação de códigos matriciais bidimensionais com paridades diagonais. A seguir apresentamos a decodificação para estes códigos, considerando a detecção e a correção dos erros aleatórios ou em rajada. Como visto, a codificação de um código unidimensional se dá através da adição de uma paridade, normalmente ao final do código para que este fique na forma sistemática, por meio da soma módulo 2 dos bits da mensagem. Ao receber a mensagem, é verificado se a paridade corresponde aos bits de informação. Este tipo de código pode detectar qualquer número ímpar de erros, porém não é capaz de saber a posição do erro para corrigi-lo. Exemplo 3.2.8 Considere uma mensagem u = [11100010]. Para codificá-la, deve ser adicionado um bit de paridade ao final da mensagem 1 + 1 + 1 + 0 + 0 + 0 + 1 + 0 = 0 (mód 2) obtendo uma palavra-código c = [111000100]. Imagine que o vetor recebido seja v = [111100100], ao verificar percebe-se que a paridade falha, logo teve um erro e a palavra recebida v não foi a palavra enviada. Agora, se a palavra recebida apresentar dois erros, como por exemplo v = [110001100], a paridade continua correta e não é possível verificar se houve erro, e assim acaba-se considerando v como a palavra enviada erroneamente. Já para códigos matriciais com paridade bidimensionais de parâmetros [n1n2, (n1−1)(n2−1), 4] = [(k1 + 1)(k2 + 1), k1k2, 4], ao receber a matriz código, é verificada cada linha e cada coluna para aferir se as paridades falham. Se não houve erro, a matriz recebida é aceita como a matriz enviada. Este tipo de código é capaz de detectar diversos erros, dependendo da dimensão da matriz, e corrigir um erro. A seguir é apresentado alguns exemplos para elucidar a detecção e correção. Exemplo 3.2.9 Considere a seguinte palavra-código do código matricial bidimensional [25, 16], ou equivalentemente, A(5, 5), apresentado na Figura 10. Figura 10 – Código matricial [25, 16]. fonte: Próprio Autor. 54 Figura 11 – Detecção de 1, 2 e 3 erros em códigos matriciais. (a) Detecção de 1 erro. (b) Detecção de 2 erros. (c) Detecção de 2 erros. fonte: Próprio Autor. As matrizes das Figuras 11a, 11b e 11c demonstram a detecção de 1, 2 e 3 erros, respectivamente. Observe que no caso de 1 erro, Figura 11a, as duas equações de paridade, de linha e coluna, falham e por isto torna-se possível localizá-lo e corrigi-lo. Já para o caso de 2 erros, Figura 11b é possível detectar que 4 paridades falham, e para 3 erros 6 paridades falham, Figura 11c, não sendo possível em ambos os casos localizá-los e corrigi-los. Independentemente da dimensão da matriz do código matricial de paridade bidimensional, é sempre possível detectar diversos erros através da verificação das paridades, porém a correção só é realizável quando se ocorreu apenas um erro que será definido a seguir. Os erros mais comuns ocorrem na forma aleatória, como podemos observar nos exemplos mostra- dos. Entretanto, em algumas aplicações, os erros podem ocorrer em grupos, [GUIMARÃES 2003], conhecidos como surtos de erros ou erros em rajadas. Os códigos matriciais bidimensionais com paridades diagonais, aqui apresentados, são códigos capazes de corrigir surtos de erros em linhas de comprimentos b ≤ j − 1, onde b é o comprimento do vetor do primeiro bit corrompido até o último e j é caracterizado como a quantidade de colunas do código. Para realizar a decodificação destes códigos é necessário realizar o cálculo das síndromes verticais e diagonais da matriz recebida, onde a vertical é expressa em (3.25) e a diagonal segue a mesma lógica da realizada na codificação. O vetor síndrome vertical sv, considerado o vetor das paridades das colunas, deve ser lido da esquerda para direita e o vetor síndrome diagonal sd, deve ser lido debaixo para cima. Calculadas as síndromes, o próximo passo é comparar os dois vetores. Caso eles sejam iguais, não se deve fazer nenhum deslocamento e somar o vetor síndrome vertical à primeira linha da matriz. Já quando os vetores síndromes se diferem, é realizado o deslocamento até que fiquem iguais e este deslocamento se refere a linha a ser corrigida. Para melhor elucidar este processo, a seguir apresentamos alguns exemplos. Exemplo 3.2.10 No Exemplo 3.2.7 foi realizada a codificação do código matricial através da adição da coluna referente aos bits de paridade diagonal. Suponha que um erro em rajada ocorre como mostra a Figura 12. 55 Figura 12 – Rajada de erro na primeira linha do código. fonte: Próprio Autor. O vetor síndrome vertical do código é sv = 11110, calculado através da soma módulo 2 de todas as colunas do código matricial. Já o vetor síndrome diagonal, lida debaixo para cima, é sd = 11110, calculado da mesma maneira que na codificação, porém, agora acrescentando os próprios bits de paridade diagonal. Como as duas síndromes são iguais, não se deve fazer nenhum deslocamento, assim para corrigi-lo deve-se somar sv a primeira linha do código 00101 + sv = 00101 + 11110 = 11011 (mod 2). Agora, suponha que o erro aconteceu na terceira linha como segue na Figura 13. Para este caso, as síndromes encontradas são sv = 11110 e sd = 11011. Para que as duas fiquem iguais, é necessário fazer um deslocamento cíclico de duas posições em sd. Logo, para realizar a correção, o mesmo deslocamento deve ser realizado nas linhas da matriz, indicando assim que a terceira linha está incorreta. Da mesma forma, para corrigi-la basta somar a síndrome vertical sv a terceira linha da matriz 00110 + sv = 00110 + 11110 = 11000 (mod 2). Figura 13 – Rajada de erro na terceira linha do código. fonte: Próprio Autor. A seguir, é apresentado um algoritmo sintetizando como a decodificação para estes códigos é realizada. Algoritmo 3.2.1 Para correção de uma rajada de erro em códigos matriciais com paridades digo- nais: 1. Calcular a síndrome vertical e a síndrome diagonal; 2. Verificar se são iguais, caso for, somar a síndrome vertical à primeira linha do código matricial. Caso contrário, vá para o próximo passo; 56 3. Caso as síndromes não forem iguais, fazer deslocamentos cíclicos na síndrome diagonal até que fiquem iguais e adicionar a síndrome vertical à linha equivalente ao número de deslocamento. Além de erros em rajadas dados por bits consecutivos, pode ocorrer de acontecer diversos erros em um código matricial de forma aleatória, e espalhada pelo código. A seguir, é apresentado um algoritmo capaz de corrigir tais erros. A capacidade de correção desses códigos é dado pelo Teorema 3.2.1. Teorema 3.2.1 [BLAUM, FARRELL e TILBORG 1998] O código A(n1, n2) tem a capacidade de correção de rajada b igual a n1 − 1 se, e somente se, n2 ≥ 2n1 − 3. Algoritmo 3.2.2 Decodificação de surtos de erros aleatórios: 1. Calcule a sh e a sv e encontre o peso w das síndromes. Se w = 0, a matriz recebida é a palavra-código. 2. Encontre a sequência de pelo menos n1 − 2 zeros consecutivos em sv. 3. Seja j0 a primeira coordenada diferente de zero depois da sequência de zeros encontrada em 2. Deixe j1, ..., jw−1 ser as subsequentes coordenadas diferentes de zero em sv. Posteriormente, 0 ≤ i0 < i1 < ... < iw−1 < n1 serão as coordenadas diferentes de zero em sh. 4. Corrija o código com as coordenadas da matriz encontrada em 3, da maneira (i0, j0), (i1, j1), . . ., (iw−1, jw−1). Na Figura 14 é mostrado um exemplo de como é alocado as coordenadas destes códigos. Figura 14 – Exemplo de coordenadas para código matricial. fonte: Próprio Autor. Exemplo 3.2.11 Considere um código matricial de dimensões A(5, 7) dado pela matriz na Figura 15. Figura 15 – Código matricial A(5, 7). fonte: Próprio Autor. 57 Para decodificá-la basta seguir os passos do Algoritmo 3.2.2: 1. A síndrome horizontal é sh = (01011), enquanto a síndrome vertical é sv = (1000110). Então, w = 3. 2. A sequência dada por n1 − 2 = 5− 2 = 3 zeros em sv começa na coordenada 1 e termina na coordenada 3. 3. Seguindo as coordenadas diferentes de zero em sv, começando na coordenada 4, temos j0 = 4, j1 = 5 e j2 = 0. De sh temos, i0 = 1, i1 = 3 e i2 = 4. 4. Os erros ocorreram nas coordenadas (1,4), (3,5) e (4,0). Assim, corrigindo os erros, temos: Figura 16 – Decodificação do código matricial A(5, 7). fonte: Próprio Autor. 58 4 CODIFICAÇÃO E DECODIFICAÇÃO DE CÓDIGOS MATRICIAIS MDS Neste capítulo apresentamos a codificação e decodificação dos códigos matriciais MDS. Na Seção 4.1 apresentamos a construção da matriz verificação de paridade de tais códigos, além de apresentar a matriz companheira de Frobenius que em conjunto com a matriz superregular, apresentada na Seção 2.2, são fundamentais para esta construção. Na Seção 4.2 apresentamos um algoritmo capaz de detectar e corrigir até duas rajadas de erros. Este algoritmo é uma generalização do algoritmo apresentado em [CARDELL, CLIMENT e REQUENA 2013]. E, por fim, na Seção 4.2.1, apresentamos a possibilidade de aumentar a capacidade de correção para três rajadas de erros, tendo como desafio para trabalhos futuros a estruturação de uma fórmula fechada para verificação das posições dos erros. 4.1 CODIFICAÇÃO Nesta seção apresentamos como é realizada a codificação dos códigos matriciais MDS. Para isso iniciamos definindo a matriz companheira de Frobenius e um isomorfismo que leva um elemento primitivo de um corpo finito em uma matriz companheira de Frobenius. Definição 4.1.1 Seja p(x) = xb+pb−1x b−1+ ...+p1x+p0 ∈ Fq[x] um polinômio primitivo. Podemos associar a p(x) uma matriz chamada matriz companheira de Frobenius (Frobenius companion matrix), que é uma matriz que contém 1’s (uns) na subdiagonal e a última coluna é dada em função dos coeficientes de p(x), sendo os demais elementos todos nulos, como segue C =  0 0 . . . 0 −p0 1 0 . . . 0 −p1 ... . . . . . . ... ... 0 0 . . . 0 −pb−2 0 0 . . . 1 −pb−1  . (4.1) Seja α ∈ Fqb um elemento primitivo do corpo finito Fqb , ou seja, raiz de um polinômio primitivo p(x) ∈ Fq[x]. Existe um isomorfismo φ : Fqb −→ Fq[C] definido por φ(α) = C. A seguir, ilustramos através de um exemplo o comportamento deste isomorfismo. Exemplo 4.1.1 Sejam {0, 1, α, α2, α3, α4, α5, . . . , α14} os elementos do corpo finito F24 obtidos atra- vés do polinômio primitivo p(x) = x4 + x3 + 1 ∈ F2, como no Exemplo 2.1.7. A matriz companheira de Frobenius gerada a partir deste polinômio é dada por C =  0 0 0 −p0 1 0 0 −p1 0 1 0 −p2 0 0 1 −p3  =  0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1  . (4.2) Assim, na Tabela 15, tem-se o isomorfismo φ : F24 −→ F2[C] definido por φ(α) = C. 59 Tabela 15 – Isomorfismo φ : F24 −→ F2[C] φ(α) 0 0 α0 = 1 I4 α C α2 C2 α3 C3 α4 C4 α5 C5 α6 C6 α7 C7 α8 C8 α9 C9 α10 C10 α11 C11 α12 C12 α13 C13 α14 C14 Da mesma forma, considerando Mm×n(Fq) o espaço das matrizes de ordem m× n com elementos no corpo finito Fq, podemos estender o isomorfismo dado acima, definindo o isomorfismo ψ : Mm×n(Fqb) −→ Mm×n(Fq[C]) ψ(A) 7−→ [φ(αij)] . (4.3) O comportamento de tal isomorfismo e ilustrado no exemplo a seguir. Exemplo 4.1.2 Considere o mesmo polinômio primitivo p(x) = x4 + x3 + 1 ∈ F2[x] do Exemplo 4.1.1, gerador da matriz companheira de Frobenius C, dada em (4.2). Seja A uma matriz formada por potências do elemento primitivo sobre F24 , como segue A =  α6 α3 α9 α2 α5 α4 α11 α7 α8  . Assim, para o isomorfismo ψ :M3×3(F24) −→M3×3(F2[C]), tem-se ψ(A) =  C6 C3 C9 C2 C5 C4 C11 C7 C8  . Seja C um código matricial linear sobre Fbq com parâmetros [n′, k′, d′], apresentado na Seção 3.2, por questões visuais, denotaremos por [n, k, d] representados por blocos de comprimento b. Se d 60 satisfaz a igualdade em (3.20), então C é um código matricial MDS. Nestas condições, o seguinte resultado fornece uma matriz controle de paridade para um código matricial linear sobre Fbq, que possui a propriedade de ser MDS, a partir de matrizes superregulares (Definição 2.2.1). Teorema 4.1.1 [CARDELL, CLIMENT e REQUENA 2013] Se A = [αij] ∈ M(n−k)×k(Fqb) é uma matriz superregular, então H = [ψ(A) | I(n−k)×b], onde ψ é o isomorfismo dado em (4.3), é uma matriz controle de paridade de um [n, k, n− k + 1] código matricial linear MDS C. Considere um código matricial MDS C sobre Fb2, com b um inteiro positivo, construído nas condições do Teorema 4.1.1. Os parâmetros deste código são [n, k, n− k + 1] = [m+ k, k,m+ 1], ou seja, m = n− k, e a sua matriz controle de paridade é dada por H =  A11 A12 . . . A1k A21 A22 . . . A2k ... ... . . . ... Imb Am1 Am2 . . . Amk  , (4.4) com Aij = Cσ(i,j), onde C ∈Mb×b(F2) é como em (4.1) e σ(i, j) é a potência de cada elemento (i, j) da matriz superregular A de dimensão m× k. Exemplo 4.1.3 Considere o polinômio primitivo p(x) = x3+x2+1 ∈ F2[x], como visto no Exemplo 2.1.9, e que deseja-se construir um código matricial MDS com parâmetros [4, 2, 3] sobre F23 , ou seja, m = k = 2. O primeiro passo para a construção da matriz verificação de paridade é encontrar a matriz companheira de Frobenius que é dada por C =  0 0 −p0 1 0 −p1 0 1 −p2  =  0 0 1 1 0 0 0 1 1  . Seja α ∈ F23 um elemento primitivo tal que α3+α2+1 = 0. A matriz superregular de Vandermonde com dimensão 2× 2 será dada como segue A = [ 1 1 α α2 ] . Assim, de acordo com (4.4), tem-se que a matriz verificação de paridade para este código é dada por H =  I3 I3 ... I6 C C2 ...  =  1 0 0 ... 1 0 0 ... 1 0 0 0 0 0 0 1 0 ... 0 1 0 ... 0 1 0 0 0 0 0 0 1 ... 0 0 1 ... 0 0 1 0 0 0 ... ... ... ... ... ... ... 0 0 1 ... 0 1 1 ... 0 0 0 1 0 0 1 0 0 ... 0 0 1 ... 0 0 0 0 1 0 0 1 1 ... 1 1 1 ... 0 0 0 0 0 1  . 61 4.2 DECODIFICAÇÃO Nesta seção apresentamos um algoritmo capaz de detectar e corrigir até duas rajadas de erros, sendo ele uma generalização do apresentado em [CARDELL, CLIMENT e REQUENA 2013]. Na referência, o algoritmo é utilizado para códigos com parâmetros dados por [4 + k, k, 5], limitando a distância mínima deste código em 5 e os blocos de símbolos de paridade em 4. Já o algoritmo proposto neste trabalho é válido para todo código matricial MDS com parâmetros [m+ k, k,m+ 1] para todo m ≥ 4 e m = n− k, permitindo a correção de até duas rajadas de erros de comprimento b. Observe que para m = 2 e 3 o código será capaz de corrigir até uma rajada de erro de comprimento b, pois a capacidade de correção de erros de um código linear é bd−1 2 c = bm 2 c. Seja C um código matricial MDS sobre Fb2 construído como na Seção 4.1 . Se c = [c1 c2 . . . cn] é uma palavra-código enviada e v = [v1 v2 . . . vn] um vetor recebido, então e = [e1 e2 . . . en] é o vetor erro, do qual e = v− c, onde agora tem-se que cj, vj, ej ∈ Fb2, para todo j = 1, . . . , n. A síndrome s de v é definida por sT = H · vT = [s1 s2 . . . sm], (4.5) em que si ∈ Fb2 e H é a matriz controle de paridade dada em (4.4). Assim, sTi pode ser calculada por sTi = k∑ j=1 AijvTj + n∑ j=k+1 vTj = k∑ j=1 AijeTj + n∑ j=k+1 eTj , (4.6) para cada i = 1, . . . ,m. A seguir serão apresentados dois algoritmos. Um deles capaz de corrigir apenas uma rajada de erro de comprimento b em um código matricial MDS C de Fb2 com parâmet