Устройство для реализации подстановок слов Советский патент 1991 года по МПК G06F15/20 

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

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

На фиг. 1 представлена схема предлагаемого устройства; на фиг. 2 - сх ма узла сравнения; на фиг. 3 - схема элемента хранения букв внутреннего и входного алфавита узла сравне- ния на Фиг« 4 - схема блока организации подстановки, на фиг. 5 - схема узла подстановки блока организации подстановки; на фиг. 6 - схема перво го узла контроля обрабатываемогЬ ело ва на фиг. 7 - схема второго узла контроля обрабатываемого слова.

Устройство содержит блок 1 памяти слов, блок 2 памяти вхождений, блок 3 памяти подстановок, узел 4 сдвига, коммутатор 5, первый узел 6 контроля обрабатываемого слова, узел 7 сравнения, блок 8 организации подстановки, элемент И 9, второй узел 10 контроля обрабатываемого слова, элемент ИЛИ-НЕ 11, счетчик 12 и блок 13 управления .

Узел 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) пёр

0

5

5

5

0 5

0

45

0

вый и второй элементы И 34 и 35 и элемент ИЛИ 36.

Второй узел 10 контроля обрабатываемого слова включает (фиг. 7) первый 37, второй 38 и третий 39 элементы И и элемент ИЛИ 40.

Под формулой подстановки понимается слово вида ъ

V (1) где V - слово-вхождение;

-слово-подстановка;

-признак формулы, 8 е (0,1). Работа формулы подстановок над обрабатываемым словом заключается в обнаружении в нем слова-вхождения

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

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

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

ПУСК - команда запуска устройства

СБРОС - команда установки исходных состояний;

ЧТС - команда чтения обрабатываемого слова из блока памяти слов;

ЧТВ - команда чтения слов-вхождений из блока памяти вхождений в узел сравнения;

ЧТП - команда чтения слов-подстановок из блока памяти подстановок в блок организации подстановки;

АРИФМ - признак арифметической обработки (обработки числовой информации) ;

ПРОШ1 - управляющий вход первого узла контроля обрабатываемого слова для регистрации ошибок в буквах входного алфавита при обработке чисел;

ПРОШ2 - управляющий вход второго узла контроля обрабатываемого слова для регистрации ошибок в буквах внутреннего алфавита при обработке чисел;

ПРОШЗ - вход элемента И (для регистрации ошибок в буквах выходного

алфавита при обработке чисел);

ПОТОК - признак потоковой обработки;

ППОТОК - значение управляющего входа коммутатора;

УСТ1 - команда записи всех единиц в счетчик;

ТИ - сигнал сдвига слова;

ПНПД - признак начала поступления потоковых данных;

ПКПД - признак конца поступления потоковых данных;

ОШ1 - признак ошибки при обработк чисел в букве входного слова;

ОШ2 - признак ошибки при обработк чисел в букве вспомогательного слова

ОШЗ - признак ошибки при обработк чисел в букве выходного слова;

ПКС - признак конца списка одно- буквенных слов;

0

5

0

5

0

5

0

5

0

5

Авар. ост. - признак аварийной остановки устройства;

ПРС - команда приема результирующего слова из узла сдвига в блок памяти слов.

