On-the-fly CRC calculation for a horizontal layered LDPC decoder
A method and memory system for on-the-fly horizontal layer error code processing of data for memory storage and retrieval. The method and associated system provide for generating a parity check matrix H 1 including a payload portion and a parity portion, rearranging user data circulants within rows of the payload portion to different row positions; and forming a bottom-sorted party check matrix H 2 from the rearranged user data circulants.
1 . A method for on-the-fly horizontal layer error code processing of data for memory storage and retrieval, comprising:
generating a parity check matrix including a payload portion and a parity portion, wherein the payload portion contains layers of user data circulants and the parity portion contains layers of parity data circulants;
rearranging user data circulants, within respective rows of the payload portion, to different row positions in a same row, with no shifting of the parity data circulants;
the rearranging of the user data circulants forming a bottom-sorted party check matrix including the rearranged user data circulants, wherein bottom circulants of the bottom-sorted party check matrix are arranged in a horizontal-layer sequential order; and
after the rearrangement, error-checking in the horizontal-layer sequential order using only the bottom circulants of the bottom-sorted party check matrix.
2 . The method of claim 1 , further comprising processing the bottom-sorted party check matrix using horizontal layer decoding to correct errors in stored codewords of the data retrieved from memory.
3 . The method of claim 1 , wherein, after the rearrangement, horizontal layer processing in the horizontal-layer sequential order the bottom-sorted party check matrix for error correction using the bottom circulants in each column in an order associated with a column index i.
4 . The method of claim 1 , wherein the rearrangement re-orders the columns in the payload portion so that for all column indices i, where i=[2, 3, . . . , k] is a column index in payload portion, b(i)>=b(i−1), where b(j) is the row index of the bottom circulant of column j.
5 . The method of claim 1 , wherein the parity portion contains cyclic redundant shift parity values.
6 . The method of claim 1 , wherein, the bottom circulants in the bottom-sorted party check matrix are error checked by cyclic redundancy checking (CRC).
7 . The method of claim 6 , wherein CRC encoding logic updates hard-decision bits for the bottom circulants.
8 . The method of claim 7 , wherein the hard-decision bits update register values for changing bit values in the user data circulants.
9 . The method of claim 6 , further comprising:
using the bottom-sorted parity check matrix as an ECC encoding matrix to encode the payload portion with an initial CRC parity appended thereto;
calculating a CRC parity based on the encoded payload portion of the bottom-sorted parity check matrix;
permuting a codeword such that the permuted codeword satisfies a calculated parity check with the parity check matrix; and
processing the party check matrix using horizontal layer decoding to correct errors in stored codewords when read in order of the permuted codeword.
10 . A memory system, comprising:
a storage; and
a processor configured to:
generate a parity check matrix H 1 including a payload portion and a parity portion, wherein the payload portion contains layers of user data circulants and the parity portion contains layers of parity data circulants;
rearrange user data circulants, within respective rows of the payload portion, to different row positions in a same row, with no shifting of the parity data circulants;
form from rearranged user data circulants a bottom-sorted party check matrix including the rearranged user data circulants, wherein bottom circulants of the bottom-sorted party check matrix are arranged in a horizontal-layer sequential order; and
after the rearrangement, error-check in the horizontal-layer sequential order using only the bottom circulants of the bottom-sorted party check matrix.
11 . The memory system of claim 10 , wherein the processor is further configured to: process the bottom-sorted party check matrix using horizontal layer decoding to correct errors in stored codewords of the data retrieved from memory.
12 . The memory system of claim 11 , wherein, after the rearrangement, horizontal layer processing in the horizontal-layer sequential order the bottom-sorted party check matrix for error correction using the bottom circulants in each column in an order associated with a column index i.
13 . The memory system of claim 11 , wherein the rearrangement re-orders the columns in the payload portion so that for all column indices i, where i=[2, 3, . . . , k] is a column index in payload portion, b(i)>=b(i−1), where b(j) is the row index of the bottom circulant of column j.
14 . The memory system of claim 11 , wherein the parity portion contains cyclic redundant shift parity values.
15 . The memory system of claim 11 , wherein the bottom circulants in the bottom-sorted party check matrix are error checked by cyclic redundancy checking (CRC).
16 . The memory system of claim 11 , wherein CRC encoding logic updates hard-decision bits for the bottom circulants.
17 . The memory system of claim 16 , wherein the hard-decision bits update register values for changing bit values in the user data circulants.
18 . The memory system of claim 11 , wherein the processor is configured to:
use the bottom-sorted parity check matrix as an ECC encoding matrix to encode the payload portion with an initial CRC parity appended thereto;
calculate a CRC parity based on the encoded payload portion of the bottom-sorted parity check matrix;
permute a codeword such that the permuted codeword satisfies a calculated parity check with the parity check matrix; and
process the party check matrix using horizontal layer decoding to correct errors in stored codewords when read in order of the permuted codeword.