УСТРОЙСТВО СОРТИРОВКИ ИНФОРМАЦИИ МЕТОДОМ ДЕШИФРАЦИИ ДАННЫХ Российский патент 2008 года по МПК G06F7/06 

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

Известно "Устройство для сортировки чисел" (а.с. №1304015, 1987 г.), позволяющее упорядочить массив чисел как в возрастающем, так и в убывающем порядке.

Известно "Устройство для сортировки чисел" (а.с. №1277091, 1986 г.), позволяющее упорядочить числа в возрастающем и в убывающем порядке.

Известно "Устройство для реализации упорядочивающих подстановок" (патент №2067315), выполняющее задачу алфавитной сортировки слов.

В качестве прототипа выбрано "Устройство сортировки символов" (патент №2067317), которое позволяет упорядочить информацию по возрастанию и по убыванию.

Задача заключается в следующем:

1) уменьшить аппаратные затраты устройства,

2) упростить алгоритм блока управления,

3) повысить скорость сортировки информации,

4) расширить функциональные возможности устройства сортировки информации,

5) повысить надежность работы устройства сортировки информации.

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

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

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

Задача сортировки потоков информации в вычислительной технике является настолько важной, что ее следует осуществлять только тогда, когда тщательное изучение аппаратных средств и параметров данных оправдывает сортировку [1].

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

Решение задачи осуществляется тем, что устройство сортировки информации методом дешифрации данных, содержащее блоки сортировки, блок управления, отличающийся тем, что дополнительно введены блок ввода данных, блок дешифрации, блок хранения результата, причем информационный выход блока ввода данных соединен с первыми информационными входами всех блоков сортировки и с информационным входом блока дешифрации, на информационном выходе формируются двоичные коды чисел, которые представлены в прямом коде со своими знаковыми разрядами, и символы, представленные в двоичном коде, передача входных двоичных кодов символов и чисел осуществляется в параллельном режиме побайтно, первый управляющий выход блока управления соединен с управляющим входом блока дешифрации, на котором формируется сигнал разрешения работы блока дешифрации, первый управляющий выход блока дешифрации соединен с управляющим входом первого блока сортировки, на котором формируется сигнал разрешения работы первого блока сортировки, второй управляющий выход блока дешифрации соединен с управляющим входом второго блока сортировки, на котором формируется сигнал разрешения работы второго блока сортировки, двести пятьдесят шестой выход блока дешифрации соединен с управляющим входом двести пятьдесят шестого блока сортировки, на котором формируется сигнал разрешения работы двести пятьдесят шестого блока сортировки, первый информационный выход блока управления соединен со вторым информационным входом первого блока сортировки, на котором формируются сигнал выдачи информации, сигнал сдвига информации вправо, сигналы установки режимов работы, сигнал обнуления регистра двоичного кода числа и символа первого блока сортировки, второй информационный выход блока управления соединен со вторым информационным входом второго блока сортировки, на котором формируются сигнал выдачи информации, сигнал сдвига информации вправо, сигналы установки режимов работы, сигнал обнуления регистра двоичного кода числа и символа второго блока сортировки, третий информационный выход блока управления соединен со вторым информационным входом двести пятьдесят шестого блока сортировки, на котором формируются сигнал выдачи информации, сигнал сдвига информации вправо, сигналы установки режимов работы, сигнал обнуления регистра двоичного кода числа и символа двести пятьдесят шестого блока сортировки, информационный выход первого блока сортировки соединен с информационным входом блока хранения результата, на котором формируется двоичный код числа и символа, а также знаковый разряд числа и количество чисел и символов, поступивших на вход регистра двоичного кода числа и символа первого блока сортировки, передача выходных двоичных кодов символов и чисел с информационного выхода первого блока сортировки осуществляется в параллельном режиме побайтно, информационный выход второго блока сортировки соединен с информационным входом блока хранения результата, на котором формируется двоичный код числа и символа, а также знаковый разряд числа и количество чисел и символов, поступивших на вход регистра двоичного кода числа и символа второго блока сортировки, передача выходных двоичных кодов символов и чисел с информационного выхода второго блока сортировки осуществляется в параллельном режиме побайтно, информационный выход двести пятьдесят шестого блока сортировки соединен с информационным входом блока хранения результата, на котором формируется двоичный код числа и символа, а также знаковый разряд числа и количество чисел и символов, поступивших на вход регистра двоичного кода числа и символа двести пятьдесят шестого блока сортировки, передача выходных двоичных кодов символов и чисел с информационного выхода двести пятьдесят шестого блока сортировки осуществляется в параллельном режиме побайтно, с первого по шестой управляющие входы блока хранения результата соединены соответственно со второго по седьмой управляющими выходами блока управления, на которых формируется сигнал установки в нулевое состояние двоичного счетчика, формирующего адреса строк оперативного запоминающего устройства, сигнал обнуление двоичного счетчика, формирующего адреса столбцов оперативного запоминающего устройства, сигнал генератора прямоугольных импульсов для формирования адресов столбцов в двоичном счетчике для записи результата в оперативное запоминающее устройство, сигнал тактовых импульсов для формирования адресов строк в двоичном счетчике для записи результата в оперативное запоминающее устройство, сигнал выбора кристалла для разрешения работы оперативного запоминающего устройства, сигнал выбора режима работы - запись/считывание оперативного запоминающего устройства, первый и второй управляющие входы "СБРОС" и "ПУСК" блока управления являются внешними входами устройства сортировки информации методом дешифрации данных.

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

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

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

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

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

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

