Система остаточных классов реферат

Обновлено: 02.07.2024

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

Белоголовый В. Г.

должность, уч. степень, звание

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

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

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

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

Похожие работы

2014-2022 © "РефератКо"
электронная библиотека студента.
Банк рефератов, все рефераты скачать бесплатно и без регистрации.

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

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

1. Горденко Д.В., Павлюк Д.Н., Шапошников Е.В., Кондрашов А.В., Горбачев А.В. Обнаружение ошибок с самоконтролем в модулярной арифметике // Вестник СевКавГТИ. – 2015. – Т. 1, № 1 (20). – С. 202–207.

2. Горденко Д.В., Резеньков Д.Н. Сравнительный анализ метода контроля арифметических операций в системе остаточных классов. // Современные проблемы науки и образования. – 2014. – № 3. – С. 148.

3. Горденко Д.В., Токарева Г.В. Нейронная сеть для преобразования чисел, представленных в позиционном коде в систему остаточных классов. // В сборнике: Информационные системы и технологии как фактор развития экономики региона. – 2013. – С. 60–63.

4. Горденко Д.В., Горденко Н.В. Нейронная реализация локализации ошибок в модулярном коде. // Исследования в области естественных наук. – 2013. – № 7 (19). – С. 1.

5. Червяков Н.И., Горденко Д.В., Сивоплясов Д.В., Ткачук Р.В. Модулярный сопроцессор для обработки биометрической информации. // Известия ЮФУ. Технические науки. – 2003. – № 4 (33). – С. 240–242.

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

Рассмотрим некоторые свойства остаточной арифметики в сравнении с традиционными системами счисления. Для проведения сравнения рассмотрим свойства десятичной системы. Как будет видно далее, система остаточных чисел не имеет всех этих свойств.

Любое положительное целое число х может быть записано в виде

x = + (αn10n + αn-110n-1 + … + α110 + α0), (1)

где αi – это целые десятичные цифры в интервале [0, 9]. Очевидно, что десятичная система счисления не имеет пределов, т.е. любое целое число, невзирая на его значение, может быть выражено в системе. Более того, это уникальное представление, в котором каждое целое число имеет только одно представление. Однако, в отличие от других систем счисления, десятичное представление является безызбыточным, т.е. каждое сочетание αi цифр представляет число и два разных набора αi, не относящихся к одному и тому же числу.

Десятичная система имеет представление весового числа; каждая цифра αi умножается на постоянную величину в определяемой связи. В этом случае постоянная величина или вес – это 10i, а основания степени есть основание системы, то есть 10. Все веса, используемые в этой системе, – это степени одного и того же основания. Такие числовые системы называются системами с фиксированным основанием.

Введем некоторые отличительные свойства систем счисления.

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

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

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

Также десятичная система, представленная в двоичном коде, как определено следующим уравнением, является избыточной:

x = (αn323 + αn222 + αn121 + αn020)10n + …+

+ (α0323 + α0222 + α0121 + α0020)100, (2)

где αi,j или 0 или 1 и для всех i. Избыточность проистекает из факта, что 6 из 16 двоичных комбинаций в каждой десятичной позиции не возникло.

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

, (3)

где αi – набор допустимых цифр. Если значения для wi это последовательные степени одного числа, то система счисления имеет фиксированное основание, например, основание 10 – для десятичной системы, основание 2 – для двоичной системы.

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

Говорят, что целое число делится на натуральное число с остатком, если имеется пара целых чисел и , таких, что и . называется делимым, - делителем, - неполным частным, - остатком.

Для целых чисел:

Определение

Говорят, что целое число делится на целое число с остатком, если имеется пара целых чисел и , таких, что и .

48 при делении на 5 даёт остаток 3, т.к. , , -48 при делении на 5 даёт остаток 2, т.к. , .

Сравнения и их основные свойства

Возьмём произвольное фиксированное натуральное число и будем рассматривать остатки при делении на различных целых чисел.

При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.

Определение

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

Символически сравнимость записывается в виде формулы (сравнения):

$a \equiv b \pmod<m> $

Число называется модулем сравнения.

Определение

Целые числа и называются сравнимыми по модулю , если остатки от деления этих чисел на равны.

Отношение сравнимости по модулю обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности.

