Error correcting code encoding circuit and semiconductor device including the same
A semiconductor device may include an error correcting code (ECC) encoder that encodes a codeword based on a parity check matrix and generates the encoded codeword including an information bit and a parity bit. The parity check matrix is divided into an information part corresponding to the information bit and a parity part corresponding to the parity bit. The parity part includes a block matrix T including a plurality of first sub-matrices arranged in a dual diagonal structure, a block matrix B including a first sub-matrix and a (1−a)-th sub-matrix, a block matrix D composed of a first sub-matrix, and a block matrix E including a first sub-matrix and a masked (1−(a+1))-th sub-matrix. A location where the first sub-matrix is placed in the block matrix B precedes a location where the masked (1−(a+1))-th sub-matrix is placed in the block matrix E.
1. An error correcting code (ECC) encoding circuit configured to encode a codeword based on a parity check matrix and to generate an encoded codeword (ECW) including an information bit and a parity bit,
wherein the ECC encoding circuit includes:
a parity check matrix (PCM) generator configured to generate the parity check matrix; and
an encoding unit coupled to the PCM generator and configured to generate the encoded codeword based on the codeword and the parity check matrix;
wherein the parity check matrix is divided into an information part corresponding to the information bit and a parity part corresponding to the parity bit, and
wherein the parity part includes:
a block matrix T including a plurality of first sub-matrices arranged in a dual diagonal structure;
a block matrix B including a first sub-matrix and a (1−a)-th sub-matrix, a being a natural number greater than or equal to 1;
a block matrix D composed of the first sub-matrix; and
a block matrix E including the first sub-matrix and a masked (1−(a+1))-th sub-matrix,
wherein the block matrix B and the block matrix D are positioned in the same sub-column,
wherein the block matrix T and the block matrix E are positioned in the same sub-column,
wherein a location where the first sub-matrix is placed in the block matrix B precedes a location where the masked (1−(a+1))-th sub-matrix is placed in the block matrix E,
wherein a location where the (1−a)-th sub-matrix is placed in the block matrix B precedes a location where the first sub-matrix is placed in the block matrix E,
wherein the first sub-matrix of each of the block matrices T, B, D and E is defined as a unit matrix having a size of Z×Z, Z being a natural number,
wherein the (1−a)-th sub-matrix is defined as a matrix obtained by performing a left-cyclic shift ‘a’ times on the first sub-matrix, and
wherein the masked (1−(a+1))-th sub-matrix is defined as a matrix in which a first row is masked in a matrix obtained by performing a left-cyclic shift “a+1” times on the first sub-matrix.
2. The ECC encoding circuit of claim 1 ,
wherein a relationship between the parity check matrix and the encoded codeword is expressed based on Equation 1:
H
·
ECW
=
[
Hinfo
Hpar
]
[
s
p
]
=
Hinfo
·
s
+
Hpar
·
p
=
0
,
[
Equation
1
]
and
wherein, in Equation 1, the ‘H’ denotes the parity check matrix, the ECW denotes the encoded codeword, the Hinfo denotes the information part of the PCM, the Hpar denotes the parity part of the PCM, the ‘s’ denotes the information bit of the ECW, and the ‘p’ denotes the parity bit of the ECW.
3. The ECC encoding circuit of claim 2 , wherein the encoding unit is further configured to perform an operation for calculating the parity bit, and
wherein the operation for calculating the parity bit is expressed based on Equation 2:
p
=
Hpar
-
1
(
Hinfo
·
s
)
.
[
Equation
2
]
4. The ECC encoding circuit of claim 3 , wherein the parity bit includes a first parity bit operated with the block matrix B and the block matrix D and a second parity bit operated with the block matrix T and the block matrix E, and
wherein the encoding unit includes a computing unit configured to calculate the first parity bit.
5. The ECC encoding circuit of claim 2 , wherein the PCM generator includes:
a base matrix generator configured to generate a base matrix including a block matrix Bb, a block matrix Tb, a block matrix Db, and a block matrix Eb, which respectively correspond to the block matrix B, the block matrix T, the block matrix D, and the block matrix E of the parity part and each of which is composed of components of ‘1’ or ‘0’;
a mapping table configured to store mapping data including data for sub-matrices with which components respectively corresponding to the block matrix Bb, the block matrix Tb, the block matrix Db, and the block matrix Eb of the base matrix are to be replaced; and
a matrix transform unit configured to generate the parity check matrix including the parity part based on the base matrix and the mapping data.
6. The ECC encoding circuit of claim 5 , wherein a weight of a column divided into the block matrix Bb and the block matrix Db is 3, and
wherein a weight of at least one of columns divided into the block matrix Tb and the block matrix Eb is 3.
7. The ECC encoding circuit of claim 5 , wherein the block matrix Bb includes first and second components of ‘1’ and a plurality of components of ‘0’,
wherein the block matrix Eb includes first and second components of ‘1’ and a plurality of components of ‘0’,
wherein the block matrix Tb includes a plurality of components of ‘1’ arranged in a dual diagonal structure, and
wherein the block matrix Db composed of one component of ‘1’.
8. The ECC encoding circuit of claim 7 , wherein a location value of the first component of ‘1’ of the block matrix Bb is smaller than a location value of the first component of ‘1’ of the block matrix Eb, and
wherein a location value of the second component of ‘1’ of the block matrix Bb is smaller than a location value of the second component of ‘1’ of the block matrix Eb.
9. The ECC encoding circuit of claim 8 , wherein the matrix transform unit is configured to generate the parity part by replacing:
the first component of ‘1’ of the block matrix Bb with the first sub-matrix,
the second component of ‘1’ of the block matrix Bb with the (1−a)-th sub-matrix,
the first component of ‘1’ of the block matrix Eb with the masked (1−(a+1))-th sub-matrix, and
the second component of ‘1’ of the block matrix Eb with the first sub-matrix.
10. The ECC encoding circuit of claim 1 , wherein rows of the parity part correspond to check nodes,
wherein columns of the parity part correspond to variable nodes,
wherein at least one of variable nodes divided into the block matrix B and the block matrix D has a weight of 3, and
wherein at least one of variable nodes divided into the block matrix T and the block matrix E has a weight of 3.
11. A semiconductor device comprising:
an error correcting code (ECC) encoder configured to encode a codeword based on a parity check matrix and to generate an encoded codeword (ECW) including an information bit and a parity bit,
wherein the ECC encoder includes:
a parity check matrix (PCM) generator configured to generate the parity check matrix; and
an encoding unit coupled to the PCM generator and configured to generate the encoded codeword based on the codeword and the parity check matrix;
wherein the parity check matrix is divided into an information part corresponding to the information bit and a parity part corresponding to the parity bit, and
wherein the parity part includes:
a plurality of sub-rows and a plurality of sub-columns;
a block matrix T including a plurality of first sub-matrices arranged in a dual diagonal structure;
a block matrix B including:
a first column vector positioned in a first sub-column of the plurality of sub-columns and including a (1−a1)-th sub-matrix, a1 being an integer greater than or equal to 0, and
a second column vector positioned in a second sub-column of the plurality of sub-columns and including a (1−a2)-th sub-matrix, a2 being an integer greater than or equal to 0;
a block matrix E including:
a first row vector positioned in a first sub-row of the plurality of sub-rows and including a first sub-matrix, and
a second row vector positioned in a second sub-row of the plurality of sub-rows and including the first sub-matrix; and
a block matrix D including: a masked (1−(a1+1))-th sub-matrix positioned in the first sub-column and the first sub-row,
a (1−(a1−2))-th sub-matrix positioned in the first sub-column and the second sub-row, and
a masked (1−(a2+1))-th sub-matrix positioned in the second sub-column and the second sub-row,
wherein a location where the (1−a1)-th sub-matrix of the block matrix B is placed in the first column vector precedes a location where the first sub-matrix of the block matrix E is placed in the first row vector,
wherein a location where the (1−a2)-th sub-matrix of the block matrix B is placed in the second column vector precedes a location where the first sub-matrix of the block matrix E is placed in the second row vector,
wherein the first sub-matrix is defined as a unit matrix having a size of Z×Z, Z being a natural number,
wherein the (1−aj)-th sub-matrix is defined as a matrix obtained by performing a left-cyclic shift ‘aj’ times on the first sub-matrix, j being 1 or 2,
wherein the masked (1−(aj+1))-th sub-matrix is defined as a matrix in which a first row is masked in a matrix obtained by performing a left-cyclic shift “aj+1” times on the first sub-matrix, and
wherein the (1−(aj−2))-th sub-matrix is defined as a matrix obtained by performing a left-cyclic shift “aj−2” times on the first sub-matrix.
12. The semiconductor device of claim 11 ,
wherein a relationship between the parity check matrix and the encoded codeword is expressed based on Equation 1 :
H
·
ECW
=
[
Hinfo
Hpar
]
[
s
p
]
=
Hinfo
·
s
+
Hpar
·
p
=
0
,
[
Equation
1
]
and
wherein, in Equation 1, the ‘H’ denotes the parity check matrix, the ECW denotes the encoded codeword, the Hinfo denotes the information part of the PCM, the Hpar denotes the parity part of the PCM, the ‘s’ denotes the information bit of the ECW, and the ‘p’ denotes the parity bit of the ECW.
13. The semiconductor device of claim 12 , wherein the PCM generator includes:
a base matrix generator configured to generate a base matrix including a block matrix Bb, a block matrix Tb, a block matrix Db, and a block matrix Eb, which respectively correspond to the block matrix B, the block matrix T, the block matrix D, and the block matrix E of the parity part and each of which is composed of components of ‘1’ or ‘0’;
a mapping table configured to store mapping data including data for sub-matrices with which components respectively corresponding to the block matrix Bb, the block matrix Tb, the block matrix Db, and the block matrix Eb of the base matrix are to be replaced; and
a matrix transform unit configured to generate the parity check matrix including the parity part based on the base matrix and the mapping data.
14. The semiconductor device of claim 13 , wherein the block matrix Bb includes:
a first base column vector including one component of ‘1’ and a plurality of components of ‘0’, and
a second base column vector including one component of ‘1’ and a plurality of components of ‘0’,
wherein the block matrix Eb includes:
a first base row vector including one component of ‘1’ and a plurality of components of ‘0’, and
a second base row vector including one component of ‘1’ and a plurality of components of ‘0’,
wherein each of the block matrix Db and the block matrix Tb includes a plurality of components of ‘1’ arranged in a dual diagonal structure,
wherein a location value of the component of ‘1’ in the first base column vector of the block matrix Bb is smaller than a location value of the component of ‘1’ in the first base row vector of the block matrix Eb, and
wherein a location value of the component of ‘1’ in the second base column vector of the block matrix Bb is smaller than a location value of the component of ‘1’ in the second base row vector of the block matrix Eb.
15. The semiconductor device of claim 14 , wherein the matrix transform unit is configured to generate a parity part by replacing:
the component of ‘1’ of the first base column vector with the (1−a1)-th sub-matrix,
the component of ‘1’ of the second base column vector with the (1−a2)-th sub-matrix, and
the component of ‘1’ of each of the first base row vector and the second base row vector with the first sub-matrix.