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

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

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

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

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

Задача заключалась в следующем:
1) расширить функциональные возможности устройства сортировки слов.

2) упростить алгоритм блока управления,
3) повысить надежность и производительность работы сортировочного устройства.

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

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

C первого по шестой управляющие входы первого блока хранения упорядоченных слов соединены соответственно с семнадцатым по двадцать второй управляющими выходами блока управления, n+1 информационный выход входного информационного канала соединен с первым информационным входом n-го блока поиска вхождений, второй и третий информационные входы которого соединены соответственно с третьим и четвертым информационными выходами блока управления, второй управляющий выход которого соединен с управляющим входом n-го блока поиска вхождений, управляющий выход которого соединен со вторым управляющим входом блока управления.

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

ВхИК - входной информационный канал выполняет роль параллельного интерфейса, служит для передачи слов из внешнего источника (сеть ИНТЕРНЕТ, текстовые редакторы и т.д.) в устройство сортировки слов.

БПВ - блок поиска вхождений служит для определения слов, имеющих одинаковую первую букву.

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

БОРС - блок обработки результатов сравнения служит для анализа результатов поиска на минимальное или максимальное значение в модуле АЗУ.

БХУС - блок хранения упорядоченных слов служит для записи и хранения в ОЗУ блока отсортированных слов текста.

БУ - блок служит для управления устройством.

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

Все это привело к созданию ассоциативных запоминающих устройств АЗУ. Слова в АЗУ отыскиваются по их признакам, т.е., по их содержанию, а не по адресам ячеек, в которых записаны эти слова. В АЗУ, параллельных по словам и последовательных по разрядам, для обработки данных используются последовательные алгоритмы. Это позволяет проводить операцию на равенство - искомые слова равны заданному признаку. АЗУ могут функционировать в двух основных режимах: поисковом и вычислительном. В режиме поиска обычно требуется локализовать и считать из памяти все слова, подчиняющиеся определенным условиям:
1) равные, больше или меньше;
2) поиск минимального, максимального значения;
3) поиск величин, заключенных в заданном интервале;
4) поиск ближайшего снизу (сверху) значения;
5) упорядоченная выборка (сортировка);
6) поиск на основе булевых функций и т.д. [1, 2].

Ассоциативная память характеризуется рядом особенностей, к ним относятся:
1) большая емкость, которая может наращиваться путем добавления новых модулей;
2) возможность работы с записями переменной длины, состоящими из строк символов;
3) наличие средств для поиска по различным спецификациям и их сочетаниям [1].

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

Функции анализа признаков полученных после обработки информации в модуле АЗУ выполняет третий блок каждой секции. Найденные слова записываются в оперативно-запоминающее устройство четвертого блока каждой секции. Все слова в строгом соответствии с порядком записи хранятся в ОЗУ. Для дальнейшей обработки слов, упорядоченных в алфавитном порядке и хранящихся в ОЗУ, осуществляется перезапись снова этих слов в АЗУ каждой секции для выполнения других операций, например архивации слов, подсчета одинаковых слов, определения заданных букв в определенной позиции в словах и т.д.

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

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

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

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

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

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

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

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

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

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

2. СУП - сигналы управления работой регистра RG блока поиска вхождений, поступающие из блока управления.

3. РВ - сигнал равенства входных величин, поступающий с выхода компаратора блока поиска вхождений.

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

5. УС - сигнал управления режимом работы электронного ключа ЭК блока поиска вхождений.

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

7. УР - управляющие сигналы, поступающие на вход блока ассоциативного запоминающего устройства. Сигналы управляют работой АЗУ, устанавливают режимы работы ассоциативного запоминающего устройства.

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

9. СЛ - информационный сигнал, соответствующий выходному слову модуля АЗУ блока ассоциативного запоминающего устройства. Сигнал поступает на вход оперативно-запоминающего устройства блока хранения упорядоченных слов.

10. УСЛ - упорядоченные слова, которые переписываются из ОЗУ блока хранения упорядоченных слов в модуль АЗУ блока ассоциативного запоминающего устройства.

11. ПС АЗУ - управляющий сигнал, признак просмотра всей длины строк модуля АЗУ.

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

13. АЗС - адреса (номера) строк в модуле АЗУ, в котором необходимо удалить слова во избежании ситуации "зацикливание" при упорядочении информации.

14. РАЗ - управляющий сигнал разрешения работы мультиплексора блока обработки результатов сравнения, поступающий из блока управления.

