Increasingly, 3D Graphics is becoming the main stream feature rather than the early adopters unique advantage in PC platform. In such circumstances, most of the graphics chips focus on the acceleration of the rendering capabilities. However, there are very few or almost no attempts made for the acceleration of the geometry process. This universal 3D graphics geometry processor offers a unique and optimized performance advantage for such 3D geometry calculations. By offloading such operations from the CPU, this 3D graphics geometry processor (hereinafter called 3DGP) delivers a well balanced 3D graphics acceleration environment in the PC.

This paper investigates the relations between the computational complexity and the restrictions for several problems that determine whether a given graph with edge costs and edge lengths has a spanning subgraph with such restrictions as the diameter, the connectivity, and the NA-distance and the NA-(edge)-connectivity proposed and investigated in [1]-[5]. The NA-distance and the NA-(edge)-connectivity are the measures for the distance and the connectivity between a vertex and a vertex subset (area). In this paper we prove that the minimum diameter spanning subgraph problem considering the restrictions of the diameter and the sum of edge costs is NP-complete even if the following restrictions are satisfied: all edge costs and all edge lengths are equal to one, and the upper bound of the diameter is restricted to four. Next, we prove that the minimum NA-distance spanning subgraph problem considering the restrictions of the NA-distances and the sum of edge costs is NP-complete even if the following conditions are satisfied: all edge costs and all edge lengths are equal to one, the upper bound of the NA-distance is restricted to four, each area is composed of a vertex, and the number of areas is restricted to two. Finally, we investigate the preserving NA-distance and NA-edge-connectivity spanning subgraph problem considering the preservations of the NA-distances and the NA-edge-connectivity and the restrictions of the sum of edge costs, and prove that a sparse spanning subgraph can be constructed in polynomial time if all edge costs are equal to one.

A multimedia coding standard, MPEG4 has frozen its Committee Draft (CD) as the MPEG4 version 1 CD, last October. It defines Audio-Visual (AV) coding Algorithms and their System Multiplex/Composition formats. Founding on Object-base concept, Video part adopts Shape Coding technology in addition to conventional Texture Coding skills. Audio part consists of voice coding tools (HVXC and CELP core) and audio coding tools (HILN and MPEG2 AAC or Twin VQ). Error resilience technologies and Synthetic and Natural Hybrid Coding (SNHC) technologies are the MPEG4 specific features. System part defines flexible Multiplexing of audio-visual bitstreams and Scene Composition for user-interactive re-construction of the scenes at decoder side. The version 1 standardization will be finalized in 1998, with some possible minute changes. The expected application areas are real-time communication, mobile multimedia, internet/intranet accessing, broadcasting, storage media, surveillance, and so on.

We have developed and fabricated an LSI called the FMPP-VQ64. The LSI is a memory-based shared-bus SIMD parallel processor containing 64 PEs, intended for low bit-rate image compression using vector quantization. It accelerates the nearest neighbor search (NNS) during vector quantization. The computation time does not depend on the number of code vectors. The FMPP-VQ64 performs 53,000 NNSs per second, while its power dissipation is 20 mW. It can be applied to the mobile telecommunication system.

Theoretical calculations of the pulsing operation and the intensity noise under the optical feedback are demonstrated for operation of the self-sustained pulsation lasers. Two alternative models for the optical feedback effect, namely the time delayed injection model and the external cavity model, are applied in a combined manner to analyze the phenomena. The calculation starts by supposing the geometrical structure of the laser and the material parameters, and are ended by evaluating the noise. Characteristics of the feedback induced noise for variations of the operating parameters, such as the injection current, the feedback distance and the feedback ratio, are examined. A comparison to experimental data is also given to ensure accuracy of the calculation.

In this paper, we propose dynamic cepstral representations to effectively capture the temporal information of cepstral coefficients. The number of speech frames for the regression analysis to extract a dynamic cepstral coefficient is inversely proportional to the cepstral order since the cepstral coefficients of higher orders are more fluctuating than those of lower orders. By exploiting the relationship between the window length for extracting a dynamic cepstral coefficient and the statistical variance of the cepstral coefficient, we propose three kinds of windowing methods in this work: an utterance-specific variance-ratio windowing method, a statistical variance-ratio windowing method, and an inverse-lifter windowing method. Intra-speaker, inter-speaker, and speaker-independent recognition tests on 100 phonetically balanced words are carried out to evaluate the performance of the proposed order-dependent windowing methods.

