Математические основы системы остаточных классов (стр. 9 из 19)

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

§ 3. Восстановление позиционного представления числа по его остаткам

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

1). Метод восстановления числа по его остаткам был найден еще в Китае две тыс. лет назад. Основой этого метода является теорема, названная, поэтому Китайской теоремой об остатках (КТО).

Теорема. Пусть

– попарно взаимно простые числа, = , , , …, подобраны так, что 1 , = , . Тогда решение системы , , будет иметь вид: .

Эта теорема лежит в основе метода ортогональных базисов при переводе из системы остаточных классов в позиционную систему счисления.

Пусть основания системы остаточных классов

; = = – объем диапазона системы. С выбором системы определяются ее основные константы – базисы , . Задача перевода числа = =( ) в ПСС заключается в определении таких чисел , , чтобы = . Для однозначного определения на базисы системы накладывается ряд ограничений и показывается, что таким свойством обладают базисы

= (1, 0, 0, …, 0, 0), =(0, 1, 0, …, 0, 0), = (0, 0, 0, …, 0, 1),

которые называются ортогональными.

Тогда в случае ортогональных базисов

= , . Ортогональные базисы определяются по формуле

= , , (3.1´)

где

= (3.2´)

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

º 1 (3.3´)

Тогда, по Китайской теореме, число

= ( ) .

Таким образом, если найдены ортогональные базисы для системы оснований, то для перевода числа

= ( ) достаточно вычислить и ввести эту сумму в диапазон [0; ) вычитанием величины, кратной , т.е.

= = – , (3.4´)

где

– ранг числа , показывающий сколько раз надо вычесть величину диапазона из полученного числа, чтобы вернуть его в диапазон.

Пример. Пусть дана система оснований

= 2, = 3, = 5, =7, =11, объем диапазона =2·3·5·7·11=2310. перевести число = (1, 2, 1, 4, 7) в позиционную систему.

Вычислим ортогональные базисы.

Для этого найдем величины

:

=1155, =770, =462, =330,

=210.

Ищем веса базисов:

1155

º 1( 2), º 1( 2).

770

º 1( 3), º 2( 3).