Размещено на http: //www. allbest. ru/

Пермский государственный национальный исследовательский университет Россия, 614990, Пермь, ул. Букирева, 15

Информатика

Отрицание мультиплексора

С.Ф. Тюрин, И.C. Понуровский

tyurinsergfeo@yandex.ru; 8-952-32-02-510;

iponurovskiy@gmail.com; 8-902-80-54-736

Аннотация

инверсия ортогональный преобразователь мультиплексор

Устанавливаются правила отрицания (инверсии) ортогональных конъюнкций дизъюнктивных нормальных форм (ДНФ), используемые в алгоритмах синтеза логических преобразователей автоматов в функционально полном толерантном (ФПТ) базисе. Показывается, что отрицание бинарной переключательной функции мультиплексора - генератора функций n переменных получается путем отрицания переменных данных. Применение правил отрицания иллюстрируется на примерах самосинхронных схем, имеющих двойственный канал комбинационного автомата.

Ключевые слова: бинарная переключательная функция(ПФ); отрицание (инверсия); ортогональные конъюнкции; дизъюнктивная нормальная форма (ДНФ); функционально полный толерантный (ФПТ) базис; логический преобразователь; автомат; мультиплексор-генератор функции; самосинхронная схема.

Abstract

tyurinsergfeo@yandex.ru; 8-952-32-02-510

iponurovskiy@gmail.com; 8-902-80-54-736

The rules of negation (inversion) of orthogonal conjunction of disjunctive normal forms (DNF) used in synthesis algorithms of logical converting automatons in functionally complete and tolerant (FCT) basis are formulated. It is shown, that negation of binary switching function of multiplexer (i.e. generator of function of n variables) results from negation of data variables. Negation rules usage is illustrated by the example of self-synchronous systems having duplex channel of combinational automaton.

Key words: binary switching function; negation (inversion); orthogonal conjunctions; disjunctive normal forms (DNS); functionally complete tolerant (FCT) basis; logic converter; automaton; multiplexer-function generator.

Введение

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

Особенность представления бинарных переключательных функций в избыточных (функционально полных толерантных) базисах):

(1)

(2)

заключается в двойственности базиса и необходимости представления произвольной функции в виде

(4)

Поэтому при синтезе схем автоматов в избыточных функционально полных толерантных (ФПТ) базисах возникает необходимость отрицания (инверсирования) ортогональных по некоторым переменным конъюнкций дизъюнктивной нормальной формы - ДНФ и конъюнкций в конъюнктивной нормальной форме - КНФ.

1. Правило отрицания ортогональных конъюнкций ДНФ бинарных переключательных функций

Пусть задана бинарная переключательная функция:

(5)

Получим ее отрицание (инверсию), используя закон Де-Моргана:

(6)

Исключая первую конъюнкцию по закону обобщенного склеивания, а последнюю по закону противоречия, получим:

(7)

Представим это правило в матричной форме:

(8)

Здесь отрицается (инверсируется) диагональ "a-в". Это правило инверсии ДНФ с так называемой развязывающей (ортогональной) переменной x.

2. Инверсирование двух сложных ортогональных конъюнкций

Рассмотрим пример инверсии 2 ортогональных конъюнкций из трех переменных каждая:

(9)

Таким образом, инверсия матрицы:

(10)

приводит к матрице:

(11)

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

3. Отрицание ортогональной дизъюнкции КНФ

Покажем, что

(12)

Используем дистрибутивный закон:

(13)

Поэтому, учитывая закон Порецкого

(14)

Далее, применив закон обобщенного склеивания, получим:

(15)

4. Отрицание ортогональных ДНФ

Усложним конъюнкции перед x, т.е. введем ортогональные ДНФ:

(16)

Применяя вышеприведенное правило, получим:

(17)

Иначе:

(18)

В табличной форме:

Исходная таблица 1

Инверсная таблице 1 таблица 2

5. Использования правила отрициния в самосинхронных автоматах

Самосинхронный автомат строится путём введения двойственного (бифазного) канала и индицирования входных и выходных сигналов [4, 5] (рис. 1):

Рис. 1 Самосинхронный комбинационный автомат с индикацией только выходных сигналов

Так, предлагается ФПТСС элемент - функционально полный толерантный элемент (элемент с избыточным базисом) самосинхронный (рис. 2):

Рис. 2 Базовый ФПТСС элемент

Один канал реализован на избыточном базисе:

(2ИЛИ-2И-НЕ),

двойственный канал реализован на избыточном базисе (2И-2ИЛИ-НЕ):

Парафазные переменные подаются через дополнительное устройство - формирователь спейсера[4, 5], не указанные на рис.2.

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

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

(19)

Используя базис

(20)

можно получить

(21)

соответственно, двойственная функция будет

(22)

Таким образом, в выражениях (21), (22) используется также правило инверсии. Самосинхронная реализация [4-5] представлена на рис. 3.

