Low-latency viterbi survivor memory architecture and method using register exchange, trace-back, and trace-forward

1. A method, performed by a data processor, for processing electromagnetic signals representing convolutionally encoded data streams, the method comprising:

while performing a trellis search of a convolutionally encoded data stream of bit length L, where L is an integer:

storing decision bit data representing results of the trellis search for a first D bits of the convolutionally encoded data stream in a (D×N)-bit register accessible by the data processor, where D is an integer greater than zero and less than L, and ordering the decision bit data according to the results of the trellis search for the first D bits of the convolutionally encoded data stream;

storing decision bits representing results of the trellis search for a subsequent L-D bits of the convolutionally encoded data stream in random access memory accessible by the data processor; and

upon completion of the trellis search for the first D bits of the convolutionally encoded data stream, commencing a first trace-forward process of the results of the trellis search, starting with a (D+1) st bit of the convolutionally encoded data stream; and

commencing at least one trace-back process to decode the stored decision bits in the random access memory corresponding to the (D+1) st through L th bits of the convolutionally encoded data stream, and storing decoded bits determined by the at least one trace-back process in at least one last-in first-out (LIFO) register.

2. The method of claim 1 , further comprising:

upon completion of the trellis search, commencing output of the stored decision bit data corresponding to the first D bits of the convolutionally encoded data stream from the (D×N)-bit register, based on a state position determined by the first trace-forward process at a final winning state position of the trellis search; and

following output of the stored decision bit data from the (D×N)-bit register, commencing output of the stored decoded bits corresponding to the subsequent L-D bits of the convolutionally encoded data stream from the at least one LIFO register.

3. The method of claim 1 , wherein the at least one trace-back process comprises a single trace-back process to decode the stored decision bits in the random access memory corresponding to the (D+1) st through L th bits of the convolutionally encoded data stream commenced starting with a final winning state position of the trellis search.

4. The method of claim 3 , further comprising:

upon completion of the trellis search, commencing output of the stored decision bit data corresponding to the first D bits of the convolutionally encoded data stream from the (D×N)-bit register, based on a state position determined by the first trace-forward process at the final winning state position of the trellis search,

following output of the stored decision bit data from the (D×N)-bit register, commencing output of the stored decoded bits corresponding to the subsequent L-D bits of the convolutionally encoded data stream from the at least one LIFO register.

5. The method of claim 4 , wherein the single trace-back process is commenced in parallel with output of the stored decision bit data from the (D×N)-bit register corresponding to the first D bits of the convolutionally encoded data stream.

6. The method of claim 1 , wherein the at least one trace-back process comprises at least two trace-back processes to decode the stored decision bits in the random access memory corresponding to the (D+1) st through L th bits of the convolutionally encoded data stream, including one trace-back process commenced starting with the final winning state position of the trellis search and at least one other trace-back process commenced starting with a state position determined by a trace-forward process other than the first trace-forward process at the final winning state position of the trellis search.

7. The method of claim 6 , further comprising:

upon completion of the trellis search, commencing output of the stored decision bit data corresponding to the first D bits of the convolutionally encoded data stream from the (D×N)-bit register, based on a state position determined by the first trace-forward process at the final winning state position of the trellis search,

following output of the stored decision bit data from the (D×N)-bit register, commencing output of the stored decoded bits corresponding to the subsequent L-D bits of the convolutionally encoded data stream from the at least one LIFO register.

8. The method of claim 6 , further comprising:

upon completion of the trellis search for a first P bits of the convolutionally encoded data stream, where P is an integer greater than D and less than L, commencing a second trace-forward process, starting with a (P+1) st bit of the convolutionally encoded data stream.

9. The method of claim 8 , further comprising:

commencing a first trace-back process for the decision bits stored in the random access memory corresponding to the (D+1) st through P th bits of the convolutionally encoded data stream, starting with a state position determined by the second trace-forward process at the final winning state position of the trellis search; and

commencing a second trace-back process for the decision bits stored in the random access memory corresponding to the (P+1) st through L th bits of the convolutionally encoded data stream, starting with the final winning state position of the trellis search.

