Unequal error protection in coded modulation schemes

BACKGROUND

This invention relates to coded modulation schemes used in communication systems and more particularly to the use of product codes and other concatenated codes in coded modulation schemes.

Coded modulations such as multi-level coding or block coded modulation (BCM) can be used to increase the information rate (spectral efficiency) of a communication system without decreasing power efficiency. This increase in the information rate is useful in a communication system in which speech signals are digitized and compressed before being transmitted. Higher compression saves bandwidth, but reproduction quality suffers under adverse conditions in the communication channel. The increased information rate with coded modulation permits less compression to be used, and hence reproduction quality can be improved. A greater information rate, i.e., a greater information capacity, also enables a communication system to accommodate more users.

Multi-level coding schemes, such as BCM, are described in H. Imai et al., "A New Multi-Level Coding Method Using Error Correcting Codes", <u style="single">IEEE Transactions on Information Theory</u> vol. IT-23, pp. 371-377 (May 1977); S. Sayegh, "A Class of Optimum Block Codes in Signal Space", <u style="single">IEEE Transactions on Communications</u> vol. COM-34, pp. 1043-45 (Oct. 1986); A.R. Calderbank, "Multi-Level Codes and MultiStage Decoding", <u style="single">IEEE Transactions on Communications</u> vol. COM-37, pp. 222-229 (Mar. 1989); G. Karam et al., "Block-Coded Modulation Using Reed-Muller Component Codes with Multistage Decoding", <u style="single">European Transactions on Communications</u> vol. 4, pp. 267-275 (May 1993); and T. Woerz et al., "Decoding of M-PSK Multilevel Codes", <u style="single">European Transactions on Communications</u> vol. 4, pp. 299-308 (May 1993).

This article relates generally to improvements in the DER of multistage decoding using interleaving between the levels, pass reliability information between the different stages by applying "Soft-Output" decoders, and the application of reiterated decoding. Specifically, if the Viterbi algorithm is used for decoding, the estimated information bit sequence is liable to contain error bursts. This sequence is re-encoded and fed into the decoder of the next level. Thus, the re-encoded sequence also contains error bursts. If this decoder also uses the Viterbi algorithm then it is very sensitive to these error bursts, because the algorithm is designed to deal with independent errors in the input stream. Thus, the performance of this decoder is mostly determined by preceding decoders.

In order to avoid this error propagation effect, we introduce interleaving between the coded bit streams of each level. An interleaver matrix is added to the coder block diagram between the coders of each level and the mapping unit. At the decoder, the received symbols are first written into a deinterleaver matrix and are then processed. The interleaving has to be done in such a way that the re-encoded bit streams of any two decoders are spread for the third decoder. So it will be hardly influenced by error bursts from any of the other two decoders.

Recent publications on the suitability of BCM for Rayleigh fading channels include N. Seshadri et al., "Multi-Level Coded Modulations for Fading Channels", <u style="single">Proceedings of the Fifth Tirennia International Workshop on Digital Communications</u> (E. Biglieri et al., eds.) pp. 341-352 (1992); N. Seshadri et al., "Coded Modulation with Time Diversity, Unequal Error Protection and Low Delay for the Rayleigh Fading Channel", <u style="single">Proceedings of First Universal Conference on Portable and Mobile Communications</u> pp. 283-287 (Sept. 1992); and N. Seshadri et al., "Multi-Level Block Coded Modulations with Unequal Error Protection for the Rayleigh Fading Channel", <u style="single">European Transactions on Communication</u> vol. 4, pp. 325-334 (May 1993). Multi-level BCM is an attractive scheme for combined modulation and coding, particularly for Rayleigh fading environments where interleaving depth is a crucial factor in determining the bit error rate (BER) performance.

US 5,416,804 describes apparatus for decoding digital signals, such as digital television signals, which have been transmitted by concatenated coded modulation using partitioning levels of a constellation of points representing different code values. The apparatus includes successive decoding stages which respectively operate on the successive partitioning levels of the constellation. Each decoding stage includes a detector for detecting received points in the relevant partitioning level. At least one stage includes an internal decoder for generating estimated bit sequences in accordance with an inner code and erasures of bit sequences for which the estimation is found to be ambiguous, an external decoder decoding in accordance with an outer code and correcting bit sequence erasures, and an encoder for encoding the output of the external decoder and supplying the resulting re-encoded bit sequences to the succeeding stages of the decoding apparatus to validate detection thereby of points in their partitioning levels. The apparatus may be arranged to produce only a predetermined maximum number of erased bit sequences.

EP 0,490,552 relates to an arrangement whereby unequal error protection is provided for an HDTV signal by separately coding each one of the classes of information in the HDTV signal by using a conventional coded modulation scheme and then time-division-multiplexing the various coded outputs for transmission.

US 5,581,481 relates to a storage and retrieval system for JPEG images. In one illustrative embodiment the system includes an apparatus for storing a JPEG image in or on a storage medium with unequal error protection, comprising a separator for separating the JPEG image into Type-I and Type-II information, an error correction encoder for encoding the Type-I information with more error protection than the Type-II information, and a storage recorder for recording the encoded Type-I and Type-II information in or on the storage medium. The system further includes an apparatus for reading the encoded Type-I and Type-II information from the storage medium.

