Performance of Turbo Product Code Decoding in 802.16 Systems

Performance of Turbo Product Code Decoding in 802.16 Systems

Amruta P. Pokhare

Assistant Professor Atharva College of Engineering,

Mumbai, India.

Sachin Gavhane

Assistant Professor Atharva College of Engineering,

Mumbai, India.

Trushita Chaware Assistant Professor MIT Engg. College, Mumbai, India.

Nileema Pathak

Assistant Professor Atharva College of Engineering,

Mumbai, India.

Mohan Pawar

Assistant Professor

VES Institute of Technology, Mumbai, India.

Abstract– In this paper, the effect of TPC decoding using Chase-II algorithm with reduced number of test patterns (TPs) was evaluated using the AWGN channel in orthogonal frequency division multiplexing (OFDM) mode is discussed. TPC is constructed with multi-error-correcting extended Bose-Chaudhuri-Hocquengem (eBCH) codes. TPs are classified into different conditions based on the relationship between syndromes and the number of errors so that TPs with the same codeword are not decoded except the one with the least number of errors. The parameters considered are bit error rate (BER), Eb/N0, data rate and code rate.

There are total six simulated results drawn. Out off which three results represents BER versus signal to noise ratio (SNR) for eBCH(128, 113, 2) when p= 2, 3 in 802.16 system respectively. The simulated results show BER of 6.57 X 10-5 at SNR 1dB, BER of 3.9186 X 10-4 at SNR 1dB and 8.7557 X

