This paper shows a design method for a regular expression matching circuit based on a decomposed automaton. To implement a regular expression matching circuit, first, we convert a regular expression into a non-deterministic finite automaton (NFA). Then, to reduce the number of states, we convert the NFA into a merged-states non-deterministic finite automaton with unbounded string transition (MNFAU) using a greedy algorithm. Next, to realize it by a feasible amount of hardware, we decompose the MNFAU into a deterministic finite automaton (DFA) and an NFA. The DFA part is implemented by an off-chip memory and a simple sequencer, while the NFA part is implemented by a cascade of logic cells. Also, in this paper, we show that the MNFAU based implementation has lower area complexity than the DFA and the NFA based ones. Experiments using regular expressions form SNORT shows that, as for the embedded memory size per a character, the MNFAU is 17.17-148.70 times smaller than DFA methods. Also, as for the number of LCs (Logic Cells) per a character, the MNFAU is 1.56-5.12 times smaller than NFA methods. This paper describes detail of the MEMOCODE2010 HW/SW co-design contest for which we won the first place award.

Face detection has been an independent technology playing an important role in more and more fields, which makes it necessary and urgent to have its architecture reconfigurable to meet different demands on detection capabilities. This paper proposed a face detection architecture, which could be adjusted by the user according to the background, the sensor resolution, the detection accuracy and speed in different situations. This user adjustable mode makes the reconfiguration simple and efficient, and is especially suitable for portable mobile terminals whose working condition often changes frequently. In addition, this architecture could work as an accelerator to constitute a larger and more powerful system integrated with other functional modules. Experimental results show that the reconfiguration of the architecture is very reasonable in face detection and synthesized report also indicates its advantage on little consumption of area and power.

The main benefit of HECC is that it has much smaller parameter sizes and offers equivalent security as ECC and RSA. However, there are still more researches on ECC than on HECC. One of the reasons is that the computation of scalar multiplication cannot catch up. The Kummer surface can speed up the scalar multiplication in genus two curves. In this paper, we find that the scalar multiplication formulas of Duquesne in characteristic p > 3 on the Kummer surface are not correct. We verify and revise the formulas with mathematical software. The operation counts become 29M + 2S for new pseudo-addition formulas and 30M + 10S for doubling ones. And then we speed up the scalar multiplication on the Kummer surface with Euclidean addition chains.

The problem of a Gaussian beam that is incident on a plane dielectric interface from a denser dielectric medium to a rarer one and is reflected at the interface has been important research subjects studied by many researchers. In this paper, we have obtained a novel uniform asymptotic solution for reflection and beam shift of the Gaussian beam that is incident on the interface from the denser medium. The uniform asymptotic solution consists of the geometrically reflected beam, the lateral beam if any, and the newly derived transition beam which plays an important role in the transition region near the critical angle of the total reflection. We have confirmed the validity of the uniform asymptotic solution by comparing with the reference solution obtained numerically from the integral representation. We have shown that, in addition to the Goos-Hanchen shift and the angular shift, the Gaussian beam is shifted to either direction by the interference of the geometrically reflected beam and the lateral beam near the critical angle of the total reflection.

This paper proposes a differential fault analysis on the stream cipher MUGI, which uses two kinds of update functions of an intermediate state. MUGI was proposed by Hitachi, Ltd. in 2002 and is specified as ISO/IEC 18033-4 for keystream generation. Differential fault analysis (DFA) is a type of fault analysis, which is considered to be a serious threat against secure devices such as smart cards. DFA on MUGI was first proposed at ICISC 2010 [25]; however, the attack condition for the successful attack such as the position into which the fault is injected was restricted. In this paper, we extend the attack methods which are more practical, based on a one-byte and a multi-byte fault models using the relationship between two kinds of update functions that are mutually dependent. In the proposed attack, the attacker can know the position affected by the fault injection even if he has no control of the timing of the fault injection. As a result, a 128-bit secret key can be recovered using 13 pairs of correct and faulty outputs on average.

