This paper presents a method for mechanically transforming a parallel algorithm on an original network so that the algorithm can work on a target network. It is assumed that the networks are of cube-type such as the shuffle-exchange network, omega network, and hypercube. Were those networks isomorphic to each other, the algorithm transformation is an easy task. The proposed transformation method is based on a novel graphembedding scheme <φ: δ, κ, π, ψ>. In addition to the dilating operation δ of the usual embedding scheme <φ: δ>, the novel scheme uses three primitive graph-transformation operations; κ (= δ-1) for contracting a path into a node, π for pipelining a graph, and ψ (= π-1) for folding a pipelined graph. By applying the primitive operations, the cube-type networks can be transformed so as to be isomorphic to each other. Relationships between the networks are represented by the composition of applied operations. With the isomorphic mapping φ, an algorithm in a node of the original network can be simulated in the corresponding node(s) of the target network. Thus the algorithm transformation is reduced to routine work.

For the multi-gray shades image in the passive matrix type STN-LCDs, the method which combined space modulated patterns and frame rate control(FRC)with switched some frames has been used. Although bi-level display elements are used this method makes it possible to display a multi-gray shades image without resolution-loss for still-image, while the method has a fault to perceive interference of flicker at low frame rate, as is wellknown. However the measured quantitative data for flicker and frame frequency have hardly be published. With regard to frame rate control method which some typical space modulated patterns are combined, we measure critical flicker frame frequency(CFFF) with subjective experiments. This paper also discribes that the data are arranged to be shown in form of relationship with the screen luminance and the lowest frequency components included among ripples on times and also the ripples ratio. Our experimental study provides useful data for designing such kinds of display.

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.

In this paper, we present a distributed RAID style video server that addresses the problem of increasing video stream supplying capability in VOD systems. Distibuted RAID Stylemeans extending the RAID method usually applied to disks to the servers, so as to achieve improvements in performance and reliability. The great advantage of this architecture is that the linear performance improvement can be achieved by adding inexpensive servers of a diffusion model. We have implemented the RAID0 style and RAID4 style systems. A number of new features such as the array configuration method or the striping buffer are applied to them. A precise performance evaluation was made in a near practical environment, with more than 40 video streams. We tested the system, in both normal and degraded mode (server failure) and by checking frame drop rates as well as observing picture quality. An evaluation by simulation was also conducted. The results of the above evaluations agreed well with the calculation value, to confirm the feasibility of this architecture.

This paper proposes new algorithms for diagnosing (detection, identification and location) baseline multistage interconnection networks (MIN) as one of the basic units in a massively parallel system. This is accomplished in the presence of single and multiple faults under a new fault model. This model referred to as the geometric fault model, considers defective crossing connections which are located between adjacent stages, internally to the MIN (therefore, a fault corresponds to a physical bridge fault between two connections). It is shown that this type of fault affects the correct geometry of the network, thus requiring a different testing approach than previous methods. Initially, an algorithm which detects the presence of bridge faults (both in the single and multiple fault cases), is presented. For a single bridge fault, the proposed algorithm locates the fault except in an unique pathological case under which it is logically impossible to differentiate between two equivalent locations of the fault (however, the switching element affected by this fault is uniquely located). The proposed algorithm requires log2 N test vectors to diagnose the MIN as fault free (where N is the number of input lines to the MIN). For fully diagnosing a single bridge fault, this algorithm requires at most 2 log2 N tests and terminates when multiple bridge faults are detected. Subsequently, an algorithm which locates all bridge faults is given. The number of required test vectors is O(N). Fault location of each bridge fault is accomplished in terms of the two lines in the bridge and the numbers of the stages between which it occurs. Illustrative examples are given.

There is a growing demand for high reliability beyond what current RAID can provide and there are various levels of user demand for data reliability. An efficient data placement scheme called RM2 has been proposed in [10], which makes a disk array system resistant to double disk failures. In this paper, we consider how to choose an optimal striping unit for RM2 particularly when no workload information is available except read/write ratio. For experimental purposes, we develop a disk array simulator incorporating RM2 as one of the data placement schemes including other schemes of RAID levels. In the case of disk read operations, it is shown that RM2 has an optimal striping unit of 4/3T for large requests and 8/3T for small requests, where T represents the size of a single track. We have also shown that, if any disk write operations are involved, an optimal striping unit becomes 1/3T for large requests and 8/3T for small requests.

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 recent advance of semiconductor technologies enable to produce a medium size of crossbar with reasonable cost. By making the best use of the high bandwidth of such crossbars, indirect networks including the base-m n-cube and HyperCross have been proposed and researched. In these networks, a node is connected other nodes through crossbars in multiple dimensions. Although these networks are practically used in commercial machines, almost no discussion on a class of networks including them has been done. In this paper, a network class called Multi-Dimensional X'bar (MDX) which includes the above two networks is defined. Several new networks in this class are proposed, and relationship between these networks and direct networks/multistage interconnection networks is discussed. Finally, routing methods for these new networks are proposed and the average distance is evaluated. Through the discussion and evaluation, the MDX supports higher bandwidth than the corresponding multistage interconnection network with smaller hardware than the corresponding direct network.

