Apparatus and method for communicating digital data using trellis coded QAM with punctured convolutional codes

• US 5,408,502 A
• Filed: 07/13/1992
• Issued: 04/18/1995
• Est. Priority Date: 07/13/1992
• Status: Expired due to Term

• Current Assignee: VIZIO, Inc.
• Original Assignee: General Instrument Corporation (CommScope Holding Company, Inc.)
• Inventors: How, Stephen K.
• Primary Examiner(s): Chin, Stephen
• Assistant Examiner(s): Kobayashi, Duane
• Application Number:
  US07/912,542
• Time in Patent Office: 1,009 Days
• Field of Search: 371/43, 375/94, 375/39, 375/38
• US Class Current: 375/340
• CPC Class Codes: H03M 13/25 Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM] modulation codes H03M13/31
• CPC Class Codes: H03M 13/256 with trellis coding, e.g. with convolutional codes and TCM
• CPC Class Codes: H03M 13/3961 Arrangements of methods for branch or transition metric calculation
• CPC Class Codes: H03M 13/41 using the Viterbi algorithm or Viterbi processors
• CPC Class Codes: H03M 13/6362 by puncturing
• CPC Class Codes: H04L 1/0054 Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms
• CPC Class Codes: H04L 1/0068 by puncturing
• CPC Class Codes: H04L 27/3433 using an underlying square constellation

Abstract

Digital data is communicated using trellis coded QAM. Symbols are coded for transmission using a rate 1/2 convolutional encoder punctured to rate 2/3. The coded symbols are transmitted for receipt at a receiver. At the receiver, two sets of branch metrics are computed for each received symbol. The received symbols are decoded by using the branch metrics to effect two passes through a modified rate 1/2 Viterbi decoder for each symbol.

Claims

1. A method for communicating digital data using trellis coded QAM comprising the steps of:

coding symbols for transmission using a rate 1/2 convolutional encoder punctured to rate 2/3;

transmitting the coded symbols;

receiving the transmitted coded symbols at a receiver;

computing two sets of branch metrics for each received symbol; and

decoding the received symbols by using said branch metrics to effect two passes through a rate 1/2 Viterbi decoder for each symbol.

2. A method in accordance with claim 1 wherein said symbols are coded on the basis of groups forming an 8-way partition of a QAM constellation.

3. A method in accordance with claim 2 comprising the further step of identifying an uncoded bit from each symbol by the position of a transmitted constellation point within a group.

4. A method in accordance with claim 2 wherein said symbols are coded on the basis of groups of different two-point subsets of a 16 QAM constellation and the two points in each group are separated by a distance of 2√

2Δ

₀, where Δ

₀ is the spacing between adjacent points in said 16 QAM constellation.

5. A method in accordance with claim 1 wherein:

said received symbols define received points that correspond to but may be offset from transmitted QAM constellation points due to transmission errors;

said first set of branch metrics indicates the distances between a received point and the closest actual QAM constellation point in each of a first plurality of predetermined subsets of said constellation points; and

said second set of branch metrics indicates the distances between said received point and the closest actual QAM constellation point in each of a second plurality of predetermined subsets of said constellation points.

6. A method in accordance with claim 5 wherein:

said symbols are coded on the basis of eight different groups of constellation points that form an 8-way partition of a QAM constellation;

each group is labeled with a 3-bit binary number on the basis of the distances between points of the groups;

a first group A is identifiable by a 3-bit binary number that is bitwise complementary to that of a second group H whose points are separated by 2Δ

₀ from points in group A;

a third group B whose points are separated by √

2Δ

₀ from points in group A is identifiable by a 3-bit label which is the bit-wise exclusive-or of the label of A with 001;

a fourth group G whose points are separated by 2Δ

₀ from points in group B is identifiable by a 3-bit binary number that is bitwise complementary to the label of B;

