Suguru AMITANI Toshinori YAMADA Shuichi UENO
It is a fundamental problem to construct a virtual path layout minimizing the hop number as a function of the congestion for a communication network. It is known that we can construct a virtual path layout with asymptotically optimal hop number for a mesh of trees network, butterfly network, cube-connected-cycles network, de Bruijn network, shuffle-exchange network, and complete binary tree network. The paper shows a virtual path layout with minimum hop number for a complete binary tree network. A generalization to complete k-ary tree networks is also mentioned.
Martin T. HILL Antonio CANTONI
Recent advances make it possible to mitigate a number of drawbacks of conventional phase locked loops. These advances permit the design of phase tracking system with much improved characteristics that are sought after in modern communication system applications. A new phase tracking system is outlined which reduces the effects of VCO phase noise to an insignificant level. This fact permits extremely narrow bandwidth phase tracking systems to be realized, even when a VCO with poor phase noise characteristics is employed. The improvement in performance over conventional phase locked loops is analyzed. The new phase tracking system also has other benefits such as precise centre frequency and elimination of peaking in the transfer function. To implement the phase tracking system requires a frequency measurement. We outline a new highly integrated frequency measurement method suitable for narrow bandwidth applications. Experimental results from a prototype confirms theoretical results.
Independent component analysis (ICA) is a new method of extracting independent components from multivariate data. It can be applied to various fields such as vision and auditory signal analysis, communication systems, and biomedical and brain engineering. There have been proposed a number of algorithms. The present article shows that most of them use estimating functions from the statistical point of view, and give a unified theory, based on information geometry, to elucidate the efficiency and stability of the algorithms. This gives new efficient adaptive algorithms useful for various problems.
Ken'ichi TAJIMA Yoshihiko IMAI Yousuke KANAGAWA Kenji ITOH Yoji ISOTA Osami ISHIDA
This letter presents a low spurious frequency setting algorithm for a triple tuned type PLL synthesizer driven by a DDS. The triple tuned PLL synthesizer is based on a single PLL configuration with two variable frequency dividers. The DDS is employed for a reference source of the PLL. The proposed algorithm determines appropriate frequency tuning values of the DDS frequency and the division ratios of two frequency dividers. The division ratios are selected to achieve a desired output frequency while the low spurious condition of the DDS has been maintained. A 5 to 10 GHz synthesizer with frequency step of 500 kHz demonstrated spurious level below -46 dBc with improvement of 13 dB.
This paper presents some new protocols for (M+1)st-price auction, a style of auction in which the highest M bidders win and pay a uniform price, determined by the (M+1)st price. A set of distributed servers collaborates to resolve the (M+1)st price without revealing any information in terms of bids including the winners' bids. A new trick to jointly and securely compute the highest value as a degree of distributed polynomials is introduced. The building block requires just one round for bidders to cast bids and one round for auctioneers to determine the winners.
This paper presents a high-throughput VLSI architecture for LZFG data compression and decompression. To reduce the hardware cost and maintain both of the interior node and the leaf node numbering systems, we modify the original LZFG data structure. Compared to the original LZFG tree, the number of characters in our modified LZFG data structure must be greater than one to establish one new interior node down the root node into the new node. Meanwhile, this architecture employs a series of encoding cells with content addressable memory (CAM) to search the longest match and maintain the LZFG data tree during the encoding and decoding processes. By using the parallel design, the compressor and decompressor can keep a constant high bit rate to encode and decode one character per clock cycle, that is, it is directly proportional to the operating clock rate, but independent of the sizes of the word dictionary and the input file. By using 0.25 µm CMOS silicon technology, the operating clock rate can be as high as 85 MHz. Some untargeted encoding cells will be disabled to reduce the power consumption during the comparison operation. Therefore, this architecture can be easily applied in the high-speed real-time communication and data storage systems.
Fabio ZEPPARELLI Luca ROSELLI Francesco AMBROSI Roberto SORRENTINO Pier FACCIN Andrea CASINI
To the aim of developing industrializable low-cost electronic techniques for the compensation of non-linearities in Radio-over-Fibre networks, a semiconductor laser circuit model and a predistortion circuit configuration have been implemented and simulated. The CAD procedure illustrated indicates the steps to obtain a broadband compensation (0.4-2 GHz) of both second- and third-order distortions.
Shinya KURIKI Hiroshi OYAMA Amane HAYASHI Satoru HIRANO Tomoaki WASHIO Mizushi MATSUDA Koichi YOKOSAWA
We describe here development of a multichannel high-Tc SQUID magnetometer system for measurement of cardiac magnetic fields, aiming at future application of diagnosis of heart diseases. Two types of direct-coupled SQUID magnetometers were fabricated and used: single pickup coil magnetometer having flux dams to suppress the shielding current that would induce flux penetration and the consequent low-frequency noise, and double pickup coil magnetometer having no grain boundary junctions and flux dams on the pickup coil. The superconducting film of both the magnetometers had holes and slots, leaving 5 µm-wide strip lines, to suppress trapping and penetration of magnetic flux vortices in environmental fields. We studied different schemes of active shielding to reinforce the efficiency of field-attenuation of magnetically shielded room (MSR). A feedback-type compensation using a normal detection coil wound around the wall of MSR and a selective cancellation of 50 Hz noise by means of adaptive filter were developed. Such combination of passive and active shielding, based on the use of simple MSR, would be suitable in a practical low-cost magnetometer system for clinical MCG examination. We fabricated a liquid nitrogen cryostat that could contain up to 20 magnetometer-capsules at 4 cm separation in a flat bottom, with a distance of 16 mm between the air and liquid nitrogen. The cryostat was set in a gantry, which had rotational, vertical and horizontal freedoms of movement, in a moderate-shielding MSR that was combined with the developed active shielding. Measurements of MCG were performed for normal subject using eight magnetometers operating simultaneously.
Roberto Y. OMAKI Gen FUJITA Takao ONOYE Isao SHIRAKAWA
A wavelet based algorithm for scalable video compression is described, with the main focus put on memory bandwidth reduction and efficient VLSI implementation. The proposed algorithm adopts a modified 2-D subband decomposition scheme in conjunction with a partial zerotree search for efficient Embedded Zerotree Wavelet coding. The experiment with the performance of the proposed algorithm in comparison with that of conventional DWT, MPEG-2, and JPEG demonstrates that the image quality of the proposed algorithm is consistently superior to that of JPEG, and our scheme can even outperform MPEG-2 in some cases, although it does not exploit the inter-frame redundancy. In spite of the performance inferiority to the conventional DWT, the proposed algorithm attains significant reduction of DWT memory requirements, enhancing a reasonable balance between implementation cost and image quality.
Toshinori SUEYOSHI Masahiro IIDA
Recent DSP applications have many significant issues such as higher system performance, lower power consumption, higher design flexibility, faster time-to-market, and so on. Neither a conventional ASIC nor a conventional DSP can necessarily satisfy all the requirements at once nowadays. Therefore, an alternate for DSP applications will be needed to complement the drawbacks of ASICs and DSPs. This paper introduces a new computing paradigm called configurable computing or reconfigurable computing, which has more potential in terms of performance and flexibility. Conventional silicon platforms will not satisfy the conflicting demands of standard products and customization. However, silicon platforms such as FPGAs for configurable or reconfigurable computing are standardized in manufacturing but customized in application. This paper also presents a brief survey of the existing silicon platforms that support configuration or reconfiguration in the application domain of digital signal processing such as image processing, communication processing, audio and speech processing. Finally, we show some promising reconfigurable architectures for the digital signal processing and discuss the future of reconfigurable computing.
In the field of computer graphics (CG), some adaptive methods have been proposed in order to make CG images more real in relatively low computational cost. As one of such adaptive methods, in this paper, an adaptive method will be proposed for detection of edges and approximation of surfaces in the use of the so-called automatic differentiation. In the proposed method a CG image with high quality can be generated in suitable computational cost. In this paper, three cases will be considered. The first is an adaptive distributed ray tracing which can adaptively generate anti-aliased CG images in suitable computational cost. The second is a high quality triangular meshing, which guarantees accuracy of the generated meshes according to shape of given surface in suitable computational cost. The last case is used in the so-called radiosity method.
Kazufumi HATTORI Yuuji TAKAMATSU Takao WAHO
A flash analog-to-digital converter (ADC) that uses resonant-tunneling complex gates is proposed. The ternary quantizers, consisting of monostable-to-multistable transition logic (MML) circuits, convert the analog input signal into the ternary thermometer code. This code is then converted into the binary Gray-code output by a multiple-valued multiple-input monostable-bistable transition logic element (M2-MOBILE). By assuming InP-based resonant-tunneling diode (RTD) and heterojunction field-effect transistor technology, we have carried out SPICE simulation that demonstrates a 4-bit, 10-GS/s ADC operation. The input bandwidth, defined as a frequency at which the effective number of bit decreases by 0.5 LSB, was also estimated to be 500 MHz. Compact circuit configuration, which is due to the combination of MML and M2-MOBILE, reduces the device count and power dissipation by a factor of two compared with previous RTD-based ADCs.
With increased size and issue-width, instruction issue queue becomes one of the most energy consuming units in today's superscalar microprocessors. This paper presents a novel architectural technique to reduce energy dissipation of adaptive issue queue, whose functionality is dynamically adjusted at runtime to match the changing computational demands of instruction stream. In contrast to existing schemes, the technique exploits a new freedom in queue design, namely the voltage per access. Since loading capacitance operated in the adaptive queue varies in time, the clock cycle budget becomes inefficiently exploited. We propose to trade-off the unused cycle time with supply voltage, lowering the voltage level when the queue functionality is reduced and increasing it with the activation of resources in the queue. Experiments show that the approach can save up to 39% of the issue queue energy without large performance and area overhead.
Young I. SON Hyungbo SHIM Kyoung-cheol PARK Jin H. SEO
We present a state-space approach to the problem of designing a parallel feedforward compensator (PFC), which has the same dimension of the input i.e. input-dimensional, for a class of non-square linear systems such that the closed-loop system is strictly passive. For a non-minimum phase system or a system with high relative degree, passification of the system cannot be achieved by any other methodologies except by using a PFC. In our scheme, we first determine a squaring gain matrix and an additional dynamics that is connected to the system in a feedforward way, then a static passifying control law is designed. Consequently, the actual feedback controller will be the static control law combined with the feedforward dynamics. Necessary and sufficient conditions for the existence of the PFC are given by the static output feedback formulation, which enables to utilize linear matrix inequality (LMI). Since the proposed PFC is input-dimensional, our design procedure can be viewed as a solution to the low-order dynamic output feedback control problem in the literature. The effectiveness of the proposed method is illustrated by some numerical examples.
Rong-Long WANG Zheng TANG Qi-Ping CAO
A near-optimum parallel algorithm for bipartite subgraph problem using gradient ascent learning algorithm of the Hopfield neural networks is presented. This parallel algorithm, uses the Hopfield neural network updating to get a near-maximum bipartite subgraph and then performs gradient ascent learning on the Hopfield network to help the network escape from the state of the near-maximum bipartite subgraph until the state of the maximum bipartite subgraph or better one is obtained. A large number of instances have been simulated to verify the proposed algorithm, with the simulation result showing that our algorithm finds the solution quality is superior to that of best existing parallel algorithm. We also test the proposed algorithm on maximum cut problem. The simulation results also show the effectiveness of this algorithm.
Tsunehiro YOSHINAGA Katsushi INOUE
This paper investigates the accepting powers of one-way alternating and deterministic multi-counter automata operating in realtime. We partially solve the open problem posed in [4], and show that for each k1, there is a language accepted by a realtime one-way deterministic (k+3)-counter automaton, but not accepted by any realtime one-way alternating k-counter automaton.
Hiroshi NAGAHASHI Mohamed IMINE
This paper develops a simple algorithm for calculating a polynomial curve or surface in a parallel way. The number of arithmetic operations and the necessary time for the calculation are evaluated in terms of polynomial degree and resolution of a curve and the number of processors used. We made some comparisons between our method and a conventional method for generating polynomial curves and surfaces, especially in computation time and approximation error due to the reduction of the polynomial degree. It is shown that our method can perform fast calculation within tolerable error.
SungHun NAM IlYoung CHUNG SungHo CHO ChongSun HWANG
The stateless-based cache invalidation schemes for wireless environments can be categorized into either asynchronous or synchronous cache invalidation according to the broadcasting way of invalidation report. However, if the asynchronous cache invalidation scheme attempts to support local processing of read-only transaction, a critical problem may occur; the asynchronous invalidation reports provide no guarantee of waiting time for mobile transactions requesting commit. To solve this problem, the server in our approaches broadcasts two kind of messages, asynchronous invalidation report to reduce transaction latency and periodic guide message to avoid the uncertainty of waiting time for the next invalidation report. This paper presents a simulation-based analysis on the performance of the suggesting algorithms. The simulation experiments show that the local processing algorithms of read-only transaction based on asynchronous cache invalidation scheme get better response time than the algorithm based on synchronous cache invalidation scheme.
Masaki NAKANISHI Takao INDOH Kiyoharu HAMAGUCHI Toshinobu KASHIWABARA
The class NQP was proposed as the class of problems that are solvable by non-deterministic quantum Turing machines in polynomial time. In this paper, we introduce non-deterministic quantum finite automata in which the same non-determinism as in non-deterministic quantum Turing machines is applied. We compare non-deterministic quantum finite automata with the classical counterparts, and show that (unlike the case of classical finite automata) the class of languages recognizable by non-deterministic quantum finite automata properly contains the class of all regular languages.
Kwang-Deok SEO Kook-Yeol YOO Jae-Kyoon KIM
Quantization is an essential step which leads to compression in discrete cosine transform (DCT) domain. In this paper, we show how a statistically non-optimal uniform quantizer can be improved by employing an efficient reconstruction method. For this purpose, we estimate the probability distribution function (PDF) of original DCT coefficients in a decoder. By applying the estimated PDF into the reconstruction process, the dequantization distortion can be reduced. The proposed method can be used practically in any applications where uniform quantizers are used. In particular, it can be used for the quantization scheme of the JPEG and MPEG coding standards.