"Complexity Issues in Coding Theory 001.ps.gz" - читать интересную книгу автора

ECCCTR97-046 Electronic Colloquium on Computational Complexity - Reports Series 1997 - available via:

FTP: ftp.eccc.uni-trier.de:/pub/eccc/ WWW: http://www.eccc.uni-trier.de/eccc/ Email: [email protected] with subject 'help eccc'

115 syndrome trellis 73 test set 48ff. time complexity 5 trellis complexity 74 zero neighbor 52

114 Index algorithmic problem 5 almost all 7

bound

Blokh-Zyablov 28 Justesen 27 Zyablov 27

boundary 51 channel 70

additive 70 discrete 70 memoryless 70 symmetric 70

code

algorithmic problems for 8 asymptotically good 11 correcting defects 34 correcting erasures 31 correcting localized errors 37 limit parameters of 11 linear

concatenated 26 covering radius of 41 low-density parity-check 13 rate of 8 regular-graph 17 relative distance of 8 systematic 7

check set 7 computation 5 covering 57 covering system 58

decision problem 5 defect 34

decoding

bounded distance 8 complete minimum distance 8 covering set 56 hard-decision 9, 46 gradient-like 48 information set 55 iterated majority voting 13

parallel 16 generalized minimum distance 85 list cascade 67

maximum likelihood 70 minimal-vectors 50 soft-decision 9, 70ff. split syndrome 48

punctured 62 supercode 64f. syndrome 45 syndrome trellis 72ff. weighted-partitions 83 zero-neighbors 52

edge-vertex incidence graph 18 error-correcting pair 24 Evseev lemma 45