Сортировки информации методом дешифрации данных

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

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

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

БС – блок сортировки служит для подсчета одинаковых чисел и символов, определения знакового разряда числа, для записи и хранения упорядоченной информации.

БШД – блок дешифрации данных служит для декодирования входного двоичного кода и однозначного определения номера регистра для записи и хранения информации.

БХР – блок хранения результата служит для записи и хранения в нем результата упорядоченной двоичной информации.

Структурная схема устройства сортировки информации методом дешифрации данных представлена на рисунке 1.

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

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

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

Блоки 3, … , N сортировки выполняют аналогичные функции по упорядочению двоичной информации, имеют одинаковые структурные и принципиальные схемы, как и блок 2 сортировки

Блок дешифрации состоит из каскадной схемы дешифраторов. Функция дешифратора состоит в преобразовании входной двоичной информации в унитарный код на выходе. На выходе дешифратора только один высокий уровень, одна единица. Этот высокий уровень является разрешающим сигналом для записи входной информации в определенный двоичный регистр одного из n. Входным информационным сигналом блока является двоичный код символа или модуля числа. Выходные сигналы блока дешифрации поступают на входы блоков сортировки. Единичный выходной сигнал блока поступает на разрешающий вход для записи информации в один из n регистров блоков сортировки. Двоичный код символа и числа со своим знаковым разрядом будет записана в этот регистр.

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

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

Время, затрачиваемая на упорядочение массива чисел или символов будет состоять из суммы времен: ввода данных с клавиатуры для одного символа n=20 нс, дешифрации данных m=20 нс, записи элементов в регистр блока сортировки z=25 нс, суммирования количества одинаковых элементов массива с помощью двоичных счетчиков не превышает h=135 нс, считывание информации из регистра c=25 нс, цикл записи данных в оперативное запоминающее устройство с выходов всех регистров блоков сортировки составляет w=с*256 нс, цикл считывание данных из оперативного запоминающего устройства равен p=200 нс. Окончательное время сортировки чисел и символов и считывание информации из оперативного запоминающее устройства будет вычисляться по формуле.

где KS это количество символов, поступивших с выхода шифратора.

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

ОБРАЗЕЦ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ

ФЕДЕРАЦИИ

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

УНИВЕРСИТЕТ

Кафедра “Комплексная защита информационных систем”

Специальность 090104 “Комплексная защита объектов информатизации”