УСТРОЙСТВО СОРТИРОВКИ СИМВОЛОВ Российский патент 1996 года по МПК G06F17/28 

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

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

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

В качестве прототипа выбрано "Устройство для реализации нормальных алгорифмов Маркова" (а.с. N 1455345, 1989г, бюл. N 4), которое позволяет обрабатывать информационные потоки и массивы данных текстового и числового характеров в соответствии с заданными нормальными алгоритмами.

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

Изобретение позволит повысить скорость обработки информационных потоков и массивов данных текстового характера.

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

Известны алгоритмы, позволяющие упорядочить слова из некоторого массива слов, например, по признаку алфавитного порядка, как это имеет место при формировании словарей. Известны также универсальные устройства для реализации формул подстановки в виде алгоритмов Маркова [1]
Под алгоритмом Маркова понимается конечная последовательность формул, представляющих собой слова вида:
S __→ T
где S образец, Т подстановка, S и Т произвольные слова в фиксированном алфавите.

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

где знак графического равенства, R1, R2 любые слова в фиксированном алфавите, тогда результат работы формулы будет иметь вид:

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

Размеченный алгорифм Маркова для упорядочения массива слов будет иметь вид:

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

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

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

На фиг.3 представлен вариант технической реализации коммутатора.

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

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

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

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

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

Устройство сортировки символов (фиг.1) содержит входной канал 1, блок 2 шифрации и определения адреса, блок 3 коммутатор, блок 4 определения частоты символов, первый блок 5 сортировки, второй блок 6 сортировки, блок 7 организации подстановок, блок 8 управления.

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

1. ЗС знак символа.

2. КРЗ команда разрешения записи в матричный умножитель блока БША.

3. КОП команда операции;
4. КВР команда выдачи результата из матричного умножителя блока БША.

5. ГИ1 поток тактовых импульсов 1.

6. СИХ1 сигнал синхронизации 1.

7. СОБ1 сигнал обнуления первый, поступающий на вход счетчиков СЧ1 и СЧ2 блока БОЧС.

8. ЗП/СЧ1 сигнал записи/чтения ОЗУ1 блока БОЧС.

9. ВК1 сигнал выбора кристалла ОЗУ1 блока БОЧС.

10. ГИ2 поток тактовых импульсов 2.

11. СОБ2 сигнал обнуления регистра-счетчика блока БОЧС.

12. КНИ признак наличия информации в ОЗУ1 блока БОЧС.

13. ГИЗ поток тактовых импульсов 3.

14. СИХ2 сигнал синхронизации 2.

15. СОБ3 сигнал обнуления счетчиков СЧ1 и СЧ2 блока БС1.

16. ЗП/СЧ2 сигнал записи/чтения ОЗУ2 блока БОЧС.

17. ВК2 сигнал выбора кристалла ОЗУ2 блока БОЧС.

18. ГИ4 поток тактовых импульсов 4.

19. СОБ3 сигнал обнуления счетчиков СЧ1 и СЧ2 блока БС1.

20. ЗП/СЧ3 сигнал записи/чтения ОЗУ1 блока БС1.

21. ВК3 сигнал выбора кристалла ОЗУ1 блока БС1.

22. КОИ признак наличия информации в ОЗУ1 блока БС1.

23. ГИ5 поток тактовых импульсов 5.

24. ГИ6 поток тактовых импульсов 6.

25. ЗП/СЧ4 сигнал записи/чтения ОЗУ2 блока БС1.

26. ВК4 сигнал выбора кристалла ОЗУ2 блока БС1.

27. БПС признак буфера памяти ОЗУ2 блока БС1 пуст.

28. ГИ7 поток тактовых импульсов 7.

29. ГИ8 поток тактовых импульсов 8.

30. СОБ4 сигнал обнуления счетчиков СЧ1 и СЧ2 блока БС2.

31. ЗП-СЧ5 сигнал записи-чтения ОЗУ1 блока БС2.

32. ВК5 сигнал выбора кристалла ОЗУ1 блока БС2.

33. ГИ9 поток тактовых импульсов 9.

34. ГИ10 поток тактовых импульсов 10.

35. ЗП/СЧ6 сигнал записи-чтения ОЗУ2 блока БС2.

36. ВК6 сигнал выбора кристалла ОЗУ2 блока БС2.

