This paper introduces an adaptive distributed routing algorithm for the faulty star graph. The algorithm is based on that the n-star graph has uniform node degree n-1 and is n-1-connected. By giving two routing rules based on the properties of nodes, an optimal routing function for the fault-free star graph is presented. For a given destination in the n-star graph, n-1 node-disjoint and edge-disjoint subgraphs, which are derived from n-1 adjacent edges of the destination, can be constructed by this routing function and the concept of Breadth First Search. When faults are encountered, according to that there are n-1 node-disjoint paths between two arbitrary nodes, the algorithm can route messages to the destination by finding a fault-free subgraphs based on the local failure information (the status of all its incident edges). As long as the number f of faults (node faults and/or edge faults) is less than the degree n-1 of the n-star graph, the algorithm can adaptively find a path of length at most d+4f to route messages successfully from a source to a destination, where d is the distance between source and destination.

The Future Public Land Mobile Telecommunication Systems (FPLMTS) standards have made it quite clear that in the near future, the capability in doing wireless data transmission will become necessary in order to make the tether-free use of multimedia applications possible. CDMA is considered the most appropriate and probable radio access method of FPLMTS for its high capacity and flexibility in accommodation of multimedia and variable rate users. In order to further increase the capacity of CDMA system, several techniques have been studied and proposed such as an interference canceller and adaptive array antenna. We propose the novel multi-user detection type interference cancellation technique named SRIC (Symbol Ranking type IC) in this paper. SRIC is very feasible for its small amount of operation compared with other multi-user detection type ICs and can be added to a base station with slight alteration according to the requirement of higher capacity. The performance of SRIC depends on the method of calculating the likelihood. We studied three methods. In order to reduce the operations, we tried to propose two more methods. We confirmed that SRIC can make the system capacity about three times greater than that of a conventional RAKE receiver. We also confirmed that SRIC can be reduce its operations very much at some sacrifice of their performance. There are nine variants of SRIC, which have a trade off between performance and amount of operation. We can choose one of them which is most fit to our requirement. The first operation of SRIC is common with that of a conventional RAKE receiver. Therefore, SRIC can be introduced to conventional systems afterwards by inserting the interference canceller block which functions replica generation, removal, and ranking between output of a RAKE receiver and FEC decoder.

Direct sequence code division multiple access (DS-CDMA) is attractive for mobile radio use because of its inherently high capacity. There is great demand for mobile radio to offer multimedia services. This means that various service rates and qualities should be supported. DS-CDMA systems are flexible and can accommodate various user rates easily so these demands can be met. As many users will occupy the same frequency band simultaneously, the traffic capacity of a DS-CDMA system is determined by interference power. Interference cancellation is one of the important techniques in decreasing interference power at the demodulation stage and thus increasing traffic capacity. In this paper, we propose the delayed symbol combining interference canceller which can suppress the interference from various users sending at different information rates. Performance of the proposed method is calculated by computer simulations. Furthermore, the effect of adding forward error correction to the proposed canceller is also evaluated by computer simulations. In the quasi static flat fading environment, it is found that the Eb/No degradation due to interference is suppressed to 3 dB at BER=10-3 with 24 users. In the quasi static frequency selective fading environment, it is found that the required Eb/No of the frequency selective fading canceller is about 11 dB better than that of the flat fading canceller for the target BER of 10-3. It is found that BER<10-3 is achieved with forward error correction and bit interleaving even when the maximum Doppler frequency normalized by low data bit rate is 0. 0008 and Eb/No is 20 [dB] in frequency selective fading and 30 [dB] in flat fading.

A single-chip GaAs Transmit/Receive (T/R)-MMIC front-end has been developed which is applicable to 1. 9-GHz personal communication terminals such as digital cordless phones. This chip is fabricated using a planar self-aligned gate FET useful for low-cost and high-volume production. The chip integrates RF front-end analog circuits a power amplifier, a T/R-switch, and a low-noise amplifier. Additionally integrated are a newly developed voltage-doubler negative-voltage generator (VDNVG) and a control logic circuit to control transmit and receive functions, enabling both a single-voltage operation and an enhanced power handling capability of the switch, even under a single low-voltage supply condition of 2 V. The power amplifier incorporated onto the chip is capable of delivering a 21 dBm output power at a 39% efficiency, and a 30 dB associated gain with a 2 V single power supply in the transmit mode. The gain and efficiency are higher than those of the previously reported amplifier operating with a 2 V single power supply. The VDNVG produces a step-up voltage of 2. 9 V as well as a negative voltage of -1. 8 V from a 2 V power supply, operating with a charge time of less than 0. 25 µs. The control logic circuit on the chip has a newly designed interface circuit utilizing the step-up voltage and negative voltage, thereby enabling the chip to handle high power outputs over 24 dBm with a low operating voltage of 2 V. In the receive mode, a 1. 7 dB noise figure and a 0. 6 dB insertion loss are achieved with a current dissipation of 3. 6 mA. The developed MMIC, which is the first reported 2 V single-voltage operation T/R-MMIC front-end, is expected to contribute to the size and weight reductions in personal communication terminals.

