Математические основы системы остаточных классов
Расширение системы оснований является одной из основных немодульных операций в СОК. Выполнение этой операции бывает необходимо при выполнении операции деления чисел, при вычислении позиционных характеристик, при обнаружении переполнения при выполнении сложения или умножения чисел.
Задачу расширения системы оснований можно сформулировать следующим образом: найти остаточное представление числа по новому основанию (новым основаниям), если известно представление числа по другим основаниям остатки от деления на другие числа.
Один из путей расширения системы оснований состоит в переводе числа в позиционную систему счисления и вычисления остатка от деления на новый модуль. Этот путь не является рациональным с точки зрения числа операций.
Другой метод
расширения
системы оснований
позволяет
определить
цифру числа
по новому основанию,
базируясь на
таких позиционных
характеристиках
числа, как ранг
числа, след
числа. Пусть
вновь задана
система оснований
с диапазоном
Р, ортогональными
базисами
,
веса которых
.
По определению,
.
Пусть в этой
системе задано
число
.
Расширим систему
оснований,
добавляя основание
,
тогда диапазон
системы станет
,
ортогональные
базисы системы
,
их веса
,
причём
.
Задача состоит
в определении
цифры
числа
по основанию
называют цифру
,
при которой
число
находится в
интервале
,
и что число
,
то определение
цифры по основанию
сводится к
определению
минимального
следа числа
А в расширенной
системе оснований.
Чтобы получить
формулы для
цифры
запишем выражение
для числа А
в основной
и расширенной
системах:
и
,
где
и
- ранги числа
А в основной
и расширенной
системах.
Приравнивая
правые части
этих выражений,
определяем
:

, или обозначая
через
целое число
,
а через
величину
,
получаем
.
Наконец, представляя
в виде
,
где k, q
– целые неотрицательные
числа и
,
получаем
,
или
.
(4.1ґ)
Формула (4.1ґ) и есть формула расширения диапазона чисел.
Для практической реализации этой формулы поступают следующим образом:
Вычисляют параметры основной и расширенной систем (ортогональные базисы, их веса, минимальные псевдоортогональные числа с их рангами и кратности).
Конструируют число
из минимальных
псевдоортогональных
чисел
,
,
с рангами
,
которые однозначно
определяются
выбранной
системой оснований
.
В результате,
получают число
,
где
-
след числа, а
его ранг находят
по теореме о
ранге суммы:
,
(4.2ґ)
где
- число переходов
по основанию
![]()
Расширяют число
по формуле
расширения
(4.1ґ). Пользуясь
величиной
ранга
,
вычисленной
по формуле
(4.2ґ), получают
число
,
которое отличается
от искомого
числа А цифрами
по двум последним
основаниям.Если
,
то
,
т. е.
- искомое расширение
числа А.Если
,
то прибавляют
к числу
такое из минимальных
псевдоортогональных
чисел
кратности
,
где
,
которое превратит
цифру по основанию
в
.
В результате,
получают число
.Если кратность
,
то число
является искомым
расширением
числа А, так
как к числу
,
не превышающему
прибавили
число
,
не превышающее
,
т. е.
не превышает
Р, т. е. величины
1-го интервала.Если
,
то число
может располагаться
либо в последних
частях 1-го
интервала [0;
P), либо в
младших
частях второго
интервала [P;
2P), а тогда
искомым является
число
.
Еще один путь решения поставленной задачи представляет собой перевод числа из СОК в ОПС с дополнительным финальным шагом. Рассмотрим этот метод.
Пусть СОК
состоит из
оснований
,
,
…,
.
Объем диапазона
этой системы
будет
.
Добавим к числу
оснований СОК
новое основание
.
Объем диапазона
этой системы
.
Тогда любое
число
из диапазона
[0;
)
в обобщенной
позиционной
системе счисления
представимо
в виде
=![]()
+![]()
+…+
![]()
![]()
+![]()
+
.
Если число
будет лежать
в первоначальном
диапазоне [0;
),
то в ОПС цифра
=
0. Этот факт и
используется
для получения
остатка от
деления числа
на новое основание
СОК
.
Пусть число
имело представление
(
,
,
…,
)
по основаниям
,
,
…,
.
Добавляем новое
основание
,
тогда число
=(
,
,
…,
,
)
в системе оснований
,
,
…,
,
,
где
– остаток от
деления числа
на
,
т.е. искомая
цифра по новому
основанию.
Для определения
этой цифры
рассматриваем
алгоритм перевода
числа из СОК
в ОПС, включая
неизвестную
цифру
в проводимые
операции. При
этом мы последовательно
будем получать
цифры ОПС
,
,
…,
и выражение
для цифры
.
Но так как по
предположению
число
![]()
[
0;
),
то цифра
=
0. Из полученного
соотношения
и определяем
искомую цифру
.
Пример. Пусть
задана система
модулей
=
2,
=
3,
=
5,
=
7, тогда
=
2·3·5·7=210. И пусть
задано число
=
157= (1, 1, 2, 3). Расширим
систему оснований,
добавляя
=
11. Пусть
=
(1, 1, 2, 3,
)
в системе оснований
=
2,
=
3,
=
5,
=
7,
=
11. Набор констант
=
задается матрицей

Процесс решения задачи покажем
Расширение оснований модулярного кода
| Действия | Модули | Цифры СОК | ||||
|
|
|
|
|
|
||
|
_ х а1 |
1 1 |
1 1 |
2 1 |
3 1 |
1 |
а1=0 |
|
х-а1 ґ
|
0 |
0 2 |
1 3 |
2 4 |
6 |
|
|
_ х1 а2 |
0 0 |
3 0 |
1 0 |
6 0 |
а2=0 |
|
|
х1-а2 ґ
|
0 |
3 2 |
1 5 |
6 4 |
||
|
_ х2 а3 |
1 1 |
5 1 |
2 1 |
а3=1 |
||
|
х2-а3 ґ
|
0 |
4 3 |
2 9 |
|||
|
_ х3 а4 |
5 5 |
7 5 |
А4=5 |
|||
|
х3-а4 ґ
|
0 |
7 8 |
||||
|
x4 |
|
а5= |
||||
Таким образом,
а5 =
–
3, но по условию
а5 = 0, т.е.
–
3 = 0, откуда
=
3. Получим расширенное
представление
числа
=
157 = (1, 1, 2, 3, 3) по основаниям
=
2,
=
3,
=
5,
=
7,
=
11.
Этот алгоритм может быть несколько видоизменен за счет следующего свойства:

.
Фактически
величина
используется
только на последнем
шаге определения
цифры
.
Поэтому в столбце
по новому основанию
с самого начала
можно записать
ноль и применить
алгоритм перевода
числа из СОК
в ОПС.
Пусть по этому
алгоритму будет
получено что
=
для числа (
,
,
…,
,
0). Тогда
для числа
можно найти
из соотношения:
=
0.
Рассмотрим на том же примере эту модификацию алгоритма.
Модифицированный метод расширения оснований модулярного кода
| Действия | Модули | Цифры СОК | ||||
|
|
|
|
|
|
||
|
_ х а1 |
1 1 |
1 1 |
2 1 |
3 1 |
0 1 |
А1=1 |
|
х-а1 ґ
| ||||||