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

Размещено на 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.

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

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

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

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

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

₂₃₅₆ v ₁₂₃₄ v

_2356.

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

₁₄ v ₁₂₅₆ v

₂₃₅₆ v _2356.

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₅ симметричны при доопределении карт следующим образом:

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

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

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

1) z₁ = x₁ x_4;

z₄ = x₁ * x_4.

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

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

2) z₂ = x₂ x_5;

z₅ = x₂ * x_5.

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

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

3) z₃ = x₃ x_6;

z₆ = x₃ * x_6.

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

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

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

Таблица 5.

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

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

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

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

Получили следующую систему функций:

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

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

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

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

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

где L”(y_i) - сложность представления функции y_i без учета сложности реализации

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

L(Y) = 7 + 8 + 8 + 15 + 5 = 43 (4)

оператора И, ИЛИ, НЕ, что на 30 операторов меньше, чем в (3).

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