Основные методы и алгоритмы перехода от позиционного представления к остаткам
Обработка информации в цифровых устройствах, функционирующих в СОК, осуществляется с помощью модульных и немодульных операций.
К модульным операциям относятся операции сложения, вычитания и умножения. Анализ применения арифметики СОК показывает, что их звенья имеют одинаковую структуру, типовым элементом которой является последовательность вида
, (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 по модулю , а так последовательные умножения и суммирования по модулю производятся до тех пор, пока при суммировании не будет добавлено значение младшего разряда.
|
|
|
Следует отметить, что рассмотренный метод позволяет реализовать весьма экономичные, в смысле аппаратурных затрат, цифровые устройства преобразования информации.
Дата добавления: 2019-07-15; просмотров: 192; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!