Faster Encoding using Sparse Matrix Properties

From [5], suppose we would like to impose a series of M parity check on N bits. Once sent through the channel and corrupted by additive white Gaussian noise (AWGN), the decoder, knowing the same parity check matrix, can verify the M parity checks and attempt to determine the correct set of bits that were sent. If H is the MxN parity check matrix with M < N, x is a column vector bit-sequence of length N, and, 0 is a length N column of 0’s, this amounts to satisfying:

x is composed of an M length parity block and an N-M length data block. The goal of encoding is to find the M length parity check sequence such that when concatenated with the data block, the above relationship holds under modulo 2 arithmetic. A brute force approach is to divide the H matrix and x into two parts:

Solving for the parity bits c requires time proportional to M*(N-M). A faster approach is to peform the lower and upper triangular decomposition of A ahead of time so that encoding only involves solving two matrixes using backward substitution and forward substitution only. This requires time proportional to M^2 which is usually a nice improvement given N ~ 2M.

I implemented the min-col algorithm for LU decomposition described on Radford’s website [5]. While preprocessing a large matrix can take a long time, the preprocessed output can be used each time a message is encoded which reduces the actual encoding time.

Using the sparse matrix representation in Matlab greatly increases the speed of the algorithm. I created two versions of the algorithm in LabView, one using regular matrixes and a second using sparse matrixes. Although both work, the efficiency of the sparse implementation was reduced by the fact that Labview does not use linked lists to represent their arrays.

I also implemented the efficient encoding algorithm described in [1] and [4] in Matlab. The paper describes a method to form an approximate lower triangular H matrix which can be used for encoding in near linear time. Although the algorithm I created worked well for small matrixes, when testing with large matrixes I saw erroroneous results and did not have time to fully debug the issues. The program is also posted as a reference to an alternative approach.