Recently, cars are equipped with a lot of sensors for safety driving. We have been trying to store the driving-scene video with such sensor data and to detect the change of scenery of streets. Detection results can be used for building historical database of town scenery, automatic landmark updating of maps, and so forth. In order to compare images to detect changes, image retrieval taken at nearly identical locations is required as the first step. Since Global Positioning System (GPS) data essentially contain some noises, we cannot rely only on GPS data for our image retrieval. Therefore, we have developed an image retrieval algorithm employing edge-histogram-based image features in conjunction with hierarchical search. By using edge histograms projected onto the vertical and horizontal axes, the retrieval has been made robust to image variation due to weather change, clouds, obstacles, and so on. In addition, matching cost has been made small by limiting the matching candidates employing the hierarchical search. Experimental results have demonstrated that the mean retrieval accuracy has been improved from 65% to 76% for the front-view images and from 34% to 53% for the side-view images.

We present the use of a Modified Generalized Hough Transform (MGHT) and deformable contours for image data retrieval where a given contour, gray-scale, or color template image can be detected in the target image, irrespective of its position, size, rotation, and smooth deformation transformations. Potential template positions are found in the target image using our novel modified Generalized Hough Transform method that takes measurements from the template features by extending a line from each edge contour point in its gradient direction to the other end of the object. The gradient difference is used to create a relationship with the orientation and length of this line segment. Potential matching positions in the target image are then searched by also extending a line from each target edge point to another end along the normal, then looking up the measurements data from the template image. Positions with high votes become candidate positions. Each candidate position is used to find a match by allowing the template to undergo a contour transformation. The deformed template contour is matched with the target by measuring the similarity in contour tangent direction and the smoothness of the matching vector. The deformation parameters are then updated via a Bayesian algorithm to find the best match. To avoid getting stuck in a local minimum solution, a novel coarse-and-fine model for contour matching is included. Results are presented for real images of several kinds including bin picking and fingerprint identification.

This paper presents two hardware-friendly low-power oriented fast motion estimation (ME) algorithms and their VLSI implementations. The basic idea of the proposed partial distortion sorting (PDS) algorithm is to disable the search points which have larger partial distortions during the ME process, and only keep those search points with smaller ones. To further reduce the computation overhead, a simplified local PDS (LPDS) algorithm is also presented. Experiments show that the PDS and LPDS algorithms can provide almost the same image quality as full search only with 36.7% computation complexity. The proposed two algorithms can be integrated into different FSBMA architectures to save power consumption. In this paper, the 1-D inter ME architecture [12] is used as an detailed example. Under the worst working conditions (1.62 V, 125) and 166 MHz clock frequency, the PDS algorithm can reduce 33.3% power consumption with 4.05 K gates extra hardware cost, and the LPDS can reduce 37.8% power consumption with 1.73 K gates overhead.

Password-based authenticated key exchange protocols are more convenient and practical, since users employ human-memorable passwords that are simpler to remember than cryptographic secret keys or public/private keys. Abdalla, Fouque, and Pointcheval proposed the password-based authenticated key exchange protocol in a 3-party model (GPAKE) in which clients trying to establish a secret do not share a password between themselves but only with a trusted server. On the other hand, Canetti presented a general framework, which is called universally composable (UC) framework, for representing cryptographic protocols and analyzing their security. In this framework, the security of protocols is maintained under a general protocol composition operation called universal composition. Canetti also proved a UC composition theorem, which states that the definition of UC-security achieves the goal of concurrent general composition. A server must manage all the passwords of clients when the 3-party password-based authenticated key exchange protocols are realized in large-scale networks. In order to resolve this problem, we propose a hierarchical hybrid authenticated key exchange protocol (H2AKE). In H2AKE, forwarding servers are located between each client and a distribution server, and the distribution server sends the client an authentication key via the forwarding servers. In H2AKE, public/private keys are used between servers, while passwords are also used between clients and forwarding servers. Thus, in H2AKE, the load on the distribution server can be distributed to the forwarding servers concerning password management. In this paper, we define hierarchical hybrid authenticated key exchange functionality. H2AKE is the universal form of the hierarchical (hybrid) authenticated key exchange protocol, which includes a 3-party model, and it has the characteristic that the construction of the protocol can flexibly change according to the situation. We also prove that H2AKE is secure in the UC framework with the security-preserving composition property.

