19122402
Moduli selection in RNS for efficient VLSI implementation
In this paper, we carry out a study on an important issue concerning the use of residue numbers in the design of digital systems, namely, the moduli selection. Based on a new formulation of the Chinese remainder theorem and the efficient residue-to-binary (R/B) converters designed therefrom, we propose a guideline for the selection of the low-cost moduli sets for different dynamic ranges. These sets consist of the low-cost moduli of the form 2/sup n/, ( 2/sup n/-1) or (2/sup n/ + 1), which can offer simplified modulo adders and multipliers. It is shown that for medium dynamic ranges (less than 22 bits), the three-moduli set {2/sup n/,2/sup n/ + 1,2/sup n/ - 1} is the most efficient one in terms of the design of a complete RNS system. On the other hand, for large dynamic ranges (equal to or larger than 22 bits), the general-moduli set in the form (2/sup n/, 2/sup n/ + 1,2/sup n/ - 1,2/sup n/ /spl plusmn/1,...,2/sup n/, /spl plusmn/1), with a length greater than three, is the most efficient one. These results provide the possibility of a wide range of applications of the residue number system in the design of DSP, telecommunication and cryptography systems.
29637234
A new architecture of RRNS error-correcting QC encoder/decoder and its FPGA implementation
In this paper, a new architecture of a redundant residue number system (RRNS) quasi-chaotic (QC) encoder/decoder with an error-correcting ability is proposed for secure communication and is tailored to FPGA implementation. In the proposed architecture, binary subencoders and subdecoders are used so that a number of modulo operations required in the existing design of D. R. Frey (IEEE Trans. Circuits Syst. II, vol. 40, pp. 660-666, Oct. 2000) are replaced by a simple truncation. Furthermore, a size-reduced design of the R/B (residue-to-binary) converter with error-correcting function, which is the crucial part of the system, is proposed. As a case study, the proposed architecture is implemented in FPGA for the case of the 16-bit input and some simulation results obtained.
29715580
A high-speed residue-to-binary converter and a scheme for its VLSI implementation
In this paper, a high-speed residue-to-binary converter for the recently introduced moduli set (2/sup k/, 2/sup k/-1, 2/sup k-1/-1) is proposed. Compared to the previous converter based on this moduli set, the proposed one is 40% faster; also, the time-complexity product is improved by 20%. Following the VLSI design flow established by the Canadian Microelectronics Corporation, the proposed converter is implemented in 0.5-micron CMOS technology. Based on this moduli set, layouts of the 8-bit, 16-bit, 32-bit and 64-bit residue-to-binary converters which can be used in further RNS system designs, are generated and simulation results obtained.
15012785
An area-reduced scheme for modulo 2/sup n/-1 addition/subtraction
In this paper, we present a versatile area-reduced scheme for modulo 2/sup n/-1 adders and subtracters using a MUX-based increment/decrement algorithm. A FPGA-based comparison of the proposed modulo adder and the conventional modulo adder designs is carried out. The implementation results show that the proposed adder reduces the area close to 30% compared with the modulo adder of Bayoumi et al. The delay and the power are also reduced around 10%. In addition, it is also shown that the proposed design requires less hardware resources than the parallel-prefix modulo adder of Kalampoukas et al. while providing a comparable operation speed.
15644746
RRNS quasi-chaotic coding and its FPGA implementation
In this paper, a new architecture of the redundant residue number system (RRNS) based quasi-chaotic coding is proposed for the secure telecommunication systems and networks. In the proposed architecture, a number of modulo operations required by the existing designs are replaced by binary coding operations to simplify the design. Also, a moduli selection method and a residue-to-binary converter with error-correction capability are proposed to further improve the efficiency of the design specifically for FPGA implementation. The proposed architecture is implemented and tested using Matlab and Xilinx FPGA hardware. The results show that compared to the existing design, the proposed design requires only 80% of the hardware resources while maintaining the same speed. The power consumption is also reduced by 25%.
31496165
Elliptic curves cryptosystem implementation based on a look-up table sharing scheme
Projective point elliptic curve cryptography (ECC) involves many look-up table-based field multiplications. In this paper, a novel lookup table sharing scheme is proposed to significantly reduce the number of the field multiplications and number of lookup tables. By requiring much less lookup table generation time, the proposed system offers high-speed performance for hardware realizations. Its application in a reconfigurable PC-FPGA platform is investigated, which can efficiently handle requests for different ECC key length and curves and is useful for many computer network applications
139968
Efficient Pattern-Growth Methods for Frequent Tree Pattern Mining
Mining frequent tree patterns is an important research problems with broad applications in bioinformatics, digital library, e-commerce, and so on. Previous studies highly suggested that pattern-growth methods are efficient in frequent pattern mining. In this paper, we systematically develop the pattern growth methods for mining frequent tree patterns. Two algorithms, Chopper and XSpanner, are devised. An extensive performance study shows that the two newly developed algorithms outperform TreeMinerV [13], one of the fastest methods proposed before, in mining large databases. Furthermore, algorithm XSpanner is substantially faster than Chopper in many cases.
5447146
Mining long sequential patterns in a noisy environment
Pattern discovery in long sequences is of great importance in many applications including computational biology study, consumer behavior analysis, system performance analysis, etc. In a noisy environment, an observed sequence may not accurately reflect the underlying behavior. For example, in a protein sequence, the amino acid N is likely to mutate to D with little impact to the biological function of the protein. It would be desirable if the occurrence of D in the observation can be related to a possible mutation from N in an appropriate manner. Unfortunately, the support measure (i.e., the number of occurrences) of a pattern does not serve this purpose. In this paper, we introduce the concept of compatibility matrix as the means to provide a probabilistic connection from the observation to the underlying true value. A new metric match is also proposed to capture the "real support" of a pattern which would be expected if a noise-free environment is assumed. In addition, in the context we address, a pattern could be very long. The standard pruning technique developed for the market basket problem may not work efficiently. As a result, a novel algorithm that combines statistical sampling and a new technique (namely border collapsing) is devised to discover long patterns in a minimal number of scans of the sequence database with sufficiently high confidence. Empirical results demonstrate the robustness of the match model (with respect to the noise) and the efficiency of the probabilistic algorithm.
33979500
Decentralized adaptive backstepping stabilization of interconnected systems with dynamic input and output interactions
So far there is still no result available for backstepping based decentralized adaptive stabilization of unknown systems with interactions directly depending on subsystem inputs, even though such interactions commonly exist in practice. In this paper, we provide a solution to this problem by considering both input and output dynamic interactions. To clearly illustrate our approaches, we will start with linear systems and then extend the results to nonlinear systems. Each local controller, designed simply based on the model of each subsystem by using the standard adaptive backstepping technique without any modification, only employs local information to generate control signals. It is shown that the designed decentralized adaptive backstepping controllers can globally stabilize the overall interconnected system asymptotically. The L"2 and L"~ norms of the system outputs are also established as functions of design parameters. This implies that the transient system performance can be adjusted by choosing suitable design parameters.
14070336
Image segmentation via brittle fracture mechanics
Brittle material like ceramic and rock has the nature that it is hard to crack, but if it is to crack it will crack into not dangling pieces, but separate pieces whose boundaries are contours that link up positions of strong stress in a continuous and often smooth fashion. Image segmentation desires similar results: it is to partition the image so that each partition corresponds to a separate surface or object in the imaged scene, whose boundaries are continuous and often smooth contours with a dense concentration of large intensity gradients. This work explores the adaptation of brittle fracture mechanics model toward image segmentation. An image is regarded as a plate experiencing brittle fracture when external forces arc exerted on it according to intensity gradient distribution in the image. Stress concentrations due to the external forces and its change over time due to changing crack distribution are what determine the development of cracks. Real image results indicate that the model is promising.
3251955
Containment join size estimation: models and methods
Recent years witnessed an increasing interest in researches in XML, partly due to the fact that XML has now become the de facto standard for data interchange over the internet. A large amount of work has been reported on XML storage models and query processing techniques. However, few works have addressed issues of XML query optimization. In this paper, we report our study on one of the challenges in XML query optimization: containment join size estimation. Containment join is well accepted as an important operation in XML query processing. Estimating the size of its results is no doubt essential to generate efficient XML query processing plans. We propose two models, the interval model and the position model, and a set of estimation methods based on these two models. Comprehensive performance studies were conducted. The results not only demonstrate the advantages of our new algorithms over existing algorithms, but also provide valuable insights into the tradeoff among various parameters.