Проектирование сумматора по модулю пять

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

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

Анализ технического задания

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

Y = (X1 * X2) mod 5 = X1 * X2 - [(X1 * X2) / 5] * 5, (1)

где X1,X2,Y < 5. (2)

Максимальное значение переменных X1,X2,Y равно четырем. Для представления этого числа в двоичной системе счисления понадобится число разрядов, равное

N = ]log₂5[ = 3

Представим входные и выходную переменные, как

X1 = {x₁ x₂ x₃} X2 = {x₄ x₅ x₆} Y = {y₁ y₂ y₃}

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

симметричный переменная декомпозиция алгебра

Составление таблицы истинности

На основе уравнения (1) формируем таблицу истинности устройства. Отсортируем входные наборы по убыванию количества неинверсных переменных. Согласно (2) на наборах, где X1 ? 5 или X2 ? 5, значения Y неопределенны, что обозначим, как «*». Соответствие выходных наборов входным приведено в таблице 1.

Таблица 1.

№ набора	Кол-во неинв. перемен.	Входные наборы	Значения	X1 * X2	Оста-ток	Y
		X1	X2	X1	X2
1	6	111	111	7	7	14	4	*
2	5	111	110	7	6	13	3	*
3		111	101	7	5	12	2	*
4		111	011	7	3	10	0	*
5		110	111	6	7	13	3	*
6		101	111	5	7	12	2	*
7		011	111	3	7	10	0	*
8	4	111	100	7	4	11	1	*
9		111	010	7	2	9	4	*
10		111	001	7	1	8	3	*
11		110	110	6	6	12	2	*
12		110	101	6	5	11	1	*
13		110	011	6	3	9	4	*
14		101	110	5	6	11	1	*
15		101	101	5	5	10	0	*
16		101	011	5	3	8	3	*
17		100	111	4	7	11	1	*
18		011	110	3	6	9	4	*
19		011	101	3	5	8	3	*
20		011	011	3	3	6	1	001
21		010	111	2	7	9	4	*
22		001	111	1	7	8	3	*
23	3	111	000	7	0	7	2	*
24		110	100	6	4	10	0	*
25		110	010	6	2	8	3	*
26		110	001	6	1	7	2	*
27		101	100	5	4	9	4	*
28		101	010	5	2	7	2	*
29		101	001	5	1	6	1	*
30		100	110	4	6	10	0	*
31		100	101	4	5	9	4	*
32		100	011	4	3	7	2	010
33		011	100	3	4	7	2	010
34		011	010	3	2	5	0	000
35		011	001	3	1	4	4	100
36		010	110	2	6	8	3	*
37		010	101	2	5	7	2	*
38		010	011	2	3	5	0	000
39		001	110	1	6	7	2	*
40		001	101	1	5	6	1	*
41		001	011	1	3	4	4	100
42		000	111	0	7	7	2	*
43	2	110	000	6	0	6	1	*
44		101	000	5	0	5	0	*
45		100	100	4	4	8	3	011
46		100	010	4	2	6	1	001
47		100	001	4	1	5	0	000
48		011	000	3	0	3	3	011
49		010	100	2	4	6	1	001
50		010	010	2	2	4	4	100
51		010	001	2	1	3	3	011
52		001	100	1	4	5	0	000
53		001	010	1	2	3	3	011
54		001	001	1	1	2	2	010
55		000	110	0	6	6	1	*
56		000	101	0	5	5	0	*
57		000	011	0	3	3	3	011
58	1	100	000	4	0	4	4	100
59		010	000	2	0	2	2	010
60		001	000	1	0	1	1	001
61		000	100	0	4	4	4	100
62		000	010	0	2	2	2	010
63		000	001	0	1	1	1	001 0
64	0	000	000	0	0	0	0	000

Замена симметричных переменных с использованием элементарных симметричных функций

1. Анализ симметрии переменных.

Согласно переместительному закону при перестановке слагаемых сумма чисел не меняется, следовательно можно сделать вывод о симметрии переменных x₁ и x₄, x₂ и x₅, x₃ и x₆. Подтвердим это утверждение.

Построим карты Карно для выходных функций образом, удобным для рассмотрения симметрии переменных x₁ и x₄, x₂ и x₅.

y1

x1

x4

x2

0

0

0

0

*

*

*

*

0

1

*

*

*

*

*

*

x6

x5

0

0

*

*

*

*

*

*

1

0

*

*

*

*

*

*

0

0

*

*

*

*

*

0

0

1

*

*

*

*

*

0

x6

0

0

*

*

*

*

*

0

0

0

0

1

0

*

*

1

x3

x3

y₁ = ₁₄₅₆ v ₂₃₅₆ v

₂₃₅₆ v ₁₂₃₄ v

_2356.

y2

x1

x4

x2

1

1

1

0

*

*

*

*

1

0

*

*

*

*

*

*

x6

x5

0

0

*

*

*

*

*

*

0

0

*

*

*

*

*

*

1

1

*

*

*

*

*

0

1

0

*

*

*

*

*

1

x6

0

1

*

*

*

*

*

0

0

0

0

0

1

*

*

0

x3

x3

y₂ = ₂₃₅₆ v ₂₃₄₅ v

₁₄ v ₁₂₅₆ v

₂₃₅₆ v _2356.

y3

x1

x4

x2

0

1

0

1

*

*

*

*

1

0

*

*

*

*

*

*

x6

x5

0

1

*

*

*

*

*

*

0

0

*

*

*

*

*

*

0

1

*

*

*

*

*

1

1

0

*

*

*

*

*

0

x6

1

0

*

*

*

*

*

0

0

1

0

0

1

*

*

0

x3

x3

y₃ = ₃₄₅₆ v ₂₃₄ v

₁₄ v ₁₃₅₆ v

₂₃₅₆ v ₁₅₆ v

₂₃₄₆ v ₁₂₃₆.

Сложность реализации устройства в этом представлении составляет

L(Y) = L'(y₁) + L'(y₂) + L'(y₃) + L_инв.,

где L'(y_i) - сложность представления функции y_i без учета инверсий входных переменных, а L_инв. - количество инверсных переменных, встречающихся в представлении функций y_1,2,3. Тогда

L(Y) = 19 + 21 + 27 + 6 = 73 (3)

оператора И, ИЛИ, НЕ.

На картах Карно видно, что переменные x₁ и x₄, x₂ и x₅ симметричны при доопределении карт следующим образом:

y2
						x1
				x4
	x2			1	1	1	0	*	*	1	0
				1	0	*	1	*	*	*	1		x6
		x5		0	0	*	*	*	*	*	*
				0	0	*	*	*	*	*	*
				1	1	1	0	*	*	1	0
				1	0	*	1	*	*	*	1		x6
				0	1	*	0	*	*	*	0
				0	0	0	0	1	*	0	0
					x3			x3

y1
						x1
				x4
	x2			0	0	0	0	*	*	0	0
				0	1	*	0	*	*	*	0		x6
		x5		0	0	*	*	*	*	*	*
				1	0	*	*	*	*	*	*
				0	0	0	0	*	*	0	0
				0	1	*	0	*	*	*	0		x6
				0	0	*	0	*	*	*	0
				0	0	0	1	0	*	0	1
					x3			x3

y3
						x1
				x4
	x2			0	1	0	1	*	*	0	1
				1	0	*	0	*	*	*	0		x6
		x5		0	1	*	*	*	*	*	*
				0	0	*	*	*	*	*	*
				0	1	0	1	*	*	0	1
				1	0	*	0	*	*	*	0		x6
				1	0	*	0	*	*	*	0
				0	1	0	0	1	*	0	0
					x3			x3

Перестройка карты Карно для рассмотрения симметрии переменных x₃ и x₆ также позволяет убедиться в сделанном предположении о симметрии этих переменных (причем дополнительное доопределение не требуется).

2. Замена переменных с использованием элементарных симметричных функций.

Произведем следующую замену переменных

1) z₁ = x₁ x_4;