A multiple-input multiple-output software defined radio (MIMO-SDR) platform was developed for implementation of MIMO transmission and propagation measurement systems. This platform consists of multiple functional boards for baseband (BB) digital signal processing and frequency conversion of 5 GHz-band radio frequency (RF) signals. The BB boards have capability of arbitrary system implementation by rewriting software on reconfigurable devices such as field programmable gate arrays (FPGAs) and digital signal processors (DSPs). The MIMO-SDR platform employs hybrid implementation architecture by taking advantages of FPGA, DSP, and CPU, where functional blocks with the needs for real-time processing are implemented on the FPGAs/DSPs, and other blocks are processed off-line on the CPU. In order to realize the hybrid implementation, driver software was developed as an application program interface (API) of the MIMO-SDR platform. In this paper, hardware architecture of the developed MIMO-SDR platform and its software implementation architecture are explained. As an application example, implementation of a real-time MIMO channel measurement system and initial measurement results are presented.

Wireless communications technology continues to change and yield new standards for satisfying the user demands. As a result, multiple standards coexist and wireless communications systems supporting different air interfaces cannot interact with one another. Software-defined radio is regarded as the most promising solution to cope with this problem. In this paper, we discuss the design considerations of SDR systems from a base station point of view and propose new architecture which meets the inherent requirements of SDR platform. We then introduce hardware/software of SDR platform we accomplished on the basis of the new architecture. In addition, the results of basic transmission and receiving performance are presented to prove the feasibility of the proposed platform as a base station.

Most digital signal processing (DSP) algorithms for multimedia and communication applications require multiplication and addition operations. Especially matrix-matrix or matrix-vector the multiplications frequently used in DSP implementations needs inner product arithmetic which takes the most processing time. Also multiplications for the DSP algorithms for software defined radio (SDR) applications require different input bitwidths. Therefore, the multiplications for inner product need to be sufficiently flexible in terms of bitwidths to utilize hardware resources efficiently. This paper proposes a novel reconfigurable inner product architecture based on a pipelined adder array, which offers increased flexibility in bitwidths of input arrays. The proposed architecture consists of sixteen 44 multipliers and a pipelined adder array and can compute the inner product of input arrays with any combination of multiples of 4 bitwidths such as 44, 48, 412, ... 1616. Experimental results show that the proposed architecture has latency of maximum 9 clock cycles and throughput of 1 clock cycle for inner product of various bitwidths of input arrays. When TSMC 0.18 µm libraries are used, the chip area and critical path of the proposed architecture are 186,411 gates and 2.79 ns, respectively. The proposed architecture can be applied to a reconfigurable arithmetic engine for real-time SDR system designs.

One full search variable block size motion estimation (VBSME) architecture with integer pixel accuracy is proposed in this paper. This proposed architecture has following features: (1) Through widening data path from the search area memories, m processing element groups (PEG) could be scheduled to work in parallel and fully utilized, where m is a factor of sixteen. Each PEG has sixteen processing elements (PE) and just costs 8.5K gates. This feature provides users more flexibility to make tradeoff between the hardware cost and the performance. (2) Based on pipelining and multi-cycle data path techniques, this architecture can work at high clock frequency. (3) The memory partition number is greatly reduced. When sixteen PEGs are adopted, only two memory partitions are required for the search area data storage. Therefore, both the system hardware cost and power consumption can be saved. A 16-PEG design with 4832 search range has been implemented with TSMC 0.18 µm CMOS technology. In typical work conditions, its maximum clock frequency is 261 MHz. Compared with the previous 2-D architecture [9], about 13.4% hardware cost and 5.7% power consumption can be saved.

