Устройство для вычисления минимального покрытия

Устройство для вычисления минимального покрытия

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК (я)5 С 06 F 7/38, 7/06

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4886466/24 (22) 29.11.90 (46) 15.05.93. Бюл. N. 18 (71) Московский институт инженеров гражданской авиации (72) С.Ж.Кишенский, Н.С.Вдовиченко, Е.Н,Надобных и О.lO.Õðèñòåíêo (56) Авторское свидетельство СССР

N 1068930, кл. G 06 F 7/38, 1982, Авторское свидетельство СССР

¹ 1275427, кл. G 06 F 7/38, l 985. (54) УСТРОЙСТВО ДЛЯ.ВЫЧИСЛЕНИЯ МИНИМАЛЬНОГО ПОКРЫТИЯ (57) Изобретение относится к вычислительной технике. С целью повышения быстродействия и надежности в устройство, Изобретения относится к области вычислительной техники.

Целью изобретения является повышение быстродействия и надежности устройства, На фиг. 1 приведена структурная схема устройства для вычисления минимального покрытия; на фиг.2 — структурная схема блока анализа; на фиг.3 — структурная схема генератора двоичных последовательностей.

Устройство содержит триггер 1, генератор 2 импульсов, генератор 3 двоичных последовательностей, m регистров 4, где m— количество исходных кодов, группы 5 из и элементов И каждая, объединение в k блоков no m групп 5 в каждом, где k — число циклотомических классов равнодоступного кода размерности m, à n — число разрядов каждого исходного кода, k блоков элементов

ИЛИ, k элементов 7 И, блок 8 анализа, шиф„„5U„„1815634 А1 содержащее m регистров, генератор двоичных последовательностей, блок элементов

