Correção de erros: pesos e distâncias

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

Na postagem Correção de erros, fiz uma pequena introdução a esse fascinante e importante tópico. Agora vou apresentar alguns conceitos para auxiliar a compreensão de algumas propriedades gerais dos códigos lineares binários. Já apresentei a notação binária e a aritmética módulo que deve ser utilizada. Também falei sobre como somar palavras de código e como combiná-las linearmente, além de ter definido o produto escalar entre duas delas. Chegou a hora de definir o tamanho de um código e o peso de um vetor pertencente a um espaço vetorial binário. Com esse conceito de peso, vou apresentar também a definição da distância de Hamming entre dois desses vetores.

Quando temos vetores linearmente independentes formando a base de um código binário podemos combiná-los linearmente para produzir todas as possíveis palavras do código Os únicos escalares na aritmética módulo que podemos usar é e e, portanto, uma combinação linear desses vetores consiste de uma soma de um subconjunto da base. Assim, sejam os vetores da base. Uma palavra qualquer do código é, portanto, a combinação linear

onde são escalares, cada qual podendo ser apenas ou Assim, se temos apenas duas palavras possíveis, isto é, e Se temos quatro possíveis palavras: e Veja que ao aumentar de uma unidade, multiplicamos por o número anterior de palavras do código. Então, quando devemos multiplicar por e obter oito palavras. De fato, quando as possíveis palavras são:

e

ou seja, oito palavras. Logo, para vetores linearmente independentes, o código tem palavras no total. Portanto, dizemos que o tamanho de um código formado por vetores linearmente independentes, é dado por Note que no contexto deste parágrafo, quando escrevo refiro-me ao vetor nulo, que, para um espaço vetorial de dimensões, corresponde ao vetor com bits nulos.

Vamos ver um exemplo. Considere o caso de um código Vamos tomar três vetores de cinco dimensões, linearmente independentes, tais como: e De acordo com nossa análise acima, devemos ter ou oito, palavras distintas. De fato,

e

O peso de um vetor que pertence a um espaço vetorial binário é dado pelo número de uns que tem. Assim, por exemplo, no caso de um espaço vetorial binário de cinco dimensões, o peso da palavra é o peso de é e o peso de também é Como mais um exemplo, no caso de um espaço de dimensões, o peso de é

Dados dois vetores de um espaço vetorial binário de dimensões, a distância de Hamming entre eles é definida como sendo o peso de sua soma. Assim, por exemplo, dados e a distância entre e é o peso de que é igual a Nesse caso, escrevemos Veja que o cálculo do peso e da distância de Hamming é feito com aritmética usual, mas não é feito através da aritmética módulo Observe que e que sendo que se então para quaisquer e pertencentes ao espaço vetorial. Além disso, a desigualdade triangular também pode ser facilmente verificada: para quaisquer e pertencentes ao espaço vetorial.

Um conceito muito importante para podermos demonstrar os teoremas das próximas postagens sobre este tópico de correção de erros é o da distância mínima entre duas palavras distintas de um código, sendo que a distância mínima nula de um código não é definida. Veja que o conjunto de todas as somas entre duas palavras do código é igual ao conjunto de todas as palavras do código. Sendo assim, listando todas as somas entre duas palavras quaisquer do código, estaremos listando todas as palavras do código. Logo, a menor distância entre duas palavras distintas do código é idêntica ao menor peso entre os pesos das palavras não nulas do código.

Como exemplo, consideremos de novo o código definido pelos três vetores de base: e Como vimos, as oito palavras desse código são e Os pesos dessas palavras são, respectivamente, e Logo, o menor peso não nulo é que é também a menor distância entre duas palavras distintas do código.

😎

Música desta postagem: Mazurka in B Major Op. 56 No. 1 de Frédéric Chopin, por Monica Alianello

Recomendo também a leitura das postagens a seguir:

Uma versão em PDF

Gostou desta postagem? Então clique no botão abaixo e siga o Nerdyard no Twitter! Toda vez que houver uma nova postagem aqui, você saberá imediatamente! :cool:

Siga Nerdyard no Twitter

Melhor ainda: inscreva-se em Nerdyard e receba, por e-mail, o aviso com links para cada nova postagem ou novidade.

Google Groups
Inscreva-se em Nerdyard
Melhor email:
Visite este grupo

NOTE QUE EU ODEIO SPAM COM TODA CONVICÇÃO! :cool:

Dessa forma, não se preocupe: eu juro que jamais fornecerei seu endereço de e-mail ou qualquer outra informação sobre você para ninguém!

Clip to Evernote

Deixe um comentário for Correção de erros: pesos e distâncias

Editor de Equações (www.codecogs.com/latex/eqneditor.php)

Para entender como utilizar esse editor de equações, clique aqui.