Устройство для формирования тестов

 

Изобретение относится к области автоматики и вычислительной техники и может использоваться для генерации функционально полных тестовых программ при стохастическом контроле сложных дискретных объектов. Цель изобретения - расширение области применения за счет возможности синтеза тестов для дискретных объектов типа микропроцессоров. Устройство содержит генератор, два коммутатора, группу сумматоров по модулю два, генератор псевдослучайных чисел, блок стековой памяти, блок дешифрации, блок памяти. Очередная последовательность событий появляется на выходе устройства в зависимости от содержимого блока стековой памяти и условной вероятности формирования этой последовательности . Процесс продолжается асинхронно, последовательно и поразрядно до обнуления блока стековой памяти. 8 нп. I (Л с

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕаЪБЛИН (19) (И) 44781 А 1 (SD 4 G 06 F 11/26

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К АВТОРСКОМУ С8ИДЕТЕЛ6СТ8У (21) 4240092/24-24 (22) 03.03.87 (46) 15.12.88. Бюл. 9 46 (71) Кишиневский политехнический институт им. С. Лазо (72) В.И. Борщевич, Г.К. Бодян, В.Д. Жданов и В.В. Сидоренко (53) 681.3 (088.8) (56) Авторское свидетельство СССР

В 888003, кл. G 06 F 11/26, 1980.

Авторское свидетельство СССР

Р 1156079, кл. G 06 F 11/26, 1983. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ТЕСТОВ (57) Изобретение относится к области автоматики и вычислительной техники и может использоваться для генерации функционально полных тестовых программ при стохастическом контроле сложных дискретных объектов. Цель изобретения — расширение области применения эа счет возможности синтеза тестов для дискретных объектов типа микропроцессоров. Устройство .содержит генератор, два коммутатора, группу сумматоров по модулю два, генератор псевдослучайных чисел, блок стековой памяти, блок дешифрации, блок памяти. Очередная последовательность событий появляется на выходе устройства в зависимости от содержимого блока стековой памяти и условной вероятности формирования этой последовательности. Процесс продолжается а асинхронно, последовательно и поразрядно до обнуления блока стековой памяти. 8 ил.

1444781

Изобретение относится к области автоматики и вычислительной техники и может быть использовано для моделирования марковских ветвящихся про5 цессов, а также в качестве специализированного стохастического генератора тестовых последовательностей в составе систем стохастического функционального контроля дискретных объектов, включая микропроцессорные.

Цель изобретения — расширение области применения за счет обеспечения возможности синтеза тестов для дискретных объектов типа микропроцессоров.

На фиг. 1 показана структурная схе; ма устройства; на фиг. 2 — схема генератора тактовых импульсов; на фиг.3— схема блока стековой памяти; на 20 фиг. 4 — блок памяти; на фиг. 5— блок дешифрации; на Фиг. 6 — схема мультиплексора; на фиг. 7 — схема демультиплексора; на фиг. 8 — схема демультиплексора блока памяти. 25

Устройство (Фиг. 1) содержит генератор 1 тактовых импульсов, комму-. татор, образованный группой мультиплексоров 2.1...2.п с выходаии

3. 1...3.п.п. и 4.1...4.п,, группу 30 регистров 5. 1...5.k, группу сумматоров 6 по модулю два, генератор 7 псевдослучайных чисел, мультиплексор

8, блок 9 стековой памяти, блок 10 памяти, блок 11 дешифрации, коммутатор, построенный на демультиплексорах 12-14, триггер 15 пуска, вход

16 начальной установки, вход 17 начальных условий устройства.

Генератор тактовых импульсов

40 (фиг. 2) содержит синхрогенератор

18, элемент И 19, триггер 20, элемент И-НЕ 21, триггер 22, резистор

23.

Блок стековой памяти (фиг. 3) содержит элемент И 24, элемент ИЛИ 25, счетчик 26, группу регистров 27 сдвига.

Блок памяти (фиг. 4) содержит элемент И 28, счетчик 29, узел 30 памяти, демультиплексор 31.

Блок дешифрации (фиг. 5) содержит дешифратор 32, группу триггеров 33.

Мультиплексор (фиг. 6) содержит группу мультиплексоров 34.1...34.m.

Демультиплексор (фиг ° 7) содержит элементы И 35, 36, Мультиплексор блока памяти (фиг,8) содержит группу демультиплексоров 37.

Блок 10 предназначен для установления соответствия между двоичным числом b b „...Ь „, (Ь E (0,1 ), Ь,— старший разряд числа из числовой пос- ледовательности L = (0,1...,2"-1, сформированного на выходах первого сумматора 6 группы и мультиплексоров 2 группы, и последовательностью двоичных кодов, которыми MoryT быть двоичные числа S,. и/или команды проверяемого микропроцессорного устройства, где S;,c L i = 0,2 " .

На выходах сумматора 6 и группы мультиплексоров 2 формируется и-разрядное двоичное число (вектор)

3 старший разряд числа) из числовой последовательности L = (0,1...2"-1).

Например, если n = 4, то двоичное лежит в пределах (0000,...., 1111) и является адресом двоичной последовательности M., записанной в блоке 30 памяти. Следовательно, значение и определяется верхним пределом (log

maxtN l= 2 = 16 последовательностей).

Каждая двоичная последовательность

М представляет собой последователь1 ность из двоичных чисел S и/или последовательность, состоящую из пар а А, где а 1, — логическое значение "0" или "1", которое необходимо подать на соответствующий вход

А диагностируемого объекта. Здесь

k — — О, 1,2... — номер по порядку пары а А, а значение 1 +1 соответствует числу битов в тестовом наборе (под тестовым набором будем понимать двоичный вектор, подаваемый за один такт по всем входам контролируемого объекта, в данном устройстве тестовый набор формируется побитово, а под тестом (тестовая программа) подразумевается конечное число тестовых .наборов) .

Блок 11 предназначен для распределения значений битов à > (а 1, <0, 1) ), К вЂ” порядок бита (а в двоичной последовательности), соответствующий последовательности двоичных пар а А а,А ... по соответствующим адре1 сам А данной последовательности.

Например, если тестируемый объект имеет 16 входов, тогда значения числа з

1444781

AÄ (0,...,15), т.е. объекта. Для и = 4, k = 0,7, напринеобходимо 1g < 16-=4 разряда памяти мер М -я последовательность будет для задания соответствующего значе- записана в ячейку блока 30 памяти ния номера входа А диагностируемого 5 в следующем виде: Ъ,Ъ,Ъ.,Ъ, .а, А, а, А, г Аг . а А7

Зе 0 0 1 0 (01) 0 0000(11) 1 0001(11) 0 0010(11) ...0 0111(10) 3S что соответствует подаче восьмеричного кода (100)> на входы диагностируемого объекта с- 1-й по 8-й, при этом первый выход дешифратора 32 связан через соответствующий D-триггер 33 с.первым входом объекта, второй выход дешифратора 32 с вторым входом объекта и т.д., и каждое двоичное число и пара а А заканчивается двумя битами, значения и функции которых описаны в тексте.

Узел 30 памяти предназначен для хранения последовательности двоичных кодов. Объем памяти узла 30 должен быть не меньше количества бит, зани- 25 маемых всеми заданными последовательностями двоичных кодов. При этом данная последовательность представляет собой множество двоичных чисел (Я;) и/или множество пар а А, где а — логическое значение "0" или "1", которое необходимо подать на соответ-" ствующий вход А (A > — двоичный код номера входа) контролируемого дискретного объекта (k = 0,1,2..). Каждый двоичный код последовательности сопровождается двумя разрядами, которые определяют значения уровней .логических сигналов соответственно ,на первом и втором выходах узла 30 памяти. Двоичные значения этих раз-. рядов имеют следующие функции: "О" и "1" на первом и втором выходах узла 30 памяти соответственно на группе выходов узла 30 памяти дво45 ичное число Ъ„...Ь „ и считывание из узла 30 памяти необходимо продолжить, "1" и "1" на первом и втором выходах узла 30 памяти соответственно на группе выходов узла 30 памяти пара а А < и считывание из узла 30 памяти продолжается, "1" и "0" на " первом и втором выходах узла 30 па- к мяти соответственно считывание из узла 30 памяти закончится. Синхровходы и входы последовательного занесе-. ния регистров 27 сдвига группы, а ,также. информационные входы параллель-ыаф записи и управляющий вход счетчика 26 используются при подготовке устройства к работе. Через вход 16 устройства на управляющий вход V u вход установки в "0" счетчика 26 подается уровень "О", устанавливая, тем самым режим параллельной записи, а на информационные входы Q,-Dg счетчика 26 двоичный код числа 2, т.е. код 0100.

Для записи двоичного значения начального числа регистра 27 сдвига группы устанавливаются в режим после" довательного занесения со сдвигом информации вправо. Пред этим регистры 27 группы устанавливаются в"0", подав через вход 17 устройства на входы установки в "0" уровень "0".

Через вход 17 устройства на управляющие входы V регистров 27 группы подается уровень "0", на входы

V — уровень "1", а на соответствующие информационные входы D g — двоичный код начального числа, который записывается подачей тактового импульса на синхровходы регистров 27 группы.

На группе регистров 5 задается число N — - условная вероятность, величина которого лежит в пределах от 0 до 2 -1. Если сумма чисел, noh даваемая на входы К-разрядного сумматора 6, меньше 2 -1, то на выходе

k переноса сумматора 6 будет нуль, если сумма больше 2 -1, то на выходе переноса сумматора 6 будет еди" ница. Так как вероятность появления любого числа на выходе генератора 2 равна 1/2, то вероятность появления единицы на выходе переноса сумматора 6 будет равна N/2 ". Таким образом, числа N., находящиеся в задающем регистре 5, позволяют .форми-, .к ровать на выходах сумматора 6 двоичные последовательности с вероятностью появления нулей или единиц с наперед заданной точностью, равной 1 /2

По-входу 17 записывается в регистры 27 двоичное значение начального

5 14447 числа S,, определяющего вероятностные характеристики на выходах мультиплексора 8, а по входу 16 - двоичный код 0100, обеспечивающий условия для выполнения тактов начальной установки устройства.

Устройство работает следующим образом.

Пусть задано множество М, где 10

М «6 2 ", последовательностей двоичных кодов — правила подстановок, и в этом множестве каждому правилу подстановок соответствует свое двоичное число из числовой последователь- 15 .ности 0,1,...2"-1. Пусть также для всех правил подстаноъок определены

М одномерных законов распределения вероятностей Р „, т.е. вероятность перехода определенного сложения со- 20 бытия (последовательность двоичных кодов) С < за один такт из состояния

Б. в состояние S где

S; «S Е(Оф1 ° ее,2 ) е i, j, t = 0,2 ; 2Б

Количество распределений лишь в и самом общем случае будет равно чис- З0 лу цепочек С, которое равно 2 -1.

tl

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

Цепочек распределения могут.совпадать. Поэтому число M различных распределений удовлетворяет соотношения

М « 2. При этом количество регистров кода s группе 5 будет соответствовать значеиик М, т.е. имеем .оптимальные 40 аппаратурные затраты.

Каждому состоянию S; ставится в соответствие п-разрядное двоичное число Ь„Ь,b „(Ъ е (0„1 )), Ь p — старший разряд числа, из числовой последовательности О, 1 ...2"-1.

Блок 9 етековой памяти предназначен для промежуточного хранения двоичных чисел. Блок 9 стековой памяти работает по принципу "первым .вошел — 5< последним вышел". Поэтому при записи правила подстановки необходимо учитывать, что первым из блока 9 стековой памяти будет считано двоичное число Ь ...Ь „, являющееся последним в записи.

В начальный момент времени до прихода первого тактирующего сигнала от генератора 1 счетчик 29 блока 10 для

81 6 определенности находится в нулевом состоянии, в регистры группы 27 записано начальное значение двоичного числа, в счетчик 26 блока 9 записан двоичный код числа 2.

По приходу сигнала "Пуск" (отрицательной полярности в случае использования перечисленных ранее компонент) триггер 15 устанавливается в единичное состояние.

Единичный сигнал с прямого выхода триггера 15 поступает через . вход пуска генератора 1 на вход элемента И 19 вход установки в"О" триггера 20 и вхЬд элемента И-НЕ 21.

Синхроимпульс на выходе элемента И-НЕ

21 начнет вырабатываться в момент перепада импульса на выходе генератора 18 из состояния "0" в "1". При этом на первом и втором выходах генератора 1 начинают вырабатываться синхросигналы со скважностью два, Сигнал с первого выхода генератора 1 через демультиплексор 12 инициирует работу генератора 7 псевдослучайных чисел и через элемент ИЛИ

25 осуществляет сдвиг влево информации, записанной в регистрах 27 группй, тем самым считывая верхнее двоичное число из блока 9 стековой памяти.

Это число поступает на управляющие входы мультиплексора 8 и переключает соответствующую группу информационных входов íà его выходы., Сигнал с первого выхода генератора 1 подается на счетный вход (-1) счетчика 26, уменьшая его содержимое на единицу.

Псевдослучайные числа, формируемые в любых К разрядах регистров . сдвига генератора 7, подаются на один из входов К-разрядного сумматора 6, на другой вход сумматора 6 подается постоянное число, задаваемое регистром 5.i где i — двоичное число, подаваемое на управляющий вход мультиплексора 8 (в данный момент време-. ни значение i определяется двоичным числом, считываемым из блока 9 стековой памяти).

Таким образом, на вход узла 30 памяти блока 10 поступает двоичное число, которое сформировано со значением условных вероятностей, определяемых двоичным кодом, выбранным .

1 из блока 9 памяти. Это двоичное число определяет старшие разряды адреса последовательности двоичных кодов, 7 14 в то время как двоичное значение на выходах счетчика 29 определяет младшие разряды этого адреса. Далее на . выходах узла 30 памяти появляется соответствующее значение составляющей последовательности двоичных кодов.

В зависимости от логических значений сигналов на первом и втором выходах узла 30 памяти устройство будет работать в следующих трех режимах.

Режим первый — на первом и втором выходах узла 30 памяти соответ ственно "0" и "1", которые поступают

:на соответствующие управляющие входы

V„ H V регистров 27 группы. Таким обра,зом,регистры 27 группы устанавливаются в режим сдвига информации вправо.

В первом режиме осуществляется считывание двоичного числа из блока

9 памяти и просмотр следующего кода иэ блока 10.

"0" с первого выхода. блока 10 переключает информационные входы демультиплексоров 14 и 13 соответственно на их первые выходы, а "1" с второго выхода блока 10 переключает информационный вход демультиплексора 12 на его второй выход и информационные входы демультиплексора 31 на первую группу его выходов.

Сигнал с второго выхода тактово.го генератора 1 через мультиплексоры 13 и 14 поступает на вход элемента И 24 и блока 9 памяти. Нулевой уровень на его втором инверсном входе разрешает прохождение сигнала с первого входа через элемент И 24 на суммирующий вход счетчика 26 и на первый вход элемента ИЛИ 25. При этом счетчик 26 увеличивает свое содержимое на 1, а в регистрах 27 группы осуществляется сдвиг информации (содержимого) вправо и запись логических значений двоичного числа, устанавливаемых на.информационных входах D+.

Сйгнал с первого входа генератора

1 поступает через демультиплексор 12 на вход элемента И 28 и разрешаемый .уровнем "1" на его первом входе поступает на счетный вход (1) счетчика

29. На выходах счетчика 29 устанавливается увеличенный на единицу код, который поступает на группу адрес» о ных входов узла 30 памяти, на выходах которого появляется соответствующий двоичный код.

44781

Режим второй — "1" на первом и вт ор ом выходах бл ока 10.

В этом режиме осуществляется считывание пары а1,А >из блока .10, формирование на выходе блока 11 (и таким образом на выходе устройства) последовательности логических значений одноразрядного символа à < и "npo1g смотр" следующего кода из блока 10.

Уровень "1" с первого выхода блока 10 подается на управляющий вход, демультиплексора 31, переключая информационные входы на вторую группу

15 его выходов, и подключает информационные входы демультиплексоров 13 и

14 на их вторые выходы. При этом на второй группе выходов блока 10 грамматических подстановок устанавливается значение бита а и соответствующее значение адреса А, по которому должен быть подан данный бит а .

Синхросигнал с второго выхода тактового генератора 1 через демуль25 типлексор 13 поступает на вход блока 11, преобразуя код, поданный на

его информационные входы с второй группы выходов блока 10, в сигнал на выходе, который инициирует соот30 ветствующий триггер группы 35 и на выходе которого устанавливается соответствующее значение (бит.) a .

Очередной импульс с первого выхода тактового генератора 1 поступает на счетный вход счетчика 29, на выходе которого устанавливаются увеличенные на единицу значения младших . разрядов адреса соответствующей последовательности.

4О Режим третий: окончание считывания правила подстановки из блока 10"1" на первом выходе и "0" на втором .выходе блока 10, который поступает соответственно на управляющие входы

V < и V < регистров 2 7 сдвига группы (регистры 27 группы готовы к сдвигу .информации влево). Уровень "0" с вто: рого выхода блока 10 переключает информационные входы демультиплексоров 12 и 13 на их первые выходы. . Синхроимпульс с второго выхода тактового генератора 1 через демультиплексоры 13 и 14 поступает на вход установки в "0" R счетчика 29, обну55

Очередной импульс с первого выхода тактового генератора 1 через демультитйпексор 12 инициирует работу генератора 7 псевдослучайных чисел

9 14447 и через элемент ИЛИ 25 осуществляет сдвиг влево информации, записанной в регистрах 27 сдвига группы, тем самым считывая верхнее двоичное число из блока 9 стековой памяти.. Это дво5 ичное число поступает на управляющие входы мультиплексора 8 и переключает соответствующую группу информаци" онных входов на выходы. Псевдослучай- 10 ные числа, формируемые в любых К разрядах генератора 7 псевдослучайных чисел, подаются на один из входов Кразрядного сумматора 6. На другой вход сумматора б подается постоянное число, задаваемое одним из регистров

5 кода группы. Данный двухфазный многорежимный процесс продолжается до тех пор, пока из регистров 27 сдвига группы не будет считано последнее двоичное число. При этом счетчик 26 . обнулится и при подаче тактирующего импульса на второй вход (-1) счетчика 26 на выходе заема сформируется импульс. Этот импульс переключит вы- 2Б хад триггера 15 в состояние "О", который запрещает прохождение импульсов через элемент И 19 генератора 1.

Таким образом, на выходе устройства формируются последовательности 3п событий †. функционально полная теставая программа, в соответствии с.законом распределения условных вероятностей, причем последовательности событий могут иметь различную длину. Ко35 нечность генерируемых последовательностей определяется количеством двоичных чисел, записываемых во время работы устройства в блок 9 памяти.

Формула изобретения

Устройство для формирования тестов, содержащее блок памяти, генератор псевдослучайных чисел, генера- 4 тор тактовых импульсов, мультиплексор, блок дешифрации и триггер пуска, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения путем обеспечения возможности синтеза тестов для дискретных объектов типа микропроцессор, устройство содержит два коммутатора, блок стековой памяти, группу суммато, ров по модулю два и группу регистров,:: причем выходы регистров группьi соединены с информационными входами мультиплексора, управляющий вход которого соединен с первым выходом бла81 1О ка стековой памяти, второй вьгход которого соединен с входом сброса триггера пуска, вход установки которого соединен с входом пуска устройства, выход триггера пуска соединен с входом пуска генератора тактовых импульсов, первый и второй выходы которого соединены с первым и вторым управляюющими входами первого коммутатора соответственно, первый информационный вход которого соединен с первым выходом блока памяти и с входом разрешения блока стековой памяти, первый выход коммутатора соединен с синхровходами генератора псевдослучайной последовательности и блока стековой памяти, вход сброса которого соединен с входом сброса устройства,к входу нача. льных условий которого подключена первая группа информационных входов блока стековой памяти, выходы мультиплексора соединены с первыми входами соответствующих сумматоров по модулю два группы, вторые входы которых соединены с выходами генераторов псевдо" случайных чисел, выход первого сумматора по модулю два группы соединен с входом разрешения записи блока памяти и с входом синхронизации первого коммутатора, выходы которого соединеI ны с адресными входами блока памяти вход синхронизации которого соединен с первым выходом второго коммутатора, второй выход которого соединен с входом синхронизации блока стековой памяти, вход записи которого соединен с третьим выходом второго коммутатора, первая и вторая группы выходов блока памяти соединены с группой информационных входов блока дешифрации и с второй группой информационных входов блока стековой памяти соответственно, вход синхронизации блока дешифрации соединен с четвертым выходом второго коммутатора,выходы сумматоров по модулю два группы с второго по (и+1)-й (где пдлина тестовой последовательности) соединены с информационными входами первого коммутатора, выходы блока дешифрации являются выходами устройства, вторая группа информационных входов блока стековой памяти соединена с третьей группой выходов блока памяти и с группой информационных входов второго коммутатора,четвертый выход которого соединен с входом блокировки блока стековой памяти.

144478)

На f2

На 1З

0m5

3444781

0m аа /5

На 11

На VOiz

/ФЯ, g

1444781

1444781

Oef

Я 1

О Я

Фа 11

Составитель А. Сиротская

Техред Л.Олийнык

Редактор О. Спесивых

Корректор М. Демчик

Заказ 6482/48

Тираж 704

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Подписное

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4