Устройство для реализации нормальных алгорифмов Маркова Советский патент 1989 года по МПК G06F17/00 

10

15

20

схема алгоритма функционирования блока управления; на фиг. 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) содержит группу элементов ИЛИ-НЕ 20, группу цифровых компараторов 21, группу элементов ИЛИ 22, элемент И 23.

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

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

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

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

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

Блок-схема алгоритма работы устройства для реализации нормальных 25 алгорифмов Маркова приведена на

фиг. 6, на которой позиции 31-71 являются шагами алгоритма. Для описания алгоритма используются следующие идентификаторы: УРО - общий сброс- элементов- с памятью; ПУСК - команда запуска устройства; ПВПБ - признак вхождения, начинающийся с первой бук вы; ЧТС - потенциал чтения слова из памяти слова; ЧТФ - потенциал чтения формулы из памяти формул; nsv - сигнал переключения коммутатора для записи, слова в блок регистров слова; ЗпИ - сигнал разрешения записи инфор мации в блок регистров слова; ЧТ ПВХ сигнал опроса н аличия вхождения; ПВХ сигнал реакции наличия вхождения; ПВХ1 - признак наличия вхождения; ПГС - признак границы слова; ППФ - признак последней формулы; +1СгА - управление адресом памяти формулы; ЗпС - сигнал записи слова в память слова; СТОП - признак останова устройства; Зп БОП - сигнал записи под становки в блок организации подстан

30

35

40

Нормальньй алгорифм представим ко- вки; В, П - признак равенства длин

гл г гт f тл TTi TTr T 3T-IOTJ K W Tl

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

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

слов вхождения и подстановки; Л - признак выполнения условия вхождение больше подстановки ; Пр -.признак выполнения условия вхождение меньше подстановки ; Ш1С - признак левого сдвига; ППС - признак правог сдвига; ТИ1 - тактовые импульсы сдв га в блоке регистров словп; ТИ2 - тактовые импульсы сдвмгп н блоке ор

5

0

5

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

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

Блок-схема алгоритма работы устройства для реализации нормальных 5 алгорифмов Маркова приведена на

фиг. 6, на которой позиции 31-71 являются шагами алгоритма. Для описания алгоритма используются следующие идентификаторы: УРО - общий сброс- элементов- с памятью; ПУСК - команда . запуска устройства; ПВПБ - признак вхождения, начинающийся с первой буквы; ЧТС - потенциал чтения слова из памяти слова; ЧТФ - потенциал чтения формулы из памяти формул; nsv - сигнал переключения коммутатора для записи, слова в блок регистров слова; ЗпИ - сигнал разрешения записи информации в блок регистров слова; ЧТ ПВХ- сигнал опроса н аличия вхождения; ПВХ- сигнал реакции наличия вхождения; ПВХ1 - признак наличия вхождения; ПГС - признак границы слова; ППФ - признак последней формулы; +1СгА - управление адресом памяти формулы; ЗпС - сигнал записи слова в память слова; СТОП - признак останова устройства; Зп БОП - сигнал записи подстановки в блок организации подстано0

5

40

вки; В, П - признак равенства длин

гл г гт f тл TTi TTr T 3T-IOTJ K W Tl

слов вхождения и подстановки; Л - признак выполнения условия вхождение больше подстановки ; Пр -.признак выполнения условия вхождение меньше подстановки ; Ш1С - признак левого сдвига; ППС - признак правого сдвига; ТИ1 - тактовые импульсы сдвига в блоке регистров словп; ТИ2 - тактовые импульсы сдвмгп н блоке организации подстановки; ПЗП - признак записи подстановки (внутренний потенциал блока управления); РПС - потенциал разрешения перезаписи инсЬорма- ции вправо для блока регистров слова ГОФ - признак заключительной формулы Сбр СгА - сброс счетчика адреса памяти формул; УОБОП - установка в исходное состояние блока организации подстановки; ПП VI - признак переполнения разрядной сетки блока регистров слов а.

