Устройство для реализации нормальных алгорифмов маркова

Устройство для реализации нормальных алгорифмов маркова

Иллюстрации

Показать все

Реферат

 

Устройство для реализации нормальных алгорифмов Маркова относится к техническим средствам информатики и вычислительной техники и предназначено для обработки информационных потоков и массивов данных текстового и числового,характеров в соответствии с заданными нормальными алгорифмами. Цель изобретения - повышение быстро1 Изобретение относится-к техническим средствам информатики и вычислительной техники и предназначено для обработки информационных потоков и массивов данных текстового и числового характеров в соответствии с заданными нормальными алгорифмами. Целью изобретения является повьшение быстродействия и сокращение объемов памяти при обработке текстовой информации за счет применения математическогЬ аппарата теории нормальных алгорифмов, позволяющего решать действия и сокращение объемов памяти при обр аботке текстовой информации за счет применения математического аппарата теории нормальных алгорифмов , позволяющего решать вычислитель-- ные и информационно-логические задачи - достигается тем, что в устройство , содержащее блок организации подстановки, коммутатор, блок памяти слова, дополнительно введены блок - регистров слова, дешифратор границы слова, блок поиска вхождения, блок управления , причем блок организации подстановки содержит первую и вторую группы элементов ИЛИ, первьй и второй реверсивные регистры, первьй и второй элементы И и цифровой компаратор , блок регистров слова содержит элемент И, элемент ИЛИ, элемент задержки и группу специализированных регистров, блок поиска вхождения содержит группу элементЬв ИЛИ-НЕ, группу цифровых компараторов, группу элементов ИЛИ и элемент И. 4 з.п. ф-лы, 8 ил. вычислительные и информационно-логические задачи. На фиг. 1 изображена структурная схема устройства; на фиг. 2 - структурная схема блока регистров слова; на фиг. 3 - функциональная схема реверсивного регистра; на фиг. 4 - структурная схема блока организации подстановки; на фиг. 5 - структурная схема блока поиска вхождения; на Фиг. 6 - блок-схема алгоритма работы устройства для реализации нормальныхалгорифмов Маркова; на фиг. 7 - (/) 4 01 СП 00 Oiik сд

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51) 4 G 06 F 15/20

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

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

f10 ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4234561/24-24 (22) 24. 02, 87 (46) 30,01.89. Бюл. ti - 4 (71) Курский политехнический институт (72) В. M. Довгань, Н. А. Кореневский, 10. Л. Бойко и В. В. Плотников (53) 681.325(088.8) (56) Авторское свидетельство СССР

Р 1195354, кл. G 06 F 15/16, 1984.

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

