Hiroshi NAGAMOCHI Koji MOCHIZUKI Toshihide IBARAKI
We consider a single-vehicle scheduling problem on a tree, where each vertex has a job with a release time and a processing time and each edge has a travel time. There is a single vehicle which starts from a start vertex s and reaches a goal vertex g after finishing all jobs. In particular, s is called a home location if s = g. The objective of the problem is to find a depth-first routing on T so as to minimize the completion time. In this paper, we first show that the minimum completion times of the problem for all home locations s V can be simultaneously computed in O(n) time, once the problem with a specified home location s V has been solved, where n is the number of vertices. We also show that given a specified start vertex s, the minimum completion times for all goal vertices g can be computed in O(n) time.
Elliptic curves Em: By2 = x3+Ax2+x are suitable for cryptographic use because fast addition operations can be defined over Em. In elliptic curve cryptosystems, encryption/decryption involves multiplying a point P on Em by a large integer n. In this paper, we propose a fast algorithm for computing such scalar multiplication over Em. The new algorithm requires fewer operations than previously proposed algorithms. As a result, elliptic curve cryptosystems based on Em can be speeded up by using the new algorithm.
Taiichi SAITO Shigenori UCHIYAMA
In recent years, the study of the security of Elliptic Curve Cryptosystems (ECCs) have been received much attention. The MOV algorithm, which reduces the elliptic curve discrete log problem (ECDLP) to the discrete log problem in finite fields with the Weil pairing, is a representative attack on ECCs. Recently Kanayama et al. observed a realization of the MOV algorithm for non-supersingular elliptic curves under the weakest condition. Shikata et al. independently considered a realization of the MOV algorithm for non-supersingular elliptic curves and proposed a generalization of the MOV algorithm. This short note explicitly shows that, under a usual cryptographical condition, we can apply the MOV algorithm to non-supersingular elliptic curves by using the multiplication by constant maps as in the case of supersingular. Namely, it is explicitly showed that we don't need such a generalization in order to realize the MOV algorithm for non-supersingular elliptic curves under a usual cryptographical condition.
Changhwan KIM Seyoung CHOI Youngyearl HAN
The performances of M-ary DPSK (MDPSK) and PSK (MPSK) systems using L-branch selection combining (SC) diversity reception in frequency-nonselective slow Nakagami fading channels are derived theoretically. For integer values of the Nakagami fading parameter m, the general formula for evaluating symbol error rate (SER) of MDPSK signals in the independent branch diversity system comprises numerical analyses with the integral-form expressions. An exact closed-form SER performance of MPSK signals under the effect of SC diversity via numerical integration is presented.
Broadcast data delivery is attractive for large-size data distribution where a large user community is connected to a server through a network. It is important to consider a broadcast scheduling method which minimizes the average response time. The scheme should also guarantee the expected waiting time at the time of request. In this paper, we propose a method which divides all titles into several groups and assigns FIFO to each group. The proposed method can guarantee the waiting time for each user at his request, and is superior to FIFO (in high load) and a fixed allocation method (in low load).
Mass measurement system for the measurement of mass of substances placed in randomly vibrating circumstances has been developed. Mass measurement range was defined from 0 g to 400 g for the primary model with the measurement error of approximately 3% when randomly directional vibration of 6 m/sec2 acceleration was applied to the system.
In this paper, we consider a mobile, multimedia, multihop (M3) ad hoc network. Key characteristics of this system are the mobility of users, energy constraints, and the need to operate without a fixed (wired or wireless) infrastructure. In this environment, with the advent of multimedia communications, the use of the cluster architecture has been revisited to support the resource reservation and Quality-of-Service routing. We proposed an access-based clustering protocol (ABCP) that allows the network to self-organize into a cluster architecture. Three advantages are claimed by ABCP. First, by the access-based criterion, it minimizes the overhead on cluster formation so that the protocol has short execution time and good scalability. Second, ABCP unifies the algorithms for cluster initialization and maintenance, i.e., the same set of clustering functions are used by a node regardless of whether it just becomes active or is in leaving its current cluster. Third, simulation results demonstrate that the cluster structure behaves stably amid topology changes compared with techniques previously proposed. Together with the access-based criterion, a multiple access scheme is also proposed for the broadcast of control messages.
Hua LIN Takashi YAHAGI Jianming LU Xiaoqiu WANG
The performance of a twisted-pair channel under ADSL environment is assumed to be dominated by far end crosstalk (FEXT) and additive white Gaussian noise (AWGN). In this paper, we study the channel capacity of the copper twisted pair and the optimum input power spectral density distribution at this channel capacity in the presence of ADSL environment. The channel capacity under different loop length and different input power will also be given. The simulation results show that the distribution of the optimum input power spectral density in the presence of AWGN and FEXT is not uniform. This is different from the situation where AWGN is the only interference, where the input power distribution is approximately uniform.
Fu-Ming TSOU Hong-Bin CHIOU Zsehong TSAI
Currently, the issues in Quality of Service, fairness and pricing strategies should have expedited the emergence of service differentiation in wireless access networks. In this paper, we propose a novel scheduling algorithm, called the Wireless Differentiated Fair Queueing (WDFQ) algorithm, to accommodate such need by providing delay/jitter controls, and fair residual bandwidth sharing for real-time and non-real-time traffic streams simultaneously. We show that the WDFQ scheme can achieve excellent performance, including timely delivery of real-time traffic, virtually error-free transmission of non-real-time traffic, and fair usage of channel bandwidth among remote stations. In addition, the location-dependent channel error property, as appeared in most wireless networks, are considered in the model and the temporary short error bursts are compensated by credits of bandwidth. The simulation results suggest that the length of retransmission period should be adapted to the error length to achieve good performance and maintain low implementation complexity.
In this paper, we describe statistical properties of timing jitter of symbol timing recovery circuit for carrierless amplitude/phase modulation (CAP)-based very high-rate digital subscriber line (VDSL) system. Analytical expressions of the timing jitter for envelope-based timing recovery system, such as squarer-based timing recovery (S-TR) and absolute-value-based timing recovery (A-TR) schemes, are derived in the presence of additive white Gaussian noise (AWGN) or far-end crosstalk (FEXT). In particular, the analytical and simulation results of the timing jitter performance are presented and compared for a 51.84 Mb/s 16-CAP VDSL system. The A-TR system implemented digitally meets the DAVIC's VDSL system requirement, which specifies the maximum peak-to-peak jitter value of 1.5 nsec and the acquisition time of 20 msec.
This letter presents a new transformation technique of series solution to asymptotic solution for a perfectly conducting wedge illuminated by E-polarized plane wave. This transformation gives an analytic manipulation example of the Weber-Schafheitlin integral for diffraction problem.
In this article, we shall propose an efficient anonymous channel protocol for wireless communications. The most important feature of our proposed protocol has the property of untraceability. In our scheme, the mobile stations (MSs) and the home network (HN) must authenticate each other. Moreover, the HN is untraceable in such a way that supports location anonymity and MSs identity anonymity for MSs roaming, dynamic channel assignment and broadcasting. Compare our protocol with Juang et al.'s protocol, our mobile agent communication cost is 3m which is more efficient than the Juang et al.'s protocol 5m. At the same time, our mobile agent computation cost is 2Th which is also more efficient than the Juang et al.'s protocol 1Tpublic+1Th. We can avoid employing public key cryptography in the anonymous channel ticket authentication phase since to keep the computation cost down.
A secret sharing scheme allows a secret to be shared among a set of participants, P, such that only authorized subsets of P can recover the secret, but any unauthorized subset can not recover the secret. It can be used to protect important secret data, such as cryptographic keys, from being lost or destroyed without accidental or malicious exposure. In this paper, we consider secret sharing schemes based on interpolating polynomials. We show that, by simply increasing the number of shares held by each participant, there is a multiple assignment scheme for any monotone access structure such that cheating can be detected with very high probability by any honest participant even the cheaters form a coalition in order to deceive him.
Wujian ZHANG Runde ZHOU Tsunehachi ISHITANI Ryota KASAI Toshio KONDO
The ring-like systolic array architecture described in this paper, based on a conventional one-dimensional systolic array architecture, was created through operator rescheduling based on the symmetry of data flow. This eliminated high-latency delay due to the stuffing of the array pipeline in the conventional architecture. The new architecture requires a memory bandwidth no greater than the conventional architecture does, but increases throughput and processor utilization while reducing power consumption.
Kazushi MURAKOSHI Kiyohiko NAKAMURA
An electrophysiological experiment showed that spike timing was precise to less than one millisecond. This result indicates the possibility in the precise time codings. For a high accurate time coding, reconsideration of a neural mechanism which decides firing time is required. From such viewpoint, we quantitatively examined change in firing time with interference between two synaptic inputs through Hodgkin-Huxley (HH) and integrate-and-fire (IF) model neurons. The precise firing times in the HH model neuron were extremely different from those in the IF model neuron. In this paper, the relations of input intensity to firing time are investigated in the other more two pulse generation models: Morris-Lecar (ML) and FitzHugh-Nagumo (FN) model. The result of the ML model in a certain parameter set (type-I) exhibited monotone decreasing like that of the IF model while the result of the ML model in the otter parameter set (type-II) exhibited non-monotone decreasing like that of the HH model. The result of the FN model exhibited non-monotone decreasing like the HH model despite its qualitativeness. Next the firing patterns in the four model neurons on a model of V1 (primary visual area) and LGN (lateral geniculate nucleus) with circular and mutual excitatory connections are investigated to show how dependent on model neurons the firing patterns are. The spikes in the HH, the ML type-II, and the FN model neurons elicited synchronous oscillations while the spikes in the IF and the ML type-I model neurons did not; the firing patterns dramatically changed with the dependence on the model neurons.
Koyo NITTA Toshihiro MINAMI Toshio KONDO Takeshi OGURA
This paper describes a unique motion estimation and compensation (ME/MC) hardware architecture for a scene-adaptive algorithm. By statistically analyzing the characteristics of the scene being encoded and controlling the encoding parameters according to the scene, the quality of the decoded image can be enhanced. The most significant feature of the architecture is that the two modules for ME/MC can work independently. Since a time interval can be inserted between the operations of the two modules, a scene-adaptive algorithm can be implemented in the architecture. The ME/MC architecture is loaded on a single-chip MPEG-2 video encoder.
A multimedia content is usually read-only and composed of multimedia objects with their spatial and temporal specifications. These specifications given by its author can enforce the display of objects to be well organized for its context. When multimedia contents are serviced in network environment by an on-demand basis, the temporal relationship among the objects can be used to improve the performance of the service. This paper models the temporal relationship as a scenario that represents the presentation order of the objects in a scenario and proposes several scheduling methods that make it possible to rearrange the transmission order of objects in a scenario. As a result, system resources such as computing power and network bandwidth can be highly utilized. Since the temporal relationship of a scenario is static, it is possible to reduce the scheduling overhead of a server by pre-scheduling currently servicing scenarios. In addition, several simulation results are presented in order to compare and analyze the characteristics of the proposed methods.
In this paper, a novel adaptive beamforming scheme is described. This scheme basically employs the GSC algorithm which is one of the famous adaptive interference suppression schemes. The implementation of the GSC algorithm requires complex computations due to the adaptive filtering. Therefore, we propose an efficient GSC algorithm based on the split RLS algorithm. In order to reduce the estimation error caused by the correlation between the splitted blocks, the modified GSC is employed with Walsh blocking matrix instead of Bi-diagonal one. In conclusion, the SINR of the proposed method is very close to the SINR obtained by the full tap solution, e.g. when the system complexity decreases nearly half, the SINR of the proposed method becomes 1 dB worse than that of full tap solution.
To reduce an amount of computation of full search algorithm for fast motion estimation, we propose a new and fast matching algorithm without any degradation of predicted images. The computational reduction without any degradation comes from adaptive matching scan algorithm according to the image complexity of the reference block in current frame. Experimentally, we significantly reduce the computational load compared with conventional full search algorithm.
Trong-Yen LEE Pao-Ann HSIUNG Sao-Jie CHEN
The hardware-software codesign of distributed embedded systems is a more challenging task, because each phase of codesign, such as copartitioning, cosynthesis, cosimulation, and coverification must consider the physical restrictions imposed by the distributed characteristics of such systems. Distributed systems often contain several similar parts for which design reuse techniques can be applied. Object-oriented (OO) codesign approach, which allows physical restriction and object design reuse, is adopted in our newly proposed Distributed Embedded System Codesign (DESC) methodology. DESC methodology uses three types of models: Object Modeling Technique (OMT) models for system description and input, Linear Hybrid Automata (LHA) models for internal modeling and verification, and SES/workbench simulation models for performance evaluation. A two-level partitioning algorithm is proposed specifically for distributed systems. Software is synthesized by task scheduling and hardware is synthesized by system-level and object-oriented techniques. Design alternatives for synthesized hardware-software systems are then checked for design feasibility through rapid prototyping using hardware-software emulators. Through a case study on a Vehicle Parking Management System (VPMS), we depict each design phase of the DESC methodology to show benefits of OO codesign and the necessity of a two-level partitioning algorithm.