We present a simple solution to secretly sharing a factoring witness (for given N) in a publicly-verifiable manner. Compared to the previous PVSS schemes to secretly sharing a factoring witness, the scheme enjoys the following properties: (1) the formal proofs of security can be given; (2) it is designed to be conceptually simpler; (3) it needs fewer communicated bits and, if not-so low exponent RSA (e.g., e > 219+1) is used in the previous schemes, fewer computations; (4) no general multi-party computation is required in the preparation phase.
Akihiro MORIMOTO Koji KOTANI Kazushi TAKAHASHI Shigetoshi SUGAWA Tadahiro OHMI
Precise interconnect analysis is strongly required for giga-scale integration the operation frequency of which is excess 10 GHz. In this study, detailed and accurate analyses of a coaxial interconnect and an actual rectangular interconnect have been performed by the direct evaluation of Maxwell's equations and the finite element method, respectively. It has been revealed that there are two propagation modes for LSI interconnects: skin depth limited propagation mode and interconnect induced slow wave mode. In a miniaturized interconnect, the propagation mode is the interconnect induced slow wave mode; therefore, we cannot obtain the light-speed propagation due to such an interconnect-induced effect. In order to overcome this speed limitation or to improve signal integrity, it is essential to introduce a short interconnect for a miniaturized structure, and a much larger interconnect than the skin depth. We propose a gas-isolated interconnect as a candidate for an ultimately low-k structure in order to increase the signal-propagation speed. By the introduction of such structures, the performance of miniaturized devices in the deep submicron region will be effectively enhanced.
Hyunjin LEE Sung-il CHANG Jongho LEE Hyungcheol SHIN
A MOSFET structure with non-overlapped source-drain to gate region is proposed to overcome the challenges in sub-0.1 µm CMOS device. Key device characteristics were investigated by extensive simulation study. Fringing gate electric field through the dielectric spacer induces inversion layer in the non-overlap region to act as extended S/D region. Electrons were induced reasonably under the spacer. Internal physics and speed characteristics were studied with the non-overlap distance. The proposed structure had good subthreshold slope and DIBL characteristics compared to those of overlapped structure.
Miwa MUTOH Hiroyuki FUKUYAMA Toshihiro ITOH Takatomo ENOKI Tsugumichi SHIBATA
A novel delta-sigma modulator that utilizes a resonant-tunneling diode (RTD) quantizer is proposed and its operation is investigated by HSPICE simulations. In order to eliminate the signal-to-noise-and-distortion ratio (SINAD) degradation caused from the poor isolation of a single-stage quantizer (1SQ), a three-stage quantizer (3SQ), which consists of three cascoded RTD quantizers, is introduced. At a sample rate of 10 Gsps (samples per a second) and a signal bandwidth of 40 MHz (oversampling ratio of 128), the modulator demonstrates a SINAD of 56 dB, which corresponds to the effective number of bits of 9.3.
Toshinori TAKABATAKE Masato KITAKAMI Hideo ITO
In interconnection networks, deadlock recovery has been studied in routing strategy. The routing strategy for the deadlock recovery is intended to optimize the routing performance when deadlocks do not occur. On the other hand, it is important to improve the routing performance by handling deadlocks if they occur. In this paper, a routing strategy for suspensive deadlock recovery called an escape-restoration routing is proposed and its performance is evaluated. In the principle of the proposed techniques, a small amount of exclusive buffer (escape-buffer) at each router is prepared for handling one of deadlocked packets. The transmission of the packet is suspended by temporarily escaping it to the escape-buffer. After the other deadlocked packets were sent, the suspended transmission resumes by restoring the escaped packet. Evaluation results show that the proposed techniques can improve the routing performance more than that of the previous recovery-based techniques in handling deadlocks.
Masafumi TSUTSUI Toshiaki NAGAI Masahiro ASADA
We report on the analysis and fabrication of vertical PtSi Schottky source/drain metal oxide semiconductor field effect transistors (MOSFETs), which are suitable for combination with quantum effect devices such as resonant tunneling diodes. Analysis was carried out by one-dimensional approximation of the device structure, WKB approximation of the tunneling probability in Schottky barrier tunneling and self-consistent calculation. Theoretical calculation showed good drivability (750 µA/µm) of this device with tOX = 1 nm and tSi = 5 nm. As a preliminary experiment, devices with a Si channel thickness of 8 nm, 20 nm or 30 nm and a vertical channel length of 55 nm were fabricated. Although the drain current at the "on" state was small due to the thick gate oxide of 8 nm, analysis and measurement showed reasonable agreement with respect to the drivability. Based on the results of theoretical analysis, the device drivability can be much improved by reducing the gate oxide thickness.
Muhammad E.S. ELRABAA Mohab H. ANIS Mohamed I. ELMASRY
A new contention-free Domino logic (CF-Domino) that is especially suited for low threshold voltage (LVT) is reported. Its superior noise margin and speed over conventional Domino circuits for LVTs are demonstrated using HSPICE(R) simulations and a 0.25 µm CMOS technology with a supply voltage of 2.5 V. The impacts of the new technique on dynamic and leakage powers and area were evaluated. At a 3% area increase, and keeping the noise margins constant, the new CF-DOMINO achieves 20% less delay than conventional DOMINO as the threshold voltage scales from 450 mV down to 200 mV. It also achieved 13% less dynamic power and 5% less leakage at that threshold voltage.
Ayad SOUFIANE Tsuyoshi ITOKAWA Ryozo NAKAMURA
Spiral hashing is a well known dynamic hashing algorithm. Traditional analysis of this search algorithm has been proposed under the assumption that all keys are uniformly accessed. In this paper, we present a discrete analysis of the average search cost in consideration of the frequency of access on each key for this spiral hashing algorithm. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. The evaluate formulae derived from the proposed analysis can exactly evaluate the average and variance of the search cost in conformity with any probability distribution of the frequency of access.
In the last three decades, task scheduling problems onto parallel processing systems have been extensively studied. Some of those problems take communication delays into account. In most of previous works, the structure of the parallel processing systems of the scheduling problem is restricted to be fully connected. However, the realistic models of parallel processing systems, such as hypercubes, grids, tori, and so forth, are not fully connected and the communication delay has a great effect on the completion time of tasks. In this paper, we show that the problem of scheduling tasks onto a hypercube/grid is NP-complete even if the task set forms an out- or in-tree and the execution time of each task and each communication take one unit time. Moreover, we construct linear time algorithms for computing an optimal schedule of some classes of binary and ternary trees onto a hypercube if each communication has one unit time.
Jung-Sik JEONG Kei SAKAGUCHI Jun-ichi TAKADA Kiyomichi ARAKI
It is known that MUSIC and ESPRIT algorithms can estimate simultaneously both the instantaneous Direction of Arrival (DOA) and the instantaneous Angular Spread (AS) in multiple scattering environments. These algorithms use the Extended Array Mode Vector (EAMV) with complex angle. The previous work evaluated the performance of those algorithms by comparing the estimated DOA and the estimated AS with the DOA and the AS given in the EAMV, which uses the first-order approximation. Thus, this evaluation method has not clearly reflected the estimation accuracy of MUSIC and ESPRIT. This paper presents the joint estimation performance of MUSIC and ESPRIT by introducing the criteria for evaluation. For this, the spatial signature (SS) is reconstructed from the estimates of the DOA and the AS, and compared to the true SS in the meaning of data fitting.
In order for a service discipline to be used for guaranteed service networks at very high speed, its overall implementation must be scalable while it provides as wide a network schedulability region as possible. From this point of view, GPS-based service disciplines provide a narrow network schedulability region while EDF-based disciplines suffer from the implementation complexities of rate-controllers and admission control. Alternatively, although service disciplines based on service-curves can provide a wider network schedulability region than GPS-based and EDF-based disciplines, they may have even worse implementation complexities than EDF-based disciplines. In this paper, we propose to employ a service discipline based on our specific service-curves. We show that our service discipline has comparable implementation complexity to GPS-based disciplines while providing the same wide network schedulability region that EDF-based disciplines can provide. In fact, this service discipline is an SCED service discipline proposed in [14]. However, our specific service-curves provide the SCED service discipline with the same network schedulability region that EDF-based disciplines can provide, O(1) complexity for deadline calculation, and O(N) complexity for admission control where N is the number of sessions.
Yasuyuki SAKAI Kouichi SAKURAI
We discuss multidoubling methods for efficient elliptic scalar multiplication. The methods allows computation of 2k P directly from P without computing the intermediate points, where P denotes a randomly selected point on an elliptic curve. We introduce algorithms for elliptic curves with Montgomery form and Weierstrass form defined over finite fields with characteristic greater than 3 in terms of affine coordinates. These algorithms are faster than k repeated doublings. Moreover, we apply the algorithms to scalar multiplication on elliptic curves and analyze computational complexity. As a result of our implementation with respect to the Montgomery and Weierstrass forms in terms of affine coordinates, we achieved running time reduced by 28% and 31%, respectively, in the scalar multiplication of an elliptic curve of size 160-bit over finite fields with characteristic greater than 3.
This letter proposes a design methodology of a capacitor for a switched capacitor filter. The capacitor design method makes the capacitor accurate to the capacitance ratio and insensitive to the process deviation. The SCF designed is used for the PCM CODEC filter and the deviation of the frequency characteristic is below 0.05 dB for a process deviation 0.5 µm in 5 µm CMOS process.
Ryuhei MIYASHIRO Tomomi MATSUI
Sports scheduling concerns how to construct a schedule of a sports competition mathematically. Many sports competitions are held as round-robin tournaments. In this paper, we consider a particular class of round-robin tournaments. We report some properties of round-robin tournaments and enumerate home-away tables satisfying some practical requirements by computer search.
Satoko MORIGUCHI Kazuo MUROTA Akiyoshi SHIOURA
M-convex functions have various desirable properties as convexity in discrete optimization. We can find a global minimum of an M-convex function by a greedy algorithm, i.e., so-called descent algorithms work for the minimization. In this paper, we apply a scaling technique to a greedy algorithm and propose an efficient algorithm for the minimization of an M-convex function. Computational results are also reported.
The main objective of vehicle suspensions is to improve ride comfort and road holding ability. Though passive suspensions consist of spring and damper, active suspensions adopt an actuator in addition to passive suspensions. In this paper, a quarter car model with an asymmetric hydraulic actuator is used. Moreover, the damping coefficient of the damper, which is changed according to the actuator velocity, is considered. The LPV (Linear Parameter Varying) model is obtained by applying feedback linearization technique. Next, a gain-scheduled controller, based on LQ regulator with different weighting factor, is designed according to the actuator velocity and the stability of the proposed controller is also proved. The effectiveness of the proposed controller is shown by numerical simulations.
Toshiyuki YOROZUYA Koji OHASHI Mineo KANEKO
In this paper, we study loop pipeline scheduling problem under given resource assignment (operation to functional unit assignments and data to register assignments), which is one of the key tasks in data-path synthesis based on the assignment solution space exploration. We show an approach using a precedence constraint graph with parametric disjunctive arcs generated from the specified assignment information, and derive a scheduling method using branch-and-bound exploration of the parameter space. As an application of the proposed scheduling method, it is incorporated with Simulated-Annealing (SA) based exploration of assignment solution space, and it is demonstrated that data-paths of the fifth-order elliptic wave filter are successfully synthesized.
In this paper, new integrated schemes of scheduling real-time traffic and cell loss control in high speed ATM networks are proposed for multiple priorities based on variable queue length thresholds for scheduling and the Partial Buffer Sharing policy for cell loss control. In our schemes, the queues for buffering arriving cells can be constructed in two ways: one individual queue for each user connection, or one physical queue for all user connections. The proposed schemes are considered to provide guaranteed QoS for each connection and cell sequence integrity for virtual channel/path characteristics. Moreover, these new schemes are quite flexible and can realize different scheduling algorithms. This paper also provides the Stochastic Petri Net models of these integrated schemes and an approximate analysis technique, which significantly reduces the complexity of the model solution and can be applied to real ATM switch models. From the numerical results, we can see that our schemes outperform those well-known schemes such as the head-of-line (HOL) priority control and the queue length threshold (QLT) policy.
Hiroshige OHNO Hiroshi NARUSE Toshio KURASHIMA Atsushi NOBIKI Yasuomi UCHIYAMA Yuki KUSAKABE
We applied a Brillouin-OTDR, which is a distributed optical fiber strain sensor, to two actual concrete piles. The piles were made for use as highway foundations by on-site-pouring at construction sites and underwent load testing to ensure that their characteristics satisfied the required levels. Compressive strain caused by the load exerted on the piles was measured to an accuracy of 0.01% and a spatial resolution of 1 m. This measurement was obtained by embedding a strain-sensing optical fiber in the piles during construction. The results showed that there was good agreement between the measured strain and both the theoretical values and the values obtained with a conventional strain gauge based on electric resistance. Furthermore, the obtained strain distribution reflected the effects of friction between the pile surface and the ground. These results demonstrate the effectiveness of the Brillouin-OTDR for this kind of testing and also as a means of obtaining detailed data on the strain in concrete piles.
This paper proposes new recursive fixed-point smoother and filter using covariance information in linear discrete-time stochastic systems. In this paper, to be able to treat the estimation of the stochastic signal, a performance criterion, extended from the criterion in the H estimation problem, is newly proposed. The criterion is transformed equivalently into a min-max principle in game theory, and an observation equation in a Krein space is obtained as a result. The estimation accuracy of the proposed estimators are compared with the recursive least-squares (RLS) Wiener estimators, the Kalman filter and the fixed-point smoother based on the state-space model.