15. ЗАП - управляющий сигнал, соответствующий только одному минимальному или максимальному значению, обнаруженному в строках модуля АЗУ.

16. ЗАС - сигнал разрешения записи слова в оперативно-запоминающее устройство блока хранения упорядоченных слов. Сигнал поступает на вход блока управления.

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

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

19. СБР - сигнал сброса в нулевое состояние двоичного счетчика Сч1 блока обработки результатов сравнения.

20. ОБН - сигнал обнуления двоичного счетчика Сч2 блока обработки результатов сравнения.

21. ЕДН - выходной сигнал мультиплексора блока обработки результатов сравнения.

22. ВК - сигнал выбора кристалла, поступающий на вход ОЗУ блока БХУС. Сигнал управляет работой ОЗУ.

23. Сч/Зп - управляющий сигнал считывания или записи информации ОЗУ блока БХУС. Сигнал управляет режимами работы ОЗУ.

24. ИМ - прямоугольные импульсы, поступающие на суммирующий вход двоичного счетчика Сч3 - счетчика столбцов для формирования адреса столбцов в ОЗУ блока БХУС.

25. ИМП - прямоугольные импульсы, поступающие на суммирующий вход двоичного счетчика Сч4 - счетчика строк для определения адреса строк в ОЗУ блока БХУС.

26. ССБР - сигнал сброса в нулевое состояние счетчика Сч3 блока БХУС.

27. СБО - сигнал обнуления счетчика Сч4 блока БХУС.

28. m - длина строк в модуле АЗУ.

29. j - текущее значение счетчика длины строк в модуле АЗУ.

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

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

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

В блоке 5 алгоритма на вход блока управления поступает текстовая информация по входному информационному каналу по команде: БУ:=ВхИК для определения разделителя между словами текста - пробела.

В блоках 6, 7, 8, 9 алгоритма сформирован цикл, в котором происходит распределение слов текста по секциям. В каждую секцию записываются слова, имеющие одинаковую первую букву. В этих секциях происходит сортировка слов по первой букве.

В блоке 6 алгоритма анализируется признак конца текста КТ. Если признак конца текста КТ еще не пришел (слова текста поступают) - выход НЕТ блока, то на входы всех блоков поиска вхождений устройства поступает информация по входному информационному каналу. Если обнаружен признак конца текста КТ (текст окончен) - выход ДА блока, то происходит выход из цикла и осуществляется переход на блок 10 алгоритма.

В блоке 7 алгоритма на входы блоков поиска вхождений устройства поступает информация из входного информационного канала по команде: БПВi:=ВхИК.

В блоке 8 алгоритма происходит анализ сигнала сравнения PBi. Если сигнал равен единице - выход 1 блока, то в соответствующий i блок ассоциативного запоминающего устройства записывается слово, с определенной первой буквой, код которой поступает на второй вход компаратора блока (фиг.2). Если сигнал PBi равен нулю - выход 0 блока, то происходит переход на блок 6 алгоритма.

В блоке 9 алгоритма происходит загрузка модулей АЗУ блоков ассоциативных запоминающих устройств словами, имеющими одинаковую первую букву по команде: БАЗУ1:=СОПБ1 (фиг.3).

В блоке 10 алгоритма по командам: j:=1; m:=9 происходит установка начальных значений во всех ассоциативных запоминающих устройствах. Число m означает номер столбца в АЗУ, с которого начинается считывание столбцов. Первая буква слов расположена с первого номера по восьмой. Вторая с девятого по шестнадцатый и т.д. Целесообразно обработку производить, начиная с девятого столбца, т.е. со второй буквы.

В блоке 11 алгоритма на модуль АЗУ блоков БАЗУ устройства поступают сигналы управления работой памяти - УРi. Для установки режима поиска минимума (максимума) в модуле АЗУ необходимо установить соответствующий режим работы [1,4]. На вход счетчика внешнего адреса ВнАд - Сч5 DD.5 из блока управления поступают от генератора тактовых импульсов ГТИ - прямоугольные импульсы (фиг.3) для формирования адреса в модуль АЗУ. Процесс управления работой модуля АЗУ, а также формирование внешних адресов ВнАд осуществляется по командам: БАЗУi:=УРi, БАЗУi:=ГТИi.

В блоке 12 алгоритма по команде: MHXi:=PA3i на управляющий вход мультиплексора МИХ DD.20 блока обработки результатов сравнения подается сигнал из блока управления - сигнал разрешения работы мультиплексора РА3 (стробирующий вход) (фиг.4).

