A pre-trained convolutional deep neural network (CNN) is the feed-forward computation perspective, and it is widely used for the embedded vision systems. One of the applications of the CNN is a frame object detection problem. It is widely used in the embedded systems, such as a robot, an automobile, a security camera, and a drone, that require a highly performance-power efficient device. In the CNN, the 2D convolutional operation occupies more than 90time. Since the 2D convolutional operation performs massive multiply-accumulation (MAC) operations, conventional realizations could not implement a fully parallel CNN. The RNS decomposes an integer into a tuple of integers by residues of moduli set. Since no pair of modulus has a common factor with any other, the conventional RNS decomposes the MAC unit into circuits with different sizes means that the RNS could not utilize resources of an FPGA with uniform size. In this paper, we use the nested RNS (NRNS), which recursively decompose the RNS. It can decompose the MAC unit into circuits with small sizes. In the CNN using the NRNS, a MAC unit is decomposed into 4-bit ones realized by look-up tables of the FPGA. Thus, it leads to a high clock frequency with less hardware. We designed the Tiny YOLOv2 for the practical object detection, and it using the CNN based on the NRNS is implemented on a Digilent NetFPGA-SUME FPGA board. Compared with the NVidia GTX1080Ti (Pascal architecture) for the designed Tiny YOLOv2, the FPGA using the NRNS was 3.19 times better than the GPU as for the performance-power efficiency.

Ternary content addressable memories (TCAMs) are special memories which are widely used in high-speed network applications such as routers, firewalls, and network address translators. In high-reliability network applications such as aerospace and defense systems, soft-error tolerant TCAMs are indispensable to prevent data corruption or faults caused by radiation. This paper shows a novel way in generating keys to cover the correct match. It proposes a novel soft-error tolerant TCAM for multiple-bit-flip errors using partial don't-care keys (X-keys). First, this paper observes the case of single-bit-flip errors by X-TCAM. Second, it extends the X-TCAM to the case of multiple-bit-flip errors called KX-TCAM, where K stands for the maximum number of errors k. KX-TCAM corrects up to k-bit-flip errors and enhances the tolerance of the TCAM against soft errors, where k is the maximum number of bit flips in a word of a TCAM. KX-TCAM consists of a TCAM, a preprocessed don't-care-bit index look-up memory (X look-up), and a backup error checking and correction (ECC)-SRAM. First, KX-TCAM randomly selects a search key. After that, KX-TCAM detects multiple-bit-flip errors by the generated X-keys using the X look-up. If the keys match the different locations, then a soft error is suspected and KX-TCAM refreshes the TCAM words by using the backup ECC-SRAM. Experimental results show that the soft-error tolerance capability of KX-TCAM significantly outperforms existing state-of-the-art schemes. Moreover, the hardware overhead of KX-TCAM is small due to the use of a single TCAM. KX-TCAM can be easily implemented and is useful for fault-tolerant packet classifiers.

Index generation functions are useful for pattern matching. This paper presents an algorithm to find support-reducing decompositions for index generation functions. Let n be the number of the input variables, and let s be the number of bound variables. Then, the exhaustive search for finding an optimum support-reducing decomposition requires to check (ns) combinations. We found a special property of index generation functions that drastically reduces this search space. With this property, we developed a fast algorithm. For a given number of bound variables, it finds a decomposition with the fewest rails. Experimental results up to n = 60 and s = 33 are shown.

A pre-trained deep convolutional neural network (CNN) is a feed-forward computation perspective, which is widely used for the embedded systems, requires high power-and-area efficiency. This paper realizes a binarized CNN which treats only binary 2-values (+1/-1) for the inputs and the weights. In this case, the multiplier is replaced with an EX-NOR circuit. To reduce both power and area, we realize the 2-valued CNN by off- and on-chip memories. Since our 2D convolution operations are realized by the on-chip memory, our implementation consumes lower power than the DSP block. We decompose the memory part, and realize them by a cascade of memories (LUT cascade). By introducing a batch normalization technique, the classification error for the binarized CNN can be improved. We implemented the CIFAR-10 benchmark on the NetFPGA-SUME board, which has the Xilinx Inc. Virtex 7 FPGA and three on-chip QDR II+ Synchronous SRAMs. Compared with the conventional FPGA realizations, the performance is 2.82 times faster, the power efficiency is 1.76 times, and the area efficiency is 29.13 times better.

This paper proposes a novel soft-error tolerant TCAM using partial don't-care keys (X-keys), namely TX, which significantly enhances the tolerance of the TCAM against soft errors. Experimental results show that the soft-error tolerance of the TX outperforms existing schemes. Moreover, the overhead of the TX is very small.

A pre-trained deep convolutional neural network (DCNN) is the feed-forward computation perspective which is widely used for the embedded vision systems. In the DCNN, the 2D convolutional operation occupies more than 90% of the computation time. Since the 2D convolutional operation performs massive multiply-accumulation (MAC) operations, conventional realizations could not implement a fully parallel DCNN. The RNS decomposes an integer into a tuple of L integers by residues of moduli set. Since no pair of modulus have a common factor with any other, the conventional RNS decomposes the MAC unit into circuits with different sizes. It means that the RNS could not utilize resources of an FPGA with uniform size. In this paper, we propose the nested RNS (NRNS), which recursively decompose the RNS. It can decompose the MAC unit into circuits with small sizes. In the DCNN using the NRNS, a 48-bit MAC unit is decomposed into 4-bit ones realized by look-up tables of the FPGA. In the system, we also use binary to NRNS converters and NRNS to binary converters. The binary to NRNS converter is realized by on-chip BRAMs, while the NRNS to binary one is realized by DSP blocks and BRAMs. Thus, a balanced usage of FPGA resources leads to a high clock frequency with less hardware. The ImageNet DCNN using the NRNS is implemented on a Xilinx Virtex VC707 evaluation board. As for the performance per area GOPS (Giga operations per second) per a slice, the proposed one is 5.86 times better than the existing best realization.