Отнесём все целые числа, дающие при делении на один и тот же остаток в один класс, поэтому получится различных классов по модулю . Множество всех чисел сравнимых с по модулю называется классом вычетов по модулю .

Подробнее о свойствах сравнений и классах вычетов смотри Сравнения и их основные свойства

Теорема о делении с остатком. Алгоритм Евклида

Теорема о делении с остатком

Для любых целых и , , существует единственный набор целых чисел и , что и , где — модуль числа .

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

Алгоритм Евклида для целых чисел

Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел

определена тем, что каждое — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

= r_ q_ + r_k" />
= r_q_+ r_n" />
= r_n q_n" />

Тогда НОД , наибольший общий делитель и , равен , последнему ненулевому члену этой последовательности.

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

Корректность этого алгоритма вытекает из следующих двух утверждений:

Китайская теорема об остатках

Фундаментальным положением, лежащим в основе модулярного представления чисел, является китайская теорема об остатках (Chinese Remainder Theorem - CRT). Например, эта теорема гарантирует, что при правильном выборе модулей СОК каждое число из динамического диапазона имеет в СОК единственное представление, и по этому представлению можно определить представленное число. В своей первоначальной формулировке эта теорема была доказана китайским математиком Сунь-Цзы приблизительно в 100 г. н.э. В современной формулировке теорема звучит так:

Пусть - попарно взаимно простые числа, большие 1, и пусть . Тогда существует единственное неотрицательное решение по модулю следующей системы сравнений:

" />
, " />
, , " />
.

Другими словами, отображение, которое каждому целому числу , , ставит в соответствие кортеж , где , i = 1, \ldots k" />
является биекцией кольца на декартово произведение \times Z_ \times \ldots \times Z_" />
колец , Z_, \ldots, Z_" />
.

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

Теоремы Эйлера и Ферма, их роль в вычислении мультипликативных обратных элементов по заданному модулю

Определение

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

Т.е. это количество таких натуральных чисел из отрезка , наибольший общий делитель (НОД) которых с равен единице.

Tеоремa Эйлера

Если и взаимно просты, то \equiv 1 \pmod p" />
, где - функция Эйлера.

Частным случаем теоремы Эйлера является малая теорема Ферма.

Малая теорема Ферма

Если - простое число и - произвольное целое число, не делящееся на , то \equiv 1 \pmod p " />
.

Числа Мерсенна, Ферма и операции над ними

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

Определение

Числа Мерсенна — числа вида , где — натуральное число. Названы в честь французского математика Марена Мерсенна.

Иногда числами Мерсенна называют только числа с нечетными или простыми индексами n.

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

При простых значениях n = p число может оказаться простым, но может быть составным. Например, при мы получаем простые числа Мерсенна: , а при числа - составные.

Определение

, где n — неотрицательное целое число.

При числа Ферма простые: . Известно, что для числа являются составными. На 2014 г. не найдено ни одного простого числа такого вида для .

Все числа Мерсенна и Ферма – взаимно простые. Кроме того, для модулей СОК вида , легко реализуется преобразование и арифметические операции. Поэтому эффективно выбирать модули СОК в виде чисел Мерсенна и Ферма.

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

Представление чисел в виде набора остатков от деления на выбранные натуральные модули - основания системы называется системой остаточных классов - СОК (residue number system - RNS) или модулярной системой счисления - МСС (modular system).

Выбор СОК как системы счисления

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

К любой кодовой системе применимы следующие требования:

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

Системы счисления подразделяются на позиционные, непозиционные и смешанные. (Система счисления)

В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. Обычно используется b-ричная система счисления, которая определяется целым числом b>1, называемым основанием системы счисления.

Смешанная система счисления является обобщением b-ричной системы счисления и также зачастую относится к позиционным системам счисления. Смотри Полиадический код.

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

Всякая вычислительная структура тесно связана с системой счисления, в которой она работает.

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

В качестве такой непозиционной системы удобна система остаточных классов (СОК).

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

Модульные операции, которые могут быть выполнены параллельно и независимо над отдельными цифрами чисел: сложение, умножение, вычитание без знака.

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

Основным достоинством системы остаточных классов является сравнительная простота выполнения модульных операций, недостатком - большая трудоемкость немодульных операций.