В блоках 13, 14, 15, 16, 17 сформирован цикл, по которому обрабатываются (просматриваются) все строки модуля АЗУ. В строках модуля записаны слова. Каждый символ кодируется восмью разрядами. Слова имеют разную длину.

В блоке 13 алгоритма анализируется условие m<=j, по которому происходит выполнение процесса просмотра модуля АЗУ - выход - НЕТ, или осуществляется выход из цикла считывание данных из АЗУ - выход - ДА. Если выполняется условие выход по ДА, то происходит переход на блок 18 алгоритма. В случае выхода по НЕТ выполняется цикл "считывание столбцов модуля АЗУ".

В блоке 14 алгоритма на управляющие входы мультиплексора МИХ подаются сигналы управления АЗС. Работа мультиплексора заключается в последовательном соединении всех входов ПСВ элемента с единственным выходом - ЕДН. В результате соединения (коммутации) анализируется состояние каждого входа. Операция осуществляется для обнаружения высокого потенциала, обнаружения единицы на входе мультиплексора. Эта операция осуществляется по команде: МИХi:=АЗСi (фиг.4).

В блоке 15 алгоритма происходит анализ состояния сигнала ЕДН - единицы на выходе мультиплексора МИХ. Если сигнал ЕДН равен нулю выход блока - 0, то осуществляется переход на блок 17 алгоритма. Если сигнал ЕДН равен единице выход 1 блока, то происходит переход на блок 16 алгоритма.

В блоке 16 алгоритма по команде Счi:=ГИ на суммирующий вход двоичного счетчика поступают прямоугольные импульсы из блока управления. В этом случае происходит подсчитывание прямоугольных импульсов, поступивших на вход счетчика (фиг.4).

В блоке 17 алгоритма происходит увеличение счетчика j на единицу по команде: j:=j+1. По выходу блока осуществляется переход на блок 13 алгоритма.

В блоке 18 алгоритма анализируется состояние сигнала ЗАП. Если сигнал ЗАП равен нулю выход 0, то происходит переход на блок 24 алгоритма. Если ЗАП равен единице - выход 1, то осуществляется переход на блок 19 алгоритма, где произойдет запись слова в ОЗУ блока БХУС (фиг.4, 5).

В блоке 19 алгоритма происходит формирования сигналов из блока управления для записи информации в ОЗУ i-й секции. Сигнал разрешения для записи информации поступает из блока управления по командам: BKi:=0, Сч/Зпi:=0. На управляющие входы поступают нулевые значения, что соответствует режиму записи в ОЗУi-секции устройства очередного слова (фиг.5).

В блоке 20 алгоритма по командам: ОЗУi:=Ад Стi, ОЗУi:=Ад Стрi, происходит подача на адресные входы ОЗУ i-й секции адресов строк и адресов столбцов с выходов двоичных счетчиков Сч3 и Сч4 (фиг.5) для записи информации в ОЗУ.

В блоке 21 алгоритма по команде ОЗУi:=СЛk происходит подача на входную шину для записи в i-блок ОЗУ устройства очередного слова СЛk из блока ассоциативного запоминающего устройства.

В блоке 22 алгоритма на адресные входы ассоциативного запоминающего устройства i-й секции поступает внешний адрес ВнАд с выхода счетчика Сч5 блока БАЗУ по команде: АЗУi:=ВнАд (фиг.3).

В блоке 23 алгоритма по команде: A3yi:=del СЛk происходит удаление слова из АЗУ i-й секции слова по установленному внешнему адресу ВнАд во избежание процесса "зацикливание" (фиг.3). По выходу этого блока происходит переход на блок 10 алгоритма.

В блоке 24 алгоритма происходит анализ сигнала ПС АЗУ - признака просмотра длины модуля АЗУ. Если вся длина модуля АЗУ просмотрена - выход ДА, то осуществляется переход на блок 26 алгоритма. Это означает, что просмотрены все символы слов, которые хранятся в модуле АЗУ. Если признак просмотра длины модуля АЗУ - ПС АЗУ равен нулю - выход НЕТ, то происходит переход на блок 25 алгоритма. В этом случае процесс "считывание столбцов модуля АЗУ" продолжается.

В блоке 25 алгоритма по команде: m:=m+8 осуществляется увеличение состояния параметра m на величину восемь т.е. байта - на количество двоичных разрядов символа. Этот процесс осуществляется для того, чтобы можно было бы просмотреть двоичный код в столбцах модуля АЗУ очередного символа слова.

