Використання системи числення Фібаначчі

(Р = 2; Q = 8; тп = 3).

    Доказ. Запишемо вихідне число в розгорнутому вигляді в системах числення з основами Р і Q:

а0 + а^Р + а2Р2 + ... + а^Р”1 = Ъ0 + bxQ + b2Q2 + ... + ЪП2Яп>.

    Перетворимо вираз в лівій частині рівності наступним чином (розіб'ємо його на групи по m членів і замінимо Рm на Q):

(а0 + ахР + ... + ат_хРm *) + Рт(аm + “m+1Р + - + «а»-!*""1) + р2т(-) + ••• =

= Q°(a0 + аmр + ... + o,m_iPm~X)  + *m+хР + - + «2(-) + - •

   Покажемо, що будь-який многочлен в дужках строго менше Q. Для цього кожну цифру Р-ічної системи числення at замінимо на максимальну цифру [Р-1] алфавіту цієї системи:                                               

а0 + а1Р +... + ат_1Рm~1<(Р-1)(1 + Р + Р2 + ... +Рm~1) = (P-l)^rrr<Q.

   У наведених перетвореннях була застосована формула суми кінцевого числа елементів геометричної прогресії зі знаменником Р і першим членом, рівним одиниці.

    Отже, кожен многочлен в дужках при ступені Q можна записати у вигляді однієї цифри Q-ічної системи числення. В силу єдиності подання натуральних чисел в будь-якій системі числення:

  ао aip + ••• + аm-\Р ~ V

    аm + аm+1Р + - + a2i»-lРП~1 =^1.

  Теорема доведена.

   Теорема 2. Для того щоб перевести ціле число з системи числення з основою = Рт, де тп – натуральне число, в систему числення з основою Р, необхідно кожну Q-ічну цифру перевести в систему з основою Р і доповнити, якщо це необхідно, отримані числа зліва нулями так, щоб кожне число, за винятком самого лівого, складалося рівно з mn цифр .

   Наприклад:

7316 = 111 | 0011 = 11100112 (Р = 2; Q = 16; тп = 4).

   Доказ. Уявімо кожну цифру Ър i = 0, ..., п2,  у поданні вихідного числа в      Q-ічній системі числення в Р-ічній системі числення. Так як bt< Q = Рт, то максимальна кількість цифр в отриманому уявленні рівно m.

^00 + Ъ01Р + ^02 Р + ••• + ^0(т-1)Р + -Р>10 + ЬпР + + - + ь1(т-1)рт~1> + …

   Після розкриття дужок у силу єдиності подання чисел у Р-ічній системі числення отримуємо:

&00 = а0’ ^01 = av …’ ^10 = ат’ ^11 = am+v ’

   Теоремо доведена.

   Примітка. Аналогічні твердження справедливі також і для правильних дробів. Переклад дробової частини з Q-ічної системи в Р-ічну здійснюється, як і для цілих чисел. Незначущими в дробовій частині тепер є праві нулі в     Р-ічному поданні самої правої цифри дробової частини Q-ічного числа. При зворотному ж перекладі цифри Р-ічного дробу групуються за m штук зліва направо, починаючи з першої цифри після коми. Якщо остання група містить менше m цифр, то до неї додають праворуч відповідну кількість нулів.

    Приклад 5. Переведемо двійкове число 1010,000110112  у вісімкову систему числення.

    Для двійкої та вісімкової систем числення виконується співвідношення     Q = Рт, а саме 8 = 23. Отже, при перекладі будемо групувати цифри двійкового числа по три (в цілій частині - справа наліво, в дробовій частині - зліва направо): 1|010,|000|110|112 = 12,066g (остання група двійкових цифр була доповнена нулем праворуч).

   Відповідь: 1010,000110112 = 12,066g.

  Приклад 6. Переведемо число А, 1С16 з шістнадцятирічної системи числення в четвіркову.

   Для шістнадцятирічної  та четвіркової систем числення виконується співвідношення Q = Рт, а саме 16 = 42. Тому замінимо кожну 16-річну цифру її 4-ковим поданням, для чого використовуємо десяткову систему в якості проміжної: А1б = Ю10 = 224; С16 = = 1210 = 304. Тоді А,1С16 = 22,|01|304 (останній незначущий 0 можна опустити).

    Відповідь: А,1С1б = 22,0134.

Отримані результати для змішаних систем числення, таких що Pm = Q, мають ряд практичних застосувань.

1. Арифметичні дії над числами, записаними в одній з таких систем, ви можете виконувати в іншій системі, якщо остання більш зручна для вас. Наприклад, обчислення в 100-ічній системі замінюються на десяткову арифметику (100-ічні числа переводяться в десяткову систему, а результат при необхідності може бути знову записаний в 100-ічній), а дії з шестнадцятирічній або вісімковими числами легко замінюються на двійкову арифметику .
2. Заміна системи числення з меншою основою Р на систему з більшою основою Q = Рт забезпечує скорочення запису числа, зменшуючи кількість цифр в m разів. Наприклад, при використанні двійкової системи числення числа можна представляти в 16-річній, скоротивши кількість цифр у записі числа в 4 рази (16=24).
3. У деяких випадках вдається зробити більш раціональним рішення задачі переведення чисел з однієї системи в іншу, навіть якщо безпосередньо їх основи не пов'язані співвідношенням Q = Pm. Наприклад, при перекладі чисел з вісімкової системи в шістнадцятирічнуі навпаки зручно спочатку переписати число в двійковому вигляді (8 = 23  та 24 = 16).

   Приклад 7. Переведемо число BF3,616  у вісімкову систему числення:

BF3,616 = 1011|1111|0011,01102 = 101|111|110|011,0112 = 5763,38

 

РОЗДІЛ ІІІ. СИСТЕМИ ЧИСЛЕННЯ ТА АРХІТЕКТУРА КОМП’ЮТЕРІВ

 

    У кожній галузі науки і техніки існують фундаментальні ідеї чи принципи, які визначають її утримання і розвиток. У комп'ютерній науці роль таких фундаментальних ідей зіграли принципи, сформульовані незалежно один від одного двома найбільшими вченими XX століття – американським математиком і фізиком Джоном фон Нейманом і радянським інженером і вченим Сергієм Олександровичем Лебедевим.

   Центральне місце серед «принципів Неймана-Лебедева», що визначають архітектуру ЕОМ, займає пропозицію про використання двійкової системи числення. Ця пропозиція була обумовлена низкою обставин: простотою виконання арифметичних операцій у двійковій системі числення; її «оптимальним» узгодженням з булевої логікою; простотою технічної реалізації двійкового елемента пам'яті (тригера).

   Однак на певному етапі розвитку комп'ютерної техніки було виявлено, що використання класичної двійкової системи числення для подання інформації в комп'ютері має істотні недоліки. Першим з них є так звана проблема представлення негативних чисел. Другий недолік двійкової системи числення отримав назву нульовий надмірності.

    Як відомо, негативні числа безпосередньо не можуть бути представлені в двійковій системі числення, що використовує тільки дві цифри 0 і 1. Перед модулем від'ємного числа необхідно ставити знак «мінус». Це тягне за собою необхідність аналізувати знаки операндів при виконанні арифметичних операцій, що знижує швидкість обробки інформації. Для того щоб не виконувати аналіз операндів, був розроблений і реалізований спосіб представлення цілих негативних чисел у вигляді додаткового коду, що істотно спростило схему виконання арифметичних операцій, але ускладнило сприйняття записи негативних чисел.

    Другий недолік двійковій системи особливо неприємний при зберіганні і передачі двійкових кодів. Нульова надмірність (тобто відсутність надмірності) двійкового представлення означає, що в системі числення відсутній механізм виявлення помилок, які, на жаль, неминуче виникають в комп'ютерних системах під впливом зовнішніх і внутрішніх факторів.

    Суть цієї проблеми полягає в наступному. Нехай в процесі передачі або зберігання інформації, представленої, наприклад, двійковим кодом 10011010, під впливом зовнішніх або внутрішніх факторів відбулося спотворення інформації, і вона перейшла в кодову комбінацію 11010010 (спотворені розряди підкреслені). Оскільки комбінація 11010010 (як і будь-який інший двійковий код) є «дозволеною» в двійковій системі числення, то без додаткових дій неможливо визначити, відбулося спотворення інформації чи ні. Для вирішення цієї проблеми можна, наприклад, для кожного байта         (8 розрядів двійкового числа) підраховувати кількість одиниць, або для групи байтів підраховувати контрольну суму і т. д. У будь-якому випадку повинні бути використані спеціальні методи надлишкового кодування, що уповільнює роботу комп'ютера і вимагає додаткової пам'яті.

    В умовах, коли людство все більше і більше залежить від надійності роботи комп'ютерних систем (управління ракетами, літаками, атомними реакторами, банківськими системами), питання про ефективні механізми виявлення помилок висувається на передній план. Ясно, що для комп'ютерів, заснованих на двійковій системі числення, не завжди можна ефективно вирішувати цю проблему.

    Спроба подолати ці та інші недоліки двійкової системи числення стимулювала використання в комп'ютерах інших систем числення та розвиток власне теорії систем числення.

 

1. Використання врівноваженої трійкової системи числення.

 

    Для подолання недоліків використання двійкової системи для кодування інформації вже на етапі зародження комп'ютерної ери був виконаний ряд проектів і зроблено кілька цікавих математичних відкриттів, пов'язаних з системами числення. Мабуть, найбільш цікавим проектом в цьому відношенні є трійковий комп'ютер "Сетунь", розроблений в 1958р. в Московському державному університеті ім. М. В. Ломоносова під керівництвом Н. П. Брусенцова (Сетунь - назва річки, що протікає неподалік від МДУ).

    У ЕОМ «Сетунь» застосовувалася врівноважена (симетрична) трійкова система числення для подання чисел, використання якої вперше в історії комп'ютерів поставило знак рівності між поданням негативних і позитивних чисел, дозволило відмовитися від різних «хитрощів», що використовуються для представлення негативних чисел. Ця обставина, а також використання «трійкової логіки» при розробці програмного забезпечення привело до створення досить досконалою архітектури комп'ютера.

     ЕОМ «Сетунь» є найбільш яскравим прикладом, що підтверджує вплив системи числення на архітектуру комп'ютера!

    Визначення 2. Система числення з основою Р = 3 і цифрами 1, 0, 1, де 1 означає «мінус одиниця», називається врівноваженою трійковою або симетричною трійковою системою числення.

   Приклад 8. Наведемо приклади запису деяких чисел в врівноваженій трійковій системі:

Позитивні десяткові числа	Позитивні трійкові врівноважені числа	Негативні трійкові врівноважені числа	Негативні десяткові числа
1	1	1	-1
2	1 1	1 1	-2
3	1 0	1 0	-3
4	1 1	1 1	-4
5	1 1 1	1 1 1	-5
6	110	1 1 0	-6
7	111	1 1 1	-7
8	1 0 1	10 1	-8
9	10 0	10 0	-9
10	1 0 1	1 0 1	-10
11	111	1 1 1	-11
12	110	1 1 0	-12
13	111	1 1 1	-13
14	1111	1111	-14

 

    З наведеного прикладу зрозуміло, чому ця система числення називається врівноваженою або симетричною.

    Головна особливість врівноважених систем числення – при виконанні арифметичних операцій не використовується «правило знаків».

 

2. Використання системи числення Фібаначчі.

 

    На зорі комп'ютерної ери було зроблено ще два відкриття в області позиційних способів подання чисел, які, однак, маловідомі і в той період не привернули особливої уваги математиків і інженерів. Мова йде про властивості системи числення Фібоначчі та системи числення золотої пропорції.

    В останні десятиліття XX століття групою математиків під керівництвом професора А. П. Стахова в СРСР були отримані надзвичайно цікаві результати, пов'язані з вирішенням проблеми надійності зберігання, обробки і передачі інформації в комп'ютерних системах. Математиками було запропоновано використовувати в якості системи числення в комп'ютерах систему Фібаначчі. Нагадаємо, що алфавітом цієї системи є цифри 0 і 1, а базисом – послідовність чисел Фібоначчі: 1, 2, 3, 5, 8, 13, 21, 34 ....

    Основна перевага кодів Фібоначчі для практичних застосувань полягає в їх «природній» надмірності, яка може бути використана для цілей контролю числових перетворень. Ця надмірність проявляє себе у властивості множинності уявлень одного і того ж числа. Наприклад, число 30 в коді Фібоначчі має кілька виглядів:

30 = 1001101flb = 1010001/;ь = 111101^.

     При цьому різні кодові вигляди одного і того ж числа можуть бути отримані один з одного за допомогою спеціальних Фібоначчієвих операцій згортки (011 -> 100) і розгортки (100 - »011), виконуваних над кодовим зображенням числа. Якщо над кодовим зображенням виконати всі можливі згортки, то ми прийдемо до спеціального Фібоначчієвого зображення, так званою мінімальною формою, в якій немає двох поруч стоячих одиниць. Якщо ж у кодовому зображенні виконати всі можливі операції розгортки, то прийдемо до спеціального Фібоначчієвого зображення, так званому максимальної або розгорнутої форми, в якій поряд не зустрічаються два нуля.

    Аналіз Фібоначчієвої арифметики показав, що основними її операціями є операції згортки, розгортки і заснована на них операція приведення коду Фібоначчі до мінімальної форми.

    Ці математичні результати стали основою для проекту створення комп'ютерних і вимірювальних систем на основі системи числення Фібаначчі.

    При розробці елементної бази нової комп'ютерної техніки основним операційним елементом став пристрій приведення коду Фібоначчі до мінімальної форми. Це пристрій реалізовувся через RS і логічні елементи і/або. Були створені дослідні зразки мікросхеми, що виконує наступні операції: запис і читання даних, згортка, розгортка, переміщення, поглинання, приведення до мінімальної форми, підсумовування, віднімання, реверсивний зсув, логічне множення, логічне додавання і додавання по модулю 2.