Data caching is widely known as an effective power-saving technique, in which mobile devices use local caches instead of original data placed on a server, in order to reduce the power consumption necessary for network accesses. In such data caching, a cache invalidation mechanism is important in preventing these devices from unintentionally accessing invalid data. In this paper, we propose a broadcast-based protocol for cache invalidation in a location-aware system. The proposed protocol is designed to reduce the access time required for obtaining necessary invalidation reports through broadcast media and to avoid client-side sleep fragmentation while retrieving the reports. In the proposed protocol, a Bloom filter is used as the data structure of an invalidation report, in order to probabilistically check the invalidation of caches. Furthermore, we propose three broadcast scheduling methods that are intended to achieve flexible broadcasting structured by the Bloom filter: fragmentation avoidance scheduling method (FASM), metrics balancing scheduling method (MBSM), and minimizing access time scheduling method (MASM). The broadcast schedule is arranged for consecutive accesses to geographically neighboring invalidation reports. In addition, the effectiveness of the proposed methods is evaluated by simulation. The results indicate that the MBSM and MASM achieve a high rate of performance scheduling. Compared to the FASM, the MBSM reduces the access time by 34%, while the fragmentations on the resultant schedule increase by 40%, and the MASM reduces the access time by 40%, along with an 85% increase in the number of fragmentations.

This paper proposes a new sine wave approximation method for the PAC of DDFS. Sine wave is approximated by removing the harmonic components from trapezoid waveform. Experimental results show that the proposed PAC is advantageous in the SFDR range less than 60 dBc due to its small hardware cost.

Nearest neighbor search (NNS) among large-scale and high-dimensional vectors plays an important role in recent large-scale multimedia search applications. This paper proposes an optimized multiple codebook construction method for an approximate NNS scheme based on product quantization, where sets of residual sub-vectors are clustered according to their distribution and the codebooks for product quantization are constructed from these clusters. Our approach enables us to adaptively select the number of codebooks to be used by trading between the search accuracy and the amount of memory available.

This paper provides conceptual and experimental analysis of a new approach in the study of kanji, our “Learner's Visualization (LV) Approach”. In a previous study we found that the LV Approach assists beginning learners in significantly updating their personal kanji deconstruction visualization. Additionally, in another study our findings provided evidence that beginning learners also receive a significant impact in the ability to acquire vocabulary. In this study, our research problem examines how beginning and intermediate students use visualization to cognitively deconstruct (divide) kanji in different ways, and how this affects their learning progress. We analyze the cognitive differences in how kanji learners explore and deconstruct novel kanji while using the LV Approach and how these differences affect their learning process while using the LV Approach. During the learning experience, our LILES System (Learner's Introspective Latent Envisionment System), based on the LV Approach, guides learners to choose from a set of possible “kanji deconstruction layouts” (layouts showing different ways in which a given kanji can be divided). The system then assists learners in updating their “kanji deconstruction level” (the average number of parts they visualize within kanji according to their current abilities). Statistical analysis based on achieved performance was conducted. The analysis of our results proves that there are cognitive differences: beginners deconstruct kanji into more parts (“blocks”) than intermediate learners do, and while both improve their kanji deconstruction scores, there is a more significant change in “kanji deconstruction level” in beginners. However, it was also found that intermediate learners benefit more in “kanji retention score” compared with beginners. Suggestions for further research are provided.

When a link or node fails in a network, the affected flows are automatically rerouted. This increases the hop counts of the flows, which can drastically degrade network performance. Keeping the hop lengths as stable as possible, i.e., minimizing the difference in hop length between the original flow and the rerouted flow is important for network reliability. Therefore, network service providers need a method for designing networks that stabilizes the flow hop length and maintains connectivity during a link or node failure with limited investment cost. First, we formulate the network design problem used for determining the set of links to be added that satisfies the required constraints on flow hop length stability, connectivity, and node degree. Next, we prove that this problem is NP-complete and present two approximation algorithms for the optimization problem so as to minimize the number of links added. Evaluation of the performance of these algorithms by using 39 backbone networks of commercial ISPs and networks generated by two well-known models showed that the proposed algorithms provide effective solutions in sufficiently short computation time.

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.

A broadband cruciform substrate integrated waveguide coupler is designed based on the planar circuit approach. The broadband property is obtained by widening the crossed region in the same way as rectangular waveguide cruciform couplers. As a result, a 3 dB coupler with fractional bandwidth of 30% is realized at 24 GHz.

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.

