GB2377867A - A 2/3 rate binary convolutional encoder - Google Patents

Abstract

A method of performing forward error correction in a data communication system comprises using 64 state trellis, rate 2/3, binary convolutional codes (BCC). The input bit stream is convolutionally encoded in a BCC rate 2/3 encoder, with the resulting 3-bit BCC codewords being further encoded by mapping onto an 8-QAM Gray code. Decoding comprises an 8-QAM decoding followed by convolutional decoding, <I>eg</I>. Viterbi decoding. The convolutional encoder has two shift registers fed with respective bits from input data bit pairs <I>b<SB>0</SB>, b<SB>1</SB></I> and generating output bit triplets <I>c<SB>0</SB>, c<SB>1</SB></I> and <I>c<SB>2</SB></I>, using a generator polynomial<BR> <BR> G<I>(D)</I> = [<I>D<SP>3</SP></I> + <I>D<SP>2</SP></I>, <I>D<SP>2</SP></I> + 1, <I>D<SP>3</SP></I> + <I>D<SP>2</SP></I> + 1; <I>D<SP>3</SP></I> + <I>D</I> + 1, <I>D<SP>3</SP></I> + <I>D<SP>2</SP></I> + <I>D</I> + 1, 1]<BR> <BR> which can be written in octal form as [14 05 15 ; 13 17 01]. An alternative circuit is represented by [14 04 15 ; 13 17 01] (fig. 3). This coding circuit has been found to provide a large coding gain with low complexity.

Description

<Desc/Clms Page number 1>

DATA COMMUNICATION SYSTEM The present invention relates to the use of binary convolutional codes for forward error correction in data communications, and more particularly to convolutional codes that can be used with Phase Shift Keying (PSK), Quadrature Amplitude Modulation (QAM) and M-ary Bi-Code Keying (MBCK) constellations.

Binary convolutional codes are the most widely used form of forward error correction (FEC) in digital data transmission systems. This is so due to the combination of good coding gain performance and the relative simplicity of decoding this type of code.

Such codes may be decoded using either hard or soft decoding. Soft-decision decoding gives a performance improvement in terms of coding gain of around 2 dB when compared with the hard-decision decoding of the same code, and soft-decision decoding of convolutional codes offers a good performance to complexity trade-off when compared to alternative FEC schemes.

Data communication networks often comprise a layered, packet based approach for the transmission of data. The lowest layer of this model is called the physical layer or PHY. The PHY is concerned with the correct transmission of data bits over a communication channel.

One technique often used in the transmission of data over the PHY is known as trellis coded modulation (TCM). TCM is a joint forward error correction (FEC) coding and modulation scheme based on the application of a convolutional code to certain bits of an M-ary PSK or M-ary QAM constellation. TCM provides an increased data rate over a bandwidth-limited channel using readily realisable hardware such as a Viterbi Decoder; see, e. g. Gottfried Ungerboeck,"Trellis-Coded Modulation with Redundant Signal Sets", Part 1 and Part 2, IEEE Communications Magazine, Vol. 25, No. 2, Feb 1987.

Another technique often used in the transmission of data over the PHY is known as

coded QAM ; see, e. g. Wang and Onotera,"CocM 4M Mg- 2ar CoKw'on/ Code", IEEE Transactions on Communications, Vol. 43, No. 6, June 1995. Coded QAM is a joint FEC coding and modulation scheme based on the application of the industry

<Desc/Clms Page number 2>

standard convolutional codes to a Gray coded M-ary QAM constellation. Coded QAM provides a reliable link performance over a bandwidth-limited channel using readily realisable hardware such as a Viterbi Decoder; see, e. g. J. P. Odenwalder et al,"Study of Information Transfer Optimization for Communication Satellites", Final Report, NASA CRNo. 114561, Linkabit Corporation, Section 3.3, January 1973.

Currently, various convolutional codes are under discussion for use in a high-speed PHY that operates in the 2.4 GHz ISM frequency band. It would be advantageous to introduce a code that enhances the performance in terms of signal to noise ratio when compared to previous techniques, such as complementary code key (CCK) modulation.

