Ir ao conteúdo principal

Seção 8.4 Decodificação Eficiente

Agora estamos em um ponto donde já somos capazes de gerar códigos lineares que detectem e corrijam erros com relativa facilidade, mas ainda é um processo lento decodificar uma \(n\)-tupla recebida e determinar qual é a palavra do código mas próxima, pois a \(n\)-tupla recebida deve ser comparada com todas as possíveis palavras do código para determinar a decodificação apropriada. Este pode ser um problema sério se o código for muito grande.

Dada a matriz binária

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

e as 5-tuplas \({\mathbf x} = (11011)^{\rm t}\) e \({\mathbf y} = (01011)^{\rm t}\text{,}\) podemos calcular

\begin{equation*} H{\mathbf x} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} \qquad \text{y} \qquad H{\mathbf y} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}. \end{equation*}

Logo, \({\mathbf x}\) é uma palavra do código e \({\mathbf y}\) não é, pois \({\mathbf x}\) está no espaço nulo e \({\mathbf y}\) não está. Notemos que \(H{\mathbf y}\) é idêntica a primeira coluna de \(H\text{.}\) De fato, foi aqui que o erro ocorreu. Se trocamos o primeiro bit em \({\mathbf y}\) de 0 a 1, obtemos \({\mathbf x}\text{.}\)

Se \(H\) é uma matriz de \(m \times n\) e \({\mathbf x} \in {\mathbb Z}_2^n\text{,}\) então dizemos que a síndrome de \({\mathbf x}\) é \(H{\mathbf x}\text{.}\) A seguinte proposição permite a detecção e correção rápida de erros.

A demonstração segue do fato que

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

Esta proposição nos diz que a síndrome de uma palvra recebida depende somente do erro e não da palavra transmitida. A demonstração do seguinte teorema segue imediatamente da Proposição 8.4.2 e do fato que \(H{\mathbf e}\) é a \(i\)-ésima coluna da matriz \(H\text{.}\)

Consideremos a matriz

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

e suponha que as 6-tuples \({\mathbf x} = (111110)^{\rm t}\text{,}\) \({\mathbf y} = (111111)^{\rm t}\text{,}\) e \({\mathbf z} = (010111)^{\rm t}\) foram recebidas. Então

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

Logo, \({\mathbf x}\) tem um erro no terceiro bit e \({\mathbf z}\) tem um erro no quarto bit. As palavras trasmitidas para \({\mathbf x}\) e \({\mathbf z}\) devem haver sido \((110110)\) e \((010011)\text{,}\) respectivamente. A síndrome de \({\mathbf y}\) não aparece em nenhuma das colunas de \(H\text{,}\) de maneira que mais de um erro deve ter ocorrido para produzir \({\mathbf y}\text{.}\)

Subseção 8.4.1 Decodificação por Classes Laterais

Podemos usar teoria de grupos para obter outro método de decodificação. Um código linear \(C\) é um subgrupo de \({\mathbb Z}_2^n\text{.}\) Decodificação por Classes Laterais ou decodificação padrão usa as classes laterais de \(C\) em \({\mathbb Z}_2^n\) para implementar a decodificação de máxima verossimilhança. Suponha que \(C\) é um código linear \((n,m)\text{.}\) Uma classe lateral de \(C\) em \({\mathbb Z}_2^n\) é escrito na forma \({\mathbf x} + C\text{,}\) donde \({\mathbf x} \in {\mathbb Z}_2^n\text{.}\) Pelo Teorema de Lagrange (Teorema 6.2.2), existem \(2^{n-m}\) classes laterais de \(C\) em \({\mathbb Z}_2^n\text{.}\)

Seja \(C\) o código linear \((5,3)\) dado pela matriz verificadora

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

O código consiste das palavras

\begin{equation*} (00000) \quad (01101) \quad (10011) \quad (11110). \end{equation*}

Existem \(2^{5-2} = 2^3\) classes laterais de \(C\) em \({\mathbb Z}_2^5\text{,}\) cada uma de ordem \(2^2 =4\text{.}\) Estas classes laterais aparecem na Tabela 8.4.6.