Set Partitioning in Hierarchical Trees (SPIHT) is a highly efficient technique for compressing Discrete Wavelet Transform (DWT) decomposed images. Though its compression efficiency is a little less famous than Embedded Block Coding with Optimized Truncation (EBCOT) adopted by JPEG2000, SPIHT has a straight forward coding procedure and requires no tables. These make SPIHT a more appropriate algorithm for lower cost hardware implementation. In this paper, a modified SPIHT algorithm is presented. The modifications include a simplification of coefficient scanning process, a 1-D addressing method instead of the original 2-D arrangement of wavelet coefficients, and a fixed memory allocation for the data lists instead of a dynamic allocation approach required in the original SPIHT. Although the distortion is slightly increased, it facilitates an extremely fast throughput and easier hardware implementation. The VLSI implementation demonstrates that the proposed design can encode a CIF (352288) 4:2:0 image sequence with at least 30 frames per second at 100-MHz working frequency.

In this paper, we propose a power-efficient LDPC decoder architecture based on an accelerated message-passing schedule. The proposed decoder architecture is characterized as follows: (i) Partitioning a pipelined operation not to read and write intermediate messages simultaneously enables the accelerated message-passing schedule to be implemented with single-port SRAMs. (ii) FIFO-based buffering reduces the number of SRAM banks and words of the LDPC decoder based on the accelerated message-passing schedule. The proposed LDPC decoder keeps a single message for each non-zero bit in a parity check matrix as well as a classical schedule while achieving the accelerated message-passing schedule. Implementation results in 0.18 [µm] CMOS technology show that the proposed decoder architecture reduces an area of the LDPC decoder by 43% and a power dissipation by 29% compared to the conventional architecture based on the accelerated message-passing schedule.

In this paper, a novel cost effective interconnection network for two-way pipelined SIMD-based reconfigurable computing processor is proposed. Our reconfigurable computing engine is composed of the SIMD-based function units, flexible interconnection networks, and two-bank on-chip memories. In order to connect the function units, the reconfigurable network is proposed to connect all neighbors of each function unit. The proposed interconnection network is a kind of full and bidirectional connection with the data duplication to perform the data-parallelism applications efficiently. Moreover, it is a multistage network to accomplish the high flexibility and low hardware cost.

Multi-context FPGAs (MC-FPGAs) have multiple memory bits per configuration bit forming configuration planes for fast switching between contexts. The additional memory planes cause a large overhead in area when a number of contexts are used. To overcome the overhead, a fine-grained MC-FPGA architecture using a floating-gate-MOS functional pass gate (FGFP) is presented which merges threshold operation and storage function on a single floating-gate MOS transistor. The test chip is designed using a 0.35 µm CMOS-EPROM technology. The transistor count of the proposed multi-context switch (MC-switch) is reduced to 13% in comparison with SRAM-based one. The total area of the proposed MC-FPGA is reduced to about 56% of that of a conventional SRAM-based MC-FPGA.

In this paper, the interpolation line search (ILS) algorithm to find the desirable step length in a numerical optimization method is investigated to determine the optimal saturation limits with non-smooth nonlinearities. The simple steepest descent algorithm is used to illustrate that the ILS algorithm can provide adequate reductions in an objective function at minimal cost with fast convergence. The power system stabilizer (PSS) with output limits is used as an example for a nonlinear controller to be tuned. The efficient computation to implement the ILS algorithm in the steepest descent method is available by using the hybrid system model with the differential-algebraic-impulsive-switched (DAIS) structure. The simulation results are given to show the performance improved by the ILS algorithm.

In this paper, we propose a high speed Preamble Searcher suitable for the RACH (Random Access Channel) structure in WCDMA reverse link receivers. Unlike IS-95, WCDMA system uses the AISMA (Acquisition Indication Sense Multiple Access) scheme. Because of the time limit between RACH preamble transmission and AI (Acquisition Indicators), and the restriction on the number of RACH signatures assigned to RACH preamble, fast acquisition is required for efficient operation. The Preamble Searcher proposed in this paper is designed for 2-antenna systems; it adopts the FHT (Fast Hadamard Transform) algorithm that has the radix-2 16 point FFT (Fast Fourier Transform) structure. The acquisition speed using FHT is 32 times faster than the conventional method that correlates each signature. Based on this fast acquisition scheme, we improved the acquisition performance by calculating correlation up to 4096 chips of the total preamble length.