37. КПИ признак наличия информации ОЗУ2 блока БС2.

38. БСП признак буфера памяти ОЗУ2 блока БС2 ПУСТ.

39. КУП команда управления блока БОП.

40. ГИ10 поток тактовых импульсов 10.

41. СУ0 сигнал установки в нуль счетчика СЧ блока БОП.

42. КПР команда приема регистра РС блока БОП информации из коммутатора блока.

43. СИН сигнал синхронизации регистра RG блока БОП.

44. КВД команда выдачи результата регистром RG блока БОП.

45. КВС команда выдачи символов блока БОП.

46. КЗС код признака символа.

47. УМС упорядоченный массив символов выходная информация блока БОП.

48. БС входные символы.

49. АС адрес символа.

50. АСВ адреса символов вторые.

51. АСП адреса символов первые.

52. УМВ упорядоченный массив символов второй блока БС2.

53. УМП упорядоченный массив символов первый блока БС1.

54. ЧПС частота повторения символов блока БОЧС.

55. ПКМ признак конца массива символов.

56. ДКС двоичный код символов, информационный выход шифратора блока БША.

57. ФАС формирование адреса счета счетчиком СЧ1 блока БОЧС.

58. АЧС адрес частоты символов.

59. ДЧС выходные данные частоты символов из ОЗУ1 блока БОЧС.

60. ИЧС измененная частота символов, входные данные ОЗУ1 блока БОЧС.

61. АДН адресные данные ОЗУ2 блока БОЧС, выходная информация счетчика СЧ2.

62. ПУСК сигнал пуска устройства.

63. СБРОС сигнал сброса устройства.

64. ППБ признак пустых буферов памяти.

65. БСП признак буфера памяти ОЗУ2 блока БС2 пуст.

66. АСС адрес считывания символов из ОЗУ1 блока БС1, информационный выход счетчика СЧ1.

67. ВДС выходные данные символов из ОЗУ1 блока БС1.

68. АВС адреса выборки символов из ОЗУ2 блока БС1.

69. Р признак многократного обращения по одному и тому же адресу.

70. СВД выходные данные символов из ОЗУ1 блока БС2.

Блок 2 (фиг.2) содержит шифратор 9, Д-триггер 10, матричный умножитель 11, дешифратор 12.

Коммутатор 3 (фиг. 3) содержит группу элементов И13, группу элементов И14.

Блок 4 (фиг.4) содержит оперативно-запоминающее устройство 15 (ОЗУ), оперативно-запоминающее устройство 16, (ОЗУ), регистр -счетчик 17 (Рч-Сч), счетчик 18 (СЧ), реверсивный счетчик 19 (cr), группу элементов ИЛИ 20, элемент ИЛИ 21.

Блок 5 сортировки (фиг.5) содержит оперативно-запоминающее устройство 22 (ОЗУ), оперативно-запоминающее устройство 23 (ОЗУ), счетчик 24 (Сч), реверсивный счетчик 2 (Сч), группу элементов ИЛИ 26, элемент ИЛИ 27, элемент ИЛИ-НЕ 28.

Блок 7 (фиг.6) содержит регистр 29, счетчик 30, Д-триггер 31 знака, элемент ИЛИ 32, первую группу элементов И 33, вторую группу элементов И 34, группу элементов ИЛИ 35.

Блок 8 управления синтезируется на основе ГСА алгоритма управления (фиг. 7) известным способом (2). Размеченная ГСА работы блока 8 управления приведена на фиг.8 (обозначения на фиг.8 приведены в таблице в конце текста).

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

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

По сигнала "УОО" и "ПУСК" (блоки 37-39 граф-схемы алгоритма) фиг.1) происходит установка в нуль всех элементов памяти устройства по команде "СБРОС: 1" (блок 38).

В блоке 40 алгоритма происходит запись нулевой информации в ОЗУ1 блока БОЧС (фиг. 4). На вход ("ЗП-СЧ1" подается единица, на вход "ВК" подается нуль, на информационные входы ОЗУ1 подается Д/О) по командам "ЗП/СЧ1:1", ВК1: 0", ОЗУ1: Д/О"). По этим командам происходит предварительная загрузка устройства.

В блоке 41 происходит подача символов из входного канала на вход шифратора (ШД) (фиг.2).