This paper proposes a further improved technique on the stochastic functional approach for randomly rough surface scattering. The original improved technique has been established in the previous paper [Waves in Random and Complex Media, vol.19, no.2, pp.181-215, 2009] as a novel numerical-analytical method for a Wiener analysis. By deriving modified hierarchy equations based on the diagonal approximation solution of random wavefields for a TM plane wave incidence or even for a TE plane wave incidence under large roughness, large slope or low grazing incidence, such a further improved technique can provide a large reduction of required computational resources, in comparison with the original improved technique. This paper shows that numerical solutions satisfy the optical theorem with very good accuracy, by using small computational resources.

In this paper, two techniques for implementing a low-power pipelined analog-to-digital converter (ADC) are proposed. First, the time-interleaved correlated double sampling (CDS) technique is proposed to compensate the finite gain error of operational amplifiers in switched-capacitor circuits without a half-rate front-end sample-and-hold amplifier (SHA). Therefore, low-gain amplifiers and the SHA-less architecture can be used to effectively reduce power consumption of a pipelined ADC. Second, the back-end pipelined stages of a pipelined ADC are implemented using a low-power time-interleaved successive approximation (SA) ADC rather than operational amplifiers to further reduce the power consumption of the proposed pipelined ADC. A 9-bit, 100-MS/s hybrid pipelined-SA ADC is implemented in the TSMC 0.13 µm triple-well 1P8M CMOS process. The ADC achieves a spurious free dynamic range (SFDR) of 62.15 dB and a signal-to-noise distortion ratio (SNDR) of 50.85-dB for 2-MHz input frequency at a 100-MS/s sampling rate. The power consumption is 21.2 mW from a 1.2 V supply. The core area of the ADC is 1.6 mm2.

A 9-bit 100-MS/s successive approximation register (SAR) ADC with low power and small area has been implemented in 65-nm CMOS technology. A tri-level charge redistribution technique is proposed to reduce DAC switching energy and settling time. By connecting bottom plates of differential capacitor arrays for charge sharing, extra reference voltage is avoided. Two reference voltages charging and discharging the capacitors are chosen to be supply voltage and ground in order to save energy and achieve a rail-to-rail input range. Split capacitor arrays with mismatch calibration are implemented for small area and small input capacitance without linearity degradation. The ADC achieves a peak SNDR of 53.1 dB and consumes 1.46 mW from a 1.2-V supply, resulting in a figure of merit (FOM) of 39 fJ/conversion-step. The total active area is 0.012 mm2 and the input capacitance is 180 fF.

Square-related functions such as square, inverse square, square-root and inverse square-root operations are widely used in digital signal processing and digital communication algorithms, and their efficient realizations are commonly required to reduce the hardware complexity. In the implementation point of view, approximate realizations are often desired if they do not degrade performance significantly. In this paper, we propose new linear approximations for the square-related functions. The traditional linear approximations need multipliers to calculate slope offsets and tables to store initial offset values and slope values, whereas the proposed approximations exploit the inherent properties of square-related functions to linearly interpolate with only simple operations, such as shift, concatenation and addition, which are usually supported in modern VLSI systems. Regardless of the bit-width of the number system, more importantly, the maximum relative errors of the proposed approximations are bounded to 6.25% and 3.13% for square and square-root functions, respectively. For inverse square and inverse square-root functions, the maximum relative errors are bounded to 12.5% and 6.25% if the input operands are represented in 20 bits, respectively.

We present self-calibration techniques for an interleaved SAR (Successive Approximation Register) ADC. The calibration technique is based on hardware corrections for linearity of single stage, gain error and mismatch errors of parallel ADCs. The 4-interleaved 11-bit ADC has been fabricated in a 0.18-µm CMOS process. Using the calibrations, measurement and calculation results show that the differences of ramp characteristic among the 4-interleaving ADC can be decresased to under 0.63 LSB.

Least-squares policy iteration is a useful reinforcement learning method in robotics due to its computational efficiency. However, it tends to be sensitive to outliers in observed rewards. In this paper, we propose an alternative method that employs the absolute loss for enhancing robustness and reliability. The proposed method is formulated as a linear programming problem which can be solved efficiently by standard optimization software, so the computational advantage is not sacrificed for gaining robustness and reliability. We demonstrate the usefulness of the proposed approach through a simulated robot-control task.

