6533b7ddfe1ef96bd1273f4f

RESEARCH PRODUCT

Presentations of constrained systems with unconstrained positions

Gabriele FiciMaxime CrochemoreMarie-pierre Béal

subject

[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]finite-memory systemperiodic-finite-type (PFT) system[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciences02 engineering and technologyLibrary and Information Sciences01 natural sciencesModulation coding0202 electrical engineering electronic engineering information engineeringMathematicsDiscrete mathematicsChannel codefinite-state encodermodulation codeDAWG020206 networking & telecommunicationsDirected graphDirected acyclic graphforbidden blockComputer Science ApplicationsFinite sequence010201 computation theory & mathematicscodeError detection and correctionrun-length limited (RLL) codesInformation SystemsCoding (social sciences)maximum transition run (MTR)

description

International audience; 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.

yearjournalcountryeditionlanguage
2005-05-01
https://hal.science/hal-00619692