Ранг
Справедлива следующая теорема 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) |
симметрично относительно нуля.
Пусть в классической СКВ ранги всех чисел AÎ[0,M) заключены в интервале [r1, r2], а R — множество всех целых чисел из [r1, r2].
Теорема 2. В классической СКВ минимальный элемент множества R равен нулю, а максимальный где r1 – ранг числа A = 1.
Доказательство. Из соотношения для классической СКВ следует, что . Но так как всегда A<M, а rA — целое, то можем записать Поскольку 0£xi<Pi, то rA будет минимальным при xi = 0, т.е. r1 = 0. Аналогично
Исследуем структуру множества 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) |
Доказательство теоремы 3 ведется методом индукции, причем вначале доказывается необходимость условий теоремы, а потом и их достаточность.
Для ускорения поиска оснований безранговых систем необычайно полезно получить оценки (верхние и нижние) для каждого из искомых оснований. Получим также оценки для БСКВ с единичными весами ортогональных базисов.
БСКВ, для которых m1 = m2 = … = mn, необычайно полезны в том плане, что алгоритмы выполнения операций для соответствующих модулей P1, P2, …, Pn значительно проще, чем для произвольных весов ортогональ-
ных базисов.
Утверждение 3. Пусть P1, P2, … , Pn - основания некоторой БСКВ, ортогональные базисы для которой имеют единичные веса, а Pi* = (Pi*) - соответственно нижняя (верхняя) оценка величины основания Pi. Верны следующие равенства:
; . |
известны), получим оценку
для Pi*.
1. В применении к БСКВ, указанным в утверждении 3, формула для ортогонального базиса примет вид
(5) |
. |
откуда имеем, что
.
Утверждение доказано.
Пусть 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.
Из вышеизложенного следует, что БСКВ позволяет построить сравнительно простые алгоритмы выполнения немодульных операций.
Система в коде вычетов в основном применяется в специализированных вычислительных устройствах из-за высокой сложности операций определения знака числа и сравнения чисел.