Генераторы случайных и псевдослучайных последовательностей на цифровых элементах задержки (основы теории и методы построения) (16.01.2012)

Автор: Кузнецов Валерий Михайлович

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

Технически для формирования (М–1)- и (М–3)-последовательностей в схемах генераторов Фибоначчи и Галуа вместо СМ2 с константой 1 на входе можно использовать инверсные выходы разрядов регистра.

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

). По запрещенному моноциклу однозначно идентифицируются формируемые прямые или инверсные ЛРП.

. По запрещенному бициклу, решив систему линейных уравнений, идентифицируются все формируемые ЛРП.

. Идентификация всех ЛРП производится по запрещенному тетрациклу путем решения системы линейных уравнений.

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

Предметом исследования четвертой главы являются свойства элементов задержки, которые являются основными и, в ряде случаев, единственными компонентами генераторов. Наибольшей сложностью в описании характеризуются непрерывные задержки как параметры аппаратно реализуемых асинхронных элементов задержки (АЭЗ), определяющих поведение генераторов в целом. Функции АЭЗ в цифровых устройствах целесообразно возложить на стандартные ЦЭ, выполняющие функции логических элементов. Используя декомпозицию ЦЭ в виде идеального логического элемента и одновходового АЭЗ, основное внимание в работе уделено логическим повторителям и инверторам.

. Для цепочек из n повторителей или n инверторов суммарные задержки определятся соответственно как

согласно следующей зависимости соответственно для n-го повторителя или n-го инвертора:

– о неограниченном расширении. Изменение (деградация) входной длительности в цепочке инверторов происходит только при нечетных значениях n, и выражена она значительно слабее, чем для повторителей.

– n-крат-

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

Определены минимально возможные длительности входных импульсов уровня 1 и 0 (как фильтрующие способности АЭЗ) при n-кратном действии инерциальных задержек повторителей на грани исчезновения в виде

, следовательно, фильтрующая способность импульса 1 ограничена, а относительно 0 – нет.

и наоборот.

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

Это обстоятельство при синтезе АЭЗ определяет предпочтительность использования в качестве ЦЭ инверторов, способствующих обеспечению стационарности работы генераторов.

Существенным фактором, влияющим на характер функционирования асинхронного генератора, является стохастичность задержек ЦЭ, образующих АЭЗ. Этот фактор рассмотрен с двух позиций. Во-первых, случайность временных параметров любых реальных элементов проявляется в их нерегулярном разбросе от экземпляра к экземпляру (по ансамблю) в силу технологических причин. Во-вторых, внутренние шумы стандартных ЦЭ, линий и трактов связи приводят к временному непостоянству самих временных параметров, что обозначается понятием «флуктуации».

. Подобные оценки относительно одного корпуса микросхемы составляют 3–5%, а относительно входов однотипных элементов – доли и единицы процентов. Следовательно, в ряде инженерных приложений применительно к однотипным ЦЭ в пределах одного кристалла микросхемы можно принять гипотезу о равенстве средних задержек.

Экспериментально исследованы зависимости средних задержек от напряжения питания и температуры корпуса микросхемы. Результаты экспериментальных измерений хорошо согласуются с известными данными.

. Существенная зависимость от напряжения питания и температуры не обнаружена.

Пятая глава посвящена генераторам асинхронных случайных процессов (ГАСП). Дано описание и приведены типичные схемотехнические представления генераторов. Рассмотрены случаи соизмеримых и несоизмеримых временных задержек АЭЗ как при отсутствии флуктуаций, так и в предположении наличия их. Определены условия генерации процесса, исследованы его вероятностные и корреляционные свойства.

. Его функционирование происходит в непрерывном времени t.

Аппаратные реализации ГАСП представляют собой в общем случае асинхронные устройства с многоконтурной обратной связью. Структурное подобие линейных схем с ГПСП позволяет оставить их обозначения как «генератор Фибоначчи» и «генератор Галуа». Наибольший практический интерес представляет вторая схема (рис. 7), содержащая ЦЭ в виде сумматоров по модулю два (СМ2) с задержками.

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

Рассмотрен ряд идеализированных случаев работы ГАСП.

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

. Многоконтурная система обратных связей порождает сложный апериодический процесс рециркуляции начального заполнения АЭЗ, состоящий из двух подпроцессов: регенерации и аннигиляции.

-образного импульса 1 на фоне сплошного уровня 0. Результатом такой работы модели является точечный процесс с непрерывным временем.

при отсутствии фильтрующих свойств АЭЗ.

) при несоизмеримых задержках. Определяя количество траекторий рециркуляции и вычисляя соответствующие временные моменты по формулам

нетрудно сформировать введенный в работе n-мерный куб Тартальи. Производя «раскраску» куба на четные и нечетные элементы, получаем удобный в вычислительном отношении алгоритм для машинного моделирования многомерных ГАСП.

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

флуктуаций и несоизмеримости задержек. Непрерывные во времени параметры АЭЗ за счет флуктуаций порождают эффект состязания задержек, что характерно для асинхронных автоматов.

в случае единичных задержек (б) и состязаний задержек (в)

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

– множества действительных и действительных неотрицательных величин).

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

с конечной погрешностью.


загрузка...