In this paper, we consider a collision detection problem of spheres which asks to detect all pairs of colliding spheres in a set of n spheres located in d-dimensional space. We propose a collision detection algorithm for spheres based on slab partitioning technique and a plane sweep method. We derive a theoretical upper bound on the time complexity of the algorithm. Our bound tells that if both the dimension and the maximum ratio of radii of two spheres are bounded, then our algorithm runs in O(n log n + K) time with O(n + K) space, where K denotes the number of pairs of colliding spheres.

This paper is about an efficient implementation of adaptive filtering for echo cancelers. The first objective of this paper is to propose a simplified method of the flexible block Multi-Delay Filter (MDF) algorithm in the time-domain. Then, we will derive a new method for the step-size adaptation coefficient. The second objective is about the realization of a Block Proportionate Normalized Least Mean Squares (BPNLMS++) with the simplified MDF (SMDF) implementation. Using the new step-size method and the smaller block dimension proposed by SMDF, we achieve a faster convergence of the adaptive process with a limited computational cost. Then, an efficient implementation of the new procedure (SMDF-BPNLMS++) block filtering is proposed using Fermat Number Transform, which can significantly reduce the computation complexity of filter implantation on Digital Signal Processor.

In recent years, the images captured by AVHRR (Advanced Very High Resolution Radiometer) on the NOAA (National Oceanic and Atmospheric Administration) series of satellites have been used very widely for environment and land cover monitoring. In order to use NOAA images, they need to be accurately transformed from the image coordinate system into map coordinate system. This paper proposes a geometric correction method that corrects the errors caused by this transformation. In this method, the errors in NOAA image are corrected in the image coordinate system before transforming into the map coordinate system. First, the elevation values, which are read from GTOPO30 database, are verified to divide data into flat and rough blocks. Next, in order to increase the number of GCPs (Ground Control Points), besides the GCPs in the database, more GCPs are generated based on the feature of the coastline. After using reference images to correct the missing lines and noise pixels in the top and bottom parts of the image, the elevation errors of the GCP templates are corrected and GCP template matching is applied to find the residual errors for the blocks that match GCP templates. Based on these blocks, the residual errors of other flat and rough blocks are calculated by affine and Radial Basis Function transform respectively. According to the residual errors, all pixels in the image are moved to their correct positions. Finally, data is transformed from image into map by bilinear interpolation. With the proposed method, the average values of the error after correction are smaller than 0.2 pixels on both latitude and longitude directions. This result proved that the proposed method is a highly accurate geometric correction method.

This paper introduces multiple view geometry under projective projection from four-dimensional space to two-dimensional space which can represent multiple view geometry under the projection of space-time. We show the multifocal tensors defined under space-time projective projection can be derived from non-rigid object motions viewed from multiple cameras with arbitrary translational motions, and they are practical for generating images of non-rigid object motions viewed from cameras with arbitrary translational motions. The method is tested in real image sequences.

A fine-grain reconfigurable VLSI for various applications including arithmetic operations is developed. In the fine-grain architecture, it is important to define a cell function which leads to high utilization of a logic block and reduction of a switch block. From the point of view, a universal-literal-based multiple-valued cell suitable for bit-serial reconfigurable computation is proposed. A series-gating differential-pair circuit is effectively employed for implementing a full-adder circuit of Sum and a universal literal circuit. Therefore, a simple logic block can be constructed using the circuit technology. Moreover, interconnection complexity can be reduced by utilizing multiple-valued signaling, where superposition of serial data bits and a start signal which indicates heading of one-word is introduced. Differential-pair circuits are also effectively employed for current-output replication, which leads to high-speed signaling to adjacent cells The evaluation is done based on 90 nm CMOS design rule, and it is made clear that the area of the proposed cell can be reduced to 78% in comparison with that of the CMOS implementatiuon. Moreover, its area-time product becomes 92% while the delay time is increased by 18%.

