Modem and method for 8 dimensional trellis code modulation

• US 4,873,701 A
• Filed: 09/16/1987
• Issued: 10/10/1989
• Est. Priority Date: 09/16/1987
• Status: Expired due to Fees

• Current Assignee: Access Beyond, Inc. (Hayes Microcomputer Products, Inc.)
• Original Assignee: Penril Corporation
• Inventors: Tretter, Steven A.
• Primary Examiner(s): Griffin, Robert L.
• Assistant Examiner(s): Huseman, Marianne
• Application Number:
  US07/097,448
• Time in Patent Office: 755 Days
• Field of Search: 375/25, 375/26, 375/27, 375/37, 375/39, 375/38, 371/43
• US Class Current: 375/245
• CPC Class Codes: H04L 27/3427 in which the constellation is the n - fold Cartesian product of a single underlying two-dimensional constellation

Abstract

A modem and method for modulation-demodulation of a received analog signal. The modem receives sixteen bits at four bits per baud. The 8 D Block Encoder encodes nine of the sixteen bits into 12 Z-bits which are used to specify a sequence of four 2 D constellation points. These 2 D constellation points correspond to a sequence of four 2 D subsets of a 8 D subtype selected. The differential encoder differentially encodes two of the sixteen bits to make the code transparent to a 90 degree rotation. The rate 3/4 convolutional encoder generates a check bit and a bit converter converts the check bit, the differential encoded bits and the remaining five bits into 8 Z-bits. The result is an 8 D trellis with a 20-point 2 D constellation.

Claims

1. A modem for modulation-demodulation of received analog signals including a demodulator comprising:

receiving means for receiving analog signals comprised of four 2D points;

means for storing a plurality of ideal 2D points comprising a twenty point 2D signal constellation, said twenty point 2D signal constellation comprised of four 2D subsets of points;

slicing means connected to said receiving means including a set of rules for finding the best ideal 2D point in each of said four 2D subsets to each of said received four 2D points by locating the ideal 2D point closest in Euclidean distance;

first combining means connected to said slicing means for combining into pairs each of said ideal 2D points to form 4D points in each of eight 4D subsets and selecting one of said pairs of ideal 2D points in each of said 4D subsets to represent the best 4D point in each of said 4D subsets;

second combining means connected to said first combining means for combining into pairs each of said best eight 4D points to form sixteen 8D points and comparing said pairs of four 4D points with a set of allowed points in each of sixteen 8D subsets and selecting one of said 8D points to represent the best 8D point in each of the sixteen 8D subsets;

decoding means connected to said second combining means for extending a decoder trellis for implementing a Viterbi algorithm and generating as output 20 Z-bits corresponding to the best 8D point;

converting means connected to said decoding means for converting said 20 Z-bits into a stream of 16 data bits; and

sending means connected to said converting means for sending said data bits to a data sink.

2. The modem for modulation-demodulation of claim 1 wherein each of said four 2D points comprises a pair of x and y coordinates representing said analog signal.

3. The modem of claim 1 wherein said set of rules of said slicing means are such that each of said received 2D points is rotated a multiple of 90 degrees to find the best ideal 2D point in each of said four 2D subsets.

4. A modem for modulation-demodulation of a received analog signal, said modem comprising:

means for receiving blocks of 16 successive bits from a data source at four bits per baud;

means for designating 9 bits of said 16 successive bits for determining a specific 8D point of a plurality of 8D points forming an 8D subtype;

mapping means for mapping the 9 bits into 12 Z-bits such that successive groups of three Z-bits specify a sequence of four 2D points from within a particular 2D subset of points comprising a 20 point 2D signal constellation, said 20 point signal constellation being formed from a 16 point signal constellation and comprising all of said points of said 16 point signal constellation and additional points not part of said 16 point signal constellation; and

means for assigning a point not part of said 16 point constellation to one of said sequence of four 2D points if a specific one of the three Z-bits equals logic one, and assigning a point part of said 16 point constellation to one of said sequence of four 2D points if a specific one of the three Z-bits equals logic zero.

5. The modem of claim 4, and further comprising:

a convolutional encoder means;

means for driving said convolutional encoder means so that a check bit is generated from the first three bits of the received 16 bits; and

further mapping means for mapping said 16 bits and said check bits into a 2¹⁷ point 8D signal constellation where the 8D points consist of a sequence of four 2D points, said 2D points being selected from the 20 point 2D constellation so that the 8D points are formed in order that at most one point not part of said 16 point signal constellation is transmitted in the sequence of four 2D points and whereby either four points part of said 16 point signal constellation, or one point not part of said 16 point constellation and three points part of said 16 point constellation are transmitted per block of said 16 successive bits.

6. A method of decoding an analog signal comprised of 2D symbols, said method comprising the steps of:

(a) quantizing each received 2D symbol to the closest symbol in each of four 2D subsets A, B, C, or D, said four 2D subsets comprising a 2D signal constellation;

(b) storing Z-bits representing each of the four subsets together with the corresponding smallest squared Euclidean distance between the received and quantized symbols;

(c) performing steps of (a) and (b) for a block of four 2D symbols that make up an 8D symbol;

(d) rotating the received 2D symbols by 90, 180, and 270 degrees counterclockwise, respectively;

(e) combining pairs of 2D quantized symbols into two 4D quantized symbols and comparing each 4D symbol with an ideal 4D symbol for selecting the 4D symbol with the smallest squared Euclidean distance from said ideal 4D symbol;

(f) storing the 4D symbol with the smallest squared Euclidean distance together with the Z-bits of the corresponding pair of 2D subsets;

