Проектирование модулярного сумматора и умножителя

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

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

• Содержание
• Введение
• 1. Обзор системы остаточных классов и основные теоретические сведения
• 1.1 Основные понятия системы остаточных классов
• 1.2 Выбор оптимальных оснований СОК
• 1.3 Модулярные вычисления
• 1.4 Общая структура цифровых устройств
• 2. Разработка сумматора и умножителя
• 2.1 Выбор модели сумматора по модулю m
• 2.2 Выбор модели умножителя по модулю m
• 3. Постановка задачи
• 4. Разработкасумматора по модулю m
• 4.1 Примеры функционирования сумматора по модулю m
• 4.2 Пример управляющего устройства сумматором по модулю m
• 5. Разработкаумножителя по модулю m
• 5.1 Примеры функционирования умножителя по модулю m
• 5.2 Пример управляющего устройства умножителем по модулю m
• 6. Тестирование сумматора и умножителя
• 7. Алгоритм функционирования
• 8. Выбор ПЛИС семейства CycloneIII
• 9. Структурная схема устройства
• Заключение

Введение

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

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

1. Обзор системы остаточных классов и основные теоретические сведения

1.1 Основные понятия системы остаточных классов

Если задан ряд положительных целых чисел p₁, p₂,..., р_n, называемых в дальнейшем основаниями системы, то под системой счисления в остаточных классах принято понимать такую систему, в которой целое положительное число представляется в виде набора остатков (вычетов) по выбранным основаниям N = (a₁, a₂,..., a_n), причем образование цифр a_i осуществляется следующим процессом

a_i = N --p_i, (1.1)

где i = 1, 2,..., n.

Т.е. цифра i-го разряда a_iчисла N есть наименьший положительный остаток от деления N на p_i.

Здесь в отличие от обобщенной позиционной системы образование цифры каждого разряда проводится независимо друг от друга. Цифра i-го разряда a_i представляет собой наименьший положительный остаток от деления самого числа N, а не предыдущего частного, как это имело место в позиционной системе, на i-e основание _i. Очевидно, что a_i<p_i.

В теории чисел доказано, что если числа p_i взаимно простые между собой, то описанное цифрами a₁, a₂,..., a_n представление числа N является единственным.

Объем диапазона представимых чисел в этом случае как легко видеть, равен P = p₁ p₂... p_n.

Здесь, как и в обобщенной позиционной системе, диапазон представимых чисел растет как произведение оснований, а разрядность чисел N растет как сумма разрядностей тех же оснований.

Далее следует рассмотреть правила выполнения операций сложения и умножения в системе остаточных классов в случае, если оба числа и результат операции находятся в диапазоне [0, P). Пусть операнды А и В представлены соответственно остатками a_i и _i по основаниям p_i при i = 1, 2,..., n.

Результаты операций сложения и умножения А + В и АВ представлены соответственно остатками_i и _iпо тем же основаниям р_iт. е.

А = (а₁, а₂,..., а_n), (1.2)

B = (₁, ₂,..., _n), (1.3)

A + B = (₁, ₂,..., _n), (1.4)

AB = (₁, ₂,..., _n), (1.5)

и при этом имеют место соотношения

A < P, B < P, A + B < P, AB < P. (1.6)

Утверждается, что _iсравнимо с а_i + _i по модулю р_i, а _i сравнимо с а_ii по тому же модулю, т. е.

_i ? а_i + _i(mod р_i), (1.7)

_i ? а_{i i}(mod р_i), (2.8)

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

_i = а_i + _i - р_i, (1.9)

_i = а_{i i} - р_i. (1.10)

Необходимо охарактеризовать в общих чертах достоинства и недостатки введенной системы счисления в остаточных классах.

К достоинствам следует отнести [4]:

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

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

К основным недостаткам системы счисления в остаточных классах следует отнести:

· невозможность визуального сопоставления чисел, так как внешняя запись числа не дает представления о его величине;

· отсутствие простых признаков выхода результатов операций за пределы диапазона [0, P);

· ограниченность действия системы сферой целых положительных чисел;

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

1.2 Выбор оптимальных оснований СОК

