On the principal state method for run-length limited sequences

摘要

Presents a detailed result on Franaszek's (1968) principal state method for the generation of run-length constrained codes. The authors show that, whenever the constraints k and d satisfy k/spl ges/2d<0, the set of "principal states" is s/sub 0/, s/sub 1/, /spl middot//spl middot//spl middot/, s/sub k-1/. Thus there is no need for Franaszek's search algorithm anymore. The counting technique used to obtain this result also shows that "state independent decoding" can be achieved using not more than three codewords per message. Previously, it was not known beforehand that one could use fewer codewords per message than there were principal states. The counting technique also allows one to compare the principal state method with other practical schemes originating from the work of Tang and Bahl (1970) and allows one to use an efficient enumerative coding implementation of the encoder and decoder.