Códigos convolucionais

Introdução

Códigos convolucionais foram propostos por Peter Elias em 1955 como uma alternativa aos códigos de bloco e podem ser vistos como uma generalização de códigos de bloco lineares, em que os bits de saída de um determinado bloco dependem dos bits de entrada desse bloco e de um número limitado de blocos anteriores. Mais precisamente:

v_t = u_t G_0 + u_{t-1} G_1 + \cdots + u_{t-\mu} G_\mu = \sum_{i=0}^\mu u_{t-i} G_i,

onde $\mu$ é a ordem de memória do código e $G_0, G_1, \ldots, G_\mu$ são matrizes geradoras.

Peter Elias (1923–2001). Créditos: MIT Museum.

Códigos de bloco lineares:

\[ v_t = u_t G \]

Códigos convolucionais (exemplo com $\mu = 2$):

\[ v_t = u_t G_0 + u_{t-1} G_1 + u_{t-2} G_2 \]

A notação “$(n, k, \mu)$” é utilizada para denotar um código convolucional com $n$ bits de saída, $k$ bits de entrada e ordem de memória $\mu$. Assume-se que as sequências de informação e codificada são infinitas, de modo que a taxa de codificação é dada por $R = k/n$.

Ideia: Melhorar as propriedades do código aumentando $\mu$, mantendo $k$ e $n$ pequenos.

Notação: Neste apontamento, subscritos indicam o tempo e sobrescritos entre parênteses indicam o índice do bit. Por exemplo, $u_t^{(i)}$ é o $i$-ésimo bit da mensagem no tempo $t$. Além disso, por convenção, será utilizada indexação começando em $0$.

Exemplo. Código convolucional $(3, 2, 1)$

Considere um código convolucional com

\[ G_0 = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} \quad\text{e}\quad G_1 = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \end{bmatrix}. \]

Note que $n = 3$, $k = 2$, $\mu = 1$.

Determine os elementos de $v_t$ em termos dos elementos de $u_t$, $u_{t-1}$.
Esboce o diagrama de blocos correspondente.
Codifique a sequência de informação $u = \bit{01~11~10}\ldots$

Solução.

Tem-se \[ \begin{aligned} v_t & = u_t G_0 + u_{t-1} G_1 \\[1.5ex] & = \big[ u_t^{(0)} ~~~ u_t^{(1)} \big] \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} ~~ + ~~ \big[ u_{t-1}^{(0)} ~~~ u_{t-1}^{(1)} \big] \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \end{bmatrix} \\[3ex] & = \big[ u_t^{(0)} \quad u_t^{(1)} \quad u_t^{(0)} + u_t^{(1)} \big] ~~ + ~~ \big[ u_{t-1}^{(0)} + u_{t-1}^{(1)} \quad u_{t-1}^{(0)} \quad u_{t-1}^{(0)} \big] \\[2ex] & = \big[ \underbrace{u_t^{(0)} + u_{t-1}^{(0)} + u_{t-1}^{(1)}}_{v_t^{(0)}} \quad \underbrace{u_t^{(1)} + u_{t-1}^{(0)}}_{v_t^{(1)}} \quad \underbrace{u_t^{(0)} + u_t^{(1)} + u_{t-1}^{(0)}}_{v_t^{(2)}} \big]. \end{aligned} \]
O diagrama de blocos correspondente é mostrado abaixo.
A sequência codificada é $v = 011~010~110 \ldots$.

Exemplo. Código convolucional $(2, 1, 2)$

Considere um código convolucional com

\[ G_0 = \big[ 1 ~~~ 1 \big], \quad G_1 = \big[ 1 ~~~ 0 \big], \quad G_2 = \big[ 1 ~~~ 1 \big]. \]

Note que $n = 2$, $k = 1$, $\mu = 2$.

Determine os elementos de $v_t$ em termos dos elementos de $u_t$, $u_{t-1}$, $u_{t-2}$.
Esboce o diagrama de blocos correspondente.
Codifique a sequência de informação $u = \bit{1~0~1~1~0}\ldots$

Solução.

Tem-se \[ \begin{aligned} v_t & = u_t G_0 + u_{t-1} G_1 + u_{t-2} G_2 \\[1.5ex] & = \big[ u_t^{(0)} \big] \big[ 1 ~~~ 1 \big] ~~ + ~~ \big[ u_{t-1}^{(0)} \big] \big[ 1 ~~~ 0 \big] ~~ + ~~ \big[ u_{t-2}^{(0)} \big] \big[ 1 ~~~ 1 \big] \\[1.5ex] & = \big[ u_t^{(0)} ~~~ u_t^{(0)} \big] ~~ + ~~ \big[ u_{t-1}^{(0)} ~~~ 0 \big] ~~ + ~~ \big[ u_{t-2}^{(0)} ~~~ u_{t-2}^{(0)} \big] \\[1.5ex] & = \big[ \underbrace{u_t^{(0)} + u_{t-1}^{(0)} + u_{t-2}^{(0)}}_{v_t^{(0)}} \quad \underbrace{u_t^{(0)} + u_{t-2}^{(0)}}_{v_t^{(1)}} \big]. \end{aligned} \]
O diagrama de blocos correspondente é mostrado abaixo.
A sequência codificada é $v = \bit{11~10~00~01~01}\ldots$

