Given a simple connected graph G with n vertices, the spanning tree problem involves finding a tree that connects all the vertices of G. Solutions to this problem have applications in electrical power provision, computer network design, circuit analysis, among others. It is known that highly efficient sequential or parallel algorithms can be developed by restricting classes of graphs. Circular trapezoid graphs are proper superclasses of trapezoid graphs. In this paper, we propose an O(n) time algorithm for the spanning tree problem on a circular trapezoid graph. Moreover, this algorithm can be implemented in O(log n) time with O(n/log n) processors on EREW PRAM computation model.

The number of users of video on demand (VoD) services has increased dramatically. In VoD services, the demand for content items changes greatly hour to hour. Because service providers are required to maintain a stable service during peak hours, they need to design system resources based on the demand at peak time, so reducing the server load at this time is important. Although multicast delivery, in which multiple users requesting the same content item are supported by one delivery session, is effective for suppressing the server load during peak hours, user response times can increase greatly. A peer-to-peer-assisted delivery system, in which users download content items from other users watching the same content item, is also effective for reducing server load. However, system performance depends on selfish user behavior, and optimizing the usage of system resources is difficult. Moreover, complex operation, i.e., switching the delivery multicast tree or source peers, is necessary to support video cassette recorder (VCR) operation, e.g., fast forward, rewind, and pause. In this paper, we propose to reduce server load without increasing user response time by multicasting popular content items to all users independent of actual requests as well as providing on-demand unicast delivery. Through a numerical evaluation that uses actual VoD access log data, we clarify the effectiveness of the proposed method.

The focus of this study is the performance of the relaying network with incremental selective decode-and-forward (ISDF) protocol in non-selective slow Nakagami-m fading channels. To enhance bandwidth efficiency, when the direct transmission is not successful the relay is used to retransmit a clean copy of the source signal. The proposed protocol achieves a significant reduction in the power consumption and an improvement in performance compared to the fixed decode-and-forward (DF). The exact symbol error rate (SER) of M-PSK modulation for the ISDF protocol over general fading channels is derived. However, as the exact SER analysis is very complicated, we provide an approximated SER expression. Based on this approximation, we provide an optimum power allocation coefficient where the aggregate transmit power constraint is imposed on the source and the relay. Our results show that at least 50% of total power must be used by the direct link, and the remaining may be used by the relay. Furthermore, power allocation in this protocol is independent of the quality of the source-destination channel and modulation constellation size. Numerical results show that the ISDF protocol can reduce the average transmit power with respect to the fixed DF protocol.

This paper proposes a reduced-complexity multiband multiple-input multiple-output (MIMO) receiver that can be used in cognitive radios. The proposed receiver uses heterodyne reception implemented with a wide-passband band-pass filter in the radio frequency (RF) stage. When an RF Hilbert transformer is utilized in the receiver, image-band interference occurs because of the transformer's imperfections. Thus, the imperfection of the Hilbert transformer is corrected in the intermediate frequency (IF) stage to reduce the hardware complexity. First, the proposed receiver estimates the channel impulse response in the presence of the strong image-band interference signals. Next, the coefficients are calculated for the correction of the imperfection at the IF stage, and are fed back to the IF stage through a feedback loop. However, the imperfection caused by the digital-to-analog (D/A) converter and the baseband amplifier in the feedback loop corrupts the coefficients on the way back to the IF stage. Therefore, the proposed receiver corrects the imperfection of the analog devices in the feedback loop. The performance of the proposed receiver is verified by using computer simulations. The proposed receiver can maintain its performance even in the presence of strong image-band interference signals and imperfection of the analog devices in the feedback loop. In addition, this paper also reveals the condition for rapid convergence.

