Optimized Viterbi decoder and GNSS receiver
AssigneeQUALCOMM Incorporated
InventorPhilip John Young
Life of this patent
Estimating the term…
Abstract
A Viterbi decoder which is based on a special instruction set implemented in the processor, enabling it to handle the Viterbi processing with a much lower CPU loading without significantly increasing the hardware complexity. By careful application of appropriate design constraints specific to the SV navigation and analysis of the Viterbi algorithm an optimised architecture can be realized for embedding Viterbi acceleration logic efficiently into a GNSS chipset.
Claims36
A method of improving the efficiency of decoding convolutional encoded data in Viterbi decoders, comprising:
- setting a transition cost to non-negative values in a range 0 to M, where M is the maximum cost that is obtained in K steps where K is the number of memory bits in the convolutional encoded data;
- and
- allocating N bits per cumulative path cost where (2^(K+1)*M)−1<2^N−1.
A method of reducing costs in Viterbi decoding convolution-encoded data, comprising:
- processing 64 Viterbi states in 8 iterations of a loop with CPU operands, where each iteration processes 8 consecutive current states, and;
- storing associated state symbol interpretation costs to be represented as loop invariants in one 32 bit core register;
- and
- storing transition information for the loop in a second register.
A processor optimized for the decoding of convolutional encoded data configured to:
- set a transition cost to non-negative values in a range 0 to M, where M is the maximum cost that is obtained in K steps where K is the number of memory bits in the convolutional encoded data;
- and
- allocating N bits per cumulative path cost where (2^(K+1)*M)−1<2^N−1;
- wherein the processor is arranged to extend the register set of the processor with phantom registers which, when addressed by an instruction, return a value calculated from signals and/or registers not explicitly addressed by the instruction.
A processor for decoding convolutional encoded data configured to:
- set a transition cost to non-negative values in a range 0 to M, where M is the maximum cost that is obtained in K steps where K is the number of memory bits in the convolutional encoded data;
- and
- allocating N bits per cumulative path cost where (2^(K+1)*M)−1<2^N−1;
- wherein the processor is arranged to execute an instruction to implement the add-compare-select operation which operates on multiple operands stored in the core data registers where the instruction utilizes additional CPU registers which are implicitly addressed by the instruction allowing a SIMD architecture to be implemented without violating the constraints of the processors Instruction Set Architecture.
A processor for decoding convolutional encoded data, comprising an instruction extension, the instruction extension being configured for:
- implementing a traceback operation where a traceback history is represented in a pair of core CPU registers and the instruction is able to specifically set/clear bits in the traceback history based on a traceback state;
- counting an index to the bit to be set/cleared on each operation of the instruction;
- and
- detecting if the traceback history has been changed by a current step and set a flag to terminate the traceback operation on convergence with a previous value.
A processor for decoding convolutional encoded data, comprising:
- a phantom register based on a traceback state and address of a data structure in system memory where the register returns a correct address for a next 32 bit traceback history word to be read;
- where the phantom register is used by a CPU as an address register for an indirect load;
- and
- the address is a function of the current traceback state and traceback sample index.
A processor for decoding convolutional encoded data, arranged to execute an instruction to:
- retrieve the oldest bits of the traceback data in a correct bit order representative of the transmitted data;
- and
- to detect if the oldest bits of the traceback data have been changed by a current step, and set a flag to terminate the retrieval on convergence with a previous value if the detection is true;
- where an address of a field returned from the traceback data is determined implicitly by a traceback control register.
A processor for decoding convolutional encoded data, the processor configured to execute
- an instruction to consume a number of bits from a traceback data;
- and
- to detect if the traceback data has been changed by a current step, and set a flag to terminate the consumption on convergence with a previous value if the detection is true;
- wherein the processor automatically updates a traceback count field of a traceback control register.
A GNSS receiver for determining a geographic position based on a signal received by a plurality of radio localization beacons, the beacons derived from localization satellites, wherein some of the data contained in said signal are encoded according to a convolutional code, and wherein the receiver includes a processor configured to:
- set a transition cost to non-negative values in a range 0 to M, where M is the maximum cost that is obtained in K steps where K is the number of memory bits in the convolutional encoded data;
- and
- allocating N bits per cumulative path cost where (2^(K+1)*M)−1<2^N−1;
- wherein the processor is arranged to:
- extend the register set of the processor with phantom registers which, when addressed by an instruction, return a value calculated from signals and/or registers not explicitly addressed by the instruction;
- and
- execute software programs containing special instructions to decode said convolutional code.
An apparatus configured to decode convolutional encoded data in Viterbi decoders, comprising:
- means for setting a transition cost to non-negative values in a range 0 to M, where M is the maximum cost that is obtained in K steps where K is the number of memory bits in the convolutional encoded data;
- and
- means for allocating N bits per cumulative path cost where (2^(K+1)*M)−1<2^N−1.
A computer program product residing on a processor-readable medium and comprising processor-readable instructions configured to cause a processor to:
- set a transition cost to non-negative values in a range 0 to M, where M is the maximum cost that is obtained in K steps where K is the number of memory bits in the convolutional encoded data;
- and
- allocate N bits per cumulative path cost where (2^(K+1)*M)−1<2^N−1.
Dependencies are inferred from the claim text.