(g) combining the 4D quantized symbols into 8D symbols and comparing each 8D symbol with an ideal 8D symbol for selecting the 8D symbol with the smallest squared Euclidean distance from said ideal 8D symbol;

(h) storing the smallest distance of said 8D symbol long with the Z-bits of the corresponding 2D subsets; and

(i) performing a Viterbi algorithm to update the best trellis path to each of 64 possible encoder states corresponding to each quantized 8D symbol.

7. A modem for modulation-demodulation of received analog signals including a demodulator comprising:

quantizing means for performing quantizing decisions on each received 2D symbol to the closest constellation point in each of four 2D subsets A, D, C, or D;

storing means for storing Z-bits representing each of the four subsets with the corresponding squared Euclidean distance between the received and quantized points;

means for rotating the received 2D point by 90, 180, and 270 degrees counterclockwise, respectively;

combining means for combining pairs of 20 quantizing decisions into two 4D quantizing decisions by comparing a 4D subset containing pairs of 2D points and selecting the point within each 4D subset having the smallest squared Euclidean distance from an ideal 4D point; and

second storing means for storing the 4D point with smallest squared Euclidean distance together with the Z-bits for the corresponding pair of 2D subsets.

8. The modem of claim 7 further comprising:

second combining means for combining the 4D quantizing decision into 8D quantizing decisions and comparing the 8D quantizing decisions with an ideal 8D point and selecting the one with the smallest squared Euclidean distance from said ideal 8D point;

third storing means for storing the smallest distance along with the corresponding Z-bits; and

means for performing a Viterbi algorithm to update the best trellis path through each of 64 possible encoder states, for generating as output 20 bits.

9. A method of encoding received data comprising the steps of:

receiving blocks of 16 successive data bits from a data source at four bits per baud;

driving a convolutional encoder means so that a check bit is generated from the first three data bits of the received 16 bits;

differentially encoding the sixth and seventh bits of the received 16 bits to make the code transparent to 90 degree rotations;

designating the last 9 bits of said 16 successive data bits for encoding a specific 8D point within an 8D subtype;

mapping said last 9 bits into 12 Z-bits where every three Z-bits specifies a sequence of four 2D constellation points corresponding to a sequence of four 2D subsets of an 8D subtype selected;

assigning a point outside a conventional 2D 16 point signal constellation to one of said four 2D subsets if and only if a specific one of said three Z-bits equals logic one;

mapping said 16 bits and said check bit into a 2¹⁷ point 8D constellation where the 8D points consist of a sequence of four 2D points, each selected from a 20-point 2D signal constellation which includes all of said points of said conventional 2D 16 point signal constellation so that the 8D points are selected in order that at most one point outside said conventional 16 point signal constellation is transmitted in the sequence of four 2D points; and

generating from said check bit, said differentially encoded bits, and the first 5 bits of said 16 bits, eight additional Z-bits for specifying a sequence of four 2D subsets so that each pair of Z-bits comprising said eight Z-bits is assigned to a 2D subset which when rotated by 90°

becomes the 2D subset below assigned 2D subset.

10. A modem for modulation and demodulation including a modulator for accepting a stream of sixteen consecutive data bits at four bits per baud representing a portion of an analog signal and generating an 8D signal constellation from a twenty point 2D signal constellation comprised of four 2D subsets of 2D points, said modulator comprising:

a convolutional encoder which accepts as input the first three bits of said 16 bits data stream and generates as output the same first three data bits plus one additional bit designed a check bit;

a differential encoder which accepts as input the sixth and seventh bits of said 16 bit data stream and generates as output two new bits;

a bit converter which accepts as input the first five bits of said 16 bit data stream, said check bit, and said differential encoder output bits and generates as output 8 Z-bits comprised of four pairs of Z-bits;

a block encoder which accepts as input the remaining 9 bits of said 16 bit data stream and generates as output 12 Z-bits comprised of four groups of three Z-bits; and

wherein said four pairs of output Z-bits of said bit converter represents a sequence of four 2D subsets of 2D points from said 20 point 2D constellation for defining an 8D subtype contained within an 8D subset, and said four groups of three Z-bits generated by said block decoder define 2D points within said 2D subsets of said 20 point 2D signal constellation for defining an 8D point within said 8D subtype of an 8D subset.

11. The modem of claim 10 and further including a quadrature amplitude modulator for modulating said 8D point of said 8D subtype for transmission over a transmission media to a receiver.

12. The modem of claim 18 wherein said differential encoder causes the relative position of points in said four 2D subsets of said 20 point 2D signal constellation to be unaffected by a 90 degrees phase rotation.

13. A method for encoding data from a 16 bit data stream to generate a 20 point 2D signal constellation comprised of four 2D subsets of 2D points for constructing an 8D signal constellation from a sequence of 2D points selected from said 20 point signal constellation, said method comprising the steps of:

applying to a convolutional encoder the first three bits of said 16 bit data stream for generating one check bit;

applying the sixth and seventh bits of said data stream to a differential encoder for generating two new output bits;

applying the first five bits of said data stream;

said check bit, and said output bits from said differential encoder to a bit converter for generating as output 8 Z-bits comprised of four pairs of Z-bits;

applying the remaining nine bits of said data stream to a block encoder for generating as output 12 Z-bits comprised of four groups of 3 Z-bits; and

wherein said four pairs of output Z-bits of said bit converter represents a sequence of four 2D subsets of said 20 point constellation for defining an 8D subtype contained within an 8D subset, and said four groups of 3-bits generated by said block decoder define 2D points within said 2D subsets of said 20 point signal constellation for defining an 8D point within said 8D subtype of an 8D subset.