В блоке 42 происходит анализ признака конца массива "ПКМ".

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

В блоке 43 происходит анализ признака знака символа "ЗС". Если "ЗС=0" (знак символа положительный), то происходит загрузка этого символа в ОЗУ1 блока БС1 (фиг.5). Если "ЗС=1" (знак символа отрицательный), то происходит загрузка этого символа в ОЗУ1 блока БС2.

В блоке 44 по командам: "ЗП/СЧ5:1", "ВК5:0" происходит подача управляющих сигналов из блока управления на вход ОЗУ1 блока БС2, что соответствует режиму записи. По командам: "ОЗУ1:АСВ", ОЗУ1:ВС" происходит загрузка в ОЗУ1 блока БС2 очередного символа, признак которого равен единице, по соответствующему этому символу адресу.

В блоке 45 по командам: "ЗП/CЧ3:1", "ВКЗ:0" происходит подача управляющих сигналов из блока управления на вход ОЗУ1 блока БС1 (фиг.5), это соответствует режиму записи. По командам: "ОЗУ1:АСП", "ОЗУ1:ВС" происходит загрузка в ОЗУ1 блока БС1 очередного символа, знак которого равен нулю, по соответствующему этому символу адресу (фиг.5).

В блоке 46 алгоритма по командам: "ЗП/СЧ1:1, "ВК1:0" происходит подача управляющих сигналов из блока управления на вход ОЗУ1 блока БОЧС (фиг.4), что соответствует режиму записи. По команде "ОЗУ1:АС" происходит загрузка ОЗУ1 блока БОЧС (фиг.4) очередной информации из блока БША (фиг.1).

В блоке 47 алгоритма происходит анализ признака "Р". Этот признак соответствует многократному поступлению одного и того же символа. Если "Р=0", то происходит переход по алгоритму на блок 7. Если "Р=1", то происходит считывание информации из ОЗУ1 блока БОЧС (фиг.4).

В блоке 48 алгоритма по командам: "ЗП/СЧ1:0". "ВК1:0:" происходит подача управляющих сигналов из блока управления на вход ОЗУ1 блока БОЧС (фиг.4), что соответствует режиму считывания из ОЗУ1 информации. По команде "ГИ2:1" происходит подача на вход регистра-счетчика блока БОЧС (фиг.4) тактовых импульсов. По команде "РГ-СЧ:ДЧС" происходит прием регистром-счетчиком информации из ОЗУ15 блока 4.

В блоке 49 алгоритма по командам: "ЗП/CЧ1:1", "ВК1:0" происходит подача управляющих сигналов из блока управления на вход ОЗУ15 блока 4 (фиг.4), что соответствует режиму записи в ОЗУ15, по команде "ОЗУ1:ИЧС" происходит запись в ОЗУ15 блока 4 информации "ИЧС" по тому же адресу, по которому произошло чтение из ОЗУ. Эта операция необходима для подсчета количества одинаковых символов. В ОЗУ15 блока 4 содержится информация о количестве одинаковых символов: при этом "ИЧС:ДЧС+1". Признаком одинакового символа является обращение к ОЗУ15 блока по одному и тому же адресу. При этом данные о количестве одинаковых символов увеличиваются на единицу.

В блоке 50 алгоритма происходит анализ признака пустых буферов "ППБ". Если буферы ОЗУ23 блока 5 и ОЗУ23 блока 6 пусты, то это является признаком конца работы устройства, при этом осуществляется переход на 68 блок алгоритма. Если буферы ОЗУ блоков непустые, то это означает наличие в них информации, из этого следует дальнейшее продолжение работы устройства.

В блоке 51 алгоритма по командам: "СИХ1:1", "СИХ2:1" происходит подача синхроимпульсов на С-входы счетчиком устройства (фиг.1,4,5).

В блоке 52 алгоритма происходит анализ признака "КНИ" наличие информации в ОЗУ15 блока 4 (фиг.4). Если "КНИ:0", то буфер ОЗУ15 блока пуст, при этом осуществляется переход на блок 53 алгоритма. Если "КНИ:1", то буфер ОЗУ15 блока 5 непустой, при этом происходит переписывание информации из ОЗУ15 блока 4 (фиг. 4). Переписывание информации необходимо для компактного использования памяти устройства.

