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

 

Союз Советских

Социвпистичвских

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 04. 08. 80 (21) 3pp0444/18-24 (s>)h%. Кл.

6 06 Г 3/153 с орисоедннеикеи заявки йе

9кударстееньа коинтет

CCCP ю далем нзебретаннй в юткрытнй (23) Лриоритет

Опубликовано 23 11 82, Бюллетень М43

Дата опубликования описания 23 . 1 1 .82 (53) УдК 6" 1 32 (088.8) (72) Авторы мэобретения

И. П. Селезнев и Е. В. Бычков (71) Заявитель (54) УСТРО1СТВО ДЛЯ ОПРЕДЕЛЕНИЯ ДЛИНЫ

СТРОКИ СИМВОЛОВ

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

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

1О конец строки) символом. Указанная операция употребляется в языках программирования высокого уровня. Строка символов, в общем. случае, может разме15 щаться в нескольких машинных словах.

Одно полное машинное слово содержит и символов. Строка может начинаться с любой символьной позиции в машинном слове. Положение первого символ стро- п ки задается его адресом Ь в слове(базой строки ), Адрес отсчитывается от левой границы слова, причем 0 Ь— п-1.

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

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

Наиболее близким к предлагаемому устройству техническим решением является устройство, ориентированное на обработку символов (байтов) и содержащее регистр машинного слова, 976438 сумматор, регистр терминального сим" вола, регистр промежуточного результата, узел сравнения двух байтов и блок управления, причем вход регистра терминального символа соединен с входом терминального символа устройства, а информационный вход регистра машинного слова соединен с входом машинного слова устройства, входы узла сравнения двух байтов подключены к выхо- ф дам регистра машинного слова и регистра терминального символа, à его выход - к входу блока управления. Выход регистра промежуточного результата связан с входом сумматора, выход 1 которого объединен с входом регистра промежуточного результата и подключен к первому выходу -устройства. Первый выход блока управления соединен с управляющим входом регистра промежуточ- 20 ного результата, второй выход - с управляющим входом регистра машинного слова, а третий выход подключен к второму выходу устройства. Функции узла сравнения в этом устройстве выполняет 23 блок пересылки при реализации.логической функции неравнозначности. При выполнеь ии операции определения длины .строки символов в регистр машинного слова заносятся последовательные Фраг-3 менты строки символов. Из этого регистра символы последовательно передаются на один из входов узла сравне- . ния, на второй вход которого постоянно подан терминальный символ. Если

3S

:символы не равны, то с помощью сумматора на единицу увеличивается содержимое регистра промежуточного результата. При равенстве символов выполнеО ние операции завершается, регистр результата содержит результирующее значение L (21 .

Последовательный характер анализа символов строки и подсчета количества символов в ней обуславливают низкое

43 быстродействие известного устройства, что является его недостатком.

Цель изобретения — повышение быст родействия.

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

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

Блок формирования адреса крайней единицы содержит два коммутатора, два элемента ИЛИ-НЕ, элемент ИЛИ, два эле9764 мента НЕ и три элемента И, причем вход блока подключен к входам первого элемента ИЛИ-НЕ, элемента ИЛИ, информационным входам первого коммутатора, выход которого соединен с входом вто- 3 рого элемента ИЛИ-НЕ и с информационными входами второго коммутатора, выход которого подключен к входу первого элемента НЕ, выход элемента ИЛИ соединен с первыми входами элементов

И и входам второго элемента НЕ, второй вход первого элемента И соединен с выходом первого элемента ИЛИ-НЕ, который соединен с управляющим входом первого коммутатора, второй вход вто- 1 рого элемента И соединен с выходом второго элемента ИЛИ-НЕ, который соединен с управляющим входом второго коммутатора, второй вход третьего элемента И подключен к выходу первого эле- 20 мента НЕ, выходы элементов И и второго элемента НЕ соединены с выходами блока.

Блок формирования маски содержит семь элементов ИЛИ, четыре элемента

И и элемент НЕ, причем вход элемента 2s

НЕ соединен с управляющим входом блока, а его выход подключен к первым входам первого, второго и третьего элементов ИЛИ, вторые входы которых соединены с информационными входами щ блока, выход первого элемента ИЛИ соединен с первыми входами четвертого элемента ИЛИ и первого элемента И, вторые входы которых и первые входы второго элемента И и пятого элемента

ИЛИ подключены к выходу второго эле— мента ИЛИ, первые входы третьего элемента И и шестого элемента ИЛИ подключены к выходу четвертого элемента

ИЛИ, первые входы четвертого элемента И и седьмого элемента ИЛИ подключены к выходу первого элемента И, вторые входы второго, третьего, четвертого элементов И, пятого, шестого, седьмого элементов ИЛИ подключены к выходу третьего элемента ИЛИ, а их выходы соединены с выходами блока.

На фиг. 1 показана блок-схема устройства ; на фиг. 2 - блок-схема блока формирования адреса крайней единиИ цы; на фиг,. 3 - блок-схема блока фор мирования маски; на- фиг. 4 — принцип работы устройства.

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

Блок 6 формирования адреса крайней единицы содержит первый коммутатор 10, первый элемент ИЛИ-НЕ 11, второй элемент ИЛИ-НЕ 12, элемент ИЛИ 13, первый элемент НЕ 14, второй элемент

НЕ 15, первый, второй и третий элементы И 16-18 соответственно.

Блок 4 формирования маски содержит первый, второй, третий, четвертый, пятый, шестой и седьмой элементы ИЛИ19 — 25, первый, второй, третий, четвертый элементы И 26 -29, элемент HE 3Q

Регистр машинного слова обеспечивает хранение и символов 5, 5л,...

Б,символы в регистре нумеруются слева направо), причем п=2 К. Каждый символ (в том числе и хранящийся в регистре 2 терминального символа) содержит 1 двоичных разрядов.