US 5,349,589 describes a method and apparatus for digital radio communication employs separation of a frame of data to be transmitted into key bits, critical bits and unprotected bits. The key bits are processed to provide parity bits. The parity bits, and key bits are convolutionally encoded using a tail-biting scheme and merged with unprotected bits, and then transmitted. At the receiver, the decoder splits the received data into convolutionally encoded bits and unprotected bits, and trellis decodes the convolutionally encoded bits into a number of possible paths through a trellis using a generalized Viterbi algorithm. The tail-biting scheme reduces the number of bits that must be transmitted. Paths having errors in the key bits are rejected, and the path having the best metric without key bit errors is used in decoding the transmitted information. In the event that there is no such path, a previously selected path is substituted and decoded.

US 4,802,171 concerns a system and method for error correction in communication systems for transmission of digitized speech signals. Sub-band coding is preferably applied to the input signal, and the sample information and the side information provided. An error detection code (EDC) is applied to at least a portion of the side information and an error correction code (ECC) is applied over the side information and the EDC. A second EDC is applied to the ECC. These information signals and error detection and correction codes are multiplexed with the protected portion of the side information and the error correction code separated by at least the sample information. Speech signals are thus transmitted and reconstituted with improved quality with a minimum data rate required.

According to EP 0 471 085, to make an error-correcting code C_Z, encoding is performed as follows: first information of k₁ x k₂ digits having k₁ digits in a first direction and k₂ digits in a second direction is encoded into a product code C_A of n₁ x n₂ digits by combining a partial code word C₁ expressed in a linear (n₁, k₁, d₁) code having a minimum distance d₁ in the first direction with a partial code word C₂ expressed in a linear (n₂, k₂, d₂), code having a minimum distance d₂ in the second direction; second information of r x k_x (r&lt;n₁ - k₁, k_x&lt; n₂) digits is encoded into a code U_s of a linear (n₂, k_x, d₃) code having a minimum distance d₃ in the second direction; and the code U_s is superimposed on a check digit part of the product code C_A. The first and second information are obtained from the code C₂.

A transmitter using BCM and eight-point phase-shift keying (8-PSK) modulation is shown in Fig. 1a, in which a speech or other information source 11 generates an analog signal representing the speech or other information. The continuous analog speech signal is converted into a stream of digital data, such as binary bits, by a digitizer 12, such as an analog to digital converter, from which the digital data passes to a speech encoder 13.

The speech encoder 13 transforms the digital data from the digitizer 12 into a plurality of streams i₀, i₁, i₂, ... of encoded digital data elements, each stream representing a respective subset of the information in the information signal. In this 8-PSK example, there are three such streams i₀, i₁, i₂, although it will be understood that an M-ary modulation other than 8-PSK, such as 16-PSK or 16 - ary quadrature amplitude modulation (QAM), and other than three streams i of encoded digital data elements might be used. At least one of the streams of encoded data elements represents information in the speech signal that is more important than the information represented by the other streams.

The streams i₀, i₁, i₂ are provided as inputs to a BCM encoder 14, which includes a plurality of block encoders 15 connected in parallel and a bits-to-symbol mapper 16. The input streams are encoded according to respective block codes C₀, C₁, C₂, yielding respective output streams of codewords comprising respective streams b₀, b₁, b₂ of coded bits. The codes C are called component codes, and have respective rates k_i/N, i=0, 1, 2, ..., where N is the block length and k_i is the number of input symbols that are encoded in each block of N code symbols. This scheme provides an overall information rate R = (k₀ + k₁ + k₂) / (N) information bits per code symbol. For illustration, let the code C₀ be the most powerful code, followed by the code C₁ and then the code C₂. With such an arrangement, the bit stream i₀ would represent the most important class of information, which may be called Class 0; the bit stream i₁ would represent the next most important class, which may be called Class 1; and the bit stream i₂ would represent the least important class, which may be called Class 2.

Each of the succession of triplets of code bits {b₂b₁b₀} produced by the block encoders 15 is used by the mapper 16 to select a respective one of the constellation of eight 8-PSK symbols according to a predetermined scheme. In this example, b₂ is the most significant bit (MSB) and b₀ is the least significant bit (LSB). A conventional bits-to-symbol mapper, which may be realized as a lookup table or as a combination of logic elements, uses either natural binary mapping or Gray coded mapping. In this way, three N-bit block codewords generated by the three block encoders 15 are transformed into one modulation codeword, comprising N modulation symbols.

The bits-to-symbol mapper 16 produces a stream of generally complex-valued (I + jQ) modulation symbols that is provided to a symbol interleaver 17, which shuffles the order of the modulation symbols, separating formerly successive symbols in time. Interleaving helps spread the effect of noise and other impairments in the physical communication channel among the modulation symbols, minimizing the chances that all of the symbols of a codeword will be affected and taking advantage of the built-in time diversity of the multi-level block code.

The symbol interleaver 17 also separates the interleaved symbols into in-phase (I) and quadrature (Q) components, which undergo pulse-shaping by filters 18, and the filtered components are then converted from digital to analog form by D/A converters 19. The analog signals are further spectrally shaped by filters 20, and the filter output signals are applied to an I, Q modulator 21, which quadrature modulates a carrier signal with those signals. The modulated carrier signal is then amplified by a suitable amplifier 22, and the amplified carrier signal is transmitted via an antenna 23.

