Другие статьи

Операции с матрицами на C++.   Класс DMatrix



 

Избыточные недвоичные системы счисления *

 

J.T. Butler, T.Sasao

 

( Оригинал статьи на английском:  Redundant Multiple-Valued Number Systems )

 

 

ПРЕДИСЛОВИЕ

 

 

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

 

ВВЕДЕНИЕ

 

 

В человеческом обществе принято обменивать продукт труда одного типа на продукт труда другого типа. Например, когда человек расплачивается в ресторане, он обменивает деньги, полученные от своей трудовой деятельности, на результат работы поваров, скотоводов, земледельцев, транспортников и т.д. Такой обмен возможен благодаря существованию расценок на те или иные результаты  труда. Существует много способов выразить эту величину. Однако практически у всех систем счисления для представления различных чисел используется комбинация конечного набора символов. Десятичная система счисления распространена наиболее широко; принято считать, что это связано с количеством пальцев на руках. Аналогичная ситуация существует и в сфере компьютерной техники: так как проще всего построить логические элементы, имеющие два состояния, в компьютерах используется двоичная система. Обзор публикаций по многозначной логике позволяет сделать вывод о  перспективности систем счисления, использующих цифры больше единицы.

Несмотря на то, что двоичные системы получили широкое распространение только в настоящее время, существуют данные о том,  что в Китае использовали двоичные системы еще 5000 лет назад (Newman [15, p. 2422]).

 

Интересное исследование было проведено на раскопках Mohenjo-Daro, античного города, расположенного недалеко от реки Инд (Morrison and Morrison [14]). Были обнаружены камни неправильной формы, отличающиеся друг от друга по весу как 2n . Археологи считают, что они использовались торговцами культуры Harappan в качестве гирь для рычажных весов 4000 лет назад.  Предмет взвешивался с помощью этого набора камней, и таким образом его вес мог быть последовательно записан в двоичной системе счисления. Рычажные весы изображены на Рис 1.

 

 

Рис.1

 

 

Принцип работы такой системы прост: сначала находятся два маленьких камня с одинаковым весом; для установления их идентичности используются весы. Любопытно, что на раскопках обнаружены два камня с весами, отличающимися менее чем на унцию. Затем, опять используя те же весы, находится третий камень, равный по весу сумме двух предыдущих. Эти три камня используются для поиска четвертого, снова равного по весу сумме предыдущих, и так далее. Таким образом, вес камней определяется последовательностью:  1, 1, 2, 4, 8, 16, ... .

 

 

СРАВНЕНИЕ СИСТЕМ СЧИСЛЕНИЯ

 

 

СТАНДАРТНАЯ ДВОИЧНАЯ СИСТЕМА

 

 

В стандартной двоичной системе счисления представление числа N  определяется как

 

N = an-12n-1 + ... + a222 + a121 + a020, где ai Î {0, 1}.

 

На рис.2 приведен пример стандартной двоичной системы с резолюцией 4 разряда. В таблице приведены четырехразрядные двоичные представления и их значения. Гистограмма отображает количество различных представлений для каждого числа: очевидно, что существует одно и только одно 4-битное представление для каждого неотрицательного целого от 0 до 15.

 

 

                        

 

 

 

N = a323+a222+a121+a020, где ai e {0,1}.

 

 

 

 

Рис. 2.  Стандартная четырехбитная система счисления

 

 

 

НЕГА-ДВОИЧНАЯ СИСТЕМА

 

 

В нега-двоичной системе счисления можно представлять как положительные, так и отрицательные целые числа. Представление здесь выглядит так же, как и в стандартной двоичной, но с заменой основания «2» на «-2»:

 

N = an-1(-2)n-1 + ... + a2(-2)2 + a1(-2)1 + a0(-2)0

 

На рис.3 проиллюстрирована четырехбитная нега-двоичная система. Как и в стандартном случае, каждое число имеет единственное представление. Интересно, что с помощью определенного четного количества битов можно представить вдвое больше отрицательных чисел, чем положительных. Если количество бит – нечетное, количество положительных чисел больше, чем количество отрицательных, в два раза + 1. Такое несоответствие между количеством положительных и отрицательных чисел очень неудобно.

 

 

                          

 

 

 

N = a3(-2)3+a2(-2)2+a1(-2)1+a0(-2)0, где ai e {0,1}.

 

 

Рис. 3.  Нега-двоичная четырехбитная система счисления

 

 

 

 

 

СИСТЕМА С ДОПОЛНЕНИЕМ ДО ДВУХ

 

 

Как и в случае нега-двоичной системы, система с дополнением до двух позволяет представлять и положительные, и отрицательные целые числа. Однако, в этом случае количество положительных и отрицательных чисел в пределе одинаково. Представление выглядит так:

 

N = an-1(-2)n-1 + ... + a222 + a121 + a020

 

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

 

 

 

                          

 

 

 

N = a3(-2)3+a222+a121+a020, где ai e {0,1}.

 

 

Рис. 4.  Система счисления с дополнением до двух, четырехбитная

 

 

 

 

СИСТЕМА С ДОПОЛНЕНИЕМ ДО ЕДИНИЦЫ

 

 

Данная система – первый пример избыточной системы счисления. Действительно, число 0 имеет два представления, обозначаемые здесь как «0» и «-0». Каждое число представляется в этой системе как

 

N = an-1(-2)n-1 + ... + a222 + a121 + a020 + an-1 ;

 

число «0» - это 00…0, а число «-0» - 11…1 .  На рис.5 изображена четырехбитная система с дополнением до единицы. Двойственность представления нуля показана линией двойной амплитуды в точке 0.

 

 

                          

 

 

N = a3(-2)3+a222+a121+a020 +a3, где ai e {0,1}.

 

 

 

Рис. 5.  Система счисления с дополнением до единицы, четырехбитная

 

 

 

СИСТЕМА СЧИСЛЕНИЯ ФИБОНАЧЧИ

 

 

Система счисления Фибоначчи является следующим примером избыточной системы. В данной системе каждое число представляется как

 

N = an-1Fn+1 + ... + a2F4 + a1F3 + a0F2 ,

 

где Fi = Fi-1 + Fi-2 и F2 = F1 = 1.

 

Таким образом, вместо степеней 2 или -2 в качестве основания используются числа Фибоначчи. В этой системе присутствует много избыточных представлений. На рис.6 показано, что в четырехбитной системе Фибоначчи их четыре.

 

 

                   

 

N = a3F5 + a2F4 + a1F3 + a0F2, где ai e {0,1} and Fi i-е число Фибоначчи,

 

то есть:    N = a3*5 + a2*3 + a1*2 + a0.

 

 

 

Рис. 6.  Система счисления Фибоначчи, четырехбитная

 

 

СИСТЕМА ФИБОНАЧЧИ  БЕЗ СМЕЖНЫХ  ЕДИНИЦ

 

 

Цекендорф [16] доказал, что любое целое число может быть записано как сумма чисел  Фибоначчи и такое представление единственно, если не содержит двух единиц подряд. (см. рис.7). В таблице ниже вычеркнуты строки со смежными единицами. Таким образом, с помощью четырехбитной системы можно однозначно представить числа от 0 до 7.

 

 

                           

 

 

 

N = a3F5 + a2F4 + a1F3 + a0F2, где ai e {0,1} and Fi i-е число Фибоначчи,