An ultra low power and low voltage successive-approximation-register (SAR) analog-to-digital converter (ADC) with timing optimized asynchronous clock generator is presented. By calibrating the delay amount of the clock generator, the DAC settling waiting time is adaptively optimized to counter the device mismatch. This technique improved the maximum sampling frequency by 40% keeping ENOB around 7-bit at 0.4 V analog and 0.7 V digital power supply voltage. The delay time dependency on power supply has small effect to the accuracy of conversion. Decreasing of supply voltage by 9% degrades ENOB only by 0.1-bit, and the proposed calibration can give delay margins for high voltage swing. The prototype ADC fabricated in 40 nm CMOS process achieved figure of merit (FoM) of 8.75-fJ/conversion-step with 2.048 MS/s at 0.6 V analog and 0.7 V digital power supply voltage. The ADC can operates from 50 S/s to 8 MS/s keeping ENOB over 7.5-bit.

This paper introduces amplitude-only images to image trading systems in which not only the copyright of images but also the privacy of consumers are protected. In the latest framework for image trading systems, an image is divided into an unrecognizable piece and a recognizable but distorted piece to simultaneously protect the privacy of a consumer and the copyright of the image. The proposed scheme uses amplitude-only images which are completely unrecognizable as the former piece, whereas the conventional schemes leave recognizable parts to the piece which degrades privacy protection performance. Moreover, the proposed scheme improves the robustness against copyright violation regardless of the used digital fingerprinting technique, because an amplitude-only image is larger than the piece in the conventional scheme. In addition, phase-only image is used as the second piece in the proposed scheme, the consumer can confirm what he/she bought. Experimental results show the effectiveness of the proposed scheme.

Wireless personal area networks (WPANs) will play an important role in next-generation communication networks. Currently, two technologies are being considered for the physical layer of WPANs, based on the two ultra wideband (UWB) standards, namely, multiband orthogonal frequency division multiplexing (MB-OFDM) UWB and direct-sequence (DS) UWB. The coexistence issue of these two types of WPANs in the same coverage area, raises new issues and introduces new problems which should be dealt with to avoid performance degradation. In particular, efficient radio resource management (RRM) in such environments is challenging. Indeed, the coexistence of heterogenous UWB based WPANs (UPANs) has an ad hoc nature, which requires RRM approaches that are different from traditional infrastructure-based ones. In this paper, we propose new algorithms for two RRM modules in heterogeneous UPANs, namely, radio access technology (RAT) selection and vertical handoff (VHO). To improve the overall performance of the system, our design considers possible narrowband interference (NBI) in the environment as well as the link outage probability, in the decision process. We also provide an analytical model based on a 4D Markov process to study the system in equilibrium and derive the performance metrics, namely, the new-call and handoff-call blocking probabilities, throughput and average carried traffic. Numerical results and comparisons show that our design achieves enhanced performance in terms of throughput and grade of service (GoS).

At Eurocrypt'03, Boneh, Gentry, Lynn and Shacham proposed a pairing based verifiably encrypted signature scheme (the BGLS-VES scheme). In 2004, Hess mounted an efficient rogue-key attack on the BGLS-VES scheme in the plain public-key model. In this letter, we show that the BGLS-VES scheme is not secure in the proof of possession (POP) model.

The paper proposes the PMD method to design an introductory programming practice course plan that is inclusive for all learners and stable throughout a course. To achieve the course plan, the method utilizes personas, each of which represents learners having similar motivation to study programming. The learning of the personas is directed to the course goal with an enforcement resulting from the discipline, which is an integration of effective learning strategies with affective components of the persoans. Under the enforcement, services to facilitate and promote the learning of each persona can be decided, based on motivation components of each persona, motivational effects of the services, and the cycle of self-efficacy. The application of the method on about 500 freshmen in C programming practice course has shown this is a successful approach for designing courses.

In this paper, 1) it is shown that amplitude-only images (AOIs) have quite wide intensity ranges (IRs), and 2) an IR reduction method for AOIs is proposed. An AOI is the inversely transformed amplitude spectra of an image, and it is used in the privacy- and copyright-protected image trading system because of its invisibility. Since an AOI is the coherent summation of cosine waves with the same phase, the IR of the AOI is too large to be stored and/or transmitted. In the proposed method, random signs are applied to discrete Fourier transformed amplitude coefficients to obtained AOIs with significantly lower IRs without distortion while keeping the invisibility of images. With reasonable processing time, high correct watermark extracting rates, inversely quantized AOIs with low mean squared errors, and reconstructed images with high peak signal-to-noise ratios are obtained by a linear quantizer in the proposed method.

