Approaches to permutation-invariant Boolean function characterization

Ulf Schlichtmann; Franc Brglez; Michael Hermann

doi:10.1109/SSST.1992.712273

Approaches to permutation-invariant Boolean function characterization

Ulf Schlichtmann, Franc Brglez, Michael Hermann

Chair of Electronic Design Automation

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

This paper introduces characteristic signatures for Boolean functions. The signatures exhibit little or no sensitivity to permutations of input variables. We use these signatures to develop a method of rapidly matching subcircuits with cells in a (large) library. The procedure is analogous to hashing. As we cannot guarantee uniqueness of the signatures, we have devised an efficient collision strategy. It is based on extending basic signatures to resolve aliases. This approach promises significant improvements for library matching with large libraries, for example in EPGA technology mapping.

Original language	English
Title of host publication	Proceedings - SSST/CSA 1992
Subtitle of host publication	24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	258-264
Number of pages	7
ISBN (Electronic)	0818626658, 9780818626654
DOIs	https://doi.org/10.1109/SSST.1992.712273
State	Published - 1992
Event	24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design, SSST/CSA 1992 - Greensboro, United States Duration: 1 Mar 1992 → 3 Mar 1992

Publication series

Name	Proceedings - SSST/CSA 1992: 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design

Conference

Conference	24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design, SSST/CSA 1992
Country/Territory	United States
City	Greensboro
Period	1/03/92 → 3/03/92

Access to Document

10.1109/SSST.1992.712273

Cite this

Schlichtmann, U., Brglez, F., & Hermann, M. (1992). Approaches to permutation-invariant Boolean function characterization. In Proceedings - SSST/CSA 1992: 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design (pp. 258-264). Article 712273 (Proceedings - SSST/CSA 1992: 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SSST.1992.712273

Schlichtmann, Ulf ; Brglez, Franc ; Hermann, Michael. / Approaches to permutation-invariant Boolean function characterization. Proceedings - SSST/CSA 1992: 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design. Institute of Electrical and Electronics Engineers Inc., 1992. pp. 258-264 (Proceedings - SSST/CSA 1992: 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design).

@inproceedings{ba03ef9df89e495c8453ced391cea299,

title = "Approaches to permutation-invariant Boolean function characterization",

abstract = "This paper introduces characteristic signatures for Boolean functions. The signatures exhibit little or no sensitivity to permutations of input variables. We use these signatures to develop a method of rapidly matching subcircuits with cells in a (large) library. The procedure is analogous to hashing. As we cannot guarantee uniqueness of the signatures, we have devised an efficient collision strategy. It is based on extending basic signatures to resolve aliases. This approach promises significant improvements for library matching with large libraries, for example in EPGA technology mapping.",

author = "Ulf Schlichtmann and Franc Brglez and Michael Hermann",

note = "Publisher Copyright: {\textcopyright} 1992 IEEE.; 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design, SSST/CSA 1992 ; Conference date: 01-03-1992 Through 03-03-1992",

year = "1992",

doi = "10.1109/SSST.1992.712273",

language = "English",

series = "Proceedings - SSST/CSA 1992: 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "258--264",

booktitle = "Proceedings - SSST/CSA 1992",

}

Schlichtmann, U, Brglez, F & Hermann, M 1992, Approaches to permutation-invariant Boolean function characterization. in Proceedings - SSST/CSA 1992: 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design., 712273, Proceedings - SSST/CSA 1992: 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design, Institute of Electrical and Electronics Engineers Inc., pp. 258-264, 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design, SSST/CSA 1992, Greensboro, United States, 1/03/92. https://doi.org/10.1109/SSST.1992.712273

Approaches to permutation-invariant Boolean function characterization. / Schlichtmann, Ulf; Brglez, Franc; Hermann, Michael.
Proceedings - SSST/CSA 1992: 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design. Institute of Electrical and Electronics Engineers Inc., 1992. p. 258-264 712273 (Proceedings - SSST/CSA 1992: 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Approaches to permutation-invariant Boolean function characterization

AU - Schlichtmann, Ulf

AU - Brglez, Franc

AU - Hermann, Michael

PY - 1992

Y1 - 1992

N2 - This paper introduces characteristic signatures for Boolean functions. The signatures exhibit little or no sensitivity to permutations of input variables. We use these signatures to develop a method of rapidly matching subcircuits with cells in a (large) library. The procedure is analogous to hashing. As we cannot guarantee uniqueness of the signatures, we have devised an efficient collision strategy. It is based on extending basic signatures to resolve aliases. This approach promises significant improvements for library matching with large libraries, for example in EPGA technology mapping.

AB - This paper introduces characteristic signatures for Boolean functions. The signatures exhibit little or no sensitivity to permutations of input variables. We use these signatures to develop a method of rapidly matching subcircuits with cells in a (large) library. The procedure is analogous to hashing. As we cannot guarantee uniqueness of the signatures, we have devised an efficient collision strategy. It is based on extending basic signatures to resolve aliases. This approach promises significant improvements for library matching with large libraries, for example in EPGA technology mapping.

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

U2 - 10.1109/SSST.1992.712273

DO - 10.1109/SSST.1992.712273

M3 - Conference contribution

AN - SCOPUS:85068014393

T3 - Proceedings - SSST/CSA 1992: 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design

SP - 258

EP - 264

BT - Proceedings - SSST/CSA 1992

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design, SSST/CSA 1992

Y2 - 1 March 1992 through 3 March 1992

ER -

Schlichtmann U, Brglez F, Hermann M. Approaches to permutation-invariant Boolean function characterization. In Proceedings - SSST/CSA 1992: 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design. Institute of Electrical and Electronics Engineers Inc. 1992. p. 258-264. 712273. (Proceedings - SSST/CSA 1992: 24th Southeastern Symposium on System Theory and 3rd Annual Symposium on Communications, Signal Processing Expert Systems, and ASIC VLSI Design). doi: 10.1109/SSST.1992.712273

Approaches to permutation-invariant Boolean function characterization

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this