Decoding multi-block product code

This invention relates to efficient encoding, mapping, demodulation and decoding of signals expressed in a multi-level block product code format.

A product code is a multi-dimensional array of (n,k) linear block code that exploits a simple and relatively efficient method to construct more powerful codes using linear block code structures. FIG. 1 illustrates construction of a two-dimensional block product code, using a k1×k2 array of data to be encoded. In the encoding, each row of k2 data values is augmented to include n2-k2 parity check bits for the data in that row; and each column of k1 data values is augmented to include n1-k1 parity check bits for the data in that column. The (n1k1)×(n2-k2) region at the lower right of this block contains parity check bits for each of the n2-k2 columns above and for each of the n1−k1 rows to the left. Where, for example, a BCH code is used in a 64QAM configuration, k1=k2=57 and n1=n2=63. Because 57=2 6 −6−1, the 7 conventional parity check bits can be replaced by 7 Hamming error check bits using a Hamming single error correction formulation, as discussed in S. B. Wicker, Error Control Systems , Prentice Hall, Englewood Cliffs N.J., 1995, pp. 8-11, 90-94.

In any digital representation of a signal value, the most important bit is the MSB (most significant bit), followed in turn by other bits (MSB- 1 , MSB- 2 , . . . , LSB) in the representation sequence. In a conventional transmission of this digital representation, all bits are treated equally in signal coding and decoding for such transmission. This approach is often inefficient, because the bits are not equally affected by noise and other perturbations in the transmission channel and are not equally important. This is especially true where a QAM configuration is used and the higher order bits (MSB, MSB- 1 , etc.) are more likely to be correct.

What is needed is an efficient method for encoding and mapping a digital sequence into a sequence of signal values, and decoding the received signal values into a corresponding true digital sequence before encoding at the transmitter side, using a (2 2p )QAM configuration (p=2, 3, 4, etc.) for the I and Q components. This method should allow different bits in a digital representation to be protected and transmitted differently, if desired, to take account of the differing likelihoods that each bit will become corrupted by noise and other perturbations in the transmission channel.

These needs are met by the invention, which provides an optimal procedure for transmission and decoding of different bits in a digital representation of a signal value. For example, where a 64QAM (I,Q) configuration is used, the I and Q coordinates are assigned eight monotonically increasing values, −v1, −v2, −v3, −v4, v4, v3, v2 and v1, and a three-step decoding algorithm is implemented to determine a triple of values, (r b2 ,r b1 ,r b0 ) or (B 2 ,B 1 ,B 0 ), representing the decoded received signal. For other QAM configurations, other optimal value assignments are used. A transmission channel figure of merit, such as Eb/N0, is estimated to determine a (different) bit error rate associated with each of the transmitted bits.

FIG. 1 illustrates a block product code in two dimensions.

FIG. 2 illustrates a signal transmission environment according to the invention.

FIGS. 3 , 5 and 6 illustrate signal constellations for 64QAM and two kinds of 16QAM, according to the invention.

FIGS. 4 , 7 and 8 graphically illustrate relationships between expected bit error rates (BER) and a signal-noise quality parameter Eb/N0 as used in the invention for 64QAM and two different 16QAM configurations.

With reference to FIG. 2 , a digital bit sequence B is to be transmitted using a QAM or similar signal representation scheme, from a transmission module 11 , through a transmission channel 15 , to a receiving module 16 . The sequence is processed by an encoder 12 , a mapper 13 and a modulator 14 in the transmitter 11 , producing an analog signal that is transmitted over the channel 15 . The transmitted signal is received at the receiver 16 , which includes an analog-to-digital converter or demodulator (ADC) 17 , whose output signal W′ is a sequence of digital values corresponding to the output signal of the mapper 13 ; if no noise is present, W′=W. The sequence W′ is decoded by a multi-level BPC decoder 18 to recover the B=3·k bits received by the encoder 12 .

It is assumed that the bit B(k−1) is less important than, or no more important than, the bit Bk for k=1, 2, . . . , M. The sequence W is mapped by decomposition into two or more consecutive and mutually exclusive segments or sub-sequences of bits, SB 1 =(BM, . . . , Bk) and SB 2 =(B(k−1), . . . , B 0 ), or into M+1 single-bit segments, and each segment is provided with a different level of protection before transmission occurs. The sequence is received and decoded by a procedure that takes account of the differing consequences of, and likelihood of, a sequence being corrupted by the transmission process.

