Устройство для определения длины строки символов Советский патент 1982 года по МПК G06F3/153 

1

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

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

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

Наиболее близким к предлагаемому устройству техническим решением является устройство, ориентированное , на обработку символов (байтов) и содержащее регистр машинного слова,

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

ного результата, второй выход - с управляющим входом регистра машинного слова, а третий выход подключен к Btoрому выходу устройства. Функции узла сравнения в этом устройстве блок пересылки при реализации, логичес кой функции неравнозначности. При выполнении операции определения длины „строки символов в регистр машинного слова заносятся последовательные фраг менти строки символов. Из этого регистра символы последовательно передаются на один из входов узла сравнения, на второй вход которого постоянно подан терминальный символ. Если СИМВОЛЫ не равны, то с помощью сумматора на единицу увеличивается содержимое регистра промежуточного результата. При равенстве символов выполнение операции завершается, регистр результата содержит результирующее значение L 7. 3 Последовательный характер анализа символов строки и подсчета количества символов в ней обуславливают низкое быстродействие известного устройства, что является его недостатком. Цель изобретения - повышение быст родействия. Эта цель достигается тем, что в устройство, содержащее сумматор, ре гистр машинного слова, регистр терминального символа, регистр промежуточного результата, узел сравнения и .блок управления, причем информационный вход регистра терминального символа соединен с входом терминального символа устройства, а информационный вход регистра машинного слова соединен с входом машинного слова устройства, введены блок формирования маски и блок формирования адреса крайней единицы, а количество узлов сравнения равно числу символов в машинном слове, первый вход каждого узла сравнения соединен с выходом регистра машинного слова, второй вход - с выходом блока формирования маски, третий вход - с выходом регистра терминального символа, а выход - с входом блока формирования адреса крайней единицы, первый выход которого подключен к первому входу сумматора, а

