Математические основы системы остаточных классов (стр. 8 из 19)
2) Малоразрядность остатков. Поэтому, ввиду малого количества возможных кодовых комбинаций появляется возможность построения табличной арифметики. При этом большинство операций превращаются в однотактовые, осуществляемые простой выборкой из таблиц. По мере совершенствования технологии производства запоминающих устройств с высокой плотностью записи информации, составляющих техническую систему табличного метода вычислений, интерес к СОК неуклонно возрастает.
3) Реализация принципа конвейерной обработки информации. Это означает, что при выполнении вычислений модульные и следующие за ним операции удаётся совместить по времени только тогда, когда очередные операции зависят от результатов текущих, ещё не закончившихся операций. Таким образом, алгоритмы модулярной арифметики обладают конвейерной структурой.
4) Высокая точность, надёжность, способность к самокоррекции. Причём в СОК можно построить непозиционные коды, обнаруживающие и исправляющие ошибки, которые являются полностью арифметическими, то есть в этих кодах информативная и контрольная части равноправны относительно любой операции. Эта особенность предоставляет возможность варьировать корректирующей способностью кода за счёт изменения точности вычислений.
Конечно, и эта система не лишена недостатков. К ним относится невозможность визуального сравнения чисел, отсутствие признаков выхода результатов за пределы диапазона, ограниченность действия системы сферой целых положительных чисел, получение во всех случаях точного результата операции, что исключает возможность непосредственного округления результата, а также трудность выполнения немодульных операций. Но они не являются непреодолимыми.
§ 2. Основные методы и алгоритмы перехода от позиционного представления к остаткам
Обработка информации в цифровых устройствах, функционирующих в СОК, осуществляется с помощью модульных и немодульных операций.
К модульным операциям относятся операции сложения, вычитания и умножения. Анализ применения арифметики СОК показывает, что их звенья имеют одинаковую структуру, типовым элементом которой является последовательность вида
, (2.1´)где
- целочисленная функция вычета 
по некоторому модулю, рi– основание СОК, 
- операция определения наименьшего вычета по модулю рi.К немодульным операциям относятся операции, при которых значение того или иного результата разряда зависит от всех или нескольких разрядов исходного числа.
Устройства, реализующие немодульные операции, довольно чётко разделяются на 2 типа.
Примером устройства первого типа является устройство свёртки, обеспечивающее вычисление
, (2.2´)где Аi – значение i-го разряда исходного числа, представленного в позиционной системе счисления (ПСС); Qi – весовой коэффициент.
Устройства свёртки широко используются в цифровых системах, функционирующих в СОК, представляющих существенную, а порой и основную часть оборудования, предназначенную для реализации ряда способов выполнения операций – перевода чисел из ПСС в СОК, деления произвольных чисел и некоторых других. Кроме того, такие устройства находят применение и в цифровых системах, функционирующих в ПСС.
Примером устройств второго типа является устройство позиционного преобразования, обеспечивающие получение характеристик, указывающих на принадлежность числа, представленного в СОК, тому или иному интервалу диапазона представимых чисел.
Математической основой устройств первого типа является определение наименьших неотрицательных вычетов, которые определяются свёртками исходного числа по каждому модулю. Для определения свёрток по каждому модулю необходимо перевести число из позиционной системы счисления в систему остаточных классов.
Перевод числа в систему остаточных классов можно осуществить методом деления. Однако из-за операции деления техническая реализация такого метода не эффективна для машинного использования, кроме того, данный метод требует применения арифметического устройства в позиционной системе счисления.
Рассмотрим метод перевода числа из позиционной системы счисления в СОК, не содержащий операции деления, называемый методом непосредственного суммирования модульных значений разрядов позиционного числа.
Пусть число X записано в позиционной системе счисления с основанием N, т. е.
или 
, (2.3´)где
.Представим степени основания Ni и коэффициенты Aiв системе остаточных классов с основаниями
, тогда 
, 
(2.4´)Подставим (2.4´) в (2.3´), получим
(2.5´)Таким образом, для образования числа Х в СОК требуется k констант, являющихся степенями
и 
констант, соответствующих значениям 
.Имея в памяти процессора массив из
констант, весь перевод может быть осуществлён процессором, работающим в СОК.Рассмотренный метод является основой широкого выбора возможных аппаратурных реализаций цифровых преобразователей ПСС – СОК, которые различаются между собой как по составу и количеству используемых элементов, так и по скорости преобразования информации.Известные в литературе цифровые преобразователи ПСС – СОК, основанные на данном методе, анализ которых позволил сделать важные выводы о том, что одним из существенных недостатков подобных преобразователей являются большие аппаратурные затраты при переводе чисел большой разрядности и низкое быстродействие.Повышенные требования, связанные с уменьшением аппаратурных средств и увеличением скорости обработки информации, привели к необходимости глубокого изучения вопросов разработки эффективных алгоритмов. Для решения этой задачи предлагаются два метода. Рассмотрим первый метод. Для этого докажем следующую теорему, которая является основой нового метода преобразования чисел из ПСС в СОК как аппаратурными, так и программными способами.
Теорема. Пусть число Х записано в позиционной системе счисления с основанием N и если
, где 
. (2.6´)а
- простое число, r – число разрядов (при j = 1, 2,…, r), то 
и 
. (2.7´)Доказательство.
, 
. Далее, подставляя значения выражений (2.6´) в выражение (2.7´), и учитывая свойства сравнений, получим 
, (2.8´)Рассмотрим второй метод, который нашёл широкое применение в литературе. Назовём его методом последовательного умножения и суммирования. Суть метода состоит в следующем. Пусть число записано в виде (2.3´). Иначе это выражение можно записать
, 
, (2.9´) 
, 
.Т. е. значение числа Х в СОК по модулю
образуется путём умножения старшего разряда на основание системы счисления N, затем суммирования полученного результата со значением следующего разряда по модулю , затем умножения полученного результата на основание N по модулю , а так последовательные умножения и суммирования по модулю производятся до тех пор, пока при суммировании не будет добавлено значение младшего разряда.