Memory-Based Logic Synthesis
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.&n
- PDF / 4,255,054 Bytes
- 198 Pages / 439 x 666 pts Page_size
- 40 Downloads / 173 Views
Tsutomu Sasao
Memory-Based Logic Synthesis
ABC
Tsutomu Sasao Kyushu Institute of Technology Department of Computer Science and Electronic Iizuka, Japan [email protected]
ISBN 978-1-4419-8103-5 e-ISBN 978-1-4419-8104-2 DOI 10.1007/978-1-4419-8104-2 Springer New York Dordrecht Heidelberg London Library of Congress Control Number: 2011922264 c Springer Science+Business Media, LLC 2011 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
Preface
This book describes the realization of logic functions using memories. The proposed methods can be used to impalement designs in field programmable gate arrays (FPGAs) that contain both small-scale memories, called look-up tables (LUTs), and medium-scale memories, called embedded memories. The basis for memory-based design is functional decomposition, which replaces a large memory with smaller ones. An LUT cascade is introduced as a new architecture for logic synthesis. This book introduces the C-measure, which specifies the complexity of Boolean functions. Functions with a suitably small C-measure can be efficiently realized by LUT cascades. This book also shows logic design methods for index generation functions. An index generation function is a mathematical model for an address table which can be used to store internet addresses. Such a table must be updated frequently, and the operation must be performed as fast as possible. In addition, this book introduces hash-based design methods, which efficiently realize index generation functions by pairs of smaller memories. Main applications include: IP address table lookup, packet filtering, terminal access controllers, memory patch circuits, virus scan circuits, fault map of memory, and pattern matching. This book is suitable for both FPGA system designers and CAD tool developers. To read the book, a basic knowledge of logic design and discrete mathematics is required. Each chapter contains examples and exercises. Solutions for the exercises are also provided. Tsutomu Sasao
v
Acknowledgements
This research is supported in part by the Grants in Aid for Scientific Research of JSPS, the grants of MEXT knowledge Cluster Project, and Regional Innovation Cluster Program. Many people were involved in this project: Jon T. Butler, Masayuki Chiba, Bogdan Falk
Data Loading...
