Forward Error Correction Convolutional Codes for RTAs' Networks: An Overview

• I.    Introduction

  Forward error correction (FEC) is a digital channel coding algorithms used in data communication to correct data transmission errors without retransmission [1] . This scheme is divided into block codes and convolutional codes [2] , [3] , [4] . FEC Convolutional Codes (FEC-CC) were introduced by Elias in 1955 as an alternative to the class of block codes and they are widely used in many applications such as mobile communication, digital video, and satellite communication to achieve reliable data transfer [5] , [6] , [7].

In recent years, the world has witnessed a large increase in the use of modern wireless mobile devices that run multimedia applications [8] . Hence, there is rapid growth of e-business, higher data transmission rates, larger bandwidth demand and enhanced networks reliability to support the exponentially growing data transmission needs. The 2013 International Telecommunication Union (ITU) statistics showed that global mobile cellular subscription reached 6.8 billion users worldwide, with global penetration rate of 96

percent, 128 percent penetration rate in developed world and 89 percent in developing countries [9] . According to Cisco Visual Networking Index, global mobile data traffic reached 885 petabytes after offloading 429 petabytes per month to fixed network at the end of 2012. This is 96 percent traffic increase before offloading and 70 percent increase after offloading [10] .

To cope with the requirement of bandwidth for data transmission, average mobile network speeds have increased more than two folds in the year 2012. The global average mobile network downstream increased from 248 kilobits per second (kbps) in 2011 to 526 kbps in 2012. Global average mobile network connection speed for smart phones grew from 1211 kbps in 2011 to 2064 kbps in 2012. The tablets on the other hand, grew from 2032 kbps to 3683 kbps [10] . This trend of constant increase in transmission rates of mobile wireless transmission creates another problem that requires immediate attention. The formation of burst errors in data transmitted due to high transmission speed [11] and the fact that error conditions of wireless media vary widely in fading channels creates burst errors decoding challenge to FEC codes that manages the errors at the receiving device [12] .

N. Hajlaoui et al. [13] , presented experimental results on frame aggregation enhancement in IEEE 802.11n WLANs which showed that aggregation sometimes degrades quality of service of some RTAs by adding more jitter and delay in data transmission. Another experimental results done by Alaa [14] showed that even cloud computing sometimes do not offer the required quality of service to support RTAs due to increase in computation and transfer time. Similarly, it has been reported that Internet networks sometimes fail to provide the quality of service that is needed for RTAs interaction through groupware [15] , [16] .

This paper investigates Convolutional Codes as one of the most commonly used algorithm in FEC and an alternative to ARQ mechanisms. The investigation aims to improve the FEC-CC’s operational performance to support RTAs networks.

The remaining part of this paper is organized in the following manner: Section II of this paper describes the binary Convolution Codes, the encoding and decoding processes. It also analyses, evaluates and compares the decoding computational complexity challenges of

Sequential and Viterbi algorithms. Section III, discusses various techniques used to enhance performance of binary convolutional codes to improve its operational performance with their impacts to data communication systems. Section IV explains the key observations made. Section V concludes these efforts and gives recommendations for future research.

II. Binary Convolutional Codes

Fig 1: (2, 1, 2) Convolutional encoder

Convolutional codes are popular class of coders with memory, where the current output data block from the encoder is not only a function of the current input block but also of other previous data blocks. Binary convolutional codes are commonly defined by three parameters, ⁽ n , k ’ m ) where n is a number of output bits (bits in a codeword) from the encoder and, k is a number of input bits to the encoder at a time while m is a number of memory size used in that encoder. Therefore,

the hardware connection of the shift register taps to the modulo-2 adders. A generator vector represents the position of the taps for an output. A “1” represents a connection and a “0” represents no connection.

⁽ n , k , m ) binary convolutional code

generates n

encoded data bits for every k data bits, where n >  k .

⁽ n  k ) is a number of redundancy bits

added to data

bits. The redundancy bits are used by decoder to recover the distorted information. Factor k n is a code rate r of that particular convolutional encoder. Convolutional encoder is also characterized by its constraint length ⁽ K ) which is given by; K = m + ¹ where m is the memory stage of the used shift register. Constraint length