На фиг.1 изображена структурная схема устройства сортировки информации методом дешифрации данных.

На фиг.2 представлен вариант технической реализации блока ввода данных.

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

На фиг.4 изображена функциональная схема блока сортировки и блока регистра двоичного кода.

На фиг.5 показана функциональна схема блока дешифрации.

На фиг.6 представлен вариант технической реализации блока хранения результата.

На фиг.7 - содержательная граф-схема алгоритма ГСА работы устройства.

На фиг.8 - размеченная граф-схема алгоритма ГСА работы устройства.

Для описания алгоритма работы блока 7 управления используются следующие идентификаторы.

1. БВД - блок ввода данных.

2. БСi - блоки сортировки.

3. БДШ - блок дешифрации.

4. БХР - блок хранения результата.

5. БУ - блок управления.

6. ЧСД - выходной информационный двоичный сигнал числовых и символьных данных, поступающий из блока ввода данных.

7. УПРi - информационный сигнал из блока управления, состоящий из управляющих сигналов: выдачи, обнуления, сдвига, установки режимов работы регистров: реж1, реж2.

8. СРЗ - управляющий сигнал разрешения работы дешифратора ДШ1 блока дешифрации.

9. УСН - управляющий сигнал установки в нулевое состояние двоичного счетчика Сч2, формирующего адреса строк, оперативного запоминающего устройства блока хранения результата.

10. ОБН - управляющий сигнал установки в нулевое состояние двоичного счетчика Сч1, формирующего адреса столбцов, блока хранения результата.

11. ГИ - генератор прямоугольных импульсов, поступающих на суммирующий вход двоичного счетчика Сч1, формирующего адреса столбцов, блока хранения результата.

12. ТИ - генератор прямоугольных импульсов, поступающих на суммирующий вход двоичного счетчика Сч2, формирующего адреса строк, блока хранения результата.

13. ВК - управляющий сигнал выбора кристалла оперативного запоминающего устройства блока хранения результата.

14. Зп/Сч - управляющий сигнал записи/считывание информации из оперативного запоминающего устройства блока хранения результата.

15. УМД - входной информационный сигнал блока хранения результата.

16. РАЗi - управляющий сигнал из блока дешифрации, разрешающий принимать информацию регистром двоичного кода блоков спортивки.

17. УМi - выходной информационный сигнал блоков сортировки.

18. ДКЧС - выходной информационный сигнал с выхода шифратора блока ввода данных, представляющий собой двоичный код чисел и символов.

19. ЗРЧ - знаковый разряд двоичных чисел, поступающий с выхода шифратора блока ввода данных.

20. ПРИ - генератор прямоугольных импульсов блоков сортировки.

21. БППЧ - блок подсчета положительных чисел.

22. БПОЧ - блок подсчета отрицательных чисел.

23. БРгДК - блок регистра двоичного кода входного числа и символа.

24. КЛПЧ - выходной информационный сигнал двоичного счетчика Сч1 блока подсчета положительных чисел, представляющий собой количество положительных чисел.

25. КЛОЧ - выходной информационный сигнал двоичного счетчика Сч2 блока подсчета отрицательных чисел, представляющий собой количество отрицательных чисел.

26. ЗРПЧ - выходной управляющий сигнал D-триггера Тр1 блока подсчета положительных чисел, представляющий собой знаковый разряд положительных чисел.

27. ЗРОЧ - выходной управляющий сигнал D-триггера Тр2 блока подсчета отрицательных чисел, представляющий собой знаковый разряд отрицательных чисел.

28. ОБЛ - управляющий сигнал обнуления двоичных счетчиков Сч1, Сч2 и D-триггеров Тр1, Тр2, поступающий на входы установки в нулевое состояние элементов блоков подсчета положительных и отрицательных чисел.

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

30. КОЧЗОЧ - выходной информационный сигнал электронных ключей, представляющий собой количество и знаковый разряд отрицательных чисел.

31. ДКВИ - информационный двоичный код выходной информации регистра двоичного кода числа или символа.

32. ДКСЧ - информационный двоичный код выходной информации электронных ключей символа или числа.

33. CPi - входной управляющий сигнал, представляющий стробирующий, разрешающий сигнал работы дешифраторов блока дешифрации.

34. АД СТЛ - адресная шина столбцов оперативного запоминающего устройства блока хранения результата.

35. АД СТР - адресная шина строк оперативного запоминающего устройства блока хранения результата.

36. РУД - выходной информационный сигнал - результат упорядоченных данных оперативного запоминающего устройства блока хранения результата.

37. ЗВД - признак завершения ввода информации с выхода блока ввода данных.

38. ПУСК - внешний управляющий сигнал блока управления, означающий пуск работы устройства сортировки информации.

39. СБРОС - внешний управляющий сигнал блока управления, означающий сброс всех элементов памяти и двоичных счетчиков в нулевое состояние устройства сортировки информации.

