US5257272A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Time-varying modulo N trellis codes for input restricted partial response channels
Assignee: International Business Machines Corp
•
Filing: 1992-04-15
•
Granted: 1993-10-26
•
Expires: 2012-04-15
Abstract
Abstract A method and apparatus for generating high rate run length limited trellis codes and increasing minimum distance between output sequences of partial response channels with constrained channel inputs without requiring codes with spectral nulls. A Viterbi detector replicates a conventional trellis structure for the channel N times. The N copies of the channel response trellis are interconnected such that a preselected function associates each state in the trellis with a particular integer value modulo N. The number N is selected according to the channel detection and coding constraints so that diverging erroneous sequences of minimum distance lead to detector states which are distinct from the correct detector state. The detector trellis is time-varying such that only certain values of the preselected function are allowed every m bits. The time-variation assures there are no minimum distance extensions of erroneous sequences beyond a predetermined length. Reliability of storage channels is desirably increased, because more noise is required to overcome the additional distance and cause an error in distinguishing the correct encoded sequence.
Inventors
- 👤 Lyle J. Fredrickson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 14:42
CPC Classifications
H; H03; H03M; H03M5/00; H03M5/02; H03M5/04; H03M5/14; H03M5/145; H03M13/00; H03M13/25; H03M13/31; H03M13/37; H03M13/39; H03M13/41; H04; H04L; H04L25/00; H04L25/38; H04L25/40; H04L25/49; H04L25/497
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
114 words
A method for maximum likelihood detection of a high rate trellis code, comprising the steps of: using an encoder, encoding sequences of digital electrical signals constituting input data into sequences of coded bits; inputting said sequences of coded bits to a partial response channel; supplying a channel response to the coded bits, corrupted by noise, to a Viterbi detector constructed by interconnecting N copies of a trellis structure associated with the channel; using the detector to provide as output sequences maximum likelihood estimates of the sequences of the coded bits; and tracking with the detector a predetermined attribute of each sequence of coded bits modulo N for increasing minimum distance between said output sequences.
Claim 2
Independent Claim
114 words
A method for maximum likelihood detection of a high rate trellis code, comprising the steps of: using an encoder, encoding sequences of digital electrical signals constituting input data into sequences of coded bits; inputting said sequences of coded bits to a partial response channel; supplying a channel response to the coded bits, corrupted by noise, to a Viterbi detector constructed by interconnecting N copies of a trellis structure associated with the channel; using the detector to provide as output sequences maximum likelihood estimates of the sequences of the coded bits; and tracking with the detector a predetermined attribute of each sequence of coded bits modulo N for increasing minimum distance between said output sequences.
Claim 3
Dependent Claim
30 words
The method of claim 1, including the step of: time-varying said trellis structure to allow only certain values of said tracked predetermined attribute periodically in time to eliminate quasi-catastrophic sequences.
Claim 4
Dependent Claim
25 words
The method of claim 1, wherein the predetermined attribute is a weighted sum modulo N of the coded bits using a predetermined sequence of weights.
Claim 5
Dependent Claim
35 words
The method of claim 1, wherein the partial response channel has the characteristic polynomial (1+D-D 2 -D 3 ), and the predetermined attribute is the sum of alternate input bits in NRZI notation modulo N.
Claim 6
Dependent Claim
7 words
The method of claim 4, wherein N=2.
Claim 7
Dependent Claim
31 words
The method of claim 1, wherein the partial response channel has the characteristic polynomial (1-D), and the predetermined attribute is a running digital sum of consecutive input bits in NRZ notation.
Claim 8
Dependent Claim
35 words
The method of claim 6, wherein the partial response channel has the characteristic polynomial (1-D n ), where n is a nonnegative integer, and the channel is deinterleaved into n channels of the form (1-D).
Claim 9
Dependent Claim
48 words
The method of claim 1, wherein the partial response channel has the characteristic polynomial (1+D), and the predetermined attribute is a digital sum of the consecutive input bits in NRZ notation obtained by adding input bits in even index positions and subtracting input bits in odd index position.
Claim 10
Dependent Claim
35 words
The method of claim 8, wherein the partial response channel has the characteristic polynomial (1+D n ), where n is a nonnegative integer, and the channel is deinterleaved into n channels of the form (1+D).
Claim 11
Dependent Claim
35 words
The method of claim 1, including the step of: selecting the sequences of coded bits from trellis sequences in the trellis structure which do not contain subsequences that require minimum distance decisions by the detector.
Claim 12
Dependent Claim
50 words
The method of claim 1, including the steps of: identifying in the trellis structure trellis sequences which contain a pair of minimum distance subsequences; prebiasing the detector to favor only one of the subsequences of each pair; and using only the favored subsequences from each pair in the trellis code.
Claim 13
Dependent Claim
86 words
The method of claim 1, including the steps of: selecting some of the sequences of coded bits from trellis sequences of the trellis structure which do not contain subsequences that require minimum distant decisions by the detector; providing in the trellis structure other trellis sequences containing minimum distance subsequences; prebiasing the detector to favor only one of the subsequences in each such other trellis sequence; and constructing the trellis code using a combination of the trellis sequences containing the favored subsequences and trellis sequences without subsequences.
Claim 14
Independent Claim
152 words
A method for constructing a trellis structure and an associated trellis code for increasing minimum distance between output sequences of digital electrical signals transmitted over a partial response channel, comprising the steps of: preselecting a weighting function that maps channel input sequences to a selected integer value modulo N; interconnecting N Viterbi detectors, each having m channel states, each such state representing the most recent input to the partial response channel, for creating a modified trellis structure for a modified Viterbi detector having n times m states each representing a combination of a channel state and a particular value of the weighting function; and determining the value of N and constraints for the channel input sequences and the modified detector for increasing the minimum distance between output sequences by insuring that pairs of noiseless output sequences originating at a common state in the modified detector do not remerge at the minimum distance.
Claim 15
Independent Claim
152 words
A method for constructing a trellis structure and an associated trellis code for increasing minimum distance between output sequences of digital electrical signals transmitted over a partial response channel, comprising the steps of: preselecting a weighting function that maps channel input sequences to a selected integer value modulo N; interconnecting N Viterbi detectors, each having m channel states, each such state representing the most recent input to the partial response channel, for creating a modified trellis structure for a modified Viterbi detector having n times m states each representing a combination of a channel state and a particular value of the weighting function; and determining the value of N and constraints for the channel input sequences and the modified detector for increasing the minimum distance between output sequences by insuring that pairs of noiseless output sequences originating at a common state in the modified detector do not remerge at the minimum distance.
Claim 16
Dependent Claim
48 words
The method of claim 13, including the step of selecting as the trellis code one that uses a subset of sequences that corresponds to paths through the modified trellis structure from which selected states and edges have been deleted and incorporates the constraints for the channel input sequences.
Claim 17
Dependent Claim
58 words
The method of claim 13, including the steps, to eliminate quasi-catastrophic sequences from the trellis code, of: deleting selected states and/or edges from the modified trellis structure to eliminate multiple paths having identical noiseless channel output sequences; and selecting as the trellis code one which is a subset of the quasi-catastrophic sequences permitted by the modified trellis structure.
Claim 18
Independent Claim
195 words
A method for increasing the minimum distance between output sequences of partial response channels having a plurality of states without requiring codes with spectral nulls, comprising the steps of: encoding digital electrical signals constituting user input data into encoded sequences of bits which are input to the channel; preselecting a weighting function which maps each of the encoded sequences, in NRZ or NRZI notation, to an integer value modulo N; interconnecting N Viterbi detectors each having a plurality of trellis states to create a modified Viterbi detector having N times said plurality of trellis states, where each state in the modified detector is associated with a corresponding channel state and a corresponding value of the weighting function; determining the value of N and channel input and detector constraints which ensure that sequences of minimum distance emanating from a common state in the modified detector lead to different detector states; deleting from the modified detector trellis states and/or edges emanating from the trellis states from a trellis to eliminate multiple paths with identical noiseless sample values; and selecting a code which is a subset of nonquasi-catastrophic sequences that correspond to permissible paths through the modified detector.
Claim 19
Independent Claim
195 words
A method for increasing the minimum distance between output sequences of partial response channels having a plurality of states without requiring codes with spectral nulls, comprising the steps of: encoding digital electrical signals constituting user input data into encoded sequences of bits which are input to the channel; preselecting a weighting function which maps each of the encoded sequences, in NRZ or NRZI notation, to an integer value modulo N; interconnecting N Viterbi detectors each having a plurality of trellis states to create a modified Viterbi detector having N times said plurality of trellis states, where each state in the modified detector is associated with a corresponding channel state and a corresponding value of the weighting function; determining the value of N and channel input and detector constraints which ensure that sequences of minimum distance emanating from a common state in the modified detector lead to different detector states; deleting from the modified detector trellis states and/or edges emanating from the trellis states from a trellis to eliminate multiple paths with identical noiseless sample values; and selecting a code which is a subset of nonquasi-catastrophic sequences that correspond to permissible paths through the modified detector.
Claim 20
Dependent Claim
107 words
Apparatus for maximum likelihood detection of a high rate trellis code, comprising: an encoder for encoding sequences of digital electrical signals constituting input data into sequences of coded bits; a partial response channel having a trellis structure and operative to generate a channel response to said sequences of coded bits; and a Viterbi detector constructed by interconnecting N copies of the trellis structure for receiving said channel response, corrupted by noise, and generating as output sequences maximum likelihood estimates of the sequences of the coded bits, and tracking a predetermined attribute of each sequence of coded bits modulo N for increasing minimum distance between said output sequences.
Claim 21
Dependent Claim
107 words
Apparatus for maximum likelihood detection of a high rate trellis code, comprising: an encoder for encoding sequences of digital electrical signals constituting input data into sequences of coded bits; a partial response channel having a trellis structure and operative to generate a channel response to said sequences of coded bits; and a Viterbi detector constructed by interconnecting N copies of the trellis structure for receiving said channel response, corrupted by noise, and generating as output sequences maximum likelihood estimates of the sequences of the coded bits, and tracking a predetermined attribute of each sequence of coded bits modulo N for increasing minimum distance between said output sequences.
Claim 22
Dependent Claim
29 words
The apparatus of claim 17, including: means for time-varying said trellis structure to allow only certain values of said tracked predetermined attribute periodically in time to eliminate quasi-catastrophic sequences.
Claim 23
Independent Claim
28 words
The apparatus of claims 17, wherein: the sequences of coded bits are from sequences of the trellis structure without subsequences that requiring minimum distance decisions by the detector.
Claim 24
Dependent Claim
43 words
The apparatus of claim 17, wherein the trellis structure has trellis sequences which contain a pair of minimum distance subsequences, and including circuitry for prebiasing the detector to favor only one of the subsequences of each pair for use in the trellis code.
Claim 25
Dependent Claim
77 words
The apparatus of claim 17, wherein some of the sequences of coded bits contain a pair of subsequences that require minimum distant decisions by the detector; and the other sequences of coded bits do not contain such subsequences, and including circuitry for prebiasing the detector to favor one of the subsequences in each pair to construct the trellis code by use of a combination of sequences that contain subsequences and those that do not contain said subsequences.
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) | 1996-10-25 | 1997-04-26 | 1997-10-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-10-25 | 2001-04-26 | 2001-10-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-10-25 | 2005-04-26 | 2005-10-26 | $7700.00 | Window Closed / Lapsed |