we evaluate the effect of express lots on production dispatching rule scheduling and cost in VLSI manufacturing final test process. In the assignment of express lots, we make comparisons of two rules, First In First Out (FIFO) rule which is widely used and WEIGHT+RPM rule which considers the time required for jig and temperature exchanges, the remaining processing time of the machine in use and the lot waiting time in queue. When using FIFO rule, the test efficiency begins to deteriorate and the test cost per chip begins to increase, if the content of express lots exceeds 15%. Furthermore, for 30% of express lots' content, the number of total processed lots decreases by 19% and the test cost per chip increases by 22% in comparison to the cases including no express lots. For WEIGHT+RPM rule, however, the test efficiency does not deteriorate and the test cost per chip does not increase even if the content of express lots is increased up to 50%. When we use WEIGHT+RPM rule, Express Lots Tolerances (ELTs), defined as the maximum content of express lots which permits the deterioration of the system characteristics by 5%, are about three times as high as ones when using FIFO rule. It is also found that WEIGHT+RPM rule maintains higher ELTs against the changes in the numbers of planned chips and prepared jigs as compared with FIFO rule.

Let f be a one-to-one encryption function. Given f(m) and a string K, can we efficiently determine whether m contains K as a substring or not? We investigate the computational complexity of this problem, and show that it is equivalent to not only computing f-1 but also counting the number of K contained as substrings in m. Thus it is not determined in polynomial-time if f is in fact one-way.

This paper presents results of subjective assessment of the media synchronization quality in the virtual-time rendering (VTR) media synchronization algorithm. For the assessment, stored voice and video streams were transmitted as two separate transport streams from a source to a destination on various traffic conditions in an experimental system. At the destination, they were output after synchronization control. We subjectively assessed the quality of media synchronization in a systematic way. This paper examines the effects of the difference between methods of recovery from asynchrony on the media synchronization quality. The paper also clarifies the relationships between the subjective and objective performance measures. Furthermore, it examines the effect of the difference in scene between media streams and that of the modification of the target output time on the media synchronization quality.

This paper is concerned with radio resource allocation in multiple-chip-rate (MCR) DS/CDMA systems accommodating multimedia services with different information rates and quality requirements. Considering both power spectral density (PSD) over a radio frequency (RF) band and the effect of RF input filtering on the receiver in MCR-DS/CDMA systems, criteria for capacity estimation are presented and the characteristics of co-channel interference between subsystems are investigated. System performance in MCR-DS/CDMA systems is strongly affected by radio resource assignment. A minimum power-increment-based resource assignment scheme for an efficient resource assignment scheme is proposed herein. The performance of this scheme is compared with that of a random-based resource assignment scheme in terms of blocking probability and normalized throughput. The minimum power-increment-based resource assignment scheme yields a better performance than the random-based resource assignment scheme for multimedia services.

Internet users have become well acquainted with the World Wide Web (WWW) system, and WWW has become the most significant service on the Internet. In the near future, the importance of large scale hypermedia database systems based on WWW technologies is expected to continue to increace. The present study focuses on the issue of managing hyperlink integrity constraints on WWW like hypermedia database systems. After formally defining path existence constraint definitions(PEDs) using intuitive examples, we apply the notion of PEDs to represent hyperlink integrity constraints. Intuitively, a PED can be used to represent the following integrity constraint. If a reference path exists in a given database, then another corresponding reference path must also exist. An outline of a prototype hypermedia database system, AYATORI, which is based on the proposed model and under development, is also mentioned.

This letter addresses how to set SIR targets higher than normally required, in order to mitigate the effect of signal-to-interference ratio (SIR) measurement error included in power control steps. We find that scaling up the SIR targets by 1 dB is conformable to resisting SIR measurement error for code division multiple access (CDMA) mobile systems.