Similar processes are used to decode the modulated carrier signal received by a receiver and recover the information signal that was sent. As illustrated in Fig. 1b, the modulated carrier signal collected by an antenna 25 is selected by a suitable bandpass filter 26 and amplified by a suitable amplifier 27. The amplified signal is then translated in frequency by a down-converter 28, which is typically a balanced mixer and suitable oscillator, either directly to baseband or as illustrated to an intermediate frequency (IF) and then the IF signal is translated to baseband by an IF down-converter 29. In either case, the baseband signal comprises I' and Q' components, which are converted from analog to digital form by A/D converters 30. The digitized I' and Q' components are then provided to a sample timing selector 31, the output of which is a stream of complex-valued 8-PSK modulation symbols that is provided to a de-interleaver 32.

The de-interleaver 32 reverses the shuffling performed by the symbol interleaver 17 and generates a stream of modulation symbols that is identical to the stream generated by the bits-to-symbol mapper 16. The de-interleaved symbols produced by the de-interleaver 32 are applied to a BCM decoder 33, which transforms the de-interleaved symbols into parallel data symbol streams i₀, i₁, i₂. The data symbol streams are then applied to a speech decoder 34, which reverses the encoding performed by the speech encoder 13 and produces a speech signal.

As described above, the BCM encoder 14 uses the triplets {b₂b₁b₀} of block code symbols as addresses for the 8-PSK symbols, which may be stored in a memory at locations identified by the addresses. The relationship between the triplets and the modulation symbols is called a "mapping", and typically either natural order binary mapping or Gray code mapping is used. Fig. 2 illustrates a BCM encoder 14 in which C₀ is a (4,1) repetition code and C₁ and C₂ are (4,3) single-parity-check codes, and Fig. 3 illustrates the natural binary mapping of triplets to 8-PSK symbols. In the encoder illustrated in Fig. 2, the block length N of the codes C₀, C₁, C₂ is four, and thus four triplets of block code symbols {111}, {100}, {110}, and {101} are used to select four 8-PSK symbols that compose the BCM codeword {S₁S₂S₃S₄}. In this example of natural binary mapping, the bits-to-symbol mapper 16 would transform code bit triplets to 8-PSK modulation symbols using the following rule: <maths id="math0001" num=""><math display="block"><mrow><mi mathvariant="normal">modulation symbol number</mi><mo>=</mo><mn>4</mn><msub><mrow><mi mathvariant="normal">b</mi></mrow><mrow><mn>2</mn></mrow></msub><mo>+</mo><mn>2</mn><msub><mrow><mi mathvariant="normal">b</mi></mrow><mrow><mn>1</mn></mrow></msub><mo>+</mo><msub><mrow><mi mathvariant="normal">b</mi></mrow><mrow><mn>0</mn></mrow></msub></mrow></math><img file="EP1018232B1_D0001.tif" /></maths> where the eight 8-PSK modulation symbols, indicated in the complex plane by the "x" marks, are consecutively numbered counter clockwise starting from the positive real axis as shown in Fig. 3.

One of the main features of block coded modulation schemes is that each class of bits may be encoded by a different code, and thus unequal error protection of the bits can be readily achieved. The unequal error protection is useful particularly for speech data, where all the bits are not equally important in a perceptual sense. Optimizing a coded modulation scheme to achieve a desired BER performance involves choosing the component codes and the appropriate bits-to-symbol mapping scheme that achieve the desired performance specifications. It is often desirable to improve the BER performance of a specific class of bits without increasing decoding complexity significantly or affecting the BER performance of the other classes of bits.

SUMMARY

One of the important considerations in the design of a coded modulation scheme is the choice of the component codes, which has a significant impact on the overall BER performance and which determines the decoding complexity.

According to the present invention there is provided a coded modulation method according to the appended independent Claim 1, a coded modulator according to the appended independent claim 5, a communications apparatus according to the appended independent Claim 9 and an apparatus for decoding according to the appended independent Claim 14. Preferred embodiments are defined in the dependent claims.

BRIEF DESCRIPTION OF THE DRAWINGS

The features and advantages of the invention will be understood by reading this description in conjunction with the drawings, in which: <ul id="ul0001" list-style="none" compact="compact"><li>Figs. 1a, 1b illustrate a transmitter that includes a BCM encoder and a receiver that includes a BCM decoder;</li><li>Fig. 2 illustrates a BCM encoder;</li><li>Fig. 3 illustrates a natural binary mapping scheme for the BCM encoder of Fig. 2;</li><li>Fig. 4 illustrates a product code, comprising a set of nested codes;</li><li>Fig. 5a illustrates a BCM encoder employing a product code, comprising an outer code and an inner code;</li><li>Fig. 5b illustrates a BCM encoder having an interleaver disposed between an outer-code encoder and an inner-code encoder;</li><li>Fig. 6a illustrates signal fading and a stream of transmitted symbols;</li><li>Fig. 6b illustrates a stream of interleaved transmitted symbols;</li><li>Fig. 7 illustrates an interleaver;</li><li>Fig. 8 illustrates a decoding trellis for a BCM scheme according to the invention; and</li><li>Fig. 9 illustrates interleavers and bit separation when using product codes.</li></ul>

DETAILED DESCRIPTION

A product code can improve the BER performance of a selected class of information in the coded modulation scheme without affecting the decoding complexity or BER performance of other classes of information. Moreover, it is advantageous to pass soft information between decoders of inner and outer codes of a product code.