В блоке 55 алгоритма по командам: "ГИ1:1" происходит подача из блока управления на суммирующий вход счетчика СЧ18 блока 4 (фиг.4), тактовых импульсов "ЗП/СЧ1:0", "ВК1:0" происходит подача управляющих сигналов из блока управления на вход ОЗУ15 блока 4, что соответствует режиму чтения информации из ОЗУ15.

В блоке 58 алгоритма по командам: "ГИЗ:1" происходит подача на суммирующий вход счетчика СЧ19 блока 4, тактовых импульсов "ЗП/СЧ2:1", "ВК2:0" происходит подача на управляющие входы ОЗУ16 блока 4 сигналов из блока управления, что соответствует режиму записи информации, "ОЗУ2:ДЧС"- по этой команде происходит подача на вход данных ОЗУ16 информации "ДЧС", при том эта информация записывается в ОЗУ16 блока. При этом происходит переход на блок 52 алгоритма.

В блоке 53 алгоритма происходит анализ признака "КОИ" наличие информации в ОЗУ22 блока 5. Если "КОИ=0", то происходит дальнейшее считывание информации из ОЗУ22, если "КОИ=1", то при этом происходит запись этой информации в ОЗУ23 блока 5 (фиг.5).

В блоке 56 алгоритма по командам:"ГИ5:1" происходит: подача из блока управления на суммирующий вход счетчика СЧ24 блока 5 (фиг.5) тактовых импульсов, "ЗП/СЧ3:0", "ВК3:0" происходит подача управляющих сигналов на вход ОЗУ22 блока 5 (фиг.5), что соответствует режиму чтения информации из ОЗУ22.

В блоке 59 алгоритма по командам: "ГИ6:1" происходит подача на суммирующий вход счетчика СЧ25 блока 5 (фиг.5) тактовых импульсов, "ЗП/СЧ4:1", "ВК4: 0" происходит подача на управляющие входы ОЗУ23 блока 5 сигналов, что соответствует режиму записи информации в ОЗУ23 блока, по команде "ОЗУ2:ВДС" происходит подача информационного сигнала "ВДС" на вход данные ОЗУ23, при этом информация записывается в ОЗУ23 блока.

В блоке 54 алгоритма происходит анализ признака "КПИ" наличие информации в ОЗУ22 блока 6. Если "КПИ=0", то осуществляется переход на блок 61 алгоритма (вся информация с ОЗУ22 в ОЗУ23 блока 6 переписана). Если "КПи=1", то это означает, что в ОЗУ22 находится еще информация и при этом необходимо ее переписать в ОЗУ23 блока.

В блоке 57 алгоритма по командам: "ГИ8:1", "ЗП/СЧ5:0", "ВК5:0" происходит подача тактовых импульсов на суммирующий вход счетчика блока 6, ОЗУ22 блока находится в режиме чтения информации из памяти.

В блоке 60 алгоритма по командам: "ГИ9:1", "ЗП/СЧ6:1", "ВК6:0", "ОЗУ2: СДВ" происходит подача на суммирующий вход счетчика тактовых импульсов. ОЗУ23 находится в режиме записи информации. На вход данные памяти поступает информационный сигнал "СДВ", при этом эта информация записывается в ОЗУ23 блока 6.

В блоке 61 алгоритма по командам: "КПР:1", "СИН:1" происходит подача разрешающего сигнала на прием информации в регистр RG блока 7 (фиг.6) из коммутатора блока. На синхронизирующий вход регистра подаются синхроимпульсы из блока управления.

В блоке 62 алгоритма происходит анализ признака "КУП" (команда управления коммутатором). Если "КУП=0", то в регистр RG блока 6 БОП загружается информация символов, имеющих признак знака нуль. Если "КУП=1", то в регистр RG блока БОП загружается информация символов, имеющих признак знакового разряда единицу.

В блоке 63 алгоритма по командам: "RG:УПМ", "КЗС:0" происходит загрузка в регистр RG блока 7 символов с признаком знака нуль. Триггер признака Тзп блока БОП устанавливается в состояние нуль.

В блоке 64 алгоритма по командам: "RG:УМВ", "КЗС:1" происходит загрузка в регистр RG блока 7 символов с признаком единица. Триггер этого признака Тзн БОР устанавливается в состояние единица.