По сигналу УОО (фиг. 1 и 6) все элементы устройства с памятью устанавливаются в исходное состояние. По сигналу Пуск устройство начинает свою работу, выставляя для блока I памяти слова и блока 7 памяти формул потенциалы ЧТС и ЧТФ, в результате чего на выход блока I памяти слова вьщается обрабатьшаемое слово, а на выходе блока 7 памяти формул вьщают- ся коды слов вхождения W, подстановки S и признаки заключительной ПЗФ последней ППФ формулы. При этом блок

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

в четвертой зоне - признак последней формулы (один разряд) из списка. Читаемая строка образует одну формулу.

8блоке 1 памяти слов и блоке 7 памяти формул слова V, W и S всегда записаны так, что первые буквы этих

слов (кроме пустых) являются значительными, отсутствие буквы записывается нулями. Границы слова определяются по отсутствию значащих букв (байт буквы - не пустой), Слова пишутся без разрывов. На такте выбора информации из памяти сигналом ПЗУ коммутатор обеспечивает подключение выходов блока 1 памяти слова к входам блока 3 регистров слова, по этому же сигналу блок 5 организации подстановки по выходу 1 дает разрешение на запись информации в блок 3 регистров слова на максимальнзпо длину слова и одновременно.сигналом ЗПИ производится запись слова в этот блок (блок- схема алгоритма работы). На следующем такте блок 8 управления опрашивает блок 6 поиска вхождения сигналом ЧтПВХ (блок 37) и, если вхождение обнаружено, на его выходе вырабатывается сигнал ПВХ (блок 38). Дополни553456