A coded modulation method includes the steps of encoding each of a plurality of streams of data bits according to a respective code, thereby generating respective streams of coded bits, and selecting modulation symbols based on respective groups of the coded bits. At least one stream of data bits is encoded according to a product code and at least one other stream of data bits is encoded according to at least one other code. Each group of coded bits used for selecting modulation symbols includes coded bits from all of the streams of coded bits. The product code and other code may be block codes having a predetermined block length.

In addition, the encoding step may include the steps of encoding the stream of data bits according to an outer code, thereby generating a stream of outer-code bits, and encoding the stream of outer-code bits according to an inner code, thereby generating a stream of product-code bits. The inner code may have the predetermined block length. Also, the method may further include the step of interleaving the outer-code bits, wherein the interleaved outer-code bits are encoded according to the inner code. The modulation symbols may be phase-shift keying symbols.

A coded modulator includes a device for encoding each of a plurality of streams of data bits according to a respective code and for generating respective streams of coded bits, and a device for selecting modulation symbols based on respective groups of the coded bits. At least one of the streams of data bits is encoded according to a product code and the remaining streams of data bits are encoded according to at least one other code. Each group includes coded bits from all of the streams of coded bits.

The inner code of the product code and the other code or codes may be block codes having the a predetermined block length. The encoding device may include a device for encoding a stream of data bits according to an outer code, thereby generating a stream of outer-code bits, and a device for encoding the stream of outer-code bits according to an inner code, thereby generating the stream of product-code bits. The inner code may have the predetermined block length. The encoding device may further include a device for interleaving the outer-code bits thereby generating interleaved outer-code bits, and the interleaved outer-code bits may be encoded according to the inner code. The selecting device may include a memory having a plurality of storage locations that are identified by respective addresses. Each modulation symbol may be stored in a respective one of the storage locations, and the selecting device may retrieve modulation symbols stored in storage locations identified by the groups of coded bits.

A communications apparatus includes a device for generating a plurality of streams of data bits, comprising a first stream of data bits and other streams of data bits; a device for encoding the first stream of data bits according to a product code and for generating a stream of product-code bits; at least one device for encoding the other streams of data bits according to at least one other code and for generating at least one stream of other-code bits; and a device for selecting modulation symbols based on respective groups of the product-code bits and the other-code bits. Each group includes at least one product-code bit and at least one other code bit.

The communications apparatus further includes a device for interleaving the selected modulation symbols; a device for transmitting a carrier signal modulated by the interleaved selected modulation symbols; and a device for receiving the carrier signal modulated by the interleaved selected modulation symbols and for recovering the interleaved selected modulation symbols. The communications apparatus further includes a device for de-interleaving the interleaved selected modulation symbols; and a device for decoding the de-interleaved selected modulation symbols, thereby recovering the plurality of streams of data bits.

The product coding device may include a device for encoding the stream of data bits according to an outer code, thereby generating a stream of outer-code bits, and a device for encoding the stream of outer-code bits according to an inner code, thereby generating the stream of product-code bits. The outer code, inner code, and at least one other code may be block codes. Also, the product coding device may further include a device for interleaving the outer-code bits.

Moreover, the device for de-interleaving the modulation symbols may include a memory having an array of storage locations that are identified by respective addresses. The interleaved modulation symbols may be stored in respective storage locations, and the decoding device may lecode the modulation symbols stored in the memory according to a viterbi algorithm. Also, the modulation symbols may be stored in the memory such that all coded bits produced by the inner code are stored in respective rows, and the decoding device, in decoding the coded bits stored in each row, generates soft information that is used in decoding coded bits produced by the outer code.

Furthermore, the decoding device may utilize an iterative decoding process in which soft information is generated by decoding the coded bits stored in each row, the soft information is used in decoding the coded bits produced by the outer code, and the decoded bits produced by the outer code are used to again decode the coded bits stored in each row.

T here is provided an apparatus for decoding a stream of modulation symbols that respectively represent coded bits, wherein the coded bits are produced by respective codes and wherein at least one of the respective codes is a product code including at least one inner code and at least one outer code. The apparatus includes a memory having an array of storage locations that are identified by respective addresses; a device for storing the modulation symbols in respective storage locations; and a device for decoding the modulation symbols stored in the memory according to a viterbi algorithm. The modulation symbols are stored in the memory such that all coded bits produced by the at least one inner code are stored in respective rows, and the decoding device, in decoding the coded bits stored in each row, generates soft information that is used in decoding coded bits produced by the outer code.

Also, the decoding device may utilize an iterative decoding process in which soft information is generated by decoding the coded bits stored in each row, the soft information is used in decoding the coded bits produced by the at least one outer code, and the decoded code bits produced by the at least one outer code are used to again decode the coded bits stored in each row.

Furthermore, the coded bits produced by the at least one outer code may be stored in nonadjacent rows of the memory.

In an exemplary communication system such as that illustrated in Figs. 1a, 1b, an analog speech signal may be digitized at a rate of 64 kilobits/second (Kbps) using standard eight-bit pulse code modulation (PCM). The digitized speech may then be compressed by a speech encoder according to a speech coding algorithm, and the bits included in the encoded digital speech signal may then be categorized into classes based on their importance in reproduction of the analog speech signal. The more important bit classes should be preserved with less distortion or errors, which can arise from transmission of these bits through a communication channel. For example, information sent through a radio channel can suffer from transmitter noise, environmental noise, interference from other channel users, signal strength variations (fading), receiver noise, etc. Figs. 1a, 1b, 2, and 3 illustrate a BCM scheme based on 8-PSK modulation with three block codes C₀, C₁, C₂ for coding bit classes Class 0, Class 1, Class 2 bits, respectively.