This paper provides a novel normalized sign least-mean square (NSLMS) algorithm which updates only a part of the filter coefficients and simultaneously performs sparse updates with the goal of reducing computational complexity. A combination of the partial-update scheme and the set-membership framework is incorporated into the context of L∞-norm adaptive filtering, thus yielding computational efficiency. For the stabilized convergence, we formulate a robust update recursion by imposing an upper bound of a step size. Furthermore, we analyzed a mean-square stability of the proposed algorithm for white input signals. Experimental results show that the proposed low-complexity NSLMS algorithm has similar convergence performance with greatly reduced computational complexity compared to the partial-update NSLMS, and is comparable to the set-membership partial-update NLMS.

3D display systems without glasses are preferred because of the inconvenience wearing of special glasses while viewing 3D content. In general, non-glass type 3D displays work by sending left and right views of the content to the corresponding eyes depending on the user position with respect to the display. Since accurate user position estimation has become a very important task for non-glass type 3D displays, most of such systems require additional hardware or suffer from low accuracy. In this paper, an accurate user position estimation method using a single camera for non-glass type 3D display is proposed. As inter-pupillary distance is utilized for the estimation, at first the face is detected and then tracked using an Active Appearance Model. The pose of face is then estimated to compensate the pose variations. To estimate the user position, a simple perspective mapping function is applied which uses the average of the inter-pupillary distance. For accuracy, personal inter-pupillary distance can also be used. Experimental results have shown that the proposed method successfully estimated the user position using a single camera. The average error for position estimation with the proposed method was small enough for viewing 3D contents.

This paper describes a high-speed, robust, scalable, and low-cost feed-forward time amplifier that uses phase detectors and variable delay lines. The amplifier works by detecting the time difference between two rising input edges with a phase detector and adjusting the delay of the variable delay line accordingly. A test chip was designed and fabricated in 65 nm CMOS. The measured resulting performance indicates that it is possible to amplify time difference while maintaining high-speed operation.

This paper proposes methods for “restricting the message space” of public-key encryption, by allowing a third party to verify whether a given ciphertext does not encrypt some message which is previously specified as a “bad” (or “problematic”) message. Public-key encryption schemes are normally designed not to leak even partial information of encrypted plaintexts, but it would be problematic in some circumstances. This higher level of confidentiality could be abused, as some malicious parties could communicate with each other, or could talk about some illegal topics, using an ordinary public key encryption scheme with help of the public-key infrastructure. It would be undesirable considering the public nature of PKI. The primitive of restrictive public key encryption will help this situation, by allowing a trusted authority to specify a set of “bad” plaintexts, and allowing every third party to detect ciphertexts that encrypts some of the specified “bad” plaintext. The primitive also provides strong confidentiality (of indistinguishability type) of the plaintext when it is not specified as “bad.” In this way, a third party (possible a gateway node of the network) can examine a ciphertext (which comes from the network) includes an allowable content or not, and only when the ciphertext does not contain forbidden message, the gateway transfers the ciphertext to a next node. In this paper, we formalize the above requirements and provide two constructions that satisfied the formalization. The first construction is based on the techniques of Teranishi et al. (IEICE Trans. Fundamentals E92-A, 2009), Boudot (EUROCRYPT 2000), and Nakanishi et al. (IEICE Trans. Fundamentals E93-A, 2010), which are developed in the context of (revocation of) group signature. The other construction is based on the OR-proof technique. The first construction has better performance when very few messages are specified as bad, while the other does when almost all of messages are specified as bad (and only very few messages are allowed to encrypt).

