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

Материал из Википедии — свободной энциклопедии

Текущая версия [показать стабильную версию] (сравнить)

Данная версия страницы не проверялась участниками с соответствующими правами. Вы можете прочитать последнюю проверенную или т. н. стабильную версию от 25 октября 2009, однако она может значительно отличаться от текущей версии. Проверки требуют 48 правок.

Перейти к: навигация, поиск

Двоичная система счисления — это позиционная система счисления с целочисленным основанием 2. В этой системе счисления натуральные числа записываются с помощью всего лишь двух символов (в роли которых обычно выступают цифры 0 и 1).

Содержание

1 История
2 Запись двоичных чисел
3 Таблицы умножения и сложения двоичных чисел
4 Преобразование чисел
5 Двоичные показательные позиционные системы счисления с основанием показательной функции не равной 2
6 Сравнение с другими системами счисления
7 Применения
- 7.1 В цифровых устройствах
- 7.2 В английской системе мер
8 См. также
9 Ссылки

[править] История

Полный набор из 8 триграмм и 64 гексаграмм, аналог 3-битных и 4-битных цифр, был известен в древнем Китае в классических текстах книги Перемен. Порядок гексаграмм в книге Перемен, расположенных в соответствии со значениями соответствующих двоичных цифр (от 0 до 63), и метод их получения был разработан китайским учёным и философом Шао Юн в XI веке. Однако нет доказательств, свидетельствующих о том, что Шао Юн понимал правила двоичной арифметики, располагая двухсимвольные кортежи в лексикографическом порядке.

Индийский математик Пингала (200 год до н.э.) разработал математические основы для описания поэзии с использованием первого известного применения двоичной системы счисления.^[1]^[2]

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

В 1605 году Френсис Бэкон описал систему, буквы алфавита которой могут быть сведены к последовательностям двоичных цифр, которые в свою очередь могут быть закодированы как едва заметные изменения шрифта в любых случайных текстах. Важным шагом в становлении общей теории двоичного кодирования является замечание о том, что указанный метод может быть использован применительно к любым объектам.^[3] (См. Шифр Бэкона)

Современная двоичная система была полностью описана Лейбницом в XVII веке в работе Explication de l'Arithmétique Binaire^[4]. В системе счисления Лейбница были использованы цифры 0 и 1, как и в современной двоичной системе. Как человек, увлекающийся китайской культурой, Лейбниц знал о книге Перемен и заметил, что гексаграммы соответствуют двоичным числам от 0 до 111111. Он восхищался тем, что это отображение является свидетельством крупных китайских достижений в философской математике того времени.^[5]

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

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

В ноябре 1937 Джордж Штибиц, впоследствии работавший в Bell Labs, создал на базе реле компьютер "Model K" (от англ. "Kitchen", кухня, где производилась сборка), который выполнял двоичное сложение. В конце 1938 Bell Labs развернула исследовательскую программу во главе со Штибицом. Созданный под его руководством компьютер, завершённый 8 января 1940, умел выполнять операции с комплексными числами. Во время демонстрации на конференции American Mathematical Society в Дармутском колледже 11 сентября 1940 Штибиц продемонстрировал возможность посылки команд удалённому калькулятору комплексных чисел по телефонной линии с использованием телетайпа. Это была первая попытка использования удалённой вычислительной машины посредством телефонной линии. Среди участников конференции, бывших свидетелями демонстрации, были Джон фон Нейман, Джон Мокли и Норберт Винер, впоследствии писавшие об этом в своих мемуарах.

[править] Запись двоичных чисел

Двоичная система счисления является частным случаем сдвоенных двоичных показательных позиционных систем счисления с обоими основаниями (a и b) равными 2. Целые числа записываются в виде:
$x_{2,2} = (a_{n-1} a_{n-2}\dots a_{1} a_{0})_{2,2} = \sum_{k=0}^{n-1} a(2)_k b^k$ , где:
n - число цифр (знаков) в числе x_2,2,
k - порядковый номер цифры,
a=2 - множество a{0,1} из которого берутся a_k, основание внутриразрядной системы счисления,
a_k - цифры числа x_2,2 из множества a{0,1},
b=2 - основание показательной функции, основание межразрядной системы счисления.
Целые числа являются частными суммами степенного ряда:
$F(X) = \sum\limits_{n=0}^{\infty}a_nX^n,$ в котором коэффициенты a_n берутся из кольца R=a{0,1}, X=2, n=k, а верхний предел в частных суммах ограничен с $\infty$ до - n-1.
Из комбинаторики известно, что число записываемых чисел (кодов) не зависит от основания показательной функции - b, которое определяет диапазон представляемых числами x_2,b величин, и равно числу размещений с повторениями:
$\bar{A}(a,n)=\bar{A}_a^n=a^n=2^n$ , где:
a=2 - 2-х элементное множество a{0,1} из которого берутся цифры a_k, n - число элементов (цифр) в числе x_2,b.

