Data encoding by efficient inversion of a parity-check sub-matrix

A data encoder, comprising:

• an interface, which is configured to receive a data vector for transmission or storage;
• a memory storing information for encoding data with a code, which can be defined by a parity-check matrix H formed of a data sub-matrix Hs and a parity sub-matrix Hp, the information including a data sub-matrix Hs, and pre-calculated values of functions of matrices A, C, U and V of a decomposition of Hp of the form Hp=A+UCV, where A is a block triangular matrix, C is a matrix that is smaller than Hp, and the matrices U and V are placement matrices, wherein the storage space of the pre-calculated values is smaller than required to store an inverse of Hp;
• encoding circuitry, which is configured to:
• produce an intermediate vector y by multiplying the data vector by the data sub-matrix Hs,
• calculate a vector y which fulfils the equation y=A−1s from the produced intermediate vector s and one or more of the pre-calculated values stored in the memory,
• calculate a modified vector s′, which fulfils the equation s′=s−UW−1V·y, where W−1=(C−1+VA−1U)−1, from the vector y, the produced intermediate vector s, and one or more of the pre-calculated values stored in the memory,
• derive a parity part p of a code word, which fulfils the equation Ap=s′, using the modified vector s′ and pre-calculated values stored in the memory, and
• generate a code word representing the received data vector, as a function of the received data vector and the derived parity part;
• and
• an output interface configured to transmit or store the code word to a device, wherein some code words transmitted or stored by the output interface get corrupted while being stored or transmitted, and wherein the corrupted code words are decoded to recover the data vector.

A computer software product, the product comprising a tangible non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by a processor of a data encoder, cause the processor to be configured for encoding data with a code which can be defined by a parity-check matrix H formed of a data sub-matrix Hs and a parity-check sub-matrix Hp, by storing, in a memory, the data sub-matrix Hs, and pre-calculated values of functions of matrices A, C, U and V of a decomposition of Hp of the form Hp=A+UCV, where A is a block triangular matrix, C is a matrix that is smaller than Hp, and the matrices U and V are placement matrices, wherein the storage space of the pre-calculated values is smaller than required to store an inverse of Hp, to receive, via an interface of the data encoder, a data vector for transmission or storage to be encoded into a code word to produce an intermediate vector s by multiplying the data vector by the data sub-matrix Hs, to calculate a vector y which fulfils the equation y=A−1s from the produced intermediate vector s and one or more of the pre-calculated values stored in the memory, to calculate a modified vector s′, which fulfils the equation s′=s−UW−1V·y, where W−1=(C−1+VA−1U)−1, from the vector y, the produced intermediate vector s, and one or more of the pre-calculated values stored in the memory, to derive a parity part p of the code word, which fulfils the equation Ap=s′, using the modified vector s′ and pre-calculated values stored in the memory, to generate a code word representing the received data vector, as a function of the received data vector and the derived parity part, and to transmit or store the code word to a device, wherein some code words transmitted or stored by the output interface get corrupted in the transmission or storing, and wherein the corrupted code words are decoded to recover the data vector.