For reducing requirement of large memory and minimizing computation complexity in a large-vocabulary continuous speech recognition system, speech segmentation plays an important role in speech recognition systems. In this paper, we formulate the speech segmentation as a two-phase problem. Phase 1 (frame labeling) involves labeling frames of speech data. Frames are classified into three types: (1) silence, (2) consonant and (3) vowel according to two segmentation features. In phase 2 (syllabic unit segmentation) we apply the concept of transition states to segment continuous speech data into syllabic units based on the labeled frames. The novel class of hyperrectangular composite neural networks (HRCNNs) is used to cluster frames. The HRCNNs integrate the rule-based approach and neural network paradigms, therefore, this special hybrid system may neutralize the disadvantages of each alternative. The parameters of the trained HRCNNs are utilized to extract both crisp and fuzzy classification rules. In our experiments, a database containing continuous reading-rate Mandarin speech recorded from newscast was utilized to illustrate the performance of the proposed speaker independent speech segmentation system. The effectiveness of the proposed segmentation system is confirmed by the experimental results.

Orthogonal frequency division multiplexing (OFDM) has been receiving a lot of attention in the field of broadcasting because of its ruggedness under multipath environments. One of important issues to realize high quality reception of OFDM signals is to correct frequency and timing offsets between the transmitter and receiver so that orthogonality of the carriers can be maintained. This paper discusses a frequency and timing period acquisition technique for OFDM systems. A new offset estimation technique is introduced that detects both the frequency and timing peirod offsets at the same time by using only one pilot symbol with its suitable frequency assignment. A pseudo noise (PN) sequence is also introduced to assign these frequencies of the pilot symbol so that the frequency acquisition range can be widened. Numerical examples are given to show the estimate variances of the proposed frequency and timing period estimator over both additive white Gaussian noise (AWGN) and multipath fading channels. Also the bit error rate (BER) performance for an open loop acquisition system is examined.

Three techniques are proposed for reducing the time required for protocol processing: protocol data unit management using page management, assembly and disassembly of data packet header and contents in hardware, and rescheduling of protocol processing. These techniques were shown to be feasible by applying them to the TCP/IP over a fiber-distributed data interface network. The maximum communication throughput was 91.6 Mbps; the total throughput for 64 sessions was 89.6 Mbps, only 2% less than the maximum. These techniques will enable the development of more effcient video-on -demand systems.

A classs of type 1 linear phase FIR digital filters is proposed. The filter can be realized using a parallel, modular and regular array structure. It is shown that, under some simple constraints, the consisting modules of the array can be realized free of multiplier coefficients. Such two dimensional mesh arrays are specially suitable for realization with special-purpose systolic hardware for high-speed digital signal processing tasks. Compared to the array structure, proposed by the authors, for multiplierless realization of maximally flat FIR digital filters, this class needs less adders to fulfill the same magnitude response requirements. Another attractive property of the proposed array is that a number of highpass or lowpass filters with different passband widths can be realized simultaneously in a very economical way.

In this paper, a feasible optical code-division multiple-access (CDMA) technique is proposed for high-speed computer networks using prime codes and optical signal processing to guarantee real-time data communications. All-optical architectures for fastly tunable CDMA encoders and decoders are presented, which can be feasibly implemented in the optical domain by using electrooptic switches and optical delay lines. This can support an ultrahigh throughput and a very fast reconfiguration time. Furthermore, we present a self-synchronized sample technique to ensure the correct phase synchronization between optical clock stream and asynchronous electronic data at each electrooptic modulator of an optical CDMA transmitter.

A new high-speed decoding algorithm for Difference-set cyclic codes, and the design and implementation of a 50 MHz CMOS LSI for decoding the (1057, 813) DSCC, are presented. The algorithm, called modified threshold decoding, makes it possible to introduce an arbitrary number of pipeline stages into feedback loops in decoding circuits. A prototype LSI containing about 13k logic gates was fabricated using 1 µm CMOS gate-array technology. The power consumption is less than 750 mW at a 50 MHz clock rate. It is available for digital data transmission systems having an I/O data rate of up to 25 MBPS. It is being used in experimental set-ups targeted at future digital broadcasting systems. The proposed algorithm has an important advantage for much longer codes as it has the potential to be used in the high-speed decoding of DSCCs having a code length longer than 1057.