a fifth group C is identifiable by a 3-bit binary number that is the bitwise exclusive-or of the label of A with 010;

a sixth group F whose points are separated by 2Δ

₀ from points in group C is identifiable by a 3-bit binary number that is bitwise complementary to the label of C;

a seventh group D whose points are separated by √

2Δ

₀ from points in group C is identifiable by a 3-bit label which is the bit-wise exlcusive-or of the label of C with 001;

an eighth group E whose points are separated by 2Δ

₀ from points in group D is identifiable by a 3-bit binary number that is bitwise complementary to the label of D;

wherein Δ

₀ is the minimum distance between points in said QAM constellation; and

said first plurality of predetermined subsets comprise the unions of groups A∪

B, H∪

G, C∪

D, and F∪

E; and

said second plurality of predetermined subsets comprise the unions of groups A∪

G, C∪

E, H∪

B, and F∪

D.

7. A method for decoding received convolutionally encoded symbols comprising the steps of:

computing two sets of branch metrics for each received symbol; and

decoding the received symbols by using said branch metrics to effect two passes through a rate 1/2 Viterbi decoder for each symbol.

8. A method in accordance with claim 7 wherein said received symbols are coded on the basis of groups forming an 8-way partition of a QAM constellation.

9. A method in accordance with claim 8 comprising the further step of identifying an uncoded bit from each received symbol by determining the position of a transmitted constellation point within a group.

10. A method in accordance with claim 7 wherein:

said received symbols define received points that correspond to but may be offset from transmitted QAM constellation points due to transmission errors;

said first set of branch metrics indicates the distances between a received point and the closest actual QAM constellation point in each of a first plurality of predetermined subsets of said constellation points; and

said second set of branch metrics indicates the distances between said received point and the closest actual QAM constellation point in each of a second plurality of predetermined subsets of said constellation points.

11. A method in accordance with claim 10 wherein:

said symbols are coded on the basis of eight different groups of constellation points that form an 8-way partition of a QAM constellation partition;

each group is labeled with a 3-bit binary number on the basis of the distances between points of the groups;

a first group A is identifiable by a 3-bit binary number that is bitwise complementary to that of a second group H whose points are separated by 2Δ

₀ from points in group A;

a third group B whose points are separated by √

2Δ

₀ from points in group A is identifiable by a 3-bit label which is the bit-wise exclusive-or of the label of A with 001;

a fourth group G whose points are separated by 2Δ

₀ from points in group B is identifiable by a 3-bit binary number that is bitwise complementary to the label of B;

a fifth group C is identifiable by a 3-bit binary number that is the bitwise exclusive-or of the label of A with 010;

a sixth group F whose points are separated by 2Δ

₀ from points in group C is identifiable by a 3-bit binary number that is bitwise complementary to the label of C;

a seventh group D whose points are separated by √

2Δ

₀ from points in group C is identifiable by a 3-bit label which is the bit-wise exlcusive-or of the label of C with 001;

an eighth group E whose points are separated by 2Δ

₀ from points in group D is identifiable by a 3-bit binary number that is bitwise complementary to the label of D;

wherein Δ

₀ is the minimum distance between points in said QAM constellation; and

said first plurality of predetermined subsets comprise the unions of groups A∪

B, H∪

G, C∪

D, and F∪

E; and

said second plurality of predetermined subsets comprise the unions of groups A∪

G, C∪

E, H∪

B, and F∪

D.

12. Apparatus for encoding digital QAM data for communication to a receiver comprising:

means for coding symbols representative of QAM constellation points for transmission using a rate 2/3 code provided by a rate 1/2 convolutional encoder having a trellis with alternating branches punctured to form said rate 2/3 code; and

means for transmitting the coded symbols provided by said coding means;

wherein said symbols are coded on the basis of groups forming an 8-way partition of a QAM constellation and each require the computation of two sets of branch metrics and two passes through said trellis for decoding.

