US 2005/0060633 A1Published application

Low-latency architectures for high-throughput viterbi decoders

AssigneeLeanics Corporation

InventorsKeshab Parhi, Junjin Kong

Life of this patent

Estimating the term…

Loading patent…

Abstract

Digital circuits and methods for designing digital circuits are presented. More particularly, the present invention relates to error correction circuits and methods in communications and other systems. In the present invention, a novel K-nested layered look-ahead method and its corresponding architecture, which combine K-trellis steps into one trellis step (where K is the encoder constraint length), are proposed for implementing low-latency high through-put rate Viterbi decoder circuits. The main idea of the present invention involves combining K-trellis steps as a pipeline structure and then combining the resulting look-ahead branch metrics as a tree structure in a layered manner to decrease the ACS precomputation latency of look-ahead Viterbi decoder circuits. The proposed method guarantees parallel paths between any two trellis states in the look-ahead trellises and distributes the add-compare-select (ACS) computations to all trellis layers. It leads to regular and simple architecture for the Viterbi decoding algorithm. The look-ahead ACS computation latency of the proposed method increases logarithmically with respect to the look-ahead step (M) divided by the encoder constraint length (K) as opposed to linearly as in prior work. The main advantage of this invention is that it has the least latency among all known look-ahead Viterbi decoder circuits for a given level of parallelism.

Claims18

Dependent claims

A method for implementing a M-parallel Viterbi decoder by combining M trellis steps of a trellis, generated by a convolutional code encoder containing (K−1) memory elements, as a pipeline structure, comprising:

(i) a M-step look-ahead add-compare-select precomputation unit,
(ii) an add-compare-select recursion unit,
(iii) a survivor path management circuit, and
(iv) flip-flops or registers for inter-stage pipelining,
wherein:
the M-step look-ahead add-compare-select precomputation unit is obtained by:
(a) forming an initial add-compare-select circuit which combines the branch metrics of the first K inputs, and replicating this M/K times for processing of all M parallel inputs,
(b) forming a log2(M/W) layered intermediate add-compare-select circuit, where inputs of each add-compare-select unit are coupled to the outputs of the previous layer, and each of its outputs is coupled to an input of the add-compare-select unit of the next layer.
and wherein:
the inputs of the add-compare-select recursion unit are coupled to the outputs generated by the final layer of the intermediate circuit and the outputs generated by the said add-compare-select recursion unit in the past clock cycle,
and wherein:
the survivor path management circuit is implemented as a pipeline structure, obtained by:
(c) forming a log2(M/K) layered survivor path circuit corresponding to the log2(M/K) layered intermediate add-compare-select circuit, where each input of this circuit is coupled to a parallel path select output generated by the add-compare-select units of the previous layer and is controlled by a parallel path select output generated by the add-compare-select units of the current layer, and each of its outputs is coupled to the inputs of the survivor path circuit of the next layer, and wherein the first layer inputs are the parallel path select outputs generated by the initial add-compare-select circuit,
(d) a final survivor path circuit associated with the add-compare-select recursion unit, wherein its inputs are coupled to the parallel path select signals of the last layer of the log2(M/K) layered survivor path circuit and the control signals are coupled to the path select signals generated by the add-compare-select recursion unit.

11 more elements

A digital circuit, operating at more than 2 Gigabit per second, for implementing a M-parallel Viterbi decoder by combining M trellis steps of a trellis, generated by a convolutional code encoder containing (K−1) memory elements, as a pipeline structure, comprising:

(i) a M-step look-ahead add-compare-select precomputation unit,
(ii) an add-compare-select recursion unit,
(iii) a survivor path management circuit, and
(iv) flops or registers for inter-stage pipelining,
wherein:
the M-step look-ahead add-compare-select precomputation unit is obtained by:
(a) forming an initial add-compare-select circuit which combines the branch metrics of the first K inputs, and replicating this M/K times for processing of all M parallel inputs,
(b) forming a log2(M/K) layered intermediate add-compare-select circuit, where inputs of each add-compare-select unit are coupled to the outputs of the previous layer, and each of its outputs is coupled to an input of the add-compare-select unit of the next layer.
and wherein:
the inputs of the add-compare-select recursion unit are coupled to the outputs generated by the final layer of the intermediate circuit and the outputs generated by the said add-compare-select recursion unit in the past clock cycle,
and wherein:
the survivor path management circuit is implemented as a pipeline structure obtained by:
(c) forming a log2(M/K) layered survivor path circuit corresponding to the log2(M/K) layered intermediate add-compare-select circuit, where each input of this circuit is coupled to a parallel path select output generated by the add-compare-select units of the previous layer and is controlled by a parallel path select output generated by the add-compare-select units of the current layer, and each of its outputs is coupled to the inputs of the survivor path circuit of the next layer, and wherein the first layer inputs are the parallel path select outputs generated by the initial add-compare-elect circuit,
(d) a final survivor path circuit associated with the add-compare-select recursion unit, wherein its inputs are coupled to the parallel path select signals of the last layer of the log2(M/K) layered survivor path circuit and the control signals are coupled to the path select signals generated by the add-compare-select recursion unit.

11 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/922,205Filed 19 Aug 2004
Priority: 19 Aug 2003
Published: 17 Mar 2005
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

H03M 13/3961
Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes: arrangements of methods for branch or transition…
H03M 13/395
Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes: using a collapsed trellis, e.g. M-step…
H03M 13/4107
Using the Viterbi algorithm or Viterbi processors: implementing add, compare, select [ACS] operations
H03M
Coding

Family

Application60/496,307Us provisional application · filed 19 Aug 2003
US 7,308,640 B2Related patent
US 2005/0060633 A1This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key