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

Версия 16:28, 8 октября 2014

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

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

В настоящее время широкое применение получили следующие три вида преобразования:

• метод понижения разрядности числа;

• метод на основе сети прямого распространения;

• метод непосредственного суммирования.

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

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

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