Index generation functions

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

Index generation functions are binary-input integer valued functions. They represent functions of content addressable memories (CAMs). Applications include: IP address tables; terminal controllers; URL lists; computer virus scanning circuits; memory patch circuits; list of English words; code converters; and pattern matching circuits. This book shows memory-based realization of index generation functions. It shows: 1. methods to implement index generation functions by look-up table (LUT) cascades and index generation units (IGU), 2. methods to reduce the number of variables using linear transformations, and 3. methods to estimate the sizes of memories, with many illustrations, tables, examples, exercises, and their solutions.

Original languageEnglish
Title of host publicationSynthesis Lectures on Digital Circuits and Systems
Subtitle of host publicationLecture #54
PublisherMorgan and Claypool Publishers
Pages1-183
Number of pages183
Edition3
DOIs
Publication statusPublished - 1 Jan 2020

Publication series

NameSynthesis Lectures on Digital Circuits and Systems
Number3
Volume14
ISSN (Print)1932-3166
ISSN (Electronic)1932-3174

Fingerprint

Data storage equipment
Networks (circuits)
Code converters
Computer viruses
Associative storage
Linear transformations
Pattern matching
Websites
Scanning
Controllers

Keywords

  • Affine equivalence
  • Code converter
  • Computer virus scanning
  • Constant-weight code
  • Equivalence class
  • Functional decomposition
  • Hash function
  • IP address table
  • Incompletely specified function
  • Index generation function
  • Index generation unit
  • Irreducible index generation function
  • LUT cascade
  • Linear decomposition
  • Linear transformation
  • M-out-of-n code
  • Minimization of variables
  • Random function
  • SAT solver
  • Symmetric function
  • URL list
  • Upper bound

Cite this

Sasao, T. (2020). Index generation functions. In Synthesis Lectures on Digital Circuits and Systems: Lecture #54 (3 ed., pp. 1-183). (Synthesis Lectures on Digital Circuits and Systems; Vol. 14, No. 3). Morgan and Claypool Publishers. https://doi.org/10.2200/S00953ED1V01Y201909DCS057
Sasao, Tsutomu. / Index generation functions. Synthesis Lectures on Digital Circuits and Systems: Lecture #54. 3. ed. Morgan and Claypool Publishers, 2020. pp. 1-183 (Synthesis Lectures on Digital Circuits and Systems; 3).
@inbook{ee73b10c9a994aa8a53885d93d522687,
title = "Index generation functions",
abstract = "Index generation functions are binary-input integer valued functions. They represent functions of content addressable memories (CAMs). Applications include: IP address tables; terminal controllers; URL lists; computer virus scanning circuits; memory patch circuits; list of English words; code converters; and pattern matching circuits. This book shows memory-based realization of index generation functions. It shows: 1. methods to implement index generation functions by look-up table (LUT) cascades and index generation units (IGU), 2. methods to reduce the number of variables using linear transformations, and 3. methods to estimate the sizes of memories, with many illustrations, tables, examples, exercises, and their solutions.",
keywords = "Affine equivalence, Code converter, Computer virus scanning, Constant-weight code, Equivalence class, Functional decomposition, Hash function, IP address table, Incompletely specified function, Index generation function, Index generation unit, Irreducible index generation function, LUT cascade, Linear decomposition, Linear transformation, M-out-of-n code, Minimization of variables, Random function, SAT solver, Symmetric function, URL list, Upper bound",
author = "Tsutomu Sasao",
year = "2020",
month = "1",
day = "1",
doi = "10.2200/S00953ED1V01Y201909DCS057",
language = "English",
series = "Synthesis Lectures on Digital Circuits and Systems",
publisher = "Morgan and Claypool Publishers",
number = "3",
pages = "1--183",
booktitle = "Synthesis Lectures on Digital Circuits and Systems",
edition = "3",

}

Sasao, T 2020, Index generation functions. in Synthesis Lectures on Digital Circuits and Systems: Lecture #54. 3 edn, Synthesis Lectures on Digital Circuits and Systems, no. 3, vol. 14, Morgan and Claypool Publishers, pp. 1-183. https://doi.org/10.2200/S00953ED1V01Y201909DCS057

Index generation functions. / Sasao, Tsutomu.

Synthesis Lectures on Digital Circuits and Systems: Lecture #54. 3. ed. Morgan and Claypool Publishers, 2020. p. 1-183 (Synthesis Lectures on Digital Circuits and Systems; Vol. 14, No. 3).

Research output: Chapter in Book/Report/Conference proceedingChapter

TY - CHAP

T1 - Index generation functions

AU - Sasao, Tsutomu

PY - 2020/1/1

Y1 - 2020/1/1

N2 - Index generation functions are binary-input integer valued functions. They represent functions of content addressable memories (CAMs). Applications include: IP address tables; terminal controllers; URL lists; computer virus scanning circuits; memory patch circuits; list of English words; code converters; and pattern matching circuits. This book shows memory-based realization of index generation functions. It shows: 1. methods to implement index generation functions by look-up table (LUT) cascades and index generation units (IGU), 2. methods to reduce the number of variables using linear transformations, and 3. methods to estimate the sizes of memories, with many illustrations, tables, examples, exercises, and their solutions.

AB - Index generation functions are binary-input integer valued functions. They represent functions of content addressable memories (CAMs). Applications include: IP address tables; terminal controllers; URL lists; computer virus scanning circuits; memory patch circuits; list of English words; code converters; and pattern matching circuits. This book shows memory-based realization of index generation functions. It shows: 1. methods to implement index generation functions by look-up table (LUT) cascades and index generation units (IGU), 2. methods to reduce the number of variables using linear transformations, and 3. methods to estimate the sizes of memories, with many illustrations, tables, examples, exercises, and their solutions.

KW - Affine equivalence

KW - Code converter

KW - Computer virus scanning

KW - Constant-weight code

KW - Equivalence class

KW - Functional decomposition

KW - Hash function

KW - IP address table

KW - Incompletely specified function

KW - Index generation function

KW - Index generation unit

KW - Irreducible index generation function

KW - LUT cascade

KW - Linear decomposition

KW - Linear transformation

KW - M-out-of-n code

KW - Minimization of variables

KW - Random function

KW - SAT solver

KW - Symmetric function

KW - URL list

KW - Upper bound

UR - http://www.scopus.com/inward/record.url?scp=85074211431&partnerID=8YFLogxK

U2 - 10.2200/S00953ED1V01Y201909DCS057

DO - 10.2200/S00953ED1V01Y201909DCS057

M3 - Chapter

AN - SCOPUS:85074211431

T3 - Synthesis Lectures on Digital Circuits and Systems

SP - 1

EP - 183

BT - Synthesis Lectures on Digital Circuits and Systems

PB - Morgan and Claypool Publishers

ER -

Sasao T. Index generation functions. In Synthesis Lectures on Digital Circuits and Systems: Lecture #54. 3 ed. Morgan and Claypool Publishers. 2020. p. 1-183. (Synthesis Lectures on Digital Circuits and Systems; 3). https://doi.org/10.2200/S00953ED1V01Y201909DCS057