The following description assumes that the speech coder has three bit classes that correspond to the bits' perceptual significance and that are protected by a BCM scheme accordingly, and the following description is in terms of 8-PSK. Nevertheless, it will be appreciated by those of ordinary skill in this art that the invention-is not limited to this example. The invention is generally applicable to M-ary modulation schemes, such as M-ary PSK, for which the M modulation symbols would be addressed by M-tuplets {b_M-1b_M-2 ... b₁b₀}. The invention is also generally applicable to coding schemes other than block coding and to speech coders having other than three classes.

In accordance with the invention, the BER performance for a selected class of information such as Class 0 is improved by use of a product code or concatenated code as described below. A product code or concatenated code comprises a set of nested codes. As illustrated by Fig. 4, the output is formed by the product of the nested codes code 1, code 2, ..., code N. The codes C₀ and C₁ can advantageously be used as the nested codes as described in more detail below. In the BCM scheme illustrated in Fig. 2, the code C₀ is a (4,1) repetition code (rate = 1/4), whereby each input bit is repeated four times; and the codes C₁ and C₂ are a (4,3) single-parity-check code (rate = 3/4), whereby groups of three input bits and one parity bit are the output bits and each parity bit is chosen such that the modulo-2 sum of the four bits in the respective group is zero.

As an example of the invention, the BCM encoder 14 illustrated in Figs. 1a and 2 is modified such that the (4,1) repetition code C₀ is replaced with a product code C₀ formed, for example, by the product of the (4,1) repetition code and the (4,3) single-parity-check code. In such a system, the product code C₀ would have a rate that is the product of the rates of the nested codes, that is, rate = 1/4 * 3/4 = 3/16. In this example, the two nested codes can conveniently be identified as an outer code C₀^(O)) and an inner code C₀^(I), and the outer code is the (4,3) single-parity-check code and the inner code is the (4,1) repetition code. As before, the C₁ code is the (4,3) single parity check code (rate = 3/4) and the C₂ code is the (4,3) single-parity-check code (rate = 3/4). It will be understood, however, that many other codes can be used as the nested codes.

Using a product code to encode the Class 0 information stream i₀ has several advantages. First, the effective block length of code C₀ is increased (to sixteen, in this example) without increasing the length of the BCM codewords, and thus the Class 0 bits are more heavily protected. This advantage is achieved without affecting the system's decoding complexity as far as the codes C₁ and C₂ are concerned. In addition, since the length of the BCM codewords is not changed, the interleaving depth that can be achieved with a finite-size interleaver is not changed. A possible disadvantage of using a product code is that the information rate for the selected class of bits is decreased. Depending on the specific application and the particular choice of inner and outer codes, the improvement in BER performance for the selected class may justify the lowering of the information rate.

Fig. 5a illustrates an improved encoder 14' using a product code for a selected class of information in accordance with the invention. According to Fig. 5a, Class 0 information i₀ is first encoded by an outer encoder 15-1, which produces a stream i₀' of outer code bits that passes to an inner encoder 15-2. The stream b₀ of product-code bits generated by the inner encoder 15-2 passes, with the code-bit streams b₁, b₂ produced by respective encoders that encode the Class 1 and Class 2 information streams according to the codes C₁ and C₂ encoders, to the bits-to-symbol mapper 16 (shown in Fig. 1a). The bits-to-symbol mapper 16 uses these code-bit streams as addresses for retrieving complex-valued 8-PSK symbols from respective storage locations in a memory. The modulation symbols retrieved by the bits-to-symbol mapper 16 are provided to the symbol interleaver 17 (shown in Fig. 1a) for further processing in the manner described above in connection with Fig. 1a.

An alternative to the arrangement depicted in Fig. 5a is depicted in Fig. 5b, which shows an additional interleaver 17-1, disposed between the outer-code encoder 15-1 and the inner-code encoder 15-2, for shuffling the outer-code bits. This arrangement is advantageous because, as described in more detail below, it helps avoid losing the benefits of the outer code.

As described above, a radio channel may experience fading, which is a decrease in received signal level that, if deep enough, can make decoding very difficult in the presence of receiver noise and interference, increasing the probability of errors due to the decreased signal to noise ratio. Fig. 6a illustrates a fade in signal amplitude level and a corresponding portion of a stream of transmitted symbols S₁, S₂, S₃, ... conveyed by the fading signal. As illustrated, a fade can affect a large number of consecutive symbols, which without interleaving might be a substantial portion of the symbols of one or more transmitted codewords. (Three BCM codewords, each comprising four symbols S, are indicated in Fig. 6a.) If too many of its symbols are received with poor signal to noise ratio, a codeword may not be decoded correctly.

Interleaving shuffles the stream of symbols so that the symbols composing a given codeword are spaced far enough apart that they are unlikely to be affected by the same fade. In other words, the symbols composing a codeword experience different radio propagation conditions, making it more likely that the codeword will be decoded correctly. This is depicted in Fig. 6b, which corresponds to Fig. 6a. The symbols S₅, S₉, S₁₃, S₁₇ affected by the fade come from different BCM codewords as a result of the interleaving.