По команде СБРОС: 1 все элементы устройства устанавливаются в исходное состояние По команде ПУСК: 1 устройство начинает работать. По команде ЧТВ: 1 осуществляется параллельная передача левых частей формулы подстановок заданного нормального алгорифма из блока 2 памяти вхождений в узел 7 сравнения. Одновременно по команде ЧТП: 1 таким же образом ведется загрузка блока 8 правыми частями формулы подстановок заданного нормального алгорифма из блока 3 памяти подстановок. В следующем такте анализируется признак АРИФМ и, если необходима обработка числовой информации, для узлов 6 и 10 и элемента И 9 устанавливаются признаки регистрации ошибок ПРОШ1 1, ПРОШ2 1, ПРОШЗ 1, в противном случае, если обрабатывается символьная информация, указанные потенциалы устанавливаются в нулевые значения по командам ПРОШ1: О, ПРОШ2: О, ПРОШЗ: 0. Затем анализируется признак ПОТОК, который идентифицирует режим работы устройства. Если устройство работает в потоковом режиме (информация поступает от других устройств и передается на другие устройства), то ППОТОК: 1. Затем анализируется признак начала поступления потоковых данных (от внешнил источников) ПНДП и, если ПНДП 1, по сигналу ТИ: 1 данные, пройдя через коммутатор 5 и узел 6, который регистрирует ошибки в буквах входного алфавита в случае обработки числовой информации, сравниваются в узле 7 со словами-вхождениями задацг, кого нормального алгорифма. В том же такте при обнаружении вхождения в обрабатываемом двухбуквенном слове блок 8 организации подстановки осу- - ществляет подстановку, причем буквы слова-подстановки, стоящие во второй позиции, через узел 10 поступают на вход узла 7 сравнения, а буквы, стоящие в первой позиции слова-подстановки, через элемент И 9 - на выходы устройства. Таким образом, результатом каждого такта работы (после загрузки узла 7 и блока 8 организации подстановки) устройства является

одна буква в первой позиции и одна буква во второй позиции слова-подстановки, причем первая может сразу поступить на обработку в другое устройство. На каждом такте при обработке чисел также регистрируются три вида ошибок. Если ошибка обнаружена (ОШ1 1 или ОШ2 1, или ОШЗ 1), то устройство выдает команду аварийного останова Авар. ост.. Устройство заканчивает работу, если ПКПД 1