A. Encoding Binary Convolutional Codes

Apart from the generator sequences used in the previous section, state, tree and trellis diagrams demonstrate and provide better understanding of internal operations and processes of a binary convolutional encoder and decoder.

State diagram of a (2, 1, 2) binary convolutional encoder can be treated as a finite state machine where the contents of the shift register represents the states. The

v output of a code block t at time t depends on the

s current state

u t and the data block t . Each change of

relates to the

depends. Fig.

encoder with

. Z- = 1 input length K = 3 .

number of bits upon which the output 1 shows a standard ⁽ 2 ^{,1,2 )} convolutional rate r = ¹² , where output n = ² ,

, memory size m ² and constraint . For each input bit, there are 2 output bits,

ss state from t to t+1 is associated with the input of a data block and the output of a code block. The state diagram is obtained by drawing all possible contents (states) of the registers with arrows that show all possible state transitions from the current state to the next state. In Fig. 2, nodes are all possible states of the standard encoder shown in Fig.1 with labeled arrows (inputs/outputs that

which depend on the previous 2 input bits. The encoder consists of an m-stage shift register together with modulo-2 adders and a multiplexer for serializing the encoder outputs.

If the input sequence is u = ( u ₀, u_x , u ₂ ••••) , the two

uv correspond to t t

) indicating the state transitions. The

encoder maps the input block of data to output block of

codewords. Table I, Fig. 2, Fig. 3, and Fig.4 show an

example

of     encoding      (1  1  0  1)      to

encoder output sequences v ¹ = ( v 1 , v 1 , v 1 ....) and 2 222

v = ( v ₀ , v j , v ₂ ....) are equal to the convolution of the input sequence u with the two code generator sequences g ¹ = (1,1,1) and g ² = (1,0,1) i.e., the encoding equations are v ¹ = u * g ¹ and v ² = u * g ² where * is a convolution operation. Generator representation shows

(11  01  01 00) using different presentation diagrams.

The white nodes in Fig. 3 and Fig. 4 show the encoding path of the same data.

Node content corresponds to a shift register contents:

S 0 = 00, S 1 =01, S 2 =10 and S 3 =11.

Path labels:

u/v1v2 -input/output(Data/Codeword)

Fig 2: (2, 1, 2) binary convolutional encoder state diagram

Table I: Encoding (1-1-0-1) to (11-01-01-00)

Input bit “u” (data)	Input State	Output bits “v1v2” (Codewords)	Next State
1	S 0	11	S 2
1	S 2	01	S 3
0	S 3	01	S 1
1	S 1	00	S 2

It is customary to start and terminate the encoding process at all zero state s ⁰ (00), therefore, in actual implementation of binary convolutional encoder tail bits are added to input data to push the encoder memory to all zero state. This fact makes the binary convolutional encoder to have a design rate and an implementation rate whereby implementation rate is always smaller than the actual design rate.

Tree diagram can also be used to demonstrate the encoding and decoding processes. Referring to Fig.3 the encoding process starts from left towards the right with time interval L , the nodes are the states of the register { «Ш¹⁰,¹¹ } tha_t corresponds to { s 0 . ^s | . ^s 2 , s 3 ! respectively.

4 Terminating Tail Bits

Key

Path branch labels:

u/v1v2 – input/output (data/codeword)

Fig 3: Tree diagram of (2, 1, 2) binary convolutional code

A code tree of ⁽ n , k , m ) binary convolutional code presents every codeword as a path on a tree. For input sequences of length L bits, the code tree consists of

₂ kL

paths; this makes it a bit difficult to manage when working with long input blocks.

Key

Path branch labels:

u/v1v2 – input/output (data/codeword)

Fig 4: Trellis diagram of (2, 1, 2) binary convolutional encoder

Trellis diagrams as named by Forney [17] and shown in Fig. 4 is a structure obtained from a code tree by 2m nodes kL to be shown and the same 2 paths in the trellis diagram at each time interval.

• B.    Decoding Binary Convolutional Codes

