Системи числення та архітектура комп'ютера

Размещено на http://www.allbest.ru/

Зміст

Вступ

Розділ І. Перевід чисел з десяткової системи числення в р-ічну

1.1 Два способи переводу цілих чисел

1.2 Перевід кінцевих десятинних дробів

Розділ ІІ. Змішані системи числення

Розділ ІІІ. Системи числення та архітектура комп'ютерів

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

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

3.3 Недвійкова комп'ютерна арифметика

Висновки

Список використаних джерел

Вступ

Однією з формальних мов є система числення.

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

Найпростішим способом запису натурального числа є зображення його за допомогою відповідної кількості паличок або рисочок. Таким способом можна користуватися для невеликих чисел.

Розрізняють такі типи систем числення:

§ непозиційні

§ позиційні;

§ змішані.

Позиційна система числення - система числення, в якій значення кожної цифри залежить від місця в послідовності цифр у записі числа. Для позиційних систем числення характерні наочність зображення чисел і відносна простота виконання операцій.

У позиційних системах числення одна і та ж цифра (числовий знак) у записі числа набуває різних значень залежно від своєї позиції. Таким чином, позиція цифри має вагу у числі. Здебільшого вага кожної позиції кратна деякому натуральному числу b (b>1), яке називається основою системи числення.

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

Винахід позиційної системи числення, заснованої на помісному значенні цифр, приписують шумерам і вавилонцям. Її було розвинуто індусами і вона отримала неоціненні наслідки для історії людської цивілізації.

Для запису чисел системи числення з основою до 36 включно у якості цифр використовуються арабські цифри (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) а потім букви латинського алфавіту (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z). При цьому, a = 10, b = 11 і т.д.

Також поширені системи числення з основами:

§ 2 - двійкова (у дискретній математиці, інформатиці, програмуванні)

§ 8 - вісімкова (у програмуванні)

§ 12 - дванадцятирічна (мала широке застосування у давнину, подекуди використовується і нині)

§ 16 - шістнадцятирічна (поширена у програмуванні, а також для кодування шрифтів)

§ 60 - шістдесяткова (для виміру кутів і, зокрема, довготи і широти)

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

Найбільшого поширення в ЕОМ отримали 2 типи архітектури: прінстонська (фон Неймана) і гарвардська. Обидві вони виділяють 2 основних вузли ЕОМ: центральний процесор і пам'ять комп'ютера. Різниця полягає в структурі пам'яті: в прінстонській архітектурі програми і дані зберігаються в одному масиві пам'яті і передаються в процесор одним каналом, тоді як гарвардська архітектура передбачає окремі сховища і потоки передачі для команд і даних.

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

За перерахованими ознаками та їх поєднаннями серед архітектури виділяють:

· За розрядністю інтерфейсів і машинних слів: 8 -, 16 -, 32 -, 64-розрядні (ряд ЕОМ має й інші розрядності);

· За особливостями набору регістрів, формату команд і даних: CISC, RISC, VLIW;

· За кількістю центральних процесорів: однопроцесорні, багатопроцесорні, суперскалярні;

· багатопроцесорні за принципом взаємодії з пам'яттю: симетричні багатопроцесорні (SMP), масивно-паралельні (MPP), розподілені.

Розділ І. Перевід чисел з десяткової системи числення в p-ічну

1.1 Два способи переводу цілих чисел

Спосіб 1. Перевід діленням на Р із залишком.

Запишемо число а в Р-ічной системі числення в розгорнутій формі:

а = апРп + ап_гРп 1 + ... + агР + а0,

де ап, an_v ... av а0 поки невідомі. Тоді, розділивши а на Р із залишком, отримуємо цілу частку:

апРп~х + ап_хРп~г + ... + аа (1.1)