13. Apparatus for decoding the symbols transmitted from the encoder of claim 12 comprising:

means for receiving the transmitted coded symbols;

means operatively associated with said receiving means for computing two sets of branch metrics for each received symbol; and

means for decoding the received symbols by using said branch metrics to effect two passes through a rate 1/2 Viterbi decoder for each symbol.

14. Apparatus in accordance with claim 12 wherein:

an uncoded bit is communicated within each symbol by the position of a transmitted constellation point within a group.

15. Apparatus in accordance with claim 12 wherein said symbols are coded on the basis of groups of different two-point subsets of a 16 QAM constellation and the two points in each group are separated by a distance of 2√

2Δ

₀, where Δ

₀ is the spacing between adjacent points in said 16 QAM constellation.

16. Apparatus in accordance with claim 13 wherein:

said received symbols define received points that correspond to but may be offset from transmitted QAM constellation points due to transmission errors;

said first set of branch metrics indicates the distances between a received point and the closest actual QAM constellation point in each of a first plurality of predetermined subsets of said constellation points; and

said second set of branch metrics indicates the distances between said received point and the closest actual QAM constellation point in each of a second plurality of predetermined subsets of said constellation points.

17. Apparatus for decoding received convolutionally encoded symbols comprising:

means for computing two sets of branch metrics for each received symbol; and

means responsive to said branch metrics for decoding the received symbols by effecting a first pass through a rate 1/2 Viterbi decoder for each symbol in accordance with the first set of branch metrics for the symbol and a second pass through said decoder for each symbol in accordance with the second set of branch metrics for the symbol.

18. Apparatus in accordance with claim 17 wherein said received symbols are coded on the basis of groups forming an 8-way partition of a QAM constellation.

19. Apparatus in accordance with claim 18 wherein:

an uncoded bit is communicated within each received symbol by the position within a group of a transmitted constellation point represented by the symbol.

20. Apparatus in accordance with claim 17 wherein:

said received symbols define received points that correspond to but may be offset from transmitted QAM constellation points due to transmission errors;

said first set of branch metrics indicates the distances between a received point and the closest actual QAM constellation point in each of a first plurality of predetermined subsets of said constellation points; and

said second set of branch metrics indicates the distances between said received point and the closest actual QAM constellation point in each of a second plurality of predetermined subsets of said constellation points.

21. Apparatus in accordance with claim 20 wherein:

said symbols are coded on the basis of eight different groups of constellation points forming an 8-way partition of a QAM constellation;

each group is labeled with a 3-bit binary number on the basis of the distances between points of the groups;

a first group A is identifiable by a 3-bit binary number that is bitwise complementary to that of a second group H whose points are separated by 2Δ

₀ from points in group A;

a third group B whose points are separated by √

2Δ

₀ from points in group A is identifiable by a 3-bit label which is the bit-wise exclusive-or of the label of A with 001;

a fourth group G whose points are separated by 2Δ

₀ from points in group B is identifiable by a 3-bit binary number that is bitwise complementary to the label of B;

a fifth group C is identifiable by a 3-bit binary number that is the bitwise exclusive-or of the label of A with 010;

a sixth group F whose points are separated by 2Δ

₀ from points in group C is identifiable by a 3-bit binary number that is bitwise complementary to the label of C;

a seventh group D whose points are separated by √

2Δ

₀ from points in group C is identifiable by a 3-bit label which is the bit-wise exclusive-or of the label of C with 001;

an eighth group E whose points are separated by 2Δ

₀ from points in group D is identifiable by a 3-bit binary number that is bitwise complementary to the label of D;

wherein Δ

₀ is the minimum distance between points in said QAM constellation; and

said first plurality of predetermined subsets comprise the unions of groups A∪

B, H∪

G, C∪

D, and F∪

E; and

said second plurality of predetermined subsets comprise the unions of groups A∪

G, C∪

E, H∪

B, and F∪

D.