We demonstrate circuits that generate set and integer partitions on a set S of n objects at a rate of one per clock. Partitions are ways to group elements of a set together and have been extensively studied by researchers in algorithm design and theory. We offer two versions of a hardware set partition generator. In the first, partitions are produced in lexicographical order in response to successive clock pulses. In the second, an index input determines the set partition produced. Such circuits are useful in the hardware implementation of the optimum distribution of tasks to processors. We show circuits for integer partitions as well. Our circuits are combinational. For large n , they can have a large delay. However, one can easily pipeline them to produce one partition per clock period. We show (1) analytical and (2) experimental time/complexity results that quantify the efficiency of our designs. For example, our results show that a hardware set partition generator running on a 100MHz FPGA produces partitions at a rate that is approximately 10 times the rate of a software implementation on a processor running at 2.26GHz.

This paper presents a packet classifier using multiple LUT cascades based on edge-valued multi-valued decision diagrams (EVMDDs (k)). First, a set of rules for a packet classifier is partitioned into groups. Second, they are decomposed into field functions and Cartesian product functions. Third, they are represented by EVMDDs (k), and finally, they are converted to LUT cascades using adders. We implemented the proposed circuit on a Virtex 7 VC707 evaluation board. The system throughput is 345.60 Gbps for minimum packet size (40 Bytes). As for the normalized throughput (efficiency), the proposed one is 7.14 times better than existing FPGA implementations.

In the internet, packets are classified by source and destination addresses and ports, as well as protocol type. Ternary content addressable memories (TCAMs) are often used to perform this operation. This paper shows a method to reduce the number of words in TCAM for multi-field classification functions. We use head-tail expressions to represent a multi-field classification rule. Furthermore, we present an O(r2)-algorithm, called MFHT, to generate simplified TCAMs for two-field classification functions, where r is the number of rules. Experimental results show that MFHT achieves a 58% reduction of words for random rules and a 52% reduction of words for ACL and FW rules. Moreover, MFHT is fast and useful for simplifying TCAM for packet classification.

This paper shows a heuristic method to reduce the number of variables to represent incompletely specified index generation functions using linear decompositions. To find good linear transformations, two measures are introduced: the imbalance measure and the ambiguity measure. Experimental results using m-out-of-n code to binary converters, randomly generated functions, IP address tables, and lists of English words show the usefulness of the approach.

This paper shows a realization of incompletely specified index generation functions in the form f(X1,X2) = g(h(X1)+X2), where + denotes an integer addition. A decomposition algorithm is shown. Experimental results show that most of n = 2q-3 variable functions where k = 2q-1 combinations are specified can be realized by a pair of q-input q-output LUTs. The computation time is O(k). Experimental results using address tables, lists of English words, and randomly generated functions are shown.

A branching program machine (BM) is a special purpose processor that uses only two kinds of instructions: Branch and output instructions. Thus, the architecture for the BM is much simpler than that for a general purpose processor (MPU). Since the BM uses the dedicated instructions for a special purpose application, it is faster than the MPU. This paper presents a packet classifier using a parallel branching program machine (PBM). To reduce computation time and code size, first, a set of rules for the packet classifier is partitioned into groups. Then, they are evaluated by the PBM in parallel. Also, this paper shows a method to estimate the number of necessary BMs to realize the packet classifier. The PBM32 consisting of 32 BMs has been implemented on an FPGA, and compared with the Intel's [email protected]. The PBM32 is 8.1-11.1 times faster than the Core2Duo, and the PBM32 requires only 0.2-10.3 percent of the memory for the Core2Duo.

In an incompletely specified function f, don't care values can be chosen to minimize the number of variables to represent f. We consider incompletely specified functions f: Pn→ Q, where P={0,1,..., p-1}, Q={0,1,..., q-1}, u combinations are mapped to i (i=0,1,...,q-1), uq=k, and other combinations are mapped to don't cares. We show that most functions can be represented with 2 [logp(k+1)] variables or less. Experimental results are shown to support this.

