Aula 26 - Álgebra II

Suponhamos que, num determinado sistema de comunicação, necessitamos de um código com, no máximo, q^{k} palavras. Poderemos então usar todas as palavras a_{1}a_{2} ⋯ a_{k} ∈ 𝔽_{q}^{k} de comprimento k. Este código será muito pouco eficiente, uma vez que a distância mínima entre palavras é igual a 1.

O Teorema da aula anterior diz-nos que, se quisermos aumentar a eficiência deste código, teremos de aumentar a distância mínima entre as suas palavras. Como poderemos fazer isso? Muito simplesmente, acrescentando a cada palavra a_{1}a_{2} ⋯ a_{k} um bloco c_{k+1} ⋯ c_{n} ∈ 𝔽_{q}^{n−k} tal que, sempre que

d(a_{1}a_{2} ⋯ a_{k}, a′_{1}a′_{2} ⋯ a′_{k}) = 1

então d(c_{k+1} ⋯ c_{n}, c′_{k+1} ⋯ c′_{n}) é máxima, ou seja, igual a n − k. Se, além disso, tivermos o cuidado de garantir que d(c_{k+1} ⋯ c_{n}, c′_{k+1} ⋯ c′_{n}) = n − k + 1 − i sempre que d(a_{1}a_{2} ⋯ a_{k}, a′_{1}a′_{2} ⋯ a′_{k}) = i, teremos um código C com distância mínima δ(C) = n − k + 1.

Os primeiros k símbolos de cada palavra

c = a_{1}a_{2} ⋯ a_{k}c_{k+1} ⋯ c_{n}

são a mensagem original e os n−k símbolos adicionais são os símbolos de controle. A função 𝔽_{q}^{k} → 𝔽_{q}^{n} que aplica a palavra a_{1}a_{2} ⋯ a_{k} na palavra a_{1}a_{2} ⋯ a_{k}c_{k+1} ⋯ c_{n} chama-se um esquema de codificação. Estes esquemas de codificação fazem parte de qualquer sistema de comunicação actual, que pode ser descrito do seguinte modo:

f

g

a

Mensagem

c

Mensagem codificada

ã

Mensagem descodificada

c + e

Mensagem recebida Canal de comunicação

Ruído

[figure]

A função f é um esquema de codificação. À função g : 𝔽_{q}^{n} → 𝔽_{q}^{k} chama-se esquema de descodificação. Os esquemas de codificação podem ser apresentados do seguinte modo. Seja H uma matriz (n − k) × n, com entradas em 𝔽_{q}, do tipo H = [A, I_{n−k}], onde A é uma matriz (n − k) × k e I_{n−k} é a matriz identidade de ordem n − k. Os símbolos de controle c_{k+1}, …, c_{n} podem então ser determinados a partir do sistema de equações Hc^{T} = 0, onde 0 denota o vector nulo de 𝔽_{q}^{n−k}.

Exemplo: Seja H a seguinte matriz 3 × 7 sobre 𝔽_{2}:

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

O código definido por H será constituído pelas palavras c = a_{1}a_{2}a_{3}a_{4}c_{5}c_{6}c_{7}, onde os símbolos de controle c_{5}, c_{6}, c_{7} podem ser calculados resolvendo o sistema Hc^{T} = 0, dados a_{1}, a_{2}, a_{3}, a_{4}:

\{ \begin{matrix}a_{1} & & & + & a_{3} & + & a_{4} & + & c_{5} & & & & = & 0 \\ a_{1} & + & a_{2} & & & + & a_{4} & & & + & c_{6} & & = & 0 \\ a_{1} & + & a_{2} & + & a_{3} & & & & & & + & c_{7} & = & 0 \end{matrix}

Portanto,

\{ \begin{matrix}c_{5} = a_{1} + a_{3} + a_{4} \\ c_{6} = a_{1} + a_{2} + a_{4} \\ c_{7} = a_{1} + a_{2} + a_{3} \end{matrix}

pelo que c = (a_{1}, a_{2}, a_{3}, a_{4}, a_{1} + a_{3} + a_{4}, a_{1} + a_{2} + a_{4}, a_{1} + a_{2} + a_{3}). Assim, neste exemplo o esquema de codificação é a função linear de 𝔽_{2}^{4} em 𝔽_{2}^{7}, definida por

(a_{1}, a_{2}, a_{3}, a_{4}) ↦ (a_{1}, a_{2}, a_{3}, a_{4}, a_{1} + a_{3} + a_{4}, a_{1} + a_{2} + a_{4}, a_{1} + a_{2} + a_{3}),

e C é formado pelas 16 palavras

(a_{1}, a_{2}, a_{3}, a_{4}, a_{1} + a_{3} + a_{4}, a_{1} + a_{2} + a_{4}, a_{1} + a_{2} + a_{3}) a_{1}, a_{2}, a_{3}, a_{4} ∈ 𝔽_{2}.

Em geral, quando os esquemas de codificação são dados por aplicações lineares, usa-se a seguinte terminologia:

CÓDIGOS (n, k)-LINEARES Seja H = [A, I_{n−k}] uma matriz (n − k) × n com entradas em 𝔽_{q}. O conjunto C dos vectores n-dimensionais c ∈ 𝔽_{q}^{n} tais que Hc^{T} = 0 diz-se um código (n, k)-linear sobre 𝔽_{q}. A matriz H diz-se a matriz de controle de C. No caso q = 2, C diz-se um código binário.

          [Note que o conjunto C das soluç~ oes do sistema Hc^{T} = 0 de
                  equaç~ oes lineares é um subespaço de dimens~ ao k do
                                               espaço vectorial 𝔽_{q}^{n}]

Exemplos: Os códigos C_{2} e C_{3} da aula anterior são exemplos de códigos lineares. C_{2} é um código (4, 2)-linear sobre 𝔽_{2}, com matriz de controle

H_{2} = [ \begin{matrix}1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{matrix} ] ,

e C_{3} é um código (6, 2)-linear sobre 𝔽_{2}, com matriz de controle

H_{3} = [ \begin{matrix}1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 \end{matrix} ] .

Teorema. Um código (n, k)-linear com matriz de controle H tem distância mínima δ(C) ≥ s + 1 se e só se quaisquer s colunas de H são linearmente independentes.

Demonstração. “⇒” Suponhamos, por hipótese, que δ(C) ≥ s + 1. Se H tivesse s colunas, h_{i_{1}}, h_{i_{2}}, …, h_{i_{s}}, linearmente dependentes, teríamos

a_{i_{1}}h_{i_{1}} + a_{i_{2}}h_{i_{2}} + ⋯ + a_{i_{s}}h_{i_{s}} = 0

para alguns a_{i_{1}}, a_{i_{2}}, …, a_{i_{s}} ∈ 𝔽_{q} não todos nulos. Mas, então, a palavra c = c_{1}c_{2} ⋯ c_{n}, definida por

c_{j} = \{ \begin{matrix}0 & se j ∉ \{i_{1}, i_{2}, …, i_{s}\} \\ a_{i_{k}} & se existe k ∈ \{1, 2, …, s\} tal que j = i_{k} \end{matrix} ,

pertenceria a C, o que é uma contradição, pois d(c, 0) ≤ s.

“⇐” Suponhamos, por absurdo, que existem c, d ∈ C tais que d(c, d) ≤ s. Como C é linear, c − d ∈ C e, obviamente, d(c − d, 0) = d(c, d) ≤ s. Sejam x_{i_{1}}, x_{i_{2}}, …, x_{i_{r}} as r coordenadas (letras) da palavra c − d não nulas (r ≤ s). Como c − d ∈ C, então H(c − d)^{T} = 0, ou seja, h_{i_{1}}x_{i_{1}} + h_{i_{2}}x_{i_{2}} + ⋯ + h_{i_{r}}x_{i_{r}} = 0. Mas isto significa que as r colunas h_{i_{1}}, h_{i_{2}}, …, h_{i_{r}} de H são linearmente dependentes, o que é absurdo por hipótese.

Exemplos: Na matriz H_{2} acima, s = 1, uma vez que há duas colunas linearmente dependentes (a primeira e a terceira, por exemplo). Na matriz H_{3}, quaisquer duas colunas são linearmente independentes mas as colunas 1, 3 e 5 são linearmente dependentes, pelo que s = 2.

Vimos na aula anterior que, depois de recebida uma palavra y pelo receptor, a sua descodificação, isto é, a determinação da palavra exacta c que lhe deu origem (isto é, a palavra enviada pelo emissor), pode ser feita determinando a palavra de C que está mais próxima de y (princípio do vizinho mais próximo). Claro que isto pode ser feito por “força bruta”, determinando a distância de Hamming entre y e \underline{todas} as palavras de C. Mas isto é impraticável quando |C| é muito grande!

Em vez da força bruta, pode usar-se uma abordagem através da matriz H. Para isso, consideremos o espaço vectorial 𝔽_{q}^{n}/C formado por todas as classes

a + C := {a + c : c ∈ C}

com a ∈ 𝔽_{q}^{n}. Cada classe contém q^{k} palavras e 𝔽_{q}^{n} pode particionar-se em s + 1 = q^{n−k} classes de C:

𝔽_{q}^{n} = (0 + C) ∪ (a^{(1)} + C) ∪ ⋯ ∪ (a^{(s)} + C).

A palavra recebida y tem que estar nalguma das classes, digamos a^{(i)} + C, pelo que y = a^{(i)} + d para algum d ∈ C. Se c foi a palavra transmitida, então o erro é dado por e = y − c = a^{(i)} + d − c ∈ a^{(i)} + C. Portanto, o erro e pertence à mesma classe da palavra y recebida. Assim, pelo princípio do vizinho mais próximo, para determinar o erro e, e consequentemente a palavra original y − e, bastará determinar o líder da classe de y:

PESO DE UMA PALAVRA; LÍDER DE UMA CLASSE O peso (de Hamming) de c ∈ 𝔽_{q}^{n} é o número de coordenadas não-nulas de c. Por outras palavras, o peso de c ∈ 𝔽_{q}^{n} é a distância d(c, 0). Um elemento de peso mínimo numa classe a + C chama-se um líder de a + C.

É claro que se houver mais do que um líder na classe de y o erro não poderá ser corrigido, uma vez que o receptor não conseguirá decidir qual dos lideres será o vector erro e. Por exemplo, no código (4, 2)-linear binário C com matriz de controle

( \begin{matrix}1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{matrix} ) ,

a lista das 4 classes deste código é a seguinte:

classe 0 + C = C:  0000 1010 0111 1101

outras classes: \{ \begin{matrix}1000 & 0010 & 1111 & 0101 \\ 0100 & 1110 & 0011 & 1001 \\ 0001 & 1011 & 0110 & 1100 \end{matrix}

A classe na segunda linha tem dois lideres: 1000 e 0010. Por exemplo, se a palavra recebida for a palavra y = 1111 que está na segunda classe, o vector erro tanto pode ser 1000 como 0010, ou seja, a palavra original pode bem ter sido a palavra 0111 ou 1101. Isto acontece porque δ(C) = 2 e, portanto, o código não corrige todos os erros singulares. Se a palavra y recebida for a palavra 1110 na terceira classe, o erro só poderá ser igual a 0100 e, portanto, o receptor descobre imediatamente o erro: a palavra original só pode ter sido a palavra 1010.

        [Se no canal de comunicaç~ ao só ocorrerem no máximo t erros e
   δ(C) ≥ 2t + 1 (portanto C corrige sempre os t eventuais erros), n~ ao
     poder~ ao existir dois lideres e_{1} e e_{2} na mesma classe; de facto,
     se tal fosse possível, c_{1} := y − e_{1} e c_{2} := y − e_{2} seriam palavras

de C tais que d(c_{1}, c_{2}) ≤ d(c_{1}, y) + d(y, c_{2}) = d(e_{1}, 0) + d(e_{2}, 0) ≤ t + t,

                           uma contradiç~ ao com o facto δ(C) ≥ 2t + 1]

A classe de cada y pode ser determinada calculando a sua síndrome:

SÍNDROME DE UMA PALAVRA O vector S(c) = Hc^{T} de comprimento n − k chama-se a síndrome de c ∈ 𝔽_{q}^{n}.

Proposição.

(1) S(c) = 0 se e só se c ∈ C.

(2) S(c) = S(d) se e só se c + C = d + C.

Demonstração. (1) É imediato da definição de C em termos de H.

(2) S(c) = S(d) ⇔ Hc^{T} = Hd^{T} ⇔ H(c − d)^{T} = 0 ⇔ c − d ∈ C ⇔ c + C = d + C.

No exemplo anterior,

palavras de C:  0000 1010 0111 1101 \binom{0}{0}

outras classes: \{ \begin{matrix}1000 & 0010 & 1111 & 0101 & \binom{1}{0} \\ 0100 & 1110 & 0011 & 1001 & \binom{1}{1} \\ 0001 & 1011 & 0110 & 1100 & \underbrace{\binom{0}{1}}_{Síndromes} \end{matrix}

ALGORITMO DE DESCODIFICAÇÃO Dados: palavra y recebida.

(1) Calcular S(y).

(2) Determinar o líder e tal que S(e) = S(y).

(3) A palavra original é a palavra c = y − e.

Exemplo: Consideremos o código do exemplo anterior. Se y = 1110 é recebida, começamos por determinar S(y) = Hy^{T} = \binom{1}{1}. O erro e será então igual ao líder da respectiva classe, ou seja, a 0100. A palavra original era então igual a y − e = 1010.

Em códigos lineares muito grandes é praticamente impossível listar todas as classes e determinar os respectivos lideres; por exemplo, um código (50, 20)-linear binário tem aproximadamente 10^{9} classes. Nesse caso, determina-se directamente o líder da classe da palavra y, determinando a palavra e de menor peso tal que He^{T} = S(y). No exemplo acima,

He^{T} = \binom{1}{1} ⇔ ( \begin{matrix}1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{matrix} ) ( \begin{matrix}e_{1} \\ e_{2} \\ e_{3} \\ e_{4} \end{matrix} ) = \binom{1}{1} ⇔ \{ \begin{matrix}e_{1} + e_{3} = e_{4} \\ e_{2} = 1 + e_{4} \end{matrix} ⇔

⇔ e = (0100) ∨ e = (1110) ∨ e = (0011) ∨ e = (1110).

O vector (0100) é o que tem menor peso, pelo que e = (0100).