Device and method for achieving rotational invariance in a multi-level trellis coding system

Claim 3

The device of claim 1 wherein the signal points of the two-dimensional signal constellation lie on a rectangular grid.

Claim 4

The device of claim 1 wherein the unknown rotation of signal points is one of: 90°, 180° and 270°.

Claim 5

The device of claim 1, wherein the trellis code is a 4-dimensional trellis code.

Claim 6

The device of claim 4 wherein the 4-dimensional trellis code is a 16-state code.

Claim 7

The device of claim 1, wherein the parity bit is computed according to a nonlinear function of a plurality of second rotationally-significant label bits.

Claim 8

The device of claim 6 wherein the nonlinear function is a quadratic function of the plurality of the second rotationally-significant label bits.

Claim 9

The device of claim 1 wherein the parity bit is determined by the SPC means according to a formula of a form: P=A⊕Σ.sub.0≦i≦L-2 P1(i)⊕Σ.sub.0≦i≦L-1 B(i)P2(i) ⊕ΣΣ.sub.0≦i,j≦L-1 C(i,j) P2(i) P2(j), where A is a preselected binary constant, L is a frame length, i and j are integers, B(i) and C(i,j) are preselected binary constants, and P2(i), P2(j) represents a plurality of second rotationally-significant label bits and Pl(i) represents a plurality of first rotationally-significant label bits, where C(i,j) are chosen such that for any integer n, where 0≦n<L-1, P2(n) appears in the second-order terms an odd number of times, and B(i) are selected such that the total number of non-zero terms in the last two summations is even.

Claim 10

The device of claim 8 wherein C(i,j)=1 when i is odd and j=i-1, and B(i)-1 for even values of i.

Claim 11

The device of claim 8 wherein B(i)=1 for odd values of i, L is a multiple of 4.

Claim 12

The device of claim 1, further including a differential encoder, operably coupled to receive at least two data bits, for generating the p rotationally-significant bits.

Claim 13

