Method and apparatus for decoding non-binary parity check code

Abstract

A method of decoding a non-binary Low Density Parity Check (LDPC) code is provided. The method includes a plurality of messages to perform hard decision for all messages except for one message, and combines the hard-decided values with the one message that is not hard-decided, to update a final output message.

Claims

1. A method of decoding a non-binary low density parity check (LDPC) code, the method comprising: receiving a plurality of messages from a plurality of variable nodes connected to a check node and hard-deciding the messages except for one message from a variable node among the plurality of variable nodes; and combining the hard-decided values with the one message that is not hard-decided, to update a final output message.

2. The method of claim 1, wherein the one message that is not hard-decided is determined to have a lowest reliability from a previously-defined reliability measurement vector.

3. The method of claim 2, wherein the reliability measurement vector has a different value for each codeword symbol and a size of the reliability measurement vector is equal to a number of non-binary symbols of a single codeword.

4. The method of claim 2, wherein, when the codeword symbol is hard-decided, values of the reliability measurement vector have a probability value that the codeword symbol is hard-decided for each of the non-binary symbols or a value corresponding thereto.

5. The method of claim 2, wherein, when decoding fails, the reliability measurement vector is updated according to a predetermined rule until a decoding counter reaches a predetermined maximum value, and the hard decision is performed again.

6. An apparatus for decoding a non-binary low density parity check (LDPC) code, the apparatus comprising: a hard decision unit configured to receive a plurality of messages from a plurality of variable nodes connected to a check node and hard-decide the messages except for one message from a variable node among the plurality of variable nodes; and an output unit configured to combine the hard-decided values with the one message that is not hard-decided and update a final output message.

7. The apparatus of claim 6, wherein the hard decision unit is further configured to determine that the one message that is not hard-decided has a lowest reliability from a previously-defined reliability measurement vector.

8. The apparatus of claim 7, wherein the reliability measurement vector has a different value for each codeword symbol and a size of the reliability measurement vector is equal to a number of non-binary symbols of a single codeword.

9. The apparatus of claim 7, wherein, when the codeword symbol is hard-decided, values of the reliability measurement vector have a probability value that the codeword symbol is hard-decided for each of the non-binary symbols or a value corresponding thereto.

10. The apparatus of claim 7, further comprising a reliability measurement vector updating unit configured to: update, when decoding fails, the reliability measurement vector according to a predetermined rule until a decoding counter reaches a predetermined maximum value, wherein the hard decision unit is further configured to perform the hard decision on the basis of the updated reliability measurement vector.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The above and other aspects, features, and advantages of certain embodiments of the present disclosure will be more apparent from the following description taken in conjunction with the accompanying drawings, in which:

(2) FIG. 1 illustrates a block diagram of a transmitter and a receiver according to an embodiment of the present disclosure;

(3) FIG. 2 illustrates an example of a factor graph of a non-binary LDPC code according to an embodiment of the present disclosure;

(4) FIG. 3 illustrates that a check node and a permutation node of are approximated to a permutation node of through the Extended Iterative Soft-reliability Based Majority-logic (EISBM) decoding according to an embodiment of the present disclosure;

(5) FIG. 4 is a flowchart of a decoding procedure according to an embodiment of the present disclosure; and

(6) FIG. 5 is a block diagram illustrating a configuration of an apparatus for decoding according to an embodiment of the present disclosure.

(7) Throughout the drawings, it should be noted that like reference numbers are used to depict the same or similar elements, features, and structures.

DETAILED DESCRIPTION

(8) The following description with reference to the accompanying drawings is provided to assist in a comprehensive understanding of various embodiment of the present disclosure as defined by the claims and their equivalents. It includes various specific details to assist in that understanding but these are to be regarded as merely exemplary. Accordingly, those of ordinary skill in the art will recognize that various changes and modifications of the various embodiments described herein can be made without departing from the scope and spirit of the present disclosure. In addition, descriptions of well-known functions and constructions may be omitted for clarity and conciseness.

(9) The terms and words used in the following description and claims are not limited to the bibliographical meanings, but, are merely used by the inventor to enable a clear and consistent understanding of the present disclosure. Accordingly, it should be apparent to those skilled in the art that the following description of various embodiments of the present disclosure is provided for illustration purpose only and not for the purpose of limiting the present disclosure as defined by the appended claims and their equivalents.

