Ir ao conteúdo principal

Seção 8.2 Códigos Lineares

Para ganhar mais informação sobre um código particular e desenvolver técnicas mais eficientes de codificação, decodificação e detecção de erros, necessitaremos agregar uma maior estrutura para nossos códigos. Uma forma de conquistar isso é pedir que o código também seja um grupo. Um código de grupo ou código linearé um código que também é um subgrupo de \({\mathbb Z}_2^n\text{.}\)

Para verificar que um código é um código de grupo, só precisamos verificar uma coisa. Se somamos dois elementos no código, o resultado deve ser uma \(n\)-tupla que novamente está no código. Não é necessário verificar que o elemnto inverso da \(n\)-tupla esta no código, pois cada palavra do código é seu próprio inverso, também não é necessário checar que \({\mathbf 0}\) seja uma palavra do código. Por exemplo,

\begin{equation*} (11000101) + (11000101) = (00000000). \end{equation*}

Suponha que temos um código que consista das seguintes 7-tuplas:

\begin{align*} &(0000000) & & (0001111) & & (0010101) & & (0011010)\\ &(0100110) & & (0101001) & & (0110011) & & (0111100)\\ &(1000011) & & (1001100) & & (1010110) & & (1011001)\\ &(1100101) & & (1101010) & & (1110000) & & (1111111). \end{align*}

É uma tarefa simples, porém tediosa verificar que este código é um subgrupo de \({\mathbb Z}_2^7\) e que portanto, é um código de grupo. Este código detecta um erro e corrige um erro, mas calcular todas as distâncias entre pares de palavras do código para determinar que \(d_{\min} = 3\) é um processo longo e tedioso. É muito mais simples ver que o peso mínimo de todas as palavras não nulas é 3. Como veremos daqui a pouco, isso não é uma coincidência. Mas a relação entre pesos e distâncias em um código particular é fortemente dependente do fato que o código seja um grupo.

Suponha que \({\mathbf x}\) e \({\mathbf y}\) são \(n\)-tuplas binárias. Então a distância entre \({\mathbf x}\) e \({\mathbf y}\) é exatamente o número de lugares em que \({\mathbf x}\) e \({\mathbf y}\) diferem. Mas \({\mathbf x}\) e \({\mathbf y}\) diferem em uma coordenada particular se e somente a soma é 1 nessa coordenada, pois

\begin{align*} 1 + 1 & = 0\\ 0 + 0 & = 0\\ 1 + 0 & = 1\\ 0 + 1 & = 1. \end{align*}

Assim, o peso da soma é igual a distância entra as duas palavras.

Observe que

\begin{align*} d_{\min} & = \min \{ d({\mathbf x},{\mathbf y}) : {\mathbf x}\neq{\mathbf y} \}\\ &= \min \{ d({\mathbf x},{\mathbf y}) : {\mathbf x}+{\mathbf y} \neq {\mathbf 0} \}\\ &= \min\{ w({\mathbf x} + {\mathbf y}) : {\mathbf x}+{\mathbf y}\neq {\mathbf 0} \}\\ & = \min\{ w({\mathbf z}) : {\mathbf z} \neq {\mathbf 0} \}. \end{align*}

Subseção 8.2.1 Códigos Lineares

A partir do Exemplo 8.2.1, fica fácil verificar que o peso mínimo diferente de zero é 3, o código realmente detecta e corrige todos os erros individuais. Reduzimos o problema de encontrar “bons” códigos para o de gerar códigos de grupos. Uma forma fácil de gerar códigos de grupo é aplicar um pouco de teoria de matrizes.

Definimos o produto interno de duas \(n\)-tuplas binárias como

\begin{equation*} {\mathbf x} \cdot {\mathbf y} = x_1 y_1 + \cdots + x_n y_n, \end{equation*}

donde \({\mathbf x} = (x_1, x_2, \ldots, x_n)^{\rm t}\) e \({\mathbf y} = (y_1, y_2, \ldots, y_n)^{\rm t}\) são vetores coluna. 1  Por exemplo, se \({\mathbf x} = (011001)^{\rm t}\) e \({\mathbf y} = (110101)^{\rm t}\text{,}\) então \({\mathbf x} \cdot {\mathbf y} = 0\text{.}\) Também podemos pensar no produto interno como o produto de um vetor linha com um vetor coluna; isto é,

