Coffey, John T. and Goodman, Rodney M. (1990) The complexity of information set decoding. IEEE Transactions on Information Theory, 36 (5). pp. 1031-1037. ISSN 0018-9448. https://resolver.caltech.edu/CaltechAUTHORS:20190314-142000507
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Published Version
See Usage Policy. 637Kb |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190314-142000507
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.
| Item Type: | Article | ||||||
|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||
| Additional Information: | © 1990 IEEE. Manuscript received August 8, 1988. Revised February 7, 1990. | ||||||
| Issue or Number: | 5 | ||||||
| Record Number: | CaltechAUTHORS:20190314-142000507 | ||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20190314-142000507 | ||||||
| Official Citation: | J. T. Coffey and R. M. Goodman, "The complexity of information set decoding," in IEEE Transactions on Information Theory, vol. 36, no. 5, pp. 1031-1037, Sept. 1990. doi: 10.1109/18.57202 | ||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
| ID Code: | 93833 | ||||||
| Collection: | CaltechAUTHORS | ||||||
| Deposited By: | George Porter | ||||||
| Deposited On: | 14 Mar 2019 21:51 | ||||||
| Last Modified: | 03 Oct 2019 20:58 |
Repository Staff Only: item control page