In a secure partially blind signature scheme, the signer assures that the blind signatures issued by him contains the information he desires. The techniques make it possible to minimize the unlimited growth of the bank's database which storing all spent electronic cash in an anonymous electronic cash system. In this paper we propose an efficient partially blind signature scheme for electronic cash. In our scheme, only several modular additions and modular multiplications are required for a signature requester to obtain and verify a signature. It turns out that the proposed scheme is suitable for mobile clients and smart-card applications because no time-consuming computations are required, such as modular exponentiation and inverse computations. Comparing with the existing blind signature schemes proposed in the literatures, our method reduces the amount of computations for signature requesters by almost 98%.

This paper proposes a top-down co-verification approach in the design of embedded systems composed of both hardware and software, for multimedia applications. In order to realize the optimized embedded system in cost, performance, power consumption and flexibility, hardware/software co-design becomes to be essential. In this top-down co-design flow, a target design is verified at three different levels: (1) algorithmic, (2) implementation, and (3) experimental. We have developed a methodology of top-down co-verification, which consists of the system level simulation at the algorithmic level, two type of co-simulations at the implementation level and the co-emulation at the experimental level. We have realized an environment optimized for verification performance by employing verification models appropriate to each verification stage and an efficient top-down environment by introducing the component logical bus architecture as the interface between hardware and software. Through actual application to a image compression and expansion system, the possibility of efficient co-verification was demonstrated.

BTS (Binary-tree Timing Simulator) is a waveform-based switch-level timing simulator for VLSI circuits and the primary goal is to obtain an accurate waveform during the transient period. To achieve high accuracy, the internal charge effect should be considered because the delay behavior of a CMOS gate is dramatically influenced by internal charges stored in the internal nodes. However, the delay estimation will become a difficult problem when the charge sharing effect is considered. Therefore, this paper presents a recursive algorithm based on Modified Threaded Binary (MTB) tree for efficiently performing the internal-charge-delay estimation in transistor groups using the switch-level delay model. The algorithm CSEE (Charge Sharing Effect Estimation) can determine the charge distribution among the internal nodes, and then increases the accuracy of the waveform approximate technique used in BTS.

In this letter, a design method of linear-phase paraunitary filter banks is proposed for an odd number of channels. In the proposed method, a non-linear unconstrained optimization process is assumed to be applied to a lattice structure which makes the starting guess of design parameters simple. In order to avoid insignificant local minimum solutions, a recursive initialization procedure is proposed. The significance of our proposed method is verified by some design examples.

This paper deals with overload control during congestion in a shared buffer ATM switch via selective cell discard and buffer management. Specifically, we consider the question of efficiency in buffer control schemes in order to reduce the number of cells that have to be discarded during congestion, in the meantime provide "fair" access to the shared buffer by all users. To prevent performance degradation of the shared buffer switch under imbalance traffic conditions, a "gated" buffer control scheme is proposed. The concept of the "gated" control policy is that we add a control gate in front of the corresponding logical queue of each overloaded output port. Some incoming cells destined for the overloaded ports can be blocked before entering the shared buffer. It will make rooms in the shared buffer for those incoming cells destined for the non-overloaded ports. This gated buffer control scheme can be modeled as a variation of SMXQ (sharing with a maximum queue length) scheme with a set of dynamically adjusted queue length thresholds. The simulation study of the gated buffer control is applied to a shared buffer ATM switch under various cell discard mechanisms. In most cases the proposed gated buffer control scheme can not only reduce the overall cell loss but also satisfy the "fair" access requirement under network congestion conditions, if we adjust the dynamical queue length thresholds properly.

The problem of constructing the proper-path-decomposition of width at most 2 has an application to the efficient graph layout into ladders. In this paper, we give a linear time algorithm which, for a given graph with maximum vertex degree at most 3, determines whether the proper-pathwidth of the graph is at most 2, and if so, constructs a proper-path-decomposition of width at most 2.

This paper proposes polling-based real-time software for MPEG2 System protocol LSIs, which is a typical embedded and real-time system on a chip, and demonstrates its performance and usefulness. The polling-based real-time software is designed and optimized by analyzing application specific function requirements and deciding scheduling intervals and the execution cycles of each task. It requires neither hardware for multiple interrupt handling nor software for heavy context switching. The polling-based approach provides sufficient performance without any hardware and software overhead for a real-time application like the MPEG2 System protocol.