Блок 4 формирования маски обеспечивает формирование и-разрядного двоичного слова M=m» m<, л „(маски), содержащего единственную группу двоичных разрядов, имеющих единичное значение (разряды в маске нумеруются слева направо). Номер разряда слова М, соответствующего положению крайней левой единицы в указанной группе, определяется обратным кодом К-разрядного двоичного числа С, поступающего на информационный вход блока 4, а положение крайней правой единицы постоянно и совпадает с крайним правым разрядом

I f слова M,m и q =1) . Например, если С =

=100, то M= 00011111, так как (С)

= 011. Блок 4 работает указанным образом при единичном значении сигнала

P на его управляющем входе. Если P=O, то mz=m = ...=m „=1. Число С снимаI о л ил ется с К младших разрядов регистра 3 промежуточного результата.

Блок 4 формирования маски представляет собой многовыходную комбинационную логическую схему, аргументами коI торой являются разряды Со, Сл,..., Ск двоичного числа С С - старший разряд) и признак р. На входе, блока формируются сигналы С =С. 1=0, k-1.

4л

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

> о .! i=O и-2; m>-ë =1

Здесь К.= С о Св .. С -" о 11

1 при G = 0 (сл при G=1

976438 причем

i4.О +9< +" С

Логические выражения для m можно

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

m = С. о фф, п)„= С.ц, /С„1 С1

m„= С о С„„m m t:„, Ñ, гп = С С„„С, m = С С1 С, mq = С о m = 1 т

Структура блока 4, реализующая данные выражения, показана на фиг. 3.

Блок 6 формирования адреса крайней единицы также представляет собой многовыходную комбинационную логическую схему. При n=e работа блока определяется логическими выражениями ао о Ъс " " .

ЪФЛ .Ф ФбЧ Ч

Е, =,с „Я, ч й;> ч,Д„4г Ф 4 ф,(q ÷9.) y= qo (q« %д.ЪР Ьо%аЬМьйа(йуЬьс т

Пример реализации блока 6 показан на фиг. 2. Этот блок работает в соответствии с приведенными выражениями.

В этом блоке при подаче на управляющий вход первого коммутатора логичес- кого "0" яа выход коммутатора подаются сигналы g© — g, а при подаче лоГической 1 - сиГнали ) -, gg При подаче на управляющий вход второго

-.коммутатора логического 0" íà его M выход коммутируются сигналы и, а при

I подаче логической "1" - сигналы g .

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

Е -1 сЦ g о в ъ ч а "s I )3m„ где S„>, S - значения 3-ro разряда символов 5 и S соответственно.Т

1

На выходах узлов 5 сравнения в целом вырабатывается и-разрядное двоич- ное слово 0 = q „ v „... q„ „, поступаю щее на вход блока 6 формирования адре са крайней единицы. Блок 6 преобразует слово Q в (К + 1)-разрядное двоичное число E = 1 1 ... 1„, определяющее номер крайнего левого разряда слова Q, имеющего единичное значение. Если ц = q ... = q„ < О, то Е=2 и

1=1. В остальных случаях А» Е» 2 " — 1

1О =О, Единичное значение признака F на первом выходе устройства указывает

На окончание операции определения длины строки символов. Значение этого признака определяется соотношением

F=1 .

В сумматоре 7 производится суммирование числа С, хранящегося в регистре 3 промежуточного результата, и числа Е с выхода блока 6. Сигнал р, также поступающий в сумматор, используется в качестве сигнала переноса в младший разряд. При завершении операции на втором выходе сумматора формируется результирующее значение длины L строки символов. Разрядность v сумматора 7 в регистре 3 определяется допустимым значением параметра 1 .

В предлагаемом устройстве структура блока 8 проста: он представляет собой двухразрядный счетчик, элемент

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

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

Сигналом начальной установки поступающим с третьего входа устройства, производится занесение терми.— нального символа в регистр 2 и обратного кода базы строки I b)о О в регистр