(10) It is to be understood that the singular forms a, an, and the include plural referents unless the context clearly dictates otherwise. Thus, for example, reference to a component surface includes reference to one or more of such surfaces.

(11) Embodiments of the present disclosure, which will be described below, disclose a method of restoring loss and distortion of data in all electronic devices such as a mobile phone, a TeleVision (TV), a Personal Computer (PC), an electronic board, a tablet PC, and an electronic book, which can transmit/receive various multimedia services (e.g., a video conference/call as well as high capacity contents such as High Definition (HD) contents and Ultra High Definition (UHD) contents, etc.) through the network. In particular, disclosed is a method capable of increasing the transmission efficiency without largely increasing decoding complexity in a high-order modulation scheme and a non-binary decoding scheme when the channel encoding scheme is applied to data. It is noted that, in the present specification, for the convenience of description, only non-binary parity check codes will be described, but the present disclosure is not limited to a specific non-binary coding scheme.

(12) A parity check code is generally defined by a parity-check matrix. In the non-binary parity check code, elements constituting a parity check matrix are defined by non-binary symbols as well as 0 and 1, which is different from the binary parity check code. Here, the non-binary symbols can be represented by elements on a ring or a group and can be configured by elements on a finite field.

(13) Although only non-binary parity check codes defined on a finite field will be disclosed in the embodiments of the present disclosure, the present disclosure is not limited to the finite field and can be also applied to a non-binary parity check code defined on a ring or a group. Further, although examples of the most well-known non-binary parity check code are the Reed-Solomon (RS) code and the non-binary LDPC code, it is noted that the present disclosure is not limited to a specific error-correcting code.

(14) An example of a parity check matrix H formed by elements 0, 1, and .sup.2 on a finite field or a Galois field GF(4) is represented in Equation (1).

(15) $\begin{array}{cc}H=\left[\begin{array}{ccccccc}1& 1& 1& 0& 1& 0& 0\\ & {}^2& 0& 1& 0& 1& 0\\ {}^2& 0& & & 0& 0& 1\end{array}\right]& \mathrm{Equation}\left(1\right)\end{array}$

(16) When codewords of the non-binary parity check code defined by Equation (1) are defined as c=(c.sub.0, c.sub.1, c.sub.2, c.sub.3, c.sub.4, c.sub.5, c.sub.6) (here, c.sub.nGF(4)), Equation (2) is established.

(17) $\begin{array}{cc}H.Math.\underset{\_}{c}=\left[\begin{array}{c}{c}_0+c_1+c_2+c_4\\ c_0+{}^2{c}_1+c_3+c_5\\ {}^2{c}_0+c_2+c_3+c_6\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]=\underset{\_}{0}& \mathrm{Equation}\left(2\right)\end{array}$

(18) Here, it should be noted that all sum calculations and all product calculations are calculations defined on the GF(4).

(19) In Equation (2), each row of the parity check matrix H of Equation (1) corresponds to one parity check equation. In addition, it can be seen that values of each parity check equation for the codeword c becomes 0.

(20) In general, when a parity check matrix having the size of MN for a non-binary parity check code defined on a GF(q) is represented as H and a codeword having the length of N is represented as c=(c.sub.0, c.sub.1, . . . , c.sub.N-1), Equation (3) is satisfied.

(21) $\begin{array}{cc}{s}_m=\underset{nN\left(m\right)}{.Math.}{H}_{\mathrm{mn}}{c}_n=0,m=0,1,2,\mathrm{.Math.},\left(M-1\right)& \mathrm{Equation}\left(3\right)\end{array}$

(22) Here, s.sub.m denotes a value of an m.sup.th parity check equation, H.sub.mn denotes an element at the m.sup.th row and the n.sup.th column in the parity check matrix H, and N(m) denotes a set N(m)={n:H.sub.mn0} indicating locations of columns corresponding to elements, which is not zero, at the m.sup.th row in the parity check column H. Further, in Equation (3), H.sub.mn and the codeword symbol c.sub.n are elements of GF(q), and sum and product calculations are also calculations defined on the GF(q). For reference, an index set of a parity check equation corresponding to elements in the n.sup.th column is defined as M(n)={m:H.sub.mn0}.

