6.3 Turbo Coding

Turbo codes are one of the few FEC codes to come close to the Shannon limit, the theoretical limit of the maximum information transfer rate over a noisy channel. The turbo codes were proposed by Berrou and Glavieux (from ENST Bretagne, France) in 1993. The main feature of turbo codes that make them different from the traditional FEC codes are the use of two error-correcting codes and an interleaver. Decoding is then made iteratively taking advantage of the two sources of information.

Data transmission is coded as follows (see Figure 6.7). Three blocks of bits are sent. The first block is the m-bit block of uncoded data. The second block is n/2 parity bits added in sequence for the payload data, computed using a convolutional code. The third subblock is another n/2 parity bits added in sequence for a known permutation of the payload data, also computed using a convolutional code. Hence, two different redundant blocks of parity bits are added to the sent payload. The complete block has m + n bits of data with a code rate of m/(m + n), as shown in the figure.

image from book
Figure 6.7: Turbo coded sequence generation

The data decoding process is the major innovation of turbo codes. The likelihood is used in order to take advantage of the differences between the two decoders. The turbo code inventors like to make the parallel with solving crosswords through both vertical and horizontal approaches.

Each of the two convolutional decoders generates an hypothesis, with derived likelihoods. for the m-bits sequence, called the a posteriori probability (APP). The hypothesis and the received sequence (recalculated) parity bits are compared and, if they differ, the decoder exchanges the derived likelihoods it has for each bit in the hypotheses. An iterative process is run until the two convolutional decoders come up with the same hypothesis for the m-bits sequence. The number of steps is usually of the order of 10.

6.3.1 Convolutional Turbo Codes (CTC)

Different classes of turbo codes exist. Convolutional Turbo Codes (CTC) are defined as opptional FEC for OFDM and OFDMA PHY. For OFDMA PHY, the CTC can be used for the support of the optional Hybrid ARQ (HARQ, see Chapter 8). According to mobile WiMAX profiles, the CTC is mandatory for OFDMA PHY. A brief overview of the CTC defined for OFDMA PHY is proposed here.

The CTC encoder, including its constituent encoder, is depicted in Figure 6.8. It uses a double binary Circular Recursive Systematic Convolutional Code. The bits of the data to be encoded are alternatively fed to A and B, starting with the MSB of the first byte being fed to A. The encoder is fed by blocks of k bits or N couples (k = 2N bits). For all the frame sizes, k is a multiple of 8 and N is a multiple of 4. Further, N is limited to 8 ≤ N/4 ≤ 1024.

image from book
Figure 6.8: OFDMA PHY Convolutional Turbo Code (CTC) encoder. (From IEEE Std 802.16-2004 ^[1]. Copyright IEEE 2004, IEEE. All rights reserved.)

The encoding block size depends on the number of subchannels allocated and the modulation specified for the transmission. Concatenation of a number of subchannels must be performed in order to make larger blocks of coding where it is possible, with the limitation of not passing the largest block under the same coding rate. The concatenation rule should not be used when using HARQ. A table providing the number of subchannels concatenated as a function of the number of subchannels is given in the standard.

Figure 6.9 shows a block diagram of CTC subpacket generation. The CTC encoded codeword with a coding rate of 1/3 goes through the interleaving block and puncturing is performed. FEC structures proposed in the standard ^[1] puncture the mother codeword to generate a subpacket with various coding rates: 1/2, 2/3, 3/4 and 5/6. The subpacket may also be used as HARQ packet generation (with different SPIDs). The length of the subpacket is chosen according to the needed coding rate, reflecting the channel condition (this is link adaptation).

image from book
Figure 6.9: Block diagram of subpacket generation. (From IEEE Std 802.16-2004 ^[1]. Copyright IEEE 2004, IEEE. All rights reserved.)

6.3.2 Block Turbo Codes (BTC)

Block Turbo Codes (BTC) are defined as an optional FEC for OFDM and OFDMA PHY. The BTC is also optional in WiMAX profiles.

For OFDM and OFDMA PHY, the BTC is based on the product of two simple component codes, which are binary extended Hamming codes or parity check codes. The codes are not the same for the two PHYs. BTC component codes of OFDM are shown in Table 6.1. The component codes are used in a two-dimensional matrix form, which is depicted in Figure 6.10. The k_x information bits in the rows are encoded into n_x bits by using the component block (n_x, k_x) code specified in the standards for the respective composite code. After encoding the rows, the columns are encoded using a block code (n_y, k_y), where the check bits of the first code are also encoded. The overall block size of such a product code is n = n_x n_y, the total number of information bits k = k_x k_y and the code rate is R = R_x R_y, where R_i = k_i/n_i, i = x, y. Data bit ordering for the composite BTC matrix is defined such that the first bit in the first row is the LSB (Least Significant Byte) and the last data bit in the last data row is the MSB.

Table 6.1: BTC component codes of OFDM PHY. (From IEEE Std 802.16-2004 ^[1]. Copyright IEEE 2004, IEEE. All rights reserved)
Open table as spreadsheet
Component code (n,k)	Code type
(64,57)	Extended Hamming code
(32,26)	Extended Hamming code
(16,11)	Extended Hamming code
(64,63)	Parity check code
(32,31)	Parity check code
(16,15)	Parity check code
(8,7)	Parity check code

To match a required packet size, BTCs may be shortened by removing symbols from the BTC array. In the two-dimensional case, rows, columns, or parts thereof, can be removed until the appropriate size is reached.