И, блок элементов ИЛИ, элемент ИЛИ, элемент И, генератор импульсов, триггер, введены (К-1) блоков элементов И, (К-1) блоков элементов ИЛИ, (К х 1) элементов И, мультиплексор, три регистра, три блока сравнения, счетчик, элемент ИЛИ и элемент задержки, а генератор двоичных последовательностей выполнен с (К-1) дополнительными группами выходов. Цель достигается за счет обеспечения последовательности параллельной сортировки входных массивов и фиксирования и индикации цикла работы устройства. 3 ил. ратор 9, регистры 10, 11, блоки 12, 13, 14 а сравнения, счетчик 15, элементы И 16, 17, (ф элемент 18 задержки, элемент ИЛИ 19, ь мультиплексор 20, вход 21 запуска устройст- (Я ва, выход 22. регистр 23, установочный вход 0, 24, генератор 3 имеет k групп 25 выходов, выходы групп 5 соединены с входами групп

6 шинами 26.

Блок 8 анализа имеет входы 27 и содержит k элементов НЕ 28, (k-1) элементов И 29, Ф элемент И-НЕ 30, элементы НЕ 28 имеют выходы 31.

Генератор 3 двоичных последовательностей содержит k блоков 32 памяти, адресные входы которых объединены, а выходы являются группами соответствующих выходов блока 3.

Приведем сначала вербальное описание работы устройства.

1815634

Вычисление минимального покрытия производится параллельным анализом возможности покрытия совокупностями исходных кодов некоторой предметной области по k каналам. Каждый канал оперирует со своими совокупностями исходных кодов (их наборами из записанных в регистрах 4) для анализа покрытия.

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

Под покрытием понимается набор строк некой двоичной матрицы, содержащих в совокупности хотя бы одну единицу в каждом столбце, а под минимальным покрытием— минимальный набор таких строк.

Для определения минимального покрытия необходимо в принципе перебором определить такую совокупность исходных кодов (минимальную по количеству кодов). которая бы полностью покрыла "единицами" некоторое и-разрядное слово. В описываемом устройстве анализ производится параллельно для ряда К совокупностей наборов кодов. При этом применен следующий принцип, основанный на теории кодирования: общая совокупность наборов различных m кодов, проверяемых на получение минимального покрытия при заданном

m составляет 2 — 1 (аналогично количеству кодовых комбинаций равнодоступного mразрядного кода, исключая нулевую комбинацию, естественно, имеются в виду двоичные коды).

Множество кодовых комбинаций равнодоступного кода длиной m разложимо на подмножества, которые называются "циклотомическими классами"; внутри каждого циклотомического класса входящие в него кодовые комбинации представляют собой сдвиг (циклический) некоторого начального элемента (начальной кодовой комбинации), являющейся "представителем циклотомического класса", Для любого m, любой циклотомический класс содержит не более m кодовых комбинаций, причем, как указано выше. все они имеют (внутри данного класса) одинаковое число "единиц", То есть, одну и ту же степень покрытия. Таким образом, параллельно анализируя не реализацию полного покрытия все циклотомические классы, расположив их так, что при обнаружении полного покрытия в некотором классе. классы с большим числом единиц

10 нии(цепи начальной установки не показаны

15 на чертеже), В регистр 23 записано число

"m" в двоичном коде. В регистры 4 записаны исходные коды, используемые для покрытия. (Цепи записи также не показаны; за-. пись в регистры 4 и 23 может, например, 20 осуществляться путем подачи на информационные входы регистров требуемых кодов, и импульса на синхровходы, которые не показаны на чертеже). В блоки памяти генератора 3 занесены двоичные

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

30 записываются члены циклотомического класса, представителем которого является кодовое слово, состоящее из одной, младшей единицы и остальных m-1 нулей (класс с одной единицей — единственный для любого равнодоступного кода); во второй блок памяти — класс, строющийся на основе представителя с двумя единицами, в третий

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

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

В исходном состоянии триггер 1, регистры 10 и 11, счетчик 15 — в нулевом состояблок — также класс на основе представителя с двумя единицами, не входящего в число кодовых слов, записанных в предыдущем блоке, а если такового нет — класс на основе представит ля с трем единицами, и т,д. Таким образом, по мере увеличения индексов блоков памяти генератора 3, в низ записываются члены соответствующих циклотомических классов с неубывающим числом единиц в равнодоступном коде длиной m, причем необходимо для вычисления циклотомических классов умножением предыдущего члена на "2" с последующей операцией по модулю 2m-1; это условие не распространяется лишь на класс единственным членом, равным "2 -1", который заменяет нулевой член.

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

1815634 класса, а затем тактовыми импульсами от генератора 2 сдвигается по циклу (регистры замкнуты в циклические петли).

Запуск устройства производится подачей короткого положительного импульса на 5 вход 21. Триггер 1 устанавливается в единичное состояние, регистры 10 и 11 сбрасываются (если в них были зафиксированы результаты предыдущего вычисления).

Триггер 12 открывает генератор 2, который начинает формировать тактовые импульсы.

Первым тактовым импульсом счетчик 15 устанавливает содержимое "1", которое поступает на адресные входы генератора 3—

его блоков памяти, на выходах которых (их первых ячеек) формируются первые члены (фактически — и редста вител и соответствующих циклотомических классов) наборов.

Рассмотрим в качестве примера функ- 20 ционирование совокупности групп 5ц, 521 5 1, 61. 71, регистров 4 и сигналов на группах выходов генератора 3.

Первая группа сигналов генератора 3, поступая на соответствующие группы 5 зле- 25 ментов И, открывает элементь И этих групп (их входы объединены для каждой группы 5).

На вторые входы элементов И групп 5 поступают исходные коды. Если в данном наборе входов для данной группы 5 — единица, то 30 соответствующий код (исходный) из регистра 4 проходит на выход элемента И; если на соответствующем выходе группы 25 генератора 3 — "нуль", на выходе соответствующего блока элементов И совокупность и нулей. 35

Коды по этим выходам поступают в блок 61 элементов ИЛИ. причем соединение осуществлено таким образом, что одноименные разряды выходов групп 5 подключаются к одному элементу ИЛИ блока 6, таким обра- 40 зом, если хотя бы на одном из i-ых выходов регистров 4, выбранных с помощью первой группы 25> выходов генератора 3, на данном такте присутствует единичный сигнал, на выходе i-го элемента блока 6 элементов

ИЛИ также формируется единичный сигнал.

Если данный выходной код на первой группе 25> выходов генератора 3 реализует полное покрытие, на выходах всех элементов блока 61элементов ИЛИ первым появляется единичный сигнал, и единичный сигнал формируется на выходе первого элемента И 71.

Аналогично функционируют остальные блоки в своих циклотомических классах. 55

Сигналы с выходов элементов И 7 поступают в блок 8 анализа. Единичные значения соответствующих сигналов с выходов элементов И 7 сигнализируют об обнаружении полного покрытия в соответствующем канале. В блоке 8 среди них выбирается сигнал, соответствующий меньшему среди всех индексу канала (как показано выше, этот сигнал соответствует покрытию минимальному среди всех обнаруженных полных покрытий на данном такте). Это реализовано следующим образом. Единичные значения сигналов, сигнализирующие об обнаружении полных покрытий на соответствующих каналах, поступают на входы элементов НЕ 28 и

И 29. В том случае, если какой-либо сигнал некоторого канала имеет единичное значение, его инверсия с выхода соответствующего элемента Н Е 28 закрывает элементы И

29 с большими номерами и, таким образом, на совокупности выходов элементов И 7 и элементов НЕ 282 — 28к получается позиционный единичный код разрядности "K", и ричем место "единицы" (единственной) соответствует номеру канала с минимальным индексом, в котором на данном такте обнаружено покрытие. Шифратор 9 преобразует единичный позиционный код в двоичный код. B том случае, когда ни в одном из каналов не обнаружено полного покрытия, на выходах всех элементов НЕ 28— единичные сигналы, и на выходе элемента

И вЂ” НЕ 30 — нулевой сигнал (в этот же момент на выходах шифратора 9 — нулевой код).

Если же хотя бы в одном канале обнаружено полное покрытие, на выходе элемента И вЂ” НЕ

30 — единичный сигнал.

Двоичный код канала с минимальным индексом (номером), в котором обнаружено на данном такте полное покрытие (минимальное полное покрытие для данного конкретного такта) поступает на входы адреса мультиплексора 20. задавая номер группы

25 выходов генератора 3, на которых в данном такте установлен код минимального покрытия для данного такта, которые коммутируются мультиплексором 20 на его выходы. Этот же код подается на входы блоков сравнения 12 и 13, Блок 13 на выходе (типа "меньше") выдает положительный сигнал в том случае, когда код с шифратора 9 меньше кода, записанного в регистре 10), в котором хранится текущий — по всем предыдущим тактам — код номера канала, в котором было обнаружено минимальное покрытие). Блок 12 сравнения на выходе (типа "равно") выдает единичный сигнал при равенстве кода с выходов шифратора 9

