Двійкова система числення

Двійкова система числення - це позиційна система числення з основою 2. У цій системі числення, числа записуються за допомогою двох символів (0 і 1).

1. Історія

• Повний набір з 8 триграм і 64 гексаграмм, аналог 3-бітних і 6-бітних цифр, був відомий в древньому Китаї в класичних текстах книги Змін. Порядок гексаграмм в книзі Змін, розташованих у відповідності зі значеннями відповідних двійкових цифр (від 0 до 63), і метод їх отримання був розроблений китайським вченим і філософом Шао Юн в XI столітті. Проте немає доказів, що свідчать про те, що Шао Юн розумів правила двійковій арифметики, розташовуючи двохсимвольного кортежі в лексикографічному порядку.

• Індійський математик Пінгала ( 200 рік до н.е..) розробив математичні основи для опису поезії з використанням першого відомого застосування двійкової системи числення. ^{[1] [2]}

• Прообразом баз даних, широко використовувалися в Центральних Андах ( Перу, Болівія) у державних та громадських цілях в I-II тисячолітті н. е.., була вузликова писемність Інків - стос, що складалася як з числових записів десяткової системи ^[3], так і не числових записів у двійковій системі кодування ^[4]. У стос застосовувалися первинні та додаткові ключі, позиційні числа, кодування кольором та освіта серій повторюваних даних ^[5]. Стос вперше в історії людства використовувалося для застосування такого способу ведення бухгалтерського обліку як подвійний запис ^[6].

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

• В 1605 Френсіс Бекон описав систему, літери алфавіту якої можуть бути зведені до послідовностей двійкових цифр, які в свою чергу можуть бути закодовані як ледь помітні зміни шрифту в будь-яких випадкових текстах. Важливим кроком у становленні загальної теорії двійкового кодування є зауваження про те, що вказаний метод може бути використаний стосовно будь-яких об'єктів. ^[7] (Див. Шифр Бекона)

• Сучасна двійкова система була повністю описана Лейбніцем в XVII столітті в роботі Explication de l'Arithmtique Binaire ^[8]. В системі числення Лейбніца були використані цифри 0 і 1, як і в сучасній двійковій системі. Як людина, що захоплюється китайською культурою, Лейбніц знав про книзі Змін і зауважив, що гексаграми відповідають двійковим числах від 0 до 111 111. Він захоплювався тим, що це відображення є свідченням великих китайських досягнень у філософській математики того часу. ^[9]

• В 1854 англійський математик Джордж Буль опублікував знакову роботу, що описує алгебраїчні системи стосовно до логіці, яка в даний час відома як Булева алгебра або алгебра логіки. Його логічного обчисленню судилося зіграти важливу роль у розробці сучасних цифрових електронних схем.

• В 1937 Клод Шеннон предствить до захисту кандидатську дисертацію Символічний аналіз релейних і перемикальних схем в MIT, в якій булева алгебра і двійкова арифметика були використані стосовно до електронних реле і перемикачів. На дисертації Шеннона по суті заснована вся сучасна цифрова техніка.

• У листопаді 1937 Джордж Штібіц, згодом працював у Bell Labs, створив на базі реле комп'ютер "Model K" (від англ. "K itchen", кухня, де проводилася збірка), який виконував двійкове додавання. В кінці 1938 року Bell Labs розгорнула дослідницьку програму на чолі зі Штібіцом. Створений під його керівництвом комп'ютер, завершений 8 січня 1940, умів виконувати операції з комплексними числами. Під час демонстрації на конференції American Mathematical Society в Дармутском коледжі 11 вересня 1940 Штібіц продемонстрував можливість посилки команд віддаленого калькулятору комплексних чисел по телефонній лінії з використанням телетайпа. Це була перша спроба використання віддаленої обчислювальної машини за допомогою телефонної лінії. Серед учасників конференції, колишніх свідками демонстрації, були Джон фон Нейман, Джон мокли і Норберт Вінер, згодом писали про це у своїх мемуарах.

