US5970104A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for generating branch metrics and branch indices for convolutional code Viterbi decoders
Assignee: Cadence Design Systems Inc
•
Filing: 1997-03-19
•
Granted: 1999-10-19
•
Expires: 2017-03-19
Abstract
Abstract A Viterbi decoder generates a branch metric table from first and second data signals taken at two sample times and provides selected branch metrics to an add/compare/select circuit in response to branch indices from a branch index generator. The branch metrics in the branch metric table are the sixteen combinations of the sum of the first and second parallel data signals at first and second sample times and the inverse of such signals. The branch index generator generates the branch indices in response to a received state from the add/compare/select circuit, convolutional code polynomials and the possible states of a radix-4 trellis. The add/compare/select generates a survivor path decision based on the selected branch metrics.
Inventors
- 👤 Yan Zhong
- 👤 Lin Yang
- 👤 Manouchehr Rafie
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 04:07
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/004; H04L1/0045; H04L1/0054; H03; H03M; H03M13/00; H03M13/37; H03M13/39; H03M13/395; H03M13/41; H03M13/4107; H03M13/65; H03M13/6508; H03M13/6561
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
123 words
A method for generating branch metric indices for Viterbi decoding, the method comprising: generating states of an encoder at selected first and second times; generating branch indices and generator polynomials in response to the states of the encoder at each of the first and second times; generating first and second parallel data signals in response to data received at the selected first and second times, respectively; generating a branch metric in response to the branch indices by: generating a branch metric table, including table elements representing a sum of the first and second parallel data signals and the inverses of the first and second data signals; and retrieving from the branch table a branch metric corresponding to at least one generated branch metric.
Claim 2
Independent Claim
123 words
A method for generating branch metric indices for Viterbi decoding, the method comprising: generating states of an encoder at selected first and second times; generating branch indices and generator polynomials in response to the states of the encoder at each of the first and second times; generating first and second parallel data signals in response to data received at the selected first and second times, respectively; generating a branch metric in response to the branch indices by: generating a branch metric table, including table elements representing a sum of the first and second parallel data signals and the inverses of the first and second data signals; and retrieving from the branch table a branch metric corresponding to at least one generated branch metric.
Claim 3
Dependent Claim
25 words
The method of claim 1, further comprising generating output data as a convolution of said generated first and second data signals and said generator polynomials.
Claim 4
Dependent Claim
159 words
A Viterbi decoder comprising: a branch index generator for generating a plurality of branch indices, each branch index corresponding to a branch transitions between a first plurality of states and a second plurality of states indicative of received data and to convolutional code polynomials; a branch metric table for receiving and storing branch metrics indicative of received data at selected first and second times, the branch metric table including sixteen elements, with each element corresponding to combinations of a sum of (i) the first and second parallel data signals at the first and second times and (ii) inverses of the first and second parallel data signals at the first and second times; and a selection circuit coupled to the branch metric table for selecting, for each one of the first plurality of states, a corresponding one of the second plurality of states in response to the branch indices corresponding to the each one of the first plurality of states.
Claim 5
Dependent Claim
159 words
A Viterbi decoder comprising: a branch index generator for generating a plurality of branch indices, each branch index corresponding to a branch transitions between a first plurality of states and a second plurality of states indicative of received data and to convolutional code polynomials; a branch metric table for receiving and storing branch metrics indicative of received data at selected first and second times, the branch metric table including sixteen elements, with each element corresponding to combinations of a sum of (i) the first and second parallel data signals at the first and second times and (ii) inverses of the first and second parallel data signals at the first and second times; and a selection circuit coupled to the branch metric table for selecting, for each one of the first plurality of states, a corresponding one of the second plurality of states in response to the branch indices corresponding to the each one of the first plurality of states.
Claim 6
Dependent Claim
31 words
The Viterbi decoder of claim 3, further comprising a state generator for generating said first and second pluralities of states indicative of received data at said respective first and second times.
Claim 7
Dependent Claim
26 words
The Viterbi decoder of claim 4, wherein said state generator includes a shift register that provides state signals indicative of shifted bits of said received data.
Claim 8
Dependent Claim
106 words
The Viterbi decoder of claim 3, wherein said first plurality of states is defined as S.sup.(n) =(b2 b1 S.sub.L-2.sup.(n+2) S.sub.L-3.sup.(n+2) . . . S.sub.3.sup.(n+2) S.sub.2.sup.(n+2)), said second plurality of states is defined as S.sup.(n) =(S.sub.L-2.sup.(n+2) S.sub.L-3.sup.(n+2) . . . S.sub.1.sup.(n+2) S.sub.0.sup.(n+2)), said branch metric, denoted bi {S.sup.(n+2) ] [b1 b2], is defined as bi[S(n+2)) [b1 b2]=v.sub.1.sup.(n+1) |v.sub.0.sup.(n+1) |v.sub.1.sup.(n) |v.sub.0.sup.(n), said branch metric indices v 0 .sup.(n+1), v 1 .sup.(n+1), v 0 .sup.(n), v 1 .sup.(n) are defined by ##EQU1## and said convolutional code polynomials are defined as g.sup.(1) =(g.sub.0.sup.(1) g.sub.1.sup.(1) . . . g.sub.L-3.sup.(1) g.sub.L-2.sup.(1) g.sub.L-1.sup.(1)), g.sup.(2) =(g.sub.0.sup.(2) g.sub.1.sup.(2) . . . g.sub.L-3.sup.(2) g.sub.L-2.sup.(2) g.sub.L-1.sup.(2)). 7.
Claim 9
Dependent Claim
51 words
The Viterbi decoder of claim 3, wherein said branch index generator comprises: a shift register for shifting said received data at said respective first and second times; and a metric index generator for generating selected metric indices in response to said states from the shift register and said convolutional code polynomials.
References Cited (Backward Citations)
US4536878A
Cited
US4757506A
Cited
US4748626A
Cited
US5594742A
Cited
US5390198A
Cited
US5742622A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-10-18 | 2003-04-19 | 2003-10-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-10-18 | 2007-04-19 | 2007-10-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-10-18 | 2011-04-19 | 2011-10-19 | $7700.00 | Window Closed / Lapsed |