Устройство для реализации подстановок слов

Устройство для реализации подстановок слов

Иллюстрации

Показать все

Реферат

 

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

,Ф

СОЮЗ СОВЕТСКИХ

СОЦИЛЛИСТИ ЕСНИХ

РЕСПУБЛИК (5g)5 С 06 Р 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н AВТОРСиоюм ЕНИДЕтеЛьСТВМ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЦТИЯМ

ПРИ ГКНТ СССР j (21) 4673821/24-24 (22) 04.04. 89 (46) 30. 10.9 I Бюл. Р 40 (71) Курский политехнический институт (72) В.M.Äîírëëü, О,Ф.Кор )$IhI(QB>

В,В.Керекеша, Ф.A.Ñòàðêîâ и С.С.Шевелев (53) 681.325 (088.8) (56) Лвторское свидетельство СССР

9 1455345, кл. G 06 F 15/16, 1986.

Лвторское свидетельство СССР

1596345, кл. G 06 F 15/20, 1988, (54) УСТРОЙСТВО ЛЛЯ РЕАЛИЗАЦИИ ПОДСТАНОВОК СЛОВ (57) Изобретение относится к техниИзобретение относится к техническим средствам информатики и вычислительной техники и может быть использовано для обработки информационных потоков и массивов данных текстового и числового типов в соответствии с заданным нормальным алгоритмом, Цель изобретения — увеличение быстродействия.

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

Устройство цля реализации подстановок сло» о, жит блок 1 обнаружения вхо:ю < ..я, блок 2 памяти вхожде„.Я0,„, 1688253 A 1 ческим средствам информатики и вычислительной техники и может быть использовано для обработки информационных потоков и массивов данных текстового и числового типов в соответствии с заданным нормальным алгоритмом.

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

9 управления.

Блок 3 анализа переходов содержит первый и второй регистры 10 и .11, первый и второй коммутаторы 12 и !3, первый и второй счетчики 14 и 15, триггер 16, элемент сравнения 17 и элемент ИЛИ 18.

Первый блок 4 подстановки содержит сдвигающие регистры 19, дешифратор

20, регистр 2 1, коммутатор 22, триггер 23, с первой по девятую группы элементов И 24-1 — 24-9, первую и вторую группы элементов ИЛИ 25-1 и

25-2, элемент ИЛИ 26 и элемент И 27.

Блок 7 просмотра содержит операционные узлы 28, регистр 29, первую и вторую группы элементов И 30 и 31.

1 и! »(- рво! О !10 1Рт!э < .1) ть»«! ) 11< м() 1» ы р«! II4 32- 15,:>пел!Р«»т И 16, псрн«111 ll вт<>1 <)й

)л< менты Н1 . 3? и "<<1, перв«»й и нтoi <)ll .)л()л»енть« задержки 3

Каждый о«терл!!««<>н!»«,тй узел 28 б. !Окя

7 росм()трл содержит первый и второй регистры 41 и 42, эпементы сравнения

43, элемент И 44, группу элементов И

>, пе.ртэь«3 1 и вт<)рой элементы И.11И 46 и 47.

Второй блок 5) подстановки содержит сдвигающпе регигтрь! 48, с первогo по »етн< ртый триггеры 49-52, перв«!11, и второй элементы И 53 — 54, перв! Нй и

