Contents

1 Convolutional Codes and Block Codes

2 Fire Codes

3 Parity Codes

4 GSM Channel Coding Standards

5 Interleaving

6 Ciphering

7 Current Research

References

Further Information

Introduction

Depending on the transmission mode, radio path transmission uses different codes. Moreover, several codes are "concatenated" in certain cases, i.e., redundancy is added by applying a given code, then more redundancy is added by applying another code.

The codes used in GSM are:

• Block Convolutional Codes: these codes are only used for correction purposes. They achieve tremendous efficiency when they are combined with likelihood estimation such as that coming from the demodulator,

• Fire Code: this code is dedicated to the detection and correction of 'bursty' errors, i.e., errors that occur in a short time interval. It is used in concatenation after a block convolutional code, for which residual errors often appear in short time intervals.

• simple Parity Codes: used for error detection.

1 Convolutional Codes and Block Codes

• the source sequence, the source sequence delayed by one bit period, and the source sequence delayed by 3 bit periods,

• the source sequence, the source sequence delayed by two bit periods, and the source sequence delayed by 3 bit periods.

The condensed form used to describe these codes consists in using polynomials, which in the above example are  and , where ' + ' denotes the exclusive-or operator and D represents a delay unit.

This method, as described here, has two drawbacks: it is adapted to infinite sequences, and it results in an efficiency ratio which is limited to fractions of the form 1/c.

Two modifications of this basic schemes are used in GSM. First, the source sequence consists of finite blocks of p bits. They can be coded as described above, but with the addition of a few known bits at both ends of the block, called tail bits. Second, an efficiency of the form p/q was needed in one case, and is obtained by puncturing the code, i.e., by keeping only q bits among pn, through a pre-determined rule.

For instance, if we want to apply the code described above to a block of b = 12 bits, we could add 3 bits set to '0' at the start and at the end of the sequence and thus get bc = 30 bits. In order to get a convolutional efficiency of e.g., 2/3, alternate bits of the second sequence could be omitted. The coded result uses 23 bits. This is illustrated in the table below.
 
 

The actual efficiency coefficient is slightly smaller than the convolutional efficiency, because of the tail bits, and in this case amounts to 12/13.

The convolutional codes used in GSM are not much complex than this. The maximum degree of the corresponding polynomials is 4. Now, convolutional codes of larger degrees usually have better performance, at the price of decoder complexity. In GSM, however, simple codes have been chosen because the performance gain is limited by the interleaving depth. The span of a code can be understood in broad terms as the length of the sequence of coded bits which must be analyzed to decode one information bit. It can be shown, with the assumption that bursts are mostly all good or all bad, that little gain is obtained if the span is greater than the interleaving depth. The GSM convolutional codes have been chosen as simple as possible, with a span just big enough (e.g., 22 for the 9.6 kbps data transmission mode).
 
 

2 Fire Code

A Fire code is a conventional linear binary block code, i.e., it consists in transmitting, in addition to the information bits, k a number or redundant bits computed by exclusive-or manipulations on the information bits. Moreover Fire codes derive from codes belonging to the 'cyclic' code family. In this case, the redundancy computation formulas can be expressed as follows. The original sequence can be used to build a polynomial, whose coefficients are the bits of the sequence. The redundancy can be expressed as the coefficients of another polynomial obtained as the remainder of the division of the polynomial representing the sequence by a pre-defined polynomial, characteristic of the code and called the generator polynomial.

A Fire code has a generator polynomial designed to allow good detecting and/or correcting performance when errors happen in groups. The GSM Fire code uses the following generator polynomial:

This polynomial, being of degree 40, gives a remainder having 40 coefficients, and thus there are 40 redundancy bits. The properties of this code are such that error groups of 11 bits can be detected and corrected.
 
 

3 Parity codes

These are linear block codes, derived, like the Fire code, from cyclic codes. For speech, a 3-bit redundancy code enables to assess the correctness of the bits which are most sensitive to errors in the speech frame . Its detection capability is quite limited. All one-error patterns are detected, but there are patterns of two errors which are not detected.

For the RACH (Random Access Channel) and SCH (Synchronization Channel) bursts, codes of respectively 6 and 10 bits of redundancy are aimed at detection, though they have adequate properties to be used for error correction. These codes have a minimum distance of 4, which means that they could be used to detect all patterns of 3 errors, and they could be used to correct all single error cases).
 
 

4 GSM Channel Coding Standards

The input rate for the speech transmission mode on a full rate traffic channel is equal to 13 kbps, by blocks of 260 bits. When errors occur, the received speech is disturbed in different ways depending on the role of the bits in error. Thus it was decided to protect these 260 bits in different ways:

• 182 bits are protected by a convolutional block code with a convolutional efficiency of ½,

• among these 182 bits, 50 are additionally protected by a detection code adding 3 redundancy bits. These 50 bits are the category Ia bits; the other 132 bits are category Ib bits,

• the other 78 bits are not protected.

The polynomial representing the detection code for category Ia bits is . Bits of class Ia are of such importance that if any one of them is corrupted, the user will hear a potentially loud noise in place of a 20ms speech slice. Detection of such errors is therefore important and allows the bad block to be replaced by something less disturbing s.a. an extrapolation of the preceding block.

The convolutional code consists in adding 4 bits set to '0' to the initial 185 bit sequence, and applying two convolutions whose polynomials are respectivelyand. No puncturing is applied, and the result is composed of twice 198 bits, i.e., 378 bits. The efficiency of class I bits is just below 0.5. The 78 non-protected bits must of course be added to these 378 bits, leading to a coded block length of 456 bits.
 

5 Interleaving

To further protect against burst errors common to the radio interface, each sample is interleaved. The 456 bits output by the convolutional encoder are divided into 8 blocks of 57 bits, and these blocks are transmitted in eight consecutive time slot bursts. Since each time slot bursts can carry two 57 bit blocks, each burst carries traffic from two different speech samples.
 
 

6 Ciphering

Digital transmission allows easy protection of data against non-authorised third parties. Such protection has been introduced in GSM by means of transmission ciphering, which is independent of the type of data being transmitted. This is achieved by performing an 'exclusive-or' operation between a pseudo-random bit sequence and 114 useful bits of a normal burst. The algorithm used to generate the pseudo-random sequence is called "A5".
 

7 Current Research

The need for increased utilization of the available wireless communication spectrum has fueled the development of advanced channel coding techniques. From simple waveform coding techniques operating at 64 kbps, the advance of channel coding algorithms has produced communication quality at 2 kbps and below. This allows up to 32 communication channels to operate a bandwidth formerly occupied by one channel. The current research priorities in the area of mobile communications channel coding standards include:

• The development of channel coding schemes with perceptual tolerance to time varying congestion, characteristic of mobile networks
• The development of efficient, scalable or layered source coding standards with layered specific QoS requirements.
• Investigation and development of effective hybrid schemes which combine purely passive error recovery techniques with active FEC-based approaches.

References

Further Information

Created:            05th Oct. 1999 
Last Modified: 11th Oct. 1999 @ 03:00 (GMT +02) 

Back to the Table of Contents