DocumentCode :
747321
Title :
Construction of encoders with small decoding look-ahead for input-constrained channels
Author :
Ashley, Jonathan J. ; Marcus, Brian H. ; Roth, Ron M.
Author_Institution :
Res. Div., IBM Almaden Res. Center, San Jose, CA, USA
Volume :
41
Issue :
1
fYear :
1995
fDate :
1/1/1995 12:00:00 AM
Firstpage :
55
Lastpage :
76
Abstract :
An input-constrained channel is defined as the set S of finite sequences generated by a finite labeled directed graph which defines the channel. A construction based on a result of Adler, Goodwyn, and Weiss (1977) is presented for finite-state encoders for input-constrained channels. Let G=(V, E) denote a smallest deterministic presentation of S. For a given input-constrained channel S and for any rate p: q up to the capacity c(S) of S, the construction provides finite-state encoders of fixed-rate p: q that can be implemented in hardware with a number of gates which is at most polynomially large in |V|. When p/q<c(S), the encoders have order ⩽12|V|, namely, they can be decoded by looking ahead at up to 12|V| symbols, thus improving slightly on the order of previously known constructions. A stronger result holds when p/q⩽c(S)-((log2, e)/(2Pq)) and S is of finite memory, where the encoders can. Be decoded by a sliding-block decoder with look-ahead ⩽2|V|+1
Keywords :
directed graphs; encoding; sequential decoding; telecommunication channels; decoding look-ahead; deterministic presentation; finite labeled directed graph; finite sequences; finite-state encoders; gates; input-constrained channels; sliding-block decoder; Computer science; Decoding; Hardware; Information theory; Magnetic devices; Magnetic separation; Optical devices; Polynomials; Read-write memory;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/18.370118
Filename :
370118
Link To Document :
بازگشت