The encoded kL codewords bit sequences are then modulated to relevant signals (waveforms) for transmission through a medium. The characteristics of the medium introduce noise to the sent signals and distort them [18] . The distorted signal is said to have transmission errors. Transmission errors in digital communication can occur in a single bit where a bit in a data block is distorted or multiple bits where many but not consecutive bits in a data block are distorted or burst bits where many and consecutive bits are distorted in a data block [19] . Transmission errors cause the receiver to receive different data from the sent one, hence the need to have a mechanism of identifying errors and estimating the original sent data to correct the transmission errors.

Estimation mechanism at the receiving end is conceptually divided into two main parts: demodulation and decoding [20] . The demodulator transforms the received waveforms into discrete signals for the decoder to determine the original data sequences. If the discrete demodulated signal is binary (i.e. 0 and 1), then the demodulator is called a hard-decision demodulator and its subsequent decoder is also termed a hard-decision decoder. If the demodulator passes analog (i.e., discretein-time but continuous-in-value) or quantized outputs to the decoder, then it is called a soft-decision demodulator and its subsequent decoder is also called soft-decision decoder. Uncorrected or wrongly estimated data by demodulator are forwarded to a decoder for further transmission error suppression. The remaining part of this section discusses the Fano and Stack sequential algorithms; and the Viterbi algorithm for decoding binary convolutional codes. In general, the decoding process of FEC codes with errors is more difficult than the encoding process at the sender [18] .

• C.    Fano algorithm

  Decoding binary convolutional codes using Sequential algorithm was first introduced by Wozencraft in 1957 [21] , [22] . In 1963, Fano [23] extended the algorithm by improving decoding efficiency. Fano algorithm can be well described by analogy. Imagine being given some guidelines to go to a place using landmarks, but the guidelines were poorly given and sometimes landmark is not recognized giving a feelling of being on a wrong path. Then one stops and backtracks to a point where one recognizes a landmark and takes an alternative path until the next landmark is seen. Eventually, in this fashion one manages to reach the destination. In this process, one may back track several times depending on how good the guidelines were. This is quite similar to searching on a tree (refer to the tree diagram in Fig. 3). Fano decoder allows both forward and backward movements through the trellis or tree. The decoder keeps track of its decisions and tallies it up. If the tally increases faster than a given threshold value, then the decoder drops that path branch and retraces back to the last divergence point where the tally was below the threshold and then consider an altenative branch.

Fano Algorithm requires small memory to keep track of its three paths in a tree, the current path, immediate predecessor and one of its succesor path. This information enables the algorithm to move forward and backward using its dynamic threshold. Althogh Fano algorithm has very high node computation load but it has less evaluation cost compared to that of the stack algorithm [24] discussed in the next subsection.

Considering a binary convolutinal encoder discribed above, Fano algorithm suffers an exhaustive ^{2 kL} tree searches for decoding ^kL encoded data bit sequences. The exhaustive tree search composes a computational complexity in the order of ^{(2 )} , where k is a number of parralel input data to the binary convolutional encoder at one time interval and L is the number of time intervals. The computational complexity of the decoding process using this algorithm becomes worse if multiple or burst transmission errors are experienced, because they increase the probability of the algorithm backtracking and sometimes with the posibility of revisiting same paths more than once [20] . Furthermore, complexity of this algorithm increases with the increase of length L of a codeword sequence, thus, this method is effective for short block length. However, increasing the number of input bits ^k at a time improves the code rate and hence the data throughput. On the other hand, increasing of input bits k at a time, increases the Fano algorithm decoding complexity. This algorithm has variable computational delay hence not attractive for most of the delay sensitive RTAs [25] , [26] .

In implementation, Fano algorithm has been improved in different ways to improve its operational performances. Two uni directional or two bidirectinal parrellel Fano decoders have been designed to work together [25] , [26] , [27] , [28] .

• D.    Stack Algorithm.

