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

(5)5 Г 0 ПИСАНИЕ ИЗОБРЕТЕНИ 324/24 5,895.03.91. Бюл,21) 4684 22) 03,0 сти ническии Ф.Король арков льство 15/20, ство С 15/20,ПО технивычисисых симОСУДАРСТВЕННЫЙ КОМИТЕТИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГКНТ СССР К А ВТОРСКОМУ СВИДЕТЕЛЬСТ(54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИСТАНОВОК СЛОВ(57) Изобретение относится кческим средствам информатикилительной техники и может бытпользовано для обработки данн вольного и числового типов с помощьюнормальных алгорифмов состоящих исключительно из формул подстановок сдвухбуквенными левыми и правыми частями, Цель изобретения - увеличениебыстродействия при обработке информации по заданной схеме нормального алгорифма, содержащего исключительноформулы подстановки с двухбуквеннымилевыми и правыми частями. Поставленная цель достигается тем, что устройство содержит блок 1 памяти слов,блок 2 памяти вхождений, блок 3 памяти подстановок, узел 4 сдвига, коммутатор 5, первый узел 6 контроля обрабатываемого слова, узел 7 сравнения, блок 8 органиэации подстановки,элемент И 9, второй узел 1 О контроляобрабатываемого слова, элемент ИЛИНЕ 11, счетчик 12 и блок 13 управления, 7 ил.15 Узел 7 сравнения включает (фиг,2) элементы 14 хранения букв внутренне го и входного алфавита, первую 15, вторую 16 и третью 17 группы элементов И, элементы НЕ 18, с первого по третий элементы 19-21 задержки, триггеры 22 и элемент ИЛИ 23.Каскадный элемент 14 хранения букв внутреннего и входного выполнен (фиг. 3) на триггере 24, первом и втором элементах И 25 и 26 и элементе ИЛИ 27.Блок 8 организации подстановки содержит (фиг, 4) узлы 28 подстановки, регистр 29, элемент ИЛИ 30 иэлемент 31 задерЖки.Каждый узел 28 подстановки (фиг. 5) состоит иэ триггера 32 и элемента И 33.Первый узел 6 контроля обрабатываемого слова содержит (фиг. 6) пер 3 16351Изобретение относитСя к техническим средствам информатики и вычислительной техники и может быть использовано для обработки данных символьного и числового вида с помощью нормальных алгорифмов, состоящих исключительно из формул подстановок сдвухбуквенными левыми и правыми частями,Цель изобретения - увеличение10быстродействия при обработке информации по заданной схеме нормальногоалгорифма, содержащего исключительноформулы подстановки с двухбуквенными левыми и правыми частями,На фиг. 1 представлена схема предлагаемого устройства, на фиг. 2 - схема узла сравнения; на фиг, 3 - схема элемента хранения букв внутреннего и входного алфавита узла сравнения; на фиг, 4 - схема блока организации подстановки, на фиг, 5 - схемаузла подстановки блока организацииподстановки на фиг. 6 - схема первого узла контроля обрабатываемогб слова, на фиг. 7 - схема второго узлаконтроля обрабатываемого слова,Устройство содержит блок 1 памятислов, блок 2 памяти вхождечий, блок3 памяти подстановок, узел 4 сдвига, 30коммутатор 5, первый узел 6 контроля обрабатываемого слова, узел 7 сравнения, блок 8 организации подстановки, элемент И 9, второй узел 10 контроля обрабатываемого слова, элементИЛИ-НЕ 11, счетчик 12 и блок 13 управления. 92 Ьвый и второй элементы И 34 и 35 иэлемент ИЛИ 36,Второй узел О контроля обрабатываемого слова включает (фиг, 7) первый 37, второй 38 и третий 39 элементы И и элемент ИЛИ 40,Под формулой подстановки понимается слово видаЧ Р (1)где Ч - слово-вхождение;Р - слово-подстановка;О - признак формулы, 1(О, 1).Работа формулы подстановок над обрабатываемым словом заключается вобнаружении в нем слова-вхожденияи замены позиции слова-вхождениясловом-подстановкойПозиция вхождения является первой тогда, когда припросмотре обрабатываемого слова слева направо вхождение обнаружено первый раэ, Если признак формулы б = 1,то формула является заключительной,Она работает один раз и алгорифм,представляющий собой конечный списокФормул подстановок, прекращает своюработу, Если признак формулы б = О,то Формула используется столько раз,сколько раз обнаруживается ее вхождение в обрабатываемом слове. Еслиформула подстановок в списке простая, то при обнаружении первой позиции ее вхождения в обрабатываемомслове осуществляется подстановка, апереход выполняется на первую формулу алгорифма, Следующая формулаподстановок в алгорифме включаетсяв работу тогда, когда предыдущая формула подстановок не обнаруживаетни одной собственной позиции вхождения при полном просмотре всего обрабатываемого слова, Алгорифм заканчивает свою работу, если ни одна формула не срабатывает или срабатываетзаключительная формула. Рассматривается класс нормальных алгорифмов, у которых все формулы подстановок имеют непустые левые и правые части, длина каждой из которых равна двум буквам. При этом каждая из двух букв, составляющих слово- вхождение и слово-подстановку, принадлежит разным непересекающимся подмножествам исходного алфавита. В первой позиции слова-вхождения находятся буквы, принадлежащие одному из непересекающихся подмножеств исходного алфавита. Этому же подмножеству принадлежат буквы, которые нахо1635192 30 50 дятся во второй позиции слова-подстановки. Во второй позиции слова- вхождения находятся буквы из второго непересекающегося подмножества с пер-, вым подмножеством исходного алфавита, В первой позиции слова-подстановки находятся буквы, принадлежащие третьему подмножеству, непересекающемуся с первым и вторым подмножествами исходного алфавита.Далее используются следующие обозначения;ПУСК - команда запуска устройства,СБРОС - команда установки исход 15 ных состояний;ЧТС - команда чтения обрабатываемого слова из блока памяти слов;ЧТВ - команда чтения слов-вхождений из блока памяти вхождений в узел 20 сравнения;ЧТП - команда чтения слов-подстановок из блока памяти подстановок в блок организации подстановки;АРИФМ - признак арифметической 25 обработки (обработки числовой информации);ПРОШ 1 - управляющий вход первого узла контроля обрабатываемого слова для регистрации ошибок в буквах входного алфавита при обработке чиПРОШ 2 - управляющий вход второго узла контроля обрабатываемого слова для регистрации ошибок в буквах внутреннего алфавита при обработке чи 35 сел;ПРОШЗ - вход элемента И (для регистрации ошибок в буквах выходного алфавита при обработке чисел);ПОТОК - признак потоковой обработки;ППОТОК - значение управляющего входа коммутатора;УСТ 1. - команда записи всех единиц в счетчик;45ТИ - сигнал сдвига слова;ПНПД - признак начала поступления потоковых данных;ПКПД - признак конца поступления потоковых данных;ОШ 1 - признак ошибки при обработке чисел в букве входного слова;ОШ 2 - признак ошибки при обрвботке чисел в букве вспомогательного слова;ОШЗ - признак ошибки при обработке55 чисел в букве выходного слова;ПКС - признак конца списка одно- буквенных слов; 6Авар. ост, - признак аварийной остановки устройства;ПРС - команда приема результирующего слова из узла сдвига в блок памяти слов.По команде СБРОС: = 1 все элементы устройства устанавливаются в исходное состояние По команде ПУСК: - 1 устройство начинает работать. По команде ЧТВ: = 1 осуществляется параллельная передача левых частей формулы подстановок заданного нормального алгорифма иэ блока 2 памяти вхожденнй в узел 7 сравнения. Одновременно по команде ЧТП: = 1 таким же образом ведется загрузка блока 8 правыми частями формулы подстановок заданного нормального алгорифма из блока 3 памятиподстановок, В следующем такте анализируется признак АРИФМ и, если необходима обработка числовой информации, для узлов 6 и 10 и элемента И 9 устанавливаются признаки регистрации ошибок ПРОШ 1 = 1, ПРОШ 2 = 1, ПРОШЗ = 1, в противном случае, если обрабатывается символьная информация, указанные потенциалы устанавливаются в нулевые значения по командам ПРОШ 1: = О, ГРОШ 2; = О, ПРОШЗ: = О. Затем анализируется признак ПОТОК, который идентифицирует режим работы устройства, Если устройство работает в потоковом режиме (информация поступает от других устройств и передается на другие устройства), то ППОТОК: = 1. Затем анализируется признак начала поступления потоковых данных (от внешних источников) ПНДП и, если ПНДП = 1, по сигналу ТИ: = 1 данные, пройдя через коммутатор 5 и узел 6, который регистрирует ошибки в буквах входного алфавита в случае обработки числовой информации, сравниваются в узле 7 со словами-вхождениями задан-ного нормального алгорифма, В том же такте при обнаружении вхождения в обрабатываемом двухбуквенном слове блок 8 организации подстановки осу-,- ществляет подстановку, причем буквы слова-подстановки, стоящие во второй позиции, через узел 1 О поступают на вход узла 7 сравнения, а буквы, стоящие в первой позиции слова-подстановки, через элемент И 9 - на выходы устройства. Таким образом, результатом каждого такта работы (после загрузки узла 7 и блока 8 организации подстановки) устройства являетсяодна буква в первой позиции и однабуква во второй позиции слова-под"становки, причем первая может сразупоступить на обработку в другое уст"ройство. На каждом такте при обработке чисел также регистрируются тривида ошибок. Если ошибка обнаружена(ОШ 1 = 1 или ОШ 2 = 1, или ОШЗ = 1),то устройство выдает команду аварийного останова нЛвар. ост,", устройство заканчивает работу, если ПКПД = 1.Если устройство работает в автономном режиме (ПОТОК = 0), то по команде ЧТС: = 1 осуществляется параллельная передача обрабатываемогосписка однобуквенных слов из блокапамяти слов в узел 4, Одновременнозначение управпнющего входа коммутатора 5 устанавливается в нулевое значение по команде ППОТОК: = О, а счетчик 12 - в единичное состояние по команде УСТ: = 1. По сигналу ТИ: = 1в узле 4 осуществляется сдвиг вправо,в результате которого битовый срез,представляющий собой букву-слово, поступает на коммутатор 5, затем черезузел 6 - в узел 7 сравнения, где потому же сигналу ТИ: = 1 (с задержкой) происходит параллельное сравнение двухбуквенного обрабатываемогослова с левыми частями формул подстановок заданного нормального алгорифма. В этом же такте состояние счетчика 12 уменьшается на единицу, а также осуществляется подстановка и регистрируются ошибки. При нулевомсостоянии счетчика элемент ИЛИ-НЕ 11выдает признак конца списка обрабатываемых однобуквенных слов (ПКС = 401).Таким образом, в автономном режиме работы устройства в одном тактеосуществляется групповая компарацияслов-вхождений с двухбуквенным обрабатываемым словом, подстановка, регистрация ошибок в случае обработкичисловой информации и анализ признакаконца слова. В случае обнаруженияошибки (ОШ 1 = 1 или ОШ 2 = 1, илиОШЗ = 1) блок 13 управления выдаеткоманду аварийного остановаВыходные бу,вы накапливаются в узле 4,вытесняя по такту сдвига вправо обрабатываемые однобуквенные слова, ЕслиПКС = 1, то по команде ПРС: = 1 про 55исходит передача выходного слова вблок 1 памяти слов, и устройство заканчивает работу,Узел 4 сдвига выполняет параллельный прием всего списка однобуквенных обрабатываемых слов из блока памяти слов по команде ЧТС: = 1, последова" тельный (по букве) прием выходной последовательности однобуквенных слов по сигналу ТИ: = 1, параллельную выдачу в блок 1 памяти слов выходного списка однобуквенных слов и последовательную (по букве) выдачу списка на коммутатор 5.Узел 6 регистрирует ошибки первого типа-ошибки в букве входного алфавита при обработке числовой информации. При обработке числовой информации используются только четыре бита из байта входного однобуквенного слова, при этом ошибкой считаются следующие кодовые комбинации:1 1 1 О О 1 1О О О О 1 О 11 1 О 1 1 О 11 О О О О 1 ООстальные 4 бита байта нулевые,Узел 7 работает следующим образом. После запуска устройства (команда ПУСК: = 1) узел 7 загружается (из блока 2) левыми частями формул подстановок заданного алгорифма (команда ЧТВ: = 1), т.е, в каждый элемент 14 поступают команда ЧТВ: = 1 и соответствующий бит вхождения, Далее при поступлении двухбуквенного обрабатываемого слова по сигналу ТИ: = 1 через элемент 19 задержки осуществляется параллельное сравнение двух букв обрабатываемого слова со всеми двухбуквенными словами-вхождениями, хранящимися в узле 7. Прямой и инверсный биты обрабатываемого слова через элементы И 15 и 16 подаются на соответствующие элементы 14, Каждый элемент 14 регистрирует совпадение обрабатываемого бита и бита вхождения, Элементы И 17 собирают сигналы совпадения, и, если две буквы обрабатываемого слова совпали с двумя буквами одного иэ слов-вхождений, соответствующий триггер 22 устанавливается в единицу, Элемент ИЛИ 23 выдает признак вхождения ПВХ, по которому через злемент 21 задержки осуществляется сброс триггеров 22 в исходное состояние, Из всей совокупности выходов узла 7 только один выход несет едиии 1 ный потенциал, так9 163 как слова-вхождения альтернативны по отношению друг к другуБлок 8 организации подстановки работает следующим образом.После запуска устройства блок 8 органиэации подстановки загружается из блока 3 памяти правыми частями формул подстановок заданного алгорифма (команда ЧПТ: = 1), т,е. в каждый узел 28 поступают команда ЧТП:1 и соответствующий бит слова-подстановки, Далее иэ узла 7 на второй управляющий вход блока 8 организации подстановки поступает единичный сигнал ПВХ, На каждый узел 28 подстановки поступает сигнал с соответствующего триггера 22, который управляет выдачей бита подстановки, Таким образом, выход узла 28 подстановки является разрешенным информационным битом двухбуквенного слова-подстановки, Выходы ячеек "собираются" соответствующими элементами ИЛИ 30, где регистр 29 по сигналу ПВХ принимает двухбуквенное слово,Элемент И 9 используетсяфдля ре; гистрации ошибок третьего типа-ошибок выходного алфавита при обработке числовой информации, При обработке числовой информации используются только два первых (верхних) бита из байта выходной буквы-слова, при этом ошибкой считается кодовая комбинация: 1Остальные шесть битов0нулевые.Узел 10 регистрирует ошибки второго типа-ошибки в букве вспомогательного слова при обработке числовой информации. При обработке числовой информации используются только четыре первых (верхних) бита из байта буквы (вспомогательного слова), при этом ошибками считаются следующие кодовые комбинации:0 11 0 11 0 1г О 1Остальные (нижние) четыре бита -нулевые,Формула из обретенияУстройство для реализации подстановок слов, содержащее блок памяти1 слов, коммутатор, узел сдвига, узел5192, Осравнения, блок организации подстановки и блок управления причем пер вый выход блока управления подключен к входу записи блока памяти слон второй выход блока управления подключен к входу чтения блока памяти слов и входу считывания узла сдвига, вы 10 15 20 25 30 35 40 45 50 55 ходы первой группы которого подключены соответственно к информационным входам блока памяти слоя, третий, четвертый и пятый выходы блока управления подключены соответственно к входу синхронизации узла сдвига, управляющему входу коммутатора и первому управляющему входу блока органиэации подстановки, вход запуска устройства подключен к входу запуска блока управления, шестой выход которого подключен к выходу признака аварийного останова устройства, о т л и ч а ющ е е с я тем, что, с целью увеличения быстродействия при обработке информации по заданной схеме нормального алгорифма, содержащего исключительно формулы подстановки с двухбуквенными левыми и правыми частями, в него введены блок памяти вхождений, блок памяти подстановок, первый и второй узлы контроля обрабатываемого слова элемент И, элемент ИЛИ-НЕ и счетчик, причем третий выход блока управления подключен к вычитающему входу счетчика и входу синхронизации узла сравнения, информационные входы первой группы которого подключены соответственно к выходам блока памяти вхождений, информационные выходы счетчика подключены к входам элемента ИЛИ-НЕ, выход которого подключен к входу признака конца списка однобуквенных слов блока управления, седьмой выход которого подключен к информационному входу счетчика, выходы блока памяти слов подключены соответственно к информационным входам первой группы узла сдвига, выходы второй группы которого подключены соответственно к информационным входам первой группы коммутатора, выходы которого подключены к информационным входам первого узла контроля обрабатываемого слова и информационным входам второй группы узла сравнения выход и выходы группы которого подключены соответ-. ственно к второму управляющему входу и информационным входам первой группы блока органиэации подстановки, информационные входы второй группы которо 1635192 12го подключены к выходам блока памятиподстановок, выходы первой группыблока организации подстановок подключены к входам группы элемента И, инАорма 1 ионным входам второй группы узла сдвига и информационным выходамустройства, выходы второй группы блока организации подстановок подключенык информационным входам второго узла ,контроля обрабатываемого слова и ин-,формационным входам третьей группыузла сравнения, инФормационные входыустройства подключены соответственнок информационным входам второй группы коммутатора, восьмой выход блокауправления подключен к управляющемувходу первого узла контроля обрабатываемого слова, выход которого подключен к первому входу признака ошибки блока управления, девятый выходкоторого подключен к входу чтенияблока памяти вхождения и входу признака разрешения работы узла сравнения, десятый и одиннадцатый выходыблока управления подключены соответственно к управляющему входу второгоузла контроля обрабатываемого словаи входу элемента И, выходы которыхподключены соответственно к второмуи третьему входам признака ошибкиблока управления, входы режима с первого по четвертый которого подключены соответственно к входам признакаарифметической обработки, признакапотоковой обработки, признака началапоступлення данных и признака концапоступления данных, причем первыйузел контроля обрабатываемого словасодержит первый и второй элементы Ии элемент ИЛИ, причем с первого почетвертый информационные входы первого узла контроля обрабатываемого слова подключены соответственно к перво 5 10 15 20 25 30 35 40 му входу первого элемента И, второму(инверсному) входу первого элементаИ, первому входу второго элемента Ии второму (инверсному) входу второгоэлемента И, управляющий вход первогоузла контроля обрабатываемого словаподключен к третьим входам первогои второго элементов И, выходы которыхподключены к входам элемента ИЛИ,выход которого подключен к выходу первого узла контроля обрабатываемогослова, причем второй узел контроляобрабатываемого слова содержит первый, второй и третий элементы И иэлемент ИЛИ, первый информационныйвход второго узла контроля обрабатываемого слова подключен к первым входам первого и второго элементов И ипервому (инверсному) входу третьегоэлемента И, второй информационныйвход второго узла контроля обрабатываемого слова подключен к второмувходу первого элемента И, второмувходу третьего элемента И и второму(инверсному) входу второго элементаИ, третий информационный вход второго узла контроля обрабатываемого слова подключен к третьему входу первого элемента И, третьему входу третьего элемента И и третьему (инверсному)входу второго элемента И, четвертыйинформационный вход второго узла контроля обрабатываемого слова подключенк четвертому входу первого элементаИ, четвертому входу третьего элемента И и четвертому (инверсному) входувторого элемента И, выходы первого,второго и третьего элементов И подключены к входам элементов ИЛИ, выход которого подключен к выходу вто-,рого узла контроля обрабатываемогослова, управляющий вход которогоподключен к пятым входам первого,второго и третьего элементов И,Тираж 410 Подлис митета по изобретениям и о сква, Ж, Раушская наб.,ытням при ГКНТ СС 4/5