Daniel FOGARAS Kokichi SUGIHARA
The paper presents a topology-oriented robust algorithm for the incremental construction of line arrangements. In order to achieve a robust implementation, the topological and geometrical computations are strictly separated. The topological part is proved to be reliable without any assumption on the accuracy of the geometrical part. A self-correcting property is introduced to minimize the effect of numerical errors. Computational experiments show how the self-correcting property works, and we also discuss some applications of the algorithm.
Yangseok JEONG Heungryeol YOU Dae-Hee YOUN Chungyong LEE
In positioning systems NLOS (Non-Line of Sight) errors always cause remarkable positive bias and directly increase range measurement errors. In this paper, a new method is proposed to calibrate NLOS errors in positioning systems by using the relationship between mean excess delay and delay spread measured at a mobile station. The computer simulations showed that the proposed calibration technique effectively reduces the positioning error caused by urban NLOS environment.
Shinya ISHIHARA Toshiaki MIYAZAKI Atsushi TAKAHARA Seiichiro TANI
This paper describes the concept of an adaptive network, that is, a network environment that can rapidly and autonomously adapt its behavior according to network conditions and traffic status. The user interface of the adaptive network can access any resource in the network as a memory-mapped I/O device, as if it were attached to the local bus of the user's PC. This network concept has several benefits. From the application development viewpoint, no network related programming is required, and applications do not have to be modified even if the network topologies and protocols are changed. Network maintenance and upgrading can be done anytime without having to worry about the application users, because the network itself is concealed from the applications. In addition, the reconfigurable hardware technology functions as an autonomous network control through the use of a lower-layer protocol. We developed a testbed that makes heterogeneous resources available to users and used it to demonstrate the feasibility of our concept by implementing and running some applications over it.
Haiyun JIANG Shotaro NISHIMURA Takao HINAMOTO
In this paper, we present a method to analyze the steady-state performance of a complex coefficient adaptive IIR notch filter which is useful for the rejection of multiple narrow-band interferences from broad-band signals in quadrature phase shift keying (QPSK) spread-spectrum communication systems. The adaptive notch filter based on the simplified gradient algorithm is considered. Analytical expressions have been developed for the conditional mean and variance of notch filter output. The signal-to-noise ratio improvement factor is also obtained from which the validity of the use of the notch filter can be concluded. Finally, the results of computer simulations are shown which confirm the theoretical predictions.
This letter is concerned with a performance analysis of a VPG DS/CDMA acquisition system employing a reference filter based on the statistical evaluation of the decision threshold. The probabilities of detection and false alarm are derived, and the mean acquisition time is evaluated as a measure of the system performance. From the results, it is shown that in the performance analysis of the parallel acquisition system with reference filtering, the statistical evaluation of the decision threshold seems more appropriate than the approximation of the decision threshold adopted in other acquisition schemes.
Coloring problem is a well-known combinatorial optimization problem of graphs. This paper considers H-coloring problems, which are coloring problems with restrictions such that some pairs of colors can not be used for adjacent vertices. The restriction of adjacent colors can be represented by a graph H, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices can be used for adjacent vertices. Especially, H-coloring problem with a complete graph H of order k is equivalent to the traditional k-coloring problem. This paper presents sufficient conditions such that H-coloring problem can be reduced to an H-coloring problem, where H is a subgraph of H. And it shows a hierarchy about classes of H-colorable graphs for any complement graph H of a cycle of order odd n 5.
Koji CHIDA Shigenori UCHIYAMA Taiichi SAITO
Since the invention of the RSA scheme, a lot of public-key encryption and signature schemes based on the intractability of integer factoring have been proposed. Most employ integers of the form N = p q, such as the RSA scheme, but some employ integers of the form N = pr q. It has been reported that RSA decryption speed can be greatly improved by using N = pr q integers for large r. On the other hand, Boneh et al. proposed a novel integer factoring method for integers such as N = pr q for large r. This factoring algorithm, the so-called Lattice Factoring Method, is based on the LLL-algorithm. This paper proposes a new method for factoring integers of the form N = pr q for large r and gives a new characterization of r such that factoring integers N = pr q is easier. More precisely, the proposed method strongly depends on the size and smoothness of the exponent, r. The theoretical consideration of and implementation of our method presented in this paper show that if r satisfies a certain condition our method is faster than both Elliptic Curve Method and Lattice Factoring Method. In particular, the theoretical consideration in this paper mainly employs the techniques described in the excellent paper by Adleman, Pomerance and Rumely that addresses primality testing.
Naris RANGSINOPPAMAS Tanun JARUVITAYAKOVIT Prasit PRAPINMONGKOLKARN
In this paper, we propose a new consolidation algorithm called the Selective Backward Resource Management (BRM) cell Feedback (SBF) algorithm. It achieves a fast response and low consolidation noise by selectively forwarding BRM cell from the most congested branch to the source instead of waiting from all branches. Mathematical models are derived to quantitatively characterize the performance, i.e. the response time and ACR of the source, of SBF and previously proposed algorithms. The interoperation of consolidation algorithms in point-to-multipoint available bit rate (ABR) is investigated. We address response time, consolidation noise and the effect of asymmetrical round trip delay (RTD) from branch point to destinations aspects. All combinations of four different consolidation algorithms are interoperated in both local/metropolitan area network (LAN/MAN) and wide area network (WAN) configuration. By a simulation method, we found that the consolidation algorithm used at the uppermost stream branch point, especially in WAN configuration, plays an important role in determining the performance of the network. However, consolidation algorithm used at the lower stream branch point affects the network performance insignificantly. Hence, in order to achieve a good and effective performance of the consolidation algorithms interoperated network, a fast response with low consolidation noise algorithm should be used at the uppermost stream branch point and a simple and easy to implement algorithm should be used at the lower stream branch point.
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.
This paper considers combining receptions with multiple receive antennas for space time coded MPSK signals over correlated Rayleigh fading channels. For the system with dual-antenna at receiver, a new transform is proposed, which can convert the correlated fading signals into uncorrelated ones. With the results obtained by using the proposed transform, the equivalent selective combining (SC) reception and maximum likelihood (ML) reception are presented. Theoretical analysis shows that ML reception has better performance than SC reception in terms of bit error rate. For the system with triple antenna at receiver, the simulation results are presented by using Monte Carlo method. All the results show that compared to using a receive antenna, a considerable signal to noise ratio gain can be obtained by using multiple receive antennas when the correlation coefficients among the receive antennas is not too high.
Hideki SASAKI Takashi HARADA Toshihide KURIYAMA
This paper presents a new decoupling circuit for suppressing radiated emissions due to power plane resonance in multilayer printed circuit boards (PCBs). This circuit is based on transmission line theory, and consists of two decoupling capacitors and one power trace. The two capacitors, one mounted on the power pin of an IC and the other mounted on the common power distribution bus in a board, are connected through the power trace. The characteristic impedance of the trace is much higher than the impedance of the capacitors. In addition, the length of the trace between the capacitors is less than 1/4 the effective wavelength for high frequency (e.g., 1 GHz). Tests we performed on simple PCBs confirm that our decoupling circuit suppresses radiated emissions due to power plane resonance.
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.
Makoto SYUTO Eriko SATAKE Koichi TANNO Okihiko ISHIZUKA
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.
In this paper, we propose a new approach to the adaptive MLSE receiver, which is based on the delay estimation of the paths in the fading channel. The path delays are estimated by using the known training sequence, and based on this estimation the proposed MLSE tracks not the T-spaced equivalent channel but the variations of each path in the frequency-selective channel directly. It will be shown through computer simulations that the proposed MLSE can improve the performance of the conventional MLSE receivers, when the number of paths is small.
We consider diagnosability of butterfly networks under the comparison approach proposed by Maeng and Malek. Sengupta and Dahbura discussed characterization of diagnosable systems under the comparison approach, and designed a polynomial time algorithm to identify the faulty processors. However, for a general system, it is not algorithmically easy to determine its diagnosability. This paper proposes two comparison schemes for generating syndromes on butterfly networks, and determine the diagnosability of the network.
A base model should be transmitted first in progressive transmission schemes, and its transmission delay dominates initiation time for rendering. To reduce the initiation time, we restructure the base model to transmit visible vertices and triangles for some specific viewpoints first, and therefore clients can start rendering when parts of model file are received. Simulation results show that only 37.4% - 51.3% of model file are required to start rendering, and hence the initiation time is significantly reduced.
Chien-Hsing WU Chien-Ming WU Ming-Der SHIEH Yin-Tsung HWANG
In this paper, we present the division algorithm (DA) for the computation of b=c/a over GF(2m) in two aspects. First, we derive a new formulation for the discrete-time Wiener-Hopf equation (DTWHE) Ab = c in GF(2) over any basis. Symmetry of the matrix A is observed on some special bases and a three-step procedure is developed to solve the symmetric DTWHE. Secondly, we extend a variant of Stein's binary algorithm and propose a novel iterative division algorithm EB*. Owing to its structural simplicity, this algorithm can be mapped onto a systolic array with high speed and low area complexity.
Hiroyuki KAWAI Yoshitsugu INOUE Junko KOBARA Robert STREITENBERGER Hiroaki SUZUKI Hiroyasu NEGISHI Masatoshi KAMEYAMA Kazunari INOUE Yasutaka HORIBA Kazuyasu FUJISHIMA
This paper describes a kind of 3D graphics geometry processor architecture for high performance/cost 3D graphics, its application to a real chip, and the results of performance evaluation. In order to establish the high speed geometry processing, dedicated hardware is introduced for accelerating special operations, such as power calculations, clip tests, and program address generation. The dedicated hardware consists of a modified floating-point multiplier in a four-parallel SIMD processing core, a clip test unit, and an internal program address generation scheme optimized to geometry processing mode. Special instructions corresponding to the dedicated schemes are also defined and added. The parallelism of the SIMD core is adjusted to a geometry data structure. Employing dedicated hardware and software significantly accelerates these complicated operations deriving from geometry algorithms. The collaboration of the hardware design and the software design considerably reduces instruction step counts for complex processing. Two kinds of program are dealt with in the proposed architecture. One is a special case program containing few conditional jump instructions, and the other is a general case program combining many program routines. The proposed program address generation scheme provides the automatic selection of a program optimized to each geometry processing mode. By this program address generation scheme and the program types, the frequency of the conditional jump operations, that usually disturb a pipeline operation, are minimized under practical use. Additionally, the programmable design and this program address generation scheme facilitate the load balancing of the geometry calculations with the CPU. A programmable geometry processor was fabricated by using 0.35 µm CMOS process as an application of this architecture. One point three million transistors are integrated in a 11.84 12.07 mm2 die. The increase of the gate counts for all the dedicated hardware is a total of 24 K gates and is approximately only a 7.4% increase of the total gate count. This chip operates at 150 MHz, and achieves the processing performance of 5.8 M vertex/sec. The result shows that the proposed programmable architecture (ESIMD: Enhanced SIMD) is 2.3 times more cost effective than a programmable geometry LSI reported previously.
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.
In this paper, a novel type of neural networks called grey neural network (GNN) is proposed and applied to improve short term load forecasting (STLF) performance. This work is motivated by the following observations: First, the forecasting performance of neural network is affected by the randomness in STLF data. That is, poor performance results from large randomness and vice versa. Second, the grey first-order accumulated generating operation (1-AGO) is reported having randomness reduction property. By the observations, the GNN is proposed and expected to have better STLF performance. The GNN consists of grey 1-AGO, the piecewise linear neural network (PLNN), and grey first-order inverse accumulated generating operation (1-IAGO). Given a set of STLF data, the data is first converted by grey 1-AGO and then is put into the PLNN to perform forecasting. Finally, the predicted load of GNN is obtained through grey 1-IAGO. For comparison, the original STLF data is also put into the PLNN itself. With identical training conditions, the simulation results indicate that with various network structures the GNN, as expected, outperforms the PLNN itself in terms of mean squared error.