Математические основы проектирования цифровых устройств

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

Математические основы проектирования цифровых устройств

План

• 1. Понятие системы счисления. Ее типы
• 2. Основы алгебры логики
• 2.1 Логические функции
• 2.2 Правила алгебры логики
• 2.3 Составление логических функций
• 2.4 Минимизация логических функций
• Библиографический список

1. Понятие системы счисления. Ее типы

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

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

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

XXXIV = 10 + 10 + 10 - 1 + 5 = 3Ч10 + -1 + 5 = 34.

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

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

Наша привычная десятичная система является позиционной, ее основание q равно 10 и использует цифры от 0 до 9. Например, в числе 34 цифра 3 имеет весовой коэффициент 10¹ и вносит вклад в число 3Ч10¹ = 30, а цифре 4 соответствует величина 4Ч10⁰ = 4:

3Ч10¹+4Ч10⁰ = 30 + 4 = 34.

В числе 304 цифра 3 имеет уже весовой коэффициент 10², и ей будет соответствовать величина 3Ч10² = 300. Расписывая подобным образом цифры 0 и 4, с учетом их позиции i, получим:

3Ч10²+0Ч10¹+4Ч10⁰ = 300 + 0 + 4 = 304.

Из приведенных примеров видно, что чем больше позиция цифры, тем больше ее вес.

Этому же правилу подчиняются цифры дробной части числа, например, 34,25 распишется как

3Ч10¹ + 4Ч10⁰ + 2Ч10^-1 + 5Ч10^-2 = 30 + 4 + 0,2 + 0,05 = 34,25.

Изменяя основание системы q, можно создать сколь угодно много позиционных систем счисления: двоичную (q = 2), троичную (q = 3), четверичную (q = 4) и т.д.

На сегодняшний день в цифровой схемотехнике, помимо десятичной, широко применяются двоичная, восьмеричная и шестнадцатеричная системы счисления. Их основания q равны 2, 8 и 16, а весовые коэффициенты i-ой позиции определяются как 2ⁱ, 8ⁱ и 16ⁱ соответственно.

Двоичная система счисления использует всего две цифры: 0 и Поэтому число 2₍₁₀₎, записанное в десятичной системе счисления, в двоичной будет выглядеть как 10₍₂₎. При этом нельзя произносить "ДЕСЯТЬ", поскольку этой записи соответствует число ДВА. Все числа, записанные в отличной от десятичной системы счисления, произносятся по цифрам, т.е. 10₍₂₎ - это "ОДИН, НОЛЬ", а не "ДЕСЯТЬ". Чтобы отличить одну форму записи числа от другой, будем в индексе числа в скобочках указывать соответствующее системе счисления основание.

Восьмеричная система счисления использует восемь цифр: 0 - 7. Число 34₍₁₀₎ в ней будет иметь вид 42₍₈₎. И помним, что это не "СОРОК ДВА", а "ЧЕТЫРЕ, ДВА".

И последняя, которая нас интересует, - это шестнадцатеричная система счисления. Как отмечалось выше, ее основание q = 16, поэтому количество цифр будет тоже 16: 0-9, A, B, C, D, E, F. Обозначение недостающих цифр заимствовано из латинского алфавита. Цифре A соответствует десятичное число 10, цифре В - 11 и т.д. Число 110₍₁₀₎ в шестнадцатеричной системе выглядит как 6E₍₁₆₎.

Перевод чисел из десятичной системы счисления в любую не десятичную

ПРАВИЛО! Исходное десятичное число делят на основание целевой системы нацело. Остаток от деления записывают в младший разряд получаемого числа, а результат деления снова делят на основание целевой системы. Остаток от деления записывают в следующий более старший разряд. Процесс деления продолжают до тех пор, пока результат не станет нулевым.

Пример:

Получившиеся остатки деления записываются снизу вверх. Следует обратить внимание, что чем больше основание системы счисления q, тем компактней запись числа X.

Перевод чисел из любой не десятичной системы счисления в десятичную

ПРАВИЛО! Каждую цифру исходного числа умножают на ее весовой коэффициент, а затем получившиеся произведения складывают.

Пример:

1101110₍₂₎>X₍₁₀₎ = 1Ч2⁶ + 1Ч2⁵ + 0Ч2⁴ + 1Ч2³ + 1Ч2² + 1Ч2¹ + 0Ч2⁰ = 110₍₁₀₎;

156₍₈₎>X₍₁₀₎ = 1Ч8² + 5Ч8¹ + 6Ч8⁰ = 110₍₁₀₎;

6E₍₁₆₎>X₍₁₀₎ = 6Ч16¹ + E(14)Ч16⁰ = 110₍₁₀₎.

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

Пример:

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

Перевод чисел из двоичной системы счисления в шестнадцатеричную (восьмеричную) и обратно

ПРАВИЛО! Исходное двоичное число разбивают, начиная справа, на группы по четыре (три) цифры, затем каждую группу преобразуют в шестнадцатеричную (восьмеричную) цифру, в соответствии с таблицей

ПРАВИЛО ОБРАТНОГО ПЕРЕВОДА! Каждую шестнадцатеричную (восьмеричную) цифру числа преобразовать в группу из четырех (трех) двоичных цифр по той же таблице.

Таблица 1.1 Числовой ряд

Пример:

2. Основы алгебры логики

Основой проектирования цифровых устройств является алгебра логики, разработанная ирландским математиком Джорджем Булем (1815-1864 гг.). В ее основе лежат две цифры - 0 и 1, поэтому эта алгебра работает с двоичной системой счисления.

