1 Математические и логические основы построения компьютеров

Прежде всего, при изучении данной дисциплине разберёмся с идеями, лежащими в основе современных компьютеров.

1.1 Позиционные системы счисления

1.1.1 Основные понятия

Система счисления – это принятый способ записи чисел и сопоставления этим записям реальных значений.

В любой системе счисления для представления чисел выбираются некоторые символы (знаки), отличные друг от друга. Эти символы называются базисными числами, а число таких символов называетсяоснованием системы счисления.В современном мире наибольшее распространение получило представление чисел посредством арабских цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Для изображения (или представления) чисел в настоящее время используются в основном позиционные системы счисления.

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

Десятичная, привычная для всех позиционная система счисления (ПСС) основана на том, что десять единиц каждого разряда объединяются в одну единицу соседнего старшего разряда. Таким образом, каждый разряд (позиция) имеют вес равный степени 10. Например, число 341.62 можно представить в виде

. (1.1)

Следовательно, последовательность цифр 341.62 – это сокращенная запись выражения (1.1).

Десятичная запись любого числа Xв виде последовательности цифр

, (1.2)

основана на представлении этого числа в виде полинома:

, (1.3)

где каждый коэффициент a_iможет быть одним из чисел, для обозначения которых введены специальные знаки 0, 1,…, 9.

Полиномом P(S) будем называть алгебраическую сумму произведений коэффициентов d_i на степени величины S:

.

Таким образом, запись (1.2) является перечислением всех коэффициентов полинома (1.3). Точка, отделяющая целую часть числа от дробной, служит для фиксации значений позиций цифр и является началом отсчёта позиций.

Число К единиц (K - целое и положительное) какого-либо разряда числа, объединяемых в единицу более старшего разряда, называют основанием ПСС, а сама система счисления называется К-ичной.

Например, основанием десятичной ПСС является число 10, двоичной - число 2, троичной – число 3 и т.д. Для записи произвольного числа в К-ичной ПСС достаточно иметь К разных цифр a_i ,В троичной ПСС любое число можно представить посредством цифр 0, 1, 2. Числа, лежащие в основе ПСС называютсябазисными.

В истории цивилизации использовались различные ПСС. Например, в Древнем Вавилоне использовались ПСС с основанием 60, были ПСС с основанием 12, 20 и ряд других.

Запись произвольного числа ХвK-ичной ПСС основывается на представлении этого числа в виде полинома:

, (1.4)

где каждый коэффициент a_iможет быть одним из базисных чисел и изображается одной цифрой.

Как и для десятичной ПСС, число Х, представленное вK-ичной ПСС, можно кратко записать в виде (1.2), путём перечисления всех коэффициентов (1.4) с указанием позиционной точки.

Арифметические действия над числами в любой ПСС производятся по тем же правилам, что и в десятичной ПСС, так как все они основываются на правилах выполнения действий над соответствующими полиномами. При этом нужно только пользоваться теми таблицами сложения и умножения, которые имеют место для ПСС с основанием К.

Для указания того, в какой ПСС записано число, при его изображении основание ПСС указывают в виде нижнего индекса, например 35.648 .

Примеры. Приведём примеры выполнения арифметических действий в различных ПСС:

5₆ + 3₆ = 5₆ + 1₆ + 2₆ = 10₆ +2₆ = 12₆ ,

15₈ - 7₈ = 10₈ + 5₈ - 7₈ = 8₁₀ +5₁₀ - 7₁₀ = 13₁₀ -7₁₀ = 6₁₀ = 6₈ ,

_1445₇ 35₇

141₇ 31₇

_35₇

35₇

0

Отметим, что во всех ПСС с любым основанием К умножения на числа вида K^m, где m – целое число, сводится просто переносу (сдвигу) точкой у множимого на m разрядов влево или вправо (в зависимости от знака).