lekcii5 (522349), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

П Иногда для большей наглядности будут использоваться другие обозначения знаков набора ш: 6«будет обозначаться знаком Л, а 6< -- знаком ~ 1«палочка»). Лекция 3 1.5 Системы счисления Система счисления это способ числовой интерпретации цифровых с<юбщений. При этом удобно каждое число выражать отдельным словом (не используя многословных бухгалтерских устных «сумм прописью» типа Одно, тысяча, девятьсот восемьдесят девять).

Рассмотренный в утверждении 1.4.1 способ кодирования может быть положен в основу т, н, натуральной системы счисления. В этом случае элементам бесконечного (счетного) множества 1)! натуральных чисел ставятся в соответствие слова в ш' (звездочка, над алс))авитом обозначает множество всевозможных слов, образованных из его букв, Вклк) !Йя пустОС слОВО), щ)и этом числу 7! сопОстаВлястся слОВО из 7! палОчек. Зтй система называется натуральной, поскольку она представляет собой естественную числову!о абсгрйкцик) ВОзникп11 к) От псресч>й>тй прсдм)'тОВ категории нуля и Отрицательных чп1ссл отсутству>от.

Как установили биологи ))1ГУ, натуральной системой счисления в пределах 20 владеют даже вороны. Кроме того, они могут складывать и вычитать числа, порядка 3 4. Знаменитый коллектив французских математиков Бурбаки склонен, для большей общности, не только приписывать 0 к натуральным числам, но и считать его одновременно и положительньгхл, и отрицательным. Во многих случаях действительно полезно и удобно наряду с натуральными числами рассматривать и нуль.

Для представления нуля можно слегка изменить способ кодирования - - использовать пйз!Очку для обозначения нуля, две палочки — для единицы и т. д. Такую систему счисления будем называть кардинальной. В этом случае арифметические операции несколько усложняются: например, для сложения необходимо не только обьсдипить две кучки палочек, но и изъять одну лиши!о!О для правильного представления суммы. Недостатком этих замечательных по своей простоте систем счисления является линейный рост длины числового слова пропорционально величине представляемого числа. Так для изображения десятичного числа 1000 потребуется половина экрана терминала! То есть линейный рост в данном случае просто катастрофичен. Этот недостаток исправляется В Т. Н.

ПОЗИПИОННЫХ СИСТРЫЙХ 1П1ИСЛЕНИЯ. Позиционная система счисления это полиномиальный способ числовой интерщ)етапии слОВ !ид цифроВым йгн))авитОм. Коэффициентами многОч>лена, яВляются малые цельи; числй. Ознй;)йк>)цие уже й щ)нори (Вручнук)) 10)оинтерщ)стщ>овйнные цифры. Значения этого многочлена вычисляются в точке, равной основанию системы счисления. НозициОннйЯ система задает(я Одним нйтуральныы числОм р е 1') - — основанием системы счисления -- которое однозначно определяет алфавит Ар — — (О, 1,..., .р — 1) и функцию интерпретации х= а„а )...а>ай — „р ))(а;)р = р ~(Ь,)71' -Ьп,Ь,— ! ..Ь)ЬС =х Интерпретация чисел опирается на натуральную интерпретапию цифр и основания системы счисления;д(11;1 = 1 палочек Если в эту формулу подставить р = 1, то получится единичная система счисления аналог натуральной.

Натуральные системы счисления принято считать непозиционными, хотя по некоторым соображениям их можно одновременно считать позиционными. Действительно, натуральная система счисления подходит под определение для р = 1 и каждая дополнительная палочка слева увеличивает значение числа на 1 сообразно единичному основанию системы счисления. 25 Если основание системы счисления больше 1, то длина слова, изображающего число, равна целой части логарифма этого числа по основанию системы счисления р, увеличенной на 1. Таким образом, линейный рос ~ тпп1пы кодового слова сменяется гораздо более пологим логарифмическим и десятичное число 1000 изображается словом всего лишь из 4 цифробукв. Из основополагающей формулы позипионной системы счисления следует способ перевода, изображения числа, в другую систему счисления: надо просто получить коэффициенты с разложения этого же числа по степеням другого основания о.

Это будут остатки целочисленного деления числа х на основание целс вой системы счисления о. Чтобы составить из них число в позиционной форме, надо всего лишь записать полученные остатки в обратном порядке. Наиболее распространенными системами счисления являются системы с основанием 2, 3, 8, 10, 16. Системы счисления с нецелыми основаниями практически не используются, хотя наилучшей в некотором смысле является система, счисления с основанием е.

Это основание доставляет максимум функции значения которой равны количеству кодовых слов длины и в р-ичном алфавите ~75, 76, 801. Для решения этой элементарной экстремальной задачи достаточно знаний основ матане.- лиза из школьной программы. Среди систем счисления с целыми основаниями ближе всего к е. троичпая, Она-то и использовалась в паре случаев для практической реализации идеала. (Троичнея ЭБМ «Сетуньи и ее заокеанский собрат.) Среди рассматриваемых систем удобно выделить подкласс из двоичной, восьмеричной и шестнадцатиричной. Нодставляя в основополагающую формулу вместо р 2., 2' и 24 получим после приведения подобных членов двоичные триады и тетрады кодовые слова (составные буквы), .изображаклцие (кодирующие!) 8- и 16-ричные цифры.

Это дает основание реализовать перевод между системами счисления с кратными основаниями как простое пс1текодировапие изображеш1й чисел. В Остальных случаях это оолее трудоемкая арифметическая процедура. '1ем болыпе основание системы счисления, тем более экономна запись, и тем более сложная аппаратура требуется (клавиатура, .кодировка, шрифт). Так, десятичная система счисления в 1ояв 10 — более чем в 3 раза экономнее (формула перехода к логарифму по другому основанию), А как вам нравится система счисления с основанием 256? Удобно, конечно, каждую цифру представить в памяти ЭВМ одним байтом с нспосречственной аппаратной адресацией.

Однако при этом потребуется 347-кнопочная клавиатура (101+ 256 — 10), которая так же удобна, как и 101-кнопочная мышь. Кстати, эта система счисления нашла применение в алгоритме Рабина-Карпа, используемом для быстрого поиска подстроки. Л аналогичная идея прямого внешнего представления изображений чисел в ЭВМ была применена в так называемой десятичной арифметике, реализованной во многих универсальных ЭВМ 60- 70-х годов: применение для этой цели ВС1)-кодировки давало экономию на переводе чисел в двоичную систему счисления.