Multi-view video can provide users with three-dimensional (3-D) and virtual reality perception through multiple viewing angles. In recent years, depth image-based rendering (DIBR) has been generally used to synthesize virtual view images in free viewpoint television (FTV) and 3-D video. To conceal the zero-region more accurately and improve the quality of a virtual view synthesized frame, an integrated hole-filling algorithm for view synthesis is proposed in this paper. The proposed algorithm contains five parts: an algorithm for distinguishing different regions, foreground and background boundary detection, texture image isophotes detection, a textural and structural isophote prediction algorithm, and an in-painting algorithm with gradient priority order. Based on the texture isophote prediction with a geometrical principle and the in-painting algorithm with a gradient priority order, the boundary information of the foreground is considerably clearer and the texture information in the zero-region can be concealed much more accurately than in previous works. The vision quality mainly depends on the distortion of the structural information. Experimental results indicate that the proposed algorithm improves not only the objective quality of the virtual image, but also its subjective quality considerably; human vision is also clearly improved based on the subjective results. In particular, the algorithm ensures the boundary contours of the foreground objects and the textural and structural information.

The gathering problem of anonymous and oblivious mobile robots is one of the fundamental problems in the theoretical mobile robotics. We consider the gathering problem in unoriented and anonymous rings, which requires that all robots eventually keep their positions at a common non-predefined node. Since the gathering problem cannot be solved without any additional capability to robots, all the previous results assume some capability of robots, such as the agreement of local view. In this paper, we focus on the multiplicity detection capability. This paper presents a deterministic gathering algorithm with local-weak multiplicity detection, which provides a robot with information about whether its current node has more than one robot or not. This assumption is strictly weaker than that in previous works. Our algorithm achieves the gathering from an aperiodic and asymmetric configuration with 2 < k < n/2 robots, where n is the number of nodes. We also show that our algorithm is asymptotically time-optimal one, i.e., the time complexity of our algorithm is O(n). Interestingly, despite the weaker assumption, it achieves significant improvement compared to the previous algorithm, which takes O(kn) time for k robots.

BEAN is a newly proposed lightweight stream cipher adopting Fibonacci FCSRs. It is designed for very constrained environments and aims at providing a balance between security, efficiency and cost. A weakness in BEAN was first found by Å gren and Hell in 2011, resulting in a key recovery attack slightly better than brute force. In this paper, we present new correlations between state and keystream with large statistical advantage, leading to a much more efficient key recovery attack. The time and data complexities of this attack are 257.53 and 259.94, respectively. Moreover, two new output functions are provided as alternatives, which are more efficent than the function used in BEAN and are immune to all attacks proposed on the cipher. Also, suggestions for improving the FCSRs are given.

A wide-tuning-range LC-tuned voltage-controlled oscillator (LC-VCO) – featuring small VCO-gain (KVCO) variation – has been developed. For small KVCO variation, a serial LC-resonator that consists of an inductor, a fine-tuning varactor, and a capacitor bank was added to a conventional parallel LC-resonator that uses a capacitor bank scheme. The resonator was applied to a 3.9-GHz VCO for multi-band W-CDMA RFIC fabricated using 0.25-µm Si-BiCMOS technology. The VCO exhibited KVCO variation of only 21%, which is one third that of a conventional VCO, with a 34% tuning range. The VCO also exhibited a low phase noise of -121 dBc/Hz at 1-MHz offset frequency and a low current consumption of 6.0 mA.

A vertex cover of a given graph G = (V,E) is a subset N of V such that N contains either u or v for any edge (u,v) of E. The minimum weight vertex cover problem (MWVC for short) is the problem of finding a vertex cover N of any given graph G = (V,E), with weight w(v) for each vertex v of V, such that the sum w(N) of w(v) over all v of N is minimum. In this paper, we consider MWVC with w(v) of any v of V being a positive integer. We propose simple procedures as postprocessing of algorithms for MWVC. Furthremore, five existing approximation algorithms with/without the proposed procedures incorporated are implemented, and they are evaluated through computing experiment.