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

 

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

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

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

РЕСПУБЛИК (19) (11) А1 (У1)5 О 06 F 15/20

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

К А BTOPGKOMY СВИДЕТЕЛЬСТВУ

С: %

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

AQ ИЗОБРЕТЕНИЯМ И OTHpbITHRM

ПРИ ГКНТ СССР (21) 4684324/24 (22) 03,05,89 (46) 15.03.91. Бюл. У 1О (7 1) Курский политехнический институт (72) В.М.Довгаль, О.Ф.Корольков, В.В.Керекеша, Ф.А,Старков и С.С.Шевелев (53) 68 1.325(088,8) (Se) Авторское свидетельство СССР

11 1455345> кл, С 06 F 15/20, 1986.

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

11> 1533543,. кл. С 06 F 15/20, 26.09,88, (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ ПОДСТАНОВОК СЛОВ (57) Изобретение относится к техническим средствам информатики и вычислительной техники и может быть использовано для обработки данных символьного и числового типов с помощью нормальных алгорифмов> состоящих исключительно из формул подстановок с двухбуквенными левыми и правыми частями, Цель изобретения — увеличение быстродействия при обработке информации по заданной схеме нормального алгорифма, содержащего исключительно формулы подстановки с двухбуквенными левыми и правыми частями. Постав1 ленная цель достигается тем, что устройство содержит блок 1 памяти слов, блок 2 памяти вхождений, блок 3 памяти подстановок, узел 4 сдвига, коммутатор 5, первый узел 6 контроля обрабатываемого слова, узел 7 сравнения, блок 8 органиэации подстановки, элемент И 9, второй узел 1О контроля обрабатываемого слова, элемент ИЛИНЕ 11, счетчик 12 и блок 13 управления, 7 ил.

Узел 7 сравнения включает (фиг,2) элементы 14 хранения букв внутренне- 40 го и входного алфавита, первую 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 контроля обрабатываемого слова содержит (фиг. 65 пер-!

3 16351

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

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

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

Устройство coJl,åðæèò блок 1 памяти слов, блок 2 памяти вхождечий, блок

3 памяти подстановок, узел 4 сдвига, 30 коммутатор 5, первый узел 6 контроля обрабатываемого слова, узел 7 сравнения, блок 8 организации подстановки, элемент И 9, второй узел 10 контроля обрабатываемого слова, элемент

ИЛИ-НЕ 11, счетчик 12 и блок 13 управления.

92

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

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

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

P — слово-подстановка; — признак формулы, 8 E (О, 1) °

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

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

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

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

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

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

ПУСК вЂ” команда запуска устройства, СБРОС вЂ” команда установки исход15 ных состояний;

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

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

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

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

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

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

ПРОШЗ вЂ” вход элемента И (для регистрации ошибок в буквах выходного алфавита при обработке чисел);

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

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

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

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

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

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

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

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

ОШЗ вЂ” признак ошибки при обработке

5 чисел в букве выходного слова;

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

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

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

По команде СБРОС: = 1 все элементы устройства устанавливаются в исходное состояние По команде ПУСК: — 1 устройство начинает работать. По команде ЧТВ: = 1 осуществляется параллельная передача. левых частей формулы подстановок заданного нормального алгорифма иэ блока 2 памяти вхождещ и в узел 7 сравнения. Одновременно по команде ЧТП: = 1 таким же образом ведется загрузка блока 8 правыми частями формулы подстановок заданного нормального алгорифма из блока 3 памяти подстановок, В следующем такте анализируется признак АРИФМ и, если необходима обработка числовой информации, для узлов 6 и 10 и элемента И

9 устанавливаются признаки регистрации ошибок ПРОШ1 = 1, ПРОШ2 = 1, ПРОШЗ = 1, в противном случае, если обрабатывается символьная информация, указанные потенциалы устанавливаются в нулевые значения по командам ПРОШ1:

= О, ПРОШ2: = О, ПРОШЗ: = О. Затем анализируется признак ПОТОК, который идентифицирует режим работы устройства, Если устройство работает s потоковом режиме (информация поступает от других устройств и передается на другие устройства), то ППОТОК: = 1.

Затем анализируется признак начала поступления потоковых данных (от внешних источников) ПНДП и, если

ПНДП = 1, по сигналу ТИ: = 1 данные, пройдя через коммутатор 5 и узел 6, который регистрирует ошибки в буквах входного алфавита в случае обработки числовой информации, сравниваются в узле 7 со словами-вхождениями задан ного нормального алгорифма, В том же такте при обнаружении вхождения в обрабатываемом двухбуквенном слове блок 8 организации подстановки осу-.ществляет подстановку, причем буквы слова-подстановки, стоящие во второй позиции, через узел 10 поступают на вход узла 7 сравнения, а буквы, стоящие в первой позиции слова-подстановки, через элемент И 9 — на выходы устройства. Таким образом, результатом каждого такта работы (после загрузки узла 7 и блока 8 организации подстановки) устройства является

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

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

1).

Таким образом, в автономном режиме работы устройства в одном такте осуществляется групповая компарация слов-вхождений с двухбуквенным обра- 45 батываемым словом, подстановка, регистрация ошибок в случае обработки числовой информации и анализ признака конца слова. В случае обнаружения ошибки (ОШ1 = 1 или ОШ2 = 1, или

ОШЗ = 1) блок 13 управления выдает команду аварийного останова ° Выходные бу .вы накапливаются в узле 4, вытесняя IIQ такту сдвига вправо обрабатываемые однобуквенные слова. Если

ПКС = 1, то по команде ПРС: = 1 про55 исходит передача выходного слова в блок 1 памяти слов, н устройство заканчивает работу.

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

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

1 1 1 0 0 1 1

0 0 0 О 1 0 1

1 1 0 1 1 О 1

1 О 0 0 0 1 0

Остальные 4 бита байта нулевые.

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

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

ПУСК: = 1) узел 7 загружается (из блока 2) левыми частями формул подстановок заданного алгорифма (команда ЧТВ: = 1), т.е, в каждый элемент

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

ИЛИ 23 выдает признак вхождения ПВХ, по которому через злемент 21 задержки осуществляется сброс триггеров

22 в исходное состояние. Из всей совокупности выходов узла 7 только один выход несет еднпн пц, и потенциал, так

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

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

После запуска устройства блок 8 органиэации подстановки загружается из блока 3 памяти правыми частями формул подстановок заданного алгорифма (команда ЧПТ: = 1), т,е. в каж- 10 дый узел 28 поступают команда ЧТП:

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

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

35 нулевые.

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

45 кодовые комбинации:

0 1

1 0 1

0 1

1 0 50

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

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

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

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

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

40 му входу первого элемента И, второму (инверсному) входу первого элемента

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

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

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

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

1635192

1635192

1635192

ПРОШ1

Составитель В. Смирнов

Техред A.Kðàâ÷óê Корректор В.Гирняк

Редактор А.Лежнина

Заказ 757 Тираж 410 Подлисное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101