Cutoff rate of overlapping multi-pulse pulse position modulation (OMPPM) is analyzed in the quantum-limited and the background noise cases. Our results suggest that the derived cutoff rate is higher than conventional one because of the infinite quantization at the demodulator and the definition of the erasure event in conventional analysis.

When an image of a 3D object is transmitted or recorded, its range image as well its grey-scale image are required. In this paper, we propose a method of coding for efficient compression of a pair of a pair of range and grey-scale images of 3D objects. We use Lambertian reflection optical model to model the relationship between a 3D object shape and it's brightness. Good illuminant direction estimation leads to good grey-scale image generation and furthermore effects compression results. A method for estimating the illuminant derection and composite albedo from grey-scale image statistics is presented. We propose an approach for estimating the slant angle of illumination based on an optical model from a pair of range and grey-scale images. Estimation result shows that our approach is better. Using the estimated parameters of illuminant direction and composite albedo a synthetic grey-scale image is generated. For comparison, a comparison coding method is used, in which we assume that the range and grey-scale images are compressed separately. We propose an efficient compression coding method for a pair of range and grey-scale images in which we use the correlation between range and grey-scale images, and compress them together. We also evaluate the coding method on a workstation and show numerical results.

A new application of the factorization method is reported for 3-D shape reconstruction from endoscope image sequences. The feasibility of the method is verified with some theoretical considerations and results of extensive experiments. This method was developed by Tomasi and Kanade, and improved by Poelman and Kanade, with the aim of achieving accurate shape reconstruction by using a large number of points and images, and robustly applying well-understood matrix computations. However, the latter stage of the method, called normalization, is not as easily understandable as the use of singular value decomposition in the first stage. In fact, as shown in this report, many choices are possible for this normalization and a variety of results have been obtained depending on the choice. This method is easy to understand, easy to implement, and provides sufficient accuracy when the approximation used for the optical system is reasonable. However, the details of the theoretical basis require further study.

Many numerical simulation problems of natural phenomena are formulated by large tridiagonal and block tridiagonal linear systems. In this paper, an efficient parallel algorithm to solve a tridiagonal linear system is proposed. The algorithm named bi-recurrence algorithm has an inherent parallelism which is suitable for parallel processing. Its time complexity is 8N - 4 for a tridiagonal linear system of order N. The complexity is little more than the Gaussian elimination algorithm. For parallel implementation with two processors, the time complexity is 4N - 1. Based on the bi-recurrence algorithm, a VLSI oriented tridiagonal solver is designed, which has an architecture of 1-D linear systolic array with three processing cells. The systolic tridiagonal solver completes finding the solution of a tridiagonal linear system in 3N + 6 units of time. A highly parallel systolic tridiagonal solver is also presented. The solver is characterized by highly parallel computability which originates in the divide-and-conquer strategy and high cost performance which originates in the systolic architecture. This solver completes finding the solution in 10(N/p) + 6p + 23 time units, where p is the number of partitions of the system.

Because the match phase in OPS5-type production systems requires most of the system's execution time and memory accesses, we proposed hash-based parallel production systems, CPPS (Clustered Parallel Production Systems), based on the RETE algorithm for distributed memory parallel computers, or multicomputers to reduce such a bottleneck. CPPS was effective in speeding up the match phase, but still left room for optimizations. In this paper, we introduce software cache techniques to memory nodes in the CPPS as one of the optimizations, and implement it on a multicomputer, nCUBE2. The benchmark results show that the CPPS with the software cache is about 2-fold faster than the original, and more than 7-fold faster than the simple hash method proposed by Acharya et al. for a large scale problem. The speed-up can be attributed to decreased communication costs.

The use of high-performance portable computers has become widespread. It is expected that many people will carry large amounts of multimedia information in these portable computers. In face-to-face communication, however, few systems are capable of exchanging multimedia information. Previously, we developed the Nomadic Collaboration Support System, which supports face-to-face communication through conversation and the distribution of documents. The system makes it possible for each participant in face-to-face communication to distribute electronic documents to other participants and edit them synchronously. However, it is often impossible for participants to obtain suitable amounts of information during face-to-face communication because of the difficulty in tailoring the documents for each participant. In this paper, we propose a technique to exchange hypertext documents on the Nomadic Collaboration Support System, which will allow each participant to obtain the most suitable amount of information possible from the distributor without his tailoring documents for each participant.