Пусть диапазон представления чисел в СОК равен P = p₁ p₂... p_n. Поскольку желательно, чтобы P было как можно большим, проще всего принять p₁ наибольшим нечетным числом, соответствующим машинному слову, в качестве p₂ принять наибольшее нечетное число <p₁, взаимно простое с p₁, а в качестве p₃ - наибольшее нечетное число <p₂, взаимно простое как с p₁, так и с p₂, и т.д., пока не наберется столько p_j, сколько будет достаточно для образования нужного P[1].

При работе на двоичных компьютерах иногда желательно выбирать модули p_j иным образом:

p_j = 2^ej - 1. (1.11)

Другими словами, значение каждого модуля на единицу меньше очередной степени двойки. Такой выбор значения модуля p_j зачастую упрощает выполнение основных арифметических операций, т.к. выполнять вычисления с числами, представленными по модулю 2^ej- 1, несколько проще, чем с числами, представленными в обратном коде. После того, как значения модулей выбраны таким образом полезно несколько ослабить условие 0 ? a_i<p_j и потребовать только, чтобы

0 ? a_i<2^ej, (1.12)

a_i ? N (mod 2^ej - 1), (1.13)

N = (а₁, а₂,..., а_n). (1.14)

Таким образом, значение p_j = 2^ej- 1 принимается в качестве оптимального, поскольку это означает, что p_j может быть любым e_j- битовым двоичным числом[1].

Для работы с модулями вида 2^ej- 1 необходимо знать, при каких условиях число 2^e- 1 является взаимно простым с числом 2^f- 1. К счастью для этого существует очень простое правило

gcd(2^e - 1, 2^f- 1) = 2^{gcd(e, f)}- 1. (1.15)

Формула (2.15) утверждает в частности, что 2^e- 1 и 2^f- 1 взаимно просты тогда и только тогда, когда взаимно просты e и f. Формула (1.15) следует из алгоритма Евклида и тождества

(2^e - 1) (mod(2^f- 1)) = 2^{e(mod f)}- 1. (1.16)

Поэтому на компьютере с длиной слова 2³² можно выбрать p₁ = 2²⁹ - 1, p₂ = 2²⁵ - 1, p₃ = 2²³ - 1, p₄ = 2¹⁹ - 1, p₅ = 2¹⁷ - 1,p₆ = 2¹³ - 1, p₇ = 2¹¹ - 1, p₈ = 2⁷ - 1 что обеспечивает эффективность сложения, вычитания и умножения целых чисел в интервале вплоть до p₁ p₂p₃ p₄p₅p₆p₇p₈<2¹⁴⁴.

В данном курсовом проекте для представления 64-х битных чисел используется следующая система модулей: (13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61) - все они взаимнопросты друг с другом, их произведение равно

50774191064678342417>18 446 744 073 709 551 616. Каждый из модулей не превышает 6 бит, то есть операции сложения и умножения будут производиться над 6-битными числами.

1.3 Модулярные вычисления

Основным достоинством СОК является то, что арифметические операции производятся в ней независимо по каждому из модулей, следовательно, они могут выполняться параллельно по L вычислительным каналам:

Обобщенная структура устройств цифровой обработки сигналов в модулярной арифметике представлена на рисунке 1.1. Число X на входе преобразовываются из позиционной системы счисления (ПСС) в модулярное представление в СОК в базисе модулей { m₁, m₂,…, m_l }, после чего выполняются независимые вычисления для каждого модуля i m. На выходе происходит обратное преобразование из СОК в ПСС [1].

Однако в данном курсовом проекте преобразование из ПСС в СОК и обратно не выполняются по условиям ТЗ.

1.4 Общая структура цифровых устройств

Общая функциональная схема цифровых устройств приведена на рисунке 1.4 (а).

В состав любого цифрового устройства входят операционный автомат и управляющий автомат.

Операционный автомат объединяет функциональные модули, производящие непосредственную обработку поступающей информации. Операционный автомат имеет информационные входы I и входы z управления; информационные выходы D, а также выходы u, которые сигнализируют о результатах выполнения операций. Сигналы, формируемые на этих выходах, называются осведомительными сигналами или внутренними логическими условиями устройства. Операционный автомат составляется из типовых функциональных модулей, таких, как параллельные и последовательные регистры, счетчики, комбинационные сумматоры, схемы сравнения, мультиплексоры шифраторы, дешифраторы и др. В робототехнических системах и комплексах частью операционного автомата можно считать функциональные блоки, производящие определенные действия, например перемещение манипулятора, опрос датчиков и т.п. Результатом функционирования указанных блоков должно являться появление сигналов, имеющих два состояния: 0 и 1.

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

