Hardware implementations of trellis based decoders for linear block codes

Abstract

Forward error correction based on convolutional codes or block codes is an essential part in today’s communication systems. If convolutional codes are used, mostly the graphical trellis representation of a code is used in decoding. Efficient trellis based decoding algorithms can then be used, such as the Viterbi algorithm (VA)[3] or the maximum a posteriori algorithm (MAP)[4]. However, it is shown in [1] that a linear binary block code can also be represented by a Trellis diagram. Then, the efficient VA and MAP can also be applied to block codes. This work presents two new architectures for the VA and MAP for block codes and their implementation on FPGA. First, we construct a Viterbi decoder and show how a Banyan permutation network can be used to solve the time variance problem of a Trellis diagram for block codes. Afterwards, we use part of the presented to design a MAX-Log- MAP decoder for linear block codes. To our best knowledge they are the first hardware implementations of these kind. We present implementation details for FPGA designs (Xilinx Virtex 6) of VA and MAP decoders for different trellis sizes. The FPGA designs are analyzed and compared, regarding resource consumption and data throughput. For a 64 state trellis the VA consumes 2800 LUTs and achieves a throughput of 140 Mbit/s, the MAP consumes 6800 LUTs at 70 Mbit/s.

Correção de erro do tipo FEC (do Inglês Forward Error Correction) baseados em códigos bloco ou convolucionais é uma importante parte dos sistemas de comunicação atuais. Se códigos convolucionais são usados, normalmente a representação em treliça do código é utilizada na decodificação. Dessa forma, eficientes algoritmos de decodificação podem ser utilizados, como o algoritmo de Viterbi (VA)[3] e o máximo a posteriori (MAP)[4]. Contudo, é mostrado em [1] que códigos bloco lineares também podem ser representados por um diagrama em treliça. Assim, os algoritmos VA e MAP também podem ser utilizados na sua decodificação. Esse trabalho apresenta duas novas arquiteturas para o VA e o MAP para códigos bloco e suas implementações em FPGA. Primeiro, nós construímos um decodificador Viterbi e mostramos como uma rede de permutação de Banyan pode ser usada para resolver o problema da variancia no tempo discreto de um diagrama em treliça para códigos bloco. Depois disso, nós reusamos a unidade de recurção do decodificador Viterbi para implementar um decodificador MAX-Log-MAP para códigos bloco. Para o nosso melhor conhecimento, elas são as primeiras implementações em hardware desse tipo. Nós apresentamos detalhes de implementação em FPGA (Xilinx Virtex 6) do decodificador Viterbi e MAP para diferentes tamanhos de treliça. As implementações em FPGA são analisadas e comparadas, considerando o uso de recursos e vazão de dados. Para um diagrama em treliça com 64 estados, o VA consome 2800 LUTs com uma vazão de 140 Mbit/s. Já o MAP consome 6800 Luts a 70 Mbit/s.