Title :
On the inherent intractability of certain coding problems (Corresp.)
Author :
Berlekamp, Elwyn R. ; Mceliece, Robert J. ; Van Tilborg, Henk C A
fDate :
5/1/1978 12:00:00 AM
Abstract :
MEMBER, IEEE, AND HENK C. A. V~ TILBORG The fact that the general decoding problem for linear codes and the general problem of finding the weights of a linear code are both NP-complete is shown. This strongly suggests, but does not rigorously imply, that no algorithm for either of these problems which runs in polynomial time exists.
Keywords :
Decoding; Linear codes; Decoding; Equations; Estimation theory; Feedback; Gaussian channels; Linear code; Polynomials; Processor scheduling; Rate-distortion; Source coding;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.1978.1055873