"единице" (что сигнализирует о выявлении покрытия в RepBoM канале), с единственной единицей в составе сигналов соответствующей группы генератора 3; "единица" выдается постоянно на входе 24 устройства.

1815634

Итак, в первом такте работы, при отсутствии обнаружения полного покрытия в каком-либо канале, на выходах шифратора 9. нулевой код, а на его дополнительном выходе — нулевой сигнал. Блок 13 сравнения срабатывает (в исходном состоянии в регистр

10 записывается код, заведомо больший максимально возможного кода с выходов шифратора 9, и этот же код записывается в регистр 10 при окончании очередного процесса вычисления минимального покрытия — в момент поступления импульса запуска с входа 21 устройства), однако, в данном случае не срабатывает (закрытый нулевым сигналом с выхода блока 8) элемент И 17. Блок

16 закрыт нулевым сигналом с блока 12, Поступление задержанного тактового импульса с выхода элемента 18 задержки опрашивает блоки 16 и 17. Так как, по нашему условию, они не открыты, то ничего не происходит, устройство ожидает следующего тактового импульса.

Если же на первом (очередном тактовом импульсе обнаружено полное покрытие по какому-либо каналу (кроме первого), то срабатывают блоки 13» 0, и задержанный тактовый импульс формирует импульс записи на выходе элемента И 17, по которому в регистр 10 записывается код канала, в которой обнаружено минимальное (на данный такт) покрытие, а в регистр 11 — код минимального покрытия с соответствующей группы 25 выходов генератора 3.

Время задержки элемента 18 выбирается таким, чтобы тактовый импульс поступал на блоки 16 и 17 после формирования кода на выходе блока 20.

Очередной (после первого, записывающего покрытие) тактовый импульс сравнивает код текущего (если он есть) канала, в котором обнаружено покрытие. с кодом. записанным в регистре 10. если код канала в текущем такте больше кода, записанного о регистре 11, то ничего не происходит. так как текущее покрытие заведомо не является минимальным; если же код с выходов шифратора 9 меньше, то происходит его перезапись в регистр 10 и соответствующего ему кода минимального(на текущий такт) покрытия в регистр 11.

Если же на любом такте обнаружено полное покрытие в первом канале. то срабатывает элемент И 16 (по задержанному тактовому импульсу), и через элемент ИЛИ 19 устанавливает триггер 1 и счетчик 15 в нулевое состояние, подготавливая устройство к следующему процессу вычисления. В этом случае элемент 17 также срабатывает и за5

55 писывает код минимального (в данном случае покрытие является абсолютно минимальным. так как в него входит лишь один из исходных кодов) покрытия в регистр 11, и "единицу" в регистр 10. Срабатывание регистров 10 и 11 происходит надежно, так как они срабатывают по фронту сигнала с выхода элемента И 17. а блоки 1 и 15 сбрасываются потенциалу сигнала с элемента И 16 (при необходимости на выходе элемента И

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

В том случае, если на m тактов (достаточных для опроса всех наборов кодов исходных) не выявлено ни одного покрытия, то очередным тактовым импульсом счетчик

15 переводится в состояние "m+1", по выходу "больше" срабатывает блок сравнения 14 (в регистре 23 записан код "m") и аналогично через элемент ИЛИ 19 производится установка блоков 1 и 15 в исходное состояние.

При этом ситуация, при которой отсутствует покрытие, распознается пользователем по нулевому содержимому регистра 11 (сброшенного в начале процесса вычисления), Она же может быть распознана снятием сигнала с выхода блока сравнения 14 (не показан отдельным выходом).

Таким образом, описываемое устройство позвал яет on редел ить. минимальное покрытие максимум на m тактов (если такое покрытие вообще существует для данной совокупности исходных кодов). При обнаружении покрытия в первом канале работа устройства заканчивается после m тактов.

Аналогично, если минимальное покрытие обнаружено за время вычисления не в первом канале. устройство также работает в течение m тактов и сбрасывается по сигналу с выхода блока 14, причем в этом случае в регистре 11 записан код минимального покрытия (выбранного не из первого канала).

Остановимся на реализации регистра

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

8. Это можно реализовать. например, таким 815634

10 образом. Регистр 10 выполняется на Д-триггерах типа К 155 ТМ 2. Д4 и С-входы триггеров соответствуют по активным уровням сигналов сигналам. указанным в устройстве. Каждый триггер К 155 TM 2 имеет установочный (единичный) и нулевой входы. активными уровнями сигналов для которых являются нулевые. Для этих конкретных триггеров на входах единичных и нулевых следует ввести элементы НЕ (для триггеров, у которых единичный и нулевой входы требуют единичных активных уровнеи сигналов в элементах НЕ на этих входах нет необходимости). И вход 21 устройства подключается к единичным и нулевым входам тех триггеров, которые, устанавливаясь в соответствующие состояния, формируют на прямых выходах код, заведомо больший, чем любой код, снимаемый с шифратора 9. Так, если, например, m = 6, регистр 10 содержит

3 триггера, и к входу 21 устройства через элементы НЕ подключаются единичные входы всех триггеров, обеспечивается запись в такой регистр при начальной установке двоичного числа "111", то есть десятичного числа "7".

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

Пусть, например, m = 6(имеется 6исходных кодов). Число различных наборов данных кодов, которые необходимо исследовать на наличие покрытия и набора минимального покрытия, равно 63 (искл>очая нулевую комбинацию, которая фактически соответствует невозможной ситуации, при которой покрытие обеспечивается вообще без кодов). Для общего случая m кодов, общее количество наборов, исследуемых на минимальное покрытие, составляет 2 -1. Процесс получения циклотомических классов состоит в следующем: записываем все наборы в удобной форме (например. в десятичной системе счисления): выбираем первый набор (он всегда—

"1", для любого "m"); этот набор является представителем первого циклотомического класса;остальные члены первого циклотомического класса получаем последовательным умножением представителя. а далее— каждого полученного очередного члена — на

"2", по модулю 2 -1; если после очередного умножения получаем снова один из членов данного класса (обычно это его представитель), то класс полностью определен; вычер1. 1,2,4,8, 16.32

2. 3, 6, 12. 24, 48. 33

000001, 1.

000011. 2 . киваем все члены данно о класса из общего набора кодов; среди оставшихся наборов выбираем минимальный и проделываем с ним изложенные пункты 3)-5) для нового циклотомического класса; если больше не осталось наборов. все циклотомические классы определены: записываем в каждый блок памяти генератора 3 последовательно в ячейки его памяти члены соответствующего циклотомического класса. При этом запись для любого класса его членов в блок памяти генератора 3 может производиться» в произвольном порядке. Однако, перед записью необходимо упорядочить циклотомические классы таким образом, чтобы удовлетворялось правило: представитель циклотомического класса с большим номером должен содержать не меньше единиц, чем представитель циклотомического класса с меньшим номером.

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

