首页|Small Hazard-Free Transducers

Small Hazard-Free Transducers

扫码查看
原文链接
  • NETL
  • NSTL
  • IEEE
In digital circuits, hazardous input signals are a result of spurious operation of bistable elements. For example, the problem occurs in circuits with asynchronous inputs or clock domain crossings. Marino (TC’81) showed that hazards in bistable elements are inevitable. Hazard-free circuits compute the “most stable” output possible on hazardous inputs, under the constraint that it returns the same output as the circuit on stable inputs. Ikenmeyer et al. (JACM’19) proved an unconditional exponential separation between the hazard-free complexity and (standard) circuit complexity of explicit functions. Despite that, asymptotically optimal hazard-free sorting circuit are possible (Bund et al., TC’19). This raises the question: Which classes of functions permit efficient hazard-free circuits? We prove that circuit implementations of transducers with small state space are such a class. A transducer is a finite state machine that transcribes, symbol by symbol, an input string of length n into an output string of length n. We present a construction that transforms any function arising from a transducer into an efficient circuit that computes the hazard-free extension of the function. For transducers with constant state space, the circuit has asymptotically optimal size, with small constants if the state space is small.

CircuitsTransducersHazardsLogic gatesSymbolsLogicEncodingBoolean functionsStandardsComputers

Johannes Bund、Christoph Lenzen、Moti Medina

展开 >

CISPA Helmholtz Center for Information Security, Bar-Ilan University, Ramat Gan, Israel|Laboratoire Méthodes Formelles, Université Paris-Saclay, CNRS, ENS Paris-Saclay, Gif-sur-Yvette, France

CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

Alexander Kofkin Faculty of Engineering, Bar-Ilan University, Ramat Gan, Israel

2025

10.1109/TC.2025.3533096

IEEE transactions on computers

IEEE transactions on computers

ISSN：
年,卷(期)：2025.74(5)
  • 28