This paper proposes a multiple open-loop frequency estimation scheme based on differential detection for M-ary phase shift keying (MPSK), which accomplishes fast initial acquisition, precise frequency estimation and wide frequency coverage at the same time. The proposed scheme, which has a good trade-off between complexity and performance, operates as follows: 1) it consists of several frequency error detectors (FEDs) based on differential detection with different delays; 2) it precisely estimates frequency in a wide range (the same range of one symbol differential detection) by open-loop according to frequency errors detected by the FEDs. For real-time symbol-by-symbol operation in order to track fast time-varying frequency, it has a smaller complexity than the other frequency estimation schemes. It is confirmed by analysis, numerical calculation and computer simulation that the frequency estimation error of the proposed scheme is close to the Cramer-Rao lower bound (CRLB) (asymptotic degradation of the proposed scheme from the CRLB is about 0. 5 dB) while keeping a wide frequency coverage and this scheme can track fast time-varying frequency.

In many embedded systems, a significant amount of power is consumed for off-chip driving because off-chip capacitances are much larger than on-chip capacitances. This paper proposes instruction scheduling techniques to reduce power consumed for off-chip driving. The techniques minimize the switching activity of a data bus between an on-chip cache and a main memory when instruction cache misses occur. The scheduling problem is formulated and two scheduling algorithms are presented. Experimental results demonstrate the effectiveness and the efficiency of the proposed algorithms.

The datapath width of a core processor has a strong effect on cost, power consumption, and performance of an embedded system integrated with memories into a single-chip. However, it is difficult for designers to appropriately determine the datapath width for each application because of the limited reusability of software and the lack of compilation techniques. The purpose of this paper is to clarify supports required from software for the optimal datapath width determination. As a solution, an embedded programming language, called Valen-C, and a retargetable Valen-C compiler are proposed. In this paper, the syntax and semantics of Valen-C along with the mechanism of the Valen-C retargetable compiler and how to preserve the accuracy of computation of programs in relation to various datapath widths are also described. Experiments with practical applications show that the total cost of the system including a core processor, ROM, and RAM is drastically reduced with little performance loss by reducing the datapath width.

This paper presents a new binding algorithm for a retargetable compiler which can deal with diverse architectures of application specific embedded processors. The architectural diversity includes a "non-orthogonal" datapath configuration where all the registers are not equally accessible by all the functional units. Under this assumption, binding becomes a hard task because inadvertent assignment of an operation to a functional unit may rule out possible assignment of other operations due to unreachability among datapath resources. We propose a new BDD-based algorithm to solve this problem. While most of the conventional methods are based on the covering of expression trees obtained by decomposing DFGs, our algorithm works directly on the DFGs so as to avoid infeasible bindings. In the experiments, a feasible binding which satisfies the reachability is found or the deficiency of datapath is detected within a few seconds.

In this paper, we propose and evaluate the performance of Wireless ATM MAC layer protocol to support efficiently various ATM traffics, such as CBR, VBR, ABR and UBR, in wireless ATM network environments for reverse and forward link. The proposed MAC protocol could extend efficiently the service discipline of ATM traffics from wired network to wireless ATM network environments. Thus, available bandwidth, which is remained except the bandwidth for CBR and VBR traffics, could be effectively allocated to ABR and UBR traffics. Especially, in view of reverse link, two-phase scheduling algorithm supports successfully variable characteristics of VBR traffic. And, in view of forward link, 'Wireless Dynamic Weighted Earliest Deadline First' scheduling algorithm minimizes the mean cell delay and required buffer size. Simulation results show that proposed method provides effective performance in wireless ATM environments.

This paper proposes two types of acceleration parameters for the Durand-Kerner method and its variant, where the values of parameters are determined at each iteration step. Numerical examples are also shown.

In this paper, we discuss the initial acquisition of the code division multiplexed DS/SS down-link signals at a user terminal of multiple LEO mobile satellite communication systems. In LEO systems, a receiver generally receives signals from plural satellites for soft hand-off and for satellite diversity as a countermeasure to shadowing. In this situation, the signal from each satellite becomes the interference to the signals from other satellites. In addition to this inter-satellite interference, we have to consider the intra-satellite interference from user channels to a pilot channel because of the loss of orthogonality of channels at initial acquisition stage especially under frequency offsets due to Doppler effect. Thus in this paper, we analytically evaluate the performance of an initial acquisition scheme, taking the intra/inter-satellite interference under Doppler shift into account.

