For a property π on graphs, the edge-contraction problem with respect to π is defined as a problem of finding a set of edges of minimum cardinality whose contraction results in a graph satisfying the property π. This paper gives a lower bound for the approximation ratio for the problem for any property π that is hereditary on contractions and determined by biconnected components.
Xiaoqing WEN Yoshiyuki YAMASHITA Seiji KAJIHARA Laung-Terng WANG Kewal K. SALUJA Kozo KINOSHITA
Research on low-power scan testing has been focused on the shift mode, with little consideration given to the capture mode power. However, high switching activity when capturing a test response can cause excessive IR-drop, resulting in significant yield loss due to faulty test results. This paper addresses this problem with a novel low-capture-power X-filling method by assigning 0's and 1's to unspecified bits (X-bits) in a test cube to reduce the switching activity in capture mode. This method can be easily incorporated into any test generation flow, where test cubes can be obtained during ATPG or by X-bit identification. Experimental results show the effectiveness of this method in reducing capture power dissipation without any impact on area, timing, and fault coverage.
Shin-ichiro MATSUZAWA Kazuo SATO Shuji ASO Atushi SANADA Hiroshi KUBO
A planar composite right/left-handed leaky wave antenna which operates at W-band is fabricated and its backward to forward beam scanning operation including broadside direction is confirmed experimentally. The scanning angle from 61 to 114 degrees with a frequency scanning range of 76 to 79 GHz is achieved.
This letter presents a new stable clustering architecture to reduce the number of re-clustering in MANET. Since some existing stable clustering schemes based on measured metric have certain deficiency in negative effect caused by nodes moving fast or causing ping pong effect, we introduce average connection time as major parameter to form as well as maintain cluster structure over the entire networks. From simulation results it is clear that average connection time is more adequate parameter for stable cluster architecture than other measured factors, resulting in fewer number of cluster changes than previous schemes.
David DELAUNE Josaphat Tetuko SRI SUMANTYO Masaharu TAKAHASHI Koichi ITO
The Japan Aerospace Exploration Agency (JAXA) plans to launch a geostationary satellite called Engineering Test Satellite VIII (ETS-VIII) in FY 2006. In this paper, a microstrip line array antenna, which has a very simple structure, is introduced to radiate a circularly polarized wave aiming at ETS-VIII applications. This antenna consists of a triangular conducting line with its vertexes rounded off, located above a ground plane, with a gap on one of its side to produce a circular polarization. The proposed antenna is analyzed by numerical simulations for a single element as well as for a three elements array configuration and the possibility of beam-switching in the azimuth space is experimentally confirmed in the latter case. It is found that by properly feeding the elements constituting the array antenna, for an elevation angle El = 48in Tokyo area, three beams are created in the conical-cut direction with a minimum gain more than 6.6 dBic and an axial ratio less than 3 dB.
Seungjae BAHNG Seokjoo SHIN Anders HØST-MADSEN
Motivated by the result in [12] we present a new block iterative multiuser detection algorithm utilizing the constant modulus (CM) property of data symbols. The proposed iterative detector is developed based on a constrained least square (LS) cost function and CM projection. It can be seen as an extension of least squares constant modulus algorithm [1] in a sense that it minimizes the CM and the LS cost functions iteratively. Simulation study shows that even for a reasonably small number of symbols, say around 100 received symbols, the proposed iterative detector approaches the performance of ideal MMSE detector and considerably outperforms the conventional blind detectors, such as subspace blind method [7] or MOE detector [5].
Hung-Wei WU Min-Hang WENG Yan-Kuin SU Ru-Yuan YANG Cheng-Yuan HUNG
This paper proposes a parallel coupled microstrip bandpass filter (BPF) with ring Electromagnetic Bandgap (EBG) cells on the middle layer for spurious suppression. The ring EBG cells of the middle layer add a good stopband-rejection mode to the second harmonics of the parallel coupled microstrip BPF with suppression of over -50 dB, without affecting the center frequency and insertion loss of the original designed BPF. The design of ring EBG cells is presented and verified by the experimented results.
Fumiyo FUKUMOTO Yoshimi SUZUKI
We address the problem of dealing with large collections of data, and investigate the use of automatically constructing domain specific category hierarchies to improve text classification. We use two well-known techniques, the partitioning clustering method called k-means and loss function, to create the category hierarchy. The k-means method involves iterating through the data that the system is permitted to classify during each iteration and construction of a hierarchical structure. In general, the number of clusters k is not given beforehand. Therefore, we used a loss function that measures the degree of disappointment in any differences between the true distribution over inputs and the learner's prediction to select the appropriate number of clusters k. Once the optimal number of k is selected, the procedure is repeated for each cluster. Our evaluation using the 1996 Reuters corpus, which consists of 806,791 documents, showed that automatically constructing hierarchies improves classification accuracy.
Shinichiro NISHIZAWA Friedrich LANDSTORFER Kouta MATSUMOTO Osamu HASHIMOTO
In this paper, the magnetic field properties and the dosimetry at intermediate frequency (21 kHz) for an induction heater are investigated with the coil model, which is prescribed as substitute source model in the European standard EN50366 (CENELEC). The accuracy of the magnetic field vectors and the values of the induced current density, which are achieved with the coil model, are compared with the results of a realistic model of the induction heater obtained from the equivalent source model. It is shown that the coil model coincides well for the magnitude of the magnetic field strength around the induction heater. On the other hand, the dominant field vector of the coil model differs significantly from the real induction heater, which leads to induced current densities in the body model which are three time larger. Owing to these results, the applicability of the coil model prescribed in the EN50366 is confirmed for the induction heater.
Hideki TODE ZhengYu XIE Koso MURAKAMI
At present, a demand to the technology of contents distribution by which each user can request the desired content through network is increasing. There are some merits and demerits respectively with the existing on-demand systems for contents distribution, such as the methods based on broadcast and select transfer or multicast one. In this paper, we propose a hybrid scheduling method which adaptively uses both broadcasting and multicasting in order to improve the system efficiency. Adequate channel boundary to adopt two different transfer mechanisms is found through analytical consideration. Also, performance improvement of our proposal is verified in terms of response time and request blocking rate through computer simulation.
Masayoshi NABESHIMA Kouji YATA
It is well known that TCP does not fully utilize the available bandwidth in fast long-distance networks. To solve this scalability problem, several high speed transport protocols have been proposed. They include HighSpeed TCP (HS-TCP), Scalable TCP (S-TCP), Binary increase control TCP (BIC-TCP), and H-TCP. These protocols increase (decrease) their window size more aggressively (slowly) compared to standard TCP (STD-TCP). This paper aims at evaluating and comparing these high speed transport protocols through computer simulations. We select six metrics that are important for high speed protocols; scalability, buffer requirement, TCP friendliness, TCP compatibility, RTT fairness, and responsiveness. Simulation scenarios are carefully designed to investigate the performance of these protocols in terms of the metrics. Results clarify that each high speed protocol successfully solves the problem of STD-TCP. In terms of the buffer requirement, S-TCP and BIC-TCP have better performance. For TCP friendliness and compatibility, HS-TCP and H-TCP offer better performance. For RTT fairness, BIC-TCP and H-TCP are superior. For responsiveness, HS-TCP and H-TCP are preferred. However, H-TCP achieves a high degree of fairness at the expense of the link utilization. Thus, we understand that all the proposed high speed transport protocols have their own shortcomings. Thus, much more research is needed on high speed transport protocols.
Temperature-tracking is becoming of paramount importance in modern electronic design automation tools. In this paper, we present a deterministic thermal placement algorithm for standard cell based layout which can lead to a smooth temperature distribution over the die. It is mainly based on Fiduccia-Mattheyses partition scheme and a former substrate thermal model that can convert the known temperature constraints into the corresponding power distribution constraints. Moreover, a kind of force-directed heuristic based on cells' power consumption is introduced in the above process. Experimental results demonstrate a comparatively uniform temperature distribution and show a reduction of the maximal temperature on the die.
Yang SONG Zhenyu LIU Satoshi GOTO Takeshi IKENAGA
Because of the data correlation in the motion estimation (ME) algorithm of H.264/AVC reference software, it is difficult to implement an efficient ME hardware architecture. In order to make parallel processing feasible, four modified hardware friendly ME workflows are proposed in this paper. Based on these workflows, a scalable full search ME architecture is presented, which has following characteristics: (1) The sum of absolute differences (SAD) results of 44 sub-blocks is accumulated and reused to calculate SADs of bigger sub-blocks. (2) The number of PE groups is configurable. For a search range of MN pixels, where M is width and N is height, up to M PE groups can be configured to work in parallel with a peak processing speed of N16 clock cycles to fulfill a full search variable block size ME (VBSME). (3) Only conventional single port SRAM is required, which makes this architecture suitable for standard-cell-based implementation. A design with 8 PE groups has been realized with TSMC 0.18 µm CMOS technology. The core area is 2.13 mm1.60 mm and clock frequency is 228 MHz in typical condition (1.8 V, 25).
Mitsuji MUNEYASU Osamu HISAYASU Kensaku FUJII Takao HINAMOTO
A simultaneous equations method is one of active noise control algorithms without estimating an error path. This algorithm requires identification of a transfer function from a reference microphone to an error microphone containing the effect of a noise control filter. It is achieved by system identification of an auxiliary filter. However, the introduction of the auxiliary filter requires more number of samples to obtain the noise control filter and brings a requirement of some undesirable assumption in the multiple channel case. In this paper, a new simultaneous equations method without the identification of the auxiliary filter is proposed. By storing a small number of input signals and error signals, we avoid this identification. Therefore, we can reduce the number of samples to obtain the noise control filters and can avoid the undesirable assumption. From simulation examples, it is verified that the merits of the ordinary method is also retained in the proposed method.
Shingo YAMAGUCHI Kousuke YAMADA Qi-Wei GE Minoru TANAKA
In this paper, we discuss a new property, named dead, of (dataflow) program nets. We say that a node of a program net is dead iff the node cannot fire once in any possible firing sequence, and furthermore the program net is partially dead. We tackle a problem of deciding whether a given program net is partially dead, named dead problem. Program nets can be classified into four subclasses: general, acyclic, SWITCH-less, and acyclic SWITCH-less nets. For each subclass, we give a method of solving dead problem and its computation complexity. Our results show that (i) acyclic SWITCH-less nets are not partially dead; (ii) for SWITCH-less nets, dead problem can be solved in polynomial time; (iii) for acyclic nets and general nets, dead problem is intractable.
Daisuke TAKASE Tomoaki OHTSUKI
We propose optical wireless multiple-input multiple-output (OMIMO) communications to achieve high speed transmission with a compact transmitter and receiver. In OMIMO, by using zero forcing (ZF), minimum mean square error (MMSE) or other detection techniques, we can eliminate the interference from the other optical transmit antennas. In this paper, we employ ZF as the detection technique. We analyze the signal-to-interference-plus-noise ratio (SINR) and the bit error rate (BER) of the proposed OMIMO with a linear array and a square array of optical transmit and receive antennas, where we employ subcarrier multiplexing (SCM) for each optical transmit antenna. Note that the proposed OMIMO is applicable to other arrangements of optical transmit and receive antennas. We show that the proposed OMIMO system can realize MIMO multiplexing and achieve high speed transmission by correctly aligning the optical transmit and receive antennas and the transmitter semiangle.
Etsuko TOYODA Morihiko MATSUMOTO Tomoyuki FUJITA Kenichi SHIOI Kazuaki YANO Masamitsu WATANABE Toshihiro ICHINO Yoshimori MIYATA Nobuo KUWAKI
We have developed a promising method for suppressing moisture condensation that prevents insulation failures in surge protectors. By analyzing surge protectors retrieved from the field, we found that electrolytic corrosion had occurred due to the encroachment of sea salt, the application of bias voltages, and the condensation of moisture. To suppress moisture condensation, a key factor in insulation failure, we applied a previously developed humidity-control package containing water-absorbent polymer. We experimentally optimized the design and functionality of the polymer package. We found that sealing the feed-through apertures alone was not enough to suppress moisture inflow and that a relatively large amount of water-absorbent polymer was needed to prevent water condensation in environments with extremely high humidity for extended periods of time. Laboratory experiments and field tests demonstrated that our optimized package minimized humidity fluctuation and thus moisture condensation in surge protectors, thereby preventing insulation failure. Application of this method to installed surge protectors greatly reduced the insulation failure rate.
Arny ALI Takamichi INOUE Fumiyuki ADACHI
The downlink (base-to-mobile) bit error rate (BER) performance for a mobile user with relatively weak received signal in a multicarrier-CDMA (MC-CDMA) cellular system can be improved by utilizing the site diversity reception. With joint use of MMSE-based frequency domain equalization (FDE) and antenna diversity combining, the site diversity operation will increase the downlink capacity. In this paper, an expression for the theoretical conditional BER for the given set of channel gains is derived based on Gaussian approximation of the interference components. The local average BER is then obtained by averaging the conditional BER over the given set of channel gains using Monte-Carlo numerical method. The outage probability is measured from the numerically obtained cumulative distribution of the local average BER to determine the downlink capacity. Results from theoretical computation are compared to the results from computer simulation and discussed.
Atsushi KUROKAWA Hiroo MASUDA Junko FUJII Toshinori INOSHITA Akira KASEBE Zhangcai HUANG Yasuaki INOUE
In general, a corner model with best- and worst-case delay conditions is used in static timing analysis (STA). The best- and worst-case delays of a stage are defined as the fastest and slowest delays from a cell input to the next cell input. In this paper, we present a methodology for determining the parameters that yield the best- and worst-case delays when interconnect structural parameters have the minimum and maximum values with process variations. We also present analysis results of our circuit model using the methodology. The min and max conditions for the time constant are found to be (+Δw, +Δt, +Δh) & (-Δw, -Δt, -Δh), respectively. Here, +Δ or -Δ means the max or min corner value of each parameter variation, where w is the width, t is the interconnect thickness, and h is the height. Best and worst conditions for delay time are as follows: 1) given a circuit with an optimum driver, dense interconnects, and small branch capacitance, the best and worst conditions are respectively (-Δw, +Δt, +Δh) & (+Δw, +Δt, -Δh), 2) given driver and/or via resistances that are higher than the interconnect resistance, dense interconnects, and small branch capacitance, they are (-Δw, -Δt, +Δh) & (+Δw, +Δt, -Δh), and 3) for other conditions, they are (+Δw, +Δt, +Δh) & (-Δw, -Δt, -Δh). Moreover, if there must be only one condition each for the best- and worst-case delays, they are (+Δw, +Δt, +Δh) & (-Δw, -Δt, -Δh).
Chien Trinh NGUYEN Shinji SUGAWARA Tetsuya MIKI
Supporting Quality of Service (QoS) over the Internet is a very important issue and many mechanism have been already devised or are under way towards achieving this goal. One of the most important approaches is the class-based architecture, which provides a scalable mechanism for QoS support in a TCP/IP network. Class-based service differentiation can be realized without resource reservation, admission control and traffic policing. However, the resulting services are only relative. While it is, in principle, not feasible to provision for absolute guarantees without admission control and/or traffic policing, such a service can be reasonably well emulated using adaptive rate allocation at the link scheduler of routers. In this paper, we propose mechanism for link scheduler of router that achieve emulated absolute and other relative guarantees using dynamic weighted fair queueing (DWFQ) combining with class packet dropping. The weights of DWFQ are frequently adjusted to current load conditions and based on prediction of realistic class traffic. These mechanisms can realize many approaches to QoS guarantees and class-based differentiation.