Back to results
US 2011/0211659 A1Published application
Low-latency Viterbi survivor memory architecture and method using register exchange, trace-back, and trace-forward
AssigneeResearch In Motion Limited
InventorMartin Kosakowski
Life of this patent
Estimating the term…
Abstract
In various aspects, the disclosure describes systems and methods for decoding of convolutionally encoded signals representing, for example, telecommunications signals such as command or content signals used in digital telecommunications. In various embodiments such aspects of the disclosure provide systems and methods for improving the efficiency, speed, and power consumption of such processes by providing architectures and methods for processing various parts of the encoded data records in parallel, using multiple and optionally specially-designed, dedicated memory registers and multiplexers.
Claims18
A method, performed by a data processor, for processing electromagnetic signals representing convolutionally encoded data streams of bit length L, the method comprising:
- while performing a trellis search of a convolutionally encoded data stream of bit length L:
- storing decision bit data representing results of the trellis search for the first D bits of the data stream in a (D×N)-bit register accessible by the processor;
- storing decision bits representing results of the trellis search for the subsequent L×D bits of the data stream in random access memory accessible by processor;
- and
- upon completion of the trellis search for the first D bits of the data stream, starting, with the (D+1)st bit of the data stream, a first trace-forward process;
- and
- upon completion of the trellis search for the first P bits of the data stream, starting, with the (P+1)st bit of the data stream, a second trace-forward process.
4 more elements
A system for processing electromagnetic signals representing convolutionally encoded data streams, the system comprising:
- at least one processor configured to execute a trellis search of one or more convolutionally encoded data streams of bit length L;
- at least one (D×N)-bit data register for storage of trellis search results provided by the at least one processor for the first D bits of each corresponding data stream;
- at least one random access memory store configured for storage of the subsequent L−D bits of each corresponding data stream;
- and
- a plurality of (N×M)-bit registers for storage of trace-forward data provided by the at least one processor.
2 more elements
The system of 9, further comprising, further comprising a trace-back logic unit configured to perform trace-back operations on data stored in at least one of the plurality of trace-forward registers.
A method, performed by a data processor for processing electromagnetic signals representing convolutionally encoded data streams of bit length L, the method comprising:
- while performing a Viterbi trellis search of a convolutionally encoded data stream of bit length L:
- storing decision bit data determined by an add-compare-select unit representing results of the trellis search for the first D bits of the data stream in a register accessible by the processor, and reordering the data stored in the register array according to the latest add-compare-select decision;
- storing decision bits determined by the add-compare-select unit representing results of the trellis search for the subsequent L−D bits of the convolutionally encoded data stream in random access memory accessible by the same or another processor;
- and
- in parallel with the Viterbi trellis search, starting, with the first bit of the data stream, a first trace-forward process, and updating a first trace-forward unit after each decision of the add-compare-select unit;
- upon completion of the trellis search for the first D bits of the data stream, starting, with the (D+1)st bit of the data stream, a second trace-forward process, and updating said first trace-forward unit after each decision of the add-compare-select unit;
- upon completion of the trellis search for the first P bits of the data stream, starting, with the (P+1)st bit of the data stream, a third trace-forward process, and updating a second trace-forward unit after each decision of the add-compare-select unit;
- upon completion of the Viterbi trellis search, using position information determined by the first trace-forward process, checking a tail-biting criterion, and:
- if the tail-biting criterion is not fulfilled, repeating the Viterbi trellis search, starting with final path metrics determined during the previous iteration;
- and
- if the tail-biting criterion is fulfilled:
- initiating output of the first D decoded bits of the register array, based on the state position determined by the value of the second trace-forward unit at a final winning state position of the trellis search, while commencing the first and second trace-back processes;
- and in parallel to processing of such output:
- commencing a first trace-back process for the trellis search results corresponding to the Pth through Dth bits of the data stream starting with the state position determined by the value of a third trace-forward unit at the final winning state position of the trellis search, and storing the resultant decoded bits in a first LIFO memory;
- and
- commencing a second trace-back process for the trellis search results for the Lth through Pth bits of the data stream starting with the final winning state position of the trellis search;
- and storing the resultant decoded bits in a second LIFO memory;
- upon completion of the first trace-back process, commencing output of the data stored in the first LIFO memory;
- and
- upon completion of outputting of data stored in the first LIFO memory, outputting data stored in the second LIFO memory.
17 more elements
A method, performed by a data processor, for processing electromagnetic signals representing convolutionally encoded data streams of bit length L, the method comprising:
- performing a Viterbi trellis search of a convolutionally encoded data stream of bit length L, including;
- storing decision bit data determined by an add-compare-select unit representing results of the trellis search for the first D bits of the data stream in a register accessible by the processor, and reordering the data stored in the register array according to the latest add-compare-select decision;
- storing decision bits determined by the add-compare-select unit representing results of the trellis search for the subsequent L−D bits of the convolutionally encoded data stream in random access memory accessible by processor;
- and
- upon completion of the trellis search for the first D bits of the data stream, starting, with the (D+1)st bit of the data stream, a first trace-forward process, and updating a first trace-forward unit after each decision of the add-compare-select unit;
- upon completion of the trellis search for the first P bits of the data stream, starting, with the (P+1)st bit of the data stream, a second trace-forward process, and updating a second trace-forward unit after each decision of the add-compare-select unit;
- upon completion of the Viterbi trellis search, initiating output of the results of the trellis search corresponding to the first D bits of the data stream from the register based on a state position determined by the value of the first trace-forward unit;
- commencing a first trace-back process for the trellis search results corresponding to the Pth through Dth bits of the data stream starting with the state position determined by the value of the second trace-forward unit at;
- and storing the resultant decoded bits in a first LIFO memory;
- and
- commencing a second trace-back process for the trellis search results for the Lth through Pth bits of the data stream;
- and storing the resultant decoded bits in a second LIFO memory;
- upon completion of the first trace-back process, commencing output of the data stored in the first LIFO memory;
- and
- upon completion of outputting of data stored in the first LIFO memory, outputting data stored in the second LIFO memory.
12 more elements
Dependencies are inferred from the claim text.