Генератор М-последовательности.

В аппаратурных псевдослучайных датчиках и узлах ЭВМ при генерировании ПСЧП с равномерным распределением наиболее часто используется метод, который заключается в получении линейной двоичной последовательности по рекуррентному выражению:

где i - номер такта; символы выходной последовательности; постоянные коэффициенты. При соответствующем выборе коэффициентов {a_к} генерируемая числовая последовательность имеет максимальную (для данного m) величину периода и называется М-последовательностью. Одним из главных преимуществ метода генерирования ПС – последовательностей максимальной длины является простота его реализации.

Генератор М-последовательности может быть построен двумя методами, отличающимися способом включения сумматоров по модулю два: они могут включаться как в цепь обратной связи генератора, так и в меж разрядные связи элементов памяти регистров сдвига.

Структурная схема генератора М – последовательности, построенного по способу включения сумматоров в цепь обратной связи представлена на рис.1.1

Генератор М-последовательности с сумматорами по модулю два, стоящими в цепи обратной связи: а_i, a_i-1, a_{i-2, …}a_i-m – символы последовательности; a_i – коэффициенты, определяющие вид обратной связи.

 

Алгоритм размножения М-последовательности.

Для того, чтобы обеспечить различные режимы испытаний, генераторы испытуемых сигналов должны удовлетворять ряду требований (многоканальность, быстродействие, достаточная длина периода и т.д.). В основе наиболее перспективного метода построения быстродействующего параллельного генератора псевдослучайных последовательностей испытательных сигналов лежит идея использования ( в качестве независимых последовательностей для формирования разрядов очередного кода) участков одной и той же последовательности. В данном случае генерирование различных участков осуществляется с помощью h-входовых сумматоров по модулю два, т.е. hÎ {2, m}, где m- разрядность регистра сдвига. Соединения сумматоров по модулю два с разрядами регистра сдвига определяются набором коэффициентов d_i(1)Î {0, 1}(i=1, 2, 3,..m), значения которых зависят от величины сдвига l(l=1, 2, 3, …) и вида порождающего полинома.

Методика выбора коэффициентов d_i(1), однозначно определяющих связи многовходового сумматора по модулю два, описывается на итерационном подходе, когда на основании d_i(h), по расчётным соединениям находятся d_i(1)(h=1, 2, ….h< l).

Предположим, что коэффициенты d_i(1) и d_i(S), позволяющие получить сдвинутые копии М-последовательности на 1 и S тактов, известны; тогда содержимое a₁(k+1) первого разряда регистра сдвига в (к+1)-м такте работы определяется следующим образом:

(1.3.1)

где а_i(к) содержимое i-того разряда регистра сдвига в к-м такте его работы, а символ означает операцию суммирования по модулю два. Содержимое первого разряда регистра сдвига в (k+s)-м такте работы имеет вид

(1.3.2)

для определения содержимого первого разряда регистра сдвига в (k+1+s)-м такте, аналогично как и для (1.3.1) и (1.3.2), необходимо предварительно выбрать численное значение коэффициентов . С другой стороны, a₁(k+1+s) можно найти на основании (1.3.1) следующим образом:

где  с учётом (1.3.1) принимает вид

значения вычисляются по формуле

,

где -постоянные коэффициенты, определяемые как:

Окончательно для получаем:

 

Глава2.

Практическая реализация системы обучения методам компактного тестирования.

2.1 Реализация графического интерфейса.

 

Программа написана под операционную систему Windows 95. Так как сама операционная система Windows 95 является графической, то интерфейсы программ написанных под эту систему похожи друг на друга. Вследствие этого обучение работе с данной программой облегчается. Графический интерфейс построен таким образом, чтобы пользователю было, как можно удобнее и понятней работать с программой. Все необходимые команды доступны через главное меню. Главное меню — это специальная панель инструментов, расположенная в верхней части экрана, которая содержит такие меню, как: Файл, Редактировать, Полином, Состояние, Диагностика, Анализ, Стоп. Через эти меню становятся доступны основные функции программы. На главной форме расположены кнопки логических элементов, генераторов, индикаторов.

Интерфейс программы состоит из трёх форм:

1. Главной формы, на которой расположены меню и все элементы необходимые для работы цифровых схем.

2. Форма свойств элементов. Отображает свойства элемента при его выделении.

3. Форма «Конструктор» - на ней строятся цифровые схемы.

2.2 Разработка и реализация алгоритма моделирования цифровых схем.

 

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

 

 

 

 

Результат тестирования

Моделирование сложных логических схем на большом числе входных наборов эффективно можно осуществлять только при помощи ЭВМ. Для того чтобы смоделировать работу устройства на ЭВМ, необходимо описать математическую модель этого устройства.

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

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

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

В программе реализованы все типы логических элементов, вследствие этого можно построить большое количество разнообразных цифровых схем.

Программа была написана при помощи объектно-ориентированного языка Паскаль в среде Delphi 3.

Объектно-ориентированный язык программирования характеризуется тремя основными свойствами:

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

