1-7hit |
Toshishige SHIMAMURA Hiroki MORIMURA
A new threshold circuit technique is proposed for a vibration sensing circuit that operates at a nanowatt power level. The sensing circuits that use sample-and-hold require a clock signal, and they consume power to generate a signal. In the use of a Schmitt trigger circuit that does not use a clock signal, a sink current flows when thresholding the analog signal output. The requirements for millimeter-sized wireless sensor nodes are an average power on the order of a nanowatt and a signal transition time of less than 1 ms. To meet these requirements, our circuit limits the sink current with a nanoampere-level current source. The chattering caused by current limiting is suppressed by feeding back the change in output voltage to the limiting current. The increase in the signal transition time that is caused by current limiting is reduced by accelerating the discharge of the load capacitance. For a test chip fabricated in the 0.35-µm CMOS process, the proposed threshold circuits operate without chattering and the average powers are 0.7-3 nW. The signal transition times are estimated in a circuit simulation to be 65-97 µs. The proposed circuit has 1/150th the power-delay product with no time interval of the sensing operation under the condition that the time interval is 1s. These results indicate that, the proposed threshold circuits are suitable for vibration sensing in millimeter-sized wireless sensor nodes.
Hiroki MANIWA Takayuki OKI Akira SUZUKI Kei UCHIZAWA Xiao ZHOU
The energy of a threshold circuit C is defined to be the maximum number of gates outputting ones for an input assignment, where the maximum is taken over all the input assignments. In this paper, we study computational power of threshold circuits of energy at most two. We present several results showing that the computational power of threshold circuits of energy one and the counterpart of energy two are remarkably different. In particular, we give an explicit function which requires an exponential size for threshold circuits of energy one, but is computable by a threshold circuit of size just two and energy two. We also consider MOD functions and Generalized Inner Product functions, and show that these functions also require exponential size for threshold circuits of energy one, but are computable by threshold circuits of substantially less size and energy two.
Kazuyuki AMANO Masafumi YOSHIDA
We present an explicit construction of a MAJn-2 °MAJn-2 circuit computing MAJn for every odd n≥7. This gives a partial solution to an open problem by Kulikov and Podolskii (Proc. of STACS 2017, Article No.49).
Recently, Impagliazzo et al. constructed a nontrivial algorithm for the satisfiability problem for sparse threshold circuits of depth two which is a class of circuits with cn wires. We construct a nontrivial algorithm for a larger class of circuits. Two gates in the bottom level of depth two threshold circuits are dependent, if the output of the one is always greater than or equal to the output of the other one. We give a nontrivial circuit satisfiability algorithm for a class of circuits which may not be sparse in gates with dependency. One of our motivations is to consider the relationship between the various circuit classes and the complexity of the corresponding circuit satisfiability problem of these classes. Another background is proving strong lower bounds for TC0 circuits, exploiting the connection which is initiated by Ryan Williams between circuit satisfiability algorithms and lower bounds.
Hiroshi FUKETA Masanori HASHIMOTO Yukio MITSUYAMA Takao ONOYE
Timing margin of a chip varies chip by chip due to manufacturing variability, and depends on operating environment and aging. Adaptive speed control with timing error prediction is promising to mitigate the timing margin variation, whereas it inherently has a critical risk of timing error occurrence when a circuit is slowed down. This paper presents how to evaluate the relation between timing error rate and power dissipation in self-adaptive circuits with timing error prediction. The discussion is experimentally validated using adders in subthreshold operation in a 90 nm CMOS process. We show a trade-off between timing error rate and power dissipation, and reveal the dependency of the trade-off on design parameters.
Shao-Chin SUNG Kunihiko HIRAISHI
Obradovic and Parberry showed that any n-input k-ary function can be computed by a depth 4 unit-weight k-ary threshold circuit of size O(nkn). They also showed that any n-input k-ary symmetric function can be computed by a depth 6 unit-weight k-ary threshold circuit of size O(nk+1). In this paper, we improve upon and expand their results. The k-ary threshold circuits of nonunit weight and unit weight are considered. We show that any n-input k-ary function can be computed by a depth 2 k-ary threshold circuit of size O(kn-1). This means that depth 2 is optimal for computing some k-ary functions (e.g., a PARITY function). We also show that any n-input k-ary function can be computed by a depth 3 unit-weight k-ary threshold circuit of size O(kn). Next, we show that any n-input k-ary symmetric function can be computed by a depth 3 k-ary threshold circuit of size O(nk-1), and can be computed by a depth 3 unit-weight k-ary threshold circuit of size O(knk-1). Finally, we show that if the weights of the circuit are polynomially bounded, some k-ary symmetric functions cannot be computed by any depth 2 k-ary threshold circuit of polynomial-size.
Shao-Chin SUNG Tetsuro NISHINO
In this paper, we show that a parity function with n variables can be computed by a threshold circuit of depth O((log n)/c) and size O((2clog n)/c), for all 1c [log(n+1)]-1. From this construction, we obtain an O(log n/log log n) upper bound for the depth of polylogarithmic size threshold circuits for parity functions. By using the result of Impagliazzo, Paturi and Saks[5], we also show an Ω (log n/log log n) lower bound for the depth of the threshold circuits. This is an answer to the open question posed in [11].