Title :
Links between complexity theory and constrained block coding
Author :
Stockmeyer, Larry ; Modha, Dharmendra S.
Author_Institution :
IBM Almaden Res. Center, San Jose, CA, USA
Abstract :
The goal of this paper is to establish links between computational complexity theory and the theory and practice of constrained block coding. The complexities of several fundamental problems in constrained block coding are precisely classified in terms of the existing complexity-theoretic structure. One type of problem studied is the design of encoder and decoder circuits using minimum or approximately minimum hardware for a given constraint and rate. Another is computing the maximum rate of a block code, given the constraint and the codeword length
Keywords :
block codes; computational complexity; constraint theory; block code; codeword length; complexity-theoretic structure; computational complexity theory; constrained block coding; decoder circuits; encoder circuits; maximum rate computation; Block codes; Complexity theory; Computational complexity; Computer networks; Constraint theory; Decoding; Hardware; Logic circuits; Logic gates; Polynomials;
Conference_Titel :
Information Theory, 2001. Proceedings. 2001 IEEE International Symposium on
Conference_Location :
Washington, DC
Print_ISBN :
0-7803-7123-2
DOI :
10.1109/ISIT.2001.936114