In this paper, we describe the implementation of the proposed single user type CDMA adaptive interference canceller (AIC) with RAKE structure in the developed testbed for the base station, and evaluate its performance in the multiuser and multipath fading environment. Laboratory experiment demonstrates that the AIC receiver is much more near-far resistant than the conventional matched filter (MF) receiver in the multiuser case. When the power of the other users is 6 dB larger than that of the desired user, the AIC receiver can achieve the BER of 10-3 at C/PG = 33. 3 % in the 2-path fading channel, while the MF receiver cannot achieve the BER at C/PG of more than 20. 8%. Furthermore, we evaluate the effect of transmission power reduction in the transmitter with transmission power control (TPC). The experimental result shows that the required transmission power can be greatly reduced by 3. 0 dB and 9. 2 dB with the AIC receiver at C/PG = 29. 2 % and 33. 3%, respectively.

Reducing communication overhead is a key goal of program optimization for current scalable multiprocessors. A well-known approach to achieving this is to map tasks (indivisible units of computation) to processors so that communication and computation overlap as much as possible. In an earlier work, we developed a look-ahead scheduling heuristic for efficiently reducing communication overhead with the aim of decreasing the completion time of a given parallel program. In this paper, we report on an extension of the algorithm, which fills in the idle time slots created by interprocessor communication without increasing the algorithm's time complexity. The results of experiments emphasize the importance of optimally filling idle time slots in processors.

CEFLAR is one way of realizing ATM-ABR with no cell loss. This paper shows that the transition characteristics of CEFLAR(transition time to achieve fair share), important when addressing network fairness, strongly depend on the acceleration-ratio coefficient, not the rate decrease factor or the distance between source and congestion estimation nodes. This paper also shows that the average throughput of a transmission line in transition degrades as the rate decrease factor decreases and as the distance between the source and congestion estimation nodes increases.

Array redistribution is required very often in programs on distributed memory parallel computers. It is essential to use efficient algorithms for redistribution, otherwise the performance of programs may degrade considerably. In this paper, we focus on automatic generation of communication routines for multi-dimensional redistribution. The principal advantage of this work is to gain the ability to handle redistribution between arbitrary source and destination processor sets and between arbitrary source and destination distribution schemes. We have implemented these algorithms using Parallelware communication library. Some experimental results show the efficiency and flexibility of our techniques compared to the other redistribution works.

This paper proposes a scalable multiecho cancellation system based on multiple autonomic and distributed echo canceler units. The proposed system does not have any common control section. Distributed control sections are equipped with in multiple echo cancelers operating autonomically. Necessary information is transferred from one unit to the next one. When the number of echoes to be canceled is changed, the necessary number of echo canceler units, each of which may be realized on a single chip, are simply plugged in or unplugged. The proposed system also provides fast convergence thanks to the novel coefficient location algorithm which consists of flat-delay estimation and constrained tap-position control. The input signal is evaluated at each tap to determine when to terminate flat-delay estimation. The number of exchanged taps is selected larger in flat-delay estimation than in constrained tap-position control. The convergence time with a colored-signal input is reduced by approximately 50% over STWQ, and 80% over full-tap NLMS algorithm. With a real speech input, the proposed system cancels the echo by about 20 dB. Tap-positions have been shown to be controlled correctly.

In this paper, we consider linear subcodes of RMr,m whose bases are formed from the monomial basis of RMr,m by deleting ΔK monomials of degree r where ΔK < . For such subcodes, a procedure for computing the number of minimum weight codewords is presented and it is shown how to delete ΔK monomials in order to obtain a subcode with the smallest number of codewords of the minimum weight. For ΔK 3, a formula for the number of codewords of the minimum weight is presented. A (64,40) subcode of RM3,6 is being considered as an inner code in a concatenated coding system for NASA's high-speed satellite communications. For (64,40) subcodes, there are three equivalent classes. For each class, the number of minimum weight codewords, that of the second smallest weight codewords and simulation results on error probabilities of soft-decision maximum likelihood decoding are presented.

An efficient hybrid scheme has been developed for optimizing register allocation applicable to CISC and RISC processors, which is crucial for maximizing their execution speed. Graph-coloring at the function level is combined with a powerful local register assigner. This assigner uses accurate program flows and access patterns of variables, and optimizes a wider local range, called an extended basic-block (EBB), than other optimizing compilers. The EBB is a set of basic-blocks that constitute a tree-shaped control flow, which is suitable for the large nested branches that frequently appear in embedded system-control programs, such as those for telephone call processing. The coloring at the function level involves only the live-ranges of program variables that span EBBs. The interference graph is therefore very small even for large functions, so it can be constructed quickly. Instead of iterative live-range splitting or spilling, the unallocated live-ranges are optimized by the EBB-based register assigner, so neither load/store insertion nor code motion is needed. This facilitates generating reliable code and debug symbols. The information provided for the EBB-based assigner facilitates the priority-based heuristics, fine-grained interference checking, and deferred coloring, all of which increase the colorability. Using a thread-support package for CHILL as a sample program, performance measurement showed that local variables are successfully located in registers, and the reduction of static cycles is about 20-30%. Further improvements include using double registers and improving debuggability.