тельно на этом же такте блок 8 управления выставляет признак ПВПБ. При наличии ПВХ блок 8 управления g выставляет признак ПВХ1. При отсутствии ПВХ признак ПВХ1 не выставляется и осуществляется проверка признака границы слова путем анализа сигнала ПГС на выходе дешифратора 2 границы 10 слова (блок 39). Если слово V в блоке 3 регистров слова пустое (), а формула не последняя (nil(), производится вызов следующей формулы из блока 7 памяти формулы путем выдачи 15 сигнала +1 СгА в счетчик адреса блока 7 памяти формул (блок 41) и после выполнения команд блока 71 цикл работы повторяется с блока 7 блок-схемы алгоритма (фиг. 6).Если слово V пу- 20 стое () и формула последняя (), сигнапом ЗПС производится перепись слова из блока 3 регистров блока в блок 1 памяти слова (блоки 38, 39, 40, 69) и устройство ост.анав- 25 ливает свою работу, вырабатывая при- /знак СТОП (блок 70).

Если при отсутствии вхождения () слово V не пустое (), блок 8 управления снимает признак 30 вхождения, начинающийся с первой буквы (, блок 42), выставляет признак левого сдвига (блок 58) и вырабатьшает импульс сдвига ТИ1, циклически сдвигающий влево анализируе- 35 мое слово V на одну букву в блоке 3 регистров слова. Сигналом. ЧТПВХ опрашиваем блок 6 поиска вхождения и проверяем наличие признака границы слова ПГС. Если слойо не пустое () 40 и вхождения нет (), повторяются сдвиги влево (переход на блок 53) до тех пор, пока либо появится признак границы слова ПГС 1 (блок 14), либо будет обнаружено вхождение ( и 45 ПВХ 1)-блоки 44 и 45, после чего блок 8 управления выставляет признак , (блок 48), снимает признак левого сдвига () для блока 3 регистров слова и переходит к выполне- 50 нию ветви блок-схемы алгоритма начинающейся с блока 48. Если возник признак границы слова , то блок 8 управления снимает признак левого сдвига , выставляет признак пра- 55 вого сдвига (), признак циклической перезаписи информации вправо () - блок 47, и вьщает тактовый импульс ТИ1 (блок 51), обеспечивающий г в блоке 3 регистров слова правый цик ический сдвиг на один байт. Далее анализируется наличие призна1са границы слова ПГС (блок 66) и, если , 1сдвиг вправо повторяется до появле- ния , по которому блоком 8 уп- |равления вырабатьшается признак ле- ого сдвига (блок 55), вьщает- сЯ один тактовьй импульс (блок 58) и снимается признак левого сдвига (блок 60). Б результате вьшолнения этой ветви алгоритма сдвинутое ранее влево слово V возвращается в исходное положение и ввиду .того, что в полностью, просмотренном слове V не бьшо обнаружено вхождение, необходимо произвести анализ признаков заключительной и ,,. I (или) последней формулы, для чего производится переход к очередной об- щей ветви работы алгоритма, начинаю- щейся блоком 65, в соответствии с которым блок 8 управления проверяет состояние признака записи подстанов ки, а так как записи подстановки не было (), анализируется признак последней формулы (блок 66), Если формула не последняя (блок 66), , производится смена формулы путем выдачи сигнала +1 СгА, производится сброс внутреннего признака ГВП блока 8 управления, осуществляется установка в исходное состояние элементов блока 5 организации подстановки сигналом УОБОП, сбрасывается признак ПВХ1 (блок 71). Цикл работы устройства повторяется, начиная с чтения ГШХ и установкой признака ПВПБ (блок 37).

хода блока 7 памяти формул (по шинам подстановки S) с входами блока 3, регистров слова и ввиду того, что блок 5 организации подстановки по выходам I выставляет вектор признаков длины места подстановки, начиная с левой буквы слова, оказывается подготовленным для записи подстановки со стира10 :нием обнаруженного вхождения..Запись Iподстановки осуществляется сигналом 31Ш.(блок 48), после подстановки блоком 8 управления анализирует внутренний признак наличия вхождения

15 начинающегося с первой буквы слова V (блок 64).

Если вхождение не было обнаружено (ПВ11Б 0), то повторяется цикл работы блоков 47, 49, 51, 53, 55, 58, 60,

20 который приводит к установлению слова V таким образом, что его левая буква оказывается в левых разрядах блока 3 регистра слова и управление работой устройства вновь будет пере25 дано блоку 65. Если после работы блока 48 блок-схема алгоритма признак ПВ11Б 1 (вхождение обнаружено с первой левой буквы слова V), то передача управления 47 производится сразу

30 без изменения положения слова V;

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

35

сигнал Л , по которому блок 8 управления выставляет признак левого сдвига ( блок 57) и вырабатывает тактовые импульсы ТИ1 и ТИ2 (блок 59) для блока 3 регистров слова и блока

Если в результате работы устройст- 40 5 организации подстановки соответст55345

хода блока 7 памяти формул (по шинам подстановки S) с входами блока 3, регистров слова и ввиду того, что блок 5 организации подстановки по выходам I выставляет вектор признаков длины места подстановки, начиная с левой буквы слова, оказывается подготовленным для записи подстановки со стира10 :нием обнаруженного вхождения..Запись Iподстановки осуществляется сигналом 31Ш.(блок 48), после подстановки блоком 8 управления анализирует внутренний признак наличия вхождения

15 начинающегося с первой буквы слова V (блок 64).

Если вхождение не было обнаружено (ПВ11Б 0), то повторяется цикл работы блоков 47, 49, 51, 53, 55, 58, 60,

20 который приводит к установлению слова V таким образом, что его левая буква оказывается в левых разрядах блока 3 регистра слова и управление работой устройства вновь будет пере25 дано блоку 65. Если после работы блока 48 блок-схема алгоритма признак ПВ11Б 1 (вхождение обнаружено с первой левой буквы слова V), то передача управления 47 производится сразу

30 без изменения положения слова V;

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

сигнал Л , по которому блок 8 управления выставляет признак левого сдвига ( блок 57) и вырабатывает тактовые импульсы ТИ1 и ТИ2 (блок 59) для блока 3 регистров слова и блока

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

ва вхождение обнарзшено, начиная с первой левой буквы слова V (блок 37), или вхождение обнаружено при левых сдвигах- слова V (блок 45), то блок 8 управления выставляет признак (блок 48) и сигналом ЗПБОП (блок 48) осуществляет запись в блок 5 организации подстановки информации, необходимой для организации подстановки W - S в слове V, где V Р , 50 левых букв вхождения на длину разно- либо V W,, либо V . ЕС- сти iLs-L l. Когда число сдвигов бу- ли длина вхождения равна длине подстановки, , блок 5 организации подстановки выставляет сигнал , по которому блок 8 управления снимает приг 55 знак ПВХ1, формирует внутренний признак ПЗП (блок 63).

Ввиду того, что признак , коммутатор 4 обеспечивает связь высти

« Y4.

дет равно разности I.Lj-Lsvb блок 5 организации подстановки вьщает признак (блок 62), по которому блок 8 управления передает к выполнению блока 63. После выполнения блока 63 в блоке 3 регистров- слова на место оставшейся части вхождения буДет записана подстановка 5.-

венно, по которым в них производится сдвиг информации влево до тех пор, пока число сдвигов не будет равно разности iLj-L I, гДе L - число букв вхождения; Lg - число букв подстановки. При этом левые сдвиги в блоке 3 регистров слова производятся с запретом циклического переноса (), что приводит к стиранию

левых букв вхождения на длину разно- сти iLs-L l. Когда число сдвигов бу-

сти

« Y4.

дет равно разности I.Lj-Lsvb блок 5 организации подстановки вьщает признак (блок 62), по которому блок 8 управления передает к выполнению блока 63. После выполнения блока 63 в блоке 3 регистров- слова на место оставшейся части вхождения буДет записана подстановка 5.-

Если при обнаружении вхождения , длина слова вхождения меньше длины слова подстановки В П, блок 5 организации подстановки вырабатывает сигнал Пр, по которому блок 8 управления выставляет признак правого сдвига (, блок 56) и вырабатывает тактовые импульсы ТИ1 и .ТИ2 (блок 59) с блока 3 регистра слова и блока 5 организации подстановки соответственно, по которым в них производится сдвиг информации вправо до тех пор, пока число сдвигов не будет равно разности | Lg-L f. При этом пра вые сдвиги в блоке 3 регистров слова производятся с запретом циклического переноса (), что приводит к сдвигу слова V на длину разности . Когда число сдвигов будет равно разности, блок 5 организации подстановки выдает признак Б П (блок 62), по которому блок 8 управления передает к выполнению блока 63 обеспечивающего запись поХ1;становки S в слово V,

Если в результате работы устройства алгоритм приходит к блоку 65, а признак записи подстановки отсутствует и формула последняя(ГШФ 1, блок 66 то устройство заканчивает работу, вы рабатьюая признак СТОП (цепь алгоритма с непоследней формулой рассмотрена ранее).

Если подстановка для данной фор- мулы выполнялась (), то для заключительной формулы (, блок 37) блок 8 управления вырабатьшает сигнал СЗпС, обеспечивающий перезапись обработанного слова V в блок 1 па- мяти слова, и выставляет сигнал стоп, останавливая работу устройства. Если формула незаключительная (), блок 8 управления вьщает сигнал Сбр СгА (блок 68), что приво- дит к выбору из блока памяти 7 формул первой формулы из списка, и далее цикл работы устройства повторяется (после выполнения блока 71).

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

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

g 0 5

0

г Q g

Q

g

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

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

11

вв: сигналы ПЛС и ТИ1 (условие ПВХ1 х X ЩТС ТИ1).

После обнаружения границы слова при .циклическом сдвиге влево, т.е. при условии ПВХ1 1ШС ТК1 в соответ- сфии с блок-схемой алгоритма (фиг. 6, блЬк 64), на входы блока 3 регистров слова поступят сигналы РПС.(разрешение правого циклического сдвига), ППС (признак правого сдвига) и очередные тактовые импульсы ТИ1, т.е. вьполнится условие IBX1 РПС ППС х X ТИ1. При этом сигнал РПС поступит через первые входы специализирован- ньх регистров 9 на первые входы пер- вьх элементов И13 и организует цепи правого ци1шического сдвига информа- Ц1:И с тар выходов вторых реверсшзных регистров 15 через элементы И13 в первые реверс шные регистры 14. Сиг- игл ППС- через пятые входы специапи- 31-рованных регистров 9 поступит на

пе К вп Г1

бг щ

10

15

20

рвые входы реверсивных регистров

и через четвертые элементы И18 на 25 юрые входы перв ых реверсивных растров 14, разрешая тем самым по- йтовый циклический сдвиг информа3

35

40

:и вправо во-всех первых 14 и вторых 15 рервесивных регистрах, осуществляемый при поступлении каждого тгжтового импульса ТИ1 на восьмой вз:од блока 3 регистров-слова.

Циклический сдвиг вправо будет осуществляться до обнаружения границы слова V, что приведет к тому, что слово V будет возвращено в реверсив- Hiiie регистры 14 и сдвинуто вправо на одну букву. При этом с входов блока 3;регистров слова сигналы РПС, ППС и TJJll будут сняты (условие ПВХ1 РПС ШС ТИ1), но будут вновь (для воз- в:р ащения слова V в исходное положе- левая буква слови V должна быть записана в первые разряды первых ре- 45 вфрсивных регистров 14) поданы сигна- 1ШС и один тактовый импульс ТИ1 Н&. входы блока 3 регистров слова, которые и осуществляют сдвиг слова V н& одну влево. Все сдвиги вправо и 50 с,|1виг влево на одну букву осуществля- ю|гся в соответствии с блоками 64 - &0 (фиг. 6) блок-схемы алгоритма.

Если же вхождение W в слово V было обнаружено, то на третьем входе nqji- 55 вйтся признак ПВХ1 и через третьи специализированных регистров 9 И элементы НБ19, ИЗ, И4 запретит левые и правые сдвиги вторых реверсив145534512

ньк регистров 15 и передачу информации циклического сдвига через вторые элементы И16 из первых реверсивных регистров 14. Теперь при поступлении сигналов ПЛС ТИ1 или ППС ТИ1 будут осуществляться правые и левые сдвиги информации только в первых реверсивных регистрах 14. Очевидно, что при левых сдвигах первых реверсивных регистров 14 информация будет по- буквенно стираться, а при правых - смещаться вправо на число предшествующих тактовых импульсов ТИ1. При этом при правых сдвигах может возникнуть ситуация переполнения разрядной сетки (единица в т-м разряде хотя бы одного из первых реверсивных регистров 14). В этом случае через элемент ИЛИ 10, элемент 12 задержки, и элемент И11 будет выработан сигнал ПЕРЕПОЛНЕНИЕ (ПП V 1) на выходе признака переполнения блока 3 регистров слова.

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

При поступлении управляющих сигналов УИП по первым информационным вхо- дам блока 3 регистров на вторые-уп- равляющие входы первых реверсивных регистров 14 подстановка S, поступающая через вторые информационные входы блока 3 регистров слова и через входы специализированных регистров 9 iна информационные входы первьк ревер- 1СИВНЫХ регистров 14 по сигналу разрешения записи ЗПИ,- будет запиа ана в первые реверс ивные регистры 14, образуя новое слово V, в сочетании Р,8Р1Или SP, Pi, или .

Если V PiP|S или V/ , то слово V будет сдвинуто вправо

так, чтобы его первая буква оказалась в левых разрядах реверсивных регистspoB, как бьто описано (с организаци ей циклического сдвига вправо до границы слова и на один такт влево), по

командам из блока 8 управления.

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

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

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

так, чтобы его первая буква оказалась в левых разрядах реверсивных регистspoB, как бьто описано (с организаци ей циклического сдвига вправо до границы слова и на один такт влево), по

командам из блока 8 управления.

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

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

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

Если в процессе работы устройства в соответствующих байтах блока 3 per. гистра слова и слова W обнаруживается совпадение букв, соответствующие входные компараторы вьфабатывают сигналы логической единицы. И если при этом произойдет сравнение по всем байтам, то через соответствующие элементы ИЛИ 22 и при наличии на втором

того, выходы элементов ИЛИ 30 являются не информационными входами блока 5 организации подстановки,с первого входа которого поступает сигнад, раз- решения записи значений L и L соответственно, а на одном из трех выходов цифрового компаратора 27 появляются признаки Пр или , или Л, 10 причем при L LJ вьщается признак Пр, при I.. 1-5 - признак , при W Lj признак Л.

Если вхо}|даение меньше подстановки iLyj, Ljl то сигнал с выхода цифровходе блока б поиска вхождения сигна-15 вого Jco fflapaтopa 27 одновременно пола Чт.ПВХ откроется элемент И23, ко-, торый выработает сигнал ПВХ на выходе блока 6 поиска вхождения. Если же

ступает на второй вход второго элемента И29 и на входы второго регистра 28 сдвига и при поступлении тактовых импульсов ТИ2 с третьего входа 20 блока 5 организации подстановки начинается правый сдвиг (с записью 1 на каждом такте ТИ2 в левый разряд) второго регистра сдвига до тех пор, пока цифровой компаратор 27 не елисравниваемые слова V., и W различаются хотя бы в одной букве (в непустой своей части), то сигнал на выходе блока 6 поиска вхождения не вырабатывается.

Сигнал на выходе.блока 6 поиска

вхождения вырабатьтается и в том слу- 25 мет сигнал с первого -выхрда и выдаст

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

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

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

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

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

В П на надо понимать лишь как дополнительную запись слова в регистр с меньшие количеством логических единиц модуля разницы , что gQ обеспечивает (по сигналам блока В управления) подготовку места записи слова подстановки в блоке 3 регистров слова.

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

Логические условия: ХЗгПВХ; Х4:ПГС; Х5:Ш1Ф;

того, выходы элементов ИЛИ 30 являются не информационными входами блока 5 организации подстановки,с первого входа которого поступает сигнад, раз- решения записи значений L и L соответственно, а на одном из трех выходов цифрового компаратора 27 появляются признаки Пр или , или Л, причем при L LJ вьщается признак Пр, при I.. 1-5 - признак , при W Lj признак Л.

Если вхо}|даение меньше подстановки iLyj, Ljl то сигнал с выхода цифрового Jco fflapaтopa 27 одновременно пового Jco fflapaтopa 27 одновременно поступает на второй вход второго элемента И29 и на входы второго регистра 28 сдвига и при поступлении тактовых импульсов ТИ2 с третьего входа блока 5 организации подстановки начинается правый сдвиг (с записью 1 на каждом такте ТИ2 в левый разряд) второго регистра сдвига до тех пор, пока цифровой компаратор 27 не елисигнал со своего второго выхода (),

