University of South Florida

Raghu Sastry

Nagarajan Ranganathan

The edit distance between two strings a.sub.1, . . . , a.sub.m and b.sub.1, . . . , b.sub.n is the minimum cost s of a sequence of editing operations (insertions, deletions and substitutions) that convert one string into the other. This invention provides VLSI circuit structure for computing the edit distance between two strings over a given alphabet. The circuit structure can perform approximate string matching for variable edit costs. More importantly, the circuit structure does not place any constraint on the lengths of the strings that can be compared. It makes use of simple basic cells and requires regular nearest-neighbor communication, which makes it suitable for VLSI implementation.

VLSI circuit structure for determining the edit distance between strings

A VLSI structure and method for polygon recognition that identifies an unknown two dimensional contour as corresponding to one or more of a plurality of known two dimensional contours. The VLSI architecture comprises a systolic processing system comprising a plurality of matrix element processing elements (MEPEs), and an array of feasible match processing elements (FMPEs) interconnected with selected MEPEs and with each other in a predetermined configuration. The plurality of MEPEs receive inputs comprising pairs of edge length ratios and corresponding threshold values for consecutive edges of the unknown contour and for each of the known polygon contours. Each MEPE (i) receives edge length ratios and threshold values for a pair of edges of the unknown contour and a known polygon contour, (ii) determines a dissimilarity value for the pair of edges, and (iii) directs this value to a selected FMPE of the array. The dissimilarity value is determined using the absolute differences between respective edge length ratios and threshold values for the pair of edges. The array of FMPEs determines feasible matches between pairs of consecutive edges of the unknown contour and the known polygon contours and delivers outputs related thereto, and a comparator device compares such outputs and delivers a final output which is indicative of the longest number of consecutive edges, above a predetermined minimum, for which feasible matches have occurred between the unknown contour and a known polygon contour.

Growing community of inventors

Campbell, CA, United States of America

Raghu Sastry