3. Под действием сигнала Ь блок 8 управления переходит в состояние, при котором р=1..Импульсным сигналом, возбуждаемым на четвертом входе устройства, в регистр 1 заносится машинное слово, содержащее начальный фрагмент строки символов. На выходе блока 4 формирования маски вырабатывает-. ся слово И, для которого m =m в =1, а остальные разряди ймеют

yl=1 нулевое значение. Вследствие этого

q =q =...=q О, а значения остальО 4 Ь1 ных разрядов слова 0 определяются pe\

97643

9 зультатам сравнения символов Sb, S +q, ..., S< „ с терминальным символом 3

Пусть терминальный символ для рассматриваемой строки символов расположен на символьной позиции d в регистре 1 (d > b). В этом случае Я -S вследствие чего q<=1 (крайняя левая единица в слове 0), и на выходе бло ка 6 формирования адреса крайней еди- 10 ниЦы устанавливаются значения E=d, 10

Сумматором 7 вырабатывается значение 1-=/С+Е+Р/ mod=2 = JEblogpd+1/ pg=

2 = /2 -Ь + 0 „„8=2 = d-b, опреде- 1s ляющее результирующее значение длины строки символов, и выполнение операции заканчивается (F=1).

Если терминальный символ для рассматриваемой строки в регистре 1 отсутствует, то все разряды слова Q имеют нулевое значение, Е=2 ", и на выходе сумматора вырабатывается чис" " tt) " " l .a=av= l "- < l a, а, к @ определяющее количество символов заданной строки содержащихся в регистре 1. Признак F = 1 =О, и выполнение операции продолжается. Импульсным сиг-зо налом о(производится .занесение в регистр 1 очередного фрагмента стро.ки символа. В результате воздействия этого сигнала на блок 8 управления на . его выходе устанавливается значение р = О. В регистр 3 переносится значение 1 с выхода сумматора 7. Все раз/ ряды маски M теперь имеют единичное значение. Если в принятом фрагменте отсутствует терминальный символ, то щ все разряды слова Q имеют нулевое значение, Е=2", а в сумматоре 7 производится сложение числа символов, зафиксированных в предыдущем фрагменте строки (С), и числа Е, определяющего аз количество символов в слове, которое хранится в регистре 1. Выполнение операции продолжается (Г=1 =О), причем сигналом в регистр 1 заносится очередной фрагмент строки символов, а в р регистр 3 передается значение L с выхода сумматора. Если в последующих машинных словах, заносимых в регистр 1, отсутствует терминальный символ, то описанный цикл работы устройства . повторяется для каждого из этих слов, 1 вследствие чего в регистре 3 накапливается число, соответствующее количест

8 10 ву переданных в устройство символов строки. Наконец, если в регистр 1 за" несен фрагмент, содержащий терминальный символ (например, на позиции а, 0 а с п-1), то на выходе блока 6 фор" мирования адреса крайней единицы вырабатывается значение Е = а, на выходе сумматора 7 устанавливается результирующее значение параметра L, и выполнение операции завершается (Г=1)..

Работу устройства продемонстрируем на примере определения длины строки символов (фиг. 2). Здесь принято n=v

=4, база строки b=2 (двоичный код 10) .

В качестве терминального символа использован пробел. В таблице указаны значения сигналов в устройстве для трех машинных слов и, и, из, последовательно помещаемйх в регистр машинного слова 1. Значение L=j, вырабатываемое в третьем цикле работы устройства, определяет результат операции. . Если длина 1 строки символов, определяемая с помощью устройства, должна быть на единицу меньше количества символов в ней, сигнал р, поступающий в сумматор 7, должен постоянно иметь нулевое значение (этот сигнал можно в сумматор не подавать).

Если строки, длина которых должна быть определена, всегда выравнена по границе машинного слова (в этом случае Ь=О), то из оассмотренного устройства можно исключить формирователь 4 маски и блок 8 управления. При начальной ус- ановке в этом случае регистр 3 промежуточного результата устанавливается в "0".

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

1. Определение номера позиции в строке, содержащей заданный символ.

2. Определение индекса вхождения заданной подстройки у в строку x (on" ределяется номер позиции самого левого символа строки х, начиная с которой х входит в у). Эту операцию можно выполнить следующим образом сначала определить номер позиции строки х, содержащий первый символ подстройки у(это делается с помощью предлагаемого устройства), а затем, если такой символ в х действительно содержится, произвести сравнение подстроки у с l1 9764 фрагментом строки х, начинающимся с указанного символа.

3. Определение числа повторений заданного символа в строке.

С целью технико-экономического обоснования изобретения сравним быстродействие известного и предлагаемого устройств. В известном устройстве для каждого символа строки выполняется операция сравнения и операция измене- 16 ния на единицу содержимого регистра промежуточного результата. Следователь но, если строка содержит М в символов, то время Т выполнения всей операции определяется выражением 13

Т, -" 2N t gq, где t - длительность типового цикла обработки информации в устройстве (чтение данных из регистров и выполнение ариф;26 метической/логической операции).

Время Т выполнения операции в предлагаемом устройстве определяется выражением 25

Тх = N töi где М - количество машинных слов, в 4/ которых размещена строка., — длительность типового цикла ц обработки информации.

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

3S к увеличению на 10-20 длительности типового цикла обработки,t> Ы1,2 ц ) .

Полагая для достаточно длинных строк символов N = и 1и,,и — число символов в машинном слове), получим

