Моделі та метод арифметичного складання двійкових біноміальних чисел в інформаційно-комунікаційних технологіях

Abstract

Низка інформаційних завдань в комп’ютерних системах і компонентах найбільш ефективним чином вирішуються за допомогою неоднорідних систем числення, наприклад таких, як факторіальних, фібоначчієвих або біноміальних. Завдяки своїм властивостям, які не мають двійкові системи чисел, а саме надлишковість, нерівномірність, вбудовані засоби контролю помилок, здатність генерувати комбінаторні об’єкти, неоднорідні системи числення за умови вирішення спеціалізованих завдань дозволяють досягати унікальних характеристик при застосуванні інформаційно-комунікаційних технологій на їх основі або побудові спеціалізованих цифрових систем. На сучасному етапі розробки обчислювальної техніки та інформаційно комунікаційних технологій широке використання нетрадиційних неоднорідних систем числення суттєво залежить від наявності розробленої машинної арифметики. Особливе місце серед неоднорідних систем числення займають структурні двійкові біноміальні системи числення через їх значну надлишковість, складний функціональний зв'язок між ваговими коефіцієнтами та значеннями біноміальних розрядів, подібність їх структури до структури розповсюджених відомих кодів-сполучень. Виходячи зі своїх позитивних властивостей двійкові біноміальні системи числення знаходять своє практичне використання при вирішення таких інформаційних завдань, як стиснення інформації, шифрування даних, генерування рівноважних та квазірівноважних кодів, наскрізний контроль правильності даних та організація завадостійкої лічби. Але на сьогоднішній день не існує розроблених правил і процедур виконання арифметичних операцій над біноміальними числами, зокрема біноміального складання. Як наслідок, це є стримуючим фактором для більш широкого впровадження біноміальних систем числення у інформаційні технології обробки даних. Сучасний стан розв’язання цієї проблеми полягає у використанні табличного методу, або моделей біноміальних лічильних пристроїв, або проміжних ступеневих систем числення, наприклад десяткової або двійкової. Табличний метод знаходження результату біноміального додавання, хоча і є швидкісним, потребує великих програмно-апаратних витрат. Застосування моделей біноміальних лічильних пристроїв та проміжних ступеневих систем числення призводить до великих часових втрат поряд із значними додатковими апаратно-програмними витратами. Вказані недоліки суттєво перешкоджають використанню біноміального арифметичного складання в інформаційно комунікаційних технологіях. У дисертаційній роботи вирішується наступна наукова-прикладна задача з розробки і дослідження арифметичного складання двійкових біноміальних чисел при обмеженнях на обсяг програмно-апаратних витрат з метою прискорення обчислювальної обробки біноміальної числової інформації для більш ефективного впровадження інформаційно-комунікаційних технологій для вирішення спеціалізованих завдань зі стиснення інформації, генерування комбінаторних об'єктів, комбінаторної оптимізації, шифрування даних тощо. Метою дисертаційної роботи стосовно дослідження та розробки моделей і методу арифметичного складання двійкових біноміальних чисел, що генеруються двійковими біноміальними системами числення, є зменшення часу виконання операції при обмеженнях на об'єм програмно-апаратних витрат. Актуальність теми дисертаційних досліджень визначається тим, що розробка моделей і методу біноміального арифметичного складання стануть основою для побудови біноміальної машинної арифметики для комп'ютерних систем та компонентів, надаватимуть нові можливості щодо створення ефективних інформаційно-комунікаційних технологій по обробці даних: генерування комбінаторних об’єктів, проведення комбінаторної оптимізації, забезпечення завадостійких біноміальних обчислень, а також стимулюватимуть подальший розвиток теорії двійкових біноміальних систем числення. Об'єкт досліджень – процеси обчислювальної обробки інформації в інформаційно-комунікаційних технологіях, які функціонують у двійковій біноміальній системі числення. Предмет досліджень – моделі і методи підвищення продуктивності спеціалізованих інформаційно-комунікаційних технологій в режимі реального часу на основі моделей і методу арифметичного складання біноміальних чисел, що генеруються двійковими біноміальними системами числення. Новим науковим результатом дисертації є розв'язання важливої і актуальної науково-прикладної задачі з розробки моделей та методу біноміального арифметичного складання, що надає можливість суттєво зменшити часові витрати, необхідні для виконання операції над двійковими біноміальними числами, генерованих двійковими біноміальними системами числення, при обмеженнях на обсяг програмно-апаратних витрат. В дисертаційній роботі вперше отримані: 1. Матрична модель двійкових біноміальних чисел, яка базується на матриці вагових коефіцієнтів і враховує функціональний зв'язок між значеннями попередніх біноміальних розрядів та їх позиціями в розрядній сітці біноміальних чисел. При цьому вагові коефіцієнти двійкових біноміальних чисел представляються двохелементними кортежами, кожному з яких відповідає одинична комірка матриці біноміального числа. Така будова матричної моделі двійкових біноміальних чисел дозволяє просто та в наявному вигляді формувати одиниці переносу з одного біноміального розряду в інший. 2. Матрична модель біноміального арифметичного складання, на основі якої провадиться підсумовування двійкових біноміальних чисел. Розроблена модель дозволяє замінити громіздкі операції з кількісними значеннями біноміальних коефіцієнтів на значно простіші операції з їх верхніми та нижніми параметрами, тобто з координатами стовпців та рядків матриці біноміального арифметичного складання. Таким чином, операції по знаходженню біноміальних вагових коефіцієнтів з визначенням факторіалів замінюються звичайними операціями порівняння, віднімання або додавання одиниці, що значно пришвидшує процес підсумовування двійкових біноміальних чисел. 3. Метод арифметичного складання двійкових біноміальних чисел, який на основі перетворень переносу, зсуву, симетрії та розкладання, що виконуються над комірками матриці біноміального складання, провадить підсумовування двійкових біноміальних чисел, оперуючи координатами комірок матриці складання замість оперування зі значеннями біноміальних коефіцієнтів. Це потребує значно менших обсягів часових та програмно-апаратних витрат для отримання результату додавання порівняно з іншими існуючими методами. В дисертаційній роботі набули удосконалення: 1. Методи оцінки обсягів часових та програмно-апаратних витрат арифметичного складання двійкових біноміальних чисел, які дозволяють визначити граничні максимальні значення витрат при практичній реалізації і проводити порівняння з цього погляду з іншими існуючими підходами для отримання результату додавання біноміальних чисел. 2. Моделі оброблення кодів-сполучень, за якими представляються сигнали в інформаційно-комунікаційних технологіях, на основі операцій додавання або добутку із застосуванням арифметичного складання відповідних їм двійкових біноміальних чисел. Це розширює можливості інформаційно-комунікаційних технологій щодо якісної та швидкодіючої обробки сигналів, кодованих кодами сполучень. 3. Моделі генерування кодів-сполучень, до яких відносяться поширені рівноважні або квазірівноважні коди, на основі арифметичної операції складання двійкових біноміальних чисел, які дозволяють пришвидшити процес генерування кодів-сполучень та підвищити функціональну гнучкість інформаційних систем генерації. 4. Інформаційно-комунікаційна технологія стиснення рівноважних кодів із застосуванням арифметичного складання двійкових біноміальних чисел, яка дозволяє суттєво підвищити коефіцієнт стиснення інформаційних масивів, складених з рівноважних кодів, і, як наслідок, збільшити швидкість передачі даних по каналам зв'язку. Отримала подальший розвиток теорія біноміальних систем числення і позиційної біноміальної лічби, що обумовлює більш поширене застосування двійкових біноміальних систем числення та генерованих ними біноміальних чисел при розробці нових інформаційних технологій обробки даних. Практичне значення отриманих результатів визначається розробленими алгоритми арифметичного складання двійкових біноміальних чисел, які характеризуються ефективністю, кінцевістю та можуть бути достатньо легко з обчислювального погляду реалізовані на практиці. Алгоритми арифметичного складання двійкових біноміальних чисел на основі матричного представлення та динамічного масиву складання дозволяють виконувати операції за поліноміальний час, відповідно у асимптотичному вираженні за кубічний O (n3) та квадратичний час O (n2), де n – параметр біноміальної системи числення. Це значно менше факторіального часу O n( !), який потребується у разі застосування традиційного способу знаходження результату біноміального додавання із використанням проміжних ступеневих систем числення. Різниця між алгоритмом на основі матричного представлення двійкових біноміальних чисел та алгоритмом на основі динамічного масиву полягає в тому, що останній виконує пошук перетворюваних двоелементних кортежів тільки серед одиничних елементів, що помітно скорочує час операції додавання. Але з іншого боку алгоритм на основі матриці біноміального складання дозволяє контролювати успішність процесу проведення операції на усіх етапах її виконання. Синтезована також структурна модель спеціалізованого пристрою арифметичного складання на основі матричного представлення двійкових біноміальних чисел, в якому основний обсяг витрат покладається на застосування оперативної пам'яті для збереження матриці біноміального складання розмірності (n − k) x (k + 1) комірок.

