We have discussed a ray tracing method to estimate the scattering characteristics from random rough surface. It has been shown from the traced rays that the diffracted rays dominate over the reflected rays. For the field evaluation, we have used the Fresnel function for the diffracted coefficient and the Fresnel's reflection coefficients. Numerical examples have been carried out for the scattering characteristics of an ocean wave-like rough surface and the delay spared characteristics of a building-like surface. In the present work we have demonstrated that the ray tracing method is effective to numerical analysis of a rough surface scattering.

A broadcast distribution system (BDS) is a system for the distribution of digital contents over broadcast channel where the data supplier broadcasts the contents in encrypted form and gives each subscriber a decoder containing a secret decryption key. A traitor is a subscriber who offers the information which allows to decrypt the broadcast. When a pirate decoder is captured, if at least one traitor can be identified from it, a BDS is said to be traitor-tracing. If the data supplier can prevent subscribers from obtaining the contents without recalling their decoders, a BDS is said to be subscriber-excluding. In this paper, we propose an efficient BDS which is both subscriber-excluding and traitor-tracing. We use similar mathematics to a threshold cryptosystem. In the proposed BDS, the maximum number of excluded subscribers reaches the maximum number of traitors in a coalition for which at least one traitor can be identified. We prove that the proposed BDS is secure against ciphertext-only attack if and only if ElGamal cryptosystem is secure against the attack and the discrete logarithm problem is hard. The proposed BDS is the first one which satisfies all the following features: Both subscriber-excluding and traitor-tracing, identifying all the traitors, black box tracing and public key system.

This paper focuses on introducing a highly efficient data structure that effectively captures the multipath phenomenon needed for accurate propagation modeling and fast propagation prediction. We propose a new object representation procedure called circular representation (CR) of microwave masking objects such as buildings, to improve over the conventional vector representation (VR) form in fast ray tracing. The proposed CR encapsulates a building with a circle represented by a center point and radius. In this configuration, the CR essentially functions as the basic building block for higher geometric structures, enhancing the efficiency more than when VR is used alone. Only one CR is needed to represent one building while several wall vectors are required in VR. As a result, a significant computational reduction can be achieved in ray tracing by the proposed method. Our aim is to show CR as a solution to achieving efficiency in data structuring for effective propagation prediction modeling. We show that the computational load is reduced by the proposed method. Further reduction is shown attainable using the hierarchical structure of CR in a deterministic propagation model, undergoing ray tracing. The simulation results indicate that the proposed CR scheme reduces the computational load proportionally to the number of potential scattering objects while its hierarchical structure achieves about 50% of computational load reduction in the hierarchical octree structure.

In our previous paper we presented a path-tracing method of multiple gate delay fault diagnosis in combinational circuits. In this paper, we propose an improved method that uses the ambiguous delay model. This delay model makes provision for parameter variations in the manufacturing process of ICs. For the effectiveness of the current method, we propose a timed 8-valued simulation and some new diagnostic rules. Furthermore, we introduce a preparatory process that speeds up diagnosis. Also, at the end of diagnosis, additional information from the results of the preparatory process makes it possible to distinguish between non-existent faults and undiagnosed faults.

This paper presents a prediction of the millimeter-wave multipath propagation characteristics in the typical urban environment. To analyze the propagation in an outdoor environment, the three dimensional model based on the geometrical optics and the uniform geometrical theory of diffraction is employed. Prediction by the three dimensional ray tracing method needs a detailed map, which records locations and shapes of obstacles surrounding a transmitter and a receiver. It is usually difficult to create a complete map because tremendous data is necessary to describe the area structure. We propose, in this report, a three dimensional propagation model to predict the millimeter wave propagation characteristics by using the information available from only a map on the market. This approach gives us much convenience in the actual design. The modeled results are demonstrated and furthermore comparison are made between the simulated results and the experimental data.

Mechanism of UHF radiowave propagation into multistory office buildings are explored by using ray-tracing based models, which include a three-dimensional (3-D) ray-tracing model and a direct-transmitted ray (DTR) model. Prediction accuracy of the models is ascertained by many measured data and the measurements are carried out at many specific sites with different propagation scenarios. Their measured results also demonstrate some important propagation phenomena. It is found that (1) the direct transmitted wave may be the dominant mode; (2) the path loss neither increases nor decreases monotonically as a function of increasing floor level; and (3) there is not much difference of the average path loss among the receiving positions in the same room.

