InnoWave Telecommunications

Interleaving

The decoding result of the convolutional code strongly depends on the frequency and grouping of bit errors that occur during transmission. Especially burst errors during long and deep fading periods, i.e. a series of erroneous sequential bits, have negative impact on error correction. In such cases, the channel is not a binary channel without memory, rather the single-bit errors have statistical dependence, which diminishes the result of the error correction procedure of the convolutional code. To achieve good error correction results, the channel should have no memory, i.e. the bit errors should be statistically independent. Therefore, burst errors occurring frequently on the radio channel should be distributed uniformly across the transmitted codewords. This can be accomplished through the interleaving technique described in the following.

The interleaving approach is to distribute codewords from the convolutional encoder by spreading in time and merging them across several bursts for transmission. This principle is shown in Figure 6.11. By time spreading, each of the codewords is distributed across a

Figure 6.11: Interleaving: spreading and merging

threefold length. Merging the bit sequences generated in this way has the effect that the individual bits from each of the three codewords are sorted into alternate bursts; this way each codeword is transmitted as distributed over a total of three bursts, and two bits of a data block are never transmitted adjacent to each other.

This kind of interleaving is also known as diagonal interleaving. The number of bursts over which a codeword is spread is called the interleaving depth; a spreading factor can be defined analogously. A burst error is therefore distributed uniformly over several subsequently transmitted codewords because of the distribution of the data over several bursts. This generates bit error sequences which are less dependently distributed in the data stream, hence it improves the success of the error correction process.

Figure 6.12 shows an example. During the third burst of transmission, severe fading of the signal leads to a massive burst error. This burst is now heavily affected by a total of six single-bit errors. In the process of deinterleaving (inversion of merging, despreading) these bit errors are distributed across three data blocks, corresponding to the bit positions which were sorted into the respective bursts during interleaving. The number of errors per data block is now only two, which can be much more easily corrected.

Figure 6.12: Distributing bit errors through deinterleaving

Another kind of interleaving is block interleaving. In this principle, codewords are written line by line into a matrix (Figure 6.13), which is subsequently read out column by column. The number of lines of the interleaving matrix determines the interleaving depth. As long as the length of a burst error is shorter than the interleaving depth, the burst error generates only single-bit errors per codeword if block interleaving is used [9,54].

Figure 6.13: Principle of block interleaving

■nnmiiiiiiiiiD

Figure 6.13: Principle of block interleaving

However, the great advantage of interleaving, to alleviate the effect of burst errors for optimal error correction with a convolutional code, is traded for a not insignificant disadvantage for speech and data communication. As evident from Figures 6.11 and 6.13, the bits of a codeword are spread across several bursts (here: three). For a complete reconstruction of a codeword, one has to wait for the complete transmission of three bursts. This forces a transmission delay, which is a function of the interleaving depth.

In GSM, both methods of interleaving are used (Figure 6.14), blockwise as well as bitwise. With a maximal interleaving depth of 19, this can lead to delays of up to 360 ms (Table 6.8).

Full-rate speech channel, TCH/F2.4, and FACCH - The speech channel TCH/FS in GSM uses block-diagonal interleaving. The 456 bits of a codeword are distributed across eight interleaving blocks, where one interleaving block has 114 bit positions. The exact interleaving rule for mapping the coded bits c(n, k = 0,..., 455) of the nth codeword, onto bit position i(bj = 0,...,114) of the bth interleaving block, is i(b, j) = c(n, k)

with n = 0,1,2,..., N, N + 1,... k = 0,1,2,..., 455 b = b0 + 4n + (k mod 8) j = 2((49k) mod 57)) + ((k mod 8) div 4)

RÄCH SACCH TCH FACCH TCH

SCH BCCH, PCH Voice Data

AGCH, SDCCH 2.4 kbitte Other

2 x P1 bit 456 bit

456 bit 456 bit

456 bit 456 bit

2 x P1 bit 456 bit

456 bit 456 bit

Figure 6.14: Overview: interleaving of (full-rate) logical channels

Figure 6.14: Overview: interleaving of (full-rate) logical channels

The bits of the nth codeword (data block n in Figure 6.15) are distributed across eight interleaving blocks, beginning with block B = b0 + 4n. To do so, the coded bits are mapped to the even bits of the first four interleaving blocks (B + 0,...,B + 3) and to the odd bits of the other four interleaving blocks (B + 4,...,B + 7). The even bits of the last four interleaving blocks (B + 4,...,B + 7) are occupied by data from codeword n + 1. Each interleaving block thus contains 57 bits of the current codeword n and 57 bits of the following codeword n + 1 or the preceding codeword n — 1, respectively. In this way, a new codeword is started after each fourth merged interleaving block.

i block i

Figure 6.15: Interleaving TCH/FS: block mapping i block i

Figure 6.15: Interleaving TCH/FS: block mapping