В блоке 26 алгоритма анализируется признак просмотра всей информации в модуле - АЗУ ПУСТ. Если признак равен нулю - выход НЕТ блока, то это означает, что информация имеется в модуле АЗУ, процесс просмотра будет продолжен. В этом случае осуществляется переход на блок 19 алгоритма. Если признак АЗУ ПУСТ равен единице - выход ДА, то это означает, что модуль АЗУ пуст т.е. вся информация в нем просмотрена (фиг.3).

В блоке 27 алгоритма по команде: БАЗУi:=УСi осуществляется переписывание всех отсортированных слов из ОЗУ блока хранения упорядоченных слов в модуль АЗУ блока ассоциативных запоминающих устройств для проведения дальнейших поисковых операций (фиг.1).

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

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

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

Блок 1 поиска вхождений БПВ (фиг.2) содержит электронные ключи ЭлКл, компаратор КОМ и регистр RG. Функция блока поиска вхождений заключается в следующем: из всех слов текста необходимо отобрать те слова, у которых одинаковая первая буква. Этот блок сортирует слова по первой букве. На фиг.2 показана структурная схема блока БПВ. На управляющий вход электронного ключа ЭлКл DD. 11 поступает управляющий сигнал УС из блока управления (фиг.1). На информационные входы электронного ключа ЭлКл поступает первая буква слова из входного информационного канала ВхИК. Выходная информация с выхода электронного ключа ЭлКл поступает на первый вход узла сравнения - компаратора КОМ DD. 12 (фиг.2). На второй вход компаратора КОМ DD.12 поступает двоичный код первой буквы (код ASCII - международная американская стандартная кодировка символов).

Перед началом работы устройства в регистр RG DD.13 блока БПВ, после обнуления и установки к работе информационным сигналом СУП1, загружается код буквы - КПБ1 из блока управления (фиг.1). Если управляющий сигнал УС электронного ключа ЭлКл равен нулю, то информация на первый вход компаратора КОМ не поступает, электронные ключи заперты. Если управляющий сигнал равен единице, то в этом случае электронные ключи ЭлКл DD.11 будут открыты, информация поступит на вход компаратора КОМ DD.12.

Компаратор КОМ DD.12 работает в режиме сравнения на равенство. Если выходной сигнал компаратора КОМ - РВ равен нулю, то сравнения не произошло, входные величины не равны между собой. Если сигнал РВ равен единице, то в этом случае входные коды равны между собой. Определено слово из текста, которое имеет заданную первую букву. Это слово поступает на вход блока ассоциативного запоминающего устройства - БАЗУ и записывается в модуль АЗУ по внешнему адресу (фиг.3). Сигнал РВ поступает на вход блока управления.

Блок 2 ассоциативного запоминающего устройства (фиг.3) содержит модуль АЗУ DD.16, регистр аргумента поиска DD.17, селектор адреса и дешифратор DD. 15, память фиксации реакций DD.18, анализатор многократного совпадения DD. 19, двоичный счетчик Сч5 DD.14. Вначале работы устройства двоичный счетчик Сч5 DD. 14 обнуляется управляющим сигналом УСО, который поступает из блока управления. Режим работы модуля АЗУ устанавливается на поиск минимального или максимального значения. В модуле АЗУ записываются все слова с одинаковыми первыми буквами. Поэтому поиск минимального или максимального значения следует проводить, начиная со вторых букв слов.

На первый вход селектора адреса и дешифратора поступает информационный сигнал СОПБ из блока поиска вхождений (фиг.1). На второй вход поступает информационный сигнал УСЛ. Это упорядоченные слова записываются из ОЗУ блока БХУС для дальнейшей обработки. На третий вход этого блока поступает внешний адрес ВнАд с выхода двоичного счетчика Сч5 DD.14 (фиг.3). По этому адресу входная информация СОПБ записывается в модуль АЗУ. На суммирующий вход счетчика Сч5 DD.14 поступают сигналы прямоугольных импульсов ГТИ из блока управления. Счетчик подсчитывает количество прямоугольных импульсов на входе и в результате этого формируется внешний адрес в двоичном коде, который поступает на вход селектора адреса и дешифратора.

