

Multilevel coding using trelliscoded modulation and reedsolomon codes 
5258987 
Multilevel coding using trelliscoded modulation and reedsolomon codes


Patent Drawings: 
(10 images) 

Inventor: 
Wei 
Date Issued: 
November 2, 1993 
Application: 
07/869,985 
Filed: 
April 16, 1992 
Inventors: 
Wei; LeeFang (Lincroft, NJ)

Assignee: 
AT&T Bell Laboratories (Murray Hill, NJ) 
Primary Examiner: 
Canney; Vincent P. 
Assistant Examiner: 

Attorney Or Agent: 
Slusky; Ronald D.deBlasi; Gerard A. 
U.S. Class: 
714/758; 714/784; 714/792 
Field Of Search: 
371/37.1; 371/37.4; 371/37.5; 371/43; 371/44; 371/45 
International Class: 
H04L 27/34 
U.S Patent Documents: 
5023889; 5052000; 5117427 
Foreign Patent Documents: 

Other References: 
Outage Control in Digital Cellular Systems by Stuber et al., IEEE Transactions on Vehicular Technology, vol. 40, No. 1, Feb. 1991, pp.177187.. The Performance of RateCompatible Punctured Convolutional Codes for Digital Mobile Radio by Hagenauer et al., IEEE Transactions on Communication, vol. 38, No. 7, Jul. 1990, pp. 966980.. J. Wu and X. Zhu, "MultiLevel Multidimensional Trellis Codes", International Symposium on Information Theory, Abstracts of Papers, 1990, p. 110.. A. Ushirokawa and H. Matsui, "Multilevel Codes for HighSpeed Voiceband Data Modem," Proc. of IEEE Globecom 1989, pp. 19711975.. G. J. Pottie and D. P. Taylor, "Multilevel Codes Based on Partitioning," IEEE Transactions on Information Theory, vol. 35, No. 1, Jan. 1989, pp. 8798.. L. F. Wei, "TrellisCoded Modulation with Multidimensional Constellations," IEEE Transactions on Information Theory, vol. IT33, No. 4, Jul. 1987, pp. 483501.. A. M. Michelson and A. H. Levesque, ErrorControl Techniques for Digital Communication, John Wiley & Sons, 1985, Chapter 6.. 