Т т, =1,7И .

Следовательно, быстродействие предлагаемого устройства при п=4 в 6 раз,, а при п=8 в 12 раз выше, чем у извест45 ного устройства.

Формула изобретения

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

SS ный вход регистра терминального симво.ла соединен с входом терминального символа устройства, информационный

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

2. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что блок управления содержит двухразрядный счетчик, элемент НЕ и элемент И, причем счетный вход счетчика соединен с выходом элемента И, первый вход которого соединен с третьим входом блока, второй вход элемента И соединен с инверсным выходом старшего разряда счетчика, который подключен к выходу блока, третий вход элемента И соединен с выходом элемента HE,вход, которого подключен к первому входу блока, вход уста13 9764 новки начального значения счетчика соединен с вторым входом блока.

3. Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок форми.рования адреса крайней единицы содержит первый и второй коммутаторы, два элемента ИЛИ-НЕ, элемент ИЛИ, два элемента НЕ, три элемента И, причем вход блока подключен к входам первого элемента ИЛИ-НЕ, элемента ИЛИ, информа- 10 ционным входом первого коммутатора, выход которого соединен с входом второго элемента ИЛИ-НЕ и с информационными входами второго коммутатора, выход которого подключен к входу перво- м го элемента НЕ, выход элемента ИЛИ соединен с первыми входами элементов

И и входом второго элемента НЕ, второй вход первого элемента И соединен с выходом первого элемента ИЛИ-НЕ, ко р0 торый также соединен с управляющим входом первого коммутатора, второй вход второго элемента И соединен с выходом второго элемента ИЛИ-НЕ, который также соединен с управляющим вхо- 2s дом второго коммутатора, второй вход третьего элемента И подключен к выходу первого элемента НЕ., выходы элементов И и второго элемента НЕ соединены с выходами блока. 30

4. Устройство по и. 1, о т л и— ч а ю щ е е с я тем, что блок Формирования маски содержит семь элементов

38

14

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

ИЛИ подключены к выходу четвертого элемента ИЛИ, первые входы четвертого элемента И и седьмого элемента ИЛИ подключены к выходу первого элемента

И, вторые входы второго, третьего и четвертого элементов И, пятого, шестого, седьмого элементов ИЛИ подключены к выходу третьего элемента ИЛИ, а их выходы соединены с выходами блока.

Источники информации, принятые во внимание при экспертизе

1. Каган Б. M., Каневский М. М.

Цифровые вычислительные машины и системы. М., "Энергия", 1980, с. 353-354

2. Флорес А. Организация вычислительных машин. М., "Мир", 1972, с.308 (прототип) .

976438

Фиг. 5

Фиг. Ф

Составитель А. Чеканов

Редактор Т. Кугрышева Техред З.Палий Корректор М. Демчик

Заказ 9004/75 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5 филиал ППП "Патент", г. Ужгород, ул. Проектная, 4