DocumentCode :
1316528
Title :
On the decoding delay of encoders for input-constrained channels
Author :
Ashley, Jonathan J. ; Marcus, Brian H. ; Roth, Ron M.
Author_Institution :
IBM Res. Div., Almaden Res. Center, San Jose, CA, USA
Volume :
42
Issue :
6
fYear :
1996
fDate :
11/1/1996 12:00:00 AM
Firstpage :
1948
Lastpage :
1956
Abstract :
Finite-state encoders that encode n-ary data into a constrained system S are considered. The anticipation, or decoding delay, of such an (S,n)-encoder is the number of symbols that a state-dependent decoder needs to look ahead in order to recover the current input symbol. Upper bounds are obtained on the smallest attainable number of states of any (S, n)-encoder with anticipation t. Those bounds can be explicitly computed from t and S, which implies that the problem of checking whether there is an (S, n)-encoder with anticipation t is decidable. It is also shown that if there is an (S,n)-encoder with anticipation t, then a version of the state-splitting algorithm can be applied to produce an (S, n) encoder with anticipation at most 2t-1. We also observe that the problem of checking whether there is an (S, n)-encoder having a sliding-block decoder with a given memory and anticipation is decidable
Keywords :
block codes; decoding; delays; anticipation; constrained system; current input symbol recovery; decoding delay; finite state encoders; input constrained channels; memory; sliding block decoder; state dependent decoder; state splitting algorithm; upper bounds; Computer science; Decoding; Delay; Magnetic devices; Optical devices; Read-write memory; Upper bound;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/18.556686
Filename :
556686
Link To Document :
بازگشت