1. at 1.5dB and BER of 8.1112 X 10-4 at SNR 1dB and 1.0572 X 10-5 at 2dB for eBCH(128,113,2) where p= 2, 3

   respectively. The other three results represent the percent of TPs decoded in 802.16 systems respectively.

   The research contribution shows that the percent of TPs need to be decoded for eBCH (128, 113, 2) when p = 2, 3 for 1st iteration it is between 22% – 10% and for 5th iteration onwards it is between 14% – 6% for SNR = 1.5dB, 1.8dB, 2.0dB, 2.2dB, 2.4dB and 2.5dB in 802.16 system, respectively. This research contribution helps to make the 802.16 systems simpler, reduces the decoding time, complexity and improves the performance.

   Keywords–Turbo product codes, Chase II algorithm, test patterns, extended BCH codes, 802.16 system.

   1. INTRODUCTION

      1. is commonly called as Worldwide Interoperability for Microwave access (Wi-MAX). It provides specifications for both fixed Line of sight (LOS) communication in the range of 10-66GHz (802.16c) and fixed portable Non-LOS communication in the range of 2- 11GHz (802.16a, 802.16d). Also it defines wireless communication for mobiles, moving at speed of 125 kmph, in the range of 2-6 GHz (802.16e). Earlier single carrier multiplexing was used, which faced a major limiting factor

         of Inter symbol interference (ISI). 802.16e is well implemented with Orthogonal Frequency Division Multiplexing (OFDM) as its physical layer scheme as an alternative for the Single carrier multiplexing [1]. Hence, it was decided to implement 802.16e OFDM systems.

         Efficient communication systems permit a high rate of information to be communicated with the lowest possible power. Commonly used error correcting codes for a wireless medium are Convolutional Turbo Codes (CTC). TPC is used instead of CTC. TPC with eBCH as a constituent code provides further benefits because eBCH codes are decoded easily using the syndrome method and it is used for multiple random error correction. A general comparison for parameters of CTC and TPC is as follows [2]:

         Code Rate:

         • CTCs perform best for low code rate applications

         • TPCs perform best for high code rate applications Data Rate:

         • CTCs will have difficulty achieving high data rates

         • TPCs operate at high data rates Error Floor:

         • CTCs exhibit error floor at BERs below 10-5

         • TPCs error floor is less pronounced and at lower BER values

      TPC provides a performance/complexity trade off and

      is effectively used in the latest wireless applications to its best capacity. TPCs have been used with hamming

      code as constituent coding for various wireless communication applications. TPC using hamming code is been proposed as an optional coding scheme in the 802.16 standard. TPC with BCH code in 802.16 systems is area where work is in progress. Promising features of TPC and BCH codes has led to the motivation to explore its implications in 802.16 systems.

      Soft input soft output (SISO) decoding techniques have to be used to get maximum benefit of coding. Exploring the features of decoding technique for TPCs in various communication systems is the motivation to choose TPC. The efficient decoding is always a need. To decode TPCs, the Chase algorithm [3] is repeatedly applied along rows/columns in order to obtain codewords and extrinsic information for each bit position. In Chase Pyndiah Algorithm [3], the number

      of Test Pattern (TP) increases with the number of least reliable bits and where all the TPs are to be decoded.

      Due to the need of high code rate and less decoding

      eBCH(128,11 QPSK OFDM

      Input Data

      3,2) as FEC Modulati Transm codes -on -itter

      AWGN

      Channel

      Chase II

      decoding

      with TP QPSK OFDM

      Demodulati

      complexity, TP reduction technique is needed in the

      reduction

      – Receive

      implication of 802.16 systems.

      This paper proposes the use of TPC for the purpose of error correction in 802.16 systems. To achieve high code rate with less decoding complexity, a method to reduce the number of test patterns (TPs) [4] decoded in the Chase-II algorithm constructed with multi-error-correcting extended Bose-Chaudhuri-Hocquengem (eBCH) codes is been used during the implementation of 802.16 systems.

      The rest of this letter is organized as follows. In Section 2, the proposed method is briefly described. Then in Section 3 the implementation of the Chase-II algorithm for TPC decoding is briefly described. Then, the proposed method with TP reduction is explained in detail. In Section 4, the complexity reduction in TPs is studied through simulations. Finally, conclusions are drawn in Section 5, followed by the acknowledgment and references.

   2. PROPOSED METHOD

      Error correction technique plays a very important role in wireless communication. Various channel coding techniques are used to detect and correct the errors at the receiver side. Turbo product code is one of the powerful error correcting technique which is used in Wireless Communication. This project proposes the use of TPCs for encoding and decoding. As stated in the introduction TPC performs best for high code rate and high data rate applications without any error floor. It also is a low cost method with simplified decoding and has low power consumption.

      The implementations of 802.16 system with a method to reduce the number of TPs decoded in the Chase-II algorithm for TPCs constructed with multi-error-correcting extended Bose-Chaudhuri-Hocquengem (eBCH) codes will be studied. The implementations of 802.16 system with a method to reduce the number of TPs decoded in the Chase- II algorithm for TPCs constructed with multi-error- correcting extended Bose-Chaudhuri-Hocquengem (eBCH) codes will be studied.The block diagram of proposed system has been shown in Fig 1.

      technique on -r

      Output

      Data

      Fig 1. Block diagram of proposed system

   3. CHASE DECODING WITH TP REDUCTION

      FOR TPC

      Assume C = (cep, c0, · · · , cn1) is a column or a row of a 2-D TPC built with eBCH(n+1, k, t),

      where ci {0,1}, i = 0,··· ,n 1,cep = c0 c

      • · · cn1, and is the exclusive OR operation. When

      C is transmitted over an additive white Gaussian

      noise (AWGN) channel with the BPSK assumption {0

      +1, 1 1}, the corrupted version, R = (rep, r0,···,rn1), will be obtained at the receiver. Then, from R, the hard-decision Y = (yep, y0, · · ·, yn1) and p LRB positions, j0, j1, ··· ,jp1, are obtained. Here, assume that

      rep is not one of the LRBs. In the Chase-II algorithm, 2p

      test patterns are formed by setting 0 or 1 in the LRB positions and 0 in other positions.

      Through the operation of exclusive OR between Y and each TP, 2p test sequences (TSs) are then obtained.

      Because one TP forms one TS, TP and TS are used interchangeably hereafter. The aim of the Chase-II algorithm is to find the maximum likelihood codeword among all the codewords decoded from these TSs and the extrinsic information for each decoded bit. In the following subsection 3.6.1, a brief description of Chase-II algorithm for TPC decoding [4], where the calculation of syndromes, even parity and metrics follows the method in [5], but with extension to t = 2. And then a TP reduced decoding method [4].

   4. CHASE-II ALGORITHM FOR TPC DECODING

      Since one TP is different from some other TPs in only one bit position, syndromes, even parity and metrics are calculated recursively. Therefore, it is necessary to initialize the syndromes, even parity and metric of the first TP (TP0) which is mentioned in equation 1, 2, 3, 4

      and 5 respectively.

      1 n1 | , (1)

      S0 = y0 y1x ··· yn1x

      3 n1

      x=

      3 (2)

      | ,

      S0 = y0 y1x ··· yn1x

      foreBCH2,

      x=

      5

      = y y x · · · y

      n1 5

      x |

      (3)

      the EC capability t is larger than the number of errors in

      S0 0

      1 n1

      eBCH3.

      x= , for

      those TSs. In order to reduce the decoding complexity, first find one TP with the least number of errors and then

      Even parity:

      P0 = yep y0 y1 · · · yn1.

      Metric:

      (4)

      reject other TPs that have the same codeword upon decoding. The representation of syndromes reveals the possible number of errors in TPs.

      Later, obtain and list this relationship and the number of

      l0 = 0. (5)

      = S

      1 b 1 j (6)

      S 2 +j j b ,

      TPs with the same codeword. For example, with eBCH2, when a TP has syndromes satisfying the first condition without errors, then all TPs that have one bit or two bits

      = S

      3 b 3

      S

      2 +j j

      3j

      b , for eBCH2,

      (7)

      different from the found TP will have the same codeword. TPs having errors greater than the EC capacity

      5 b

      S 2 +j

      = S 5 5j , for eBCH3, (8)

      j b

      P2b +j = Pj 1, (9)

      are not decoded and rejected directly. Some TPs are also rejected by checking the even parity. When the last condition as mentioned in table 1 [4], is encountered in

      l2b +j = lj (2yjb 1) rjb (10)

      2 +j

      Where j = 0, · · · , 2b, and b = 0, · · · , p 1; is the primitive element of GF (2m) that generates the coding polynomial; jb is the only bit position that TP b differs

      j j j

      from TPj . Only relative metrics lj are calculated in the above, because they are enough to find the maximum likelihood codeword and to evaluate extrinsic information [3], [6]. S 2, S 4 and S 6 need

      not to be calculated due to the fact that Sj2 = (S 1)2, S 4 =

      eBCH2 codes but the even parity value is 1 that means there are actually more than two errors existing. It is beyond the EC capacity of the eBCH2 codes. Therefore, such TP is also rejected directly.

      In existing methods syndromes and even parity are immediately used for error correction after they have been calculated. While in [4], the representation of syndromes and the values of even parity are exploited to classify TPs before the start of error correction process.

      (Sj1)4, and S 6 = (S 3)2.

      j j

      TABLE I. SYNDROMES, THE NUMBER OF ERRORS AND

      j j THE NUMBER OF TPS WITH THE SAME

      The above recursive calculation was the key point in [7], [5], the TP decoding complexity was not considered because the codewords determined from syndromes for the single-EC eBCH component codes. However, when multi- EC eBCH codes are considered, the process to find the error locator polynomial and error positions according to the

      syndromes requires many more operations [8]. For a TP

      (TP0) whos syndromes and even parity

      updating needs only one addition operation each, this decoding process dominates the complexity. Furthermore, once a codeword is obtained, the metric of corresponding TPs also need to be updated at the corrected error positions.

      As a result, reducing the number of TPs for the processes of codeword decoding and metric updating is important for TPCs with multi-EC components codes and is the focus of reference [4]. With the decoded codewords and their metrics, then the extrinsic information is evaluated from any one method from [3], [9].

   5. TPC DECODING WITH TP REDUCTION

      Suppose there are bit errors located at some LRB positions for particular TS. Then, there must be different TS which has no errors at the LRB positions because all possible variations in LRBs are enumerated by TPs. These two TSs may produce the same codeword after decoding, while the decoding complexity of the latter TS is smaller. Some other TSs may also be decoded to the same codeword as long as

      CODEWORDS FOR EBCH2

      Codes	Errors	Relationship
      		Syndrome conditions	Number of TPs having the same codeword
      eBCH2	0	S 1 = S 3 = 0 0 0	p(p + 1)/2 + 1
      	>2	S 1 = 0, S 3 0 0 0	Rejected
      	1	S 1S 3 = 0 0 0	p + 1
      	2	other	1 if Pj = 1 reject the TP

      After calculating syndromes and even parity, check whether there is a TP whose syndromes satisfy the first condition (number of errors is equal to 0) as mentioned in table 1. If one TP satisfies the condition, there is no need to do any decoding because the corresponding test sequence of this TP is the codeword itself. Then, directly reject all other TPs whose number of bit difference in LRBs compared with the found TP is within the EC capability t. All these TPs shall generate the same codeword when decoded.

      After the first condition has been checked and processed, the remaining TPs will be checked according to the next condition and certain TPs are rejected from decoding algorithm. It needs to be pointed out that this checking process, though actually binary comparisons, does not cause any additional cost. This is because in the conventional eBCH decoding of each TS, these conditions also need to be considered. In [4], since checking one condition is conducted only for the remaining TPs after processing previous conditions, this

      process in fact reduces the comparison cost and is beneficial with large complexity reduction in TP decoding.

      Example:

      For number of coded bits n = 7, number of information bits k = 4, error correction capacity t = 1

      m = 3

      n = 2m 1

      Assuming message bits = 1 1 1 1

      Transmitted code for this message is receivedcode = 1 1 1 1 1 1 1

      Assume error is at last bit, hence the received code will be receivedcode1 =1 1 1 1 1 1 0

      Let, least reliable bits (LRB) p = 2

      Assuming 1st and 2nd bits as LRB then following are the test patterns (TPs) generated:

      TP0 = 0 0 0 0 0 0 0

      TP1 = 0 1 0 0 0 0 0

      TP2 = 1 0 0 0 0 0 0

      TP3 = 1 1 0 0 0 0 0

      Now, generating the test sequences (TSs): TSs = receivedcoe1 TPs

      TS0 = 1 1 1 1 1 1 0

      TS1 = 1 0 1 1 1 1 0

      TS2 = 0 1 1 1 1 1 0

      TS3 = 0 0 1 1 1 1 0

      Considering GF (2m) = GF (2 3) = GF (8) where generator polynomial is 3 + + 1 = 0.

      According to equation 3.19 and equation 3.20 syndromes for TS0 are calculated as follows:

      S01 = + 2 + 3 + 4 + 5 + 6

      TABLE II. TPC IN 802.16 SYSTEMS PARAMETERS

      Modulation	Data Block Size (k x k)	Coded Block Size (n x n)	Code Rate
      QPSK	12769 bits	16384 bits	0.779

      The need of using complex interleaver as in case of CTC and doing its optimization using different techniques as explained in [10], for obtaining better BER is avoided. Chase Pyndiah algorithm as explained above in section

      3.3.2 is applied for 8 iterations for decoding the TPC at the receiver. TPC is implemented in a 128 point FFT OFDM systems. Modulation method used is QPSK. The results, which are plotted using Monte Carlo simulation method for iteration 2, iteration 4, iteration 6 and iteration 8 as shown in Figures 2, 4 respectively.

      In this paper, there are total 4 simulation results drawn, out off which two represents BER versus SNR for eBCH (128,113,2) where p= 2, 3 respectively as shown in

      figures 2, 4 respectively. The other 2 represents the percent of TPs decoded for eBCH (128, 113, 2) when p = 2, 3 for SNR=1.5dB, 1.8dB, 2.0dB, 2.2dB, 2.4dB and

      2.5dB in 802.16 systems, as shown in Figures 3, 5 respectively.

      The percent of TPs decoded for eBCH(128,113,2) when p

      = 2 for SNR=1.5dB, 1.8dB, 2.0dB, 2.2dB, 2.4dB and

      2.5dB in 802.16 systems, is depicted in Figure 3[11]. These results indicate that for one block size (128X128),

      st

      S01 = + 2 + +1 + 2 + + 2 + + 1+ 2 + 1

      22% of TPs are actually decoded at the 1 iteration for

      S01 = 1

      S03 = 3 + 6 + 9 + 12 + 15 + 18

      S03 = + 1 + 2 + 1 + 2 + 2 + + 1 + + 2 +

      S03 = 1

      SNR 1.5dB. The percentage of TPs being decoded decreases dramatically with the increase of iteration number as well as the increase of SNR. At 1st iteration the percent of TPs decoded where 20%, 19%, 18%, 16%

      for SNR 1.8dB, 2dB, 2.2dB, 2.5dB respectively as shown

      According to table 1 conditions:

      1st condition (number of errors is equal to 0): S01

      = S03 =

      in Figure 3[11]. And from 5th iteration onwards the

      0

      0

      0

      0 is not satisfied. 2nd condition (number of errors are greater than 2): S01 = 0, S 3 0 is not satisfied. 3rd condition (number of errors is equal to 1): S 1 S 3 =

      percent of TPs decoded where between 13%-12% for SNR=1.5dB, 1.8dB, 2.0dB, 2.2dB, 2.4dB and 2.5dB, as

      shown in Figures 2 respectively.

      1. (1 1 = 0) is satisfied. Since 3rd condition is satisfied no need to check 4th condition.

         Therefore, TS0 is decoded to get the correct bits=1 1 1 1 1

      2. 1 respectively.

   6. SIMULATION RESULTS

      The simulated results shows the implications of using TPC with constituent code of eBCH= (128,113,2)2 as a FEC in an 802.16e systems. To achieve high code rate with less decoding complexity, a method to reduce the number of test patterns (TPs) decoded in the Chase-II algorithm constructed with multi-error-correcting extended Bose- Chaudhuri-Hocquengem (eBCH) codes [4] is been used during the implementation of 802.16 systems. The parameters set for the systems where k=113 and n=128 as mentioned in Table 2.

      The Percent of TPs decoded for eBCH(128,113,2) when

      p= 3 for SNR=1.5dB, 1.8dB, 2.0dB, 2.2dB, 2.4dB and

      2.5dB in 802.16 systems, is depicted in Figure 5. These results indicate that for one block size (128X128), less than 14% of TPs are actually decoded at the 1st iteration for SNR 1.5dB. The percentage of TPs being decoded decreases dramatically with the increase of iteration number as well as the increase of SNR. At 1st iteration the percent of TPs decoded where less than 13%, 12%, 12%, 10% for SNR 1.8dB, 2dB, 2.2dB, 2.5dB

      respectively as shown in Figure 5. And from 5th iteration

      onwards the percent of TPs decoded where less than 8% for SNR=1.5dB, 1.8dB, 2.0dB, 2.2dB, 2.4dB and 2.5dB,

      respectively.

      The calculation of extrinsic information in this letter follows the method in [3] and the decoding performance is as shown in Figures 3 and 5 respectively.

      The simulated results gives BER of 6.57 X 10-5 at SNR 1dB for eBCH (128,113,2) where p= 2 as shown in Figure 2. BER of 3.9186 X 10-4 at SNR 1dB and 8.7557 X 10-5 at

      SNR 1.5dB for eBCH (128,113,2) where p = 3 as shown in Figure 4.

      Fig 2. BER versus Eb/N0 for TPC with eBCH(128,113,2) where p=2 in

      802.16 systems [11]

      Fig 3. Percent of TPs decoded when p=2 for TPCs constructed with eBCH(128,113,2) in 802.16 systems. Curves from top to bottom are for SNR=1.5dB, 1.8dB, 2.0dB, 2.2dB and 2.5dB, respectively [11]

      Fig 4. BER versus Eb/N0 for TPC with eBCH(128,113,2) where p=3 in

      802.16 systems

      Fig 5. Percent of TPs decoded when p=3 for TPCs constructed with eBCH(128,113,2) in 802.16 systems. Curves from top to bottom are for SNR=1.5dB, 1.8dB, 2.0dB, 2.2dB and 2.5dB, respectively.

   7. CONCLUSION

