Error correction circuit and error correction method

Abstract

The present invention provides an error correction circuit for receiving and decoding a trellis-encoded signal of a series of data Z q , Z q−1 , . . . ,Z 1 which comprises convolutional-encoded bits and unencoded bits, the convolutional-encoded bits being obtained by convolutional-encoding lower t bits X t , X t−1 , . . . ,X 1 of an input p-bit series of data X p , X p−1 , . . . ,X 1 (where p≧2, q≧p, and p>t≧1), and the unencoded bits being obtained by not convolutional-encoding upper (p-t) bits thereof. The circuit includes: a maximum likelihood decoder for preselecting one of m parallel paths of transition from state x at time k to state y at time k+1.

What is claimed is:  
     
         1 . An error correction circuit for receiving and decoding a trellis-encoded signal of a series of data Z q , Z q−1 , . . . ,Z 1  which comprises convolutional-encoded bits and unencoded bits, the convolutional-encoded bits being obtained by convolutional-encoding lower t bits X t , X t−1 , . . . ,X 1  of an input p-bit series of data X p , X p−1 , . . . , X 1  (where p≧2, q≧p, and p>t≧1), and the unencoded bits being obtained by not convolutional-encoding upper (p-t) bits thereof, the circuit comprising: 
 a maximum likelihood decoder for preselecting one of m parallel paths of transition from state x at time k to state y at time X+1.  
 
     
     
         2 . An error correction circuit according to  claim 1 , wherein the maximum likelihood decoder comprises: 
 a selection section for selecting one of the m parallel paths transition from state x at time k to state y at time k+1; and    a calculation section for obtaining a path metric using a branch metric.    
     
     
         3 . An error correction circuit according to  claim 1 , wherein: 
 the error correction circuit receives and decodes data which is produced by mapping the series of data Z q , Z q−1 , . . . ,Z 1  onto j points;    the series of data Z q , Z q−1 , . . . ,Z 1  is obtained by performing a trellis encoding operation on a first series of data Y r , Y r−1 , . . . ,Y t+1  (r>t≧1) and a second series of data Y t , Y t−1 , . . . ,Y 1 , the first series of data being obtained by preceding upper bits of the input series of data X p , X p−1 , . . . , X 1  (p≧2), and the second series of data comprising lower bits of the input series of data X p , X p−1 , . . . , X 1 ;    the maximum likelihood decoder is operable to perform n different maximum likelihood decoding methods for maximum-likelihood-decoding the received data based on a plurality of states, wherein the maximum likelihood decoder selects one of the n maximum likelihood decoding methods so as to maximum-likelihood-decode the received data based on the selected maximum likelihood decoding method.    
     
     
         4 . An error correction circuit according to  claim 3 , further comprising a postcoder for postcoding or not postcoding the decoded data from the maximum likelihood decoder, wherein whether the decoded data is postcoded or not depends upon the n maximum likelihood decoding methods.  
     
     
         5 . An error correction circuit according to  claim 3 , wherein the maximum likelihood decoder further comprises: 
 a branch metric production section for producing first path information indicating the selected path and a branch metric according to the n maximum likelihood decoding methods;    a calculation section for obtaining a path metric based on the branch metric obtained by the branch metric production section and for obtaining second path information based on the path metric;    a path metric memory for storing the path metric obtained by the calculation section;    a path memory for storing the first path information obtained by the selection section and the second path information obtained by the calculation section; and a trace back section for obtaining decoded data based on the path metric obtained by the calculation section and the first and second path information stored in the path memory.    
     
     
         6 . An error correction circuit according to  claim 3 , wherein the maximum likelihood decoder further comprises: 
 a branch metric production section for producing first path information indicating the selected path and a branch metric based on the n maximum likelihood decoding methods;    a calculation section for obtaining a path metric based on the branch metric obtained by the branch metric production section and for obtaining second path information based on the path metric;    a path-metric memory for storing the path metric obtained by the calculation section;    a path memory for storing the first path information obtained by the selection section and the second path information obtained by the calculation section; and    a register exchange section for obtaining the decoded data based on the path information and the path metric obtained by the calculation section and the candidate for the decoded data comprising the first path information and the second path information stored in the path memory.    
     
     
         7 . An error correction circuit according to  claim 4 , wherein the postcoder comprises a memory for storing upper bits of the decoded data from the maximum likelihood decoder.  
     
     
         8 . An error correction circuit according to  claim 3 , wherein: 
 the maximum likelihood decoder comprises a branch metric production section; and    the branch metric production section references contents of a diagram so as to derive first path information indicating the selected path and a branch metric from the received data, wherein the contents of the diagram are obtained by associating the first series of data Y r , Y r−1 , . . . ,Y t+1 , the second series of data Y t , Y t−1 , . . . ,Y 1 , and the received data, which is produced by mapping the series of data Z q , Z q−1 , . . . ,Z 1  onto j points, with one another.    
     
     
         9 . An error correction circuit according to  claim 3 , wherein: 
 the maximum likelihood decoder comprises a branch metric production section; and    the branch metric production section references contents of a diagram so as to derive first path information indicating the selected path and a branch metric from data which is obtained by passing the received data through a linear filter, wherein the contents of the diagram are obtained by associating the series of data X p , X p−1 , . . . ,X 1  and data obtained by passing, through the linear filter, data which is produced by mapping the series of data Z q , Z q−1 , . . . ,Z 1  onto j points, with each other.    
     
     
         10 . An error correction circuit according to  claim 9 , wherein the linear filter comprises a comb filter.  
     
     
         11 . An error correction circuit according to  claim 3 , wherein: 
 the maximum likelihood decoder comprises a branch metric production section; and    the branch metric production section references contents of a diagram so as to derive a candidate for the decoded data and a branch metric from the received data, wherein the contents of the diagram are obtained by associating the first series of data Y r , Y r−1 , . . . ,Y t−1  the second series of data Y t , Y t−1 , . . . ,Y 1 , and the received data, which is produced by mapping the series of data Z q , Z q−1 , . . . ,Z 1  onto j points, with one another.    
     
     
         12 . An error correction circuit according to  claim 3 , wherein: 
 the maximum likelihood decoder comprises a branch metric production section; and    the branch metric production section references contents of a diagram so as to derive a candidate for the decoded data and a branch metric from data obtained by passing the received data through a linear filter, wherein the contents of the diagram are obtained by associating the series of data X p , X p−1 , . . . ,X 1  and data obtained by passing, through the linear filter, data which is produced by mapping the series of data Z q , Z q−1 , . . . ,Z 1  onto j points, with each other.    
     
     
         13 . An error correction circuit according to  claim 12 , wherein the linear filter comprises a comb filter.  
     
     
         14 . An error correction circuit according to  claim 3 , wherein the maximum likelihood decoder performs a decoding operation using a Viterbi algorithm.  
     
     
         15 . An error correction circuit according to  claim 1 , wherein: 
 the error correction circuit receives and decodes data which is produced by mapping the trellis-encoded signal onto a 2-dimensional data series; and    the error correction circuit further comprises a section for demapping a series of data which is obtained through a maximum likelihood decoding operation on the 2-dimensional data series by the maximum likelihood decoder.    
     
     
         16 . An error correction circuit according to  claim 15 , further comprising a section for delaying the demapped series of data.  
     
     
         17 . An error correction circuit according to  claim 1 , wherein: 
 the error correction circuit receives and decodes data which is produced by mapping the trellis-encoded signal onto a 2-dimensional data series:    the c-bit trellis-encoded signal is a series of data Z q , Z q−1 , . . . ,Z 1  which comprises convolutional-encoded bits and unencoded bits, the convolutional-encoded bits being obtained by performing a differential encoding operation on lower t bits X t , X t=1 , . . . ,X 1  of the input p-bit series of data X p , X p−1 , . . . ,X 1  (where p≧2, q≧p, and p>t≧1) and convolutional-encoding the differential-encoded bits, and the unencoded bits being obtained by not convolutional-encoding upper (p-t) bits thereof; and    the error correction circuit further comprises: 
 a section for performing a differential decoding operation on a first series of data which is produced through a maximum likelihood decoding operation on the 2-dimensional data series by the maximum likelihood decoder; and  
 a section for demapping a second series of data which is produced through a maximum likelihood decoding operation on the 2-dimensional data series by the maximum likelihood decoder.  
   
     
     
         18 . An error correction circuit according to  claim 17 , further comprising a section for delaying the demapped series of data.  
     
     
         19 . An error correction circuit according to  claim 1 , wherein: 
 the error correction circuit receives and decodes data which is produced by mapping the trellis-encoded signal onto a 2-dimensional data series;    the c-bit trellis-encoded signal is a series of data Z q , Z q−1 , . . . ,Z 1  which comprises punctured bits and unencoded bits, the punctured bits being obtained by convolutional-encoding lower t bits X t , X t−1 , . . . ,X 1  of the input p-bit series of data X p , X p−1 , . . . ,X 1  (where p≧2, g≧p, and p>t≧1) and puncturing the convolutional-encoded bits, and the unencoded bits being obtained by not convolutional-encoding upper (p-t) bits thereof; and    the error correction circuit further comprises: 
 a section for depuncturing the 2-dimensional data series;  
 a section for puncturing a second series of data which is produced through a maximum likelihood decoding operation on the depunctured series of data by the maximum likelihood decoder; and  
 a section for demapping the punctured series of data.  
   
     
     
         20 . An error correction circuit according to  claim 19 , further comprising a section for delaying the demapped series of data.  
     
     
         21 . An error correction circuit according to  claim 1 , wherein: 
 the error correction circuit receives and decodes data which is produced by mapping the trellis-encoded signal onto a 2-dimensional data series;    the c-bit trellis-encoded signal is a series of data Z q , Z q−1 , . . . ,Z 1  which comprises punctured bits and unencoded bits, the punctured bits being obtained by performing a differential encoding operation on lower t bits X t , X t−1 , . . . ,X 1  of the input p-bit series of data X p , X p−1 , . . . , X 1  (where p≧2, q≧p, and p>t≧1), convolutional-encoding the differential-encoded bits, and puncturing the convolutional-encoded bits, and the unencoded bits being obtained by not convolutional-encoding upper (p-t) bits thereof; and    the error correction circuit further comprises: 
 a section for depuncturing the 2-dimensional data series;  
 a section for performing a differential decoding operation on a first series of data which is produced through a maximum likelihood decoding operation on the depunctured series of data by the maximum likelihood decoder;  
 a section for puncturing a second series of data which is produced through a maximum likelihood decoding operation on the depunctured series of data by the maximum likelihood decoder; and  
 a section for demapping the punctured series of data.  
   
     
     
         22 . An error correction circuit according to  claim 21 , further comprising a section for delaying the demapped series of data.  
     
     
         23 . An error correction circuit according to  claim 1 , wherein the maximum likelihood decoder comprises: 
 a section for producing a branch metric;    a section for addition, comparison and selection of branch metrics and path metrics:    a path metric memory for storing a plurality of path metrics:    a plurality of path memories; and    a trace back processing section for outputting a first series of data which is obtained by decoding a series of encoded data, and a second series of data which is obtained by decoding a series of data which contains information of a series of unencoded data.    
     
     
         24 . An error correction circuit according to  claim 1 , wherein the maximum likelihood decoder comprises: 
 a section for producing a branch metric;    a section for addition, comparison and selection of branch metrics and path metrics;    a path metric memory for storing a plurality of path metrics;    a plurality of path memories; and    a register exchange section for outputting a first series of data which is obtained by decoding a series of encoded data, and a second series of data which is obtained by decoding a series of data which contains information of a series of unencoded data.    
     
     
         25 . An error correction circuit, comprising a maximum likelihood decoder for performing a maximum likelihood decoding operation on a series of data, wherein the maximum likelihood decoder comprises: 
 a section for producing a branch metric:    a section for addition, comparison and selection of branch metrics and path metrics;    a path metric memory for storing a plurality of path metrics;    a plurality of path memories; and    a trace back processing section for outputting a first series of data which is obtained by decoding a series of encoded data, and a second series of data which is obtained by decoding a series of data which contains information of a series of unencoded data.    
     
     
         26 . An error correction circuit, comprising a maximum likelihood decoder for performing a maximum likelihood decoding operation on a series of data, wherein the maximum likelihood decoder comprises: 
 a section for producing a branch metric;    a section for addition, comparison and selection of branch metrics and path metrics;    a path metric memory for storing a plurality of path metrics;    a plurality of path memories; and    a register exchange section for outputting a first series of data which is obtained by decoding a series of encoded data, and a second series of data which is obtained by decoding a series of data which contains information of a series of unencoded data.    
     
     
         27 . An error correction method for receiving and decoding a trellis-encoded signal of a series of data Z q , Z q−1 , . . . ,Z 1  which comprises convolutional-encoded bits and unencoded bits, the convolutional-encoded bits being obtained by convolutional-encoding lower t bits X t , X t−1 , . . . ,X 1  of an input p-bit series of data X p , X p , . . . ,X 1  (where p≧2, q≧p, and p>t≧1), and the unencoded bits being obtained by not convolutional-encoding upper (p-t) bits thereof, the method comprising: 
 a maximum likelihood decoding step of preselecting one of m parallel paths of transition from state x at time k to state y at time k+1.  
 
     
     
         28 . An error correction method according to  claim 27 , wherein the maximum likelihood decoding step comprises: 
 a selection step of selecting one of the m parallel paths transition from state x at time k to state y at time k+1; and    a calculation step of obtaining a path metric using a branch metric.    
     
     
         29 . An error correction method according to  claim 27 , wherein: 
 the error correction method is for receiving and decoding data which is produced by mapping the series of data Z q , Z q−1 , . . . ,Z 1  onto j points:    the series of data Z q , Z q−1 , . . . ,Z 1  is obtained by performing a trellis encoding operation on a first series of data Y r , Y r−1 , . . . ,Y t+1  (r>t≧1) and a second series of data Y t , Y t−1 , . . . ,Y 1 , the first series of data being obtained by precoding upper bits of the input series of data X p , X p , . . . ,X 1  (p≧2), and the second series of data comprising lower bits of the input series of data X p , X p−1 , . . . ,X 1 ;    the maximum likelihood decoding step is operable to perform n different maximum likelihood decoding methods for maximum-likelihood-decoding the received data based on a plurality of states, wherein the maximum likelihood decoder selects one of the n maximum likelihood decoding methods so as to maximum-likelihood-decode the received data based on the selected maximum likelihood decoding method.    
     
     
         30 . An error correction method according to  claim 29 , further comprising a postcoding step of postcoding or not postcoding the decoded data from the maximum likelihood decoding step, wherein whether the decoded data is postcoded or not depends upon the n maximum likelihood decoding methods.  
     
     
         31 . An error correction method according to  claim 29 , wherein the maximum likelihood decoding step comprises: 
 a branch metric production step of producing first path information indicating the selected path and a branch metric according to the n maximum likelihood decoding methods:    a calculation step of obtaining a path metric based on the branch metric obtained in the branch metric production step and obtaining second path information based on the path metric;    a path metric memory step of storing the path metric obtained in the calculation step;    a path memory step of storing the first path information obtained in the selection step and the second path information obtained in the calculation step; and    a trace back step of obtaining decoded data based on the path metric obtained in the calculation step and the first and second path information stored in the path memory step.    
     
     
         32 . An error correction method according to  claim 29 , wherein the maximum likelihood decoding step comprises: 
 a branch metric production step of producing first path information indicating the selected path and a branch metric based on the n maximum likelihood decoding methods:    a calculation step of obtaining a path metric based on the branch metric obtained in the branch metric production step and obtaining second path information based on the path metric;    a path metric memory step of storing the path metric obtained in the calculation step;    a path memory step of storing the first path information obtained in the selection step and the second path information obtained in the calculation step; and    a register exchange step of obtaining the decoded data based on the path information and the path metric obtained in the calculation step and the candidate for the decoded data comprising the first path information and the second path information stored in the path memory step.    
     
     
         33 . An error correction method according to  claim 30 , wherein the postcoder comprises a step of storing upper bits of the decoded data from the maximum likelihood decoding step.  
     
     
         34 . An error correction method according to  claim 29 , wherein: 
 the maximum likelihood decoding step comprises a branch metric production step; and    the branch metric production step comprises referencing contents of a diagram so as to derive first path information indicating the selected path and a branch metric from the received data, wherein the contents of the diagram are obtained by associating the first series of data Y r , Y r−1 , . . . ,Y t+1 , the second series of data Y t , Y t−1 , . . . ,Y 1 , and the received data, which is produced by mapping the series of data Z q , Z q−1 , . . . ,Z 1  onto j points, with one another.    
     
     
         35 . An error correction method according to  claim 29 , wherein: 
 the maximum likelihood decoding step comprises a branch metric production step; and    the branch metric production step comprises referencing contents of a diagram so as to derive first path information indicating the selected path and a branch metric from data which is obtained by passing the received data through a linear filter, wherein the contents of the diagram are obtained by associating the series of data X p , X p−1 , . . . ,X 1  and data obtained by passing, through the linear filter, data which is produced by mapping the series of data Z q , Z q−1 , . . . ,Z 1  onto j points, with each other.    
     
     
         36 . An error correction method according to  claim 35 , wherein the linear filter comprises a comb filter.  
     
     
         37 . An error correction method according to  claim 29 , wherein: 
 the maximum likelihood decoding step comprises a branch metric production step; and    the branch metric production step comprises referencing contents of a diagram so as to derive a candidate for the decoded data and a branch metric from the received data, wherein the contents of the diagram are obtained by associating the first series of data Y r , Y r−1 , . . . ,Y t+1 , the second series of data Y t , Y t−1 , . . . ,Y 1 , and the received data, which is produced by mapping the series of data Z q , Z q−1 , . . . ,Z 1  onto j points, with one another.    
     
     
         38 . An error correction method according to  claim 29 , wherein: 
 the maximum likelihood decoding step comprises a branch metric production step; and    the branch metric production step comprises referencing contents of a diagram so as to derive a candidate for the decoded data and a branch metric from data obtained bypassing the received data through a linear filter, wherein the contents of the diagram are obtained by associating the series of data X p , X p−1 , . . . ,X 1  and data obtained by passing, through the linear filter, data which is produced by mapping the series of data Z q , Z q−1 , . . . ,Z 1  onto j points, with each other.    
     
     
         39 . An error correction method according to  claim 38 , wherein the linear filter comprises a comb filter.  
     
     
         40 . An error correction method according to  claim 29 , wherein the maximum likelihood decoding step comprises performing a decoding operation using a Viterbi algorithm.