6. The decoding apparatus according to claim 1 wherein the means for repeatedly carrying out decoding comprises: means for recognizing an order of reliability levels of symbols included in the coded word held with the attached known information; means for carrying out a diagonalization process on a parity check matrix on the basis of information corresponding to a reliability-level order recognized by the means for recognizing; means for updating a message by carrying out a belief propagation process through use of the parity check matrix that is subjected to the diagonalization process; means for computing log likelihood ratios by using the updated message and the symbols of the coded word; means for recognizing an order of reliability levels of the computed log likelihood ratios; means for carrying out a decoding process by using the computed log likelihood ratios; means for producing a first result of determination as to whether or not a first condition for termination of the repeatedly performed decoding processing is satisfied; means for producing a second result of determination as to whether or not a second condition for termination of the repeatedly performed decoding processing is satisfied; and means for executing control controlling the means for recognizing an order of reliability levels of symbols included in the coded word, the means for carrying out the diagonalization, the means for updating, the means for computing, the means for recognizing an order of reliability of levels of the computed log likelihood ratios, and the means for carrying out the decoding process to repeatedly carry out their respective processes till a predetermined process termination condition is satisfied based on the first and second determination result.
6. The decoding apparatus according to claim 1 wherein the means for repeatedly carrying out decoding comprises: means for recognizing an order of reliability levels of symbols included in the coded word held with the attached known information; means for carrying out a diagonalization process on a parity check matrix on the basis of information corresponding to a reliability-level order recognized by the means for recognizing; means for updating a message by carrying out a belief propagation process through use of the parity check matrix that is subjected to the diagonalization process; means for computing log likelihood ratios by using the updated message and the symbols of the coded word; means for recognizing an order of reliability levels of the computed log likelihood ratios; means for carrying out a decoding process by using the computed log likelihood ratios; means for producing a first result of determination as to whether or not a first condition for termination of the repeatedly performed decoding processing is satisfied; means for producing a second result of determination as to whether or not a second condition for termination of the repeatedly performed decoding processing is satisfied; and means for executing control controlling the means for recognizing an order of reliability levels of symbols included in the coded word, the means for carrying out the diagonalization, the means for updating, the means for computing, the means for recognizing an order of reliability of levels of the computed log likelihood ratios, and the means for carrying out the decoding process to repeatedly carry out their respective processes till a predetermined process termination condition is satisfied based on the first and second determination result. 11. The decoding apparatus according to claim 6 wherein the means for carrying out the diagnalization process carries out a diagonalization process by using reliability levels obtained as a result of an updating process and by using an algebraic-geometry codes or codes of the same type as the algebraic-geometry codes in a finite field F (q=p m ) where p is a prime number.