By improving the range and data throughput, the introduction of such a code would enlarge the number of applications possible with previously proposed techniques. Importantly, the encoder and decoder for such a code should possess low computational complexity.

The object of the present invention is to provide a binary convolutional code having the aforementioned advantages.

According to its main aspect, the invention provides a data communication method wherein data is convolutionally encoded for transmission and decoded for reception, wherein the convolutional coding implements the octal generator [14, 05,15 ; 13,17, 01] or [14, 04,15 ; 13, 17, 01]. Preferably the convolutionally encoded data is further coded for transmission and decoded for reception, preferably using 8-QAM coding for the further coding and decoding is an 8-QAM coding, and preferably using a Gray code for the 8QAM coding.

The preferred code has an octal generator polynomial G = [14 05 15; 13 1701] ; an alternative code with slightly worse performance is described by the generator polynomial G = [14 04 15; 13 17 01]. These codes have a high coding rate of 2/3, a constraint length of 4, and a trellis span of 64; they provide a large coding gain, and are of low complexity (64 state trellis). These codes introduce a coding gain greater than 5dB at the SNR operating point, and give a good trade-off between additive white Gaussian noise performance and complexity.

<Desc/Clms Page number 3>

These codes can be used with a number of symbol-to-bit mappers. When operating with a bit-derived metric, the code is particularly suited to the M-ary Bi-code Keying (MBCK) waveform set. The system formed by the combination of MBCK with these convolutional codes brings benefits to applications including the wireless LAN and cellular mobile telephone systems.

In a preferred form, the binary convolutional codewords are jointly mapped onto in-phase (I) and quadrature phase (Q) symbols using the QAM constellation discussed below. This provides improved performance without undue complexity when compared with schemes that use a 256-state trellis BCC or schemes that independently encode the I and Q symbols. The combination of Gray coded multi-level modulation and symbol-to-bit mapping gives large coding gains, and the substantial increase in performance and low implementation complexity that may be achieved makes it an ideal solution for high performance forward error correction in a high-speed physical layer.

Communication systems embodying the present codes will now be described by way of example and with reference to the drawings, in which: Figure 1 is a general block diagram of a communication system; Figure 2 is a block diagram of a BCC encoder using the octal generator

[14, 05, 15 ; 13, 17, 01] ; Figure 3 is a block diagram of a BCC encoder using the octal generator [14, 04,15 ; 13,17, 01] ; and Figure 4 is a diagram of an 8-QAM constellation that can be used in the system.

Fig. 1 shows the transmission side of a communication system. The incoming data bits are first encoded in a BCC encoder. This involves pairing the bits of the incoming bit

stream into bit pairs bo, bl. Each bit pair is encoded into 3 code bits Co, Cl, C2, which are

<Desc/Clms Page number 4>

treated as a 3-bit BCC codeword. (Each 2-bit input bit pair influences more than one 3-bit codeword, as discussed below. ) Each BCC codeword in turn in then passed to an 8-QAM Map encoder, which converts it to an 8-QAM signal.

The reception side of the system, not shown, is the reverse of the transmission side.

Each received 8-QAM signal symbol is decoded by an 8-QAM map reverser to recover the 3-bit BCC codeword, the details of the reverser being determined by the 8-QAM map encoder of the transmission side. Each such codeword in turn is fed to a BCC decoder to recover the original pair of data bits. The BCC decoder can conveniently be a conventional Viterbi decoder (maximum likelihood or a posteriori decoding), the details of which are determined by the BCC encoder of the transmission side and in particular by its generator polynomial. The Viterbi decoder may use hard-decision or soft-decision decoding. Alternatively, the decoding may be done using sequential decoding.

The data used in the scheme may be either continuous or packet encapsulated. If the encoder is used in a packet-encapsulated system, then it is placed in a known state at the beginning and end of every packet. To place the encoder in a known state at the beginning of a packet, the six memory elements of the convolutional encoder (Figure 2, discussed below) are loaded with predetermined values that are typically all Os. To place it in a known state at the end of the packet, six predetermined data bits are appended to the last data bit input to the convolutional encoder; typically, the appended bits are all Os, which places the encoder in the all 0 state. The same method is used to place the encoder of Figure 3 into a known state.

