  Parity check matrices (PCMs) are used to define linear error correcting codes
and ensure reliable information transmission over noisy channels. The set of
codewords of such a code is the null space of this binary matrix.
  We consider the problem of minimizing the number of one-entries in
parity-check matrices. In the maximum-likelihood (ML) decoding method, the
number of ones in PCMs is directly related to the time required to decode
messages. We propose a simple matrix row manipulation heuristic which alters
the PCM, but not the code itself. We apply simulated annealing and greedy local
searches to obtain PCMs with a small number of one entries quickly, i.e. in a
couple of minutes or hours when using mainstream hardware. The resulting
matrices provide faster ML decoding procedures, especially for large codes.