In this paper we compare various parallel preconditioners such as Point-SSOR (Symmetric Successive OverRelaxation), ILU(0) (Incomplete LU) in the Wavefront ordering, ILU(0) in the Multi-color ordering, Multi-Color Block SOR (Successive OverRelaxation), SPAI (SParse Approximate Inverse) and pARMS (Parallel Algebraic Recursive Multilevel Solver) for solving large sparse linear systems arising from two-dimensional PDE (Partial Differential Equation)s on structured grids. Point-SSOR is well-known, and ILU(0) is one of the most popular preconditioner, but it is inherently serial. ILU(0) in the Wavefront ordering maximizes the parallelism in the natural order, but the lengths of the wavefronts are often nonuniform. ILU(0) in the Multi-color ordering is a simple way of achieving a parallelism of the order N, where N is the order of the matrix, but its convergence rate often deteriorates as compared to that of natural ordering. We have chosen the Multi-Color Block SOR preconditioner combined with direct sparse matrix solver, since for the Laplacian matrix the SOR method is known to have a nondeteriorating rate of convergence when used with the Multi-Color ordering. By using block version we expect to minimize the interprocessor communications. SPAI computes the sparse approximate inverse directly by least squares method. Finally, ARMS is a preconditioner recursively exploiting the concept of independent sets and pARMS is the parallel version of ARMS. Experiments were conducted for the Finite Difference and Finite Element discretizations of five two-dimensional PDEs with large meshsizes up to a million on an IBM p595 machine with distributed memory. Our matrices are real positive, i.e., their real parts of the eigenvalues are positive. We have used GMRES(m) as our outer iterative method, so that the convergence of GMRES(m) for our test matrices are mathematically guaranteed. Interprocessor communications were done using MPI (Message Passing Interface) primitives. The results show that in general ILU(0) in the Multi-Color ordering and ILU(0) in the Wavefront ordering outperform the other methods but for symmetric and nearly symmetric 5-point matrices Multi-Color Block SOR gives the best performance, except for a few cases with a small number of processors.

This letter proposes two efficient decision-feedback (DF) detection schemes for space-time block code (STBC) over time-selective fading channels. The existing DF detection causes error propagation when the first symbol is not detected correctly. However, the proposed detection schemes provide two candidates according to a channel gain or an average log-likelihood ratio (LLR) based selection rule and choose a better candidate for the first symbol. Simulation results show that the proposed detection schemes reduce error propagation and yield significant signal-to-noise ratio (SNR) gain with moderate complexity, compared to the existing DF detection scheme.

This paper presents the processor architecture which provides much higher level dependability than the current ones. The features of it are: (1) fault tolerance and secure processing are integrated into a modern superscalar VLSI processor; (2) light-weight effective soft-error tolerant mechanisms are proposed and evaluated; (3) timing errors on random logic and registers are prevented by low-overhead mechanisms; (4) program behavior is hidden from the outer world by proposed address translation methods; (5) information leakage can be avoided by attaching policy tags for all data and monitoring them for each instruction execution; (6) injection attacks are avoided with much higher accuracy than the current systems, by providing tag trackings; (7) the overall structure of the dependable processor is proposed with a dependability manager which controls the detection of illegal conditions and recovers to the normal mode; and (8) an FPGA-based testbed system is developed where the system clock and the voltage are intentionally varied for experiment. The paper presents the fundamental scheme for the dependability, elemental technologies for dependability and the whole architecture of the ultra dependable processor. After showing them, the paper concludes with future works.

We present a systematic and efficient way of managing the path metric memory and simplifying its connection network to the add_compare_select unit (ACSU) for Viterbi decoder (VD) design. Using the derived equations for memory partition and add-compare-select (ACS) arrangement together with the extended in-place scheduling scheme proposed in this work, we can increase the memory bandwidth for conflict-free path metric accesses with hardwired interconnection between the path metric memory and ACSU. Compared with the existing work, the developed architecture possesses the following advantages: (1) Each partitioned memory bank can be treated as a local memory of a specific processing element, inside the ACSU, with hardwired interconnection, so that the interconnect complexity is reduced significantly. (2) The partitioned memory banks can be merged into only two pseudo-banks regardless of the number of adopted ACS processing elements. This not only greatly simplifies the design of address generation unit, but also makes smaller the physical size of required memory. (3) The implementation can be accomplished in a systematic way with regular and simple controlling circuitry. Experimental results demonstrate the effectiveness of the developed architecture and the benefit will be more apparent for convolutional codes with large memory order.

