VLSI design of a systolic array for finding maximal overlaps of strings

Mohammad Alimuddin; Gerhard F. Beckhoff

doi:10.1109/MWSCAS.1992.271263

VLSI design of a systolic array for finding maximal overlaps of strings

Mohammad Alimuddin
, Gerhard F. Beckhoff

King Fahd University of Petroleum & Minerals

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

Abstract

The Shortest Common Superstring (SCS) problem requires that the maximal overlaps between a given set of strings be found. Conventionally the Knuth-Morris-Pratt (KMP) algorithm is employed for this purpose. A hardware implementation of the KMP algorithm would be pattern specific and hence infeasible for the SCS problem. An efficient VLSI design of a systolic array for finding maximal overlaps of strings is described in this paper.

Original language	English
Title of host publication	1992 Proceedings of the 35th Midwest Symposium on Circuits and Systems
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	556-559
Number of pages	4
ISBN (Electronic)	0780305108
DOIs	https://doi.org/10.1109/MWSCAS.1992.271263
State	Published - 1992

Publication series

Name	Midwest Symposium on Circuits and Systems
Volume	1992-August
ISSN (Print)	1548-3746

Bibliographical note

Publisher Copyright:
© 1992 IEEE.

ASJC Scopus subject areas

Electronic, Optical and Magnetic Materials
Electrical and Electronic Engineering

Access to Document

10.1109/MWSCAS.1992.271263

Cite this

Alimuddin, M., & Beckhoff, G. F. (1992). VLSI design of a systolic array for finding maximal overlaps of strings. In 1992 Proceedings of the 35th Midwest Symposium on Circuits and Systems (pp. 556-559). Article 271263 (Midwest Symposium on Circuits and Systems; Vol. 1992-August). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/MWSCAS.1992.271263

@inproceedings{6d4242db3d714206805e39f2c5b71fdf,

title = "VLSI design of a systolic array for finding maximal overlaps of strings",

abstract = "The Shortest Common Superstring (SCS) problem requires that the maximal overlaps between a given set of strings be found. Conventionally the Knuth-Morris-Pratt (KMP) algorithm is employed for this purpose. A hardware implementation of the KMP algorithm would be pattern specific and hence infeasible for the SCS problem. An efficient VLSI design of a systolic array for finding maximal overlaps of strings is described in this paper.",

author = "Mohammad Alimuddin and Beckhoff, \{Gerhard F.\}",

note = "Publisher Copyright: {\textcopyright} 1992 IEEE.",

year = "1992",

doi = "10.1109/MWSCAS.1992.271263",

language = "English",

series = "Midwest Symposium on Circuits and Systems",

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

pages = "556--559",

booktitle = "1992 Proceedings of the 35th Midwest Symposium on Circuits and Systems",

address = "United States",

}

VLSI design of a systolic array for finding maximal overlaps of strings. / Alimuddin, Mohammad; Beckhoff, Gerhard F.
1992 Proceedings of the 35th Midwest Symposium on Circuits and Systems. Institute of Electrical and Electronics Engineers Inc., 1992. p. 556-559 271263 (Midwest Symposium on Circuits and Systems; Vol. 1992-August).

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

TY - GEN

T1 - VLSI design of a systolic array for finding maximal overlaps of strings

AU - Alimuddin, Mohammad

AU - Beckhoff, Gerhard F.

PY - 1992

Y1 - 1992

N2 - The Shortest Common Superstring (SCS) problem requires that the maximal overlaps between a given set of strings be found. Conventionally the Knuth-Morris-Pratt (KMP) algorithm is employed for this purpose. A hardware implementation of the KMP algorithm would be pattern specific and hence infeasible for the SCS problem. An efficient VLSI design of a systolic array for finding maximal overlaps of strings is described in this paper.

AB - The Shortest Common Superstring (SCS) problem requires that the maximal overlaps between a given set of strings be found. Conventionally the Knuth-Morris-Pratt (KMP) algorithm is employed for this purpose. A hardware implementation of the KMP algorithm would be pattern specific and hence infeasible for the SCS problem. An efficient VLSI design of a systolic array for finding maximal overlaps of strings is described in this paper.

UR - https://www.scopus.com/pages/publications/85065739091

U2 - 10.1109/MWSCAS.1992.271263

DO - 10.1109/MWSCAS.1992.271263

M3 - Conference contribution

AN - SCOPUS:85065739091

T3 - Midwest Symposium on Circuits and Systems

SP - 556

EP - 559

BT - 1992 Proceedings of the 35th Midwest Symposium on Circuits and Systems

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

VLSI design of a systolic array for finding maximal overlaps of strings

Abstract

Publication series

Bibliographical note

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this