Ir ao conteúdo principal

Seção 8.3 Matrizes Verificadora e Geradora

Devemos encontrar uma forma sistemática de gerar códigos lineares assim como métodos rápidos de decodificação. Examinando as propriedades da matriz \(H\) e escolhendo \(H\) cuidadosamente, é possível desenvolver métodos muito eficientes para codificar e decodificar mensagens. Com este objetivo, introduziremos a matriz geradora padrão e a matriz verificadora canônica.

Suponha que \(H\) é uma matriz de \(m \times n\) com coeficiente em \({\mathbb Z}_2\) e \(n \gt m\text{.}\) Se as últimas \(m\) colunas da matriz formam a matriz identidade de \(m \times m\text{,}\) \(I_m\text{,}\) então a matriz é uma matriz verificadora canônica. Mais especificamente, \(H= (A \mid I_m)\text{,}\) donde \(A\) é a matriz de \(m \times (n-m)\)

\begin{equation*} \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1,n-m} \\ a_{21} & a_{22} & \cdots & a_{2,n-m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{m,n-m} \end{pmatrix} \end{equation*}

e \(I_m\) é a matriz identidade de \(m \times m\)

\begin{equation*} \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix}. \end{equation*}

Com cada matriz verificadora canônica podemos associar uma matriz geradora padrão de \(n \times (n-m)\)

\begin{equation*} G = \left( \frac{I_{n-m}}{A} \right). \end{equation*}

Nosso objetivo será mostrar que existe um \(\mathbf x\) que satisfaça \(G {\mathbf x} = {\mathbf y}\) si e somente se \(H{\mathbf y} = {\mathbf 0}\text{.}\) Dado um bloco \({\mathbf x}\) a ser codificado, a matriz \(G\) nos permitirá codificá-lo rapidamente para uma palavra \({\mathbf y}\) do código linear.

Suponha que temos as seguintes oito palavras por codificar:

\begin{equation*} (000), (001), (010), \ldots, (111). \end{equation*}

Para

\begin{equation*} A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}, \end{equation*}

as matrizes geradora padrão e verificadora canônica são

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

e

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

respectivamente.

Observe que as linhas em \(H\) representam as verificações de paridade em certas posições das 6-tuplas. Os uns da matriz identidade servem como verificadores de paridade para os uns na mesma linha. Se \({\mathbf x} = (x_1, x_2, x_3, x_4, x_5, x_6)\text{,}\) então

\begin{equation*} {\mathbf 0} = H{\mathbf x} = \begin{pmatrix} x_2 + x_3 + x_4 \\ x_1 + x_2 + x_5\\ x_1 + x_3 + x_6 \end{pmatrix}, \end{equation*}

o que produz um sistema de equações:

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

Aqui \(x_4\) serve como bit de controle para \(x_2\) e \(x_3\text{;}\) \(x_5\) é um bit de controle para \(x_1\) e \(x_2\text{;}\) e \(x_6\) é um bit de controle para \(x_1\) e \(x_3\text{.}\) A matriz identidade impede que \(x_4\text{,}\) \(x_5\text{,}\) e \(x_6\) tenham que checar um ao outro. Logo, \(x_1\text{,}\) \(x_2\) e \(x_3\) podem ser arbitrários, mas \(x_4\text{,}\) \(x_5\) e \(x_6\) devem ser escolhidos de maneira a assegurar as paridades respectivas. O espaço nulo de \(H\) pode ser calculado facilmente

\begin{equation*} \begin{array}{cccc} (000000) & (001101) & (010110) & (011011) \\ (100011) & (101110) & (110101) & (111000). \end{array} \end{equation*}

Uma forma ainda mais fácil de calcular o espaço nulo é com a matriz geradora \(G\) (Tabela 8.3.2).

Tabela 8.3.2.
Palavra de Mensagem \(\mathbf x\) Palavra do código \(G \mathbf x\)
000 000000
001 001101
010 010110
011 011011
100 100011
101 101110
110 110101
111 111000

Deixamos a demonstração deste teorema como exercício. À luz do teorema, os primeiros \(n - m\) bits de \({\mathbf x}\) são chamados bits de informação e os últimos \(m\) bits se denominam bits de verificação. No Exemplo 8.3.1, os primeiros três bits são de informação e os últimos três são bits de verificação.

Sejam \(G {\mathbf x}_1 = {\mathbf y}_1\) e \(G {\mathbf x}_2 ={\mathbf y}_2\) duas palavras do código. Então \({\mathbf y}_1 + {\mathbf y}_2\) está em \(C\) pois