В блоке 65 алгоритма по команде "СЧ:ЧПС" происходит загрузка в счетчик СЧ блока 7 информации из блока 4, в котором содержится информация о количестве одинаковых символов, поступивших из входного блока (фиг.4).

В блоке 66 регистра по командам: "ГИ11:1", "КВД:1", "УМС:RG", "КЗС:КУП" происходит подача тактовых импульсов на вычитающий вход счетчика СЧ блока 7, подача на вход выдачи информации из регистра RG разрешающего сигнала, информация из регистра RG подается на информационный выход устройства, код знака символа принимает значение, равное управляющему сигналу "КУП", поступающему из блока управления.

В блоке 67 алгоритма происходит анализ признака "КВС" наличие информации в счетчике СЧ блока 7. Если "КВС:0", то происходит переход на блок 62 алгоритма. Если "КВС-1", то это означает, что счетчик непустой и происходит выдача символов до тех пор, пока счетчик не обнулится.

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

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

Основная идея работы устройства заключается в следующем: на вход устройства для сортировки символов поступает символьная информация, в блоке шифрации и определения адреса происходит умножение входного символа с константой. Константа выбирается заранее. Результат умножения является адресом памяти, по которому будет записан входной символ. В качестве памяти применяется оперативно-запоминающее устройство (ОЗУ). Адрес ОЗУ произведение символа и константы. Данные ОЗУ символ. Если на вход устройства поступает несколько раз один и тот же символ, то в блоке 4 определения частоты символов происходит подсчет количества одинаковых символов. При выдаче упорядоченного массива символов, каждый символ является столько раз, сколько раз был зафиксирован в блоке 4 определения частоты символов. В первом разряде символа содержится информация о признаке символа. Если первый разряд равен "0", то данный символ записывается в блок сортировки первый. Если первый разряд равен "1", то данный символ записывается в блок сортировки второй.

Блок 2 шифрации и определения адреса работает следующим образом.

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

Сигнал "ЗС" (выход Д-триггера) признак символа поступает на вход блока управления. По этому сигналу происходит начало работы устройства. По приходу из блока 8 управления (фиг.1) команды "КРЗ" команды разрешения записи - происходит запись двоичного кода символа в матричный умножитель. По команде "КОП" команде операции происходит умножение двоичного кода символа с заранее записанной в матричный умножитель константой. По команде "КВР" - команде выдачи результата происходит выдача результата умножения из блока шифрации и определения адреса. Дешифратор определяет признак конца массива символов. По сигналу "ПКМ" признак конца массива символов, поступающем в блок управления, происходит переписывание информации из ОЗУ22 в ОЗУ23 блоков: сортировки первый (фиг.5), сортировки второй, определения частоты символов (фиг.4). Сигнал "ЗС" поступает на вход коммутатора 3 (фиг.1).

Коммутатор 3 работает следующим образом.

Группы элементов И работают в ключевом режиме. Управляющим входом элементов является информационный сигнал "АСП", поступающий на адресный вход ОЗУ22 блока сортировки первый (фиг.5). Если "ЗС" равен единице, то выходом коммутатора является информационный сигнал "АСв", поступающий на адресный вход ОЗУ1 блока сортировки второй. На информационные входы элементов И поступает информационный сигнал "АС" из блока шифрации и определения адреса.

Блок определения частоты символов (фиг.4) работает следующим образом.

