lekcii6 (Лекции), страница 2

Знаки исходного набора могут быть закодированы знакаыи стандартного а.|фавнта м , .где т — |псла знаков в исходном наборе. Пусть Ц б м Сопоставим ему код 6а6|... Ь, (| + 1 раз 6|) (пос.юдннй код ыы будем для краткости обозначать ЬаЬ*,"'). Утверждение доказано. С Иналу|а лля большей наглядности будут использоваться другие обозначения знаков набора лх Ье будет обозначаться знаком Л, а 6, - знаком ! («палочка»). Лекция 3 1.5 Системы счисления Система счисления — это способ числовой интерпретация цифровых сообщений. Прн этом удобно каждое число выражать отдельным слово|| (не нпюльзуя многословных бухгалтерских ус| и ых «сулш про песью» тина 0«6|а п|мся |а деаящьсош весел н дынт двел|ль).

Расслютрснный в утверждении 1.4.1 способ кодирования может бы|ь положен в основу т. и. натуральной системы счисления. В элам слу.чае элелюнтаы бюсконечного (счетного) множества Я натуральных чисел ставятся в соотвсгс| вне слова в ы* (звезда |- ка над алфавитом обозначаю множество всевозмо>кных слов, образованных нз сто букв, включая пустое слово). прн этол| числу и сопоставляется с юво нз и палочек.

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

Длн представления нуля можно |щетка нзменнть способ капцювання - - использовать палочку для обозначения нуля, две пв.ючкн -- „тля единицы н т. д. '1акую систему счисления будеы называть кардинальной. В этом случае арифметические операции несколько усложняктгсн: например, для сложения необходныо не только объединить две кучки палочек, по н нзъять одну лишнюю длн правильного иредставлення суммы.

Не;|остатком этих замечательных по своей простоте систем счнслення являет|я линейный рост длины числового слова пропорционально нелнчнне представляемого числа. Так для изображения десятичного чнсла 1000 потребуе|сн половина экрана терл|инала! То есть линейный рост в данном случае просю катастрофичен.

Этот недостаток нснранляс вся в т. н. позиционных системах счисления. Позиционная система счисления —. это полиномиа|ьный с|юсоб чнслоной интерпретация слов над цнфровыы алфавитоль Коэффнцнснтаын лп|ого иена являются малые пелые числа„означающие уже а нрнори (вручную) проянтерпре|ярова|п|ыс цифры. Значения этого мноточлена иычис:шются в точке, равной основанию сисшмы счисления. Познцио|п|вя снпшма задается одннл| натуральным числом р б 14 основанием системы счисления — казарес однозначно определяет алфавит Ар — — (О, 1,..., р — 1) н функцию ннтерпрстацнн |ъ ч | х = и„а ..|...а,аа " > л>(а )р'=- > р(6>)д> Ь Ь -> Ь>Ьа — — х .=а |.=о Интерпретация чисел опирается на натуральну|а н|перпрета|цпо цифр н основания снесены счисления Э>(а,) = Если в эту формулу подставить р — —.

1, то па>учится единичная снстеыа с исзения— аналог натуральной. Натура.|ьныа снстсл|ы счисления привета считать непознционньн|н, хотя по некоторым сообра>кенням нх можно одпонременно считать позиционными. Действительно, натуральная систеыа счисления подходит нод определение Лля р =. ! и каждая дополл|итсс>ьная> палочка слева увеличивает значение числа на 1 сообразно еднничнол|у основанию системы счнслсння — | ° — | — р ~<х(р" | — 1, Число Кодовое слово 0 -ч ** | — | -ч<ш -ч * -|-2 вьы 27 Гали основаяис системы счисления болыпе !. то длина слова, изображающе|о число.

равна це |ой части логарифма этого числа по основанию снстемы с шсления р. увеличенной на !. '!аким образом. линейный рост длины кодового слова сменяется гораздо более пологим логарифмическим в дссячичнос число 1000 изображается словом всего лилль из 4 цифрабукв. Из основано.|влачащей форм!мы позиционной сисчемы счис.|ения |медузе способ перевода изображении числа в другую систему счислоння: надо просто по.|учять коэффициенты с разложения этого же числа по степеням другого оснокакия 4. Это будут ос|иски цело пчаленного деления числа т на основание целевой сишел|ы счисления ф Чтобы составить из них чис.ю в позиционной форл|е, надо всего лишь эш|ыс|кть полу лепные остатки в обратнол| поря,чке. Наибачее распрсстране>п|ьвп! систел|ами счисления являются сис|емы с оснокапием 2, 3, 8, !О, !6. Системы счисления с нецелылш основаниями практически пе используются, хош наилучшей в некотором смысле является система счисления с основанием е.

Это основание доставляет максимум функции значения которой равны количеству кодовых слов длины л в |яичном алфавите (75, 76, 80(. Для решения этой элементарной экстрема:|ьной задачи достаточно знаний основ матаналяза из школьной программы. Среди сна|ем счисления с целыми оснонаниями ближе всего к е троячная. Она-то и попользовалась в паре случаев для практической реализации идеала (Троичная ЭВЫ <Сетунь» и ее заокеанский с|брат.) Среди рассматриваемых систем удобно выделить подкласс из двои шой, восьл|ернчной и шестнадцатиричной. Подставлая в основополагающую формулу вместо р 2, 2э и 2< получим после приведения подобных членов двоичные триады и те|разы - кодовые слова (составные буквы), изображающие (кодируюнчие!) 8- н !6-ричные цифры. Это даат основание реализовать перевод между системами счисления с кратньв|и основаниял|и как простое пераксдирование изображений чисел.

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

Однако при этом потребуечси 347кнопочпая клавиа|урв (101-~266 — !0). которая так |ке уз|обив, как н !01-кнопочная мьппь. Кстати, эча сис|сма счисления нашла применение в алгоритме Рабина-Карпа, яспользуемом для быстрого поиска подстроки. Л аналогичная идея прямого внешнсто предо|веления изображений чисел в ЭВМ была применена в так называемой десяти шой арифметике, .реализованной во многих универсе.|ьных ЭВМ 60- 70-х годов; применение для этой цели ВСО-кодировки давало экономи|о на переводе чисел в двоичную систему счисления. Всем измствая римская спешна счнслеиш| пепози|щопаая. а точнее поэиииаввая с нере- |тяшрной и вел!вишенной позиционностью С поэициоиныл|н системами счисления также связаны обратная и чополнительная кодировки отрицательных чисел в ЭВМ. Число — х кодируется дополяепиом до ближайшей целой степени р с числом разрядов, на единипу Гюлынил! количества цифр в разрячной сетке мапшнпого слоны р" — т, — ! -> ~ (р — !)р* — Я <»,р' .= ! 4- ~ (р — ! — а,)р'.

Диапазон представимых чисел носимметричен относите.льна О| но предавая.|ение 0 однозначно и арифлютические операции не чребукл изменения. Такам обрезом, в дополнительном кода отрицательные числа представлшотся б|ыьп|ими полож|ггечьнылш, вдвое сужав диапазон допустимых положительных |наел. При этом, чем болыпе |юложптезьное значение кодового слова отрицательного числа, чвм меныпе абсолютная величина представляамо|о им числа. Например, в 64-битной ЭВМ ОЕС Л!ру|в: 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000001 0000000000000000000000000000000000000000000000000000000000000010 0111111111111111111111111111111111111111111111111111111111111111 1000000000000000000000000000000000000000000000000000000000000000 1000000000000000000000000000000000000000000000000000000000000001 1000000000000000000000000000000000000000000000000000000000000010 1111111Ш111111111111111111111111111111111111111111111111111110 1111111111111111111111111111111111111111111111111111111111111111 Цяфраия обратного кода явля|ется дополнения до максилшльной цифры;|анной системы счисленяя р — ! — а,.