Códigos de bloco

O problema de codificação de canal

Considere o modelo de comunicação abaixo.

No modelo, a informação consiste em uma sequência de bits, aqui assumidos independentes e equiprováveis. Essa informação deve ser transmitida através de um canal de comunicação, modelado por um sistema estocástico que tem em sua entrada e em sua saída sequências de números complexos.

Para possibilitar a comunicação, é necessário realizar codificação de canal. No transmissor, o codificador de canal é responsável por mapear os bits de informação na sequência complexa que será a entrada do canal. No receptor, o decodificador de canal é responsável por mapear a sequência complexa obtida na saída do canal em uma estimativa dos bits de informação.

Uma possível abordagem para o problema de codificação de canal consiste na separação em duas camadas: controle de erros e modulação. Nesse caso, o codificador de canal é composto por um codificador binário seguido de um modulador, enquanto o decodificador de canal é composto por um demodulador seguido de um decodificador binário.

O codificador binário recebe como entrada uma sequência de bits e gera como saída outra sequência de bits. Seu papel é inserir redundância na informação de modo a facilitar a correção de erros no receptor. O decodificador binário, por sua vez, recebe como entrada uma sequência de bits (que pode ser encarada como sendo a sequência na saída do codificador binário, mas com alguns bits trocados) e tem como objetivo estimar os bits de informação originais, explorando a redundância inserida pelo codificador. Note que a cascata modulador–canal–demodulador pode ser abstraída como um canal de comunicação que tem como entrada e saída sequências de bits.

É importante destacar que a separação entre controle de erros e modulação nem sempre é a melhor solução para o problema de codificação de canal. Em muitos casos, especialmente quando há limitação de largura de banda, controle de erros e modulação são realizados conjuntamente em uma técnica conhecida como modulação codificada.

Códigos de bloco

Na codificação de bloco, a informação é segmentada em blocos de $k$ bits, que são mapeados em blocos de $n$ bits pelo codificador. Como o código deve inserir redundância na informação, deve-se ter $n > k$. O parâmetro $R = k/n$ é chamado de taxa de codificação e indica a quantidade de bits de informação por bit transmitido.

Utiliza-se a nomenclatura “código $(n, k)$” para se referir a um código de bloco com $n$ bits na saída do codificador e $k$ bits na entrada.

Adotando a separação controle-de-erros–modulação descrita acima, obtém-se o diagrama de bloco a seguir, em que o canal binário pode ser modelado como uma soma módulo 2 (xor) elemento-a-elemento entre a palavra-código e um padrão de erro. O padrão de erro é uma sequência de $n$ bits contendo $\bit{1}$ nas posições em que ocorreu troca de bit e $\bit{0}$ nas demais posições.

Exemplos

Exemplo. Código de Hamming $(7, 4)$

O código de Hamming $(7,4)$ foi proposto por Richard W. Hamming em 1950. O codificador mapeia uma mensagem de quatro bits

\[ u = [u_1 ~~ u_2 ~~ u_3 ~~ u_4] \]

em uma palavra-código de sete bits

\[ v = [v_1 ~~ v_2 ~~ v_3 ~~ v_4 ~~ v_5 ~~ v_6 ~~ v_7] = [u_1 ~~ u_2 ~~ u_3 ~~ u_4 ~~ p_1 ~~ p_2 ~~ p_3], \]

onde os bits de paridade $p_1$, $p_2$, $p_3$ são escolhidos de modo que a paridade de cada um dos círculos abaixo seja par.

Richard W. Hamming (1915–1998). Copyright by Nokia Bell Labs. Fonte: PSD Trailblazers (The University of Chicago).

A decodificação é feita da seguinte forma. Calcule as paridades dos círculos e verifique se são todas pares. Se sim, declare que não houve erro. Senão, identifique qual dos bits foi trocado e inverta-o.

Solução.

A tabela de codificação tem $2^4 = 16$ entradas e é mostrada abaixo.

