Проектирование генераторов псевдослучайных тестов icon

Проектирование генераторов псевдослучайных тестов




Скачати 104.67 Kb.
НазваПроектирование генераторов псевдослучайных тестов
Дата01.07.2012
Розмір104.67 Kb.
ТипЛекция
1. /lec1 Надежность вычислительных устройств.doc
2. /lec10 Подходы построения производственных тестов комбинационных схем.doc
3. /lec11 Случайное тестирование ВУ.doc
4. /lec12 Проектирование генераторов псевдослучайных тестов.doc
5. /lec13 Элементы вероятностной логики.doc
6. /lec14 Показатели неисправности при случайном тестировании.doc
7. /lec15 Построение зависимости длины случайного теста от вероятности обнаружения неисправностей.doc
8. /lec16 Оптимизация случайного теста ВУ.doc
9. /lec2 Дефекты элементов вычислительной техники.doc
10. /lec3 Структурные методы синтеза тестов комбинационных схем.doc
11. /lec4 Показатели тестируемости неисправностей.doc
12. /lec5 Булева производная и ее применение для вычисления наблюдаемости.doc
13. /lec6 Наблюдаемость и активизация путей схемы.doc
14. /lec7 Эквивалентность доминирование и совмещение КН.doc
15. /lec8 Синтез тестов КН комбинационных схем по методу булевой производной.doc
16. /lec9 Машинно-ориентированный синтез тестов комбинационных схем по D-алгоритму.doc
Лекция 1 надежность вычислительных устройств двумя важнейшими техническими категориями изделия вообще и вычислительного устройства, в частности, являются качество и надежность. Качеств о
Комбинационных схем
Тестирование ву на случайных тестовых воздействиях называется случайным
Проектирование генераторов псевдослучайных тестов
Аксиомы теории вероятностей
Лекция 15 построение зависимости длины случайного теста
Дефекты элементов вычислительной техники
Структурные методы синтеза тестов комбинационных схем
Лекция 4 показатели тестируемости неисправностей
Лекция 5 Булева производная и ее применение для вычисления наблюдаемости Определение бпx
Лекция 6 Hаблюдаемость и активизация путей схемы Наблюдаемость кт теснейшим образом связана с понятием схемного пути. Схемный путь
Синтез тестов кн комбинационных схем по методу булевой производной
Машинно-ориентированный синтез тестов

Л е к ц и я 12


ПРОЕКТИРОВАНИЕ ГЕНЕРАТОРОВ ПСЕВДОСЛУЧАЙНЫХ ТЕСТОВ


Построение на практике генератора случайной последовательности сопряжено с большими проблемами, среди которых прежде всего нужно выделить следующие:


  • сложность создания источника случайных сигналов;

  • большие аппаратурные затраты многоканального генератора.


Поэтому на практике применяют не случайные, а псевдослучайные последовательности.

К настоящему времени проектирование генераторов псевдослучайных последовательностей (ГПСТ) не представляет затруднений.

Наиболее просто строится "линейный" ГПСТ.

Линейный ГПСТ и его свойства



Под линейным ГПСТ подразумевается генератор, который обеспечивает вероятность следования сигналов "0" и "1", близкую к 0.5.

Среди таких генераторов на практике нашли генераторы на базе р е г и с т р а с д в и г а с л и н е й н ы м и о б р а т н ы м и с в я з я м и ( РСЛОС ).

РСЛОС, в свою очередь, - это разновидность л и н е й н о й п о с л е д о в а т е л ь н о с т н о й м а ш и н ы ( ЛПМ ) без входов - а в т о н о м н о й Л П М.

ЛПМ строится как композиция следующих элементов:


- проводник: ──────────── ;

╔═════╗

- элемент задержки - производит задержку сигнала ║ D ║

на один такт. Для построения этого элемента >─╢ ╟─>─ ;

может использоваться триггер, например , D-типа: ║ 1 ║

╚═════╝


^

- усилитель с коэффициентом усиления gj - произво- ┌──┴──┐

дит усиление сигнала в gj раз, где gj может при- │ gj │ ;

нимать два значения: 0 или 1. Если gj=1, то вход └──┬──┘

усилителя связывается с выходом проводником, gj=0 ^

обозначает разрыв входа с выходом:


- сумматор по "модулю 2" - производит суммирова- ┌─────┐

ние входных сигналов и результат выставляет на ─>─┤ + ├─>─ .

выходе : └──┬──┘

^


