Search

In this paper, a platform is presented, that given a Stochastic Context-Free Grammar (SCFG), automatically outputs the description of a parser in synthesizable Hardware Description Language (HDL) which can be downloaded in an FPGA (Field Programmable Gate Arrays) board. Although the proposed methodology can be used for various inexact models, the probabilistic model is analyzed in detail and the extension to other inexact schemes is described. Context-Free Grammars (CFG) are augmented with attributes which represent the probability values. Initially, a methodology is proposed based on the fact that the probabilities can be evaluated concurrently with the parsing during the parse table construction by extending the fundamental parsing operation proposed by Chiang & Fu. Using this extended operation, an efficient architecture is presented based on Earley's parallel algorithm, which given an input string, generates the parse table while evaluating concurrently the probabilities of the generated dotted grammar rules in the table. Based on this architecture, a platform has been implemented that automatically generates the hardware design of the parser given a SCFG. The platform is suitable for embedded systems applications where a natural language interface is required or in pattern recognition tasks. The proposed hardware platform has been tested for various SCFGs and was compared with previously presented hardware parser for SCFGs based on Earley's parallel algorithm. The hardware generated by the proposed platform is much less complicated than the one of comparison and succeeds a speed-up of one order of magnitude. [ABSTRACT FROM AUTHOR]

In this paper, we synthesize a Breakout game code which runs on an FPGA development and education board. For this purpose, an original Breakout game code that runs exclusively on the FPGA board is designed in VHDL hardware description language. The strength of this design is that the code does not require any SRAM modules for storage which eliminates the memory requirements and results in faster operation. Altera DE0 development and education board is used for the implementation. However, since only the standard VHDL functions is used in the code, it can run on any other FPGA boards. [ABSTRACT FROM AUTHOR]

In this paper, we propose an efficient symbol detection algorithm for multiple-input multiple-output spatial multiplexing (MIMO-SM) systems and present its design and implementation results. By enhancing the error performance of the first detected symbol that causes error propagation, the proposed algorithm achieves a considerable performance gain compared with the conventional sorted QR decomposition (SQRD) based detection and the ordered successive detection (OSD) algorithms. The bit error rate (BER) performance of the proposed detection algorithm is evaluated by a simulation. In the case of a 16QAM MIMO-SM system with 4 transmit and 4 receive (4 × 4) antennas, at BER = 10-3 the proposed algorithm results in a gain improvement of about 2.5-13.5 dB over the previous algorithms. The proposed detection algorithm was designed in a hardware description language (HDL) and synthesized to gate-level circuits using 0.18 μm 1.8 V CMOS standard cell library. The results show that the proposed algorithm can be implemented without increasing the hardware costs significantly. [ABSTRACT FROM AUTHOR]

In this paper a platform is presented, that given a stochastic context-free grammar (SCFG), automatically outputs the description of the parser in synthesizable hardware description language (HDL) which can be downloaded in an Field Programmable Gate Arrays (FPGA) board. Initially, according to our methodology the SCFG is augmented with attributes which store the probability values and can be evaluated through corresponding stack actions. The architecture of the produced system is based on a proposed extension of Earley's parallel algorithm, which given an input string, generates the parse trees in the form of an AND-Or parse tree. This AND-or parse tree is then traversed using a proposed tree traversal technique in order to execute the corresponding actions in the correct order, so as to compute the necessary probabilities. The platform is suitable for embedded systems applications where a natural language interface is required or in pattern recognition tasks. The parser generated by the presented platform has been tested for various SCFGs and compared to software approaches. The performance comparison is one to two orders of magnitude in favor of the presented hardware, compared to previous software approaches, depending on the application, the input string length and the number of produced trees. [ABSTRACT FROM AUTHOR]