Efficient parallel algorithms for several problems on proper circular arc graphs are presented in this paper. These problems include finding a maximum matching, partitioning into a minimum number of induced subgraphs each of which has a Hamiltonian cycle (path), partitioning into induced subgraphs each of which has a Hamiltonian cycle (path) with at least k vertices for a given k, and adding a minimum number of edges to make the graph contain a Hamiltonian cycle (path). It is shown here that the above problems can all be solved in logarithmic time with a linear number of EREW PRAM processors, or in constant time with a linear number of BSR processors. A more important part of this work is perhaps the extension of basic BSR to allow simultaneous multiple BROADCAST instructions.

An attenuation correction method was proposed for laser-produced plasma emission computed tomography (ECT), which is based on a relation of the attenuation coefficient and the emission coefficient in plasma. Simulation results show that the reconstructed images are dramatically improved in comparison to the reconstructions without attenuation correction.

The objective of this paper is to find a parametric representation for the vocal-tract log-area function that is directly and simply related to basic acoustic characteristics of the human vocal-tract. The importance of this representation is associated with the solution of the articulatory-to-acoustic inverse problem, where a simple mapping from the articulatory space onto the acoustic space can be very useful. The method is as follows: Firstly, given a corpus of log-area functions, a parametric model is derived following a factor analysis technique. After that, the articulatory space, defined by the parametric model, is filled with approximately uniformly distributed points, and the corresponding first three formant frequencies are calculated. These formants define an acoustic space onto which the articulatory space maps. In the next step, an independent component analysis technique is used to determine acoustic and articulatory coordinate systems whose components are as independent as possible. Finally, using singular value decomposition, acoustic and articulatory coordinate systems are rotated so that each of the first three components of the articulatory space has major influence on one, and only one, component of the acoustic space. An example showing how the proposed model can be applied to the solution of the articulatory-to-acoustic inverse problem is given at the end of the paper.

In this paper, DSPs, of which memory addresses are pointed by special purpose registers (address registers: ARs), are assumed, and methods to derive an efficient memory access pattern for those DSPs proposed. In such DSPs, programmers must take care for efficient allocation of memory space as well as effective use of registers, in order to derive an efficient program in the sense of execution period. In this paper, memory addresses and AR update operations are modeled by an access graph, and a novel memory allocation method is presented. This method removes cycles and forks in a given access graph, and decides an address location of variables in memory space with less overhead. In order to utileze multiple ARs, methods to assign variables into ARs are investigated. The proposed methods are applied to the compiler for DSP56000 and are proved to be effective by generated codes for several examples.

This paper presents a binary neural network approach for link activation problems in multihop radio networks. The goal of the NP-complete problems is to find a conflict-free link activation schedule with the minimum number of time slots for specified communication requirements. The neural network is composed of NM binary neurons for scheduling N links in M time slots. The energy functions and the motion equations are newly defined with heuristic methods. The simulation results through 14 instances with up to 419 links show that the neural network not only surpasses the best existing neural network in terms of the convergence rate and the computation time, but also can solve large scale instances within a constant number of iteration steps.

This paper discusses a massively parallel interconnection scheme for multithreaded architecture and introduces a new class of direct interconnection networks called the hierarchical Multidimensional Directed Cycles Ensemble (hMDCE). Its suitability for massively parallel systems is discussed. The network is evolved from the Multidimensional Directed Cycles Ensemble (MDCE) network, where each node is substituted by lower-level sub-networks. The new network addresses some serious problems caused by the increasing scale of parallel systems, such as longer latency, limited throughput and high implementation cost. This paper first introduces the MDCE network and then presents and examines in detail the hierarchical MDCE network. Bisection bandwidth of hMDCE is considerably reduced from its ancestor MDCE and the network performs significantly higher throughput and lower latency under some practical implementation constraints. The gate count and delay time of the compiled circuit for the routing function are insignificant. These results reveal that the hMDCE network is an important candidate for massively parallel systems interconnection.

The mesh-connected computers with hyperbus broadcasting are an extension of the mesh-connected computers with multiple broadcasting. Instead of using local buses, we use global buses to connect processors. Such a strategy efficiently reduces the time complexity of the semigroup problem from O(N) to O(log N). Also, the matrix multiplication and the transitive closure problems are solved in O(log N) and O(log2 N) time, respectively. Then, based on these operations, several interesting problems such as the connected recognition problem, the articulation problem, the dominator problem, the bridge problem, the sorting problem, the minimum spanning tree problem and the bipartite graph recognition problem can be solved in the order of polylogarithmic time.

