Duality of Channel Encoding and Decoding Part II: Rate-1 Non-binary Convolutional Codes
Qimin You, Yonghui Li, Senior Member, IEEE, Soung Chang

arXiv:1801.02713v1 [cs.IT] 8 Jan 2018

Liew, Fellow, IEEE, and Branka Vucetic, Fellow, IEEE

Abstract
This is the second part of a series of papers on a revisit to the bidirectional Bahl-Cocke-JelinekRaviv (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.

Index Terms
BCJR MAP decoding, computational complexity, convolutional codes, dual encoder.

Yonghui Li, Qimin You and Branka Vucetic are with School of Electrical and Information Engineering, University of Sydney,
Sydney, NSW, 2006, Australia. Email: {yonghui.li, qimin.you, branka.vucetic}@sydney.edu.au
Soung C. Liew is with Department of Information Engineering, The Chinese University of Hong Kong, Hong Kong,
Email:soung@ie.cuhk.edu.hk.

1

I.

INTRODUCTION

In part I of this series of papers [1], [2], we revisited the bidirectional Bahl-Cocke-JelinekRaviv (BCJR) soft-in-soft-out (SISO) maximum a posteriori probability (MAP) decoding process
of rate-1 binary convolutional codes. We observed an explicit relationship between the encoding
and decoding of rate-1 binary convolutional codes and proposed a low complexity decoder using
shift registers in the complex number field. The input to the decoder is the logarithm of soft
symbol estimates of the coded symbols obtained from the received signals, and the output is
the logarithm of the soft symbol estimates of the information symbols. The proposed decoder
reduced the computational complexity of SISO MAP forward and backward recursion from
exponential to linear without any performance loss.
The last few years have witnessed a drastic increase in the demand for reliable communications, constrained by the scarce available bandwidth, to support high-speed data transmission
applications, such as voice, video, email and web browsing. To accommodate such demand,
non-binary convolutional codes have been proposed to replace binary convolutional codes in
many applications [3]–[5]. For example, non-binary turbo codes, which employ non-binary
convolutional codes as component codes, achieve lower error-floor and better performance at
the waterfall region compared to binary turbo codes [6]. Additionally, non-binary convolutional
codes suit situations where bandwidth-efficient higher order (non-binary) modulation schemes are
used, as well as situations where non-coherent modulation schemes are used, such as frequencyshift keying [7].
The main obstacle that impedes the practical implementation of the non-binary convolutional
codes is the high decoding complexity. The decoding of non-binary convolutional codes is
not equivalent to the decoding of binary convolutional codes, because the non-binary decoder
operates on the symbol level, instead of bit level. Decoding is essentially finding an optimal
path in a trellis based graph. Therefore, the Viterbi algorithm (VA) [8] can be applied to decode
non-binary convolutional codes. It provides the maximum-likelihood estimate of the information
sequence based on the exhaustive search of the trellis over a fixed length window. Unfortunately,
in standard VA, hard decision outputs are produced instead of soft outputs containing a posterior
probability (APP) of the transmitted symbols. Therefore, the standard VA can not be used to
decode concatenated codes, like turbo codes. To overcome this problem, the modified soft-

2

output VA (SOVA) was proposed in [9] to decode non-binary convolutional codes. SOVA not
only delivers the maximum-likelihood information sequence but also provides the APPs of
the transmitted symbols. Therefore, it can be applied to decode concatenated codes. However,
according to [10], the computational complexity of VA and SOVA is proportional to the number
of states, which is q K , where q is the field size and K is the constraint length [11]. Thus, it grows
rapidly for non-binary alphabets, which makes practical implementation tremendously difficult.
Furthermore, both VA and SOVA suffer from considerable performance loss compared to the
BCJR MAP algorithm [12] which achieves optimal symbol error probability.
The BCJR MAP decoding algorithm is a bidirectional decoding algorithm which includes a
forward and backward decoding recursion. The APP of the information symbol is estimated
based on the combined forward and backward recursions. All the intermediate results during
forward and backward recursions have to be stored before a decision is made, which incurs
large memory storage requirements. Furthermore, the computational complexity at each time
unit in both recursions is proportional to q 2K . The high computational complexity results in
large decoding delay and unacceptably high costs.
Therefore, a low complexity decoder with good error performance is desirable for the pragmatic implementation of non-binary convolutional codes. In the decoding of turbo codes based on
memory-1 convolutional codes in [13], the authors found that the encoder memory at the current
time slot is a linear combination of the encoder memory at the previous time slot and the current
input. Since the encoder memory at the previous time slot and the current input are independent,
the probability mass function (pmf) of the current encoder memory can be calculated by the
convolution of the pmf of encoder memory at the previous time slot and the pmf of the current
input. This reduced the calculation complexity in the forward and backward recursions at each
time slot to q 2 . To further reduce complexity, fast Fourier transform (FFT) is employed on the
pmf involved in the convolutions [13]. The decoding complexity is thus reduced to q log2 q at
each time slot. However, this calculation simplification only works for memory-1 convolutional
codes. The generalization to non-binary convolutional codes with arbitrary memory length is not
considered in [13]. Furthermore, forward and backward recursions still have to be performed
based on the trellis of the non-binary convolutional codes. All the intermediate results have to
be stored and thus large memory requirements are incurred.
In this paper, we propose a low complexity decoder for general rate-1 non-binary convolutional

3

codes that achieves exactly the same error performance as the bidirectional BCJR MAP decoding algorithm. We observe an explicit relationship between the BCJR MAP forward/backward
decoder of a convolutional code and its encoder. Based on this observation, we propose the
dual encoders for SISO forward and backward decoding, which are simply implemented using
shift registers whose contents are pmfs of complex vectors. Then, the bidirectional SISO MAP
decoding is achieved by linearly combining the shift register contents in the forward and backward dual encoders. This significantly reduces the original exponential computational complexity
of BCJR MAP forward and backward recursion to (q 2 )K. To further reduce the computational
complexity, FFT [14], [15] is applied and its complexity is reduced to (q log2 q)K. Mathematical
proofs and simulation results are provided to validate our proposed decoder.
The rest of this paper is organized as follows. In Section II, we propose an dual encoder for
SISO MAP forward decoding of non-binary convolutional codes. The dual encoder for SISO
MAP backward decoding is presented in Section III. The bidirectional BCJR MAP decoding
is achieved by linearly combining the shift register contents of the forward and backward dual
encoders, and simulation results are provided to validate our proposed decoder in Section IV.
In Section V, concluding remarks are drawn. Mathematical proofs are given in the appendices.
II. D UAL

ENCODER OF

SISO MAP

FORWARD DECODING

In this section, we focus on the SISO MAP forward decoding algorithm. We consider convolutional codes over the finite fields with q elements, denoted by GF (q). We focus on the
decoding of a single constituent rate-1 convolutional code in GF (q), generated by g(x) =
a(x)
f (x)

=

1+a1 x+···+an−1 xn−1 +xn
,
1+f1 x+···+fn−1 xn−1 +xn

where ai , fi ∈ GF (q), i = 1, 2, · · · , n − 1. Its encoder C is shown

in Fig. 1, where all the additions and multiplications are performed in GF (q). In this paper,
the input, output and memory of shift registers for convolutional encoders are in GF (q). Let
−
→
→
b = (b1 , b2 , · · · , bL ) and −
c = (c1 , c2 , · · · , cL ) denote the information symbol sequence and
the codeword sequence, where L is the frame length. The code sequence is modulated and
transmitted through the additive white Gaussian noise (AWGN) channel. The receiver obtains
→
−
yk = (y1 , y2, · · · , yL ) at the output of the channel.
→
Let p (ω) = p (c = ω|−
y ) , ω ∈ GF (q) denote the conditional probability of the code symbol
ck

k

k

4

−
ck given →
yk . Let us further define the following probability mass function of ck and bk
Pck = [pck (0), pck (1), · · · , pck (q − 1)]

(1)

Pbk = [pbk (0), pbk (1), · · · , pbk (q − 1)].

(2)

Fig. 1: Encoder C of a rate-1 convolutional code in GF (q), generated by g(x) =
1+a1 x+···+an−1 xn−1 +xn
,
1+f1 x+···+fn−1 xn−1 +xn

where all the additions and multiplications are performed in GF (q).

Fig. 2: A convolutional code with generator polynomial g(x) = 1 + x in GF (4).

Fig. 3: An encoder C̄ with generator polynomial q(x) =

1
1+x

in GF (4).

The aim of the decoder is to derive Pbk based on the pmf of the code symbols. To facilitate
the exposition, we first consider a simple example. Let us consider a convolutional code with

5

generator polynomial g(x) = 1 + x in GF (4). Its encoder is shown in Fig. 2. We define an
1
1
= 1+x
(Fig. 3). If the input to the encoder C̄
encoder C̄ in GF (4), described by q(x) = g(x)
→
is a codeword −
c , generated by g(x), the output of the encoder C̄ is the decoded information
→
−
→
−
sequence b . Let S ′ (k) denote the memory of the shift register of encoder C̄ at time k, the

encoder output bk is given by
bk = ck + ck−1
→
−
= ck + S ′ (k − 1),
→
−
where S ′ (k) = ck . Therefore, we have the following relationship
n
o
→
−
pbk (ω) = p {bk = ω} = p ck + S ′ (k − 1) = ω .

(3)

(4)

→
−
Note that ck and S ′ (k − 1) are independent, and equation (4) can be written as
pbk (ω) =

q−1
X

ck =0

n−
o
→
p {ck } p S ′ (k − 1) = ω − ck .

(5)

→
−
According to the properties of random variables, since bk is the summation of ck and S ′ (k − 1)
→
−
→′
=
in GF (4), the pmf of bk is the convolution of the pmf of ck and S ′ (k − 1). Let P−
S (k−1)
→′
−
→′
→′
→′
(q − 1)] denote the pmf of S (k − 1), then the pmf of bk
(1), · · · , p−
(0), p−
[p−
S (k−1)
S (k−1)
S (k−1)
can be calculated as
→′
Pbk = Pck ∗ P−
.
S (k−1)

(6)

where ∗ denotes the convolution operation.
Its corresponding dual encoder is shown in Fig. 4. As verified mathematically in Appendix
A, this dual encoder achieves exactly the same BER as the bidirectional BCJR MAP decoding
algorithm.

Fig. 4: The dual encoder of the SISO forward decoding for the code g(x) = 1 + x in GF (4),
where ∗ denotes the convolution operation.

6

This dual encoder could be generalized to any rate-1 convolutional codes in GF (q). First, we
n−1

n

(x)
1+f1 x+···+fn−1 x
+x
= fa(x)
= 1+a
n−1 +xn , shown
1 x+···+an−1 x
→
in Fig. 5. If the input to the encoder C̄ is a codeword −
c , generated by g(x), the output of
→
−
the encoder C̄ is the decoded information sequence b . In this encoding process, at each time

define an encoder C̄ in GF (q), described by q(x) =

1
g(x)

instant, each encoder memory can be described as a linear combination of input symbols over
P
→
−
GF (q), denoted by S ′i (k) = kp=1 ηp cp , where ηp ∈ GF (q). If the linear combination equations
of two memories contain one or more common input symbols, we say that the two memories
→
−
→
−
are correlated. For example, if S ′1 (3) = c1 + c3 , and S ′3 (3) = c1 , then these two memories are
correlated, as both linear combination equations of these two memories contain the input symbol
c1 .

Fig. 5: An encoder C̄ in GF (q), described by q(x) =

1+f1 x+···+fn−1 xn−1 +xn
.
1+a1 x+···+an−1 xn−1 +xn

If we map the structure in Fig. 5 to the convolutional structure in Fig. 6, where each + is
replaced by ∗. The output of the dual encoder in Fig. 6 is different from the decoding output of the
BCJR MAP forward decoding output, resulted from the correlation of the encoder memories of
C̄. Thus, when memories are correlated, the dual encoder cannot be used as an equivalent MAP
forward decoding. To eliminate the memory correlation, we can multiply both the numerator
and denominator of polynomial q(x) by a common polynomial without actually changing the
polynomial of q(x). In order to obtain such a common polynomial, let us first define the minimum
complementary polynomial for a given polynomial a(x) as the polynomial of the smallest degree,
z(x) = 1 + z1 x + · · · + zl−1 xl−1 + xl ,

(7)

7

such that
a(x)z(x) = 1 + xn+l .

(8)

=

Fig. 6: The dual encoder of the SISO forward decoding, described by q(x)
xn−1 +xn

1+f1 x+···+fn−1
.
1+a1 x+···+an−1 xn−1 +xn

Since a(x) always divides xq

n −1

+ 1, the minimum complementary polynomial of a(x) always

exists. Let f (x)z(x) = (1 + f1 x + · · · + fn−1 xn−1 + xn ) 1 + z1 x + · · · + zl−1 xl−1 + xl = 1 +
→
−
h1 x + · · · + hn+l−1 xn+l−1 + xn+l and let S ′ j (k), j = 1, 2, · · · , n + l, denote the memory of the
j-th shift register of encoder C̄, generated by q(x) =
1+

h1 x+···+hn+l−1
1+xn+l

xn+l−1

f (x)z(x)
a(x)z(x)

=

1+h1 x+···+hn+l−1 xn+l−1 +xn+l
1+xn+l

=

. In encoder C̄, the output is given by

→
−
→
−
→
−
bk = ck + h1 S ′ 1 (k − 1) + h2 S ′ 2 (k − 1) + · · · + hn+l−1 S ′ n+l−1 (k − 1),

(9)

and the memory of shift registers for encoder C̄ can be expressed as
−′
→
→
−
S 1 (k) = ck + S ′ n+l (k − 1)
→′
−
→
−
S j (k) = S ′ j−1(k − 1), j ≥ 2.

(10)
(11)

Note that the additions and multiplications in the above three equations are performed in
→
−
GF (q). If we denote hi S ′ i (k − 1), i = 1, 2, · · · , n + l − 1, as one symbol in GF (q), then the
→
−
→
−
→
−
value of hi S ′ i (k − 1) equals S ′ i (k − 1) multiplied by hi in GF (q). The pmf of hi S ′ i (k − 1)
→′
→′
and can be derived by cyclically shifting the jth element of P−
is denoted by Ph −
S (k−1)
S (k−1)
i

i

i

→′
to position [jhi ]q . Let Πhi denote such permutation of P−
by hi , where each jth element
S (k−1)
i

8

→′
→′
in P−
is cyclically shifted to the [jhi ]q in Πhi P−
[16]. Based on (9), the probability
S (k−1)
S (k−1)
i

i

that bk = ω can be written as
pbk (ω) = p {bk = ω}
o
n
→
−
→
−
→
−
= p ck + h1 S ′ 1 (k − 1) + h2 S ′ 2 (k − 1) + · · · + hn+l−1 S ′ n+l−1 (k − 1) = ω .

(12)

→
−
→
−
→
−
Because ck and h1 S ′ 1 (k−1)+h2 S ′ 2 (k−1)+· · ·+hn+l−1 S ′ n+l−1 (k−1) are mutually independent,
equation (12) can be written as
pbk (ω)
=

q−1
X

ck =0

o
n −
→
−
→
−
→
p {ck } p h1 S ′ 1 (k − 1) + h2 S ′ 2 (k − 1) + · · · + hn+l−1 S ′ n+l−1(k − 1) = ω − ck (13)

According to the definition of convolution, the probability mass function of bk can be expressed
from (13) as
Pbk = Pck ∗ Ph

−
→

−
→

−
→

′
′
′
1 S 1 (k−1)+h2 S 2 (k−1)+···+hn+l−1 S n+l−1 (k−1)

.

(14)

Similarly, due to the independence of the memories of shift registers, the pmf vectors of bk
→
−
can be represented as the convolution of the pmf vectors of ck and hj S ′ j (k)
Pbk = Pck ∗ Ph

−
→

′
1 S 1 (k−1)

→′
= Pck ∗ Πh1 P−
S

∗ · · · ∗ Ph

1 (k−1)

−
→

′
n+l−1 S n+l−1 (k−1)

→′
∗ · · · ∗ Πhn+l−1 P−
S

n+l−1 (k−1)

.

(15)

Similarly, following (10) and (11), shift register contents of the dual encoder are updated as
follows
→′
P−
S

1 (k)

→′
= Pck ∗ P−
S

n+l (k−1)

→′
→′
P−
= P−
S (k)
S
j

j−1 (k−1)

.

(16)
(17)

Based on the above analysis, we can derive a simple structure for MAP forward decoding
implemented using the convolutional encoders, described by q(x) = 1 +

h1 x+···+hn+l−1 xn+l−1
,
1+xn+l

as

shown in Fig. 7, where ∗ denotes the convolution operation and Πhi denotes permutation. The
input of the dual encoder is Pck and the output of the dual encoder Pbk . Here the convolution
operation is performed on complex vectors.

9

Fig. 7: The dual encoder of the SISO forward decoding for the code g(x), given by q(x) =
1+

h1 x+···+hn+l−1 xn+l−1
.
1+xn+l

Equations (15), (16), (17) and Fig. 7 reveal an interesting relationship of the convolutional
encoder and the SISO forward decoder for rate-1 convolutional codes in GF (q). This can be
summarized in the following theorem.
Theorem 1: Dual encoder for SISO MAP forward decoding: For a rate-1 convolutional
code in GF (q), generated by g(x) =

1+a1 x+···+an−1 xn−1 +xn
,
1+f1 x+···+fn−1 xn−1 +xn

we define its dual encoder as

the encoder with inverse generator polynomial of g(x), given by q(x) =
1+

h1 x+···+hn+l−1 xn+l−1
.
1+xn+l

1
g(x)

=

f (x)z(x)
a(x)z(x)

=

Then the SISO MAP forward decoding of convolutional codes can be

implemented by its dual encoder of complex vectors, which is shown in Fig. 7. The output of
the dual encoder is the pmf of the information sequence. Note that all the operations in the dual
encoder are convolution operations.
Proof: See Appendix A.
The complexity of the dual encoder for forward decoding in Fig. 7 is dominated by the
convolution operations, and thus scales as O (q 2 K) [17]. The complexity can be further reduced
by applying the FFT on the probability vectors involved in the convolutions [18]. Let F [P1 ] =
(F [P1 ](0), F [P1 ](1), · · · , F [P1 ](q − 1)) and F [P2 ] = (F [P2 ](0), F [P2 ](1), · · · , F [P2 ](q − 1)) be
the FFT transformed vectors of P1 and P2 , we define the Hadamard product, which is the
element-wise multiplication of two vectors [19], of F [P1 ] and F [P2 ] as F [P1 ] ◦ F [P2 ] =
(F [P1 ](0)F [P2 ](0), F [P1](1)F [P2 ](1), · · · ,F [P1 ](q − 1)F [P2 ](q − 1)). The Fourier transform of
the convolution of two functions equals the product of the Fourier transforms of these two

10

functions [20]. Therefore, (15), (16) and (17) can be expressed as
o
n
−
→
→′
]
◦
·
·
·
◦
F
[Π
P
]
Pbk = F −1 F [Pck ] ◦ F [Πh1 P−
hn+l−1 S ′
S 1 (k−1)
n+l−1 (k−1)
n
o
→′
→′
]
P−
= F −1 F [Pck ] ◦ F [P−
S
(k−1)
S (k)
1

n+l

→′
→′
P−
= P−
S (k)
S
j

j−1 (k−1)

.

(18)
(19)
(20)

Therefore, we propose an FFT dual encoder for forward decoding, shown in Fig. 8, where ◦
denotes the element-wise multiplication of two vectors and F the FFT of a vector. Note that all
the convolution operations in the dual encoder in Fig. 7 become the element-wise multiplication
in Fig. 8, and this considerably reduces the complexity from O ((q 2 ) K) to O ((q log2 q) K).
Note that the output of the FFT dual encoder is exactly the same as the output of the dual
encoder for forward decoding.

Fig. 8: The FFT dual encoder of SISO forward decoding for the code g(x).

III. I NVERSEV

ENCODER OF

SISO MAP

BACKWARD DECODING

In this section, we propose an dual encoder for the BCJR MAP backward decoding of rate-1
convolutional codes in GF (q). In the BCJR MAP backward decoding, the received signals are
decoded in a time-reverse order. That is, given the received signal sequence y = (y1 , y2 , · · · , yL ),
the order of the signals to be decoded is from yL , yL−1 , to y1 . In addition, in the backward
decoding, the decoder has to follow the trellis in a reverse direction. Figs. 9 and 10 show the
encoder and its trellis, described by the generator polynomial g(x) =

1+2x
.
1+x

Fig. 11 shows the

11

backward trellis, where the input to the decoder is at the right hand side of the decoder and its
output is at the left hand side, which operates in a reverse direction of the conventional order.

Fig. 9: The encoder of code g(x) =

1+2x
.
1+x

Fig. 10: The trellis of code g(x) =

1+2x
.
1+x

Fig. 11: The backward trellis of code g(x) =

1+2x
.
1+x

For ease of exposition, we propose to present the backward trellis in the forward direction
where the decoder input and output are changed to the conventional order. Specifically, for a
convolutional encoder, described by g(x) =

a(x)
f (x)

=

1+a1 x+···+an−1 xn−1 +xn
,
1+f1 x+···+fn−1 xn−1 +xn

if the labeling of the

kth shift register in the encoder is changed from Sk to Sn−k and their respective coefficients

12

are changed from from ak to an−k , k = 1, 2, · · · , n, and from bk to bn−k , the resulting encoder
is referred to as the reverse-memory labeling encoder of g(x). For example, Fig. 12 shows the
forward representation of the backward trellis of code g(x) =

1+2x
.
1+x

Its corresponding reverse-

memory labeling encoder is shown in Fig. 13.

Fig. 12: The equivalent forward representation of the backward trellis of code g(x) =

1+2x
.
1+x

Fig. 13: The encoder corresponds to the trellis of Fig. 12.

It is shown in [1, Theorem 3] that the relationship of the encoders for the forward and
backward trellises can be extended to general rate-1 convolutional codes in GF (q), as shown in
the following theorem.
Theorem 2: Given an encoder with generator polynomial g(x) =

a(x)
f (x)

=

1+a1 x+···+an−1 xn−1 +xn
,
1+f1 x+···+fn−1 xn−1 +xn

the forward representation of its backward trellis can be implemented by its reverse-memory
labeling encoder of the same generator polynomial g(x).
Proof: This can be proved similarly as the proof of Theorem 3 in [1], and we omit it here.

13

From Theorem 1, we know that the SISO forward decoding of a given convolutional code,
generated by g(x) =

a(x)
,
f (x)

can be implemented by its dual encoder described by q(x) =

f (x)z(x)
,
a(x)z(x)

where z(x) is the degree l minimum complementary polynomial of a(x). Then according to
Theorem 2, the SISO backward decoding of the convolutional code can be implemented by
its reverse-memory labeling encoder of q(x). By combining Theorems 1 and 2, we can obtain
the dual encoder for SISO MAP backward decoding, which is summarized in the following
Theorem.
Theorem 3: dual encoder for SISO MAP backward decoding: We consider a convolutional
code, generated by g(x) =

a(x)
f (x)

=

1+a1 x+···+an−1 xn−1 +xn
.
1+f1 x+···+fn−1 xn−1 +xn

Let z(x) be the degree-l minimum

complementary polynomial of a(x). Its SISO backward decoding can be implemented by its
dual encoder, described by q(x) =

f (x)z(x)
a(x)z(x)

= 1+

h1 x+···+hn+l−1 xn+l−1
,
1+xn+l

with reverse-memory

labeling and time-reverse input, shown in Fig. 14.
Proof: See Appendix B.

Fig. 14: The dual encoder of the SISO backward decoding for the code g(x), given by q(x) =
1+

h1 x+···+hn+l−1 xn+l−1
.
1+xn+l

The computational complexity of the dual encoder for the SISO backward decoding is dominated by the convolution operation. Similar to the forward decoding, we can apply FFT to further
reduce the complexity of dual encoder for backward decoding. The FFT backward dual encoder
is shown in Fig. 15.

14

Fig. 15: The FFT dual encoder of SISO backward decoding for the code g(x).

IV. T HE

REPRESENTATION OF BIDIRECTIONAL

SISO MAP

DECODING

In the previous two sections, dual encoders for SISO MAP forward and backward decoding
have been proposed. Based on the derived dual encoder structures, in this section, we represent
the bidirectional SISO decoder by linearly combining shift register contents of the dual encoders
for SISO MAP forward and backward decoding. We prove mathematically that such linear
combining achieves exactly the same output as the bidirectional BCJR MAP decoding.
In the bidirectional BCJR MAP decoding, the APPs derived from the forward and backward
recursions are combined at the same state at each time unit to obtain the desired decoding output.
Therefore, it is usually assumed that the encoder begins with and ends at the all-zero state [10].
The proposed dual encoder will produce the same output as the BCJR MAP algorithm when the
forward and backward dual encoders have the same state at each time unit. As will be discussed
shortly, this is ensured if the proposed dual encoder begins with and terminates at the all-zero
state. To achieve this, tail symbols are added at the end of the code sequence.
Let us consider an encoder C̄ of memory length n + l in GF (q), described by q(x) =
h x+···+hn+l−1 xn+l−1
(x)z(x)
→
1
= fa(x)z(x)
= 1+ 1
. If the input to the encoder C̄ is a codeword −
c =
g(x)
1+xn+l
(c1 , c2 , · · · , cL ), generated by g(x), the output of the encoder C̄ the decoded information sequence
−
→
b . Let us define (cL+1 , ..., cL+n+l ) as the tail-bits required to terminate C̄ at the all-zero state.
Then following an analysis similar to that in [1], we can prove that the tail-biting convolutional
encoder C̄ has the following property.
n+l−1 x
Lemma 1: The tail-bits that terminate the encoder C̄, described by q(x) = 1+ h1 x+···+h
1+xn+l

n+l−1

,

15

at the all-zero state also terminate the encoder C, generated by g(x) =

a(x)
,
f (x)

at the all-zero state.

Lemma 2: For a tail-biting convolutional encoder C̄, generated by q(x), and a given input
sequence (c1 , c2 , · · · , cL , cL+1 , · · · , cL+n+l ), we define its backward encoder as the encoder of the
same generator polynomial with reverse-memory labeling and time-reverse input (cL+n+l , · · · , cL+1 ,
cL , · · · , c2 , c1 ). Then the tail-biting encoder C̄ and its backward encoder arrive at the same state
at any time k.
In the decoding structures we introduced in the previous two sections, the input, output and
shift register contents of dual encoders for forward and backward decoding are pmf vectors.
To derive the bidirectional SISO decoder output, we need to combine the shift register contents of dual encoders for forward and backward decoding in an optimal way. Let PS′j (k) =
[pSj′ (k) (0), pSj′ (k) (1), pSj′ (k) (α), · · · , pSj′ (k) (αq−2)] denote the combined pmf of the jth shift register
−
→′
are obtained from the forward
and P←
of the combined dual encoder at time k. Since P−
S (k)
S ′ (k)
j

j

decoding based on the received signals from time 1 to k and that from backward decoding based
on the received signals from time L+n+l to k +1, they are independent. Furthermore, as shown
in Lemma 2, for tail-biting encoder C̄, generated by q(x), forward and backward encoders will
arrive at the same state at time k. Therefore, in the optimal combining, we have
→′
−
◦ P←
.
PS′j (k) = P−
S (k)
S ′ (k)
j

j

(21)

Based on the dual encoder structure in Fig. 7, the bidirectional SISO MAP decoding can be
implemented by the proposed dual encoder with combined shift register contents. The output of
the combined dual encoder is given by
Pbk = Pck ∗ Πh1 PS′1 (k−1) ∗ · · · ∗ Πhn+l−1 PS′n+l−1 (k−1) .

(22)

As shown in the following theorem, such combining will produce exactly the same output as
the bidirectional BCJR MAP algorithm.
Theorem 4: We can represent the bidirectional SISO MAP decoder by linearly combining
shift register contents of dual encoders for forward and backward decoding, as shown in (21)
and (22). This decoder produces exactly the same decoding output as the bidirectional BCJR
MAP decoding algorithm.
Proof: See Appendix C.

16

To reduce computational complexity, FFT can be applied to (22)
n
o
Pbk = F −1 F [Pck ] ◦ F [Πh1 PS′1 (k−1) ] ◦ · · · ◦ F [Πhn+l−1 PS′n+l−1 (k−1) ] .

(23)

Next, let us present some simulation results to validate our proposed scheme. A BPSK
modulation is assumed. A frame size of L = 256 symbols is employed over AWGN channels.
The bit error rate (BER) of various 4-state and 16-state convolutional codes are shown in Figs.
16 to 20. The curve “dual encoder forward+backward” refers to the direct summation of the
forward and backward dual encoder outputs, and the curve “dual encoder shift register combined
output” refers to the optimal combined output (22).
Figs. 16 to 20 show that the direct summation of the forward and backward dual encoder
outputs suffers from some performance loss when compared to the bidirectional BCJR MAP
algorithm. The SNR loss relative to the bidirectional BCJR MAP algorithm is 0, 0.1, 0.48, 0.1
and 1 dB for codes g(x) = 1 + x, g(x) = 1 + 3x + 2x2 , g(x) = 1 + x + 2x2 , g(x) =
g(x) =

1+3x+2x2
.
1+x+2x2

1+x
1+2x

and

However, the proposed optimal linear combining scheme achieves exactly the

same performance as the bidirectional BCJR MAP algorithm.
V. C ONCLUSIONS
In this paper, we investigated the BCJR MAP decoding of rate-1 convolutional codes in GF (q).
We observed an explicit relationship between the SISO BCJR MAP forward and backward
decoder of a convolutional code and its encoder. Based on this observation, we proposed dual
encoders for forward and backward decoding. The input of the dual encoders is the probability
mass function of the code symbols and the output of the dual encoders is the probability
mass function of the information symbols. The bidirectional SISO decoder is implemented by
linearly combining the shift register contents of the dual encoders for forward and backward
decoding. The proposed dual encoders significantly reduced the computational complexity of
the bidirectional BCJR MAP decoding from exponential to linear in terms of convolutional
code constraint length. To further reduce the complexity, fast Fourier transform is employed.
Mathematical proofs and simulation results validate that the proposed dual encoder with shift
register contents combining produces exactly the same output as the BCJR MAP decoding
algorithm.

17

A PPENDIX A
PROOF OF THEOREM

1

We consider the BCJR forward decoding algorithm of a general convolutional code g(x) in
h x+···+h

xn+l−1

n+l−1
GF (q). Its dual encoder for forward decoding is described by q(x) = 1 + 1
. If
1+xn+l

the state of the dual encoder transits from u′1 , u′2, · · · , u′n+l at time k − 1 to (u1 , u2 , · · · , un+l )

at time k with input ck , then the probability of bk = ω can be expressed as
X
→
Pbk (ω) = P {bk = ω|−
y}=
αk−1 (u′ ) γk (u′, u)
(u′ ,u)=U (bk =ω)

n+l
Y

X

=

→′
P−
S

j (k−1)

(u′j )P (ck )

(u′ ,u)=U (bk =ω) j=1

X

=
u′1 ,u′2 ,··· ,u′n+l ,

Pn+l−1
j=1

n+l
Y

→′
P−
S

j (k−1)

(u′j )P (ck ).

(24)

hj u′j +ck =ω j=1

n+l−1

n+l−1 x
, the dual encoder output
According to the generator polynomial q(x) = 1 + h1 x+···+h
1+xn+l
→′
−
is independent of the shift register contents in S n+l (k − 1), shown in Fig. 8. Therefore (24) can

be written as
X

Pbk (ω) =
u′1 ,u′2 ,··· ,u′n+l ,

Pn+l−1
j=1

u′1 ,u′2 ,··· ,u′n+l ,

Pn+l−1
j=1

→′
P−
S

n+l−1
Y

→′
P−
(u′ )P (ω
S j (k−1) j

j (k−1)

(u′j )P (ck )

hj u′j +ck =ω j=1

X

=

n+l−1
Y

hj u′j =ω−ck

−

j=1

n+l−1
X

hj u′j ).

(25)

j=1

According to the definition of convolution operation, the probability mass function of bk can be
written as
→′
∗ Pck .
Pbk = PPn+l−1 h −
S (k−1)
j

j=1

(26)

j

Using similar procedures of deriving (26) from (25), we can get
Pbk = Pck ∗ Ph

−
→

′
1 S 1 (k−1)

→′
= Pck ∗ Πh1 P−
S

∗ · · · ∗ Ph

1 (k−1)

This proves Theorem 1.

−
→

′
n+l−1 S n+l−1 (k−1)

→′
∗ · · · ∗ Πhn+l−1 P−
S

n+l−1 (k−1)

.

(27)

18

A PPENDIX B
PROOF OF THEOREM

3

←
−
We consider the backward decoding of convolutional codes in GF (q). Let S ′ j (k), j = 1, 2, · · · , n+
l, denote the memory of the j-th shift register of the backward encoder of C̄, generated by q(x).
←
−
−
−
−
−
Let P←
= [p←
(0), p←
(1), · · · , p←
(q − 1)] denote the pmf vector of S ′ j (k). The
S ′ (k)
S ′ (k)
S ′ (k)
S ′ (k)
j

j

j

j

probability that bk = ω is given by
→
Pbk (ω) = P {bk = ω|−
y}=

X

βk (u) γk (u′ , u)

(u′ ,u)=U (bk =ω)

=

X

n+l
Y

−
P←
(u )P (ck )
S ′ (k) i

(28)

X

n+l
Y

−
(u )P (ck )
P←
S ′ (k) i

(29)

(u′ ,u)=U (bk =ω)

=

i

i=1

i

(u′ ,u)=U (bk =ω) i=2

n+l−1
Y

X

=
u′1 ,u′2 ,··· ,u′n+l ,

Pn+l−1
j=1

hj u′j +ck =ω

−
P←
S′

j (k−1)

(u′j )P (ck ).

(30)

j=1

Note that (29) is derived from (28) because at time slot k, the dual encoder output for BCJR
−
MAP backward decoding is independent of P←
S′

1 (k)

Pbk = Pck ∗ Ph

←
−

′
1 S 1 (k−1)

−
= Pck ∗ Πh1 P←
S′

. Based on (30), we can get

∗ · · · ∗ Ph

1 (k−1)

←
−

′
n+l−1 S n+l−1 (k−1)

−
∗ · · · ∗ Πhn+l−1 P←
S′

n+l−1 (k−1)

.

(31)

This proves Theorem 3.
A PPENDIX C
P ROOF

OF THEOREM

4

We consider a convolutional code in GF (q), generated by g(x). Its dual encoder for decoding is described by q(x). It is assumed that the state of the dual encoder C̄ transits from

u′1 , u′2, · · · , u′n+l at time k−1 to (u1 , u2 , · · · , un+l ) at time k with input ck . For the bidirectional

19

BCJR MAP algorithm, the probability that bk = ω is given by
X
→
Pbk (ω) = P {bk = ω|−
y}=
αk−1 (u′ ) γk (u′, u) βk (u)
(u′ ,u)=U (bk =ω)

=

X

n+l
Y

X

n+l−1
Y

(u′ ,u)=U (bk =ω)

=

→′
P−
S

(u′ )P (ck )
(k−1) j

j

j=1

n+l
Y

=
u′1 ,u′2 ,··· ,u′n+l ,

Pn+l−1
j=1

→′
P−
S

j

(u′ )P (ck )
(k−1) j

u′1 ,u′2 ,··· ,u′n+l ,
→′
where PSj′ (k−1) (u′j ) = P−
S

Pn+l−1
j=1

j (k−1)

(ui )

n+l
Y

−
P←
S′

j (k)

(ui )

i=2

n+l−1
Y

→′
P−
(u′ )P (ck )
S j (k−1) j

n+l−1
Y

PSj′ (k−1) (u′j )P (ck ),

hj u′j +ck =ω

−
(u′j )P←
S′

j (k−1)

n+l−1
Y

−
P←
S′

j (k−1)

(u′j )

j=1

hj u′j +ck =ω j=1

X

=

j (k)

i=1

(u′ ,u)=U (bk =ω) j=1

X

−
P←
S′

(32)

j=1

(u′j ). From (32), we can get

Pbk = Pck ∗ Ph1 S′1 (k−1) ∗ · · · ∗ Phn+l−1 S′n+l−1 (k−1)
= Pck ∗ Πh1 PS′1 (k−1) ∗ · · · ∗ Πhn+l−1 PS′n+l−1 (k−1) .

(33)

Comparing the shift register combined outputs of the dual encoder in (22) and the outputs of
the bidirectional BCJR MAP algorithm in (33), we can see that they are exactly of the same.
This proves Theorem 4.
R EFERENCES
[1] Y. Li, Q. You, S. C. Liew, and B. Vucetic, “Duality of channel encoding and decoding - part 1: Rate-1 binary convolutional
codes,” European Transactions on Emerging Telecommunications Technology.
[2] Y. Li, M. S. Rahman, and B. Vucetic, “SISO MAP decoding of rate-1 recursive convolutional codes: a revisit,” in Proc.
IEEE ISIT, Cambridge, July 2012.
[3] B. Vucetic and J. Yuan, Turbo Codes: Principles and Applications.

Kluwer Academic Publishers, 2000.

[4] C. Berrou and A. Glavieux, “Near optimum error correcting coding and decoding: turbo-codes,” IEEE Trans. Commun.,
vol. 44, no. 10, pp. 1261 –1271, Oct. 1996.
[5] S. Benedetto and G. Montorsi, “Design of parallel concatenated convolutional codes,” IEEE Trans. Commun., vol. 44,
no. 5, pp. 591 –600, May 1996.
[6] J. da Silva Barros and R. B. Filho, “Turbo codes with symmetric and asymmetric component codes defined over finite
fields of integers,” IET Communications, vol. 3, no. 11, pp. 1800 –1807, Nov. 2009.
[7] A. Ghrayeb and T. Abualrub, “Asymptotic performance comparison of concatenated (turbo) codes over GF(4),” Int. J.
commun. syst., Mar. 2004.

20

[8] A. J. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Trans.
Inform. Theory, vol. 13, pp. 260–269, Apr. 1967.
[9] L. Gong, W. Xiaofu, and Y. Xiaoxin, “On SOVA for nonbinary codes,” IEEE Commun. Lett., vol. 3, no. 12, pp. 335 –337,
Dec. 1999.
[10] S. Lin and D. J. Costello Jr., Error Control Coding: Fundamentals and Applications.

Prentice-Hall, Inc., 1983.

[11] W. E. Ryan and S. G. Wilson, “Convolutional codes over GF(q) with applications to frequency-hopping channels,” in Proc.
MILCOM, Washington, Oct. 1987.
[12] L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE
Trans. Inform. Theory, vol. 20, no. 2, pp. 284 – 287, Mar. 1974.
[13] G. Liva, S. Scalise, E. Paolini, and M. Chiani, “Turbo codes based on time-variant memory-1 convolutional codes over
Fq,” in Proc. ICC, June 2011.
[14] A. V. Oppenheim, A. S. Willsky, and S. Hamid, Signals and Systems, 2nd ed.

Prentice-Hall, 1996.

[15] M. Mandal and A. Asif, Continuous And Discrete Time Signals And Systems.

Cambridge University Press.

[16] G. J. Byers and F. Takawira, “Fourier transform decoding of non-binary LDPC codes,” in Proc. SATNAC, Western Cape,
South Africa, Sep. 2004.
[17] R. G. Gallager, Information theory and reliable communication.

New York: Wiley, 1968.

[18] M. C. Davey, “Error-correction using low-density parity-check codes,” Ph.D dissertation, Univ. of Cambridge, Cambridge,
U.K., Dec. 1999.
[19] R. A. Beezer, A first course in linear algebra.

Congruent Press; 3 edition, Dec. 2012.

[20] A. V. Oppenheim, R. W. Schafer, and J. R. Buck, Discrete-time signal processing.

Prentice Hall, Aug. 2009.

21

100
Bidirectional BCJR MAP
Dual encoder shift register combined output

Bit Error Rate

10

-1

Dual encoder forward+backward

10-2

10-3

10-4

10-5

10-6

4

5

6

7

8

9

E b /N0 dB

Fig. 16: BER performance of g(x) = 1 + x code over AWGN channels.

22

100
Bidirectional BCJR MAP
Dual encoder shift register combined output

Bit Error Rate

10

-1

Dual encoder forward+backward

10-2
10-3
10-4
10-5
10-6

4

5

6

7

8

9

E /N dB
b

0

Fig. 17: BER performance of g(x) = 1 + 3x + 2x2 code over AWGN channels.

23

100
Bidirectional BCJR MAP
Dual encoder shift register combined output

Bit Error Rate

10

-1

Dual encoder forward+backward

10-2

10-3

10-4

10-5

10-6

4

5

6

7

8

9

E / N dB
b

0

Fig. 18: BER performance of g(x) = 1 + x + 2x2 code over AWGN channels.

24

100
Bidirectional BCJR MAP
Dual encoder shift register combined output

10

-1

Dual encoder forward+backward

Bit Error Rate

10-2

10-3

10-4

10-5

10-6

4

5

6

7

8

9

E /N dB
b

0

Fig. 19: BER performance of g(x) =

1+x
1+2x

code over AWGN channels.

25

100
Bidirectional BCJR MAP
Dual encoder shift register combined output

10

-1

Dual encoder forward+backward

Bit Error Rate

10-2

10-3

10-4

10-5

10-6

4

5

6

7

8

9

E b /N0 dB

Fig. 20: BER performance of g(x) =

1+3x+2x2
1+x+2x2

code over AWGN channels.