Работа алгоритма управления устройства.

Содержательная граф-схема алгоритма управления приведена на фиг.7 и отражает работу блока 7 управления (фиг.1).

Блок 1 алгоритма является начальным боком алгоритма.

В блоке 2 алгоритма выполняется подача сигнала «СБРОС» установки в нулевое состояние на входы всех элементов устройства сортировки.

В блоке 3 алгоритма по команде «ПУСК:=1» происходит установка внешнего сигнала устройства ПУСК в единичное значение.

В блоке 4 алгоритма по команде «ОБН:=1» происходит установка в нулевые значения элементов памяти и двоичных счетчиков устройства.

Блоки 5, 6, 7, 8, 9 и 10 представляют собой цикл, в котором производится определение блока сортировки устройства для записи входной двоичной информации.

В блоке 5 осуществляется анализ признака «ЗВД» - завершения ввода данных. По выходу «Да» осуществляется переход на блок 11 алгоритма. По выходу «Нет» осуществляется переход на блок 6 алгоритма.

В блоке 6 по команде «БС:=ЧСД» на вход блоков сортировки поступают числовые и символьные данные, по команде «БДШ:=ЧСД» на вход блока дешифрации поступают числовые и символьные данные.

Блоки 7, 8, 9 и 10 образуют цикл, в котором определяется регистр блока сортировки и подача на него входного информационного двоичного сигнала.

В блоке 7 происходит изменение переменной счетчика цикла i от начального единичного значения до конечного 256 с шагом+1.

В блоке 8 анализируется признак «PA3i» - разрешение записи входных данных в регистр i-го блока сортировки.

В блоке 9 по команде «БСi:=PA3i» происходит подача управляющего сигнала из блока дешифрации для разрешения записи информации в регистр i-го блока сортировки.

В блоке 10 по команде «БСi:=ЧСД» осуществляется запись в регистр i-го блока сортировки двоичного кода входных числовых и символьных данных.

В блоке 11 анализируется признак сортировки данных по возрастанию - «СОРВОЗ». По выходу «Нет» осуществляется переход на блок 17 алгоритма. По выходу «Да» осуществляется переход на блок 12 алгоритма.

В блоке 12 по команде «БХР:=ЗП» производится подача из блока управления на вход блока хранения результата управляющего сигнала для записи данных в оперативное запоминающее устройство.

В блоке 13 по команде «БХР:=ГИ» происходит подача прямоугольных импульсов на суммирующий вход двоичного счетчика СЧ1, формирующего адреса столбцов оперативного запоминающего устройства блока хранения результата, по команде «БХР:=ТИ» происходит подача прямоугольных тактовых импульсов на суммирующий вход двоичного счетчика СЧ2, формирующего адреса строк оперативного запоминающего устройства блока хранения результата.

Блоки 14, 15 и 16 образуют цикл, в котором происходит запись данных из блоков сортировки в блок хранения результата. По завершении цикла осуществляется переход на блок 34 алгоритма.

В блоке 14 происходит изменение переменной счетчика цикла i от начального значения единицы до конечного 256 с шагом+1.

В блоке 15 по команде «РгДКЧСi:=ВЫДi» на вход регистра i-го блока сортировки подается i-й информационный сигнал для выдачи числовых и символьных данных из регистров.

В блоке 16 по команде «БХР:=УМi» происходит подача выходного информационного сигнала с выхода регистра i-го блока сортировки на вход блока хранения результата.

В блоке 17 анализируется признак сортировки числовых и символьных данных по убыванию «СОРУБВ». По выходу «Нет» осуществляется переход на блок 23 алгоритма, по выходу «Да» осуществляется переход на блок 18 алгоритма.

В блоке 18 по команде «БХР:=ЗП» производится подача из блока управления на вход оперативного запоминающего устройства блока хранения результата управляющего сигнала для записи входных данных.

В блоке 19 по команде «БХР:=ГИ» происходит подача прямоугольных импульсов на суммирующий вход двоичного счетчика СЧ1, формирующего адреса столбцов оперативного запоминающего устройства блока хранения результата, по команде «БХР:=ТИ» происходит подача прямоугольных тактовых импульсов на суммирующий вход двоичного счетчика СЧ2, формирующего адреса строк оперативного запоминающего устройства блока хранения результата.

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

В блоке 20 происходит изменение переменной счетчика цикла i, от конечного значения 256 до начального единичного параметра с шагом -1.

В блоке 21 по команде «РгДКЧСi:=ВЫДi» на вход регистр i-го блока сортировки подается i-й информационный сигнал для выдачи данных из регистров.

В блоке 22 по команде «БХР:=УМi» происходит подача выходного информационного сигнала с выхода регистра i-го блока сортировки на вход блока хранения результата.

В блоке 23 происходит анализ признака «СОРИНТ», при котором упорядочение входной двоичной информации осуществляется в определенном интервале от заданного начального значения х до конечного параметра v. По выходу «Нет» осуществляется переход на блок 29 алгоритма, по выходу «Да» осуществляется переход на блок 24 алгоритма.

В блоке 24 по команде «БХР:=ЗП» производится подача из блока управления на вход оперативного запоминающего устройства блока хранения результата управляющего сигнала для записи входных данных.