Petri nets with inhibitor arcs are referred to as inhibitor-arc Petri nets. It is shown that modeling capability of inhibitor-arc Petri nets is equivalent to that of Turing machines. The subject of this paper is the legal firing sequence problem (INLFS) for inhibitor-arc Petri nets: given an inhibitor-arc Petri net IN, an initial marking M0 and a firing count vector X, find a firing sequence δ such that its firing starts from M0 and each transition t appears in δ exactly X(t) times as prescribed by X. The paper is the first step of research for time complexity analysis and designing algorithms of INLFS, one of the most fundamental problems for inhibitor-arc Petri nets having more modeling capability than ordinary Peri nets. The recognition version of INLFS, denoted as RINLFS, means a decision problem, asking a "yes" or "no" answer on the existence of a solution δ to INLFS. The main results are the following (1) and (2). (1) Proving (1-1) and (1-2) when the underlying Petri net of IN is an unweighted state machine: (1-1) INLFS can be solved in pseudo-polynomial (O(|X|)) time for IN of non-adjacent type having only one special place called a rivet; (1-2) RINLFS is NP-hard for IN with at least three rivets; (2) Proving that RINLFS for IN whose underlying Petri net is unweighted and forward conflict-free is NP-hard. Heuristic algorithms for solving INLFS are going to be proposed in separate papers.

This paper proposes efficient DSP instructions and their hardware architecture for the Viterbi algorithm. The implementation of the Viterbi algorithm on a DSP chip has been attracting more interest for its flexibility, programmability, etc. The proposed architecture can reduce the Trace Back (TB) latency and can support various wireless communication standards. The proposed instructions perform the Add Compare Select (ACS) and TB operations in parallel and the architecture has special hardware, called the Offset Calculation Unit (OCU), which automatically calculates data addresses for acceleration of the trellis butterfly computations. When the constraint length K is 5, the proposed architecture can reduce the decoding cycles about 17% compared with Carmel DSP and about 45% compared with TMS320C55x.

This paper proposes a fast motion estimation algorithm for variable block-sizes by utilizing motion vector bottom-up procedure for H.264. The refined motion vectors of adjacent small blocks are merged to predict the motion vectors of larger blocks for reducing the computation. Experimental results show that our proposed method has lower computational complexity than full search, fast full search and fast motion estimation of the H.264 reference software JM93 with slight quality decrease and little bit-rate increase.

Multipath search based instantaneous root-mean-squared (RMS) delay spread (RDS) estimators mainly depend on path detection or multipath search. This paper proposes a novel method for multipath search through Minimum Descriptive Length (MDL) criterion, and hence a novel instantaneous RDS estimation method for wireless OFDM systems. compared with the conventional multipath search based instantaneous RDS estimators, the proposed estimator doesn't need any a priori information about the noise variance and the channel power delay profile (PDP) while the performance is improved. Simulation results demonstrate that the proposed estimator is also insensitive to the variance of SNR and robust against the frequency selectivity, as well as the vehicle speed.

We present a low power architecture that dynamically controls wordlengths in a wireless OFDM demodulator. Finding the optimum wordlength for digital circuit systems is difficult because the trade-off between the hardware cost and system performance is not conclusive. Actual circuit systems have large wordlengths at the circuit design level to avoid calculation errors caused by a lack of dynamic range. This indicates that power dissipation can still be reduced under better conditions. We propose a tunable wordlength architecture that dynamically changes its own wordlength according to the communication environment. The proposed OFDM demodulator measures error vector magnitudes (EVMs) from de-modulated signals and tunes the wordlength to satisfy the required quality of communication by monitoring the EVM performance. The demodulator can reduce dissipated energy by a maximum of 32 and 24% in AWGN and multipath fading channels.

We consider the reliability-based heuristic search methods for maximum likelihood decoding, which generate test error patterns (or, equivalently, candidate codewords) according to their heuristic values. Some studies have proposed methods for reducing the space complexity of these algorithms, which is crucially large for long block codes at medium to low signal to noise ratios of the channel. In this paper, we propose a new method for reducing the time complexity of generating candidate codewords by storing some already generated candidate codewords. Simulation results show that the increase of memory size is small.