This paper shows an implementation of CANSCID (Combined Architecture for Stream Categorization and Intrusion Detection). To satisfy the required system throughput, the packet assembler and the regular expression matching are implemented by the dedicated hardware. On the other hand, the counting of matching results and the system control are implemented by a microprocessor. A regular expression matching circuit is performed as follows: First, the given regular expressions are converted into a non-deterministic finite automaton (NFA). Then, to reduce the number of states, the NFA is converted to a modular non-deterministic finite automaton (MNFA(p)) with p-character-consuming transition. Finally, a finite-input memory machine (FIMM) to detect p-characters is generated, and the matching elements (MEs) realizing the states for the MNFA(p) are generated. We loaded 140 regular expressions of the MEMOCODE 2010 design contest on Terasic Corp. DE3 prototyping board (FPGA: Altera's Stratix III). The maximum throughput of our implementation was 798 mega bits per second (Mbps).

This paper shows a new architecture for a virus scanning system, which is different from that of an intrusion detection system. The proposed method uses two-stage matching: In the first stage, a hardware filter quickly scans the text to find partial matches, and in the second stage, the MPU scans the text to find a total match in the ClamAV 514,287 virus pattern set. To make the hardware filter simple, we use a finite-input memory machine (FIMM). To reduce the memory size of the FIMM, we introduce the parallel sieve method. The proposed method is memorybased, so it is quickly reconfigurable and dissipates lower power than a TCAM-based method. The system is implemented on the Stratix III FPGA with three off-chip SRAMs and an SDRAM, where all ClamAV 514,287 virus patterns are stored. Compared with existing methods, our method achieves 1.41-31.36 times more efficient area-throughput ratio.

This paper shows a method to reduce the number of input variables to represent incompletely specified index generation functions. A compound variable is generated by EXORing the original input variables. By using both original and compound variables, incompletely specified index generation functions can be represented by fewer variables. As a means to select variables, a heuristic method using information gains is presented. We compare representing random functions using 1. only original variables, and 2. both original and compound variables. Experimental results show that the use of compound variables effectively reduces the number of input variables.

This paper presents a virus scanning engine. After showing the difference between ClamAV (an anti-virus software) and SNORT (an intrusion detection software), we show a new architecture for the virus scanning engine, which is different from that of the intrusion detection engine. The new architecture consists of a parallel finite-input memory machine (PFIMM) and general purpose MPUs. It uses two-stage matching. That is, in the first stage, the parallel hardware filter quickly scans the text to find partial matches, and in the second stage, the MPU scan the text to find the total match. To reduce the memory size, compressed match vectors are used. The system is implemented on the Stratix III FPGA, where 65,536 ClamAV virus patterns are stored. As for the area-performance ratio, our system is 1.2-26.3 times more efficient than existing ones.

This paper analyzes complexities of decision diagrams for elementary functions such as polynomial, trigonometric, logarithmic, square root, and reciprocal functions. These real functions are converted into integer-valued functions by using fixed-point representation. This paper presents the numbers of nodes in decision diagrams representing the integer-valued functions. First, complexities of decision diagrams for polynomial functions are analyzed, since elementary functions can be approximated by polynomial functions. A theoretical analysis shows that binary moment diagrams (BMDs) have low complexity for polynomial functions. Second, this paper analyzes complexity of edge-valued binary decision diagrams (EVBDDs) for monotone functions, since many common elementary functions are monotone. It introduces a new class of integer functions, Mp-monotone increasing function, and derives an upper bound on the number of nodes in an EVBDD for the Mp-monotone increasing function. A theoretical analysis shows that EVBDDs have low complexity for Mp-monotone increasing functions. This paper also presents the exact number of nodes in the smallest EVBDD for the n-bit multiplier function, and a variable order for the smallest EVBDD.

This paper proposes a design method and programmable architectures for numerical function generators (NFGs) of two-variable functions. To realize a two-variable function in hardware, we partition a given domain of the given function into segments, and approximate the function by a polynomial in each segment. This paper introduces two planar segmentation algorithms that efficiently partition a domain of a two-variable function. This paper also introduces two architectures that can realize a wide range of two-variable functions. Our architectures allow a systematic design of two-variable functions. FPGA implementation results show that, for a complicated function, our NFG achieves 58% of memory size and 39% of delay time of a circuit designed using one-variable NFGs.

This paper considers a single-digit error detection in a redundant residue number system (RRNS). Let f be the function that denotes the set of legitimate codes of an RRNS. To analyze the complexity of the error detection circuit, C-measure, the maximum value of the column multiplicity for f is considered. We show that the C-measure is much smaller than the dynamic range of the RRNS. In this way, we show that f can be implemented by a small Look-up table (LUT) cascade.

Two-variable numerical functions are widely used in various applications, such as computer graphics and digital signal processing. Fast and compact hardware implementations are required. This paper introduces the bilinear interpolation method to produce fast and compact numerical function generators (NFGs) for two-variable functions. This paper also introduces a design method for symmetric two-variable functions. This method can reduce the memory size needed for symmetric functions by nearly half with small speed penalty. Experimental results show that the bilinear interpolation method can significantly reduce the memory size needed for two-variable functions, and the speed of NFGs based on the bilinear method is comparable to that of NFGs based on tangent plane approximation. For a complicated function, our NFG is faster and more compact than a circuit designed using a one-variable NFG.

In an incompletely specified function f, don’t care values can be chosen to minimize the number of variables to represent f. It is shown that, in incompletely specified functions with k 0’s and k 1’s, the probability that f can be represented with only p = 2[log2(k + 1)] variables is greater than e−1= 0.36788. In the case of multiple-output functions, where only the outputs for k input combinations are specified, most functions can be represented with at most p = 2[log2(k+1)]−1variables. Experimental data is shown to support this. Because of this property, an IP address table can be realized with a small amount of memory.

In this paper, we introduce the edge-valued binary decision diagram (EVBDD) to reduce the memory and delay in numerical function generators (NFGs). An NFG realizes a function, such as a trigonometric, logarithmic, square root, or reciprocal function, in hardware. NFGs are important in, for example, digital signal applications, where high speed and accuracy are necessary. We use the EVBDD to produce a fast and compact segment index encoder (SIE) that is a key component in our NFG. We compare our approach with NFG designs based on multi-terminal BDDs (MTBDDs), and show that the EVBDD produces SIEs that have, on average, only 7% of the memory and 40% of the delay of those designed using MTBDDs. Therefore, our NFGs based on EVBDDs have, on average, only 38% of the memory and 59% of the delay of NFGs based on MTBDDs.

This paper focuses on numerical function generators (NFGs) based on k-th order polynomial approximations. We show that increasing the polynomial order k reduces significantly the NFG's memory size. However, larger k requires more logic elements and multipliers. To quantify this tradeoff, we introduce the FPGA utilization measure, and then determine the optimum polynomial order k. Experimental results show that: 1) for low accuracies (up to 17 bits), 1st order polynomial approximations produce the most efficient implementations; and 2) for higher accuracies (18 to 24 bits), 2nd-order polynomial approximations produce the most efficient implementations.

An address generator produces a unique address from 1 to k for the input that matches to one of k registered vectors, and produces 0 for other inputs. This paper presents the super hybrid method to design an address generator. The hash memories realize about 96% of the registered vectors, while the reconfigurable PLA realizes the remaining 4% of the registered vectors. With the super hybrid method, we can implement up to 20 times more registered vectors than the conventional method that uses only logic elements of an FPGA. Experimental results using lists of English words show that the usefulness of the approach.

This paper presents a method to implement a reconfigurable logic array on an FPGA. To design circuits with 2-valued k-input LUTs, 2k-valued logic is introduced. Standard benchmark functions as well as symmetric functions are efficiently implemented by a logic array with 2k-valued variables. Number of products and number of bits to represent functions by the expressions with 2k-valued variables for k = 1,2,3,4, and 5 are compared. Both sum-of-products expressions and EXOR sum-of-products expressions of 2k-valued logic significantly reduces needed FPGA resources, when 2 les k les 5. Experimental results for benchmark functions and symmetric functions are shown. Implementations of arrays with 16-valued variables on Xilinx and Altera FPGAs are also shown.

An address table relates k different registered vectors to the addresses from 1 to k. An address generation function represents the address table. This paper presents a realization of an address generation function with an LUT cascade on an FPGA. The address generation function is implemented by BRAMs of an FPGA, while the addition and the deletion of registered vectors are implemented by an embedded processor on the FPGA. Compared with CAMs produced by the Xilinx Core Generator, our implementations are smaller and faster. This paper also shows that the addition and deletion of a registered vector can be done in time that is proportional to the number of cells in the LUT cascade.

This paper proposes an architecture and a synthesis method for high-speed computation of fixed-point numerical functions such as trigonometric, logarithmic, sigmoidal, square root, and combinations of these functions. Our architecture is based on the lookup table (LUT) cascade, which results in a significant reduction in circuit complexity compared to traditional approaches. This is suitable for automatic synthesis and we show a synthesis method that converts a Matlab-like specification into an LUT cascade design. Experimental results show the efficiency of our approach as implemented on a field-programmable gate array (FPGA)

This paper presents architecture and a synthesis method for programmable numerical function generators (NFGs) for trigonometric, logarithmic, square root, and reciprocal functions. Our NFG partitions a given domain of the function into nonuniform segments using a LUT cascade, and approximates the given function by a quadratic polynomial for each segment. Thus, we can implement fast and compact NFGs for a wide range of functions. Implementation results on an FPGA show that: 1) our NFGs require only 4% of the memory needed by NFGs based on the linear approximation with nonuniform segmentation; and 2) our NFGs require only 22% of the memory needed by NFGs based on the 5th-order approximation with uniform segmentation. Our automatic synthesis system generates such compact NFGs quickly.