For mobile telecommunication systems, it is important to accurately predict the propagation-path loss in terms of the estimation of the radiowave coverage area. The propagation-path loss has been estimated in a median obtained spatially from many received amplitudes (envelopes) within a region of several tens times as long as the wavelength, rather than in the envelopes themselves. Although ray tracing can obtain the envelopes and their median that reflect the site-dependent characteristics, the estimated median sometimes does not agree with the measured one. Therefore, the accuracy improvement has been expected. In this paper, an accuracy improvement is achieved by substituting a median with random phases for the median obtained spatially from many envelopes. The characteristic function method is used to obtain the cumulative distribution function and the median analytically where the phases are randomized. In a multipath environment, the phase-estimation error accompanying the location error of the ray tracing input influences the spatially obtained median. The phase-randomizing operation reduces the effects of the phase-estimation error on the median prediction. According to our estimation, improvements in accuracy of 4. 9 dB for the maximum prediction error and 2. 9 dB for the RMS prediction error were achieved. In addition, a probability-based cell-design method that takes the radiowave arrival probability and the interference probability into consideration is possible by using the percentiles obtained by the characteristic function method and the cell-design examples are shown in this paper.

Testing for delay faults is very important in the verification of the timing behavior of digital circuits. When a circuit which is unable to operate at the desired clock speed is identified, it is necessary to locate the delay fault(s) affecting the circuit in order to remedy the situation. In this paper, we present a path-tracing method of multiple gate delay fault diagnosis in combinational circuits. We first present the basic rules for deducing suspected faults based on the multiple gate delay fault assumption. Next, in order to improve diagnostic resolution, we introduce rules for deducing non-existent faults based on the fault-free responses at the primary outputs. Using these rules, we present the detailed method for diagnosing multiple delay faults based on paths sensitized by test-pairs generated for marginal delays and gate delay faults [7]. Finally, we present results obtained from experiments on the ISCAS '85 benchmark circuits. The experimental results show the effectiveness of our method.

This paper is concerned with Wiener-Hopf solutions to the electromagnetic wave scattering by a conducting finite thin plate when the incident wave is not a plane wave. The incident wave is approximated in terms of a piece-wise plane wave on a divided small section of the conducting plate. The final expressions are given in an analytically compact form and the results are accurate as long as the plate width is greater than the wavelength and the divided section is so small that we can expand the incident wave by a piece-wise plane wave. A criterion for the ray tracing method is also proposed.

This paper presents almost rigorous Wiener-Hopf solutions to the plane wave scattering by a conducting finite thin plate. The final field expressions are given in an analytically compact form and the results are accurate as long as the plate width is greater than the wavelength. Numerical examples are given for the near and far field distributions. A criterion is also proposed to estimate under what condition the ray tracing method holds.

The multipass rendering method based on the global illumination model can generate the most photo-realistic images. However, since the multipass rendering method is very time consuming, it is impractical in the industrial world. This paper discusses a massively parallel processing approach to fast image synthesis by the multipass rendering method. Especially, we focus on the performance evaluation of the view-dependent object-space parallel processing on the (Mπ)2 which has been proposed in our previous paper. We also propose two kinds of distributed frame buffer system named cached frame buffer and multistage-interconnected frame buffer. These frame buffer systems can solve the access conflict problem on the frame buffer. The simulation results show that the (Mπ)2 has a scalable performance. For example, the (Mπ)2 with more than 4000 processing elements can achieve an efficiency of over 50%. We also show that both of the proposed distributed frame buffer systems can relieve the overhead due to frame buffer access in the (Mπ)2 in the case that a large number of high-performance processing elements are adopted in the system.

The design, fabrication, and testing of a highly multimode polymeric 88 star coupler is described. The design process allowed a comparison to be made of ray tracing and beam propagation methods for the design of such highly multimode waveguide devices. The results obtained with either of these two different methods agree well with actual measurements on a fabricated 88 multimode-input star coupler with a refractive index difference of Δn=0.0274 and a device length of L=4.25 cm. The reduction in the rms power fluctuation in the output guides with the choice of a higher refractive index difference is demonstrated.

As the demand of wireless personal communications networks increases, detailed chracteristics of indoor radio propagation in UHF band are required. In this paper, multipath fading characteristics at 1 GHz in an indoor mobil (walking speed) channel are investigated. By using a computer-controlled antenna scanner, signal strength was measured at 1400 points with a quarter wavelength resolution, which forms a two-dimensional fading map. The fading characteristics were found to be mainly dominated by the signals through the LOS path and the reflected paths due to two side-walls and one front-wall. It is analytically shown that middle-scale (over three wavelengths) fading is caused by the reflection from the side-walls, and periodical small-scale (equal to or less than a wavelength) fading is caused by the reflection from the front-wall. A software simulator based on geometric optics was developed in order to predict the measured fades. A modified algorithm for the two-dimensional ray launching technique which removes the necessity of checking the "multiple-counted rays" is presented. Comparison between measurements and predictions shows good agreement highlighting the usefulness of the two-dimensional simulator as a tool for channel design.