1) наборы для m = 6 (в десятичной форме) будут числами от "1" до "63". (Соответственно. например, набор "1" соответствует покрытию "000001", а набор "23" — покрытию

"010111");

30 2) первый набор — "1";

3) последовательно умножая его на "2", получаем {умножение — по модулю 63) числа;

1, 2, 4, 8, 16, 32, 1 (64), 2 (128), 4,.... Таким образом, члены первого циклотомического

35 класса — 1, 2, 4, 8, 16 и 32. (заметим, и это характерно для членов любого циклотомического класса, что при двоичном представлении все члены данного циклотомического класса получаются один из другого циклическим сдвигом одного из них);

Пункты 4(и 5) изложены в пункте 3);

6) среди оставшихся наборов минимальным является набор"3". Проделываем с ним те же операции и определяем класс, представителем которого он является. Члены этого класса: 3, 6, 12. 24, 48, 33.

Аналогично, определяя следующие классы по представленному алгоритму (учитывая, как сказано в описании данного устройства на стр.G) неприменения операции взятия числа по модулю 63, если оно само равно "63", получаем следующую совокупность циклотомических классов и их членов

55 (после перечисления членов каждого класса приведен в двоичной форме его представитель), и далее — число единиц в нем:

1815634

5

3. 5, 10, 20, 40, 17, 34 000101 . 2 .