і а0 в залишку, що не перевищує Р- 1. Таким чином, ми визначили останню цифру в Р-ічной записі чісла а. Розділивши отриману частку (1.1) знову на Р, отримаємо в залишку значення ау. Нова частка: anPn ~ 2 + + o, n-iPn1 + . . . + #2. Таким чином, ми визначили передостанню цифру в Р-ічному записі числа а. Продовжуємо цей процес, поки частка при діленні на ціле число стане рівно нулю. Більш формально даний спосіб можна записати у вигляді наступного алгоритму.

Алгоритм переводу цілого числа з десяткової системи числення в Р-ічную.

1. Ділимо вихідне число а на Р остачі в десятковій системі числення і записуємо в якості нового значення десяткового числа а цілу частину результату від ділення.

2. Залишок від ділення замінюємо на відповідну цифру в Р-ічной системі числення і приписуємо її зліва до отриманих раніше цифрам Р-ічного запису числа а (перша отримана цифра відповідає меншому розряду).

3. Виконуємо пункти 1 і 2, до тих пір поки число а не стане рівним 0.

Приклад 1. Переведемо число 123 в трійкову систему числення.

123:3=41 (0) У дужках вказані залишки від ділення

41:3=13 (3) на ціле число, які є відповідними

13:3=4 (1) трійковому вигляду числа.

4:3=1 (1)

1:3=0 (1)

Відповідь: 123 = 111 203

Переведемо це ж число в шістнадцятирічну систему числення.

123:16 = 7 (11)

7:16 = 0 (7)

Замінимо число 11 на шістнадцятирічну цифру.

Відповідь: 123 = 7В1б.

Спосіб 2. Цей спосіб заснований на виділенні максимального ступеня числа Р у вихідному десятковому числі.

Замінимо в розгорнутій формі запису числа в Р-ічній системі всі цифри на максимальну (рівну Р-1) і покажемо, що і в цьому випадку число строго менше, ніж Pn + 1. Очевидно, що таке число також не менше, ніж Рn, так як аn > 1.

Рп < апРп + а^Р^1 + ... + агР + а0 <(Р-1)- Рл + (Р-1)-Рл_1 + ... + (Р-1)-Р +

+ (Р-1) = Pп+1 - 1 < Pп+1

Останню рівність отримано з використанням формули суми кінцевого числа членів геометричної прогресії. Для знаходження більшої цифри (аn) в Р-ічному записі числа необхідно знайти такий ступінь числа Р, для якої виконуються нерівності: Рп< а< Рп+1, тобто аn дорівнюватиме цілій частині від ділення а на Рn. Залишком ж від такого поділу є число ал_1Рл_1 + ... + + ахР + а0 > 0. Позначимо його, як і раніше, а. Якщо воно дорівнює нулю, то і всі цифри ап1, ... av а0 рівні 0, і обчислення закінчуються, в іншому випадку ми знову шукаємо максимальний ступінь k числа Р, для якої справедливо:

Р* < а^ри'1 + ... + ахР + a0Pk+1 < Рп.

