Patent US5982818A successfully refreshed from Google Patents.
US5982818A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for implementing trellis codes for ISI channels
Assignee: Individual
•
Filing: 1997-01-07
•
Granted: 1999-11-09
•
Expires: 2017-01-07
Abstract
Abstract A method of design and implementation of trellis codes for intersymbol interference channels is provided wherein a set of input vectors is mapped to a set of output vectors comprising the steps of forming a minimized basis having a set of minimized basis vectors configured for a set of channel output signals corresponding to the set of output vectors; selecting the smallest member of the set of minimized basis vectors as a coset vector; forming a partition basis by adding the coset vector to at least one member of the set of the minimized basis vectors; and forming a subsequent minimized basis from the partition basis. These codes circumvent the necessity for intersymbol interference removal, thereby reducing equalization complexity.
Inventors
- 👤 Daniel J. Krueger
- 👤 Joao R. Cruz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 19:00
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/25; H03M13/256; H04; H04L; H04L27/00; H04L27/32; H04L27/34; H04L27/3405; H04L27/3416
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
138 words
A method for designing a logic circuit which implements a mapping from a set of input words to a set of output words, wherein the mapping is determined by constructing a binary tree, and wherein the set of output words is split into at least one coset having leaves of the binary tree, the method of determining the at least one coset comprising the steps of: forming a minimized basis composed of a set of minimized basis vectors for a set of channel output signals corresponding to the set of output words; selecting the smallest member of the set of minimized basis vectors as a coset vector; forming a partition basis by adding the coset vector to at least one member of the set of minimized basis vectors; and forming a subsequent minimized basis from the partition basis.
Claim 2
Independent Claim
138 words
A method for designing a logic circuit which implements a mapping from a set of input words to a set of output words, wherein the mapping is determined by constructing a binary tree, and wherein the set of output words is split into at least one coset having leaves of the binary tree, the method of determining the at least one coset comprising the steps of: forming a minimized basis composed of a set of minimized basis vectors for a set of channel output signals corresponding to the set of output words; selecting the smallest member of the set of minimized basis vectors as a coset vector; forming a partition basis by adding the coset vector to at least one member of the set of minimized basis vectors; and forming a subsequent minimized basis from the partition basis.
Claim 3
Independent Claim
260 words
A method for designing a logic circuit which implements a mapping from a set of input vectors to a set of output vectors, wherein the mapping is determined by constructing a binary tree, and wherein the set of output vectors is split into at least one coset having leaves of the binary tree, the method of determining the at least one coset comprising the steps of: (a) forming a minimized basis composed of a set of minimized basis vectors for a set of channel output signals corresponding to the set of output vectors; (b) selecting the smallest member of the set of minimized basis vectors as a coset vector; (c) noting the coset vector in a list of coset vectors; (e) forming a partition basis by adding the coset vector to at least one member of the set of minimized basis vectors; (f) forming a subsequent minimized basis from the partition basis; and (e) repeating steps (b), (c), (d), and (e) as necessary to achieve a desired minimum distance between a coset of channel output signals corresponding to one of the at least one cosets of output vectors, the membership of the one of the at least one cosets of output vectors being determined by a mutual shared combination of at most one of each vector in the list of coset vectors, the combination being that used to express the coset of channel output signals corresponding to one of the at least one coset of output vectors in terms of a final minimized basis and the list of coset vectors.
Claim 4
Independent Claim
260 words
A method for designing a logic circuit which implements a mapping from a set of input vectors to a set of output vectors, wherein the mapping is determined by constructing a binary tree, and wherein the set of output vectors is split into at least one coset having leaves of the binary tree, the method of determining the at least one coset comprising the steps of: (a) forming a minimized basis composed of a set of minimized basis vectors for a set of channel output signals corresponding to the set of output vectors; (b) selecting the smallest member of the set of minimized basis vectors as a coset vector; (c) noting the coset vector in a list of coset vectors; (e) forming a partition basis by adding the coset vector to at least one member of the set of minimized basis vectors; (f) forming a subsequent minimized basis from the partition basis; and (e) repeating steps (b), (c), (d), and (e) as necessary to achieve a desired minimum distance between a coset of channel output signals corresponding to one of the at least one cosets of output vectors, the membership of the one of the at least one cosets of output vectors being determined by a mutual shared combination of at most one of each vector in the list of coset vectors, the combination being that used to express the coset of channel output signals corresponding to one of the at least one coset of output vectors in terms of a final minimized basis and the list of coset vectors.
Claim 5
Dependent Claim
14 words
The method of claim 2 wherein the minimum distance is the minimum Euclidean distance.
Claim 6
Dependent Claim
67 words
The method of claim 2 wherein the set of channel output signals corresponding to the set of output vectors can be determined by a correspondence expressing an output signal from an interference-free discrete-time channel in terms of an input signal which is assumed to be zero for all time outside a time interval during which a member of the set of output vectors determines the input signal.
Claim 7
Dependent Claim
34 words
The method of claim 2 further comprising the step of extending the binary tree by arbitrarily splitting the at least one coset until each of the at least one cosets has only one member.
Claim 8
Dependent Claim
18 words
The method of claim 2 wherein the mapping excludes one or more of the at least one cosets.
Claim 9
Dependent Claim
50 words
The method of claim 2, further comprising the steps of fabricating the logic circuit and mounting the fabricated logic circuit into an encoder module configured for receiving a sequence of user data vectors and, in response to the received sequence of user data vectors, generating a sequence of output vectors.
Claim 10
Dependent Claim
71 words
The method of claim 7, further comprising the step of providing a convolutional encoder having: a shift register for storing a predetermined number of user data vectors; and a plurality of logic gates interconnected between the shift register and the logic circuit, the plurality of logic gates being configured for generating, from the contents of the shift register and a current user data vector, an input vector to the logic circuit.
Claim 11
Dependent Claim
90 words
The method of claim 7, further comprising the steps of: connecting, between an input register and the logic circuit, a shift register configured for storing at least one edge vector; connecting to the shift register a plurality of logic gates configured for determining a current edge vector based on a current user vector and the contents of the shift register; and connecting to the logic circuit an additional circuit which forms an input vector to the logic circuit from the current user vector and the contents of the shift register.
Claim 12
Dependent Claim
108 words
The method of claim 7, further comprising the step of integrating the logic circuit into a digital communications system having: an encoder portion into which the encoder module is integrated, the encoder portion being configured for receiving an input sequence of user data and, in response to the received data, for generating an encoded sequence of data; a discrete-time channel coupled to the encoder portion for receiving the encoded sequence of data and for generating from the input sequence an output sequence of data; and a decoder coupled to the channel for receiving and decoding the output sequence of data, and for outputting the decoded sequence of data.
Claim 13
Independent Claim
91 words
A method for mapping a set of input vectors to a set of output vectors, the method comprising: forming a minimized basis having a set of minimized basis vectors configured for a set of channel output signals corresponding to the set of output vectors; selecting the smallest member of the set of minimized basis vectors as a coset vector; forming a partition basis by adding the coset vector to at least one member of the set of the minimized basis vectors; and forming a subsequent minimized basis from the partition basis.
Claim 14
Independent Claim
91 words
A method for mapping a set of input vectors to a set of output vectors, the method comprising: forming a minimized basis having a set of minimized basis vectors configured for a set of channel output signals corresponding to the set of output vectors; selecting the smallest member of the set of minimized basis vectors as a coset vector; forming a partition basis by adding the coset vector to at least one member of the set of the minimized basis vectors; and forming a subsequent minimized basis from the partition basis.
Claim 15
Dependent Claim
148 words
The method of claim 11 further comprising, after the step of selecting, the step of noting the coset vector in a list of coset vectors; and, after the step of forming a subsequent basis, repeating the steps of selecting, noting, forming a partition basis, forming a subsequent basis as necessary to achieve a desired minimum Euclidean distance between a coset of channel output signals corresponding to one of the at least one cosets of output vectors, the membership of the one of the at least one cosets of output vectors being determined by a mutual shared combination of at most one of each vector in the list of coset vectors, the combination being that used to express the coset of channel output signals corresponding to one of the at least one coset of output vectors in terms of a final minimized basis and the list of coset vectors.
Claim 16
Dependent Claim
67 words
The method of claim 12 wherein the set of channel output signals corresponding to the set of output vectors can be determined by a correspondence expressing an output signal from an interference-free discrete-time channel in terms of an input signal which is assumed to be zero for all time outside a time interval during which a member of the set of output vectors determines the input signal.
Claim 17
Dependent Claim
34 words
The method of claim 12 further comprising the step of extending the binary tree by arbitrarily splitting the at least one coset until each of the at least one cosets has only one member.
Claim 18
Dependent Claim
18 words
The method of claim 12 wherein the mapping excludes one or more of the at least one cosets.
Claim 19
Dependent Claim
50 words
The method of claim 12, further comprising the steps of fabricating the logic circuit and mounting the fabricated logic circuit into an encoder module configured for receiving a sequence of user data vectors and, in response to the received sequence of user data vectors, generating a sequence of output vectors.
Claim 20
Dependent Claim
90 words
The method of claim 15, further comprising the steps of: connecting, between an input register and the logic circuit, a shift register configured for storing at least one edge vector; connecting to the shift register a plurality of logic gates configured for determining a current edge vector based on a current user vector and the contents of the shift register; and connecting to the logic circuit an additional circuit which forms an input vector to the logic circuit from the current user vector and the contents of the shift register.
Claim 21
Dependent Claim
108 words
The method of claim 15, further comprising the step of integrating the logic circuit into a digital communications system having: an encoder portion into which the encoder module is integrated, the encoder portion being configured for receiving an input sequence of user data and, in response to the received data, for generating an encoded sequence of data; a discrete-time channel coupled to the encoder portion for receiving the encoded sequence of data and for generating from the input sequence an output sequence of data; and a decoder coupled to the channel for receiving and decoding the output sequence of data, and for outputting the decoded sequence of data.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-08 | 2003-05-10 | 2003-11-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-08 | 2007-05-10 | 2007-11-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-08 | 2011-05-10 | 2011-11-09 | $7700.00 | Window Closed / Lapsed |