Huynen has already provided a method to decompose a Mueller matrix in order to retrieve detailed target information in a polarimetric radar system. However, this decomposition sometimes fails in the presence of small error or noise in the elements of a Mueller matrix. This paper attempts to improve Huynen's decomposition method. First, we give the definition of stable decomposition and present an example, showing a problem of Huynen's approach. Then two methods are proposed to carry out stable decompositions, based on the nonlinear least square method and the Newton's method. Stability means the decomposition is not sensitive to noise. The proposed methods overcomes the problems on the unstable decomposition of Mueller matrix, and provides correct information of a target.

We propose a fault-tolerant routing algorithm for 2D meshes. Our routing algorithm can tolerate any number of concave fault regions. It is based on xy-routing and uses the concept of the fault ring/chain composed of fault-free elements surrounding faults. Three virtual channels per physical link are used for deadlock-free routing on a fault ring. Four virtual channels are needed for a fault chain. For a concave fault ring, fault-free nodes in the concave region have been deactivated to avoid deadlock in the previous algorithms, which results in excessive loss of the computational power. Our algorithm ensures deadlock-freedom by restricting the virtual channel usage in the concave region, and it minimizes the loss of the computational power. We also extend the proposed routing scheme for adaptive fault-tolerant routing. The adaptive version requires the same number of virtual channels as the deterministic one.

For a given N-vertex graph H, a graph G obtained from H by adding t vertices and some edges is called a t-FT (t-fault-tolerant) graph for H if even after deleting any t vertices from G, the remaining graph contains H as a subgraph. For the n-dimensional cube Q(n) with N vertices, a t-FT graph with an optimal number O(tN+t2) of added edges and maximum degree of O(N+t), and a t-FT graph with O(tNlog N) added edges and maximum degree of O(tlog N) have been known. In this paper, we introduce some t-FT graphs for Q(n) with an optimal number O(tN+t2) of added edges and small maximum degree. In particular, we show a t-FT graph for Q(n) with 2ctN+ct2((logN)/C)C added edges and maximum degree of O(N/(logC/2N))+4ct.

To further increase the capacity of the DS-CDMA reverse-link, this paper investigates the effectiveness of interference rejection weight control (IRWC) for the pilot symbol-assisted coherent multistage interference canceller (PSA-COMSIC) using recursive channel estimation (RCE). First, a bit error rate (BER) expression of the serial (successive) and parallel type hard decision multistage interference canceller (MSIC) with IRWC using Gaussian approximation for multiple access interference (MAI) are presented for no fading channels. It is theoretically shown that IRWC is effective in mitigating the interference replica generation error in hard decision MSIC. Next, the BER performance of PSA-COMSIC using IRWC in a multipath Rayleigh fading channel when channel coding is applied is evaluated by computer simulations. The BER performance and capacity are evaluated not only for the conventional serial and parallel types but also for serial/parallel (S/P) hybrid type and non-linear/linear (N/L) hybrid type schemes, both of which are effective in significantly reducing the demodulation processing delay. The simulation results demonstrate that, in interference-limited channels where the back ground noise is negligible, the capacity of serial type PSA-COMSIC using IRWC is about 10% higher than that without IRWC. It is also found that if we can accept a slight capacity degradation compared to the serial type PSA-COMSIC, S/P hybrid schemes are effective in reducing the demodulation processing delay.

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 have proposed a non-invasive method for diagnosis of the early stage of atherosclerosis, namely, the detection of small vibrations on the aortic wall near the heart by using ultrasound diagnostic equipment. It is, however, necessary to confirm the effectiveness of such measurement of the pulse wave velocity for quantitative evaluation of the local characteristics of atherosclerosis. It is well known that Young's modulus of a tube wall, estimated from measured pulse wave velocity, depends on inner pressure because of the non-linear relationship between the inner pressure and the change of volume in the tube. The inner pressure, however, changes during the period of one heartbeat. In this experimental study, we found for the first time that Young's modulus of the tube wall, estimated from the measured pulse wave velocity, depends not only on the diastolic pressure but also on the pulse pressure and the pressure gradient of the systolic period.