This paper shows a new type of a cycle-based logic simulation method using a look-up table (LUT) cascade emulator. The method first transforms a given circuit into LUT cascades through BDD (binary decision diagram). Then, it stores LUT data to the memory of an LUT cascade emulator. Next, it generates the C code representing the control circuit of the LUT cascade emulator. And, finally, it converts the C code into the execution code. This method is compared with a levelized compiled code (LCC) simulator with respect to the simulation time and setup time. Although we used standard PC to simulate the circuit, experimental results show that this method is 12-64 times faster than the LCC

An LUT cascade emulator realizes an arbitrary sequential circuit. Given a sequential circuit, we convert the combinational part into one or more LUT cascades, and store LUT (cell) data into a memory in the LUT cascade emulator. The emulator evaluates multi-output logic functions by reading cell data sequentially. To improve the tolerance to soft errors, cell data in the memory are encoded by error correcting codes. Also, error-correcting circuits and checking circuits that periodically scan the memories are appended. When a soft error is detected, it removes the error by rewriting the correct data into the memory. To mask soft errors in flip-flops, a TMR (triple module redundancy) technique is employed. Our system detects a soft error in a single bit. Also, the mission time of the system is more than 1000times of time of an ordinary LUT cascade emulator

A weighted-sum (WS) function computes the sum of selected integers. This paper considers a design method for WS functions by look-up table (LUT) cascades. In particular, it derives upper bounds on the column multiplicities of decomposition charts for WS functions. From these, the size of LUT cascades that realize WS functions can be estimated. The arithmetic decomposition of a WS function is also shown. With this method, a WS function can be implemented with cascades and adders.

A multiple-output function can be represented by a binary decision diagram for characteristic function (BDD/spl I.bar/for/spl I.bar/CF). This paper presents a new method to represent multiple-output incompletely specified functions using BDD/spl I.bar/for/spl I.bar/CF. An algorithm to reduce the widths of BDD/spl I.bar/for/spl I.bar/CFs is presented. This method is useful for decomposition of incompletely specified multiple-output functions. Experimental results for radix converters, adders and a multiplier show that this method is useful for the synthesis of LUT cascades. This data structure is also useful to three-valued logic simulation.

This paper first defines the n-input q-output WS function, as a mathematical model of the combinational part of the distributed arithmetic of a finite impulse response (FIR) filter. Then, it shows a method to realize the WS function by an LUT cascade with k-input q-output cells. Furthermore, it 1) shows that LUT cascade realizations require much smaller memory than the single ROM realizations; 2) presents new design method for a WS function by arithmetic decomposition, and 3) shows design results of FIR filters using FPGAs with embedded memories.

This paper presents an architecture and a synthesis method for programmable numerical function generators of trigonometric functions, logarithm functions, square root, reciprocal, etc. Our architecture uses an LUT (look-up table) cascade as the segment index encoder, compactly realizes various numerical functions, and is suitable for automatic synthesis. We have developed a synthesis system that converts MATLAB-like specification into HDL code. We propose and compare three architectures implemented as a FPGA (field-programmable gate array). Experimental results show the efficiency of our architecture and synthesis system.