This paper proposes the countermeasures against an improved fault sensitivity analysis. Our countermeasure is proposed based on the WDDL technique due to its built-in resistance against both the power-based attack and differential fault analysis. At CHES 2010, Li et al. proposed the FSA attack on WDDL-AES. The vulnerability of WDDL-AES in their attack mainly comes from the implementation deficiency rather than the WDDL technique itself. This paper first proposes an improved fault sensitive analysis that can threat a well-implemented WDDL-AES based on the input-data dependency for the critical path delay of WDDL S-box. Then we discuss the possibility of efficient countermeasures by modifying the WDDL circuit with a limited overhead. The countermeasures are discussed based on either modifying the dual-rail to single-rail converter or the introduction of the enable signal.

This paper presents a glitchy-clock generator integrated in FPGA for evaluating fault injection attacks and their countermeasures on cryptographic modules. The proposed generator exploits clock management capabilities, which are common in modern FPGAs, to generate clock signal with temporal voltage spike. The shape and timing of the glitchy-clock cycle are configurable at run time. The proposed generator can be embedded in a single FPGA without any external instrument (e.g., a pulse generator and a variable power supply). Such integration enables reliable and reproducible fault injection experiments. In this paper, we examine the characteristics of the proposed generator through experiments on Side-channel Attack Standard Evaluation Board (SASEBO). The result shows that the timing of the glitches can be controlled at the step of about 0.17 ns. We also demonstrate its application to the safe-error attack against an RSA processor.

Error analysis of the multilevel fast multipole algorithm is studied for electromagnetic scattering problems. We propose novel error prediction and control methods and verify that the computational error for scattering problems with over one million unknowns can be precisely controlled under desired digits of accuracy. Optimum selection of truncation numbers to minimize computational error also will be discussed.

Soft error has become an increasingly significant concern in modern micro-processor design, it is reported that the instruction-level temporal redundancy in out-of-order cores suffers an performance degradation up to 45%. In this work, we propose a fault tolerant architecture with fast error correcting codes (such as the two-dimensional code) based on double execution. Experimental results show that our scheme can gain back IPC loss between 9.1% and 10.2%, with an average around 9.2% compared with the conventional double execution architecture.

Soft errors caused by energetic particle strikes in on-chip cache memories have become a critical challenge for microprocessor design. Architectural vulnerability factor (AVF), which is defined as the probability that a transient fault in the structure would result in a visible error in the final output of a program, has been widely employed for accurate soft error rate estimation. Recent studies have found that designing soft error protection techniques with the awareness of AVF is greatly helpful to achieve a tradeoff between performance and reliability for several structures (i.e., issue queue, reorder buffer). Considering large on-chip L2 cache, redundancy-based protection techniques (such as ECC) have been widely employed for L2 cache data integrity with high costs. Protecting caches without accurate knowledge of the vulnerability characteristics may lead to the over-protection, thus incurring high overheads. Therefore, designing AVF-aware protection techniques would be attractive for designers to achieve a cost-efficient protection for caches, especially at early design stage. In this paper, we propose an improved AVF estimation framework for conducing comprehensive characterization of dynamic behavior and predictability of L2 cache vulnerability. We propose to employ Bayesian Additive Regression Trees (BART) method to accurately model the variation of L2 cache AVF and to quantitatively explain the important effects of several key performance metrics on L2 cache AVF. Then we employ bump hunting technique to extract some simple selecting rules based on several key performance metrics for a simplified and fast estimation of L2 cache AVF. Using the simplified L2 cache AVF estimator, we develop an AVF-aware ECC technique as an example to demonstrate the cost-efficient advantages of the AVF prediction based dynamic fault tolerant techniques. Experimental results show that compared with traditional full ECC technique, AVF-aware ECC technique reduces the L2 cache access latency by 16.5% and saves power consumption by 11.4% for SPEC2K benchmarks averagely.