Weighted Round Robin (WRR) scheduling is an extension of round robin scheduling. Because of its simplicity and bandwidth guarantee, WRR cell scheduling is commonly used in ATM switches. However, since cells in individual queues are sent cyclically, the delay bounds in WRR scheduling grow as the number of queues increases. Thus, static priority scheduling is often used with WRR to improve the delay bounds of real-time queues. In this paper, we show that the burstiness generated in the network is an even greater factor affecting the degradation of delay bounds. In ATM switches with per-class queueing, a number of connections are multiplexed into one class-queue. The multiplexed traffic will have a burstiness even if each connection has no burstiness, and when the multiplexed traffic is separated at the down stream switches, the separated traffic will have a burstiness even if the multiplexed traffic has been shaped in the upstream switches. In this paper, we propose a new WRR scheme, namely, WRR with Save and Borrow (WRR/SB), that helps improving the delay bound performance of WRR by taking into account the burstiness generated in the network. We analyze these cell scheduling methods to discuss their delay characteristics. Through some numerical examples, we show that delay bounds in WRR are mainly dominated by the burstiness of input traffic and, thus WRR/SP, which is a combination of WRR and static priority scheduling, is less effective in improving delay bounds. We show that WRR/SB can provide better delay bounds than WRR and that it can achieve the same target delay bound with a smaller extra bandwidth, while large extra bandwidth must be allocated for WRR.

Let T1, , Tn be n spanning trees rooted at node r of graph G. If for any node v, n paths from r to v, each path in each spanning tree of T1, , Tn, are internally disjoint, then T1, , Tn are said to be independent spanning trees rooted at r. A graph G is called an n-channel graph if G has n independent spanning trees rooted at each node of G. We generalize the definition of n-channel graphs. If for any node v of G, among the n paths from r to v, each path in each spanning tree of T1, , Tn, there are k internally disjoint paths, then T1, , Tn are said to be (k,n)-independent spanning trees rooted at r of G. A graph G is called a (k,n)-channel graph if G has (k,n)-independent spanning trees rooted at each node of G. We study two fault-tolerant communication tasks in (k,n)-channel graphs. The first task is reliable broadcasting. We analyze the relation between the reliability and the efficiency of broadcasting in (k,n)-channel graphs. The second task is secure message distribution such that one node called the distributor attempts to send different messages safely to different nodes. We should keep each message secret from the nodes called adversaries. We give two message distribution schemes in (k,n)-channel graphs. The first scheme uses secret sharing, and it can tolerate up to t+k-n listening adversaries for any t < n if G is a (k,n)-channel graph. The second scheme uses unverifiable secret sharing, and it can tolerate up to t+k-n disrupting adversaries for any t < n/3 if G is a (k,n)-channel graph.

Co-channel interference is a major deteriorating factor limiting the capacity of mobile communication systems. To mitigate the effect of the interference, a kind of nonlinear interference canceller named trellis-coded co-channel interference canceller (TCC) has been proposed. In TCC the trellis-coded modulation (TCM) is introduced to both the desired signal and the interference signal in order to enhance the cancelling performance. In this paper, the bit error rate (BER) performance of TCC in static channel is theoretically evaluated for the first time. An equivalent TCM (E-TCM) model is firstly established, and a BER asymptotic estimate (AE) and a BER upper bound (UB) of TCC are then evaluated respectively by analyzing E-TCM. In the evaluation of AE, the BER performance is calculated as a function of phase difference between the desired signal and the interference signal (φ), subsequently the average BER performance over φ can be evaluated. The UB of BER is calculated using a transfer function based on the matrix representation. This paper also demonstrates that AE gives higher accuracy and less calculation complexity than UB. Performance comparisons reveal the consistency of these theoretical results with that of computer simulations.

