Аппаратная реализация модулярного сумматора и умножителя на базе ПЛИС

Аппаратная реализация модулярного сумматора и умножителя на базе ПЛИС

Реферат

МОДУЛЯРНАЯ АРИФМЕТИКА, МОДУЛЯРНЫЙ СУММАТОР, МОДУЛЯРНЫЙ УМНОЖИТЕЛЬ, СОК, ALTERA, QUARTUS.

Объект разработки - модулярный сумматор и умножитель на базе системы остаточных классов.

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

Введение

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

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

Долгое время модулярная арифметика рассматривалась как интересный сугубо теоретический вопрос из-за сложности производства вычислительных структур для её реализации. Современное развитие технологии интегральных схем сделало возможным использование модулярной арифметики для многих областей цифровой обработки сигналов, распознавания образов и других задач, требующих интенсивных вычислений [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 основание p_i. Очевидно, что a_i < p_i.

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

Объем диапазона представимых чисел в этом случае как легко видеть, равен

P = p₁ p₂ ... p_n.

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

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

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

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

B = (b₁, b₂, ..., b_n ), (1.3)

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

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

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

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

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

g_i ≡ а_i + b _i (mod р_i ), (1.7)

d_i ≡ а_ib _i (mod р_i ), (2.8)

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

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

d_i = а_i b _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). (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) - все они взаимно просты друг с другом, их произведение равно 50 774 191 064 678 342 417> 18 446 744 073 709 551 616. Каждый из модулей не превышает 6 бит, то есть операции сложения и умножения будут производиться над 6-битными числами.

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

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

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

Рисунок 1.1 - Общая структура обработка данных в СОК

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

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

Общая функциональная схема цифровых устройств приведена на рисунке 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) - выходной символ.

Рисунок 1.4 (б) - Автомат Мили

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

Рисунок 1.4 (в) - Автомат Мура

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

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

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

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

Рисунок 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 схема переводится в исходное состояние, при этом комбинационная схема должна снимать блокировку в прохождении импульсов.

Рисунок 1.4 (д) - Включение счетчика в структуру управляющего автомата

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

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

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

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

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

Рисунок 2.1 (а) - Модулярное суммирование с помощью большой LUT-таблицы

Для больших модулей, память LUT была бы значительного размера и другие схемы для суммирования оказываются в этом случае более предпочтительными. Следующее предложение основывается на обычном суммировании x+y и одной таблицы, содержащей все возможные значения для |x+y|_m.

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

Рисунок 2.1 (б) - Модулярное суммирование с предварительным обычным суммированием.

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

Рисунок 2.1 (в) - Модулярное суммирование без использования LUT-таблиц

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

 

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

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

(2.1)

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

 (2.2)

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

(2.3)

Рисунок 2.2 (а) - Схема модулярного умножителя по модулю m на основе закона квадратов

Существование операции деления на 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)

Таким образом, умножение двух чисел q_j и q_k можно производить вычисляя модулярную сумму соответствующих указателей i_j и i_k , а затем проводя обратное преобразование из степенного пространства в исходный вид. Необходимо специально обрабатывать случаи, когда один из операндов на входе умножителя равен нулю и в этом случае назначать нулевой результат произведения. Это происходит потому, что не определён элемент в степенном пространстве, соответствующий нулевому элементу группы Q .

Степени i_j и i_k для q_j и q_k , соответственно, могут быть заранее вычислены и помещены в LUT. Сложение степеней выполняет сумматор по модулю m_j-1. Обратное преобразование из степенного представления i_j и i_k в исходное q_j и q_k также может быть выполнено с помощью предварительно вычисленных LUT.

Рисунок 2.2 (б) - Схема модулярного умножителя, основанного на исчислении степеней (умножитель Галуа)

Рассмотрим в качестве примера работу этого умножителя на примере умножения двух чисел 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 и | i_j + i_k |₃₀ = 8. Элементу i_n = 8 в табл. 1 соответствует q_n = 20, следовательно, |14 × 28|₃₁ = 20 .

Рисунок 2.2 (в) - Схема работы 5-битного умножителя Галуа

На рис. 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 способом с ФЗ в ПК. Главным недостатком данной схемы является после то, что после перемножения чисел, результат, выходящий за пределы основания, нуждается в корректировке, т.е. выделении остатка от деления.

А*В = (59*43) mod 61 = 2537 mod 61 = (36).

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

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

Рисунок 2.2 (г) - Схема умножения чисел I способом с ФЗ в ПК

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 4 (а) - Фрагмент функциональной схемы модулярного сумматора

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

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

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

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

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

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

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

·        R - сброс.

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

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

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

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

Рисунок 4 (б) - УГО модулярного сумматора

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

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

Пример 1.

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

 

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

Проверка:

(А+В) mod 13 = (9 + 8) mod 13 = 4.

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

Рисунок 4.1 (а) - Решение Примера 1 в QUARTUS II

Пример 2.

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

000101110011

000111 111010

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

Проверка:

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

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

Рисунок 4.1 (б) - Решение Примера 2 в QUARTUS II

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

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

Рисунок 4.2 - Управляющее устройство сумматором

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

module UA

(

// {{ALTERA_ARGS_BEGIN}} DO NOT REMOVE THIS LINE!, p, Z, S

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

);

// Port Declaration

// {{ALTERA_IO_BEGIN}} DO NOT REMOVE THIS LINE!clk;[12:0] p;Z;[3:0] S;

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

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

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

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

begin(pc)

:begin=4'b0110; //s1,s2 =pc+1;

:begin(p[0]==1) and (p[1]==1) and ... (p[13]==1) begin =4'b1000; //s3=pc+1;

:begin=4'b0000;=1;S=4'b0000;