Тоді n -1 - k наступних за аn цифр будуть рівні нулю (при n - 1 = k нульові цифри між аn і аk відсутні, а аk отримуємо в результаті поділу без остачі а на Р. Поки залишок від такого поділу не стане дорівнювати нулю, будемо продовжувати описані дії.

Приклад 2. Переведемо другим способом число 100 в двійкову систему числення.

Використовуючи таблицю двійкових ступенів, запишемо нерівності: 26 <100 <27. Отже, двійковий запис числа 100 складатиметься з 7 цифр. Ціла частина від ділення 100 на 26 дорівнює 1, тобто більша цифра шуканого числа дорівнює 1. Залишок від ділення 100 на 26 дорівнює 36. Так як 25 < 36 < 26, то і друга зліва цифра дорівнює одиниці. Залишок же від ділення 36 на 2 дорівнює 4 = 2, тобто третя і четверта, а також шоста і сьома цифри в двійковому записі числа 100 нульові.

Відповідь: Ю010 = 11001002.

Приклад 3. Переведемо в шістнадцятирічну систему числення число 525.

Використовуючи таблицю ступенів числа 16, запишемо нерівності: 16 << 525 < 16. Отже, запис числа 525 в шістнадцятирічній системі матиме три цифри. Розділимо 525 на 256, отримаємо частку 2 і в залишку 13, таким чином більша цифра в шістнадцятирічному записі - 2. В силу того, що 13< <16, друга цифра в шістнадцятирічному вигляді дорівнює 0, а меншою цифрою є [13], вона позначається символом D.

Відповідь: 52510 = 20D16.

Зауважимо, що другий спосіб переводу ефективний лише тоді, коли нам уже відомі значення всіх ступенів числа Р, які не перевищують вихідне число. Але перевага такого методу полягає в природному порядку записи одержані Р-ічних чисел (зліва направо), що буває важливо при програмуванні: чергова отримана цифра відразу ж може виводитися на друк. У першому ж способі перекладу всі цифри треба попередньо запам'ятати для подальшого роздруковки результату в порядку, зворотному їх отриманню.

1.2 Перевід кінцевих десяткових дробів

В цьому пункті ми розглянемо перевід тільки кінцевих десяткових дробів.

Якщо в дробу є ненульова ціла частина, то вона переводиться з десяткової системи в Р-ічну окремо. Сформулюємо правила переводу дробової частини.

Даний правильний кінцевий десятковий дріб. Припустимо , що в Р-ічній системі наш дріб Комерсант має вигляд b =0,Ъ_хЪ_2...Ък... (в Р-ічній системі дріб може виявитися нескінченним). Необхідно знайти цифри b_v Ъ_2> ... > >Ъ_к, ... .

Запишемо десятковий дріб Ъ в розгорнутій формі в Р-ічній системі числення:

Ъ = Ь_гР-1 + Ь_2Р-2 + ... + Ъ_кР~к + ... . (1.2)

Помножимо ліву (саме число) і праву частини виразу (1.2) на Р. У правій частині одержимо:

Ь_! + Ь_2Р~1 + ... + b_kP'k+1 + ..., (1.3)

значить, перша цифра дробової частини числа Ъ в Р-ічній системі дорівнює цілій частині результату множення десяткового дробу Ь на Р. Дробову частину результату множення позначимо через Ъ, тобто . Ь = Ъ^1 + ... + +Ь_кР~к+1 + ..., і знову помножимо отриману рівність на Р. В результаті праворуч отримаємо: Ъ_2 + &_3Р 1 + ... + Ъ_кР~к+2 ..., і ціла частина результату в лівій частині буде дорівнювати Ъ_2 (друга шукана цифра). Цей процес необхідно продовжувати до тих пір, поки дробова частина результату множення лівої частини на Р не дорівнюватиме нулю або не буде виділений період з повторюваних цифр Ь_г. Іноді процес можна перервати раніше, коли вже досягнута необхідна точність обчислень.

Сформулюємо описані вище правила перекладу десяткових дробів в Р-ічну систему у вигляді алгоритму.

Алгоритм перекладу правильних кінцевих десяткових дробів в Р-ічну систему числення

Приклад 3. Переведемо число 0,375 в двійкову систему:

0,375-2=0,75 -- перша цифра результату

0,75-2=1,5 -- друга цифра результату

0,5-2=1,0 -- остання цифра результату

Відповідь: 0,375 = 0,011₂

Переведемо число 0,515625 в четвіркову систему.

0,515625-4 = 2,0625

0,0625-4=0,25

0,25-4=1,0

Відповідь: 0,515625 = 0,201₄.

Приклад 4. Переведемо число 0,123 в п'ятіркову систему.

0,123-5=0,615 0

0,615-5=3,075 3

0,075-5=0,375 0

0,375-5=1,875 1

0,875-5 = 4,375 4

Дробова частина останнього виразу, рівна вже зустрічалася раніше, дробової частини, отже, останні дві цифри утворюють період п'ятіркового дробу.

Розділ ІІ. Змішані системи числення

У деяких випадках числа, задані в системі числення з основою Q, доводиться зображати за допомогою цифр в інший Р-ічній системі числення.

Визначення 1. Системи числення, в яких кожен коефіцієнт розкладання числа за ступенями Q (цифра Q-ічної системи числення) записується в Р-ічній системі числення, називаються змішаними. Інакше такі системи називають P-Q-ічними.

Наприклад, раніше широке поширення в обчислювальній техніці мала двійково-десяткова система. У двійково-десятковій системі числення основою системи числення є число 10, але всі десяткові цифри окремо кодуються чотирма двійковими цифрами і в такому вигляді записуються послідовно один за одним. Так, число 83910 в двійково-десятковій системі числення буде записуватися як 100000111001₂_₁₀. Зауважимо, що таке подання володіє надмірністю, оскільки чотири двійкові цифри можуть кодувати не 10, а 16 різних чисел.

Особливий інтерес представляє випадок, коли

Q=P^m,

де m n - натуральне число. Для таких систем вид числа в P-Q-ічній системі збігається з видом числа в Р-ічній системі. Тоді перевод чисел з Р-ічної системи числення в Q-ічну і навпаки може проводитися за більш простим алгоритмам (сформулюємо і доведемо їх поки тільки для цілих чисел).

Теорема 1. Для того щоб перевести ціле число з системи числення з основою Р в систему числення з основою Q = Р^т, де т - натуральне число, достатньо записати числа в Р-ічній системі розбити на групи по т п цифр, починаючи з правої цифри, і кожну таку групу замінити однією цифрою в Q-ічній системі. наприклад: 10101₂ = 10|101 = 25_g

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

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

а₀ + а^Р + а₂Р² + ... + а^Р”¹ = Ъ₀ + b_xQ + b₂Q² + ... + Ъ_П2Я^п>.

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

(а₀ + а_хР + ... + а_т__хР^m *) + Р^т(^аm + “_m+1^Р + - + «а»-!*""¹) + ^р2т(-) ⁺ *** =

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

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

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

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

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

^ао aip + *** + аm-\Р ~ V

^аm + ^аm₊1^Р + - + a₂i»-lР^П~¹ =^1.

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

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

Наприклад:

73₁₆ = 111 | 0011 = 1110011₂ (Р = 2; Q = 16; тп = 4).

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

^00 ^{+ Ъ}01^{Р +} ^02 Р + *** + ^0(т-1)Р ⁺ -Р>10 + ЬпР + + - + ^ь1(т-1)^рт~¹> + …

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

&00 ^{= а}0' ^01 ^{= a}v …' ^10 ^{= а}т' ^11 ^{= a}m+v '

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

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

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

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

Відповідь: 1010,00011011₂ = 12,066_g.

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

Для шістнадцятирічної та четвіркової систем числення виконується співвідношення Q = Р^т, а саме 16 = 4². Тому замінимо кожну 16-річну цифру її 4-ковим поданням, для чого використовуємо десяткову систему в якості проміжної: А_1б = Ю₁₀ = 22₄; С₁₆ = = 12₁₀ = 30₄. Тоді А,1С₁₆ = 22,|01|30₄ (останній незначущий 0 можна опустити).

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

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

1. Арифметичні дії над числами, записаними в одній з таких систем, ви можете виконувати в іншій системі, якщо остання більш зручна для вас. Наприклад, обчислення в 100-ічній системі замінюються на десяткову арифметику (100-ічні числа переводяться в десяткову систему, а результат при необхідності може бути знову записаний в 100-ічній), а дії з шестнадцятирічній або вісімковими числами легко замінюються на двійкову арифметику .

2. Заміна системи числення з меншою основою Р на систему з більшою основою Q = Р^т забезпечує скорочення запису числа, зменшуючи кількість цифр в m разів. Наприклад, при використанні двійкової системи числення числа можна представляти в 16-річній, скоротивши кількість цифр у записі числа в 4 рази (16=2⁴).

3. У деяких випадках вдається зробити більш раціональним рішення задачі переведення чисел з однієї системи в іншу, навіть якщо безпосередньо їх основи не пов'язані співвідношенням Q = P^m. Наприклад, при перекладі чисел з вісімкової системи в шістнадцятирічну і навпаки зручно спочатку переписати число в двійковому вигляді (8 = 2³ та 2⁴ = 16).

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

BF3,6₁₆ = 1011|1111|0011,0110₂ = 101|111|110|011,011₂ = 5763,3₈

Розділ ІІІ. Системи числення та архітектура комп'ютерів

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

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

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

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

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

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

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

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

3.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

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

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

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

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

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

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

30 = 1001101_flb = 1010001_/;ь = 111101^.

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

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

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

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

Відмінною особливістю мікросхеми була наявність контрольного виходу, на якому формувалася інформація про неправильну роботу мікросхеми.

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

І хоча створити фібоначчі-комп'ютер з різних причин поки так і не вдалося, теоретичні основи даного напрямку становлять безсумнівний інтерес і можуть стати джерелом нових ідей не тільки в комп'ютерній області, а й в області математики. Особливо ефективним вважається використання «фібоначчієвих» уявлень у вимірювальній техніці і цифровій обробці сигналів.

3.3 Недвійкова комп'ютерна арифметика

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

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

Система залишкових класів (СОК) - це непозиційних система числення, числа в якій представляються залишками від ділення на обрану систему підстав система залишкових класів (СОК) - це непозиційних система числення, числа в якій представляються залишками від ділення на обрану систему підстав P_v Р₂, ..., Р_п і є взаємно простими числами. Операції додавання, віднімання та множення над числами в СОК здійснюються незалежно по кожній підставі без переносів між розрядами.

Такі операції, як ділення, порівняння та ін., Що вимагають інформації про величину всього числа, в СОК виконуються по більш складним алгоритмам. І в цьому полягає суттєвий недолік даної системи числення, стримуючий її широке застосування в якості комп'ютерної. Однак сьогодні в сучасних комп'ютерах при роботі з великими і супервеликими числами використовують СОК, бо тільки СОК-арифметика дозволяє отримувати результати обчислень в реальному часі.

У таких випадках в якості підстав СОК беруть величини, близькі до 2^т (тп - двійкова розрядність комп'ютера), наприклад, 2^m_1 - 1, 2^m_1, 2^m~ + 1 і т. д. Починаючи з середини минулого століття вчені багатьох країн світу, включаючи і нашу, займаються проблемою підвищення швидкості «незручних» операцій в СОК. Сама ж система залишкових класів застосовується в обчислювальних системах досить широко вже кілька десятиліть.

числення код комп'ютерний арифметика

Висновки

Є два способи переводу цілих чисел:

Спосіб 1. Перевід діленням на Р із залишком.

Спосіб 2. Спосіб заснований на виділенні максимального ступеня числа Р у вихідному десятковому числі.

У деяких випадках числа, задані в системі числення з основою Q, доводиться зображати за допомогою цифр в інший Р-ічній системі числення.

Особливий інтерес представляє випадок, коли Q=P^m, де m n - натуральне число. Для таких систем вид числа в P-Q-ічній системі збігається з видом числа в Р-ічній системі. Тоді перевод чисел з Р-ічної системи числення в Q-ічну і навпаки може проводитися за більш простим алгоритмам (сформулюємо і доведемо їх поки тільки для цілих чисел).

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

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

^ао aip + *** + аm-\Р ~ V

^аm + ^аm₊1^Р + - + a₂i»-lР^П~¹ =^1.

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

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

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

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

Список використаних джерел

1. Є.В. Андрєєва, Л.Л. Босова, І.М. Фаліна Навчальний посібник “Математичні основи інформатики”. Москва: БІНОМ. Лабораторія знань, 2005.

Размещено на Allbest.ru