First, we show that the necessary and sufficient condition for the existence of a balanced bowtie decomposition of the complete tripartite multi-graph λ Kn1,n2,n3 is (i) n1=n2=n3 0 (mod 6) for λ 1,5 (mod 6), (ii) n1=n2=n3 0 (mod 3) for λ 2,4 (mod 6), (iii) n1=n2=n3 0 (mod 2) for λ 3 (mod 6), and (iv) n1=n2=n3 2 for λ 0 (mod 6). Next, we show that the necessary and sufficient condition for the existence of a balanced trefoil decomposition of the complete tripartite multi-graph λ Kn1,n2,n3 is (i) n1=n2=n3 0 (mod 9) for λ 1,2,4,5,7,8 (mod 9), (ii) n1=n2=n3 0 (mod 3) for λ 3,6 (mod 9), and (iii) n1=n2=n3 3 for λ 0 (mod 9).

A new architecture-based Dynamically Programmable Arithmetic Array processor (DPAA) is proposed for general purpose Digital Signal Processing applications. Parallelism and pipelining are achieved by using DPAA, which consists of various basic arithmetic blocks connected through a code-division multiple access bus interface. The proposed architecture poses 100% interconnection flexibility because connections are done virtually through code matching instead of physical wire connections. Compared to conventional multiplexing architectures, the proposed interconnection topology consumes less chip area and thus, more arithmetic blocks can be incorporated. A 16-bit prototype chip incorporating 10 multipliers and 40 other arithmetic blocks had been implemented into a 4.5 mm 4.5 mm chip with 0.6 µm CMOS process. DPAA also features its simple programmability, as numerical formula can be used to configure the processor without programming languages or specialized CAD tools.

Autonomous distributed scheduling is based on the autonomous decentralized optimization and recently focused as one of flexible scheduling techniques which can more cope with dynamically changing situation than traditional ones. This paper proposes an autonomous distributed scheduling scheme for the parallel machine scheduling problem. Through computer simulation, we observe that our proposed scheme can more quickly reduce the total deadline over-time than one in the literature and can adapt flexibly to unusual situation (addition of jobs).

The k-vertex-connectivity augmentation problem for a specified set of vertices of a graph with degree-unchangeable vertices, kVCA(G,S,D), is defined as follows: "Given a positive integer k, an undirected graph G=(V,E), a specified set of vertices S V and a set of degree-changeable vertices D V, find a smallest set of edges E such that the vertex-connectivity of S in (V,E E) is at least k and E {(u,v) u,v D}. " The main result of the paper is that checking the existence of a solution and finding a solution to 2VCA(G,S,D) or 3VCA(G,S,D) can be done in O(|V|+|E|) or O(|V|(|V|+|E|)) time, respectively.

For the purpose of equalisation of rapidly time variant multipath channels, we derive a novel adaptive algorithm, the amplitude banded LMS (ABLMS), which implements a non-linear adaptation based on a coefficient matrix. Then we develop the ABLMS algorithm as the adaptation procedure for a linear transversal equaliser (LTE) and a decision feedback equaliser (DFE) where a parallel adaptation scheme is deployed. Computer simulations demonstrate that with a small increase of computational complexity, the ABLMS based parallel equalisers provide a significant improvement related to the conventional LMS DFE and the LMS LTE in the case of a second order Markov communication channel model.

Optimization procedure on higher order Delta-sigma (ΔΣ) modulator coefficients is proposed. The procedure is based on the higher order ΔΣ modulator stability judgement method. The application specification can be satisfied with the proposed method. The 4th order modulator examples are illustrated. Optimized coefficients and its behavior model simulation results demonstrated that this methodology is suitable for the design of higher order ΔΣ AD converter. The coefficients tolerance up to 2% is allowed for switched-capacitor implementation, with not more than 3.5 dB SNR (Signal to Noise Ratio) degradation. The optimized coefficients improves 2 to 3 bit of the modulator's resolution than the previous proposed algorithm, and remains the stable input limit satisfies the original design requirement.

This paper presents a fast algorithm for calculating box splines sampled at regular intervals. This algorithm is based on the representation by directional summations, while splines are often represented by convolutions. The summation-based representation leads less computational complexity: the proposed algorithm requires fewer additions and much fewer multiplications than the algorithm based on convolutions. The proposed algorithm is evaluated in the sense of the number of additions and multiplications for three- and four-directional box splines to see how much those operations are reduced.

Recently, Vatan, Roychowdhury and Anantram have presented two types of revised versions of the Calderbank-Shor-Steane code construction, and have also provided an exhaustive procedure for determining bases of quantum error-correcting codes. In this paper, we investigate the revised versions given by Vatan et al., and point out that there is no essential difference between them. In addition, we propose an efficient algorithm for searching for bases of quantum error-correcting codes. The proposed algorithm is based on some fundamental properties of classical linear codes, and has much lower complexity than Vatan et al.'s procedure.