2. Запис двійкових чисел

Двійкова система числення є окремим випадком здвоєних двійкових показових позиційних систем числення з обома підставами (a і b) рівними 2. Цілі числа записуються у вигляді:

де:

• - Репрезентована число,
• - Запис числа, рядок цифр і знаків,
• - Число цифр (знаків) в числі x _2,2,
• - Порядковий номер цифри,
• - Цифри числа x _2,2 з безлічі a = {0,1}, вагові коефіцієнти, у двійковій системі числення підставу внутріразрядной системи числення дорівнює 2,
• - Підстава показовою вагової функції, підстава міжрозрядної системи числення.

Цілі числа є приватними сумами степеневого ряду :

в якому коефіцієнти a _n беруться з кільця R = a {0,1}, X = 2, n = k, а верхня межа в приватних сумах обмежений з до - n-1.

Підстава показовою функції - b визначає лише діапазон представляються числами x _{2, b} величин.
Число записуваних кодів від підстави показовою функції - b не залежить.
Число записуваних кодів залежить від основи внутріразрядной системи числення - a, визначається в комбінаториці і дорівнює числу розміщень з повтореннями :

де a = 2 - 2-х елементне безліч a = {0,1} з якого беруться цифри a _k, n - число елементів (цифр) в числі x _{2, b.}

Дробові числа записуються у вигляді:

де:

• - Число цифр дробової частини числа,
• - Вагові коефіцієнти з безлічі , Підстава внутріразрядной системи числення дорівнює 2,
• - Підстава показовою вагової функції, підстава міжрозрядної системи числення.

Слід зазначити, що число може бути записано в двійковому вигляді, а система числення при цьому може бути не двійковій, з іншою підставою. Приклад: двійково-десяткове кодування, в якому десяткові цифри записуються у двійковому вигляді, а система числення - десяткова.

3. Додавання, віднімання і множення двійкових чисел

Таблиця складання

Приклад складання "стовпчиком" (14 + 5 = 19):

Таблиця віднімання

Таблиця множення

Приклад множення "стовпчиком" (14 5 = 70):

4. Перетворення чисел

Для перетворення з двійкової системи в десяткову використовують наступну таблицю ступенів підстави 2:

Починаючи з цифри 1 всі цифри множаться на два. Точка, яка стоїть після 1, називається двійковій крапкою.

4.1. Перетворення двійкових чисел в десяткові

Припустимо, вам дано двійкове число 110001. Для перекладу на десяткове просто запишіть його справа наліво як суму за розрядами наступним чином:

.

Можна записати це у вигляді таблиці наступним чином:

Точно так же, починаючи з двійковою точки, рухайтеся справа наліво. Під кожною двійковій одиницею напишіть її еквівалент в рядку нижче. Складіть отримані десяткові числа.
Таким чином, двійкове число 110001 рівнозначно десятковому 49.

4.2. Перетворення методом Горнера

