US5987638A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for computing the result of a viterbi equation in a single cycle
Assignee: LSI Corp
•
Filing: 1997-04-22
•
Granted: 1999-11-16
•
Expires: 2017-04-22
Abstract
Abstract A Viterbi calculator performs additions in parallel with comparison to compute the result of a single Viterbi equation in a single clock cycle. Therefore, the results of a butterfly operation involving two Viterbi equations can be computed in a single clock cycle by use of two Viterbi calculators. Alternatively, the butterfly operation can be implemented by a single Viterbi calculator used in a pipelined manner, although the throughput is at the rate of every two clock cycles. When a single Viterbi calculator is used in the pipelined manner, two multiplexers are used to alternately swap the constant values being supplied to the Viterbi calculator. The pipelined use of a single Viterbi calculator requires less space on an integrated circuit die than the parallel use of two Viterbi calculators, and is useful in applications where the variable data is available every two clock cycles (e.g. due to latency in accessing memory).
Inventors
- 👤 Robert K. Yu
- 👤 Satish Padmanabhan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 14:31
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/65; H03M13/6502; H03M13/37; H03M13/39; H03M13/41; H03M13/4107
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
231 words
An apparatus for performing a Viterbi computation, said apparatus comprising a first device, said first device having: a first variable bus, a second variable bus, a first constant bus, and a second constant bus for carrying signals of values pi {n}, pj {n}, ri and rj, said first device comprising: a sums generator having four input buses and two groups of terminals, each input bus being directly connected to one of said first variable bus, said second variable bus, said first constant bus and said second constant bus, wherein said sums generator generates a first sum signal of value pi{n}+ri at a first group of terminals, and a second sum signal of value pi{n}+rj at a second group of terminals; a parallel selector having four input buses and an output terminal, said four input buses of said parallel selector being directly connected to said four input buses of said sums generator; and a multiplexer having two input buses, a control line and a group of output terminals, said two input buses of said multiplexer being connected to said two groups of terminals of said sums generator, said control line being connected to said output terminal of said parallel selector; wherein: said multiplexer responds to a signal on said control line by selectively coupling one of said two input buses of said multiplexer to said group of output terminals of said multiplexer.
Claim 2
Independent Claim
231 words
An apparatus for performing a Viterbi computation, said apparatus comprising a first device, said first device having: a first variable bus, a second variable bus, a first constant bus, and a second constant bus for carrying signals of values pi {n}, pj {n}, ri and rj, said first device comprising: a sums generator having four input buses and two groups of terminals, each input bus being directly connected to one of said first variable bus, said second variable bus, said first constant bus and said second constant bus, wherein said sums generator generates a first sum signal of value pi{n}+ri at a first group of terminals, and a second sum signal of value pi{n}+rj at a second group of terminals; a parallel selector having four input buses and an output terminal, said four input buses of said parallel selector being directly connected to said four input buses of said sums generator; and a multiplexer having two input buses, a control line and a group of output terminals, said two input buses of said multiplexer being connected to said two groups of terminals of said sums generator, said control line being connected to said output terminal of said parallel selector; wherein: said multiplexer responds to a signal on said control line by selectively coupling one of said two input buses of said multiplexer to said group of output terminals of said multiplexer.
Claim 3
Dependent Claim
81 words
The apparatus of claim 1 wherein said sums generator includes two full adders, a first full adder being coupled to receive signals from said first variable bus and said first constant bus thereby to supply a signal of value pi{n}+ri at said first group of terminals, and said second full adder being coupled to receive signals from said second variable bus and said second constant bus thereby to supply a signal of value pj {n}+rj at said second group of terminals.
Claim 4
Dependent Claim
64 words
The apparatus of claim 1 wherein said parallel selector includes: a plurality of 4:2 adders coupled to said four input buses of said parallel selector; and a carry chain having an output line and a plurality of input terminals, said output line being coupled to said output terminal of said parallel selector and said input terminals being coupled to said row of 4:2 adders.
Claim 5
Dependent Claim
39 words
The apparatus of claim 3 wherein said parallel selector further comprises a plurality of inverters, at least a group of said 4:2 adders being coupled through said inverters to two of said four input buses of said parallel selector.
Claim 6
Dependent Claim
79 words
The apparatus of claim 1 further comprising a second device identical to said first device, wherein said first variable buses of each of said devices are coupled together, said second variable buses of each of said devices are coupled together, said first constant bus of said first device is coupled to said second constant bus of said second device and said second constant bus of said first device is coupled to said first constant bus of said second device.
Claim 7
Dependent Claim
42 words
The apparatus of claim 1 further comprising two multiplexers, a first multiplexer having a first group of output terminals coupled to said first constant bus and said second multiplexer having a second group of output terminals coupled to said second constant bus.
Claim 8
Independent Claim
93 words
A method for performing a Viterbi computation using signals of values pi{n}, pj{n}, ri and rj, said method comprising: generating a first sum signal of value pi{n}+ri, and a second sum signal of value pj{n}+rj using said signals of values pi{n}, pj{n}, ri and rj; generating a selection signal using said signals of values pi{n}, pj{n}, ri and rj, said selection signal indicating the minimum of said first sum signal and said second sum signal; and selecting the minimum of said first sum signal and said second sum signal using the selection signal.
Claim 9
Independent Claim
93 words
A method for performing a Viterbi computation using signals of values pi{n}, pj{n}, ri and rj, said method comprising: generating a first sum signal of value pi{n}+ri, and a second sum signal of value pj{n}+rj using said signals of values pi{n}, pj{n}, ri and rj; generating a selection signal using said signals of values pi{n}, pj{n}, ri and rj, said selection signal indicating the minimum of said first sum signal and said second sum signal; and selecting the minimum of said first sum signal and said second sum signal using the selection signal.
Claim 10
Dependent Claim
29 words
The method of claim 7 wherein said generating of selection signal comprises: computing the value pi{n}+ri-pj{n}-rj; and passing a carry signal generated during said computing as the selection signal.
Claim 11
Dependent Claim
35 words
The method of claim 7 wherein each of said generatings, and said selecting are included in a current cycle, said method further comprising: storing an output signal from a previous cycle during said current cycle.
Claim 12
Independent Claim
171 words
A method for performing a Viterbi computation using signals of values pi{n}, pj{n}, ri and rj, said method comprising: generating a first sum signal of value pi{n}+ri, and a second sum signal of value pj{n}+rj using said signals of values pi{n}, pj{n}, ri and rj; simultaneously generating a selection signal using said signals of values pi{n}, pj{n}, ri and rj, said selection signal indicating the minimum of said first sum signal and said second sum signal; and selecting the minimum of said first sum signal and said second sum signal using the selection signal; wherein said generating, said simultaneous generating and said selecting are included in a current cycle, said method further comprising storing an output signal from a previous cycle during said current cycle; and wherein said signals of values ri and rj are supplied to two buses of a single device implementing said cycle, said method further comprising alternately swapping between supplying signals of values ri and rj or signals of values rj and ri to said two buses.
Claim 13
Independent Claim
171 words
A method for performing a Viterbi computation using signals of values pi{n}, pj{n}, ri and rj, said method comprising: generating a first sum signal of value pi{n}+ri, and a second sum signal of value pj{n}+rj using said signals of values pi{n}, pj{n}, ri and rj; simultaneously generating a selection signal using said signals of values pi{n}, pj{n}, ri and rj, said selection signal indicating the minimum of said first sum signal and said second sum signal; and selecting the minimum of said first sum signal and said second sum signal using the selection signal; wherein said generating, said simultaneous generating and said selecting are included in a current cycle, said method further comprising storing an output signal from a previous cycle during said current cycle; and wherein said signals of values ri and rj are supplied to two buses of a single device implementing said cycle, said method further comprising alternately swapping between supplying signals of values ri and rj or signals of values rj and ri to said two buses.
Claim 14
Independent Claim
114 words
A method for performing a Viterbi computation using signals of values pi{n}, pj{n}, ri and rj, said method comprising: generating a first sum signal of value pi{n}+ri, and a second sum signal of value pj{n}+rj using said signals of values pi{n}, pj{n}, ri and rj; simultaneously generating a selection signal using said signals of values pi{n}, pj{n}, ri and rj, said selection signal indicating the minimum of said first sum signal and said second sum signal; selecting the minimum of said first sum signal and said second sum signal using the selection signal; and retrieving the signals of values pi{n+1} and pj{n+1} during said current cycle and a next cycle following said current cycle.
Claim 15
Independent Claim
114 words
A method for performing a Viterbi computation using signals of values pi{n}, pj{n}, ri and rj, said method comprising: generating a first sum signal of value pi{n}+ri, and a second sum signal of value pj{n}+rj using said signals of values pi{n}, pj{n}, ri and rj; simultaneously generating a selection signal using said signals of values pi{n}, pj{n}, ri and rj, said selection signal indicating the minimum of said first sum signal and said second sum signal; selecting the minimum of said first sum signal and said second sum signal using the selection signal; and retrieving the signals of values pi{n+1} and pj{n+1} during said current cycle and a next cycle following said current cycle.
Claim 16
Dependent Claim
23 words
The method of claim 11 further comprising: retrieving the signals of values ri and rj during said current cycle and said next cycle.
Claim 17
Independent Claim
120 words
A method for performing a Viterbi computation using signals of values pi{n}, pj{n}, ri and rj, said method comprising: generating a first sum signal of value pi{n}+ri, and a second sum signal of value pj{n}+rj using said signals of values pi{n}, pj{n}, ri and rj; simultaneously generating a selection signal using said signals of values pi{n}, pj{n}, ri and rj, said selection signal indicating the minimum of said first sum signal and said second sum signal; selecting the minimum of said first sum signal and said second sum signal using the selection signal; and generating a third sum signal of value pi{n}+rj, and a fourth sum signal of value pj{n}+ri using said signals of values pi{n}, pj{n}, ri and rj.
Claim 18
Independent Claim
120 words
A method for performing a Viterbi computation using signals of values pi{n}, pj{n}, ri and rj, said method comprising: generating a first sum signal of value pi{n}+ri, and a second sum signal of value pj{n}+rj using said signals of values pi{n}, pj{n}, ri and rj; simultaneously generating a selection signal using said signals of values pi{n}, pj{n}, ri and rj, said selection signal indicating the minimum of said first sum signal and said second sum signal; selecting the minimum of said first sum signal and said second sum signal using the selection signal; and generating a third sum signal of value pi{n}+rj, and a fourth sum signal of value pj{n}+ri using said signals of values pi{n}, pj{n}, ri and rj.
Claim 19
Dependent Claim
12 words
The method of claim 13, wherein: said sum signals are generated simultaneously.
Claim 20
Dependent Claim
40 words
The method of claim 13, wherein: said third sum signal and said fourth sum signal are generated in a next cycle following a current cycle, said first sum signal and said second sum signal are generated in said current cycle.
Claim 21
Dependent Claim
33 words
The method of claim 10 further comprising: generating a third sum signal of value pi{n}+rj, and a fourth sum signal of value pj{n}+ri using said signals of values pi{n}, pj{n}, ri and rj.
Claim 22
Dependent Claim
33 words
The method of claim 11 further comprising: generating a third sum signal of value pi{n}+rj, and a fourth sum signal of value pj{n}+ri using said signals of values pi{n}, pj{n}, ri and rj.
Claim 23
Dependent Claim
17 words
The method of claim 7 wherein: each of said sum signals are generated simultaneous with each other.
References Cited (Backward Citations)
US4614933A
Cited
US5027374A
Cited
US5220570A
Cited
US5502736A
Cited
US5491705A
Cited
US5509020A
Cited
US5504784A
Cited
US5539757A
Cited
JPH07273670A
Cited
US5815515A
Cited
US5781569A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-15 | 2003-05-17 | 2003-11-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-15 | 2007-05-17 | 2007-11-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-15 | 2011-05-17 | 2011-11-16 | $7700.00 | Window Closed / Lapsed |