Введение
1 Исследование процесса упорядочения в информационно-управляющих системах 14
1.1 Условия функционирования устройств упорядочения 14
1.2 Характеристики входных информационных потоков 15
1.3 Классификация алгоритмов выполнения функции упорядочения 17
1.4 Обоснование способа реализации устройств упорядочения 18
1.5 Постановка задачи 23
2 Математические модели устройств упорядочения .25
2.1 Основные понятия и определения 25
2.2 Способы упорядочения 29
2.3 Функция упорядочения 32
2.4 Математическая модель признаковых базовых устройств упорядочения 38
2.4.1 Функция упорядочения F 38
2.4.1.1 Устройства упорядочения типа «переменная-переменная» 39
2.4.1.2 Устройства упорядочения типа «переменная-группа» 42
2.4.2 Функция упорядочения F п 43
2.4.2.1 Устройства упорядочения признакового типа «переменная-переменная» 43
2.4.3 Функция упорядочения FA 45
2.4.4 Функция упорядочения FAn 45
2.5 Математическая модель позиционных базовых устройств упорядочения 46
2.5.1 Матричная модель 46
2.5.2 Основные термины и определения 48
2.5.3 Операции над матрицей 49
2.5.3.1 Определение вектора занятости z матрицы Мдля функций упорядочения F, F* 49
2.5.3.2 Определение вектора занятости z матрицы Мдля функций упорядочения F*n 50
2.5.3.3 Сравнение столбцов Xj и Xj 50
2.5.3.4 Определение вектора занятости z матрицы Мдля функций упорядочения F я 51
2.5.3.5 Попарное «исключающее ИЛИ» соседних элементов вектора m с записью результата ву+1 элемент 51
2.5.3.6 Попарное «исключающее ИЛИ» соседних элементов вектора m с записью результата ву-1 элемент 52
2.5.3.7 Определение неординарности столбца m матрицы М 52
2.5.3.8 Определение вектора неординарности к матрицы М 55
2.5.3.9 Сдвиг столбцов матрицы М, соответствующих нулевым элементам вектора z, влево 56
2.5.3.10 Сдвиг столбцов матрицы М, соответствующих нулевым элементам вектора z, вправо 56
2.5.3.11 Сдвиг столбцов матрицы М, соответствующих ненулевым элементам вектора z, влево 57
2.5.3.12 Сдвиг столбцов матрицы М, соответствующих ненулевым элементам вектора z, вправо 57
2.5.3.13 Сдвиг всех столбцов матрицы Мвправо 57
2.5.3.14 Замена столбца матрицы М 58
2.5.3.15 Определение вектора занятости g столбца m 59
2.5.3.16 Замена элемента столбца а 59
2.5.3.17 Формирование ординарного столбца те 60
2.5.3.18 Формирование остаточного столбца тост 61
2.5.3.19 Разложение столбца m 61
2.5.4 Условия логической схемы алгоритма 61
2.5.5 Модели позиционных базовых устройств упорядочения 62
2.5.5.1 Функции упорядочения F, F 62
2.5.5.2 Функция упорядочения Fп 63
2.5.5.3 Функция упорядочения F п 65
2.5.5.4 Функция упорядочения FA 66
2.5.5.5 Функция упорядочения FAn 68
2.6 Основные результаты 68
3 Структурный синтез устройств упорядочения 70
3.1 Выбор архитектуры базовых устройств упорядочения 70
3.2 Структурный синтез признаковых базовых устройств упорядочения 71
3.2.1 Методика синтеза 71
3.2.2 Синтез признаковых базовых устройств упорядочения 76
3.2.2.1 Функция упорядочения F* 76
3.2.2.1.1 Базовые устройства упорядочения типа «переменная-переменная»76
3.2.2.1.2 Базовые устройства упорядочения типа «переменная-группа» 77
3.2.2.2 Функция упорядочения F*n 77
3.2.2.3 Функция упорядочения FA. Синтез базовых устройств упорядочения типа «переменная-переменная» 79
3.2.2.4 Функция упорядочения FAn 80
3.3 Структурный синтез позиционных базовых устройств упорядочения 81
3.3.1 Методика синтеза 81
3.3.1.1 Абстрактный синтез 82
3.3.1.2 Структурный синтез 84
3.3.2 Синтез позиционных БУУ 88
3.3.2.1 Функции упорядочения F, F* 88
3.3.2.1.1 Абстрактный синтез 88
3.3.2.1.2 Структурный синтез 89
3.2.2.2 Функция упорядочения Fп 91
3.3.2.2.1 Абстрактный синтез 91
3.3.2.2.2 Структурный синтез 92
3.2.2.3 Функция упорядочения F*n 94
3.3.2.3.1 Абстрактный синтез 95
3.3.2.3.2 Структурный синтез 96
3.2.2.4 Функция упорядочения F*n 98
3.3.2.4 Функция упорядочения FA 99
3.3.2.4.1 Абстрактный синтез 99
3.3.2.4.2 Структурный синтез 101
3.4 Структурный синтез комбинированных базовых устройств упорядочения 106
3.5 Организация взаимодействия устройства упорядочения с несколькими обслуживающими приборами 106
3.6 Основные результаты 107
4 Сравнительный анализ типовых структур базовых устройств упорядочения и исследование разработанных устройств упорядочения на моделях и макетах 108
4.1 Сравнительный анализ структур по основным показателям 108
4.1.1 Количество функциональных элементов 108
4.1.2 Количество элементов памяти, необходимых для задания приоритета 109
4.1.3 Количество мест в очереди 110
4.1.4 Механизм смены приоритетов 111
4.1.5. Быстродействие 113
4.1.6. Обработка неординарного информационного потока 114
4.1.7. Технологичность производства 115
4.1.8 Обобщенный сравнительный анализ 116
4.2 Исследование свойств устройств упорядочения на моделях 119
4.2.1 Цель моделирования 119
4.2.2 Методика моделирования 119
4.2.3 Средства моделирования 120
4.2.4 Исходные данные для моделирования 121
4.2.5 Результаты моделирования 121
4.3 Экспериментальное исследование устройств упорядочения на макетах 125
4.3.1 Цель исследования 125
4.3.2 Методика исследования 126
4.3.3 Исходные данные 126
4.3.4 Результаты исследования 126
4.4 Основные результаты 128
Заключение 132
Список литературы 134
Приложения 141