In the scattering problem of periodic gratings, at a low grazing limit of incidence, the incident plane wave is completely cancelled by the reflected wave, and the total wave field vanishes and physically becomes a dark shadow. This problem has received much interest recently. Nakayama et al. have proposed “the shadow theory”. The theory was first applied to the diffraction by perfectly conductive gratings as an example, where a new description and a physical mean at a low grazing limit of incidence for the gratings have been discussed. In this paper, the shadow theory is applied to the analyses of multilayered dielectric periodic gratings, and is shown to be valid on the basis of the behavior of electromagnetic waves through the matrix eigenvalue problem. Then, the representation of field distributions is demonstrated for the cases that the eigenvalues degenerate in the middle regions of multilayered gratings in addition to at a low grazing limit of incidence and some numerical examples are given.

Satellite-borne SAR (synthetic aperture radar) is for high-resolution geosurface measurements. Recently, a feature extraction method based on CCD (coherent change detection) was developed, where a slight surface change on the geosurface is detected using the phase relationship between sequential complex SAR images of the same region made at different times. For accurate detection of the surface change, the log-likelihood method has been proposed. This method determines an appropriate threshold for change detection, making use of the phase characteristic of the changed area, and thus enhances the detection probability. However, this and other conventional methods do not seek to proactively employ phase information of the estimated coherence function, and their detection probability is often low, especially in the case that the target has small surface or local uniform changes. To overcome this problem, this paper proposes a novel transformation index that considers the phase difference of the coherence function. Furthermore, we introduce a pre-processing calibration method to compensate the bias error for the coherence phase which resulting mainly from the orbit error of the antenna platform. Finally, the results from numerical simulations and experiment modeling of the geosurface measurement verify the effectiveness of the proposed method, even in situations with low SNR (signal to noise ratio).

In multimedia communication, due to the limited computational capability of the personal information machine, a coder with low computational complexity is needed to integrate services from several media sources. This paper presents two efficient candidate schemes to simplify the most computationally demanding operation, the excitation codebook search procedure. For fast adaptive codebook search, we propose an algorithm that uses residual signals to predict the candidate gain-vectors of the adaptive codebook. For the fixed codebook, we propose a fast search algorithm using an energy function to predict the candidate pulses, and we redesign the codebook structure to twin multi-track positions architecture. Overall simulation results indicate that the average perceptual evaluation of speech quality (PESQ) score is degraded slightly, by 0.049, and our proposed methods can reduce total computational complexity by about 67% relative to the original G.723.1 encoder computation load, and with perceptually negligible degradation. Objective and subjective evaluations verify that the more efficient candidate schemes we propose can provide speech quality comparable to that using the original coder approach.

This paper deals with the diffraction of a transverse magnetic (TM) plane wave by a perfectly conductive periodic surface by an integral method. However, it is known that a conventional integral method does not work for a critical angle of incidence, because of divergence of a periodic Green's function (integral kernel). To overcome such a divergence difficulty, we introduce an image Green's function which is physically defined as a field radiated from an infinite phased array of dipoles. By use of the image Green's function, it is newly shown that the diffracted field is represented as a sum of radiation from the periodic surface and its image surface. Then, this paper obtains a new image integral equation for the basic surface current, which is solved numerically. A numerical result is illustrated for a very rough sinusoidal surface. Then, it is concluded that the method of image Green's function works practically even at a critical angle of incidence.

Orthogonal frequency division multiple access (OFDMA) is adopted as a multiuser access scheme in recent cellular systems such as long term evolution (LTE) and WiMAX. In those systems, the performance improvement on cell-edge users is crucial to provide high-speed services. We propose a new resource allocation scheme based on multiple input multiple output – orthogonal frequency division multiple access – code division multiplexing (MIMO-OFDMA-CDM) to achieve performance improvements in terms of cell-edge user throughput, bit error rate, and fairness among users. The proposed scheme adopts code division multiplexing for MIMO-OFDMA and a modified proportional fairness algorithm for CDM, which enables the fairness among users and a higher throughput. The performance improvements are clarified by theoretical analysis and simulations.