На вход регистра аргумента поиска DD.17 поступает из блока управления информационный сигнал УР, который устанавливает режим работы модуля АЗУ (фиг. 3). Перед началом поиска во все разряды памяти реакций заносятся нули: если на одном из шагов выявляется слова, совпадающие с режимом поиска, то соответствующие им разряды устанавливаются в "1". Те разряды, которые были однажды установлены в "1", далее не изменяют своего значения независимо от результатов последующих сравнений [1].

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

Анализатор многократного совпадения DD.18 выполняет функцию приоритетного искателя и состоит из буферных регистров [1]. На выходе этого блока при поиске минимального или максимального значения в модуле АЗУ формируются признаки обработки слов - информационный сигнал - ПСВ (фиг.3). На выходе этого же блока формируется сигнал ПС АЗУ, который означает признак просмотра всех столбцов в модуле АЗУ. Этот сигнал поступает на вход блока БОРС (фиг. 1).

Если сигнал ПС АЗУ равен нулю, то процесс поиска продолжается. Если сигнал равен единице, то необходимо записать в ОЗУ блока БХУС все слова из модуля АЗУ, у которых признак поиска ПСВ остался в нулевом состоянии, из модуля АЗУ удалить эти слова. Информационный сигнал ПСВ поступает на вход мультиплексора МИХ блока обработки результатов сравнения для дальнейшего анализа (фиг. 1, 3, 4). Выходной информацией модуля АЗУ является сигнал СЛ - те слова, которые поступают на вход ОЗУ блока БОРС (фиг.1).

Блок 3 обработки результатов сравнения БОРС (фиг.4) содержит мультиплексор МИХ DD. 20 с инверсными входами, двоичный счетчик Сч1 DD.21, двоичный счетчик Сч2 DD.24, логический элемент И DD.22 на два входа, логический элемент И DD.23 на три входа с одним инверсным входом, логический элемент И DD. 25 с инверсными входами с одним прямым входом. Работа блока БОРС начинается с подачи сигнала разрешения РАЗ, равного единице, из блока управления на управляющий вход мультиплексора МИХ DD.20. На информационные входы мультиплексора МИХ подается сигнал ПСВ с выхода анализатора многократного совпадения блока БАЗУ (фиг.3, 4).

Счетчик Сч1 DD.21 блока формирует управляющие сигналы АЗС, которые поступают на вход мультиплексора МИХ DD.20 (фиг.4). Перед началом работы устройства все двоичные счетчики установлены в нулевое состояние. Счетчик Сч1 DD. 21 обнуляется сигналом СБР - сброс, поступающего из блока управления. На второй вход счетчика Сч1 DD.21 поступают из блока управления тактовые импульсы ТИ на суммирующий вход счетчика. При поступлении управляющих сигналов АЗС на входы мультиплексора МИХ DD.20 происходит последовательное соединение каждого входа с одним выходом ЕДН.

Если на выходе ЕДН будет единица, то откроется логический элемент И DD. 23, но при нулевом значении сигнала ПС АЗУ (просмотра строк модуля АЗУ). На выходе логического элемента И DD.23 будет высокий потенциал - единица. На второй прямой вход логического элемента И DD.23 из блока управления поступают прямоугольные импульсы ГИ. При открытом логическом элементе И DD.23 прямоугольные импульсы ГИ поступают на вход суммирующего входа счетчика Сч2 DD. 24. Перед началом текстовой обработки, двоичный счетчик Сч2 DD.24 был обнулен сигналом ОБН, который поступил из блока управления.

Двоичный счетчик Сч2 DD.24 предназначен для подсчета прямоугольных импульсов ГИ, которые поступили на суммирующий вход. Выходная информация из двоичного счетчика Сч2 DD.25 поступает на вход логического элемента И DD.25, который выполняет функцию дешифратора. Эта функция заключается в поиске одной единицы, поступившей на вход элемента. Если на прямой вход логического элемента И DD.25 поступила единица, а на все остальные входы поступили нули, то в этом случае на выходе будет установлена единица. Выходной сигнал ЗАП будет равен единице. Это означает, что в модуле АЗУ найдена буква, которая имеет минимальное (максимальное) значение.

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

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