endmodule

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

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

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

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

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

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

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

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

Рисунок 5 (а) - Фрагмент функциональной схемы модулярного умножителя

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

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

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

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

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

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

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

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

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

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

·        R - сброс.

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

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

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

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

Рисунок 5 (б) - УГО модулярного умножителя

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) mod 31 = (7 * 10) mod 31 = 8.

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

Рисунок 5.1 (а) - Решение Примера 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) mod 31 = (28 * 15) mod 31 = 17.

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

Рисунок 5.1 (б) - Решение Примера 2 в QUARTUS II

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

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

Рисунок 5.2 - Управляющее устройство сумматором

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

module UA

(

// {{ALTERA_ARGS_BEGIN}} DO NOT REMOVE THIS LINE!, p, Z, S

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

);

// Port Declaration

// {{ALTERA_IO_BEGIN}} DO NOT REMOVE THIS LINE!clk;[12:0] p;Z;[5:0] S;

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

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

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

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

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

begin(pc)

:begin=6'b000110; //s1,s2 =pc+1;

:begin=6'b000000;=1;S=6'b000000;

end

endmodule

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

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

Регистры.

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

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

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

Сумматоры.

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

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

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

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

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

Рисунок 7 (а) - Алгоритмы работы сумматора

Рисунок 7 (б) - Алгоритмы работы умножителя

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

 

Рисунок 9 (а) - Структурная схема разработанного устройства

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

Рисунок 8 (б) - Структурная схема разработанного устройства в перспективе

Заключение

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

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

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

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

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

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

Библиографический список

1.      Акушский И.Я. Машинная арифметика в остаточных классах /И.Я. Акушский, Д.И. Юдицкий. - М.: Сов. Радио, 1968. - 440с.

.        Кнут Д. Сортировка Червяков Н.И. Принципы построения модулярных сумматоров и умножителей /Н.И. Червяков, И.В. Дьяченко // Сборник научных трудов. Зеленоград: 2006.

.        Осепян О.А., Исмайлов Ш-М.А. Методика генерации оптимального основания для представления чисел в системе остаточных классов.

4.      Баранов С.И. Синтез микропрограммных автоматов. - Л.: Энергия, 1979. - 231 с.

.        Голдсуорт В. Проектирование цифровых логических устройств. - М.: Машиностроение, 1985. - 288 с.

.        Закревский А.Д. Алгоритмы синтеза дискретных автоматов. - М.: Наука, 1971. - 511 с.

7.      Intel Atom [Текст]: первые конфигурируемые процессоры линейки. [Электронный ресурс]. - <#"668577.files/image042.gif">

Приложение Б

(Обязательное)

Функциональная схема модулярного сумматора

Приложение В (Обязательное)

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

Приложение Г

(Обязательное)

Функциональная схема модулярного умножителя

Приложение Д(Обязательное)

Алгоритм функционирования модулярного умножителя

Приложение Е (Обязательное)

Алгоритм самотестирования сумматора

Приложение Ж(Обязательное)

Алгоритм самотестирования умножителя

Приложение З(Необязательное)

Программный модуль, описывающий работу LUT1 - таблицы

на языке Verilog

SUBDESIGN LUT1

([5..0] : INPUT;[5..0]: OUTPUT;

)[5],q[4],q[3],q[2],q[1],q[0]=>i[5],i[4],i[3],i[2],i[1],i[0];

0,0,0,0,0,1=>0,0,0,0,0,0;

,0,0,0,1,0=>0,1,1,0,0,0;

,0,0,0,1,1=>0,0,0,0,0,1;

,0,0,1,0,0=>0,1,0,0,1,0;

,0,0,1,0,1=>0,1,0,1,0,0;

,0,0,1,1,0=>0,1,1,0,0,1;

,0,0,1,1,1=>0,1,1,1,0,0;

,0,1,0,0,0=>0,0,1,1,0,0;

,0,1,0,0,1=>0,0,0,0,1,0;

,0,1,0,1,0=>0,0,1,1,1,0;

,0,1,0,1,1=>0,1,0,1,1,1;

,0,1,1,0,0=>0,1,0,0,1,1;

,0,1,1,0,1=>0,0,1,0,1,1;

,0,1,1,1,0=>0,1,0,1,1,0;

,0,1,1,1,1=>0,1,0,1,1,1;

,1,0,0,0,0=>0,0,0,1,1,0;

,1,0,0,0,1=>0,0,0,1,1,1;

,1,0,0,1,0=>0,1,1,0,1,0;

,1,0,0,1,1=>0,0,0,1,0,0;

,1,0,1,0,0=>0,0,1,0,0,0;

,1,0,1,0,1=>0,1,1,1,0,1;

,1,0,1,1,0=>0,1,0,0,0,1;

,1,0,1,1,1=>0,1,1,0,1,1;

,1,1,0,0,0=>0,0,1,1,0,1;

,1,1,0,0,1=>0,0,1,0,1,0;

,1,1,0,1,0=>0,0,0,1,0,1;

,1,1,0,1,1=>0,0,0,0,1,1;

,1,1,1,0,0=>0,1,0,0,0,0;

,1,1,1,0,1=>0,0,1,0,0,1;

,1,1,1,1,0=>0,0,1,1,1,1;

END TABLE;

END;

Список сокращений

ФЗ - фиксированная запятая

ПЗ - плавающая запятая

СОК - система остаточных классов

ПСС - позиционная система счисления

УА - управляющий автомат

ОА - операционный автомат

УУ - управляющее устройство

ОУ - операционное устройство

LUT - Look-Up Tables

ШИВх - шина входа

ШИВх - шина выхода

УГО - условно графическое обозначение

ПК - персональный компьютер

ТЗ - техническое задание