Р 1187173, кл. (: 06 F 15/04, 1984. (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ НОРИАЛЬНЫХ АЛГОРИФМОВ МАРКОВА (57) Устройство для реализации нормальных алгорифмов Маркова относится к техническим средствам информатики и вычислительной техники и предназначено для обработки информационных потоков и массивов данных текстового и числового, характеров в соответствии с заданными нормальными алгорифмами.

Цель изобретения — повышение быстроИзобретение относится к техническим средствам информатики и вычислительной техники и предназначено для обработки информационных потоков и массивов данных текстового и числового характеров в соответствии с задан-. ными нормальными алгорифмами.

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

„„SU„, 1455345 А1 действия и сокращение объемов памяти при обработке текстовой информации за счет применения математического аппарата теории нормальных алгорифМоВ позволяющего решать вычислитель-. ные и информационно-логические задачи — достигается тем, что в устройство, содержащее блок организации подстановки, коммутатор, блок памяти слова, дополнительно введены блокрегистров слова, дешифратор границы слова, блок поиска вхождения, блок управления, причем блок организации подстановки содержит первую и вторую группы элементов ИЛИ, первый и второй реверсивные регистры, первый и второй элементы И и цифровой компаратор, блок регистров слова содержит элемент И, элемент ИЛИ, элемент задержки и группу специализированных регистров, блок поиска вхождения содержит группу элементов ИЛИ-НЕ, группу цифровых компараторов, группу элементов ИЛИ и элемент И. 4 з.п. ф-лы, 8 ил. вычислительные и информационно-логические задачи.

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

1455345 схема алгоритма функционирования блока управления; на фиг. 8 — таблица переходов блока управления.

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

Блок 3 регистров слова (фиг, 2) содержит группу 9 из восьми специализированных. регистров, элемент

ИЛИ 10, элемент И 11, элемент 12 задержки. Специализированный регистр 9 содержит первый элемент И 13, первыи

14 и второй 15 реверсивные регистры, второй 16, третий 17, четвертый 18 элементы и элемент НЕ 19.

Блок 6 поиска вхождения (фиг. 4) содержит группу элементов ИЛИ-HE 20, группу цифровых компараторов 21, ( группу элементов ИЛИ 22, элемент

И 23.

Блок 5 организации подстановки (фиг, 5) содержит первую группу элементов ИЛИ 24, первый регистр 25 сдвига, первый элемент И 26, цифровой компаратор 27, второй регистр

28 сдвига, второй элемент И 29, вто. рую группу элементов ИЛИ ЗО.

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

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

Нормальный алгорифм представим конечным числом формул подстановок.

Каждая формула подстановки имеет два признака использования: текущий и заключительный. Текущий признак определяет применение формулы cTQJIbKG раз, сколько раз слово, вхождение которого распознается, входит в оба рабатываемое слово. Заключительный признак определяет применение форму10

Ф

55 лы при распознанном вхождении один и только один раз, что обозначается специальным символом, В качестве символов признаков используются "0 для текущего и "1" для заключительного признака. При срабатывании любой текущей формулы подстановки следующей формулой, включаемой в работу, является первая формула из списка формул алгорифма. При срабатывании любой з ак лючи тел ьно и фо рмулы подс та нов к и алгорифм прекращает свою работу и выдается результат. Алгорифм также прекращает свою работу, если включенная в обработку слова формула подстановки является; последней в алгорифме и вхождение не имеет места.

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

Блок-схема алгоритма работы устройства для реализации нормальных алгорифмов Маркова приведена на фиг. 6, на которой позиции 31-71 являются шагами алгоритма. Для описания алгоритма используются следуюшие идентификаторы: УОΠ— общий сброс. элементов с памятью; ПУСК вЂ” команда запуска устройства; ПВПБ — признак вхождения, начинаюшийся с первой буквы; ЧТС вЂ” потенциал чтения слова из памяти слова; ЧТФ вЂ” потенциал чтения формулы из памяти формул; П$7 — сигнал переключения коммутатора для записи, слова в блок регистров слова;

ЗпИ вЂ” сигнал разрешения зanиси инфор— мации в блок регистров слова; ЧТ ПВХ— сигнал опроса наличия вхождения; ПВХ— сигнал реакции наличия вхождения;

ПВХ1 — признак наличия вхождения;

ПГС вЂ” признак границы слова; ППФ— признак последней формулы; +1СгА— управление адресом памяти формулы;

ЗпС вЂ” сигнал записи слова в память слова; СТОП вЂ” признак останова устройства; Зп БОП вЂ” сигнал записи подстановки в блок организации подстановки; В = П вЂ” признак равенства длин слов вхождения и подстановки; Л— признак выполнения условия "вхожде— ние больше подстановки"; Пр . †.признак выполнения условия вхождение меньше подстановкии, ПЛС вЂ” признак левого сдвига; ППС вЂ” признак прлвого сдвига; THl — тактовые импульсы сдвига в блоке регистров словл; ТИ2 тактовые импульсы сдв п л п блок» ор1455345 ганизации подстановки; ПЗП вЂ” признак записи подстановки (внутренний потенциал блока управления); РПС вЂ” потенциал разрешения перезаписи информации вправо для блока регистров слова;

ПЗФ вЂ” признак заключительной формулы, Сбр CrA — сброс счетчика адреса памяти формул; УОБОП вЂ” установка в исходное состояние блока организации подстановки, ПП Vl — признак переполнения разрядной сетки блока регистров слова.

По сигналу "УОО" (фиг ° l и 6) все элементы устройства с памятью устанавливаются в исходное состояние.

По сигналу "Пуск" устройство начинает свою работу, выставляя для блока 1 памяти слова и блока 7 памяти формул потенциалы ЧТС и ЧТФ, в результате чего на выход блока 1 памяти слова выдается обрабатываемое слово, а на выходе блока 7 памяти формул выдаются коды слов вхождения II, подстановки S и признаки заключительной ПЗФ последней ППФ формулы. При этом блок

7 памяти формул разделена на 4 зоны: в первой зоне записаны слова подстановок, во второй зоне — слова вхождений, в третьей зоне — признаки заключйтельной формулы (один разряд), в четвертой зоне — признак последней формулы (один разряд) из списка. Читаемая строка образует одну формулу.

В блоке 1 памяти слов и блоке 7 памяти формул слова V M u S всегда записаны так, что первые буквы этих слов (кроме пустых) являются значительными, отсутствие буквы записывается нулями. Границы слава определяются по отсутствию значащих букв (байт буквы — не пустой). Слова пишутся без разрывов. На такте выбора информации из памяти сигналом IISV коммутатор обеспечивает подключение выходов блока 1 памяти слова к входам блока 3 регистров слова, по этому же сигналу блок 5 организации подстановки по выходу 1 дает разрешение на запись информации в блок 3 регистров слова на максимальную длину слова и одновременно сигналом ЗПИ производится запись слова в этот блок (блоксхема алгоритма работы). На следующем такте блок 8 управления опрашивает блок 6 поиска вхождения сигналом

ЧтПВХ (блок 37) и, если вхождение обнаружено, на его выходе вырабатывается сигнал ПВХ (блок 38). Дополни5

55 тельно на этом же такте блок 8 управления выставляет признак ПВПБ.

При наличии ПВХ блок 8 управления выставляет признак ПВХ1. При отсутствии ПВХ признак ПВХI не выставляется и осуществляется проверка признака границы слова путем анализа сигнала

ПГС на выходе дешифратора 2 границы слова (блок 39}. Если слово V в блоке 3 регистров слова пустое (ПГС=О), а формула не последняя (ППФ=О), производится вызов следующей формулы из блока 7 памяти формулы путем выдачи сигнала +1 CrA в счетчик адреса блока 7 памяти формул (блок 41) и после выполнения команд блока 71 цикл работы повторяется с блока 7 блок-схемы алгоритма (фиг ° 6).Если слово V пустое (ПГС=I) и формула последняя (ППФ=!}, сигналом ЗПС производится перепись слова из блока 3 регистров блока в блок 1 памяти слова (блоки

38, 39, 40, 69) и устройство останавливает свою работу, вырабатывая признак "СТОП" (блок 70) °

Если при отсутствии вхождения (ПВХ=О) слово V не пустое (ПГС=О), блок 8 управления сигает признак вхождения, начинающийся с первой буквы (ПВПБ=О, блок 42), выставляет признак левого сдвига ПЛС=I (блок 58) и вырабатывает импульс сдвига ТИ1, циклически сдвигающий влево анализируемое слово U на одну букву в блоке 3 регистров слова. Сигналом ЧТПВХ опрашиваем блок 6 поиска вхождения и про" веряем наличие признака границы слова ПГС. Если слово не пустое (ПГС=О) и вхождения нет (ПВХ=О), повторяются сдвиги влево (переход на блок 53) до тех пор, пока либо появится признак границы слова ПГС= 1 (блок 14), либо будет обнаружено вхождение (ПГС=О и

ПВХ=1) — блоки 44 и 45, после чего блок 8 управления выставляет признак

ПВХ1=1, (блок 48), снимает признак левого сдвига (ПЛС=О) для блока 3 регистров слова и переходит к выполнению ветви блок-схемы алгоритма начи" нающейся с блока 48. Если возник признак границы слова ПГС=1, то блок 8 управления снимает признак левого сдвига ПЛС=О, выставляет признак правого сдвига (ППС=I), признак циклической перезаписи информации вправо (РПС=!) — блок 47, и выдает тактовый импульс ТИI (блок 51), обеспечивающий, в блоке 3 регистров слова правый цик1455345

1г ический сдвиг на один байт. Далее анализируется наличие признака грани4ы слова ПГС (блок 66) и, если ПГС=О, сдвиг вправо повторяется до появле5 ния ПГС= I, по которому блоком 8 управления вырабатывается признак леЙого сдвига ПЛС=1 (блок 55), выдается один тактовый импульс THI =I (блок 58) и снимается признак 1р левого сдвига ПЛС=О (блок 60).

В результате выполнения этой ветви алгоритма сдвинутое ранее влево слово U возвращается в исходное положение и ввиду .того, что в полностью . I5 просмотренном слове V не было обнаружено вхождение, необходимо произвести анализ признаков заключительной и (или) последней формулы, для чего производится переход к очередной об- 2р щей ветви работы алгоритма, начинаю-: щейся блоком 65, в соответствии с которым блок 8 управления проверяет состояние признака записи подстановг, ки, а так как записи подстановки не ,было (ПЗП=О), анализируется признак

1, последней формулы (блок 66) . Если .формула не последняя (блок 66), ! ППФ=О, производится смена формулы, путем выдачи сигнала +1 CrA, произ- ЗО водится сброс внутреннего признака

I ПЗП блока 8 управления, осуществляет1 ,1 ,ся установка в исходное состояние злементов блока 5 организации подстановки сигналом УОБОП, сбрасывается признак ПВХI (блок 71). Цикл работы устройства повторяется, начиная с чтения ПВХ и установкой признака

ПВПБ {блок 37).

Если в результате работы устройст- 40 ва вхождение обнаружено, начиная с первой левой буквы слова V (блок 37), или вхождение обнаружено при левых сдвигах. слова V (блок 45), то блок

8 управления выставляет признак 45

ПВХ=1 (блок 48) и сигналом ЗПБОП (блок 48) осуществляет запись в блок

5 организации подстановки информации, необходимой для организации подстановки W S в слове V, где V = Р,ыР, 5р либо V = M Р,Р, либо 7 = Р,Р И. Если длина вхождения равна длине подстановкй,,блок 5 организации подстановки выставляет сигнал В=П, по которому блок 8 управления снимает приг знак ПВХI, формирует внутренний признак ПЗП (блок 63).

Ввиду того, чтЬ признак ПЯЧ=О, коммутатор 4 обеспечивает связь выхода блока 7 памяти формул (по шинам подстановки S) с входами блока 3, регистров слова и ввиду того, что блок

5 организации подстановки по выходам

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

ЗПИ .(блок 48), после подстановки блоком 8 управления анализирует внутренний признак наличия вхождения ! начинающегося с первой буквы слова

U (блок 64).

Если вхождение не было обнаружено (ПВПБ=О), то повторяется цикл работы блоков 47, 49, 51, 53, 55, 58, 60, который приводит к установлению слова V таким образом, что его левая буква оказывается в левых разрядах блока 3 регистра слова и управление работой устройства вновь будет передано блоку 65. Если после работы блока 48 блок-схема алгоритма признак

ПВПБ=I (вхождение обнаружено с первой левой буквы слова V) то передача управления 47 производится сразу без изменения положения слова V;

Если при обнаружении вхождения длина слова вхождения больше длины слова подстановки В ) П, блок 5.организации подстановки вырабатывает сигнал Л, по которому блок 8 управления выставляет признак левого сдвига (ПЛС=I блок 57) и вырабатывает тактовые импульсы ТИI и ТИ2 (блок 59) для блока 3 регистров слова и блока

5 организации подстановки соответственно, по которым в них производится сдвиг информации влево до тех пор, пока число сдвигов не будет равно разности )L>-Ь I где T. — число букв вхождения; L з — число букв подстановки. При этом левые сдвиги в блоке 3 регистров слова производятся с запретом циклического переноса (ПВХI=I), что приводит к стиранию левых букв вхождения на длину разности t Ls L I. Когда число сдвигов будет равно разности I I. -1,„ i, блок 5 организации подстановки выдает признак В=П (блок 62), по которому блок