The transform coding scheme is often used for data compression of images, but the blocking effects peculiar to the scheme appear more clearly in reproduced images as a coding rate (bits/pixel) decreases. These effects can sometimes be viewed as a periodical square-grid overlaying the images. In this paper,we propose a new method for selectively measuring the above blocking effects among several types of image degradation by means of the techniques of nonlinear signal processing for spectral infomation (cepstral techniques), in order to compare the amount of blocking effects for the different coding images. First a two-component model which consists of DC and AC images, is discussed from a viewpoint of subimage-by-subimage coding, and some basic properties of cepstral information for the model are investigated. Then we show a procedure to compute the cepstral information for two-dimensional image signals taking the horizontal and vertical directions ioto account, and introduce a cepstral mean square error (CMSE) as a new measure to estimate the amount of blocking effects. The computer simulation results for some test images using different coding schemes show that the amount of blocking effects in each image can be easily measured and estimated by this method even when the blocking effects appear slightly.

A protocol completion method is proposed to transform protocols synthesized from service specifications into error-free protocols. Communication service specifications described by message sequence charts can be synthesized into protocols. The synthesized protocols may include latent exceptional behaviors that are beyond the given service specifications. Therefore, even if the service specifications themselves are verified, these exceptional behaviors may produce protocol errors such as deadlock states or unspecified reception. Error-free protocols can be obtained from error-free service specifications by synthesizing and then completing the synthesized protocols. By taking account of each service specification through protocol completion, every exceptional behavior can be detected in the protocol entities including erroneous exceptional behaviors. This function can also be applied to resolution of feature interactions. The proposed method is applied to the synthesis of the X.227 protocol from its partial service specifications.

We present a volume rendering algorithm which renders images at approximately two to seven times the speed of a conventional ray caster with almost no visible loss of image quality. This algorithm traverses the volume data in object order and renders the image by performing ray casting for the pixels within the footprint of the voxel (i.e., rectangular prism) being processed. The proposed algorithm supports the rendering of both single and multiple isosurfaces with arbitrary opacity values. While the projection approach to volume rendering is not new, we present an algorithm specifically designed for the perspective projection, evaluate its rendering speed for both single and multiple isosurfaces with arbitrary opacity values, and examine how efficiently it uses cache memory.

A simple algorithm is proposed for representing nonseparable functions by equivalent separable functions. In this algorithm, functions are first represented by computational graphs, which are directed graphs representing the computational process of the functions. Then, the vertices of the computational graphs are searched in preorder or postorder, and the transformation to separable forms is performed at the places where it is necessary. By this repetition of the transformation, nonseparable functions are represented by separable functions automatically. The proposed algorithm will be useful in various fields of science and engineering because funcutions of one variable are easy to deal with.

We have devised a polynomial time algorithm to decide the security of cryptographic protocols formally under certain conditions, and implemented the algorithm on a computer as a supporting system for deciding the security. In this paper, a useful approach is presented to decide security problems which do not satisfy some of the above-mentioned conditions by using the system. For its application, we consider a basic security problem of Kerberos protocol, whether or not an enemy can obtain the session key between a client and a server by using any information not protected in communication channels and using any operation not prohibited in the system. It is shown that Kerberos is secure for this problem.

In this paper, we propose a timing constrained database system which accesses a database at a host computer via a mobile support server with a wireless portable computer running in mobile computing environments, so that we can provide seamless database access between a communication cell and the host computer even if the user of the portable computer moves from one communication cell to another. Then, we also provide some new kind of database cache algorihm, such as all-cell-cache, neighbour-cell-cache, 1-cell-skip-cache, 2-cell-skip-cache and 3-cell-skip-cache methods, each of which manages the data downloading and uploading among the host database and some cell databases at the mobile support servers so as to minimize the database access fault probability when the user moves from one communication cell to another. And, we show the averaged database access time and the averaged database cache hit ratio which are computed by simulating each of the above database cache algorithms with random variables generation method. Finally, we conclude that each above cache alogorithm is advantageous to the database in mobile computineg einvironments.

In this paper, we propose an analytic model using a semi-markov process for parallel computers which provides hardware support for a cache coherence mechanism. The model proposed here, the Semi-markov Memory and Cache coherence Interference model, can be used for the performance prediction of cache coherence based parallel computers since it can be easily applied to descriptions of the waiting states due to network contention or memory interference of both normal data accesses and cache coherence requests. Conventional analytic models using stochastic processes to describe parallel computers have the problem of numerical explosion in the number of states necessary as the system size increases even for simple parallel computers without cache coherence mechanisms. The number of states required by constructing our proposing analytic model, however, does not depend on the system size but only on the kind of cache coherence protocol. For example, the number of states for the Synapse cache coherence protocol is only 20, as is described in this paper. Using the proposed analytic model, we investigate several comparative experiments with widely known simulation results. We found that there is only a 7.08% difference between the simulation and our analytic model, while our analytic model can predict the performance of a 1,024 processor system in the order of microseconds.