Блок 4 хранения упорядоченных слов БХУС (фиг.5) содержит оперативно-запоминающее устройство ОЗУ DD.28. Каждое ОЗУi работает совместно с двумя двоичными счетчиками Сч3 DD.26 и Сч4 DD.27. Этот блок предназначен для хранения упорядоченных слов текста. Счетчики Сч3 и Сч4 формируют адреса столбцов и адреса строк. По этим адресам информация записывается в оперативно-запоминающее устройство. На фиг.5 представлен вариант технической реализации блока БХУС и показаны связи с двоичными счетчиками Сч3 и Сч4. Все остальные блоки БХУС устройства имеют аналогичную структуру. На фиг.5 представлено оперативно-запоминающее устройство ОЗУ DD.28, двоичный счетчик, формирующий адреса столбцов ОЗУ-Сч3 DD. 26, двоичный счетчик формирующий адреса строк ОЗУ-Сч4 DD.27.

Двоичные счетчики вначале работы устройства обнулены управляющими сигналами ССБР1, СБ01, поступающие из блока управления. На суммирующие входы счетчиков поступают прямоугольные импульсы ИМ1, ИМП1 из блока управления. Счетчики формируют адреса строк и столбцов, по которым будут записаны слова СЛ1 из блока БАЗУ (фиг. 1), поступающие на вход оперативно-запоминающего устройства ОЗУ DD.28. Входным сигналом СЛ1 является обнаруженное слово в блоке ассоциативного запоминающего устройства. Входной сигнал поступает на входную шину ОЗУ1. Сигналы управления оперативно-запоминающего устройства ОЗУ DD.28 считывания/запись и выбора кристалла соответственно при записи принимают значения Сч/Зп1= 0, ВК1=0. Выходом ОЗУ1 является информационный сигнал УСЛ1 (фиг.5).

Блок 10 управления синтезируется на основе ГСА алгоритма управления (фиг. 6) известным способом. Размеченная ГСА работы блока 10 управления приведена на фиг.7, где обозначено:
Логические условия:
Х1:"УОО"
Х2: "ПУСК"
Х3: "КТ"
Х4: "РВi"
Х5: "m<=j"
Х6: "ЕДН"
Х7: "ЗАП"
Х8: "ПС АЗУ"
Х9: "АЗУ ПУСТ"
Операторы:
Y1: "СБРОС:=1"
Y2: "БУ:=ВхИК"
Y3: "БПВi:=ВхИК"
Y4: "БАЗУ:=СОПi"
Y5: "j:=1"
Y6: "m:=9"
Y7: "БАЗУi:=УPi"
Y8: "БАЗУi:=ГТИi"
Y9: "МИХi:=РАЗi"
Y10: "МИХi:=АЗСi"
Y11: "Счi:=ГИ"
Y12: "j:=j+1"
Y13: "ВКi:=0"
Y14: "Сч/Зпi:=0"
Y15: "ОЗУi:=Ад Стi"
Y16: "ОЗУi:=Ад Стрi"
Y17: "ОЗУi:=СЛk"
Y18: "АЗУi:=ВнАДi"
Y19: "АЗУ:=del СЛk"
Y20: "m:=m+8"
Y21: "БАЗУi:=УСЛi"
Источники информации
1. Кохонен Т. Ассоциативные запоминающие устройства: Пер с англ. - М.: Мир, 1982. - 384 с., ил.

2. Преснухин Л.Н., Нестеров П.В. Цифровые вычислительные машины: Учеб. пособие для студентов вузов. - М.: Высш. школа, 1981 - 511 с., ил.

3. Самофалов К.Г., Корнейчук В.И., Тарасенко В.П. Цифровые электронные вычислительные машины. - Киев: Вища школа. Головное изд-во, 1983. - 455 с.

4. Цифровые и аналоговые интегральные микросхемы: Справочник под ред. С. В.Якубовского. - М.: Радио и связь, 1990. - 496 с., ил.

5. Большие интегральные схемы запоминающих устройств: Справочник/ А.Ю. Гордонов, Н.В.Бекин, В.В.Цыркин и др.; Под ред. А.Ю.Гордонова и Ю.Н.Дбкова. - М.: Радио и связь, 1990. - 288 с., ил.

6. Применение интегральных микросхем в электронной вычислительной технике: Справочник / Р.В.Данилов, С.А.Ельцова, Ю.П. Иванов и др.; Под. ред. Б. Н.Файзулаева, Б.В.Тарабрина. - М.: Радио и связь, 1987. - 384 с., ил.

7. Популярные цифровые микросхемы: Справочник. 2-е изд., испр. - Челябинск: Металлургия, Челябинское отд., 1989. - 352 с., ил.

8. Патент N 2067315 (прототип).

9. Патент N 2128855 (аналог).

10. Патент N 2067317 (аналог).

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

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