Устройство для формирования тестов Советский патент 1988 года по МПК G06F11/26 

4 4 4

ч1

00

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

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

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

Устройство (фиг. 1) содержит генератор 1 тактовых импульсов, коммун татор, образованный группой мульти- плексоров ...2.п, с выхода}-ш 3.1...3.п.п„ и 4.1...4.п., группу регистров 5.1.t.5.k, группу сумматоров 6 по модулю два, генератор 7 псевдослучайных чисел, мультиплексор 8, блок 9 стековой памяти, блок 10 памяти, блок 11 дешифрации, коммутатор, построенньй на демультиплексо- pax 12-14, триггер 15 пуска, вход 16 начальной установки, вход 17 начальных условий устройства.

Генератор тактовых импульсов (фиг. 2) содержит синхрогенератор 18, элемент И 19, триггер 20, элемент И-НЕ 21, триггер 22, резистор 23.

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

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

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

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

Демультиплексор (фиг. 7) содержит элементы И 35, 36,

5

0

5

0

5

0

5

5

Мультиплексор блока памяти (фиг.8) содержит группу демультиплексоров 37.

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

На выходах сумматора 6 и группы мультиплексоров 2 формируется п-раз- рядное двоичное число (вектор) bj.o.bt, (bj - О или 1, bo - старший разряд числа) из числовой последовательности L (0,1.. .) . Например, если п 4, то двоичное число S bob,b,b J, где S; е L-, лежит в пределах (0000,....,1111) и является адресом двоичной последовательности М;, записанной в блоке 30 памяти. Следовательно, значение п определяется верхним пределом , где М - число всех последовательностей М (для рассматриваемого примера maxtM N 16 последовательностей).

Каждая двоичная последовате чьность М. представляет собой последовательность из двоичный чисел S ; и/или последовательность, состоящую из пар -а| А(, где а j - логическое значение О или 1, которое необходимо подать на соответствующий вход А, диагностируемого объекта. Здесь k 0,1,2... - номер по порядку пары , а значение k+1 соответствует числу битов в тестовом наборе (под тестовым набором будем понимать двоичный вектор, подаваемый за один такт по всем входам контролируемого объекта, в данном устройстве тестовый набор формируется побитово, а под тестом (тестовая программа) подразумевается конечное число тестовых .наборов).

Блок 11 предназначен для распределения значений битов а (а е О, 1) ), К - порядок бита (а, в двоичной последовательности) , соответствующий последовательности двоичных пар a(jAca,A... по соответствующим адресам А данной последовательное.

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

31444781

А лежат в пределах (0,..,,15)g, т.е. объекта. Для п 4, k

необходимо Ig разряда памяти для задания соответствующего значения номера входа А диагностируемого

мер последовател записана в ячейку бло в следующем виде:

объекта. Для п 4, k

0,7, например последовательность будет записана в ячейку блока 30 памяти в следующем виде:

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

(01)

АО

О 0000(11)

что соответствует подаче восьмеричного кода (100)g на входы диагностируемого объекта с 1-й по 8-й, при этом первый выход дешифратора 32 связан через соответствующий D-триг- гер 33 с.первым входом объекта, второй выход дешифратора 32 с вторым входом объекта и т.д., и каждое двоичное число и пара а А заканчивается двумя битами, значения и функции которых описаны в тексте.

Узел 30 памяти предназначен для хранения последовательности двоичных

кодов. Объем памяти узла 30 должен бытъ не меньше количества бит, занимаемых всеми заданными последовательностями двоичных кодов. При этом данная последовательность представляет собой множество двоичных чисел (S,-) и/или множество пар , где . логическое значение О шш 1, которое необходимо подать на соответ-

ствующий вход Aj ft двоичный код номера входа) контролируемого дискретного объекта (k 0,1,2..). Каждый двоичный код последовательности сопровождается двумя разрядами, которые определяют значения уровней

логических сигналов, соответственно jHa первом и йтором выходах узла 30 памяти. Двоичные значения этих разрядов имеют следующие функции: О и 1 на первом и втором выходах узла 30 памяти соответственно на группе выходов узла 30 памяти двоичное число .-Ь, и считывание из узла 30 памяти необходимо продолжить, 1 и 1 на первом и втором выходах узла 30 памяти соответственно на группе вькодов узла 30 памяти пара (и считывание из узла 30 памяти продолжается, 1 и О на первом и втором выходах узла 30 памяти соответственно считывание из узла 30 памяти закончится. Синхровхо- ДЫ и входы последовательного занесения регистров 27 сдвига группы, а .также, информационные входы параллель«о4 записи и управляющий вход счетчиЗг AI

1 0001 Си)

о 0010(11) ...о 0111(10),

5

0

0

5

0

5

0

ка 26 используются при подготовке устройства к работе. Через вход 16 устройства на управляющий вход V и вход установки в О счетчика 26 подается уровень О, устанавливая, тем сгамь1м режим параллельной записи, а на информационные входы P, счетчика 26 двоичный код числа 2, т.е. код 0100.,