This paper addresses a pipelined partial rolling (PPR) architecture for the AES encryption. The key technique is the PPR architecture, which is suitable for FPGA implementation. Using the proposed architecture on the Altera Stratix EP1S20F780C5 FPGA, the AES-4SM achieves a throughput of 5.61 Gbps by using 20 M4Ks, and the AES-8SM achieves a throughput of 10.49 Gbps by using 40 M4Ks. Compared with the unrolling implementation that achieves a throughput of 20.48 Gbps by using 80 M4Ks on the same FPGA, implementations with the PPR architecture reduce the amount of memory up to 75% while increasing the memory efficiency (i.e., throughput divided by the size of memory for core) up to 9.6%.The PPR architecture.lls the gap between unrolling and rolling architectures,and.ts on less expensive FPGAs.

The traditional problem in binary decision diagrams (BDDs) has been to minimize the number of nodes since this reduces the memory needed to store the BDD. Recently, a new problem has emerged: minimizing the average path length (APL). APL is a measure of the time needed to evaluate the function by applying a sequence of variable values. It is of special significance when BDDs are used in simulation and design verification. A main result of this paper is that the APL for benchmark functions is typically much smaller than for random functions. That is, for the set of all functions, we show that the average APL is close to the maximum path length, whereas benchmark functions show a remarkably small APL. Surprisingly, however, typical functions do not achieve the absolute maximum APL. We show that the parity functions are unique in having that distinction. We show that the APL of a BDD can vary considerably with variable ordering. We derive the APL for various functions, including the AND, OR, threshold, Achilles' heel, and certain arithmetic functions. We show that the unate cascade functions uniquely achieve the absolute minimum APL.

This paper proposes minimization algorithms for the memory size and the average path length (APL) of heterogeneous multivalued decision diagrams (MDDs). In a heterogeneous MDD, each multivalued variable can take different domains. To represent a binary logic function using a heterogeneous MDD, we partition the binary variables into groups with different numbers of binary variables and treat the groups as multivalued variables. Since memory size and APL of a heterogeneous MDD depend on the partition of binary variables as well as the ordering of binary variables, the memory size and the APL of a heterogeneous MDD can be minimized by considering both orderings and partitions of binary variables. The experimental results show that heterogeneous MDDs can represent logic functions with smaller memory sizes than free binary decision diagrams (FBDDs) and smaller APLs than reduced ordered BDDs (ROBDDs); the APLs of heterogeneous MDDs can be reduced by half of the ROBDDs without increasing memory size; and heterogeneous MDDs have smaller area-time complexities than MDD(k)s.

This paper shows a method to decompose a given multiple-output circuit into two circuits with intermediate outputs. We use a BDD for characteristic function (BDD for CF) to represent a multiple-output function.Many benchmark functions were realized by LUT cascades with intermediate outputs. Especially, adders and a binary to BCD converter were successfully designed. Comparison with FPGAs is also presented.

Abstract — This paper shows four different methods to evaluate multiple-output logic functions using decision diagrams: Shared BDD (SBDD), Multi-Terminal BDD (MTBDD), BDD for characteristic functions (CF), and BDDs for Encoded Characteristic Function for Non-zero outputs (ECFNs). Methods to compute average evaluation time for each type of decision diagrams are presented. By experimental analysis using benchmark functions, the number of nodes and average evaluation time are compared. Our results show that BDDs for ECFNs outperforms MTBDDs, BDDs for CFs, and SBDDs with respect to both number of nodes and computation time. The sizes of BDDs for ECFNs

In some cases, minimum Sum-Of-Products (SOP) expressions of Boolean functions can be derived by detecting decomposition and observing the functional properties such as unateness, instead of applying the classical minimization algorithms. This paper presents a systematic study of such situations and develops a divide-and-conquer algorithm for SOP minimization, which can dramatically reduce the computational effort, without sacrificing the minimality of the solutions. The algorithm is used as a preprocessor to a general-purpose exact or heuristic minimizer, such as ESPRESSO. The experimental results show significant improvements in runtime. The exact solutions for some large MCNC benchmark functions are reported for the first time.

A function f is AND bi-decomposable if it can be written as f (X1,X2) = h1(X1)h2(X2). In this case, a sum-of-products expression (SOP) for f is obtained from minimum SOPs (MSOP) for h1 and h2 by applying the law of distributivity. If the result is an MSOP, then the complexity of minimization is reduced. However, the application of the law of distributivity to MSOPs for h1 and h2 does not always produce an MSOP for f. We show an incompletely specified function of n(n-1) variables that requires at most n products in an MSOP, while 2(n-1) products are required by minimizing the component functions separately. We introduce a new class of logic functions, called orthodox functions, where the application of the law of distributivity to MSOPs for component functions of f always produces an MSOP for f . We show that orthodox functions include all functions with three or fewer variables, all symmetric functions, all unate functions, many benchmark functions, and few random functions with many variables.

A realization of multiple-output logic functions using a RAM and a sequencer is presented. First, a multiple-output function is represented by an encoded characteristic function for non-zeros (ECFN). Then, it is represented by a cascade of look-up tables (LUTs). Finally, the cascade is simulated by a RAM and a sequencer. Multiple-output functions for benchmark functions are realized by cascades of LUTs, and the number of LUTs and levels of cascades are shown. A partition method of outputs for parallel evaluation is also presented. A prototype has been developed by using RAM and FPGA. This realization uses time domain multiplexing, and is useful for the case where the number of output pins is limited.

