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

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

Размещено на 13

43

Размещено на

Реферат

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

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

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

Введение

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

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

Долгое время модулярная арифметика рассматривалась как интересный сугубо теоретический вопрос из-за сложности производства вычислительных структур для её реализации. Современное развитие технологии интегральных схем сделало возможным использование модулярной арифметики для многих областей цифровой обработки сигналов, распознавания образов и других задач, требующих интенсивных вычислений [1].

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 сравнимо с а_{i i} по тому же модулю, т. е.

_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)