Для записи двоичного значения начального числа регистра 27 сдвига группы устанавливаются в реж1-гм после . довательного занесения со сдвигом : информации вправо. Пред этим регист- 5 ры 27 группы устанавливаются , подав через вход 17 устройства на входы установки в О уровень О. Через вход 17 устройства на управляющие входы V, регистров 27 группы подается уровень О, на входы V - уровень 1, а на соответствующие информационные входы D |. - двоичный код начального числа, который записьшается подачей тактового импульса на синхровходы регистров 27 группы.

На группе регистров 5 задается число N - условная вероятность, ве- л гчина которого лежит в пределах от О до 2 -1. Если сумма чисел, подаваемая на входы К-разрядного сумматора 6, меньше 2-1, то на выходе переноса сумматора 6 будет нуль, если сумма больше 2 -1, то на выходе переноса сумматора 6 будет еди ница. Так как вероятность появления любого числа на выходе генератора 7 равна 1/2, то вероятность появления единицы на выходе перенося сумматора 6 будет равна N/2 . Таким образом, числа N;, находящиеся в задающем регистре 5, позволяют.-формировать на выходах сумматора 6 двоичные последовательности с вероятностью появления нулей или единиц с наперед заданной точностью, равной 1/2Ч

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

5

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

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

, Пусть задано множество М, где М i 2 последовательностей .двоичных кодов - правила подстановок, и в этом множестве каждому правилу подстановок соответствует свое двоич14447816

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

числа, в счетчик 26 блока 9 записан двоичный код числа 2,

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

Единичный сигнал с прямого выхода триггера 15 поступает через . вход пуска генератора 1 на вход эленоё число из числовой последователь- 15 меНта И 19, вход установки тригности 0,1,,. ., Пусть также для всех правил подстаиоьок определены М одномерных законов распределения вероятностей Р,- , т.е. вероятность перехода определенного сложения события (последовательность двоичных кодов). С |. за один такт из состояния S. в состояние S;, где

гера 20 и вхЬд злемента И-НЕ 21. . Синхроимпульс на выходе элемента И-НЕ 21 начнет вырабатываться в момент пе- репада импульса на выходе генерато- 20 ра 18 из состояния О в 1. При этом на первом и втором выходах генератора 1 начинают вырабатьтаться синхросигналы со скважностью два..

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

Sj ,S: Eip,1...,2 } : i, j, t 0, 25 pa 1 через демультиплексор 12 инициирует работу генератора 7 псевдослучайных чисел и через элемент ИЛИ 25 осуществляет сдвиг влево информа ции, записанной в регистрах 27 групп

nn

.

Количество распределений лишь в самом общем случае будет равно числу цепочек С, которое равно . Во многих практически важных случаях распределения для некоторых цепочек могут отсутствовать, а для некоторых Ееиочек распределения могут совпадать. Поэтому число М различных распределений удовлетворяет соотношения М 2. При этом количество регистров кода в группе 5 будет соответствоват значению М, т.е. имеем -оптимальные аппаратурные затраты.

Каждому состоянию S; ставится в соответстйие п-разрядное двоичное число (Ь е ), bo - старший разряд числа, из числовой последовательности О, 1..о... .

Блок 9 стековой памяти предназначен для промежуточного хранения двоичных чисел. Блок 9 стековой памяти работает по принципу первым вошел - последним вьппел. Поэтому при записи правила подстановки необходимо учитьюать, что первым из блока 9 стеТаким образом, на вход узла 30 памяти блока 10 поступает двоичное число, которое сформировано со знаковой памяти будет считано двоичное

число bg...Ь„, являющееся последним .gg чением условных вероятностей, опрев записи. деляемых двоичным кодом, выбранным .

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

из блока 9 памяти. Это двоичное чис ло определяет старшие разряды адрес последовательности двоичных кодов.

числа, в счетчик 26 блока 9 записан двоичный код числа 2,

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

Единичный сигнал с прямого выхода триггера 15 поступает через . вход пуска генератора 1 на вход элегера 20 и вхЬд злемента И-НЕ 21. . Синхроимпульс на выходе элемента И-НЕ 21 начнет вырабатываться в момент пе- репада импульса на выходе генерато- ра 18 из состояния О в 1. При этом на первом и втором выходах генератора 1 начинают вырабатьтаться синхросигналы со скважностью два..

Сигнал с первого выхода генератоpa 1 через демультиплексор 12 иниpa 1 через демультиплексор 12 ини

циирует работу генератора 7 псевдослучайных чисел и через элемент ИЛИ 25 осуществляет сдвиг влево информации, записанной в регистрах 27 группь1,р

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

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

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

числом, считываемым из блока 9 стековой памяти).

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

7

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

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

Режим первый - на первом и вто- ром выходах узла 30 памяти соответственно О и 1, которые поступают на соответствующие управляющие входы V иУ регистров 27 группы. Таким образом,регистры 27 группы устанавливаются в режим сдвига информации вправо,

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

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

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