A simple form of interleaving can be implemented with an array of memory elements. A rectangular interleaver comprises an array of N_r rows and N_c columns of memory elements, each element storing one modulation symbol S, which as described above is usually complex-valued. The stream of symbols S₁, S₂, S₃, ...., S₁₀₀ is written into the interleaver row-wise and read out of the interleaver column-wise as depicted in Fig. 7. The number N_c of columns is usually chosen to be the block length of the modulation codewords (which is four, in this example). The number N_r of rows is chosen so that the separation between two successive symbols of a codeword is large enough to minimize the effects of fading. Thus, the four symbols S₁, S₂, S₃, S₄ composing codeword 1 form the first row of the array; the four symbols S₅, S₆, S₇, S₈ composing codeword 2 form the second row of the array; and so forth. Reading out column-wise shuffles the order of the symbols, producing a stream of interleaved symbols S₁, S₅, S₉, ... S₉₇, S₂, S₆, S₁₀, ... S₁₀₀. It may be noted that successive input symbols are separated by twenty-five symbol periods in the output stream (N_r = 25). It will be understood that the numbers N_r, N_c can vary, depending on the selected coded modulation scheme and desired interleaving depth.

In order to increase the improvement of BER performance provided by using a product code, the decoding procedure implemented by the decoder 33 (Fig. 1b) should fully exploit the advantages of the product code by using soft information derived from decoding the inner code for decoding the outer code. An advantageous decoding procedure is described in more detail below, in which the inner code protects bits in each row of a memory array and the outer code protects bits along each column (spanning many rows). The decoding of the inner code is accomplished when the symbols stored in each row of an interleaver such as that illustrated in Fig. 7 are decoded using Applicants' trellis decoding procedure that is described in more detail below.

The trellis decoding procedure would be carried out by a device located in a position in the receiver that is equivalent to the position of the BCM decoder 33 shown in Fig. 1b. It will be appreciated that such a device may be implemented as hard-wired logic circuitry of an application-specific integrated circuit (ASIC) or as an integrated digital signal processor. Of course it will be understood that an ASIC may include hard-wired logic circuitry that is optimal for performing a required function, which is an arrangement commonly selected when speed or another performance parameter is more important than the versatility of a programmable digital signal processor.

Fig. 8 shows a trellis that is a complete graphical representation of the decoding procedure appropriate for a BCM scheme employing three component codes C₀ (rate 1/4 repetition code), C₁ (rate 3/4 single-parity-check code), and C₂ (rate 3/4 single-parity-check code) whose bits are mapped onto the constellation of eight 8-PSK symbols. The particular mapping is not important here, although it is believed that an advantageous mapping is described in Patent Application WO-A-99/17509, by Applicants entitled "Improved Bits-to-Symbol Mappings for Coded Modulations".

Specifically, according to this disclosure each code symbol is mapped onto a constellation of modulation symbols, thereby generating a stream of modulation symbols wherein the modulation symbols are assigned locations in the constellation based on maximized products of non-zero squared Euclidean distances between code symbols along decoding trellis paths.

In particular, the modulation symbols may be assigned locations in the constellation by minimizing a metric given by: <maths id="math0002" num=""><math display="block"><mrow><msub><mi>M</mi><mrow><mi>p</mi><mi>d</mi></mrow></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mrow><msub><mi>N</mi><mi>p</mi></msub></mrow></munderover><mrow><mfrac><mrow><msub><mi>N</mi><mi>i</mi></msub></mrow><mrow><msub><mi>P</mi><mrow><mi>d</mi><mi>i</mi></mrow></msub></mrow></mfrac></mrow></mstyle></mrow></math><img file="EP1018232B1_D0002.tif" /></maths> where N_p is a number of decoding trellis paths having differing product distances, P_di is the product distance of an i-th decoding trellis path relative to a desired decoding trellis path, and N_i is a number of decoding trellis paths having the same product distance as the i-th decoding trellis path.

Each possible BCM codeword corresponds to a respective path through the trellis.

In this example, the BCM component codes each have a block length of four, yielding four triplets of coded bits (addressing four 8-PSK symbols) for each BCM codeword that represents seven information bits. The number of information bits represented by each BCM codeword determines the number of BCM codewords that can possibly occur in that BCM code. In this example and since each information bit can take only one of two values (0 and 1), the number of possible BCM codewords is 2⁷ = 128. Each of these 128 possible BCM codewords is represented by a respective path through the trellis shown in Fig. 8.

It can be seen that each path through the trellis, e.g., the path ABCDO, comprises a set of branches, e.g., AB, BC, CD, and DO. Each branch is labeled with the decimal value of a respective triplet {b₂b₁b₀} that can be generated by the three component-code encoders at each signalling interval. For example, the branches AB, BC, CD, and DO are labeled with the values 0, 0, 0, and 0, respectively. Thus in this example, the path ABCDO represents the BCM codeword comprising all zeroes. As another example, the path AXPZO represents the BCM codeword comprising all sevens.