На рис. 3 АВ - бифазное А (не А), ВВ - бифазное В (не В), Y - выходной сигнал, YB - бифазный выход (не Y), I - выход индикатора окончания переходного процесса. Основной канал реализует функцию

(21)

двойственный -

(22)

То есть двойственность реализуется за счёт только входных сигналов в отличие от схем рис. 1, 2.

Рис. 3 Самасинхронная реализация функции исключающего ИЛИ (суммы по модулю 2)

6. Инверсия выражений с ортогональностью по нескольким переменным. Отрицание мультиплексора

Пусть задана функция мультиплексирования с четырех направлений 4-1:

(23)

Преобразуем ее:

(24)

Очевидно, что отрицанием этой функции будет выражение, в котором согласно правилу (3) отрицаются ДНФ в скобках, а они, соответственно, также отрицаются:

(25)

Получаем выражение:

(26)

То есть "отрицание мультиплексора" - это мультиплексор, у которого отрицаются входы данных a,b,c,d.

Поэтому в схеме самосинхронного мультиплексора 2-1AiBi, i=1…8 [5] (рис.4):

Рис. 4 Самосинхронная реализация мультиплексора 2-1

Оба канала AiBi-NAiNBi (N - бифазные сигналы) реализованы на однотипных элементах АОАI1. То есть первый канал реализует функцию:

(27)

Двойственный канал реализует отрицание мультиплексора:

(28)

7. Самосинхронный логический элемент конфигурируемого логического блока (КЛБ) программируемой логической интегральной схемы

Современные программируемые логические схемы (ПЛИС) типа FPGA ( field-programmable gate array) содержат конфигурируемые логические блоки (КЛБ) [6], состоящие из логических элементов ЛЭ, программируемых локальных и глобальных матриц соединений-ЛМС, ГМС (рис. 5)

Рис. 5 Конфигурируемый логический блок (КЛБ) ПЛИС FPGA

Причем каждый логический элемент ЛЭ строится как постоянное запоминающее устройство ПЗУ (LUT - Look Up Table), представляющее собой мультиплексор 16-1, входы данных которого настраиваются так называемыми конфигурируемыми ячейками памяти [6] (рис. 6):

Рис. 6 Логический элемент ПЛИС FPGA

На рис. 6 входные сигналы -S0,S1,S2,S3, элемент настроен на реализацию суммы по модулю два S0S1S2S3. Элементарные мультиплексоры 2-1 реализуются так же, как в коммутаторе (это тоже мультиплексор) [6] (рис. 7).

Рис. 7 Коммутатор сигналов с локальных межсоединений на вход КЛБ

Таким образом, для получения второго канала СС схемы - дерева мультиплексоров необходимо проинвертировать данные конфигурируемой памяти (рис. 8):

Рис. 8 Двойственный канал самосинхронного логического элемента ПЛИС FPGA

Таким образом, на базе существующих конфигурируемых логических блоков - КЛБ (рис. 5), содержащих 8 ЛЭ, можно путем доработки (введения индикаторный элементов и блока спейсера) построить 4 самосинхронных элемента.

Заключение

Таким образом, правила отрицания (инверсии) ортогональных конъюнкций ДНФ (дизъюнкций КНФ) позволяют упростить алгоритмы представления произвольных логических функций в избыточных (ФПТ) базисах. Отрицание логической функции мультиплексора - генератора функций n переменных получается путем отрицания переменных данных.

Это позволяет строить самосинхронные логические элементы ПЛИС FPGA путем введения двойственного канала с отрицанием разрядов конфигурационной памяти. Подобное дублирование может быть также использовано для контроля правильности функционирования КЛБ в отказоустойчивых системах.

Список литературы

1. Тюрин С.Ф. Функционально-полные толерантные булевы функции // Наука и технология в России. 1998. № 4. С.7-10.

2. Тюрин С.Ф. Проблема сохранения функциональной полноты булевых функций при "отказах" аргументов //Автоматика и телемеханика. 1999. № 9. С.176-186.

3. Tyurin S., Kharchenko V. Redundant Basises for Critical Systems and Infrastructures: General Approach and Variants of ImplementationProceedings of the 1st Intrenational Workshop on Critical Infrastructures Safety and Security. Kirovograd, 2011. Vol.2. P.300-307.

4. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах / под ред. В.И.Варшавского. М.: Наука, 1986. 400 с.

5. Степченков Ю.А., Дьяченко Ю.Г., Гринфельд Ф.И. и др. Библиотека самосинхронных элементов для технологии БМК // Проблемы разработки перспективных микроэлектронных систем. 2006: сб. науч. тр. / под общ. ред. А.Л.Стемпковского. М.: ИППМ РАН, 2006. С. 259-264.

6. Цыбин С. Программируемая коммутация ПЛИС: взгляд изнутри [Электронный ресурс]. URL: http://www.kite.ru-/articles/plis/ 2010_11_56.php (дата обращения: 03.10.12)

Размещено на Allbest.ru