промежуточного результата подключены к первому входу синхронизации устройства третий вход блока управления, управляющий вход регистра машинного выполняет js - - °Р°и управляющий вход регист-i второй выход соединен с первым входом блока управления и выходом окончания операции устройства, второй вход блока управления, управляющий вход регистра терминального символа первый управляющий вход регистра ра промежуточного результата подключены к второму входу синхронизации устройства, третий управляющий вход регистра промежуточного результата. управляющий вход блойса формирования маски и управляющий вход сумматора подключены к выходу блока управления, первый информационный вход регистра промежуточного результата пйдключен К входу установки базы строки устройства, а .выход связан с информационным входом блока формирования маски и вторым входом сумматора, выход которого соединен с вторым информационным входом регистра промежуточного результата и подключен к выходу значения длины строки устройства. Кроме того, блок управления содержит двухразрядный счетчик, элемент НЕ и элемент И, причем счетный вход сче-чика соединен с выходом элемента И, первый вход которого соединен с третьим входом блока, второй вход элемента И соединен с инверсным выходом старшего разряда счетчика, который подключен к выходу блока, третий вход элемента И соединен с выходом элемента НЕ, вход которого подключен к первому входу блока, вход-установки начального значения счётчика соединен с вторым входом блока. Блок формирования адреса крайней единицы содержит два коммутатора, два элемента ИЛИ-НЕ, элемент ИЛИ, два элемента НЕ и три элемента И, причем вхо блока подключен к входам первого элемента ИЛИ-НЕ, элемента ИЛИ, информационным входам первого коммутатора, выход которого соединен с входом вто рого элемента ИЛИ-НЕ и с информационными входами второго коммутатора, выход которого подключен к входу первого элемента НЕ, выход элемента ИЛИ соединен с первыми входами элементов И и входам второго элемента НЕ, второй вход первого элемента И соединен с выходом первого элемента , ко торый соединен с управляющим входом первого- коммутатора, второй вход второго элемента И соединен с выходом второго элемента ИЛИ-НЕ, который соед нен с управляющим входом второго коммутатора, второй вход третьего элемен та И подключен к выходу первого элемента НЕ, выходы элементов И и второг элемента НЕ соединены с выходами блок Блок формирования маски содержит семь элементов ИЛИ, четыре элемента И и элемент НЕ, причем вход элемента НЕ соединен с управляющим входом блока , а его выход подключен к первым входам первого, второго и третьего элементов ИЛИ, вторые входы которых соединены с информационными входами блока, выход первого элемента ИЛИ соединен с первыми входами четвертого элемента ИЛИ и первого элемента И, вторые входы которых и первые входы второго элемента И и пятого элемента ИЛИ подключена к выходу второго эле мента ИЛИ, первые входы третьего эле мента И и шестого элемента ИЛИ подключены к выходу четвертого элемента ИЛИ, первые входы четвертого элемента И и седьмого элемента ИЛИ подключены к выходу первого элемента И, вто рые входы второго, третьего, четвертого элементов И, пятого, шестого, седьмого элементов ИЛИ подключены к выходу третьего элемента ИЛИ, а их выходы соединены с выходами блока, На фиг. 1 показана блок-схема уст ройства ; на фиг. 2 - блок-схема бло ка формирования адреса крайней едини цы; на фиг.. 3 - блок-схема блока фор мирования маски; на-фиг. - принцип работы устройства. Устройство для определения длины строки символов содержит регистр 1 машинного слов, регистр 2 терминаль ного символа, регистр 3 промежуточно го результата, блок 4 формирования маски, однотипные узлы 5 сравнения, S B4 блок 6 формирования адреса крайней единицы, сумматор 7, блок 8 управления. Блок 6 формирования адреса крайней единицы содержит первый коммутатор 10, первый элемент ИЛИ-НЕ 11, второй элемент ИЛИ-НЕ 12, элемент ИЛИ 13, первый элемент НЕ 1, второй элемент НЕ 15 первый, второй и третий элементы И 16-18 соответственно. Блок Ц формирования маски содержит первый, второй, третий, четвертый, пятый , шестой и седьмой элементы ИЛИ 19 - 25, первый, второй, третий, четвертый элементы И 2б -29, элемент НЕ 30 Регистр 1 машинного слова обеспечивает хранение п символов S, S , ... 5 у, (символы в регистре нумеруются слева направо) , причем . Каждый символ (в том числе и хранящийся в регистре 2 терминального символа) содержит Ig двоичных разрядов. Блок 4 формирования маски обеспечивает формирование п-разрядного двоичного слова , т,..т,(маски), содержащего единственную группу двоичных разрядов, имеющих единичное значение (разряды в маске нумеруются слева направо). Номер разряда слова М, соответствующего положению крайней левой единицы в указанной группе, определяется обратным кодом К-разрядног6 двоичного числа С , поступающего на информационный вход блока 4, а положение крайней правой единицы постоянно и совпадает с крайним правым разрядом слова М(тц-и 1). Например, если С 100, то И 0001 1 111 , так как If С 011. Блок 4 работает указанным образом при единичном значении сигнала Р на его управляющем входе. Если , то гп т . . . . Число С снимается с К младших разрядов регистра 3 промежуточного результата. Блок 4 формирования маски представляет собой многовыходную комбинацион, аргументами коную логическую схему, ДЫ CQ, Cj,. .. , С торой являются разряды двоичного числа С CQ старший разряд) и признак р. На входе, блока формируются сигналы С.- Ср , k-1. Логические функции, определяющие значения сигналов на выходах блока, могут быт.ь представлены в общем виде , , n-2; myi.H 1 Здесь К- е, QGiH-H 1 4-1 G J I G о 1c. G 1 причем ,....(5-,.,aH Логические выражения для m можно упростить, используя методы минимизации логических функций. В частности, если с является трехразрядным числом, то 4 --lo--и -2оо 1 m т 0 -К -fi 0 1-t -i m 1 т Структура блока k, реализующая данные выражения, показана на фиг. 3. Блок 6 формирования адреса крайней единицы также представляет собой миоговыходную комбинационную логическун схему. При работа блока определяется логическими выражениями

. :

; 1 - % Ч-Ла 4% Ч4 qff Чб 97 1. ) V ЪЯ 9аЯ,)