Переклад цілих чисел методом Горнера Для того, щоб перетворювати числа з двійкової в десяткову систему даним методом, треба підсумувати цифри зліва направо, множачи раніше отриманий результат на основу системи (в даному випадку 2). Наприклад, бінарне число 1011011 переводиться в десяткову систему так: 0 * 2 + 1 = 1>> 1 * 2 + 0 = 2>> 2 * 2 + 1 = 5>> 5 * 2 ​​+ 1 = 11>> 11 * 2 + 0 = 22>> 22 * 2 + 1 = 45>> 45 * 2 ​​+ 1 = 91 Тобто в десятковій системі це число буде записано як 91. Або число 101111 переводиться в десяткову систему так: 0 * 2 + 1 = 1>> 1 * 2 + 0 = 2>> 2 * 2 + 1 = 5>> 5 * 2 ​​+ 1 = 11>> 11 * 2 + 1 = 23>> 23 * 2 + 1 = 47 Тобто в десятковій системі це число буде записано як 47. Переклад дробових чисел методом Горнера 1) 0,1101 ₂ = 0, X ₁₀ (розглядаємо цифри в зворотному порядку)
1:2 = 0,5
0,5 +0 = 0,5
0,5:2 = 0,25
0,25 +1 = 1,25
1,25:2 = 0,625
0,625 +1 = 1,625
1,625:2 = 0,8125
Відповідь: 0,1101 ₂ = 0,8125 ₁₀
2) 0,356 ₈ = 0, X ₁₀ (розглядаємо цифри в зворотному порядку)
6:8 = 0,75
0,75 +5 = 5,75
5,75:8 = 0,371875
0,371875 +3 = 3,371875
3,371875:8 = 0,46484375
Відповідь: 0,356 ₈ = 0,46484375 ₁₀
3) 0, A6E ₁₆ = 0, X ₁₀ (розглядаємо цифри в зворотному порядку)
14:16 = 0,875
0,875 +6 = 6,875
6,875:16 = 0,4296875
0,4296875 +10 = 10,4296875
10,4296875:16 = 0,65185546875
Відповідь: 0, A6E ₁₆ = 0,65185546875 ₁₀

4.3. Перетворення десяткових чисел у двійкові

Припустимо, нам потрібно перевести число 19 в двійкове. Ви можете скористатися такою процедурою:

 19 / 2 = 9 із залишку 1 9 / 2 = 4 c залишком 1 4 / 2 = 2 без залишку 0 2 / 2 = 1 без залишку 0 1 / 2 = 0 з залишку 1 

Отже, ми ділимо кожне приватне на 2 і записуємо залишок у кінець двійковій запису. Продовжуємо поділ до тих пір, поки в приватному не буде 0. Результат записуємо справа наліво. Тобто нижнє число буде самим лівим і.т.д. В результаті отримуємо число 19 в двійковій запису: 10011.

4.4. Перетворення дрібних двійкових чисел в десяткові

Потрібно перевести число 1011010.101 в десяткову систему. Запишемо це число наступним чином:

4.5. Перетворення дрібних десяткових чисел у двійкові

Переклад дробового числа з десяткової системи числення в двійкову здійснюється за наступним алгоритмом:

• Спочатку перекладається ціла частина десяткового дробу в двійкову систему числення;
  
• Потім дробова частина десяткового дробу множиться на основу двійкової системи числення;
  
• В отриманому творі виділяється ціла частина, яка приймається як значення першого після коми розряду числа в двійковій системі числення;
  
• Алгоритм завершується, якщо дробова частина отриманого твори дорівнює нулю або якщо досягнута необхідна точність обчислень. В іншому випадку обчислення тривають з попереднього кроку.
  

Приклад: Потрібен перевести дробове десяткове число 206,116 в дробове двійкове число.

Переклад цілої частини дає 206 ₁₀ = 11001110 ₂ по раніше описаним алгоритмам; дробову частину множимо на підставу 2, заносячи цілі частини твору в розряди після коми шуканого дробового двійкового числа:

.116 2 = 0.232
.232 2 = 0.464
.464 2 = 0.928
.928 2 = 1856
.856 2 = 1.712
.712 2 = 1.424
.424 2 = 0.848
.848 2 = 1.696
.696 2 = 1.392
.392 2 = 0.784
і т. д.
Отримаємо: 206,116 ₁₀ = 11001110,0001110110 ₂

5. Застосування

5.1. У цифрових пристроях

Двійкова система використовується в цифрових пристроях, оскільки є найбільш простий і відповідає вимогам:

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

У цифровій електроніці одному двійковому розряду в двійковій системі числення відповідає (очевидно) один двійковий розряд двійкового регістра, тобто двійковий тригер з двома станами (0,1).

5.2. В англійській системі мір

При вказівці лінійних розмірів у дюймах за традицією використовують двійкові дроби, а не десяткові, наприклад: 5 ", 7 ¹⁵ / _16", 3 ¹¹ / ₃₂ "і т. д.

6. Приклади чисел-ступенів двійки

Примітки