LINEAR BOUND FOR SLIDING-BLOCK DECODER WINDOW SIZE.

Abstract

Summary form only given. Methods presented by other authors for coding arbitrary n-ary sequences into constrained systems of sequences, called subshifts of finite type and defined by labeled directed graphs, are considered. The codes have limited error propagation because the decoders are sliding-block with a finite window size. Here, the author proves an upper bound for the necessary decoding window size. For codes, with coding ratio 1, from arbitrary n-ary sequences into subshifts of finite type of entropy at least log n, where n is an integer, the bound is quadratic in the number of states in the natural directed graph defining the constrained system of sequences. In the case where the entropy is greater than log n and the memory of the subshift of finite type is 1, the bound is linear.