(23) Since a codeword of the non-binary parity check code defined in Equation (3) is configured by a non-binary symbol, when modulation is applied to the non-binary parity check code, it may be considered that the modulation has been applied such that the non-binary symbol directly corresponds to the signal constellation. However, since a unit by which information is processed in the actual communication system is a bit, a plurality of bit units corresponding to symbols, respectively, and are mapped to the signal constellation and the modulation is then applied. At this time, a symbol defined on the GF(q) can be converted into log.sub.2 q bits with various converting schemes. For example, when the length of a codeword of the non-binary parity check code defined by Equation (3) is N and the symbol of the codeword is defined on GF(q), it can be seen that the codeword of the non-binary code can be configured using N.Math. log.sub.2 q bits.

(24) FIG. 1 illustrates a block diagram of a transmitter and a receiver according to an embodiment of the present disclosure.

(25) Referring to FIG. 1, a transmission unit 100 includes a channel encoder 101, an interleaver 102, and a signal constellation mapper 103. When a non-binary channel encoding scheme is applied in the channel encoder 101, a data to which channel encoding is to be applied is converted into non-binary symbols, the channel encoder 101 generates a non-binary codeword, the interleaver 102 rearranges a sequence if necessary, and the signal constellation mapper 103 modulates the corresponding bit string for transmission through the channel 104. The interleaver 102 may be removed and may have various forms if necessary. Further, determining a signal constellation and then converting into a modulation signal through the signal constellation mapper 103 is omitted for the convenience of description.

(26) A reception unit 110 includes a binary de-mapper 105, a de-interleaver 106 and a channel decoder 108. The de-mapper 105 calculates a probability value, a Likelihood Ratio (LR), a Log Likelihood Ratio (LLR) of a non-binary symbol, or a value corresponding thereto using a signal received from the channel 104, the de-interleaver 106 rearranges the calculated value, and the channel decoder 107 applies the de-interleaved calculated values, to obtain a non-binary codeword or a bit value corresponding thereto. The de-interleaver 106 may be removed and may have various forms if necessary.

(27) Next, a Q-ary Sum Product Algorithm (QSPA) of a non-binary LDPC code will be described.

(28) FIG. 2 illustrates an example of a factor graph of a non-binary LDPC code according to an embodiment of the present disclosure.

(29) Referring to FIG. 2, f.sup.a.sub.j is a message calculated for a decoder input based on a value received from a channel and implies a probability that x.sub.j, which is a j.sup.th variable node (j.sup.th codeword symbol, i.e., a node on a factor graph corresponding to a codeword symbol corresponding to a j.sup.th column of a parity check matrix), is an element a on a finite field. Here, Q.sub.ij.sup.a is a message transferred from a j.sup.th variable node via a permutation node p.sub.ij to a i.sup.th check node (node on the factor graph corresponding to an i.sup.th parity check equation), and .sub.ij.sup.a is a message transferred from the i.sup.th check node to the j.sup.th variable node and implies a probability of satisfying a check equation S.sub.i when a message of {.sub.ij.sup.a:jN(i)\j, aGF(q)} is given. When passing through the permutation node P.sub.ij corresponding to H.sub.ij, the messages Q.sub.ij.sup.a and .sub.ij.sup.a transmitted between the i.sup.th check node and the j.sup.th variable node are updated to messages .sub.ij.sup.a and R.sub.ij.sup.a, and .sub.ij.sup.H.sup.ij.sup.a=R.sub.ij.sup.a.sub.ij.sup.H.sup.ij.sup.a=Q.sub.ij.sup.a are calculated.

(30) A proceeding process of the QSPA will be configured as follows.

(31) Step 1: Initialization

(32) Q.sub.ij.sup.a is initialized to a message f.sub.j.sup.a obtained from a channel.

(33) Step 2: .sub.ij.sup.a Updating

(34) A message .sub.ij.sup.a transmitted from a i.sup.th check node to a j.sup.th variable node is calculated using

(35) $R_{\mathrm{ij}}^a=\underset{X^{\left(i\right)}:x_j=a}{\overset{}{.Math.}}\mathrm{Pr}\left(s_i|X^{\left(i\right)}\right)\underset{kN\left(i\right)\backslash \left\{j\right\}}{.Math.}{Q}_{\mathrm{ik}}^{x_k},$
and .sub.ij.sup.H.sup.ij.sup.a=Q.sub.ij.sup.a is calculate.