$u$	$v$
$\bit{0000}$	$\bit{0000000}$
$\bit{0001}$	$\bit{0001111}$
$\bit{0010}$	$\bit{0010011}$
$\bit{0011}$	$\bit{0011100}$
$\bit{0100}$	$\bit{0100101}$
$\bit{0101}$	$\bit{0101010}$
$\bit{0110}$	$\bit{0110110}$
$\bit{0111}$	$\bit{0111001}$
$\bit{1000}$	$\bit{1000110}$
$\bit{1001}$	$\bit{1001001}$
$\bit{1010}$	$\bit{1010101}$
$\bit{1011}$	$\bit{1011010}$
$\bit{1100}$	$\bit{1100011}$
$\bit{1101}$	$\bit{1101100}$
$\bit{1110}$	$\bit{1110000}$
$\bit{1111}$	$\bit{1111111}$

Como exemplo, suponha que a mensagem seja $u = \bit{1011}$. O codificador mapeia $u$ em $v = \bit{1011010}$, de acordo com a figura abaixo.

A tabela de decodificação tem 128 entradas e não será mostrada aqui. Como exemplo, suponha que seja transmitido $v = \bit{1011010}$, mas que haja troca de bit na terceira posição, de modo que a palavra recebida seja $b = \bit{1001010}$. A figura abaixo mostra os bits de $b$ dispostos nos círculos.

Os dois círculos de baixo possuem paridade ímpar (incorreta), enquanto o círculo de cima possui paridade par (correta). Portanto, o bit que deve ser invertido é $b_3$. Assim, a mensagem estimada é $\hat{u} = \bit{1001}$.

Se houver uma única troca de bit pelo canal, qualquer que seja a posição, o código é capaz de corrigir o erro. A taxa de codificação é $R = 4/7$.

Códigos sistemáticos

Uma vantagem dos códigos sistemáticos é que a recuperação da mensagem a partir da palavra-código é trivial: basta descartar os bits de paridade.

Os três exemplos vistos anteriormente — código de repetição $(3, 1)$, código de paridade simples $(3, 2)$ e código de Hamming $(7, 4)$ — são exemplos de códigos sistemáticos (por quê?).

Códigos de bloco lineares

Nesta seção serão apresentados os conceitos básicos da teoria de códigos de bloco lineares. Neste contexto, o parâmetro $n$ é chamado de comprimento do código e o parâmetro $k$ é chamado de dimensão do código.

Como consequência, temos que a palavra nula é sempre uma palavra-código.

Matriz geradora

Os outros três exemplos vistos anteriormente são também exemplos de códigos lineares. A seguir, são apresentadas as matrizes geradoras desses códigos.

Exemplo. Código de Hamming $(7, 4)$

Determine a matriz geradora do código de Hamming $(7, 4)$.

Solução.

Da descrição do código, sabemos que a mensagem $u = [u_1 ~~ u_2 ~~ u_3 ~~ u_4]$ é mapeada na palavra-código $v$ da seguinte forma:

\[ v = \big[ v_1 ~~ v_2 ~~ v_3 ~~ v_4 ~~ v_5 ~~ v_6 ~~ v_7 \big] = \big[ u_1 ~~ u_2 ~~ u_3 ~~ u_4 ~~ p_1 ~~ p_2 ~~ p_3 \big], \]

em que os bits de paridade $p_1$, $p_2$, $p_3$ são escolhidos de modo que a paridade de cada um dos círculos abaixo seja par.

Assim, temos que

\[ \begin{cases} v_1 ~ = ~ u_1, \\ v_2 ~ = ~ u_2, \\ v_3 ~ = ~ u_3, \\ v_4 ~ = ~ u_4, \end{cases} \qquad \text{e} \qquad \begin{cases} p_1 + u_1 + u_2 + u_4 ~ = ~ \bit{0}, \\ p_2 + u_1 + u_3 + u_4 ~ = ~ \bit{0}, \\ p_3 + u_2 + u_3 + u_4 ~ = ~ \bit{0}, \\ \end{cases} \]

Isolando os bits de paridade e substituindo $v_5 = p_1$, $v_6 = p_2$ e $v_7 = p_3$, obtemos

\[ \begin{cases} v_5 ~ = ~ u_1 + u_2 + u_4, \\ v_6 ~ = ~ u_1 + u_3 + u_4, \\ v_7 ~ = ~ u_2 + u_3 + u_4. \end{cases} \]

Portanto,

