Delay optimization of linear depth Boolean circuits with prescribed input arrival times
We consider boolean circuits \(C\) over the basis \(\Omega=\{\lor,\land\}\) with inputs \(x_1, x_2,\ldots, x_n\) for which arrival times \(t_1,t_2,\ldots,t_n\in\mathbb{N}_0\) are given. For \(1\leq i\leq n\) we define the delay of \(x_i\) in \(C\) as the sum of \(t_i\) and the number of gates on a longest directed path in \(C\) starting at \(x_i\). The delay of \(C\) is defined as the maximum delay of an input. Given a function of the form \[ f(x_1,x_2,\ldots, x_n)=g_{n-1}(g_{n-2}(\ldots g_3(g_2(g_1(x_1,x_2),x_3),x_4),\ldots ),x_{n-1}),x_n) \] where \(g_j\in \Omega\) for \(1\leq j\leq n-1\) and arrival times for \(x_1,x_2,\ldots x_n\), we describe a cubic-time algorithm that determines a circuit for \(f\) over \(\Omega\) that is of linear size and whose delay is at most 1.44 times the optimum delay plus some small constant.
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- scientific article; zbMATH DE number 48134 (Why is no real title available?)
- scientific article; zbMATH DE number 1033441 (Why is no real title available?)
- On the Addition of Binary Numbers
- On the Time Required to Perform Addition
- Parallel Prefix Computation
- The delay of circuits whose inputs have specified arrival times
- Constructing depth-optimum circuits for adders and \textsc{And}-\textsc{Or} paths
- The delay of circuits whose inputs have specified arrival times
- On the cost of optimal alphabetic code trees with unequal letter costs
- New inequality relations between depth and delay
- Faster carry bit computation for adder circuits with prescribed arrival times
- Fast prefix adders for non-uniform input arrival times
- Faster linear-size \textsc{and}-\textsc{or} path and adder circuits
This page was built for publication: Delay optimization of linear depth Boolean circuits with prescribed input arrival times
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q866541)
