| TR#: | CS0965 |
| Class: | CS |
| Title: | Lower bounds on the anticipation of encoders for input-constrained channels |
| Authors: | Gitit Ruckenstein and Ron M. Roth |
| CS0965.pdf | |
| Abstract: | An input-constrained channel S is defined as the set of words generated by a finite labeled directed graph. A fixed-rate finite-state encoder for S is a finite-state machine E that maps unconstrained binary sequences into sequences of S in a lossless manner, and the anticipation of E measures the smallest decoding look-ahead of any decoder of E. It is shown that every fixed-rate finite-state encoder with finite anticipation for S can be obtained through state-spitting rounds applied to a certain graph presentation of S. By further characterizing the properties of such state-splitting rounds, lower bounds are derived on the anticipation of any fixed-rate finite state encoder for S with a given rate p:q. Those lower bounds improve on previously known bounds and, in particular, they are shown to be tight for the common rates used for the (1,7)-RLL and (2,7)-RLL constraints. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1999/CS/CS0965), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1999
To the main CS technical reports page