In this paper, we propose an idea for intramedia synchronization control using a method of end-to-end delay monitoring to estimate future delay in delay compensation protocol. The estimated value by Kalman filtering at the presentation site is used for feedback control to adjust the retrieval schedule at the source according to the network conditions. The proposed approach is applicable for the real time retrieving application where `tightness' of temporal synchronization is required. The retrieval schedule adjustment is achieved by two resynchronization mechanisms-retrieval offset adjustment and data unit skipping. The retrieval offset adjustment is performed along with a buffer level check in order to compensate for the change in delay jitter, while the data unit skipping control is performed to accelerate the recovery of unsynchronization period under severe conditions. Simulations are performed to verify the effectiveness of the proposed scheme. It is found that with a limited buffer size and tolerable latency in initial presentation, using a higher efficient delay estimator in our proposed resynchronization scheme, the synchronization performance can be improved particularly in the critically congested network condition. In the study, Kalman filtering is shown to perform better than the existing estimation methods using the previous measured jitter or the average value as an estimate.

The switch-block architecture of FPGAs is discussed to see a good balance between programmable-switch resources and routability. For the purpose, FPGAs are assumed to have certain extremal structures, whose switch-blocks consist of parallel or complete switch-sets where a switch-set is a set of switches between two sides of the switch-block. A polynomial time detailed-routing algorithm for a given global-routing is presented if the switch-block consists of two or less parallel switch-sets or three that form a cycle. For other FPGAs, the corresponding decision problem is proved to be -complete. A best compromise between switch resources and routability is offered.

In the wireless ATM network, the key issue is to guarantee various QoS (Quality of Service) under the conditions of the limited radio link bandwidth and error prone characteristics. In this paper, we show a combination method of the error correction schemes, which is suitable to establish multimedia wireless ATM Networks while keeping an efficient use of the limited bandwidth. We consider two levels of FEC; a bit-level and a cell-level to guarantee cell loss probabilities of real time applications. By combining two levels of FEC, various requirements on cell loss can be met. We then apply the bit-level FEC and ARQ protocol for the data communication; tolerant to the delay characteristics. Through the analytical methods, the required overheads of FECs are examined to satisfy the various QoS requirements of CBR connections. The mean delay analysis for the UBR service class is also presented. In numerical examples, we show how the combination scheme to guarantee various cell loss requirements affects the call blocking probability of the CBR service class and the delay of UBR service class.

We propose a new approach to the exact performance analysis of a shared buffer ATM multiplexer, which is loaded with mixed correlated and uncorrelated traffic sources. We obtain the joint steady-state probabilities of both states of the input process and the buffer using a one-dimensional Markov chain. From these probabilities we calculate the loss probabilities and the average delays of the correlated and the uncorrelated traffic sources.

A new approach for generating a system model from its input-output data is presented. The model is approximated as a linear combination of simple basis functions. The number of basis functions is kept as small as possible to prevent over-fitting and to make the model efficiently computable. Based on these conditions, genetic programming is employed for the generation and selection of the appropriate basis. Since the obtained model can be expressed in simple mathematical expressions, it is suitable for using the model as a macro or behavior model in system level simulation. Experimental results are shown.

This paper describes the 'Procyon' processor which is to be used for geometry processing. The objective of this processor is to provide a high performance geometry processor to support next generation 3D graphics such as game and CAD applications. The Procyon processor is a four parallel VLIW processor which makes hardware logic simple. We are pursuing performance improvement by compiler optimization. Procyon has a unique feature called 'Software bypass' as well as special hardware to support 3D graphics processing. Software bypass enables the compiler to make accesses to data on hardware bypass lines. By using this information, the compiler can schedule instructions much more freely and generates efficient VLIW code. Other features of Procyon are multiply-add-accumulate instruction, SIMD instructions and clipping instructions. Procyon VLIW code is held in compacted form, which improves memory performance. A program development environment, such as a pipeline simulator and an assembly code parallelizer, is also prepared for system and application programmers. Preliminary simulation results demonstrate that a performance of 2. 6 M polygons per second at 125 MHz Procyon is attained.

We propose a finite-capacity single-vacation model, with close-down/setup times and a Markovian arrival process (MAP), for SVC-based IP-over-ATM networks. This model considers the SVC processing overhead and the bursty nature of IP packet arrivals. Specifically, the setup time corresponds to the SVC setup time and the vacation time corresponds to the SVC release time, while the close-down time corresponds to the SVC timeout. The MAP is a versatile point process by which typical bursty arrival processes like the IPP (interrupted Poisson process) or the MMPP (Markov modulated Poisson process) is treated as a special case. The approach we take here is the supplementary variable technique. Compared with the embedded Markov chain approach, it is more straightforward to obtain the steady-state probabilities at an arbitrary instant and the practical performance measures such as packet loss probability, packet delay time, and SVC setup rate. For the purpose of optimal design of the SVC-based IP-over-ATM networks, we also propose and derive a new performance measure called the SVC utilization ratio. Numerical results show the sensitivity of these performance measures to the SVC timeout period as well as to the burstiness of the input process.