This paper proposes a fast timing recovery method with a decision feedback equalizer for baudrate sampling. The proposed method features two special techniques. The first one is for coarse estimation of the sampling phase. Internal signals of the oversampled analog-to-digital converter at different phases are directly taken out for parallel evaluation. The second technique provides fine tuning with a phase-modification stepsize which is adaptively controlled by the residual intersymbol interference. Simulation results by a full-duplex digital transmission system with a multilevel line code show superiority of the proposed method. The coarse timing estimation and the fine tuning reduce 75% and 40% of the time required by the conventional method,respectively. The overall saving in timing recovery is almost 60% over the conventional method. The proposed method could easily be extended to other applications with a decision feedback equalizer.

This paper provides an architectural study of optical ring trunk-transmission networks using either Time Division Multiplexing (TDM) or Wavelength Division Multiplexing (WDM). A timeslot arrangement algorithm for distributed controlled TDM rings is proposed that minimizes the number of slots (wavelengths) required in bi-directional ring networks. This algorithm is applied in a straightforward manner to wavelength arrangement in WDM ring networks. The technique, characterized by timeslot (or wavelength) conversion, realizes common add/drop procedures in all Add/Drop Multiplexers (ADMs) when they are connected logically in a mesh topology. A self-healing algorithm is also proposed for network restoration. It offers good performance in terms of protection line-capacity, restoration delay, and survivability against multiple failures.

2D (two-dimensional) convolution is a basic operation in image processing and requires intensive computation. Although the SIMD model is considered suitable for 2D convolution, previous 2D convolution algorithms on the SIMD model assume unbounded number of PEs (Processing Elements) available, which we call unbounded case. Unbounded case could not be satisfied on real computers. In this paper, time-optimal data-parallel 2D convolution is studied on mesh-connected SIMD computers with bounded number of PEs. Because the optimal computation complexity is not difficult to achieve, the main concern of this paper is how to achieve optimal communication complexity. Firstly the lower bound computation complexity is analyzed. Then the lower bound communication complexities are analyzed under two typical data-distribution strategies: block-mapping and cyclic-mapping. Based on the analysis result, an optimal algorithm is presented under the block-mapping. The algorithm achieves the lower bound complexity both in computation and in communication.

The medial axis transform (MAT) is an image representation scheme. For a binary image, the MAT is defined as a set of upright maximal squares which consist of pixels of value l entirely. The MAT plays an important role in image understanding. This paper presents a parallel algorithm for computing the MAT of an n n binary image. We show that the algorithm can be performed in O(log n) time using n2/log n processors on the EREW PRAM and in O(log log n) time using n2/log log n processors on the common CRCW PRAM. We also show that the algorithm can be performed in O(n2/p2 + n) time on a p p mesh and in O(n2/p2 + (n log p)/p) time on a p2 processor hypercube (for 1 p n). The algorithm is cost optimal on the PRAMs, on the mesh (for 1 p n) and on the hypercube (for 1 p n/log n).

