Title :
Finite-state codes
Author :
Pollara, Fabrizio ; Mceliece, Robert J. ; Abdel-Ghaffar, Khaled
Author_Institution :
Jet Propulsion Lab., Pasadena, CA, USA
fDate :
9/1/1988 12:00:00 AM
Abstract :
A class of codes called finite-state (FS) codes is defined and investigated. The codes, which generalize both block and convolutional codes, are defined by their encoders, which are finite-state machines with parallel inputs and outputs. A family of upper bounds on the free distance of a given FS code is derived. A general construction for FS codes is given, and it is shown that in many cases the FS codes constructed in this way have a free distance that is the largest possible. Catastrophic error propagation (CEP) for FS codes is also discussed. It is found that to avoid CEP one must solve the graph-theoretic problem of finding a uniquely decodable edge labeling of the state diagram
Keywords :
boundary-value problems; codes; encoding; errors; graph theory; block codes; catastrophic error propagation; convolutional codes; encoders; finite-state codes; finite-state machines; graph-theoretic problem; parallel inputs; parallel outputs; state diagram; upper bounds; Block codes; Convolutional codes; Information theory; Notice of Violation; Random processes; Random variables; Rate distortion theory; Source coding; Stochastic processes; Upper bound;
Journal_Title :
Information Theory, IEEE Transactions on
