US5136593A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for fixed delay tree search
Assignee: Carnegie Mellon University
•
Filing: 1989-10-30
•
Granted: 1992-08-04
•
Expires: 2009-10-30
Abstract
Abstract A method for identifying a signal subject to intersymbol interference comprising the steps of receiving tau +1 samples of the signal where tau is greater than or equal to one; searching a tree representation of known values to determine the path of the branch of the tree which most closely corresponds to the tau +1 samples of the signal; and releasing the symbol of the first metric of the determined branch. The released symbol is the identity of the sample. Preferably, the receiving step includes the step of receiving tau +1 sequential samples, with each sample corresponding to a unique portion of the signal, and the searching step includes the step of comparing each symbol of each metric of each path of each branch with the symbol's corresponding sample in regard to time. An apparatus for identifying a signal subject to intersymbol interference comprising a device for implementing a fixed delay tree search on samples of the signal to determine a symbol associated with a given sample and then releasing that sample. The apparatus also is comprised of a device for inputting samples to the implementing a device.
Inventors
- 👤 Jaekyun J. Moon
- 👤 L. Richard Carley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 04:13
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/37; H03M13/39; H04; H04L; H04L25/00; H04L25/02; H04L25/03; H04L25/03006; H04L25/03178; H04L25/03312; H04L25/03324; H04L25/03203; H04L25/03248; H04L25/03299
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
147 words
A method for identifying signals subject to intersymbol interference comprising the step of: receiving τ+1 samples of the signals where τ≧1; and computer implemented steps of: forming a tree representation of known responses such that a symbol of each metric of the tree is predetermined by the symbol's position in the tree representation of known responses and the symbol associated with each metric is identified from the sumbol's position, in the tree representation of known responses without the symbol having to be stored in memory, said symbol is representative of a predetermined value and is a digital signal; searching the tree representation of known responses to determine a path of a branch of the tree which most closely corresponds to the τ+1 samples of the signals; and releasing the symbol of a first metric of a determined branch, said symbol being an identity of a first sample.
Claim 2
Independent Claim
147 words
A method for identifying signals subject to intersymbol interference comprising the step of: receiving τ+1 samples of the signals where τ≧1; and computer implemented steps of: forming a tree representation of known responses such that a symbol of each metric of the tree is predetermined by the symbol's position in the tree representation of known responses and the symbol associated with each metric is identified from the sumbol's position, in the tree representation of known responses without the symbol having to be stored in memory, said symbol is representative of a predetermined value and is a digital signal; searching the tree representation of known responses to determine a path of a branch of the tree which most closely corresponds to the τ+1 samples of the signals; and releasing the symbol of a first metric of a determined branch, said symbol being an identity of a first sample.
Claim 3
Dependent Claim
30 words
A method as described in claim 1 wherein the receiving step includes the step of receiving τ+1 sequential samples, with each sample corresponding to a unique portion of the signals.
Claim 4
Dependent Claim
36 words
A method as described in claim 2 wherein the searching step includes the step of comparing each symbol of each metric of each pair of each branch with each symbol's corresponding sample in regard to time.
Claim 5
Dependent Claim
27 words
A method as described in claim 3 including before the searching step the step of forming the tree representation without paths that violate any run-length limited constraints.
Claim 6
Dependent Claim
35 words
A method as described in claim 4 including after the releasing step the step of repeating with each next in time sample the searching and releasing steps until there is no sample left to release.
Claim 7
Dependent Claim
49 words
A method as described in claim 5 including after a releasing step the steps of discarding an unused branch without having to store and examine the symbol associated with an initial metric of each path of each branch, and extending each path of an surviving branch by one metric.
Claim 8
Dependent Claim
83 words
A method as described in claim 6 including before the repeating step, the step of adjusting the signals by an amount corresponding to a difference between a value of the symbol of a released metric and an actual value of the sample associated with the released metric such that the value of the next in time sample more closely approximates the value of the symbol which identified the next in time sample then the value of the sample associated with the released metric.
Claim 9
Independent Claim
123 words
An apparatus for identifying a signal subject to intersymbol interference comprising: means for implementing a fixed delay tree search on samples of the signal to determine a symbol associated with a given sample and then releasing that symbol; means for inputting samples to the implementing means; and a feedback filter which receives the symbol released from the implementing means and produces a correction factor corresponding to a difference between a value of the released symbol and an actual value of a sample associated with the released symbol such that a value of a next in time sample more closely approximates a value of the symbol which identifies the next in time sample then the value of the sample associated with the released metric.
Claim 10
Independent Claim
123 words
An apparatus for identifying a signal subject to intersymbol interference comprising: means for implementing a fixed delay tree search on samples of the signal to determine a symbol associated with a given sample and then releasing that symbol; means for inputting samples to the implementing means; and a feedback filter which receives the symbol released from the implementing means and produces a correction factor corresponding to a difference between a value of the released symbol and an actual value of a sample associated with the released symbol such that a value of a next in time sample more closely approximates a value of the symbol which identifies the next in time sample then the value of the sample associated with the released metric.
Claim 11
Dependent Claim
21 words
An apparatus as described in claim 8 wherein the implementing means includes a computer having a fixed delay tree search program.
Claim 12
Dependent Claim
159 words
An apparatus as described in claim 9 wherein the program comprises the steps of: forming a tree representation of known responses such that a symbol of each metric of the tree is predetermined by the symbol's position in the tree representation of known responses and the symbol associated with each metric is identified from the symbol's position in the tree representation of known responses without the symbol having to be stored in memory, said symbol is representative of a predetermined value and is a digital signal; searching the tree representation of known responses to determine a path of a branch of the tree which most closely corresponds to τ+1 samples of the signals where τ≧1; and releasing the symbol of a first metric of a determined branch, said symbol being an identity of a first sample wherein the receiving step includes the step of receiving τ+1 sequential samples, with each sample corresponding to a unique portion of the signals.
Claim 13
Dependent Claim
36 words
A method as described in claim 10 wherein the searching step includes the step of comparing each symbol of each metric of each path of each branch with each symbol's corresponding sample in regard to time.
Claim 14
Dependent Claim
27 words
A method as described in claim 11 including before the searching step the step of forming the tree representation without paths that violate any run-length limited constraints.
Claim 15
Dependent Claim
35 words
A method as described in claim 12 including after the releasing step the step of repeating with each next in time sample the searching and releasing steps until there is no sample left to release.
Claim 16
Dependent Claim
49 words
A method as described in claim 13 including after the releasing step the steps of discarding an unused branch without having to store and examine the symbol associated with an initial metric of each path of each branch, and extending each path of the surviving branch by one metric.
Claim 17
Dependent Claim
83 words
A method as described in claim 14 including before the repeating step, the step of adjusting the signals by an amount corresponding to a difference between a value of the symbol of a released metric and an actual value of the sample associated with the released metric such that the value of the next in time sample more closely approximates the value of the symbol which identifies the next in time sample then the value of the sample associated with the released metric.
References Cited (Backward Citations)
US4015238A
Cited
US4536878A
Cited
US4706211A
Cited
US4606027A
Cited
US4614933A
Cited
US4669084A
Cited
US4797887A
Cited
US4805174A
Cited
US4748626A
Cited
US4847871A
Cited
US4910669A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-08-04 | 1996-02-03 | 1996-08-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-08-04 | 2000-02-03 | 2000-08-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-08-04 | 2004-02-03 | 2004-08-04 | $7700.00 | Window Closed / Lapsed |