z₄ = x₁ * x_4.

Таблица 2. Таблица истинности замены

x1	x4	z1	z4
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Запрещенным является состояние z₁ = 1, z₄ = 1.

2) z₂ = x₂ x_5;

z₅ = x₂ * x_5.

Таблица 3. Таблица истинности замены

x2	x5	z2	z5
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Запрещенным является состояние z₂ = 1, z₅ = 1.

3) z₃ = x₃ x_6;

z₆ = x₃ * x_6.

Таблица 4. Таблица истинности замены

x3	x6	z3	z6
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Запрещенным является состояние z₃ = 1, z₆ = 1.

Построим таблицу отображения исходных входных наборов в базис z_i и вычеркнем повторяющиеся наборы в z-отображении:

Таблица 5.

X1	X2	Y	Z
x1 x2 x3	x4 x5 x6	y1 y2 y3	z1 z2 z3	z4 z5 z6
011	011	001	000	011
100	011	010	111	000
011	100	010	111	000
011	010	000	001	010
011	001	100	010	001
010	011	000	001	010
001	011	100	010	001
100	100	011	000	100
100	010	001	110	000
100	001	000	101	000
011	000	011	011	000
010	100	001	110	000
010	010	100	000	010
010	001	011	011	000
001	100	000	101	000
001	010	011	011	000
001	001	010	000	001
000	011	011	011	000
100	000	100	100	000
010	000	010	010	000
001	000	001	001	000
000	100	100	100	000
000	010	010	010	000
000	001	001	001	000
000	000	000	000	000
Доопределено:
010	101	010	111	000
111	000	010	111	000
110	000	001	110	000
110	001	010	111	000
001	110	010	111	000
000	110	001	110	000
000	111	010	111	000
000	101	000	101	000
101	010	010	111	000
101	000	000	111	000