Exception handling is not only useful for increasing program readability, but also provides an effective means to check and locate errors, so it increases productivity in large-scale program development. Some typical and frequent program errors, such as out-of-range indexing, null dereferencing, and narrowing violations, cause exceptions that are otherwise unlikely to be caught. Moreover, the absence of a catcher for exceptions thrown by API procedures also causes uncaught exceptions. This paper discusses how the exception handling mechanism should be supported by the compiler together with the operating system and debugging facilities. This mechanism is implemented in the compiler by inserting inline check code and accompanying propagation code. One drawback to this approach is the runtime overhead imposed by the inline check code, which should therefore be optimized. However, there has been little discussion of appropriate optimization techniques and efficiency in the literature. Therefore, a new solution is proposed that formulates the optimization problem as a common assertion elimination (CAE). Assertions consist of check code and useful branch conditions. The latter are effective to remove redundant check code. The redundancy can be checked and removed precisely with a forward iterative data flow analysis. Even in performance-sensitive applications such as telecommunications software, figures obtained by a CHILL optimizing compiler indicate that CAE optimizes the code well enough to be competitive with check suppressed code.

A fault-tolerant wormhole routing algorithm on mesh-connected processors is proposed. The proposed algorithm is based on the solid fault model and allows the fault polygons to be overlapped. The algorithm compares the position of fault region relative to current channel with the fault direction field of a misrouted message to route around overlapped fault polygons. A node deactivating algorithm to convert non-solid fault region into solid fault region is also proposed. The proposed routing algorithm uses four virtual channels and is deadlock and livelock free.

Recently, a trellis-based recursive maximum likelihood decoding (RMLD) algorithm has been proposed for decoding binary linear block codes. This RMLD algorithm is computationally more efficient than the Viterbi decoding algorithm. However, the computational complexity of the RMLD algorithm depends on the sectionalization of a code trellis. In general, minimization of the computational complexity results in non-uniform sectionalization of a code trellis. From implementation point of view, uniform sectionalization of a code trellis and regularity among the trellis sections are desirable. In this paper, we apply the RMLD algorithm to a class of codes which are transitive invariant. This class includes Reed-Muller (RM) codes, the extended and permuted BCH (EBCH) codes and their subcodes. For this class of codes, the binary uniform sectionalization of a code trellis results in the following regular structure. At each step of decoding recursion, the metric table construction procedure is applied uniformly to all the sections and the size and structure of each metric table are the same. This simplifies the implementation of the RMLD algorithm. Furthermore, for all RM codes of lengths 64 and 128 and EBCH codes of lengths 64 and 128 with relatively low rate, the computational complexity of the RMLD algorithm based on the binary uniform sectionalization of a code trellis is almost the same as that based on an optimum sectionalization of a code trellis.

In this paper, we propose an adaptive lattice-transversal joint (LTJ) filter structure that is quite suitable for the practical implementation of the acoustic echo canceller. The structure maintains fast convergence of the lattice structure and low computational complexity of the transversal structure simultaneously. It is particularly more efficient in memory usage than any other existing fast-convergent algorithm for the acoustic echo cancellation.

This paper describes a new architecture-based DSP processor, which consists of n n mesh multiprocessor for digital signal processing. A prototype chip, RCDSP9701 has been designed and implemented using a CMOS 0. 6 µm process. This architecture has better performance compare to the traditional microprocessor solution to Digital Signal Processing. The proposed method poses remarkable flexibility compare to ASIC (Application Specified Integrated Circuits) approach for Digital Signal Processing applications. In addition, the proposed architecture is fault tolerant and suitable for parallel computing applications. In this paper, an implementation into a silicon chip of the new architecture is presented to give a better understanding of our work.

In this paper, we propose a multiple access technique using a simple interference canceller for common code transmission. In the proposed system, we adopt a common code for a receiver oriented system. All the transmitters utilize the same pseudo noise (PN) code to communicate with a receiver. Here the receiver structure becomes very simple with only one matched filter (MF). The proposed system has two very important merits. One is to avoid packet collisions by means of an interference cancellation method based on a common code chip shift transmission technique. That is, in order to avoid interference, which occurs because all the received signals have the same PN code, the same data with different timing are transmitted in two channels. In this study, we define and evaluate three types of packet collision which can be reduced by the canceller. The other merit is to reduce the system degradation due to the correlation side-lobes by means of a side-lobe canceller. In spread spectrum (SS) communication systems with PN codes like M-sequences, the correlation side-lobes appear at the detector in the case of the polarity data changing from 1 to 1 . The side-lobes degrade the system quality. Therefore in this system a interference canceller operates to cancel the correlation side-lobes and attempts to reduce the system degradation. Finally, by our cancellation method it becomes possible to realize a simple multiple access using only one PN code under the condition of a receiver oriented system without a base station.