A method for the recognition of handprinted Thai characters input using an image scanner is presented. We use methods of edge detection and boundary contour tracing algorithms to extract loop structures from input characters. The number of loops and their locations are detected and used as information for rough classification. For fine classification, local feature analysis of Thai characters is presented to discriminate an output character from a group of similar characters. In this paper, four parts of the recognition system are presented: Preprocessing, single-character segmentation, loop structure extraction and character identification. Preprocessing consists of pattern binarization, noise reduction and slant normalization based on geometrical transformation for the forward (backward) slanted word. The method of single-character segmentation is applied during the recognition phase. Each character from an input word including the character line level information is subjected to the processes of edge detection, contour tracing and thinning to detect loop structures and to extract topological properties of strokes. The decision trees are constructed based on the obtained information about loops, end points of strokes and some local characteristics of Thai characters. The proposed system is implemented on a personal computer, and a high recognition rate is obtained for 1000 samples of handprinted Thai words from 20 subjects.

In this paper we will propose a deterministic approach to model the radio wave propagation channels in large empty buildings. This technique applies the modified SBR method to find equivalent sources (images) in each launched triangular ray tube, and sums the receiving amplitude contributed by all images coherently. In addition, vector effective antenna height (VEH) is introduced to consider the polarization coupling effect resulting from the multiple reflection inside the buildings. We verify this approach by comparing the numerical results in three canonical examples where closed-form solutions exist. The good agreement indicates that our method can provide a good approximation of high frequency radio propagation inside buildings where multiple reflection is dominant. Work reported in this paper has shown that propagation loss in large empty buildings can vary considerably according to the geometrical configurations of buildings and polarizations. This SBR/image method can be enhanced by including the wall penetration and wedge diffraction effects so that more complicated indoor environments with furniture will be handled. Additional considerations, such as buildings crowded with pedestrians are left for future studies.

This paper proposes a hierarchical parallel processing system for the multipass rendering method. The multipass rendering method based on the integration of radiosity and ray-tracing can synthesize photo-realistic images. However, the method is also computationally expensive. To accelerate the multipass rendering method, the system, called (Mπ)2, employs two kinds of parallel processing schemes. As a coarse-grain parallel processing, object-space parallel processing with multiple processing elements based on the object-space subdivision is adapted, and each processing element (PE) is equipped with multiple pipelined units for a fine-grain parallel processing. To balance load among the system, static load balancing at the PE level and dynamic load balancing at the pipelined unit level within the PE are introduced. Especially, we propose a novel static load allocation scheme, skewed-distributed allocation, which can effectively distribute a three-dimensional object space to one- or two-dimensional processor configuration of the (Mπ)2 system. Simulation experiments show that the two-dimensional (Mπ)2 systems with the skewed-distributed allocation outperform the three-dimensional systems with the non-skewed distributed allocation. Since lower dimensional systems can be built at a lower cost than higher dimensional systems, the skewed-distributed allocation will be meritorious. Besides, by the combination of static load balancing by the skewed-distributed allocation and the dynamic load balancing by dynamic ray allocation within each PE, the system performance can be further boosted. We also propose a cached frame buffer system to relieve access collision on a frame buffer.

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.

An automatic transistor-level performance fault tracing method is proposed which is applicable to the case where only CAD layout data is available in the CAD-linked electron beam test system. The technique uses an integrated algorithm that combines a previously proposed transistor-level fault tracing algorithm and a successive circuit extraction from CAD layout data. An expansion of the algorithm to the fault tracing in a combined focused ion beam and electron beam test system which enables us to measure signals on the interconnections in the lower layers is also described. An application of the technique to a CMOS model layout with about 100 transistors shows its validity.

In this paper, we discuss computational methods for obtaining the bifurcation points and the branch directions at branching points of solution curves for the nonlinear resistive circuits. There are many kinds of the bifurcation points such as limit point, branch point and isolated point. At these points, the Jacobian matrix of circuit equation becomes singular so that we cannot directly apply the usual numerical techniques such as Newton-Raphson method. Therefore, we propose a simple modification technique such that the Newton-Raphson method can be also applied to the modified equations. On the other hand, a curve tracing algorithm can continuously trace the solution curves having the limit points and/or branching points. In this case, we can see whether the curve has passed through a bifurcation point or not by checking the sign of determinant of the Jacobian matrix. We also propose two different methods for calculating the directions of branches at branching point. Combining these algorithms, complicated solution curves will be easily traced by the curve tracing method. We show the example of a Hopfield network in Sect.5.

In this paper we will propose a deterministic approach to model the radio propagation channels complex indoor environments. This technique applies the SBR method to find equivalent sources (images) in each launched ray tube, and sums the receiving amplitude contributed by all images coherently. We verify our SBR/image approach by comparing the numerical results in two canonical examples where closed-form solutions exist. The good agreement indicates that our method can provide a good approximation of high frequency radio propagation inside corridors where reflection is dominant. In the special case of a curved corridor, which can not be solved by analytic methods, we find a "focusing" effect that at some certain point the receiver will receive high power, even though it is out of sight. This SBR/image method can be enhanced by including the wall penetration and wedge diffraction effects, and even more complicated indoor environments will be tackles in the near future.