Для построения ГПСТ обычно применяют две эквивалентные модификации автономных ЛПМ, которые получили названия " Р С Л О С с в н е ш н и м и с у м м а т о р а м и о б р а т н ы х с в я з е й " и " Р С Л О С с в н у т р е н н и м и с у м м а т о р а м и о б р а т н ы х с в я з е й ". Структуры указанных модификаций РСЛОС представлены на рис. .

╔═════╗ ╔═════╗ ╔═════╗

║ D ║ ║ D ║ ║ D ║

┌─>─╢ ╟─>─┬─>─╢ ╟──>─┬── ... ─>─╢ ╟─>───┐

│ ║ 1 ║ │ ║ 2 ║ │ ║ n ║ │

│ ╚═════╝ │ ╚═════╝ │ ╚═════╝ │

│ Y1 ─<──┤ Y2 ─<───┤ Yn ─<───┤

┌──┴──┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐

│ g0 │ │ g1 │ │ g2 │ │ gn │

└──┬──┘ └──┬──┘ └──┬──┘ └──┬──┘

^ v v │

│ ┌──┴──┐ ┌──┴──┐ │

└──────────┤ + ├─<──────┤ + ├─<─────────────────┘

└─────┘ └─────┘


Рис. РСЛОС с внешними сумматорами обратных связей ( РСЛОСext ).


╔═════╗ ╔═════╗ ╔═════╗

║ D ║ ┌─────┐ ║ D ║ ┌─────┐ ║ D ║

┌─>─╢ ╟─>─┬─>─┤ + ├─>─╢ ╟─>─┬─>─┤ + ├─>─ ... ─╢ ╟─>─┬──>─┐

│ ║ 1 ║ │ └──┬──┘ ║ 2 ║ │ └──┬──┘ ║ n ║ │ │

│ ╚═════╝ │ ^ ╚═════╝ │ ^ ╚═════╝ │ │

┌──┴──┐ Y1 ─<──┘ ┌──┴──┐ Y2 ─<──┘ ┌──┴──┐ Yn ─<──┘ ┌──┴──┐

│ g0 │ │ g1 │ │ g2 │ │ gn │

└──┬──┘ └──┬──┘ └──┬──┘ └──┬──┘

^ ^ ^ v

└────────────────────┴───────────────────────┴───────────────────────────┘


Рис. РСЛОС с внутренними сумматорами обратных связей ( РСЛОСint ).


На качество функционирования РСЛОСА важнейшее влияние оказывает вид ОС, которая задается путем подбора коэффициентов gj, j = 0,1,...,n. Ее можно описать так называемым многочленом обратной связи (МОС), который имеет следующий вид:





где X - фиктивная переменная многочлена;

"+" - операция "сумма по модулю 2".


Доказано , что если в качестве G(X) выступает примитивный, а значит и неприводимый, многочлен, то на выходах РСЛОС генерируется периодическая последовательность с максимальным для разрядности n периодом следования сигналов, равным L = 2n - 1. Такие последовательности называются последовательностями максимальной длины или М-последовательностями. Рассмотрим с в о й с т в а М -п о с л е д о в а т е л ь н о с т е й :


1. С в о й с т в а п е р и о д а - период М-последовательности, т.е. число элементов, через которые элементы повторяются, равна n

L = 2n - 1 .


2. С в о й с т в о к о м б и н а ц и й - М-последовательность содержит все n-значные комбинации двоичных сигналов, кроме нулевой.


3. С в о й с т в о е д и н и ц и н у л е й - число нулевых (n0) и единичных (n1) символов М-последовательности соответственно равно :


n0 = 2n-1 - 1 ; n1 = 2n-1 .


4. С в о й с т в о с е р и й - в периоде М-последовательности из общего числа 2n-1 серий 2n-2 содержат один символ ( 0 или 1 ), 2n-3 - 2 символа, 2n-4 - 3 символа и т.д., пока 2n-a не станет равным 1.


5. С в о й с т в о с д в и г а и с л о ж е н и я - сумма по "модулю 2" М-последовательности с той же самой последовательностью, что и исходная, но сдвинутая относительно первой на некоторое число t (любое число, не равное периоду) элементов, является также М-последовательностью, того же вида, что и исходная, но

сдвинутая относительно нее на некоторое число элементов t` ( t` ? t ).


6. С в о й с т в о в е р о я т н о с т е й - вероятность появления единичных и нулевых символов М-последовательностей близко к 0.5 :








где .


Так как уже при небольших значениях n d практически равно 0, то


Р( Y(t)=0 ч Р( Y(t)=1 ) ч 0.5 .


7. С в о й с т в о к о р р е л я ц и и - корреляция (зависимость) элементов различных М-последовательностей Mi и Mj, а также автокорреляция элементов одной М-последовательности Мi, сдвинутых друг относительно друга на t элементов, описываются коэффициентами корреляции и автокорреляции Кij(t), Кai(t) соответственно, численные значения которых обратно пропорциональны периоду М-последовательности :





Так как уже при небольших n коэффициенты корреляции и автокорреляции практически равны 0, появление элементов различных М-последовательностей и элементов внутри одной М-последовательности можно считать событиями практически взаимонезависимыми.


Анализ свойств М-последовательности показывает, что они наилучшим образом среди всевозможных последовательностей равной длины приближаются по вероятностным характеристикам к идеальной СП.


Описанные свойства РСЛОС позволяют считать их хорошими ГПСТ.

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

Недостатком описанных ГПСТ, построенных на основе РСЛОС, является то , что они способны генерировать ПСП только фиксированной вероятности следования сигналов - 0.5. Такие последовательности находят большое применение, однако там, где нужны ПСП с вероятностью отличной от 0.5, например, при желании минимизировать длину теста, нужны соответствующие ГПСТ. Построению таких генераторов посвящается следующий подраздел.


ГПСТ с произвольной вероятностью сигналов



Различают две основные структуры ГПСТ с произвольной вероятностью сигналов:


  • ГПСТ с сосредоточенным РСЛОС ;

  • ГПСТ с распределенными РСЛОС .


Cтруктуры указанных генераторов приведены на рисунке:


1) ГПСТ со сосредоточенным РСЛОС

┌─────────┐

│ РСЛОС │

└────╥───n┘

n 2) ГПСТ с распределенными РСЛОС



┌──────────────╨──────────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐

│ Р М П │ │ РСЛОС1 │ │ РСЛОСj │ │ РСЛОСm │

└──╥───────────╥───────────╥──┘ └────╥──n1┘ └────╥──nj┘ └────╥──nm┘

║ ║ ║ ║ ║ ║

l1 lj lm l1 lj lm

┌──╨──┐ ┌──╨──┐ ┌──╨──┐ ┌──╨──┐ ┌──╨──┐ ┌──╨──┐

│ ПВ1 │ ... │ ПВj │ ... │ ПВm │ │ ПВ1 │ ... │ ПВj │ ... │ ПВm │

└──┬──┘ └──┬──┘ └──┬──┘ └──┬──┘ └──┬──┘ └──┬──┘

v v v v v v

Р1 Рj Рm Р1 Рj Рm


ГПСТ включают следующие компоненты:


  • РСЛОС (РСЛОСj) разрядностью n (nj) - выступает в качестве источника п (nj) М-последовательностей;

  • расширитель М-последовательностей (РМП) - предназначен для увеличения М-последовательностей ;

  • преобразователь вероятностей (ПВ) - преобразует ПСП вероятностью 0.5 в ПСП требуемой вероятности.


Расширитель М-последовательностей имеет следующую структуру


n М-последовательностей от РСЛОС


│ │ │

│ │ │

│ ┌─────┐ │ ┌─────┐ │

... <─├─>┤ + ├<─├─>┤ + ├<─├─> ...

│ └──┬──┘ │ └──┬──┘ │

│ │ │ │ │

v v v v v


M-последовательностей


В качестве преобразователей вероятностей может выступать преобразователь на базе дешифратора, ЗУ ( ОЗУ либо ПЗУ ) либо схемы сравнения (СхСр). Структуры таких преобразователей показаны на рисунке:


1) ПВ на базе 2) ПВ на базе ОЗУ 3) ПВ на базе

дешифратора cхемы сравнения


l М - п о с л е д о в а т е л ь н о с т е й о т Р С Л О С


(адрес ЗУ)

║ ║ ║

A A константа g-1 А

┌───────╨───────┐ ┌─────╨───────┐ ║ ║

│ D C │ │ З У │ l ║

└─┬─────┬─────┬─┘ │ (ОЗУ, ПЗУ) │ ┌──╨──────────╨────┐

1│ ... │g ...│ n │ l │ │ = = │

┌─┴─────┴──┐ │2 │ 2 x 1 │ │ СхСр │

│ 1 │ v │ 11...10...0 ├─┐ └────────┬─────────┘

└────┬─────┘ └────────────l┘ │ │

│ 12 g 2 │ │

Y v Y v Y v


Сигналы на выходе преобразователей описываются следующей закономерностью: если l-разрядный код, поступающий от РСЛОС либо от РМП на вход ПВ, меньше либо равен g, то выход Y устанавливается равным 1 ; в противном случае - Y=0:


1, если [A] ? g;

Y =

0, если [A] > g,

Вероятность сигнала лог."1" при этом для всех типов преобразователей определяется по одной формуле:


Рy = g 2-1 . ( * )


Расчет параметров ГПСТ



Расчет ГПСТ сводится к расчету разрядности РСЛОС - n (nj, j=1,m ), а также параметров ПВ - l и g ; в качестве исходных данных при расчете выступают требуемые вероятности сигналов : Р1,..., Рm и соответствующие им погрешности вероятностей - E1,... , Em, а также допустимый коэффициент корреляции и автокорреляции - Кдоп.


На первом этапе рассчитываются параметры l и g.


Параметры l и g рассчитываются совместно, так как они одновременно влияют на вероятность выходных сигналов. Действительно, вероятность сигнала лог."1" на выходе ПВ с параметрами l и g определяется по формуле ( * ). Эта вероятность не должна отклоняться по абсолютной величине от требуемого значения Р не более, чем допустимая погрешность - Е, поэтому должно выполняться неравенство:


| Р - g 2-1 | ? Е .


Разделим Р на 2-1 - получим частное g` и остаток - r- , который мы назовем "отрицательным остатком":


Р = 2-1 g` + r- .


Если в приведенное соотношение вместо g` подставить g`+1, то правая ее часть будет превышать левую на величину r+ , которую мы условно назовем "положительным остатком" :


r+ = 2-1 ( g` + 1 ) - P .


Параметры l и g=g` либо g=g`+1 можно считать удовлетворительными, если выполняется одно из соответствующих неравенств:


r- ? E

или

r+ ? E .


Отсюда следует алгоритм расчета параметров ПВ, который мы условно называем алгоритмом "LG".


Алгоритм "LG"

(расчет параметров l,g)

*****************************************************************


1. Выбирается первое значение l.

2. Выполняется деление выходной вероятности P на 2-1 - в результате получается частное - g` и остаток r-.

3. Если r- ? E , то g = g` и выполняется переход на п.7.

4. Вычисляется r+ по формуле


r+ = ( g` + 1 ) 2-1 - P .


5. Если r+ ? E , то g = g`+1 и и выполняется переход на п.7.

6. Выбирается следующее значение l и производится переход на п.2.

7. Конец.


Значения параметра l могут выбираться путем последовательного наращивания (инкрeментирования) значений, начиная с 1: l = 1,2,3,... Для более быстрой реализации алгоритма рекомендуется использовать метод половинного деления. В последнем случае в качестве первого значения l рекомендуется выбирать 10.


П р и м е р. Рассчитать преобразователь вероятности ГПСТ, вырабатывающий псевдослучайную последовательность с вероятностью Р = 0.7 и погрешностью Е = 0.01.


Процесс решения отразим следующей последовательностью шагов алгоритма "LG" ( l выбираем путем инкрементирования ):


шаг 1 2 3 4 5 6 7

l 1 2 3 4 5 6 7

g` 1 2 5 11 22 44 -

r- .2 .2 .075 .013 .013 .013 -

r+ .3 .5 .05 .05 .019 .003


