In this paper, we introduce a new decision problem associated with lattices, named the Exact Length Vector Problem (ELVP), and prove the NP-completeness of ELVP in the ∞ norm. Moreover, we define two variants of ELVP. The one is a binary variant of ELVP, named the Binary Exact Length Vector Problem (BELVP), and is shown to be NP-complete in any p norm (1 ≤ p ≤ ∞). The other is a nonnegative variant of ELVP, named the Nonnegative Exact Length Vector Problem (NELVP). NELVP is defined in the 1 norm, and is also shown to be NP-complete.

We study quantum entanglement by Schmidt decomposition for some typical quantum algorithms. In the Shor's exponentially fast algorithm the quantum entanglement holds almost maximal, which is a major factor that a classical computer is not adequate to simulate quantum efficient algorithms.

This paper presents a method for lossy compression of digital video data by parametric line and Natural cubic spline approximation. The method estimates the variation of pixel values in the temporal dimension by taking group of pixels together as keyblocks and interpolating them in Euclidean space. Break and fit criterion is used to minimize the number of keyblocks required for encoding and decoding of approximated data. Each group of pixels at fixed spatial location is encoded/decoded independently. The proposed method can easily be incorporated in the existing video data compression techniques based on Discrete Cosine Transform or Wavelet Transform.

We propose constant-round protocols for interval tests, equality tests, and comparisons where shared secret inputs are not given bitwise. In [9]. Damgård et al. presented a novel protocol called the bit-decomposition, which can convert a polynomial sharing of an element in prime field Zp into sharings of bits. Though, by using the bit-decomposition protocol, those protocols can be constructed with constant round complexities theoretically, it involves expensive computation, leading to relatively high round and communication complexities. In this paper, we construct more efficient protocols for those protocols without relying on the bit-decomposition protocol. In the interval test protocol, checking whether a shared secret exists in the known interval is reduced to checking whether a bitwise-shared random secret exists in the appropriate interval. In the comparison protocol, comparing two shared secrets is reduced to comparing the two secrets viaindirectly where p is an odd prime for an underlying linear secret sharing scheme. In the equality test protocol, checking whether two shared secrets are equal is reduced to checking whether the difference of the two secrets is zero and furthermore checking whether the difference is a zero is reduced to checking quadratice residuosity of a random secret in a probabilistic way.

The latest LSIs still lack performance in pattern matching and picture recognition. Living organisms, on the other hand, devote very little energy to processing of this type, suggesting that they operate according to a fundamentally different concept. There is a notable difference between the two types of processing: the most similar pattern is always chosen by the conventional digital pattern matching process, whereas the choice made by an organism is not always the same: both the most similar patterns and other similar patterns are also chosen stochastically. To realize processing of this latter type, we examined a calculation method for stochastically selecting memorized patterns that show greater similar to the input pattern. Specifically, by the use of a random voltage sequence, we executed stochastic calculation and examined to what extent the accuracy of the solution is improved by increasing the number of random voltage sequences. Although calculation of the Manhattan distance cannot be realized by simply applying stochastic computing, it can be done stochastically by inputting the same random voltage sequence to two modules synchronously. We also found that the accuracy of the solution is improved by increasing the number of random voltage sequences. This processor operates so efficiently that the power consumption for calculation does not increase in proportion to the number of memorized vector elements. This characteristic is equivalent to a higher accuracy being obtained by a smaller number of random voltage sequences: a very promising characteristic of a stochastic associative processor.

In human-computer interaction, Fitts' law has been applied in one-dimensional pointing task evaluation for some decades, and the usage of effective target width (We) in Fitts' law has been accepted as an international standard in ISO standards 9241-9 [4]. However, the discussion on the concrete methods for calculating We has not been developed comprehensively nor have the different methods of calculation been integrated. Therefore, this paper focuses on a detailed description and a comparison of the two main We calculation methods. One method is mapping all the abscissa data in one united relative coordinate system to perform the calculation (called CC method) and the other is dividing the data into two groups and mapping them in two separate coordinate systems (called SC method). We tested the accuracy of each method and compared both methods in a highly controlled experiment. The experiments' results and data analysis show that the CC method is better than the SC method for human computer interface modeling. These results will be instrumental for future application of Fitts' law.