Общими управляющими входами автомата являются вход тактирования c и вход сброса r. По входу с осуществляется синхронизация работы операционного и управляющего автомата. По входу r производится установки внутренних элементов памяти автоматов в состояние, которое считается исходным (начальным).

Управляющий автомат проектируется на основании понятия абстрактного автомата. Существуют следующие схемы абстрактных автоматов.

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

w(t + 1) = L₁(u(t), q(t)); z(t) = L₂(u(t), q(t)),

где u(t) - управляющие символы; q(t) - внутреннее состояние автомата; w(t + 1) - следующее состояние автомата; z(t) - выходной символ.

В этом абстрактном автомате выдача символа z(t) происходит сразу, при старом значении внутреннего состояния q(t). Поэтому переход в новое состояние отстает по времени на один такт от изменения выходного символа. Это свойство автомата Мили поясняет рисунок 1.4 (б)

Автомат Мура, или автомат второго рода, приведен на рисунке 1.4 (в). Он имеет функцию переходов такую же, как у автомата Мили, а функцию выходов, не зависящую непосредственно от входной переменной u(t).

Система функций для автомата Мура имеет вид

w(t + 1) = L₁(u(t), q(t)); z(t) = L₂(q(t)),

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

При проектировании управляющих блоков на практике чаще применяется более простая модель Мура. Функциональная схема управляющего автомата на базе абстрактного автомата Мура приведена на рисунке 1.4 (г).

На рисунке 1.4 (г) приведены следующие обозначения:

комбинационная схема L;

элемент памяти (регистр) RG;

вектор v внешних управляющих символов;

вектор у символов, несущих информацию о состоянии устройства;

вектор u осведомительных символов, поступающих с операционного автомата;

вектор управляющих символов z, подаваемых на операционный автомат;

вектор q текущих состояний управляющего автомата;

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

r - сигнал сброса, переводящий управляющий автомат в исходное состояние;

с - сигнал тактирования управляющего автомата.

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

Комбинационная схема автомата (элемент L) объединяет все логические элементы, участвующие в формировании вектора управления z выходного вектора у и вектора возбуждения w на основании вектора осведомительных символов u, вектора внешнего управления v и вектора текущих состояний автомата q.

Если количество состояний цифрового управляющего устройства заранее известно, в управляющий автомат может быть включен счетчик состояний в соответствии с функциональной схемой, приведенной на рисунке 1.4 (д). Указанный счетчик может быть реализован и в виде части регистра RG, однако в этом случае существенно возрастает сложность структуры логического блока L. При включении счетчика в структуру управляющего автомата используется комбинационная схема Lcu, назначение которой - обеспечить прохождение тактирующих импульсов с на выход с' в процессе отработки управляющим автоматом его программы и заблокировать прохождение импульсов после отработки программы. По входу r схема переводится в исходное состояние, при этом комбинационная схема должна снимать блокировку в прохождении импульсов.

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

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

2. Разработка сумматора и умножителя

2.1 Выбор модели сумматора по модулю m

модулярный сумматор умножитель

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

Первая из них вычисляет модульную сумму |x+y|_mс помощью таблицы размером n*2²ⁿ, n=[log₂m]. Для двух соответствующих элементов просто выбирается ответ из большой таблицы. Это решение очень хорошо подходит для случаев, когда длина слова мала, например, n < 5 [1].

Для больших модулей, память LUT была бы значительного размера и другие схемы для суммирования оказываются в этом случае более предпочтительными. Следующее предложение основывается на обычном суммировании x+y и одной таблицы, содержащей все возможные значения для |x+y|_m. При этом существенно сокращается размер подстановочной таблицы с n*2²ⁿдо n*2ⁿ⁺¹, что даёт возможность расширять набор модулей в случае необходимости большего динамического диапазона или избыточных модульных каналов для коррекции ошибок [1].

Третья схема суммирования является самой распространённой и наиболее предпочтительной в большинстве случаев. В этой схеме используется два сумматора и мультиплексор для выборарезультата в соответствии с выражением:

В данном курсовом проекте используется последняя схема суммирования без использования LUT-таблиц ввиду простоты реализации и минимальных аппаратурных затрат.

2.2 Выбор модели умножителя по модулю m

Умножители на основе закона квадратов (рис. 2.2 (а)) вычисляют модулярное произведение|x*y|_mс помощью следующегоравенства (закон квадратов):

(2.1)

где 0 ? x, y <m. Модулярное умножение на основе (3.1) можнозаписать следующим образом:

(2.2)

и произведение|x*y|_mможно вычислять по формуле:

(2.3)

Существование операции деления на 2 ставит под угрозу целочисленность промежуточных вычислений и, соответственно, правильность результата после использования таблиц подстановок. Более того, существование обратного по умножению по модулю mдля 2 элемента,, гарантируется только в случае, если 2 не делит m (т.е. m - нечётно). Тэйлор в работе [11] привёл доказательство теоремы, показав, что даже если при вычислении (2.2) будут промежуточные дроби, они взаимно уничтожатся.

Умножители, основанный на арифметике указателей [12, 13] является сравнимой альтернативой по сложности и скорости умножителям, основанным на законе квадратов. Их использование ограничено простыми модулями и основывается на осуществлении преобразования в степенную форму (так называемое степенное исчисление), в котором умножение может более быстро осуществляться посредством операции суммирования.

Метод работы этого умножителя связан с математическими свойствами полей Галуа [14, 15], обозначаемых GF(p), где p -простое число. Все ненулевые элементы поля Галуа могут быть получены путём многократного возведения в степень примитивного элемента - порождающего поле GF(p) элемента g_j. Это свойство полей Галуа можно использовать для умножения в GF(m_j)благодаря использованию изоморфизма между мультипликативной по модулю m_j группой Q = {1,2,…,m -1}, и аддитивной по модулю (m_j-1)- группой I ={0,1,…,m - 2}. Этот изоморфизм может быть установлен следующим образом:

(2.4)

и умножение над полем GF(m) может производиться по формуле:

(2.5)

Рассмотрим в качестве примера работу этого умножителя на примере умножения двух чисел 14 и 28 по модулю 31.

Так как 31 - простое число, существует порождающий элемент g, дающий возможность ассоциировать каждый элемент мультипликативной группы

Q = {1,2,…,31} с элементом аддитивной группы I ={0,1,…,30}. Соответствие задаётся выражением В табл.1 рассчитано соответствие между элементами группы Q и соответствующей степенью из аддитивной группы I. Эта таблица в сущности и представляет собой содержание LUT размером 2⁵?5прямого и обратного преобразования в умножителе, изображенном на рис. 2.2 (б).

Рассмотрим работу умножителя Галуа (рис. 2.2 (б), рис. 2.2 (в), табл. 1) на примере умножения |14 ? 28 |₃₁. Итак, q_j= 14 и q_k= 28, а произведение |q_j ? q_k |₃₁получается посредством суммирования соответствующих им элементов i_jи i_k, выбранных из табл. 1.Таким образом, указатели оказываются i_j= 22 и i_k= 16 и

На рис. 2.2 (в) показано, каким образом происходит умножение чисел 14и 28 по модулю 31 по схеме, изображённой на рис. 2.2 (б). Для простоты две таблицы LUT1 и LUT2 объединены в одну и представляют собой таблицы, переводящие умножаемые числа в степенное представление по табл. 1, а в качестве сумматора выступает простой модулярный сумматор, изображённый на рис. 2.1 (а). LUT3выполняет сложение по модулю 30, а LUT4 переводит результат из степенного представления обратно в первоначальный. LUT4представляет собой табл. 1, только отсортированную по i_n. На рис. 2.2 (и) ADDR на входе таблицы и [ADDR] на выходе показывают, что значение, поступившее на вход таблицы, рассматривается в качестве линейного адреса элемента, который будет выдан на выход таблицы, т.е. [ADDR] - это содержимое ячейки таблицы по адресу ADDR.

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

Так же, нельзя исключать использования стандартных схем умножения чисел с фиксированной запятой. Их применение целесообразно при малой разрядности операндов. На рис. 2.2 (г) приведена схема умножения чисел I способом с ФЗ в ПК. Главным недостатком данной схемы является после то, что после перемножения чисел, результат, выходящий за пределы основания, нуждается в корректировке, т.е. выделении остатка от деления.