4. 7, 14. 28, 56. 49, 35 000111 . 3 .

5. 9, 18,36 001001.2.

6. 11, 22, 44, 25, 50, 37 001011. 3.

7. 13, 26. 52, 41, 19, 38 001101 . 3 .

8. 15, 30, 60, 57, 51, 39 001111 . 4 .

9, 21, 42 010101 . 3 .

10. 23, 46, 29, 58, 53, 43 010111 . 4 .

11. 27, 54, 45 011011, 4.

12, 31. 62, 61, 59, 55, 47 011111, 5, 13, 63 11111. 6 .

Заметим, что в данном случае по числу единиц в представителях классы еще не упорядочены. Для упорядочения следует поменять местами соответственно классы М 4 и М 5, а также пару классов — М 8 и М 9, Окончательно — для данного случая необходимо 13 блоков памяти в генераторе двоичных последовательностей, в которые по номерам последовательно — в блоки 32l32ig записываются в каждый члены своего класса, а по номерам классов — соответственно последовательно классы:

1, 2, 3, 4, 5. 4, 6, 7, 8, 10, 11, 12 и 13.

Заметим также, что не все классы имеют размерность "m", некоторые — меньше по размерности (числу членов). Однако, это не влияет на работу устройства, так как многократное пробегание членов какого-либо класса за m тактов работы устройства не изменяет результатов его работы.

