Presentations of constrained systems with unconstrained positions

Marie-Pierre Béal 1 Maxime Crochemore 1 Gabriele Fici 1
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
Abstract : We give a polynomial-time construction of the set of sequences that satisfy a finite-memory constraint defined by a finite list of forbidden blocks, with a specified set of bit positions unconstrained. Such a construction can be used to build modulation/error-correction codes (ECC codes) like the ones defined by the Immink-Wijngaarden scheme in which certain bit positions are reserved for ECC parity. We give a lineartime construction of a finite-state presentation of a constrained system defined by a periodic list of forbidden blocks. These systems, called periodic-finite-type systems, were introduced by Moision and Siegel. Finally, we present a linear-time algorithm for constructing the minimal periodic forbidden blocks of a finite sequence for a given period.
Document type :
Journal articles
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download
https://hal-upec-upem.archives-ouvertes.fr/hal-00619692
Contributor : Marie-Pierre Béal <>
Submitted on : Thursday, October 6, 2011 - 2:20:01 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:02 PM
Long-term archiving on : Saturday, January 7, 2012 - 2:20:32 AM

Files

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619692, version 1

Collections

CNRS | UNIV-MLV | LIGM_ALGO | LIGM | ENPC | PARISTECH | UPEC-UPEM

Citation

Marie-Pierre Béal, Maxime Crochemore, Gabriele Fici. Presentations of constrained systems with unconstrained positions. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2005, 51 (5), pp.1891-1900. ⟨hal-00619692⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

255

Files downloads

257

Contact

CCSD