Системы счисления и ЭВМ

Размещено на http://www.allbest.ru/

СИСТЕМЫ СЧИСЛЕНИЯ И ЭВМ

А.А. Борисенко

С точки зрения теории кардинальных чисел система счисления должна решать задачу установления однозначного соответствия между элементами двух множеств. С одной стороны, это натуральные числа (номера) из некоторого диапазона P, принимающие значения 0,1,...,P-1, а с другой - P некоторых различающихся между собой знаков X- системных чисел. Так как число P может быть неограниченно большим, то знаки X представляют в виде последовательностей цифр x_j, j=1,2,...,n, порождаемых алфавитом

A={a₁,a₂,...,a_k}, x_j?A, j=1,2,...к; X=(x₁,...,x_n).

Очевидно, что имеется Кⁿ возможных последовательностей X, и, значит, соответственно имеется возможность кодирования P=Кⁿ натуральных чисел.

Теория порядковых чисел основывается на системе аксиом Пеано [1]. Под этой системой понимается некоторая система (П,S_c,1), где S_c- функция следования на П, относительно которой П замкнуто, и где:

а) S_c(X)№1 для всех XОП;

б) для всех XОП и S_c(X) =S_c(Y) следует X=Y;

в) если A, 1A и A обладает тем свойством, что из XA следует S_c(X)ОA, то A=П.

Аксиомы Пеано задают натуральный ряд чисел. Прежде всего задаётся положительное число 1, с которого начинается счет. За ним может следовать только одно целое число X, отличное от 1-2= S_c(1). Применяя к X функцию S_c(X)=x+1 достаточное число раз, можно получить из 1 любое целое положительное число, а значит, и натуральный ряд чисел.

Система счисления должна иметь возможность своими внутренними средствами в соответствии с аксиомами Пеано реализовать функцию следования. Это значит, что пo виду X система счисления должна определить следующий знак X`. Так как каждый элемент натурального ряда отличается на 1 от предшествующего, то X`=S_c(X)=X+1.

