“Работа в системе остаточных классов” (стр. 1 из 3)

ГУАП

КАФЕДРА № 52

ПРЕПОДАВАТЕЛЬ

доцент				Белоголовый В. Г.
должность, уч. степень, звание		подпись, дата		инициалы, фамилия

Курсовая работа На тему:

“Работа в системе остаточных классов”

По дисциплине: Инженерно-техническая защита информации

РАБОТУ ВЫПОЛНИЛ

СТУДЕНТ ГР.	5821				Качанов С. С.
			дата		инициалы, фамилия

Санкт-Петербург
2011

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

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

Использование системы остаточных классов (СОК) и модулярных вычислений позволяет существенно увеличить скорость арифметических вычислений за счёт параллельного выполнения операций над остатками. Современная аппаратная база позволяет также заменять арифметические операции над остатками однотактными табличными выборками. Разработан вычислительный объект «нейронная сеть конечного кольца», сочетающий преимущества модулярного представления информации, и параллельность и помехоустойчивость нейронных сетей. Долгое время модулярная арифметика рассматривалась как интересный сугубо теоретический вопрос из-за сложности производства вычислительных структур для её реализации. Современное развитие технологии интегральных схем сделало возможным использование модулярной арифметики для многих областей цифровой обработки сигналов, распознавания образов и других задач, требующих интенсивных вычислений.

Система остаточных классов – непозиционная

система счисления

Пусть заданы взаимно простые положительные числа m₁, m₂,..., m_L, которые называют основаниями или модулями системы (НОД(m_i, m_j) = 1 для i≠j). Число

, называют вычислительным диапазоном получившейся числовой системы. Любое число X из кольца целых чисел по модулю M, X Z(M), имеет уникальное представление в заданной СОК /при первом использовании сокращения – дать расшифровку!/.

(1)

СОК могут быть также представлены и отрицательные числа из

диапазона {-(M - 1) / 2,…, -1, 0, 1,…, (M - 1) / 2} для нечётного M и

{- M/2,…,-1, 0, 1, (M/2) - 1} для чётного M . При этом, если X < 0 , то:

(2)

Основным достоинством СОК является то, что арифметические

операции производятся в ней независимо по каждому из модулей,

следовательно, они могут выполняться параллельно по L

вычислительным каналам:

(3)

Малоразрядность обрабатываемых остатков позволяет для повышения быстродействия арифметических операций в вычислительных каналах применять методы табличной подстановки (LUT). Более подробно модулярная арифметика в вычислительных каналах будет рассмотрена ниже, а пока же

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

Китайская теорема об остатках (КТО). Пусть даны попарно взаимно простые модули

, и число X Z (M), СОК-представление которого определяется выражением: (4)

Тогда:

(5)

Иными словами, кольцо целых чисел по модулю M, Z (M), изоморфно прямой сумме колец целых чисел по модулям

, и существует единственное

X

Z (M), , восстанавливаемое по остаткам из выражения (4) по формуле: (6)

где

= и - обратный по умножению в кольце Z(m_i) элемент для m_i:

Конечно, в Древнем Китае эта закономерность была сформулирована не в таком виде, а, вероятнее всего, в виде алгоритма решения математических загадок типа «необходимо определить число, имеющее остатками 2, 3, 2, соответственно, при делении на 3, 5, 7» (речь идёт о числе 23) В XVIII веке Эйлер продемонстрировал одно из возможных применений КТО для модулярных вычислений в СОК, а в XIX веке К.Ф.Гаусс доказал эту теорему, заложив основы современной теории СОК. Таким образом, КТО предоставляет фундаментальный метод для замены операций в кольце Z (M) на операции в нескольких независимых кольцах Z(m_i), осуществляемые параллельно (5).

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

Как было отмечено выше (3), операции сложения и умножения в СОК осуществляются параллельно по L вычислительным каналам. Обобщенная структура устройств цифровой обработки сигналов в модулярной арифметике представлена на рис. 1. Число X на входе преобразовываются из позиционной системы счисления (ПСС) в модулярное представление в СОК в базисе модулей

после чего выполняются независимые вычисления для каждого модуля m_i . На выходе происходит обратное преобразование из СОК в ПСС.

Рис. 1. Общая структура устройств цифровой обработки сигналов в СОК.

Cтруктура, изображённая на рис. 1, имеет ряд неоспоримых преимуществ при её реализации на интегральных схемах:

1. Независимость каждого канала по отдельному модулю обеспечивает значительную гибкость при планировке и топологическом проектировании кристалла.

2. Реализация таких устройств на основе ПЛИС, обладающих меньшими вентильными ресурсами, может быть легко перепланирована и размещена в несколько кристаллов.

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

4. Отсутствие специальных требований по синхронизации между отдельными каналами (за исключением синхронизации на входе и выходе) значительно облегчает трассировку цепей тактовых частот, которые будут иметь меньшую расфазировку. Это, в свою очередь, приводит к уменьшению пиковых выбросов по цепям синхронизации.

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