The effect of TPC (eBCH) channel coding method is evaluated using the AWGN channel in OFDM mode. The implemention of 802.16 system along with method [4] to reduce the number of TPs decoded in the Chase-II algorithm for TPCs constructed with multi-error-correcting extended eBCH codes, provides a better performance with respect to data rate, code rate, bandwidth and power gain, as compared to other available Codes.

Analysis of TPC (eBCH) is done considering parameters like BER, Eb/N0 ratio, characteristics of channel under consideration, noise variance of channel etc.

ACKNOWLEDGEMENT

I must thank, first and foremost, my guide Mrs. Trushita Chaware, Assistant Professor who gave me opportunity to write this paper. Without her guidance and patience, this dissertation would not be possible. Finally, I thank her to review and provide her invaluable suggestions that helped me to improve the quality of my paper.

REFERENCES

1. M. S. Baig, Signal Processing Requirements for WiMAX (802.16e) Base Station, M. Eng. thesis, Chalmers University of Technology, Goteborg, Sweden, 2005.

2. B. Thomson. (n.d.). Improving Bandwidth Utilization with Turbo Product Codes [Online]. Available:

   http://www.ewh.ieee.org/r6/scv/comsoc/0009.pdf

3. R. Pyndiah, Near-optimum decoding of product codes: block turbo codes, IEEE Trans. Commun., vol. 46, no. 8, pp. 1003- 1010, 1998.

