Decoding apparatus and method in a communication system using low density parity check codes
A decoding method in a communication system using a Low Density Parity Check (LDPC) code. The method includes determining whether an LDPC codeword to be decoded is a general LDPC codeword to which a puncturing scheme is not applied or a punctured LDPC codeword to which the puncturing scheme is applied; if the LDPC codeword to be decoded is the punctured LDPC codeword, generating a child parity check matrix according to a mother parity check matrix indicative of a parity check matrix of the general LDPC codeword, and a puncturing pattern applied to the punctured LDPC codeword; and decoding the punctured LDPC codeword according to the child parity check matrix.
1. A decoding method in a communication system using a Low Density Parity Check (LDPC) code, the method comprising:
determining whether an LDPC codeword to be decoded is a general LDPC codeword to which a puncturing scheme is not applied or a punctured LDPC codeword to which the puncturing scheme is applied;
if the LDPC codeword to be decoded is the punctured LDPC codeword, generating a child parity check matrix using a mother parity check matrix indicative of a parity check matrix of the general LDPC codeword, and a puncturing pattern applied to the punctured LDPC codeword; and
decoding the punctured LDPC codeword using the child parity check matrix;
wherein generating the child parity check matrix comprises generating a Tanner graph of the punctured LDPC codeword by deleting parity nodes corresponding to parity bits punctured to generate the punctured LDPC codeword from the general LDPC codeword in a Tanner graph of the general LDPC codeword, and generating the child parity check matrix using the Tanner graph of the punctured LDPC codeword; and
wherein deleting parity nodes corresponding to parity bits punctured to generate the punctured LDPC codeword comprises adding each of remaining parity nodes except for parity nodes corresponding to the punctured parity bits of a first parity node corresponding to a non-punctured parity bit preceding the remaining parity node, and all information nodes connected between the first parity node and the remaining parity node in the Tanner graph of the general LDPC codeword.
2. The decoding method of claim 1 , wherein deleting parity nodes corresponding to parity bits punctured to generate the punctured LDPC codeword is performed to satisfy:
p
(
j
+
1
)
=
p
(
j
-
t
)
+
∑
i
=
1
n
-
2
(
g
(
i
,
j
)
+
g
(
i
,
j
-
1
)
+
…
+
g
(
i
,
j
-
t
)
)
mod
2
where p(j) denotes a j th parity bit, g(i,j) denotes a j th information node among the information nodes connected to an i th check node, and ‘n’ denotes a degree of the i th check node, and ‘mod’ denotes a modulo operation.
3. The decoding method of claim 1 , wherein generating a child parity check matrix comprises generating the child parity check matrix by operating row vectors included in the mother parity check matrix according to the puncturing pattern if the LDPC code is a block LDPC (B-LDPC) code.
4. The decoding method of claim 1 , further comprising:
generating the child parity check matrix by operating row vectors included in the mother parity check matrix according to the puncturing pattern defined as
G p (2 i )=0, i= 1,2,3,4,5,6
where G p (2i) denotes a parity group corresponding to a (2i) th row of the mother parity check matrix, and G p (2i)=0 indicates that all parity bits in the Gp(2i) are punctured if the general LDPC codeword is a B-LDPC codeword with coding rate=½, the punctured LDPC codeword is a punctured B-LDPC codeword with coding rate=⅔, the mother parity check matrix includes a plurality of permutation matrixes, and parity bits of the B-LDPC codeword with coding rate=½ are grouped in 12 parity bits, the step of generating a child parity check matrix.
5. The decoding method of claim 4 , wherein operating row vectors included in the mother parity check matrix according to the puncturing pattern is performed according to:
r′ i =r 2i-1 Ør 2i , i=1,2,3,4,5,6
where r′ i denotes an i th row vector of the child parity check matrix, r 2i-1 denotes a (2i−1) th row vector of the mother parity check matrix, r 2i denotes a (2i) th row vector of the mother parity check matrix, and Ø denotes an operation for each individual element in the vector, and is expressed as
−1Ø−1=−1
−1Øa=a
aØb=(a,b)
where ‘a’ and ‘b’ indicate positive integers, and (a,b) indicates that positions of ‘1’s existing in a first row vector are ‘a’ and ‘b’ and the next row vector is right-cyclically-shifted from the first row vector, and further indicates a sum per row between elements in the same position of a permutation matrix associated with parameter ‘a’ and a permutation matrix associated with parameter ‘b’.
6. The decoding method of claim 1 , further comprising:
generating the child parity check matrix by operating row vectors included in the mother parity check matrix according to the puncturing pattern defined as
Gp (4 i )=0, i= 1,2,3
Gp (4 i− 1)=0, i= 1,2,3
Gp (4 i− 2)=0, i= 1,2,3
where G p (4i) denotes a parity group corresponding to a (4i) th row of the mother parity check matrix, and G p (4i)=0 indicates that all parity bits in the Gp(4i) are punctured if the general LDPC codeword is a B-LDPC codeword with coding rate=½, the punctured LDPC codeword is a punctured B-LDPC codeword with coding rate=⅘, the mother parity check matrix includes a plurality of permutation matrixes, and parity bits of the B-LDPC codeword with coding rate=½ are grouped in 12 parity bits, the step of generating a child parity check matrix.
7. The decoding method of claim 6 , wherein operating row vectors included in the mother parity check matrix according to the puncturing pattern is performed according to:
r′ i =r 2i-1 Ør 2i , i=1,2,3
where r′ i denotes an i th row vector of the child parity check matrix, r 2i-1 denotes a (2i−1) th row vector of the mother parity check matrix, r 2i denotes a (2i) th row vector of the mother parity check matrix, and Ø denotes an operation for each individual element in the vector, and is expressed as
−1Ø−1=−1
−1Øa=a
aØb=(a,b)
where ‘a’ and ‘b’ indicate positive integers, and (a,b) indicates that positions of ‘1’s existing in a first row vector are ‘a’ and ‘b’ and the next row vector is right-cyclically-shifted from the first row vector, and further indicates a sum per row between elements in the same position of a permutation matrix associated with parameter ‘a’ and a permutation matrix associated with parameter ‘b’.
8. A decoding apparatus in a communication system using a Low Density Parity Check (LDPC) code, the apparatus comprising:
a controller for determining whether an LDPC codeword to be decoded is a general LDPC codeword to which a puncturing scheme is not applied or a punctured LDPC codeword to which the puncturing scheme is applied, and if the LDPC codeword to be decoded is the punctured LDPC codeword generating a child parity check matrix using a mother parity check matrix indicative of a parity check matrix of the general LDPC codeword, and a puncturing pattern applied to the punctured LDPC codeword; and
an LDPC decoder for decoding the punctured LDPC codeword using the child parity check matrix;
wherein the controller deletes parity nodes corresponding to parity bits punctured to generate a Tanner graph of the punctured LDPC codeword and the punctured LDPC codeword from the general LDPC codeword in a Tanner graph of the general LDPC codeword, and generates the child parity check matrix using the Tanner graph of the punctured LDPC codeword; and
wherein the controller deletes parity nodes corresponding to parity bits punctured to generate the punctured LDPC codeword which is achieved by adding each of remaining parity nodes except for parity nodes corresponding to the punctured parity bits to a first parity node corresponding to a non-punctured parity bit preceding the remaining parity node, and all information nodes connected between the first parity node and the remaining parity node in the Tanner graph of the general LDPC codeword.
9. The decoding apparatus of claim 8 , wherein the controller deletes parity nodes corresponding to parity bits punctured to generate the punctured LDPC codeword according:
p
(
j
+
1
)
=
p
(
j
-
t
)
+
∑
i
=
1
n
-
2
(
g
(
i
,
j
)
+
g
(
i
,
j
-
1
)
+
…
+
g
(
i
,
j
-
t
)
)
mod
2
where p(j) denotes a j th parity bit, g(i,j) denotes a j th information node among the information nodes connected to an i th check node, and ‘n’ denotes a degree of the i th check node, and ‘mod’ denotes a modulo operation.
10. The decoding apparatus of claim 8 , wherein if the LDPC code is a block LDPC (B-LDPC) code, the controller generates the child parity check matrix by operating row vectors included in the mother parity check matrix according to the puncturing pattern.
11. The decoding apparatus of claim 8 , wherein the controller generates the child parity check matrix by operating row vectors included in the mother parity check matrix according to the puncturing pattern defined as
G p (2 i )=0, i= 1,2,3,4,5,6
where G p (2i) denotes a parity group corresponding to a (2i) th row of the mother parity check matrix, and G p (2i)=0 indicates that all parity bits in the Gp(2i) are punctured if the general LDPC codeword is a B-LDPC codeword with coding rate=½, the punctured LDPC codeword is a punctured B-LDPC codeword with coding rate=⅔, the mother parity check matrix includes a plurality of permutation matrixes, and parity bits of the B-LDPC codeword with coding rate=½ are grouped in 12 parity bits.
12. The decoding apparatus of claim 11 , wherein the controller operates row vectors included in the mother parity check matrix according to the puncturing pattern using:
r′ i =r 2i-1 Ør 2i , i=1,2,3,4,5,6
where r′ i denotes an i th row vector of the child parity check matrix, r 2i-1 denotes a (2i−1) th row vector of the mother parity check matrix, r 2i denotes a (2i) th row vector of the mother parity check matrix, and Ø denotes an operation for each individual element in the vector, and is expressed as
−1Ø−1=−1
−1Øa=a
aØb=(a,b)
where ‘a’ and ‘b’ indicate positive integers, and (a,b) indicates that positions of ‘1’s existing in a first row vector are ‘a’ and ‘b’ and the next row vector is right-cyclically-shifted from the first row vector, and further indicates a sum per row between elements in the same position of a permutation matrix associated with parameter ‘a’ and a permutation matrix associated with parameter ‘b’.
13. The decoding apparatus of claim 8 , wherein the controller generates the child parity check matrix by operating row vectors included in the mother parity check matrix according to the puncturing pattern defined as
Gp (4 i )=0, i= 1,2,3
Gp (4 i− 1)=0, i= 1,2,3
Gp (4 i− 2)=0, i= 1,2,3
where G p (4i) denotes a parity group corresponding to a (4i) th row of the mother parity check matrix, and G p (4i)=0 indicates that all parity bits in the Gp(4i) are punctured if the general LDPC codeword is a B-LDPC codeword with coding rate=½, the punctured LDPC codeword is a punctured B-LDPC codeword with coding rate=⅘, the mother parity check matrix includes a plurality of permutation matrixes, and parity bits of the B-LDPC codeword with coding rate=½ are grouped in 12 parity bits.
14. The decoding apparatus of claim 13 , wherein the controller operates row vectors included in the mother parity check matrix according to the puncturing pattern using:
r′ i =r 2i-1 Ør 2i , i=1,2,3
where r′ i denotes an i th row vector of the child parity check matrix, r 2i-1 denotes a (2i−1) th row vector of the mother parity check matrix, r 2i denotes a (2i) th row vector of the mother parity check matrix, and Ø denotes an operation for each individual element in the vector, and is expressed as
−1Ø−1=−1
−1Øa=a
aØb=(a,b)
where ‘a’ and ‘b’ indicate positive integers, and (a,b) indicates that positions of ‘1’s existing in a first row vector are ‘a’ and ‘b’ and the next row vector is right-cyclically-shifted from the first row vector, and further indicates a sum per row between elements in the same position of a permutation matrix associated with parameter ‘a’ and a permutation matrix associated with parameter ‘b’.