A hybrid network architecture using subcarrier multiplexed optical fiber (SCMOL) and coaxial cable is proposed in this paper for the access link of future personal communication systems (PCS) between tiny passive radio base stations in microcells and remote central base stations. Results indicate that the required number of laser diodes, photodetectors and amount of fiber could be reduced by more than 4 times with the proposed hybrid access link compared to the point-to-point SCMOL link and the network cost would decrease proportionally.

In future mobile radio, high-speed transmission and efficient spectrum utilization will be important. However, multipath propagation with large delay difference and cochannel interference are obstacles to the advanced mobile communication system. An adaptive antenna can suppress multipath signals and cochannel interference signals. This paper reviews basic performance of multipath fading reduction and cochannel interference suppression using the adaptive antenna. After a brief explanation of adaptive antenna concepts, we show simulation and experimental results of the fading reduction. It is pointed out that the adaptive antenna cancels multipath signals with large delay difference strongly. This feature is very important for high-speed TDMA systems. Moreover, it is shown from simulation results that the adaptive antenna improves the spectrum efficiency by suppressing the cochannel interference signals.

A new current-mode analog BiCMOS multiplier/divider circuit based on the translinear principle is presented. This circuit can be implemented by a standard 0.8µm BiCMOS process. The simulation results showed that the circuit realizes the high-speed and high-precision operation with a 3V supply.

The MU radar of Japan is one of important candidates for providing accurate ground truth for the TRMM precipitation radar. It can provide the dropsize distribution data together with the background atmospheric wind data with high accuracy and high spatial resolution. Special observation scheme developed for TRMM validation using the MU radar is described, and preliminary results from its test experiment are shown. The high-resolution MU radar data are also used in numerical simulations to validate the rain retrieval algorithm for the TRMM PR data analysis. Among known sources of errors in the rain retrieval, the vertical variability of the dropsize distribution and the partial beam-filling effect are examined in terms of their significance with numerical simulations based on the MU radar data. It is shown that these factors may seriously affect the accuracy of the TRMM rain retrieval, and that it is necessary to establish statistical means for compensation. However, suggested means to improve the conventional α-adjustment method require careful treatment so that they do not introduce new sources of errors.

A verification is made on the accuracy of Radar-AMeDAS precipitation, which represents hourly precipitation over the Japanese Islands and the surrounding sea area with a spatial resolution of 5km using data from 5cm conventional radars, 10cm Fujisan Radar, and Automated Meteorological Data Acquisition System (AMeDAS) raingauge network. By comparing with data from a very dense raingauge network of the Tokyo Metropolitan Government, it is found that 1) Radar-AMeDAS precipitation shows good agreement if a positioning error of one pixel of 5km square is allowed 2) Radar-AMeDAS precipitation represents almost the average of raingauge measurements in the 5km square for most of the precipitation caused by a large scale disturbance, and 3) Radar-AMeDAS precipitation is close to the maximum raingauge measurement in the pixel when precipitation is extremely localized such as thunderstorms or showers. Radar-AMeDAS precipitations are compared also with AMeDAS measurements statistically with respect to the appearance rates, that is (total number of pixels where specific intensity is observed) / (total number of all pixels), for different precipitation intensities. The rate of Radar- AMeDAS precipitation shows excellent agreement with that of AMeDAS if radar echoes are observed at the altitude lower than 2km. Since Radar- AMeDAS precipitation on land sometimes represents the maximum of precipitation in a pixel for the purpose of unfailingly detecting extremely localized severe precipitation, it shows a high appearance rate at high precipitation intensity than AMeDAS, which is considered to represent statistically the average of a pixel. As a result, in estimating areal rainfall amounts, Radar- AMeDAS precipitation overestimates AMeDAS measurement by 8% at 5mm/h and by 12% at 40mm/h. Radar- AMeDAS precipitation over the sea, with no local calibration by AMeDAS and with little influence of orography, is 2% weaker in intensity than AMeDAS at 10mm/h, and 12% at 40mm/h.

A new source line routing architecture features a blanket-like source line made of double aluminum layers by utilizing a pure tungsten metal layer as the local interconnection layer in the peripheral region. The relaxed pitch of the signal lines improves the RC time delay constant of the signal lines and gives stable Vcc and Vss levels throughout the chip. Furthermore, this architecture brings about an 8% area reduction of the peripheral region in 256 Mb DRAMs with high performance,when used in collaboration with hierarchical bit-line architecture.