Heterogeneous distributed computing environments are well suited to meet the fast increasing computational demands. Task scheduling is very important for a heterogeneous distributed system to satisfy the large computational demands of applications. The performance of a scheduler in a heterogeneous distributed system normally has something to do with the dynamic task flow, that is, the scheduler always suffers from the heterogeneity of task sizes and the variety of task arrivals. From the long-term viewpoint it is necessary and possible to improve the performance of the scheduler serving the dynamic task flow. In this paper we propose a task scheduling method including a scheduling strategy which adapts to the dynamic task flow and a genetic algorithm which can achieve the short completion time of a batch of tasks. The strategy and the genetic algorithm work with each other to enhance the scheduler's efficiency and performance. We simulated a task flow with enough tasks, the scheduler with our strategy and algorithm, and the schedulers with other strategies and algorithms. We also simulated a complex scenario including the variant arrival rate of tasks and the heterogeneous computational nodes. The simulation results show that our scheduler achieves much better scheduling results than the others, in terms of the average waiting time, the average response time, and the finish time of all tasks.

Manually collecting contexts of a target word and grouping them based on their meanings yields a set of word senses but the task is quite tedious. Towards automated lexicography, this paper proposes a word-sense discrimination method based on two modern techniques; EM algorithm and principal component analysis (PCA). The spherical Gaussian EM algorithm enhanced with PCA for robust initialization is proposed to cluster word senses of a target word automatically. Three variants of the algorithm, namely PCA, sGEM, and PCA-sGEM, are investigated using a gold standard dataset of two polysemous words. The clustering result is evaluated using the measures of purity and entropy as well as a more recent measure called normalized mutual information (NMI). The experimental result indicates that the proposed algorithms gain promising performance with regard to discriminate word senses and the PCA-sGEM outperforms the other two methods to some extent.

In the age of pervasive computing, ubiquitous collaboration has become an every-day life paradigm. Without an ideal computing infrastructure, issues with ubiquitous collaboration, such as network unreliability, platform heterogeneity, and client's resource constraints, are inevitable. The traditional replication scheme copes with network unreliability by replicating all the objects of a shared application together at once. This is, however, suitable for neither cooperative applications nor mobile computing devices. These problems can be naturally addressed by using a fine-grained replication scheme that enables a portion of the application objects to be replicated. This paper presents an object-oriented middleware that is capable of dynamically and transparently replicating remotely shared Java applications in a partially and on-demand incremental manner. It is also able to maintain various consistency semantics and enables the coexistence of fine-grained replications and conventional remote method invocations. Empirical results indicate several practical benefits of the middleware.

This paper contributes to a new generalized cyclotomic sequences of order two with respect to p1e1p2e2… ptet. The emphasis is on the linear complexity and autocorrelation of new prime-square sequences and two-prime sequences, two special cases of these generalized cyclotomic sequences. Our method is based on their characteristic polynomials. Results show that these sequences possess good linear complexity. Under certain conditions, the autocorrelation functions of new prime-square sequences and two-prime sequences may be three-valued.

In multi-input multi-output orthogonal frequency division multiplexing (MIMO-OFDM) systems, phase tracking schemes suffer from co-channel interference (CCI) and inter-carrier interference (ICI) caused by residual frequency offset. In this paper, we propose a residual frequency offset compensation scheme using feedback phase tracking to eliminate the effect of both ICI and CCI for MIMO-OFDM systems. The proposed phase tracking scheme estimates the amount of residual frequency offset in the frequency domain, and compensates for it in the time domain, periodically. Thus, the effect of ICI can be reduced. Furthermore, we consider two methods of channel estimation that enable the system to estimate the channel response several times within a packet to eliminate the effect of CCI. This is because the channel is generally estimated at the beginning of a packet, and this estimation is affected by residual frequency offset. First is the method that employs midambles. Second is the one that reuses the preamble. When the channel is estimated several times within a packet, the effect of CCI can be reduced. Simulation results show the proposed scheme can compensate for residual frequency offset and CCI more accurately than the conventional scheme, and improve the packet error rate (PER) performance.