Based on the least square (LS) approximation of sinusoidal signal in frequency domain by sample data, a frequency estimator is derived. Since sinusoidal signals are narrow-banded whereas white noise spreads equally in the whole spectrum, only narrow-band approximation around the actual tone is needed, and thus the influence of noise can be decreased significantly with high computational efficiency. Experimental results show that, without any iterations, the performance of the proposed estimator is close to the Cramer-Rao Bound (CRB), and has a lower SNR threshold compared with other existing estimators.

Digital signal processing requires digital filters with variable frequency characteristics. A variable digital filter (VDF) is a filter whose frequency characteristics can be easily and instantaneously changed. In this paper, we present a design method for variable linear-phase finite impulse response (FIR) filters with multiple variable factors and a reduction method for the number of polynomial coefficients. The obtained filter has a high piecewise attenuation in the stopband. The stopband edge and the position and magnitude of the high piecewise stopband attenuation can be varied by changing some parameters. Variable parameters are normalized in this paper. An optimization methodology known as semidefinite programming (SDP) is used to design the filter. In addition, we present that the proposed VDF can be implemented using the Farrow structure, which suitable for real time signal processing. The usefulness of the proposed filter is demonstrated through examples.

This paper treats a band-broadening design technique of a dual-band branch-line coupler with matching networks composed of an impedance step and a short-circuited stub based on the equivalent admittance approach. By replacing each right-handed transmission line (RH-TL) with a composite right/left-handed transmission line (CRLH-TL), very flat couplings over a relative bandwidth of about 10% can be obtained at two arbitrary operating frequencies in comparison with previous CRLH-TLs branch-line couplers. Furthermore, by adding periodical open-circuited stubs into RH-TLs of the designed CRLH-TLs branch-line coupler with matching networks, the entire size of the coupler can be reduced to about 50%. Verification of these band-broadening and size-reduction design techniques can be also shown by an electromagnetic simulation and experiment.

In this paper, a modified Belief Propagation (BP) decoding algorithm for low-density parity check (LDPC) codes based on minimum mean square error (MMSE) criterion is proposed. This modified algorithm uses linear equation to replace the hyperbolic function in the original BP algorithm and optimizes the linear approximation error based on MMSE criterion. As a result, compared with the standard BP algorithm the computational complexity is reduced significantly as the modified algorithm requires only addition operations to implement. Besides that simulation results show our modified algorithm can achieve an error performance very close to the BP algorithm on the additive white Gaussian noise channel.

We consider the minimum cost edge installation problem (MCEI) in a graph G=(V,E) with edge weight w(e)≥ 0, e∈ E. We are given a vertex s∈ V designated as a sink, an edge capacity λ>0, and a source set S⊆ V with demand q(v)∈ [0,λ], v∈ S. For each edge e∈ E, we are allowed to install an integer number h(e) of copies of e. MCEI asks to send demand q(v) from each source v∈ S along a single path Pv to the sink s without splitting the demand of any source v∈ S. For each edge e∈ E, a set of such paths can pass through a single copy of e in G as long as the total demand along the paths does not exceed the edge capacity λ. The objective is to find a set P={Pv| v∈ S∈ of paths of G that minimizes the installing cost ∑e∈ E h(e)w(e). In this paper, we propose a (15/8+ρST)-approximation algorithm to MCEI, where ρST is any approximation ratio achievable for the Steiner tree problem.

Charge redistribution based successive approximation (SA) analog-to-digital converter (ADC) has the advantage of power efficiency. Split capacitor digital-to-analog converter (CDAC) technique implements two sets of binary-weighted capacitor arrays connected by a bridge capacitor so as to reduce both input load capacitance and area. However, capacitor mismatches degrade ADC performance in terms of DNL and INL. In this work, a split CDAC mismatch calibration method is proposed. A bridge capacitor larger than conventional design is implemented so that a tunable capacitor can be added in parallel with the lower-weight capacitor array to compensate for mismatches. To guarantee correct CDAC calibration, comparator offset is cancelled using a digital timing control charge compensation technique. To further reduce the input load capacitance, an extra unit capacitor is added to the higher-weight capacitor array. Instead of the lower-weight capacitor array, the extra unit capacitor and the higher-weight capacitor array sample analog input signal. An 8-bit SA ADC with 4-bit + 4-bit split CDAC has been implemented in a 65 nm CMOS process. The ADC has an input capacitance of 180 fF and occupies an active area of 0.03 mm2. Measured results of +0.2/-0.3LSB DNL and +0.3/-0.3LSB INL have been achieved after calibration.