Таким образом, как следует из описания работы устройства, оно позволяет вычислить минимальное покрытие в любом случае не более, чем за m тактов, причем при фактическом наличии минимального покрытия в первом циклотомическом классе быстродействие описываемого устройства совпадает с быстродействием прототипа, а при любой другой ситуации (наличии минимального покрытия в любом классе, кроме первого), описываемое устройство функционирует быстрее, так как требует лишь m тактов для полного проведения вычисления, в то время, как прототип в зависимости от фактического наличия и места (и вида) минимального покрытия требует от m до 2m-1 тактов работы.

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

В то же время прототип при отсутствии возможности вычисления покрытия (если такто20

У

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

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

Устройство для вычисления минимального покрытия, содержащее генератор импульсов, mрегистров,,где m — количество исходных кодов, первый блок элементов И из m групп по и элементов И s каждой. где

n — число разрядов каждого исходного кода, первый блок элементов ИЛИ из и элементов

ИЛИ, генератор двоичных последовательностей, первый элемент И и триггер, выход которого подключен к входу запуска генератора импульсов, выходы каждого i-ro регистра соединены с одними входами соответствующих элементов И 1-й группы первого блока элементов И, другие входы которых объединены и соединены с i-м выходом первой группы выходов генератора двоичных последовательностей, выходы i-x элементов И каждой группы первого блока элементов И соединены с соответствующим группе входом 1-ro элемента ИЛИ первого блока элементов ИЛИ, выходы элементов ИЛИ первого блока элементов

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

И в каждой, где к — число циклотомических классов равнодоступного кода размерности

m, (к-1) блоков элементов ИЛИ иэ и элементов ИЛИ в каждом, (к+1) элементов И, блок анализа, шифратор, три регистра, элемент

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

14

1815634

13 другие входы элементов И i-ой группы J-го блока элементов И объединены и соединены с 1-м выходом J-й группы выходов генератора двоичных последовательностей, где ) =

1...к, выходы J-й группы выходов генератора двоичных последовательностей соединены с О+1)-й группой информационных входов мультиплексора, первая группа информационных входов которого подключена к общей шине. выходы i-x элементов И всех групп

J-ro блока элементов И, начиная с J = 2, соединены с входами i-го элемента ИЛИ J-ro блока элементов ИЛИ. выходы элементов

ИЛИ j-ro, начиная с J = 2, блока элементов

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

5 элемента И подключен к выходу блока анализа, выход (к+1)-го элемента И соединен с одним входом элемента ИЛИ, выход которого соединен с входом установки в "О" триггера и счетчика, выходы которого

"0 соединены с входами генератора двоичных последовательностей и одной группой входов третьего блока сравнения, выход кото- рого соединен с другим входом элемента

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

1815634

Составитель С.Кишенский

Техред М.Моргентал Корректор Т.Вашкович

Редактор

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

Заказ 1636 Тираж Подписное

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

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