We present a receiver structure with joint blind equalization, carrier recovery, and timing recovery. The blind equalizer employs a decomposition transversal filtering technique which can reduce the complexity of convolution to about a half. We analyze the performance surface of the equalizer cost function and show that the global minima correspond to perfect equalization. We also derive proper initial tap settings of the equalizer for convergence to the global minima. We describe the timing recovery and the carrier recovery methods employed. And we describe a startup sequence to bring the receiver into full operation. The adaptation algorithms for equalization, carrier recovery, and timing recovery are relatively independent, resulting in good operational stability of the overall receiver. Some simulation results for cable-modem type of transmission are presented.

Support of collaborative work and management of spatio-temporal data has become one of the most interesting and important database applications, which is due to the tremendous progress of database and its surrounding technologies in the last decade. In this paper, we investigate the new generation database technologies that are needed to support such advanced applications. Because of the recent progress of virtual reality technology, virtual work spaces are now available. We examine a typical CSCW (Computer Supported Cooperative Work) fsystem to identify database problems that arise from it. We introduce typical approaches to database improvement based on the high-level view and the virtual reality technique. Also, in this paper, the following are introduced and discussed: the design and implementation of three- and four-dimensional spatio-temporal database systems, VRML (Virtual Reality Modeling Language) database systems, fast access methods to spatio-temporal data, and the interval-based approach to temporal multimedia databases.

Adaptive maximum likelihood differential detection implemented by a reduced state-transition Viterbi algorithm (called adaptive 3-state RSTVDD) is presented for adaptive reception of M-ary differential phase shift keying (DPSK) signals transmitted over additive white Gaussian noise (AWGN) and frequency-nonselective Rayleigh fading channels. The adaptive 3-state RSTVDD comprises 1DD, a differential encoder, and reverse modulator, followed by reduced-state (3-state) Viterbi DD (RSVDD) with adaptive phase reference estimation. The adaptive 3-state RSVDD detector estimates the sequence of phase errors of the 1DD output. The phase reference estimator is an adaptive least mean square (LMS) filter with a step-size that adapts to changing channel conditions. The final detected symbol sequence is the modulo-2π sum of the 1DD output phase sequence and the detected phase error sequence. The bit error rate (BER) performance of M-ary DPSK, M=4, 8, and 16, in the AWGN and Rayleigh fading channels is evaluated by computer simulation to show that adaptive 3-state RSTVDD can achieve almost the same BER performance as the previously developed adaptive M-state RSVDD. Since the number of trellis states is reduced to three irrespective of M, the adaptive 3-state RSTVDD has lower computation complexity and it is particularly useful for M-ary DPSK with M8.

The optimistic analytical results for performance analysis of buffered banyan networks are mainly due to certain independence assumptions used for simplifying analysis. To capture more effects of cell correlation, a refined analytical model for both single-buffered and multiple buffered banyan networks is proposed in this paper. When cell output contention occurs at a 2 2 switch element, two contention resolution schemes are used. One is based on randomly choosing the winning cell and another is to give priority to the cell which has been delayed in the current buffer for at least one stage cycle. The switch throughput, cell transfer delay and cell delay deviation for single-buffered banyan networks with and without using priority scheme are derived. Then the model is generalized to multiple buffered banyan networks where analytical expressions for throughput and delay are obtained. We show that using the priority scheme the cell delay deviation is reduced and the influence on throughput performance is insignificant. The results obtained from our analytical model are compared with the simulations and good agreement is observed. Comparisons with some proposed analytical models in the literature reveal that our model is more accurate and powerful in predicting the performance of buffered banyan networks.

This paper focuses on the problems how to organize and retrieve video data in an effective manner. First we identify several issues to be solved for the problems. Next, we overview our current research results together with a brief survey in the research area of video databases. We especially describe the following research results obtained by the the Japanese Ministry of Education under Grant-in-Aid for Scientific Research on Priority Area: "Advanced Databases" concerned with organization and retrieval of video data: Instance-Based Video Annotation Models, Self-Organization of Video Data, and A Query Model for Fragmentally Indexed Video.

