Ранг

Форма (1)

Положительные числа в БСКВ

Отрицательные числа в БСКВ

(0,0,0)

(1,1,1)

(

,1,1)

(1,

)

(0,2,2)

(0,

,2)

(0,1,

)

(1,0,3)

(

,0,3)

(1,0,

)

(0,1,4)

(0,

,4)

(0,2,

)

(1,2,0)

(

,2,0)

(1,

,0)

(0,0,1)

(0,0,

)

(1,1,2)

(1,

,2)

(

,2,

)

(0,2,3)

(0,

,3)

(0,1,

)

(1,0,4)

(1,0,

)

(

,0,1)

(0,1,0)

(0,

,0)

Справедлива следующая теорема 1.

Теорема 1. Для того чтобы в СКВ с основаниями P1, P2, …, Pn , ортогональными базисами B1, B2, … , Bn , весами m1, m2, …, mn для любого целого AÎ[0, M) с рангом rA существовала ФНР, необходимо и достаточно, чтобы выполнялось соотношение

(2)

Доказательство. Необходимость. Пусть ( x1, x2, … , xn) — код некоторого числа AÎD в заданной СКВ. Предположим, что его можно представить в форме (1). Не нарушая общности рассуждений, будем считать, что A в форме (1) имеет вид

(x1, x2, … , xk, xk+1 – Pk+1, … , xj – Pj, xj+1, …, xn).

Тогда

Согласно формуле восстановления позиционного значения числа

A в СКВ имеем

Но это две численные формы одного и того же числа A. Значит

Откуда следует, что

Достаточность. Пусть для rA заданного числа A выполняется (2). Не

нарушая общности рассуждений, предположим, что

Тогда

т. е. число A имеет ФНР.

Теорема доказана.

Следствие 1. Если для выбранной системы модулей P1,P2, …, Pn веса ортогональных базисов m1 = m2 = … = mn = 1, то для любого AÎ[0, M) существует ФНР.

Следствие 2. Число A в ФНР будет иметь столько отрицательных разрядов, сколько слагаемых mi входит в сумму (2).

Следствие 3. Чтобы число AÎ[0,M) имело единственную ФНР, необходимо и достаточно, чтобы для указанного A сумма (2) была единственной.

Пусть D1 — область определения операций в БСКВ. Как следует из (1) D1Ì[Amin, Amax], где Amin =

Установим связь между кодированием чисел противоположных по знаку. Пусть (x1, x2, … , xn) представление числа A>0 в ФНР. По определению БСКВ

(3)

Поскольку Bi>0, то

Следовательно, представление числа –A по представлению числа A получается инвертированием знаков всех его разрядов. Отсюда следует, что множество D1

симметрично относительно нуля.

Пусть в классической СКВ ранги всех чисел AÎ[0,M) заключены в интервале [r1, r2], а R — множество всех целых чисел из [r1, r2].

Теорема 2. В классической СКВ минимальный элемент множества R равен нулю, а максимальный

где r1 – ранг числа A = 1.

Доказательство. Из соотношения

для классической СКВ следует, что

. Но так как всегда A<M, а rA — целое, то можем записать

Поскольку 0£xi<Pi, то rA будет минимальным при xi = 0, т.е. r1 = 0. Аналогично

Следствие. Мощность множества R равна r2 + 1.

Исследуем структуру множества D1. Обозначим через

соответственно подмножества положительных и отрицательных элементов множества D1. Разобъем весь интервал [Amin, Amax] на интервалы длины M и перенумеруем их ±0, ±1, ±2, … соответственно влево и вправо от нуля. Из определения (3) и симметричности множества D1 следует, что (–M,0]ÌD1 и [0,M)ÌD1.

Пусть P - множество всевозможных наборов (x1, x2, …, xn), удовлетворяющих условию –Pi <xi<Pi, i = 1, 2, …, n, для системы модулей P1,P2, … , Pn, допускающих ФНР. Пусть (x1, x2, … , xn) - произвольный набор из P, а ранги чисел AÎ[0, M) принимают все целые значения из интервала [0, r2]. Будем говорить, что заданный набор порождает во множестве D1

новый элемент, если возможно представление его в форме (1) таким образом, чтобы результаты подстановки обеих версий наборов в (3) не были равны.

Утверждение 1. Каждый набор (x1, … , xn) порождает в D1 столько новых элементов, чему равен ранг числа, соответствующего этому набору в СКВ.

Справедливость утверждения 1 вытекает непосредственно из соотношения (1) и теоремы 1.

