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

Abstract:

A method for data encoding includes receiving a data vector to be encoded into a code word in accordance with a code defined by a parity-check matrix H. An intermediate vector s is produced by multiplying the data vector by a data sub-matrix H.sub.s of the parity-check matrix H. A parity part of the code word is derived by applying a sequence of operations to the intermediate vector s based on a decomposition of a parity sub-matrix H.sub.p of the matrix H using matrices A, C, U and V, in which decomposition A is a block triangular matrix that has the same size as H.sub.p, C is matrix that is smaller than H.sub.p, and the matrices U and V are placement matrices that are selected so that A, C, U and V satisfy a matrix equation H.sub.p=A+UCV.