On the Numbers of Products in Prefix SOPs for Interval Functions

スポンサーリンク

概要

• 論文の詳細を見る

• First, this paper derives the prefix sum-of-products expression (PreSOP) and the number of products in a PreSOP for an interval function. Second, it derives Ψ(n,τp), the number of n-variable interval functions that can be represented with τp products. Finally, it shows that more than 99.9% of the n-variable interval functions can be represented with $\lceil \frac{3}{2}n - 1 \rceil$ products, when n is sufficiently large. These results are useful for a fast PreSOP generator and for estimating the size of ternary content addressable memories (TCAMs) for packet classification.

著者

• SASAO Tsutomu

  Department of Computer Science and Electronics, Kyushu Institute of Technology

• Sasao Tsutomu

  Department Of Computer Science And Electronics Kyushu Institute Of Technology

• SYAFALNI Infall

  Department of Computer Science and Electronics, Kyushu Institute of Technology

関連論文

• A Systematic Design Method for Two-Variable Numeric Function Generators Using Multiple-Valued Decision Diagrams
• Compact Numerical Function Generators Based on Quadratic Approximation : Architecture and Synthesis Method(Circuit Synthesis,VLSI Design and CAD Algorithms)
• A Parallel Branching Program Machine for Sequential Circuits: Implementation and Evaluation
• Bi-Partition of Shared Binary Decision Diagrams(Special Section on VLSI Design and CAD Algorithms)
• Time-Division Multiplexing Realizations of Multiple-Output Functions Based on Shared Multi-Terminal Multiple-Valued Decision Diagrams (Special Issue on Multiple-Valued Logic and Its Applications)
• Design Method for Numerical Function Generators Using Recursive Segmentation and EVBDDs(Logic Synthesis and Verification,VLSI Design and CAD Algorithms)
• Exact Minimization of FPRMs for Incompletely Specified Functions by Using MTBDDs(Logic Synthesis, VLSI Design and CAD Algorithms)
• A New Equivalence Relation of Logic Functions and Its Application in the Design of AND-OR-EXOR Networks(Discrete Mathematics and Its Applications)
• BDD Representation for Incompletely Specified Multiple-Output Logic Functions and Its Applications to the Design of LUT Cascades(Logic Synthesis and Verification,VLSI Design and CAD Algorithms)
• A Systematic Design Method for Two-Variable Numeric Function Generators Using Multiple-Valued Decision Diagrams
• A Quaternary Decision Diagram Machine : Optimization of Its Code
• Efficient Computation of Canonical Form under Variable Permutation and Negation for Boolean Matching in Large Libraries(Logic Synthesis,VLSI Design and CAD Algorithms)
• A Parallel Branching Program Machine for Sequential Circuits : Implementation and Evaluation
• A Memory-Based Programmable Logic Device Using a Look-Up Table Cascade with Synchronous SRAMs
• A Realization of Multiple-Output Functions by a Look-Up Table Ring(Logic Synthesis)(VLSI Design and CAD Algorithms)
• Design Methods of Radix Converters Using Arithmetic Decompositions(Computer Components)
• A Design of AES Encryption Circuit with 128-bit Keys Using Look-Up Table Ring on FPGA(Computer Components)
• Area-Time Complexities of Multi-Valued Decision Diagrams(Discrete Mathematics and Its Applications)
• On Properties of Kleene TDDs(Special Issue on Test and Diagnosis of VLSI)
• Representations of Multiple-Output Functions Using Binary Decision Diagrams for Characteristic Functions (Special Section on VLSI Design and CAD Algorithms)
• Compact Representations of Logic Functions Using Heterogeneous MDDs(Logic and High Synthesis)(VLSI Design and CAD Algorithms)
• A PC-Based Logic Simulator Using a Look-Up Table Cascade Emulator(Simulation and Verification,VLSI Design and CAD Algorithms)
• A Design Algorithm for Sequential Circuits Using LUT Rings(Logic Synthesis, VLSI Design and CAD Algorithms)
• Fast Boolean Matching under Permutation by Efficient Computation of Canonical Form(Logic Synthesis)(VLSI Design and CAD Algorithms)
• Output Phase Optimization for AND-OR-EXOR PLAs with Decoders and Its Application to Design of Adders(Digital Circuits and Computer Arithmetic, Recent Advances in Circuits and Systems-Part 1)
• A Design Method of a Regular Expression Matching Circuit Based on Decomposed Automaton
• A Virus Scanning Engine Using an MPU and an IGU Based on Row-Shift Decomposition
• On the Numbers of Products in Prefix SOPs for Interval Functions
• On Optimizations of Edge-Valued MDDs for Fast Analysis of Multi-State Systems

もっと見る 閉じる

スポンサーリンク