eng
Проектирование контролепригодных цифровых ИС с регулярной структурой, к которым относятся сумматоры, умножители, делители, различные схемы памяти, значительно проще, чем ИС с нерегулярной структурой. Контролепригодная схема однотактного матричного двоичного умножителя, обладающая проверяющим тестом длины 6 относительно ее одиночных константных неисправностей независимо от ее размерности [1, 2], имеет существенный недостаток – значительный объем аппаратных средств, необходимый для ее реализации. Этого недостатка лишена рассматриваемая оригинальная контролепригодная функционально-логическая схема однотактного матричного двоичного умножителя, обладающая проверяющим тестом длины 5.
Основу новой схемы составляют слои одноразрядных сумматоров, объединенных в пределах каждого слоя в сумматор параллельного действия с последовательным переносом. При этом построение контролепригодной схемы одноразрядного сумматора, лежащей в основе многоразрядного сумматора каждого слоя, базируется на представлении функции суммы S в форме полинома Жегалкина, а функции переноса Р, в отличие от работ [3, 4], – в "смешанной" форме (специфика функции Р допускает такое представление):
...
где а и b – значения исходных одноразрядных операндов, p и Р – значения входного и выходного сигналов переноса, соответственно, S – значение сигнала суммы, r – символ сложения по mod 2, Ъ – символ дизъюнкции.
Контролепригодная логическая схема одноразрядного сумматора, реализованная по приведенным формулам, показана на рис.1. Проверяющий тест для этой схемы относительно всех одиночных константных неисправностей содержит 5 векторов и описывается таблицей, представленной на рис.1. Обнаружение отмеченных неисправностей этой схемы происходит следующим образом. Тестовые векторы 1, 2, 4 и 5 из таблицы рисунка 1 обнаруживают все одиночные константные неисправности данной схемы, кроме одиночной неисправности типа "константа 1" на том входе конъюнктора 2, который связан с внешним входом р. Эту неисправность обнаруживает тестовый вектор 3.
Контролепригодная схема n-разрядного (где n – натуральное число) двоичного сумматора каждого слоя рассматриваемого матричного умножителя получается из n контролепригодных схем полного одноразрядного сумматора обычным путем, т.е. соединением выхода переноса i-й схемы с входом переноса (i + 1)-й схемы, где 1 Ј i Ј n – 1. Эта схема приведена на рис.2.
Проверяющий тест Т для контролепригодной схемы n-разрядного двоичного сумматора относительно всех ее одиночных константных неисправностей состоит из двух частей Т = Т1 Т2 и строится следующим образом:
· часть Т1 содержит три тестовых вектора t1, t2, t3, которые образуются путем простой итерации соответственно первого, второго и третьего тестовых векторов из таблицы рис.1 для всех разрядов;
· часть Т2 содержит два тестовых вектора t4, t5. Тестовый вектор t4 образуется путем итерации четвертого тестового вектора из таблицы рис.1 для нечетных разрядов и пятого тестового вектора из этой таблицы для четных разрядов. Пятый тестовый вектор t5 образуется путем итерации пятого тестового вектора из таблицы рис.1 для нечетных разрядов и четвертого тестового вектора из этой таблицы для четных разрядов.
Тест Т описывается таблицей рис.2.
Контролепригодная функционально-логическая схема однотактного nxm-разрядного матричного умножителя (где n – число разрядов множимого, m – число разрядов множителя) для случая n = 5, m = 4 приведена на рис.3. Эта схема, как и схема обычного 5х4-разрядного матричного умножителя, содержит три слоя сумматоров и четыре слоя конъюнкторов. Однако, как уже отмечалось, схемы сумматоров реализованы по приведенным выше формулам. Помимо этого, рассматриваемая схема содержит шесть дополнительных двухвходовых элементов "исключающее ИЛИ" и два дополнительных входа u1, u2. При этом в рабочем режиме на входы с, u1, u2, p1, p2, p3 подаются сигналы логического "0". Проверяющий тест для этой схемы относительно всех ее одиночных константных неисправностей содержит 5 векторов и описывается таблицей рис.3.
При подаче на входы схемы тестовых векторов из таблицы (см. рис.3) в последовательности v1 v2, v3 v4, v5 на входы сумматора первого слоя поступят тестовые векторы из таблицы рис.2 в последовательности t1, t2, t3, t5, t4; на входы сумматора второго слоя – тестовые векторы из таблицы рис.2 в последовательности t2, t1, t3, t5, t4; на входы сумматора третьего слоя – тестовые векторы из таблицы рис.2 в последовательности t1, t2, t3, t5, t4, т.е. обеспечивается подача на входы n-разрядного сумматора каждого слоя проверяющего теста этого сумматора относительно одиночных константных неисправностей. При этом также обеспечивается подача на входы каждого слоя конъюнкторов их проверяющих тестов и подача на входы дополнительных элементов "исключающее ИЛИ" проверяющих тестов этих элементов.
Синтез тестовой последовательности для рассматриваемой контролепригодной схемы матричного двоичного умножителя может быть осуществлен на основе комбинации формальных и эвристических методов. Сначала строится проверяющий тест для схемы одноразрядного сумматора с помощью формальных методов (например, с помощью D- и PODEM-алгоритмов), а затем на основе этого теста поэтапно проводится построение общей тестовой последовательности для схемы матричного умножителя с помощью эвристических методов. Легко видеть, что в общем случае, т.е. когда n и m – произвольные натуральные числа, контролепригодная функционально-логическая схема однотактного матричного умножителя содержит m-1 сумматоров с последовательным переносом, m слоев конъюнкторов, а также n+m-3 дополнительных двухвходовых элементов "исключающее ИЛИ". Число дополнительных входов при этом не изменится и останется равным двум.
Проверяющий тест для общего случая также содержит 5 векторов и строится следующим образом:
· на каждый вход yj подается последовательность 1, 1, 0, 1, 0, если j – нечетное число, и последовательность 1, 1, 0, 0, 1, если j – четное число (j О {1, 2, ..., n }) ;
· на каждый вход хi подается последовательность 0, 1, 1, 1, 1, если i – нечетное число, и последовательность 1, 0, 1, 1, 1, если i – четное число (i О {1, 2, ..., m });
· на каждый вход pk подается последовательность 0, 1, 0, 0, 1, если k – нечетное число, и последовательность 1, 0, 0, 0, 1, если k – четное число (k О {1, 2, ..., m-1});
· на вход u1 подается последовательность 0, 0, 1, 1, 1, а на вход u2 последовательность 1, 1, 1, 0, 0 .
Схема одноразрядного сумматора, лежащая в основе рассматриваемой контролепригодной схемы матричного двоичного умножителя, легко преобразуется в схему, отличающуюся от схемы на рис.1 только тем, что логические элементы 1, 2, 3 последней заменены логическими элементами "И–НЕ". Проверяющий тест контролепригодной схемы матричного умножителя, которая получается в результате данного преобразования схемы одноразрядного сумматора, останется прежним. При этом полученная контролепригодная схема в общем случае требует для своей реализации значительно меньших аппаратных затрат, чем более ранняя схема [1]. Дело в том, что одноразрядный сумматор, лежащий в основе этой схемы, требует для своей реализации девять двухвходовых элементов "И–НЕ", а одноразрядный сумматор, лежащий в основе полученной схемы – два двухвходовых элемента "исключающее ИЛИ" и три двухвходовых элемента "И–НЕ". В случае использования биполярной технологии (в частности, ТТЛ) логический элемент "И–НЕ" может быть реализован схемой, содержащей два биполярных транзистора и два резистора [5]. Элемент "исключающее ИЛИ" в этом случае может быть реализован схемой, содержащей всего три биполярных транзистора и два диода [6]. Другими словами, здесь схемотехническая сложность реализации элемента "исключающее ИЛИ" практически равна схемотехнической сложности реализации элемента "И–НЕ". Известна также простая реализация элемента "исключающее ИЛИ" на основе КМОП-технологии [7].
Литература
1. Takach A.R., Jha N.K. Easily testable gate – level and DCVS multipliers. – IEEE Trans. on computer aided design, 1991, v.10, №7, p.932–942.
2. Киносита К., Асада К., Карацу О. Логическое проектирование СБИС. – М.: Мир, 1988.
3. Тимошкин А.И. Контролепригодная функционально-логическая схема двоичного сумматора. – Приборы и системы управления, 1997, №1, с. 42–43.
4. Тимошкин А.И. Контролепригодная схема двоичного сумматора. – Автоматика и вычислительная техника, 2000, №3, с. 82–84.
5. Ватанабэ М., Асада К., Кани К., Оцуки Т. Проектирование СБИС. – М.: Мир, 1988.
6. А.с. 319076. Логический элемент "исключающее ИЛИ"./ В.Я. Загурский, Ю.Н. Артюх, А.К. Баумс. Изобретения. 1971. Бюллетень № 32.
7. А.с. 790340. Логический элемент "исключающее ИЛИ" на КМДП-транзисторах./ Ю.И. Грибов, Л.В. Шафранский, И.Д. Якушев. Изобретения. 1980. Бюллетень № 47.
...
где а и b – значения исходных одноразрядных операндов, p и Р – значения входного и выходного сигналов переноса, соответственно, S – значение сигнала суммы, r – символ сложения по mod 2, Ъ – символ дизъюнкции.
Контролепригодная логическая схема одноразрядного сумматора, реализованная по приведенным формулам, показана на рис.1. Проверяющий тест для этой схемы относительно всех одиночных константных неисправностей содержит 5 векторов и описывается таблицей, представленной на рис.1. Обнаружение отмеченных неисправностей этой схемы происходит следующим образом. Тестовые векторы 1, 2, 4 и 5 из таблицы рисунка 1 обнаруживают все одиночные константные неисправности данной схемы, кроме одиночной неисправности типа "константа 1" на том входе конъюнктора 2, который связан с внешним входом р. Эту неисправность обнаруживает тестовый вектор 3.
Контролепригодная схема n-разрядного (где n – натуральное число) двоичного сумматора каждого слоя рассматриваемого матричного умножителя получается из n контролепригодных схем полного одноразрядного сумматора обычным путем, т.е. соединением выхода переноса i-й схемы с входом переноса (i + 1)-й схемы, где 1 Ј i Ј n – 1. Эта схема приведена на рис.2.
Проверяющий тест Т для контролепригодной схемы n-разрядного двоичного сумматора относительно всех ее одиночных константных неисправностей состоит из двух частей Т = Т1 Т2 и строится следующим образом:
· часть Т1 содержит три тестовых вектора t1, t2, t3, которые образуются путем простой итерации соответственно первого, второго и третьего тестовых векторов из таблицы рис.1 для всех разрядов;
· часть Т2 содержит два тестовых вектора t4, t5. Тестовый вектор t4 образуется путем итерации четвертого тестового вектора из таблицы рис.1 для нечетных разрядов и пятого тестового вектора из этой таблицы для четных разрядов. Пятый тестовый вектор t5 образуется путем итерации пятого тестового вектора из таблицы рис.1 для нечетных разрядов и четвертого тестового вектора из этой таблицы для четных разрядов.
Тест Т описывается таблицей рис.2.
Контролепригодная функционально-логическая схема однотактного nxm-разрядного матричного умножителя (где n – число разрядов множимого, m – число разрядов множителя) для случая n = 5, m = 4 приведена на рис.3. Эта схема, как и схема обычного 5х4-разрядного матричного умножителя, содержит три слоя сумматоров и четыре слоя конъюнкторов. Однако, как уже отмечалось, схемы сумматоров реализованы по приведенным выше формулам. Помимо этого, рассматриваемая схема содержит шесть дополнительных двухвходовых элементов "исключающее ИЛИ" и два дополнительных входа u1, u2. При этом в рабочем режиме на входы с, u1, u2, p1, p2, p3 подаются сигналы логического "0". Проверяющий тест для этой схемы относительно всех ее одиночных константных неисправностей содержит 5 векторов и описывается таблицей рис.3.
При подаче на входы схемы тестовых векторов из таблицы (см. рис.3) в последовательности v1 v2, v3 v4, v5 на входы сумматора первого слоя поступят тестовые векторы из таблицы рис.2 в последовательности t1, t2, t3, t5, t4; на входы сумматора второго слоя – тестовые векторы из таблицы рис.2 в последовательности t2, t1, t3, t5, t4; на входы сумматора третьего слоя – тестовые векторы из таблицы рис.2 в последовательности t1, t2, t3, t5, t4, т.е. обеспечивается подача на входы n-разрядного сумматора каждого слоя проверяющего теста этого сумматора относительно одиночных константных неисправностей. При этом также обеспечивается подача на входы каждого слоя конъюнкторов их проверяющих тестов и подача на входы дополнительных элементов "исключающее ИЛИ" проверяющих тестов этих элементов.
Синтез тестовой последовательности для рассматриваемой контролепригодной схемы матричного двоичного умножителя может быть осуществлен на основе комбинации формальных и эвристических методов. Сначала строится проверяющий тест для схемы одноразрядного сумматора с помощью формальных методов (например, с помощью D- и PODEM-алгоритмов), а затем на основе этого теста поэтапно проводится построение общей тестовой последовательности для схемы матричного умножителя с помощью эвристических методов. Легко видеть, что в общем случае, т.е. когда n и m – произвольные натуральные числа, контролепригодная функционально-логическая схема однотактного матричного умножителя содержит m-1 сумматоров с последовательным переносом, m слоев конъюнкторов, а также n+m-3 дополнительных двухвходовых элементов "исключающее ИЛИ". Число дополнительных входов при этом не изменится и останется равным двум.
Проверяющий тест для общего случая также содержит 5 векторов и строится следующим образом:
· на каждый вход yj подается последовательность 1, 1, 0, 1, 0, если j – нечетное число, и последовательность 1, 1, 0, 0, 1, если j – четное число (j О {1, 2, ..., n }) ;
· на каждый вход хi подается последовательность 0, 1, 1, 1, 1, если i – нечетное число, и последовательность 1, 0, 1, 1, 1, если i – четное число (i О {1, 2, ..., m });
· на каждый вход pk подается последовательность 0, 1, 0, 0, 1, если k – нечетное число, и последовательность 1, 0, 0, 0, 1, если k – четное число (k О {1, 2, ..., m-1});
· на вход u1 подается последовательность 0, 0, 1, 1, 1, а на вход u2 последовательность 1, 1, 1, 0, 0 .
Схема одноразрядного сумматора, лежащая в основе рассматриваемой контролепригодной схемы матричного двоичного умножителя, легко преобразуется в схему, отличающуюся от схемы на рис.1 только тем, что логические элементы 1, 2, 3 последней заменены логическими элементами "И–НЕ". Проверяющий тест контролепригодной схемы матричного умножителя, которая получается в результате данного преобразования схемы одноразрядного сумматора, останется прежним. При этом полученная контролепригодная схема в общем случае требует для своей реализации значительно меньших аппаратных затрат, чем более ранняя схема [1]. Дело в том, что одноразрядный сумматор, лежащий в основе этой схемы, требует для своей реализации девять двухвходовых элементов "И–НЕ", а одноразрядный сумматор, лежащий в основе полученной схемы – два двухвходовых элемента "исключающее ИЛИ" и три двухвходовых элемента "И–НЕ". В случае использования биполярной технологии (в частности, ТТЛ) логический элемент "И–НЕ" может быть реализован схемой, содержащей два биполярных транзистора и два резистора [5]. Элемент "исключающее ИЛИ" в этом случае может быть реализован схемой, содержащей всего три биполярных транзистора и два диода [6]. Другими словами, здесь схемотехническая сложность реализации элемента "исключающее ИЛИ" практически равна схемотехнической сложности реализации элемента "И–НЕ". Известна также простая реализация элемента "исключающее ИЛИ" на основе КМОП-технологии [7].
Литература
1. Takach A.R., Jha N.K. Easily testable gate – level and DCVS multipliers. – IEEE Trans. on computer aided design, 1991, v.10, №7, p.932–942.
2. Киносита К., Асада К., Карацу О. Логическое проектирование СБИС. – М.: Мир, 1988.
3. Тимошкин А.И. Контролепригодная функционально-логическая схема двоичного сумматора. – Приборы и системы управления, 1997, №1, с. 42–43.
4. Тимошкин А.И. Контролепригодная схема двоичного сумматора. – Автоматика и вычислительная техника, 2000, №3, с. 82–84.
5. Ватанабэ М., Асада К., Кани К., Оцуки Т. Проектирование СБИС. – М.: Мир, 1988.
6. А.с. 319076. Логический элемент "исключающее ИЛИ"./ В.Я. Загурский, Ю.Н. Артюх, А.К. Баумс. Изобретения. 1971. Бюллетень № 32.
7. А.с. 790340. Логический элемент "исключающее ИЛИ" на КМДП-транзисторах./ Ю.И. Грибов, Л.В. Шафранский, И.Д. Якушев. Изобретения. 1980. Бюллетень № 47.
Отзывы читателей
