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

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

1. Сложение в шестнадцатеричной, двоичной, восьмеричной и десятичной системах счисления

1) Вычисления целесообразно начать с шестнадцатеричной системы:

ВD₁₆ + AA₁₆

Вычисление:

D + A = 13₁₀ + 10₁₀ = 23₁₀, поскольку 23>15, требуется перенос в

старший разряд

23₁₀ = 16₁₀ + 7₁₀

С учетом переноса получаем:

1+ 11 + 10 = 22₁₀, поскольку 22>15, требуется перенос в старший разряд.

22₁₀ = 16₁₀ + 6₁₀

Получаем в старшем разряде 1.

BD₁₆+AA₁₆=116² + 616¹ + 716⁰ = 167₁₆

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

B=1011 ₂

D = 1101₂

A = 1010₂

A = 1010₂

BD₁₆= 1011 1101₂

AA₁₆=1010 1010₂

Выполним сложение, учитывая, что

0+0= 0

1+0= 1

1+1 =10₂

1+1+1 =11₂

счисление тождественный граф логический

В результате с учетом переносов в старшие разряды получим:

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

0111₂ = 7

0110₂ = 6

0001₂ = 1

000101100111₂ = 167₁₆

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

BD₁₆= 1011 1101₂ = 010 111 101 ₂

Из таблицы получаем:

010₂ = 2

111₂ = 7

101₂ = 5

BD₁₆ = 275₈

Аналогично получим:

AA₁₆=1010 1010₂ = 010 101 010₂

010₂ = 2

101₂ = 5

010₂ = 2

В9₁₆ = 252₈

Осуществим поразрядное сложение 275₈ + 252₈

Вычисления выполняются аналогично шестнадцатеричной системе

5 + 2 = 7₈, поскольку 7<8, то перенос в старший разряд

не требуется

7 + 5 = 12₈, поскольку 12>7, требуется перенос в старший разряд

12₈ = 8₈ +4 ₈

1 + 2 + 2 = 5_8, поскольку 5<7, то перенос в старший разряд

не требуется

Таким образом:

275₈ + 252₈ = 547₈

Выполним проверку путем перевода результата в двоичную и шестнадцатеричную системы счисления

5₈ = 101₂

4₈ = 100₂

7₈ = 111₂

Отсюда получим

527₈ = 101 100 111₂ = 0001 0110 0111₂ = 167₁₆

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

BD₁₆= 11 16¹+13 16⁰=189₁₀

AA₁₆= 10 16¹+10 16⁰=170₁₀

189₁₀+170₁₀=359₁₀

167₁₆=116²+616+716⁰ =359₁₀

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

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

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

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

На основе данной таблицы можно получить аналитическое выражение для логической функции в совершенной дизъюнктивной или конъюнктивной нормальной формах (СДНФ или СКНФ). Элементы СДНФ называют минитермами, а СКНФ - макстермами. СДНФ представляет собой дизъюнкцию минитермов, а СКНФ - конъюнкцию макстермов. Легко обнаружить, что минитерм равен 1 только при одном единственном входном слове, а макстерм равен 0 также только при одном единственном входном слове. Аналитическое выражение функции в форме СДНФ будет содержать конституенты единиц (и только их) для входных слов, при которых функция =1, а в форме СКНФ будет содержать конституенты нулей (и только их) для входных слов, при которых функция =0. При этом, если аргумент во входном слове =1, он входит в конституенту единицы в прямой форме, а в конституенту нуля - в инверсной. И наоборот, если аргумент во входном слове =0, он входит в конституенту нуля в прямой форме, а в конституенту единицы - в инверсной.

В результате для заданной функции можно получить следующие аналитические выражения в форме СДНФ:

и СКНФ:

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

Каноническая задача синтеза логических схем сводится к минимизации булевых функций, т.е. к представлению их в дизъюнктивной нормальной форме, которая содержит наименьшее число букв (переменных и их отрицаний). Такие формы называют минимальными. Формула, представленная в дизъюнктивной нормальной форме, упрощается многократным применением закона склеивания и закона поглощения . Здесь под a и b можно понимать любую формулу алгебры логики.

Минимизируем булевы функции:

1) Начинаем склеивание входных слов в форме СДНФ:

Путем склеивания мы получили минмальную форму .

2) Начинаем склеивание входных слов в форме CКНФ:

Путем склеивания мы получили минмальную форму .

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

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

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

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

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

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

1) Склеиваем точки, принадлежащие одному ребру, получаем ребра:

2) Склеиваем ребра, принадлежащие одной грани и параллельные друг другу, получаем грани:

3) В итоге получаем минимальную функцию

Таким образом, результат минимизации методом S-кубов проверен тождественными преобразованиями.

3. Минимизация логических функций методом карт Карно. Построение логических схем

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

Минимизируем с помощью карты Карно функцию, заданную следующей таблицей соответствия:

Отобразим данную функцию на карте Карно, проставив 1 в ячейки карты, соответствующие входным словам, при которых функция =1. Ребрам, граням и кубам на карте Карно соответствуют ортогональные области (блоки - строки, столбцы, квадраты, прямоугольники) заполненные 2, 4 и 8 единицами.

Минитерм, соответствующий той иди иной области (блоку) определяется как конъюнкция переменных или их инверсий, соответствующих областям, на пересечении которых данная ассоциация находится. Минимальная форма формируется как дизъюнкция этих минитермов. Для приведенной функции минимальная форма будет содержать минитермы, соответствующие трем ассоциациям: из двух единиц и из 8 единиц.

В результате минимальная форма будет иметь вид:

Для полученной минимальной формы логическая схема будет иметь вид:

4. Построение графа конченого автомата по общей таблице выходов и переходов. Моделирование работы конечного автомата

Таблицa состояний и переходов конечного автомата

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

Подобное построение осуществляется для каждого исходного состояния конечного автомата (каждой строки).

Граф конечного автомата выглядит следующим образом:

По графу осуществляем моделирование работы автомата при подаче на него некоторой последовательности входных слов. Для каждого входного слова и данного состояния по графу определяется выходное слово и состояние в следующем такте S(?+1). Затем процедура повторяется для этого нового состояния и т.д. Таблица моделирования работы автомата приведена ниже:

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