(36) Here, X.sup.(i) implies a set of values corresponding to variable nodes connected to the Pi.sup.th check nodes. Pr(s.sub.i|X.sup.(i)) has a value of 1 when S.sub.1 is satisfied with respect to a given X.sub.(i) and has a value of 0 when S.sub.i is not satisfied with respect to the given X.sup.(i).

(37) Step 3: Permutation Step

(38) The message transmitted from the variable node to the check node is updated as .sub.ij.sup.H.sup.ij.sup.a=R.sub.ij.sup.a and .sub.ij.sup.H.sup.ij.sup.a=Q.sub.ij.sup.a in the permutation node p.sub.ij.

(39) Step 4: Q.sub.ij.sup.a Updating

(40) The message Q.sub.ij.sup.a transmitted from the j.sup.th variable node to the i.sup.th check node has a message updating rule which is equal to Equation (4).

(41) $\begin{array}{cc}{Q}_{\mathrm{ij}}^a={}_{\mathrm{ij}}{f}_j^a\underset{kM\left(j\right)\backslash \left\{i\right\}}{.Math.}{R}_{\mathrm{kj}}^a& \mathrm{Equation}\left(4\right)\end{array}$

(42) Here, .sub.ij is a normalizing factor for satisfying .sub.aGF(q)Q.sub.ij.sup.a=1. After decoding, a hard decision vector z is calculated using Equation (5).

(43) $\begin{array}{cc}{z}_j=\arg {\max }_{a\mathrm{GF}\left(q\right)}{f}_j^a\underset{kM\left(j\right)}{.Math.}{R}_{\mathrm{ij}}^a& \mathrm{Equation}\left(5\right)\end{array}$

(44) When values of all the check equation are zero, the repeated decoding terminates. Otherwise, the repeated decoding is continuously performed predetermined times.

(45) The QSPA algorithm performed through the above procedure, which is an algorithm in which values used in a decoding process is based on floating point calculation, has a high complexity that is disadvantageous to apply in an actual system. For this reason, various decoding algorithms for decreasing the decoding complexity of a non-binary code have been known.

(46) An example of decoding algorithm of the non-binary LDPC code for decreasing the complexity corresponds to the ISBM decoding algorithm.

(47) A decoder of the LDPC code, which is defined on a finite field GF(q) having the size of q=2.sup.b and is represented as a parity check matrix having the size of MN, has a purpose of finding a non-binary vector z having the length N satisfying Hz=0 when a channel output is given. z.sup.(k) is a hard decision vector determined in k.sup.th repeated decoding, and {tilde over (S)}.sub.j.sup.(k) is defined as Equation (6) using a syndrome vector s.sup.(k)=z.sup.(k)H.sup.T.
{tilde over (S)}.sub.j.sup.(k)={{tilde over (s)}.sub.i=h.sub.i,j.sup.1s.sub.i:s.sub.iS.sub.j}Equation (6)

(48) Here, S.sub.j is a set of check nodes connected to a j.sup.th variable node. When it is assumed that all hard-decided symbols of variable nodes connected to {tilde over (s)}.sub.i, except for z.sub.j, are correct, z.sub.j and {tilde over (s)}.sub.i satisfy

(49) ${\tilde{s}}_i=\underset{kN\left(i\right)}{.Math.}{h}_{i,k}{z}_k=e_j+c_j+\underset{kN\left(i\right)\backslash j}{.Math.}{h}_{i,k}{c}_k=e_j.$
Here, c.sub.j implies a j.sup.th symbol of the codeword, and e.sub.j implies an error of the jth symbol. When all the hard-decided symbols of {tilde over (s)}.sub.i, except for z.sub.j, have a correct value, a newly-defined variable .sub.i,j=z.sub.j{tilde over (s)}.sub.i is equal to c.sub.j.