\[ \begin{aligned} v & = \big[ v_1 ~~ v_2 ~~ v_3 ~~ v_4 ~~ v_5 ~~ v_6 ~~ v_7 \big] \\ & = \big[ u_1 ~~~~~ u_2 ~~~~~ u_3 ~~~~~ u_4 ~~~~~ u_1 \! + \! u_2 \! + \! u_4 ~~~~~ u_1 \! + \! u_3 \! + \! u_4 ~~~~~ u_2 \! + \! u_3 \! + \! u_4 \big] \\ & = \big[ u_1 ~~ u_2 ~~ u_3 ~~ u_4 \big] \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix} = u G, \end{aligned} \]

de modo que a matriz geradora é dada por

\[ G = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix} . \]

Note que no caso de códigos de bloco sistemáticos, a matriz geradora possui a matriz identidade $k \times k$ como submatriz.

Matriz verificadora

Seja $m = n - k$ a redundância do código.

Relação entre as matrizes geradora e verificadora

As matrizes $G$ e $H$ estão relacionadas pela equação

De modo geral, uma matriz pode ser obtida a partir da outra através de eliminação gaussiana. No caso particular de códigos sistemáticos, temos o seguinte resultado.

A seguir serão determinadas as matrizes verificadoras dos códigos de repetição $(3, 1)$, de paridade simples $(3, 2)$ e de Hamming $(7, 4)$.

Exemplo. Código de Hamming $(7, 4)$

Determine a matriz verificadora do código de Hamming $(7, 4)$.

Solução.

Aqui, a redundância é $m = 3$ e a matriz geradora é dada por

\[ G = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix} = \big[ I_4 ~~ P \big], \]

onde

\[ P = \begin{bmatrix}1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1\end{bmatrix}. \]

Portanto, a matriz verificadora é dada por

\[ H = \big[ P^\transpose ~~ I_3 \big] = \begin{bmatrix}1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1\end{bmatrix}. \]

De fato, temos que

\[ \begin{align*} \text{$v$ é palavra-código} \quad \iff \quad & H v^\transpose = 0 \\ \quad \iff \quad & \begin{bmatrix}1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1\end{bmatrix} \begin{bmatrix}v_1 \\ v_2 \\ \vdots \\ v_7\end{bmatrix} = \begin{bmatrix}0 \\ 0 \\ 0\end{bmatrix} \\ \quad \iff \quad & \begin{cases} v_1 + v_2 + v_4 + v_5 ~ = ~ 0, \\ v_1 + v_3 + v_4 + v_6 ~ = ~ 0, \\ v_2 + v_3 + v_4 + v_7 ~ = ~ 0, \end{cases} \\ \quad \iff \quad & \text{a paridade de cada círculo abaixo é par.} \end{align*} \]

Isso está de acordo com a definição do código de Hamming $(7, 4)$.

Propriedades de um código linear

A distância de Hamming entre duas palavras binárias de mesmo comprimento é definida como o número de posições em que os bits correspondentes são diferentes. O peso de Hamming de uma palavra binária é o número de bits iguais a $\bit{1}$. Neste apontamento, a distância de Hamming é denotada por $\dH(\cdot, \cdot)$ e o peso de Hamming é denotado por $\wH(\cdot)$.

Distância mínima e distribuição de peso das palavras-código

Pode-se mostrar que, no caso de códigos de bloco lineares, a distância mínima é dada pelo menor peso de Hamming entre todas as palavras-código não-nulas.

A distribuição de peso das palavras-código satisfaz $A_0 + A_1 + \cdots + A_n = 2^k$ e, além disso, é tal que

• $A_0 = 1$,
• $A_i = 0$ para $1 \leq i \leq \dmin \! - \! 1$, e
• $A_{\dmin} > 0$.

Decodificação de mínima distância e capacidade de correção de erros

Relembrando o diagrama de blocos do modelo de comunicação considerado.

Uma forma de decodificar um código de bloco é através da decodificação de mínima distância.

Utilizando decodificação de mínima distância, pode-se mostrar o seguinte resultado, que é válido para códigos de bloco em geral (não necessariamente lineares). No que segue, $\lfloor x \rfloor$ denota o maior inteiro menor ou igual a $x$.

Família dos códigos de Hamming

Os códigos de Hamming são obtidos a partir da seguinte construção, baseada na matriz verificadora.

