A linear bound for sliding-block decoder window size

Abstract

The author gives an upper bound on the necessary length of a sliding-block decoder window for finite-state codes from arbitrary n-ary data into any constrained system Sigma with capacity at least log(n) presented by a graph G with memory m and anticipation a. Specifically, it is shown that the ACH code construction algorithm can be used to construct a code with a sliding-block decoder at rate t:t and with window length m+a+2t, where t is upper-bounded by a linear function of the number of states of G. It is demonstrated that this is the best one can do in the sense that any general upper bound on the decoder window length for finite-state codes into systems Sigma with finite memory must grow at least linearly with the number of states of the graph G presenting Sigma .< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>