Method and apparatus for implementing decode operations in a data processor
AssigneeARC International
InventorJonathan Ferguson
Life of this patent
Estimating the term…
Abstract
An improved method and apparatus for performing operations (such as Viterbi decode) in digital processors using a reduced number of cycles. In one aspect, the invention comprises efficient methods for performing multiple “butterfly” add-compare-select (ACS) operations using an improved dual butterfly (DVBF) extension instruction added to the instruction set of a user-configured processor. The DVBF extension allows performance of two butterfly operations in a single cycle. In another aspect, an improved path metric addressing scheme is disclosed. An integrated circuit (IC) device incorporating the aforementioned features, and method of designing such IC, are also disclosed.
Claims28
A method of processing trellis state information within a processor, the processor comprising:
- a storage device configured to store a plurality of path metric data;
- at least one memory port, said at least one memory port adapted to transfer data and signals to and from said storage device;
- at least one function port, said at least one function port adapted to transfer data and signals to and from a macro function;
- a data transfer fabric adapted to transfer data and signals between said at least one memory port and said at least one function port;
- and
- an arbitration unit adapted to arbitrate access to various portions of said storage device by said macro function;
- wherein the method comprises:
- providing a plurality of path metrics for each of a plurality of states;
- concatenating at least two of said path metrics for adjacent states to produce a word;
- generating an address such that a read operation may be performed in a linear fashion during a subsequent decoding cycle;
- and
- storing said word at said address in said storage device.
A digital processor having an instruction set with at least one instruction for trellis decoding, comprising:
- a multistage pipeline;
- a storage device configured to store a plurality of metric data;
- and
- a macro-function, said macro function under at least partial control of said at least one instruction and comprising a Viterbi accelerator unit comprising a plurality of add-compare-select (ACS) hardware;
- wherein said at least one instruction is used to:
- (i) perform multiple ACS operations associated with said trellis decode using said ACS hardware;
- and
- (ii) store metrics generated by said performance of said ACS operations within said storage device.
For use in a digital processor, a method for determining a path metric associated with a dual add-compare-select, the method comprising:
- retrieving at least one existing path metric from a first location in XY memory;
- providing at least one control word;
- determining a first branch metric and a second branch metric based on said control word;
- determining the negatives of at least one of said first and second branch metrics when required;
- selecting one branch metric from the group comprising said first and second branch metrics and said at least one negative when determined;
- determining at least one new path metric based at least in part on said selected branch metric and said at least one existing path metric;
- and
- storing said at least one new path metric at a second location within said XY memory, said second location being different from said first location.
A control data word for use in trellis decode operations, comprising:
- at least first, second and third data fields comprising a plurality of data bits, said first field contiguous within said word with said second field, said second field contiguous with said third field;
- and
- at least fourth, fifth and sixth data fields comprising a plurality of data bits, said fourth field contiguous within said word with said fifth field, said fifth field contiguous with said sixth field;
- wherein said first, second, and third fields comprise data relating to a first dual add-compare-select, and said fourth, fifth, and sixth fields comprise data relating to a second dual add-compare-select, said first and second dual add compare selects each comprising two ACS operations;
- and
- wherein said plurality of data bits for said first, second, fourth, and fifth fields comprises first and second bits, said first and second bits being mapped to combinations of path and branch metrics, mapping of said first and second bits for said first and fourth fields comprises:
- (i) 00−path metric 0+branch metric 0
- (ii) 01−path metric 0+branch metric 1
- (iii) 10−path metric 0−branch metric 1
- (iv) 11−path metric 0−branch metric 0.
A method of processing trellis state information within a processor having a memory, comprising:
- providing a plurality of path metrics for each of a plurality of states;
- concatenating at least two of said path metrics for adjacent states to produce a word;
- and
- storing said word at a location in memory;
- wherein said path metrics are 16-bits in length, and said word is 32-bits.
A dual butterfly extension instruction for inclusion within the instruction set architecture (ISA) of a user-configured digital processor, the extension instruction performing, when executed on said processor, at least two trellis butterfly decode operations, each of said decode operations comprising determining new path metrics using a plurality of ACS operations;
- wherein said decode operations comprise obtaining existing path metrics from a first storage location associated with said processor, and storing said new path metrics at a second storage location different from the first.
A digital processor having an instruction set with at least one instruction for trellis decoding, comprising:
- a multistage pipeline;
- a storage device configured to store a plurality of metric data;
- and
- add-compare-select (ACS) hardware operatively coupled to said pipeline and said storage device;
- wherein said at least one instruction is used to:
- (i) perform multiple ACS operations associated with said trellis decode in a single instruction cycle using said ACS hardware;
- and
- (ii) store metrics generated by said performance of said ACS operations within said storage device;
- and
- wherein said processor is user-configurable at design, said user-configurability including the ability to add at least one extension instruction to said instruction set, said at least one extension instruction comprising said at least one instruction for trellis decode.
A digital processor having an instruction set with at least one instruction for trellis decoding, comprising:
- a multistage pipeline;
- a storage device configured to store a plurality of metric data;
- and
- add-compare-select (ACS) hardware operatively coupled to said pipeline and said storage device;
- wherein said at least one instruction is used to:
- (i) perform multiple ACS operations associated with said trellis decode substantially within a single instruction cycle using said ACS hardware;
- and
- (ii) store metrics generated by said performance of said ACS operations within said storage device;
- and
- wherein said processor is user-configurable at design, including the ability to add said at least one instruction for trellis decode as an extension.
A digital processor having an instruction set with at least one instruction for trellis decoding, comprising:
- a multistage pipeline;
- a storage device configured to store a plurality of metric data;
- and
- add-compare-select (ACS) hardware operatively coupled to said pipeline and said storage device;
- wherein said at least one instruction is used to:
- (i) perform multiple ACS operations associated with said trellis decode in a single instruction cycle using said ACS hardware;
- and
- (ii) store metrics generated by said performance of said ACS operations within said storage device;
- and
- wherein at least a portion of said ACS hardware is added to said design as part of adding said at least one trellis decode extension instruction to said instruction set.
A method of processing trellis state information within a processor in support of communication operations, said method comprising:
- providing a plurality of path metrics for each of a plurality of states;
- concatenating at least two of said path metrics for adjacent states to produce a word;
- generating an address such that a read operation may be performed in a linear fashion during a subsequent decoding cycle;
- and
- storing said word at said address in said storage device;
- wherein said processing of said trellis state information is used in support of communication operations by a host device of said processor.
A digital processor having an instruction set with at least one instruction for trellis decoding, comprising:
- a multistage pipeline;
- a storage device configured to store a plurality of metric data;
- at least one port adapted to transfer data and signals to and from said storage device;
- at least one function port adapted to transfer data and signals to and from a macro function;
- data transfer means adapted to transfer data and signals between said at least one port and said at least one function port, and
- an arbitration unit adapted to arbitrate access to said storage device by said macro function;
- wherein said macro function comprises a Viterbi accelerator unit comprising a plurality of add-compare-select (ACS) hardware;
- and
- wherein said at least one instruction is used to:
- (i) perform multiple ACS operations associated with said trellis decode using said ACS hardware;
- and
- (ii) store metrics generated by said performance of said ACS operations within said storage device via at least said data transfer means.
A digital processor having an instruction set with at least one instruction for trellis decoding, comprising:
- a multistage pipeline;
- a storage device configured to store a plurality of metric data;
- and
- a macro-function, said macro function under at least partial control of said at least one instruction and comprising an accelerator unit comprising a plurality of add-compare-select (ACS) hardware;
- wherein said at least one instruction is used to:
- (i) perform multiple ACS operations associated with said trellis decode using said ACS hardware;
- and
- (ii) store metrics generated by said performance of said ACS operations within said storage device.
Dependencies are inferred from the claim text.