4. G. T. Chen, L. Cao, L. Yu, and C. W. Chen, Test-Pattern- Reduced Decoding for Turbo Product Codes with Multi-Error- Correcting eBCH Codes, IEEE Trans. Commun., vol. 57, no. 2, pp. 307-310, 2009.

5. C. Argon and S. W. McLaughlin, An efficient Chase decoder for Turbo product codes, IEEE Trans. Commun., vol. 52, no. 6, pp. 896-898, 2004.

1. C. Berrou and A. Glavieux, Near optimum error correcting coding and decoding: Turbo-codes, IEEE Trans. Commun., vol.44, no.10, pp.1261- 1271, 1996.

2. S. A. Hirst, B. Honary, and G. Markarian, Fast Chase algorithm with an application in turbo decoding, IEEE Trans. Commun., vol. 49, no. 10, pp. 1693-1699, 2001.

3. T. K. Moon, Error Correcting Codes-Mathematical Methods and Algorithms, Hoboken, NJ: John Wiley and Sons, Inc., 2005.

4. N. Le, M. R. Soleymani, and Y. R. Shayan, Distance-based decoding of block Turbo codes, IEEE Commun. Lett., vol.

9, No. 11, pp. 1006-1008, 2005.

1. S.J.Park, and J.H.Jeon, Interleaver Optimization of Convolutional Turbo Code for 802.16 Systems, IEEE communications letters, vol. 13, no. 5, pp. 339-341, 2009.

2. A.P. Pokhare, T. Chware and R. Bansode, Performance of Turbo Product Code over wirelesscommunication, International Journal of Emerging Technology and Advanced Engineering, Volume 4, Issue 3, March 2014.