AATA Decodificação Eficiente

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.

🔗

Exemplo 8.4.1.

Dada a matriz binária

H = (\begin{matrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{matrix})

e as 5-tuplas $x = (11011)^{t}$ e $y = (01011)^{t},$ podemos calcular

H x = (\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}) y H y = (\begin{matrix} 1 \\ 0 \\ 1 \end{matrix}) .

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

🔗

H

é uma matriz de

m \times n

x \in Z_{2}^{n},

então dizemos que a síndrome de

x

H x .

A seguinte proposição permite a detecção e correção rápida de erros.

🔗

Proposição 8.4.2.

Seja $H$ uma matriz de $m \times n$ que determina um código linear e seja $x$ a $n$ -tupla recebida. Escrevemos $x$ como $x = c + e,$ donde $c$ é a palavra transmitida e $e$ é o erro de transmissão. Então a síndrome $H x$ da palavra recebida $x$ é igual a síndrome do erro $e .$

🔗

Demonstração.

A demonstração segue do fato que

H x = H (c + e) = H c + H e = 0 + H e = H e .

🔗

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 e

é a

i

-ésima coluna da matriz

H .

🔗

Teorema 8.4.3.

Seja $H \in M_{m \times n} (Z_{2})$ e suponha que o código linear correspondente $H$ é corretor de um erro. Seja $r$ uma $n$ -tupla recebida que foi trasmitida com não mais de um erro. Se a síndrome de $r$ é $0,$ então não ocorreu erro; do contrário, se a síndrome de $r$ é igual a alguma coluna de $H,$ digamos a $i$ -ésima coluna, então o erro ocurreu no $i$ -ésimo bit.

🔗

Exemplo 8.4.4.

Consideremos a matriz

H = (\begin{matrix} 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \end{matrix})

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

H x = (\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}), H y = (\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}), H z = (\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}) .

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

🔗

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

Z_{2}^{n} .

Decodificação por Classes Laterais ou decodificação padrão usa as classes laterais de

C

Z_{2}^{n}

para implementar a decodificação de máxima verossimilhança. Suponha que

C

é um código linear

(n, m) .

Uma classe lateral de

C

Z_{2}^{n}

é escrito na forma

x + C,

donde

x \in Z_{2}^{n} .

Pelo Teorema de Lagrange (Teorema 6.2.2), existem

2^{n - m}

classes laterais de

C

Z_{2}^{n} .

🔗

Exemplo 8.4.5.

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

H = (\begin{matrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{matrix}) .

O código consiste das palavras

(00000) (01101) (10011) (11110) .

Existem $2^{5 - 2} = 2^{3}$ classes laterais de $C$ em $Z_{2}^{5},$ cada uma de ordem $2^{2} = 4 .$ 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

x

era a palavra trasmitida e que

r

é a

n

-tupla recebida. Se

e

é o erro de transmissão, então

r = e + x

ou, equivalentemente,

x = e + r .

Mas, isso é exatamente equivalente a dizer que

r

é um elemento da classe

e + C .

Na decodificação de máxima verossimilhança esperamos que

e

seja o menor possível; isto é,

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

r + e

para obter

x .

🔗

Exemplo 8.4.7.

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 $r = (01111) .$ Para decodificar $r,$ o encontramos na classe $(00010) + C;$ logo, a palavra do código originalmente trasmitida deve ter sido $(01101) = (01111) + (00010) .$

🔗

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)

🔗

Proposição 8.4.9.

Seja $C$ um código linear $(n, k)$ dado pela matriz $H$ e suponha que $x$ e $y$ estão em $Z_{2}^{n} .$ Então $x$ e $y$ estão na mesma classe lateral de $C$ se e somente se $H x = H y .$ Isto é, duas $n$ -tuplas estão na mesma classe lateral se e somente se tem a mesma síndrome.

🔗

Demonstração.

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

🔗

Exemplo 8.4.10.

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

H x = (\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}) .

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

🔗

Dado um código de blocos

(n, k),

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 .

Suponha que temos um código de bloco

(32, 24) .

Temos uma enorme quantidade de palavras no código,

2^{24},

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.