Если же вхождение больше подстановки iLvv Ljl, то цифровой компаратор 27 вьодает со своего выхода при0 знак Л, который поступит на третий выход блока 5 организации подстановки, на второй вход первого элемента И26, на входы регистра сдвига 25 и (при поступлении ТИ2) правый сдвиг в нем будет продолжаться до выполнения условия .

При поступлении сигнала CSV записи слова V в блок 3 регистров слова он с второго входа блока организации

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

При организации сдвигов в реги5

В П на надо понимать лишь как дополнительную запись слова в регистр с меньшие количеством логических единиц модуля разницы , что gQ обеспечивает (по сигналам блока В управления) подготовку места записи слова подстановки в блоке 3 регистров слова.

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

Логические условия: ХЗгПВХ; Х4:ПГС; Х5:Ш1Ф;

ХбШЗФ; Х8:Л; Х9:Пр; Х10::

nnVl; Х11:ПВПБ; Х12:ПЗП; X13jOnepaторы: У1:УОБОП: }; У2:УОБРС: и

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

У6:П8У: 1; У7:ЗПИ: 1; У8:ЧтПВК: 1;

У9:ПВ11Б: 1; У10:ПВ11Б: 0; УП : + lClfA5 l;,

У12:ПЛС: 1; У13:ПЛС: 0; У14:ТИ : 1;

