Abstract:
Disclosed herein is a decoding apparatus that performs soft-decision decoding on a linear block code, the apparatus including a hard-decision decoder configured to perform hard-decision decoding on a received word using a hard-decision decoding algorithm; and a soft-decision decoder configured to perform, using a soft-decision algorithm, soft-decision decoding merely on a received word for which the hard-decision decoder has failed in the hard-decision decoding.

Description:
CROSS REFERENCES TO RELATED APPLICATIONS 
       [0001]    The present invention contains subject matter related to Japanese Patent Application JP 2007-326156 filed in the Japan Patent Office on Dec. 18, 2007, the entire contents of which being incorporated herein by reference. 
       BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates to a decoding apparatus and a decoding method that are applicable to a digital broadcast receiver, an optical disc playback apparatus, and the like for achieving an error correction coding technology using an algebraic technique, for example. 
         [0004]    2. Description of the Related Art 
         [0005]    For algebraic geometric codes, such as Reed-Solomon codes and BCH codes, which are subfield subcodes of the Reed-Solomon codes, high-performance and low-computational cost decoding methods employing their algebraic properties are known. 
         [0006]    Suppose, for example, that a Reed-Solomon code having a code length n, an information length k, a field of definition GF(q) (q=p m , p: a prime number), and a minimum distance d=n−k is denoted as RS(n, k). It is well known that minimum distance decoding (common decoding) of decoding a hard-decision received word into a code word having a minimum Hamming distance guarantees correction of t (t&lt;d/2) erroneous symbols. 
         [0007]    Guruswami-Sudan list decoding (hereinafter referred to as “G-S list decoding”) guarantees correction of t (t&lt;√nk) erroneous symbols (see V. Guruswami and M. Sudan, Improve decoding of Reed-Solomon and Algebraic-Geometry codes, IEEE Transactions on Information Theory, vol. 45, pp. 1757-1767, 1999). 
         [0008]    Koetter-Vardy list decoding (hereinafter referred to as “K-V list decoding”), which is an extended version of the Guruswami-Sudan list decoding and uses a soft-decision received word, is, as with the Guruswami-Sudan list decoding, made up of the following four steps, (1) calculation of reliability of each symbol from received information; (2) extraction of two-variable polynomial interpolation conditions from the reliability; (3) interpolation of two-variable polynomials; and (4) factorization of interpolation polynomials and creation of a list of decoded words. It is known that the K-V list decoding has higher performance compared to when hard-decision decoding is applied (see R. Koetter and A. Vardy, Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Transactions on Information Theory, 2001). 
         [0009]    It is also known that computational cost thereof can be reduced to a practical level by re-encoding (see R. Koetter, J. Ma, A. Vardy, and A. Ahmed, Efficient Interpolation and Factorization in Algebraic Soft-Decision Decoding of Reed-Solomon codes, Proceedings of ISIT 2003). 
         [0010]    As to linear codes, low-density parity-check codes (LDPC codes) capable of achieving high performance, nearly marginal performance, through iterative decoding using belief propagation (BP) have been recently attracting attention (see D. MacKay, Good Error-Correcting Codes Based on Very Sparse Matrices, IEEE Transactions on Information Theory, 1999). 
         [0011]    It is theoretically known that the belief propagation (BP) used in the LDPC codes is generally effective merely for linear codes having a low-density parity-check matrix. Also, it is known that reducing the density of a parity-check matrix of the Reed-Solomon codes or the BCH codes is NP-hard (see Berlekamp, R. McEliece, and H. van Tilborg, On the inherent intractability of certain coding problems, IEEE Transactions on Information Theory, vol.24, pp.384-386, May, 1978). 
         [0012]    Thus, it has been considered difficult to apply the belief propagation (BP) to the Reed-Solomon codes or the BCH codes. 
         [0013]    However, in 2004, Narayanan et al. suggested that application of the belief propagation (BP) to the Reed-Solomon codes, the BCH codes, or linear codes having a parity-check matrix that is not low in density using a parity-check matrix as diagonalized in accordance with the reliability of a received word is effective (see Jing Jiang and K. R. Narayan, Soft Decision Decoding of RS Codes Using Adaptive Parity Check Matrices, Proceeding of IEEE International Symposium on Information Theory 2004). 
         [0014]    This technique is called adaptive belief propagation (ABP) decoding. 
         [0015]      FIG. 1  is a flowchart illustrating ABP decoding that has been proposed. 
         [0016]    At step ST 1 , a reliability order of the received word is investigated, and at step ST 2 , order conversion is performed. 
         [0017]    At step ST 3 , a parity-check matrix is diagonalized in accordance with the converted order, and at step ST 4 , the belief propagation (BP) is performed using the resulting parity-check matrix. 
         [0018]    Next, LLR is calculated at step ST 5 , a reliability order of the calculated LLR is investigated at step ST 6 , and decoding is performed at step ST 7 . 
         [0019]    Thereafter, the above procedure is performed iteratively until iterative decoding termination conditions SC 1  and SC 2  are satisfied at steps ST 8  and ST 9 . 
       SUMMARY OF THE INVENTION 
       [0020]    Linear block codes, typified by the Reed-Solomon codes, are widely used as an error-correcting code for digital broadcasting and optical disc standards. 
         [0021]    As a decoding algorithm for the linear block codes, a decoding algorithm called bounded distance decoding is commonly used. In this bounded distance decoding, a decoding operation is performed based on a hard-decision received value, i.e., a received value in which each bit is quantized to zero or one (this quantization is referred to as “hard decision”). 
         [0022]    In contrast, in the case where convolution codes are subjected to Viterbi decoding, for example, the decoding operation is commonly performed using a received value that has been subjected to quantization with gradations (this quantization is referred to as “soft decision”), when the received value has passed through a communication channel allowing continuous values. 
         [0023]    This decoding method is called soft-decision decoding. In the case of the Viterbi decoding for the convolution codes, for example, it is known that the soft-decision decoding achieves a coding gain of 2 to 3 dB relative to the hard-decision decoding. 
         [0024]    Accordingly, there has been an attempt in recent years to employ the soft-decision decoding for the received value that has passed through the communication channel allowing continuous values, even in the case of the linear block codes such as the Reed-Solomon code, in order to improve decoding performance. 
         [0025]    Several different algorithms have been proposed as soft-decision decoding algorithms for the linear block codes. One of such algorithms is the ABP decoding, proposed by J. Jiang and K. R. Narayanan. The ABP decoding is considered prospective as a decoding algorithm that achieves a coding gain of approximately 1 dB with a practical amount of computation. 
         [0026]    However, all of the soft-decision algorithms for the linear block codes, including the ABP decoding algorithm, involve a higher amount of computation than the bounded distance decoding as known. Therefore, in order to realize real-time processing at a playback rate of a broadcast receiver or an optical disc, it is necessary to have computing units in parallel within a decoder or to provide a plurality of decoders, thus improving throughput, for example. 
         [0027]    In general, this inevitably results in a significant increase in circuit scale, in comparison to a decoder that is based on any known bounded distance decoding algorithm. 
         [0028]    As described above, any soft-decision decoder with a high throughput designed for the linear block codes has a disadvantage of the significant increase in circuit scale, compared to the decoder that is based on any known bounded distance decoding algorithm. 
         [0029]    The embodiment of the present invention addresses the above-identified, and other problems associated with existing methods and apparatuses, and provides a decoding apparatus and a decoding method that make it possible to significantly reduce the circuit scale of the decoder, compared to that of any known soft-decision decoder, while ensuring improved decoding performance of the soft-decision decoding. 
         [0030]    According to one embodiment of the present invention, there is provided a decoding apparatus that performs soft-decision decoding on a linear block code, the apparatus including a hard-decision decoder configured to perform hard-decision decoding on a received word using a hard-decision decoding algorithm; and a soft-decision decoder configured to perform, using a soft-decision algorithm, soft-decision decoding merely on a received word for which the hard-decision decoder has failed in the hard-decision decoding. 
         [0031]    According to another embodiment of the present invention, there is provided a decoding method for performing soft-decision decoding on a linear block code, the method including the steps of first applying a hard-decision decoding algorithm to a received word to perform hard-decision decoding on the received word; and applying a soft-decision algorithm merely to a received word for which the hard-decision decoding may be impossible to perform the soft-decision decoding on that received word. 
         [0032]    The proportion of received words that may not be decoded with a hard-decision algorithm to the whole received words is generally very small. Thus, according to the embodiment of the present invention, the soft-decision decoding employing the soft-decision algorithm may take a period of time corresponding to a plurality of code words for one received word. This eliminates the need to parallelize computing units within the decoder, the need to provide a plurality of decoders, and so on. 
         [0033]    According to the embodiment of the present invention, it is possible to reduce the circuit scale of the decoder significantly relative to any known soft-decision decoder, while maintaining improved decoding performance of the soft-decision decoding. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0034]      FIG. 1  is a flowchart illustrating ABP decoding that has been proposed; 
           [0035]      FIG. 2  is a block diagram illustrating an exemplary structure of a soft-decision decoding apparatus designed for a linear block code and which adopts a decoding method according to one embodiment of the present invention; and 
           [0036]      FIGS. 3A to 3F  show a timing diagram in the case where, in the soft-decision decoding apparatus as shown in  FIG. 2 , bounded distance decoding after hard decision for received word ends in failure. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0037]    Hereinafter, an embodiment of the present invention will be described in conjunction with the accompanying drawings. 
         [0038]      FIG. 2  is a block diagram illustrating an exemplary structure of a soft-decision decoding apparatus  100  designed for a linear block code and which adopts a decoding method according to one embodiment of the present invention. 
         [0039]    As shown in  FIG. 2 , the soft-decision decoding apparatus  100  according to the present embodiment includes a threshold processing circuit  101 , a Reed-Solomon code hard-decision decoder  102 , buffers  103  and  104 , a Reed-Solomon code soft-decision decoder  105 , and a selector  106 . 
         [0040]    In addition, “S 100 ” refers to a soft received value signal, “S 101 ” refers to a hard received value signal, “S 102 ” refers to a hard-decision decoded word signal, “S 103 ” refers to a delayed hard-decision decoded word signal, “S 104 ” refers to a hard-decision decoding failure signal, “S 105 ” refers to a delayed soft received value signal, “S 106 ” refers to a soft-decision decoded word signal, and “S 107 ” refers to a decoding result signal. 
         [0041]    In the soft-decision decoding apparatus  100  as shown in  FIG. 2 , the soft received value signal S 100  is inputted to the threshold processing circuit  101 . 
         [0042]    The threshold processing circuit  101  performs threshold processing on the inputted soft received value signal S 100 , and outputs the resulting hard received value signal S 101 . 
         [0043]    The hard received value signal S 101  is inputted to the Reed-Solomon code hard-decision decoder  102 . 
         [0044]    The Reed-Solomon code hard-decision decoder  102  subjects the inputted hard received value signal S 101  to bounded distance decoding, and outputs the resulting hard-decision decoded word signal S 102 . 
         [0045]    In the case where it may be impossible to correct an error present in the inputted hard received value signal S 101  using the bounded distance decoding, the Reed-Solomon code hard-decision decoder  102  outputs the hard-decision decoding failure signal S 104 . 
         [0046]    The hard-decision decoded word signal S 102  is inputted to the buffer  103 . The buffer  103  stores the hard-decision decoded word signal S 102  in a memory primarily, and, after delaying the data by a delay time of the Reed-Solomon code soft-decision decoder  105 , outputs the delayed hard-decision decoded word signal S 103 . 
         [0047]    Meanwhile, the soft received value signal S 100  is inputted to the buffer  104  as well. 
         [0048]    The buffer  104  stores the soft received value signal S 100  in a memory temporarily, and, after delaying the data by a delay time of the Reed-Solomon code hard-decision decoder  102 , outputs the delayed soft received value signal S 105 . 
         [0049]    The delayed soft received value signal S 105  is inputted to the Reed-Solomon code soft-decision decoder  105 . 
         [0050]    Merely when the hard-decision decoding failure signal S 104  has been inputted from the Reed-Solomon code hard-decision decoder  102  to the Reed-Solomon code soft-decision decoder  105 , the Reed-Solomon code soft-decision decoder  105  performs soft-decision decoding on the delayed soft received value signal S 105  based on the ABP decoding, for example, and outputs the resulting soft-decision decoded word signal S 106 . This soft-decision decoding takes a period of time corresponding to a plurality of received words. 
         [0051]    The delayed hard-decision decoded word signal S 103  and the soft-decision decoded word signal S 106  are both inputted to the selector  106 . 
         [0052]    As a decoded word for any received word that has been hard-decision decoded successfully, the selector  106  selects the delayed hard-decision decoded word signal S 103 , whereas as a decoded word for any received word that has not been hard-decision decoded successfully, the selector  106  selects the soft-decision decoded word signal S 106 . The selector  106  outputs the selected signal as the decoding result signal S 107 . 
         [0053]    Next, an operation of the soft-decision decoding apparatus  100  as shown in  FIG. 2  will now be described below with reference to a timing diagram of  FIGS. 3A to 3F . 
         [0054]      FIGS. 3A to 3F  show a timing diagram in the case where, in the soft-decision decoding apparatus  100  as shown in  FIG. 2 , the bounded distance decoding after the hard decision for received word  4  ends in failure. It is assumed in this example that the soft-decision decoding takes a period of time corresponding to four code words. 
         [0055]      FIG. 3A  shows the soft received value signal S 100 .  FIG. 3B  shows the hard-decision decoded word signal S 102 .  FIG. 3C  shows the delayed soft received value signal S 105 .  FIG. 3D  shows the soft-decision decoded word signal S 106 .  FIG. 3E  shows the delayed hard-decision decoded word signal S 103 .  FIG. 3F  shows the decoding result signal S 107 . 
         [0056]    As shown in  FIGS. 3A to 3F , in the circuit according to this embodiment of the present invention, the soft-decision decoding is applied merely when the bounded distance decoding after the hard decision has ended in failure. Thus, after all received values are subjected to error correction, final decoded words can be outputted in chronological order. 
         [0057]    Here, in the above example, the soft-decision decoding takes the period of time corresponding to four code words. This means that the throughput of the Reed-Solomon code soft-decision decoder  105  may be as less as approximately a quarter of system throughput. 
         [0058]    Accordingly, in the case where a plurality of soft-decision decoders are provided to achieve high throughput, the number of soft-decision decoders can be reduced to a quarter. 
         [0059]    As a matter of course, in the case where received words for which the bounded distance decoding ends in failure come in succession, for example, one or more received words may not be subjected to the soft-decision decoding. 
         [0060]    However, in actual applications such as a broadcast receiver and an optical disc player, the proportion of the received words for which the bounded distance decoding ends in failure to the whole received words is far less than 1/1000. 
         [0061]    Therefore, the probability that received words for which the bounded distance decoding ends in failure come in succession is negligibly small, and the decoding performance of the entire system would be little affected even if the soft-decision decoder were configured to desire a period of time corresponding to 100 code words to perform the soft-decision decoding on the delayed soft received value signal S 105 . 
         [0062]    Thus, there is not a need to provide a plurality of soft-decision decoders to achieve high throughput. In general, the circuit scale of the soft-decision decoders is several times as large as that of hard-decision decoders. Therefore, elimination of the need to provide a plurality of soft-decision decoders results in a significant reduction in circuit scale of the entire system. 
         [0063]    Moreover, while in the case where an ABP decoder is used as the soft-decision decoder, for example, a mechanism for parallel matrix diagonalization may be desired to achieve high throughput, the need for parallelization of computation within this type of soft-decision decoders is also eliminated. 
         [0064]    Thus, a further reduction in circuit scale may be achieved. 
         [0065]    Still further, common broadcast receivers, for example, have a buffer for smoothing a moving picture experts group (MPEG) transport stream at a final stage of a decoding section. Provision of such an output buffer within a system is not limited to the broadcast receivers but is common with various devices. 
         [0066]    Accordingly, such an output buffer may be employed as the buffer  103  for the hard-decision decoded word signal S 102  as shown in  FIG. 2 . This contributes to reducing the increase in the number of buffers. 
         [0067]    In the above-described embodiment, the linear block code to be decoded is assumed to be the Reed-Solomon code. Note, however, that the linear block code to be decoded is not limited to the Reed-Solomon code but may be any linear block code. 
         [0068]    As described above, the present embodiment eliminates the need to parallelize the computing units within the decoder, the need to provide a plurality of decoders, and so on. This contributes to reducing the circuit scale of the decoder as a whole significantly, while maintaining the decoding performance. 
         [0069]    Note that the decoding method described in detail above can be formed as a program that accords with the above-described procedure and which is to be executed by a computer such as a CPU. 
         [0070]    Also note that such a program may be stored in a storage medium such as a semiconductor memory, a magnetic disk, an optical disc, or a floppy (registered trademark) disk, so that a computer may access and execute the program when the storage medium is attached thereto. 
         [0071]    It should be understood by those skilled in the art that various modifications, combinations, sub-combinations and alterations may occur depending on design requirements and other factor in so far as they are within the scope of the appended claims or the equivalents thereof.