На 6-ом шаге получаем r+ = 0.003, что меньше заданной погрешности E = 0.01, поэтому вычисления прекращаем. В соответствии с алгоритмом выбираем второй параметр ПВ: g = g`+ 1


При расчете разрядности РСЛОС в качестве исходных выступают следующие данные:


m - число каналов (преобразователей вероятности) ГПСТ;

{ lj , gj } - параметры преобразователей вероятностей ГПСТ;

Кдоп - допустимый коэффициент корреляции и автокорреляции

выходных последовательностей ГПСТ .


Разрядность РСЛОС должно удовлетворять трем требованиям:


1) обеспечивать перебор всех n-значных комбинаций двоичных сигналов на входах всех ПВ;

2) корреляция и автокорреляция генерируемых ПСП не должна превышать допустимые граничные значения;

3) обеспечивать требуемое число вырабатываемых М-последовательностей.


Первое требование удовлетворяется, если n строго больше параметра l любого ПВ:


n > lj для всех j = 1, 2, ... , m .


Второе условие требует, чтобы генерируемые ПСП имели коэффициенты корреляции К, не превышающие Кдоп. Так как известно из свойства -1 -n "корреляции" М-последовательностей, что | К |= L , где L = 2 -1 - период М-последовательности, то сформулированное требование сводится к выполнению неравенства:


2-n -1 <= Кдоп .


Выражая это неравенство относительно n получаем





Наконец разрядность РСЛОС определяет число М-последовательностей, которые он способен генерировать самостоятельно либо совместно с РМП. Поэтому для ГПСТ с распределенным РСЛОС n должно быть не меньше параметра l каждого ПВ:


n ? lj для всех j .


Для ГПСТ со сосредоточенным РСЛОС число М-последовательностей, вырабатываемых РСЛОС совместно с РМП должно быть не меньше, чем их требуют ПВ вместе взятые, т.е. Lc = l1 + l2 +... + lm. В тоже время РСЛОС разрядностью n совместно с РМП могут вырабатывать максимум





М-последовательностей. Поэтому справедливо неравенство





Выражая это неравенство через n получаем


n ? 1.5 ? Lc .


Суммируя полученные результаты получаем требования по разрядности РСЛОС:


а) для ГПСТ с сосредоточенным РСЛОС:



б) для ГПСТ с распределенным РСЛОС:





В о п р о с ы д л я с а м о к о н т р о л я :


1. Чем обусловлена сложность построения генератора случайной тестовой последовательности ?

2. На какой основе строится линейный генератор псевдослучайных тестов (ГПСТ) ?

3. Что такое М-последовательность? Назовите условия ее формирования.

4. Перечислите свойства М-последовательности.

5. Приведите структуры нелинейных ГПСТ, опишите порядок их функционирования.

6. На каком свойстве базируется построение расширителя М-последовательностей ?

7. Какие типы преобразователей вероятностей (ПВ) Вам известны ? Приведите структуры ПВ.

8. Дайте сравнительную характеристику ПВ.

10. Поставьте задачу на расчет параметров ГПСТ.

11. Укажите факторы, определяю щие параметры ГПСТ.

12. Опишите принцип расчета параметров ПВ.

13. Как рассчитывается разрядность регистра сдвига с линейными обратными связями ?

Схожі:

Проектирование генераторов псевдослучайных тестов iconСборник тестов по инженерной графике
Сборник тестов по инженерной графике. Сборник тестовых заданий для самостоятельного контроля знаний студентов 1 курса бакалавров...
Проектирование генераторов псевдослучайных тестов iconДокументи
1. /Организационное проектирование/Навчальна програма.doc
2. /Организационное...

Проектирование генераторов псевдослучайных тестов iconКонтрольная работа по дисциплине "Проектирование и эксплуатация теплотехнических установок" "Проектирование системы энергоснабжения методической нагревательной печи "
Методическая печь нагревает слитки металла для его последующей обработки давлением. Для этого слиток должен иметь достаточно высокую...
Проектирование генераторов псевдослучайных тестов iconКонспект лекций по дисциплине «проектирование электромеханических устройств и систем»
Конспект лекций по дисциплине «Проектирование электромеханических устройств и систем» (для студентов 4 курса дневной формы обучения...
Проектирование генераторов псевдослучайных тестов iconПлазменные технологии в науке и производстве
Одно из научных направлений кафедры прикладной физики вну им. В. Даля – физика и техника низкотемпературной плазмы, в частности,...
Проектирование генераторов псевдослучайных тестов iconДокументи
1. /Кляйн/Кляйн Мелани Зависть и благодарность.pdf
2. /Кляйн/МЕЛАНИ...

Проектирование генераторов псевдослучайных тестов iconДокументи
1. /Кляйн/Кляйн Мелани Зависть и благодарность.pdf
2. /Кляйн/МЕЛАНИ...

Проектирование генераторов псевдослучайных тестов iconДокументи
1. /Кляйн/Кляйн Мелани Зависть и благодарность.pdf
2. /Кляйн/МЕЛАНИ...

Проектирование генераторов псевдослучайных тестов iconДокументи
1. /Кляйн/Кляйн Мелани Зависть и благодарность.pdf
2. /Кляйн/МЕЛАНИ...

Проектирование генераторов псевдослучайных тестов iconДокументи
1. /Кляйн/Кляйн Мелани Зависть и благодарность.pdf
2. /Кляйн/МЕЛАНИ...

Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи