Skip to Main content Skip to Navigation
Journal articles

Minimization of circuit registers: retiming revisited

Abstract : In this paper, we address the following problem: given a synchronous digital circuit, is it possible to construct a new circuit computing the same function as the original one but using a minimal number of registers? The construction of such a circuit can be done in polynomial time and is based on a result of Orlin for one periodic bi-infinite graphs showing that the cardinality maximum flow is equal to the size of a minimum cut. The idea is to view such a graph as the unfolding of the dependences in a digital circuit.
Document type :
Journal articles
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Jean Mairesse Connect in order to contact the contributor
Submitted on : Tuesday, July 24, 2007 - 6:40:48 PM
Last modification on : Thursday, January 20, 2022 - 5:28:37 PM
Long-term archiving on: : Tuesday, September 21, 2010 - 1:41:29 PM


Files produced by the author(s)


  • HAL Id : inria-00072480, version 2



Bruno Gaujal, Jean Mairesse. Minimization of circuit registers: retiming revisited. Discrete Applied Mathematics, Elsevier, 2007. ⟨inria-00072480v2⟩



Les métriques sont temporairement indisponibles