8 управления передает к выполнению блока 63. После выполнения блока 63 в блоке 3 регистров слова на место оставшейся части вхождения будет записана подстановка 5.

1455345!

Если при обнаружении вхождения, длина слова вхождения меньше длины слова подстановки В < П, блок 5 opra— низации подстановки вырабатывает

5 сигнал Пр, по которому блок 8 управления выставляет признак правого сдвига (ППС=1, блок 56) и вырабатывает тактовые импульсы ТИ! и .ТИ2 (блок 59) с блока 3 регистра слова и блока 5 организации подстановки соответственно, по которым в них производится сдвиг информации вправо до тех пор, пока число сдвигов не будет рВВНо разности (J g г (° IIpH этом пра 15 вые сдвиги в блоке 3 регистров слова производятся с запретом циклического переноса (ПВХ=!), что приводит к сдвигу слова V на длину разности Ls Lw(. Когда число сдвигов будет равно разности, блок 5 организации подстановки выдает признак В = П (блок 62), по которому блок 8 управ— ления передает к выполнению блока 63, обеспечивающего запись подстановки Я в слово V, Если в результате работы устройства алгоритм приходит к блоку 65, а признак записи подстановки отсутствует и Формула последняя(ППФ=1, блок 66) gp то устройство заканчивает работу, вы— рабатывая признак СТОП" (цепь алгоритма с непоследней Формулой рас-. смотрена ранее) °

Если подстановка для данной фор35 мулы выполнялась (ПЗ И=1), то для заключительной фо рмулы (ПЗФ= 1, блок 37) блок 8 управления вырабатывает сигнал СЗпС, обеспечивающий перезапись обработанного слова 7, в блок 1 па- 4О мяти слова, и выставляет сигнал

"СТОП", останавливая работу устройства. Если формула незаключительная (ПЗФ=О), блок 8 управления выдает сигнал Сбр CrA (блок 68), что приво- 4> дит к выбору из блока памяти 7 формул первой формулы из списка, и далее цикл работы устройства повторяется (после выполнения блока 71).

Блок 3 регистров слова (фиг. 2) работает следующим образом.

Для записи слова V в реверсивные регистры 14 через девятые входы специализированных регистров 9 и через вторые информационные входы блока 3 регистров слова на информационные входы первых реверсивных регистров

14 выставляется слово V, а через первые информационные входы блока 3 регистров слова и через восьмые входы специализированных регистров 9 на вторые управляющие входы первых реверсивных регистров 14 подаются сигналы разрешения записи. Одновременно с ними на седьмой управляющий вход блока 3 регистров слова подается сигнал ЗПИ, который через седьмые входы специализированных регистров 9 поступает на входы записи первых реверсив ных регистров 14 и производит запись слова V.

При отсутствии вхождения 11 в слово V (отсутствует признак ПВХ1) сиг— нал с третьего управляющего входа блока 3 регистров слова через третьи входы специализированных регистров 9 и элементы HE 19 поступает на первые входы элементов И 16 — 18, подготавливая цепь циклического сдвига информации влево из первых реверсивных регистров 14 во вторые реверсивные регистры 15 и при наличии признака левого сдвига ПЛС, который с пятого уггравляющего входа блока 3 регистров слова через четвертые входы специализированньгх регистров 9 поступает на входы сдвига влево первых реверсивных регистров 14 и через открытые элементы ИЗ на входы сдвига влево вторых реверсивных регистров 15, разрешая левый сдвиг первоro 14 и второго 15 реверсивных регистров, реверсивный сдвиг влево которых будет осуществляться синхронно при поступлении тактовых импульсов ТИ1 с шестого управляющего входа блока 3 регистров слова через шестые входы специализированных регистров 9 на первые управляющие входы первых реверсивных регистров 14. При этом информация из первых разрядов 1р реверсивных регистров будет переписываться через вторые элементы И16 специализированных регистров 9.в старший разряд реверсивных регистров 15 и изменяться на вторых информационных вьмо дах блока 3 регистров слова со сменой букв в сдвигаемом слове V. Циклический сдвиг в первых 14 и вторых

15 реверсивных регистрах будет продолжаться до тех пор, пока не будут обнаружены либо вхождение (ПВХ1=1), либо дешифратор границы слова (ДГС, Фиг. 1) не выдаст сигнал границы слова в блок 8 управления, который снимает с входом блока 3 регистров слова сигналы ПЛС и ТИ1 (условие IIBXI x х ЙПС ТИ1) .

После обнаружения границы слова прИ,циклическом сдвиге влево, т.е. прИ условии ПВХ! ПЛС ТИ1 в соответствии с блок-схемой алгоритма (фиг. б, блЬк 64), на входы блока 3 регистров слова поступят сигналы РПС.(разреш ие правого циклического сдвига), (признак правого сдвига) и очере ные тактовые импульсы ТИ1, т.е. вь олнится условие IIBXI РПС ППС х х Иl. При этом сигнал РПС поступит ч рез первые входы специализированнь регистров 9 на первые входы первь элементов И13 и организует цепи п авого циклического сдвига информа- ц с mp выходов вторых реверсивных р гистров 15 через элементы И13 в п рвые реверсивные регистры 14. Сиги ППС через пятые входы специализ рованных регистров 9 поступит на первые входы реверсивных регистров

1 (и через четвертые элементы И18 на в орые входы первых реверсивных реги стров 14, разрешая тем самым поб. йтовый циклический сдвиг информа" и вправо во всех первых 14 и втор 15 рервесивных регистрах, осушес вляемый при поступлении каждого т тового импульса ТИ1 на восьмой в од блока 3 регистров слова.

Циклический сдвиг вправо будет о уществляться до обнаружения граниt слова Ч„ что приведет к тому, что ово 7 будет возвращено в реверсивн te регистры 14 и сдвинуто вправо на о ну букву. При этом с входов блока

3 регистров слова сигналы РПС, ППС и

ТЙ! будут сняты (условие ПВХ1 РПС

I1!tIC ТИ1), но будут вновь (для возвращения слова V в исходное положен е левая буква слова V должна быть записана в первые разряды первых рев< рсивных регистров 14) поданы сигналд ПЛС и один тактовый импульс ТИ1 на входы блока 3 регистров слова, которые и осуществляют сдвиг слова V на одну влево. Все сдвиги вправо и сдвиг влево на одну букву осуществля ю вся в соответствии с блоками 64—

6 (фиг. 6) блок-схемы алгоритма.

Если же вхождение М в слово V было обнаружено, то на третьем входе появится признак ПВХ1 и через третьи вХоды специализированных регистров 9 и элементы НЕ19, ИЗ, И4 запретит леab>e и правые сдвиги вторых реверсив455345 12

В ных регистров 15 и передачу информации циклического сдвига через вторые элементы И16 из первых реверсивных

5 регистров 14. Теперь при поступлении сигналов ПЛС ° ТИ1 или ППС ° ТИ1 будут осуществляться правые и левые сдвиги информации только в первых реверсивных регистрах 14. Очевидно, что

10 при левых сдвигах первых реверсивных регистров 14 информация будет побуквенно стираться, а при правых— смещаться вправо на число предшествующих тактовых импульсов ТИ1. При этом при правых сдвигах может возникнуть ситуация переполнения разрядной сетки (единица в m-м разряде хотя бы одноro из первых рeaepcHaHblz регистров 14). В этом случае через

2О элемент ИЛИ 1О, элемент 12 задержки, и элемент И11 будет выработан сигнал

"ПЕРЕПОЛНЕНИЕ" (ПП V 1) на выходе признака переполнения блока 3 регистров слова.

25 После обнаружения вхождения запись подстановки S в слово V осуществляется следующим образом.

При поступлении управляющих сигналов УИП по первым информационным вхоу дам блока 3 регистров на вторые управляющие входы первых реверсивных регистров !4 подстановка S поступающая через вторые информационные входы блока 3 регистров слова и через входы специализированных регистров 9 на информационные входы первых ревер,сивных регистров 14 по сигналу разре шения записи ЗПИ,. будет запиаана в .первые реверсивные регистры 14, образуя новое слово 7, в сочетании

Р,БР > или ЯР, Р, или Р,Р Б.

Если Ч „= P1P2S или U 7 = Pfs2 то слово V будет сдвинуто вправо так, чтобы его первая буква оказалась

4 в левых разрядах реверсивных регистipoa, как было описано (с организаци"ей циклического сдвига вправо до границы слова и на один такт влево), по командам из блока 8 управления.

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

Блок 6 поиска вхождения (фиг. 4) работает следующим образом.

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

14

30 дается информация Ч, из блока 3 регистров слова и через коммутатор 4 из памяти 7 формулы вхождение W соот-" ветственно.

Если в процессе работы устройства в соответствующих байтах блока 3 ре-.. гистра слова и слова W обнаруживается совпадение букв, соответствующие вХодные компараторы вырабатывают 10 сигналы логической единицы. И если при этом произойдет сравнение по всем байтам, то через соответствующие элементы ИЛИ 22 и при наличии на втором входе блока 6 поиска вхождения сигна- 15 ла Чт.ПВХ откроется элемент И23, который выработает сигнал ПВХ на выходе блока 6 поиска вхождения. Если же сравниваемые слова V è W различаются хотя бы в одной букве (в непустой 20 своей части), то сигнал на выходе блока 6 поиска вхождения не вырабатывается.

Сигнал на выходе. блока 6 поиска вхождения вырабатывается и в том слу- 2б чае, когда первых подряд значащих букв по всей значащей длине слова У вхождения с буквами слова V блока 3 регистров слова соответственно при условии, что вся оставшаяся часть слова W вхождения имеет нулевое содержание. Это достигается срабатыванием соответствующих элементов ИЛИ—

HE 20, которые через элементы ИЛИ 22 открывают элемент И23 для прохождения сигнала ЧтПВХ на выход блока 6 поиска вхождения.

Блок 5 организации подстановки (фиг. 5) работает следующим образом.

Установка в исходное- состояние 40 производится сигналом УОБОП, поступающим с блока 5 организации подстановки на входы сброса регистров 25 и 28 сдвига. По первым и шестым входам блока 5 организации подстановки слово 45

W вхождения и S подстановки побуквенно подаются на входы первой группы элементов ИЛИ 24 и второй группы элементов ИЛИ 30 соответственно, на выходах которого сигналы появляются 50 лишь в том случае, если на их входах имеются значащие буквы (код значащей буквы хотя бы в одном разряде имеет значение логической единицы) и, сле-. довательно на четвертых входах perm» стров .25 сдвига и 28 появляется столько подряд следующих сигналов, сколько букв содержится в слонах W и S соответственно (T и T.5). Кроме того, выходы элементов ИЛИ 30 являются не информационными входами блока

5 организации подстановки,с первого входа которого поступает сигнал,, разрешения записи значений Ь, и Lz соответственно, а на одном из трех вйходов цифрового компаратора 27 появляются признаки Пр или В=П, или Л, причем при Ь„, L выдается признак

Пр, при L T. — признак В П, при

Ь 7 L+ признак Л.

Если вхождение меньше подстановки

IT, (L I, то сигнал с выхода цифрового коипаратора 27 одновременно поступает на второй вход второго элемента И29 и на входы второго регистра 28 сдвига и при поступлении тактовых импульсов ТИ2 с третьего входа блока 5 организации подстановки начинается правый сдвиг (с записью "1" на каждом такте ТИ2 в левый разряд) второго регистра сдвига до тех пор, пока цифровой компаратор 27 не снимет сигнал с первого:выхода и выдаст сигнал со своего второго выхода (В П).

Если.же вхождение больше подстановки ITÄ ® > L5 I, то цифровой компаратор 27 выдает со своего выхода признак Л, который поступит на третий выход блока 5 организации подстановки, на второй вход первого элемента

И26, на .входы регистра сдвига 25 и (при поступлении ТИ2) правый сдвиг в нем будет продолжаться до выполнения условия В П.

При поступлении сигнала OSV записи слова V в блок 3 регистров слова он с второго входа блока организации подстановки через вторую группу элементов ИЛИ 30 поступает.на информационный выход блока 5 организации подстановки.

При организации сдвигов в регистрах смену признаков В П на В П и

В ) П на В П надо понимать лишь как дополнительную зались слова в регистр с меньшим количеством логических единиц модуля разницы I Të + — Ь< l р что обеспечивает (по сигналам блока 8 управления) подготовку места записи слова подстановки в блоке 3 регистров слова.

На фиг. 7 приведена отмеченная граф-схема алгоритма функционирова-. ния блока 8 управления, в которой,, введены следующие обозначения (6).

Логические условия: Х1:"УОО";

Х2:"ПУСК"; ХЗ:ПВХ; Х4:ПГС; Х5:ППФ;

Хб:ПЗФ; Х7: В=П; Х8:Л; Х9:Пр; Х10

ПП71; Х11:ПВПБ; Х12:ПЗП; X13:Операторы: У1:УОБОП:=(; У2:УОБРС:=1;

УЗ:ПУСК:=1; У4:ЧтС:=1; .У ЧтФ =1.

5

Уб:IISV:=I У7:ЗПИ:=1; У8:ЧтПВХ;=1;

У9:ПВПБ:=1; У10:ПВПБ:=О; У11;+!С А:=1

)1

У12:ПЛС:=1; У13:HJIC:=0; У)4:ТИ1:=1;

У15:IIIIC:=I; У1б:IIIIC: О; У17:PIIC:=1;

У18:РПС:=О; У19:Сбр СгА =1; У2О:ЗПБОП: 10

=1; У21:ПЗП:=1; У22:ПЗП1=0; У23:

:ПВХ1:=1; У24:ПВХ1:=О; У25:ЗПС:=1;

У2б: "СТОП", СБРОС: =О, ПУСК: =О; У27: СБРОС:=1; У28:ТИ2; =1, При этом.для конкретности условия, 15 что по команде У27 (Сброс: =1) производится установка в исходное состояние всех элементов с памятью блока 8 управления счетчиком адреса памяти 7 формулы снимаются сигналы чтения сло- 2( ва и форм. лы (ЧТС:=О, ЧтФ:=О).

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

1. Устройство для реализации нормальных алгорифмов, содержащее блок организапии подстановки, коммутатор, блок памяти слова, о т л и ч а ю— щ е е с я тем, что, с целью повышения быстродействия и сокращения обь- 30 емов памяти нри обработке текстовой информации за счет применения математического аппарата теории нормальных алгорифмов, в него введены блок регистров слова блок памяти формул, дешифратор границы слова, блок поиска вхождения, блок управления, первый и второй выходы которого соединены с первыми и вторыми управляющими входами блока памяти слова соответствен- 40 но, третий выход соединен с входом опроса блока поиска вхождения, четвертый выход соединен с управляющим входом коммутатора и первым управляющим входом блока организации подста- 45 новки, пятый, шестой и седьмой выходы блока управления соединены соответственно с первым, вторым и третьии управляющими входами блока.памяти формул, выходы с восьмого по де- gg сятый соединены с управляющими входами с второго по четвертый блока организации подстановки соответственно, выходы с одиннадцатого по семнадцатый соединены соответственно с управляющими входами с первого по седьмой блока регистров слова, первый вход блока управления соединен с выходом блока поиска вхождения, второй и третий входы блока управления соединены с третьим и четвертым информационными выходами блока памяти формул, входы с четвертого по шестой блока управления соединены с выходами с второ "o по четвертый блока организации подстановки соответственно, седьмой вход блока управления соединен с выходом признака переполнений блока регистров слова и с выходом признака переполнения устройства, восьмой вход блока управления соединен с выходом дешифратора грантщы слова, информационные выходы блока па- . мяти слова соединены с первой группой информационных входов коммутатора, вторая группа информационных входов которого соединена с вторыми информа ционными выходами блока памяти фор мул и вторыми информационными входами блока организации подстановки, а выходы соединены с вторыми информационными входами блока регистров слова, первая группа управляющих входоВ которого соединена с первой группой управляющих выходов блока организа= ции подстановки, первые информационные входы которого соединены с первыми информационными выходами блока памяти формул и вторыми информационными входами блока поиска вхождения, первые информационные входы которого соединены с информационными входами блока памяти слова и с первыми информационными выходами блока регистров слова, вторые информационные вы" ходы которого соединены с входами дешифратора границы слова, девятый вход блока управления является. входом пуска устройства, десятый вход блока управления является входом общего сброса устройства, восемнадцатый вы" ход блока управления является выходом признака окончания работы устройства..

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

1455345

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

3. Устройство по п. 2, о т л и— ч а ю ш е е с я тем, что специализированный регистр содержит с первого по четвертый элементы И, элемент НЕ, первый и второй реверсивиые регистры, входы сброса которых соединены и являются вторым входом специали- З0 зированного регистра, информационные выходы первого реверсивного регистра являются вторыми выходами специализированного регистра, а информацион-! ные выходы старшего и младшего раэря- 35 дов первого реверсивного регистра яв" ляются соответственно первым. и третьим выходами специализированного регистра, первый вход первого элемента

И является первым входом специали- 40 зированиого Регистра, а второй выход соединен со старшим разрядом второго реверсивного регистра, выход первого элемента И соединен с входом записи левого разряда первого реверсивного 45 регистра, информационные входы которого являются девятыми входами специализированного регистра, а вторые управляющие. входы являются восьмыми управляющими входами специализирован;.ного регистра, первые управляющие входы первого и второго реверсивных

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

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

К-й (где К - количество элементов

ИЛИ в группе) соединены с выходами соответствующих элементов ИЛИ