Предварительной записью в ОЗУ15 является запись нулевой информации. В основе работы блока лежит подсчет количества одинаковых символов. Если одни и те же символы поступают на вход устройства многократно, то всякий раз считывается информация о количестве поступления символа из ОЗУ1 блока, суммируется с единицей и снова записывается по этому же адресу в ОЗУ1. По приходу информационного сигнала "АС" из блока шифрации и определения адреса, через схему ИЛИ поступает на адресный вход ОЗУ1 блока. По приходу сигналов из блока 8 управления "ЗП"/СЧ1:0" и "ВК1:0" происходит считывание информации о количестве поступивших символов "ДЧС". По приходу сигнала "СОБ2=0" из блока управления регистр-счетчик Рч-Сч предварительно был обнулен. По приходу сигнала "ГИ2=1" из блока управления происходит суммирование информации "ДЧС" с единицей. Информационный сигнал "ИЧС:ДЧС+1". Измененный сигнал "ИЧС" поступает на вход данные ОЗУ1 и записывается по этому же адресу в память. По приходу в блок 8 управления признака конца массива символов "ПКМ" из блока 2 шифрации и определения адреса происходит переписывание информации из ОЗУ15 и ОЗУ16 блока, для компактного использования памяти и для ускоренного считывания информации из ОЗУ2. По приходу из блока 8 управления сигнала "СОБ1=0" счетчик 18 предварительно был обнулен. Счетчик 18 синхронизирован сигналом "СИХ1" из блока управления. По приходу из блока управления сигнала "ГИ1=1" происходит формирование счетчиком 18 адресов считывания "ФАС" через схему ИЛИ1 информации из ОЗУ15. При этом управляющие сигналы "ЗП/СЧ1=0", "ВК1=0", что соответствует режиму чтения. По приходу сигнала "КНИ-1" в блок 8 управления происходит запись информации из ОЗУ15 в ОЗУ16. По приходу сигнала "СОБ1" из блока 8 управления предварительно реверсивный счетчик 19 был обнулен. Счетчик 19 синхронизирован сигналом "СИХ2". По приходу сигнала "ГИЗ= 1" происходит формирование адресов записи в ОЗУ16. При этом "ЗП/СЧ2=1", ВК2= 0", что соответствует режиму записи. Информационный выход ОЗУ15 "ДЧС" поступает на вход данные в ОЗУ16, по приходу из блока 8 управления сигнала "ГИ4= 1" происходит считывание информации из ОЗУ16. При этом "ЗП/СЧ2=0", "ВК2=0". Режим считывания из ОЗУ16 происходит одновременно из всех ОЗУ блоков: сортировки первый, сортировки второй, определения частоты символов. Информационный выход блока 4 определения частоты символов "ЧПС" поступает в блок 7 организации подстановок (фиг.1).

Блок сортировки работает следующим образом.

В этом блоке 5 происходит запись символов по соответствующим каждому символу адресам. На вход блока сортировки первый поступают символы, первый разряд которых равен нулю. Информационный сигнал "ВС" поступает из входного канала на вход данные ОЗУ блока сортировки первый. На адресные входы ОЗУ22 блока поступает информационный сигнал "АСП" через элемент ИЛИ1. По приходу из блока 8 управления сигналов "ЗП/СЧ3=1", "ВК3=0", что соответствует режиму записи, данные "ВС" записываются по своим адресам "АСП" в ОЗУ22, по приходу в блоке 8 управления (фиг.1) признака конца массива символов "ПКМ" происходит переписывание информации из ОЗУ22 в ОЗУ23 блока сортировки первый (фиг. 5). Для этого по сигналу СОБ3" из блока 8 управления предварительно счетчик адресов СЧ1 был обнулен. На вход С счетчика СЧ24 поступают синхроимпульсы "СИХ1" из блока 8 управления. По приходу сигнала "ГИ5=1" происходит подача тактовых импульсов из блока 8 управления. При этом "ЗЧ/СЧ3=0", "ВК3=0", что соответствует режиму чтения данных из ОЗУ1. По признаку наличие информации в выходных данных ОЗУ22 "КОИ=1", происходит запись данных в ОЗУ23 блока. По команде "СОБ3" из блока 8 управления предварительно реверсивный счетчик СЧ25 был обнулен. На С вход счетчика СЧ25 поступают синхроимпульсы "СИХ2". По приходу сигнала "ГИ6=1" на суммирующий вход счетчика СЧ25 поступают тактовые импульсы из блока 8 управления (фиг.5). По этим сигналам "ЗП"/СЧ4=1", "ВК4= 0", что соответствует режиму записи, происходит запись данных "ВДС" из ОЗУ22 в ОЗУ23. Если перезапись закончена, то по приходу из блока 8 управления сигналов "ЗП/СЧ4=0", "ВК4=0", что соответствует режиму чтения данных из ОЗУ23. По приходу на вычитающий вход счетчика СЧ25 сигнала "ГИ7=1" происходит считывание данных из ОЗУ23 блока сортировки первый (фиг.5). Информационный сигнал "УСП" является выходным сигналом блока. Элемент ИЛИ-НЕ определяет признак "БПС= 1" того, что буфер памяти пуст. Все данные из ОЗУ23 считаны (фиг.5).