Observação: Os códigos dos exemplos são não-sistemáticos.

Diagrama de estados

Os estados são as saídas dos blocos de atraso. Assim sendo, o número de estados é $2^\nu$, onde $\nu$ é o número de blocos de atraso, também chamado de comprimento de restrição do código.

Exemplo.

Determine o diagrama de estados do código $(2,1,2)$ do exemplo anterior e codifique novamente a sequência de informação $u = \bit{1~0~1~1~0}\ldots$.

Solução.

O diagrama de estados é mostrado abaixo, em que convenciona-se que linha cheia representa bit de entrada $\bit{0}$ e linha tracejada representa bit de entrada $\bit{1}$.

Iniciando no estado $00$ e seguindo o diagrama, a sequência codificada é $v = \bit{11~10~00~01~01}\ldots$.

Terminação de códigos convolucionais

Na prática, a sequência de informação $u$ não é infinita. Técnicas de terminação são necessárias, transformando um código convolucional $(n, k, \mu)$ em um código de bloco $(n', k')$.

Se um total de $h$ blocos de informação (cada qual contento $k$ bits) são codificados, então a dimensão do código de bloco resultante é dada por $k' = hk$. No entanto, o comprimento $n'$ depende da técnica de terminação utilizada.

Terminação por truncamento direto

O codificador sempre inicia no estado zero e sua saída termina imediatamente após o último bloco de informação. O codificador não necessariamente termina no estado zero. Nesse caso, o comprimento do código de bloco resultante é dado por $n' = hn$, de modo que a taxa de codificação é dada por

