Метод синтеза генераторов детерминированных тестов на сетях клеточных автоматов (СКА)
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?четчиках) [6].
Большое распространение получают генераторы тестов на основе СКА. Главное достоинство таких сетей по сравнению с другими схемами - регулярность структуры и локальность взаимосвязей между клеточными автоматами (КА), что делает их привлекательными при реализации ДУ на программируемых логических интегральных схемах типа CPLD, FPGA. Важной характеристикой СКА является более высокая частота генерации тестов.
4.1 Метод генерирования субпоследовательностей
Исходным данным для работы алгоритма является детерминированное множество двоичных векторов М, в виде произвольной последовательности
где vi - i-й вектор M, m - количество векторов в M.
В процессе работы алгоритма, исходное множество М сортируется определенным образом, при этом М, как правило, разбивается на несколько субпоследовательностей Sl, каждая из которых реализуется генератором на СКА. Необходимо, чтобы эти субпоследовательности удовлетворяли следующим условиям:
) Каждая субпоследовательность Sl должна быть детерминированной;
) ;
) Длина субпоследовательностей Sl - ;
) Последний вектор Sl берется в качестве первого Sl+1.
где символ означает объединение множеств, Sl отыскиваемая субпоследовательность, над которой выполняются действия.
Весь алгоритм разбит на 2 этапа. Первый этап - это упорядочивание исходного множества векторов в субпоследовательности, отвечающие выше указанным требованиям. Второй - это вычисление по полученным субпоследовательностям правил настроек СКА.
Упорядочивание исходного множества в субпоследовательности
Первый этап состоит из таких шагов:
1)Все векторы из исходного множества пронумеровываются.
2)Путём подбора отыскивается начальный вектор vн.
)Текущая субпоследовательность Sl= [], l=1.
4)Присоединить начальный вектор к Sl (Sl (1) =vн).
)Если в М не существует непомеченного вектора vi, такого, чтобы для субпоследовательности Sl+ vi выполнялось (2.2), перейти к пункту 8.
)Sl= vi.
7)Пометить vi как использованный.
)Если в М все векторы помечены, перейти к пункту 12.
)l=l+1;
10)Sl (1) =vi;
11)Перейти к пункту 5;
)Конец.
Знак "+" в пунктах 5 и 6 означает операцию присоединения вектора v к субпоследовательности Sl.
4.2 Алгоритмы отыскания субпоследовательностей
4.2.1 Алгоритм основной программы
На рисунке 4.2 показана блок-схема алгоритма первого этапа, реализованного в системе Delphi.
В данной схеме переменные М, List2 - объектного типа. Они содержат в себе список строк, а так же свойства и методы, предназначенные для работы со списком. Переменная М содержит исходный список векторов, а List2 предназначен для хранения полученных субпоследовательностей. Переменные i, j, L - целочисленного типа, i используется как счетчик, в j хранится индекс начального вектора, L используется для сравнения длинны субпоследовательности, полученной с различными начальными векторами.
В алгоритме используется подпрограмма GetSubSeq, с тремя параметрами. Первый параметр представляет собой список и должен содержать исходный список векторов. Второй параметр - это строка, содержащая первый вектор искомой субпоследовательности. Третий параметр - список к которому будет добавлена найденная субпоследовательность. Векторы, вошедшие в субпоследовательность удаляются из исходного списка.
Операторы с 4 по 8 составляют тело цикла, в котором отыскивается наилучший начальный вектор для первой субпоследовательности. Критерий качества этого вектора - максимально возможная длина первой субпоследовательности. В блоке 4 запоминается i-й вектор из исходного списка в переменную Sample, удаляется i-й вектор из исходного списка, очищается список, предназначенный для сохранения результата. В переменной L сохраняется длина субпоследовательности, полученная для предыдущего начального вектора. На первом проходе цикла L = 0. Оператор 6 выполняет переход по ветви "Да", если длина субпоследовательности для текущего начального вектора больше, чем для предыдущего, в этом случае запоминается улучшенный результат (блок 7). В результате в переменной Sample2 останется наилучший начальный вектор для первой субпоследовательности.
В блоке 9 выполняется поиск индекса вектора Sample2 в исходном множестве, а затем этот индекс удаляется. Это нужно для того, чтобы данный вектор не повторился дважды в первой субпоследовательности. После выполнения блока10, в List2 запоминается первая субпоследовательность. Далее, построение остальных субпоследовательностей происходит в цикле, условием выхода из которого (блок 11) является отсутствие неиспользованных векторов в исходном множестве.
4.2.2 Алгоритмы подпрограмм
Основой алгоритма, приведенного в п.4.2.1 является подпрограмма GetSubSeq. Ее блок-схема представлена на рис.4.3 Переменная М содержит исходное множество двоичных векторов. Sample - содержит начальный вектор, Lst2 - список, к которому будет добавлена полученная субпоследовательность. List3 и List4 - два вспомогательных списка, которые создаются в операторе 2 и существуют все время выполнения подпрограммы. List3, после выполнения подпрограммы, будет содержать искомую субпоследовательность, List4 предназначен для хранения результатов выполнения подпрограммы GetByMask.
В результате выполнения блока 2, в List3 находится начальный вектор. В блоке 3 вызывается подпрограмма GetMask, которая на основе списка List3 получает маску, используемую для нахождения следующего вектора су?/p>