US5375129A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Maximum likelihood sequence detector
Assignee: Nokia Mobile Phones UK Ltd
•
Filing: 1991-07-16
•
Granted: 1994-12-20
•
Expires: 2011-07-16
Abstract
Abstract A maximum likelihood detector using the Viterbi algorithm for estimating a sequence of data bits received over a communication channel. Depending on the constraint length (C), a plurality of different states is associated with the transmitted bits (e.g. 16 if C=4). The detector comprises various data sources relating respectively to state transition probabilities (branch metrics, previous partial path metrics) and observed values of the received bits. Means are provided for calculating the partial path metrics for each state using values from said data sources. The calculating means comprise a common adder/accumulator for performing repeated additive arithmetic operations and for storing the cumulative result thereof. Multiplexing means are also provided for selectively coupling the data sources in a predetermined order to the adder/accumulator to implement the partial path metric calculation. The architecture is compatible with VLSI techniques and enables the detector to be implemented using minimal semiconductor area. The detector may be used independently as an equaliser or a decoder but in a preferred embodiment both these functions re-use the same common hardware in series enabling both the equaliser and decoder to be implemented in a single integrated circuit (i.e. on one `chip`).
Inventors
- 👤 Andrew Cooper
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 04:35
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/65; H03M13/6502; H03M13/37; H03M13/39; H03M13/3961; H03M13/41; H03M13/4161; H03M13/4169; H04; H04L; H04L25/00; H04L25/02; H04L25/03; H04L25/03006; H04L25/03178; H04L25/03184; H04L25/03197
Claims Analysis
Total Claims: 68
Claim 1
Independent Claim
146 words
A maximum likelihood (ML) detector for estimating a data symbol in a sequence of transmitted data symbols received over a communication channel, wherein a plurality of different states is associated with the transmission of said data symbols, the ML detector comprising: a plurality of data sources relating respectively to state transition probabilities and observed values of received data symbols, and means for calculating partial path metrics for each state using values from said data sources for enabling an estimation of a received data symbol to be accomplished; wherein the calculating means comprise common add/accumulate means having respective inputs from each of said plurality of data sources for performing repeated additive arithmetic operations and for storing a cumulative result thereof, and multiplexing means are provided for selectively coupling said data sources in a predetermined order to said common add/accumulative means to implement a partial path metric calculation.
Claim 2
Dependent Claim
146 words
A maximum likelihood (ML) detector for estimating a data symbol in a sequence of transmitted data symbols received over a communication channel, wherein a plurality of different states is associated with the transmission of said data symbols, the ML detector comprising: a plurality of data sources relating respectively to state transition probabilities and observed values of received data symbols, and means for calculating partial path metrics for each state using values from said data sources for enabling an estimation of a received data symbol to be accomplished; wherein the calculating means comprise common add/accumulate means having respective inputs from each of said plurality of data sources for performing repeated additive arithmetic operations and for storing a cumulative result thereof, and multiplexing means are provided for selectively coupling said data sources in a predetermined order to said common add/accumulative means to implement a partial path metric calculation.
Claim 3
Dependent Claim
31 words
A ML detector as claimed in claim 1, wherein the data sources relating to state transition probabilities include data sources relating respectively to previous partial path metrics and to branch metrics.
Claim 4
Dependent Claim
90 words
A ML detector as claimed in claim 2, including a further data source for outputting terms that represent a characteristic of the communication channel, and means for calculating the branch metrics using values from said further data source and from the data source relating to the observed values of the received data symbols, wherein the branch metric calculating means comprise said common add/accumulate means, the multiplexing means being adapted for selectively coupling said data sources in a predetermined order to said common add/accumulate means to implement the branch metric calculations.
Claim 5
Dependent Claim
21 words
A ML detector as claimed in claim 1, wherein the data sources comprise memory means for storing the state transition probabilities.
Claim 6
Dependent Claim
24 words
A ML detector as claimed in claim 1, wherein the data sources include memory means for storing observed values of the received data symbols.
Claim 7
Dependent Claim
135 words
A ML detector as claimed in claim 1, wherein the predetermined order in which the multiplexing means couples the data sources to the add/accumulate means is such that for each state at a given time a first partial path metric is calculated in respect of a state transition corresponding to the transmission of a first symbol type, and subsequently a second partial path metric is calculated in respect of a state transition corresponding to the transmission of a second symbol type, means being provided for storing said first partial path metric, the detector further including means for comparing the first partial path metric in the storage means and the second partial path metric in the add/accumulate means and for selecting the larger of said first and second partial path metrics for each state in turn.
Claim 8
Dependent Claim
26 words
A ML detector as claimed in claim 6, including memory means for storing the larger of the first and second partial path metrics for each state.
Claim 9
Dependent Claim
39 words
A ML detector as claimed in claim 7, including data symbol storage means for storing for each state either a first or a second symbol depending on which of the first and second partial path metric is the larger.
Claim 10
Dependent Claim
29 words
A ML detector as claimed in claim 8, including means for reading from the data symbol storage means an estimate of the most likely sequence of transmitted data symbols.
Claim 11
Dependent Claim
76 words
A ML detector as claimed in claim 1, wherein the calculating means comprises a first add/accumulate means for calculating for each state in turn a first partial path metric in respect of a state transition corresponding to the transmission of a first symbol type, and a second add/accumulate means for calculating for each state in turn a second partial path metric in respect of a state transition corresponding to the transmission of a second symbol type.
Claim 12
Dependent Claim
21 words
A ML detector as claimed in claim 10, wherein said first and second add/accumulate means are arranged to operate in parallel.
Claim 13
Dependent Claim
43 words
A ML detector as claimed in claim 10, including means for comparing the first and second partial path metrics in said first and second add/accumulate means respectively and for selecting the larger of said first and second partial path metrics for each state.
Claim 14
Dependent Claim
26 words
A ML detector as claimed in claim 12, including memory means for storing the larger of the first and second partial path metrics for each state.
Claim 15
Dependent Claim
39 words
A ML detector as claimed in claim 13, including data symbol storage means for storing for each state either a first or a second symbol depending on which of the first and second partial path metric is the larger.
Claim 16
Dependent Claim
29 words
A ML detector as claimed in claim 14, including means for reading from the data symbol storage means an estimate of the most likely sequence of transmitted data symbols.
Claim 17
Dependent Claim
24 words
A ML detector as claimed in claim 1, including means for generating information indicative of the relative confidence level of each estimated data symbol.
Claim 18
Dependent Claim
152 words
An equalizer for equalising a signal which has become distorted by transmission through a dispersive communications channel, comprising: a maximum likelihood (ML) detector for estimating a data symbol in a sequence of transmitted data symbols received over a communication channel, wherein a plurality of different states is associated with the transmission of said data symbols, the ML detector comprising: a plurality of data sources relating respectively to state transition probabilities and observed values of received data symbols, and means for calculating partial path metrics for each state using values from said data sources, wherein the calculating means comprise common add/accumulate means having respective inputs from each of said plurality of data sources for performing repeated additive arithmetic operations and for storing a cumulative result thereof, and multiplexing means are provided for selectively coupling said data sources in a predetermined order to said common add/accumulate means to implement a partial path metric calculation.
Claim 19
Dependent Claim
152 words
An equalizer for equalising a signal which has become distorted by transmission through a dispersive communications channel, comprising: a maximum likelihood (ML) detector for estimating a data symbol in a sequence of transmitted data symbols received over a communication channel, wherein a plurality of different states is associated with the transmission of said data symbols, the ML detector comprising: a plurality of data sources relating respectively to state transition probabilities and observed values of received data symbols, and means for calculating partial path metrics for each state using values from said data sources, wherein the calculating means comprise common add/accumulate means having respective inputs from each of said plurality of data sources for performing repeated additive arithmetic operations and for storing a cumulative result thereof, and multiplexing means are provided for selectively coupling said data sources in a predetermined order to said common add/accumulate means to implement a partial path metric calculation.
Claim 20
Dependent Claim
30 words
An equaliser as claimed in claim 17, wherein the data sources relating to state transition probabilities include data sources relating respectively to previous partial path metrics and to branch metrics.
Claim 21
Dependent Claim
89 words
An equaliser as claimed in claim 18, including a further data source for outputting terms that represent a characteristic of the communication channel, and means for calculating the branch metrics using values from said further data source and from the data source relating to the observed values of the received data symbols, wherein the branch metric calculating means comprise said common add/accumulate means, the multiplexing means being adapted for selectively coupling said data sources in a predetermined order to said common add/accumulate means to implement the branch metric calculations.
Claim 22
Dependent Claim
20 words
An equaliser as claimed in claim 17, wherein the data sources comprise memory means for storing the state transition probabilities.
Claim 23
Dependent Claim
23 words
An equaliser as claimed in claim 17, wherein the data sources include memory means for storing observed values of the received data symbols.
Claim 24
Dependent Claim
134 words
An equaliser as claimed in claim 17, wherein the predetermined order in which the multiplexing means couples the data sources to the add/accumulate means is such that for each state at a given time a first partial path metric is calculated in respect of a state transition corresponding to the transmission of a first symbol type, and subsequently a second partial path metric is calculated in respect of a state transition corresponding to the transmission of a second symbol type, means being provided for storing said first partial path metric, the detector further including means for comparing the first partial path metric in the storage means and the second partial path metric in the add/accumulate means and for selecting the larger of said first and second partial path metrics for each state in turn.
Claim 25
Dependent Claim
25 words
An equaliser as claimed in claim 22, including memory means for storing the larger of the first and second partial path metrics for each state.
Claim 26
Dependent Claim
38 words
An equaliser as claimed in claim 23, including data symbol storage means for storing for each state either a first or a second symbol depending on which of the first and second partial path metric is the larger.
Claim 27
Dependent Claim
28 words
An equaliser as claimed in claim 24, including means for reading from the data symbol storage means an estimate of the most likely sequence of transmitted data symbols.
Claim 28
Dependent Claim
75 words
An equaliser as claimed in claim 17, wherein the calculating means comprises a first add/accumulate means for calculating for each state in turn a first partial path metric in respect of a state transition corresponding to the transmission of a first symbol type, and a second add/accumulate means for calculating for each state in turn a second partial path metric in respect of a state transition corresponding to the transmission of a second symbol type.
Claim 29
Dependent Claim
20 words
An equaliser as claimed in claim 26, wherein said first and second add/accumulate means are arranged to operate in parallel.
Claim 30
Dependent Claim
42 words
An equaliser as claimed in claim 26, including means for comparing the first and second partial path metrics in said first and second add/accumulate means respectively and for selecting the larger of said first and second partial path metrics for each state.
Claim 31
Dependent Claim
25 words
An equaliser as claimed in claim 28, including memory means for storing the larger of the first and second partial path metrics for each state.
Claim 32
Dependent Claim
38 words
An equaliser as claimed in claim 29, including data symbol storage means for storing for each state either a first or a second symbol depending on which of the first and second partial path metric is the larger.
Claim 33
Dependent Claim
28 words
An equaliser as claimed in claim 30, including means for reading from the data symbol storage means an estimate of the most likely sequence of transmitted data symbols.
Claim 34
Dependent Claim
23 words
An equaliser as claimed in claim 17, including means for generating information indicative of the relative confidence level of each estimated data symbol.
Claim 35
Dependent Claim
164 words
A decoding arrangement for decoding a convolutionally encoded data signal, comprising: a maximum likelihood (ML) detector for estimating a data symbol in a sequence of transmitted data symbols received over a communication channel, wherein a plurality of different states is associated with the transmission of said data symbols, the ML detector comprising: a plurality of data sources relating respectively to state transition probabilities and observed values of received data symbols, and means for calculating partial path metrics for each state using values from said data sources for enabling an estimation of a received data symbol to be accomplished for decoding a convolutionally encoded data symbol, wherein the calculating means comprise common add/accumulate means having respective inputs from each of said plurality of data sources for performing repeated additive arithmetic operations and for storing a cumulative result thereof, and multiplexing means are provided for selectively coupling said data sources in a predetermined order to said common add/accumulate means to implement a partial path metric calculation.
Claim 36
Dependent Claim
164 words
A decoding arrangement for decoding a convolutionally encoded data signal, comprising: a maximum likelihood (ML) detector for estimating a data symbol in a sequence of transmitted data symbols received over a communication channel, wherein a plurality of different states is associated with the transmission of said data symbols, the ML detector comprising: a plurality of data sources relating respectively to state transition probabilities and observed values of received data symbols, and means for calculating partial path metrics for each state using values from said data sources for enabling an estimation of a received data symbol to be accomplished for decoding a convolutionally encoded data symbol, wherein the calculating means comprise common add/accumulate means having respective inputs from each of said plurality of data sources for performing repeated additive arithmetic operations and for storing a cumulative result thereof, and multiplexing means are provided for selectively coupling said data sources in a predetermined order to said common add/accumulate means to implement a partial path metric calculation.
Claim 37
Dependent Claim
31 words
A decoding arrangement as claimed in claim 33, wherein the data sources relating to state transition probabilities include data sources relating respectively to previous partial path metrics and to branch metrics.
Claim 38
Dependent Claim
90 words
A decoding arrangement as claimed in claim 34, including a further data source for outputting terms that represent a characteristic of the communication channel, and means for calculating the branch metrics using values from said further data source and from the data source relating to the observed values of the received data symbols, wherein the branch metric calculating means comprise said common add/accumulate means, the multiplexing means being adapted for selectively coupling said data sources in a predetermined order to said common add/accumulate means to implement the branch metric calculations.
Claim 39
Dependent Claim
21 words
A decoding arrangement as claimed in claim 33, wherein the data sources comprise memory means for storing the state transition probabilities.
Claim 40
Dependent Claim
24 words
A decoding arrangement as claimed in claim 33, wherein the data sources include memory means for storing observed values of the received data symbols.
Claim 41
Dependent Claim
135 words
A decoding arrangement as claimed in claim 33, wherein the predetermined order in which the multiplexing means couples the data sources to the add/accumulate means is such that for each state at a given time a first partial path metric is calculated in respect of a state transition corresponding to the transmission of a first symbol type, and subsequently a second partial path metric is calculated in respect of a state transition corresponding to the transmission of a second symbol type, means being provided for storing said first partial path metric, the detector further including means for comparing the first partial path metric in the storage means and the second partial path metric in the add/accumulate means and for selecting the larger of said first and second partial path metrics for each state in turn.
Claim 42
Dependent Claim
26 words
A decoding arrangement as claimed in claim 38, including memory means for storing the larger of the first and second partial path metrics for each state.
Claim 43
Dependent Claim
39 words
A decoding arrangement as claimed in claim 39, including data symbol storage means for storing for each state either a first or a second symbol depending on which of the first and second partial path metric is the larger.
Claim 44
Dependent Claim
29 words
A decoding arrangement as claimed in claim 40, including means for reading from the data symbol storage means an estimate of the most likely sequence of transmitted data symbols.
Claim 45
Dependent Claim
76 words
A decoding arrangement as claimed in claim 33, wherein the calculating means comprises a first add/accumulate means for calculating for each state in turn a first partial path metric in respect of a state transition corresponding to the transmission of a first symbol type, and a second add/accumulate means for calculating for each state in turn a second partial path metric in respect of a state transition corresponding to the transmission of a second symbol type.
Claim 46
Dependent Claim
21 words
A decoding arrangement as claimed in claim 42, wherein said first and second add/accumulate means are arranged to operate in parallel.
Claim 47
Dependent Claim
43 words
A decoding arrangement as claimed in claim 42, including means for comparing the first and second partial path metrics in said first and second add/accumulate means respectively and for selecting the larger of said first and second partial path metrics for each state.
Claim 48
Dependent Claim
26 words
A decoding arrangement as claimed in claim 44, including memory means for storing the larger of the first and second partial path metrics for each state.
Claim 49
Dependent Claim
39 words
A decoding arrangement as claimed in claim 45, including data symbol storage means for storing for each state either a first or a second symbol depending on which of the first and second partial path metric is the larger.
Claim 50
Dependent Claim
29 words
A decoding arrangement as claimed in claim 46, including means for reading from the data symbol storage means an estimate of the most likely sequence of transmitted data symbols.
Claim 51
Dependent Claim
24 words
A decoding arrangement as claimed in claim 33, including means for generating information indicative of the relative confidence level of each estimated data symbol.
Claim 52
Dependent Claim
182 words
An arrangement for receiving a convolutionally encoded signal transmitted over a dispersive communications channel, comprising: equalising means having an input for receiving the convolutionally encoded signal for equalising the convolutionally encoded signal; and decoding means for subsequently decoding the equalised convolutionally encoded signal, wherein the equalising means and the decoding means are each comprised of a same maximum likelihood (ML) detector that is utilized by both the equalising means and decoding means for estimating received data symbols in the received convolutionally encoded signal, wherein the common ML detector comprises: a plurality of data sources relating respectively to state transition probabilities and observed values of the received data symbols, and means for calculating partial path metrics for each state using values from said data sources, wherein the calculating means comprise common add/accumulate means having respective inputs from each of said plurality of data sources for performing repeated additive arithmetic operations and for storing a cumulative result thereof, and multiplexing means for provided for selectively coupling said data sources in a predetermined order to said add/accumulate means to implement a partial path metric calculation.
Claim 53
Dependent Claim
182 words
An arrangement for receiving a convolutionally encoded signal transmitted over a dispersive communications channel, comprising: equalising means having an input for receiving the convolutionally encoded signal for equalising the convolutionally encoded signal; and decoding means for subsequently decoding the equalised convolutionally encoded signal, wherein the equalising means and the decoding means are each comprised of a same maximum likelihood (ML) detector that is utilized by both the equalising means and decoding means for estimating received data symbols in the received convolutionally encoded signal, wherein the common ML detector comprises: a plurality of data sources relating respectively to state transition probabilities and observed values of the received data symbols, and means for calculating partial path metrics for each state using values from said data sources, wherein the calculating means comprise common add/accumulate means having respective inputs from each of said plurality of data sources for performing repeated additive arithmetic operations and for storing a cumulative result thereof, and multiplexing means for provided for selectively coupling said data sources in a predetermined order to said add/accumulate means to implement a partial path metric calculation.
Claim 54
Dependent Claim
36 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 49, wherein the data sources relating to state transition probabilities include data sources relating respectively to previous partial path metrics and to branch metrics.
Claim 55
Dependent Claim
95 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 50, including a further data source for outputting terms that represent a characteristic of the communication channel, and means for calculating the branch metrics using values from said further data source and from the data source relating to the observed values of the received data symbols, wherein the branch metric calculating means comprise said common add/accumulate means, the multiplexing means being adapted for selectively coupling said data sources in a predetermined order to said common add/accumulate means to implement the branch metric calculations.
Claim 56
Dependent Claim
26 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 49, wherein the data sources comprise memory means for storing the state transition probabilities.
Claim 57
Dependent Claim
29 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 49, wherein the data sources include memory means for storing observed values of the received data symbols.
Claim 58
Dependent Claim
140 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 49, wherein the predetermined order in which the multiplexing means couples the data sources to the add/accumulate means is such that for each state at a given time a first partial path metric is calculated in respect of a state transition corresponding to the transmission of a first symbol type, and subsequently a second partial path metric is calculated in respect of a state transition corresponding to the transmission of a second symbol type, means being provided for storing said first partial path metric, the detector further including means for comparing the first partial path metric in the storage means and the second partial path metric in the add/accumulate means and for selecting the larger of said first and second partial path metrics for each state in turn.
Claim 59
Dependent Claim
31 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 54, including memory means for storing the larger of the first and second partial path metrics for each state.
Claim 60
Dependent Claim
44 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 55, including data symbol storage means for storing for each state either a first or a second symbol depending on which of the first and second partial path metric is the larger.
Claim 61
Dependent Claim
34 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 56, including means for reading from the data symbol storage means an estimate of the most likely sequence of transmitted data symbols.
Claim 62
Dependent Claim
81 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 49, wherein the calculating means comprises a first add/accumulate means for calculating for each state in turn a first partial path metric in respect of a state transition corresponding to the transmission of a first symbol type, and a second add/accumulate means for calculating for each state in turn a second partial path metric in respect of a state transition corresponding to the transmission of a second symbol type.
Claim 63
Dependent Claim
26 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 58, wherein said first and second add/accumulate means are arranged to operate in parallel.
Claim 64
Dependent Claim
48 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 58, including means for comparing the first and second partial path metrics in said first and second add/accumulate means respectively and for selecting the larger of said first and second partial path metrics for each state.
Claim 65
Dependent Claim
31 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 60, including memory means for storing the larger of the first and second partial path metrics for each state.
Claim 66
Dependent Claim
44 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 61, including data symbol storage means for storing for each state either a first or a second symbol depending on which of the first and second partial path metric is the larger.
Claim 67
Dependent Claim
34 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 62, including means for reading from the data symbol storage means an estimate of the most likely sequence of transmitted data symbols.
Claim 68
Dependent Claim
29 words
An arrangement for receiving a convolutionally encoded signal as claimed in claim 49, including means for generating information indicative of the relative confidence level of each estimated data symbol.
References Cited (Backward Citations)
GB1478736A
Cited
US4675871A
Cited
US4573155A
Cited
US4730322A
Cited
US4797887A
Cited
US4805174A
Cited
US4847871A
Cited
US4932029A
Cited
EP0302330A2
Cited
US4945538A
Cited
EP0398690A2
Cited
US4941154A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-12-19 | 1998-06-20 | 1998-12-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-12-19 | 2002-06-20 | 2002-12-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-12-19 | 2006-06-20 | 2006-12-20 | $7700.00 | Window Closed / Lapsed |