((.ъЧ4((,

Пример реализации блока 6 показан на фиг. 2. Этот блок работает в соответствии с приведенными выражениями. В этом блоке при подаче на управляющий вход первого коммутатора логичес кого О на выход коммутатораподаются сигналы Од - д, а при подаче логической 1 - сигналы Пи Яб подаче на управляющий вход второго .-коммутатора логического П на его 35 выход коммутируются сигналы g , а при подаче логической 1 - сигналы д.

В соответствии с количеством символов в регистре 1 в состав устр йства входит п узлов 5 сравнения. В узле производится сравнение терминального символа Sy из регистра 2 и символа S из регистра 1 , причем результат сравнения определяется также значением сигнала , поступающего из блока «5 формирования маски. Сигнал q-на выходе i-ro узла вырабатывается в соответствии с выражением

,..s)J.i«, «

где , Syi- значения j-ro разряда

символов S,- и S-r соответственно. На выходах узлов 5 сравнения в целом вырабатывается п-разрядное двоич- ное слово О . .. ay,, поступаю щее на вход блока 6 формирования адре са крайней единицы. Блок 6 преобразу97б$ 10 20

ся результирующее значение длины L строки символов. Разрядность v сумматора 7 в регистре 3 определяется допустимым значением параметра L.

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

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

Сигналом начальной установки |, , поступающим с третьего входа устройства, производится занесение терминального символа в регистр 2 и обратного кода базы строки bjopp в регистр 3. Под действием сигнала f блок 8 управления переходит в состояние, при котором . Импульсным сигналом о(., возбуждаемым на четвертом входе устройства, в регистр 1 заносится машинное слово, содержащее начальный фрагмент строки символов. На выходе блока 4 формирования маски вырабатывается слово М, для которого m..m,.....

,, . о Р+

т э остальные разряды имеют нулевое значение. Вследствие этого ...q, 0, а значения остальных разрядов слова Q определяются ре8 8ет слово Q в (к + 1)-разрядное двоичное число Е 1 Ц... 1, определяющее номер крайнего левого разряда слова Q, имеющего единичное значение. Еели Яр q ... q 0, то Е. и 1 1. В остальных случаях 10 0. Единичное значение признака F на первом выходе устройства указывает Иа окончание операции определения длины строки символов. Значение этого признака определяется соотношением В сумматоре 7 производится суммирование числа С, хранящегося в регистР 3 промежуточного результата, и чис выхода блока 6. Сигнал р, так ®поступающий в сумматор, использует качестве сигнала переноса в млад ший разряд. При завершении операции навтором выходе сумматора формируетзультатам сравнения символов Sg, S, ..., S с терминальным символом S. Пусть терминальный символ для рассматриваемой строки символов расположен на символьной позиции d в регистре 1 (d Ь). В этом случае 8,3,$, вследствие чего (крайняя левая ч дQ) , и на выходе бло единица в слове ка 6 формирования адреса крайней едини ы устанавливаются значения , Сумматором 7 вырабатывается значение LWC+F.+P/ mod 2 lCb o6f5bd+1/ oa -2 + d-b, определяющее результирующее значение длины строки символов, и выполнение операции заканчивается (). Если терминальный символ для рассматриваемой строки в регистре 1 отсутствует , то все разряды слова Q имеют нулевое значение, , и на выходе сумматора вырабатывается b-:ib o5p-a.4i u,,,,- ji-bfQ.,,,, -Q.b. определяющее количество символов заданной строки содержащихся в регистре 1. Признак F Тр 0, и выполнение операции продолжается. Импульсным сиг налом oL производится -занесение в. регист-р 1 очередного фрагмента стро.ки символа. В результате воздействия этого сигнала на блок 8 управления на его выходе устанавливается значение р 0. В регистр 3 переносится значение Ь с выхода сумматора 7- Все разряды маски М теперь имеют единичное значение. Если в принятом фрагменте отсутствует терминальный символ, то все разряды слова Q имеют нулевое зна чение, , а в сумматоре 7 производится сложение числа символов, зафиксированных в предыдущем фрагменте строки (с), и числа Е, определяющего количество символов в слове, которое хранится в регистре 1.Выполнение опе рации продолжается ( 0), причем сигналом в регистр 1 заносится очередной фрагмент строки символов, а в регистр 3 передается значение L с выхода сумматора. Если в последующих I машинных словах, заносимых в регистр 1, отсутствует терминальный символ, , то описанный работы устройства повторяется для каждого из этих слов, вследствие чего в регистре 3 накапливается число, соотвеУствующее количес 9 8 ву переданных в устройство символов строки. Наконец, если в регистр 1 занесен фрагмент, содержащий терминальный символ (например, на позиции а, Oi а sn-1) , то на выходе блока 6 формирования адреса крайней единицы вырабатывается значение Е а, на в:ыходе сумматора 7 устанавливается результирующее значение параметра U , и выполнение операции завершается (). . Работу устройства продемонстрируем на примере определения длины строки символов (фиг. 2). Здесь принято 4, база строки (двоичный код Ю) . В качестве терминального символа использован пробел. В таблице указаны значения сигналов в устройстве для трех машинных слов W;, w,, w, последовательно помещаемых в регистр машинного слова 1, Значение вырабатываемое в третьем цикле работы устройства, определяет результат операции. Если длина L строки символов, определяемая с помощью устройства, должна быть на единицу меньше количества символов в ней, сигнал р, поступающий в сумматор 7, должен постоянно иметь нулевое значение этот сигнал можно в сумматор не подавать). Если строки, длина которых должна быть определена, всегда выравнена по границе машинного слова в этом случае 0), то из рассмотренного устпойства можно исключить формирователь k маски и блок В управления. При начальной ус-.ановке в этом случае регистр 3 промежуточного результата устанавливается в О. Кроме операции определения длины строки символов, на основе предлагаемого устройства можно обеспечить эффективное выполнение следующих операций , используемых в задачах обработки строк символов. 1 . Определение номера позиции в строке, содержащей заданный символ. 2. Определение индекса вхождения заданной подстройки у в строку х (определяется номер позиции самого левого символа строки х, начиная с которой X входит в у). Эту операцию можно выполнить следующим образом сначала определить номер позиции строки х, содержащий первый символ подстройки у (это делается с- помощью предлагаемого устройства) , а затем, если такой символ в X действительно содержится, произвести сравнение подстроки у с фрагментом строки х, начинающимся с указанного символа. 3. Определение числа повторений заданного символа в строке. С целью технико-экономического обоснования изобретения сравним быстродействие известного и предлагаемого устройств. В известном устройстве для каждого символа строки выполняется операция сравнения и операция изменения на единицу содержимого регистра промежуточного результата. Следовател но, если строка содержит N символов, то время Т| выполнения всей операции определяется выражением T 2Ngtu,, где t(, - длительность типового цикла обработ1 и информации в устройстве (чтение данных из регистров и выполнение ариф метической/логической операции) . Время Т выполнения операции в пре лагаемом устройстве определяется выражением. TI где N - количество машинных слов, в которых размещена строка, t - длительность типового цикла обработки информации. , В Предлагаемом устройстве в связи с введением узлов сравнения и блока формирования адреса крайней единицы на -5 уровней увеличивается глубина логических цепей, что может привести к увеличению на 10-20 длительности типового цикла обработки (t,. ,21ц ) Полагая для достаточно длинных стр символов N, , ьП - число СК1МВОЛО в машинном слове), получим тГ Ь7нСледовательно, быстродействие пред лагаемого устройства при п в 6 раз, а при. в 12 раз выше, чем у извест ного устройства, Формула изобретения 1. Устройство для определения длины строки символов, содержащее сумматор, регистр машинного слова, регист терминального символа, регистр промежуточного результата, узел сравнения и блок управления, причем информацион ный вход регистра терминального симво ла соединен с входом терминального символа устройства, информационный вход регистра машинного слова соединен с входом машинного слова устройства, отличающееся тем, что. с целью повышения быстродействия устройства, оно дополнительно содержит блок формирования маски и блок формирования адреса крайней единицы и п узлов сравнения (где п - число символов в машинном слове), первый вход каждого узла сравнения соединен с выходом регистра машинного слова, второй вход - с выходом блока формирования маски, третий вход - с выходом регистра терминального символа, а выход - с входом блока формирования адреса крайней единицы, первый выход которого подключен к первому входу сумматора, а второй выход соединен с первым входом блока управления и выходом окончания операции устройства, второй вход блока управления, управляющий вход регистра терминального символа и первый вход регистра промежуточного результата подключены к первому входу синхронизации устройства, третий вход блока управления, управляющий вход регистра машинного слова и второй управляющий вход регистра промежуточного результата подключены к к второму входу синхронизации устройства, третий управляющий вход регистра промежуточного результата, управляющий вход блока фг рмирования маски и управляющий вход сумматор°а подклю- чены к выходу блока управления, первый информационный вход регистра промежуточного результата подключен к входу установки базы строки устройства, а выход связан с информационным входом блика формирования маски и вторым входом сумматора, выход которого соединен с вторым информационным входом, регистра промежуточного результата и подключён к выходу значения длины строки устройства. 2. Устройство по п. 1, о т л и чающееся тем, что блок управления содержит двухразрядный счетчик, элемент НЕ и элемент И, причем счетный вход счетчика соединен с выходом элемента И, первый вход которого соединен с третьим входом блока, второй вход элемента И соединен с инверсным выходом старшего разряда счетчика, который подключен к выходу блока, третий вход элемента 1 соединен с выходом элемента НЕ,вход , которого подключен к первому входу блока, вход установки начального значения сметчика соединен с вторым входом блока. 3. Устройство по п.1, о т л и чающееся тем, что блок формй.рования адреса крайней единицы содержит первый и второй коммутаторы два элемента ИЛИ-НЕ, элемент ИЛИ, два эле мента НЕ, три элемента И, причем вход блока подключен к входам первого элемента ИЛИ-НЕ, элемента ИЛИ, информационным входом первого коммутатора, выход которого соединен с входом второго элемента ИЛИ-НЕ и с информационными входами второго коммутатора, выход которого подключен к входу первого элемента НЕ, выход элемента ИЛИ соединен с первыми входами элементов И и входом второго элемента НЕ, второй вход первого элемента И соединен с выходом первого элемента ИЛИ-НЕ, ко торый также соединен с управляющим входом первого коммутатора, второй вход второго элемента И соединен с выходом второго элемента ИЛИ-НЕ, кото рый также соединен с управляющим входом второго коммутатора, второй вход третьего элемента И подключен к выходу первого элемента НЕ., выходы элементов И и второго элемента НЕ соединены с выходами блока. Ц. Устройство по п. 1, о т л и чающееся тем, что блок формирования маски-содержит семь элементов 97 8 четыре элемента И, элемент НЕ, причем вход элемента НЕ соединен с управляющим входом блока, а его выход подключен к первым входам первого, второго и третьего элементов ИЛИ, вторые входы которых соединены с информационными входами блока, выход первого элемента ИЛИ соединен с первыми входами четвертого элемента ИЛИ и первого элемента И, вторые входы которых и первые входы второго элемента И и пятого . элемента ИЛИ подключены к выходу второго элемента ИЛИ, первые входы третьего элемента И и шестого элемента ИЛИ подключены к выходу четвертого элемента ИЛИ, первые входы четвертого элемента И и седьмого элемента ИЛИ подключены к выходу первого элемента И, вторые входы второго, третьего и четвертого элементов И, пятого, шестого, седьмого элементов ИЛИ подключены к выходу третьего элемента ИЛИ, а их выходы соединены с выходами блока . Источники информации, принятые во внимание при экспертизе 1.Каган Б. М., Каневский М. М. Цифровые вычислительные машины и системы. М., Энергия, 1980, с. 353-35. 2.Флорес А. Организация вычислительных машин. М., Мир, 1972, с.308 (прототип).

i/tf

Фиг. 2

OmfOfftf O/Wj 6/77 о

) dw

Is Фиг.З

(риг.