Tabela 8.4.6.
Representante Classe lateral
da classe
\(C\) (00000) (01101) (10011) (11110)
\((10000) + C\) (10000) (11101) (00011) (01110)
\((01000) + C\) (01000) (00101) (11011) (10110)
\((00100) + C\) (00100) (01001) (10111) (11010)
\((00010) + C\) (00010) (01111) (10001) (11100)
\((00001) + C\) (00001) (01100) (10010) (11111)
\((10100) + C\) (00111) (01010) (10100) (11001)
\((00110) + C\) (00110) (01011) (10101) (11000)

Nossa tarefa é descobrir como, conhecendo as classes laterais, pode nos ajudar a decodificar uma mensagem. Suponha que \({\mathbf x}\) era a palavra trasmitida e que \({\mathbf r}\) é a \(n\)-tupla recebida. Se \({\mathbf e}\) é o erro de transmissão, então \({\mathbf r} = {\mathbf e} + {\mathbf x}\) ou, equivalentemente, \({\mathbf x} = {\mathbf e} + {\mathbf r}\text{.}\) Mas, isso é exatamente equivalente a dizer que \({\mathbf r}\) é um elemento da classe \({\mathbf e} + C\text{.}\) Na decodificação de máxima verossimilhança esperamos que \({\mathbf e}\) seja o menor possível; isto é, \({\mathbf e}\) terá o menor peso. Uma \(n\)-tupla de peso mínimo em uma classe se denomina líder de classe. Uma vez que determinamos um líder para cada classe, o processo de decodificação se transforma no de calcular \({\mathbf r} + {\mathbf e}\) para obter \({\mathbf x}\text{.}\)

Na Tabela 8.4.6, note que escolhemos um representante de peso mínimo para cada classe. Esses representantes são líderes de classe. Agora suponha que recebemos a palavra \({\mathbf r} = (01111)\text{.}\) Para decodificar \({\mathbf r}\text{,}\) o encontramos na classe \((00010) + C\text{;}\) logo, a palavra do código originalmente trasmitida deve ter sido \((01101) = (01111) + (00010)\text{.}\)

Um problema potencial com este método de decodificação é que temos que examinar cada classe em busca da palavra recebida. A seguinte proposição entrega um método para a implementação da decodificação por classes laterais. Estabelece que podemos associar uma síndrome com cada classe, logo, podemos fazer uma tabela que designa um líder de classe a cada síndrome. Tal lista se denomina tabela de decodificação.

Tabela 8.4.8.
Síndromes Líder de classe
(000) (00000)
(001) (00001)
(010) (00010)
(011) (10000)
(100) (00100)
(101) (01000)
(110) (00110)
(111) (10100)

Duas \(n\)-tuplas \({\mathbf x}\) e \({\mathbf y}\) estão na mesma classe lateral \(C\) precisamente quando \({\mathbf x} - {\mathbf y} \in C\text{;}\) mas, isto é equivalente a \(H({\mathbf x} - {\mathbf y}) = 0\) ou \(H {\mathbf x} = H{\mathbf y}\text{.}\)

A Tabela 8.4.8 é uma tabela de decodificação para o código \(C\) dado no Exemplo 8.4.5. Se é recebido \({\mathbf x} = (01111)\text{,}\) então sua síndrome é calculada como

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

Examinando a tabela de decodificação, determinamos que o líder de classe é \((00010)\text{.}\) Agora é fácil decodificar a palavra recebida.

Dado um código de blocos \((n,k)\text{,}\) surge a pergunta se a decodificação por classes laterais é um sistema manejável ou não. Uma tabela de decodificação requer uma lista de líderes de classes laterais e síndromes para cada uma das \(2^{n - k}\) classes laterais de \(C\text{.}\) Suponha que temos um código de bloco \((32, 24)\text{.}\) Temos uma enorme quantidade de palavras no código, \(2^{24}\text{,}\) mas existe somente \(2^{32 - 24} = 2^{8} = 256\) classes laterais.

Sage.

Sage tem muitos comandos relacionados a teoria de códigos, incluindo a capacidade de construir diferentes familias de códigos.