Введение в архитектуру компьютеров

Кодирование данных с помощью вычетов


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

Не явилась исключением и система кодирования данных с применением вычетов.

Пусть P1, P2, ..., Pn  — целые числа; Pi > 1, (Pi, Pj

) = 1, i ¹ j; M = 

; xi – наименьшие неотрицательные решения системы сравнений

A º xi (mod Pi), i = 1, 2, ..., n; A Ì [0,M).

Тогда кортеж (x1, x2, ..., xn) будем называть кодом числа A в системе в коде вычетов (СКВ) при заданных основаниях P1, P2, ..., Pn. Записывают это обычно так: A ~ (x1, x2, ..., xn). Компоненты xi называют разрядами числа A в СКВ. Идейными корнями данная система восходит к так называемой китайской теореме об остатках.

Теорема. Пусть числа Ms и Ms’ определены из условий

P1,P2,...,Pk º  MsPs, MsMs’ º 1 (mod Ps)

и пусть

x0 = M1M1’b1 + M2M2’b2 +¼+ MkMk’bk.

Тогда совокупность значений x, удовлетворяющих системе сравнения x ºb1(mod P1), x ºb2(mod P2), ¼, x ºbk(mod Pk), определяется сравнением x º x0(mod P1, ..., Pk).

Среди особенностей СКВ исследователи отмечали следующие:

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



· отсутствие переносов между разрядами при выполнении арифметических операций упрощает их выполнение;

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

Арифметические операции

Рассмотрим алгоритмы арифметических операций. Пусть необходимо выполнить операцию A Ä B = C, где A ~ (x1,x2,...,xn); B ~ (y1,y2,...,yn); C ~ (g1,g2,...,gn).


1. Если Ä  –  сложение, то

gi = | xi + yi |

Pi, т.е. gi = xi + yi - liPi,

где



2. Если Ä  –  вычитание, то

gi = | xi – yi |

Pi, т. е. gi = xi – yi + liPi,

где



3. Если Ä – умножение, то

gi = | xiyi |

Pi, т. е. gi = xiyi – liPi,

где
; [x] – наибольшее целое, не больше x.

4. Если Ä – деление, то

gi =
, где ki = 0, 1, ..., Pi –1

Иногда операцию деления A/B заменяют операцией умножения A на мультипликативную инверсию от B по модулю M, т. е. выполняют умножение:

(x1, x2, ..., xn)?(y1’, y2’, ..., yn’),

где (y1’, y2’, ..., yn’) – мультипликативная инверсия от B по модулю M. Здесь yi’ =
, т. е. yi’ – решение уравнения | yi’yi|Pi = 1 или сравнения yi’yi º 1(mod Pi). Мультипликативная инверсия существует, если (yi, Pi) = 1, для всех i =
.

Пример. Пусть P1 = 2, P2 = 3, P3 = 5. M = 30. Тогда числу A = 7 будет в данной СКВ соответствовать код (1, 1, 2), а числу 3 ~ (1, 0, 3).

Выполним арифметические операции над кодами чисел 3 и 7 в СКВ



 (1, 1, 2)



 (1, 1, 2)



(1, 1, 2)


+







x




 (1,
, 3)



 (1,
, 3)



(1,
, 3)



 (
, 1,
)



(
, 1, 4)



(1,
, 1)

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

Восстановление позиционного значения числа А по его коду (x1, x2, ..., xn) в СКВ осуществляется из соотношения

Anec=
rАM,

где Bi  – ортогональные базисы; rА  –  ранг числа А.

Ортогональные базисы представляют собой целые числа, удовлетворяющие соотношению



и ищутся среди чисел вида

, где mi Ì {1, 2, ..., Pi–1}.



Для заданной системы оснований P1, P2, ..., Pn

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

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

Исследование алгоритмов выполнения различных операций в коде вычетов показывает, что основным требованием предъявляемым к модулям системы, является однозначность кодирования данных. Известно (это доказано в теории чисел), что для выполнения этого требования необходимо, чтобы (pi, pj) = 1 для всех i ¹ j, i, j = 1,…, n, т. е. необходима взаимная простота модулей системы.

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

Итак, целое неотрицательное число A будем представлять в виде


(l1x1 + (1 – l1) (x1 – P1), …, ln xn + (1 – ln) (xn – Pn)),


(1)

где liÎí0, 1ý, xi = ÷A÷ pi. Значения li следует выбирать таким образом, чтобы форма (1) для любого целого числа A из области определения имела нулевой ранг. Назовем форму (1) формой нулевого ранга (ФНР).

Определение 1. Систему в коде вычетов, для которой любое целое AÎ[0, M) допускает ФНР, назовем безранговой СКВ (БСКВ).

Из (1) следует, что разряды чисел в этой системе могут быть положительными, отрицательными или равны нулю.

Примеры, демонстрирующие представления целых чисел в БСКВ, даны в табл. 5.2. При этом в предпоследнем столбце приведены коды чисел 0, 1, 2, … , 10, а в последнем - коды чисел  0, –1, –2, …, –10.

Из примера следует, что трансформирование положительных чисел в равные по абсолютной величине отрицательные получаются инвертированием знаков всех разрядов числа. Этот факт следует из (1) и формы восстановления позиционного значения числа по его коду в БСКВ. Суть инвертирования состоит в дополнении значения каждого разряда до соответствующего Pi, i = 1, 2, … , n, и замене знака  каждого разряда числа на противоположный.


Содержание раздела