Построим карты Карно преобразованных функций.

y1

z1

z2

z4

0

*

*

*

*

*

*

*

*

Подобные документы

• Математическая логика

  Основные понятия алгебры логики. Дизъюнктивные и конъюнктивные нормальные формы. Сущность теоремы Шеннона. Булевы функции двух переменных. Последовательное и параллельное соединение двух выключателей. Свойства элементарных функций алгебры логики.
  
  контрольная работа [345,3 K], добавлен 29.11.2010
  

• Функционально полные системы булевых функций

  Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полинома Жегалкина. Распознавание монотонной функции по вектору ее значений. Доказательство теоремы Поста.
  
  учебное пособие [1,3 M], добавлен 20.08.2014
  

• Алгебра логики

  Основные аксиомы и тождества алгебры логики. Аналитическая форма представления булевых функций. Элементарные функции алгебры логики. Функции алгебры логики одного аргумента и формы ее реализации. Свойства, особенности и виды логических операций.
  
  реферат [63,3 K], добавлен 06.12.2010
  

• Функционально полные системы логических функций. Алгебраический подход

  Основная функционально полная система логических функций. Законы алгебры логики в основной функционально полной системе и их следствия. Переместительный и распределительный законы. Закон инверсии (правило Де Моргана). Системы логических функций.
  
  реферат [40,5 K], добавлен 17.11.2008
  

• Дискретная математика

  Понятие алгебры логики, ее сущность и особенности, основные понятия и определения, предмет и методика изучения. Законы алгебры логики и следствия из них, методы построения формул по заданной таблице истинности. Формы представления булевых функций.
  
  учебное пособие [702,6 K], добавлен 29.04.2009
  

• Синтез логического автомата

  Составление таблицы истинности. Получение уравнений функций алгебры логики для заданных выходов. Реализация схемы логического автомата на электромагнитных реле РП-23, на диодной матрице. Реализация структурной схемы логического автомата, на микросхемах.
  
  курсовая работа [862,4 K], добавлен 12.12.2012
  

• Полином Жегалкина

  Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.
  
  курсовая работа [701,9 K], добавлен 27.04.2011
  

• Булевы функции

  Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.
  
  контрольная работа [178,2 K], добавлен 20.01.2011
  