O código de Hamming de ordem $m$ possui os seguintes parâmetros:

• Para $m=2$, a matriz verificadora é dada por

  \[ H = \begin{bmatrix} ~1 & 1 & 0~ \\ ~1 & 0 & 1~ \end{bmatrix}. \]

  Portanto, o código de Hamming de ordem $2$ é o código de repetição $(3, 1)$.

• Para $m=3$, a matriz verificadora é dada por

  \[ H = \begin{bmatrix} ~1 & 1 & 0 & 1 & 1 & 0 & 0~ \\ ~1 & 0 & 1 & 1 & 0 & 1 & 0~ \\ ~0 & 1 & 1 & 1 & 0 & 0 & 1~ \end{bmatrix}. \]

  Portanto, o código de Hamming de ordem $3$ é o código de Hamming $(7, 4)$.

• Para $m=4$, a matriz verificadora é dada por

  \[ H = \begin{bmatrix} ~1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0~ \\ ~1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0~ \\ ~0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0~ \\ ~0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1~ \end{bmatrix}. \]

  Este é o código de Hamming $(15, 11)$.

Arranjo padrão e síndrome

Arranjo padrão

O conjunto de todas as palavras binárias de $n$ bits constitui um grupo sob a operação de adição binária. As palavras-código de um código linear, por sua vez, formam um subgrupo desse grupo. Da teoria de grupos, sabe-se que um grupo pode ser particionado em cosets de um subgrupo, em que cada coset é uma translação do subgrupo. Com base nessa observação, é possível definir o conceito de arranjo padrão.

Definição. Arranjo padrão

O arranjo padrão de um código de bloco linear é uma tabela com $2^m$ linhas e $2^k$ colunas, em que:

• A primeira linha contém todas as palavras-código, com a palavra-código nula na primeira posição.
• Cada linha é um coset do subgrupo de palavras-código, em que o elemento na primeira posição, chamado de representante (ou líder), possui peso mínimo dentro do coset.

David Slepian teaching Information Theory. CC BY-SA 4.0 by Don Slepian. Fonte: Wikimedia Commons.

No contexto de códigos corretores de erro, os representantes dos cosets são os padrões de erro corrigíveis. Se os representantes de menor peso são escolhidos, o arranjo padrão fornece uma maneira de implementar decodificação de mínima distância: ao receber uma palavra $b$, selecione a palavra-código $\hat{v}$ que se encontra na mesma coluna de $b$.

A distribuição de peso dos padrões de erro corrigíveis satisfaz $\alpha_0 + \alpha_1 + \cdots + \alpha_n = 2^m$ e, além disso, é tal que

onde $t$ é a capacidade de correção de erros do código. Códigos em que $\alpha_i = 0$ para $t \! + \! 1 \leq i \leq n$ são chamados de códigos perfeitos.

Síndrome

A síndrome $s$ não depende da palavra-código $v$, mas apenas do padrão de erro $e$:

O diagrama de blocos abaixo ilustra o processo de decodificação via síndrome.

O bloco indicado por $s \mapsto \hat{e}$ pode ser implementado de diferentes formas. Para códigos com um valor reduzido de $m$, é viável armazenar uma tabela na memória. Já para códigos com $m$ elevado, torna-se necessário o uso de algoritmos que calculam $\hat{e}$ a partir de $s$, os quais dependem das propriedades algébricas do código.

Modelo probabilístico

Considere o diagrama de blocos a seguir. Nesta seção, adotamos um modelo probabilístico para o problema, onde letras maiúsculas denotam variáveis aleatórias.

Iremos assumir as seguintes hipóteses:

• Os bits da mensagem, $U_1, U_2, \ldots, U_k$, são independentes e equiprováveis. Equivalentemente, a mensagem $U$ é selecionada uniformemente sobre o conjunto de todas as palavras de $k$ bits.

• Os bits do padrão de erro, $E_1, E_2, \ldots,E_n$, são independentes com $\Pr[E_i = \bit{1}] = p$, em que $p$ é chamado de probabilidade de inversão de bit do canal. Assume-se $p < 1/2$ (o caso $p > 1/2$ pode ser convertido em $p < 1/2$ invertendo os bits da palavra recebida).

  

  Este modelo é conhecido como canal binário simétrico (BSC, do inglês binary symmetric channel). O canal é dito ser sem memória no sentido de que cada transmissão é independente das outras.

