Результаты работы --> Статьи --> Мажорирующие булевые функции

О применении систем мажорирующих булевых функций

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

Если имеется M датчиков и N входных полюсов приемника, где М > N и >= M, то в качестве "однотактного" кодирующего устройства можно использовать комбинационную схему с M входными и N выходными полюсами. В простейшем случае, если предположить, что в один момент времени может быть получена информация только с одного датчика, то схема должна реализовать простой двоичный шифратор. Если же допустить одновременное срабатывание двух и более датчиков, то в этом случае кодирующее устройство должно пре-образовать состояний датчиков в возможных входных состояний приемника. Очевид-но, что без потери информации такое преобразование осуществить невозможно. Цель данной статьи заключается в том, чтобы рассмотреть один из вариантов минимизации потери ин-формации при реализации данного преобразования.

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

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

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

{(0000), (0001)} -> (00);

{(0010), (0011)} -> (01);

{(0100), (0101), (0110), (0111)} -> (10);

{(1000), (1001), (1010), (1011), (1100), (1101), (1110), (1111)} -> (11);

Заметим, что функции и переменные в приведенном выше отображении нумеруются справа налево. Для реализации данного отображения может быть использован комбинацион-ный автомат размерности 4 x 2, задаваемый двумя функциями четырех переменных:

_

F1= X4 V X2 X3, F2= X4 V X3,

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

{(00000), (00001)} -> (000);

{(00010), (00011)} -> (001);

{(00100), (00101), (00110), (00111)} -> (010);

{(01001), (01001), (01010), (01011), (01100), (01101), (01110), (01111)} -> (011);

{(10000), (10001), (10010), (10011), (10100), (10101), (10110), (10111), (11000), (11001), (11010), (10011), (11100), (11101), (11110), (11111)} -> (100).

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

_ _ _ F1= X5(X4 V X2 X3), F2= X5(X4 V X3), F3 = X5

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