Двоичные логические операции с цифровыми сигналами (битовые операции).

09.11.2013 19:03

Логические операции (булева функция) своё теоретическое обоснование получили в алгебре логики.

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

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


Отрицание, НЕ


Инвертор, НЕ
A − A
0 1
1 0

Мнемоническое правило для отрицания звучит так: На выходе будет:

  • "1" тогда и только тогда, когда на входе «0»,
  • "0" тогда и только тогда, когда на входе «1»


Повторение, ДА


Повторитель (буфер) ДА
A A
0 0
1 1

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

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


Конъюнкция (логическое умножение). Операция 2И. Функция min(A,B)


2И
A B A٨B
0 0 0
1 0 0
0 1 0
1 1 1

Логический элемент, реализующий функцию конъюнкции, называется схемой совпадения. Мнемоническое правило для конъюнкции с любым количеством входов звучит так: На выходе будет:

  • "1" тогда и только тогда, когда на всех входах действуют «1»,
  • "0" тогда и только тогда, когда хотя бы на одном входе действует «0»


Дизъюнкция (логическое сложение). Операция 2ИЛИ. Функция max(A,B)


2ИЛИ
A B BvA
0 0 0
1 0 1
0 1 1
1 1 1

Мнемоническое правило для дизъюнкции с любым количеством входов звучит так: На выходе будет:

  • "1" тогда и только тогда, когда хотя бы на одном входе действует «1»,
  • "0" тогда и только тогда, когда на всех входах действуют «0»


Инверсия функции конъюнкции. Операция 2И-НЕ(Штрих Шеффера)


2И-НЕ
A B A / B
0 0 1
0 1 1
1 0 1
1 1 0

Мнемоническое правило для И-НЕ с любым количеством входов звучит так: На выходе будет:

  • "1" тогда и только тогда, когда хотя бы на одном входе действует «0»,
  • "0" тогда и только тогда, когда на всех входах действуют «1»


Инверсия функции дизъюнкции. Операция 2ИЛИ_НЕ(Стрелка Пирса)


2ИЛИ-НЕ
A B A↓B
0 0 1
0 1 0
1 0 0
1 1 0

Мнемоническое правило для ИЛИ-НЕ с любым количеством входов звучит так: На выходе будет:

  • "1" тогда и только тогда, когда на всех входах действуют «0»,
  • "0" тогда и только тогда, когда хотя бы на одном входе действует «1»


Эквивалентность (равнозначность), 2ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ


2ИСКЛ-ИЛИ-НЕ
A B A↔B
0 0 1
0 1 0
1 0 0
1 1 1

Мнемоническое правило эквивалентности с любым количеством входов звучит так: На выходе будет:

  • "1" тогда и только тогда, когда на входе действует четное количество,
  • "0" тогда и только тогда, когда на входе действует нечетное количество


Сложение по модулю 2 (2ИСКЛЮЧАЮЩЕЕ ИЛИ, неравнозначность). Инверсия равнозначности.

 

 

A B f(AB)
0 0 0
0 1 1
1 0 1
1 1 0

Мнемоническое правило для суммы по модулю 2 с любым количеством входов звучит так: На выходе будет:

  • "1" тогда и только тогда, когда на входа действует нечётное количество ,
  • "0" тогда и только тогда, когда на входа действует чётное количество


Импликация от A к B (инверсия декремента)

A B A→B
0 0 1
0 1 1
1 0 0
1 1 1

Мнемоническое правило для инверсии декремента звучит так: На выходе будет:

  • "0" тогда и только тогда, когда на "B" меньше "А",
  • "1" тогда и только тогда, когда на "B" больше либо равно "А"


Импликация от B к A (инверсия инкремента)

A B B→A
0 0 1
0 1 0
1 0 1
1 1 1

Мнемоническое правило для инверсии инкремента звучит так: На выходе будет:

  • "0" тогда и только тогда, когда на "B" больше "А",
  • "1" тогда и только тогда, когда на "B" меньше либо равно "А"


Декремент. Запрет импликации по B. Инверсия импликации от A к B

A B f(AB)
0 0 0
0 1 0
1 0 1
1 1 0

Мнемоническое правило для инверсии импликации от A к B звучит так: На выходе будет:

  • "1" тогда и только тогда, когда на "A" больше "B",
  • "0" тогда и только тогда, когда на "A" меньше либо равно "B"


Инкремент. Запрет импликации по A. Инверсия импликации от B к A

A B f(AB)
0 0 0
0 1 1
1 0 0
1 1 0

Мнемоническое правило для инверсии импликации от B к A звучит так: На выходе будет:

  • "1" тогда и только тогда, когда на "B" больше "A",
  • "0" тогда и только тогда, когда на "B" меньше либо равно "A"

Примечание 1. Элементы импликаций не имеют промышленных аналогов для функций с количеством входов, не равным 2.
Примечание 2. Элементы импликаций не имеют промышленных аналогов.

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

  • И, НЕ (2 элемента)
  • ИЛИ, НЕ (2 элемента)
  • И-НЕ (1 элемент)
  • ИЛИ-НЕ (1 элемент).

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

Назад