В блоке 25 по команде «БХР:=ГИ» происходит подача прямоугольных импульсов на суммирующий вход двоичного счетчика СЧ1, формирующего адреса столбцов оперативного запоминающего устройства блока хранения результата, по команде «БХР:=ТИ» происходит подача прямоугольных тактовых импульсов на суммирующий вход двоичного счетчика СЧ2, формирующего адреса строк оперативного запоминающего устройства блока хранения результата.

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

В блоке 26 происходит изменение переменной счетчика цикла i, от начального значения х до конечного параметра v с шагом +1.

В блоке 27 по команде «РгДКЧСi=ВЫДi» на вход регистр i-го блока сортировки подается i-й информационный сигнал для выдачи результата сортировки из регистров.

В блоке 28 по команде «БХР:=УМi» происходит подача выходного информационного сигнала с выхода регистра i-го блока сортировки на вход блока хранения результата.

В блоке 29 анализируется признак «ЧИСИМ», при котором считывается и записывается двоичный код определенного конкретного числа или символа из регистра блоков сортировки. По выходу «Да» осуществляется переход на блок 30 алгоритма, по выходу «Нет» осуществляется переход на конечный блок 34 алгоритма.

В блоке 20 по команде «БХР:=ЗП» производится подача на вход оперативного запоминающего устройства блока хранения результата разрешающего управляющего сигнала из блока управления для записи входных данных в ОЗУ.

В блоке 31 по команде «БХР:=ГИ» происходит подача прямоугольных импульсов на суммирующий вход двоичного счетчика СЧ1, формирующего адреса столбцов оперативного запоминающего устройства блока хранения результата, по команде «БХР:=ТИ» происходит подача прямоугольных тактовых импульсов на суммирующий вход двоичного счетчика СЧ2, формирующего адреса строк оперативного запоминающего устройства блока хранения результата.

В блоке 32 по команде «РгДКЧСi:=ВЫД1» на вход регистр i-го блока сортировки подается i-й разрешающий информационный сигнал для выдачи результата из регистра.

В блоке 33 по команде «БХР:=УМi» происходит подача выходного информационного сигнала с выхода регистра i-го блока сортировки на вход блока хранения результата.

Блок 34 является конечным блоком алгоритма.

Работа устройства сортировки информации методом дешифрации заключается в следующем.

Внешние управляющие сигналы "ПУСК" и "СБРОС" поступают в блок 7 управления.

Блок 1 ввода данных БВД содержит шифратор ШФ DD8, представляющий собой обычную стандартную клавиатуру (фиг.2). Этот блок позволяет вводить символы и двоичные числа со своими знаковыми разрядами в двоичном коде. Символы представлены в коде ASCII - международная американская стандартная кодировка символов. С выхода шифратора формируется восьми разрядный информационный сигнал ДКЧС, представляющий двоичный код символов или чисел. Выходным сигналом шифратора ШД является знаковый разряд числа ЗРЧ. Двоичные положительные числа имеют в знаковом разряде значение нуль. Примером может служить положительное число 10, представленное в десятичной системе счисления, в двоичном представлении это число имеет вид 0.1010. Отрицательное число имеет в знаковом разряде единицу. Для примера возьмем число -12 в десятичной системе счисления, в двоичном коде это число имеет вид 1.1100. Выходной информацией блока 1 ввода данных БВД является информационный сигнал ЧСД, представляющий собой двоичный код символа и числа со своим знаковым разрядом. Выходной информационный сигнал ЧСД блока 1 ввода данных БВД поступает на входы блоков сортировки и блока дешифрации (фиг.1, 2).

Блок 2 сортировки состоит из трех блоков: блока подсчета положительных чисел БППЧ, блока подсчета отрицательных чисел БПОЧ, блока регистра двоичного кода БРгДК и генератора прямоугольных импульсов ПРИ, выполненного на элементе DD18 (фиг.3, 4). Блок подсчета положительных чисел БППЧ предназначен для определения и хранения знакового разряда числа - нуля и для подсчета положительных чисел, поступивших на вход блока сортировки. Блок подсчета отрицательных чисел БПОЧ предназначен для определения и хранения знакового разряда числа - единицы и для подсчета отрицательных чисел, поступивших на вход блока сортировки. Блок регистра двоичного кода БРгДК предназначен для записи, хранения и выдачи двоичного кода символа и модуля и знакового разряда числа. Генератор прямоугольных импульсов ПРИ предназначен для генерации прямоугольных импульсов. На фиг.3 представлены принципиальные схемы: блока подсчета положительных чисел БППЧ, блока подсчета отрицательных чисел БПОЧ, структурная схема блока регистра двоичного кода БРгДК и генератор прямоугольных импульсов ПРИ. На фиг.4 предложена принципиальная схема блока регистра двоичного кода БРгДК. Блок подсчета положительных чисел БППЧ состоит из логической схемы И с одним инверсным управляющим входом, выполненной на пороговом элементе DD9, логической схемы И с прямым управляющим входом, выполненной на пороговом элементе DD10, двоичного счетчика Сч1 DD11, предназначенного для подсчета прямоугольных импульсов, поступающих на суммирующий вход, D триггера Тр1, выполненного на элементе DD12, предназначенного для записи и хранения знакового разряда положительного числа. Предварительно перед сортировкой информации двоичные счетчики Сч1, Сч2, D триггера Тр1 и Тр2 были обнулены управляющим сигналом обнуления ОБЛ, поступившим из блока регистра двоичного кода. Сигнал обнуления ОБЛ, который поступает одновременно на входы установки в состояние нуль R двоичных счетчиков и триггеров. Входным управляющим сигналом блока сортировки БС1 является сигнал знаковый разряд числа ЗРЧ, который поступает с выхода блока 1 ввода данных. Управляющий сигнал знаковый разряд числа ЗРЧ параллельно поступает на прямой управляющий вход логической схемы И DD15 блока подсчета отрицательных чисел и на инверсный управляющий вход логической схемы И DD9 блока подсчета положительных чисел. Логические схемы И DD15 и И DD9 выполняют функцию электронных ключей (фиг.3). На прямые информационные входы логических схем И DD15, DD9 поступают прямоугольные импульсы с выхода генератора прямоугольных импульсов ПРИ.