Сигнал с первого входа генератора 1 поступает через демультиплексор 12 на вход элемента И 28 и разрешаемый уровнем 1 на его первом входе поступает на счетный вход (1) счетчика 29. На выходах счетчика 29 у5танав- ливается увеличенный на единицу код,

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

0

; 5

0 .

5 0

0 5 ; i

5

0

5

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

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

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

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

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

Режим третий: окончание считывания правила подстановки из блока 10 - 1 на первом выходе и О на втором выходе блока 10, который поступает соответственно на управляющие входы V, и Vj регистров 27 сдвига группы

(регистры 27 группы готовы к сдвигу информации влево), Уровень О с второго выхода блока 10 переключает информационные входы демультиплексоров 12 и 13 на их первые выходы.

. Синхроимпульс с второго выхода тактового генератора 1 через демуль- типлексоры 13 и 14 поступает на вход установки в О R счетчика 29, обнуляя его. . . Очередной импульс с первого выхода тайтового генератора 1 через де- мультшшексор 12 инициирует работу генератора 7 псевдослучайных чисел

и через элемент ИЛИ 25 осуществляет сдвиг влево информации,записанной в регистрах 27 сдвига группы, тем самым считывая верхнее двоичное число из блока 9 стековой памяти. Это двоичное число поступает на управляющие входы мультиплексора 8 и переключает соответствующую группу информационных входов на выходы. Псевдослучай ные числа, формируемые в любых К разрядах генератора 7 псевдослучайных чисел, подаются на один из входов К- разрядного сумматора 6, На другой вход сумматора 6 подается постоянное число, задаваемое одним из регистров 5 кода группы. Данньй двухфазный мно горежимНый процесс продолжается до ;тех пор, пока из регистров 27 сдвига группы не будет считано последнее двоичное число. При этом счетчик 26 обнулится и при подаче тактирующего импульса на второй вход (-I) счетчика 26 на выходе заема сформируется импульс. Этот импульс переключит вы- ход триггера 15 в состояние О, который запрещает прохождение импульсов через элемент И 19 генератора 1. Таким образом, на выходе устройства формируются последовательности событий - функционально полная тесто вая программа, в соответствии с законом распределения условных вероятностей, причем последовательности событий .могут иметь различную длину. Конечность генерируемых последовательностей определяется количеством двоичных чисел, записываемых во время работы устройства в блок 9 памяти.

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

Устройство для формирования тестов, содержащее блок-памяти, генератор псевдослучайных чисел, генера- тор тактовых импульсов, мультиплексор, блок дешифрации и триггер пуска, отличающееся тем, что, с целью расширения области применения путем обеспечения возможности синтеза тестов для дискретных объектов типа микропроцессор, уст: ройство содержит два коммутатора, блок стековой памяти, группу суммато; ров по модулю два и группу регистров причем выходы регистров группы соединены с информационными входами мультиплексора, управляющий вход которого соединен с первым выходом бло

g 0 5 о

0

5

0

5

ка стековой памяти, второй выход которого соединен с входом сброса триггера пуска, вход установки которого соединен с входом пуска устройства, выход триггера пуска соединен с входом пуска генератора тактовых импульсов, первый и второй выходы которого соединены с первым и вторым управлякь ющими входами первого коммутатора соответственно, первый информационный вход которого соединен с первым выходом блока памяти и с входом разрешения блока стековой памяти, первый выход коммутатора соединен с синхро- входами генератора псевдослучайной последовательности и блока стековой памяти,вход сброса которого соединен с входом сброса устройства,к входу начат льных условий которого подключена первая группа информационньгх входов блока стековой памяти, выходы мультиплексора соединены с первыми входами соответствующих сумматоров по модулю два группы, вторые входы которых соединены с выходами генераторов псевдослучайных чисел, выход первого сумматора по модулю два группы соединен с входом разрешения записи блока памяти и с входом синхронизации первого коммутатора, выходы которого соедине- ны с адресными входами блока памяти, вход синхронизации которого соединен с первьп- выходом второго коммутатора, второй выход которого соединен с входом синхронизации бло ка стековой памяти, вход записи которого соединен с третьим выходом второго коммутатора, первая и вторая группы выходов блока памяти соединены с группой информационных входов блока дешифрации и с второй группой информационных входов блока стековой памяти соответственно, вход синхронизации блока дешифрации соединен с четвертым выходом второго коммутатора выходы сумматоров по модулю два группы с второго по (п+1)-й (где п - длина тестовой последовательности) соединены с информационными входами перзвого коммутатора, выходы блока дешифрации являются выходгши устройства, вторая группа информационных входов блока стековой памяти соединена с третьей группой выходов блока памяти и с группой информаци- онных входов второго коммутатора,четвертый выход которого соединен с входом блокировки блока стековой памяти.

OmiS

Фиг. 5

ffrnS,

Вт 12

На в

3Q

j;

: «ап

На ЗЛ13 ,l2

Фиг.$

fw

(7m/ 0m 9

OmW

35

Hal

36

Has

9и.г. 7

Фиг. 8