Дробные числа записываются в виде:
$x_{2,2} = (a_{n-1} a_{n-2}\dots a_{1} a_{0},a_{-1} a_{-2}\dots a_{-(m-1)} a_{-m})_{2,2} = \sum_{k=-m}^{n-1} a(2)_k b^k$ , где:
m - число цифр дробной части числа,
a=2 - основание внутриразрядной системы счисления,
b=2 - основание показательной функции, основание межразрядной системы счисления.
Следует отметить, что число может быть записано в двоичном виде, а система счисления при этом может быть не двоичной, с другим основанием. Пример: двоично-десятичное кодирование, в котором десятичные цифры записываются в двоичном виде, а система счисления - десятичная.

[править] Таблицы умножения и сложения двоичных чисел

×	0	1
0	0	0
1	0	1

соответствует булевой функции f_{(2,1,8)₁₀},

+	0	1
0	0	1
1	1	10

соответствует булевой функции f_{(2,2,134)₁₀}.

[править] Преобразование чисел

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

512

256

128

64

32

16

8

4

2

1

Начиная с цифры 1 все цифры умножаются на два. Точка, которая стоит после 1 называется двоичной точкой.

[править] Преобразование двоичных чисел в десятичные

Допустим, вам дано двоичное число 110001. Для перевода в десятичное просто запишите его справа налево как сумму по разрядам следующим образом:

$1\times 2^0 + 0\times 2^1 + 0\times 2^2 + 0\times 2^3 + 1\times 2^4 + 1\times 2^5 = 1\times 1 + 0\times 2 + 0\times 4 + 0\times 8 + 1\times 16 + 1\times 32= 49$ .

Можно записать это в виде таблицы следующим образом:

512	256	128	64	32	16	8	4	2	1
				1	1	0	0	0	1
				+32	+16				+1

Точно так же, начиная с двоичной точки, двигайтесь справа налево. Под каждой двоичной единицей напишите её эквивалент в строчке ниже. Сложите получившиеся десятичные числа.
Таким образом, двоичное число 110001 равнозначно десятичному 49.

[править] Преобразование методом Горнера

Основная статья: Метод Горнера