Finite impulse response (FIR) filtering is the most computationally intensive operation in the channelizer of a wireless communication receiver. Higher order FIR channel filters are needed in the channelizer to meet the stringent adjacent channel attenuation specifications of wireless communications standards. The computational cost of FIR filters is dominated by the complexity of the coefficient multipliers. Even though many methods for reducing the complexity of filter multipliers have been proposed in literature, these works focused on lower order filters. This paper presents a coefficient-partitioning-based binary subexpression elimination method for realizing low power FIR filters. We show that the FIR filters implemented using proposed method consume less power and achieve speed improvement compared to existing filter implementations. Design examples of the channel filters employed in the Digital Advanced Mobile Phone System (D-AMPS) and Personal Digital Cellular (PDC) receivers show that the proposed method achieved 23% average reductions of full adder and power consumption and 23.3% reduction of delay over the best existing method. Synthesis results show that the proposed method offers average area reduction of 8% and power reduction of 22% over the best known method in literature.

Often, the major requisites of short-range communication systems are low power consumption and low cost, rather than high data-transmission speeds. This paper proposes low-cost and extremely low-power radio communication devices that use a basic one-chip microcomputer for short-range transmission and reception. In the proposed transmitter, a rectangular wave is generated at external I/O ports as carrier by the basic one-chip microcomputer and is then filtered and radiated by an antenna circuit. In the proposed receiver, the received signal is detected by a radio IC and is subsequently digitally processed by a microcomputer with a built-in A/D converter. The proposed transmitter and receiver are demonstrated, and the system performance is experimentally evaluated.

We propose a practical link protection scheme, called Single Backup-table Rerouting, (SBR) as an extension for Open Shortest Path First (OSPF). SBR protects against any single link failure as soon as the failure occurs if the topology of every area in OSPF is two-link-connected. An efficient algorithm to compute a set of backup tables is provided for networks with symmetric link costs. The foremost feature of SBR is that the backup process is fully distributed, so no message exchange is required and the modification of OSPF is minor. OSPF is extended with the following: only one extra backup routing table, a 2-bit flag at each traffic packet, and a process for handling the backup table. There are no changes to the message format of OSPF. In this paper, we present the practical link protection scheme by fitting SBR into several OSPF specific mechanisms such as OSPF areas, Equal Costs Multipath (ECMP), and virtual links with proofs of their correctness. Furthermore, together with a loop-free routing technique for link-state routing, SBR guarantees the consistency of every route against a single link failure, even during the path recomputation phase, until it converges to the new shortest paths.

A software birthmark means the inherent characteristics of a program that can be used to identify the program. A comparison of such birthmarks facilitates the detection of software theft. In this paper, we propose a static Java birthmark based on a set of stack patterns, which reflect the characteristic of Java applications. A stack pattern denotes a sequence of bytecodes that share their operands through the operand stack. A weight scheme is used to balance the influence of each bytecode in a comparison of the birthmarks. We evaluate the proposed birthmark with respect to two properties required for a birthmark: credibility and resilience. The empirical results show that the proposed birthmark is highly credible and resilient to program transformation. We also compare the proposed birthmark with existing birthmarks, such as that of Tamada et al. and the k-gram birthmark. The experimental results show that the proposed birthmark is more stable than the birthmarks in terms of resilience to program transformation. Thus, the proposed birthmark can provide more reliable evidence of software theft when the software is modified by someone other than author.

Programmable Metallization Cell (PMC) Random Access Memory is based on the electrochemical growth and removal of nanoscale metallic pathways in thin films of solid electrolytes. In this study, we investigate the nature of thin films formed by the photo doping of Cu into chalcogenide materials for use in programmable metallization cell devices. These devices rely on metal ion transport in the film so produced to create electrically programmable resistance states. The results imply that a Cu-rich phase separates owing to the reaction of Cu with free atoms from chalcogenide materials.