In this paper, several hardware architectures for the realization of ensembles of axis-parallel, oblique and nonlinear decision trees (DTs) are presented. Hardware architectures for the implementation of a number of ensemble combination rules are also presented. These architectures are universal and can be used to combine predictions from any type of classifiers, such as decision trees, artificial neural networks (ANNs) and support vector machines (SVMs). Proposed architectures are suitable for the implementation using Field Programmable Gate Arrays (FPGA) and Application Specific Integrated Circuits (ASIC). Experiment results obtained using 29 datasets from the standard UCI Machine Learning Repository database suggest that the FPGA implementations offer significant improvement in the classification time in comparison with the traditional software implementations. Greatest improvement can be achieved using the SP2-P architecture implemented on the FPGA achieving 416.53 times faster classification speed on average, compared with the software implementation. This result has been achieved on the FPGA working at 135.51 MHz on average, which is 33.21 times slower than the operating frequency of the general purpose computer on which the software implementation has been executed. [ABSTRACT FROM AUTHOR]

This paper introduces a novel method for the conversion of synchronous cryptographic circuits into equivalent asynchronous ones. The new method is based on ASERT (Asynchronous Scheduling by Edge Reversal Timing), a fully decentralized timing signaling and synchronization algorithm. From a synthesizable HDL code, an asynchronous timing network, made from standard cells libraries, is generated in order to replace the clock tree of the target circuit. ASERT works with matched delays, local clocks or any equivalent way of determining, statically or dynamically, the operating time of each functional unit. Synchronous to asynchronous conversion of three different cryptographic circuits, including the fully synthesized netlists of AES, Reed-Solomon decoder, and RSA cipher cores, are presented. [ABSTRACT FROM AUTHOR]

In this paper, the descriptional complexity of extended finite splicing systems is studied. These systems are known to generate exactly the class of regular languages. Upper and lower bounds are shown relating the size of these splicing systems, defined as the total length of the rules and the initial language of the system, to the size of their equivalent minimal nondeterministic finite automata (NFA). In addition, an accepting model of extended finite splicing systems is studied. Using this variant one can obtain systems which are more than polynomially more succinct than the equivalent NFA or generating extended finite splicing system. [ABSTRACT FROM AUTHOR]

Modern complex system design demands modeling on a high level of abstraction together with the system environment components. Such model enables mission level system simulation in the context of its operational conditions. Mission level design using hardware description language AleC++ is presented in this paper. It provides mission and system level verification of a mixed-signal system-on-chip. After validation at mission and system level, this language enables designers to replace some of the components with implementation level models to test and validate the system implementation at mission level. Also, the language provides modeling capabilities that give the designer an opportunity to analyze the influence of low-level technological and environmental parameters to the complete system behavior. In this way a uniform design framework is achieved from mission/system down to implementation level. The application of the language both for mission/system and implementation level modeling is illustrated by an example of the electronic compass. [ABSTRACT FROM AUTHOR]

Gemmating P systems were introduced as a theoretical model based on the biological idea of the gemmation of mobile membranes. In the general model of extended gemmating P systems, strings are modified either by evolution rules in the membranes or while sending them to another membrane. We here consider the restricted variant of extended gemmating P systems with pre-dynamic rules where strings are only modified at the ends while sending them from one membrane to another one. In a series of papers the number of membranes being sufficient for obtaining computational completeness has steadily been decreased. In this paper we now prove the optimal result, i.e., gemmating P systems only using pre-dynamic rules are already computationally complete with three membranes, even in the non-extended case and with the minimal weight of rules possible. Moreover, we also show that for gemmating tissue P systems two cells suffice, and if we allow the environment to be fully involved in the communication of strings, even one cell together with the environment can manage the task to generate any recursively enumerable language. [ABSTRACT FROM AUTHOR]

This paper presents an evolutionary algorithm to solve the datapath allocation problem in high-level synthesis. The method performs allocation of functional units, registers, and multiplexers in addition to controller synthesis with the objective of minimizing the cost of hardware resources. The system handles multicycle functional units as well as structural pipelining. The proposed method was implemented using C++ on a Linux workstation. We tested our method on a set of high-level synthesis benchmarks, all yielding good solutions in a short time. An integration path to Field Programmable Gate Arrays (FPGAs) is provided through VHDL. [ABSTRACT FROM AUTHOR]

