Організація структурних засобів формування послідовностей псевдовипадкових рівноймовірних двійкових наборів

Анотація

У роботі представлено результати дослідження та розроблення структурних методів апаратної генерації псевдовипадкових рівноймовірних двійкових послідовностей. Проаналізовано особливості існуючих підходів до синтезу генераторів псевдовипадкових наборів і визначено їхні обмеження, пов’язані з фіксованим розподілом імовірностей або жорстко заданою потужністю вихідної множини. Запропоновано новий метод побудови структурних засобів генерації, який ґрунтується на каскадному дихотомічному розкладанні числа можливих комбінацій вихідної послідовності. Такий підхід забезпечує формування повної множини рівноймовірних наборів заданої розрядності при зменшенні апаратних витрат. Розроблено алгоритм побудови генератора, який охоплює етапи формування дерева розкладання, синтезу та мінімізації комбінаційних схем, що реалізують функції парності, а також визначення ймовірностей переходів між вершинами графа розкладання. Опис алгоритму подано у формалізованому вигляді, що спрощує його подальшу реалізацію та аналіз. Показано, що використання запропонованого методу дозволяє визначати ймовірності переходів через прості відношення між компонентами розкладання, що значно спрощує схемотехнічну реалізацію генератора. Запропонована структура формувача забезпечує отримання рівноймовірних псевдовипадкових наборів незалежно від потужності вихідної множини. Доведено, що швидкодія такого генератора визначається не розміром множини N, а її двійковим логарифмом, тобто розрядністю вихідного коду m. Практичну реалізацію методу проілюстровано на прикладі, наведено способи обчислення ймовірностей та побудови функцій парності. Отримані результати можуть бути використані під час проектування високопродуктивних систем тестування цифрових пристроїв, засобів моделювання відмовостійких багатопроцесорних систем і генераторів випадкових даних у цифровій обчислювальній техніці.