The work done by Fano was further developed by Zigangirov [29] , and then by Jelinek [30] who proposed the sequential stack algorithm. In spite of the fact that Stack algorithm is different in its design from the Fano algorithm, it behaves in the same way as the Fano algorithm in a tree search. It has been proven that both algorithms visit about the same set of nodes and paths in the decoding process [20] , [31] . Stack algorithm uses a stack utility to store the decoded data, and therefore, it needs a sorting procedure to rearange the stack contents when the system is backtracking from time to time. The sorting process is time consumming and hence Stack algorithm is more costly than a non sorting fano algorithim [20] , [24] . Contrary to Fano algorithm which may revisit a path several times and hence higher computational complexity, the Stack algorithm visits a path once. However, Stack algorithm has also a stack size drawback in that if a large number of paths are examined during the search process, a stack overflow can happen which simply discards paths with the smallest function value. This fact degrades the algorithm performance if the discarded path happens to be an early predecessor of the optimal code path [32] , [33] . Recent studies show the use of hybrid stack algorithms in multiple antennas at transmitter and receiver, multiple-input multiple-output (MIMO) wireless communication system for wireless transmission error detection only and not for transmission error correction [34] . The main disadvantage of stack algorithm is time delay because of backtracking [34] , [35] . This shortcoming makes the sequential algorithims too oblivion compared to other algorithims such as Virterbi algorithm [36] , [37] .

• E.    Viterbi Algorithm

  Viterbi decoding was introduced by Viterbi in 1967 [38] . It is probably the most popular and widely adopted in practice decoding algorithm for Convolutional codes [6] . This algorithm is also the best known implementation of the maximum likelihood decoding [20] , [39] , [40] . The Viterbi decoder examines an entire received data sequence of a given length at a time interval on a trellis, then computes a metric for each path and makes a decision based on this metric. One of the common metric used by Viterbi Algorithm for paths comparison is the Hamming distance metric, which is a bit-wise comparison between the received codeword and the allowable codeword, Table IIA and Table IIB show how the calculation is done. The Hamming metrics are calculated for each path branch in every time interval and then cumulatively added to get a total path metric of up to time ^L or L + m .

There are two methods of calculating a Hamming distance metric; Table IIA describes a method where the surviving path with the highest total Hamming metric is considered to be the final winner. Table IIB describes the opposite method where the path with the lowest total metric is the final winner. The decoding example in this paper (Fig. 5) uses the method described in Table IIA.

Table II a: Hamming metric calculation

Received Codeword	Valid Codeword 1	Hamming Metric 1	Valid Codeword 2	Hamming metric 2
11	00	0	11	2
01	11	1	00	1
01	01	2	10	0

Table II b: Hamming metric calculation

Received Codeword	Valid Codeword 1	Hamming Metric 1	Valid Codeword 2	Hamming metric 2
11	00	2	11	0
01	11	1	00	1
01	01	0	10	2

In decoding the received binary convolutional codewords using trellis diagram, all paths are followed until two or more paths converge on one node. The paths with higher metric (also known as survivor paths) are kept and those with lower metric are discarded. The surviving paths are further compared again and again whenever they converge in a node to get a winning 2m survivor

S paths can be forced to converge at state 0 if m zeros were added as terminating tail bits to the binary convolutional encoder (see Fig. 4).

Fig. 5 shows an example of a Viterbi algorithm in decoding codeword stream obtained in Table I (i.e. 1101-01-00), received with a single transmission error in position 3 (i.e. 11-11-01-00) to (1-1-0-1). Decoding is the reverse process of the encoding process shown in Fig. 4 and the Viterbi decoder starts from state S0. The received codewords (on the top line of Fig. 5) are compared bit by bit with the allowed codewords obtained from the Viterbi decoder using the method described in Table IIA to obtain the branch metrics. In Fig. 5, path branch metrics are put in path labels using a round bracket i.e. (x). The cumulative path metrics are put in a square bracket i.e. [x]. The decoding process in Fig. 5 follows the following four steps:

• •    The allowed path codeword is compared with the received codeword for that particular time interval and the results put in a round bracket (i.e. (x)) as path branch metric.

• •    The path cumulative hamming metric of the current path branch is found by adding the obtained branch metric to the cumulative path metric of the immediate predecessor surviving path. Note that, the first path branches from the starting node do not have immediate path branch predecessor, therefore, the cumulative branch path metric of their immediate predecessor is zero.

• •    The cumulative path branch metrics of the branches which  converge in  a node are

compared. The  branch path  with higher cumulative branch path metric is a survivor path and kept while other paths are discarded. If the converging paths have the same cumulative path metrics, then they are all kept. Step one to three is recurring at each time interval L of the trellis diagram.

• •    Eventually, the cumulative hamming metrics of all the surviving paths are compared. The surviving path with highest hamming metric is the final winner and data are extracted from this path. If more than one path has the same highest cumulative path metrics then one of the surviving paths with highest cumulative path metric is arbitrarily selected as a final winner.

Out of the 2 ^kL exhaustive searches of different paths on trellis, Viterbi Algorithm reduces this number by searching one stage at a time in the trellis diagram. In each node of the trellis there are 2 ^k calculations and the number of nodes per stage in a trellis is 2 ^m . Since all the stages in the trellis are ^L + m , then the complexity of Viterbi Algorithm is reduced to the order of(2 ( k + m ) ( L + m )). It should also be noted that the time interval L is now a linear factor and not an exponent factor in complexity. The algorithm eliminates least likely trellis path at each data decoding stage and therefore the reduction of decoding complexity with early rejection of unlikely surviving paths [42] . Unlike Stack algorithm in a stack overflow, Viterbi algorithm maintains all the paths which are likely to be winning survival paths [33] .

Single bit Error

Received      11

Codewords

Key

Labels:

xx/y - Allowed Codeword/Output

(x) - Branch path Hamming Metric

[x] - Cumulative path Hamming Metric

Paths:

- Paths with lower Hamming metrics (Non surviving paths are discarded)

- Paths with higher Hamming metrics(Surviving paths are kept)

- Winning surviving path

Fig 5: Trellis diagram of a Viterbi decoder in decoding the received codewords with error in position 3 (i.e. 11-11-01-00) to (1-1-0-1)

An increase in m improves error correction capabilities of binary convolutional codes [43] , [7]. However, it should be noted that Viterbi Algorithm has m as an exponent factor on its decoding computational complexity, hence the maximum practical limit of length of K is 10 [41] . Contrary to Viterbi Algorithm,

Sequential decoding can achieve a desired bit error probability when a sufficiently large constraint length is taken for the binary convolutional code. These specific characteristics make the sequential decoding algorithms useful for special type of applications [20] .

• F.    Computational Complexity Comparison of Sequential

Vs Viterbi Algorithms

Let us assume that both algorithms decode the received codewords encoded by a binary (2, 1, 2) Convolutional encoder where the input k and memory length m are constants 1 and 2 respectively. Since Fano and Stack algorithms have proven to visit almost the same nodes and paths in decoding, then they have almost the same order of ^{(2 )} computational complexity. Viterbi

( k + m )

algorithm has the order of (     ( + m)) Computational complexity. Table III compares the decoding computational complexity of the Sequential and Viterbi algorithms.

Fig. 5 shows the results of the computational complexity of the Sequential and Viterbi algorithms simulated using MATLAB software. The simulation results in Fig. 5 show that, an increase in block length L causes an exponential increase in decoding computational complexity of the Sequential algorithms. Incomparably, Viterbi algorithm has a small linear increase of the decoding computational complexity. Algorithm with high computational complexity will practically be too slow to support RTAs.

Table III: Computational Complexity of Sequential and Viterbi decoding

Increase in Input Block length (L)	Sequential decoding Complexity (2L)	Viterbi decoding Complexity (16 +8L )
1	2	24
2	4	32
3	8	40
4	16	48
5	32	56
6	64	64
7	128	72
8	256	80
9	512	88
10	1024	96

Decoding Computational Complexity

0      1      2      3      4      5      6      7      8      9     10

Increase in Data Block length (L)

Fig 6: Comparison of Sequential and Viterbi decoding computational Complexity

• III.    Enhensing Convolutional Decoding

In general, binary convolutional decoding algorithms can work well with a single bit transmission error and hardly with spaced multiple bits transmission errors in a data block [43] . However, decoding binary convolutional codes is a difficult task especially when burst errors occur in a data block [18] , [44] . According to Nouh et al. [18] , decoding of error correction codes is a Non-deterministic Polynomial-time hard problem (NP-Hard problem). Therefore, the quality of a decoder highly depends on industrial requests. Sometimes few transmission errors are tolerated in favor of the reduction of the code complexity. When a high quality decoder is needed, other mechanisms such as hybrid code system or code concatenation, code puncturing and code interleaving are used to support decoders.

Ján Poctavek [45] with his research team in 2011 noted that, Hybrid codes that combine convolutional codes with other types of FEC or even Automatic Repeat Request algorithms (ARQ) are used to increase error correction capability. In hybrid codes the involved algorithms are put either in serial or parallel with the convolutional code, another good example of this can be seen in the work by T-Y. Chen et al. [46] where a Modified Incremental Redundancy with Feedback (MIRF) allows short convolutional codes to deliver bit error rate performance similar to a long block length turbo code, but with lower latency. Many other examples of this type can be seen in M. Francis and R. Greens’ contribution [47] . However, it is important to note that hybrid codes are used when individual codes or algorithms fail to meet the required quality of service.

The second alternative is to apply a code puncturing technique. Code puncturing allows an encoder-decoder pair to change their code rates r , which is the code error correction capabilities without changing their basic structure [48], [49]. Code puncturing involves deleting certain code bits. Puncturing convolutional codes was introduced by Cain, Clark and Geist in 1979 [50] and further modified by Hagenauer in 1988 [51]. These codes draw attention of many developers because of their flexibility to wireless channel. On the other hand, puncturing adjacent bits result in burst error which in turn degrades the binary convolutional encoder/decoder ability to recover lost bits [49].

Another alternative in supporting FEC to combat the effects of multiple and burst errors is the use of an interleaving utility [37] , [52] , [53] . Interleaving simply involves rearranging data bits from two or more codewords before transmission on the channel [54] . Interleaving process is done by writing data bits row-byrow into a x b matrix and reading out column-by-column before sending the data over the channel. The reverse process (de-interleaving) is performed at the receiver to get the original arrangement. This process results into each successive bits of any given codeword to have a - 1 symbols that belong to other a - 1

• IV.  Remarks and Discussion

The analysis made from the literature reviewed on FEC convolutional codes, a number of factors affecting operational performance have been observed as follows:

• •    Decoding binary convolutional codes received with errors is amongst the extremely difficult problems.

• •    Sequential algorithms have higher decoding complexity which depends on a dynamic exponential variable L (decoding block length). Decoding long block length using sequential decoder in a bad error condition results in a prohibitive amount of decoder computation overheads that may degrade quality of most RTAs.

• •    In Viterbi algorithm, block length L is a linear factor of the decoding computational complexity and has lower effect in the algorithm decoding computational complexity. Note that increase in block length L is favorable to a bad error condition.

• •    Convolutional codes work better with small code rate r , increase in number of inputs k improves the data transmission speed. However, when burst errors occur convolutional codes perform poorly without an interleaver.

• •    The use of interleaver helps decoders by converting transmission burst errors into a single bit error in each data block. However, interleaver results in higher delay.

• •    Increase in m (memory size) improves Viterbi algorithm error correcting capability. However, when constraint length K is higher than 10 the algorithm becomes impractical as it results in excessive delay due to exponential growth of its computational complexity. However, the memory size m is a fixed variable in a binary convolutional encoder.

This paper reviewed the computational challenges of the convolutional encoder-decoder with the aim to improve its operational performance in data communication networks to meet RTA’s requirements. It has been observed that improving the decoding part of the algorithm may yield better results in serving RTAs. Sequential and Viterbi algorithms for decoding binary convolutional codes were analyzed and compared to determine possible elements for improvement of binary convolutional codes. Sequential algorithms have shown high exponential increase of their decoding computational complexity and thus, too jittery to meet RTAs requirements. Exceptionally, Viterbi Algorithm has shown linear growth of its decoding computational complexity with the increase in data block length which indicates a good potential for improved performance. Therefore, future work entails the designing of an improved Viterbi algorithm to improve its operational performance.