Apparatus and method for viterbi decoding

Abstract

The path temporary storage unit 101 stores path select signals outputted from the ACS means 100 over a certain period of time. The partial trace back unit 102 performs a partial trace back between the first time point and the second time point by using the path select signals stored in the path temporary storage unit 101, and detects a non-passing node through which surviving paths do not pass at the second time point. The conversion unit 103 receives the signals from the partial trace back unit 102, and converts the path select signal corresponding to the non-passing node into a predetermined fixed value. This decreases the probability of occurrence of a signal transition in the path memory 104, thereby reducing power consumption.

What is claimed is:  
     
       1. A viterbi decoder which has path storage means for storing path select signals and which performs decoding by using said path storage means, said viterbi decoder performing the steps of: 
       partially tracing back path select signals outputted from ACS means between a first time point and a second time point, thereby finding surviving paths reaching each node at the first time point;  
       detecting a non-passing node through which said surviving paths do not pass, of nodes at the second time point;  
       converting a path select signal corresponding to said non-passing node at the second time point in such a manner as to decrease a probability of occurrence of a signal transition in said path storage means; and  
       storing path select signals corresponding to said nodes at the second time point to said path storage means.  
     
     
       2. The viterbi decoder of  claim 1 , wherein said path select signal corresponding to said non-passing node is converted into a predetermined fixed value which is one of signal values of said path select signal. 
     
     
       3. The viterbi decoder of  claim 1 , wherein said path select signal corresponding to said non-passing node is converted into a same value as a value already stored in a storage region in said path storage means where said path select signal to be converted is supposed to be written. 
     
     
       4. A viterbi decoder which has path storage means for storing path select signals and which performs decoding by using said path storage means, said viterbi decoder comprising: 
       a path temporary storage unit for storing path select signals outputted from ACS means over a certain period of time and then outputting said path select signals;  
       a partial trace back unit for tracing back surviving paths reaching each node at time t+p by using path select signals between time t and time t+p−1 where p is a natural number which are stored in said path temporary storage unit and path select signals at time t+p outputted from said ACS means so as to detect a non-passing node through which said surviving paths do not pass; and  
       a conversion unit for inputting path select signals at time t outputted from said path temporary storage unit, and receiving signals from said partial trace back unit so as to convert a path select signal corresponding to said non-passing node out of said path select signals at time t into a predetermined fixed value which is one of signal values of said path select signal,  
       said path storage means storing path select signals at time t outputted from said conversion unit.  
     
     
       5. A viterbi decoder which has path storage means for storing path select signals and which perform decoding by using said path storage means, said viterbi decoder comprising: 
       a path temporary storage unit for storing path select signals outputted from ACS means over a certain period of time and then outputting said path select signals;  
       a partial trace back unit for tracing back surviving paths reaching each node at time t+p by using path select signals between time t and time t+p−1 where p is a natural number which are stored in said path temporary storage unit and path select signals at time t+p outputted from said ACS means so as to detect a non-passing node through which said surviving paths do not pass;  
       readout means for reading out storage contents in a storage region in said path storage means where path select signals at time t are supposed to be written; and  
       a conversion unit for inputting path select signals at time t outputted from said path temporary storage unit and said storage contents outputted from said readout means and receiving signals from said partial trace back unit so as to convert a path select signal corresponding to said non-passing node out of said path select signals at time t into a same value as a value which is contained in said storage contents and stored in a storage region where said path select signal to be converted is supposed to be written,  
       said path storage means storing path select signals at time t outputted from said conversion unit.  
     
     
       6. The viterbi decoder of  claim 4  or  5 , 
       wherein said partial trace back unit finds a function g (t, j) concerning each node j at time t, and determines that node j is a non-passing node when g (t, j)=0,  
       where g (t, i) is a function for calculating g (r, i)=Σ{g (r+1, n (i))×f (r, n (i))} from r=t+p−1 until r=t in sequence by using g (t+p, k)=1 as an initial value where k is an any node number, where  
       n (i): transition target nodes at time r+1 of a node i at time r;  
       f (r, n (i)): a function which indicates whether or not surviving paths reaching nodes n (i) at time r+1 pass through node i at time r, and which becomes “1” when said surviving paths pass through said nodes i, “0” otherwise;  
       Σ{ }: an OR of all said nodes n (i); and  
       X: AND.  
     
     
       7. The viterbi decoder of  claim 6 , wherein said partial trace back unit comprises a plurality of storage means for storing each value of g (r, i) at time r, and performs calculation of said function g (t, j) by pipeline processing. 
     
     
       8. A viterbi decoding method for performing decoding by using path storage means for storing path select signals, said viterbi decoding method comprising the steps of: 
       partially tracing back path select signals outputted from ACS means between a first time point and a second time point, thereby finding surviving paths reaching each node at the first time point;  
       detecting a non-passing node through which said surviving paths do not pass, of nodes at the second time point;  
       converting a path select signal corresponding to said non-passing node at the second time point in such a manner as to decrease a probability of occurrence of a signal transition in said path storage means; and  
       storing path select signals corresponding to said nodes at the second time point to said path storage means.  
     
     
       9. The viterbi decoding method of  claim 8 , wherein said path select signal corresponding to said non-passing node is converted into a predetermined fixed value which is one of signal values of said path select signal. 
     
     
       10. The viterbi decoding method of  claim 8 , wherein said path select signal corresponding to said non-passing node is converted into a same value as a value already stored in a storage region in said path storage means where said path select signal to be converted is supposed to be written. 
     
     
       11. A viterbi decoder which has path storage means for storing path select signals and which performs decoding by using said path storage means, said viterbi decoder performing the steps of: 
       applying predetermined conversion to path select signals outputted from ACS means;  
       storing converted path select signals in said path storage means;  
       applying conversion reverse to said predetermined conversion to path select signals outputted from said path storage means; and  
       performing decoding by using reversely-converted path select signals,  
       said predetermined conversion being so conducted that, out of combinations of path select signals representing surviving paths in a predetermined portion in a trellis diagram, a first combination with a relatively high frequency of occurrence contains a predetermined fixed value which is one of signal values of said path select signals more than a second combination with a relatively low frequency of occurrence.  
     
     
       12. The viterbi decoder of  claim 11 , wherein said predetermined conversion is performed by using a combination of path select signals with a relatively few number of merges of surviving paths as the first combination, and a combination of path select signals with a relatively large number of merges of surviving paths as the second combination. 
     
     
       13. A viterbi decoder comprising: 
       a conversion unit for applying predetermined conversion to path select signals outputted from ACS means;  
       path storage means for storing path select signals outputted from said conversion unit;  
       reverse conversion unit for applying conversion reverse to said predetermined conversion in said conversion unit to path select signals outputted from said path storage means; and  
       a decoding unit for performing decoding by using path select signals outputted from said reverse conversion unit,  
       said conversion unit so performing conversion that, out of combinations of path select signals representing surviving paths in a predetermined portion in a trellis diagram, a first combination with a relatively few number of merges of surviving paths has a predetermined fixed value which is one of signal values of path select signals more than a second combination with a relatively large number of merges of surviving paths.  
     
     
       14. The viterbi decoder of  claim 13 , wherein 
       said ACS means outputs “0” when a transition from a node 2*s 0 +0 at time t is selected, and outputs “1” when a transition from a node 2*s 0 +1 at time t is selected as a path select signal for a node s 0 +i0*2 (K−2)  at time t+1 where s 0 <2 (K−2) , s 0  is either “0” or a positive integer, and i 0 =0, 1; and  
       said conversion unit outputs an exclusive OR of PS (i 0 =0) and a logical inverse signal of PS (i 0 =1) regarding a path select signal PS for node s 0 +i0*2 (K−2)  at time t+1 as a new path select signal PS (i 0 =0).  
     
     
       15. A viterbi decoding method for performing decoding by using path storage means which stores path select signals, said viterbi decoding method comprising the steps of: 
       applying predetermined conversion to path select signals outputted from ACS means;  
       storing converted path select signals in said path storage means;  
       applying conversion reverse to said predetermined conversion to path select signals outputted from said path storage means; and  
       performing decoding by using reversely-converted path select signals,  
       said predetermined conversion being so conducted that, out of combinations of path select signals representing surviving paths in a predetermined portion in a trellis diagram, a first combination with a relatively high frequency of occurrence contains a predetermined fixed value which is one of signal values of said path select signals more than a second combination with a relatively low frequency of occurrence.  
     
     
       16. The viterbi decoding method of  claim 15 , wherein said predetermined conversion is performed by using a combination of path select signals with a relatively few number of merges of surviving paths as the first combination, and a combination of path select signals with a relatively large number of merges of surviving paths as the second combination. 
     
     
       17. The viterbi decoding method of  claim 16 , wherein said ACS means outputs “0” when a transition from a node 2*s 0 +0 at time t is selected, and outputs “1” when a transition from a node 2*s 0 +1 at time t is selected as a path select signal for a node s 0 +i0*2 (K−2)  at time t+1 where s 0 <2 (K−2) , s 0  is either 0 or a positive integer, and i 0 =0, 1; and 
       in said predetermined conversion, as for path select signals {PS (i 0 =0), PS (i 0 =1)} for node s 0 +i0*2 (K−2)  at time t+1,  
       a) {0, 1} is converted to {0, 1} 
       b) {1, 0} is converted to {0, 0} 
       c) {0, 0} is converted to {1, 0} 
       d) {1, 1} is converted to {1, 1}.