The individual bits of codeword n are alternatively distributed across the interleaving blocks, e.g. every eighth bit is in the same interleaving block according to the term (k mod 8), whereas bit position j within an interleaving block b = B + 0, B + 1,..., B + 7 is determined by two terms: the term (k mod 8) div 4 is used to determine the even/odd bit positions; and the term 2 ((49k) mod 57) determines the offset within the interleaving block. The first interleaving block B derived from codeword n thus contains bit numbers 0,8,16,...,448,456 of this codeword.

The placement of these bits for the first block B in the interleaving block is illustrated in Figure 6.16. This placement is chosen in such a way that no two directly adjacent bits of the interleaving block belong to the same codeword. In addition, the mapped bits are

Figure 6.16: Mapping of codeword n onto interleaving block B for a TCH/FS

combined into groups of eight bits each, which are distributed as uniformly as possible across the entire interleaving block. This achieves additional spreading of error bursts within a data block. Therefore, the interleaving for the TCH/FS is block-diagonal interleaving with additional merging of data bits within the interleaving block. This is also called intraburst interleaving (Figure 6.14). The data channel TCH/F2.4 and the FACCH in GSM use the same interleaving methods as the TCH/FS.

Table 6.8: Transmission delay caused by interleaving

Channel type Interleaving Transmission depth delay |ms|

TCH, full-rate, voice	8	38
TCH, half-rate, voice	4
TCH, full-rate, 14.4 kbit/s	19	93
TCH, full-rate, 9.6 kbit/s	19	93
TCH, full-rate, 4.8 kbit/s	19	93
TCH, half-rate, 4.8 kbit/s	19	185
TCH, full-rate, 2.4 kbit/s	8	38
TCH, half-rate, 2.4 kbit/s	19	185
FACCH, full-rate	8	38
FACCH, half-rate	8	74
SDCCH	4	14
SACCH/TCH	4	360
SACCH/SDCCH	4	14
BCCH, AGCH, PCH	4	14

Other data traffic channels - For the other data services in the traffic channel (TCH/ F14.4, TCH/F9.6, TCH/F4.8, TCH/H4.8, and TCH/H2.4) the interleaving is somewhat simpler. A pure bitwise diagonal interleaving with an interleaving depth of 19 is used. In this case, the interleaving rule is i(b, j) = c(n, k)

with b = b0 + 4n + (k mod 19) + k j = k mod 19 + 19(k mod 6) div 114

The bits of a data block (n,k) are distributed in groups of 114 bits across 19 interleaving blocks, whereby groups of six bits are distributed uniformly over one interleaving block.

With this diagonal interleaving, each interleaving block also starts a new 114-bit block of data. A closer look at this interleaving rule reveals that the input to the interleaver consists of blocks of 456 coded data bits as codewords. The whole codeword is therefore really spread across 22 interleaving blocks; the nominal interleaving depth of 19 results historically from 114-bit block interleaving.

Half-rate speech channel - The interleaving rule for the half-rate speech channel (TCH/ HS) is given by i(b, j) = c(n, k)

with

\n = 0,1,2,.., N, N + 1, ... k = 0,1,2,..., 227 b = b0 + 2n + (k mod 4)

and j according to a table in the GSM standard. The 228 bits of a codeword n are distributed over 4 blocks. Beginning with interleaving block B = b0 + 2n, it occupies the even numbered bits of the first two interleaving blocks (B + 0, B + 1) and the odd numbered bits of the other two blocks (B + 2, B + 3). Consequently, the following codeword n + 1 uses the even numbered bits of the blocks B + 2 (= b0 + 2(n + 1) + 0) and B + 3(= b0 + 2(n + 1) + 1) as well as the odd numbered bits of the interleaving blocks b0 + 2(n + 1) + 2 and b0 + 2(n + 1) + 3. As with the TCH/FS, one interleaving block contains 57 bits from codeword n and 57 bits from codeword n + 1 or n — 1. In summary, a new codeword starts every second interleaving block.

Signalling channels - Most signaling channels use an interleaving depth of 4, such as SACCH, BCCH, PCH, AGCH, and SDCCH. The interleaving scheme is almost identical to the one used for the TCH/FS, however, the codewords c(n,k) are spread across four rather than eight interleaving blocks:

n = 0,1,2,...,N,N + 1,... k = 0,1,2,..., 455 b = b0 + 4n + (k mod 4) j = 2((49k) mod 57)) + ((k mod 8) div 4)

With this kind of interleaving, there are also eight blocks generated, just like in the case of the TCH/FS, however, at the same time a block of 57 even bits is combined with a block of 57 odd bits to form a complete interleaving block. This has the consequence that consecutive coded signaling messages are not block-diagonally interleaved, but that each four consecutive interleaving blocks are fully occupied with the data of just one, and only one, codeword. Also, a new codeword starts after every four interleaving blocks. Therefore, this interleaving of GSM signaling messages is in essence also a block interleaving procedure. This is especially important for signaling channels to ensure the transmission of individual protocol messages independent of preceding or succeeding messages. This also enables with some kind of asynchronous communication of signaling information. The signaling data of the RACH and SCH must each be transmitted in single data bursts; no interleaving occurs.

0 0