yj5:nnC l; У16;ШС: 0; У17:РПС: 1;

У18:Р11С: 0; У19:Сбр У20:ЗПБОП: 10 нен с выходом признака переполнений

и третий входы блока управления соединены с третьим и четвертым информа ционными выходами блока памяти формул, входы с четвертого по шестой блока управления соединены с выходами с второго по четвертый блока орга низации подстановки соответственно, седьмой вход блока управления соеди 1; У21:ПЗП: 1; У22:ПЗП: 0; У23: :ПВХ1: 1| У24:1ШХ1: 0| У25:ЗПС: 1; , СБРОС: 0, ПУСК; 0; У27:СБРОС: 1; У28:ТИ2:.

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

При этом .для конкретности условия, 15 слова, информационные выходы блока па-.

мяти слова соединены с первой группой информационных входов коммутатора, вторая группа информационных входов которого соединена с вторыми информачто по команде У27 (Сброс: 1) пройз водится установка в исходное состояние всех элементов с памятью блока 8 управления счетчиком адреса памяти 7 формулы снимаются сигналы чтения ело- 21 ционными выходами блока памяти форва и формз лы (, ).

мул и вторыми информационными входа- Ми блока организации подстановки, а : выходы соединены с вторыми информационными входами блока регистров слоФормула изоб

