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

/2 4 С 06 ОПИСАНИЕ ИЗОБРЕТЕ ЕЛЬСТВ Н АВТОРСКОМУ С ий инс КореневсПлотников во СССР 6, 1984.СССР 4, 1984. тельс15/ льств Р 15/ И НОР и н носит анА тики ехническим средствам ичислительной техникибработки информ к едназннных ено для о о токов и ссивов данных стово ычислительные ие относится к техниче Изобретем средств информационно-логики и вычислим информа ики и пре дназначено дл ных потоков и ового и число ельной те аботки и сивов да рмаци ных тек зада ответствиилгорифмамиия являетси сокраще о х теров в смальнымиизобретеродействи ми н повыше об Целе бь стовои в памяти при обработк ГОСУДАРСТ 8 ЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦ МАЛЬНЫХ АЛГОРИФМОВ МАРКОВА (57) Устройство для реализац мальных алгорифмов Марков о и числового, характеров в соответствиис заданными нормальными алгорифмами.Цель изобретения - повышение быстронформации за счет применения матеатического аппарата теории нормальых алгорифмов, позволяющего решать действия и сокращение объемов памя при обработке текстовой информации за счет применения математического аппарата теории нормальных алгорифмов, позволяющего решать вычислительные и инФормационно-логические задачи - достигается тем, что в устройство, содержащее блок организацииподстановки, коммутатор, блок памяти слова, дополнительно введены блокрегистров слова, дешифратор границыслова, блок поиска вхождения, блок управления, причем блок организацииподстановки содержит первую и вторуюгруппы элементов ИЛИ, первый и второй реверсивные регистры, первый ивторой элементы И и цифровой компаратор, блок регистров слова содержитэлемент И, элемент ИЛИ, элемент задержки и группу специализированныхрегистров, блок поиска вхождения содержит группу элементЬв ИЛИ-НЕ, группу цифровых компараторов,. группу элементов ИЛИ и элемент И, 4 з.п. ф-лы, 8 ил. ческие задачи.На фиг. 1 изображена структурная схема устройства; на Фиг. 2 - структурная схема блока регистров слова; на фиг. 3 - функциональная схема реверсивного регистра; на Фиг. 4 - структурная схема блока организации подстановки; на фиг. 5 - структурная схема блока поиска вхождения; на Фиг. 6 - блок-схема алгоритма работы устройства для реализации нормальных алгорифмов Маркова; на фиг. 7 - граф19 мационными входами первого сдвигового регистра, вход сброса которого со.единен с входом сброса второго сдвигового регистра и является третьим,управляющим входом блока организации,подстановки, входы разрешения работыпервого и второго сдвиговых регистров объединены и являются вторым управляющим входом блока организации 1 Оподстановки, выходы элементов ИЛИвторой группы соединены с соответствующими информационными входами второго сдвигового регистра и являютсяинформационными выходами блока организации подстановки, информационныевыходы первого и второго сдвиговыхрегистров соединены соответственнос первым и вторым информационнымивходами цифрового компаратора, выходпризнака равенства кодов являетсяпервым выходом блока организации под -1455345 20становки, выход Иеньше цифровогокомпаратора соединен с вторым входомвторого элемента И, с входами сдвигавправо и левого разряда второго одвигового регистра и является вторым выходом блока организации подстановки,выход "Больше" цифрового компараторасоединен с вторым входом первого элемента И, входом сдвига вправо и входом левого разряда первого сдвигового регистра и является третьим инФормационным выходом блока организации подстановки, первые входы элементов ИЛИ второй группы объединены иявляются первым управляюшим входомблока организации подстановки, входыс второго по (К+1)-й (где К - длинакода знака в слове) элементов ИЛИвторой группы являются вторыми информационными входами блока организацииподстановки.1455345 а х У ат а, а а 4 аб аб а, аб атт атт а атб атб 11Хт Хб ХбХ 1 ХбХ 11ХтрХт Хах,хХб Хт ХаХб Хтт ХтбХ 11 Хтб ХбХб Хт 1 ХтбХб ХтбХб Ха"б ХтхХб ХЦ7 атб атт атб Составитель О, ГречухинаТехред М. Ходанич Корректор С Редактор Е, Копча Черни Заказ 7456/55 Тираж 667 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при Г,"П СССР 113035, Москва, Ж, Раушская наб д. 45 Ул, Проектная, 4 Производственно-полиграфическое предприятие, г. Ужгород,аб ау а 4 аб аб ат а, Ъ а 4 аб аб а 9 а, ат ат а, ат атт ать а аб атб Отб а,б атт а, ат 1 атб а, а 4 аб ат 4 а,ц а, а 4 ат 4 аат ат Хт7Х, Х,ХбХб Х 4Х,хбХ 4 хб77Хб44 Х 4Х 11юХтбХ 4 ХтбХ 411 Ут й У 41УбУф Уб УбУ 1УбУб .УттУа УаЬб УббУббУт Уп У 4Уб Ут 4Уб Ут 4Утб Утб УттУаУббУ 14УхбУ 14Уи УтбУтбУт 4Ут6 ОУббУттит,УтрУт УтбУтб УоУХ 4Ут 4 УтбУббУт 4 УтбУт Уо Утб Убт Уб 4УгбУт Ухх УХ 4Утх У 11 УтбУтбУббУббУт Ья У 94УтбУбб У, Уб Уб У 4 Уб Уб, У Уб Уб Уб Уб Ъ Уп У 11 Ф Утт Ут 4 Утб Ттт Утб Уб Утб % Уе Ъ Ъ Уе Убб Ь Уб Ъ Утб Ъ У 4 б Утб Угу 1 8 3б 7 8 У 10 17 1 г О 74 73 1 В 17 18 7 У гв г 1 гг гя г О 86 г 7 гв ЯД Ю Л зг зз юи л Лб 37 ЗВ ЗУсхема алгоритма Функционирования блока управления; на Фиг, 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.Устройство работает следующим образом.Теория алгорифмов Маркова является математическим аппаратом, описывающим формально широкий класс процессов преобразования информации,называемых нормальными алгорифмами,Всякий нормальный алгорифм работаетнад словами, заданными в некоторомФиксированном алфавите. Работа нормального алгорифма заключается в выполнении двух операций: распознаваниевхождения одного слова в другое;осуществление подстановки третьегослова на место того слова, которое входит в исходное.Нормальный алгорифм представим конечным числом Формул подстановок.Каждая формула подстановки имеетдва признака использования: текущий и заключительный, Текущий признак определяет применение Формулы столька раз, сколько раз слово, вхождение которого распознается, входит в оборабатываемое слово. Заключительный признак определяет применение форму 10 15 20 25 30 35 40 45 50 55 лы при распознанном вхождении один и только один раз, что обозначается специальным символом, В качестве символов признаков используются пОи для текущего и "1" для заключительного признака, При срабатывании любой текущей формулы подстановки следующей формулой, включаемой в работу, является первая Формула из списка Формул алгорифма, При срабатывании любой заключительной Формулы подстановки алгорифм прекращает свою работу и выдается результат. Алгорифм также прекращает свою работу, если включенная в обработку слова формула подстановки является, последней в алгорифме и вхождение не имеет места.В дальнейшем символ "О" используется для любой промежуточной формулы подстановки и "1" для последней фор мулы алгорифма.Блок-схема алгоритма работы устройства для реализации нормальных алгорифмов Маркова приведена на фиг, 6, на которой позиции 31-71 являются шагами алгоритма. Для описания алгоритма используются следующие идентификаторы: УОО - общий сброс элементов с памятью; ПУСК - команда запуска устройства; ПВПБ - признак вхождения, начинающийся с первой буквы; ЧТС - потенциал чтения слова из памяти слова; ЧТФ - потенциал чтения формулы из памяти формул; ПБЧ - сигнал переключения коммутатора для записи, слова в блок регистров слова; ЗпИ - сигнал разрешения записи информации в блок регистров слова; ЧТ ПВХ - сигнал опроса наличия вхождения; ПВХ - сигнал реакции наличия вхождения;ПВХ 1 - признак наличия вхождения;ПГС - признак границы слова; ППф - признак последней формулы; +1 СгА - управление адресом памяти формулы; ЗпС - сигнал записи слова в память слова; СТОП - признак останова устройства; Зп БОП - сигнал записи подстановки в блок организации подстановки; В = П - признак равенства длин слов вхождения и подстановки; Л - признак выполнения условия "вхожде - ние больше подстановки"; Пр ; .признак выполнения условия вхождение меньше подстановки; ПЛС - признак левого сдвига; ППС - признак прлвого сдвига; ТИ 1 - тактовые импульсы сдвига в блоке регистров словл; ТИ 2 тактовые импульсы сдвп л п блок ор 1455345ганизации подстановки; ПЗП - признакзаписи подстановки (внутренний потенциал блока управления); РПС - потенциал разрешения перезаписи инФормации вправо для блока регистров слова;ПЗФ - признак заключительной формулы,Сбр СгА - сброс счетчика адреса памяти формул; УОБОП - установка в исходное состояние блока организацииподстановки; ПП Ч - признак переполнения разрядной сетки блока регистров слова,По сигналу "УОО" (фиг1 и 6) всеэлементы устройства с памятью устанавливаются в исходное состояние,По сигналу "Пуск" устройство начинаетсвою работу, выставляя для блока 1памяти слова и блока 7 памяти формулпотенциалы ЧТС и ЧТФ, в результатечего на выход блока 1 памяти словавыдается обрабатываемое слово, а навыходе блока 7 памяти формул выдаются коды слов вхождения Ы, подстановки Я и признаки заключительной ПЗФпоследней ППФ формулы. При этом блок7 памяти формул разделена на 4 зоны:в первой зоне записаны слова подстановок, во второй зоне - слова вхождений, в третьей зоне - признаки заключйтельной формулы (один разряд),в четвертой зоне - признак последнейформулы (один разряд) из списка. Читаемая строка образует одну формулу.В блоке 1 памяти слов и блоке 7 памяти формул слова Ч,и Я всегда записаны так, что первые буквы этихслов (кроме пустых) являются значительными, отсутствие буквы записывается нулями. Границы слава определяются по отсутствию значащих букв(байт буквы - не пустой). Слова пишутся без разрывов. На такте выбораинформации из памяти сигналом ПЯЧкоммутатор обеспечивает подключениевыходов блока 1 памяти слова к входамблока 3 регистров слова, по этому жесигналу блок 5 организации подстановки по выходу 1 дает разрешение на запись информации в блок 3 регистровслова намаксимальную длину слова иодновременно сигналом ЗПИ производится запись слова в этот блок (блоксхема алгоритма работы). На следующем такте блок 8 управления опрашивает блок 6 поиска вхождения сигналомЧтПВХ (блок 37) и, если вхождение обнаружено, на его выходе вырабатывается сигнал ПВХ (блок 38). Дополни 5 10 15 20 25 30 35 40 45 50 55 тельно на этом же такте блок 8 управления выставляет признак ПВПБ, При наличии ПВХ блок 8 управления выставляет признак ПВХ 1, При отсутствии ПВХ признак ПВХ 1 не выставляется и осуществляется проверка признака границы слова путем анализа сигнала ПГС на выходе дешифратора 2 границы слова (блок 39). Если слово Ч в блоке 3 регистров слова пустое (ПГС=О), а формула не последняя (ППФ=О), производится вызов следующей формулы из блока 7 памяти формулы путем выдачи сигнала +1 СгА в счетчик адреса блока 7 памяти формул (блок 41) и после выполнения команд блока 71 цикл работы повторяется с блока 7 блок-схемы алгоритма (фиг. 6).Если слово Ч пустое (ПГС=1) и формула последняя (ППФ=1), сигналом ЗПС производится перепись слова из блока 3 регистров блока в блок 1 памяти слова (блоки 38, 39, 40, 69) и устройство останавливает свою работу, вырабатывая признак "СТОП" (блок 70).Если при отсутствии вхождения (ПВХ=О) слово Ч не пустое (ПГС=О), блок 8 управления сничает признак вхождения, начинающийся с первой буквы (ПВПБ=О, блок 42), выставляет признак левого сдвига ПЛС=1 (блок 58) и вырабатывает импульс сдвига ТИ 1, циклически сдвигающий влево анализируемое слово Ч на одну букву в блоке 3 регистров слова. Сигналом ЧТПВХ опрашиваем блок 6 поиска вхождения и про" веряем наличие признака границы слова ПГС, Если слово не пустое (ПГС=О) и вхождения нет (ПВХ=О), повторяются сдвиги влево (переход на блок 53) до тех пор, пока либо появится признак границы слова ПГС= 1 (блок 14), либо будет обнаружено вхождение (ПГС=О и ПВХ=1) - блоки 44 и 45, после чего блок 8 управления выставляет признак ПВХ 1=1, (блок 48), снимает признак левого сдвига (ПЛС=О) для блока 3 регистров слова и переходит к выполнению ветви блок-схемы алгоритма начи" нающейся с блока 48. Если возник при" знак границы слова ПГС=1, то блок 8 управления снимает признак левого сдвига ПЛС=О, выставляет признак правого сдвига (ППС=1), признак циклической перезаписи информации вправо (РПС=1) - блок 47, и выдает тактовый импульс ТИ 1 (блок 51), обеспечивающий, в блоке 3 регистров слова правый цик 1455345девический сдвиг на один байт. Далееанализируется наличие признака граниЦы слова ПГС (блок 66) и, если ПГС=О,сдвиг вправо повторяется до появле 5ния ПГС=1, по которому блоком 8 управления вырабатывается признак леЙого сдвига ПЛС=1 (блок 55), выдается один тактовый импульс ТИ 1=1(блок 58) и снимается признак 10левого сдвига ПЛС=О (блок 60),В результате выполнения этой ветвиалгоритма сдвинутое ранее влево слово 7 возвращается в исходное положение и ввиду, того, что в полностью . 15просмотренном слове 7 не было обнаружено вхождение, необходимо произвестианализ признаков заключительной и(или) последней Формулы, для чегопроизводится переход к очередной общей ветви работы алгоритма, начинающейся блоком 65, в соответствии скоторым блок 8 управления проверяетсостояние признака записи подстановг,ки, а так как записи подстановки не 25,последней Формулы (блок бб). ЕслиФормула не последняя (блок бб),ППФ=О, производится смена формулы,путем выдачи сигнала +1 СгА, производится сброс внутреннего признакаПЗП блока 8 управления, осуществляет,ся установка в исходное состояниезлементов блока 5 организации подстановки сигналом УОБОП, сбрасываетсяпризнак ПВХ 1 (блок 71). Цикл работыустройства повторяется, начиная счтения ПВХ и установкой признакаПВПБ (блок 37).Если в результате работы устройства вхождение обнаружено, начиная спервой левой буквы слова 7 (блок 37),или вхождение обнаружено при левыхсдвигах слова 7 (блок 45), то блок8 управления выставляет признак 45ПВХ=1 (блок 48) и сигналом ЗПБОП(блок 48) осуществляет запись в блок5 организации подстановки инФормации,необходимой для организации подстановки И - Б в слове 7, где 7 = Р,11 Р, 50либо 7 = И,Р,Р, либо 7 = Р,РИ. Если длинавхождения равна длине подстановкйблок 5 организации подстановки выставляет сигнал В=П, по которому блок 8 управления снимает пригзнак ПВХ 1, формирует внутренний признак ПЗП (блок 63),Ввиду того, чтЬ признак ПЯ 7=0,коммутатор 4 обеспечивает связь выхода блока 7 памяти формул (по шинамподстановки 8) с входами блока 3, регистров слова и ввиду того, что блок5 организации подстановки по выходам1 выставляет вектор признаков длиныместа подстановки, начиная с левойбуквы слова, оказывается подготовленным для записи подстановки со стира,нием обнаруженного вхождения, Записьподстановки осуществляется сигналомЗПИ .(блок 48), после подстановкиблоком 8 управления анализирует внутренний признак наличия вхожденияначинающегося с первой буквы слова7 (блок 64).Если вхождение не было обнаружено(ПВПБ=О), то повторяется цикл работыблоков 47, 49, 51, 53, 55, 58, 60,который приводит к установлению слова 7 таким образом, что его леваябуква оказывается в левых разрядахблока 3 регистра слова и управлениеработой устройства вновь будет передано блоку 65. Если после работы блока 48 блок-схема алгоритма признакПВПБ=1 (вхождение обнаружено с пер-.вой левой буквы слова 7), то передача управления 47 производится сразубез изменения положения слова 7;Если при обнаружении вхождениядлина слова вхождения больше длиныслова подстановки ВП, блок 5.организации подстановки вырабатываетсигнал Л, по которому блок 8 управления выставляет признак левого сдвига (ПЛС=1 блок 57) и вырабатываеттактовые импульсы ТИ 1 и ТИ 2 (блок 59)для блока 3 регистров слова и блока5 организации подстановки соответственно, по которым в них производитсясдвиг информации влево до тех пор,пока число сдвигов не будет равноразности Ь 5-Ь , где 1. - числобукв вхождения; Ь з - число букв подстановки, При этом левые сдвиги вблоке 3 регистров слова производятсяс запретом циклического переноса(ПВХ 1=1), что приводит к стираниюлевых букв вхождения на длину разностиЬ-Ь 1. Когда число сдвигов будет равно разностиЬз,ц 1, блок 5организации подстановки выдает признак В=П (блок 62), по которому блок8 управления передает к выполнениюблока 63. После выполнения блока 63в блоке 3 регистров слова на местооставшейся части вхождения буДет записана подстановка 5, 1455345 ОЕсли при обнаружении вхождения, длина слова вхождения меньше длины слова подстановки ВП, блок 5 орга - низации подстановки вырабатывает5 сигнал Пр, по которому блок 8 управления выставляет признак правого сдвига (ППС=1, блок 56) и вырабатывает тактовые импульсы ТИ и ТИ 2 (блок 59) с блока 3 регистра слова и блока 5 организации подстановки соответственно, по которым в них производится сдвиг информации вправо до тех пор, пока число сдвигов не будет равно разности 1 з1, При этом пра 15 вые сдвиги в блоке 3 регистров слова производятся с запретом циклического переноса (ПВХ=), что приводит к сдвигу слова Ч на длину разностиЬ.щ . Когда число сдвигов будет равно разности, блок 5 организации подстановки выдает признак В = П (блок 62), по которому блок 8 управления передает к выполнению блока 63, обеспечивающего запись подстановки Я 25 в слово Ч.Если в результате работы устройства алгоритм приходит к блоку 65, а признак записи подстановки отсутствует и Формула последняя(ППФ=1, блок 66) ЗО то устройство заканчивает работу, вы - рабатывая признак СТОП" (цепь алгоритма с непоследней Формулой рас смотрена ранее)Если подстановка для данной Формулы выполнялась (ПЗП=1), то для заключительной Формулы (ПЗФ=1, блок 37) блок 8 управления вырабатывает сигнал СЗпС, обеспечивающий перезапись обработанного слова Ч, в блок 1 па- мяти слова, и выставляет сигнал "СТОП", останавливая работу устройства. Если формула незаключительная (ПЗФ=О), блок 8 управления выдает сигнал Сбр СгА (блок 68), что приво дит к выбору из блока памяти 7 формул первой формулы из списка, и далее цикл работы устройства повторяется (после выполнения блока 71).Блок 3 регистров слова (фиг. 2) 50 работает следующим образом.Для записи слова Ч в реверсивные регистры 14 через девятые входы специализированных регистров 9 и через вторые информационные входы блока 3 регистров слова на информационные входы первых реверсивных регистров 14 выставляется слово Ч, а через первые информационные входы блока 3 регистров слова и через восьмые входыспециализированных регистров 9 навторые управляющие входы первых реверсивных регистров 14 подаются сигналы разрешения записи. Одновременнос ними на седьмой управляющий входблока 3 регистров слова подается сигнал ЗПИ, который через седьмые входыспециализированных регистров 9 поступает на входы записи первых реверсивных регистров 14 и производит записьслова Ч. При отсутствии вхождения М в слово Ч (отсутствует признак ПВХ 1) сигнал с третьего управляющего входа блока 3 регистров слова через третьи входы специализированных регистров 9 и элементы РЕ 19 поступает на первые входы элементов И 16 - 18, подготавливая цепь циклического сдвига информации влево из первых реверсивных регистров 14 во вторые реверсивные регистры 15 и при наличии признака левого сдвига ПЛС, который с пятого управляющего входа блока 3 регистров слова через четвертые входы специализированных регистров 9 поступает на входы сдвига влевопервых реверсивных регистров 14 и через открытые элементы ИЗ на входы сдвига влево вторых реверсивных регистров 15, разрешая левый сдвиг первого 14 и второго 15 реверсивных регистров, реверсивный сдвиг влево которых будет осуществляться синхронно при поступлении тактовых импульсов ТИ 1 с шестого управляющего входа блока 3 регистров слова через шестые входы специализированных регистров 9 на первые управляющие входы первых реверсивных регистров 14. При этом информация из первых разрядов 1 р реверсивных регистров будет переписываться через вторые элементы И 16 специализированных регистров 9.в старший разряд реверсивных регистров 15 и изменяться на вторых информационных вьмо дах блока 3 регистров слова со сменой букв в сдвигаемом слове Ч. Циклический сдвиг в первых 14 и вторых 15 реверсивных регистрах будет продолжаться до тех пор, пока не будут обнаружены либо вхождение (ПВХ 1=1), либо дешифратор границы слова (ДГС, Фиг. 1) не выдаст сигнал границы слова в блок 8 управления, который снимает с входом блока 3 регистров слова сигналы ПЛС и ТИ 1 (условие ПВХ 1 х х йС ТИ 1).После обнаружения границы слова при ,циклическом сдвиге влево, т.е, прИ условии ПВХ ПЛС ТИ 1 в соответствии с блок-схемой алгоритма (Фиг, б, блЬк 64), на входы блока 3 регистров слова поступят сигналы РПС.(разреш ие правого циклического сдвига),(признак правого сдвига) и очере ные тактовые импульсы ТИ 1, т.е. вь олнится условие 1 ВХ РПС ППС х х И 1. При этом сигнал РПС поступит ч рез первые входы специализированнь регистров 9 на первые входы первь элементов И 13 и организует цепи п авого циклического сдвига информа- ц с шр выходов вторых реверсивных р гистров 15 через элементы И 13 в п рвые реверсивные регистры 14. Сиги ППС через пятые входы специализ рованных регистров 9 поступит на первые входы реверсивных регистров 1 и через четвертые элементы И 18 на ворые входы первых реверсивных реги стров 14, разрешая тем самым поб.йтовый циклический сдвиг информаи вправо во всех первых 14 и вто- Р 15 рервесивных регистрах, осушес вляемый при поступлении каждого т тового импульса ТИ 1 на восьмой в од блока 3 регистров слова.Циклический сдвиг вправо будет о уществляться до обнаружения грани слова Ч что приведет к тому, что ово 7 будет возвращено в реверсивн 1 е регистры 14 и сдвинуто вправо на одну букву. При этом с входов блока 3 регистров слова сигналы РПС, ППС и ТЙ будут сняты (условие ПВХ 1 РПС 1 П 1 С ТИ 1), но будут вновь (для возвращения слова Ч в исходное положене левая буква слова 7 должна быть записана в первые разряды первых ревФрсивных регистров 14) поданы сигнал 9 ПЛС и один тактовый импульс ТИ 1 нВ входы блока 3 регистров слова, которые и осуществляют сдвиг слова Ч на одну влево, Все сдвиги вправо и сдвиг влево на одну букву осуществляювся в соответствии с блоками 64 - 6 (фиг. 6) блок-схемы алгоритма.Если же вхождение М в слово 7 было обнаружено, то на третьем входе появИтся признак ПВХ 1 и через третьи вХоды специализированных регистров 9 и элементы НЕ 19, ИЗ, И 4 запретит левье и правые сдвиги вторых реверсив 455345 12ных регистров 15 и передачу информации циклического сдвига через вторыеэлементы И 16 из первых реверсивных5регистров 14. Теперь при поступлениисигналов ПЛСТИ 1 или ППСТИ 1 будутосуществляться правые и левые сдвиги информации только в первых ревер"сивных регистрах 14. Очевидно, что10 при левых сдвигах первых реверсивныхрегистров 14 информация будет побуквенно стираться, а при правых -смещаться вправо на число предшествующих тактовых импульсов ТИ 1. Приэтом при правых сдвигах может возникнуть ситуация переполнения разрядной сетки (единица в ш-м разряде хотя бы одного из первых реверсивныхрегистров 14). В этом случае через2 О элемент ИЛИ 1 О, элемент 12 задержки,и элемент И 11 будет выработан сигнал"ПЕРЕПОЛНЕНИЕ" (ПП 7 1) на выходепризнака переполНения блока 3 регистров слова,25 После обнаружения вхождения записьподстановки Б в слово Ч осуществля-ется следующим образом.При поступлении управляющих сигналов УИП по первым информационным вхоу дам блока 3 регистров на вторые уп"равляющие входы первых реверсивныхрегистров 4 подстановка Б, поступающая через вторые информационные входы блока 3 регистров слова и черезвходы специализированных регистров 9на информационные входы первых ревер,сивных регистров 14 по сигналу разрешения записи ЗПИ,. будет запиаана впервые реверсивные регистры 14, образуя новое слово 7, в сочетанииР,БРили БР, Р, или Р,РБ.Если 7= РГБ или 7 = Р, БР,то слово Ч, будет сдвинуто вправотак, чтобы его первая буква оказалась45 в левых разрядах реверсивных регистров, как было описано (с организаци"ей циклического сдвига вправо до границы слова и на один такт влево), покомандам из блока 8 управления.По сигналу ЗПИ открываются вторыеэлементы И управления синхровходамии информация будет записываться только в те триггеры, где по входам Сстоят логические единицы.Блок 6 поиска вхождения (фиг. 4)работает следующим образом.Для получения сигнала о наличиивхождения на первый и второй информационные входы названного блока по 14553451413ЭО дается информация Ч, из блока 3 регистров слова и через коммутатор 4 из памяти 7 формулы вхождение У соот- " ветственно.Если в процессе работы устройства в соответствующих байтах блока 3 ре- гистра слова и слова М обнаруживается совпадение букв, соответствующие вХОдные компараторы вырабатывают 10 сигналы логической единицы. И если при этом произойдет сравнение по всем байтам, то через соответствующие элементы ИЛИ 22 и при наличии на втором входе блока б поиска вхождения сигна ла Чт.ПВХ откроется элемент И 23, ко-. торый выработает сигнал ПВХ на выходе блока б поиска вхождения. Если же сравниваемые слова Ч и М различаются хотя бы в одной букве (в непустой 20 своей части), то сигнал на выходе блока б поиска вхождения не вырабатывается.Сигнал на выходе. блока б поиска вхождения вырабатывается и в том слу чае, когда первых подряд значащих букв по всей значащей длине слова У вхождения с буквами слова Ч, блока 3 регистров слова соответственно при условии, что вся оставшаяся часть слова У вхождения имеет нулевое содержание. Это достигается срабатыванием соответствующих элементов ИЛИ - НЕ 20, которые через элементы ИЛИ 22 открывают элемент И 23 для прохождения сигнала ЧтПВХ на выход блока б поиска вхождения.Блок 5 организации подстановки (фиг. 5) работает следующим образом.Установка в исходное состояние 40 производится сигналом УОБОП, поступающим с блока 5 организации подстановки на входы сброса регистров 25 и 28 сдвига. По первыми шестым входам блока 5 организации подстановки слово б М вхождения и 8 подстановки побуквенно подаются на входы первой группы элементов ИЛИ 24 и второй группы элементов ИЛИ 30 соответственно, на выходах которого сигналы появляются 60 лишь в том случае, если на их входах имеются значащие буквы (код значащей буквы хотя бы в одном разряде имеет значение логической единицы) и, сле. - довательно на четвертых входах реги . стров .25 сдвига и 28 появляется столько подряд следующих сигналов, сколько букв содержится в слонах Ю и 8 соответственно (1,ци 1.), Кроме того, выходы элементов ИЛИ 30 являются не информационными входами блока5 организации подстановки,с первоговхода которого поступает сигнал разрешения записи значений Ь, и Ьд соответственно, а на одном из трех вйходов цифрового компаратора 27 появляются признаки Пр или В=П, или Л,причем при 1 , с Ь выдается признакПр при Ь 1признак В Пф приЬ 7 Ь признак Л,Если вхождение меньше подстановки1 Ь ч ( 1То Сигнал с ВыхОДа ЦифРОвого коипаратора 27 одновременно поступает на второй вход второго элемента И 29 и на входы второго регистра 28 сдвига и при поступлении тактовых импульсов ТИ 2 с третьего входаблока 5 организации подстановки начинается правый сдвиг (с записью "1"на каждом такте ТИ 2 в левый разряд)второго регистра сдвига до тех пор,пока цифровой компаратор 27 не снимет сигнал с первого:выхода и выдастсигнал со своего второго выхода (В П).Если.же вхождение больше подстановки 111. 1, то цифровой компаратор 27 выдает со своего выхода признак Л, который поступит на третийвыход блока 5 организации подстановки, на второй вход первого элементаИ 2 б, на .входы регистра сдвига 25 и(при поступлении ТИ 2) правый сдвигв нем будет продолжаться до выполнения условия В П.При поступлении сигнала иБЧ записи слова Ч в блок 3 регистров словаон с второго входа блока организацииподстановки через вторую группу элементов ИЛИ 30 поступает.на информационный выход блока 5 организацииподстановки.При организации сдвигов в регистрах смену признаков ВП на В П иВ ) П на В П надо понимать лищь какдополнительную зались слова в регистрс меньшим количеством логических едиНИЦ мОДулЯ РазниЦы Ьр Ьз 1 чтообеспечивает (по сигналам блока 8управления) подготовку места записислова подстановки в блоке 3 регистровслова,На фиг. 7 приведена отмеченнаяграф-схема алгоритма функционирования блока 8 управления, в которойвведены следуюшие обозначения (6).Логические условия: Х 1;"УОО"Х 2:"ПУСК"; Хз:ПВХ; Х 4:ПГС; Х 5:ППф;:ПВХ 1:=1; У 24;ПВХ 1:=О; У 25:ЗПС:=1;У 2 б:"СТОП", СБРОС:=О, ПУСК; =О;У 27:СБРОС:=1; У 28 фТИ 2;=1,При этом .для конкретности условия, 15 что по команде У 27 (Сброс;=1) производится установка в исходное состояние всех элементов с памятью блока 8 управления счетчиком адреса памяти 7 формулы снимаются сигналы чтения сло( ва и формулы (ЧТСф=О, ЧтФ:=О).Формула изо бре тения1. Устройство для реализации нормальных алгорифмов, содержащее блок организации подстановки, коммутатор, блок памяти слова, о т л и ч а ю - щ е е с я там, что, с целью повыше ния быстродействия и сокращения обь емов памяти нри обработке текстовой информации за счет применения математического аппарата теории нормальных алгорифмов, в него введены блок регистров слова, блок памяти формул, дешифратор границы слова, блок поиска вхождения, блок управления, первый и второй выходы которого соединены с первьщи и вторыми управляющими входами блока памяти слова соответствен но, третий выход соединен с входом опроса блока поиска вхождения, четвертый вьиод соединен с управляющим входом коммутатора и первым управляющим входом блока организации подста новки, пятый, шестой и седьмой выходы блока управления соединены соответственно с первым, вторым и третьки управляющими входами блока,памяти формул, выходы с восьмого по де О сятый соединены с управляющими входами с второго по четвертый блока организации подстановки соответствен. но, вьиоды с одиннадцатого по семнадцатый соединены соответственно с управляющими входами с первого по седьмой блока регистров слова, первый вход блока управления соединен с выходом блока поиска вхождения, второй и третий входы блока управления соединены с третьим и четвертым информа" ционными выходами блока памяти формул, входы с четвертого по шестой блока управления соединены с выходами с второго по четвертый блока организации подстановки соответственно, седьмой вход блока управления соединен с выходом признака переполнений блока регистров слова и с вьиодом признака переполнения устройства, восьмой вход блока управления соединен с выходом дешифратора гранюы слова, информационные выходы блока па-мяти слова соединены с первой группой информационных входов коммутатора, вторая группа информационных входов которого соединена с вторыми информационнымн выходами блока памяти формул и вторыми информационными входами блока организации подстановки, а выходы соединены с вторыми информационными входами блока регистров слова, первая группа управляющих входоВ которого соединена с первой группой управляющих выходов блока организации подстановки, первые информационные входы которого соединены с первыми информационными выходами блока памяти формул и вторыми информационными входами блока поиска вхождения, первые информационные входы которого соединены с информационными входами блока памяти слова и с первыми информационными выходами блока регистров слова, вторые информационные вы" ходы которого соединены с входами дешифратора границы слова, девятый вход блока управления является. входом пуска устройства, десятый вход блока управления является входом общего сброса устройства, восемнадцатый вы" ход блока управления является выходом признака окончания работы устройства, .2. Устройство по п. 1, о т л и - ч а ю щ е е с я тем, что блок регистров слова содержит группу регистров,. элемент ИЛИ, элемент И, элемент задержки, вход которого соединен с шестыми управляющими входами специализированных регистров группы и является шестым управляющим входом блока регистров слова, выход элемента задержки соединен с вторым входом элемента И, первый вход которого соединен с выходом элемента ИЗЫДИ, а третий вход соединен с пятыми управляющими входами специализированных регистров группы и является пятым управляющим входом блока регистров слова, выход элемента И является выходом признака переполнения блока регистров слова, входы элемента ИЛИ соединены с первыми выходами соответствующих специализированных регистров группы, вторые выходы которых яв ляются первыми информационными выходами блока регистров слова, третьи выходы специализированных регистров группы являются вторыми информационными выходами блока регистров слова, 15 первые, вторые, третьи, четвертые, седьмые, восьмая и девятая группы входов всех специализированных регистров группы являются соответственно четвертым, третьим, пятым, седьмым, 20 девятым управляющими, первой и второй группами управляющих входов блока регистров слова.3. Устройство по.п, 2, о т л и - ч а ю щ е е с я тем, что специализированный регистр содержит с первого по четвертый элементы И, элемент НЕ, первый и второй реверсивиые регистры, входы сброса которых соединены и являются вторым входом специали зированного регистра, информационные выходы первого реверсивного регистра являются вторыми выходами специализированного регистра, а информационные выходы старшего и младшего раэря- З 5 дов первого реверсивного регистра яв" ляются соответственно первым.и третьим выходами специализированного регистра, первый вход первого элемента И является первым входом специали зированиого регистра, а второй выход соединен со старшим разрядом второго реверсивного регистра, выход первого элемента И соединен с входом записи левого разряда первого реверсивного 45 регистра, информационные входы которого являются девятыми входами специализированного регистра, а вторые управляющие. входы являются восьмыми управляющими входами специализирован ; ного регистра, первые управляющие входы первого и Второго реверСивных , регистров соединены и являются шестым ,входом специализированного регистра, вход элемента НЕ является третьим 55 входом специализированного регистра, а выход соединен с первьми входами с второго по четвертый элементов И, второй вход второго элемента И соединен с младшим разрядом информационного выхода первого реверсивного регистра, а выход - с входом записи правого разряда второго реверсивного регистра, входы сдвига вправо и влевокоторого соединены соответственно свыходами четвертого и третьего элементов И, вторые входы которых являются соответственно пятьм и четвертымвходами специализированного регистраи соединены соответственно с входамисдвига вправо и влево первого реверсивного регистра, вход разрешения записи которого является седьмым входом специализированного регистра,4. Устройство по и. 1, о т л и -ч а ю щ е е с я тем, что блок поиска вхождения содержит группу элементов ИЛИ - НЕ, группу цифровых компараторов, группу элементов ИЛИ, элемент И, входы которого с первого поу 4К-й (где К - количество элементовИЛИ в группе) соединены с выходамисоответствующих элементов ИЛИ группы, первые входы которых соединеныс выходами соответствующих цифровыхкомпараторов группы, а вторые входысоединены с выходами соответствующихэлементов ИЛИ-НЕ группы, входы которых являются информационными входамиблока поиска вхождения и соединеныс первыми входами соответствующихцифровых компараторов, вторые входыкоторых являются первыми ннформационньки входами блока поиска вхождения,выход элемента И является выходомблока поиска вхождения, (К+1)-й входэлемента И является входом опросаблока поиска вхождения,5. Устройство по п. 1, о т л и - ч а ю щ е е с я тем, что блок организации подстановки содержит первую и вторую группы элементов ИЛИ, первый и второй сдвнговые регистры, цифровой компаратор, первый и второй элементы И, выходы которых соединены с первыми управляющими входами соответственно первого и второго сдвиговых регистров, а первые входы первого и второго элементов И обьедийены и являются четвертым управляющим входом блока организации подстановки, входы элементов ИЛИ первой группы являются первыми информационными входами блока организации подстановки, а выходы элементов ИЛИ первой группы соединены с соответствующими инфор