Redundant Binary (RB) to Two's Complement (TC) converter offers nonredundant representation. However, the sign bit of TC representation has to be handled using nonstandard hardware blocks. The concept of Inverted encoding of negative weighted bits (IEN) eliminates the need of sign extension and offers design only using predefined hardware blocks. NonRedundant Binary (NRB) representation refers to both conventional and IEN representations. The NRB representation is also useful considering problem related to shifting in Carry Save (CS) representation of a RB number. In this paper, we have proposed two new conversion circuits for RB to NRB representation. The proposed circuits of the RB to NRB converter are coded in Verilog Hardware Description language (HDL) and synthesized using the Encounter(R) RTL Compiler RC13.10 v13.10-s006_1 of Cadence tool considering ASIC platform. Considering 64 bits' operand, the delay power product performances of proposed one-bit and two-bit computations offer improvement of almost 29.9% and 47%, respectively as compared to Carry-Look-Ahead (CLA). The proposed one-bit converter is also applied in the final stage of the Modified Redundant Binary Adder (MRBA). The 32-bit MRBA offers a delay improvement of 7.87% replacing conventional converter with proposed one-bit converter in same FPGA 4vfx12sf363-12 device. [ABSTRACT FROM AUTHOR]

Non-recursive trade-offs between different representations of languages reveal a basic phenomenon. The gain in economy of description can be arbitrary. The purpose of this paper is to survey the main aspects and results regarding different representations of languages whose relative succinctness is not recursively bounded. Basic properties of descriptional systems and reasonable size measures are addressed, and the unified fundamental proof schemes emerging from the literature are presented. A comprehensive overview of results is given. Finally, some new results are shown. In particular, it is proved that between each two levels of the infinite one-way k-head finite automata hierarchies there is a non-recursive trade-off. Moreover, non-recursive trade-offs are shown between nondeterministic 2-head and deterministic k-head automata. [ABSTRACT FROM AUTHOR]

This paper presents the development of a reduced-order macro-model for a two-axis electrostatic torsional micromirror using analog hardware description language (AHDL). The proposed macromodel permits extremely fast simulation while providing nearly FEM accuracy. This enables the user to investigate the close-loop controlled global system level performances at acceptable computational cost. [ABSTRACT FROM AUTHOR]

Networks on Chip (NoCs) are commonly used to integrate complex embedded systems and multiprocessor platforms due to their scalability and versatility. Modeling tools used at the functional level use SystemC to perform hardware-software co-design and error correction concurrently, thus, reducing time to market. This work analyzes a JPEG encoding algorithm mapped onto a configurable M × N, mesh/torus, NoC platform described in SystemC with the transaction level modeling (TLM) standard; timing constraints for both, the router and network interface controller, are assigned according to a hardware description language (HDL) model written for this purpose. Processing nodes are also described as SystemC threads and their computation delays are assigned depending on the amount and cost of the operations they perform. The programming model employed is message passing. We start by describing and profiling the JPEG algorithm as a task graph; then, four partitioning proposals are mapped onto three NoCs of different size. Our analysis comprises changes in topology, virtual channel depth, routing algorithms, network speed and task-node assignments. Through several high-level simulations we evaluate the impact of each parameter and we show that, for the proposed model, most improvements come from the algorithm partitioning. [ABSTRACT FROM AUTHOR]

Limitations caused by degeneration of dynamics characteristics may exist in the traditional single chaotic system. The authors propose a method i.e., switch controller chaos and pseudo random bit generator (it is called SCS-PRBG for short), which is based on multiple chaotic systems and switch control. By the theoretic analysis of random key stream and performance of SCS-PRBG, we can see that its digital stream cipher has better randomicity and security. And if using hardware parallel computation, the speed of encryption can be improved sharply. The results of the experiments also present better security of this arithmetic. [ABSTRACT FROM AUTHOR]

We study lower bounds on space and input head reversals for deterministic, nondeterministic, and alternating Turing machines accepting nonregular languages. Three notions of space, namely strong, middle, weak are considered, and another notion, called accept, is introduced. In all cases, we obtain tight lower bounds. Moreover, we show that, while for determinism and nondeterminism such lower bounds are optimal even with respect to unary languages, for alternation optimal lower bounds for unary languages turn out to be strictly higher than those for languages over alphabets with two or more symbols. [ABSTRACT FROM AUTHOR]