р е т е н и я

мент задержки, вход которого соединен с шестыми управляющими входами специализированных регистров группы и является шестым управляющим входом блока регистров слова, выход эле мента задержки соединен с вторым вхо дом элемента И, первый вход которого соединен с выходом элемента Ш1И, а третий вход соединен с пятыми управ-

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

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

блока памяти слова и с первыми информационными выходами блока регистров слова, вторые информационные выходы которого соединены с входами дешифратора границы слова, девятый

вход блока управления является входом пуска устройства, десятый вход блока

управления является входом общего , сброса устройства, восемнадцатый выход блока управления явл;5ется выхо- дом признака окончания работы устройства, .

17

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

гистры, входы сброса которых соединены и являются вторым входом специали- 30 элементов ИЛИ-НЕ группы, входы кото- зированного регистра, информационные Рьк являются информационньми входами выходы первого реверсивного регистра являются вторыми выходами специализированного регистра, а информационные выходы старшего и младшего разря- 35 дов первого реверсивного регистра яв- ными входами блока поиска вхождения,

выход злемента И является выходом блока поиска вхождения, ()-й вход элемента И являе тся входом опроса 40

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

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

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

ю5534518

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

15

20

25

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

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

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

блока поиска вхождения.

0 -

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

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

19

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

45534520

становки, выход Меньше цифрового компаратора соединен с вторым входом второго элемента И, с входами сдвига вправо и левого разряда второго сдвигового регистра и является вторым выходом блока организации подстановки, выход Больше цифрового компаратора соединен с вторым входом первого эле- tO мента И, входом сдвига вправо и входом левого разряда первого сдвигового регистра и является третьим информационным выходом блока организации подстановки, первые входы элемен- 15 tOB ИЛИ второй группы объединены и являются первым управляющим входом блока организации подстановки, входы с второго по (К+1)-й (где К - длина кода знака в слове) элементов ИЛИ 20 второй группы являются вторыми информационными входами блока организации подстановки.

Физ.1

SФие.З г

ЧгifrOU

II fa.

w

iput-S

1