\begin{equation*} G( {\mathbf x}_1 + {\mathbf x}_2) = G {\mathbf x}_1 + G {\mathbf x}_2 = {\mathbf y}_1 + {\mathbf y}_2. \end{equation*}

Além disso, devemos mostrar que dois blocos de mensagem diferentes não podem ser codificados para mesma palavra do código. Isto é, devemos mostrar que se \(G {\mathbf x} = G {\mathbf y}\text{,}\) então \({\mathbf x} = {\mathbf y}\text{.}\) Suponha que \(G {\mathbf x} = G {\mathbf y}\text{.}\) Então

\begin{equation*} G {\mathbf x} - G {\mathbf y} = G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}. \end{equation*}

Mas as primeiras \(k\) coordenadas em \(G( {\mathbf x} - {\mathbf y})\) são exatamente \(x_1 -y_1, \ldots, x_k - y_k\text{,}\) pois estão determinadas pela matriz identidade, \(I_k\text{,}\) que é parte de \(G\text{.}\) Logo, \(G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}\) se e somente se \({\mathbf x} = {\mathbf y}\text{.}\)

Antes de demonstrar a relação entre a matriz verificadora canônica e a matriz geradora padrão, demonstraremos um lema.

Seja \(C = HG\text{.}\) O coeficiente \(ij\)th de \(C\) é

\begin{align*} c_{ij} & = \sum_{k=1}^n h_{ik} g_{kj}\\ & = \sum_{k=1}^{n-m} h_{ik} g_{kj} + \sum_{k=n-m+1}^n h_{ik} g_{kj}\\ & = \sum_{k=1}^{n-m} a_{ik} \delta_{kj} + \sum_{k=n-m+1}^n \delta_{i-(m-n),k} a_{kj}\\ & = a_{ij} + a_{ij}\\ & = 0, \end{align*}

donde

\begin{equation*} \delta_{ij} = \begin{cases} 1, & i = j \\ 0, & i \neq j \end{cases} \end{equation*}

é o delta de Kronecker.

Primeiro suponha que \({\mathbf y} \in C\text{.}\) Então \(G {\mathbf x} = {\mathbf y}\) para algum \({\mathbf x} \in {\mathbb Z}_2^m\text{.}\) Pelo Lema 8.3.5, \(H {\mathbf y} = HG {\mathbf x} = {\mathbf 0}\text{.}\)

Reciprocamente, suponha que \({\mathbf y} = (y_1, \ldots, y_n)^{\rm t}\) está no espaço nulo de \(H\text{.}\) Devemos encontrar \({\mathbf x}\) em \({\mathbb Z}_2^{n-m}\) tal que \(G {\mathbf x}^{\rm t} = {\mathbf y}\text{.}\) Como \(H {\mathbf y} = {\mathbf 0}\text{,}\) devemos satisfazer o seguinte conjunto de equações:

\begin{align*} a_{11} y_1 + a_{12} y_2 + \cdots + a_{1, n-m} y_{n-m} + y_{n-m+1} & = 0\\ a_{21} y_1 + a_{22} y_2 + \cdots + a_{2, n-m} y_{n-m} + y_{n-m+1} & = 0\\ & \vdots \\ a_{m1} y_1 + a_{m2} y_2 + \cdots + a_{m, n-m} y_{n-m} + y_{n-m+1} & = 0. \end{align*}

Equivalentemente, \(y_{n-m+1}, \ldots, y_n\) estão determinados por \(y_1, \ldots, y_{n-m}\text{:}\)

\begin{align*} y_{n-m+1} & = a_{11} y_1 + a_{12} y_2 + \cdots + a_{1, n-m} y_{n-m}\\ y_{n-m+1} & = a_{21} y_1 + a_{22} y_2 + \cdots + a_{2, n-m} y_{n-m}\\ & \vdots\\ y_{n-m+1} & = a_{m1} y_1 + a_{m2} y_2 + \cdots + a_{m, n-m} y_{n-m}. \end{align*}

Por fim podemos tomar \(x_i = y_i\) para \(i= 1, \ldots, n - m\text{.}\)

Seria bom poder calcular a distância mínima de um código linear diretamente a partir de sua matriz \(H\) para poder determinar as capacidades de detecção e correcção de erros do código. Suponha que