Следствие 1. Множества

имеют одну и ту же мощность, т.

е. ê

ê= ê

ê.

Следствие 2. Мощность множества D1 меньше мощности множества целых чисел из интервала [Amin, Amax].

Обозначим через 01 множество особых точек, т. е. 01 – это такое множество, что 01Ì[Amin, Amax], но 0ËD1. Наличие 01

несколько ухудшает характеристики БСКВ. Если окажется, что существуют множества D1, для которых êD1ê = ê[Amin, Amax]ê (мы рассматриваем только целые числа из интервала), то указанный недостаток будет исключен. Вообще говоря, не совсем ясно, насколько существен данный недостаток, так как аналогичная ситуация, возникающая при округлении чисел в позиционной системе счисления (ПСС), не вызывает практических затруднений, и тщательное ее исследование в литературе не встречалось.

Вышеизложенное позволяет сформулировать следующее утверждение.

Утверждение 2. Набор (x1 x2 , … , xn) из P с рангом

не порождает в интервале с номером +N (а следовательно и –N) особую точку, если

Следствие 1. Число AÎ[0, M) не может быть порождающим ни для какого элемента из интервала с номером N>r2.

Следствие 2. Мощность множества D1 равна

, где êSi ê- мощность множества Si, элементами которого являются числа из [0, M), имеющие ранг ri.

Выясним, как построить систему модулей, ортогональные базисы для которых имели бы наперед заданные веса.

Теорема 3. Для того чтобы совокупность целых чисел P1, P2, …, Pn (Pi >1, i = 1, 2, …, n) представляла собой набор оснований системы в коде вычетов, ортогональные базисы для которых имели бы заданные веса m1, m2, … , mn, необходимо и достаточно, чтобы для Pi выполнялось соотношение

(4)

где gn+1 = -1, g1 (i = 1, 2, … , n) - целые числа, gi ¹ 0.

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

Для ускорения поиска оснований безранговых систем необычайно полезно получить оценки (верхние и нижние) для каждого из искомых оснований. Получим также оценки для БСКВ с единичными весами ортогональных базисов.

БСКВ, для которых m1 = m2 = … = mn, необычайно полезны в том плане, что алгоритмы выполнения операций для соответствующих модулей P1, P2, …, Pn значительно проще, чем для произвольных весов ортогональ-

ных базисов.

Утверждение 3. Пусть P1, P2, … , Pn - основания некоторой БСКВ, ортогональные базисы для которой имеют единичные веса, а Pi* = (Pi*) - соответственно нижняя (верхняя) оценка величины основания Pi. Верны следующие равенства:

;

Доказательство. Так как gi+1³1, то, подставив в формулу (4) выражение gi+1= 1 (в предположении, что P1, P2, … , Pi-1

известны), получим оценку

для Pi*.

1. В применении к БСКВ, указанным в утверждении 3, формула для ортогонального базиса

примет вид

(5)

где Mi= M/Pi. Откуда имеем

Не нарушая общности рассуждений, предположим, что система оснований упорядочена по возрастанию. Так как gi³1 (i = 1, 2, … , n) и P1<P2< …<Pn, то

т.е.

,

откуда имеем, что

.

Утверждение доказано.

Пусть S (n) - множество всех БСКВ с mi = 1, i = 1, 2, …, n. При нахождении БСКВ всегда необходимо находить величину g1. Используя полученные результаты, дадим его оценку для некоторого n.

Из (5) следует, что

Вместо P1*

можно взять i-е простое число. Тогда для оценки g1 необходимо подсчитать сумму

Оказалось, что минимальное n, при котором Sn ³ 2, равно 59. Следовательно, S (n) для всех n<59 имеет g1= 1. Так как для БСКВ, имеющих практическое значение, n < 59, то фактически всегда

можно считать g1

= 1.

Приведем примеры безранговых систем с количеством оснований, равным 3, 4 и 5:

при n = 3: P1 = 2, P2 = 3, P3 = 5;

       n = 4: P1 = 2, P2 = 3, P3 = 41, P4

= 7;

       n = 5: P1 = 2, P2 = 3, P3 = 7, P4

= 83, P5 = 85;

                  P1 = 2, P2 = 3, P3 = 7, P4 = 43, P5

= 1805;

                  P1

= 2, P2 = 3, P3 = 11, P4 = 17, P5 = 59.

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

Система в коде вычетов в основном применяется в специализированных вычислительных устройствах из-за высокой сложности операций определения знака числа и сравнения чисел.

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

Главная сайта