В случае равенства нулевому значению сигнала знакового разряда числа ЗРЧ, который поступает на инверсный управляющий вход логической схемы И DD9, открывается электронный ключ. На выходе открытого электронного ключа логической схемы И DD9 сформируется прямоугольный импульс. Выход логической схемы И DD9 одновременно поступает на суммирующий вход двоичного счетчика Сч1 DD11 и на управляющий вход логической схемы И DD10, выполняющей функцию электронного ключа блока подсчета положительных чисел БППЧ. Единичный выход логической схемы И DD9, поступающий на управляющий вход электронного ключа, откроет логическую схему И DD10. Через открытый электронный ключ логической схемы И DD10 сигнал знакового разряда числа ЗРЧ, поступающий на информационный вход схемы, поступает на вход D триггера Тр1 DD12 и установит триггер в нулевое состояние на выходе. Выходной сигнал знакового разряда положительного числа ЗРПЧ D триггера Tp1 DD12 принимает нулевое значение. Выход D триггера Tp1 DD12 поступает на вход блока регистра двоичного кода БРгДК. Двоичный счетчик Сч1 DD11 подсчитает количество прямоугольных импульсов, поступивших на суммирующий вход. На выходе двоичного счетчика Сч1 DD11 сформируется информационный сигнал, который соответствует количеству положительных чисел КЛПЧ. Выход двоичного счетчика Сч1 DD11 поступает на вход блока регистра двоичного кода БРгДК (фиг.3). Если сигнал знакового разряда числа ЗРЧ, равный единичному значению, поступает на прямой управляющий вход логической схемы И DD15, то открывается электронный ключ. На выходе открытого электронного ключа логической схемы И DD15 сформируется прямоугольный импульс. Выход логической схемы И DD15 одновременно поступает на суммирующий вход двоичного счетчика Сч2 DD16 и на управляющий вход логической схемы И DD13, выполняющей функцию электронного ключа блока подсчета отрицательных чисел БПОЧ. Единичный выход логической схемы И DD15, поступающий на управляющий вход электронного ключа, откроет логическую схему И DD13. Через открытый электронный ключ логической схемы И DD13 сигнал знакового разряда числа ЗРЧ, поступающий на информационный вход схемы, поступает на вход D триггера Тр2 DD14 и установит триггер в единичное состояние на выходе. Выходной сигнал знакового разряда отрицательного числа ЗРОЧ D триггера Тр2 DD14 принимает единичное значение. Выход D триггера Тр2 DD14 поступает на вход блока регистра двоичного кода БРгДК. Двоичный счетчик Сч2 DD16 подсчитает количество прямоугольных импульсов, поступивших на суммирующий вход. На выходе двоичного счетчика Сч2 DD16 сформируется информационный сигнал, который соответствует количеству отрицательных чисел КЛОЧ. Выход двоичного счетчика Сч2 DD16 поступает на вход блока регистра двоичного кода БРгДК (фиг.3).