In this paper a high-performance copy network named PPCN is proposed for large scale ATM switching systems. The proposed copy network consists of multiple planes of the P2I Copy Networks(PCN) arranged in parallel. The PCN planes are designed based on the P2I multistage interconnection networks (MINs). A single PCN plane is itself a preliminary self-routing copy network which, however, is not a non-blocking one. A novel dispatcher is designed to dispatch input cells to the PCN planes such that no internal blocking nor output contention arises during the cell replication procedure and the offered load can be shared in an efficient way. The architecture of the PPCN provides flexibility for the maximum fanout for an input cells. In a PPCN system, the maximum fanout for an input cells is determined only by the number of interconnection stages within the PCN planes, independent of the input size of the system. The performance of the PPCN is studied under uniform traffic. It is shown that a small constant number of PCN planes are sufficient for a PPCN system to achieve an acceptable low overflow probability regardless of the system size. The hardware complexity of an N N PPCN is O(N log2 K) and the length of the routing tag is O(log2 K) bits, where K is the maximum fanout for an input cell. The storage complexity of the translation tables adopted in an N-inlet PPCN is O(N), which is much lower than that of the previously proposed ones.

We propose a new method of progressive transmission of continuous tone images using multi-level error diffusion method. Assuming that the pixels are ordered and the error is diffused to later pixels, multi-level error-diffused images are resolved into a multiple number of bit planes. In an image with 8 bits per pixel, the number of the bit planes that we construct is 9, and the 2-level, 3-level, 5-level,, error-diffused images are produced by a successive use of the bit planes. The original image is finally achieved precisely.

Decision trees are used as a convenient means to explain given positive examples and negative examples, which is a form of data mining and knowledge discovery. Standard methods such as ID3 may provide non-monotonic decision trees in the sense that data with larger values in all attributes are sometimes classified into a class with a smaller output value. (In the case of binary data, this is equivalent to saying that the discriminant Boolean function that the decision tree represents is not positive. ) A motivation of this study comes from an observation that real world data are often positive, and in such cases it is natural to build decision trees which represent positive (i. e. , monotone) discriminant functions. For this, we propose how to modify the existing procedures such as ID3, so that the resulting decision tree represents a positive discriminant function. In this procedure, we add some new data to recover the positivity of data, which the original data had but was lost in the process of decomposing data sets by such methods as ID3. To compare the performance of our method with existing methods, we test (1) positive data, which are randomly generated from a hidden positive Boolean function after adding dummy attributes, and (2) breast cancer data as an example of the real-world data. The experimental results on (1) tell that, although the sizes of positive decision trees are relatively larger than those without positivity assumption, positive decision trees exhibit higher accuracy and tend to choose correct attributes, on which the hidden positive Boolean function is defined. For the breast cancer data set, we also observe a similar tendency; i. e. , positive decision trees are larger but give higher accuracy.

In order to exploit fully the frequency diversity benefits of multicarrier modulation (MCM), and the very nature of the frequency selective radio channel, we investigate an erasure decoded π/4 QDPSK MCM (ED-MCM) by employing simple Hamming (block) code. We propose the threshold-free criteria, i. e. relative minimum receive power test (RMRPT) and relative maximum decision error test (RMDET) for erasure generation and evaluate ED-MCM's performance by applying these tests to average received power, average decision error, instantaneous symbol/bit decision errors. At a normalized delay spread of 1/64, computer simulation results indicate a coding gains of 6.0 - 7.0 dB with ED-MCM at a BER of 10-3. RMDET/RMRPT based erasure decoding yields a 1.5 - 2.5 dB improvement over the conventional forward error correction (FEC) decoding at a BER of 10-5. The simulation results at other normalized delay spreads, i. e. , 1/32, 1/16 are also obtained. The erasure criteria (RMRPT and RMDET) applied to average values of received power/decision error yield consistently better performance over error only decoding. The results indicate that the erasure decoding based on relative (threshold-free) measures clearly promises an improved performance of the MCM system.

