Представление биномиальных чисел в матричной форме

Представление биномиальных чисел в матричной форме

Борисенко А.А., проф.

Сумский государственный университет

Автором в начале 80-х годов на основе предпринятых им исследований в области позиционных систем счисления были предложены биномиальные системы счисления с двоичным алфавитом [1, 2]. При этом было получено более десяти изобретений на различные двоичные биномиальные устройства и выданы соответствующие авторские свидетельства.

Среди этих изобретений имеется два, в которых использовался необычный даже для биномиальных систем счисления ступенчатый (каскадный) биномиальный счет. Особенностью этого счета является повышенное быстродействие и надежность [3, 4].

Однако для реализации устройств с каскадным счетом потребовались большие аппаратурные затраты, что делало затруднительным его получение. За последние 15 лет появилась недорогая и надежная технология реализации цифровых схем на программируемых логических интегральных схемах (ПЛИС) с практически неограниченными возможностями. Поэтому на сегодня полученные изобретения «созрели» для практической реализации. В свою очередь каскадный счет требует практической разработки более совершенных алгоритмов работы соответствующих схем и оценки их быстродействия и надежности.

Для реализации данных изобретений в работе предлагаются специальные (0, 1)-матрицы, названные автором биномиальными числовыми матрицами (БЧМ) или просто биномиальными матрицами (БМ), которые, кроме практического значения, интересны и сами по себе, так как представляют сложный математический объект, образующий числа в матричной форме.

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

Считалось, что ничего проще и надежнее, чем двоичная система счисления, не может быть. Правда, была известна еще более простая и надежная унитарная система счисления (число-импульсная), но ее использование в качестве универсального средства счета, как правило, даже не рассматривалось из-за низкого быстродействия реализованных на ней устройств и машин, хотя при этом подкупала их высокая надежность. Поэтому время от времени в унитарной системе счисления реализовывались цифровые устройства и даже машины, например, такая машина, как «Промінь».

При использовании БМ выгодно сочетается большое быстродействие, построенных на её основе цифровых устройств, за счет отсутствия переносов и распараллеливания операций и одновременно их высокая надежность.

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

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

Определение 1. Биномиальной числовой двоичной ()-матрицей (биномиальной матрицей) называется (0, 1)-матрица

содержащая строк длины к,

где, которая удовлетворяет следующим свойствам:

1 Число элементов биномиальной матрицы

.

2 В столбце матрицы может находиться не более одной 1, т.е.

,

где.

3 Число единиц в матрице не превышает значение, а число нулей :

,

.

4 Единицы в матрице в количестве от 1 до расположены в одной или нескольких строках так, что первая из них находится в крайнем левом, а последняя - в любом последующем столбце. При этом между столбцами с единицами отсутствуют столбы, в которых находятся нули. Это значит, что если даны начальная 1 в виде элемента, промежуточная в форме и конечная, то

,

;.

5 Логическое суммирование элементов диагоналей биномиальной матрицы слева направо образует цифры биномиального числа:

6 Сдвиг каждой строки биномиальной матрицы за исключением первой по отношению к предшествующей на один разряд влево образует каскадный (ступенчатый) код, в котором цифры биномиального числа образуются логическим суммированием по столбцам:

.

7 Если в ()-й строке расположена последовательность единиц, то она всегда расположена в ее начальной части, начиная с элемента и до, то есть произведение

,

.

8 Во всех строках матрицы за исключением ()-ой в любой ее части может быть образована последовательность единиц длиной от 1 до, в которой не могут присутствовать промежуточные нули.

Это значит, что если даны начальная единица в строке и конечная ; , то логическое произведение

.

9 Среди элементов любой диагонали матрицы, направленной слева направо, только один элемент может быть равен 1.

Это значит, что произведение для всех значений и

,

где при

или при

.

Из приведенных неравенств (8, 9) вытекает следующее условие для выбора:

При

.

10 Количества единиц в биномиальной матрице и в биномиальном числе равны между собой:

.

11 В первом столбце БМ за исключением БМ нулевого числа обязательно содержится 1.

12 Единицы в матрице располагаются так, что единица каждого последующего столбца находится или в той же строке, что и в предшествующем столбце, или в одной из верхних строк с меньшим номером.

13 Если в первом столбце 1 отсутствует, то и в остальных столбцах не будет единиц.

14 Нижние элементы первого столбца БМ, содержащей хотя бы одну 1, начиная с ()-го элемента и до элемента, образующего 1, представляют собой старшие разряды соответствующего биномиального числа.

Элементы второго столбца БМ, начинающиеся с элемента, соответствующего 1 первого столбца и направленные к вершине этого столбца до элемента равного 1 включительно или при его отсутствии до 0 в начале столбца включительно, образуют следующие за полученными в первом столбце старшими разрядами младшие по отношению к ним разряды биномиального числа.

Аналогично с правилом нахождения элементов второго столбца находятся элементы, образующие младшие разряды биномиального числа третьего числа и т.д. до -го столбца включительно.

Приведем все биномиальные матрицы для, число которых определяется диапазоном биномиальных чисел:

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

Число элементов в этих матрицах равно. Из них единицами могут быть заполнены не больше.

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

В каждом столбце и идущей слева направо диагонали матрицы находится не более одной 1.

Число единиц в любой строке матрицы не превышает и расположены они так, что между ними отсутствуют нули.

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

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

Summary

Тhe new matrix aprouch in the field of binomial counting is proposed in the paper. It allows us to represent binomial numbers into matrix form. As a result when counting the transfer is absent, ant there is a possibility to control it deeply. These metrits give а possibility to develop super-high-speed and superreliable counters.

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

Борисенко А. А., Губарев С. Н., Куно Г. В. Биномиальные системы счисления с двоичным алфавитом // Автоматизированные системы управления и приборы автоматики. - Харьков, 1985. - №75.

Борисенко А. А., Губарев С. Н., Куно Г. В. Биномиальные счетчики. // Автоматизированные системы управления и приборы автоматики. - Харьков, 1989. - №92.

Борисенко А.А., Воронов В.Г., Володченко Г.С., Куно Г.В. Биномиальный быстродействующий суммирующий счетчик с коррекцией ошибок: А.с. СССР 1298906.

Борисенко А.А., Куно Г.В., Путятин Е. П. Биномиальный быстродействующий помехоустойчивый вычитающий счетчик: А.с. СССР 1422404.