In this paper, we propose a technique to synthesize a hardware circuit from a protocol specification consisting of several concurrent EFSMs with multi-rendezvous specified among their subsets. In our class, each multi-rendezvous can be specified among more than two EFSMs, and several multi-rendezvous can be specified for different combinations of EFSMs. In the proposed technique, using the information such as current states of EFSMs, input values at external gates and guard expressions, we compose a circuit to evaluate whether each multi-rendezvous can be executed. If several exclusive multi-rendezvous get executable simultaneously for some combinations of EFSMs, we select one of them according to the priority order given in advance. We compose such a circuit as a combinational logic circuit so that it works fast. By applying our technique to Abracadabra protocol specified in LOTOS, it is confirmed that the derived circuit handles multi-rendezvous efficiently.

Digital signal processors (DSPs) usually employ indirect addressing using an address register (AR) to indicate their memory addresses, which often introduces overhead codes in AR updates for next memory accesses. In this paper, AR update scheme is extended such that address can be efficiently modified by 2 in addition to conventional 1 updates. An automatic address allocation method of program variables for this new addressing model is presented. The method formulates program variables and AR modifications by a graph, and extracts a maximum chained triangle graph, which is accessed only by AR 1 and 2 operations, so that the estimated number of overhead codes is minimized. The proposed methods are applied to a DSP compiler, and memory allocations derived for several examples are compared with memory allocations by other methods.

In this paper, we propose an interference canceller for asynchronous DS-CDMA. The principle is based on parallel cancellation using soft decision(PCSD), however, we propose to add an operation to suppress the strength of interfering signals replica on PCSD. We show here that this operation plays a very important theoretical role in PCSD, and that the performance of our proposed scheme approaches that of a perfect decorrelating detector under certain conditions. With this theoretical background in mind, we named this scheme the "Near-Decorrelating Multistage Detector"(NDMD). To demonstrate NDMD performance, we performed two kinds of computer simulations. In the first kind of simulation, simple conditions are assumed in order to evaluate basic cancelling performance. In the other kind of simulation, essential techniques for CDMA cellular systems such as FEC, transmission power control(TPC), and base band filtering were implemented while taking into account NDMD as applied to such systems. These simulations numerically demonstrate that NDMD is very efficient in cancelling out interference and that it improves asynchronous DS-CDMA performance.

Multicasting is an important feature for any switching network being intended to support broadband integrated services digital networks (B-ISDN). This paper proposes an improved multicast packet switch based on Lee's nonblocking copy network. The improved design retains the desirable features of Lee's network including its nonblocking property while adopting techniques to overcome the various limitations mentioned in various literature. The proposed network architecture utilizes d-dilated banyan networks to increase the amount of cells that can be replicated within the copy network. Cell splitting is used to optimize the utilization of the network's available bandwidth. Furthermore, the proposed architecture allows for the modular expansion in capacity to accomodate changing traffic patterns. The modular design of the proposed switch likewise offers easy handling and replacement of faulty modules.

This paper presents a practical fault-tolerant architecture for mesh parallel machines that has t spare processors and has 2(t+2) communication links per processor while tolerating at most t+1 processor and link faults. We also show that the architecture presented here can be laid out efficiently in a linear area with wire length at most O(t).

In this paper, a dynamic constructive algorithm for fault tolerant feedforward neural network, called DCFTA, is proposed. The algorithm starts with a network with single hidden neuron, and a new hidden unit is added dynamically to the network whenever it fails to converge. Before inserting the new hidden neuron into the network, only the weights connecting the new hidden neuron to the other neurons are trained (i. e. , updated) until there is no significant reduction of the output error. To generate a fault tolerant network, the relevance of each synaptic weight is estimated in each cycle, and only the weights which have their relevance less than a specified threshold are updated in that cycle. The loss of a connections between neurons (which are equivalent to stuck-at-0 faults) are assumed. The simulation results indicate that the network constructed by DCFTA has a significant fault tolerance ability.

Considering the pattern classification/recognition tasks, the influence of the activation function on fault tolerance property of feedforward neural networks is empirically investigated. The simulation results show that the activation function largely influences the fault tolerance and the generalization property of neural networks. It is found that, neural networks with symmetric sigmoid activation function are largely fault tolerant than the networks with asymmetric sigmoid function. However the close relation between the fault tolerance and the generalization property was not observed and the networks with asymmetric activation function slightly generalize better than the networks with the symmetric activation function. First, the influence of the activation function on fault tolerance property of neural networks is investigated on the XOR problem, then the results are generalized by evaluating the fault tolerance property of different NNs implementing different benchmark problems.