Для того, что бы преобразовывать числа из двоичной в десятичную систему данным методом, надо суммировать цифры слева-направо, умножая ранее полученный результат на основу системы (в данном случае 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.

[править] Преобразование десятичных чисел к ближайшей степени двойки, не меньшей этого числа

Ниже приведена функция, возвращающая число, не меньшее аргумента, и являющееся степенью двух.

unsigned int to_deg_2(unsigned int number) {
  --number;
  for(int i = 1; i < sizeof(unsigned int) * 8; i *= 2) {
    number |= (number >> i);
  }
  return number + 1;
}

[править] Преобразование десятичных чисел в двоичные

Допустим, нам нужно перевести число 19 в двоичное. Вы можете воспользоваться следующей процедурой :

19 /2 = 9  с остатком 1
9  /2 = 4  c остатком 1
4  /2 = 2  с остатком 0
2  /2 = 1  с остатком 0
1  /2 = 0  с остатком 1

Итак, мы делим каждое частное на 2 и записываем в остаток 1 или 0. Продолжать деление надо пока в делимом не будет 1. Ставим числа из остатка друг за другом, начиная с конца. В результате получаем число 19 в двоичной записи (начиная с конца): 10011.

См. также Деление с остатком (деление по модулю)

[править] Двоичные показательные позиционные системы счисления с основанием показательной функции не равной 2

Являются целочисленными сдвоенными показательными системами счисления.
Целые числа записываются в виде:
$x_{2,b}=(a_{n-1}a_{n-2}...a_2a_1a_0)_{2,b}=\sum_{k=0}^{n-1}a_k b^k$ , где:
b>2 - основание показательной межразрядной функции.
Дробные числа записываются в виде:
$x_{2,b}=(a_{n-1}a_{n-2}...a_1a_0,a_{-1}a_{-2}...a_{-(m-1)}a_{-m})_{2,b}=\sum_{k=m}^{n-1}a_k b^k$ , где:
m - число цифр дробной части числа x_2,b.

[править] Сравнение с другими системами счисления

В статье "Системы счисления (продолжение)"^[6] описываются преимущества и недостатки 4-ричной системы счисления по сравнению с двоичной в компьютерах, созданных Хитогуровым.
Сравнение различных показательных систем счисления по одному параметру - удельной натуральнологарифмической плотности записи чисел приводится в статье «Плотность записи чисел в сдвоенных позиционных показательных системах счисления».

[править] Применения

[править] В цифровых устройствах

Двоичная система используется в цифровых устройствах, поскольку является наиболее простой и соответствует требованиям:

Чем меньше значений существует в системе, тем проще изготовить отдельные элементы, оперирующие этими значениями. В частности, две цифры двоичной системы счисления могут быть легко представлены многими физическими явлениями: есть ток — нет тока, индукция магнитного поля больше пороговой величины или нет и т. д.
Чем меньше количество состояний у элемента, тем выше помехоустойчивость и тем быстрее он может работать. Например, чтобы закодировать три состояния через величину индукции магнитного поля, потребуется ввести два пороговых значения, что не будет способствовать помехоустойчивости и надёжности хранения информации.
Двоичная арифметика является довольно простой. Простыми являются таблицы сложения и умножения — основных действий над числами.

В цифровой электронике одному двоичному разряду в двоичной системе счисления соответствует^{[источник не указан 181 день]} один двоичный разряд двоичного регистра, т.е. двоичный триггер с двумя состояниями (0,1).

[править] В английской системе мер

При указании линейных размеров в дюймах по традиции используют двоичные дроби, а не десятичные, например: 5¾″, 7¹⁵/₁₆″, 3¹¹/₃₂″ и т. д.

[править] См. также

[править] Ссылки

↑ Sanchez, Julio & Canton, Maria P. (2007), Microcontroller programming : the microchip PIC, Boca Raton, Florida: CRC Press, p. 37, ISBN 0-8493-7189-9
↑ W. S. Anglin and J. Lambek, The Heritage of Thales, Springer, 1995, ISBN 0-387-94544-X
↑ Bacon, Francis, The Advancement of Learning, vol. 6, London, pp. Chapter 1, <http://home.hiwaay.net/~paul/bacon/advancement/book6ch1.html>
↑ http://www.leibniz-translations.com/binary.htm Leibniz Translation.com EXPLANATION OF BINARY ARITHMETIC
↑ Aiton, Eric J. (1985), Leibniz: A Biography, Taylor & Francis, pp. 245–8, ISBN 0-85274-470-6
↑ http://potan.livejournal.com/91399.html Системы счисления (продолжение)

Арифметические основы цифровой техники
http://static.dstu.edu.ru/informatics/mtdss/part1.html 1. Системы счисления

[0] Sanchez, Julio & Canton, Maria P. (2007), Microcontroller programming : the microchip PIC, Boca Raton, Florida: CRC Press, p. 37, ISBN 0-8493-7189-9

[1] W. S. Anglin and J. Lambek, The Heritage of Thales, Springer, 1995, ISBN 0-387-94544-X

[2] Bacon, Francis, The Advancement of Learning, vol. 6, London, pp. Chapter 1, <http://home.hiwaay.net/~paul/bacon/advancement/book6ch1.html>

[3] ttp://www.leibniz-translations.com/binary.htm Leibniz Translation.com EXPLANATION OF BINARY ARITHMETIC

[4] Aiton, Eric J. (1985), Leibniz: A Biography, Taylor & Francis, pp. 245–8, ISBN 0-85274-470-6

[5] ttp://potan.livejournal.com/91399.html Системы счисления (продолжение)

[1]

[2]

[3]

[4]

[5]

[6]