To estimate the field emission current associated with an array of carbon nanowalls (CNWs), the model of the floating rods between anode and cathode plates was proposed. An approximate formula for the enhancement factor was derived, showing that the interwall distance of the CNW array critically affects the field emission. The field enhancement factor was almost one order of magnitude less than that of vertically aligned CNTs. Considering the field emission current density, the field emission can be optimized when the interwall distance is comparable with the wall height. For same separation distance, the macroscopic field strength of the CNW array is almost one order of magnitude higher than that of vertical CNT array to obtain the emission current of 1 mA from the cathode surface of 1 cm2.

This paper presents a method of generating sets of orthogonal and zero-correlation zone (ZCZ) periodic real-valued sequences of period 2n, n ≥ 1. The sequences admit a fast correlation algorithm and the sets of sequences achieve the upper bound on family size. A periodic orthogonal sequence has the periodic autocorrelation function with zero sidelobes, and a set with orthogonal sequences whose mutual periodic crosscorrelation function at zero shift is zero. Similarly, a ZCZ set is the set of the sequences with zero-correlation zone. In this paper, we derive the real-valued periodic orthogonal sequences of period 2n from a real-valued Huffman sequence of length 2ν+1, ν being a positive integer and ν ≥ n, whose aperiodic autocorrelation function has zero sidelobes except possibly at the left and right shift-ends. The orthogonal and ZCZ sets of real-valued periodic orthogonal sequences are useful in various systems, such as synchronous code division multiple access (CDMA) systems, quasi-synchronous CDMA systems and digital watermarkings.

This paper proposes a test scheduling method for stuck-at faults in a CHAIN interconnect, which is an asynchronous on-chip interconnect architecture, with scan ability. Special data transfer which is permitted only during test, is exploited to realize a more flexible test schedule than that of a conventional approach. Integer linear programming (ILP) models considering such special data transfer are developed according to the types of modules under test in a CHAIN interconnect. The obtained models are processed by using an ILP solver. This framework can not only obtain optimal test schedules but also easily introduce additional constraints such as a test power budget. Experimental results using benchmark circuits show that the proposed method can reduce test application time compared to that achieved by the conventional method.

This paper presents an interconnect resilient (IR) methodology with maximal interconnect fault tolerance, yield, and reliability for both single and multiple interconnect faults under stuck-at and open fault models. By exploiting multiple routes inherent in an interconnect structure, this method can tolerate faulty connections by efficiently finding alternative paths. The proposed approach is compatible with previous interconnect detection and diagnosis methods under oscillation ring schemes, and together they can be applied to implement a robust interconnect structure that may still provide correct communication even under multiple link faults in Network-on-Chips (NoCs). With such knowledge, designers can significantly improve interconnect reliability by augmenting vulnerable interconnect structures in NoCs. As a result, the experimental results show that alternative paths in NoCs can be found for almost all paths. Hence, the proposed method provides a good way to achieve fault tolerance and reliability/yield improvement.

In order to improve the cell boundary throughput performance and to extend the coverage area, relaying transmission with relay stations (RSs) is becoming a promising architecture for the next generation cellular systems. However, if RSs are operated in every cell, the interference between cells increases and the throughput improvement effect with RSs is prone to be restricted. In this paper, we propose a scheme reducing the interference from other cells by using packet transmission control. This packet transmitting control technique is realized by the compound scheduling technique with the Proportional fair (PF) scheduling and the Maximum Carrier-to-Interference power Ratio (Max CIR) scheduling. The proposed scheme can improve the throughput around the cell boundary by controlling the timing of transmission of each cell with appropriate power and user assignment. The simulation results show that the proposed method can also improve the fairness of user throughput and system throughput considering the users of whole cell.