Efficient encoding for non-binary error correction codes

A solid state storage device comprising, memory cells and a controller, wherein the controller is configured for encoding information bits with a Q-ary linear error correction code defined over a binary-extension Galois field GF(2k), wherein the Q-ary linear error correction code is defined by a quasi-cyclic parity-check matrix having an information section associated with the information bits and a parity section associated with parity bits, wherein the parity section has an approximate lower triangular form and comprises a plurality of circulants, wherein the parity section comprises:

• a first circulant sub-matrix which comprises a first circulant having a first shift and being defined by a first parameter belonging to the Galois field GF(2k);
• a second circulant sub-matrix which has a triangular structure and comprises a second circulant having a second shift and being defined by a second parameter belonging to the Galois field GF(2k), said second parameter being the inverse of the first parameter, the second shift being equal to a difference between a number of rows of each circulant and the first shift;
• a third circulant sub-matrix which comprises a third circulant having a third shift and being defined by a third parameter belonging to the Galois field GF(2k);
• and
• a fourth circulant sub-matrix,
• the controller being configured for:
• determining a first set of parity-check bits according to the information bits, to said second and third circulant sub-matrices, and to a fourth circulant, the fourth circulant having a fourth shift and being defined by the multiplicative inverse of a fourth parameter given by a product between the first and third parameters, wherein the fourth shift is equal to a difference between said number of rows and said first and third shifts, and
• determining a second set of parity-check bits according to the determined first set of parity-check bits, to said first and second circulant sub-matrices and to the information bits, and
• storing the information bits and the first and second sets of parity-check bits in the memory cells of the solid state storage device.