In an irredundant sum-of-products expression (ISOP), each product is a prime implicant (Pl) and no product can be deleted without changing the function. Among the ISOPs for some function f, a worst ISOP (WSOP) is an ISOP with the largest number of Pls and a minimum ISOP (MSOP) is one with the smallest number. We show a class of functions for which the Minato-Morreale ISOP algorithm produces WSOPs. Since the ratio of the size of the WSOP to the size of the MSOP is arbitrarily large when it, the number of variables, is unbounded, the Minato-Morreale algorithm can produce results that are very far from minimum. We present a class of multiple-output functions whose WSOP size is also much larger than its MSOP size. For a set of benchmark functions, we show the distribution of ISOPs to the number of Pls. Among this set are functions where the MSOPs have almost as many Pls as do the WSOPs. These functions are known to be easy to minimize. Also, there are benchmark functions where the fraction of ISOPs that are MSOPs is small and MSOPs have many fewer Pls than the WSOPs. Such functions are known to be hard to minimize. For one class of functions, we show that the fraction of ISOPs that are MSOPs approaches 0 as n approaches infinity, suggesting that such functions are hard to minimize.

This paper discusses early work by Komamiya in Reed-Muller and arithmetic expressions for switching functions.

This paper presents an exact minimization algorithm for fixed polarity Reed-Muller expressions (FPRMs) for incompletely specified functions.For an n-variable function with « unspecified minterms there are 2 n•« distinct FPRMs.A minimum FPRM is one with the fewest products.The minimization algorithm is based on the multi-terminal binary decision diagrams.Experimental results for a set of functions are shown.The algorithm can be extended to obtain exact minimum Kronecker expressions for incompletely specified functions.

A hardware logic simulation engine based on decision diagrams is presented.For the data structure of the engine, we propose PMDDs (Paged reduced ordered Multi-valued Decision Diagrams).A unit of this engine consists of memory (RAMs) and con trol circuits: RAMs store the PMDD data, and the control circuits trace the edges according to the input vectors.The engine consists of several units, and is accelerated by pipelining.Experimental results using a prototype are shown.

Abstract | Finding simple disjoint functional decompositions is a basic problem, but is generally time-consuming since there are nearly 2 n bipartitions of input variable. This paper introduces three parameters to nd bipartitions of the input variables. It also de nes \\ideal random logic functions, " and derives their properties. Experimental results using randomly generated functions and benchmark functions show the usefulness of the approach. I.

We present a method of path selection and test generation for path delay faults. The proposed method addresses the fact that logic circuits typically have very large numbers of paths, and a large percentage of these paths are typically untestable. The proposed method selects a set of potentially testable long paths by utilizing non-enumerative identification of untestable paths and removing untestable paths from consideration. Test generation is also applied as part of the proposed method. We demonstrate the effectiveness of the method by presenting results for benchmark circuits.

This paper presents an efficient method to check the equivalence of two Boolean functions under permutation of the variables. The problem is also known as Boolean matching. As a basis of the Boolean matching, we use the notion P-representative. If two functions have the same P-representative then they match. We develop a breadth-first search technique to quickly compute the P-representative. On an ordinary workstation, on the average, our method requires several microseconds to test the Boolean matching for functions with up to eight variables. This approach is promising for Boolean matching of multiplexor-based field-programmable gate arrays (FPGAs) and for library matching with many large cells.

