Устройство для определения длины строки символов

Союз СоветскихСоциапистичвскихРеспублик АВТОРСКО СВИДЕТЕЛЬС3) Лрноритет нзебретенннткрытнй681.32 (088.8) публиковано 2 З 11 82, БвллетенДата опубликования описания 23(72) Авторы изобретения и Е. В. Быч П. Селез Заявитель СТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ДЛИНЫ СТРО 1(И СИМВОЛОВ 5 Изобретение относится к вычислительной технике и может быть использовано при построении быстродействующих устройств, ориентированных на обработку символьной информации.В таких устройствах возникает необходимость в выполнении операции определения длины 1. строки символов, которая равна количеству символов, размещенных между началом строки и определенным терминальным ( фиксирующимю конец строки) символом. Указанная операция употребляется в языках программирования высокого уровня. Строка символов, в общем случае, может размещаться в нескольких машинных словах. Одно полное машинное слово содержит и символов. Строка может начинаться с любой символьной позиции в машинном слове. Положение первого символа строки задается его адресом Ь в слове(базой строки ), Адрес отсцитывается от левой границы слова, причем 0ЬИзвестно устройство, содержащее регистр машинного слова, регистр тер-, минального символа, регистр промежуточного результата, арифметико-логический узел и блок управления. Выходы регистров подсоединены к входам арифметико-логического узла, выход которого подключен к входу регистра промежуточного результата. Выход блока управления связан с управляющим входом арифметико-логического узла. В этом устройстве операция определения длины строки может быть выполнена путем последовательного выделения символов строки из машинных слов, сравнения их с терминальным символом и подсчета числа операций сравнения, для которых зафиксировано неравенство символов 1 .Наиболее близким к предлагаемому устройству техническим решением является устройство, ориентированное на обработку символов (байтов) и содержащее регистр машинного слова,976438 сумматор, регистр терминального сим" вола, регистр промежуточного результата, узел сравнения двух байтов и блок управления, причем вход регистра терминального символа соединен с входом терминального символа устройства, а информационный вход регистра машинного слова соединен с входом машинного слова устройства, входы узла сравнения двух байтов подключены к выхо- ф дам регистра машинного слова и регистра терминального символа, а его выход - к входу блока управления, Выход регистра промежуточного результата связан с входом сумматора, выход 1 которого объединен с входом регистра промежуточного результата и подключен к первому выходу устройства, Первый выход блока управления соединен с управляющим входом регистра промежуточ- о ного результата, второй выход - с управляющим входом регистра машинного слова, а третий выход подключен к второму выходу устройства, Функции узла сравнения в этом устройстве выполняет 2 блок пересылки при реализации,логической Функции неравнозначности. При выполнеь ии операции определения длины ,строки символов в регистр машинного слова заносятся последовательные Фраг-з, менты строки символов. Из этого регистра символы последовательно передаются на один из входов узла сравне- , ния, на второй вход которого постоянно подан терминальный символ. Если35 :символы не равны, то с помощью сумматора на единицу увеличивается содержимое регистра промежуточного результата. При равенстве символов выполнеОние операции завершается, регистр результата содержит результирующее значение2 1 .Последовательный характер анализа символов строки и подсчета количества символов в ней обуславливают низкое45 быстродействие известного устройства, что является его недостатком.Цель изобретения - повышение быст родействия.Эта цель достигается тем, что в устройство, содержащее сумматор, регистр машинного слова, регистр терминального символа, регистр промежуточного результата, узел сравнения и ,блок управления, причем информационный вход регистра терминального символа соединен с входом терминального символа устройства, а информационный вход регистра машинного слова соединен с входом машинного слова устройства, введены блок формирования маски и блок формирования адреса крайней единицы, а количество узлов сравнения равно числу символов в машинном слове, первый вход каждого узла сравнения соединен с выходом регистра машинногслова, второй вход - с выходом блока формирования маски, третий вход - с выходом регистра терминального символа; а выход - с входом блока Формирования адреса крайней единицы, первый выход которого подключен к первому входу сумматора, а второй выход соединен с первым входом блока управления и выходом окончания операции устройства, второй вход блока управления, управляющий вход регистра терминального символа и первый управляющий вход регистра промежуточного результата подключены к первому входу .синхронизации устройства третий вход блока управления, управляющий вход регистра машинного слова и второй управляющий вход регист- ра промежуточного результата подключены к второму входу синхронизации устройства, третий управляющий вход регистра промежуточного результата, управляющий вход блока формирования маски и управляющий вход сумматора подключены к выходу блока управления, первый информационный вход регистра промежуточного результата подключен к входу установки базы строки устройства, а .выход связан с информационным входом блока Формирования маски и вторым входом сумматора, выход которого соединен с вторым информационным входом регистра промежуточного результата и подключен к выходу значения длины строки устройства.Кроме того, блок управления содержит двухразрядный счетчик, элемент НЕ и элемент И, причем счетный вход сче чика соединен с выходом элемента И, первый вход которого соединен с третьим входом блока, второй вход элемента И соединен с инверсным выходом старшего разряда счетчика, который подключен к выходу блока, третий вход элемента И соединен с выходом элемента НЕ, вход которого подключен к первому входу блока, вход .установки начального значения счетчика соединен с вторым входом блока.Блок Формирования адреса крайней единицы содержит два коммутатора, два элемента ИЛИ-НЕ, элемент ИЛИ, два эле9764 мента НЕ и три элемента И, причем входблока подключен к входам первого элемента ИЛИ-НЕ, элемента ИЛИ, информационным входам первого коммутатора,выход которого соединен с входом второго элемента ИЛИ-НЕ и с информационными входами второго коммутатора, выход которого подключен к входу первого элемента НЕ, выход элемента ИЛИсоединен с первыми входами элементовИ и входам второго элемента НЕ, второй вход первого элемента И соединенс выходом первого элемента ИЛИ-НЕ, который соединен с управляющим входомпервого коммутатора, второй вход вто фрого элемента И соединен с выходомвторого элемента ИЛИ-НЕ, который соединен с управляющим входом второго коммутатора, второй вход третьего элемента И подключен к выходу первого элемента НЕ, выходы элементов И и второгоэлемента НЕ соединены с выходами блока,Блок формирования маски содержитсемь элементов ИЛИ, четыре элементаИ и элемент НЕ, причем вход элемента 2 ЗНЕ соединен с управляющим входом блока, а его выход подключен к первымвходам первого, второго и третьегоэлементов ИЛИ, вторые входы которыхсоединены с информационными входами щблока, выход первого элемента ИЛИ соединен с первыми входами четвертогоэлемента ИЛИ и первого элемента И,вторые входы которых и первые входывторого элемента И и пятого элементаИЛИ подключены к выходу второго эле -мента ИЛИ, первые входы третьего элемента И и шестого элемента ИЛИ подключены к выходу четвертого элементаИЛИ, первые входы четвертого элемента И и седьмого элемента ИЛИ подключены к выходу первого элемента И, вто.рые входы второго, третьего, четвертого элементов И, пятого, шестого,седьмого элементов ИЛИ подключены квыходу третьего элемента ИЛИ, а ихвыходы соединены с выходами блока.На фиг. 1 показана блок-схема устройства ; на фиг. 2 - блок-схема блока формирования адреса крайней единиИцы; на фиг 3 - блок-схема блока формирования маски; на фиг. 4 - принципработы устройства,Устройство для определения длиныстроки символов содержит регистр 1машинного слова, регистр 2 терминальИного символа, регистр 3 промежуточного результата, блок 4 формированиямаски, однотипные узлы 5 сравнения,38 бблок 6 формирования адреса крайнейединицы, сумматор 7, блок 8 управления.Блок 6 формирования адреса крайней единицы содержит первый коммутатор 10, первый элемент ИЛИ-НЕ 11, второй элемент ИЛИ-НЕ 12, элемент ИЛИ 13,первый элемент НЕ 14, второй элементНЕ 15, первый, второй и третий элементы И 16-18 соответственно.Блок 4 формирования маскисодержитпервый, второй, третий, четвертый, пятый, шестой и седьмой элементы ИЛИ 19 - 25, первый, второй, третий, четвертый элементы И 26 -29, элемент НЕ 30Регистрмашинного слова обеспечивает хранение и символов, 5 л,Б. ,символы в регистре нумеруетсяслева направо), причем п=2 К. Каждыйсимвол в том числе и хранящийся врегистре 2 терминального символа) содержит 1 двоичных разрядов.Блок 4 формирования маски обеспечивает формирование н-разрядного двоичного слова К=в , в, л маски),содержащего единственную группу двоичных разрядов, имеющих единичное значение (разряды в маске нумеруются слеванаправо). Номер разряда слова И, соответствующего положению крайней левойединицы в указанной группе, определяется обратным кодом К-разрядного двоичного числа С, поступающего на информационный вход блока 4, а положение крайней правой единицы постояннои совпадает с крайним правым разрядомслова И,ил =1), Например, если С == 011, Блок 4 работает указанным образом при единичном значении сигналаР на его управляющем входе. Если Р=0,то щ =щ = =щи =1, Число С снимао л- = и л=ется с К младших разрядов регистра 3промежуточного результата.Блок 4 формирования маски представляет собой многовыходную комбинационную логическую схему, аргументами которой являются разряды Со, Сл СКдвоичного числа С С " старший разряд) и признак р, На входе, блока формируются сигналы С =С 1=0, М.4 л Р фЛогические функции, определяющие значения сигналов на выходах блока, могут бьть представлены в общем видеш,=;оК 3 =О, и; щи л =1Ф97643 9зультатам сравнения символов Бв, 6+, , 5с терминальным символомПусть терминальный символ для рассматриваемой строки символов расположен на символьной позиции д в регистре 1 (дЬ), В этом случае 5 =5 вследствие чего о=1 (крайняя левая единица в слове 0), и на выходе блока 6 Формирования адреса крайней еди о ниЦы устанавливаются значения Е=д, 1, =1.Сумматором 7 вырабатывается значение 1. /г+Г+Р / вод=2 = ЕЬоьР +1/иод= 2"= /2 -Ь + до 8=2" = д-Ь, опреде ляющее результирующее значение длины строки символов, и выполнение операции заканчивается (Г=1).Если терминальный символ для рассматриваемой строки в регистре 1 от- го сутствует, то все разряды слова ( имеют нулевое значение, Е=2 ", и на выходе сумматора вырабатывается чис- ЛО :Х":ч. Ьф оа: определяющее количество символов заданной строки содержащихся в регистре 1. Признак Г = 1 =0, и выполнение операции продолжается. Импульсным сиг-зо налом о. производится .занесение в регистр 1 очередного фрагмента стро.ки символа. В результате воздействия этого сигнала на блок 8 управления на . его выходе устанавливается значение р = 0. В регистр 3 переносится значение Ь с выхода сумматора 7, Все раз/ряды маски И теперь имеют единичное значение. Если в принятом фрагменте отсутствует терминальный символ, то 4 о все разряды слова 0 имеют нулевое значение, Е=2", а в сумматоре 7 производится сложение числа символов, зафиксированных в предыдущем фрагменте строки (С), и числа Е, определяющего аз количество символов в слове, которое хранится в регистре 1. Выполнение операции продолжается ,Г=1 =0), причем сигналом в регистр 1 заносится очередной фрагмент строки символов, а в р регистр 3 передается значениес выхода сумматора. Если в последующих машинных словах, заносимых в регистр1, отсутствует терминальный символ, то описанный цикл работы устройства я . повторяется для каждого из этих слов, вследствие чего в регистре 3 накапливается число, соответствующее колицест 8 10ву переданных в устройство символовстроки. Наконец, если в регистр 1 за"несен Фрагмент, содержащий терминальный символ (например, на позиции а,Оасп),.то на выходе блока 6 фор"мирования адреса крайней единицы вырабатывается значение Е = а, на выходе сумматора 7 устанавливается результирующее значение параметра Ь , и выполнение операции завершается (Г=1).Работу устройства продемонстрируемна примере определения длины строкисимволов (Фиг. 2). Здесь принято п=ч- база строки Ь=2 (двоичный код 10),В качестве терминального символа использован пробел. В таблице указанызначения сигналов в устройстве для трехмашинных слов и , и , и , последовательно помещаемых в регистр машинногослова 1. Значение =7, вырабатываемоев третьем цикле работы устройства, определяет результат операции.Если длина 1. строки символов, определяемая с помощью устройства, должна быть на единицу меньше количествасимволов в ней, сигнал р, поступающийв сумматор 7, должен постоянно иметьнулевое значение (этот сигнал можнов сумматор не подавать),Если строки, длина которых должнабыть определена, всегда выравнена погранице машинного слова (в этом случае Ь=0), то из оассмотренного устройства можно исключить формирователь 4маски и блок 8 управления, При начальной ус. ановке в этом случае регистр 3промежуточного результата устанавливается в "0",Кроме операции определения длиныстроки символов, на основе предлагаемого устройства можно обеспечить эффективное выполнение следующих операций, используемых в задачах обработ-ки строк символов,1. Определение номера позиции встроке, содержащей заданный символ.2. Определение индекса вхождениязаданной подстройки у в строку х (оп"ределяется номер позиции самого левого символа строки х, начиная с которой х входит в у). Эту операцию можновыполнить следующим образом сначалаопределить номер позиции строки х,содержащий первый символ подстройкиу(это делается с помощью предлагаемого устройства), а затем, если такойсимвол в х действительно содержится,произвести сравнение подстроки у с11 9764фрагментом строки х, начинающимся суказанного символа.3. Определение числа повторенийзаданного символа в строке,С целью технико-экономическогообоснования изобретения сравним быстродействие известного и предлагаемогоустройств. В известном устройстве длякаждого символа строки выполняетсяоперация сравнения и операция изменения на единицу содержимого регистрапромежуточного результата. Следовательно, если строка содержит М в символов,то время Т выполнения всей операцииопределяется выражением 13Т, а 2 Мвйц,где 1 - длительность типового циклаобработки информации в устройстве (чтение данных изрегистров и выполнение ариф;26метической/логической операции).Время Т выполнения операции в пред.лагаемом устройстве определяется выражением 2где М - количество машинных слов, вЮкоторых размещена строка.,- длительность типового циклацобработки информации.30В предлагаемом устройстве в связис введением узлов сравнения и блокаФормирования адреса крайней единицына 1-5 уровней увеличивается глубиналогических цепей, что может привести3к увеличению на 10-203 длительноститипового цикла обработки ,ц Ы 1,2 ц ).Полагая для достаточно длинных строксимволов Ч = Й 1 и, ,и - число символовв машинном слове), получимТ 4т, иСледовательно, быстродействие предлагаемого устройства при п=1 в 6 раза при п=8 в 12 раз выше, чем у извест 45ного устройства.Формула изобретения1. Устройство для определения дли 50 ны строки символов, содержащее сумма-.тор, регистр машиннопо слова, регистр терминального символа, регистр промежуточного результата, узел сравнения и блок управления, причем информационЯ ный вход регистра терминального симво.па соединен с входом терминального символа устройства, информационный 12вход регистра машинного слова соединен с входом машинного слова устройства. о т л и ч а ю щ е е с я тем, что. с целью повышения быстродействия устройства, оно дополнительно содержит блок Формирования маски и блок формирования адреса крайней единицы и и узлов сравнения (где и - число символов в машинном слове), первый вход каждого узла сравнения соединен с выходом регистрз машинного слова, второй вход - с выходом блока формирования маски, третий вход - с выходом регистра терминального символа, а выход - с входом блока формирования адреса крайней единицы, первый выход которого подключен к первому входу сумматора, а второй выход соединен с первым входом блока управления и выходом окончания операции устройства, второй вход блока управления, управляющий вход регистра терминального символа и первый вход регистра промежуточного результата подключены к первому входу синхронизации устройства, третий вход блока управления, управляющий вход регистра машинного слова и второй управляющий вход регистра промежуточного результата подключены к к второму входу синхронизации устройства, третий управляющий вход регистра промежуточного результата, управляющий вход блока Фрмирования маски и управляющий вход сумматора подключены к выходу блока управления, первый информационный вход регистра промежуточного результата подключен к входу установки базы строки устройства, а выход связан с информационным входом блока формирования маски и вторым входом сумматора, выход которого соединен с вторым информационным входом.регистра промежуточного результата и подключен к выходу значения длины строки устройства. 2.Устройство по и, 1, о т л и ч а ю щ е е с я тем, что блок управления содержит двухразрядный счетчик, элемент НЕ и элемент И, причем счетный вход счетчика соединен с выходом элемента И, первый вход которого соединен с третьим входом блока, второй вход элемента И соединен с инверсным выходом старшего разряда счетчика, который подключен к выходу блока, третий вход элемента И соединен с выходом элемента НЕ,вход, которого подключен к первому входу блока, вход уста13 9764 новки начального значения счетчика соединен с вторым входом блока.3. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что блок форми.рования адреса крайней единицы содержит первый и второй коммутаторы, два элемента ИЛИ-НЕ, элемент ИЛИ, два элемента НЕ, три элемента И, причем вход блока подключен к входам первого элемента ИЛИ-НЕ, элемента ИЛИ, информа О ционным входом первого коммутатора, выход которого соединен с входом второго элемента ИЛИ-НЕ и с информационными входами второго коммутатора, выход которого подключен к входу перво з го элемента НЕ, выход элемента ИЛИ соединен с первыми входами элементов И и входом второго элемента НЕ, второй вход первого элемента И соединен с выходом первого элемента ИЛИ-НЕ, ко ро торый также соединен с управляющим входом первого коммутатора, второй вход второго элемента И соединен с выходом второго элемента ИЛИ-НЕ, который также соединен с управляющим вхо дом второго коммутатора, второй вход третьего элемента И подключен к выходу первого элемента НЕ., выходы элементов И и второго элемента НЕ соединены с выходами блока. 30Устройство по и. 1, о т л и ч а ю щ е е с я тем, цто блок Формирования маски содержит семь элементов 3814ИЛИ, четыре элемента И, элемент НЕ, причем вход элемента НЕ соединен с управляющим входом блока, а его выход подключен к первым входам первого, второго и третьего элементов ИЛИ, вторые входы которых соединены с информационными входами блока, выход первого элемента ИЛИ соединен с первыми входми четвертого элемента ИЛИ и первого элемента И, вторые входы которых и первые входы второго элемента И и пятого . элемента ИЛИ подключены к выходу второго элемента ИЛИ, первые входы третьего элемента И и шестого элемента ИЛИ подключены к выходу четвертого элемента ИЛИ, первые входы четвертого элемента И и седьмогоэлемента ИЛИ подключены к выходу первого элемента И, вторые входы второго, третьего и четвертого элементов И, пятого, шестого, седьмого элементов ИЛИ подключены к выходу третьего элемента ИЛИ,а их выходы соединены с выходами блока. Источники информации,принятые во внимание при экспертизе 1. Каган Б. М., Каневский М. М. Цифровые вычислительные машины и системы. М "Энергия", 1980, с. 353-354. 2, Флорес А, Организация вычислительных машин. М., "Мир", 1972, с 308 прототип),976438 г Составитель А. ЧеканоТехред З.Палий М, Демчик Кугрыше ор едак Тираж 731 Подписи ИИПИ Государственного комитета СССР по делам изобретений и открытий 35, Москва, Ж, Раушская наб., д. Маказ 9004/7 13 Проектная иал ППП "Патент", г. Ужгоро