An English auction is the most familiar type of auctions. Generally, an electronic auction has mainly two entities, the registration manager (RM) who treats the registration of bidders, and the auction manager (AM) who holds auctions. Before starting an auction, a bidder who wants to participate in English auction is registered to RM with her/his information. An electronic English auction protocol should satisfy the following nine properties, (a) Anonymity, (b) Traceability, (c) No framing, (d) Unforgeability, (e) Fairness, (f) Verifiability, (g) Unlinkability among plural auctions, (h) Linkability in an auction, and (i) Efficiency of bidding. Furthermore from the practical point of view we add two properties (j) Easy revocation and (k) One-time registration. A group signature is adapted to an English auction in order to satisfy (a), (b), and (f). However such a direct adoption suffers from the most critical drawback of efficiency in group signatures. In this paper we propose more realistic electronic English auction scheme, which satisfies all of these properties without using a group signature. Notable features of our scheme are: (1) both of bidding and verification of bids are done quite efficiently by introducing a bulletin board, (2) both properties (j) Easy revocation and (k) One-time registration are satisfied.

In 1998, Fan and Lei proposed a partially blind signature scheme that could reduce the computation load and the size of the database for electronic cash systems. In this Letter, we show that their scheme could not meet the untraceability property of a blind signature.

In this paper the authors propose a method for designing the Virtual Private Network (VPN) that guarantees a strict Quality of Service (QoS) over IP networks. The assumed QoS metric is PLP (Packet Loss Probability), and it is guaranteed probabilistically by the provision of an appropriate equivalent bandwidth. We consider two network architectures for constructing VPN, the customer pipe scheme and the Hose scheme, and we present an analytic model to compute the amount of the required bandwidth for the two schemes. Finally, we investigate the validity of the proposition via numerical experiments.

A method for estimating propagation characteristics is described that uses the characteristics of pilot-data-inserted orthogonal frequency division multiplexing (OFDM) signal and is suitable for high-mobility OFDM transmission scheme. Several pilot data are inserted periodically along the frequency axis before the inverse fast Fourier transformation (IFFT) process in the transmitter. At the receiver, the received OFDM signal is correlated with a prepared distinctive OFDM signal in which several pilot data are inserted in the same positions as in the transmitted OFDM symbols and zeros are inserted in the other positions. The propagation characteristics can be estimated precisely and used to cancel any interference caused by delayed waves. Computer simulation shows that this method can estimate the propagation characteristics, which can then be used to cancel the interference caused by delayed waves before the FFT at the receiver under fast multipath fading conditions.

We consider equalizer initialization problems when the transmitted symbol rate is higher than the available channel bandwidth. In this case, the coefficients of an adaptive equalizer in the receiver can be updated only once per a predefined symbol period, requiring unacceptably long training time. The training time can be reduced significantly if the equalizer begins the training process from a properly initialized condition. In this letter, a fast initialization method is analytically designed for a minimum mean squared error (MMSE) type equalizer. Finally, the initialization performance is verified by computer simulation.

A novel power spectral density accumulation (PSDA) method for estimating the bandwidth of the clutter spectra is proposed, based on a priori knowledge of the shape of the clutter spectra. The comparison of the complexity and the performance between the PSDA method and the general ones is presented. It is shown that the PSDA method is effective for the short-time clutter data in the practical application.

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.

We consider the polymatroid packing and covering problems. The polynomial time algorithm with the best approximation bound known for either problem is the greedy algorithm, yielding guaranteed approximation factors of 1/k for polymatroid packing and H(k) for polymatroid covering, where k is the largest rank of an element in a polymatroid, and H(k)=Σi=1k 1/i is the kth Harmonic number. The main contribution of this note is to improve these bounds by slightly extending the greedy heuristics. Specifically, it will be shown how to obtain approximation factors of 2/(k+1) for packing and H(k)-1/6 for covering, generalizing some existing results on k-set packing, matroid matching, and k-set cover problems.

In this letter, we propose high-speed binary to residue converters for moduli 2n, 2n 1 without using look-up table. For integration of residue arithmetic circuit using a signed-digit (SD) number representation with ordinary binary system, the proposed circuits carry out the efficient conversion. Using SD adders instead of ordinary adders that are used in conventional binary to residue converter, the high-speed conversion without the carry propagation can be achieved. Thus, the proposed converter is independent of the size of modulus and can speed up the binary to residue conversion. On the simulation, the conversion delay times are 1.78 ns for modulus 210-1 and 1.73 ns for modulus 210+1 under the condition of 0.6 µm CMOS technology, respectively. The active area of the proposed converter for moduli 210 1 is 335 µm325 µm.

The effectiveness and possible applications of all-optical wavelength conversion using optical fibers are described. Several types of ultra-broad and ultra-fast wavelength conversion using highly-nonlinear fiber are shown. Over 70 nm conversion band by four-wave mixing, 500-fs pulse trains conversion by cross-phase-modulation-based nonlinear optical loop mirror and time-based optical add-drop multiplexing for 160 Gbit/s signal using wavelength conversion by supercontinuum are successfully demonstrated.

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.

The Task-Coalition Assignment Problem (TCAP) is a formalization of the distributed computation problem. In TCAP, a set of agents and a set of tasks are given. A subset of the agents processes a task to produce benefit. The goal of TCAP is to find the combination of the tasks and the subsets of the agents that maximizes the sum of the benefit. In this paper, we define 1-TCAP, which is a practical subclass of TCAP. In 1-TCAP, tasks and agents are characterized by scalar values. We propose a polynomial-time approximation algorithm for 1-TCAP, and show that this algorithm achieves an approximation ratio 9/4. Here, an algorithm achieves an approximation ratio α for a maximization problem if, for every instance, it produces a solution of value at least OPT/α, where OPT is the value of the optimal solution.

A technique that uses a linear prediction error filter (LPEF) and an adaptive digital filter (ADF) to achieve noise reduction in a speech degraded by additive background noise is proposed. It is known that the coefficients of the LPEF converge such that the prediction error signal becomes white. Since a voiced speech can be represented as the stationary periodic signal over a short interval of time, most of voiced speech cannot be included in the prediction error signal of the LPEF. On the other hand, when the input signal of the LPEF is a background noise, the prediction error signal becomes white. Assuming that the background noise is represented as generate by exciting a linear system with a white noise, then we can reconstruct the background noise from the prediction error signal by estimating the transfer function of noise generation system. This estimation is performed by the ADF which is used as system identification. Noise reduction is achieved by subtracting the noise reconstructed by the ADF from the speech degraded by additive background noise.

A digital circuit technique is proposed to process directly bit-stream signals from analog-to-digital converters based on sigma-delta modulation. Newly developed adder and multiplier are fundamental circuit modules for the processing. Using the fundamental modules and up/down counters, other circuit modules such as divider and square root circuits are also realized. The signal processors built of the modules have advantages over multi-bit Nyquist rate processors in circuit scale by the following two distinct features: First, single-bit/multi-bit converters are not needed at the inputs of the processors because the arithmetic modules directly process bit-stream signals. Secondly, the arithmetic modules consist of small number of logic gates. As an application of the technique to digital signal processing for communications, a QPSK demodulator is presented. The demodulator is structured with 40% of logic gates consumed by an equivalent multi-bit demodulator.

This paper proposes a method for mapping a finite state machine (FSM) into a two-dimensional array of LUTs, which is a part of our plastic cell architecture (PCA). LSIs based on the PCA have already implemented as asynchronous devices. Functions that run on the LSIs must also be asynchronous. In order to make good use of the LSIs, a system that translates functions into circuit information for the PCA is needed. We introduce a prototype system that maps an asynchronous FSM onto the PCA. First, a basic mapping method is considered, and then we create three methods to minimize circuit size. Some benchmark suites are synthesized to estimate their efficiency. Experimental results show that all the methods can map an asynchronous FSM onto the PCA and that the three methods can effectively reduce circuit size.

In computer-aided drafting and design, interactive graphics is used to design components, systems, layouts, and structures. There are several approaches for using automated graphical layout tools currently. Our approach employs a genetic algorithm to implement a tool for automated 3D graphical layout design and presentation. The effective use of a genetic algorithm in automated graphical layout design relies on defining a fitness function that reflects user preferences. In this paper, we describe a method to define fitness functions and chromosome structures of selected objects. A learning mechanism is employed to adjust the fitness values of the objects in the selected layout chosen by the user. In our approach, the fitness functions can be changed adaptively reflecting user preferences. Experimental results revealed good performance of the adaptive fitness functions in our proposed mechanism.

A robust adaptive beamforming method is proposed to cancel coherent, as well as incoherent, interference using an array of arbitrary geometry. In this method, coherent interferences are suppressed by a transformation of received data with the estimates of their arrival angles and then, to reject incoherent interferences, the array output power is minimized subject to the look direction constraint in the transformed signal-plus-interference (TSI) subspace. This TSI subspace-based beamforming results in robustness to errors in the angle estimations. Its performance is theoretically examined. The theoretic results conform to simulation results. It is straightforward to apply the theoretic results to the performance analysis of subspace-based adaptive beamfomers only for incoherent interference cancellation.

We describe the logic design of a single-flux-quantum (SFQ) 22 unit switch. It is the main component of the SFQ Banyan packet switch we are developing that enables a switching capacity of over 1 Tbit/s. In this paper, we focus on the design of the controller in the unit switch. The controller does not have a simple "off-the-shelf" conventional circuit, like those used in shift registers or adders. To design such a complicated random logic circuit, we need to adopt a systematic top-down design approach. Using a graphical technique, we first obtained logic functions. Next, to use the deep pipeline architecture, we broke down the functions into one-level logic operations that can be executed within one clock cycle. Finally, we mapped the functions on to the physical circuits using pre-designed SFQ standard cells. The 22 unit switch consists of 59 logic gates and needs about 600 Josephson junctions without gate interconnections. We tested the gate-level circuit by logic simulation and found that it operates correctly at a throughput of 40 GHz.

In this paper, we propose an improved network-flow based multi-way circuit partitioning algorithm whose objective is to minimize the number of sub-circuits. It iteratively extracts a size-maximal feasible sub-circuit one at a time. In our approach, two devices are applied. One is in the use of an exact min-cut graph, and the other is in the idea of keeping the number of I/O pins of the residual circuit as small as possible after one-time extraction. We implemented our algorithm in C for experiments, and tested it with several industrial cases and MCNC benchmarks. Compared to the known approach, we observed more than 10% reduction in average of the sub-circuit number.

This paper describes the circuit design procedure of the zero-current soft switching (ZCS) high frequency inverter for induction heating uses. Its output power can be regulated from its maximum to minimum by the instantaneous current vector control scheme using phase shift control between switching units at a fixed frequency. In addition, it can be safely operated since no extraordinarily high voltage or current results even at a short-circuit period at the load. Also, its overall efficiency reaches 90%. The detailed load and frequency characteristics of the inverter are elucidated by the computer-aided simulation. Then, the circuit design procedure is presented, and practical numerical examples are obtained according to this procedure which reveal that the inverter is highly practical and the design procedure is effective. The trial inverters yielding 2 kW or 4 kW were actually prepared. The observed values of the voltages and currents of the inverters were found to be in good agreement with the calculated ones. These facts certificate the validity of the proposed design procedure.