10. The method of claim 9 , wherein the first trace-back process and at least a portion of the second trace-back are performed in parallel.

11. The method of claim 8 , further comprising:

upon completion of the trellis search for a first 2P bits of the convolutionally encoded data stream, where 2P is an integer greater than P and less than L, commencing a third trace-forward process, starting with a (2P+1) st bit of the convolutionally encoded data stream.

12. The method of claim 11 , further comprising:

commencing a first trace-back process for the decision bits stored in the random access memory corresponding to the (D+1) st through P th bits of the convolutionally encoded data stream, starting with a state position determined by the second trace-forward process at the final winning state position of the trellis search;

commencing a second trace-back process for the decision bits stored in the random access memory corresponding to the (P+1) st through 2P th bits of the convolutionally encoded data stream, starting with a state position determined by the third trace-forward process at the final winning state position of the trellis search; and

commencing a third trace-back process for the decision bits stored in the random access memory corresponding to the (2P+1) st through L th bits of the convolutionally encoded data stream, starting with the final winning state position of the trellis search.

13. The method of claim 12 , wherein the first trace-back process and at least a portion of the second trace-back are performed in parallel.

14. The method of claim 6 , further comprising:

upon completion of the trellis search for a first P bits of the convolutionally encoded data stream, where P is an integer greater than D and less than L, commencing a second trace-forward process, starting with a (P+1) st bit of the convolutionally encoded data stream;

in parallel with outputting of the decision bit data from the (D×N)-bit register, commencing a first trace-back process for the decision bits stored in the random access memory corresponding to the (D+1) st through P th bits of the convolutionally encoded data stream, starting with a state position determined by the second trace-forward process at the final winning state position of the trellis search, and storing decoded bits determined by the first trace-back process in a first LIFO register;

following output of the stored decision bit data from the (D×N)-bit register, commencing output of the decoded bits stored in the first LIFO register corresponding to the (D+1) st through P th bits of the convolutionally encoded data stream;

commencing a second trace-back process for the decision bits stored in the random access memory corresponding to the (P+1) st through L th bits of the convolutionally encoded data stream, starting with the final winning state position of the trellis search, and storing decoded bits determined by the second trace-back process in a second LIFO register; and

following output of the stored decoded bits in the first LIFO register, commencing output of the decoded bits stored in the second LIFO register corresponding to the (P+1) st through L th bits of the convolutionally encoded data stream.

15. The method of claim 6 , further comprising:

upon completion of the trellis search for a first P bits of the convolutionally encoded data stream, where P is an integer greater than D and less than L, commencing a second trace-forward process, starting with a (P+1) st bit of the convolutionally encoded data stream;

in parallel with outputting of the decision bit data from the (D×N)-bit register:

commencing a first trace-back process for the decision bits stored in the random access memory corresponding to the (D+1) st through P th bits of the convolutionally encoded data stream, starting with a state position determined by the second trace-forward process at the final winning state position of the trellis search, and storing decoded bits determined by the first trace-back process in a first LIFO register; and

commencing a second trace-back process for the decision bits stored in the random access memory corresponding to the (P+1) st through L th bits of the convolutionally encoded data stream, starting with the final winning state position of the trellis search, and storing decoded bits determined by the second trace-back process in a second LIFO register;

following output of the stored decision bit data from the (D×N)-bit register, commencing output of the decoded bits stored in the first LIFO register corresponding to the (D+1) st through P th bits of the convolutionally encoded data stream; and

following output of the stored decoded bits in the first LIFO register, commencing output of the decoded bits stored in the second LIFO register corresponding to the (P+1) st through L th bits of the convolutionally encoded data stream.

16. The method of claim 6 , further comprising

upon completion of the trellis search for a first P bits of the convolutionally encoded data stream, where P is an integer greater than D and less than L, commencing a second trace-forward process, starting with a (P+1) st bit of the convolutionally encoded data stream;

upon completion of the trellis search for a first 2P bits of the convolutionally encoded data stream, where 2P is an integer greater than P and less than L, commencing a third trace-forward process, starting with a (2P+1) st bit of the convolutionally encoded data stream;

in parallel with outputting of the decision bit data from the (D×N)-bit register:

commencing a first trace-back process for the decision bits stored in the random access memory corresponding to the (D+1) st through P th bits of the convolutionally encoded data stream, starting with a state position determined by the second trace-forward process at the final winning state position of the trellis search, and storing decoded bits determined by the first trace-back process in a first LIFO register; and

commencing a second trace-back process for the decision bits stored in the random access memory corresponding to the (P+1) st through 2P th bits of the convolutionally encoded data stream, starting with a state position determined by the third trace-forward process at the final winning state position of the trellis search, and storing decoded bits determined by the first trace-back process in a second LIFO register;

following output of the stored decision bit data from the (D×N)-bit register, commencing output of the decoded bits stored in the first LIFO register corresponding to the (D+1) st through P th bits of the convolutionally encoded data stream;

following output of the stored decoded bits in the first LIFO register, commencing output of the decoded bits stored in the second LIFO register corresponding to the (P+1) st through 2P th bits of the convolutionally encoded data stream;

commencing a third trace-back process for the decision bits stored in the random access memory corresponding to the (2P+1) st through L th bits of the convolutionally encoded data stream, starting with the final winning state position of the trellis search, and storing decoded bits determined by the third trace-back process in the first LIFO register array; and

following output of the stored decoded bits in the second LIFO register, commencing output of the decoded bits stored in the first LIFO register corresponding to the (2P+1) st through L th bits of the convolutionally encoded data stream.

17. The method of claim 1 , wherein:

D =round-up( D ′);

L/ 5 ≦D′≦L/ 2;

M=CL− 1;

N= 2 M =2 (CL-1) ;

CL=the constraint length of a convolutional encoder used to generate the convolutionally encoded data stream; and

M=the number of delay elements of the convolutional encoder.

18. 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, where L is an integer;

a (D×N)-bit data register for storage of decision bit data representing results of the trellis search provided by the at least one processor for a first D bits of each corresponding data stream, where D is an integer greater than zero and less than L, and the decision bit data stored in the (D×N)-bit data register re-orderable by the at least one processor according to the results of the trellis search for the first D bits of each corresponding data stream;

a memory store configured for storage of decision bits representing results of the trellis search provided by the at least one processor for a subsequent L−D bits of each corresponding data stream;

at least one (N×M)-bit trace-forward register for storage of trace-forward data provided by the at least one processor; and

a trace-back logic unit configured to perform at least one trace-back process to decode the stored decision bits in the memory store.

19. The system of claim 18 , wherein the at least one processor is configured to output the stored decision bit data from the (D×N)-bit data register based on the trace-forward data stored in the at least one (N×M)-bit trace-forward register.

20. The system of claim 19 , further comprising at least one last-in first-out (LIFO) register for temporary storage of decision bits outputted from the memory store.

21. The system of claim 18 , wherein the trace-back unit is configured to perform a single trace-back process to decode the stored decision bits in the memory store commenced starting with a final winning state position of the trellis search.

22. The system of claim 18 , wherein the trace-back unit is configured to perform at least two trace-back processes to decode the stored decision bits in the memory store, including one trace-back process commenced starting with the final winning state position of the trellis search, and at least one other trace-back process commenced starting with a state position determined from the trace-forward data stored in the at least one (N×M)-bit trace-forward register.

23. The system of claim 22 , wherein the at least one (N×M)-bit trace-forward register comprises at least two (N×M)-bit trace-forward registers, including a first trace-forward register for storage of trace-forward data used to output the stored decision bit data from the (D×N)-bit data register, and at least a second trace-forward register for storage of trace-forward data used by the trace-back unit to decode the stored decision bits in the memory store.

24. The system of claim 23 , wherein the at least one (N×M)-bit trace-forward register further comprises a third trace-forward register for storage of trace-forward data used by the trace-back unit to decode the stored decision bits in the memory store.

25. The system of claim 18 , wherein:

D =round-up( D ′);

L/ 5 ≦D′≦L/ 2;

M=CL− 1;

N= 2 M =2 (CL-1) ;

CL=the constraint length of a convolutional encoder used to generate the one or more convolutionally encoded data streams; and

M=the number of delay elements of the convolutional encoder.