Блок 6 сортировки второй по схемотехническому решению и порядку работы аналогичен блоку сортировки второй. Различие заключается лишь в том, что блок сортировки второй упорядочивает символы, первый разряд которых равен единице. Блок сортировки второй содержит оперативно-запоминающее устройства ОЗУ1 и ОЗУ2, счетчик адресов СЧ1, реверсивный счетчик СЧ2, элемент ИЛИ1, элемент ИЛИ2, элемент ИЛИ-НЕ. Счетчики блока СЧ1 и СЧ2 предварительно обнулены сигналом "СОБ4", на синхровходы счетчика СЧ1 подаются синхроимпульсы "СИХ1" счетчика СЧ2 синхроимпульсов "СИХ2". Эти сигналы поступают из блока 8 управления (фиг. 1). По сигналам "ЗП/СЧ5=1", "ВК5=0" (режим записи) входные данные "ВС" записываются по соответствующим адресам "АСВ". По приходу сигнала в блок 8 управления признака конца массива символов, происходит процесс переписывания информации из ОЗУ1 в ОЗУ2 блока 6 сортировки второй. По сигналу "ГИ8= 1" формируются адреса считывания. По сигналам ЗП/СЧ5=0", "ВК5=0" происходит считывание данных из памяти. При наличии информации на выходе ОЗУ1, признак "КПИ= 1", происходит запись данных в ОЗУ2 блока. По приходу сигнала "ГИ9=0" формируются счетчиком СЧ1 адреса записи данных "ВДС" в память. Сигналы "ЗП/СЧ6= 1", "ВК6= 0" (режим записи). Режим считывания данных "УМП" из ОЗУ2 происходит по сигналу "ГИ10=1", поступающему на вычитающий вход счетчика СЧ2. Сигналы "ЗП/СЧ6=0", "ВК6=0" (режим считывания информации). Элемент ИЛИ-НЕ формирует признак "БСП=1" определяющий, что буфер памяти пуст.

Блок 7 организации подстановок является выходным блоком устройства, он формирует последовательность упорядоченных символов. Каждому символу на выходе присваивается его признак. На информационные входы первой группы элементов И1.Ик33 поступает информационный сигнал "УМВ", являющийся выходом блока сортировки второй. На информационные входы второй группы элементов И1.Ик33 поступает информационный сигнал "УМП", являющийся выходом блока 5 сортировки
второй. По приходу сигнала "КУП" из блока 8 управления (фиг.1) происходит выбор выдачи упорядоченных массивов. Если "КУП=0", то на выходе блока 7 организации подстановок вначале будет формироваться массив символов, имеющих признак нуль, Д-триггер Тэн установится в нуль. Если "КУП=1", то на выходе блока будет формироваться массив символов, имеющих единичный признак, Д-триггер Тзн установится в единицу. По приходу сигнала "КПР=1" команды приема из блока 8 управления происходит прием в регистр RG29 информации с выходов группы элементов ИЛИ1.ИЛИ35. По сигналу "СИН=1" происходит подача синхроимпульсов на вход регистра RG. По приходу сигнала "КВД=1" команды выдачи из блока 8 управления происходит выдача символов из регистра RG. Количество выдачи каждого символа регистром будет соответствовать двоичному числу, записанному в счетчик СЧ30. Сигналом СУ "0", установка в нуль, счетчик СЧ предварительно был обнулен. Информационный сигнал "ЧПС" частота повторения символов является входом счетчика СЧ. По приходу сигнала из блока 8 управления "ГИ11=1" на вычитающий вход счетчика СЧ30 происходит вычитание единицы из двоичного значения "ЧПС". Элемент ИЛИ контролирует выдачу количества символов из регистра 29. Если "КВС=0", то выдачу данного символа прекратить. Если "КВС=1", то данный символ выдавать до тех пор, пока "КВС" не будет равен нулю. Информационный сигнал "УМС" является внешним выходом устройства. Сигнал "КЗС" код знака символа соответствует знаку символа "КЗС=КУП". ТТТ1 ЫЫЫ2 ЫЫЫ4 ЫЫЫ6

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

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