This paper proposes an autonomous relay access algorithm that provides an intelligent wireless network structure for inter-vehicle communication systems. The proposed algorithm introduces a special classification among mobile terminals and assigns terminals to one of several terminal groups, which are adaptively and autonomously constructed according to traffic conditions. The proposed algorithm uses the terminal groups to conduct relay access transmission among terminals, and achieves a high rate of successful inter-terminal transmission. Computer simulation confirms that the proposed algorithm can achieve a lower blocking probability than that without a relay access scheme.

VCSEL output light polarization was controlled by fabricating devices on (311) substrate. Stability was improved by introducing compressive strain to the quantum wells in the active layer. In experiments, the power penalty due to polarization-dependent loss in the transmission line was negligible for both VCSELs with unstrained and strained quantum well active layers on (311)B substrate. The sensitivity at 2.5 Gbps was improved in a device with a strained active layer because the intensity noise due to the polarization instability was reduced. These characteristics are discussed and compared to calculated results.

As noncoherent direct sequence code-division multiple-access (DS-CDMA) mobile satellite communications, two typical transmission schemes are compared; one is a quasi-synchronous differential BPSK (QS-DBPSK) where orthogonal signals are used for reducing the multiple access interference and the other is M-ary orthogonal signaling (MOS) scheme where orthogonal signals are used for exploiting more efficient modulation. The performances are evaluated in additive white Gaussian noise (AWGN) and shadowed Rician fading (SRF) channels and the effects of timing misalignments in the QS-DBPSK system and the amount of Doppler shifts of a SRF channel are investigated. The results show that MOS much outperforms QS-DBPSK in the region of low system loading up to about 50% and a precise chip synchronization is required for QS-DBPSK. In a SRF channel, it is also shown that QS-DBPSK much outperforms MOS in a slow fading channel but MOS has a performance gain against the large Doppler shift.

A simplified analysis is presented for the reverse link maximum capacity trade-offs between each layer, spectrum efficiency and its multi-rate features of TDMA/W-CDMA and N-CDMA/W-CDMA overlaid systems with the perfect power control based on the measurement of signal-to-interference ratio (CIR). In order to suppress the multi-cross interference, the other important techniques used in the analysis are the ideal notch filtering and the signal level clipper for W-CDMA system transmitters and receivers. We firstly propose the concepts of the notch filtering depth and signal level clipping depth in the paper. The numerical results can be adopted as a guideline in designing the overlaid systems in the various cases as well as a means to investigate the flexibility of sharing of the spread spectrum and their feasibility in the future mobile communication system.

A modified version of the SAGE algorithm is presented for joint delay-azimuth-attenuation parameters' estimation in a multiuser DS-CDMA system. The introduced modification consists of using different time interval lengths when calculating the time correlations for optimizing the different channel parameters. This modification was proposed for the purpose of a further reduction in the algorithm's computational weight in case of receiving sufficiently resolvable waves. Specifically, we found that short interval windows are sufficient for estimating delays and azimuth angles, which is quite effective in reducing the computational burden in their optimization processes. As for the estimation of the attenuation parameters, a longer time window, equal to the preamble length, is considered for more accurate estimation. Also two other estimators are proposed. The first one combining the modified SAGE with a sequential estimation of the attenuation parameters, suitable for slowly varying channels. Another one, similar to the first, and primarily designed to alleviate the influence of present strong interferers. Through a numerical example, the performances of the three presented estimation schemes, in terms of their near-far resistance, are compared. And it is shown that the proposed second combined estimator outperforms the modified SAGE in environments with high MAI levels.

In order to increase the link capacity in the wideband direct sequence code division multiple access (W-CDMA) reverse link, employing a parallel-type coherent multi-stage interference canceller (COMSIC) is more practical than employing a serial (successive)-type due to its inherent advantage of a short processing delay, although its interference suppression effect is inferior to that of the serial-type. Therefore, this paper proposes a parallel-type COMSIC with iterative channel estimation (ICE) using both pilot and decision-feedback data symbols at each canceling stage in order to improve the interference suppression effect of the parallel-type COMSIC. Computer simulation results demonstrate that by applying the parallel-type COMSIC with ICE after FEC decoding, the capacity in an isolated cell can be increased by approximately 1.6 (2.5) times that of the conventional parallel-type COMSIC with channel estimation using only pilot symbols (the MF-based Rake receiver) at the required average transmit Eb/N0 of 15 dB, i.e. in the interference-limited channel. The results also show that, although the capacity in the isolated cell with the parallel-type COMSIC with ICE after FEC decoding is degraded by approximately 6% compared to that with the serial-type COMSIC with ICE after FEC decoding, the processing delay can be significantly decreased owing to the simultaneous parallel operation especially when the number of active users is large.