Decoding such a BCM codeword is preferably done using the well known Viterbi algorithm, which has also been modeled as a trellis. According to the Viterbi algorithm, each branch of the trellis represents a symbol and a metric is assigned to each branch that corresponds to the likelihood that the symbol represented by that branch is the actual transmitted symbol. One such metric is the squared Euclidean distance between a received signal and an estimated value of the signal, using the hypothesis that the symbol corresponding to that branch was actually transmitted. Branches merge at each node in the trellis, and at each node the branch assigned the lowest valued metric is selected and used to update a node metric, or path metric. This is repeated through the trellis, and finally the path having the best path metric is selected. The information bits that are represented by the symbols represented by the selected path are produced as the decoded bits.

The following describes one example of the procedure implemented by an improved decoder 33' for decoding BCM codewords formed by using a product code.

As in the example illustrated in Fig. 5a, a (4,1) repetition code is the inner code and a (4,3) single-parity-check code is the outer code. The symbol interleaver 17 at the transmitter (see Fig. 1a) is configured as an array of memory elements having four columns and sixty-eight rows, and the four modulation symbols comprising each BCM codeword are written into the interleaver 17 by row and read out by column. Hence, successive symbols in a BCM codeword are separated by sixty-eight symbol periods, which provides protection in a fading environment.

The receiver includes a de-interleaver 32 for recreating the picture at the transmitter. The de-interleaver 32 also is configured as an array of memory elements having four columns and sixty-eight rows. The received symbols produced by the sample timing selector 31 are written into the de-interleaver 32 by row, and thus each row stores a BCM codeword comprising successive symbols that have been affected by radio propagation conditions that were separated in time by sixty-eight symbol durations.

Each row of symbols stored in the de-interleaver 32 is decoded by an improved decoder 33' using the Viterbi algorithm as described above. Since the inner code is a repetition code that produces the same bits over the entire block length (trellis), only two path metrics at the end of each decoded row of the de-interleaver array need be retained. These two path metrics are soft information that is used during the decoding of the outer code. The decoding of the stream b₀ encoded according to the product code is described below.

The bits b₀ are protected by the product code, comprising the inner code and the outer code as illustrated in Fig. 5a. In this arrangement, the codewords of the inner-code stored in the rows of the de-interleaver memory while the codewords of the outer-code are stored along the columns (i.e., across multiple rows) of the de-interleaver memory, as illustrated in Fig. 9 for one codeword 901. Decoding a codeword generated by this exemplary product code begins by decoding row 1, at the end of which there exists one of two possible values for bit b₀: b₀ = 0 or b₀ = 1. A value of 1 may be decoded if the best path, i.e., the path having the best path metric, is in the bottom half of the trellis shown in Fig. 8, and a value of 0 may be decoded if the best path is in the top half of the trellis. This can be decided from Fig. 9.

Nevertheless, the decision on this bit can be improved due to the second level of coding, the outer code. Hence, at the end of decoding each row, the best path metric from each half of the trellis is used to represent the probability of the bit value being a 1 or a 0. These probabilities are denoted as P_1j and P_0j, respectively, where the index j denotes the row number (in this case row 1) that was decoded. These probability values are stored as soft information, and decoding continues with rows 2, 3, and 4.

The result of this process for one product-code codeword is the probability values P₁₁, P₁₂, P₁₃, P₁₄ and P₀₁, P₀₂, P₀₃, P₀₄, which are then combined according to one of the following rules to yield the decoded codeword C_d: <maths id="math0003" num=""><math display="block"><mtable columnalign="left"><mtr><mtd><mi mathvariant="normal">Rule</mi><mi> </mi><mn>1</mn></mtd></mtr><mtr><mtd><msub><mi>C</mi><mi>d</mi></msub><mo>=</mo><munder><mrow><mi mathvariant="normal">min</mi></mrow><mi>i</mi></munder><mrow><mo>{</mo><mrow><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mi>l</mi></mrow><mrow><msub><mi>N</mi><mrow><mi>block</mi></mrow></msub></mrow></munderover><mrow><msub><mi>P</mi><mrow><mn>0</mn><msub><mi>j</mi><mi>k</mi></msub></mrow></msub></mrow></mstyle><mo>+</mo><msub><mi>C</mi><mrow><mi>i</mi><msub><mi>j</mi><mi>k</mi></msub></mrow></msub><mrow><mo>(</mo><mrow><msub><mi>P</mi><mrow><mn>1</mn><msub><mi>j</mi><mi>k</mi></msub></mrow></msub><mo>−</mo><msub><mi>P</mi><mrow><mn>0</mn><msub><mi>j</mi><mi>k</mi></msub></mrow></msub></mrow><mo>)</mo></mrow></mrow><mo>}</mo></mrow></mtd></mtr></mtable></math><img file="EP1018232B1_D0003.tif" /></maths><maths id="math0004" num=""><math display="block"><mtable columnalign="left"><mtr><mtd><mi mathvariant="normal">Rule</mi><mi> </mi><mn>2</mn></mtd></mtr><mtr><mtd><msub><mi>C</mi><mi>d</mi></msub><mo>=</mo><munder><mrow><mi mathvariant="normal">max</mi></mrow><mi>i</mi></munder><mrow><mo>{</mo><mrow><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mi>l</mi></mrow><mrow><msub><mi>N</mi><mrow><mi>block</mi></mrow></msub></mrow></munderover><mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><mn>2</mn><msub><mi>C</mi><mrow><mi>i</mi><msub><mi>j</mi><mi>k</mi></msub></mrow></msub></mrow><mo>)</mo></mrow><mrow><mo>(</mo><mrow><msub><mi>P</mi><mrow><mn>1</mn><msub><mi>j</mi><mi>k</mi></msub></mrow></msub><mo>−</mo><msub><mi>P</mi><mrow><mn>0</mn><msub><mi>j</mi><mi>k</mi></msub></mrow></msub></mrow><mo>)</mo></mrow></mrow></mstyle></mrow><mo>}</mo></mrow></mtd></mtr></mtable></math><img file="EP1018232B1_D0004.tif" /></maths> where <i>c</i>_{ij<sub2>k</sub2>} is the bit value (0 or 1) in row j_k of the i - th codeword of the outer code C_i = {C_ij1 C_ij2 ··· c_{ijN<sub2>block</sub2>}}, and N_block is the block length of the outer code. Rules 1 and 2 can be derived using a conditional log-likelihood function.

