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