For the obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem, we present a Steiner-point-based algorithm that achieves the best practical performance among existing heuristics. We first propose a new concept of Steiner point locations, creating a linear-space routing graph with satisfactory Steiner point candidates to resolve the bottleneck of most existing heuristics. Then, we propose a Steiner-point-based framework to yield a solution, which is close to the key to the handling of the OARSMT problem. Experimental results show that this algorithm achieves excellent solution quality and speed performance at the same time. We also extend the Steiner-point-based framework to the obstacle-avoiding preferred direction Steiner tree problem with a good performance.

This paper predicts programspsila effect of time-domain electromagnetic interference (EMI) on a simple microcontroller. Using the instruction current concept and a modified instruction set simulator (ISS) for this purpose, this paper can predict, in the time domain, accurate conducted EMI behaviors when different programs are running on this system. Different program codespsila EMI behaviors are predicted, and all of these codes fit well with the measurement results. The modified ISS is adapted to estimate the pipeline effect of a microcontroller and to give an accurate current profile of any complex multi-instruction program. By using the instruction current model and the proposed ISS, this paper can predict the EMI behavior of a very complex program-a simple home-made operating system (OS) kernel. To the best of our knowledge, this paper is the first work on observation and prediction of EMI behavior of an embedded system OS kernel.

We propose the application of cosine windowing for the orthogonal frequency-division multiplexing (OFDM) systems to self-cancel intercarrier interference (ICI) in fast time-varying channels prior to receptions. With a time-domain cosine window immediately after the inverse discrete Fourier transform (IDFT) unit in OFDM transmitters, the ICI fractions from adjacent subcarriers significantly cancel one another at the expense of the orthogonality violation among subcarriers in the main lobe. As a result, the frequency-domain channel matrix reshaped by the cosine windowing can be closely approximated to a strictly banded matrix. In the complex exponential basis expansion model (CE-BEM), we present the estimation of the channel matrix with the assistance of the pilot clusters. Simulation results show that the receivers implementing the CE-BEM channel estimation and the low-complexity block turbo minimum mean square error (MMSE) equalization perform with considerably lower bit error rates (BER) even in very fast time-varying channels.

For the obstacle-avoiding rectilinear Steiner minimal tree problem, this paper presents an O(n log n)-time algorithm with theoretical optimality guarantees on a number of specific cases, which required O(n3) time in previous works. We propose a new framework to directly generate O(n) critical paths as essential solution components, and prove that those paths guarantee the existence of desirable solutions. The path-based framework neither generates invalid initial solutions nor constructs connected routing graphs, and thus provides a new way to deal with the OARSMT problem. Experimental results show that our algorithm achieves the best speed performance, while the average wirelength of the resulting solutions is only 1.1% longer than that of the best existing solutions.