Блок регистра двоичного кода БРгДК блока 2 сортировки состоит из регистра двоичного кода числа и символа РгДКЧС, выполненного на элементе DD25, системы электронных ключей первой СЭК₁, системы электронных ключей второй СЭК₂, системы электронных ключей третьей СЭК₃ (фиг.4). Регистр двоичного кода числа и символа РгДКЧС элемент DD25 является универсальным восьмиразрядным регистром. Например, микросхема К155ИР13 [2]. Регистр может работать в режимах: параллельный ввод, хранение, установки нулей, операции сдвига, последовательный ввод. Режимы работы задаются сигналами на управляющих входах. Входным входом блока регистра двоичного кода БРгДК является информационный сигнал управления первый УПР₁, который поступает из блока 7 управления. В состав информационного сигнала управления первый УПР₁ входят управляющие сигналы: ВЫД - выдача результата, СДВ - сдвига информации, РЕЖ₁ и РЕЖ₂ - сигналы установки режимов работы микросхемы, ОБЛ - установки в нулевое состояние элементов памяти микросхемы, на тактовый вход С регистра поступает управляющий сигнал РАЗ₁ с выхода блока дешифрации, который является разрешающим сигналом для записи входной двоичной информации в регистр блока. Двоичный код в триггеры регистра будет записан по перепаду 0,1 тактового импульса [2]. На входы D₁-D₈ регистра поступает входной информационный двоичный сигнал числовых и символьных данных ЧСД с выхода блока 1 ввода данных. Предварительно перед работой устройства управляющим сигналом ОБН - установки в нуль будут обнулены все триггеры регистра. По перепаду входного управляющего сигнала РАЗ₁ информационный двоичный сигнал числовых и символьных данных ЧСД, поступающий из блока 1 ввода данных, будет записан в регистр блока регистра двоичного кода БРгДК блока 2 сортировки. Двоичный код выходной информации ДКВИ является выходом регистра (фиг.4). Система электронных ключей первая СЭК₁ состоит из логических элементов И, выполненных на пороговых элементах DD19, DD20, DD21. На информационные входы пороговых элементов DD19, DD20 системы электронных ключей первая СЭК1 поступает информационный сигнал количества отрицательных чисел КЛОЧ, на информационный вход порогового элемента DD21 поступает управляющий сигнал знакового разряда отрицательного числа ЗРОЧ. На управляющие входы системы электронных ключей первая СЭК₁ параллельно поступает сигнал выдачи ВЫД информации, который поступает из блока 7 управления. Выходной информацией системы электронных ключей первая СЭК₁ является двоичный код количества отрицательных чисел и знаковый разряд отрицательных чисел КОЧЗОЧ. Если управляющий сигнал выдачи ВЫД информации равен нулевому значению, то логические элементы И системы электронных ключей первая СЭК₁ будут заперты. В этом случае выходной информационный сигнал код количества отрицательных чисел и знаковый разряд отрицательных чисел КОЧЗОЧ будет равен нулю. Если управляющий сигнал выдачи ВЫД информации равен единичному значению, то логические элементы И системы электронных ключей первая СЭК₁ будут открыты. В этом случае выходной информационный сигнал код количества отрицательных чисел и знаковый разряд отрицательных чисел КОЧЗОЧ будет равен числовому двоичному значению количества отрицательных чисел КЛОЧ и знаковому разряду отрицательного числа ЗРОЧ. Система электронных ключей вторая СЭК₂ состоит из логических элементов И, выполненных на пороговых элементах DD22, DD23, DD24. На информационные входы пороговых элементов DD22, DD23 системы электронных ключей вторая СЭК₂ поступает информационный сигнал количества положительных чисел КЛПЧ, на информационный вход порогового элемента DD24 поступает управляющий сигнал знакового разряда положительного числа ЗРПЧ. На управляющие входы системы электронных ключей вторая СЭК₂ параллельно поступает сигнал выдачи ВЫД информации, который поступает из блока 7 управления. Выходной информацией системы электронных ключей вторая СЭК₂ является двоичный код количества положительных чисел и знаковый разряд положительных чисел КПЧЗПЧ. Если управляющий сигнал выдачи ВЫД информации равен нулевому значению, то логические элементы И системы электронных ключей вторая СЭК₂ будут заперты. В этом случае выходной информационный сигнал код количества положительных чисел и знаковый разряд положительных чисел КПЧЗПЧ будет равен нулю. Если управляющий сигнал выдачи ВЫД информации равен единичному значению, то логические элементы И системы электронных ключей вторая СЭК₂ будут открыты. В этом случае выходной информационный сигнал код количества положительных чисел и знаковый разряд положительных чисел КПЧЗПЧ будет равен числовому двоичному значению количества положительных чисел КЛПЧ и знаковому разряду положительного числа ЗРПЧ. Система электронных ключей третья СЭК₃ состоит из логических элементов И, выполненных на пороговых элементах DD26, DD27. На информационные входы пороговых элементов DD26, DD27 системы электронных ключей третья СЭК3 поступает информационный сигнал двоичного кода ДКВИ, поступающий с выхода регистра двоичного кода числа и символа РгДКЧС DD25. На управляющие входы системы электронных ключей третья СЭК₃ параллельно поступает сигнал выдачи ВЫД информации, который поступает из блока 7 управления. Выходной информацией системы электронных ключей третья СЭК₃ является двоичный код символа или числа ДКСЧ. Если управляющий сигнал выдачи ВЫД информации равен нулевому значению, то логические элементы И системы электронных ключей третья СЭК₃ будут заперты. В этом случае выходной информационный сигнал двоичного кода символа или числа ДКСЧ будет равен нулю. Если управляющий сигнал выдачи ВЫД информации равен единичному значению, то логические элементы И системы электронных ключей третья СЭК₃ будут открыты. В этом случае выходной информационный сигнал двоичного кода символа или числа ДКСЧ будет равен двоичному коду выходной информации регистра двоичного кода числа и символа РгДКЧС (фиг.4).

Блоки 3, ..., 256 сортировки выполняют аналогичные функции по упорядочению двоичной информации, имеют одинаковые структурные и принципиальные схемы, как и блок 2 сортировки (фиг.1). Количество блоков сортировки равно числу 256. Символы латинского и русского алфавитов кодируются восьмиразрядным двоичным кодом. Общее количество блоков соответствует числу 2⁸=256. Числа, которые упорядочены в представленном устройстве, принадлежат диапазону 1-2⁸≤N≤2⁸-1.