An edge-weighted directed graph is referred to as a network in this paper, and an edge operation is an operation that increases or decreases an edge weight. Decreasing an edge weight from the infinite to a finite value or increasing any edge weight from a finite one to the infinite corresponds to addition or deletion of this edge, respectively. The dynamic shortest path problem (DSPP for short) is defined by "Given any network with a specified vertex (denoted as s), and any sequence of edge operations, construct a shortest path tree of each network obtained by executing those edge operations one by one in the order of the sequence." As an application, fast routing for an interior network using link state protocols, such as OSPF and IS-IS, requires solving DSPP efficiently. In this paper, among as many existing algorithms as possible, including those which execute several edge operations simultaneously, fundamental and/or important algorithms are implemented and their capability is evaluated based on the results of computational experiments.

Fractional Motion Estimation (FME) is an advanced feature adopted in H.264/AVC video compression standard with quarter-pixel accuracy. Although FME could gain considerably higher encoding efficiency, sub-pixel interpolation and sum of absolute transformed difference (SATD) computation, as main parts of FME, increase the computation complexity a lot. To reduce the complexity of FME, this paper proposes a full computation reusable VLSI oriented algorithm. Through exploiting the similarity among motion vectors (MVs) of partitions in the same macroblock (MB), temporary computation results can be fully reused. Furthermore, a simple and effective searching method is adopted to make the proposed method more suitable for VLSI implementation. Experiment results show that up to 80% add operations and 85% internal reference frame memory access operations are saved without any degradation in the coding quality.

This paper proposes a new efficient method of characterizing a memory compiler in order to reduce the computation time and remove human error. The new features that make our method greatly efficient are the following three points: (1) high-speed circuit simulation of the whole memory module using a hierarchical LPE (Layout Parasitic Extractor) and a hierarchical circuit simulator, (2) automatic generation of circuit simulation input data from corresponding parameterized description termed the template file, and (3) carefully selected environmental conditions of circuit level simulator and minimizing the number of runs of it. We demonstrate the effectiveness of the proposed method by application to the single-port SRAM generators using 90 nm CMOS technology.

Privacy is increasingly viewed as a key concern in multi-agent based algorithms for Distributed Constraint Satisfaction Problems (DCSP) such as the Meeting Scheduling (MS) problem. Many algorithms aim for a global objective function and as a result, incur performance penalties in computational complexity and personal privacy. This paper describes a mobile agent-based scheduling scheme called Efficient and Privacy-aware Meeting Scheduling (EPMS), which results in a tradeoff among complexity, privacy, and global utility. It also introduces a privacy loss model for collaborative computation, multiple criteria for evaluating privacy in the MS problem, and a privacy measurement metric called the Min privacy metric. We have utilized a common computational space in EPMS for reducing the complexity and the privacy loss in the MS problem. The analytical results show that EPMS has a polynomial time computational complexity. In addition, simulation results show that the obtained global utility for scheduling multiple meetings with EPMS is close to the optimal level and the resulting privacy loss is less than for those in existing algorithms.

In this paper, we present a design method for fixed-width squarer that receives an n-bit input and produces an n-bit squared product. To efficiently compensate for the truncation error, modified Booth-folding encoder signals are used for the generation of error compensation bias. The truncated bits are divided into two groups (major and minor) depending upon their effects on the truncation error. Then, different error compensation methods are applied to each group. By simulations, it is shown that the proposed fixed-width squarers have lower error than other fixed-width squarers and are cost-effective.

