Системи числення - Стор 2
(За визначенням, чергове число базису дорівнює сумі двох попередніх.)
Зауваження1. Операція згорткизменшуєкількість одиниць у фібоначчієвому записі числа, але може збільшити на одиницю кількість цифр у записі, якщо вихідний запис починався з двох одиниць. Наприклад,110101 =1000101.
Зауваження2. Операція розгорткизбільшуєкількість одиниць у фібоначчієвому записі числа, але може зменшити на одиницю кількість цифр у записі, якщо вихідний запис починався з комбінації “100”. Наприклад,1000101 =110101.
Якщо над записом числа у ФСС виконати всі можливізгортки,то ми прийдемо до спеціального фібоначчового представлення числа, званогомінімальною формою,в якій немає двох одиниць, що стоять поруч. Якщо ж у фібоначчієвому записі виконати всі можливі операції розгортки, то прийдемо до спеціального фібоначчієвого зображення, що називаєтьсямаксимальною,аборозгорнутою, формою,в якій поруч не зустрічається двох нулів. Будь-яке числоАпредставляється в мінімальній або максимальній формі єдиним способом.
Правило приведення фібоначчієвого запису числа до мінімальної форми
1. Переглядаючи запис числа ліворуч праворуч, знайдемо першу комбінацію “11”.
2. Виконаємо над нею операцію згортки:
Якщо комбінація “11” стоїть на початку запису числа, кількість цифр у записі числа збільшиться на одиницю. До запису числа зліва припишеться 1, а комбінація "11" заміниться "00";
Якщо сама ліва комбінація "11" знаходиться не на початку запису, це означає, що перед нею обов'язково коштує 0. Тоді комбінація "011" замінюється на "100".
3.Послідовно виконаємо операції згортки для всіх комбінацій “11”, рухаючись позапису числа зліва направо.
4. Якщо в запису є дві стоять одиниці, то перехід на п. 1, інакше запис, що вийшов, буде шуканою мінімальною формою.
Яке найбільше число у ФСС, представлене в мінімальній формі, можна записати в розрядах?
Очевидно, що найстарша цифра має бути 1. Далі для побудови максимального числа цифри 0 та 1 повинні чергуватись. Тоді максимальне число, яке можна записати вkрозрядах, дорівнює 10101...10 при парномуkі 10101...01 при непарномуk.
Розрядів у осередку
2 16 - 1 = 65535
При записі чисел у фібоначчієвій системі числення прийнято використовуватимінімальнуформу запису:у цій формі немає двох одиниць, що йдуть поспіль. Тобто числа 100 у ФСС будуть записано однозначним чином.Оскільки цифрами фібоначчієвої системи числення є 0 і 1, то фібоначчі код містить тільки нулі і одиниці. Але якщо при передачі фібоначчієвого коду, представленого в мінімальній формі, з'явилися дві одиниці, що поспіль йдуть, то можна однозначно сказати, що інформація прийшла зі спотворенням (втратою).
"Природна" надмірність кодів Фібоначчі, яка проявляється в "множинності" уявлень одного і того ж числа, може бути використана для контролю числових перетворень в цифрових пристроях.
Аналіз фібоначчієвої арифметики показав, що основними її операціями є операціїзгортка, розгорткаі заснована на них операціяприведення коду Фібоначчі до мінімальної форми.
Ці математичні результати стали основою для проектів створення комп'ютерних та вимірювальних систем на основі фібоначчієвої системи числення.
Як відомо, комп'ютерна програма реалізується за допомогою команд процесора,сама програма та оброблювані дані зберігаються в оперативній пам'яті. На жаль, неможливо повністю виключити помилки, що виникають внаслідок несправної роботи комп'ютерних елементів. Розрізняють два типи несправностей:
постійна відмоваелемента (елемент, що одного разу відмовив, “вибуває з гри”);
випадкова відмова(елемент “відмовляє” у випадкові моменти часу, тоді як інші моменти часу елемент працює коректно).
Останній тип відмов називаєтьсязбоєм.Збої в процесорі виникають під впливом різних факторів, що викликаються зовнішніми та внутрішніми шумами в комп'ютерних елементах та їх електронних ланцюгах. Збої в електронних елементах, зокрема в тригерах, виникають значно частіше, ніж постійні відмови.
Експериментально доведено, щозбої тригерівв режимі перемикання є найбільш імовірною причиною ненадійного функціонування процесорів.Ось чому проектування цифрових автоматів, що самоконтролюються, гарантують ефективний контроль збоїв тригерів, є однією з найважливіших проблем проектування високонадійних процесорів. .
Як уже говорилося раніше, у 80-х роках минулого століття група вчених під керівництвом професора Олексія Петровича Стахова з Таганрозького радіотехнічного інституту дійшла ідеї створення процесора, що дозволяє виявляти збої тригерів, що виникають у момент їх перемикання. Такий процесор вони називалиперешкодостійким процесором.Основна ідея створення завадостійкого процесора полягала в наступному:
вся оброблювана інформація має бути представлена у фібоначчієвій системі числення;
необхідно вибрати деякий набір операцій, званихбазовими мікроопераціями,на основі яких можебути реалізований будь-який алгоритм обробки інформації;
запровадити ефективну систему схемного контролю базових мікрооперацій.
Як такі базові операції було обрано:
Перші дві операції було розглянуто нами вище.
Операціяпереміщенняє порозрядною двомісною операцієюM(A,B). Якщо коміркаAмає двійкову цифру 1 вk-му розряді, а коміркаBу цьому розряді має цифру 0, то в результаті операції переміщення цифра 1 з коміркиAпереміщається в коміркуB, а цифра 0 з коміркиВпереміщається в коміркуA.