Пример: А = 120 = (59), В = 104 = (43), p = 61.

А*В= (59*43) mod61 = 2537 mod61 = (36).

В данном примере для получения произведения необходимо было бы 41 раз вычесть основание 61 из 2537 или разделить 2537 на 61, что впоследствии привело бы к значительному усложнению схемы.

Исходя из недостатков первой и третьей схем, в данном курсовом проекте используется вторая - схема умножителя Галуа.

3. Постановка задачи

Реализовать модулярный сумматор и умножитель на базе ПЛИС со следующими характеристиками:

· формат данных - 64-разрядные целочисленные данные;

· входные данные поступают в СОК в формате вектора состоящего из тринадцати 6-разрядных значений, соответственно заданным основаниям;

· выходные данные также находятся в СОК;

· подключение к ПК черезUSB 2.0;

· сумматор и умножитель разместить на отдельных/одной ПЛИСфирмы Altera;

· питание ПЛИС 1,2 В, 5,0 В;

· разработать алгоритмы функционирования сумматора и умножителя;

· разработать алгоритмы самотестирования сумматора и умножителя;

· произвести проверку работоспособности разрабатываемого устройства на контрольных примерах.

4. Разработка сумматора по модулю m

Модулярный сумматор должен содержать:

· два 78-разрядных входных регистра для приёма операндов с ШИВх,

· 78-разрядный регистр для выдачи результата на ШИВых,

· двадцать шесть 7-разрядных сумматоров для сложения и корректировки операндов,

· тринадцать 7-разрядных мультиплексора.

Операнды поступают в сумматор по 77-разрядной ШИВх и записываются в соответствующие регистры. На первом сумматоре происходит сложение операндов, а на втором - коррекция результата. Управление мультиплексором т.е. выбор результата зависит от единицы переноса, возникающая на втором сумматоре, если таковая возникла - снимается результат с 1 плеча и записывается в выходной регистр.

На рис. 4 (а) представлен фрагмент функциональной схемы сумматора для основания 13.

На рис. 4 (б) изображён модулярный сумматор.

Назначение входных и выходных сигналов:

1) управляющие входы:

· S1 - запись данных по порту А,

· S2 - запись данных по порту В,

· S3 - выдача результата,

· CLK - системный синхроимпульс (вырабатывается тактовым генератором),

· R - сброс.

2) входы данных:

· А [77..0] - порт А для входных 78-разрядных данных,

· В [77..0] - порт В для входных 78-разрядных данных,

· Q [77..0] - порт Q для выходных 78-разрядных данные.

4.1 Примеры функционирования сумматора по модулю m

Произведём проверку работоспособности сумматора суммированием чисел по модулю 13.

Пример 1.

Дано: А = 9 = 001001₂, В = 8 = 001000₂, Корректировка 51 = 110011₂.

001001 010001

001000 110011

010001 1000100

При возникновении единицы переноса результат снимается с плеча мультиплексора data1x[6..0] и он равен 000100₂ = 4.

Проверка: (А+В) mod 13 = (9+8) mod 13 = 4.

На рис. 4.1 (а) представлена временная диаграмма решения данного примера в QUARTUS II.

Пример 2.

Дано: А = 2 = 000010₂, В = 5 = 000101₂, Корректировка 51 = 110011₂

000010 000111

000101 110011

000111 111010

Единицы переноса нет - результат снимается с плеча мультиплексора data0x[6..0] и он равен 000111₂ = 7.

Проверка:

(А+В) mod 13 = (2+5) mod 13 = 7.

На рис. 4.1 (б) представлена временная диаграмма решения данного примера в QUARTUS II.

4.2 Пример управляющего устройства сумматором по модулю m

Пример управляющего устройства сумматором приведён на рисунке 4.2. На входы поступают осведомительные сигналы p[12..0], а на выходе появляются соответствующие управляющие сигналы S[3..0]. Сигнал Z - обозначает окончание операции.

Пример микропрограммы:

module UA

(

// {{ALTERA_ARGS_BEGIN}} DO NOT REMOVE THIS LINE!

clk, p, Z, S

// {{ALTERA_ARGS_END}} DO NOT REMOVE THIS LINE!

);