\begin{align*} {\mathbf x} \cdot {\mathbf y} & = {\mathbf x}^{\rm t} {\mathbf y}\\ & = \begin{pmatrix} x_1 & x_2 & \cdots & x_n \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix}\\ & = x_{1}y_{1} + x_{2}y_{2} + \cdots + x_{n}y_{n}. \end{align*}

Suponha que as palavras a serem codificadas consistem de todas as 3-tuplas binárias e que nosso mecanismo de codificação é o de controle de paridade. Para codificar uma 3-tupla arbitrária, adicionamos o quarto bit para obter um número par de uns. Note que uma \(n\)-tupla arbitrária \({\mathbf x} = (x_1, x_2, \ldots, x_n)^{\rm t}\) tem um número par de uns exatamente quando \(x_1 + x_2 + \cdots + x_n = 0\text{;}\) logo, uma 4-tupla \({\mathbf x} = (x_1, x_2, x_3, x_4)^{\rm t}\) tem um número par de uns se e somente se \(x_1+ x_2+ x_3+ x_4 = 0\text{,}\) ou

\begin{equation*} {\mathbf x} \cdot {\mathbf 1} = {\mathbf x}^{\rm t} {\mathbf 1} = \begin{pmatrix} x_1 & x_2 & x_3 & x_4 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} = 0. \end{equation*}

Este exemplo nos da esperança de que haja uma conexão entre matrizes e a teoria de códigos.

Seja \({\mathbb M}_{m \times n}({\mathbb Z}_2)\) o conjunto de todas as matrizes de \(m \times n\) com coeficientes em \({\mathbb Z}_2\text{.}\) Fazemos operações entre as matrizes como sempre, exceto que todas operações de soma e produto ocorrem em \({\mathbb Z}_2\text{.}\) Defina o espaço nulo de uma matriz \(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\) como o conjunto de todas as \(n\)-tuplas binárias \({\mathbf x}\) tais que \(H{\mathbf x} = {\mathbf 0}\text{.}\) Denotamos o espaço nulo de uma matriz \(H\) por \(\Null(H)\text{.}\)

Suponha que

\begin{equation*} H = \begin{pmatrix} 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{pmatrix}. \end{equation*}

Para que uma 5-tupla \({\mathbf x} = (x_1, x_2, x_3, x_4, x_5)^{\rm t}\) esteja no espaço nulo de \(H\text{,}\) \(H{\mathbf x} = {\mathbf 0}\text{.}\) Equivalentemente, devemos satisfazer o seguinte sistema de equações:

\begin{align*} x_2 + x_4 & = 0\\ x_1 + x_2 + x_3 + x_4 & = 0\\ x_3 + x_4 + x_5 & = 0. \end{align*}

O conjunto da 5-tuplas binárias que satisfazem estas equações é

\begin{equation*} (00000) \qquad (11110) \qquad (10101) \qquad (01011). \end{equation*}

É fácil determinar que este código é um código de grupo.

Como cada elemento de \({\mathbb Z}_2^n\) é seu próprio inverso, o único que precisa ser verificado é o fecho. Sejam \({\mathbf x}, {\mathbf y} \in {\rm Null}(H)\) para alguma matriz \(H\) em \({\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Então \(H{\mathbf x} = {\mathbf 0}\) e \(H{\mathbf y} = {\mathbf 0}\text{.}\) Assim

\begin{equation*} H({\mathbf x}+{\mathbf y}) = H{\mathbf x} + H{\mathbf y} = {\mathbf 0} + {\mathbf 0} = {\mathbf 0}. \end{equation*}

Logo, \({\mathbf x} + {\mathbf y}\) está no espaço nulo de \(H\) e portanto é uma palavra do código.

Um código é um código linear se está determinado pelo espaço nulo de alguma matriz \(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\)

Seja \(C\) o código dado pela matriz

\begin{equation*} H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}. \end{equation*}

Suponha que é recebido a 6-tupla \({\mathbf x} = (010011)^{\rm t}\text{.}\) É simplesmente questão de multiplicar matrizes para determinar se \({\mathbf x}\) está ou não no código. Como

\begin{equation*} H{\mathbf x} = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}, \end{equation*}

a palavra recebida não está no código. Devemos tentar corrigi-la ou pedir que seja transmitida novamente.

Como estaremos trabalhando com matrizes, escreveremos as \(n\)-tuplas binárias como vetores coluna pelo resto do capítulo.