O decodificador pode ser projetado de acordo com dois critérios [MacKay, p. 324]:

• Problema da decodificação de palavra: Em sua forma mais geral, consiste em determinar a distribuição de probabilidade condicional da mensagem $U$, dada a palavra recebida $B$.
• Problema da decodificação bit-a-bit: Em sua forma mais geral, consiste em determinar a distribuição de probabilidade condicional de cada bit $U_i$ da mensagem, dada a palavra recebida $B$.

As distribuições condicionais mencionadas acima são chamadas de distribuições a posteriori.

Bayes’ Theorem. Fonte: Wikimedia Commons.

Decodificação MAP

A solução completa do problema de decodificação de palavra consiste em listar todas as mensagens possíveis juntamente com suas respectivas probabilidades. No entanto, dado que o número de mensagens ($2^k$) é geralmente grande e não estamos interessados nas probabilidades detalhadas de cada uma, muitas vezes consideramos uma versão simplificada do problema [MacKay, p. 325]. Essa versão é aqui chamada de decodificação MAP de palavra (do inglês maximum a posteriori):

Embora a decodificação MAP de palavra forneça a mensagem mais provável como um todo, em algumas aplicações podemos estar interessados em determinar o bit mais provável em cada posição. Isso motiva a introdução de uma estratégia alternativa de decodificação, aqui chamada de decodificação MAP bit-a-bit.

A saída do decodificador MAP de palavra não necessariamente coincide com a do decodificador MAP bit-a-bit. Isso é ilustrado no exemplo a seguir.

Portanto, o decodificador MAP de palavra minimiza a probabilidade de erro de palavra, mas não necessariamente minimiza a probabilidade de erro de bit. Para isso, é necessário o decodificador MAP bit-a-bit.

Desempenho de códigos de bloco

Nesta seção, damos continuidade ao modelo probabilístico adotado previamente, mantendo as mesmas hipóteses: mensagens equiprováveis e canal BSC sem memória.

Probabilidade de erro de palavra

A seguir, define-se a probabilidade de erro de palavra.

Perceba que a probabilidade definida acima depende do decodificador utilizado.

Decodificação de mínima distância. A decodificação de mínima distância de Hamming é ótima no sentido de minimizar a probabilidade de erro de palavra (pois coincide com o decodificador MAP de palavra). O exemplo a seguir ilustra como calcular $\Pword$ nesse caso.

O teorema a seguir generaliza esse exemplo para códigos de bloco lineares arbitrários [MacWilliams–Sloane, p. 18].

Decodificação de distância limitada. Muitos algoritmos de decodificação implementam a chamada decodificação de distância limitada (bounded distance decoding, em inglês). Nesse caso, o decodificador retorna a palavra-código mais próxima da palavra recebida, desde que a distância seja menor ou igual a $t$ (a capacidade de correção de erros do código); caso contrário, o decodificador retorna um erro.

Probabilidade de erro de bit

Quando o decodificador retorna uma mensagem incorreta, ainda é possível que alguns dos bits decodificados estejam corretos.

Agora, a decodificação de mínima distância não é mais necessariamente ótima, como já vimos.

Decodificação de mínima distância. Apesar de não necessariamente ser ótima, a decodificação de mínima distância de Hamming é frequentemente utilizada na prática. O exemplo a seguir ilustra o cálculo de $\Pbit$ nesse caso.

O teorema a seguir generaliza esse exemplo para códigos de bloco lineares arbitrários [MacWilliams–Sloane, p. 20].

Decodificação MAP bit-a-bit. O esquema de decodificação que minimiza a probabilidade de erro de bit é o decodificador MAP bit-a-bit apresentado anteriormente.

Bibliografia

1. Shu Lin; Daniel J. Costello, Jr.: Error Control Coding, 2nd edition, Pearson Education, 2004.
2. Simon Haykin: Communication Systems, 4th edition, John Wiley & Sons, 2001.
3. David J. C. MacKay: Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003.
4. F. J. MacWilliams; N. J. A. Sloane: The Theory of Error-Correcting Codes, North-Holland, 1977.