Chung-Jr LIAN Zhong-Lan YANG Hao-Chieh CHANG Liang-Gee CHEN
This paper presents a hardware-efficient architecture of tree-depth scan (TDS) and multiple quantization (MQ) scheme for zerotree coding in MPEG-4 still texture coder. The proposed TDS architecture can achieve its maximal throughput to area ratio and minimize the external memory access with only one wavelet-tree size on-chip buffer. The MQ scheme adopts the power-of-two (POT) quantization to realize a cost-effective hardware implementation. The prototyping chip has been implemented in TSMC 0.35 µm CMOS 1P4M technology. This architecture can handle 30 4-CIF (704576) frames per second with five spatial scalability and five SNR scalability layers at 100 MHz working frequency.
Takahide SATO Shigetaka TAKAGI Nobuo FUJII
A novel linear voltage-to-current conversion circuit for a rail-to-rail input voltage is proposed in this paper. A pair of MOSFETs operating in plural regions are used for the conversion and a difference of their drain currents is used as an output current. The two MOSFETs work complemetarily and realize a rail-to-rail input range. The output current is linear in any input voltage from the ground potential to a power-supply voltage. Two types of circuit configurations which realize the proposed concept are given. From the viewpoint of area efficiency and linearity the proposed circuit is superior to a voltage-to-current converter previously proposed by the authors, which uses a set of three MOSFETs to achieve a rail-to-rail voltage-to-current conversion . The operation principle of the proposed method is confirmed through HSPICE simulations.
In 1999, Araki et al. proposed a convertible limited verifier signature scheme. In this letter, we propose a universal forgery attack on their scheme. We show that any one can forge a valid signature of a user UA on an arbitrary message.
A parallel current-mode multilevel identifying circuit for flash memories is proposed. The sensing scheme based on the CMOS cross-coupled structure modified from the clamped bit-line sense amplifier achieves high speed and low power dissipation. The offset of the proposed sense amplifier due to mismatch is also reduced significantly. The circuit has been fabricated using 0.6 µm CMOS technology. The simulation and measurement indicate the sensing speed reaches 1 ns at 3 V supply voltage with average power consumption about 2 mW at 50 MHz.
This paper presents a framework for modeling and mixed-mode simulation of circuits/interconnects and electromagnetic (EM-) radiations. The proposed framework investigates the signal integrity in VLSI chips, packages and wiring boards at the GHz-band level, and verifies the electromagnetic interference (EMI) and the electromagnetic compatibility (EMC) of high-speed systems. In our framework, the frequency characteristics of interconnects and EM-radiations are extracted by the full-wave FDTD simulation. The macromodels of interconnects are synthesized as SPICE subcircuits, and the impulse responses of EM-radiations are stored in the database. Once the macromodels are synthesized, the circuit simulation with the consideration of EM-effects can be performed by using SPICE. The EM-field distributions can be also easily calculated by taking convolutions of pre-simulated EM impulse responses and the SPICE results.
Naotoshi ADACHI Shoji KASAHARA Yutaka TAKAHASHI
The ATM-ABR service category provides minimum cell rate (MCR) guarantees and robust connections even with insufficient network resources. Recently proposed rate-management algorithms for supporting multimedia applications over ABR mainly aim at minimizing the cell loss and delay. However, jitter is also an important element of QoS for multimedia applications. In this paper, we focus our attention on the arrival point of the critical cell corresponding to the end of data packet and propose a simple cell scheduling scheme for source node to reduce the jitter on application level over the ATM-ABR service class. In our proposed method, critical cells are delayed intentionally and the packet stream at application level becomes smooth. We verify the effectiveness of our proposed algorithm by an analytical model and simulation. From those results, we find that our proposed scheduling algorithm is effective in reducing the application level jitter even when the tagged cell stream is transmitted along the path with multiple nodes.
Kousuke KATAYAMA Atsushi IWATA
This paper proposes a high-resolution CMOS image sensor, which has Hadamard transform function. This Hadamard transform circuit consists of two base generators, an array of pixel circuits, and analog-to-digital converters. In spite of simple composition, a base generator outputs a variety of bases, a pixel circuit calculates a two-dimensional base from one-dimensional bases and outputs values to common line for current addition, and analog-to-digital converter converts current value to digital value and stabilize a common line voltage for elimination of parasitic capacitance. We simulated these circuit elements and optimized using SPICE. Basic operations of this Hadamard transform circuit are also confirmed by simulation. A 256 256 pixel test chip was designed in 4.73 mm 4.73 mm area with 0.35 µm CMOS technology. A fill factor of this chip is 42% and dynamic range is 55.6 [dB]. Functions of this chip are Hadamard transform, Harr transform, projection, obtaining center of gravity, and so on.
Kazuaki TSUKAKOSHI Toshiya KOBASHI Yukiyoshi KAMIO
We describe a DS-CDMA adaptive modulation system in which high-rate-data for moving pictures and LANs is transmitted to a high-speed traveling mobile terminal in the down-link. The transmission data rate is constant by changing the data-modulation level and the number of multiplex channels. We use computer simulation to evaluate the performance of the system using a RAKE receiver in a multipath-channel environment. For fdTslot 0.08, which is fading maximum Doppler frequency fd normalized by slot time Tslot, the following results are obtained. The average bit error rate (BER) of BER 1 10-3 necessary to ensure quality of high-rate-data transmission for moving pictures and LANs without error correction is attainable at low symbol-to-noise power ratio of ES/N0 14 dB and channel-use rate lower than 65%. The cell capacity of 17.2% is about 1.4 times that of the conventional system. Also, fdTslot=0.08 corresponds to the traveling speed of about 250 km/h at a carrier frequency of 8 GHz. Thus, the system enables high-rate-data and high-quality transmission needed for the moving pictures and LANs at mobile terminals with a traveling speed higher than 100 km/h at high carrier frequencies of the microwave band.
Hajime SHIBATA Soji MORI Nobuo FUJII
An automated synthesis for analog computational circuits in transistor-level configuration is presented. A cell-based structure is introduced to place moderate constraints on the MOSFET circuit topology. Even though each cell has a simple structure that consists of one current path with four transistors, common analog building blocks can be implemented using combinations of the cells. A genetic algorithm is applied to search circuit topologies and transistor sizes that satisfy given specifications. Synthesis capabilities are demonstrated through examples of three types of computational circuits; absolute value, squaring, and cubing functions by using computer simulations and real hardware.
Mahmoud MERIBOUT Masato MOTOMURA
The aim of this paper is to present a new cost estimation technique to synthesis hardware from high level circuit description. The scheduling and allocation processes are performed in alternative manner, while using realistic cost measurements models that account for Functional Unit (FU), registers, and multiplexers. This is an improvement over previous works, were most of them use very simple cost models that primarily focus on FU resources alone. These latest, however, are not accurate enough to allow effective design space exploration since the effects of storage and interconnect resources can indeed dominates the cost function. We tested our technique on several high-level synthesis benchmarks. The results indicate that the tool can generate near-optimal bus-based and multiplexer-based architectural models with lower number of registers and buses, while presenting high throughput.
Hiroshi NAGAMOCHI Shuji NAKAMURA Toshimasa ISHII
It is known that all minimum cuts in an edge-weighted undirected graph with n vertices and m edges can be represented by a cactus with O(n) vertices and edges, a connected graph in which each edge is contained in an exactly one cycle. In this paper, we show that such a cactus representation can be computed in O(mn+n2log n) time and O(m) space. This improves the previously best complexity of deterministic cactus construction algorithms, and matches with the time bound of the fastest deterministic algorithm for computing a single minimum cut.
Takao TSUKUTANI Masami HIGASHIMURA Yasutomo KINUGASA Yasuaki SUMI Yutaka FUKUI
This paper introduces a way to realize high-pass, band-stop and all-pass transfer functions using two-integrator loop structure consisting of loss-less and lossy integrators. The basic circuit configuration is constructed with five Operational Transconductance Amplifiers (OTAs) and two grounded capacitors. It is shown that the circuit can realize their circuit transfer functions by choosing the input terminals, and that the circuit parameters can also be independently set by the transconductance gains with the proportional block. Although the basic circuit configuration has been known, it seems that the feature for realizing the high-pass, the band-stop and the all-pass transfer functions makes the structure more attractive and useful. An example is given together with simulated results by PSPICE.
In this paper, parallelization methods for quantum circuits are studied, where parallelization of quantum circuits means to reconstruct a given quantum circuit to one which realizes the same quantum computation with a smaller depth, and it is based on using additional bits, called ancillae, each of which is initialized to be in a certain state. We propose parallelization methods in terms of the number of available ancillae, for three types of quantum circuits. The proposed parallelization methods are more general than previous one in the sense that the methods are applicable when the number of available ancillae is fixed arbitrarily. As consequences, for the three types of n-bit quantum circuits, we show new upper bounds of the number of ancillae for parallelizing to logarithmic depth, which are 1/log n of previous upper bounds.
Masataka TAKAMURA Yoshihide IGARASHI
We propose two simple algorithms based on bounded tickets for the mutual exclusion problem on the asynchronous single-writer/multi-reader shared memory model. These algorithms are modifications of the Bakery algorithm. An unattractive property of the Bakery algorithm is that the size of its shared memory is unbounded. Initially we design a provisional algorithm based on bounded tickets. It guarantees mutual exclusion in the case where a certain condition is satisfied. To remove the condition, we use an additional process that does not correspond to any user. The algorithm with the additional process is a lockout-free mutual exclusion algorithm on the asynchronous single-writer/multi-reader shared memory model. We then modify this algorithm to reduce the shared memory size with the cost of using another additional process. The maximum waiting time using each of the algorithms proposed in this paper is bounded by (n-1)c+O(nl), where n is the number of users, l is an upper bound on the time between two successive atomic steps, and c is an upper bound on the time that any user spends using the resource. The shared memory size needed by the first algorithm and the second algorithm are (n+1)(1+log (4n)) bits and n(1+log (4n-4))+2 bits, respectively.
In this paper, we consider the problem of multicasting a message in k-ary n-cubes under the store-and-forward model. The objective of the problem is to minimize the size of the resultant multicast tree by keeping the distance to each destination over the tree the same as the distance in the original graph. In the following, we first propose an algorithm that grows a multicast tree in a greedy manner, in the sense that for each intermediate vertex of the tree, the outgoing edges of the vertex are selected in a non-increasing order of the number of destinations that can use the edge in a shortest path to the destination. We then evaluate the goodness of the algorithm in terms of the worst case ratio of the size of the generated tree to the size of an optimal tree. It is proved that for any k 5 and n 6, the performnance ratio of the greedy algorithm is c kn - o(n) for some constant 1/12 c 1/2.
Minoru SANAGI Tomomichi KAGAWA Shigeji NOGI
A phased array behavior of a unilaterally coupled active antennas has been investigated. The active antenna is composed of a patch antenna and a parallel feedback type oscillator which can be coupled unilaterally to other oscillators without other nonreciprocal components. Numerical calculations of the reduced equations describing the behavior of the coupled oscillators array demonstrated that the phase differences between the oscillators can be varied up to about π/2 by giving the frequency changes from the injection locking frequency to the oscillators except of the first one. The oscillator mounted with the varactor diode for wide tuning range exhibited the property suitable for constructing the unilaterally coupled array. In the experiments at X-band, the electromagnetic wave radiated from the five element array was successfully scanned.
Futoshi KUROKI Motofumi YAMAGUCHI Yasujirou MINAMITANI Tsukasa YONEYAMA
Transmission characteristics of a high permittivity NRD guide were investigated. A preferable operating mode of the high permittivity NRD guide was newly identified and the wide bandwidth and low loss nature of the millimeter-wave region were observed. Moreover, a technique for construction of a millimeter-wave antenna was developed based on the high permittivity NRD guide. The novelty of the present technique lies in the use of a simple radiator, which consists of a tapered dielectric strip of simple structure which has good compatibility with millimeter wave integrated circuits. Since this radiator has a broad radiation pattern, a new type of antenna compatible with millimeter-wave integrated circuits for marine radar use was fabricated by locating the radiator at the focal point of a cylindrical parabolic reflector. Suitable beam patterns with half-power beam widths of 4in the azimuth plane and 38in the elevation plane can be obtained at 35 GHz.
Takehiro ITO Takao NISHIZEKI Xiao ZHOU
Let each vertex v of a graph G have a positive integer weight ω(v). Then a multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. A partial k-tree is a graph with tree-width bounded by a fixed constant k. This paper presents an algorithm which finds a multicoloring of any given partial k-tree G with the minimum number of colors. The computation time of the algorithm is bounded by a polynomial in the number of vertices and the maximum weight of vertices in G.
Eiju HIROWATARI Kouichi HIRATA Tetsuhiro MIYAHARA Setsuo ARIKAWA
This paper investigates the interaction of mind changes and anomalies for inductive inference of recursive real-valued functions. We show that the criteria for inductive inference of recursive real-valued functions by bounding the number of mind changes and anomalies preserve the same hierarchy as that of recursive functions, if the length of each anomaly as an interval is bounded. However, we also show that, without bounding it, the hierarchy of some criteria collapses. More precisely, while the class of recursive real-valued functions inferable in the limit allowing no more than one anomaly is properly contained in the class allowing just two anomalies, the latter class coincides with the class allowing arbitrary and bounded number of anomalies.
Mitsuyoshi KISHIHARA Isao OHTA Tadashi KAWAI Kuniyoshi YAMANE
Directional couplers with flat coupling are designed by using an asymmetrical coupled-HNRD-guide consisting of two HNRD guides of different cross sections arranged closely. First, propagation characteristics of the asymmetrical coupled-HNRD-guide are analyzed by the transverse resonance technique. Next, the whole directional couplers including tapered sections are designed from the S-parameters of the coupled HNRD guides derived from a superposition of the even-like and odd-like modes. Finally, the validity of the design procedure is confirmed by an em-simulator (HFSS).