Блок 5 дешифрации состоит из семнадцати дешифраторов ДШ1 DD28, ДШ2 DD29, ДШ3 DD30, ..., ДШ17 DD31 (фиг.5). Функция дешифратора состоит в преобразовании входной двоичной информации в унитарный код на выходе. На выходе дешифратора только один высокий уровень, одна единица. Этот высокий уровень является разрешающим сигналом для записи входной информации в определенный двоичный регистр одного из двухсот пятидесяти шести блоков 5 сортировки. Входным информационным сигналом ЧСД блока является двоичный код символа или модуля числа. Четыре старших разряда информационного сигнала поступают на вход первого дешифратора ДШ1 DD28. Младшие четыре разряда поступают параллельно на входы остальных шестнадцати дешифраторов ДШ2 DD29, ДШ3 DD30, ..., ДШ17 DD31. На разрешающий работу Е вход дешифратора ДШ1 DD28 поступает управляющий сигнал СРЗ из блока 7 управления. При единичном значении сигнала СРЗ дешифратор ДШ1 DD28 находится в рабочем состоянии, на выходе микросхемы только одна единица, остальные выходы находятся в нулевом состоянии. При нулевом значении сигнала СРЗ дешифратор находится в нерабочем режиме, на выходе микросхемы только нулевая информация. На выходе дешифратора ДШ1 DD28 при рабочем состоянии будет код один из шестнадцати. Единица на выходе первого дешифратора переведет в рабочее состояние один из оставшихся шестнадцати дешифраторов блока. На выходе только этого дешифратора будет одна единица, все остальные выходы этой микросхемы будут в нулевом состоянии. Остальные пятнадцать дешифраторов блока будут в нерабочем состоянии, т.е. на выходах этих микросхем установится нулевое состояние. На выходе блока 5 дешифрации сформируется унитарный код один из двухсот пятидесяти шести (фиг.5). Выходные сигналы блока дешифрации РАЗ₁ - РАЗ₂₅₆ поступают на входы блоков сортировки. Один единичный выходной сигнал блока дешифрации поступает на разрешающий вход для записи информации в один из двухсот пятидесяти шести регистров блоков сортировки. Поступившая на вход информация в виде двоичного кода символа и числа со своим знаковым разрядом будет записана в этот регистр (фиг.1, 4).

Блок 6 хранения результата БХР состоит из оперативного запоминающего устройства ОЗУ DD34, первого двоичного счетчика Сч1, формирующего адреса столбцов АД СТЛ DD32, второго двоичного счетчика Сч2, формирующего адреса строк АД СТР DD33 (фиг.6). Этот блок служит для хранения двоичных разрядов символьной и числовой информации при выполнении операции сортировки данных. На вход блока поступают упорядоченные двоичные коды символов и чисел в виде информационного сигнала УМД. На вход блока 6 хранения результата БХР поступают управляющие сигналы из блока 7 управления. Сигнал ОБН обнуления поступает на вход установки в нулевое состояние первого двоичного счетчика Сч1 DD32. Этот сигнал предназначен для обнуления счетчика Сч1. Сигнал УСН обнуления поступает на вход установки в нулевое состояние второго двоичного счетчика Сч2 DD33 и предназначен для обнуления счетчика Сч2. Управляющий сигнал ГИ генератора прямоугольных импульсов поступает на суммирующий вход первого двоичного счетчика Сч1 DD32 для формирования адреса столбцов в оперативном запоминающем устройстве. Управляющий сигнал ТИ генератора тактовых импульсов поступает на суммирующий вход второго двоичного счетчика Сч2 DD33 для формирования адреса строк в оперативном запоминающем устройстве. Управляющий сигнал ВК выбора кристалла поступает на вход оперативного запоминающего устройства ОЗУ из блока 7 управления и устанавливает микросхему в рабочий режим. Управляющий сигнал Зп/Сч запись/считывания поступает на вход оперативного запоминающего устройства ОЗУ из блока 7 управления и устанавливает микросхему в режимы записи или считывания информации. Информационный сигнал результат упорядоченных данных РУД является выходным сигналом оперативного запоминающего устройства (фиг.6).

Комбинационная схема блока управления устройства сортировки информации методом дешифрации данных строится по размеченной граф-схеме алгоритма ГСА (фиг.8) по известным правилам [4].

Логические условия:

X1: "СБРОС"Х4: "СОРВОЗ"Х2: "ЗВД"Х5: "СОРУБВ"Х3: "РАЗi"Х6: "СОРИНТ"Х7: "ЧИСИМ" 

Операторы:

У1: "ПУСК:=1"У8: "БХР:=ЗП"У2: "ОБН:=1"У9: "БХР:=ГИ"У3: "БС:=ЧСД"У10: "БХР:=ТИ"У4: "БДШ:=ЧСД"У11: "РгДКЧСi:=ВЫДi"У5: "For i:=1 to 256 do"У12: "БХР:=УМi"У6: "БСi:=РАЗi"У13: "For i:=256 to 1 do"У7: "БСi:=ЧСД"У14: "For i:=X to V do"

ИСТОЧНИКИ ИНФОРМАЦИИ

