While spatial reuse in a high-speed ring increases the throughput performance, it leads to a fairness problem in distributing the network bandwidth among distinct nodes. To alleviate this problem, fairness control algorithms based on a packet window have been developed. Under these algorithms, satisfied nodes are forced to pass empty slots to starved downstream nodes until their windows are refilled by a reset signal. This regulation incurs a bandwidth waste corresponding to the travel distance of those empty slots. In this paper, a waste-free fairness control method based on a two-layer window composed of the cycle and packet windows is developed. Using the proposed method, packets allocated to multiple fairness cycles are simultaneously transferred and, in consequence, the otherwise wasted bandwidth can be reused to carry, in advance, packets allocated to future fairness cycles. This method is applied to two typical ring protocols with only the packet window, ATMR and MetaRing, and their performances are investigated. The simulation results show that the cycle window is very effective to improve the performance of the ATMR and MetaRing protocols.
Do-Jong KIM Yong-Woon PARK Dong-Jo PARK
The structural characteristics of clusters are investigated in the partitioning process. Two partition functions, which show opposite properties around the optimal cluster number, are found and a new cluster validity index is presented based on the combination of these functions. Some properties of the index function are discussed and numerical examples are presented.
Shigeki OBOTE Yasuaki SUMI Yoshio ITOH Yutaka FUKUI Masaki KOBAYASHI
Recently, in the modem, the spread spectrum communication system and the software radio, Digital Signal Processor type Squaring Loop (DSP-squaring-loop) is employed in the demodulation of Binary Phase Shift Keying (BPSK) signal. The DSP-squaring-loop extracts the carrier signal that is used for the coherent detection. However, in case the Signal to Noise Ratio (SNR) is low, the DSP-Phase Locked Loop (DSP-PLL) can not pull in the frequency offset and the phase offset. In this paper, we propose a DSP-squaring-loop that is robust against noise and which uses the adaptive notch filter type frequency estimator and the adaptive Band Pass Filter (BPF). The proposed method can extract the carrier signal in the low SNR environment. The effectiveness of the proposed method is confirmed by the computer simulation results.
This paper presents adaptive image enhancement algorithms which enhance hidden signals in the pictures and describes their implementation for real-time video signals. An image enhancement algorithm proposed by T. Peli and J. S. Lim is extended for application to video signals. A fast implementation algorithm is provided with parallel implementation. The proposed algorithms are shown to be realized in real-time on 200 MHz microprocessors with multimedia extensions for 720 480 (pixels) 30 frames/sec video signals.
Trong-Yen LEE Pao-Ann HSIUNG Sao-Jie CHEN
A novel Multi-Level Partitioning (MLP) technique taking into account real-world constraints for hardware-software partitioning in Distributed Embedded Multiprocessor Systems (DEMS) is proposed. This MLP algorithm uses a gradient metric based on hardware-software cost and performance as the core metric for selection of optimal partitions and consists of three nested levels. The innermost level is a simple binary search that allows quick evaluations of a large number of possible partitions. The middle level iterates over different possible allocations of processors (that execute software) to subsystems. The outermost level iterates over the number of processors and the hardware cost range. Heuristics are applied to each level to avoid the expensive exhaustive search. The application of MLP as a recently purposed Distributed Embedded System Codesign (DESC) methodology shows its feasibility. Comparisons between real-world examples partitioned using MLP and using other existing techniques demonstrate contrasting strengths of MLP. Sharing, clustering, and hierarchical system model are some important features of MLP, which contribute towards producing more optimal partition results.
Hon-Wai CHU Chi-Chung CHEUNG Danny H. K. TSANG
It is always difficult to monitor stringent cell loss ratio (CLR), e.g. 10-9, in asynchronous transfer mode (ATM) networks, because its measurement period is too long for real-time measurement. In this paper, we propose new performance monitoring mechanisms for stringent CLR. We consider virtual ATM switches whose resources are much smaller than the real system and thus much higher CLRs will be obtained within a relatively short measurement period. By applying some regression methods in the CLRs obtained from the virtual system, we can estimate the actual CLR of the real system quite accurately and our performance monitoring mechanisms will be operated based on the estimation. Through the numerical examples, our mechanisms are not only more accurate than the traditional methods, but also have shorter measurement periods compared with direct measurement.
Yoshiyuki SHINKAWA Masao J. MATSUMOTO
It is one of the difficulties in enterprise modeling that we must deal with many fragmented pieces of knowledge provided by various domain-experts, which are usually based on mutually different viewpoints of them. This paper presents a formal approach to integrate those pieces into enterprise-wide model units using Rough Set Theory (RST). We focus on business processes in order to recognize and identify the constituents or units of enterprise models, which would compose the model expressing the various aspects of the enterprise. We defined five model unit types of "resource," "organization," "task," "function," and "behavior. " The first three types represent the static aspect of the enterprise, whereas the last two types represent the dynamic aspect of it. Those units are initially elicited from each domain-expert as his/her own individual model units, then they are integrated into enterprise-wide units using RST. Our approach is methodology-free, and any methodologies can include it in their early stage to identify what composes the enterprise.
Chyi-Ren DOW Cheng-Min LIN Da-Wei FAN
To enhance throughput and reuse bandwidth, clustering techniques can effectively manage nodes in multi-hop wireless networks. However, in such networks, hidden terminal interference degrades the system performance and increases the average packet delay time. Therefore, this work presents novel two-level cluster-based code assignment techniques to resolve the hidden terminal problems. At the low level, five basic and an optimized intra-cluster code assignment schemes are developed to calculate the number of codes used in each cluster. At the high level, two inter-cluster code assignment schemes (coarse-grained and fine-grained controls) are proposed to obtain the minimal number of code sets. The merits of our schemes include low execution time, low probability of code re-assignment, and low overhead. Furthermore, the proposed schemes allow us to regionally update orthogonal codes when the topology varies. Experimental results demonstrate that the proposed schemes outperform conventional techniques. Among the five basic intra-cluster code assignment schemes, the ordering criteria of increasing number of one-hop neighbors is the best in terms of the number of orthogonal codes to avoid hidden terminal interference. The optimized intra-cluster code assignment scheme generally obtains fewer orthogonal codes than other schemes. For inter-cluster code assignment schemes, the coarse-grained control has a lower code allocation time. However, the fine-grained control requires fewer orthogonal codes.
In this paper, we attempt to construct practical secret sharing schemes, which scheme has smaller share size and can detect cheating with high probability. We define two secure ramp schemes, secure ramp scheme and strongly secure ramp scheme. Then, we propose two constructions of secure ramp scheme. These schemes both have small share size and the cheating can be detected with high probability. So, they are practical secret sharing schemes.
Shuichi TAKANO Kiyoshi TANAKA Tatsuo SUGIMURA
This paper presents a new data hiding scheme under fractal image generation via Fourier filtering method for Computer Graphics (CG) applications. The data hiding operations are achieved in the frequency domain and a method similar to QAM used in digital communication is introduced for efficient embedding in order to explore both phase and amplitude components simultaneously. Consequently, this scheme enables us not only to generate a natural terrain surface without loss of fractalness analogous to the conventional scheme, but also to embed larger amounts of data into an image depending on the fractal dimension. This scheme ensures the correct decoding of the embedded data under lossy data compression such as JPEG by controlling the quantization exponent used in the embedding process.
Kunihiko MIYAZAKI Kazuo TAKARAGI
This paper describes an efficient k-out-of-n threshold digital signature scheme for a smart card based system where a signer uses multiple cards so that the signature can be issued in a dependable manner. The main feature of our method is that it does not require a secret communication path among these cards in the signature issuing protocol, and that it requires low communication and computational complexity. Former is an advantage under the current export control regulation which makes hard to export more than 56-bit cipher techniques, and latter is advantage over so-called robust signature.
Shin'ichiro MATSUO Hikaru MORITA
As one form of electronic commerce, the scale of online trading in stocks is rapidly growing. Although brokers lie between the customers as trustees in the current market, retrenchment of broker seems inevitable. This paper proposes a protocol that allows trading to proceed with only the market and the customers. We show the required characteristics for this type of trading at first. Next, to fulfil these characteristics, we apply an electronic auction protocol and digital signatures. The result is a trading protocol with security equivalent to that the current trading system.
In this paper, we propose a mathematical model for one-dimensional finite linear cellular automata and show connections between our model and the classical one. We then demonstrate, through some examples, that our model is a useful tool for analyzing one-dimensional finite linear cellular automata. We also extend this model to the D-dimensional case and give an algebraic characterization for it.
Shigenori UCHIYAMA Naoki KANAYAMA
Recently, Boneh et al. proposed an interesting algorithm for factoring integers, the so-called LFM (Lattice Factoring Method). It is based on the techniques of Coppersmith and Howgrave-Graham, namely, it cleverly employs the LLL-algorithm. The LFM is for integers of the form N = pr q, and is very effective for large r. That is, it runs in polynomial time in log N when r is on the order of log p. We note that for small r, e.g. N =pq, p2q, it is an exponential time algorithm in log N. In this paper, we propose a method for speeding up the LFM from a practical viewpoint. Also, theoretical considerations and experimental results are provided that show that the proposed algorithm offers shorter runing time than the original LFM.
Suguru ARIMOTO Pham Thuc Anh NGUYEN
This paper is concerned with analysis of nonlinear dynamics under geometric constraints that express pinching motions of a pair of multi-degrees of freedom fingers with soft tips. The dynamics of such a pair of soft fingers can be expressed by a set of complicated nonlinear differential equations with algebraic constraints, even if the motion is constrained in a plane. However, it is shown from the passivity analysis that dynamic stable grasping (pinching) can be realized by means of a feedforward input of desired internal force with coefficients composed of elements of Jacobian matrices plus a feedback of the difference between moments of rotation exerted at both sides of the object. It is shown in the case of a pair of 2 d.o.f. and 3 d.o.f. fingers (corresponding to a pair of thumb and index fingers) that a principle of linear superposition is applicable to design of additional feedback signals for controlling simultaneously the posture (rotational angle) and position of the mass center of the object, though the dynamics are nonlinear. A sufficient condition for applicability of the principle of superposition is discussed and given as a condition for unique stationary resolution of the overall motion to elementary motions (stable grasping, rotation control, x and y coordinates control). The principle implies that a skilled motion can be resolved into some of elementary motions which human can learn separately and independently.
Tsunehiro YOSHINAGA Katsushi INOUE
This paper investigates a hierarchical property based on the number of inkdots in the accepting powers of sublogarithmic space-bounded multi-inkdot two-way alternating Turing machines with only universal states. For each k1 and any function L(n), let strong-2UTMk(L(n)) (weak-2UTMk(L(n))) be the class of sets accepted by strongly (weakly) L(n) space-bounded k-inkdot two-way alternating Turing machines with only universal states. We show that for each k1, strong-2UTMk+1(log log n) - weak-2UTMk(o(log n)) Ø.
Hiroki KOGA Mitsugu IWAMOTO Hirosuke YAMAMOTO
This paper proposes a new construction of the visual secret sharing scheme for the (n,n)-threshold access structure applicable to color images. The construction uses matrices with n rows that can be identified with homogeneous polynomials of degree n. It is shown that, if we find a set of homogeneous polynomials of degree n satisfying a certain system of simultaneous partial differential equations, we can construct a visual secret sharing scheme for the (n,n)-threshold access structure by using the matrices corresponding to the homogeneous polynomials. The construction is easily extended to the cases of the (t,n)-threshold access structure and more general access structures.
Kenji KITAYAMA Yoshio YAMAGUCHI Jian YANG Hiroyoshi YAMADA
The Sinclair scattering matrix is defined in a fixed radar range. If a radar target extends in the range direction, the reflected signal or the compound scattering matrix will undergo interaction of multiple reflections. Since scattering matrix is subject to target parameters such as shape, size, orientation, material, and radar parameters as frequency, polarization, and incidence angle, it is difficult to specify a representative scattering matrix of a general target. Therefore we choose the simplest target, wire, and its scattering matrix to examine the effect of targets aligned in the range direction with respect to the compound scattering matrix. First, we present a simple formula for the compound scattering matrix of wires with the phase difference due to spacing. Then, we employed the FDTD method to examine the scattering phenomena, changing the spacing in the range direction. The FDTD result reveals that two wires can become sphere (plate) and dihedral corner reflector (diplane) component generators; and that four wires can become a good helix component generator. These phenomena are verified with a laboratory measurement. From the result, the target decomposition should be carefully carried out in terms of range. If a range resolution of a radar is not high enough, the scattering matrix of the desired target may be affected by the targets behind.
This paper proposes an algorithm that adaptively estimates time-varying noise variance used in Kalman filtering for real-time speech signal enhancement. In the speech signal contaminated by white noise, the spectral components except dominant ones in high frequency band are expected to reflect the noise energy. Our approach is first to find the dominant energy bands over speech spectrum using LPC. We then calculate the average value of the actual spectral components over the high frequency region excluding the dominant energy bands and use it as the noise variance. The resulting noise variance estimate is then applied to Kalman filtering to suppress the background noise. Experimental results indicate that the proposed approach achieves a significant improvement in terms of speech enhancement over those of the conventional Kalman filtering that uses the average noise power over silence interval only. As a refinement of our results, we employ multiple-Kalman filtering with multiple noise models and improve the intelligibility.
Eiichiro FUJISAKI Tatsuaki OKAMOTO
At Eurocrypt'98, Okamoto and Uchiyama presented a new trap-door (one-way) function based on factoring, while Fujisaki and Okamoto, at CRYPTO'99, showed a generic conversion from just one-way encryption to chosen-cipher secure encryption in the random oracle model. This paper shows that the result of combining both schemes is well harmonized (rather than an arbitrary combination) and, in the sense of exact security, boosts the level of security more than would be expected from [6]--The security of the scheme yielded by the combination is tightly reduced from factoring. This paper also gives a rigorous description of the new scheme, because this type of encryption may suffer serious damage if poorly implemented. The proposed scheme is at least as efficient as any other chosen-cipher secure asymmetric encryption scheme such as [2],[4],[13].