  This is the second part of a series of papers on a revisit to the
bidirectional Bahl-Cocke-Jelinek-Raviv (BCJR) soft-in-soft-out (SISO) maximum a
posteriori probability (MAP) decoding algorithm. Part I revisited the BCJR MAP
decoding algorithm for rate-1 binary convolutional codes and proposed a linear
complexity decoder using shift registers in the complex number field. Part II
proposes a low complexity decoder for rate-1 non-binary convolutional codes
that achieves the same error performance as the bidirectional BCJR SISO MAP
decoding algorithm. We observe an explicit relationship between the encoding
and decoding of rate-1 convolutional codes in $GF(q)$. Based on this
relationship, the BCJR forward and backward decoding are implemented by dual
encoders using shift registers whose contents are vectors of complex numbers.
The input to the dual encoders is the probability mass function (pmf) of the
received symbols and the output of the dual encoders is the pmf of the
information symbols. The bidirectional BCJR MAP decoding is implemented by
linearly combining the shift register contents of the dual encoders for forward
and backward decoding. The proposed decoder significantly reduces the
computational complexity of the bidirectional BCJR MAP algorithm from
exponential to linear with constraint length of convolutional codes. To further
reduce complexity, fast Fourier transform (FFT) is applied. Mathematical proofs
and simulation results are provided to validate our proposed decoder.