Всем известная римская система счисления нецозициониая, а точнее позиционная с нере- гулярной и немоиотоииой позипионностью. С позиционными системами счисления также связаны обратная и дополнительная кодировки отрицательных чисел в Э1ЗМ. Число — х кодируется дополнением до ближайшей целой степени р с числом разрядов, на единицу большим количества цифр в разрядной сетке машинного слова: и-1 и- 1 и 1 ри - х = 1+ Е(р -1) р' - Е а1р* = 1+ Е(р -1- ш) р' Диапазон представимых чисел песимметричен относительно О: но представление О однозначно и арифметические операции не требуют изменения.

Таким образом, в дополнителыюм коде отрицатсльпыс числа представляются болыпими положительными, вдвое сужая диапазон допустимых положительных чисел. При этом, чем больше положительное значение кодового слова отрипательного числа,тем меньше абсолютная величина представляемого им числа. Например, в 64-битной ЭВМ 1ЭЕС А1рйа,: тХисло Кодовое слово О 0000000000000000000000000000000000000000000000000000000000000000 1 0000000000000000000000000000000000000000000000000000000000000001 2 0000000000000000000000000000000000000000000000000000000000000010 0111111111111111111111111111111111111111111111111111111111111111 1000000000000000000000000000000000000000000000000000000000000000 1000000000000000000000000000000000000000000000000000000000000001 1000000000000000000000000000000000000000000000000000000000000010 -2 1111111111111111111111111111111111111111111111111111111111111110 -1 1111111111111111111111111111111111111111111111111111111111111111 Цифрами обратного кода являются дополнения до максималь1юй цифры данной системы счисления р — 1 — аь Обратный код легко получается из прямого, но неудобен неоднозначностью представления О и требует изменения способа выполнения арифметических операций.

Из формулы (") следует способ получения дополнительного кода: 1, Заменить цифры числа, дополнениями до максимальной цифры системы счисления (простая и быстрая неарифметическая микрокодная операция параллельного кодирования над текстом изображения числа). 2. Прибавить 1 к младшему разряду и выполнить возможно возникающие при этом персносы (эта операция каж11тся арифметической и сугубо последовательной, но наверное для нес существует аналог однотактного сумматора Бессонова, - счет плка Шеннона ~79!).

Элементарными операциями микрокода любой ЭВМ являются сдвиги: логические, циклические, арифметические. Логический сдвиг представляет собой перемещение всех разрядОВ машиннОСО слОВЙ ВлеВО и>!и Вправо нй числО разрядОВ, заданн(>е ВтОрым Операндом. При этом освобождак>щиеся при таком сдвиге свободные разряды заполняются нулями, а разряды, Выходя>цие за пределы машинного слова, теряк>тся. При циклическом сдвиге разряды машинного с;>она считаются закольцованными, образуя т.

н. двусторонний списгпс, так что вслед за последним разрядом идет первый. а перед первым последний. Арич>мети~>еский сдвиг сложнее; Он трактует слово как ДОполнит11льный кОД целОгО ~1ислй, так что сдвиг влево есть целочисленное умножение, а сдвиг вправо деление. В первом случае «знаковый» разряд распространяется вправо по сдвигаемому слову, а младшие разряды теряются, как и положено при делении нацело. При сдвиге вправо «знаковый разряд остается неизменным, а подлежащие удалению старшие разряды выпадают непосредственно перед ним. Это свойство сдвига, использующее позиционность системы счисления, позволяет очень просто реализовать довольно сложные операции умножения и деления, причем неарифметическим микрокодным образом.

Характеристики

Список файлов лекций