(50) Since the ISBM decoding algorithm quantizes a message vector r that is received from a channel and uses the message vector r to perform a sum calculation and a comparing calculation, the ISBM decoding algorithm has a smaller decoding complexity compared to the QSPA or the Extended Min-Sum (EMS) algorithm. Further, r is a vector formed by components obtained by clipping both ends of each of components of the vector r and then uniformly quantizing the remaining components in 2.sup.w1 steps, and each section is expressed by w bits. A vector r.sub.j=(r.sub.j,0, r.sub.j,1, . . . , r.sub.j,b-1) formed by a jb.sup.th element to a (j+1)b1.sup.th element of the vector r corresponds to a j.sup.th symbol c.sub.j of a codeword defined on a finite field GF(2.sup.b). In order to express a correlation between an element a.sub.l on GF(2.sup.b) and the vector r.sub.j, .sub.j,l is defined by Equation (7).

(51) $\begin{array}{cc}{}_{j,i}=\underset{t=0}{\overset{r-1}{.Math.}}\left(1-2a_{l,t}\right){\stackrel{\_}{r}}_{j,t}\left(\mathrm{here},0l<2b\right)& \mathrm{Equation}\left(7\right)\end{array}$

(52) The ISBM decoding algorithm determines a hard-decided vector z.sup.(k) in a k.sup.th repeated decoding process, and to this end, a reliability measurement vector R.sub.j.sup.(k) is defined using Equation (8).
R.sub.j.sup.(k)=(R.sub.j,0.sup.(k), . . . ,R.sub.j,2.sub.b.sub.-1)Equation (8)

(53) R.sub.j,l.sup.(k) denotes a reliability by which z.sub.j is hard-decided as an element a.sub.l on a finite field in a k.sup.th repeated decoding process, and is initialized to a multiple of vector .sub.j=(.sub.j,0, . . . , .sub.j,2.sub.b.sub.-1) using Equation (9).
R.sub.j.sup.(0)=.sub.jEquation (9)

(54) Further, an external message .sub.i,j transferred from a check node to a variable node is defined using the vector .sub.j using Equation (10).

(55) $\begin{array}{cc}{}_{i,j}=\underset{j^{}N\left(i\right)\backslash \left\{j\right\}}{\min }\underset{l}{\max }{}_{j^{},l}& \mathrm{Equation}\left(10\right)\end{array}$

(56) .sub.i,j is a reliability determination criterion of an external message transferred from a check node to a variable node. When all the hard-decided symbols of the variable nodes connected to {tilde over (s)}.sub.i, except for z.sub.j, are correct, .sub.i,j is equal to c.sub.j. Thus, to determine z.sub.j, an external message .sub.j.sup.(k)=(.sub.j,0.sup.(k), . . . , .sub.j,2.sub.b.sub.-1.sup.(k)) influencing a j.sup.th symbol is calculated using Equation (11).

(57) 0$\begin{array}{cc}{}_{j,l}^{\left(k\right)}=\underset{-{}_{i,j}^{\left(k\right)}=a_l,iM\left(j\right)}{.Math.}{}_{i,j}& \mathrm{Equation}\left(11\right)\end{array}$

(58) A process of the ISBM decoding algorithm will be configured as follows.

(59) Initialization Step:

(60) k and z are initialized to k=0 and z=z.sup.(0), and z=z.sup.(0), and a maximum repeated decoding number of times k.sub.max is determined. R.sub.j.sup.(0) is initialized to R.sub.j.sup.(0)=.sub.j with respect to 0j<N. .sub.i,j is calculated and stored with respect to 0i<M, jN(i).

(61) Step 1:

(62) A syndrome vector s.sup.(k) is calculated using s.sup.(k)=z.sup.(k)H.sup.T. When the syndrome vector s.sup.(k) is a zero vector, decoding is terminated and z.sup.(k) is output as a codeword. Otherwise, the process proceeds to step 2.

(63) Step 2:

(64) When k is equal to k.sub.max, the decoding is terminated and failure of the decoding is declared. Otherwise, the process proceeds to step 3.

(65) Step 3:

(66) .sub.j.sup.(k) is calculated with respect to 0j<N. R.sub.j.sup.(k+1) is updated using Equation (12), and then the process proceeds to step 4.
R.sub.j.sup.(k+1)=R.sub.j.sup.(k)+.sub.j.sup.(k)Equation (12)

(67) Step 4:

(68) k increases by 1. A hard-decided vector, z.sup.(k)=(z.sub.0.sup.(k), . . . , z.sub.n-1.sup.(k)) is calculated using Equation (13), and the process returns to step 1.
z.sub.j.sup.(k)=argmax.sub.a.sub.lR.sub.j,l.sup.(k)Equation (13)

(69) The above-described ISBM decoding scheme significantly decreases the decoding complexity through the quantization, but has a disadvantage in that performance deterioration is large. Thus, an embodiment of the present disclosure proposes a method which decreases the performance deterioration while a calculation complexity of a check node is not substantially different from that of the ISBM scheme.

(70) The embodiment of the present disclosure proposes the EISBM algorithm having a lower calculation complexity of a check node and the size of an external message transferred from a check node to a variable node is q. In an algorithm proposed in the embodiment of the present disclosure, a vector .sub.j having the length q is received from d.sub.v1 variable nodes connected to the same check node to update a check node, .sub.j, which has been received from d.sub.v2 variable nodes, is hard-decided, and the check node is updated.

(71) FIG. 3 illustrates that a check node and a permutation node of are approximated to a permutation node of through the Extended Iterative Soft-reliability Based Majority-logic (EISBM) decoding according to an embodiment of the present disclosure.

(72) Because it can be determined that the reliability of the hard-decided symbol z.sub.j is larger as the maximum value of .sub.j,l is larger, d.sub.v2 variable nodes having a larger maximum value of .sub.j,l are selected from d.sub.v1 variable nodes connected to a check node and a hard-decided symbol z.sub.j is determined in symbols. For example, in FIG. 3, when it is assumed that two variable nodes having the largest maximum value of .sub.j,l are nodes x1 and x3 connected to node 301 and 303, the nodes x1 and x3 are hard-decided to determine symbols z1 and z3.

(73) In this way, when a symbol of each node is determined, values of the determined symbols and permutation nodes are combined as indicated by reference numeral 306 in FIG. 3 to be converted into one permutation node as indicated by reference numeral 307. For example, when FIG. 3 is defined as a code formed by symbols 0, 1, A and A.sup.2 (here, A.sup.2=A+1 and A.sup.3=A(A+1)=A.sup.2+A=1) on a GF(4), z1 is equal to 0, z3 is equal to A, a value of the node 301 is equal to 1, a value of a node 302 is equal to A, a value of the node 303 is equal to A.sup.2, and a value of a node 304 is equal to 1, a permutation node 307 combined by a relation equation of a check node 305 can be obtained by Equation (14). Here, it is assumed that values of hard decisions for x2 and x4 are z2 and z4, respectively, and values of z1, z2, z3 and z4 is correct.

(74) $\begin{array}{cc}\begin{array}{c}0=z_1\left(301\right)+x_2\left(302\right)+z_3\left(303\right)+x_4\left(304\right)\\ =x_{2}A+A^3+x_4=x_{2}A+1+x_4{x}_4=x_{2}A+1\end{array}& \mathrm{Equation}\left(14\right)\end{array}$

(75) That is, reference numeral 307 in FIG. 3 functions as a permutation node having a form of x+ (in the present embodiment, =A, =1) with respect to a given input x.

(76) Thus, the decoding algorithm of the non-binary LDPC code proposed in the present disclosure corresponds to a method which hard-decides values of messages of all variable nodes except for a value of a decoding message corresponding to one variable node that is determined to have the lowest reliability among variable nodes connected to a check node of which a message is to be updated. The disclosed method combines the hard-decided values with permutation nodes connected to the variable nodes to which the hard decision is subjected to be converted into one permutation node 307, then applies the combined permutation node to a message to which the hard decision is not subjected, thereby updating the message.

(77) A general proceeding process of the EISBM decoding algorithm according to an embodiment of the present disclosure is configured as follows.

(78) Initialization Step:

(79) k and z are initialized to k=0 and z=z.sup.(0), and a maximum repeated decoding number of times k.sub.max and a weighting factor are determined. R.sub.j.sup.(0) is initialized to R.sub.j.sup.(0)=.sub.j with respect to 0j<N.

(80) Step 1:

(81) A syndrome vector s.sup.(k) is calculated using s.sup.(k)=z.sup.(k)H.sup.T. When the syndrome vector s.sup.(k)=0, the decoding is terminated and z.sup.(k) is output as a codeword. Otherwise, the process proceeds to step 2.