• Методические материалы по учебной дисциплине "Высшая математика" для студентов I курса заочной формы обучения

  Элементы линейной алгебры. Элементы аналитической геометрии и векторной алгебры. Введение в математический анализ. Дифференциальное исчисление функций одной переменной. Дифференциальное исчисление функций нескольких независимых переменных. Интеграл.
  
  методичка [90,5 K], добавлен 02.11.2008
  

• Таблица производных. Дифференцирование сложных функций

  Обзор таблицы производных элементарных функций. Понятие промежуточного аргумента. Правила дифференцирования сложных функций. Способ изображения траектории точки в виде изменения ее проекций по осям. Дифференцирование параметрически заданной функции.
  
  контрольная работа [238,1 K], добавлен 11.08.2009
  

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

  Сущность двоичной, восьмеричной и шестнадцатиричной систем счисления, их отличительные черты и взаимосвязь. Пример алгоритмов перевода чисел из одной системы в другую. Составление таблицы истинности и логической схемы для заданных логических функций.
  
  презентация [128,9 K], добавлен 12.01.2014
  

• Исследование алгебр многоместных функций

  История развития и становления математического понятия функции. Абстрактные характеристики упорядоченных алгебр многоместных функций: P-алгебры и D-алгебры. Исследование теории суперпозиций алгебраических структур n-местных функций Менгера и Глускера.
  
  курсовая работа [263,7 K], добавлен 22.12.2015
  

• Преобразование графиков функции

  Основные правила преобразования графиков на примерах элементарных функций: преобразование симметрии, параллельный перенос, сжатие и растяжение. Построение графиков сложных функций с помощью последовательных преобразований графиков элементарных функций.
  
  презентация [2,4 M], добавлен 16.11.2010
  

• Нахождение приближающих математических моделей в виде элементарных функций

  Определение коэффициентов элементарных функций: линейной, показательной, степенной, гиперболической, дробно-линейной, дробно-рациональной. Использование метода наименьших квадратов. Приближённые математические модели в виде приближённых функций.
  
  лабораторная работа [253,6 K], добавлен 05.01.2015
  

• Производные элементарных функций

  Частные случаи производной логарифмической функции. Производная показательной функции, экспоненты, степенной, тригонометрических функций. Производная синуса, косинуса, тангенса, котангенса, арксинуса. Производные обратных тригонометрических функций.
  
  презентация [332,2 K], добавлен 21.09.2013
  

• Эквиваленты функций

  Определение констант нуля и установление эквивалентности линейных функций при помощи таблицы истинности. Нахождение минимальной дизъюнктивной нормальной формы функции с помощью метода неопределенных коэффициентов. Преобразование функции методом Квайна.
  
  контрольная работа [335,2 K], добавлен 05.07.2014
  

• Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло

  Многие переменные, минимизация их функций. Точки максимума и минимума называются точками экстремума функции. Условия существования экстремумов функции многих переменных. Квадратичная форма, принимающая, как положительные, так и отрицательные значения.
  
  реферат [70,2 K], добавлен 05.09.2010
  

• Исследование и логическое проектирование конечного частично определённого автомата

  Построение таблицы поведения автомата и соответствующего графа. Нахождение системы булевых функций для возбуждения T-триггеров, реализующих функции "пси". Определение булевой функции для реализации функции "фи". Составление логической схемы автомата.
  
  курсовая работа [96,7 K], добавлен 27.04.2011
  

• Исследование возможностей основных соотношений булевой алгебры для решения практических задач

  Логический синтез устройства с использованием соотношений булевой алгебры. Составление таблицы истинности. Основные соотношения булевой алгебры. Логическая функция в смысловой, словесной, вербальной, табличной и аналитической математической формах.
  
  лабораторная работа [83,6 K], добавлен 26.11.2011
  

• Полиномы Жегалкина для логических операций

  Свойства алгебры Жегалкина. Действия с логическими константами (нулём и единицей). Свойства элементарных булевых функций, задаваемых логическими операциями. Способы построения полиномов с помощью таблиц истинности (метод неопределенных коэффициентов).
  
  курсовая работа [467,2 K], добавлен 28.11.2014
  

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