A Low-density parity-check code is a code that uses a sparse parity-check matrix. This sparse matrix is randomly generated subject to the sparsity constraints. These codes are among the state of the art codes. Decoding them is an NP-complete problem, but there are good approximate polynomial time decoders. They were first designed by Gallager in 1962. See Sparse graph codes.