A convolutional encoder, in basic principle, consists of a (K-l)-stage shift register with m modulo-2 adder trees connected to it. The input data bit stream is fed into the shift register, so that K successive data bits are available (including those at both ends of the shift register). Each tree of modulo-2 adders generates a respective output or code bit, so the number of code bits per input bit is m. Each adder tree can be represented by listing the sequence of points it is connected to along the shift register as 1 s, with the remaining points given as Os. The encoder can therefore be represented in abstract form by a general matrix consisting of a list of the tree codings (in e. g. binary or octal).

<Desc/Clms Page number 5>

This simple system generates m output bits per input bit. To reduce the expansion ratio of the system, the stream of input bits can be stepped through the shift register p bits at a time. This results in m output bits being produced for every p input bits instead of for every input bit. With this modification, the input bits can be treated as grouped in groups of p, and the shift register can be regarded as, and indeed physically split into, p parallel sections. Each adder tree will in general have inputs from all the shift register sections, and can be encoded by a set of codes, one for each shift register. The encoder as a whole can therefore be represented by a 2-dimensional matrix, with each row representing a respective shift register and each column a respective output bit. (The matrix can also be given as two successive lists.) Fig. 2 shows the details of an embodiment of the convolutional BCC rate 2/3 encoder of Fig. 1, embodying the generator matrix G (D):

in octal notation the same code is given by

The encoder consists of two distinct paths for the two input data bits bo (the least significant bit) and bi (the most significant bit). The path for bo comprises three delay elements, which can comprise memory registers; the path for b, comprises another three delay elements. For every two bits (bo, bu) input, three output bits Co, ci, C2 are provided at the encoder output, where Co is the least significant bit and ci is the most significant bit.

Modulo 2 adders connect predetermined outputs of the delay elements in order to implement the desired generator matrix.

Considering the shift register for input bit bo, the connections to the adder tree for output bit Co can be represented as 1100, which is thus the entry (in binary) in the top row

<Desc/Clms Page number 6>

(input bit bo) and left-hand column (output bit co) of the matrix; the connections of the Co adder tree from the shift register for input bit b, are 1011 (binary), corresponding to the entry for the bottom row and left-hand column of the matrix; and so on.

Fig. 3 shows a slight modification of the Fig. 2 circuit to implement the generator

matrix 14 04 15J matrix 13 17 01 The 3-bit output of the BCC encoder is mapped to an I/Q constellation by the 8QAM map unit in the transmission side. The preferred mapping is shown in Fig. 4. Each group of three output bits (000, 001, 010, 011, 100, 101, 110 and 111) from the BCC is used to provide one I/Q (complex) symbol according to the assignment given in the Table below. (It will be noted that this assignment is a Gray code, : in that any pair of adjacent symbols round the circle differ by only a single bit.) In the Table, the first codeword bit Co is the first bit of the codeword in time.

Codeword I Q c0c1c2 Symbol Symbol 000 -1 -3 001 -1 3 010 1 -3 Oil 1 3 100 3-3 101 -3 1 Yo 111 3 1

It will of course be understood that the invention is not limited to the specific details described herein, which are given by way of example only, and that various modifications and alterations are possible within the scope of the invention.

Claims (8)

1. CLAIMS : 1 A data communication method wherein data is convolutionally encoded for transmission and decoded for reception, wherein the convolutional coding implements the octal generator [14, 05,15 ; 13,17, 01] or [14, 04,15 ; 13,17, 01].
2. 2 A data communication method according to claim 1 wherein the convolutionally encoded data is further coded for transmission and decoded for reception.
3. 3 A data communication method according to claim 2 wherein the further coding and decoding is an 8-QAM coding.
4. 4 A data communication method according to claim 3 wherein the 8-QAM coding is a Gray code.
5. 5 A data communication method substantially as herein described and illustrated.
6. 6 The data transmission method of any previous claim.
7. 7 The data reception method of any previous claim.
8. 8 Apparatus for performing the method of any previous claim.