Yibo FAN Xiaoyang ZENG Satoshi GOTO
Integer Motion Estimation (IME) costs much computation in H.264/AVC video encoder. 2-D SAD tree IME architecture provides very high performance for encoder, and it has been used by many video codec designs. This paper proposes an optimized hardware design of 2-D SAD tree IME. Firstly, a new hardware architecture is proposed to reduce on-chip memory size. Secondly, a new search pattern is proposed to fully use memory bandwidth and reduce external memory access. Thirdly, the data-path is redesigned, and the performance is greatly improved. In order to compare with other IME designs, an IME design support D1 size, 30 fps with search range [32, 32] is implemented. The hardware cost of this design includes 118 KGates and 8 Kb SRAM, the maximum clock frequency is 200 MHz. Compared to the original 2-D SAD tree IME, our design saves 87.5% on-chip memory, and achieves 3 times performance than original one. Our design provides a new way to design a low cost and high performance IME for H.264/AVC encoder.
Yuta YAMATO Xiaoqing WEN Kohei MIYASE Hiroshi FURUKAWA Seiji KAJIHARA
Power-aware X-filling is a preferable approach to avoiding IR-drop-induced yield loss in at-speed scan testing. However, the ability of previous X-filling methods to reduce launch switching activity may be unsatisfactory, due to low effect (insufficient and global-only reduction) and/or low scalability (long CPU time). This paper addresses this reduction quality problem with a novel GA (Genetic Algorithm) based X-filling method, called GA-fill. Its goals are (1) to achieve both effectiveness and scalability in a more balanced manner and (2) to make the reduction effect of launch switching activity more concentrated on critical areas that have higher impact on IR-drop-induced yield loss. Evaluation experiments are being conducted on both benchmark and industrial circuits, and the results have demonstrated the usefulness of GA-fill.
Jong-Ok KIM Peter DAVIS Tetsuro UEDA Sadao OBANA
In this paper, we address adaptive link switching over heterogeneous wireless access networks including IEEE 802.11. When an IEEE 802.11 link is congested, the transmission link of a terminal with multi-RATs (radio access technologies) is switched to another radio access systems. To this end, we propose link-level metrics of LC (link cost) and AC (access cost) for quantifying TCP congestion over IEEE 802.11 networks. The proposed metric can be easily measured at a local wireless terminal, and that enables each multi-RAT terminal to work in a distributed way. Through various indoor and outdoor experiments using a test-bed system, we verify that the proposed link level metrics are good indicators of TCP traffic congestion. Experimental results show that the proposed metrics can detect congestion occurrence quickly, and avoid the TCP throughput degradation of other neighboring terminals, when they are used for transmission link switching.
Kei HASHIMOTO Heiga ZEN Yoshihiko NANKAKU Akinobu LEE Keiichi TOKUDA
This paper proposes Bayesian context clustering using cross validation for hidden Markov model (HMM) based speech recognition. The Bayesian approach is a statistical technique for estimating reliable predictive distributions by treating model parameters as random variables. The variational Bayesian method, which is widely used as an efficient approximation of the Bayesian approach, has been applied to HMM-based speech recognition, and it shows good performance. Moreover, the Bayesian approach can select an appropriate model structure while taking account of the amount of training data. Since prior distributions which represent prior information about model parameters affect estimation of the posterior distributions and selection of model structure (e.g., decision tree based context clustering), the determination of prior distributions is an important problem. However, it has not been thoroughly investigated in speech recognition, and the determination technique of prior distributions has not performed well. The proposed method can determine reliable prior distributions without any tuning parameters and select an appropriate model structure while taking account of the amount of training data. Continuous phoneme recognition experiments show that the proposed method achieved a higher performance than the conventional methods.
Bandwidth is an extremely valuable and scarce resource in multimedia networks. Therefore, efficient bandwidth management is necessary in order to provide high Quality of Service (QoS) to users. In this paper, a new QoS-aware bandwidth allocation algorithm is proposed for the efficient use of available bandwidth. By using the multi-objective optimization technique and Talmud allocation rule, the bandwidth is adaptively controlled to maximize network efficiency while ensuring QoS provisioning. In addition, we adopt the online feedback strategy to dynamically respond to current network conditions. With a simulation study, we demonstrate that the proposed algorithm can adaptively approximate an optimized solution under widely diverse traffic load intensities.
Shieh-Shing LIN Shih-Cheng HORNG Ch'i-Hsin LIN
This letter presents an experiment for estimating accurate state in distributed power systems. This letter employs a technique that combines a projected Jacobi method with a parallel dual-type method to solve the distributed state estimation with constraints problems. Via numerous tests, this letter demonstrates the efficiency of the proposed method on the IEEE 118-bus with four subsystems in a PC network.
Kazuyoshi TAKAGI Yuki ITO Shota TAKESHIMA Masamitsu TANAKA Naofumi TAKAGI
In this paper, we propose a method for layout-driven skewed clock tree synthesis for SFQ logic circuits. For a given logic circuit without a clock tree, our algorithm outputs a circuit with a synthesized clock tree and timing adjustments achieving the given clock period and a rough placement of the clocked gates. In the proposed algorithm, clocked gates are grouped into levels and the clock tree is synthesized for each level. For each level, we estimate the clock timing for all possible placements of each gate, and then we search a placement of all gates that minimizes the total number of delay elements for timing adjustment. Once the placement is obtained, we synthesize a clock tree without wire intersections. We applied the proposed method to a moderate size circuit and confirmed that clock trees satisfying given timing requirements can be synthesized automatically.
Let Q be the set of all primitive words over a finite alphabet having at least two letters. In this paper, we study the language D(1) of all non-overlapping (d-primitive) words, which is a proper subset of Q. We show that D(1) is a context-sensitive langauage but not a deterministic context-free language. Further it is shown that [D(1)]n is not regular for n ≥ 1.
Longbiao WANG Norihide KITAOKA Seiichi NAKAGAWA
We propose a blind dereverberation method based on spectral subtraction using a multi-channel least mean squares (MCLMS) algorithm for distant-talking speech recognition. In a distant-talking environment, the channel impulse response is longer than the short-term spectral analysis window. By treating the late reverberation as additive noise, a noise reduction technique based on spectral subtraction was proposed to estimate the power spectrum of the clean speech using power spectra of the distorted speech and the unknown impulse responses. To estimate the power spectra of the impulse responses, a variable step-size unconstrained MCLMS (VSS-UMCLMS) algorithm for identifying the impulse responses in a time domain is extended to a frequency domain. To reduce the effect of the estimation error of the channel impulse response, we normalize the early reverberation by cepstral mean normalization (CMN) instead of spectral subtraction using the estimated impulse response. Furthermore, our proposed method is combined with conventional delay-and-sum beamforming. We conducted recognition experiments on a distorted speech signal simulated by convolving multi-channel impulse responses with clean speech. The proposed method achieved a relative error reduction rate of 22.4% in relation to conventional CMN. By combining the proposed method with beamforming, a relative error reduction rate of 24.5% in relation to the conventional CMN with beamforming was achieved using only an isolated word (with duration of about 0.6 s) to estimate the spectrum of the impulse response.
Jin-soo KIM Jae-Gon KIM Kwang-deok SEO
We propose an efficient selective block encoding scheme with motion information feedback in distributed video coding (DVC). The proposed scheme estimates the spatial and temporal matching costs for each block in the side information (SI) and for the blocks with high matching costs, the motion information is provided to the encoder side to selectively encode the motion-compensated frame difference signal. Experimental results show that the proposed scheme outperforms the recently developed DVC algorithms.
Min LUO Akitsugu WATANABE Haruo YOKOTA
Scalability and availability are the key features of parallel database systems. To realize scalability, many dynamic load-balancing methods with data placement and parallel index structures on shared-nothing parallel infrastructure have been proposed. Data migration with range-partitioned placement using a parallel Btree is one solution. The combination of range partitioning and chained declustered replicas provides high availability (HA) while preserving scalability. However, independent treatment of the primary and backup data in each node requires long failover times. We propose a novel method for the compound treatment of chained declustered replicas using a parallel Btree, termed the Fat-Btree. In the proposed method, a single Fat-Btree provides access paths to both the primary and backup data of all processor elements (PEs), which greatly reduces failover time. Moreover, these access paths overlap between two neighboring PEs, which enables dynamic load balancing without physical data migration by dynamically redirecting the access paths. In addition, this compound treatment improves memory space utilization to enable index processing with good scalability. Experiments using PostgreSQL on a 160-node PC cluster demonstrate the effectiveness of the high scalability and availability of our proposed method.
Adam JATOWT Yukiko KAWAI Katsumi TANAKA
Due to the increased preservation efforts, large amounts of past Web data have been stored in Web archives and other archival repositories. Utilizing this data can offer certain benefits to users, for example, it can facilitate page understanding. In this paper, we propose a system for interactive exploration of page histories. We demonstrate an application called Page History Explorer (PHE) for summarizing and visualizing histories of Web pages. PHE portrays the overview of page evolution, characterizes its typical content over time and lets users observe page histories from different viewpoints. In addition, it enables flexible comparison of histories of different pages.
Motoki MIURA Taro SUGIHARA Susumu KUNIFUJI
Practitioners of the Jiro Kawakita (KJ) method, a method for organizing ideas, typically use paper labels and four-colored ball-point pens to record their ideas during the creative thinking process. A similar approach is used in group KJ method sessions; however, the effectiveness of capturing and sharing the diagrams and information is limited because of the large amount of paper required. Considering the merits of the conventional paper-pen approach and the demand for quick sharing of diagrams after a session, we designed and implemented a system to digitize group KJ sessions--not just the diagrams but also the details of the creative process. We used digital pens during the session to capture the position and orientation of labels as well as their content. We confirmed the efficiency of our system by applying it to several GKJ sessions.
Masakatsu OGAWA Takefumi HIRAGURI Kentaro NISHIMORI Naoki HONMA Kazuhiro TAKAYA Kazuo MURAKAWA
This paper proposes a power saving control method for battery-powered portable wireless LAN (WLAN) access points (APs) in an overlapping basic service set (OBSS) environment. The IEEE802.11 standard does not support power saving control for APs. Some conventional power saving control methods for APs have been proposed that use the network allocation vector (NAV) to inhibit transmission at stations (STAs) while the AP is sleeping. However, since with these approaches the actual beacon interval in the OBSS environment may be extended due to the NAV as compared to the beacon interval which is set at the AP, the power consumption and delay may be increased as compared to a single BSS unaffected by interference from neighboring APs. To overcome this problem, this paper introduces a new action frame named power saving access point (PSAP) action frame which the AP uses to inform STAs within its BSS about the AP's sleep length. In addition, a function of the PSAP action frame is that STAs enter the sleep state after receiving the PSAP action frame. The proposed control method avoids the postponement of beacon transmission and reduces the power consumption in an OBSS environment, as compared to the conventional control method. Numerical analysis and computer simulation reveal that the newly proposed control method conserves power as compared to the conventional control method. The proposed control method achieves the minimum consumed power ratio at the AP, which is 44% as compared to the standard, when the beacon interval is 100 ms and the sleep length is 60 ms, even if the number of neighboring APs in an OBSS environment is increased.
This letter proposes a robust joint linear precoding scheme based on the minimum mean squared error (MMSE) criterion for amplify-and-forward (AF) multiple-input multiple-output (MIMO) relay broadcast systems with limited feedback, where only the quantized channel direction information (CDI) of the forward channel is available for the base station (BS) and the relay station (RS). The proposed scheme employs an iterative algorithm which alternately optimizes the BS and RS precoders to jointly minimize the expected MSE conditioned on the quantized CDI.
Akio FUJIYOSHI Masakazu SUZUKI
In this paper, we study the minimum spanning tree problem with label selection, that is, the problem of finding a minimum spanning tree of a vertex-labeled graph where the weight of each edge may vary depending on the selection of labels of vertices at both ends. The problem is especially important as the application to mathematical OCR. It is shown that the problem is NP-hard. However, for the application to mathematical OCR, it is sufficient to deal with only graphs with small tree-width. In this paper, a linear-time algorithm for series-parallel graphs is presented. Since the minimum spanning tree problem with label selection is closely related to the generalized minimum spanning tree problem, their relation is discussed.
A min-max model predictive controller is developed in this paper for tracking control of wheeled mobile robots (WMRs) subject to the violation of nonholonomic constraints in an environment without obstacles. The problem is simplified by neglecting the vehicle dynamics and considering only the steering system. The linearized tracking-error kinematic model with the presence of uncertain disturbances is formed in the frame of the robot. And then, the control policy is derived from the worst-case optimization of a quadratic cost function, which penalizes the tracking error and control variables in each sampling time over a finite horizon. As a result, the input sequence must be feasible for all possible disturbance realizations. The performance of the control algorithm is verified via the computer simulations with a predefined trajectory and is compared to a common discrete-time sliding mode control law. The result shows that the proposed method has a better tracking performance and convergence.
Daiki KOIDE Shouta KATO Eri IKEDA Nobuyuki IWATA Hiroshi YAMAMOTO
The purpose of this work is to synthesize a three-dimension C60 polymer using photo-polymerization method. The used pristine materials were C60 precipitates prepared by a liquid-liquid interfacial precipitation (LLIP) method. The prepared LLIP material was set in the vacuum and was compressed in the anvil with the pressure of 600 MPa or 7 GPa. The 4th harmonics FEL with the wavelength of 500 nm was irradiated with macro-pulses (the pulse width of 20 µs) containing very short micro-pulses (the pulse width of 200 fs). The Raman Ag(2) peak of C60 molecules in the vicinity of 1469 cm-1 becomes broad and shifts to the lower energy region as proceeding of polymerization. Under high pressure and/or FEL irradiation the LLIP crystal revealed the large red-shift and the increment of the half width of the Raman Ag(2) peak. Furthermore the LLIP crystal mixture with iodine revealed the more distinctive red-shift, ca.13cm-1 because of highly packing of C60 molecules. The C60 molecular accession by LLIP process and/or the photo-assisted hole-doping from iodine were promising conditions to promote the photo-polymerization effectively.
Yutaka IWAIKAWA Naoyuki KAMIYAMA Tomomi MATSUI
The firefighter problem is used to model the spread of fire, infectious diseases, and computer viruses. This paper deals with firefighter problem on rooted trees. It is known that the firefighter problem is NP-hard even for rooted trees of maximum degree 3. We propose techniques to improve a given approximation algorithm. First, we introduce an implicit enumeration technique. By applying the technique to existing ()-approximation algorithm, we obtain -approximation algorithm when a root has k children. In case of ternary trees, k=3 and thus the approximation ratio satisfies ≥ 0.6892, which improves the existing result ≥ 0.6321. Second technique is based on backward induction and improves an approximation algorithm for firefighter problem on ternary trees. If we apply the technique to existing () -approximation algorithm, we obtain 0.6976-approximation algorithm. Lastly, we combine the above two techniques and obtain 0.7144-approximation algorithm for firefighter problem on ternary trees.
Kazutaka NISHINO Shinji TANI Ikuo OKA Shingo ATA
A path diversity is an effective technique to get highly reliable communications in the sensor network. In this paper, the path diversity is examined for a tree network composed of binary symmetric channels (BSC) from the view point of bit error probability (BEP). End-nodes of the network are connected to a fusion center, which sums up the received data. The probability density function (pdf) of decision variable conditioned on a source node data is derived by an iterative algorithm to obtain BEP. Numerical results show that in the case of a majority decision, BEP at the fusion center is almost the same as the BSC crossover probability due to the path diversity effects, even if the number of relay links increases.