This paper proposes a multiple open-loop frequency estimation scheme based on differential detection for M-ary phase shift keying (MPSK), which accomplishes fast initial acquisition, precise frequency estimation and wide frequency coverage at the same time. The proposed scheme, which has a good trade-off between complexity and performance, operates as follows: 1) it consists of several frequency error detectors (FEDs) based on differential detection with different delays; 2) it precisely estimates frequency in a wide range (the same range of one symbol differential detection) by open-loop according to frequency errors detected by the FEDs. For real-time symbol-by-symbol operation in order to track fast time-varying frequency, it has a smaller complexity than the other frequency estimation schemes. It is confirmed by analysis, numerical calculation and computer simulation that the frequency estimation error of the proposed scheme is close to the Cramer-Rao lower bound (CRLB) (asymptotic degradation of the proposed scheme from the CRLB is about 0. 5 dB) while keeping a wide frequency coverage and this scheme can track fast time-varying frequency.

This paper proposes two numerical methods to solve the optimal problem of contrast enhancement in the cross-pol and co-pol channels. For the cross-pol channel case, the contrast (power ratio) is expressed in a homogeneous form, which leads the polarimetric contrast optimization to a distinctive eigenvalue problem. For the co-pol channel case, this paper proposes a cross iterative method for optimization, based on the formula used in the matched-pol channel. Both these numerical methods can be proved as convergent algorithms, and they are effective for obtaining the optimum polarization state. Besides, one of the proposed methods is applied to solve the optimal problem of contrast enhancement for the time-independent targets case. To verify the proposed methods, this paper provides two numerical examples. The results of calculation are completely identical with other authors', showing the validity of the proposed methods.

In geographical databases for navigation, users raise various types of queries concerning route guidance. The most fundamental query is a shortest-route query, but, as dynamical traffic information newly becomes available and the static geographical database of roads itself has grown up further, more flexible queries are required to realize a user-friendly interface meeting the current settings. One important query among them is a detour query which provides information about detours, say listing several candidates for useful detours. This paper first reviews algorithms for the shortest and k shortest paths, and discusses their extensions to detour queries. Algorithms for finding a realistic detour are given. The efficiency and property of the algorithms are examined through experiments on an actual road network.

This paper surveys recent research activities on three major areas of digital media information base, namely, video database systems as a typical example of temporal application, database systems for mixed reality as an instance of spatial application, and kansei management for digital media retrieval as a case of humanistic feelings application. Current research results by the project Advanced Database Systems for Integration of Media and User Environments are reported.

We developed a PC cluster system which consists of 100 PCs as a test bed for massively parallel query processing. Each PC employs the 200 MHz Pentium Pro CPU and is connected with others through an ATM switch. Because the query processing applications are insensitive to the communication latency and mainly perform integer operations, the ATM connected PC cluster approach can be considered a reasonable solution for high performance database servers with low costs. However, there has been no challenge to construct large scale PC clusters for database applications, as far as the authors know. Though we employed commodity components as much as possible, we developed the DBMS itself, because that was a key component for obtaining high performance in parallel query processing, and there seemed no system which could meet our demand. On each PC node, a server program which acts as a database kernel is running to process the queries in cooperation with other nodes. The kernel was designed to execute pipelined operators and handle voluminous data efficiently, to achieve high performance on complex decision support type queries. We used the standard benchmark, TPC-D, on a 100 GB database to verify the feasibility of our approach, through comparison of our system with commercial parallel systems. As a whole, our system exhibited sufficiently high performance which was competitive with the current TPC-D top records, in spite of not using indices. For some heavy queries in the benchmark, which have high selectivity and joinability, our system performed much better. In addition, we applied transposed file organization to the database for further performance improvement. The transposed file organization vertically partitions the tuples, enabling attribute-by-attribute access to the relations. This resulted in significant performance improvement by reducing the amount of disk I/O and shifting the bottleneck to computation.