2.1 Логические функции

алгебра логика счисление функция

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

Например, в выражении y = sin(x), x является аргументом, y - функцией, а sin - это описание функции.

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

– словесная форма (функция описывается привычным для человека языком);

– таблица истинности или состояний (специальная таблица, где каждой комбинации аргументов функции ставится в соответствие некоторое ее значение);

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

Таблица 1.2 Булевы функции одной переменной y = f(x)

Булевы функции одной переменной y = f(x). В таких функциях имеется только один аргумент x, именно он и выполняемая над ним операция будут определять значение функции y. В таблице 1.2 перечислены возможные функции, их обозначения и названия. Первая функция называется константа 0, она всегда принимает нулевое значение независимо от значения аргумента x. Вторая принимает такое же значение, что и аргумент x. Третья имеет противоположное значение аргумента x и обозначается чертой над ним. Последняя, так же, как и первая, не зависит от аргумента, но, в отличие от нее, принимает всегда единичное значение.

Булевы функции двух переменных y = f(x₁, x₂). Здесь функций будет 16 (табл. 1.3).

Таблица 1.3 Булевы функции двух переменных y = f(x1, x2)

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

Они называются основными логическими функциями.

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

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

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

и ту же самую функцию, но записанную с помощью набора, состоящего из одной функции

,

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

Рис. 1.1. Реализация логической функции на элементах

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

1. Закон двойного отрицания

2. Коммутативные законы

1. 3. Идемпотентные законы

4. Ассоциативные законы

5. Дистрибутивные законы

6.

7. Законы двойственности (теоремы де Моргана, Огастес де Морган - шотландский математик и логик, 1806-1871 гг.)

8. Законы поглощения

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

2.3 Составление логических функций

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

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

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

Порядок составления логической функции:

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

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

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

Таблица 1.4 Таблица состояний

Пример. Записать СДНФ и СКНФ функции трёх аргументов, которая равна единице, когда не менее двух аргументов равны единице (табл. 1.4).

Решение. Из условия задачи имеем три аргумента: x₁, x₂ и x₃. Перечислим в левом столбце таблицы истинности всевозможные комбинации значений аргументов, а в правом - соответствующие им значения функции y. Для каждой строки составим логическую сумму или логическое произведение аргументов в соответствии с пунктом в) порядка составления функций (табл. 1.4).

2.4 Минимизация логических функций

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

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

Карты Карно используются при проектировании помехозащищённых кодов и отличаются от карт Вейча только расположением аргументов.

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

Алгоритм минимизации логической функции сводится к следующему:

для логической функции составляется таблица состояний;

в ячейки карты записываются значения функции из таблицы состояний;

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

для каждого прямоугольника записывают логическую функцию в виде логического умножения аргументов, которые для данного прямоугольника не изменяют своё значение. Произведения носят название импликанты;

полностью минимизированная логическая функция получается путём логического сложения импликантов.

Рис. 1.2 Карты Вейча

Рис. 1.3 Карты Карно

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

Пример. Минимизировать логическую функцию, заданную таблицей состояний 1.5.

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

Пример. Минимизировать логическую функцию, заданную таблицей 1.6.

Библиографический список

1. Опадчий Ю.Ф. Аналоговая и цифровая электроника / Ю.Ф. Опадчий, О.П. Глудкин, А.И. Гуров. - М.: Горячая линия - Телеком, 2002. - 768 с.

2. Пухальский Г.И. Проектирование дискретных устройств на интегральных микросхемах / Г.И. Пухальский, Т.Я. Новосельцева. - М.: Радио и связь, 1990. - 303 с.

3. Шило В.Л. Популярные цифровые микросхемы / В.Л. Шило. - М.: Металлургия, 1988. - 352 с.

4. Букреев И.Н. Микроэлектронные схемы цифровых устройств / И.Н. Букреев, Б.М. Мансуров, В.И. Горячев. - М.: Советское радио, 1975. - 367 с.

5. Стребков В.И. Импульсный частотно-фазовый дискриминатор на интегральных микросхемах / В.И. Стребков // Электронная техника в автоматике. - М.: Советское радио, 1977. - Вып. 9. - С. 223-230.

6. А.с. 569000 СССР, МКИ 2 Н 03 D 13/00. Импульсный частотно-фазовый дискриминатор / В.И. Стребков (СССР). - 3 с.: ил.

7. Федорков Б.Г. Микросхемы ЦАП и АЦП: функционирование, параметры, применение / Б.Г. Федорков, В.А. Телец. - М.: Энергоатомиздат, 1990. - 318 с.

8. Сазонов А.А. Микроэлектронные устройства автоматики / А.А. Сазонов [и др.]. - М.: Энергоатомиздат, 199 - 383 с.

9. Бубнов А.В. Логическое устройство сравнения для систем фазовой автоподстройки частоты / А.В. Бубнов [и др.] // Омский научный вестник. - 2009. - № 3(83). - С. 223-227.

10. Чижма С.Н. Основы схемотехники: учебное пособие для вузов / С.Н. Чижма. - Омск: Изд-во "Апельсин", 2008. - 424 с.: ил.

11. Гутников В.С. Интегральная электроника в измерительных устройствах / В.С. Гутников. - 2-е изд., перераб. и доп. - Л.: Энергоатомиздат, Ленингр. отделение, 1988. - 304 с.: ил.

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