Основы теории проектирования устройств цифровой обработки информации

Белорусский государственный университет информатики и радиоэлектроники

Кафедра РЭС

Реферат

На тему:

«Основы теории проектирования устройств цифровой обработки информации»

Минск, 2009

Алгебра логики (булева алгебра) в отличие от обычной алгебры оперирует переменными, которые могут принимать только два значения типа да-нет, включено-выключено и т. п. Обычно их обозначают латинскими буквами X, Y, Z, … При этом для удобства математического описания значения этих переменных принято обозначать 1 и 0.

В алгебре логики определены отношение эквивалентности (=) и три операции: дизьюнкция (операция ИЛИ), обозначаемая знаком (или «+»), коньюнкция (операция И), обозначаемая знаком (или &) или точкой, которую можно опускать (например ), и отрицание (инверсия, операция НЕ), обозначаемое чертой над переменными или над элементами 0 и 1 (например, ).

Отношение эквивалентности удовлетворяет следующим свойствам:

· - рефлексивность;

· если , то - симметричность;

· если и , то - транзитивность.

Из отношения эквивалентности следует принцип подстановки:

· если , то в любой формуле, содержащей X, вместо X можно подставить Y, и в результате будет получена эквивалентная формула.

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

Переключательной (булевой, двоичной) функцией называют функцию вида:

,

которая, как и ее переменные (аргументы) X₁, X₂, X₃, …, X_n может принимать два значения: 0 или 1.

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

В качестве примера покажем всевозможные наборы переключательных функций от одной и двух переменных (табл. 1 и 2)

Таблица 1 Таблица 2

Поскольку любая булева функция определена на наборах и сама принимает только два значения (0 или 1), то число булевых функций от n переменных равно . Например, при (т. е. для булевой функции от одной переменной) существует различных булевых функций, каждая из которых определена на наборах (табл. 1).

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

Как следует из табл. 3, существует всего четыре сингулярные функции от одной переменной X: константа 0, переменная X, инверсия X, константа 1.

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

Таблица 3

Функция - переменная X на одном наборе равна 0, а на другом наборе равна 1, т. е. повторяет переменную X.

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

При , т. е. для булевых функций от двух переменных X₁ и X₂ (бинарные функции) существует различных функций, каждая из которых определена на четырех наборах (см. табл. 2).

Булевы функции двух переменных, их условное обозначение и название приведем в табл. 4.

Среди этих 16 функций фактически бинарными являются 10, а остальные 6 зависят от двух переменных формально и являются либо константами (f₀ и f₁₅), либо сингулярными, т. е. повторениями переменных (f₃ и f₅) и их отрицаниями (f₁₀ и f₁₂).

К наиболее часто встречающимся булевым функциям от двух переменных относятся функции f₁ (конъюнкция), f₇ (дизъюнкция) и f₆ (логическая неравнозначность, исключающее ИЛИ, сложение по модулю 2).

Функция f₁ принимает значение 1 только на одном из четырех возможных наборов переменных, а именно на наборе и . На всех остальных наборах ее значение равно 0. Применительно к преобразованию сигналов это означает, что сигнал на выходе устройства, имеющего два входа (X₁ и X₂), появится только тогда, когда сигнал 1 будет одновременно присутствовать на двух входах.

Рис. 1 Обозначение логического элемента И:

а) отечественное;

б) зарубежное.

Элемент, реализующий эту функцию, носит название схемы И (логическое умножение).

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

ЛЭ И часто называют схемой совпадений или конъюнктором.

· Логика работы конъюнктора на два входа представляется таблицей истинности (состояний) (табл. 5)

Таблица 5

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

или .

Временная диаграмма работы конъюнктора на два входа имеет вид (рис. 2):

Рис 2

где U₁ и U₀ - уровни напряжения соответствующие «1» и «0».

Из временной диаграммы следует, что если на вход конъюнктора поступают сигналы в разные моменты времени и разной длительности, то сигнал на выходе конъюнктора определяется как результат пересечения входных сигналов.