\[ R' = \frac{k'}{n'} = \frac{hk}{hn} = \frac{k}{n} = R, \]

em que $R$ é a taxa do código convolucional. Este método tem a desvantagem de que os bits do final da mensagem terão maior probabilidade de erro que os demais.

Exemplo com $(n, k, \mu) = (3, 2, 2)$ e $h = 5$ blocos de informação. O código de bloco resultante tem $(n', k') = (15, 10)$.

Exemplo.

Considere novamente o código convolucional $(2,1,2)$ do exemplo anterior. Suponha que seja empregada terminação por truncamento direto com $h = 5$ blocos de informação. Determine os parâmetros (dimensão e comprimento) do código de bloco resultante e codifique a mensagem $u = \bit{1~0~1~1~0}$.

Solução.

A dimensão do código de bloco resultante é

\[ k' = hk = 5 \cdot 1 = 5 \]

e o comprimento é

\[ n' = hn = 5 \cdot 2 = 10. \]

Do exemplo anterior, tem-se que a palavra-código resultante é $v = \bit{11~10~00~01~01}$.

Terminação no estado zero

O codificador sempre inicia e termina no estado zero. Para isso, é necessário adicionar uma cauda ao final dos bits de informação, que no caso de códigos sem feedback é simplesmente uma sequência de $\mu k$ zeros.

Exemplo com $(n, k, \mu) = (3, 2, 2)$ e $h = 5$ blocos de informação. O código de bloco resultante tem $(n', k') = (21, 10)$.

O tamanho da mensagem + cauda é portanto $hk + \mu k = (h + \mu)k$, de modo que o comprimento do código de bloco resultante é dado por $n' = (h + \mu)n$. Assim, a taxa de codificação é dada por

\[ R' = \frac{k'}{n'} = \frac{hk}{(h + \mu)n} = \frac{h}{h + \mu} R, \]

em que $R$ é a taxa do código convolucional. Com a terminação no estado zero, o problema da proteção desigual dos bits é resolvido, mas às custas de uma redução na taxa de codificação. No entanto, a taxa efetiva ($R'$) se aproxima da original ($R$) à medida que $h$ cresce.

Exemplo.

Considere novamente o código convolucional $(2,1,2)$ do exemplo anterior. Suponha que seja empregada terminação no estado zero com $h = 5$ blocos de informação. Determine os parâmetros (dimensão e comprimento) do código de bloco resultante e codifique a mensagem $u = \bit{1~0~1~1~0}$.

Solução.

A dimensão do código de bloco resultante continua sendo

\[ k' = hk = 5 \cdot 1 = 5 \]

mas o comprimento é agora

\[ n' = (h + \mu)n = (5 + 2) \cdot 2 = 14. \]

Antes de codificar a mensagem $u = \bit{1~0~1~1~0}$, é necessário adicionar a cauda, que neste caso corresponde a $\mu k = 2$ zeros. Assim,

\[ u_\text{cauda} = \bit{1~0~1~1~0~0~0}. \]

A partir do diagrama de estados, obtemos a palavra-código $v = \bit{11~10~00~01~01~11~00}$.

Terminação por tail-biting

O codificador sempre inicia e termina no mesmo estado. Esta técnica proporciona proteção uniforme de erros sem diminuição na taxa, mas às custas de uma maior complexidade computacional. Os detalhes não serão abordados aqui.

Algoritmo de Viterbi

Existem inúmeros algoritmos (ótimos e sub-ótimos) para a decodificação de códigos convolucionais. Aqui, abordaremos o mais famoso deles, o algoritmo de Viterbi (1967). O algoritmo de Viterbi é ótimo no sentido de que, dada a sequência de bits recebida, ele encontra a sequência de estados mais provável (equivalentemente, minimiza a probabilidade de erro de palavra-código). O algoritmo de Viterbi pode ser utilizado tanto em HDD (hard-decision decoding) quanto em SDD (soft-decision decoding).

Observação: O algoritmo de Viterbi possui diversas aplicações, não se limitando apenas à decodificação de códigos convolucionais. Em sistemas de comunicação, ele também é empregado na decodificação de códigos de bloco e no problema de equalização de canal, por exemplo.

O algoritmo de Viterbi será aqui apresentado através de um exemplo.

Exemplo.

Considere novamente o código convolucional $(2,1,2)$ cujo diagrama de estados é mostrado abaixo.

Suponha que seja empregada terminação no estado zero com $h = 5$ blocos de informação e que a sequência de bits recebida seja

\[ b = \bit{11~11~01~01~01~11~10}. \]

Determine os bits de informação decodificados pelo algoritmo de Viterbi.

Solução.

A treliça correspondente ao diagrama de estados é mostrada abaixo.

Portanto,

\[ \begin{aligned} \hat{v} ~~~ & = ~~~ \bit{11~10~00~01~01~11~00} \quad \text{($3$ erros)} \\ \hat{u}_\text{cauda} ~~~ & = ~~~ \bit{1~0~1~1~0~0~0} \\ \hat{u} ~~~ & = ~~~ \bit{1~0~1~1~0} \end{aligned} \]

Distância livre e função de transferência de peso

Definição.

A distância livre de um código convolucional, denotada por $d_\text{free}$, é a menor distância de Hamming entre duas sequências-código distintas. Alternativamente, a distância livre corresponde ao menor peso de Hamming de uma sequência-código não-nula.

A capacidade de correção de erros de um código convolucional é dada por

\[ t = \left\lfloor \frac{d_\text{free} - 1}{2} \right\rfloor. \]

No entanto, tipicamente, um código convolucional é capaz de corrigir vários padrões de erro de peso maior que $t$ (ex: erros suficientemente espaçados).

Uma maneira de determinar a distância livre de um código convolucional é através do método de Mason, ilustrado aqui através de um exemplo.

Exemplo.

Determine o diagrama de Mason referente ao código do exemplo anterior e determine a função de transferência de peso.

Solução.

O diagrama de Mason é mostrado abaixo.

As equações de estado são:

\[ \begin{aligned} s_1 & = D^2 x + s_2, \\ s_2 & = D s_1 + D s_3, \\ s_3 & = D s_1 + D s_3, \\ y & = D^2 s_2. \end{aligned} \]

Resolvendo o sistema de equações, obtém-se a função de transferência de peso:

\[ T(D) ~~ = ~~ \frac{y}{x} ~~ = ~~ \frac{D^5}{1 - 2D}. \]

Reescrevendo a função de transferência de peso como uma série de potências, tem-se

\[ T(D) ~~ = ~~ D^5 ~ + ~ 2D^6 ~ + ~ 4D^7 ~ + ~ 8D^8 ~ + ~ \cdots \]

Daí, conclui-se que

há uma sequência-código de peso $5$ ($d_\text{free} = 5$),
há duas sequências-código de peso $6$,
há quatro sequências-código de peso $7$,
há oito sequências-código de peso $8$,

e assim por diante.

Bibliografia

Shu Lin; Daniel J. Costello, Jr.: Error Control Coding, 2nd edition, Pearson Education, 2004.
Simon Haykin: Communication Systems, 4th edition, John Wiley & Sons, 2001.