Загрузка...

Систолические алгоритмы


Систолические алгоритмы:

1). Символьная обработка: поиск вхождения подстроки в строку.

Предположим у нас имеется две строки:

clip_image002

clip_image004

Ставится задача поиска вхождения строки В в строку А. Оказывается этих точек вхождения может быть не одна. Упростим задачу и будем считать, что bi и аi это двоичные цифры, т.е. аi??0,1?, bi??0,1,??. Рез-тат мы должны получить в следующем виде:

clip_image006clip_image008

Эта задача решается с помощью линейной систолической структуры:

clip_image010

Рис.7.21.

Всего пять ПЭ. И на эту систолическую структуру мы будем подавать данные в разных направлениях. Приведем временную диаграмму функционирования этой системы.

Временная диаграмма функционирования системы

Рис.7.22. Временная диаграмма функционирования системы

В первый момент времени считаем, что никаких данных не содержится, т.е. поступает а1, далее ничего не содержится, а в конце b1.

clip_image014&clip_image016

clip_image018

В результате получаем значение множества clip_image020. За clip_image022-тактов ищется вхождение подстроки в строку.

Загрузка...