The device of claim 11 wherein the SPC means is operably coupled to receive first and second sets of differentially encoded rotationally-significant label bits (P1, P2), and, at the end of the frame, the parity bit(s) is/are selected such that adjusted parity bit(s) is/are determined in accordance with a mod-2 sum that is equal to a binary value P, the parity generating unit comprising: (A) a running sum unit, operably coupled to receive the first (P1) and second (P2) sets of differentially encoded rotationally-significant label data bits, for determining a running sum, being a mod-2 sum of a form: Σ.sub.≦ i≦L-2 P1(i) where L is a frame length and i is an integer, (B) a quadratic function unit, operably coupled to receive the second differentially encoded rotationally-significant label bits, P2, for determining a quadratic function of the form: Σ.sub.0≦i≦L-1 B(i) P2(i⊕ΣΣ.sub.0≦i,j≦L-1 C(i,j)P2(i) P2(j) where B(i) are predetermined binary constants, C(i,j) are predetermined binary constants, i and j are integers, (C) an adjusted parity generator, operably coupled to the quadratic function unit and to the running sum unit, for mod-2 summing the outputs of the running sum unit and the quadratic function unit, and mod-2 summing a prespecified binary constant (A) to provide adjusted parity bit(s) to the differential encoder, the mod-2 summing being of a form: Σ.sub.0≦n≦L-1 P1(n)=P=A⊕Σ.sub.0≦i≦L-2 P1(i) ⊕Σ.sub.0≦i≦L-1 B(i) P2(i) ⊕ΣΣ.sub.0≦k,j≦L-1 C(i,j) P2(i) P2(j), where A is a preselected binary constant, i and j are integers, B(i) and C(i,j) are preselected binary constants, and P2(i) and P2(j) represents the second differentially encoded data bits, such that B(i) and C(i,j) are selected to provide that, for any integer n, where 0≦n≦L-1, P2(n) appears in second-order terms an odd number of times, and B(i) are further selected such that the total number of terms in the two summations is even, and such that utilizing the adjusted parity bit(s) provides a frame of two-dimensional signal points that are rotationally invariant in a parity check.

Claim 14

The device of claim 12 wherein C(i,j)=1 for odd values of i, with j=i-1, and B(i)=1 for even values of n.

Claim 15

The device of claim 12 wherein B(i)=1 for odd values of n, L is a multiple of 4.

Claim 16

The device of claim 12 wherein the SPC means includes an odd indexed symbol running sum unit operably coupled to receive an odd-indexed data bit (Q3), for monitoring a running mod-2 sum of the bits of the frame and determining a parity bit such that Q3(L-1)=A⊕Q.sub.3 (1)⊕Q.sub.3 (3) ⊕. . . ⊕Q.sub.3 (L-3), where A is a preselected binary constant and Q 3 (1), Q 3 (3), . . . , Q3(L-3) are odd-indexed symbols for the input data bit Q3.

Claim 17

The device of claim 1 wherein parity is determined by one of: (A) the SPC means utilizing a mod-2 sum of a form: P1(L-1)=A⊕Σ.sub.0≦n≦L-2 P1(n)⊕ΣΣ.sub.0≦i≦L-1 P2(i) P2(j), .sub.i+l<j<L- 1 where n is a predetermined integer, L is a frame length, P2 represents the first differentially encoded bits, and P1 represents the second differentially encoded bits, (B) where L is a multiple of 4, or equivalently, a set of L quaternary numbers C(n)=2·P1(n)+P2(n), n=0, 1, . . ., L-1, is defined, and a parity bit is selected such that the mod-4 sum of C(n) is one of: 0 and 1, and (C) where L is other than a multiple of 4, the code is constrained to be rotationally invariant by adding an odd number K (K an integer) of first order terms (since K+L(L-1)/2 is even).

Claim 20

The method of claim 17 wherein the signal points of the two-dimensional signal constellation lie on a rectangular grid.

Claim 21

The method of claim 17 wherein the unknown rotation of signal points is one of: 90°, 180° and 270°.

Claim 22

The method of claim 20, wherein the trellis code is a 4-dimensional trellis code.

Claim 23

The method of claim 20 wherein the 4-dimensional trellis code is a 16-state code.

Claim 24

The method of claim 17, wherein, in the step of generating a parity check bit, the parity bit is computed according to a nonlinear function of a plurality of second rotationally-significant label bits.

Claim 25

The method of claim 22 wherein the nonlinear function is a quadratic function of the plurality of the second rotationally-significant label bits.

Claim 26

The method of claim 17 wherein, in the step of generating a parity check bit, the parity bit is determined by the SPC means according to a formula of a form: P=A⊕Σ.sub.0≦i≦L-2 P1(i)⊕Σ.sub.0≦i≦L-1 B(i) P2(i) ⊕ΣΣ.sub.0≦i,j≦L-1 C(i,j) P2(i) P2(i j), where A is a preselected binary constant, L is a frame length, i and j are integers, B(i) and C(i,j) are preselected binary constants, and P2(i), P2(j) represents a plurality of second rotationally-significant label bits and Pl(i) represents a plurality of first rotationally-significant label bits, such that C(i,j) are chosen such that for any integer n, where 0≦n≦L-1, P2(n) appears in the second-order terms an odd number of times, and B(i) are further selected such that the total number of non-zero terms in the last two summations is even.

Claim 27

The method of claim 24 wherein C(i,j)=1 for odd values of i, with j=i-1, and B(i)=1 for even values of i.

Claim 28

The method of claim 24 wherein B(i)=1 for odd values of i, L is a multiple of 4.

Claim 29

The method of claim 17, further including the step of utilizing a differential encoder for generating the p rotationally-significant bits utilizing at least two input data bits.

Claim 32

The method of claim 28, wherein the signal points of the two-dimensional signal constellation lie on a rectangular grid.

Claim 33

The method of claim 28 wherein the rotation of received signal points is one of: 90°, 180° and 270°.

Claim 34

The method of claim 28, wherein the trellis code is a 4-dimensional trellis code.

Claim 35

The method of claim 31 wherein the 4-dimensional code is a 16-state code.

Claim 36

The method of claim 28 wherein the differential encoder is a mod-4 sum differential encoder.

Claim 37

The method of claim 28 wherein the nonlinear function the parity bit is based on is a quadratic function of the first differentially-encoded rotationally significant bits.

Claim 38

The method of claim 28 wherein the first and second differentially encoded rotationally significant label bits are P1, P2 of the differential encoder and the parity bit is selected such that adjusted parity bit(s) is/are determined in accordance with a mod-2 sum that is equal to a binary value P which is determined in accordance with the second bits, P2, further including the steps of: (A) determining a running sum, being a mod-2 sum of a form: Σ.sub.≦ i≦L-2 P1(i) where L is a frame length and i is an integer, (B) determining a quadratic function of the form: Σ.sub.0≦i≦L-1 B(i) P2(i) ⊕ΣΣ.sub.0≦i,j≦L-1 C(i,j) P2(i) P2(j) where B(i) are predetermined binary constants, C(i,j) are predetermined binary constants, i and j are integers, (C) mod-2 summing the outputs of the running sum unit and the quadratic function unit, and mod-2 summing a prespecified binary constant (A) to provide adjusted parity bit(s) to the differential encoder, the mod-2 summing being of a form: Σ.sub.0≦n≦L-1 P1(n)=P=A⊕Σ.sub.0≦i≦L-2 P1(i) ⊕Σ.sub.0≦i≦L-1 B(i) P2(i) ⊕ΣΣ.sub.0≦i,j≦L-1 C(i,j) P2(i) P2(j) where A is a preselected binary constant, i and j are integers, B(i) and C(i,j) are preselected binary constants, and P2(i) and P2(j), represent the second set of differentially encoded data bits, such that B(i) and C(i,j) are selected to provide P2(n) that, for any n=i, j, appears (non-zero) in second-order terms an odd number of times, and B(i) are selected such that the total number of terms in the two summations is even, and such that utilizing the adjusted parity bit(s) provides a frame of two-dimensional signal points that are rotationally invariant in a parity check.

Claim 39

The method of claim 35 wherein C(i,j)=1 for odd values of i, with j=i-1, and B(i)=1 for even values of n.

Claim 40

The method of claim 35 wherein B(i)=1 for odd values of n, L is a multiple of 4.

Claim 41

The method of claim 28 wherein the step of determining at least a first parity bit includes the step of utilizing an odd indexed symbol running sum unit operably coupled to receive an odd-indexed data bit (Q3), for monitoring a running mod-2 sum of the bits of the frame and determining a parity bit such that Q.sub.3 (L-1)=A⊕Q.sub.3 (1) ⊕Q.sub.3 (3) ⊕. . . ⊕Q.sub.3 (L-3), where A is a preselected binary constant and Q 3 (1), Q 3 (3), . . . , Q3(L-3) are odd-indexed symbols for the input data bit Q3.

Claim 42

The method of claim 28 wherein parity is determined by one of: (A) utilizing the parity-equation in the following form: P1(L-1)=P=A⊕Σ.sub.o≦n≦L-2 P1(n)⊕Σ.sub.0≦k≦L/2-1 P.sub.2 (2K+1) P2(2k), and recursively determining P1(L-1)=P , where A is a preselected binary constant, n and k are predetermined integers, L is a frame length, P1(n) is the first set of differentially encoded bits, P2(2k, 2k+1) are successive bits of the second set of differentially encoded bits, and P2 (2k+1) is the logical inversion of P2(2k+1), by the steps of: (A1) at the start of a frame, setting P to a pre-specified binary value, which is denoted as A, (A2) In even numbered 4D intervals (n=0, 2, 4, 6, . . . ), recording the value of P2(n) for use in the next interval, and adjusting P according to P=P⊕P1(n), (A3) in odd numbered 4D intervals (n=1, 3, 5, or 7, . . . , L-3), where P2(n)-0, then P=P⊕P2(n-1)⊕P1 (n), and where P2(n)=1, then P=P⊕P1(n), and (A4) at the end of a frame (n=L-1), selecting P such that: where P2(L-2)=0, then P=P⊕P2(n-1), and where P2(L-2)=1, then P=P; (B) utilizing a mod-2 sum of a form: P1(L-1)=A⊕Σ.sub.0≦n≦L-2 P1(n)⊕ΣΣ0≦i≦L-1P2(i) P2(j), .sub.i+1≦j≦L-1 where n is a predetermined integer, L is a frame length, P2 is the second set of differentially encoded bits, and P1 is the first set of differentially encoded bits, (C) where L is a multiple of 4, or equivalently, utilizing a set of L quaternary numbers C(n)=2·P1(n)+P2(n), n =0, 1, . . . , L-1, is defined, and selecting a parity bit such that the mod-4 sum of C(n) is one of: 0 and 1, and (D) where L is other than a multiple of 4, constraining the code to be rotationally invariant by adding an odd number K (K an integer) of first order terms (since K+L(L-1)/2 is even).

Claim 43

A multi-level trellis-coded communication system for encoding a stream of input data bit sequences in a preselected multi-level code, transmitting encoded data, and decoding received data to provide a rotationally invariant parity check code, comprising: (A) a multi-level trellis encoder with at least one SPC, for encoding the stream of input data bit sequences to provide a rotationally invariant multi-level code, comprising: (1) a mapper for mapping at least a group of n label bits into a sequence of two-dimensional signal points selected from a two-dimensional signal constellation according to a labelling wherein rotation of the signal constellation affects only p rotationally-significant label bits (2≦p<n; p, n integers) of the n label bits, (2) a convolutional encoder for a trellis code, operably coupled to receive and encode selected input bits, wherein the second rotationally-significant label bit is a coded bit for the trellis code, (3) single-parity check code (SPC) means for generating a parity check bit for a first rotationally-significant label bit to allow the receiver to detect parallel transition errors in the trellis code, wherein the parallel transition errors are two-symbol errors, and wherein the parity-check bit is computed based on at least a second rotationally-significant label bit, such that the parity bit provides a means for detecting errors in the first rotationally-significant label bit even when the signal points are rotated by an unknown amount, (4) trellis encoder for encoding at least one of the data bits and rotationally-significant label bits, and (B) a modulator, pulse-shaping digital to analog (D/A) converter, operably coupled to receive trellis-encoded code, for modulating and pulse-shaping the code to form a signal and transmitting the signal along a channel, (C) an analog to digital (A/D) converter, operably coupled to receive the transmitted signal, for digitizing the signal, (D) an adaptive equalizer, operably coupled to the A/D converter, for equalizing the digitized signal, (E) a demodulator, operably coupled to the adaptive equalizer, for demodulating the equalized digitized signal, and (F) a decoder for multi-level trellis code, operably coupled to the demodulator, for decoding the demodulated equalized digitized signal to provide an estimated data bit sequence.

Claim 44

A multi-level trellis-coded communication system for encoding a stream of input data bit sequences in a preselected multi-level code, transmitting encoded data, and decoding received data to provide a rotationally invariant parity check code, comprising: (A) a multi-level trellis encoder with at least one SPC, for encoding the stream of input data bit sequences to provide a rotationally invariant multi-level code, comprising: (1) a mapper for mapping at least a group of n label bits into a sequence of two-dimensional signal points selected from a two-dimensional signal constellation according to a labelling wherein rotation of the signal constellation affects only p rotationally-significant label bits (2≦p<n; p, n integers) of the n label bits, (2) a convolutional encoder for a trellis code, operably coupled to receive and encode selected input bits, wherein the second rotationally-significant label bit is a coded bit for the trellis code, (3) single-parity check code (SPC) means for generating a parity check bit for a first rotationally-significant label bit to allow the receiver to detect parallel transition errors in the trellis code, wherein the parallel transition errors are two-symbol errors, and wherein the parity-check bit is computed based on at least a second rotationally-significant label bit, such that the parity bit provides a means for detecting errors in the first rotationally-significant label bit even when the signal points are rotated by an unknown amount, (4) trellis encoder for encoding at least one of the data bits and rotationally-significant label bits, and (B) a modulator, pulse-shaping digital to analog (D/A) converter, operably coupled to receive trellis-encoded code, for modulating and pulse-shaping the code to form a signal and transmitting the signal along a channel, (C) an analog to digital (A/D) converter, operably coupled to receive the transmitted signal, for digitizing the signal, (D) an adaptive equalizer, operably coupled to the A/D converter, for equalizing the digitized signal, (E) a demodulator, operably coupled to the adaptive equalizer, for demodulating the equalized digitized signal, and (F) a decoder for multi-level trellis code, operably coupled to the demodulator, for decoding the demodulated equalized digitized signal to provide an estimated data bit sequence.

Claim 45

The system of claim 40, wherein the signal points of the two-dimensional signal constellation lie on a rectangular grid.

Claim 46

The system of claim 40 wherein the unknown rotation of signal points is one of: 90°, 180° and 270°.

Claim 47

The system of claim 40, wherein the trellis code is a 4-dimensional trellis code.

Claim 48

The system of claim 43 wherein the 4-dimensional trellis code is a 16-state code.

Claim 49

The system of claim 40, wherein the parity bit is computed according to a nonlinear function of a plurality of second rotationally-significant label bits.

Claim 50

The system of claim 45 wherein the nonlinear function is a quadratic function of the plurality of the second rotationally-significant label bits.

Claim 51

The system of claim 40 wherein the parity bit is determined by the SPC means according to a formula of a form: P=A⊕Σ.sub.0≦i≦L-2 P1(i)⊕Σ.sub.0≦i≦L-1 B(i) P2(i) ⊕ΣΣ.sub.0≦i,j≦L-1 C(i,j) P2(i) P2(j), where A is a preselected binary constant, L is a frame length, i and j are integers, B(i) and C(i,j) are preselected binary constants, and P2(i), P2(j) represents a plurality of second rotationally-significant label bits and P1(i) represents a plurality of first rotationally-significant label bits, and where C(i,j) is chosen such that for any integer n, where 0 ≦n≦L-1, P2(n) appears in the second-order terms an odd number of times, and B(i) are further selected such that the total number of non-zero terms in the last two summations is ever.

Claim 52

The system of claim 47 wherein C(i,j)=1 for odd values of i, with j=i-1, and B(i)=1 for even values of i.

Claim 53

The system of claim 48 wherein B(i)=1 for odd values of i, L is a multiple of 4.

Claim 54

The system of claim 40, further including a differential encoder, operably coupled to receive at least two data bits, for generating the p rotationally-significant bits.