1. Кнут Д.Э. Искусство программирования, том 3. Сортировка и поиск, 2-е изд.: Пер с англ. - М.: Издательский дом "Вильямс", 2001. - 832 с.: ил.

2. Зельдин Е.А. Цифровые интегральные микросхемы в информационной измерительной аппаратуре. - Л.: Энергоатом издат. Ленингр. отд-ние, 1986. - 280 с.: ил.

3. Алексенко А.Г., Шагурин И.И. Микросхемотехника: Учеб. пособие для вузов. - 2-е изд., перераб. и доп. - М.: Радио и связь, 1990. - 496 с.: ил.

4. Баранов С.И. Синтез микропрограммных автоматов. - Энергия. Ленинградское отделение. 1974 г. - 184 с.

5. Мкртчян С.О. Проектирование логических устройств ЭВМ на нейронных элементах. - М.: Энергия, 1977 г.

6. Вавилов Е.И. и др. Синтез схем на пороговых элементах. - М.: Сов. радио. 1970 г.

7. Патент №2067317 "Устройство сортировки символов" / Шевелев С.С. и др.

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

Устройство сортировки информации методом дешифрации данных, содержащее блоки сортировки, блок управления, отличающееся тем, что дополнительно введены: блок ввода данных, блок дешифрации, блок хранения результата, причем информационный выход блока ввода данных соединен с первыми информационными входами всех блоков сортировки и с информационным входом блока дешифрации, на информационном выходе формируются двоичные коды чисел, которые представлены в прямом коде со своими знаковыми разрядами, и символы, представленные в двоичном коде, передача входных двоичных кодов символов и чисел осуществляется в параллельном режиме побайтно, первый управляющий выход блока управления соединен с управляющим входом блока дешифрации, на котором формируется сигнал разрешения работы блока дешифрации, первый управляющий выход блока дешифрации соединен с управляющим входом первого блока сортировки, на котором формируется сигнал разрешения работы первого блока сортировки, второй управляющий выход блока дешифрации соединен с управляющим входом второго блока сортировки, на котором формируется сигнал разрешения работы второго блока сортировки, двести пятьдесят шестой выход блока дешифрации соединен с управляющим входом двести пятьдесят шестого блока сортировки, на котором формируется сигнал разрешения работы двести пятьдесят шестого блока сортировки, первый информационный выход блока управления соединен со вторым информационным входом первого блока сортировки, на котором формируются: сигнал выдачи информации, сигнал сдвига информации вправо, сигналы установки режимов работы, сигнал обнуления регистра двоичного кода числа и символа первого блока сортировки, второй информационный выход блока управления соединен со вторым информационным входом второго блока сортировки, на котором формируются: сигнал выдачи информации, сигнал сдвига информации вправо, сигналы установки режимов работы, сигнал обнуления регистра двоичного кода числа и символа второго блока сортировки, третий информационный выход блока управления соединен со вторым информационным входом двести пятьдесят шестого блока сортировки, на котором формируются: сигнал выдачи информации, сигнал сдвига информации вправо, сигналы установки режимов работы, сигнал обнуления регистра двоичного кода числа и символа двести пятьдесят шестого блока сортировки, информационный выход первого блока сортировки соединен с информационным входом блока хранения результата, на котором формируется двоичный код числа и символа, а также знаковый разряд числа и количество чисел и символов, поступивших на вход регистра двоичного кода числа и символа первого блока сортировки, передача выходных двоичных кодов символов и чисел с информационного выхода первого блока сортировки осуществляется в параллельном режиме побайтно, информационный выход второго блока сортировки соединен с информационным входом блока хранения результата, на котором формируется двоичный код числа и символа, а также знаковый разряд числа и количество чисел и символов, поступивших на вход регистра двоичного кода числа и символа второго блока сортировки, передача выходных двоичных кодов символов и чисел с информационного выхода второго блока сортировки осуществляется в параллельном режиме побайтно, информационный выход двести пятьдесят шестого блока сортировки соединен с информационным входом блока хранения результата, на котором формируется двоичный код числа и символа, а также знаковый разряд числа и количество чисел и символов, поступивших на вход регистра двоичного кода числа и символа двести пятьдесят шестого блока сортировки, передача выходных двоичных кодов символов и чисел с информационного выхода двести пятьдесят шестого блока сортировки осуществляется в параллельном режиме побайтно, с первого по шестой управляющие входы блока хранения результата соединены соответственно со вторым по седьмой управляющими выходами блока управления, на которых формируется сигнал установки в нулевое состояние двоичного счетчика, формирующего адреса строк оперативного запоминающего устройства, сигнал обнуление двоичного счетчика, формирующего адреса столбцов оперативного запоминающего устройства, сигнал генератора прямоугольных импульсов для формирования адресов столбцов в двоичном счетчике для записи результата в оперативное запоминающее устройство, сигнал тактовых импульсов для формирования адресов строк в двоичном счетчике для записи результата в оперативное запоминающее устройство, сигнал выбора кристалла для разрешения работы оперативного запоминающего устройства, сигнал выбора режима работы запись/считывание оперативного запоминающего устройства, первый и второй управляющие входы "СБРОС" и "ПУСК" блока управления являются внешними входами устройства сортировки информации методом дешифрации данных.