Low-complexity nonbinary SOVA for sectionalized trellises

The advent of turbo decoding techniques has revived the interest in soft-input soft-output (SISO) decoders that are capable of outputting reliability information (soft decisions). A classical way of implementing a SISO decoder for a linear block code is to use a trellis-based decoding algorithm, such as MAP, Max-Log-MAP or SOVA [S. Lin et al. (1998)]. Recently, the idea of sectionalizing the trellis diagram representing a code has been proposed as a means to decrease the decoding complexity associated with the SISO decoders [S. Lin et al. (1998), Y. Liu et al. (2000)].This paper investigates the application of a nonbinary SOVA decoding algorithm L. Cong et al. (1999) to the sectionalized trellis of a binary linear block code and generalizes the nonbinary SOVA to a code with time-varying symbol set. Based on the above study to derive a new simplified algorithm, called the nonbinary SOVA with bit-level reliabilities (NSOVA with BLR) that we also investigate in terms of complexity for a serial and a parallel implementation. Based on the computational complexity figures for both algorithms and shows that optimal sectionalizations can be found, that minimize the computational complexity entailed when using these algorithms for decoding.