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

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

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

Пусть 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, и замене знака каждого разряда числа на противоположный.

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