article Open AccessTop 10% cited

On the inherent intractability of certain coding problems (Corresp.)

IEEE Transactions on Information Theory · 1978 · Vol. 24(3) · pp. 384–386

Elwyn R. Berlekamp✉(University of California, Berkeley)Robert J. McEliece(Jet Propulsion Laboratory)H. van Tilborg(Eindhoven University of Technology)

View via DOI Publisher page

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.

Coding theory and cryptography graph theory and CDMA systems Error Correcting Code TechniquesDecoding methodsCoding (social sciences)AlgorithmList decodingMathematicsComputer scienceLinear codeDiscrete mathematicsCombinatoricsBlock code

Citations

1,486

FWCI

6.78

field-weighted impact

References

Percentile

96%

vs. same field & year

Citations per year

Cited by

Good error-correcting codes based on very sparse matrices