In logic simulation, we often have to evaluate logic functions in the presence of unknown inputs. However, the naive method often produces incorrect values. In these cases, we can produce correct values by evaluating regular ternary logic functions instead of switching functions. This paper proposes a realization of regular ternary logic functions by using double-rail logic. This implementation requires O(2/sup n//n) logic cells, and O(n) time to simulate an n-variable logic function. We showed an FPGA realization that is about 100 times faster than software simulation.

An AND-OR-EXOR network, where the output EXOR gate has only two inputs, is one of the simplest three-level architecture. This network realizes an EXOR of two sum-of-products expressions (EX-SOP). In this paper, we show an algorithm to simplify EX-SOPs for multiple-output functions. Our objective is to minimize the number of distinct products in the sum-of-products expressions of EX-SOPs. The algorithm uses a divide-and-conquer strategy. It recursively applies the Shannon decomposition on a function with more than five variables. The algorithm obtains EX-SOPs for the five-variable functions by using an exact minimization program, then combines those EX-SOPs to generate EX-SOPs for the functions with more variables. We present experimental results for a set of benchmark functions, and show that EX-SOPs require many fewer products and literals than sum-of-products expressions. This is evidence that AND-OR-EXOR is a powerful architecture to realize many practical logic functions.

This paper classifies different decision diagrams (DDs) for discrete functions with respect to the domain and range of represented functions. Relationships among different DDs and their relations to spectral transforms are also shown. That provides a unified interpretation of DDs, and their further classification with respect to the spectral transforms.

Presents a design method for AND-OR-EXOR three-level networks, where a single two-input EXOR gate is used. The network realizes an exclusive-OR of two sum-of-products expressions (EX-SOP), where the two sum-of-products expressions (SOPs) cannot share products. The problem is to minimize the total number of products in the two SOPs. We introduced the /spl mu/-equivalence of logic functions to develop minimization algorithms for EX-SOPs with up to five variables. We minimized all the representative functions of NP-equivalence classes for up to five variables and found that five-variable functions require up to nine products in minimum EX-SOPs. For n-variable functions, minimum EX-SOPs require at most 9/spl middot/2/sup n-5/ (n/spl ges/6) products. This upper bound is smaller than 2/sup n-1/, the upper bound for conventional SOPs.

Three types of ternary decision diagrams (TDDs) are considered: AND-TDDs, EXOR-TDDs, and Kleene-TDDs. Kleene-TDDs are useful for logic simulation in the presence of unknown inputs. Let N(BDD:f), N(AND-TDD:f), and N(EXOR-TDD:f) be the number of non-terminal nodes in the BDD, the AND-TDD, and the EXOR-TDD for f, respectively. Let N(Kleene-TDD:F) be the number of non-terminal nodes in the Kleene-TDD for F, where F is the Kleenean ternary function corresponding to f. Then N(BDD:f)/spl les/N(TDD:f). For parity functions, N(BDD:f)=N(AND-TDD:f)=N(EXOR-TDD:f)=N(Kleene-TDD:F). For unate functions, N(BDD:f)=N(AND-TDD:f). The sizes of Kleene-TDDs are O(3/sup n//n), and O(n/sup 3/) for arbitrary functions, and symmetric functions, respectively. There exist a 2n-variable function, where Kleene-TD Ds require O(n) nodes with the best order, while O(3/sup n/) nodes in the worst order.

Kleene-TDDs are useful for evaluating logic functions in the presence of unknown inputs, 0 or 1. Although Kleene-TDD-based logic simulation is promising, the size of Kleene-TDD for an n-variable function is O(3/sup n//n). Thus, when n is large, the Kleene-TDDs are often too large to build. In this paper, we propose several methods to decompose Kleene-TDDs. By using this method, we can generate smaller Kleene-TDDs for sub-functions independently to reduce the necessary memory. Preliminary experimental results show that the effectiveness of the presented approach.

This paper considers two types of n-bit adders, ripple carry adders and cascaded carry look-ahead adders, with minimum tests for stuck-at-fault models. In the first part, we present two types of full adders consisting of five gates, and show their minimality. We also prove that one of the full adders can be tested by only three test patterns for single stuck-at-faults. We also present two types of 4-bit carry look-ahead adders and their minimum rests. In the second part, we consider the tests for the cascaded adders, an n-bit ripple carry adder and a 4m-bit cascaded carry look-ahead adders. These tests are considerably smaller than previously published ones.

We derive the average and worst case number of nodes in decision diagrams of r-valued symmetric functions of n variables. We show that, for large n, both numbers approach n/sup r//rl. For binary decision diagrams (r=2), we compute the distribution of the number of functions on n variables with a specified number of nodes. Subclasses of symmetric functions appear as features in this distribution. For example, voting functions are noted as having an average of n/sup 2//6 nodes, for large n, compared to n/sup 2//2, for general binary symmetric functions.

This paper presents a design method of easily testable AND-EXOR networks. It is an improvement of Reddy (1972) and Saluja-Reddy's (1975) methods, and has the following features. The network uses generalized Reed-Muller expressions (GRMs) instead of Positive Polarity Reed-Muller expressions (PPRMs). The average number of products for GRMs is less than half of that for PPRMs, and is less than that of sum-of-products expressions (SOPs). The network consists of a literal part, an AND part, an EXOR part, and a check part. The EXOR part can be a tree instead of a cascade. Thus, the network is faster. The test detects multiple stuck at faults under the assumption that the faults occur at most one part, either the literal part, the AND part, the EXOR part, or the check part.

A generalized Reed-Muller expression (GRM) is a type of AND-EXOR expressions. In a GRM, each variable may appear both complemented and uncomplemented. Networks realized using GRMs are easily tested. This paper presents GRMIN, a heuristic simplification algorithm for GRMs of multiple-output functions. GRMIN uses eight rules. As the primary objective, it reduces the number of products, and as the secondary objective, it reduces the number of literals. Experimental results show that, in most cases, GRMs require fewer products than conventional sum-of-products expressions (SOPs). GRMIN outperforms existing algorithms.

Conditions for generating optimal two-level AND-EXOR representations using rewrite rules are considered. Four results are presented. First, it is shown that a necessary condition for obtaining minimality is a temporary increase in the size of expressions during minimization. Second, a sufficient condition for obtaining minimality that consists of adding certain two rules to rule sets proposed in the literature is given. Third, transformations that allow the minimization of an expression to proceed by minimizing a transformed expression instead are defined. Fourth, it is determined experimentally that the above three theoretical results lead to better benchmarks results as well.>

Minimization of AND-EXOR programmable logic arrays (PLAs) with input decoders corresponds to minimization of the number of products in Exclusive-OR sum-of-products expressions (ESOPs) for multiple-valued-input two-valued-output functions. A simplification algorithm for ESOPs that iteratively reduces the number of the products in ESOPs and then reduces the number of the literals is presented. Various rules are used to replace a pair of products with another one. Many AND-EXOR PLAs for arithmetic circuits have been simplified. In most cases, AND-EXOR PLAs required fewer products than AND-OR PLAs.>

The authors derive an upper and a lower bound on the average number of products in the minimum sum-of-products expressions (SOPEs). The upper bound is obtained by using the minimization results of functions with fewer variables. The lower bound is based on an assumption, so it is incorrect until this assumption is proven. A lower bound L/sub p/(n,u) and an upper bound U/sub p/(n,u) on S/sub p/(n,u) are derived, where S/sub p/(n,u) is the average number of products in minimum SOPE for p-valued input two-valued output functions, n is the number of the inputs, and u is the number of minterms. The values of S/sub p/(n,u) are obtained by minimizing randomly generated functions, and they are compared to the calculated values of U/sub p/(n,u) and L/sub p/(n,u). These bounds are useful for estimating the size of programming logic arrays.>

A description is given of the design and analysis of three types of multivalued PLAs (programmable logic arrays). Type 1 PLAs realize functions directly in the form of the max of min of literal functions and constants. In Type 2 PLAs, the body of the PLA is binary and the output is encoded as a multiple-valued logic value. Type 3 PLAs are the same as type 2 PLAs except for the use of 2-bit decoders and a permutation network on the input. Using the number of columns required to realize a given function as a measure to compare PLAs, it is shown that type 3 PLAs are superior to type 2, which in turn are superior to type 1.>

MACDAS (Multi-level AND-OR Circuit Design Automation System) designs a multi-level circuit with fan-in limited AND-OR gates. In MACDAS, a given specification is converted into an AND-OR two-level circuit; input variables are paired to produce an AND-OR two-level circuit with two-variable function generators; some of the outputs are complemented to obtain a circuit with fewer AND gates; the circuit is transformed into a multi-level fan-in limited AND-OR circuit; and finally the circuit is optimized by local transformations. MACDAS has been programmed in FORTRAN and C, and runs on a personal computer. Both arithmetic and control circuits are designed to show the performance of MACDAS.

A recursive algorithm to obtain a complement of a sum-of-products expression for a binary function with p-valued inputs is presented. It produces at most pn/2 products for n-variable functions, whereas a conventional elementary algorithm produces O(tn·n(1-t)/2) products where t = 2P -1. It is 10-20 times faster than the elementary one when p = 2 and n = 8. For large practical-problems, it produces many fewer products than the disjoint sharp algorithm used by MINI. Appplications of the algorithm to PLA minimization are also presented.

A PLA minimization system having the following features is presented: 1) minimization of both two-level PLA's and PLA's with two-bit decoders; 2) optimal input variable assignment to the decoders; 3) optimal output phase assignment; and 4) essential prime implicants detection without generating all the prime implicants.

Generalized Boolean functions are shown to be useful for the design of programmable logic arrays (PLA's), and the complexity of three types of PLA's is obtained by the theory of multiple- valued decomposition. A two-level PLA consists of an AND array and an OR array, and they are cascaded to perform a two-level AND-OR circuit. A PLA with decoders consists of decoders, an AND array, and an OR array. A three-level PLA consists of a D array, an AND array, and an OR array, and they are cascaded to perform a three-level OR- AND-OR circuit. It is shown that a generalized Boolean function f(X1, X2,··, Xr):X Bni → B, where B = {0,1}, is represented by a generalized Boolean expression of 2ni-valued variables Xi; and f can be directly realized by a PLA with decoders or a three-level PLA. To realize a function of n-variables (n = 2r), the following sizes are shown to be sufficient: for a two-level PLA, (n + ½) 2n; for a PLA with two-bit decoders, 4(n + 4) 2n; for a three-level PLA, 2n+ (3n + l)√2n+ 2n2Especially in the case of PLA with two-bit decoders, the following sizes are shown to be necessary and sufficient: for an arbitrary symmetric function, 3/2(n + ½) √3n; and for a parity function, (n + ½)√ 2n.

A conservative logic element (CLE) is a multiple-output logic element whose weight of an input vector is equal to that of the corresponding output vector, and fan-out of each output terminal is restricted to one. A CLE is a generalized model of magnetic bubble logic elements, etc. In order to realize an arbitrary function, it is necessary to use constant-supplying elements (CSE's). In this correspondence, we consider the universality of CLE's in relation to the number of CSE's.

In this correspondence, the number of functions and the number of equivalence classes of functions realized by fanout-free networks and cascades of AND'S, OR'S, and inverters are presented. For fanout-free functions, recursive formulas for TND(n) and φND(n), the number of n-p-n-equivalence classes of n-variable functions and p-equivalence classes of n-variable functions, respectively, are derived. For unate cascade functions, a recursive formula for ψND(n), the number of n-variable functions, and formulas for UND(n) and ψND(n), the number of n-p -equivalence classes and p-equivalence classes, respectively, are derived. Some asymptotic properties of ψND(n), UND(n), and ψND(n) are also examined and it is shown that ψND)/ψ(n)→ 1/√2, UND(n)/U(n)→ 1/2, and ψND(n)/ψ(n)→ 1/√2 as n →∞, where ψ(n) is the number of distinct unate cascade functions of up to n variables, and U(n) and ψ(n) are the number of distinct n-p-n-and p-equivalence classes of unate cascade functions of up to n variables, respectively.

This correspondence is concerned with the realization of logical functions by using two-input three-output conservative logic elements (CLE's) called IB.

A conservative logic element (CLE) is a multiple-output logic element whose weight of an input vector is equal to that of the corresponding output vector, and is a generalized model of magnetic bubble logic elements, fluid logic elements, and so on. This paper considers the problem of realizing arbitrary 3-input 3-output conservative logic elements (3-3 CLC's) by cascade connections of 3-input 3-output CLE's called "primitives." It is shown that the necessary and sufficient number of different primitives to realize an arbitrary 3-3 CLC is three in the case when the crossovers of lines are permitted, and four in the case when the crossovers of lines are not permitted.

This paper is concerned with the realization of logic functions by using two-input magnetic bubble logic elements. A magnetic bubble logic element is the multiple-output logic element whose number of ``1'' 's of the output is equal to that of corresponding input, and fanout of each output terminal of the element is restricted to one. In order to realize some functions, it is necessary to use the generators which correspond to constant-supplying elements. First, the number of generators which are necessary and sufficient to realize an arbitrary functions is obtained for a given set of elements. In particular, it is shown that an arbitrary function can be realized by using IBelements and at most two generators. Since the IBelement is a universal element in the above sense and is considered to be rather easily realized by magnetic bubble interactions, the IBlogic circuits are mainly discussed. The IBminimum circuit defined here is a circuit which consists of minimum number of generators and minimum number of IBelements. In the last half of this paper, it is shown that the minimum circuits of most functions have the characteristic circuit structure called ``1-4 form.''

In this paper, an easily testable machine is defined as one which possesses: 1) a distinguishing sequence of length [log2 n] which forces the machine into a specific state S1, and 2) transfer sequences of length at most [1og2 n] to carry the machine from state S1 to state Si for all i. A design procedure is presented in which an arbitrary machine is augmented to an easily testable machine by adding two special input symbols to the original machine. An efficient procedure is also described for designing checking experiments for the easily testable machines. For an n-state, m-input symbol machine, this procedure gives a bound on the length of the checking experiment that is approximately mn[log2,n]. Furthermore, the total checking experiments are preset.