Abstract: | In this paper, we explore computationally efficient implementations of the soft output viterbi algorithm (SOVA) applied to Soft‐Input Soft‐Output (SISO) decoding of linear block codes. In order to simplify the trellis‐based decoding of binary block codes with SOVA, we use the technique of sectionalization of the trellis, which has been successfully applied to the simplification of the MAP and Max‐Log‐MAP algorithms. Due to the branch complexity of the sectionalized trellis, we define a generalization of a non‐binary version of SOVA. However, the computational complexity of directly applying this approach remains too high for efficient implementation; we thus introduce the concept of non‐binary SOVA (NSOVA) with propagation of bit‐level reliabilities (BLR). This new algorithm is analyzed from a computational complexity viewpoint. Both serial and parallel implementations are explored. Finally, optimal sectionalizations are derived for selected codes; since the normal SOVA decoding is a particular case of NSOVA with BLR, we show that our approach is more efficient than a bit‐level trellis by showing that, for all the codes tested, the optimal trellis is a sectionalized one. Copyright © 2007 John Wiley & Sons, Ltd. |