Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 1990 | Published
Journal Article Open

The complexity of information set decoding

Abstract

Information set decoding is an algorithm for decoding any linear code. Expressions for the complexity of the procedure that are logarithmically exact for virtually all codes are presented. The expressions cover the cases of complete minimum distance decoding and bounded hard-decision decoding, as well as the important case of bounded soft-decision decoding. It is demonstrated that these results are vastly better than those for the trivial algorithms of searching through all codewords or through all syndromes, and are significantly better than those for any other general algorithm currently known. For codes over large symbol fields, the procedure tends towards a complexity that is subexponential in the symbol size.

Additional Information

© 1990 IEEE. Manuscript received August 8, 1988. Revised February 7, 1990.

Attached Files

Published - 00057202.pdf

Files

00057202.pdf
Files (653.3 kB)
Name Size Download all
md5:a7f679aa997b3645be4a8345f217c583
653.3 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
August 19, 2023