Функция f₇ принимает значение 1 на всех наборах переменных, кроме одного и . Применительно к преобразованию сигналов это означает, что сигнал на выходе устройства, имеющего два входа (X₁ и X₂), появится только тогда, когда сигнал 1 будет присутствовать хотя бы на одном из входов. Элемент, реализующий эту функцию, носит название схемы ИЛИ (логическое сложение). Схему ИЛИ обозначают прямоугольником с символом 1 внутри него (рис. 3) и иногда называют дизъюнктором или собирательной схемой.

Рис. 3. Обозначение ЛЭ ИЛИ:

а) в отечественной литературе;

б) в иностранной или переводной

· Таблица истинности дизъюнктора имеет вид (табл. 6):

Логическое уравнение или .

Временная диаграмма работы дизъюнктера на два входа имеет вид (рис. 4):

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

Из остальных функций табл. 4 выделим функцию f₁₂. Элемент, реализующий ее, носит название схемы НЕ. Применительно к преобразованию сигналов данная функция означает, что сигнал на выходе устройства, имеющего один вход X₁ (или X₂ для f₁₀), появится только в том случае, если сигнал 1 на входе отсутствует или другими словами на вход подан сигнал логического нуля.

Рис 4

При наличии сигнала 1 на входе, на выходе схемы НЕ будет действовать сигнал 0. В соответствии с выполняемой операцией инверсии элемент НЕ иногда называют инвертором.

Рис. 5

а, б - логический элемент НЕ, в, г - логический элемент ИЛИ-НЕ, д, е - логический элемент И-НЕ

Логическое отрицание обычно обозначают сплошной линией над соответствующими логическими переменными, например .

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

ЛЭ И, ИЛИ, НЕ являются самыми важными и самыми элементарными цифровыми устройствами, называемыми вентилями (gates). (По-английски термин «вентили» (во множественном числе) пишется и звучит точно так же, как имя основателя компании Microsoft Билла Гейтса). Вентиль называется комбинационной схемой, т. к. сигнал на его выходе определяется только комбинацией входных сигналов в данный момент времени.

Некоторые из приведенных в табл. 4 функций могут быть распространены и на большее число независимых переменных. К таким функциям можно отнести, например, f₁, f₇, f₈, f₁₀, и др.

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

Обращаясь к табл. 4, можно заметить, что некоторые из приведенных функций получаются методом декомпозиции или перенумерации (переименования) аргументов булевых функций. Так функция f₁₃ может быть получена из функции f₁₁, если поменять местами аргументы X₁ и X₂. Функция f₁₄ (штрих Шеффера) может быть получена из функции f₁₂ посредством замены значений аргумента X₁ значениями функции f₁.

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

, а и ,

то очевидно, что

.

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

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

В общем случае одна из приведенных в этой системе функций, а именно дизъюнкция или конъюнкция, является лишней, поскольку ее исключение не приводит к нарушению функциональной полноты системы. Действительно, кроме этой системы функциональной полнотой будут обладать системы булевых функций вида В и С, включающие всего две функции.

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

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

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

Литература

1. Новиков Ю.В. Основы цифровой схемотехники. Базовые элементы и схемы. Методы проектирования. М.: Мир, 2001. - 379 с.

2. Новиков Ю.В., Скоробогатов П.К. Основы микропроцессорной техники. Курс лекций. М.: ИНТУИТ.РУ, 2003. - 440 с.

3. Пухальский Г.И., Новосельцева Т.Я. Цифровые устройства: Учеб. пособие для ВТУЗов. СПб.: Политехника, 2006. - 885 с.

4. Преснухин Л.Н., Воробьев Н.В., Шишкевич А.А. Расчет элементов цифровых устройств. М.: Высш. шк., 2001. - 526 с.

5. Букреев И.Н., Горячев В.И., Мансуров Б.М. Микроэлектронные схемы цифровых устройств. М.: Радио и связь, 2000. - 416 с.

6. Соломатин Н.М. Логические элементы ЭВМ. М.: Высш. шк., 2000. - 160 с.