Abstract: 
A multilevel coded modulation scheme trellis encodes a portion of the input data and the resulting encoded stream is used to identify a particular one of a predetermined number of subsets of symbols of a predetermined signal constellation. The remaining input data is coded using a ReedSolomon (RS) code whose output is used to select for transmission a particular symbol from the identified subset. In applications in which phase hits or other channel phenomena may cause the received signal points to be phaserotated versions of the signal points that were transmitted, differential encoding is included in the overall coded modulation scheme. In different embodiments, the differential encoding/decoding and RS encoding/decoding are in different orders. In one such embodiment, overlapped multilevel codes are used to preserve the advantages afforded by taking a multilevel coding approach. 
Claim: 
I claim:
1. Transmitter apparatus comprising
first and second redundancy encoders,
means for applying first and second streams of data to said first and second redundancy encoders, respectively,
mapping means for providing channel symbols selected from a predetermined signal constellation in response to the outputs of said encoders, said signal constellation having a plurality of subsets of channel symbols, the channel symbols beingseparated from each other by a predetermined distance,
characterized in that said first and second encoders are a trellis encoder and a ReedSolomon encoder, respectively, and wherein:
said mapping means a) identifies a sequence of said subsets in response to the output of said trellis encoder, the sequence having a trellis distance, and b) selects a channel symbol from each subset of said sequence in response to the output ofsaid ReedSolomon encoder, and
the trellis distance is greater than the predetermined distance.
2. The invention of claim 1 further comprising means for generating a passband signal representing the channel symbols provided by said mapping means and for applying said passband signal to a transmission channel.
3. The invention of claim 1 wherein said mapping means and said trellis encoder, in combination, provide a first particular level of error rate performance for said first stream of data and wherein said mapping means, said trellis encoder andsaid ReedSolomon encoder, in combination, provide a second particular level of errorrate performance for said second stream of data which is at least as great as said first particular level of error rate performance.
4. The invention of claim 1 wherein said signal constellation is a 2Ndimensional constellation based on a rectangular lattice, N being an integer.
5. The invention of claim 4 wherein there are 4N of said subsets.
6. The invention of claim 5 wherein said ReedSolomon encoder implements a singleerrorcorrecting ReedSolomon code.
7. The invention of claim 6 wherein said trellis encoder implements a fourdimensional trellis encoder.
8. The invention of claim 5 wherein said ReedSolomon encoder implements a doubleerrorcorrecting ReedSolomon code.
9. The invention of claim 8 wherein said trellis encoder implements a twodimensional, trellis encoder.
10. Receiver apparatus for processing a received signal that was generated by applying first and second data streams to a trellis encoder and a ReedSolomon encoder, respectively, to provide first and second encoder output streams, respectively,and by thereafter providing, in said generated signal, a sequence of channel symbols having a trellis distance and being selected from a predetermined 2Ndimensional signal constellation based on a rectangular lattice, N being an integer, said signalconstellation comprising a plurality of subsets of channel symbols separated by a predetermined distance, which is less than said trellis distance, said channel symbols being selected in response to said first and second encoder output streams, saidreceiver apparatus comprising
means including a maximum likelihood decoder for recovering from said received signal a) said first data stream and b) said second encoder output stream,
a ReedSolomon decoder, and
means for applying said recovered second encoder output stream to said ReedSolomon decoder to recover said second data stream.
11. A method comprising the steps of
applying first and second streams of data to a trellis encoder and a ReedSolomon encoder, respectively, and
generating, in response to the outputs of said encoders, an output signal representing channel symbols selected from a predetermined signal constellation, said signal constellation comprising a plurality of subsets of channel symbols separated bya predetermined distance, and wherein said generating step includes the steps of:
identifying a sequence of said subsets in response to the output of said trellis encoder, the sequence having a trellis distance, and
selecting a channel symbol from each subset of said sequence in response to the output of said ReedSolomon encoder, wherein the trellis distance is greater than the predetermined distance.
12. The invention of claim 11 wherein said generating step includes the steps of
generating, as said output signal, a passband signal representing the selected channel symbols, and
applying said passband signal to a transmission channel.
13. The invention of claim 11 wherein the combination of said applying and generating steps provides a first particular level of error rate performance for said first stream of data and a second particular level of errorrate performance forsaid second stream of data which is at least as great as said first particular level of error rate performance.
14. The invention of claim 11 wherein said signal constellation is a 2Ndimensional constellation based on a rectangular lattice, N being an integer.
15. The invention of claim 14 wherein there are 4N of said subsets.
16. The invention of claim 15 wherein said ReedSolomon encoder implements a singleerrorcorrecting ReedSolomon code.
17. The invention of claim 16 wherein said trellis encoder implements a fourdimensional trellis encoder.
18. The invention of claim 15 wherein said ReedSolomon encoder implements a doubleerrorcorrecting ReedSolomon code.
19. The invention of claim 18 wherein said trellis encoder implements a twodimensional trellis encoder. 
Description: 
BACKGROUND OF THE INVENTION
The present invention relates to multilevel coded modulation useful, for example, in voiceband data transmission (e.g., modem) applications.
As used herein, the term "multilevel coded modulation" refers to arrangements in which input data is divided into two or more streams which are individually encoded using respective redundancy codes. The coded outputs are then used jointly toselect channel symbols from a predetermined signal constellation for transmission over a communication channel, such as a voiceband telephone channel. The principle advantage of adopting a multilevel coded modulation approach is that it provides thesystem designer with increased flexibility in designing a coding scheme which provides desired levels of errorrate performance, or "coding gain," while meeting various constraints on code complexity and decoding delay.
Illustrative articles describing multilevel codes are: A. Ushirokawa et al, "Multilevel Codes for HighSpeed Voiceband Data Modem," Proc. of IEEE Globecom 1989, pp. 19715; J. Wu et al, "MultiLevel Multidimensional Trellis Codes,"International Symposium of Information Theory, Abstracts of Papers, sponsored by IEEE Information Theory Society, 1990, p. 110; and Pottie et al, "Multilevel Codes Based on Partitioning," IEEE Transactions on Information Theory, Vol. 35, No. 1, January,1989, pp. 8798.
SUMMARY OF THE INVENTION
In accordance with the present invention, I have discovered that a multilevel coded modulation scheme using a particular combination of two of these types of redundancy codes can be particularly advantageous. In particular, a first portion ofthe input data referred to herein as the "trellisencoded bits" is trellis encoded, and the resulting encoded stream is used to identify for each of a succession of symbol intervals a particular one of a predetermined number of subsets of symbols of apredetermined constellation. The remaining input data referred to herein as the "nontrellisencoded bits" is coded using a ReedSolomon (RS) code whose output is used to select for transmission a particular symbol from the identified subset. Advantageously, large coding gain can be obtained even when the RS code is a highrate (i.e., low redundancy, highlybandwidthefficient) code.
Preferred embodiments use a 2Ndimensional constellation (N=1, 2, 4, 8 . . . ) based on a rectangular lattice. The constellation is partitioned into 4N subsets. The number of states of the trellis code is selected based on the desirederrorrate performance for the trellisencoded bits. The errorrate performance of the nontrellisencoded bits, were they not to be encoded at all, would typically be worse than that for the trellisencoded bits, so that the errorrate performance ofthe coding scheme as a whole, i.e., the overall coding gain, would be determined, or "dominated," by the errorrate performance of the nontrellisencoded bits. The code implemented by the RS coder, however, is such as to increase the errorrateperformance for the nontrellisencoded bits to a level which is at least as great as that provided for the trellisencoded bits, so that the errorrate performance for the coding scheme as a whole is higher, it being as great as that which the trelliscode provides for the trellisencoded bits. Advantageously, it turns out that very simple highrate RS codes can be used in order to achieve this.
I have found two particular multilevel coded modulation schemes to be particularly advantageous. The first uses fourdimensional (4D) constellations, partitioned into eight 4D subsets; a 4D, 64state trellis code; and a singleerrorcorrectingRS code. The second uses twodimensional (2D) constellations partitioned into four 2D subsets; a 2D, 64state trellis code; and a doubleerrorcorrecting RS code. Either of these schemes may be used to particular advantage in two applications ofcurrent interest. One is the transmission of data at about 19.2 Kbps over dialup telephone channels. The other is the transmission of data at speeds up to the socalled T1 rate of 1.544 Mbps over the socalled telephone subscriber local loop such asis described generally in U.S. Pat. No. 4,924,492 issued May 9, 1990 to R. D. Gitlin et al.
The invention provides quite a number of advantages. For example, the RS code requires very little redundancy to achieve a desired level of overall errorrate performance, or coding gain; the bandwidth efficiency (bits per symbol) can be made toapproach that of a system in which the nontrellisencoded bits are not coded at all; errors due to impulse noise of any magnitude can be corrected; the transmission of data at various different bit rates is easily accommodated; and the multilevel codedsymbols selected for transmission can be interleaved in order to provide enhanced immunity to channel impulse noise and/or correlated noise.
BRIEF DESCRIPTION OF THE DRAWING
FIG. 1 is a block diagram of the transmitter portion of a telephone voiceband modem utilizing a multilevel coded modulation scheme embodying the principles of the invention;
FIG. 2 is a block diagram of the receiver portion of a telephone voiceband modem capable of receiving and processing the data signals generated by the transmitter of FIG. 1;
FIG. 3 is a chart helpful in understanding some conventional terminology and concepts;
FIG. 4 shows a twodimensional constellation that may be used in the transmitter of FIG. 1 either by itself or as a constituent of a higher dimensionality, e.g., fourdimensional constellation;
FIG. 5 shows how a fourdimensional constellation used in the illustrative embodiment is partitioned into eight subsets;
FIG. 6 is a table comparing various coded modulation schemes, including multilevel coded modulation schemes embodying the principles of the present invention;
FIG. 7 shows the frame organization used for the ReedSolomon encoder of the transmitter of FIG. 1;
FIG. 8 shows circuitry which implements a particular trellis code used by the trellis encoder of the transmitter of FIG. 1;
FIGS. 913 show various alternative embodiments for the encoder of FIG. 1 including a differential encoder, with the approaches of FIGS. 12 and 13 embodying inventions taught in respective copending patent applications;
FIGS. 1416 depict alternative embodiments for the decoder used in the receiver of FIG. 2, these corresponding to the encoders of FIGS. 1113, respectively; and
FIG. 17 shows circuitry which implements a particular trellis code that could be used by the trellis encoder of the transmitter of FIG. 1 in conjunction with the encoder of FIG. 13.
DETAILED DESCRIPTION
FIG. 1 is a block diagram of the transmitter portion of a telephone voiceband modem utilizing a multilevel coded modulation scheme embodying the principles of the invention. In overall view, binary data from a data source 101such as a personalcomputeris caused to be represented by 2Ndimensional symbols taken from a predetermined 2Ndimensional signal constellation, which symbols are modulated onto a carrier for transmission over a voiceband telephone channel 150.
Attention is directed briefly to FIG. 3, which will be helpful in understanding some of the terminology and concepts that are conventionally used in this art. Each of the aforementioned symbols is comprised of the concatenation of N constituenttwodimensional (2D) "signal points," N=1, 2, 3, . . . . Each such signal point is a point in a predetermined 2D constellationillustratively shown in FIG. 3 as a socalled QAM constellation. (The number of signal points in the 2D constellationdepends on the needs of the application.) A 2Ndimensional symbol is delivered to the transmission channel during N "signaling intervals" of duration T, one signal point in each signaling interval. The assemblage of all the different 2Ndimensionalsymbols used in any particular coded modulation scheme is referred to as the "2Ndimensional constellation."
In the illustrative embodiment of FIG. 1, the value of N is 2. That is, the signal constellation is a fourdimensional (4D) constellation comprised of symbols taken from first and second 2D signal constellations in the first and second signalingintervals of each 4D symbol interval, respectively. Illustratively, the same 2D constellation is used for both signaling intervals. That 2D constellation, in particular, is illustratively the 64signalpoint (64point) QAM constellation shown in FIG.4. Additionally, all possible combinations of two 2D signal points are used in this embodiment, so that the 4D constellation is comprised of 64.sup.2 =4096 4D symbols.
Returning now to FIG. 1, the stream of bits from source 101 is clocked into scrambler 104 at an average rate of 10.8875 bits per 4D symbol interval. (The significance of this rate will be made clear hereinbelow.) Scrambler 104 randomizes thedata in conventional fashion. The serial bit stream output of scrambler 104 is applied to serialtoparallel (S/P) converter 105, which provides 11bit output words on leads 108/109 for each 4D symbol interval. (As will be clear from the context,various ones of the leads shown and described herein, such as lead 108 or lead 109, will be understood as being, in actuality, a bundle of leads, each of which carries a respective bit.) In particular, two of the bits are provided on lead 108 and theother nine are provided on lead 109. As will be described in detail hereinbelow, S/P converter 105 occasionally will provide only the two bits on lead 108 without providing any bits on lead 109.
The stream of bits on leads 108/109 are applied to an encoder 11 comprised of 4D, 64state trellis encoder 112 and rate158/160 ReedSolomon (hereinafter RS) encoder 114. In particular, the stream of bits, comprising a succession of bit pairs,on lead 108 are supplied to trellis encoder 112, whose output on lead 113 comprises three bits. These three bits identify one of eight predetermined subsets of the 4096 4D symbols of the 4D constellation. The symbols are assigned to subsets in thefollowing, standard way: Each of the two 2D constituent constellations (FIG. 4) of the overall 4D constellation is partitioned into four 2D subsetsdenoted a, b, c, and d. FIG. 3 shows by a reference letter which of the four 2D subsets each of the 2Dpoints is assigned to. The eight subsets of the overall 4D constellation are then arrived at as shown in FIG. 5. In particular, 4D subset S0 is comprised of each 4D symbol in which the first and second constituent 2D signal points are both taken fromeither 2D subset a or 2D subset b. These combinations of signal points are denoted in FIG. 5 by (a,a) and (b,b), each of which is referred to as a "4D type." Each of the other 4D subsets, S1 through S7, is also formed by combining 2D subsets, asindicated in the FIG. Thus, as another example, 4D subset S3 is comprised of each 4D symbol in which the first and second constituent 2D signal points are taken from 2D subsets a and d, respectivelythe 4D type labeled (a,d)or from 2D subsets b and c,respectivelythe 4D type labeled (b,c). Since there are 4096 4D symbols overall and eight subsets, each 4D subset contains 512 4D symbols.
In prior art, conventional trelliscoded modulation (TCM) schemes, the bits provided on lead 109 are socalled "uncoded" bits which are used to select for transmission a particular symbol from the 4D subset identified by the bits on lead 113. Thus in a conventional TCM scheme, each ninebit word on lead 109 would be used to select one of the 2.sup.9 =512 4D symbols of the identified 4D subset.
In accordance with the invention, however, the stream of bits on lead 109 is not used to select a symbol directly. Rather, those bits are first encoded by RS encoder 114, and it is the output of RS encoder 114which is still in the form ofninebit wordsthat is used to select a particular symbol from the identified subset. The overall coding scheme, then, is a "multilevel coded modulation" scheme in that there are multiplein this case, twolevels of input bits being encoded. Specifically, some of the bits are trellisencoded and the restthe socalled "nontrellisencoded" bitsare ReedSolomon encoded.
RS encoder 114 is of a known typeillustratively, a conventional, ratek/k+2 systematic encoder over GF(2.sup.9) with k=158. Reed Solomon coding and decoding is described, for example, in Michelson et al, Error Control Techniques for DigitalCommunication, Chapter 6, John Wiley and Sons, 1985. As such, encoder 114 provides its outputs in RS frames. As shown in FIG. 7, each RS frame is comprised of 160 (i.e., k+2) ninebit RS words on lead 115. Since the RS code is a socalled systematiccode, the first k=158 words of the frame are simply 158 successive input words from lead 109. These are referred to herein as the "informationbearing words." The last two words of the 160word frame are socalled "redundant words" generated in responseto the values of the first 158 words in accordance with the selected RS code. When the overall frame of 160 words is first recovered in the receiver, the presence of these two redundant words therein makes possible the identification and correction ofany single, erroneously recovered one or two erased ones of the 160 words. This particular RS code is thus referred to as a singleerrorcorrecting RS code. The operation of RS encoder 114 is synchronized with that of S/P converter 105 in such a waythat a ninebit word is provided on lead 109 for each of the first 158 successive 4D symbol intervals comprising a frame and no bits are provided in the remaining two 4D symbol intervals. It is during these two intervals that encoder 114 outputs theaforementioned two redundant words.
As previously described, three bits are supplied on lead 113 for each of the 160 4D symbol intervals. Twelve bits are thus supplied on leads 113 and 115 for each 4D symbol intervalthree of the bits (lead 113) identifying a 4D subset and theremaining nine of the bits (lead 115) selecting a particular symbol of that subset. Those bits are provided to 4D, 64QAM constellation mapper 120, which outputs representation (e.g., the x and y coordinates) of the two constituent 2D signal points ofthe selected 4D symbol. Those representations are applied to conventional modulator 141, which applies to channel 150 a passband data signal representing those 2D signal points.
It can now be seen why it is that data source 101 is clocked so as to supply its data at the average rate of 10.8875 bits per 4D symbol interval, as noted above. Of the twelve bits needed to select a particular one of the 4096 4D symbols of theconstellation, one redundant bit is introduced by the trellis encoder and an average of 0.1125 (=9 bits.times.2/160) bits, i.e., the bits of the two redundant words, are introduced by the RS encoder. As a result, the data rate for source 101 needs to be(1210.1125)=10.8875 bits per 4D symbol interval.
We turn, now, to the receiver of FIG. 2.
The receiver receives from channel 150 the passband data signal generated by the transmitter of FIG. 1. The signal is first applied to equalizer/demodulator circuitry 210 which, in conventional fashion, recovers a sequence of signal points whichit provides on lead 211 to decoder 22 and, more particularly, to maximumlikelihood decoder 220 therein. Because of distortion and other channel anomalies that circuitry 210 is not able to fully compensate for, the signal points on lead 211 are somewhatdisplaced in 2D signal space from the 2D signal points that were transmitted. As its name implies, the function of maximumlikelihood decoder 220 is a) to determinebased on a knowledge of the trellis code used by trellis encoder 112what the mostlikely sequence of transmitted 4D symbols actually was, and b) to provide on leads 221 and 222 eleven bits corresponding to those 4D symbols, i.e., corresponding respectively to the bits on leads 108 and 115 in the transmitter.
The remainder of the processing performed in the receiver of FIG. 2 is the inverse of processing performed in the transmitter. Thus, in particular, RS decoder 230 within decoder 22 operates on each received frame of 160 ninebit words on lead222 to recover the 158 informationbearing ninebit words therein. In particular, as noted above, the decoder is capable of identifying and correcting any errorcorrupted single ninebit word or two erased words provided by maximumlikelihood decoder220. The stream of 158 corrected informationbearing words is supplied by RS decoder 230 on lead 232. The eleven bits on leads 221 and 232 are thereafter converted to serial form by paralleltoserial converter 270, descrambled by descrambler 280, andapplied to a data sink 290 which may be, for example, a mainframe computer.
The advantages of the invention can be understood by considering the following:
A given trellis code, when used in a unilevel coded modulation scheme, i.e., one in which the nontrellisencoded bits are not encoded at all, provides particular respective levels of errorrate performance for the trellisencoded andnontrellisencoded bits. For many trellis codes of interest, the errorrate performance of the nontrellisencoded bits is worse than that for the trellisencoded bits. Thus, the errorrate performance of the coding scheme as a whole, i.e., theoverall coding gain, is determined, or "dominated," by the errorrate performance of the nontrellisencoded bits. More particularly, the errorrate performance for the nontrellisencoded bits is here a function of the minimum Euclidean distancebetween the symbols within a subset.
(As will be well appreciated by those skilled in the art, the errorrate performance of the trellisencoded bits is principally determined by the minimum Euclidean distance between different valid sequences of 4D symbols selected respectivelyfrom different valid sequences of 4D subsets, that distance being referred to herein as the "trellis distance." (A "valid" sequence is one that is allowed by the trellis code to actually occur.) By contrast, the errorrate performance of thenontrellisencoded bits is principally determined by the smaller of a) the trellis distance, or b) the minimum Euclidean distance between different valid sequences of 4D symbols selected respectively from the same valid sequence of 4D subsets, referredto herein as the "nontrellis distance.")
If the overall errorrate performance is not adequate or acceptable for a given application, the prior art approach is to partition the constellation into a greater number of subsets. Since there are then fewer symbols per subset, the distancebetween them is thereby increased, the increase typically being such that the overall errorrate performance becomes dominated by the errorrate performance of the trellisencoded bits. The overall errorrate performance is thereby increased. There isa big price to be paid for this, however. The increase in the number of subsets requires the use of a trellis encoder that has an increased number of trellis states in the finitestate machine that implements the code. The complexity of themaximumlikelihood decoder is roughly proportional to the product of the number of subsets and the number of trellis states. Thus, the complexity of the maximumlikelihood decoder is increased dramatically. Indeed, it may be increased to the point thata practical and/or costacceptable implementation of the coding scheme may not be possible.
The present invention, by contrast, uses the abovedescribed ReedSolomon encoding, rather than an increase in the number of subsets, as the mechanism for increasing the errorrate performance of the nontrellisencoded bits. Indeed,lowcomplexity RS codes are available that can increase the nontrellis distance to a level which is greater than the trellis distance, with the result that the overall errorrate performance becomes dominated by the errorrate performance provided bythe trellis code to the trellisencoded bits. The latter will then dominate, thereby providing an increased level of errorrate performance for the coding scheme as a whole. Assuming, in the first instance, that the same trellis code is used, thecomplexity of the maximumlikelihood decoder, advantageously, stays the same. Moreover, a singleerrorcorrecting RS code, such as is used in the abovedescribed illustrative embodiment, is highly bandwidth efficient. In the above embodiment, forexample, the "overhead" caused by the RS code is only 0.1125 bits per 4D symbol, as previously seen.
Since the errorrate performance of the trellisencoded bits now dominates, one can, at this point, achieve an even greater level of overall errorrate performance, if desired, by using a trellis code which, although having more states, does notrequire an increased number of subsets. The overall effect, then, is to raise the overall errorrate performance while incurring a relatively modest increase in maximumlikelihood decoder complexity.
The foregoing is illustrated graphically in the table of FIG. 6. We take as a "baseline" the modulation scheme III shown in the table. This scheme is based on the 4096symbol, 4D constellation described above and partitioned into eight subsetsas also described above. As shown in the table, this scheme uses a) a 4D, 16state trellis code for the trellisencoded bitsillustratively the one disclosed in L. Wei, "Trellis Coded Modulation with Multidimensional Constellations," IEEE Transactionsand Information Theory, Jul. 1987, and b) no coding for the remaining, nontrellisencoded bits. For this scheme, the nontrellisencoded bits dominate the errorrate performance.
The next entry up, modulation scheme II, embodies the principles of the present invention. It uses the same constellation, the same partitioning and the same trellis code as scheme III. Now, however, the nontrellisencoded bits are encodedusing a singleerrorcorrecting RS code, such as the rate158/160 RS code described above. The table indicates, as discussed above, that the dominant error factor is the trellisencoded bits. As symbolically represented by the arrow at the left of thetable, the overall errorrate performance of this scheme is better than that of scheme III.
The top entry of the table, modulation scheme I, also embodies the principles of the invention, but now uses a more powerful trellis code. Specifically, that code is a 4D, 64state trellis code which, advantageously, is based on the sameeightsubset partitioning of the same 4D constellation. The overall errorrate performance is again improved by virtue of the increased errorstate performance which this code provides for the trellisencoded bits. Note that, in this case, the trellisdistance is still not as great as that of the nontrellis distance, so that the errorrate performance of the trellisencoded bits still dominates.
The trellis code used by trellis encoder 112 for scheme I is implemented by the circuitry of FIG. 8. In that FIG., each of the elements labeled "2T" is a delay element which delays its input by 2T seconds, i.e., the duration of a 4D symbolinterval. The elements labeled "+" are exclusiveOR gates. This is a "systematic" code, so that two of the three output bits on lead 113 are simply the two input bits from lead 108. The third output bit is generated by the circuitry shown in responseto the two input bits and delayed versions thereof. As noted above, the three output bits on lead 113 identify one of the eight 4D subsets S0, S1, . . . S7. In particular, the decimal value of the binary word formed by the three output bitswith theupper, middle and lowest bits being the most, secondmost and leastsignificant bitsdefines the subset. For example, the bit pattern 100 appearing on leads 113 identifies subset S4, since binary 100 is equivalent to decimal 4.
The transmitter/receiver system of FIGS. 12 is useful in the form shown for applications in which the transmitted signal points are not subjected to socalled "phase rotation" in the channel. For such applications, the bit patterns of the ninenontrellisencoded bits on lead 115 can be assigned to the 512 4D symbols on the identified 4D subset in an arbitrary manner. In the situation in which phase rotation is an issue, however, socalled differential encoding should be used and certaincriteria should be followed in making the bitpatterntosymbol assignment. Examples are discussed in detail at a more opportune point hereinbelow.
It will, of course, be appreciated that the 4D code implemented by the encoder of FIG. 8 is merely illustrative. Another code that can be used advantageously to realize encoder 112 is a 2D code in which the trellis code is a standard rate1/2,64state convolutional code, i.e., the input is one bit per 2D signaling interval and the output is two bits. The latter identify one of the four subsets of the 2D constellation of FIG. 4, with the output values 00, 01, 10 and 11 respectivelyidentifying the subsets a, c, d, b. The RS encoder receives four bits per 2D signaling interval. In order to have the trellis distance dominate, as is desirable, it is necessary in this case to use a doubleerrorcorrecting RS code for thenontrellisencoded bits. Thus there will be four redundant words in each frame. If fourbit words are RSencoded, the maximum achievable frame length is 17. Such a code, if used, would, in many applications, be very bandwidth inefficient since fourout of every 17 words is a redundant word. It is thus desirable to aggregate two signalingintervalsworth of bits so as to be able to RS encode using eightbit words, which allows for frame lengths of, for example, 160 words instead of only 17.
The coding gain of this 2D approach is about 1.5 dB greater than that provided by the 4D approach described earlier, but at a cost of supporting a lower bit ratein fact, more than 0.5 bits per 2D signaling interval less. Thus, the performanceof the two approaches is comparable for the same bandwidth efficiency (bits per signaling interval).
It should be noted at this point that the advantages achieved by RS encoding the nontrellisencoded bits bring them an increase in the time required to decode in the receiver. In particular, RS decoder 230 cannot provide any output on lead 232until the entire frame of 160 ninebit words has been supplied to it by maximumlikelihood decoder 220. On an ongoing basis, then, the bits that are output by RS decoder 230 on lead 232 are delayed by 160 4D symbol intervals. Although a delay of thismagnitude may be problematic in some applications, in others it may not. In the T1 rate application mentioned above, for example, this delay is only about 1.0 ms, which poses no problem in that application. In those applications where a delay of 160 4Dsymbol intervals is deemed unacceptable, the frame length of the singleerrorcorrecting RS code can be reduced to, for example, 40 or even 30. The price one pays in this case is a reduction in bandwidth efficiency, i.e., an increase in the averagenumber of redundant word bits per 4D symbol and a concomitant decrease in the bit rate at which the data source can be clocked.
To this point, it has been assumed that no differential encoding is performed within the transmission system. In actuality, however, this is of crucial importance for many applications, including telephone voiceband data transmission. As isabout to be explained, however, the inclusion of differential encoding in a multilevel coded modulation scheme cannot always be carried out in the straightforward manner taught by the prior art.
To begin, it will be remembered that differential encoding is needed in voiceband data transmission and other systems in order to compenstate for the fact that socalled phase hits or other channel phenomena may cause the received signal points,as represented at the output of equalizer/demodulator 210, to be phaserotated versions of the signal points that were transmitted. Since the constellations that are typically used in practice exhibit phase symmetries, it would be possible for thereceiver circuitry to mistake a transmitted signal point for a different signal point of the constellation without any indication that an error was made. For example, in the 2D constellation of FIG. 4, a point rotated by any multiple of 90 degreesbecomes another point of the constellation (as opposed to falling within the "spaces" between points). The constellation is thus said to have 90degree phase symmetry. Similarly, a constellation which exhibits this property only upon a 180degreerotation is said to have 180degree phase symmetry. In order to compensate for such rotation, it is well known to use socalled differential encoding in order to represent one or more of the data bits to be transmitted not by particular symbols, but bythe phase difference between two successively transmitted symbols.
In order for differential encoding to be implemented in a system which uses trelliscoded modulation, a particular criterion must be met. That criterion is that the selected trellis code must exhibit the property that a valid sequence ofsubsets, after rotation by an amount corresponding to a phase symmetry of the constellation, e.g., 90 degrees, becomes another valid sequence of subsets. (As noted earlier, a "valid" sequence of subsets is one that is allowed by the trellis code toactually occur.) Moreover, in the design of the differential encoder, one must consider the effects that different partitionings may have on the rotation of a subset. There are, in fact, three possible cases, referred to herein as "case 1,""case 2" and"case 3."
In case 1, the symbols of a subset of the constellation always become symbols of a different subset after rotation by an amount corresponding to any phase symmetry of the constellation. For example, in the 2D example discussed above, uponrotation by 90, 180 and 270 degrees, the symbols of a subset a become symbols of subsets c, b, and d, respectively.
In case 2, the symbols of a subset of the constellation always become symbols of the same subset after rotation by an amount corresponding to any phase symmetry of the constellation.
Case 3 is a combination of cases 1 and 2. That is, the symbols of a subset of the constellation become a) symbols of a different subset after rotation by amounts corresponding to at least one phase symmetry of the constellation, and b) symbolsof the same subset after rotation by amounts corresponding to at least one other phase symmetry of the constellation. Thus in the abovedescribed 4D code, subset S0 becomes a) subset S4 for 90 or 270degree rotations, and b) remains what it was upon a180degree rotation.
Consider, now, how these requirements affect the implementation of a multilevel code embodying the principles of the invention.
If the symmetries and partitioning of the constellation are such that case 1 obtains, it is appropriate to adopt a differential encoding approach such as used in the prior art. Specifically, one differentially encodes one or more of thetrellisencoded bits, but not any of the nontrellisencoded bits. FIG. 9 shows an embodiment of encoder 11 implementing such an arrangement. The nontrellisencoded bits are encoded only by a RS encoder 914, while the trellisencoded bits aredifferentially encoded by differential encoder 907 before being trellisencoded by trellis encoder 912. As is wellknown by those skilled in the art, a differential encoder typically operates on a subsettypically one or two)of the bits that areapplied in parallel to it, with the other bits simply being passed through the differential encoder unchanged.
A complementary decoding structure (not shown) would be used to implement decoder 22 in the receiver.
If the symmetries and partitioning of the constellation are such that case 2 obtains, it is again appropriate to adopt a differential encoding approach such as used in the prior art. Here one differentially encodes one or more of thenontrellisencoded bits, but not any of the trellisencoded bits. FIG. 10 shows an embodiment of encoder 11 implementing such an arrangement. The trellisencoded bits are encoded only by trellis encoder 1012, while the nontrellisencoded bits aredifferentially encoded by differential encoder 1007 after being encoded by RS encoder 1014. (Again, complementary decoding structure (not shown) would be used to implement decoder 22 in the receiver.) It may also be noted in passing that the way inwhich the differential decoder works means that the error correction capability of the RS code will have to be increased in this case in order to achieve the same performance as would be achieved if the phaserotation issue and the differential decoderwere not there.
Case 3 requires that both trellisencoded and nontrellisencoded bits be differentially encoded. This presents a significant problema problem that may be solved in either of two ways, as are respectively taught in two copending U.S. patentapplications (cited below) filed by me. The problem itself may be understood as follows:
As exemplified by FIG. 10, it is desirable, in general, that if any of the RSencoded bits are to be differentially encoded, that encoding should be performed after the RS encoding in the transmitter. Complementarily, the differential decodingshould be performed in the receiver before the RS decoding. The reason for this is that a conventional RS decoder is not, in general, capable of carrying out its function properly if the nontrellisencoded bits have been changed as the result of phaserotations. By performing the differential decoding in the receiver prior to the RS decoding, then, it is guaranteed that there will be no phaserotation effects in the RS decoder input bits (assuming an appropriate choice for the trellis encoder).
Although this approach will, indeed, be effective if only nontrellisencoded bits are differentially encodedwhich, again, is the situation shown in FIG. 10, corresponding to case 2I have realized that there is a subtle, but very important,problem whenever the bits to be differentially encoded include not only nontrellisencoded bits, but also trellisencoded bits, i.e., case 3. The problem arises from the fact that those bits must be processed interdependently in both the differentialencoder and the differential decoder. A structure of encoder 11 that one might think of using for this case is shown in FIG. 11, wherein the RSencoded bits generated by RS encoder 1114 are differentially encoded interdependently with thetrellisencoded bits by differential encoder 1117, the resulting differentially encoded trellisencoded bits thereupon being extended to trellis encoder 1112. The complementary structure that would be used for decoder 22 is shown in FIG. 14 ascomprising maximumlikelihood decoder 1420, differential decoder 1407 and RS decoder 1430.
The encoder/decoder combination of FIGS. 11 and 14 will, indeed, be effective as regards the compensation for phase rotations. What I have appreciated, however, is that with this interdependent processing, errors made by the maximumlikelihooddecoder in the nontrellisencoded bits before they are processed by the RS decoder will cause errors in the trellisencoded bits at the output of the differential decoder. Thus the errorrate performance of the nontrellisencoded bits output on lead1422 of maximumlikelihood decoder 1420, i.e., at a point prior to their being RS decoded by RS decoder 1430, will determine the errorrate performance of the trellisencoded bits which, in turn, determines the overall errorrate performance (codinggain). Remember that the reason that the RS encoding was included in the overall coding scheme was to raise the errorrate performance of the nontrellisencoded bits to a level that is greater than that for the trellisencoded bits so that the lattercan dominate the overall errorrate performance. Now, however, the errorrate performance of the trellisencoded bits has been brought down to the level of performance for the nontrellisencoded bits that obtained in the first instance, i.e., withoutusing the RS code. The fact that the errorrate performance of the nontrellisencoded bits is thereafter improved by virtue of their being processed by RS decoder 1430 is of no avail. Thus, no improvement in overall errorrate performance is realized.
In accordance with the invention taught in my copending U.S. patent application, Ser. No. 07/869,983, entitled "Rotationally Invariant Coding," filed of even date herewith and assigned to the same assignee and hereby incorporated by reference,the order of differential encoding and RS encoding in the transmitter and differential decoding and RS decoding in the receiver are reversed from the approaches of FIGS. 11 and 14, respectively, as would be followed by the prior art. Thus, theaforementioned problemsthe loss of bandwidth efficiency due to the need to increase the error correction capability of the RS code and, more importantly, the loss of the advantage provided by using the RS code to encode the nontrellisencodedbitsare obviated.
In particular, FIG. 12 shows an embodiment of encoder 11 implementing this approach. The input bits are first applied to differential encoder 1207 and are thereafter RS and trellisencoded by RS encoder 1214 and trellis encoder 1212,respectively. The complementary structure that is used to implement decoder 22 in this case is shown in FIG. 15 as comprising maximumlikelihood decoder 1520, RS decoder 1530 and differential decoder 1507.
Now, of course, the bits applied to RS decoder 1530 on lead 1522 will be subject to changes due to phase rotation, as noted earlier. Advantageously, however, I have discovered a technique, also taught in the aforementioned patent application,which provides an RS decoder with the capability of dealing with, i.e., properly operating in the presence of, those changes. That RS decoder is capable of dealing with bit changes of a type wherein bits in corresponding bit positions of each RS wordare complemented from their original values. In order to take advantage of that capability here, the overall coded modulation scheme is designed so that any phase rotation which changes the values of the bits that are input to RS decoder 1530 causesthose changes to, indeed, be such a complementation.
In particular, the coded modulation scheme is designed in such a way that a 180degree constellation phase rotation results in a change to each ninebit word at the input to RS decoder 1530 which is of the type just mentioned. More specifically,it causes a particular one bit of each ninebit word to be complemented. Thus, the rotation has no effect on the efficacious operation of RS decoder 1530 inasmuch as, again, that decoder uses the technique taught in my abovecited copending U.S. patent application, which allows the RS decoder to operate properly even in the presence of such changes. Moreover, the overall coding scheme is designed in such a way as to guarantee that only 180degree rotations can, in fact, occur. In thisembodiment, that result is accomplished by doing two things. The first is to use a trellis code which is only 180degree rotationally invariant. By this it is meant that, upon the transmission of a sequence of symbols taken from a valid sequence ofsubsets, and upon the subsequent rotation of those symbols by 180 degrees, the resulting sequence of symbols is a sequence taken from another valid sequence of subsets (which, in this case, is, in fact, the same sequence of subsets). The trellis codeimplemented by the circuitry of FIG. 8 is, in fact, such a code. Since the code is only 180degree rotationally invariant and not, for example, 90degree rotationally invariant, a rotation by 90 or 270 degrees will not have the above property. Thussuch a rotation will have a dramatic effect on the operation of maximumlikelihood decoder 1520 and the occurrence of such a rotation can be quickly and readily detected. The second thing done is to, in fact, look for such a rotation. Upon detection ofsame, maximumlikelihood decoder 1520 provides a control signal on lead 212 to equalizer/demodulator 210. The latter, responsive to the control signal, rotates its output by 90 degrees, thereby providing, as indicated above, an overall rotation which iseither 0 degrees (i.e., no rotation) or 180 degrees.
There are many ways of detecting the occurrence of a rotation. One particularly advantageous way relies on my observation that, within the maximumlikelihood decoder, it will be case for at least certain trellis codesincluding the trellis coderealized by the circuitry of FIG. 8that when there has been no rotation or a rotation with respect to which the code is invariant, the minimum path metric computed for a present symbol interval is more likely than not to be equal to the sum of a) theminimum path metric computed for the previous symbol interval with b) the minimum branch metric computed for the present symbol interval. (Even in a very noisy environment, in which there may be many symbol errors (e.g., greater than 10%), this equalitycriterion will be met at least about 60% of the time; and as the symbol error rate decreases, this percentage increases to about 90%.) On the other hand, when there is a rotation with respect to which the code is not invariant, then this equalitycriterion is not met about 50% of the time. Thus by monitoring this equality criterion, one can easily determine the presence of such a rotation.
(The 4D, 16state trellis encoder suggested above for use in scheme II has 90degree symmetry. Thus if one were to want to use that code in place of the 4D, 64state code implemented by the circuitry of FIG. 8, that code would have to bemodified slightly from the version which is disclosed in my aforementioned 1987 IEEE paper. The modification would simply be to exchange the roles of the two input bits in their generation of the third trellisencoder output bit.)
Unlike the earlierassumed situation of an application in which no phase rotation occurs, the bit patterns of the ninebit words on leads 115 are not assigned to the symbols of the 4D subsets arbitrarily. Rather, in this example, two criteriamust be met. The first criterion is that a particular one bit provided at the output of RS encoder 1214 on lead 115 is used to select one of the two aforementioned 4D types in the identified subset. Thus, for example, looking again at FIG. 5, the valueof 0 for this bit would select the first 4D type for the identified subset and the value of 1 for this bit would select the second 4D type for that subset.
The other eight bits on lead 115 are divided into two fourbit groups. Each group selects a particular 2D signal point from a respective one of the 2D subsets that make up the identified 4D type. The second of the aforementioned criteria isthat each set of four 2D signal points that are obtained from one another through 90degree phase rotations are assigned the same bit patterns of the fourbit group. Thus looking at FIG. 4, it will be seen that the four 2D signal points assigned the bitpattern 0001 are 90degree rotations of each other and the four 2D signal points assigned the bit pattern 0101 are 90degree rotations of each other.
Overall, then, consider the following example: Assume that the 12bit pattern on leads 115 and 113 is 000101010001, reading from top to bottom. For pedagogic convenience, we can represent this pattern in four groups thusly: 0001 0101 0 001. From all that has been discussed above, it will be appreciated that the last three bits, 001, identify subset S1 as the subset from which the 4D symbol will be selected. The fourthtolast bit, 0, identifies that it is the first, as opposed to thesecond, 4D type of the identified subset from which the symbol is to be selected. In this case, then, it is the 4D type(a,c). Thus the four last bits of the pattern tell us the two 2D signal points that comprise the 4D symbol are to be selected from2D subsets a and c, respectively. In particular, the first of these 2D points is that point from subset a which is identified by the first four bits of the 12bit pattern i.e., the point from subset a assigned to the bit pattern 0001. Similarly, thesecond of these 2D points is the point from subset c which is identified by the second four bits of the 12bit pattern, i.e., the point from subset c assigned to the bit pattern 0101.
Consider, now, the consequences of a 180degree rotation of each of the two constituent 2D signal points of this 4D symbol. The first signal point, from subset a, will rotate to become the signal point in subset b having the same assigned 4bitpattern, 0001. Similarly, the second signal point, from subset c, will rotate to become the signal point in subset d having the same assigned 4bit pattern, 0101. This new 4D symbol is in a different 4D type (b,d), but that 4D type is the second 4Dtype of the same subset S1. Therefore, upon such a rotation, maximumlikelihood decoder 220 will output the 12bit pattern 0001 0101 1 001 (assuming a correct decision is made).
As desired, then, the only effect of the 180degree rotation is to complement the ninth bit of the pattern. Indeed, it can be shown that this occurs upon the rotation of any 4D symbol.
An alternative approach to the introduction of differential encoding into a multilevel coded modulation scheme is described in my copending U.S. patent application, Ser. No. 07/869,991 entitled, "Overlapped Multilevel Codes" filed of even dateherewith and assigned to the same assignee and hereby incorporated by reference. That approach is illustrated in FIGS. 13 and 16, showing the encoder 11 and decoder 22 that would be used in that case. Here, differential encoder 1307 follows RS encoder1314 in the transmitter and differential decoder 1607 precedes RS decoder 1630 in the receiver. This approach is similar to that used for the encoder and decoder in FIGS. 11 and 14, respectively. Moreover, the consequences of such an architecture arethe same in both situations in that, as previously noted, rotations are not manifest at the input to RS decoder 1630, which is desirable. On the other hand, there still remains the need to obviate the abovediscussed problem wherein the errorrateperformance of the trellisencoded bits is brought down to the level of performance for the nontrellisencoded, notyetReedSolomon decoded bits.
In accordance with the teachings of this second of my copending applications, this problem is overcome by processing the bits in such a way that differentially encoded bits that are to be trellisencoded are derived from the output of the RSencoder. Experimental tests have confirmed that the errorrate performance (coding gain) for the overall code is, as a result, restored to the original level provided by the trellis code. Thus looking specifically at FIG. 13, it is seen that one ormore of the bits on lead 108 is applied to RS encoder 1314 (on lead 1321) along with the nontrellisencoded bits on lead 109. We have here case 3 discussed above, in which the bits to be differentially encoded are both trellis and nontrellisencodedbits. Thus the bit(s) on lead 1321, after being RSencoded by encoder 1314, are applied to differential encoder 1307 along with one or more of the other RS encoder output bits. The differentially encoded trellisencoded bits are thereupon provided onlead 1310 to trellis encoder 1312 along with the other trellis encoded bits on lead 1311.
Complementary processing is carried out in the receiver. Thus, as shown in FIG. 16, the nontrellisencoded bits that are output by maximumlikelihood decoder 1620 on lead 1621 are applied to differential decoder 1607. Of the trellisencodedbits provided by maximumlikelihood decoder 1620 on lead 1622, one or more are provided to differential decoder 1607 while the other(s) are supplied directly onto lead 221. The output bits of differential decoder 1607 on lead 1608 are RSdecoded by RSdecoder 1630. One or more output bits of the latter, corresponding to the bit(s) on lead 1321, are supplied to lead 221. The remainder are supplied to lead 232.
The trellis code that is used in this case is illustratively the 90degree rotationally invariant code implemented by the trellis encoder of FIG. 17.
The coded modulation schemes disclosed herein advantageously provide at least a measure of immunity to impulse noise. Specifically, the corruption of a given symbol by impulse noise occurring within a particular RS frame can be correctedforassuming no other errors within that frame from impulse noise or any other sourcein that a) the trellis code is powerful enough to allow for the detection of the correct subsetand thus the correct trellisencoded bitsin the receiver and b) theRS code can detect and correct any error made by the maximumlikelihood decoder in the detection of the transmitted symbol in that subsetand thus can correct nontrellisencoded bits. Advantageously, impulse noise that may extend over two or morecontiguous symbols can also be dealt with by employing a known type of interleaver which is used to separate contiguous signal points as they traverse the channel, thereby distributing the effect of any particular impulse noise eventupondeinterleaving in the receiverinto various different frames. This implies the joint selection of the interleaver parameters and the RS frame length in order to meet any overall decoding delay requirements of the system consistent with desiredbandwidth efficiency objectives.
The foregoing merely illustrates the principles of the present invention. For example, although particular bit rates, codes, constellations and partitionings are shown herein and particular parameter values (e.g., for N, k, etc.) are used, theseare all merely illustrative. For example, various different source bit rates can be accommodated via the use of a) RS words of different size (number of bits) in combination with b) various different constellation sizes, without, in general, the need tochange, for example, the encoding/decoding algorithms of the RS and trellis codes nor the RS frame length. Moreover, it may be noted that a 2Ndimensional constellation may be comprised of constituent constellations of any lower order, e.g., a 4Dconstellation may be comprised of four 1D constellations. Also, certain 2Ndimensional constellations may be such as to not be resolvable into constituent, lowerdimensional constellations. Moreover, although the invention is illustrated herein in thecontext of a passband transmission arrangement, it can also be used in baseband arrangements.
Moreover, although particular applications in which the coded modulation scheme of the present invention are disclosed, the invention is usable in other applications as well.
Additionally, it may be noted that, although the invention is illustrated herein as being implemented with discrete functional building blocks, e.g., encoders, mappers, etc., the functions of any one or more of those building blocks can becarried out using one or more appropriately programmed processors, digital signal processing (DSP) chips, etc. Thus although each of the various "means" recited in the claims hereof may correspond, in some embodiments, to specific circuitry which isspecifically designed to perform the function of just that means, it will be appreciated that such "means" may alternatively correspond, in other embodiments, to the combination of processorbased circuitry with stored program instructions which causethat circuitry to perform the function in question.
It will thus be appreciated that those skilled in the art will be able to devise numerous and various alternative arrangements which, although not explicitly shown or described herein, embody the principles of the invention and are within itsspirit and scope.
* * * * * 