Введем между знаками алфавита А отношение порядка. Будем считать, что a₁<a₂,a₂<a₃,...,a_k-1<a_k. Тогда последовательности X можно записать в лексикографическом порядке и, следовательно, по виду X можно определить X`=S_c(X). Это значит, что в непозиционных системах счисления с помощью функции S_c(X) можно реализовать арифметические операции. Однако эффективность их реализации с точки зрения быстродействия будет небольшая, так как все операции осуществляются путем последовательного перебора чисел натурального ряда, т.е. сложения с 1. Сложение в этом случае реализуется как

X+S_c(Y)= (X+Y)+1=S_c(X+Y),

а умножение

X^.1=X, X^.S_c(Y)=X(Y+1).

Остальные операции реализуются аналогичным образом [1].

Значительно повысить эффективность счета удалось в позиционных системах счисления введением числовой функции F, которая путем ускоренного выполнения арифметических операций по определённым правилам решает задачу однозначного преобразования последовательностей X=x₁x₂...x_n в числа натурального ряда и обратно. В простейшем, наиболее распространённом случае последовательность X является элементом декартовой степени Aⁿ,XAⁿ. Однако в общем случае могут быть заданы ограничения, разделяющие множество всех возможных последовательностей Aⁿ на множество R разрешенных XR--и множество запрещенных Aⁿ/R.

Элементам последовательности X в данном случае, кроме того, что они находятся в отношении порядка, присваиваются в общем случае значения целых чисел, а в наиболее распространенном случае - числа a₁=0,a₂=1,...,a_k=k-1.

Если множество R=Aⁿ, то мы имеем простейшие степенные системы счисления. Последовательности X в этом случае называются номерами. Для них характерно отсутствие избыточной информации, которая в общем случае присуща числам X в количестве

Двоичная, десятичная и другие подобные системы счисления представляют именно такие степенные позиционные системы счисления. В них веса j-х разрядов, j=0,1,...,n-1 представляют степень основания K системы счисления -K^j.

Диапазон представленных чисел в этих системах P=Kⁿ.

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

Более сложными и обобщающими являются системы счисления со смешанным основанием. В этих системах основания от разряда к разряду меняются, как правило, в порядке возрастания, а диапазон P равен их произведению. Интересным и полезным их частным случаем являются факториальные системы счисления [2].

В них основания равны 0,1,2,...,n-1, а диапазон P=n! Их особенностью является наличие запрещенных комбинаций и, следовательно, избыточной информации

Числовая функция факториальной системы счисления имеет вид

,

0a_nn.

Таблицы сложения и умножения при этом для каждого разряда свои, а длины l=n+1 разных чисел одинаковы. Ценным свойством факториальных чисел является возможность формирования на их основе перестановок.

Новый шаг в развитии теории и практики систем счисления внесла разработка фибоначчиевых систем счисления А.П.Стаховым [3]. Числовая функция в этом случае имеет вид

счисление аксиома счет пеано

,

где a_n-1,a_n-2,...,a₀- разряды числа, равные 0 или 1;

при l>0.

Эта система счисления, как и факториальная, имеет запрещенные кодовые комбинации. Однако она отличается большей сложностью и поэтому способна эффективно обнаруживать несимметричные ошибки типа 01. В то же время она обладает относительно простыми правилами выполнения арифметических операций, что делает перспективным реализацию на её основе фибоначчиевых ЭВМ.

Позже автором были разработаны двоичная и многозначная биномиальные системы счисления [4,5].

Двоичная биномиальная система счисления имеет числовую функцию

при соблюдении одной из систем ограничений:

где М - диапазон чисел;

r- длина числа;

l - 0,1,..., r-1 - порядковый номер разряда;

g_l - сумма единичных значений цифр от (r-1)-го разряда до l-го включительно:

Многозначная биномиальная система счисления имеет следующий вид:

где

X_r-l - цифра (r-l)-го разряда;

P - контрольное число;

при следующих ограничениях:

Диапазон биномиальных чисел в этом случае

Биномиальные системы счисления отличаются высокой сложностью и поэтому обладают повышенной помехоустойчивостью. Кроме того, они способны генерировать различные комбинаторные конфигурации, как, например, сочетания, сочетания с повторениями, композиции и др. Это делает перспективным разработку на их основе различных вычислительных устройств, использующих комбинаторные конфигурации. Однако арифметика в этих системах счисления достаточно сложна и поэтому такие системы счисления могут сегодня применяться в специализированных устройствах.

Рассмотренные системы счисления представляют лишь некоторые вехи на пути их развития. Возможно получение множества промежуточных систем счисления и разработка принципиально новых их классов, например, полиномиальных. Это возможно потому, что каждому комбинаторному соотношению, как показывает теория, может быть поставлена в соответствие своя система счисления. Кроме того, теория систем счисления показывает, что любую древовидную структуру можно идентифицировать с системой счисления определенной сложности, а значит избыточности и помехоустойчивости. Следовательно, в основе любых структурированных множеств, а значит кодов и языков, лежат системы счисления. С этой точки зрения можно взглянуть и на проблемы теории автоматов, математической лингвистики и других разделов математики. Однако в теории систем счисления имеется и ряд сложных не решенных на сегодняшний день проблем, как, например, разработка обобщенной для всех систем счисления арифметики. Их решение позволило бы разработать эффективные алгоритмы кодирования информации и найти новые решения ряда задач дискретной математики.

Список литературы

1. Федерман С. Числовые системы. Основания алгебры и анализа/Пер. с англ. М.: Наука, 1971.

2. Рейнгольд Э., Нивергельт Ю., Дес Н. Комбинаторные алгоритмы. Теория и практика /Пер. с англ. М. Мир, 1980.

3. Стахов А.П. Фибоначчиевые двоичные позиционные системы счисления. Кодирование и передача дискретных сообщений в системах связи. Научн.-техн. сб. М.: Наука, 1976. C.155-179.

4. Борисенко А.А. Об одной системе счисления с биномиальным основанием. Рук. деп. в ВИНИТИ, 1982, N 874-82.

5. Борисенко А.А. Система счисления с биномиальным основанием и двоичным алфавитом. Рук. деп. в ВИНИТИ, 1982, N 909-82.

6. Борисенко А.А. Методы синтеза информационных систем на основе позиционных чисел с неоднородной структурой. Диссертация на соискание ученой степени доктора технических наук. Харьков, 1991.

Размещено на Allbest.ru