\begin{align*} {\mathbf e}_1 & = (100 \cdots 00)^{\rm t}\\ {\mathbf e}_2 & = (010 \cdots 00)^{\rm t}\\ & \vdots\\ {\mathbf e}_n & = (000 \cdots 01)^{\rm t} \end{align*}

são as \(n\)-tuplas em \({\mathbb Z}_2^n\) de peso 1. Para uma matriz binária \(H\) de \(m \times n\text{,}\) \(H{\mathbf e}_i\) é exatamente a coluna \(i\)-ésima da matriz \(H\text{.}\)

Observe que

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

Enunciamos o resultado na seguinte proposição e deixamos sua demonstração como exercício.

Suponha que \({\rm Null}(H)\) é um código que detecta um erro. Então a distância mínima do código deve ser ao menos 2. Como o espaço nulo é um código de grupo, é necessário que o código não tenha nenhuma palavra de peso menor que 2 , sem contar a palavra de peso 0. Isto é, \({\mathbf e}_i\) não deve ser uma palavra do código para \(i = 1, \ldots, n\text{.}\) Como \(H{\mathbf e}_i\) é a \(i\)-ésima coluna de \(H\text{,}\) a \(i\)-ésima coluna não tem somente zeros.

Reciprocamente, suponha que nenhuma coluna de \(H\) é a coluna zero. Pela Proposição 8.3.8, \(H{\mathbf e}_i \neq {\mathbf 0}\text{;}\) logo, a distância mínima do código é ao menos 2, e o código tem a capacidade de detectar um erro.

Se consideramos as matrizes

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

e

\begin{equation*} H_2 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix}, \end{equation*}

então o espaço nulo de \(H_1\) é um código que detecta um erro e o espaço nulo de \(H_2\) não é.

Podemos melhorar o Teorema 8.3.9. Este teorema nos entrega condições sobre a matriz \(H\) que nos dizem quando o peso mínimo do código formado pelo espaço nulo de \(H\) é 2. Também podemos determinar quando a distância mínima de um código linear é 3 examinando a matriz correspondente.

Se fazemos

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

e queremos determinar se \(H\) é a matriz verificadora canônica para um código corretor de um erro, é necessário ter certeza que \({\rm Null}(H)\) não contenha nenhuma 4-tupla de peso 2. Isto é, \((1100)\text{,}\) \((1010)\text{,}\) \((1001)\text{,}\) \((0110)\text{,}\) \((0101)\text{,}\) e \((0011)\) não devem estar em \({\rm Null}(H)\text{.}\) O próximo teorema estabelece que podemos saber se o código determinado por \(H\) é corretor de erros examinando as colunas de \(H\text{.}\) Note neste exemplo que \(H\) não só não tem colunas nulas, como que também não possuir colunas repetidas.

A \(n\)-tupla \({\mathbf e}_{i} +{\mathbf e}_{j}\) tem uns nas \(i\)-ésima e \(j\)-ésima posições e zeros nas demais, e \(w( {\mathbf e}_{i} +{\mathbf e}_{j}) = 2\) para \(i \neq j\text{.}\) Como

\begin{equation*} {\mathbf 0} = H({\mathbf e}_{i} +{\mathbf e}_{j}) = H{\mathbf e}_{i} + H{\mathbf e}_{j} \end{equation*}

Só pode ocorrer se a \(i\)-ésima e a \(j\)-ésima colunas são idênticas. Como não contêm palavras de peso menor ou igual a 2, o espaço nulo de \(H\) é um código corretor de um erro.

Suponha agora que temos uma matriz verificadora canônica \(H\) com três linhas. Podemos nos perguntar quantas colunas podemos adicionar a matriz e continuar tendo um espaço nulo que seja um código que detecte e corrija um erro. Como cada coluna tem três entradas, existem \(2^3 = 8\) colunas diferentes possíveis. Não podemos adicionar as colunas

\begin{equation*} \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}. \end{equation*}

Então podemos adicionar até quatro colunas mantendo uma distância mínima de 3.

Em geral, se \(H\) é uma matriz verificadora canônica de \(m \times n\text{,}\) então existe \(n-m\) posições de informação em cada palava do código. Cada coluna tem \(m\) bits, então existem \(2^m\) possíveis colunas diferentes. É necessário que as colunas \({\mathbf 0}, {\mathbf e}_1, \ldots, {\mathbf e}_m\) sejam excluídas, deixando \(2^m - (1 + m)\) colunas restantes para informação se queremos manter a habilidade de não somente detectar, mas também corrigir um erro.