// Port Declaration

// {{ALTERA_IO_BEGIN}} DO NOT REMOVE THIS LINE!

input clk;

input [12:0] p;

output Z;

output [3:0] S;

// {{ALTERA_IO_END}} DO NOT REMOVE THIS LINE!

integerpc=1; //Объявление счетчика тактов, переменная типа integer

reg [3:0] S; //Объявление регистра для хранения массива управляющих сигналов

regZ=0; //Объявление регистра для хранения признака окончания операции

always @(posedgeclk) //Данная функция срабатывает при положительном (pos) перепаде (edge) сигнала clk (по фронту)

begin

case (pc)

1:begin

S=4'b0110; //s1,s2

pc=pc+1;

end

2:begin

if (p[0]==1) and (p[1]==1) and... (p[13]==1) begin

S=4'b1000; //s3

pc=pc+1;

end

3:begin

S=4'b0000;

Z=1;

end

default S=4'b0000;

endcase

end

endmodule

5. Разработка умножителя по модулю m

Модулярный умножитель должен содержать:

· два 78-разрядных входных регистра для приёма операндов с ШИВх,

· 78-разрядный регистр для выдачи результата на ШИВых,

· тринадцать 7-разрядных модулярных сумматоров для сложения и корректировки операндов,

· тридцать девять 6-разрядных LUT-таблиц.

Операнды поступают в умножитель по 78-разрядной ШИВх и записываются в соответствующие регистры. Производится выборка значений из таблиц LUT1и LUT2. Таблица LUT3 была заменена на 6-разрядный сумматор из пункта 3.3 данного курсового проекта. Это решение было принято в связи с уменьшением временных затрат на вычисления значений данной таблицы и простотой реализации сумматора. Его работа описана в пункте 4. Результат сложения подаётся в таблицу LUT4, записывается в выходной 78-разрядный регистр с последующей выдачей на ШИВых.Содержание таблиц LUT1, LUT2, LUT4 помещено в приложение.

На рис. 5 (а) представлен фрагмент функциональной схемы умножителя для основания 31.

На рис. 5 (б) изображён модулярный умножитель.

Назначение входных и выходных сигналов:

1) управляющие входы:

· Y1 - запись данных по порту С,

· Y2 - запись данных по порту D,

· Y3 - выдача результата умножения,

· S1 - запись данных в сумматор по порту А,

· S2 - запись данных в сумматор по порту В,

· S3 - выдача результата сложения,

· CLK - системный синхроимпульс (вырабатывается тактовым генератором),

· R - сброс.

2) входы данных:

· С [77..0] - порт D для входных 78-разрядных данных,

· D [77..0] - порт C для входных 78-разрядных данных,

· Out [77..0] - порт Out для выходных 78-разрядных данные.

5.1 Примеры функционирования умножителя по модулю m

Произведём проверку работоспособности умножителя умножением чисел по модулю 13.

Пример 1.

Дано: С = 7 = 000111₂, D = 10 = 001010₂.

Значению 000111₂ = 7 в таблице LUT1 соответствует 011100₂ = 28, а значению 001010₂ = 10 - 001110₂ = 14 в таблице LUT2. При сложении 28 и 14 по модулю 30 получаем результат 12. Данному числу в таблице LUT4 соответствует значение 001000₂ = 8.

Проверка:

(С * D) mod31 = (7*10) mod 31 = 8.

На рис. 5.1 (а) представлена временная диаграмма решения данного примера в QUARTUS II.

Пример 2.

Дано: С = 28 = 011100₂, D = 15 = 001111₂.

Значению 011100₂ = 28 в таблице LUT1 соответствует 010000₂ = 16, а значению 001111₂ = 15 - 010101₂ = 21 в таблице LUT2. При сложении 16 и 21 по модулю 30 получаем результат 7. Данному числу в таблице LUT4 соответствует значение 010001₂ = 17.

Проверка:

(С * D) mod31 = (28*15) mod 31 = 17.

На рис. 5.1 (б) представлена временная диаграмма решения данного примера в QUARTUS II.

5.2 Пример управляющего устройства умножителем по модулю m

Пример управляющего устройства умножителем приведён на рисунке 5.2. На входы поступают осведомительные сигналы p[12..0], а на выходе появляются соответствующие управляющие сигналы S[5..0]. Сигнал Z - обозначает окончание операции.