· Наследование - определение объекта и дальнейшее использование всех его свойств для построения иерархии порождённых объектов с возможностью для каждого порождённого объекта, относящегося к иерархии, доступа к коду и данным всех порождающих объектов.

· Полиморфизм - присваивание определённому действию одного имени, которое затем совместно используется по всей иерархии объектов сверху донизу, причём каждый объект иерархии выполняет это действие характерным именно для него способом.

Каждый элемент на схеме, будь это линия, логический элемент, генератор или индикатор - это есть отдельный объект. Иерархия объектов представляется в виде:

BassClass - базовый класс для всех элементов электрической схемы. В нем задаются основные логические характеристики элементов схемы. такие как, выходы элемента - ListOutLine, входы элемента - ListInLines, и методы обработки списка линий. А также абстрактный метод Execute, в котором и описываются все действия для моделирования работы логического элемента.

TPaintLogicElem - этот класс является родительским для всех логических элементов схем. Этот класс занимается прорисовкой, перемещением, установкой параметров элементов.

TAnd - логический элемент " И". В процедуре Execute выполняет логическую функцию типа " И".

TAndNot - логический элемент " И-НЕ". В процедуре Execute выполняет логическую функцию типа " И-НЕ".

TOr - логический элемент " ИЛИ". В процедуре Execute выполняет логическую функцию типа " ИЛИ".

TOrNot - логический элемент " ИЛИ-НЕ". В процедуре Execute выполняет логическую функцию типа " ИЛИ-НЕ".

TNOT - логический элемент " НЕ". В процедуре Execute выполняет логическую функцию типа " НЕ".

TGenerator - генератор счетчиковой последовательности;

TMGenerator - генератор М-последовательности.

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

TLine - объект " Линия" соединяет входные и выходные линии элементов.

TPoint - объект " точка".

2.3 Реализация алгоритма, моделирующая работу генераторов тестовых последовательностей.

Генератор счётчиковой последовательности.

 

На схеме генератор счётчиковой последовательности отображается как:

Генератор М-последовательности

Алгоритмы работы генераторов счётчиковой последовательности описан и М-последовательности описан в [1.3]

2.4 Разработка и реализация модуля моделирующего алгоритм диагностики с использованием компактных методов тестирования.

 

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

 

Сигнатурный анализатор.

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

Для описания процедуры сжатия информации, основанной на применении сигнатурного анализа, используются различные математические модели и алгоритмы. Наиболее широко используются два алгоритма:

1. Метод свёртки, при котором значение эталонной сигнатуры последовательности, формируемой на любой из полюсов ЦС, в частности и на выходном, получается при обработке её символов по отношению 1.1.

2. Алгоритм деления полинома на полином. При этом в качестве делимого используется поток сжимаемой последовательности данных, описываемых полиномом к(х) степени (l, 1 ), где l-количество бит в последовательности. Делителем служит примитивный полином , в результате деления на который получается частное q(x) и остаток S(x), связанные классическим соотношением вида

где остаток S(x) называется сигнатурой.

Наиболее предпочтительным методом синтеза многоканальных сигнатурных анализаторов является метод, позволяющий синтезировать МСА с произвольным количеством входов и не зависящим от него множеством элементов памяти, определяемым только старшей степенью порождающего полинома . Данный метод основывается на применении примитивного полинома , где m=deg  определяет достоверность анализа, а также разрядность формируемых сигнатур.

Для произвольного  функционирование одноканального сигнатурного описывается системой уравнений

(2.1)

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

Из выражения (2.1) следует, что содержимое первого элемента памяти анализатора в (к+1)-й такт его работы определяется как

 

а в (к+2) –й такт

В общем случае для некоторого k+n-1-го такта можно записать

(2.2)

где - коэффициенты, позволяющие формировать сдвинутую на n тактов копию М-последовательности, описываемую полиномом . Значение  определяются как:

Кроме того, численные значения могут быть получены в результате выполнения быстрых формальных процедур.

Коэффициенты определяются следующим образом:

.

Из выражения (2.2) для  можно получить его значение на основании n символов y(k), y(k+1), …y(k+n-1) последовательности {y(k)} и m исходных значений  В тоже время указанное выражение используется для построения функциональной схемы сигнатурного анализатора, который в каждый такт обрабатывает n символов последовательности {y(k)}. При этом подобный анализатор будет иметь n входов, что позволяет применять его для контроля цифровых схем, имеющих n выходов, причём n выходных последовательностей в этом случае преобразуются в одну вида:

(2.3)

где значение двоичного символа на v-ом выходе исследуемой цифровой схемы в к-й такт её работы.

Функционирование анализатора, обрабатывающего последовательность (2.3) в соответствии с (2.1) и (2.2), будет описываться следующей системой уравнений:

(2.4)

Использую систему уравнений (2.4), оказывается возможным построение многоканального анализатора, выполняющего за один такт те же преобразования с последовательностью, что и одноканальный за n тактов.

 

⇐ Предыдущая1234Следующая ⇒

Поделиться: