Maximum-likelihood decoding is an important and powerful tool in communications to obtain the optimal performance of a channel code.
Unfortunately, simulating the maximum-likelihood performance of a code is a hard problem whose complexity grows exponentially with the blocklength of the code. In order to optimize the performance, we minimize the number of ones in the underlying parity-check matrix, formulate it as an integer program and give a heuristic algorithm to solve it. Using these minimized matrices, we significantly reduce the runtime of several ML decoders for several codes, resulting in speedups of up to 81% compared to the original matrices.