Rules 1 and 2 above show how one can use the soft information (for each bit of the codeword of the outer code) to make a decision on the codeword of the outer code. Thus, the rules 1 and 2 are applicable in all cases.

This method can be generalized: Through the decoding process of the inner (BCM) codeword, one can generate soft information (metrics) related to the bits of the outer codeword. This soft information can then be used to decode the outer codeword. Then, using the decoded bits of the outer codeword, the remaining bits of the inner codeword can be decoded.

In this example, N_block = 4, and the (4,3) single-parity-check code has eight possible codewords, which are the code-symbol quadruplets {0000}, {0011}, {0101}, {0110}, {1001}, {1010}, {1100}, and {1111}. The codeword that is optimal according to Rules 1 or 2 is chosen, and its bits are produced by the BCM decoder as the corresponding data bits i₀. This completes the decoding of the bit stream b₀ over the inner and outer codes.

Using a product code in this way provides a significant performance gain for the stream b₀ compared to using a single code C₀. Nevertheless, letting the code bits of the outer code fall in contiguous locations (along the columns of the interleaver and de-interleaver arrays) can result in a problem. A fade might wipe out all of the code bits of the outer code with a high probability, thereby nullifying the effect of the outer code. This can be seen from Fig. 9, in which the outer-code bits run along the columns but successive outer-code bits, such as the outer code bit 901, occupy locations in successive rows.

It is therefore advantageous to separate the bits of the outer code by disposing an additional interleaver 17-1 between the outer-code encoder 15-1 and the inner-code encoder 15-2, as illustrated in Fig. 5b. This can be done without altering the size of the interleaver 17 and de-interleaver 32. The additional interleaver 17-1 shuffles the outer-code bits along the columns, with the result that there is less chance that a fade will affect all bits of an outer-code codeword, thereby making it easier to correct the isolated error using the other correct bits. The collection of bits that make up a second codeword 903 illustrate how an outer codeword would be reassembled in an embodiment incorporating the additional interleaver 17-1. Essentially, if there is no interleaver between the outer code and inner code, then the bits from the codeword of the outer code are in consecutive rows (j, j+1, j+2, ... , j+N_block-1), as illustrated by outer codeword 901. If there is an interleaver, then the bits from the codeword of the outer code are in rows (j₁, j₂, ..., j_{N_block}), where the j_k's are not consecutive, as illustrated by outer codeword 903. In this latter case, the particular j_k's for each codeword of the outer code are determined by the additional interleaver 17-1, and cannot be specified by any universally applicable formula.

The decoding process for the embodiment that includes the additional interleaver 17-1 is substantially as outlined above, with the exception that path metrics P_0j and P_1j from appropriate rows are combined according to Rules 1 or 2 to decode the bits.

The additional interleaver 17-1 yielding the arrangement that generates, for example, the outer codeword 903 is a rectangular interleaver having seventeen rows and four columns. This separates successive bits of the outer code by seventeen symbol periods. The inner-code bits are interleaved as described above by a block interleaver 17 having sixty-eight rows and four columns.

In another aspect of the invention, the use of a product code as described above can be utilized to improve the decoding of the remaining bits in each symbol. This is because once the product-coded bits have been decoded, knowledge of what its constituent bits are can be used to make better decisions in the decoding of the remaining coded bits produced by the other codes. For example, referring back to Fig. 9, the decoding of codeword 0 has been described: one first generates soft information for rows 1 through 4; then, the soft information for bits b₀¹, b₀⁵, b₀⁹ and b₀¹³ are used to perform the outer decoding. Once this has been decoded, however, one has better information about the values of these particular bits. Therefore, in accordance with this aspect of the invention, one goes back and decodes rows 1 through 4 again, this time utilizing the knowledge of what the b₀ bits ought to be. In this manner, the decoding of the b₁ and b₂ bits obtains the benefit of the outer coding and interleaving that has been applied only to the b₀ bits.

In accordance with the invention, a product code is used to improve the performance of a class of bits in a coded modulation scheme without increasing the decoding complexity or decreasing the BER performance of the other classes of bits. The decoding procedure for the product code uses soft information that is passed between the decoders of the inner and outer codes of the product code. Using a product code provides a significant performance gain for that class of bits at the expense of a marginal reduction in the information rate.

It will be appreciated by those of ordinary skill in the art that this invention can be embodied in other specific forms without departing from its essence. The embodiments described above are therefore to be considered illustrative and not restrictive. The scope of the invention is defined by the following claims rather than the foregoing description, and all changes that come within the meaning and range of equivalents of the claims are intended to be embraced therein.