Модульные операции над числами в системе остаточных классов

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

Основные методы и алгоритмы перехода от позиционного представления к остаткам

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

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

Восстановление позиционного представления числа по его остаткам

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

Метод ортогональных базисов

Метод восстановления числа по его остаткам был найден еще в Китае две тысячи лет назад. Основой этого метода является теорема, названная Китайской теоремой об остатках (КТО).

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

Перевод числа из СОК в обобщенную позиционную систему (ОПС)

Еще один метод определения величины числа связан с переводом числа из системы остаточных классов в ОПС. Для того, чтобы рассмотреть этот метод, выявим связь между представлением некоторого числа в этих двух системах.

Пусть по-прежнему СОК задается основаниями и _1, _2, \ldots, _n)" />
- число в этой системе. И пусть являются также основаниями ОПС, тогда число можно представить в виде

$A = a_n\cdot p_1\cdot p_2\cdot \ldots \cdot p_ + a_\cdot p_1\cdot p_2\cdot \ldots \cdot p_ + \ldots + a_3\cdot p_1\cdot p_2 + a_2\cdot p_1 + a_1$

где – коэффициенты (цифры) ОПС.

Очевидно, что диапазоны чисел, представимых в СОК и ОПС совпадают, т.е. можно говорить о наличии взаимно однозначного соответствия между множеством представлений чисел в СОК и ОПС.

Это равенство можно переписать в следующем виде:

$A = a_1 + p_1(a_2 + p_2(a_3 + \ldots +p_<n-2> (a_ + p_ a_n) \ldots ))$
,

откуда следует, что цифры ОПС могут быть получены из соотношений:

\right] \cdot p_1 = A - A_1\cdot p_1" />
, где \right]" />
, \right] \cdot p_2 = A_1 - A_2\cdot p_2" />
, где \right]" />
,

$\ldots$

- \left[ \frac>\right] \cdot p_n = A_ - A_n\cdot p_n" />
, где >\right]" />
.

Причем при определении цифр по этим формулам все вычисления можно вести в СОК.

Интервальные методы перевода

Достаточно эффективными методами перевода чисел из СОК в ПСС являются интервальные методы, основанные на интервальных характеристиках чисел. Одна из таких характеристик – номер интервала.

Расширение диапазона представления чисел

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

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

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

Бухштаб А. А. Теория чисел – М: Наука, 1975 г.

Айерленд К. Классическое введение в современную теорию чисел. М: Мир, 1987.

Акушинский И. Л., Юдицкий Д. И. Машинная арифметика в остаточных классах. – М. Советское радио, 1968.

Амербаев В. М. Теоретические основы мащинной арифметики, - Алма –Ата: Наука, 1976.

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

Определение. Если задан ряд положительных целых чисел p₁, p₂, . p_n, называемых в дальнейшем основаниями системы, то под системой счисления в остаточных классах будем понимать такую систему, в которой целое положительное число представляется в виде набора остатков ( вычетов ) по выбранным основаниям

причем образование цифр a_i осуществляется следующим образом:

a_i = N - , для i = 1, 2, . n, (5)

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

Таким образом, в СОK в отличие от обобщенной позиционной системы счисления образование цифры каждого разряда производится независимо друг от друга. Очевидно, что a_i 2 + (a_i l_i +b_i k_i)p_i + a_i b_i,

Пример. Сложить числа А = 23 и В = 48 в СОК.

Пусть основаниями системы являются p₁ = 3, p₂ = 5, p₃ = 7.

По выбранным основаниям числа А и В в СОК примут вид:

получим А + В = (2, 1, 1).

Легко проверить, что 23 + 48 = 71, а число 71 = (2, 1, 1) в СОК.

Пример. Умножить число А=14 на В=8 в СОК.

В соответствии с (4) получим:

g₁ = 4 - = 4 - 3 = 1,

g₂ = 12 - = 12 - 2∙5 = 2,

g₃ = 1 - = 1 - 0.7 = 1.

Таким образом, А∙В = 122 = (1, 2, 1).

Охарактеризуем в общих чертах достоинства и недостатки введенной СОK.

Достоинства:

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

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

Недостатки:

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

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

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

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

Читайте также: