Memory-Based Logic Synthesis

Product Description

This book describes the synthesis of logic functions using memories. It is useful to design field programmable gate arrays (FPGAs) that contain both small-scale memories, called look-up tables (LUTs), and medium-scale memories, called embedded memories. This is a valuable reference for both FPGA system designers and CAD tool developers, concerned with logic synthesis for FPGAs.

From the Author

Chapter 1  Introduction  
        1.1 Motivation  
        1.2 Organization of the Book  
Chapter 2 Basic Elements  
        2.1 Memory  
        2.2 Programmable Logic Array (PLA) 
        2.3 Content Addressable Memory (CAM)
        2.4 Field Programmable Gate Array (FPGA) 
        2.5 Remarks and Problems  
 
Chapter 3 Definitions and Basic Properties  
        3.1 Functions  
        3.2 Logical Expression  
        3.3 Functional Decomposition  
        3.4 Binary Decision Diagram  
        3.5 Symmetric Functions  
        3.6 Technology Mapping  
        3.7 The Mathematical Constant $e$ and Its Property 
        3.8 Remarks and Problems  
Chapter 4 MUX-Based Synthesis 
        4.1 Fundamentals of MUX  
        4.2 MUX-based Realization 
        4.3 Remarks and Problems  
Chapter 5 Cascade-Based Synthesis 
        5.1 Functional Decomposition and LUT Cascade  
        5.2 Number of LUTs to Realize General Functions  
        5.3 Number of LUTs to Realize Symmetric Functions  
        5.4 Remarks and Problems  
Chapter 6 Encoding Method  
        6.1 Decomposition and Equivalence Class  
        6.2 Disjoint Encoding  
        6.3 Non-disjoint Encoding 
        6.4 Remarks and Problems 
Chapter 7 Functions with Small C-Measures  
        7.1 C-measure and BDDs  
        7.2 Symmetric Functions 
        7.3 Sparse Functions  
        7.4 LPM Functions 
        7.5 Segment Index Encoder Function  
        7.6 WS Functions 
        7.7 Modulo Function 
        7.8 Remarks and Problems 
Chapter 8 C-Measure of Sparse Functions  
        8.1 Logic Functions with Specified Weights 
        8.2 Uniformly Distributed Functions 
        8.3 Experimental Results 
        8.4 Remarks and Problems 
Chapter 9 Index Generation Functions 
        9.1 Index Generation Functions and Their Realizations  
        9.2 Address Table  
        9.3 Terminal Access Controller  
        9.4 Memory Patch Circuit  
        9.5 Periodic Table of the Chemical Elements  
        9.6 English-Japanese Dictionary  
        9.7 Properties of Index Generation Functions 
        9.8 Realization using (p,q)-elements 
        9.9 Realization of Logic Functions with Weight $k$  
        9.10 Remarks and Problems 
Chapter 10 Hash-Based Synthesis  
        10.1 Hash Function  
        10.2 Index Generation Unit (IGU) 
        10.3 Reduction by a Linear Transformation 
        10.4 Hybrid Method 
        10.5 Registered Vectors Realized by Main Memory 
        10.6 Super Hybrid Method 
        10.7 Parallel Sieve Method 
        10.8 Experimental Results 
        10.9 Remarks and Problems  
Chapter 11 Reduction of the Number of Variables 
        11.1 Optimization for Incompletely Specified Functions  
        11.2 Definitions and Basic Properties  
        11.3 Algorithm to Minimize the Number of Variables 
        11.4 Analysis for Single-Output Logic Functions 
        11.5 Extension to Multiple-Output Functions 
        11.6 Experimental Results 
        11.7 Remarks and Problems  
Chapter 12 Various Realizations  
        12.1 Realization using Registers, Gates, and an Encoder  
        12.2 LUT Cascade Emulator 
        12.3 Realization using Cascade and AUX Memory 
        12.4 Comparison of Various Methods  
        12.5 Code Converter  
        12.6 Remarks and Problems  
Chapter 13 Conclusions  
Solutions to the Problems.

From the Back Cover

This book describes the synthesis of logic functions using memories. It is useful to design field programmable gate arrays (FPGAs) that contain both small-scale memories, called look-up tables (LU