IEEE Transactions on Information Theory · 2001 · 92 citations · 10 references
EngineeringComputer EngineeringComputer ScienceAlgorithmsOptimizationTheory Of ComputationChannel CodingCoding TheoryError Control CodingError-correcting CodesGraph AlgorithmsLinear ProgrammingBlock CodesEigenvaluesLinear Block CodesLinear CodesMinimum DistanceMinimum Distance BoundsParity Check CodesParity-check Matrices
The parity-check matrix of a linear code is used to define a bipartite code constraint (Tanner) graph in which bit nodes are connected to parity-check nodes. The connectivity properties of this graph are analyzed using both local connectivity and the eigenvalues of the associated adjacency matrix. A simple lower bound on the minimum distance of the code is expressed in terms of the two largest eigenvalues. For a more powerful bound, local properties of the subgraph corresponding to a minimum-weight word in the code are used to create an optimization problem whose solution is a lower bound on the code's minimum distance. Linear programming gives one bound. The technique is illustrated by applying it to sparse block codes with parameters [7,3,4] and [42,23,6].
10
Low-density parity-check codes
Robert G. Gallager · IEEE Transactions on Information Theory · 1962 · 10.6K citations · Full text
J. J. Stiffler · 1971 · 1.4K citations
M. Sipser, Daniel A. Spielman · IEEE Transactions on Information Theory · 1996 · 942 citations