To enhance fabrication yield for processor arrays, many reconfiguration schemes for replacing faulty processing elements (PE's) with spare PE's have been proposed. An array grid model based on single-tracks is one of such models. For this model, some algorithms for reconfiguring processor arrays have been proposed. However, an algorithm which can reconfigure the array, whenever the array is reconfigurable, has not been proposed yet. This paper presents two types of methods for reconfiguration of processor arrays. Both the types use indirect replacements for reconfiguring arrays. For an indirect replacement of a faulty non-spare PE, one has a fixed direction, the other has at most four directions among which one is chosen. For the former, we consider the several distribution of spare PE's, and computer simulations show a tendency in the term of difference in the distributions. The latter algorithms consist of two phases. In the first phase, rows and columns of spare PE's are decided in accordance with a rule. Several rules for deciding spare PE's are considered in this paper. In the second phase, faulty non-spare PE's are replaced with healthy spare PE's. By simulations the performance of the algorithms are evaluated and a tendency is shown in the terms of difference in disposition of spare PE's.

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.

This paper presets a fast computation algorithm for connection admission control for heterogeneous delay sensitive traffic in ATM networks. Cell loss probability is adopted as the measure of quality of service. In our study, cells of each connection are allowed to have two different loss priorities and the aggregate traffic can have more than two. To cope with multiple quality of service requirements, the link capacity is divided into several bands. For simplicity, each traffic source is assumed to alternate between active and idle periods. However, the results can be extended to traffic sources having more than two states. Upper bounds of actual cell loss probabilities are derived based on the bufferless fluidflow model. Numerical results show that the upper bounds are close to the actual cell loss probabilities.

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.

Video services such as video-on-demand are expected to be a motivation for deploying multimedia services in residential areas. These services should increase customer demand for video channels as customer demands become more sophisticated and diverse in the future. Therefore, it is important to determine how network configurations (i.e. network transition scenarios) should evolve in response to changes in access network demand. This paper proposes economical deployment of access networks based on transition scenarios. We conclude that transition scenarios offer more economical deployment than single-network configurations. Two transition scenarios, from passive double-star to fiber single-star, and from hybrid fiber-coax to fiber single-star, are evaluated as examples. These transition scenarios are economical even when customer demand changes. The transition starting time affects the present worth of annual charges (PWAC) of access networks more than the transition period does.

We proposed a new marker design for passive alignment of a laser to a fiber on a silicon waferboard. Our fiducial marker is simple form and easy to fabricate. With a unique marker design, high accurate positioning of the laser chip is easily achieved using a conventional flip-chip bonder. We have successfully fabricated laser modules with uniform coupling, within 1 dB for a flat end single-mode fiber and within 2 dB for a hemispherical end fiber. This assembly method offers the potential for low-cost optical module packaging.

Precise direct mounting of laser diode (LD) and photodiode (PD) chips on silica planar lightwave circuits (PLCs) has been investigated for application to transceiver modules. To achieve submicron optical alignment, self-aligned index marks on the PLCs and LDs were directly detected by transmission infrared light. The repeatability of the positioning was measured to be within 0.125 µm. The output power of the resultant module was 0.2 mW at 80 mA. A waveguide-type PD was also mounted in the same way, and module sensitivity of 0.25 A/W was demonstrated.

In this paper, we analyze the throughput and delay performances of the CDMA unslotted ALOHA system considering packet retransmisson. We also clarify the stability of the system. Based on these results, we propose the optimal retransmission control (ORC) to improve the performances. The ORC is the scheme to prevent the system from drifting to an undesirable operating point by controlling the birth rate of retransmitted packets. As a result, it is shown that the throughput and delay performances of the system with the ORC are better than without the ORC and the system does not drift to an undesirable operating point.

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.

Reduction of the complexity of the NLMS algorithm has recceived attention in the area of adaptive filtering. A processing cost reduction method, in which the component of the weight vector is updated when the absolute value of the sample is greater than or equal to an arbitrary threshold level, has been proposed. The convergence analysis of the processing cost reduction method with white Gaussian data has been derived. However, a convergence analysis of this method with correlated Gaussian data, which is important for an actual application, is not studied. In this paper, we derive the convergence cheracteristics of the processing cost reduction method with correlated Gaussian data. From the analytical results, it is shown that the range of the gain constant to insure convergence is independent of the correlation of input samples. Also, it is shown that the misadjustment is independent of the correlation of input samples. Moreover, it is shown that the convergence rate is a function of the threshold level and the eigenvalues of the covariance matrix of input samples as well as the gain constant.

This paper proposes Channel Reservation for Ahead Cells (CRAC)" scheme for street micro-cellular systems. The scheme enables mobiles to reserve the same channel over several cells at once. This paper analyzes both CRAC and FCA (Fixed Channel Assignment) in a ring-shaped service area where high speed mobiles and low speed mobiles move. In the analysis, the priority control which prioritizes hand-off calls and reservation calls over new calls over new calls is also taken into account. Obtained results include the blocking rate, the forced call termination rate, the average number of channel changings and the system utilization. From numerical results, CRAC is found to perform better than FCA with regard to the average number of channel changings and the forced call termination rate.

In packet radio networks with TDMA, the throughput performance of network should be degraded due to the unequal traffic of each user. To overcome this problem, Mini-Slotted Alternating Priorities (MSAP) and TDMA with Parallel Transmission (TDMA/PT) were proposed. Especially, TDMA/PT can attain the thorughput performance more than one, even under unequal traffic. However, TDMA/PT cannot be used for mobile networks, because each terminal should know the location of every other terminal. In this paper, we propose an entirely new protocol named Slot Reservation TDMA with Parallel Transmissino: SR-TDMA/PT," which is suitable for mobile networks because a central station is able to locate every terminal easily. The central station also reserves time slots for each terminal so as to transmit packets in parallel as much as possible. Therefore, the throughput performance of SR-TDMA/PT is higher than TDMA/PT. We describe SR-TDMA/PT in detail and evaluate the performance of this protocol by simulation under various conditions.

String grammars (languages) have been extensively studied from 60's. On the other hand, the transformational grammar, proposed by N. Chomsky, contains the transformation from the set of derivation trees of context-free language to the surface set. And the grammar regarded a tree as an input sentence to some transducer. After that from latter half of 60's, the studies of acceptors, transducers, and so on, whose input is a tree, have been studied extensively. And recently some pushdown tree automata were introduced, and their fundamental properties and some other various properties were investigated [11]-[17]. Furthermore, a top-down pushdown tree transducer (t-PDTT for short), which is an extension of a top-down pushdown automaton (t-PDTA for short), was introduced and its fundamental properties were investigated [19]. In this paper, we define the various subclasses of context-free tree grammar (CFTG for short) by the combination of variables contained in the rules. Furthermore, we consider a monadic case of CFTG which is a special case of CFTG. Based on these definitions, we classify the subclasses of CFTG, and we investigate some inclusion properties of subclasses of CFTL (where CFTL indicates the class of context-free tree languages).

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 estimating the performances of Distributed control Dynamic Channel Assignment (DDCA) strategies in sector cell layout systems, we find that sector cell layout systems with DDCA achieved a large system capacity. Moreover, we also indicate the problem, which is the increase of occurrences of cochannel interference, raised by using DDCA in sector cell layout systems. The new channel assignment algorithm, which is called Channel Searching on Direction of Sector (CSDS), is proposed to cope with the problem. CSDS assigns nominal channels to each sector according to their direction so that the same frequency channel tends to be used in sectors having the same direction. We show, by simulations, that CSDS is an adequate algorithm for sector cell layout systems because it significantly improves performance on co-channel interference while only slightly decreasing system capacity.

A direct-conversion receiver with a full digital logic FSK demodulator is presented. It is developed from the quadricorrelator which is known as a frequency detector. We show that the performance of the receiver converges to that of the analog quadricorrelator receiver as the number of mixing axes increases, and obtain the optimum filter bandwidth by computer simulation.