This paper proposes an inter-cell site diversity scheme based on 2-step selection combining (SC) and investigates through experimentation the effect of inter-cell site diversity in the transmit power-controlled wideband direct sequence code division multiple access (W-CDMA) reverse link. In the proposed algorithm, the decoded data sequence after soft-decision Viterbi decoding at each base station (BS) is transferred via the backhaul (wired line between BS and radio network controller (RNC) simulator) to the RNC simulator accompanied by reliability information of cyclic redundancy check (CRC) results per frame and the average signal-to-interference power ratio (SIR) calculated over the interleaving interval. The 2-step SC for each frame is performed at the RNC simulator using these two types of reliability information. We conclude from the laboratory experiments that the transmit power of a mobile station (MS) can be decreased since the selection period, TSEL, is shorter irrespective of the interleaving length, TILV, and that the required transmit power of a MS satisfying the average BER of 10-3 in inter-cell site diversity among 2 and 3 cell sites can be decreased by approximately 1.0 (0.5) dB and 1.3 (0.7) dB for fading maximum Doppler frequency fD = 5 (80) Hz, respectively, compared to a one-site connection (TILV = 80 msec, TSEL = 10 msec, path loss difference between 2 BSs and MS is 0 dB). We also confirmed by field experiments that the required transmit power of a MS in inter-cell site diversity between 2 cell sites can be decreased by approximately 2.0 dB compared to that of a one-site connection.

This paper evaluates through laboratory and field experiments the combined effect of the coherent adaptive antenna array diversity (CAAAD) receiver and signal-to-interference plus background noise ratio (SINR)-based fast transmit power control (TPC) in order to improve performance beyond that of space diversity (SD) with maximal ratio combining (MRC) in all low-to-high signal-to-interference power ratio (SIR) channels in the W-CDMA reverse link. Although the previously proposed CAAAD receiver comprising an adaptive antenna array based on the minimum mean square error (MMSE) criterion and a coherent Rake combiner was very effective in suppressing interference in low SIR (interference is severe) channels, SD employing MRC in noise limited channels (high SIR) outperformed the CAAAD because of its uncorrelated reception of fading variation due to its large antenna separation. The laboratory experimental results showed that the required average transmit signal energy per bit-to-background noise spectrum density (Eb/N0) with the CAAAD receiver using fast TPC is lower than that with an SD receiver over a wide range of maximum Doppler frequency values from fD = 5 Hz to 500 Hz in a low-to-high SIR channel. The results of the field experiments also showed that combining CAAAD and fast TPC is a powerful means to reduce severe multiple access interference (MAI) from high rate users in a low-to-high SIR environment and is more effective than using the SD receiver with the same number of antennas, i.e., the measured BER was improved by approximately one order of magnitude, when the relative transmit power of the desired user was 8 dB with two antennas at the average received SIR at the antenna input of -12 dB.

The performance of conventional error concealment (EC) is significantly affected by the method of selecting candidate motion vectors (MVs). In order to obtain more robust EC results, this letter proposes a new and efficient way to choose candidate MVs. The proposed approach systematically utilizes available neighboring MVs by exploiting a well-known spatiotemporal correlation of block MVs. Through extensive simulations with H.263, this letter demonstrates that the proposed candidate MVs provide superior concealed video quality in comparison to the best results of other existing techniques.

If there exist any two vertices in G whose distance becomes longer when a vertex u is removed, then u is defined as a hinge vertex. Finding the set of hinge vertices in a graph can be used to identify critical nodes in an actual network. A number of studies concerning hinge vertices have been made in recent years. In general, it is known that more efficient sequential or parallel algorithms can be developed by restricting classes of graphs. For instance, Chang et al. presented an O(n+m) time algorithm for finding all hinge vertices of a strongly chordal graph. Ho et al. presented a linear time algorithm for all hinge vertices of a permutation graph. In this paper, we shall propose a parallel algorithm which runs in O(log n) time with O(n) processors on CREW PRAM for finding all hinge vertices of an interval graph.

Since the traffic of NetNews is increasing, keeping all articles becomes serious problem from a viewpoint of waste of network bandwidth and the amount of disk usage. In addition, users read not all incoming articles. We have proposed several caching algorithms to overcome this problem and shown that a selective prefetch scheme gives the best system performance among the proposed ones. However, since the selective prefetch scheme employed a simple selecting policy, the scheme gave low hit ratio in some cases. Therefore, this paper intends to improve the selective prefetch scheme from a viewpoint of the amount of disk usage as well as hit ratio. In this paper, we divide the scheme into three factors: reference span, criterion, and threshold in criterion. Through simulation experiments using actual NetNews logs, we investigate the influence of the factors of the reference span and the threshold to system performance. As a result, it is shown that the reference span is more significant factor than the threshold, the selective prefetch scheme with a value around the seven days reference span keeps high hit ratio and reduces the amount of disk usage.

This paper describes a unique motion estimation and compensation (ME/MC) hardware architecture for a scene-adaptive algorithm. By statistically analyzing the characteristics of the scene being encoded and controlling the encoding parameters according to the scene, the quality of the decoded image can be enhanced. The most significant feature of the architecture is that the two modules for ME/MC can work independently. Since a time interval can be inserted between the operations of the two modules, a scene-adaptive algorithm can be implemented in the architecture. The ME/MC architecture is loaded on a single-chip MPEG-2 video encoder.