Если устройство работает в автономном режиме (ПОТОК 0), то по команде ЧТС: 1 осуществляется параллельная передача обрабатываемого списка однобуквенных слов из блока 1 памяти слов в узел 4. Одновременно значение управляющего входа коммутатора 5 устанавливается в нулевое зна чение по команде ППОТОК: 0, а счетчик 12 - в единичное состояние по команде УСТ: 1. По сигналу ТИ: 1 в узле 4 Осуществляется сдвиг вправо в результате которого битовый срез, представляющий собой букву-слово, потупает на коммутатор 5, затем через узел 6 - в узел 7 сравнения, где по тому же сигналу ТИ: 1 (с задержкой) происходит параллельное сравнение двухбуквенного обрабатываемого слова с левыми частями формул подстановок заданного нормального алгорифма. В этом же такте состояние счетчика 12 уменьшается на единицу, а также осуществляется подстановка и регистрируются ошибки. При нулевом состоянии счетчика элемент ИЛИ-НЕ 11 выдает признак конца списка обрабатываемых однобуквенных слов (ПКС - О.

Таким образом, в автономном режиме работы устройства в одном такте осуществляется групповая компарация слов-вхождений с двухбуквенным обрабатываемым словом, подстановка, регистрация ошибок в случае обработки числовой информации и анализ признака конца слова. В случае обнаружения ошибки (ОШ1 1 или ОШ2 1, или ОШЗ 1) блок 13 управления выдает команду аварийного останова. Выходные буквы накапливаются в узле 4, вытесняя по такту сдвига вправо обрабатываемые однобуквенные слова. Если ПКС - 1, то по команде ПРС: 1 происходит передача выходного слова в блок 1 памяти слов, и устройство заканчивает работу.

Узел 4 сдвига выполняет параллельный прием .всего списка однобуквенных обрабатываемых слов из блока памяти слов по команде ЧТС: 1, последовательный (по букве) прием выходной последовательности однобуквенных слов по сигналу ТИ: 1, параллельную выдачу в блок 1 памяти слов выходного списка однобуквенных слов и последовательную (по букве) выдачу списка на коммутатор 5.

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

1

О 1 О

1 О

о о

о о

1 о

о

1 1 о

1

о о 1

1 1 1 о

Остальные 4 бита байта нулевые. Узел 7 работает следующим образом.

I

После запуска устройства (команда

ПУСК: 1) узел 7 загружается (из блока 2) левыми частями формул подстановок заданного алгорифма (команда ЧТВ: 1), т.е. в каждый элемент 14 поступают команда ЧТВ: 1 и соответствующий бит вхождения. Далее при поступлении двухбуквенного обрабатываемого слова по сигналу ТИ: 1 через элемент 19 задержки осуществляется параллельное сравнение двух букв обрабатываемого слова со всеми двухбуквенными словами-вхождениями, хранящимися в узле 7. Прямой и инверсный биты обрабатываемого слова через элементы И 15 и 16 подаются на соответствующие элементы 14. Каждый элемент 14 регистрирует совпадение обрабатываемого бита и бита вхождения. Элементы И 17 собирают сигналы совпадения, и, если две буквы обрабатываемого слова совпали с двумя буквами одного из слов-вхождений, соответствующий триггер 22 устанавливается в единицу. Элемент ИЛИ 23 выдает признак вхождения ПВХ, по которому через элемент 21 задержки осуществляется сброс триггеров 22 в исходное состояние. Из всей совокупности выходов учла 7 только один выход несет единичный потенциал, так

как слова-вхождения альтернативны по отношению друг к другу.

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

После запуска устройства блок 8 организации подстановки загружается из блока 3 памяти правыми частями формул подстановок заданного алгорифма (команда ЧПТ: 1), т.е. в каждый узел 28 поступают команда ЧТП: 1 и соответствующий бит слова-подстановки. Далее из узла 7 на второй управляющий вход блока 8 организации подстановки поступает единичный сигнал ПВХ. На каждый узел 28 подстановки поступает сигнал с соответствующего триггера 22, который управляет выдачей бита подстановки. Таким образом, выход узла 28 подстановки является разрешенным информационным битом двухбуквенного слова-подстановки. Выходы ячеек собираются соответствующими элементами ИЛИ 30, где регистр 29 по сигналу ПВХ принимает двухбуквенное слово.

Элемент И 9 используется для ре- гистрации ошибок третьего типа-оши- бок выходного алфавита при обработке числовой информации. При обработке числовой информации используются только два первых (верхних) бита из байта выходной буквы-слова, при этом ошибкой считается кодовая комбинация: 1. Остальные шесть битов Онулевые.

Узел 10 регистрирует ошибки второго типа-ошибки в букве вспомогательного слова при обработке числово информации. При обработке числовой информации используются только четыре первых (верхних) бита из байта буквы (вспомогательного слова), при этом ошибками считаются следующие кодовые комбинации:

01

101 101 101

Остальные (нижние) четыре бита - нулевые.

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

Устройство для реализации подстановок слов, содержащее блок памяти слов, коммутатор, узел сдвига, узел

0

5

0

5

0

5

0

5

0

5

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

5 0 д

5

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

-JWt nr

%

Изобретение относится к техническим средствам информатики и вычислительной техники и может быть использовано для обработки данных символьного И ЧИСЛОВОГО ТИПОВ С ПОМОЩЬЮ нормальных алгорифмов, состоящих исключительно из формул подстановок с двухбуквенными левыми и правыми частями. Цель изобретения - увеличение быстродействия при обработке информации по заданной схеме нормального алгорифма, содержащего исключительно формулы подстановки с двухбуквенными левыми и правыми частями. Поставленная цель достигается тем,что устройство содержит блок 1 памяти слов, блок 2 памяти вхождений, блок 3 памяти подстановок, узел 4 сдвига, коммутатор 5, первый узел 6 контроля обрабатываемого слова, узел 7 сравнения, блок 8 организации подстановки, элемент И 9, второй узел 10 контроля обрабатываемого слова, элемент ИЛИ- НЕ 11, счетчик 12 и блок 13 управления. 7 ил. (Л

r

и

n

U

Т

СЮ )

Фиг.З

гг

И

+щ Tdtdtr

б S tPQ)

гЈ

г

п

3615С91

Г

л

Ј-Л

L

1635192 ПРОШ1

i

v WMW

ЛТҐ

IB

33

40

J