Trellis encoding technique for PCM modems

• US 6,848,073 B2
• Filed: 10/08/2001
• Issued: 01/25/2005
• Est. Priority Date: 06/09/1997
• Status: Expired due to Fees

• Current Assignee: VOCAL Technologies Ltd.
• Original Assignee: VOCAL Technologies Ltd.
• Inventors: Hirzel, Frederic J., Demjanenko, Victor
• Primary Examiner(s): Lamarre, Guy J.
• Application Number:
  US09/973,483
• Publication Number:
  US 20020157061A1
• Time in Patent Office: 1,205 Days
• Field of Search: 714/792, 714/755, 714/786, 714/783, 714/777, 714/778, 714/789, 375/222, 375/216, 375/265, 375/285, 375/295, 375/286, 375/342, 375/264, 375/231, 375/293, 375/371, 360/65, 341/59, 341/78, 341/94, 370/503, 370/535, 370/354
• US Class Current: 714/786
• CPC Class Codes: H03M 13/235 Encoding of convolutional codes, e.g. methods or arrangements for parallel or block-wise encoding
• CPC Class Codes: H03M 13/256 with trellis coding, e.g. with convolutional codes and TCM

Abstract

A method of applying a multidimensional error reduction/correction algorithm on a stream of one dimensional symbols, by converting the stream of one dimensional symbols into a corresponding stream of two dimensional symbols; and, applying the multidimensional error reduction/correction algorithm to the stream of two dimensional symbols. The invention also provides a method of normalizing a metric used by an error reduction/correction algorithm on a stream of symbols wherein the symbols are non-uniformly spaced, by: determining a minimum distance (dmin) between two closest symbols in the stream, for each symbol in the stream, determining a minimum distance (dsym) between each symbol in the stream and each of its adjacent neighboring symbols, and, normalizing the metric used by the error reduction/correction algorithm by the ratio dmin/dsym.

Claims

1. A method of performing four-dimensional error reduction/correction on a stream of one dimensional transmit symbols, comprising:

assigning a transmit output to a transmit symbol;

concurrently assigning a one-dimensional subset label to said transmit symbol;

storing three one-dimensional subset labels for three transmit symbols; and

forming fourth transmit symbol such that an associated fourth one-dimensional subset label is partially determined by a combination of an output of an error reduction/correction algorithm and said three stored one-dimensional subset labels, wherein forming the fourth transmit symbol comprises;

mapping respective pairs of one-dimensional subset labels selected from said fourth one-dimensional subset label and said three stored one-dimensional subset labels to produce first and second two-dimensional subset labels;

mapping said first and second two-dimensional subset labels to produce a four-dimensional subset label; and

providing said four-dimensional subset label as input to said error reduction/correction algorithm.

2. The method recited in claim 1, wherein said error reduction/correction algorithm is performed by a trellis encoder.

3. The method recited in claim 1, wherein said error reduction/correction algorithm is performed by a systematic convolutional encoder.

4. The method recited in claim 1, wherein assigning a one-dimensional subset label to said transmit symbol comprises:

ordering transmit outputs by value; and

assigning one-dimensional subset labels to said transmit outputs in sequence.

5. The method recited in claim 4, wherein ordering transmit outputs by value is performed according to increasing value of said transmit outputs.

6. The method recited in claim 4, wherein assigning subset labels in sequence is performed according to ascending values of said subset labels.

7. The method recited in claim 1, wherein forming said fourth transmit symbol further comprises:

computing U₀ as a combination of an output of an error reduction/correction encoder performing said error reduction/correction algorithm and said three stored one-dimensional subset labels; and

forming said fourth transmit symbol such that a bit 0 of said associated fourth one-dimensional subset label is determined by U₀.

8. The method recited in claim 7, wherein said error reduction/correction encoder is a trellis encoder.

9. The method recited in claim 7, wherein computing U₀ comprises determining a sum modulo 2 of said output of said error reduction/correction encoder and said three stored one-dimensional subset labels.

10. The method recited in claim 7, wherein said fourth transmit symbol is formed such that bit 0 of its associated fourth one-dimensional subset label is equal to U₀.

11. The method recited in claim 1, wherein forming said fourth transmit symbol further comprises:

generating a verification sequence bit V₀;

computing U₀ as a combination of a previous encoder output of an error reduction/correction encoder, said three stored one-dimensional subset labels and a verification sequence bit V₀; and

forming said fourth transmit symbol such that a bit 0 of its associated one-dimensional subset label is determined by U₀.

12. A method of performing four-dimensional error reduction/correction on a stream of one dimensional transmit symbols, comprising:

assigning a transmit output to a transmit symbol;

concurrently assigning a subset label to said transmit symbol, wherein transmit outputs are ordered by increasing value and subset labels are in ascending order;

forming a first transmit symbol at a time 4m+0, where m is an integer, from input data and storing a subset label r(4m+0) associated with said first transmit symbol;

forming a second transmit symbol at a time 4m+1 from input data and storing a subset label r(4m+1) associated with the second transmit symbol;

forming a third transmit symbol at a time 4m+2 from input data and storing a subset label r(4m+2) associated with the third transmit symbol;

computing U₀(m) as a sum modulo 2 of a previous output Y₀(m) of a trellis encoder and said stored subset labels r(4m +0), r(4m+1) and r(4m+2), according to the equation U₀(m)=Y₀(m)⊕

r(4m+0)⊕

r(4m+1)⊕

r(4m+2);

forming a fourth transmit symbol at a time 4m+3 from input data and U₀(m) such that a bit 0 of a subset label r(4m+3) associated with the fourth transmit symbol is determined by U₀(m);

mapping a pair of subset labels r(4m+0) and r(4m+1) to a secondary subset label s(2n+0) and further mapping a pair of subset labels r(4m+2) and r(4m+3) to a secondary subset label s(2n+1), where 2n=4m;

mapping a pair of secondary subset labels s(2n+0) and s(2n+1) to inputs of said trellis encoder Y₁(m), Y₂(m), Y₃(m) and Y₄(m), and;

calculating an output of said trellis encoder Y₀(m+1) from said input bits Y₁(m), Y₂(m), Y₃(m) and Y₄(m).

13. A method of applying a four-dimensional error reduction/correction algorithm on a stream of one-dimensional symbols, comprising:

converting pairs of symbols of said stream of one-dimensional symbols to corresponding two-dimensional symbols;

converting a pair of said two-dimensional symbols into a corresponding four-dimensional symbol;

providing said four-dimensional symbol as input to said error reduction/correction algorithm; and

forming a one-dimensional symbol of said stream of symbols that is partially determined by an output of the error reduction/correction algorithm.

14. A communication device performing error correction/reduction accordance with the method recited in claim 13.