nach oben

2011 | Buch

Memory-Based Logic Synthesis

verfasst von: Tsutomu Sasao

Verlag: Springer New York

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

Two of the most crucial problems in VLSI design are their high design cost and long design time. A solution to these problems is to use programmable architectures. Programmable LSIs reduce the hardware development cost and time drastically, since one LSI can be used for various applications. This book considers realizations of logic functions by programmable architectures. Various methods exist to realize multiple-output logic functions by programmable architectures. Among them, memories and programmable logic arrays (PLAs) directly realize logic functions. However, when the number of input variables n is large, the necessary hardware becomes too large. Thus, field programmable gate arrays (FPGAs) are widely used. Unfortunately, FPGAs require layout and routing in addition to logic design. Thus, quick reconfiguration is not so easy.

Tsutomu Sasao

Chapter 2. Basic Elements

Abstract

This chapter reviews memory, programmable logic array (PLA), content addressable memory (CAM), and field programmable gate array (FPGA).

Tsutomu Sasao

Chapter 3. Definitions and Basic Properties

Abstract

This chapter first introduces logical expressions and functional decomposition. Then, it introduces some properties of symmetric functions.

Tsutomu Sasao

Chapter 4. MUX-Based Synthesis

Abstract

This chapter shows a universal method to realize an n-variable function using multiplexers (MUXs) and look up tables (LUTs). It also derives upper bounds on the number of LUTs to realize an n-variable function. Such bounds are useful to estimate the number of LUTs needed to realize a given function when we only know the number of the input variables n.

Tsutomu Sasao

Chapter 5. Cascade-Based Synthesis

Abstract

The previous chapter presented a multiplexer (MUX)-based realization. Although such a method is applicable to any n-variable function f , the number of LUTs necessary to realize f increases as O.2n/. This chapter considers a cascade-based logic synthesis. A cascade-based realization is applicable to only a limited class of functions. However, functions with a small C-measure can be realized by cascadebased realizations with O.n/ LUTs.

Tsutomu Sasao

Chapter 6. Encoding Method

Abstract

This chapter shows a method to reduce the number of LUTs needed to realize logic functions with nonstandard encodings. In these encodings, intermediate variables in functional decomposition are represented with fewer variables. This method offers a way to find a nondisjoint decomposition.

Tsutomu Sasao

Chapter 7. Functions with Small C-Measures

Abstract

Recall that the C-measure of a function is the maximum column multiplicity among a set of functional decompositions f(X ₁, X ₂), where X ₁ = (x ₁, x ₂, …, x _k) and \({X}_{2} = ({x}_{k+1},{x}_{k+2},\ldots, {x}_{n}).\) The C-measure tends to increase exponentially with the number of input variables, n. However, many practical functions have small C-measures. This chapter considers classes of functions whose C-measures are small. Such functions can be efficiently realized by LUT cascades.

Tsutomu Sasao

Chapter 8. C-Measure of Sparse Functions

Abstract

Let f be a function of n variables. Then, the C-measure of f tends to increase exponentially with n. However, for the functions with a fixed weight u, (u ≪ 2^n − 1), C-measure increase as O(n). Thus, functions with small weights have small C-measures. This chapter considers the C-measure of functions with small weights.

Tsutomu Sasao

Chapter 9. Index Generation Functions

Abstract

This chapter introduces index generation functions with various applications. Then, it shows a method to realize index generation functions by LUTs.

Tsutomu Sasao

Chapter 10. Hash-Based Synthesis

Abstract

In Chap. 5, we considered cascade-based realizations of logic functions with small C-measure. When the weight k of the function satisfies the relation ⌈log₂(k + 1)⌉ < K, the function can be efficiently realized by a cascade of K-input cells. Also, as shown in Chap. 9, an index generation function can be implemented by a multilevel network of (p, q)-elements, or by a multilevel network with K-LUTs. However, when ⌈log₂(k + 1)⌉ ≥ K, such methods are not directly applicable.

Tsutomu Sasao

Chapter 11. Reduction of the Number of Variables

Abstract

This chapter considers a method to reduce the number of variables needed to represent incompletely specified logic functions. When the number of specified minterms is k, most functions can be represented with at most \(2{\lceil \log }_{2}(k + 1)\rceil - 2\) variables.

Tsutomu Sasao

Chapter 12. Various Realizations

Abstract

This chapter shows various realizations of index generation functions.

Tsutomu Sasao

Chapter 13. Conclusions

Abstract

This book showed various methods to realize logic functions with LUTs. These methods can be used to design FPGAs as well as custom integrated circuits. Main applications are communication circuits and pattern matching circuits, where frequent reconfiguration is needed. Major results are as follows:

Tsutomu Sasao

Backmatter

Titel: Memory-Based Logic Synthesis
verfasst von: Tsutomu Sasao
Verlag: Springer New York
Electronic ISBN: 978-1-4419-8104-2
Print ISBN: 978-1-4419-8103-5
DOI: https://doi.org/10.1007/978-1-4419-8104-2