Accelerating traceback on a signal processor

1. A method of pipelining decoding instructions in a processor, comprising:

receiving a first instruction comprising a first index including a plurality of bits and a second value comprising at least 2 b target bits;

selecting at least one target bit in the loaded second value based on the bits of the first index;

storing the at least one target bit in a predetermined location of the first index;

generating a second index based on the first index;

receiving a second instruction comprising a first address, the second index, and a constraint length k, wherein k is an integer greater than or equal to zero;

acquiring a first index-offset;

determining a byte offset as a predetermined function of the second index; and

generating the second address based on the first index-offset, the first address, and the second index, wherein the first index comprises the bits of the second index.

2. The method of claim 1 , wherein the at least one target bit comprises a plurality of bits, which are stored in the predetermined location in the first index in a forward order.

3. The method of claim 1 , wherein the at least one target bit comprises a plurality of bits, which are stored in the predetermined location in the first index in a reverse order.

4. The method of claim 1 , wherein the predetermined location comprises the beginning of the first index.

5. The method of claim 1 , wherein the second instruction uses k-b bits to compute the byte offset, where the bits selected are k- 1 -L . . . b-L, where L is in a range 0 . . . b.

6. The method of claim 5 , further comprising:

loading the bits; and

computing the second index with the first instruction based upon the loaded bits and the first index.

7. The method of claim 6 , wherein the loading and the computing are performed in parallel.

8. The method of claim 1 , further comprising:

computing traceback bits;

producing weights for the traceback bits; and

producing weights at least for the first and second indices.

9. The method of claim 1 , wherein the traceback bits and the weights are calculated and produced via a viterbi butterfly.

10. The method of claim 1 , wherein the traceback bits and the weights are calculated and produced via a plurality of viterbi butterflies operating in parallel to one another.

11. The method of claim 10 , wherein the plurality of viterbi butterflies produce two groups of traceback bits, low bits in a lower half of a traceback vector and high bits in an upper half of a traceback vector.

12. The method of claim 11 , wherein the low bits are interleaved with respect to the high bits.

13. The method of claim 11 , wherein the plurality of viterbi butterflies produce interleaved traceback bits.

14. The method of claim 1 , wherein the processor is a single instruction, multiple data processor.

15. The method of claim 1 , wherein the processor is a digital signal processor.

16. The method of claim 15 , wherein the digital signal processor is a single instruction, multiple data digital signal processor.

17. A processor comprising:

an instruction execution circuit; and

a memory coupled with the instruction execution circuit;

wherein the instruction execution circuit is configured to:

receive a first instruction comprising a first index including a plurality of bits and a second value comprising at least 2 b target bits;

select at least one target bit in a second value loaded from the memory, the target bit selected based on the bits of a first index value;

store the at least one target bit in a predetermined location of the first index value;

generate a second index value based on the first index value;

receive a second instruction comprising a first address, the second index, and a constraint length k, wherein k is an integer greater than or equal to zero;

acquiring a first index-offset;

determine a byte offset as a predetermined function of the second index; and

generate the second address based on the first index-offset, the first address, and the second index, wherein the first index comprises the bits of the second index.

18. The processor of claim 17 , wherein the at least one target bit comprises a plurality of bits, which are stored in the predetermined location in the first index in a forward order.

19. The processor of claim 17 , wherein the predetermined location comprises the beginning of the first index.

20. The processor of claim 17 , wherein the predetermined function of the byte offset is based on the bits of the second index right-shifted by b- 3 .

21. The processor of claim 17 , wherein the predetermined function of the byte offset is based on bits k- 1 to k-b of the second index.

22. A processor comprising:

means for receiving an instruction comprising a first index including a plurality of bits and a second value comprising at least 2 b target bits;

means for selecting at least one target bit in the loaded second value based on the bits of the first index;

means for storing the at least one target bit in a predetermined location of the first index; and

means for generating a second index based on the first index;

means for receiving a second instruction comprising a first address, the second index, and a constraint length k, wherein k is an integer greater than or equal to zero;

means for acquiring a first index-offset;

means for determining a byte offset as a predetermined function of the second index; and

means for generating the second address based on the first index-offset, the first address, and the second index, wherein the first index comprises the bits of the second index.

23. The processor of claim 22 , wherein the at least one target bit comprises a plurality of bits, which are stored in the predetermined location in the first index in a forward order.

24. The processor of claim 22 , wherein the predetermined location comprises the beginning of the first index.

25. The processor of claim 22 , wherein the predetermined function of the byte offset is based on the bits of the second index right-shifted by b- 3 .

26. The processor of claim 22 , wherein the predetermined function of the byte offset is based on bits k- 1 to k-b of the second index.

27. The processor of claim 17 , wherein the at least one target bit comprises a plurality of bits, which are stored in the predetermined location in the first index in a reverse order.

28. The processor of claim 17 , wherein the second instruction uses k-b bits to compute the byte offset, where the bits selected are k- 1 -L . . . b-L, where L is in a range 0 . . . b.

29. The processor of claim 17 , wherein the instruction execution circuit is further configured to:

load the bits; and

compute the second index with the first instruction based upon the loaded bits and the first index.

30. The processor of claim 29 , wherein the loading and the computing are performed in parallel.

31. The processor of claim 17 , wherein the instruction execution circuit is further configured to:

compute traceback bits;

produce weights for the traceback bits; and

produce weights at least for the first and second indices.

32. The processor of claim 17 , wherein the traceback bits and the weights are calculated and produced via a viterbi butterfly.

33. The processor of claim 17 , wherein the traceback bits and the weights are calculated and produced via a plurality of viterbi butterflies operating in parallel to one another.

34. The processor of claim 33 , wherein the plurality of viterbi butterflies produce two groups of traceback bits, low bits in a lower half of a traceback vector and high bits in an upper half of a traceback vector.

35. The processor of claim 34 , wherein the low bits are interleaved with respect to the high bits.

36. The method of claim 34 , wherein the plurality of viterbi butterflies produce interleaved traceback bits.

37. The processor of claim 17 , wherein the processor is a single instruction, multiple data processor.

38. The processor of claim 17 , wherein the processor is a digital signal processor.

39. The processor of claim 38 , wherein the digital signal processor is a single instruction, multiple data digital signal processor.

40. A non-transitory machine readable medium including instructions executable by a processor of an apparatus which cause the apparatus to:

receive a first instruction comprising a first index including a plurality of bits and a second value comprising at least 2 b target bits;

select at least one target bit in the loaded second value based on the bits of the first index;

store the at least one target bit in a predetermined location of the first index;

generate a second index based on the first index;

receive a second instruction comprising a first address, the second index, and a constraint length k, wherein k is an integer greater than or equal to zero;

acquire a first index-offset;

determine a byte offset as a predetermined function of the second index; and

generate the second address based on the first index-offset, the first address, and the second index, wherein the first index comprises the bits of the second index.