Методи перенесення і запозичення у швидкодіючих фібоначчієвих лічильниках

Abstract

У даній статті описано підхід до організації перенесення при лічбі у модифікованій фібоначчієвій системі числення. Даний підхід полягає у тому, що на кожному такті лічби наряду з додаванням одиниці у молодший розряд в залежності від напрямку лічби виконується один із видів фібоначчієвого перетворення (F-перетворення) коду лічильника. Використання FL- та FR-перетворень дозволяє виконувати перенесення і запозичення ще до того, як виникне переповнення у молодших чи загублення значення у старших розрядах. Це дозволяє уникати ситуацій, при яких за один такт перенесення або запозичення розповсюджуються далі ніж через три розряди. У статті описано модифіковану фібоначчієву систему числення, наведено аналітичні вирази для опису базису і алфавіту та показано, як представляються у ній числа. Наведено аналітичні вирази, що описують FL- та FR-перетворення. Сформульовано твердження про те, що при виконанні всіх можливих фібоначчієвих перетворень на кожному такті лічби отриманий код буде мати не більше двох сусідніх одиниць. Це дозволяє організувати швидку лічбу за рахунок малого часу розповсюдження перенесення і запозичення.

В данной статье описан подход к организации переноса при счете в модифицированной Фибоначчиева системе счисления. Данный подход заключается в том, что на каждом такте счета наряду с добавлением единицы в младший разряд в зависимости от направления счета выполняется один из видов Фибоначчиевого преобразования (F-преобразование) кода счетчика. Использование FL- и FR преобразований позволяет выполнять перенос и заимствование еще до того, как возникнет переполнение в младших или утеря значения в старших разрядах. Это позволяет избегать ситуаций, при которых за один такт перенос или заимствование распространяются дальше чем через три разряда. В статье описано модифицированную Фибоначчиева систему счисления, приведены аналитические выражения для описания базиса и алфавита и показано, как представляются в ней числа. Приведены аналитические выражения, описывающие FL- и FR преобразования. Сформулировано утверждение о том, что при выполнении всех возможных Фибоначчиевых преобразований на каждом такте счета полученный код будет иметь не более двух соседних единиц. Это позволяет организовать быстрый счет благодаря малому времени распространения переноса и заимствования.

This article describes the approach to the organization of carry-over with the account in the modified Fibonacci numerical system. This approach is based on the fact that on each count cycle, along with the addition of a unit to the low order depending on the direction of the account, one of the Fibonacci transformation types (F-transformation ) of the counter code is executed. Using FL- and FR-transformation allows you to carry out the carrying and borrowing even before there is an overflow in the lower or loss in the higher order bits. This makes it possible to avoid situations in which the carrying or borrowing is extended more than three orders in a single clock cycle. The article describes the modified Fibonacci numerical system, provides analytical expressions for describing the basis and the alphabet, and shows how the numbers are represented in it. Analytical expressions describing FL and FR transformations are given. An assertion is made that when all possible Fibonacci transformations are performed on each circle of count, the resulting code will have no more than two neighboring units. This allows you to organize a quick count due to the short transfer and borrowing time.