Uma matriz geradora é um conceito de teoria de código usado no caso de códigos lineares .
Corresponde à matriz do mapa linear de E o espaço vetorial das mensagens a serem comunicadas em F , o espaço vetorial contendo os códigos transmitidos.
A noção de matriz geradora tem tanto um interesse teórico no âmbito do estudo de códigos corretivos, por exemplo para definir a noção de código sistemático , como um interesse prático para uma implementação eficiente.
O objetivo de um código de correção é detectar ou corrigir erros após a transmissão de uma mensagem . Essa correção é possível adicionando informações redundantes. A mensagem é incorporada em um conjunto maior, a diferença de tamanho contém redundância, a imagem da mensagem pela incorporação é transmitida. Se a mensagem estiver corrompida, a redundância é projetada para detectar ou corrigir erros. Um exemplo simples é o do código de repetição , a mensagem é, por exemplo, enviada três vezes, a decodificação é feita por votação. Aqui, o conjunto maior tem dimensão tripla em relação à mensagem inicial.
Vamos relembrar os elementos básicos da formalização. Existe um conjunto E composto de sequências de valores em um alfabeto e de comprimento k , isto é, a partir do posto k , todos os valores da sequência são zero. Esses elementos são o espaço das mensagens que queremos comunicar. Para fornecer à mensagem a redundância desejada, existe um mapa injetivo φ de E com valores em F , o espaço de sequências de comprimento n com valores em um alfabeto. A função φ é chamada de codificação , φ ( E ) também notado C é chamado de código , um elemento de φ ( E ) palavra do código , n o comprimento do código ek a dimensão do código. Essas notações são usadas ao longo do artigo.
Um código linear tem uma estrutura algébrica mais rica do que a estrutura geral dos códigos corretivos. Os alfabetos A e A ' são identificados e fornecidos com uma estrutura de campo finita . O caso mais frequente consiste em escolher o campo F 2 ou uma de suas extensões finitas . Este corpo corresponde ao alfabeto binário cujas tabelas de adição e multiplicação são fornecidas abaixo:
|
|
Os conjuntos E e F são naturalmente dotados de uma estrutura de espaço vetorial de respectivas dimensões k e n . Se F d denota o corpo finito do cardinal d, onde d é uma potência de um número primo p , então o espaço vetorial F é geralmente identificado com F d n .
F é fornecido com uma distância que deriva do peso de Hamming . A distância entre dois pontos de F corresponde ao número de coordenadas diferentes de zero da diferença entre os dois pontos, na base canônica . Um código é descrito por três parâmetros, notados [ n , k , δ], n é o comprimento do código, k a dimensão do código e δ a distância mínima entre duas palavras do código. Essas notações são usadas no restante do artigo.
Finalmente, o mapa de codificação φ é escolhido linear , o código é, portanto, um subespaço vetorial .
Uma noção natural surge e dá origem à seguinte definição:
A seguinte igualdade é verificada naturalmente de acordo com as propriedades das matrizes:
Notamos que a dimensão da matriz geradora é n x k porque E é de dimensão k e F de dimensão n .
Os códigos de comprimento ne dimensão k no mesmo corpo finito têm exatamente as mesmas propriedades se suas matrizes geradoras forem equivalentes. Em particular, eles têm a mesma distância mínima. De fato, a imagem de φ, ou seja, o código permanece inalterado por qualquer permutação anterior no conjunto E , em particular por um automorfismo. Não é o mesmo para F , um automorfismo pode associar dois vetores a uma distância de Hamming de δ, dois vetores a uma distância de um, o que destruiria todas as propriedades do código.
Um código de repetição é um código que associa a mensagem m ... m a uma mensagem m de comprimento k . Se seu alfabeto for escolhido como sendo igual a um corpo finito, então o código é linear com uma matriz geradora G r igual a:
O checksum corresponde a um código de parâmetro [ k + 1, k , 2], com uma mensagem é associada a palavra do código igual à mensagem concatenada com a soma (com valor no corpo finito) de todas as letras da mensagem . Se o código for binário, isso equivale a associar um se a soma das letras for ímpar e zero caso contrário. No caso geral, sua matriz geradora G s e, usando as notações anteriores:
O código de Hamming (7,4) é um código de parâmetro binário [7,4,3]. A figura à direita é uma representação gráfica desse código. A mensagem é a palavra d 1 d 2 d 3 d 4 . A palavra de código é composta pelas quatro letras da palavra da mensagem e, em seguida, por três somas de verificação p 1 p 2 p 3 . O valor de p i é igual a zero se a soma das três letras da mensagem incluída em seu círculo na figura for par e um caso contrário.
Portanto, tem a seguinte matriz geradora G h :
Existe uma forma particularmente simples de matriz geradora, que dá origem à seguinte definição:
A matriz, então, assume a seguinte forma:
Esta forma é particularmente interessante, o cálculo da palavra de código consiste na determinação das n - k últimas coordenadas, porque k primeiro correspondem às da mensagem inicial. Além disso, sujeito à ausência de alteração, a decodificação também é rápida, consiste em considerar apenas as primeiras n coordenadas da palavra do código. Notamos de passagem que o número de linhas da matriz geradora é igual à ordem do vetor a ser codificado (aqui notado k ), caso contrário, o produto da matriz não tem significado.
Estas coordenadas correspondem exatamente à redundância, seu objetivo é a detecção ou correção de eventuais erros. No caso binário, eles correspondem à paridade das somas das letras da mensagem original, então freqüentemente se fala em bits de paridade .
Os códigos lineares podem ser colocados desta forma:
O que significa que, mesmo que isso signifique modificar a base de E , é possível expressar a matriz geradora do código graças a uma matriz sistemática.
DemonstraçãoObserve primeiro que pode ser necessário para alterar a ordem da base canônica de F . De fato, se, por exemplo, o código está incluído no espaço vetorial gerado pelos n - 1 últimos vetores da base canônica, então é fútil buscar uma forma sistemática sem modificar a ordem da base. Por outro lado, uma permutação dos vetores não modifica a distância de Hamming.
Deixe-nos primeiro mostrar o seguinte lema:
Esta é uma consequência direta do teorema da base incompleta . Na verdade, consideremos uma base do código, ele forma uma família livre. O teorema da base incompleta indica que é possível completar esta base por elementos de qualquer família de geração, por exemplo a base canónica de F . Os vetores que completam a família são n - k porque o código é de dimensão k e F de dimensão n . Esses vetores formam uma família respondendo às hipóteses da proposição. Qualquer família com uma cardinalidade mais alta tem uma codimensão maior que a dimensão do código e, portanto, a interseção do espaço gerado por tal família e o código não é reduzida ao vetor zero.
Vamos então provar a proposição:
Ou (f j ) onde j é um número inteiro entre 1 e n a base canónica de F . Mesmo que isso signifique reordená-lo, suponhamos que os n - k últimos vetores gerem um subespaço de interseção reduzido ao vetor zero com o código.
O objetivo é encontrar uma base de E ( e i ) onde i é um número inteiro entre 1 e k tal que:
Seja V i de F o subespaço vetorial gerado pelos vetores f j onde j é um elemento da união dos conjuntos {i} e [ k + 1, n ], onde i é escolhido como um elemento de [1, k ] V i contém uma interseção não vazia com o código φ ( E ). Na verdade, a dimensão do código é estritamente maior do que a codimensão de V i . Um elemento diferente de zero desta interseção tem uma coordenada diferente de zero em f i porque os últimos n - k vetores da base geram um subespaço vetorial de interseção reduzido ao vetor zero com o código. Vamos escolher o elemento da interseção com uma coordenada igual a 1 no vetor f i e ser e i denotar seu antecedente por φ. As k igualdades descritas em (ii) são verificadas.
Resta apenas mostrar que a família ( e i ) é livre. Considere uma relação de dependência linear desta família:
A imagem por φ desta relação linear de dependência ainda é zero, portanto:
Já a família ( f j ) é uma base, logo a relação de dependência linear nesta base é trivial, o que demonstra a nulidade dos coeficientes λ i . A família ( e i ) é portanto livre, é uma base porque sua cardinalidade é a da dimensão de E , que encerra a prova.