Второй элементы ИЛИ 55 и 56, группу эл<.кентон ИЛИ 57, с »етчик 58 и элемен.l,() зядержр.тт под пОд(тлнОвкой и Он имаР l (я Гп(11»О

10 вида

ГДЕ э — СЛОВО-ВХ()ждРНИЕ, .! — слов<1 — подстановка, лриии:аи формулы, оо E 1 <), 1 работы формулы попстановки над ряблтынаел«1«м словом заключается в (- 25 () бОбнлружении В нем глот»л-вхождения и элмене Iro 3èl\èè слов(3-Вхож«1(ния слОВОм подстановкой.

i,cJl1! приз нлк (3)орл»".Ны <з — 1, тО формула называется заключительной. , ется В ра!)О те столько рлэ, скопт ко т) аз обнаруживается вхождение при Ре вк!«ючении в работу. тпнако B работе норл»аль«!Ого апго 40 ри Ьл»л, когда чи(.ло <»)Ормуп В нем больше, чем одна, устанавливается ре глав мент работы клждой формулы подстлн вки. Если (1>ормула в (:!Птске незлк«!ю«и— тельная, то при обнаружении первой 45 пОзиции ВхождРния О(у!!(Р стВл «1 Р тся loJI стан< вкл, а переход выполняетгя на первую формулу. 1:.»«еду«<)щ(«я форму Iil

ПОДСтаНОВКИ НОРМЛЛ«о«»ОГО аЛГОРИфМЯ вкл«()чяетгя В раб(ту тогда, котла 50 преГ!Ь»ду!4(!я (I)()pл»у)1;1 1!< ))! с (1«1 о13К 1» и B () ()наружинлет lll! ()дн<)й < Об(тненной ПО=»иции вхождения пр«! и 1:III<)!«l прогл»отр(. всего обрлблтынл(l«() I o (Jlo13ë. ) 5

11оряпок pll»)(òr1 н<)рмлпьного л !го-: рифмл м<)жно н.эмен)! гl, г храня я эквнВял(>н тl» o(" 1> пр(Об !)(!. ()Нл ния ot)pë 0 ÿ l !—

L»i1(3l1OI i) C 1 IOI3;» »1 Еhl i) H l) < 1<. J« (!«»1! Э!

ВХ 11 ВХ П (Н =, К )Ч(К. = Н,)Ч(Вх СП )К

) !» 1 J

1((П; („Вх ) „ (2)

SV1II) где Н начало вхо ения (по жд д становки);, ВХ П

К вЂ” конец вхождения (подстановки), номера формул.

Номера i и 1 могут быть равны, тогда 6)ормупа будет активизировать слмл себя;

Вх — Вхождение (левая часть) формулы;

П вЂ” подстановка (правая часть) формулы, знак для,обозначения тоГО, ЧТО ОДНО СЛОВО ВХО дит в другое слово.

К правому типу активизации формул относятся такие формулы, которые при

tt tt просмотре обрлблтывяемого слова слева направо порождают вхождения В правом крыле обрабатываелтогo слова (r1o ходу "т«росмотра") . Ег:ти же в ре— .= . ьтлте срабатывания какой-нибудь

<><>рмупы порождается вхождение в леE3()E«крыле «>хождения обрабатываемого

cJIoBiI (против хода »!росмотря), то такой тип активизации будем наз»1«нять левым. Kp« IJIBH>»EI вхождения назывлютгя (I)i )1>л!У»! л к < iò<)Ph)<.. э Я нP 111)м<1 ll < 1 P;lб (! т 111

Влют (нхох(;!(»! Пя нР <)бн;«р ужнв 11<)гс Я ) .

1\

П(>ГИН< OК»1(Г рИЭНЛКИ Обходя ХОПОС,1< ть»х форм" <1 (?????? ()ilppjlpji????r??p ????????????, ??????(???????? ????1 ????! ?? ??1>э бать!Вающих) Оп р РДРля— ютгя, исходя из состава и структуры фОРЛ!УЛ ПОДС т лlпОВКИ у ВХОДЯЩИХ Б аЛГО -. рифм. Б н<)рмлльном алгори(т>ме могут

«три<. утствовать пары формул двух видов.

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

Ко второму виду относятся пары формул, которые активизируют срабатывание друг друга или одной из них.

Далее будем считать, что всякий раэ, когда выполняется одно из следующих условий, формулы являются активиэирующимися, при условии, что в формулах левые и правые части непусТЫ(" чб г1

Сбрт

IIP V

ПКС1

ПВХ

ПРС

ОДНА

В3А

ВСЕ

ПА

ППФ

ПЗФ

ППАд

ПКС2

ЗПС

+1СчЧ

ПзРг

ПАФ

1ТгК реходав, СбрТг

16 т» части (левая и правая) обрабатываемого слона, которые графически не равны фрагменту слова, совпавшему с некоторым вхождением формулы подстановки.

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

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

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

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

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

88253 6

Для описания работы устройства используются следующие обозначения:

Пуск — команда запуска устройства;

ЧТС вЂ” команда чтения обрабатываемого слова из блока 8 памяти слова, ЧТЧ вЂ” чтение вхождения из блока 2 памяти вхождения;

СбрСч7 — сброс счетчика длин вхождений в блок обнаружения вхождения; — признак приема слова в регистре блока 4 подстановки, сброс счетчика в блоке 5 подстановки; сброс триггера 15 признак отсутствия вхождения; тактовые сигналы (сдвига); признак конца обрабатываемого слова, признак обнаружения вхождения команда чтения подстановки; признак осуществления подстановки признак одной (первой) подстановки, признак активизирующей фор мулы в нормальном алгорифме, признак того, что можно ставить все подстановки в обрабатываемом слове; признак правоактивизирующей формулы признак последний формулы признак заключительной формулы, признак безусловного перехода по адресу; признак конца обрабатываемого слова, команда записи результирующего слова в блок 8 памяти слова, команда увеличения на единицу счетчика длины вхождения в блоке обнаружения вхождения, признак приема адресов перехода в регистры 10 и 11 блока анализа переходов признак наличия информации в счетчике 15 блока анализа. переходов; команда записи единицы в триггер 16 блока анализа пекоманда сброса триггера 16;

1 2.1,ТгТИ вхождений считывается слово-вхождение и связанные с ним признаки в блок

7 просмотра. Проверяется цризнак без- 4О условного переходя по адресу. По сигналу V5: = 1 в счетчик 14 адреса записывается адрес формулы. В случае

«сли IIIIAg =- О, то по команде V3: = 1 обрабатываемое слово и значение его длины из регистров 48 и счетчика 58 перезлписывлется B регистры 19 и 21.

В следующем такте работы по команде

СбрСчб: = 1 происходит сброс счетчика 58. Далее проверяется признак наличия или отсутствия символов в слове-вхождении, Если такие символы есть и IIPU = 1, то нл регистры 48, 19, 4 1 и 42 начинают поступать тактовые сигналы ТИ: = 1. Обрабатываемое

55 слово начинает посту:nть посимвольно из блока 4 в бчок 7 просмотра. Одновременно слово-вхожп:.ние начинает перезлписываться и деli(1f асти ре ист+1СчЛ вЂ” комлндл увеличения адреса н счетчике 14, V5 команда приема информации в счетчик !4, 5

+1Pr(;r? - комлндл увеличения адреса в счетчике 1 5.>

VH команда приема информации в счетчик 15, СбрРгСч2 — сброс счетчика 15; !О

ПК ) — результат сравнения адреса активизирующей формулы с адресом перехода, запись единицы в триггер 5t дп» формул с признаком РСЕ;

ТгТИ1 — запись единицы в триггер 52 дпя формул с. призпаками кроме BCI и ПЛ;

ППГР— признак переполнения разрядной сетки, ?О

ТгПЕE — команда злписи единицы в триггер.49

СбрТгПЕР— команда сброс.. триггера 49;

СбрСчб — сброс счетчика 58, СТОП вЂ” команда o rлновки устроЙс ва;

СБРОС вЂ” комлнда установки устройства в исходное состояние.

По команде 11уск: -- 1 устройство нлчинлет работать. По команде ЧТС: = 1 3О осуществляется запись обрабатываемого слова по всей длине из блока 8 памяти снова одновременно в регистры 48, так что каждый вертикальный срез всех регистров 48 соответствует символу. В следующем такте работы по команде ЧТЧ: = 1 иэ бчока 2 памяти ров в прлвую, г ричем тактовые сигналы в эти регистры будут поступать до тех пор, пока все вхождение не перезлпишется в правую часть, а тактовые сигналы, поступающие в регистры 48 до этого времени, блокируются, Слово продолжит перезаписываться в блок 5 до тех пор, пока не выполнится ПКГ2 — 1. Затем проверится признак переполнения разрядной сетки этого блока и в случае переполнения ППЕР = 1 выдается команда Авар.ост.: = 1 и устройство прекратит свою работу. Если в блоке 1 обнаружения вхождения бу дет обнаружено вхождение ПВХ = 1, то по команде ЧТП: = 1 слово-подстановка будет считано в регистр 29, анулируя тем самым часть слона, совпадающую со словом-вхождением. Если ПА = 1, то подстановка такой формулы должна поступать иэ левой части в правую часть регистров в блоке

7 просмотра, сравниваясь со словомвхох<дением (новое вхождение может появиться только по ходу просмотра снова), в дальнейшем к ней должна при— соединиться часть обрабатываемого слова, находящаяся в блоке 4, Если

IIA = О, то проверяется признак ВГЕ.

Если ВСГ = 1, то будут отыскиваться все вхохсдения данной формулы в слове, а нл их место будут вставляться слова-подстановки (при этом слово

«е должно возвращаться). Для этого по команде ТгПЕР: = 1 в триггер 49 записывается единица и одновременно единица записывается в триггер 51, что позволяет принять подстановку в блок 5 и только после этого оставшейся части обрабатываемого слова разрешить поступать в блок 7. Если ВСЕ

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

Если IIPC = 1, то подстановка из левой части регистров слова в блоке 7 переписллась в правую часть этого блока или в блок 5, при этом в блок 5 подстлновка записывается тогда, когда

11А =- О.

При ВЗА = 1 выполняемая формула нормального ллгорифма является формуло й„ лктивизирукщей другу:"

1688253

Для случая, когда можно выполнить все подстановки (ВСЕ = 1), по команде ЧТ": = 1 считывается слово-вхождение, в противном случае (ВСЕ = О) будет анализироваться признак перехода.

Если подстановки необходимо выполнять по всей длине слова, то происходит сброс триггера 49 (продолжится поиск вхождения). При данной ситуации подаются тактовые сигналы ТИ: = 1, продолжающиеся до тех пор, пока конец обрабатаваемого слова не появится в блоке 5 (признак ПКС2 = 1).

После загрузки обрабатываемого слова в блоке 5 проверится признак переполнения разрядной сетки устройства. Если ППЕР = 1, то формируется команда аварийной остановки устройства (Авар.ост.: = 1) и устройство пре- 20 кращает работу.

В случае ППЕР = 0 проверяется признак заключительной формулы (ПЗФ =

1) и по команде ЗПС: = 1 обрабатываемое слово записывается в память, 25 и устройство прекращает работу (СТОП: = 1). В том случае когда формула незаключительная, проверяется признак (ОДНА = 1) выполнения подстановки по первому вхождению. 30

Если ПАФ = 1, т.е. в счетчике 15 отсутствует информация, то проверяется признак последней формулы в списке формул нормального алгорифма. Если

ППФ = О, то в счетчик. 14 блока 3 анализа вхождения прибавляется единица ,по команде +1СЧА: = 1. Если ПАФ = О, 1 то все переходы будут осуществляться по адресам, записанным в регистрах

10 и 11 блока 3 анализа переходов,, причем, если подстановка была обнару жена в слове, то адрес будет взят из регистра 10, в противном случае — из регистра 11. По команде V5: = 1 будет записан в счетчик 14 и сравнен с 45 адресом хранящийся в счетчике 15 адрес первой активизирующей формулы.

В том случае когда ПК = 1, по команде +1РгСч2: = 1 состояние счетчика 15 увеличивается на единицу, одно- 50 временно в триггер 16 записывается единица ТгК: = 1, а в следующем такте работы по команде V5: = 1 эта информация перезаписывается в счетчик 14.

Блок 1 обнаружения вхождения служит для обработки сигналов, поступающих .с компараторов, осуществляющих сравнение на равенство символов вхож-, дения (левая часть формулы подстановки) и фрагмента обрабатываемого сло— ва. В случае обнаружения совпадения вхождения и части обрабатываемого слова блок обнаружения вхождения выдает сигнал совпадения в блок управления. Кроме того, блок обнаружения вхождения с помощью счетчика и дешифратора задает условие обмена информацией между блоком 7 просмотра и блоками 4 и 5 подстановки.

Счетчик 14, являющийся адресным регистром для блока 2 памяти вхождений и блока 6 памяти подстановок, хранит адрес текущей (выполняемой) формулы.

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

|активизации в обрабатываемом слове.

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

При считывании очередной формулы по команде ЧТЧ: = 1 из блока 2 памяти вхождений в регистры 10 и 11 блока поступают две метки (адреса) перехода. В регистр 10 поступает метка, к которой необходимо перейти, если слово-вхождение будет обнаружено, в регистр 11 метка поступает, тогда, когда вхождение не будет обнаружено, Эти два адреса (метки перехода) могут быть одинаковыми, разными и нулевыми.

В счетчике 14 находится адрес выполняемой в данный момент формулы. В счетчике 15 будет храниться адрес активизирующей формулы или счетчик 15 . будет находиться в нулевом состоянии.

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

ПАФ (ПАФ = 1 — пуст, ПАФ = Π— информация есть). В зависимости от характера выполняемой формулы после завершения работы с нею необходимо сделать возврат на предшествующие формулы нормального алгорифма или перейти к следующей формуле, если эта формула активизирующая, то необходимо в счетчик 15 поместить (запомнить) ее адрес, переписав из счетчика 14, при- чем, если при таком возврате (переходе) встретятся формулы, которые сами являются активизирующими, то их адреса в счетчик 15 записываться не будут

168<) 2 > 3

i2 (ПАФ = О) . Работа с формулами будет идти ио метк»м переход:I.

Если ПЛФ =- 1 и формула непоследняя (ППФ = О), то по команде +1{;чЛ: = 1 адрес, хранящийся в счетчике 14 блока 3 анализа переходя, будет увеличен на единицу, Есгти ПАФ = О, то необходимо по команде V5: ="- 1 переписать адрес перехода к следующей формуле из 10 регистра 10 или 11, причем на управляющем входе коммутатора 13 будет нулевой. потенциал. Если быпа обнаружена хотя бы одна подстановка в обрабаты ваемом слове, то ня управляющем входе 15 коммутатора 12 будет единица, а к его информационному входу будет подключен выход регистра 10, в противном случг1е — выход регистра 11. После подачи команды V5: = 1 в счетчик 14 бу- 20 дет переписан новый адрес, Если на выходе компяратора элемента сравнения

17 появится сигнал IIK ) := О (это означает, что адрес в счетчике 14 меньше, чем адрес в счетчике 15), то мож- 2- но продолжать работу с новой формулой нормяпьногo алгорифмя. Если сигнал

llK ) --= 1 (это означает, что адрес в счетчике 14 больше, чем адрес в счетчике 15), то необходимо с помощью ко- 30 мянды +1РгСч2 =. 1 увеличить адрес в счетчике 15 ня единицу и одновременно .1яиисать в триггер 16 единицу, тем самым подключить информационный выход

<четчика 15 Ко входу счетчика 14 и командой V5: =- 1 переписать информацию в него. После этого необходимо. сбросить счетчик 15 (комянда

{. брРгСч2: = 1), триггер 16 (СбрТгК: =

1) и продолжить работу согласно 40 схеме алгорифма с новой формулой.

Обр11бятывяемое слово поступает на восемь сдвигающих регистров 19 блока

14. llo команде ЧЗ: = 1 слово из блока 5 перезяписывается в сдвигяющие 45 регистры 19 блока 4, одновременно (по тому же сигналу) длина обрабатываемого слова, выряженная в двоичном коде, перезяписывяет1я из счетчика 58

1>пока 5 в регистр 21 блока 4. Регистр 50

21, информационный выход которого

oоединен с дешифрятором, может содержать также длину, равную нулю, так

KBK П!>И BPPBOM C !ÈÒÛBЯНИИ СПОВЯ ИЗ блока 8 памяти слов такая длина не

11одсчитыняется счет и1ком 58 бл:>ка 5.

Регис 1р ?1 через;1ешифрятор ?О управляет .>лементями П 24, находящимися ня

111 1хОд«х 1>е1 11о тров, что поз В(>>1яе 1 со крятить время выхода обрабатываемого слова из регистров, когда длина слона существенно меньше длины регистра. В том случае когда слово только что за— писано в сдвигающие регистры 19 блока 4 из блока 5, а в блок 5 — из блока 8 памяти слона, при этом начало слона расположено в старших разрядах регистров 19, а длина слова не под— считана, подача обрабатываемого слова из сдвигающих регистров 19 по сигналам ТИ: = 1 организуется с помощью элементов ИЛИ 24, 25, 26 ° Сигналы сдвига (ТИ: = 1) начинают поступать на входы синхронизации регистров 19 только в то время, когда ИВТг1 = 1.

В том случае когда на управляющем входе коммутатора 22 — единица (для всех формул, кроме формул с признаками ПА = 1, ВСЕ = 1) информация после подстановки с первого информационного выхода коммутатора 22 подается на соответствующий вход блока 5, в противном случае информация подается на соответствующий вход блока 7.

Через информационные входы второй группы блока 7 посимвольно поступает обрабатываемое слово из блока 4. Кажды11 бит байта поступает на соответствующий вход операционного узла 28, первый бит — на первую, второй — на вторую, ..., восьмой на восьмую. Рассмотрим один из восьми операционных узлов 28. Через элемент ИЛИ 46 информация поступает на вход сдвигающего регистра 42 (регистр слова). Из блока

2 памяти вхождений слово-вхождение поступает на D-входы регистра 41 и по команде Чт7: = l может быть принята в этот регистр, причем код первого символа слова-вхождения располагается в восьми старших разрядах регистра 41 (вертикальный срез по одноименным разрядам всех восьми регистров 41 представляет код символа), Сигнал ТИ поступает на входы синхронизации всех регистров 42 операционных узлов 28, Этот же сигнал будет поступать и на регистры 41 (вхождения), так как единица приходит с выхода элемента ИЛИ

46. На входы элемента ИЛИ 46 поступает информация со старших разрядов регистров 41, в которых записан символ слова-вхождения. По сигналам

ТИ: = 1 слово будет посимвольно поступать на ретиг тры 42, а слово-подстановка будет 11ереэяписываться из

"старших" разрядов регистров 41 узлов

1688253

28 в "младшие". Сигналы сдвига ка этих регистрах прекратятся, как только подстановка перепишется. Одновременно все восемь элементов И 44 вклю- 5 чекы и символы, прошедшие зону сравнения (длика равна длине вхождения) через элементы И 45 и ИЛИ 47 (вход соответствующего элемента И 45 управляется дешифратором длины вхождения блока 1 обнаружения вхождения), а также элементы И 44 начнут поступать на соответствующий выход данного блока. Информация с элементов 43 сравнения поступает в блок 1 обнаружения вхождения. Необходимо отметить, что по команде ЧТЧ: = 1 в регистр блока 7 из блока памяти вхождения считываются признаки выполняемой формулы. В случае обнаружени вхождения ПВХ = 1.

По этому сигналу в регистры 42 узлов

28 в следующем такте считывается подстановка, "затирая" часть слова, которая совпадает с вхождением. Словоподстановка поступает из блока 6 памяти подстановок в регистры 41. Первый символ слова-подстановки будет в старших разрядах этих регистров. Для всех формул нормального алгорифма, у которых признак ПА = О, информация с ЗО выходов элементов И 31 будет поступать в блок 5 до тех пор, пока словоподстановка не будет переписано в этот блок (ПРС = 1).

Если подстановка правоактивизирующейся формулы, то при подаче сигналов сдвига (ТИ: =.1) подстановка побитно в каждом узле 28 начнет переписываться из старших разрядов в младшие

II II Н II

Одновременно в регистрах 41 вхождение 40 также начнет переписываться из старших разрядов в младшие. При полной перезаписи сигнал ПРС будет равен единице. Элемент ИЛИ-НЕ 34 выдает в блок 9 управления единицу, как только 45 в первых разрядах регистров 42 появятся все нули (конец обрабатываемого слова, ПКС1 = 1).

В исходном состоянии блока 5 счетчик 58 и триггеры 49-52 устанавлива- 50 ются в нулевое состояние. Обрабатываемое слово или слово-подстановка может поступать в блок через информационные входы на соответствующие входы восьми элементов ИЛИ 57, Через первую группу информационных входов .из блока 4 поступает та часть обрабатываемого слова, в которой прекра,щен поиск вхождения. Через третью группу информационных входов лос ту пав ют те символы обрабатываемого слова, которые прошли сравкение в блоке 7 (ка предмет обнаружения вхождения) и совпадение не произошло. Через четвертую группу информационных входов поступает подстановка иэ блока 7.

Счетчик 58 подсчитывает число поступающих в регистры блока 5 символов.

После поступления в данкый блок всего слова в счетчике 58 будет подсчитана длина этого слова. С выходов сдвигающих регистров 48 слово может быть записано в блок 8 памяти слова и перезаписано в блок 4. По команде ЧТС:

1 слово из блока 8 памяти слов записывается во все восемь сдвигающих регистров 48, причем в лервый сдвигающий регистр 48 — все первые биты слова, соответственно в восьмой сдвигающий регистр — восьмые, Вертикальный срез по одноименным разрядам сдвигающих регистров-байт кодирует один символ слова. Триггеры 52, 51, элементы ИЛИ 55 и И 53 составляют систему элементов, позволяющую пропускать сигналы сдвига на сдвигающие регистры 48 или сигнал РТИ: = 1, поступающий из блока 7. Триггер 49 используется для задания состояния блока 9 управления, определенного по результатам анализа признаков формулы.

С выхода элемента ИЛИ 56 снимается зн;,ение признака (ПКС2 = 1) того, что в сдвигающих регистрах 48 появился конец обрабатываемого слова (восемь нулей — вертикальный "срез" по первым разрядам регистров 48). С триггера 50 поступает значение признака переполнения (ППЕР), если длина слова превысила длину регистров, формула изобретения

1. Устройство для pe;:ëçàöèè подстановок слов, содержащее блок просмотра, блок памяти слов, блок управления, первый и второй блоки подстановки, причем вход запуска и вход начальной установки устройства подключены соответственно к первому и второму входам режима блока управления, первый выход которого подключен к выходу признака аварийного останова устройства, информационные выходы первой группы первого блока подстановки подключены соответственно к ин. формационным входам первой группы!

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

55 шестнадцатому входу режима блока управления, четырнадцатый выход которого подключен к тактовым входам первого и второго блоков подстановки, блоisa обнаружения вхождения и блока просмотра, пятнадцатый выход блока управления подключен ко второму управляющему входу блока просмотра и ко входу записи/чтения блока памяти вхождения, выходы первой и второй групп которого подключены соответственно к информационным входам третьей группы блока просмотра и к информационным входам блока анализа переходов, информационные выходы которого подключены к адресным входам блока памяти вхождения и блока памяти подстановок, выходы которого подключены соответственно к информационным входам четвертой группы блока ления блоком анализа переходов и информационные выходы группы которого подключены соответственно к седьмому входу режима блока управления, к управляющему входу первого блоха подстановки, к первому управляющему входу блока просмотра, к первому управляющему входу блока анализа переходов и к информационным входам второй группы блока просмотра, выход призна— ка разрешения синхронизации, выход признака одной подстановки, выход признака активизирующей формулы, выход признака цравоактивиэирующейся формулы, выход признака всех подстановок в обрабатываемом слове, выход признака последней формулы, выход признака заключительной формулы, вы20 ход признака безусловного перехода, выход признака приема адресов, первый и второй выходы управления блоком обнаружения вхождения блока просмотра подключены соответственно ко второму

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

168 просмотра, шестнадцатый выход блока управления подключен ко входу запиcH/÷TåHHÿ блока памяти подстановок и к третьему управляющему входу блока просмотра, выходы, с семнадцатого по двадцать третий, блока управления подключены соответственно к управляющим входам, с третьего по девятый, блока анализа переходов, выход признака наличия информации и выход признака результата сравнения адреса активизирующей формулы с адресом перехода которого подключены соответственно к семнадцатому и восемнадцатому входам режима блока управления.

2. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что блок анализа переходов содержит первый и второй регистры, первый и второй счетчики, первый и второй коммутаторы, триггер, элемент ИЛИ и элемент сравнения, причем первый управляющий вход блока анализа переходов подключен к управляющему входу первого коммутатора, выходы которого подключены соответственно к информационным входам первой группы второго коммутатора, выходы которого подключены соответственно к информационным входам первого счетчика, информационные выходы которого подключены к информационным входам первой группы элемента сравнения, к информационным выходам блока анализа переходов и к информационным вхо8253 lH дам гторого счетчика, инфс рмапионньн выходы которого подключены ко входам элемента ИЛИ, к информационным входам второй группы элемента сравнения и к информационным входам второй группы второго коммутатора, управляющий вход которого подключен к выходу триггера, второй управляющий вход блока анализа

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

II II счетчика, инверсный .выход элемента

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

168825 3

° ь ф

16(RP 254

1 688253

1бВ8 53 ай. 6

Составитель В.Смирнов

Редактор Т.Орловская Техред И.Дидык - Корректор Л.Пилипенко

Заказ 3710 Тираж Подписное

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

113035, Г1осква, Ж-35, Раушская наб., д, 4/5

Производственно †издательск комбинат "Патент", г. Ужгород, ул. Гагарина, 101