We propose a CMOS image sensor that realizes wide dynamic range imaging and nonlinear representation of I/O characteristics. The proposed image sensor controls the integration time for each pixel based on the brightness distribution of objects. The histogram at the end of the integration is estimated from the early intermediate photodiode values that are read out to an external circuit. Using the estimated histogram, the imaging parameters, which control the integration time pixel-by-pixel, are optimized in the external circuit. According to the imaging parameters, the intermediate photodiode value is compared with the threshold and reset to the starting value depending on the comparison result. These processes repeat several times. At the end of the integration, the photodiode value is reconstructed by using the imaging parameters. Then, wide dynamic range images with adapted I/O characteristics are obtained. We have fabricated a prototype with a size of 6464 pixels using a 0.35-µm 2-poly 4-metal CMOS process. In this paper, we explain the principle of the proposed sensor and discuss the system architecture and its operation. The experimental results obtained using the prototype are also presented, and we verify its effectiveness.

A simple model of inductor-coupled bistable oscillators is shown to exhibit pulse wave propagation. We demonstrate numerically that there exists a pulse wave which propagates with a constant speed in comparatively wide parameter region. In particular, the propagating pulse wave can be observed in non-uniform lattice with noise. The propagating pulse wave can be observed for comparatively strong coupling case, and for weak coupling case no propagating pulse wave can be observed (propagation failure). We also demonstrate various interaction phenomena between two pulses.

For AES 128 security level there are several natural choices for pairing-friendly elliptic curves. In particular, as we will explain, one might choose curves with k=9 or curves with k=12. The case k=9 has not been studied in the literature, and so it is not clear how efficiently pairings can be computed in that case. In this paper, we present efficient methods for the k=9 case, including generation of elliptic curves with the shorter Miller loop, the denominator elimination and speed up of the final exponentiation. Then we compare the performance of these choices. From the analysis, we conclude that for pairing-based cryptography at the AES 128 security level, the Barreto-Naehrig curves are the most efficient choice, and the performance of the case k=9 is comparable to the Barreto-Naehrig curves.

In this letter, a genetic programming method is used to synthesize filters. In order to improve the group delay characteristics, we propose a novel two-stage fitness function reflecting not only the frequency response but also the group delay characteristics of the evolved filters. We also deal with two practical design considerations, i.e., the filters include parasitic effects and are composed of elements with discrete values. The proposed method is applied to low-pass filter design cases. The experimental results show the method can effectively generate filters satisfying the design considerations and possessing improved group delay characteristics when compared with traditional filters.

The Hajos calculus is a nondeterministic procedure which generates the class of non-3-colorable graphs. If all non-3-colorable graphs can be constructed in polynomial steps by the calculus, then NP = co-NP holds. Up to date, however, it remains open whether there exists a family of graphs that cannot be generated in polynomial steps. To attack this problem, we propose two graph calculi PHC and PHC* that generate non-3-colorable planar graphs, where intermediate graphs in the calculi are also restricted to be planar. Then we prove that PHC and PHC* are sound and complete. We also show that PHC* can polynomially simulate PHC.

A (k,2)-track layout of a graph G consists of a 2-track assignment of G and an edge k-coloring of G with no monochromatic X-crossing. This paper studies the problem of (k,2)-track layout of bipartite graph subdivisions. Recently V. Dujmovi and D.R. Wood showed that for every integer d ≥ 2, every graph G with n vertices has a (d+1,2)-track layout of a subdivision of G with 4 log d qn(G) +3 division vertices per edge, where qn(G) is the queue number of G. This paper improves their result for the case of bipartite graphs, and shows that for every integer d ≥ 2, every bipartite graph Gm,n has a (d+1,2)-track layout of a subdivision of Gm,n with 2 log d n -1 division vertices per edge, where m and n are numbers of vertices of the partite sets of Gm,n with m ≥ n.