(82) Step 2:

(83) When k is equal to k.sub.max, the decoding is terminated and a decoding failure is declared. Otherwise, the process proceeds to step 3.

(84) Step 3:

(85) .sub.i,j,a is determined using Equation (15) with respect to 0i<M, jN(i) and 0a<2.sup.b.
.sub.i,j,a=.sub.l,a+Equation (15)

(86) Here, =h.sub.i,lh.sub.i,j.sup.1 and

(87) $=h_{i,j}^{-1}\underset{tl,tj}{\underset{tN\left(i\right)}{\overset{}{.Math.}}}{h}_{i,t}{z}_t$

(88) Step 4:

(89) .sub.j.sup.(k)=(.sub.j,0.sup.(k), . . . , .sub.j,2.sub.b.sub.-1) is defined using

(90) ${}_{j,a}^{\left(k\right)}=\underset{iM\left(j\right)}{.Math.}{}_{i,j,a}.$
R.sub.j.sup.(k+1) is updated using Equation (16), and the process then proceeds to step 5.
R.sub.j.sup.(k+1)=R.sub.j.sup.(k)+.sub.j.sup.(k)Equation (16)

(91) Step 5:

(92) k increases by 1. A hard-decided vector z.sup.(k)=(z.sub.0.sup.(k), . . . , z.sub.n-1.sup.(k)) is determined using Equation (17), and the process returns to Step 1.
z.sub.j.sup.(k)=argmax.sub.a.sub.lR.sub.j,l.sup.(k)Equation (17)

(93) FIG. 4 is a flowchart of a decoding procedure according to an embodiment of the present disclosure.

(94) First, a value of a decoding counter K is initialized to 0 and a reliability measurement vector is initialized from a received signal at operation 401. Next, a codeword is hard-decided from the received signal at operation 402 and a syndrome vector is calculated from the hard-decided codeword at operation 403. It is determined whether the calculated syndrome vector coincides with a value of 0 at operation 404. When the calculated syndrome vector coincides with the value of 0, the decoding succeeds and the hard-decided codeword is output at operation 405. When the values of the syndrome vector are not 0, it is considered that the decoding does not succeed. Thus, the decoding counter K is compared with a predetermined maximum value Kmax at operation 406, and when the decoding counter K is less than the predetermined maximum value Kmax, the value K incremented by 1, and the reliability measurement vector is then updated according to a predetermined rule at operation 407. Thereafter, the codeword is hard-decided from a received signal again while reflecting the updated reliability measurement vector. Such a process can be repeated until the syndrome vector has the value of 0. However, when the values of the syndrome vector are not 0 and the decoding counter K is equal to the maximum value Kmax, a decoding failure is declared at operation 408 and all operations are terminated.

(95) FIG. 5 is a block diagram illustrating a configuration of an apparatus for decoding according to an embodiment of the present disclosure.

(96) Referring to FIG. 5, a hard decision unit 510 initializes a value of a decoding counter K to 0, initializes a reliability measurement vector from a received signal, and hard-decides a codeword from the received signal. An output unit 520 calculates a syndrome vector from the hard-decoded codeword and identifies whether values of the calculated syndrome vector coincide with a value of 0. When the values of the syndrome vector coincide with the value of 0, the decoding succeeds and the hard-decided codeword is output as a final codeword. When the values of the syndrome vector are not 0 decoding does not succeed, the decoding counter K is compared to the predetermined maximum value Kmax to determine if decoding should continue. Specifically, if the values of the syndrome vector are not 0 and the decoding counter does not equal the predetermined maximum value Kmax, the decoding counter K is incremented by 1 and the result is transferred to a reliability measurement vector updating unit 530. The reliability measurement vector updating unit 530 updates a reliability measurement vector according to a predetermined rule and transfers the updated reliability measurement vector to the hard decision unit 510. Thereafter, the hard decision unit 510 hard-decides the codeword from a received signal again while reflecting the updated reliability measurement vector. However, when the decoding counter K is equal to the predetermined maximum value Kmax, the output unit 520 declares that the decoding fails and the decoding operations are terminated.

(97) While the present disclosure has been shown and described with reference to various embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present disclosure as defined by the appended claims and their equivalents.