During these years, we have been focusing on developing ultra high-data-rate wireless access systems for future wireless multimedia communications. One of such kind of systems is called DPC-OF/TDMA (dynamic parameter controlled orthogonal frequency and time division multiple access) which targets at beyond 100 Mbps data rate. In order to support higher data rates, e.g., several hundreds of Mbps or even Gbps for future wireless multimedia applications (e.g., streaming video and file transfer), it is necessary to enhance DPC-OF/TDMA system based on MIMO-OFDM (multiple-input multiple-output orthogonal frequency division multiplexing) platform. In this paper, we propose an enhanced DPC-OF/TDMA system based on Multi-Layer MIMO-OFDM scheme which combines both diversity and multiplexing in order to exploit potentials of both techniques. The performance investigation shows the proposed scheme has better performance than its counterpart based on full-multiplexing MIMO-OFDM scheme. In addition to the Exhaustive Detection (EXD) scheme which applies the same detection algorithm on each subcarrier independently, we propose the Reduced-Complexity Detection (RCD) scheme. The complexity reduction is achieved by exploiting the suboptimal Layer Detection Order and subcarrier correlation. The simulation results show that huge complexity can be reduced with very small performance loss, by using the proposed detection scheme. For example, 60.7% complexity can be cut off with only 1.1 dB performance loss for the 88 enhanced DPC-OF/TDMA system.

Three distortion reduction filters for radio-on-fiber systems are proposed and evaluated from the standpoint of improvements in in-band third order intermodulation (IM3) components (spurious components), insertion loss, temperature stability and so on. The basic filter configuration includes optical comb filter, RF (radiowave frequency) comb filter, and RF dual band rejection filter (DBRF). Experiments are conducted at 2 GHz band for frequency separation Δf=5 MHz and 100 MHz in the temperature range of -10 to +50. These filters can reduce IM3 components even in the saturation region, unlike conventional linearizers. An optical comb filter can reduce IM3 components more than 20 dB and noise level around 10 dB if its polarization controller is properly adjusted, but its insertion loss is large and stability against vibration is very poor. The proposed RF comb filter and RF-DBRF can reduce IM3 components by more than 20 dB and noise level by more than 3 dB. Their stability against vibration and temperature change is good, and insertion losses are 1-2 dB for Δf=100 MHz.

Substrate-coupling equivalent circuits can be derived for arbitrary isolation structures by F-matrix computation. The derived netlist represents a unified impedance network among multiple sites on a chip surface as well as internal nodes of isolation structures and can be applied with SPICE simulation to evaluate isolation strengths. Geometry dependency of isolation attributes to layout parameters such as area, width, and location distance. On the other hand, structural dependency arises from vertical impurity concentration specific to p+/n+ diffusion and deep n-well. Simulation-based prototyping of isolation structures can include all these dependences and strongly helps establish an isolation strategy against high-frequency substrate coupling in a given technology. The analysis of isolation strength provided by p+/n+ guard ring, deep n-well guard ring as well as deep n-well pocket well explains S21 measurements performed on high-frequency test structures targeting 5 GHz bandwidth, that was formed in a 0.25-µm CMOS high frequency.

For execution of computation-intensive applications, one of the most important paradigms is to divide the application into a large number of small independent tasks and execute them on heterogeneous parallel computing environments (abbreviated by HPCEs). In this paper, we aim to execute independent tasks efficiently on HPCEs. We consider the problem to find a schedule that maximizes the throughput of task execution for a huge number of independent tasks. First, for HPCEs where the network forms a directed acyclic graph, we show that we can find, in polynomial time, a schedule that attains the optimal throughput. Secondly, for arbitrary HPCEs, we propose an (+ε)-approximation algorithm for any constant ε(ε>0). In addition, we also show that the framework of our approximation algorithm can be applied to other collective communications such as the gather operation.