Consider a digital word W having six bits (M=5) that is represented with 3 I bits and 3 Q bits in an (I,Q) format. In the most general approach, each I bit and each Q bit is provided with a different level of protection as part of the transmission process. If desired, a segment with two or more consecutive bits can be provided with the same protection. The appropriate QAM representation here uses 2 (3+3) (=64 (I,Q) coordinates in four quadrants of the ((I,Q) plane.

In a hierarchical 64QAM modulation, illustrated in FIG. 3 , 64 (I,Q) signal coordinate pairs are arranged into 4 groups of 4×4 blocks, one in each of the four quadrants in the plane. Each signal or signal value received is assigned to the “closest” (according to the metric adopted) of the 64 indicated locations in the plane, depending upon the amplitude and phase associated with that signal. Several QAM configurations are discussed and illustrated in W. Tomasi, Electronic Communication Systems , Prentice Hall, Englewood Cliffs, NJ, 1988, pp. 518-528. One problem in use of a QAM configuration is to indicate, using as few bits as possible, which signal location is presently referred to. In the invention, a 64QAM configuration uses six bits to refer to the (I,Q) location for the present signal, and these bits are specified as follows.

Consider the two three-bit specifications, (B 2 ,B 1 ,B 0 )=(I 2 ,I 1 ,I 0 ) and (B 2 ,B 1 ,B 0 )=(Q 2 ,Q 1 ,Q 0 ), referring to the in-phase coordinate and the quadrature coordinate, respectively, with each bit independently having the usual values, 0 and 1. In a preferred embodiment, each bit B 2 , B 1 and B 0 is transmitted as part of a different 64×64 block. Table 1 sets forth the assignment of the bit value combinations for the I and Q coordinates, and FIG. 3 indicates the coordinate positions in the plane corresponding to each of these 64 combinations.

For example, the pair of triples {(I 2 ,I 1 ,I 0 ), (Q 2 ,Q 1 ,Q 0 )}={(0,1,0), (1,1,0)} has the (I,Q) location coordinates (−4,7), and the pair of triples {(I 2 ,I 1 ,I 0 ), (Q 2 ,Q 1 ,Q 0 )}={(1,0,0), (0,0,1)} has the (I,Q) location coordinates (2,−7), as indicated in FIG. 3 . In a 64QAM configuration, a signal is assigned the (I,Q) coordinates of the location closest to the <measured or observed signal amplitude and phase values.

For example, consider a signal for which the measured or observed (I,Q) values are (r I ,r Q )=(−3.4,+5.6). With reference to the I and Q coordinate values ±vk chosen in Table 1, namely

(−v1, −v2, −v3, −v4, v4, v3, v2, v1)=(−9,−7,4,−2,2,4,7,9),

the “closest” of these coordinate values may be computed as follows. When r x ≧0 (x=I,Q), define

r^ x =vk for which |r x −vk′|=minimum value (k′=1, 2, 3, 4).  (1)

When r x <0, define

r^ x =−vk for which |r x +vk′|=minimum value (k′=1, 2, 3, 4).  (2)

Now identify the triple (B x2 ,B x1 ,B x0 ) from Table 1 that corresponds to r^ x for x=I and for x=Q. For the example discussed here, (r^ I ,r^ Q )=(−4,7) and (I 2 ,I 1 ,I 0 )=(0,1,0) and (Q 2 ,Q 1 ,Q 0 )=(1,1,0). A different, Viterbi-type process can also be used to decode the values (I 2 ,I 1 ,I 0 ) and (Q 2 ,Q 1 ,Q 0 ) associated with the received signal values r I and r Q .

The decision process set forth above, as well as many Viterbi-type processes, for determining the triple (I 2 ,I 1 ,I 0 ) and/or (Q 2 ,Q 1 ,Q 0 ) is a soft input-hard output (SIHO) process that is simple to apply but may not provide an optimal solution for determining the correct digital values of the transmitted triples. In a preferred embodiment, the invention uses a soft input-soft output (SISO) decision process in that it provides an intermediate sequence of probability values (associated with a selected probability measure) that a given triple (B 2 ,B 1 ,B 0 ) is the correct or optimal choice, as well as iteratively decoding these intermediate probabilities. One SISO decision process, referred to as the MAP (maximum a posteriori probability) process or the BCJR process, is discussed in detail by C. Heegard and S. B. Wicker in Turbo Coding , Kluwer Academic Publishers, Boston, 1999, pp. 70-71 and 121-140; the content of this discussion is incorporated by reference herein.

The (I,Q) coordinate values assigned according to Table 1 can be changed to decode to an integer set other than {−9, −7, 4, −2, 2, 4, 7, 9}, but it is preferred that the eight numbers used be a monotonic and distinct sequence, with a positive increment between any two consecutive values in the sequence so that a bit error rate performance curve (e.g., as shown in FIG. 4 ) be approximately uniformly distributed.

With reference to the specification in terms of a triple (I 2 ,I 1 ,I 0 ) or (Q 2 ,Q 1 ,Q 0 ), the corresponding symbol is a combination of three blocks (or six blocks) in an ordered sequence of 57 bits +6 bits +1 bit. The 57 upper bits are message or data bits, the next 6 bits are parity check bits, and the LSB (one bit) is a modulo-2 sum of the preceding 63 bits.

Assume that an analog signal is received as indicated in FIG. 2 and processed by the demodulator 17 to provide a digital sequence (I,Q) to be decoded by the decoder 18 . Let (B 2 ,B 1 ,B 0 ) represent the received I channel component, or the Q channel component, of the signal after decoding in a 64QAM format. For the mapping set forth in Table 1, the set of positive index values (v1,v2,v3,v4)=(9,7,4,2) has an average value of a1=(9+7+4+2)/4=5.5. The average value of a first remainder (after subtraction of the first average value of 5.5) is a2=(7+9)12−5.5=2.5. A second remainder is a2=(9−7)/2=1. The average value and first remainder value for each of the I and Q coordinates are indicated in FIG. 3 . The received index values, ±v1, ±v2, ±v3 and ±v4, will include noise associated with the transmission channel.

Using a selected metric process such as the one discussed in connection with Eqs. (1) and (2), or an SISO process, a triple (B 2 ,B 1 ,B 0 ) of digital values is determined whose corresponding numerical value from Table I is “closest” to the received signal value. In an SISO process the values Bk (k=2,1,0) are decoded individually, not as a group.

The received signal value r=(j) of the jth QAM signal is divided by the first average, a1=5.5, as a first stage in the decoding process

r b2 =r/a 1= r/ 5.5,  (3)

where r b2 (j) is not usually an integer and represents a symbol value, corresponding to an MSB coordinate. Using the value r b2 as an input for first stage decoding, a digital value B 2 is determined. In a second stage of decoding, a first remainder:

r b1 ={r/ 5.5−(2· B 2 −1)}·( a 1/ a 2)={ r b2 −(2· B 2 −1)}·(5.5/2.5)  (4)

is computed, and a digital value B 1 is determined after decoding of the input value r b1 . In a third stage of decoding, a second remainder

r b0 ={r/a 1−(2· B 2 −1)}· a 1−(2· B 1 −1)·( a 2/ a 3)={ r b1 −(2· B 1 −1)}·2.5.  (5)

is computed. The decoder thus receives the signal value r=r(j), determines a first ordered sequence of digital values {r b2 (j),r b1 (j),r b0 (j)}, and determines a second ordered sequence (B 2 ,B 1 ,B 0 ), individually or collectively, representing a decoding of the original received signal, r=r(j), for the selected 64QAM format. For example, if the received signal r(j) has a value of 6.5, the decoding sequence for this received signal becomes {r b2 (j),r b1 (j),r b0 (j)}={1.1818,0.4,−1.5}.

FIG. 4 graphically illustrates the relationships between bit error rates (which range from 10 −7 to 10 −2 ) associated with decoding of each of the three bits B 2 , B 1 and B 0 for values of a channel figure of merit, a signal-noise parameter Eb/N0, using the decoding scheme of the invention for a 64QAM format. With this approach, the increment Δ(Eb/N0) from bit B 2 to bit B 1 , and from bit B 1 to bit B 0 , is approximately 6 dB for each of these increments. This is a desirable situation. If Δ(Eb/N0; B 2 ;B 1 ) and Δ(Eb/N0;B 1 ;B 0 ) have substantially different numerical values, the smaller of these two increments would be dominant for purposes of BER control, which is not an optimal situation.

If the parameter value satisfies Eb/N0=14.5 dB, which would be typical for a reasonably quiet and stationary environment not subjected to strong perturbations (e.g., home receipt of a television signal), all three bits (B 2 ,B 1 ,B 0 ) can be recovered without error. In this ideal environment, an HDTV signal can be transmitted, received and displayed.

If the parameter value satisfies 7.5 dB≦Eb/N0<14.5 dB, the bits B 2 and B 1 can be recovered without error, but the bit value B 0 will have varying errors. In this environment, for example, a standard television signal SDTV may be transmitted, received and displayed.

If the parameter value satisfies 3.5 dB≦Eb/N0<7.5 dB, corresponding to a mobile transmission environment, only the bit B 2 can be recovered without error, and the bits B 1 and B 0 will have varying errors. In this environment, for example, a black and white television signal or a paging signal, using a single signal value (B 2 ), can be transmitted, received and displayed. If the parameter value satisfies Eb/N0<3.5 dB, no signal bit is free from expected error.

A four-bit transmission system will use 2 4 =16 (I,Q) values. FIG. 5 illustrates a 16QAM configuration, analogous to the 64QAM configuration shown in FIG. 3 , arranged into 4 2×2 blocks, one in each of the four quadrants. Here, the I and Q coordinate values assigned to the 16 locations are ±2 and ±5. Table 2 sets forth the I and Q location assignments for this configuration of 16QAM, corresponding to FIG. 5 .

Within a quadrant, the horizontal or vertical nearest neighbor separation distance of any two locations is 3 units (=5−2). Between two adjacent quadrants the nearest neighbor separation distance is 4 units (=2−(−2)). The average I values or average Q values and remainder values for the assigned locations in the first quadrant are a1=(5+2)/2=3.5 and a2=(5−2)/2=1.5.

Decoding for this 16QAM configuration proceeds as follows. If the jth signal value received is r=r(j), the pair (B 1 ,B 0 ) is decoded in two steps:

r b1 = r / a1 = r / 3.5 , ( 6 ) r b0 = ⁢ a1 · { r b1 - ( 2 · B1 - 1 ) } / ( a2 ) = ⁢ 3.5 · { r b1 - ( 2 · B1 - 1 ) } / ( 1.5 ) . ( 7 )

For example, if the received signal r(j) has a value of 2.75, corresponding to (B 1 ,B 0 )=(1,0), the decoding sequence for this received signal becomes {r b1 (j),r b0 (j)}={0.7858,−0.5}.

The relationships between bit error rates associated with each of the two bits B 1 and B 0 and the 16QAM format, for the I and Q coordinates choices (±2,±5), are similar to those shown in FIG. 4 for the QAM format.

FIG. 6 illustrates a different 16QAM configuration, in a different set of I and Q coordinate values are assigned to the 16 locations: ±4 and ±2. Table 3 sets forth the I and Q location assignments for the 16QAM configuration of FIG. 6 .

Within a quadrant, the horizontal or vertical nearest neighbor separation distance of any two locations is 2 units (=4−2). Between two adjacent quadrants the nearest neighbor separation distance is 4 units (=2−(−2)). The average and remainder values for the assigned locations in the first quadrant are a1=(4+2)/2=3.0 and a2=(4−2)/2=1.0.

Decoding for this 16QAM configuration proceeds as follows. If the jth signal value received is r=(j), the pair (B 1 ,B 0 ) is decoded in two steps:

r b1 = r / a1 = r / 3.0 , ( 8 ) r b0 = ⁢ a1 · { r b1 - ( 2 · B1 - 1 ) } / ( a2 ) = ⁢ 3.0 · { r b1 - ( 2 · B1 - 1 ) } / ( 1.0 ) . ( 9 )

FIGS. 7 and 8 graphically illustrate the relationships between bit error rates (which range from 10 −7 to 10 −2 ) associated with decoding of each of the two bits, B 1 and B 0 , for values of a channel figure of merit, a signal-noise parameter Eb/N0, using the decoding scheme of the invention for the two 16QAM configurations discussed herein. Although the two configurations produce similar BER values for corresponding Eb/N0 ratios, the bit B 0 for the 16QAM (2,5) configuration has significantly lower BER values, and the (2,5) mapping may be preferred over the (2,4) mapping for that reason. However, the (2,5) mapping uses more energy than the (2,4) mapping, and the required range of the Eb/N0 ratio for the bit B 1 is higher for the (2,5) mapping than for the (2,4) mapping so that the (2,4) mapping may be preferred over the (2,5) mapping.

More generally, assume that a (2 2p )QAM configuration is to be used to encode, transmit and decode a bit sequence (B(p−1),B(p−2), . . . , B 0 ), representing a signal value r, where p=2, 3, 4, . . . is a selected positive integer. Assume that the p values of the I coordinates and the p values of the Q coordinates in a first quadrant are selected to be a monotonically strictly decreasing sequence v1, v2, . . . , v(2 p ) of positive values. The signal value r=r(j) is received and processed and recovered as a p-tuple (r b,p-1 ,r b,p-2 , . . . , r b,0 ), defined by

r b,p-1 =r/a (1),  (10)

r b,p-k-1 ={r b,p-k −(2· B ( p-k )−1)·( a ( k ))}/( a ( k+ 1)) ( k= 1, . . . , p− 2),  (11)

r b,0 =a ( p− 1){ r b,1 −(2· B 1 −1)}/ a ( p )  (12)

a ( k )={ v 1+ . . . + v (2 p-k )}/2 p-k −a (k−1),  (13)

a (0)=0,  (14)

a ( p )=( v 1− v 2)/2,  (15)

where the coordinate B(p-k) is determined or decoded using an SIHO or SISO process or a selected metric process from the values r b,p-k , as a modified version of the received signal r=r(j), in a p-step decoding procedure. In particular, this prescription extends the invention to use of a 256QAM configuration, with p=4, and to use of 1024QAM configuration, with p=5.