Пример микропрограммы:

module UA

(

// {{ALTERA_ARGS_BEGIN}} DO NOT REMOVE THIS LINE!

clk, p, Z, S

// {{ALTERA_ARGS_END}} DO NOT REMOVE THIS LINE!

);

// Port Declaration

// {{ALTERA_IO_BEGIN}} DO NOT REMOVE THIS LINE!

input clk;

input [12:0] p;

output Z;

output [5:0] S;

// {{ALTERA_IO_END}} DO NOT REMOVE THIS LINE!

integerpc=1; //Объявление счетчика тактов, переменная типа integer

reg [5:0] S; //Объявление регистра для хранения массива управляющих сигналов

regZ=0; //Объявление регистра для хранения признака окончания операции

always @(posedgeclk) //Данная функция срабатывает при положительном (pos) перепаде (edge) сигнала clk (по фронту)

begin

case (pc)

1:begin

S=6'b000110; //s1,s2

pc=pc+1;

end

2:begin

if (p[0]==1) and (p[1]==1) and... (p[13]==1) begin

S=6'b011000; //s3,s4

pc=pc+1;

end

3:begin

S=6'b000000;

Z=1;

end

default S=6'b000000;

endcase

end

endmodule

6. Тестирование сумматора и умножителя

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

Регистры.

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

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

Прерывание по таймеру в ЦП.Производится запись и чтение информации в течение определённого времени, выставленного таймером в ЦП. Проверяется долговременная работоспособность.

Сумматоры.

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

Прерывание по таймеру в ЦП.Производится запись и чтение информации в течение определённого времени, выставленного таймером в ЦП. Проверяется долговременная работоспособность.

Тестирующие модули сумматора и умножителя приведены в Приложениях Е и Ж.

7. Алгоритм функционирования

Алгоритмы функционирования разработанного сумматора и умножителя представлены на рисунках 7 (а) и рисунке 7 (б) соответственно.

8. Выбор ПЛИС семейства CycloneIII

По расчетам на разрабатываемый модулярный сумматор требуется не более 80000 логических элементов (ЛЭ), а на умножитель 75000. После изучения семейства CycloneIII было принято решение использовать ПЛИС CycloneIIIEP3C80. Ниже представлены основные характеристики данной ПЛИС [9]:

· количество ЛЭ - 81262;

· количество портов ввода/вывода -296;

· количество умножителей 18х18 - 488;

· число блоков памяти - 305.

Степень использования контактов данной ПЛИС составляет 90% для сумматора и 95% для умножителя. Степень использования ЛЭ данной ПЛИС составляет 98% для сумматора и 92% для умножителя.

Так же, возможно поместить оба устройства на одну ПЛИС, но тем самым снизив отказоустойчивость. Данной ПЛИС может служить EP3C120 при условии сокращения числа логических элементов (например, выходных регистров).

· количество ЛЭ - 119088;

· количество портов ввода/вывода-532;

· количество умножителей 18х18 - 576;

· число блоков памяти - 432.

9. Структурная схема устройства

Структурная схема разработанного устройства включает в себя устройство управления (УУ), Сумматор/умножитель. Функции сопряжения с USBи работой с узлом управления берут на себя устройства, входящие в состав ПЛИС фирмы Altera. Структурная схема данного устройства представлена на рисунке 9 (а).

Для увеличения производительности, ускорения передачи информации между ПК и устройством, предлагается использовать PCI-интерфейс. USB - порт оставить в составе устройства для его настройки и отладки. Схема данного устройства представлена на рисунке 9 (б).

Заключение

В результате выполнения курсового проекта были разработаны модулярный сумматор и умножитель, удовлетворяющий техническому заданию. В ходе курсового проектирования были получены навыки работы в AlteraQuartusIIv10.1. Разработанный проект был успешно протестирован на контрольных примерах.

В случай продолжения разработки следует определить основные этапы усовершенствования:

· увеличение числа операций в СОК;

· использование более скоростного интерфейса взаимодействия вычислительного устройства с компьютером (например,PCI);

· введение переменного числа оснований с возможностью выбора их количества и значений программистом. Это позволит более эффективно использовать аппаратуру при решении конкретной задачи;

· работа с числами с ПЗ.

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