The scientific and applied problem on development and research of binary binomial numbers arithmetic addition is decided under restrictions on the amount of hardware and software expenses aimed to speed up binomial number information processing in the dissertation. Into computer systems and components some information tasks are implemented with heterogeneous number systems, for example factorial, Fibonacci and binomial ones, in the most effective way. Due to their peculiarities that binary number systems don’t hold like for example redundancy, unevenness, embedded means of error control, ability to generate combinatory objects, the heterogeneous number systems when the specialized tasks are processing allow us to achieve unique characteristics at using information technologies on their basis or at building specialized digital systems. At the present stage of computed technics and information technologies development the wide-distribution non-traditional for the heterogeneous number systems depends on the being of the developed machine arithmetic substantially. The structural binary binomial number systems occupy a special place among heterogeneous number systems thanks to their significant redundancy, complex functional dependence between weight coefficients and values of binomial digits, similarity their structure to structure of the spread well-known code-combinations. Based on their positive properties, binary binomial number systems find their practical use in solving such information tasks as information compression, data encryption, generation of constant weight and quasi-equilibrium codes, end-to-end control of data correctness and organization of interference-resistant counting. But in the present time the developed rules and procedures to fulfil arithmetic operations on the binomial numbers, including the binomial addition, don’t exist. As a consequence, there is a restraining factor for embedding binomial number systems into information technologies devoted to data processing more widely. The current state of solving this problem consists in the use of a tabular method, or models of binomial counting devices, or intermediate power number systems, for example, decimal or binary number systems. The tabular method of finding the result of binomial addition, although it is fast, requires large software and/or hardware software expenses. The use of models of binomial counting devices and intermediate power number systems leads to large time losses along with significant additional software and/or hardware costs. These shortcomings significantly prevent the use of binomial arithmetic addition in information and communication technologies. The dissertation solves the following scientific and applied problem: the development and research of the arithmetic addition of binary binomial numbers with restrictions on the amount of software and/or hardware expenses in order to speed up the computational processing of binomial numerical information for more effective implementation of information and communication technologies for solving specialized tasks of information compression, generation combinatorial objects, combinatorial optimization, encryption, etc. The aim of the dissertation devoted to research and development the models and method of arithmetic addition for binary binomial numbers that are generated with binary binomial number systems is to decrease time of this operation subject to restrictions on the amount of software and/or hardware expenses. The relevance of dissertation researches is defined by the fact that the models and method of binomial arithmetic addition development will become the basis for building binomial machine arithmetic into computer systems and components, will give new possibilities to create effective information and communication technologies of data processing such as combinatory objects generation, combinatory optimization, support of noise-immunity binomial computations, as well to stimulate further development of binomial number systems theory. Object of research is information computational processing into computer systems and components that executes by a binary binomial number system. Subject of research is models and methods for enlarging productivity of specialized information management systems, as well as computer systems and components that put them together, in real time on basis of the models and method of arithmetic addition of binomial numbers that are generated by binary binomial number systems. The new scientific result of the dissertation is the decision of the important and relevant scientific and applied problem devoted to development of the models and method of binomial arithmetic addition that give a possibility to reduce time expenses required to implement the operation on binary binomial number systems with restrictions on the amount of hard and/or software expenses. In the dissertation the following results are obtained for the first time: 1. The matrix model of binary binomial numbers that is based on the matrix of weight coefficients and takes into consideration the functional connection between the values of the forward binomial digits and their positions in the bit grid of binomial numbers. At the same time, the weighting coefficients of binary binomial numbers are represented by two-element tuples, each of which corresponds to a unit cell of the binomial number matrix. Such a construction of the matrix model for binary binomial numbers allow us to form carry units from some binomial digit to another one in the simple and obvious way. 2. The matrix model of binomial arithmetic addition on basis of which the addition of binary binomial numbers is carried out. The developed model provides a possibility to substitute the cumbersome operations with the quantitative values of the binomial coefficients by much simpler operations with their upper and lower parameters, that is, the coordinates of columns and rows from the binomial arithmetic addition matrix. It accelerates the process of binomial numbers addition significantly. 3. The method of arithmetic addition for binary binomial numbers that conducts the addition of binary binomial numbers by processing cells coordinates of the addition matrix instead of processing values of the binomial coefficients on basis of carry, shift, symmetry and decomposition transformations. It requires much less the amounts of time and hardware and software expenses for obtaining the addition result in comparison with other being methods. In the dissertation the following results are represented as improvements: 1. The methods of estimation of time and hardware and software expenses amounts for the arithmetic addition of binary binomial numbers that allow us to determine marginal maximum values of expenses during practical implementation and to compare with other methods for obtaining the binomial numbers addition result in terms of costs. 2. The models of processing signals encoded by code-combinations in information and communication technologies, based on operations of their addition or multiplication with the use of arithmetic addition of the corresponding binary binomial numbers. This expands the possibilities of information and communication technologies for high-quality and fast processing of signals represented by code combinations. 3. The models of code-combination generation, which include common constant weight or quasi-equilibrium codes, based on arithmetic addition on binary binomial numbers, which allow us to speed up the process of generating code-combinations and to increase the functional flexibility of generation systems. 4. The information and communication technology of compression of constant weight codes using the arithmetic addition of binary binomial numbers, which allows us to significantly increase the compression ratio of information arrays composed of constant weight code combinations and, as a result, to increase the speed of data transmission over communication channels. The theory of binomial number systems and positional binomial count get further development that gives an additional impact to wider using binary binomial number systems and generated by them binomial numbers when developing new information technologies of data processing. The practical significance of the obtained results is determined by the developed algorithms of arithmetic addition for binary binomial numbers that are characterized efficiency, finiteness and that fact is they can be put into practice enough easily in terms of computational complexity. The algorithms of arithmetic addition for binary binomial numbers on basis of matrix representation and dynamic array allow us to execute operations in polynomial time, cubic time O (n3) and quadratic time O (n2) accordingly in asymptotic terms, where n is a parameter of a binomial number system. It is much less factorial time O n( !) that is demanded when applying traditional technics for searching the binomial addition result with use of intermediate power number systems. The difference between the algorithm based on the matrix representation of binary binomial numbers and the algorithm based on the dynamic array is that the latter searches for transformable two element tuples only among unit elements, which significantly reduces the time of the addition operation. But on the other hand, the algorithm based on the matrix of binomial addition allows us to control the process at all stages of its execution. The structure model of specialized device for arithmetic addition on basis of matrix models of binary binomial numbers which the main part of the hard ware volume defined by necessity to use random access memory for saving the matrix of binomial addition of dimension (n − k) x (k + 1) cells.