KursLek110 (Лекция), страница 3
Описание файла
Файл "KursLek110" внутри архива находится в папке "Лекция". PDF-файл из архива "Лекция", который расположен в категории "". Всё это находится в предмете "основы теории вычислительных систем" из 6 семестр, которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 3 страницы из PDF
С/c называется непозиционной, если каждой цифре в любомместе в записи числа однозначным образом сопоставлен некоторый количественныйэквивалент ( ).Т.е. количественный эквивалент цифры в непозиционной с/c не зависит от еёместоположения в записи числа.Примерами непозиционной с/c является унарная система с алфавитом А = {} иримская с/с с алфавитомA = {, , , , , }. Для римского алфавитаколичественные эквиваленты цифр, например, () = 100,() = 10, () = 1, иони не зависят от местоположения цифр в записи числа.Например, число СС можно представить в десятичной с/с суммойколичественных эквивалентов цифр, входящих в это число:100 + 100 + 10 + 10 + 10 − 1 = 229.Определение1.3. С/c называется позиционной, если количественный эквивалент,сопоставляемый всем цифрам ∈ , зависит не только от вида этой цифры, но и отеё местоположения в записи числа.Например, для 10 c/c с алфавитом A = {0, 1, 2, … , 9}имеем555,5(5) = 500(5) = 50 (5) = 5 (5) = 0.5Возможны частично-позиционные с/c, в которых для одного подмножества цифрколичественный эквивалент однозначен, а для другого подмножества цифр он зависитот их местоположения в записи числа.Для определения количественного эквивалента числа в c/c вводится функцияF = {(1 ), (2 ), … , ( )} .Для большинства существующих с/c,функция Fесть функция сложения(аддитивные с/c).
Для мультипликативных c/c F – функция умножения.Так в предыдущем примере количественный эквивалент десятичного числа555,5 можно представить суммой количественных эквивалентов цифр, входящих в эточисло:500+50+5+0,5=555,5Проведём нумерацию мест (позиций) цифр в записи числа, начиная отразделительной запятой следующим образом:- влево в порядке возрастания целых положительных чисел, начиная с 0, т.е.0,1,2,…;- вправо целыми отрицательными числами: -1,-2,… .В этом случае каждой цифре в числе однозначно сопоставляется число, котороеназывается номером разряда.
Например, в десятичном числе 72813,69 каждая цифразанимает разряд, который сверху помечен номером:. . . 4 3 2 1 0 -1 -2 . . .7 2 8 1 3,6 9Определение1.4. Весом -го разряда для данной с/c называется отношение = ( )i / ( )0 ,если значение этого отношения постоянно для всех цифр ∈ . Запись ( )i означаетколичественный эквивалент, сопоставляемый цифре , которая записана в i-мразряде, причём = 0. Нулевой разряд имеет вес 1, т.е. 0 = 1 (( )0 / ( )0 =1).Определение 1.5. С/c называется весомозначной, если для каждого разряда выполняется отношение( ) = ∗ ( )0Причём вычисляется по некоторому закону, и различен для разныхразрядов.
Для большинства весомозначных с/c функция вычисления достаточнопроста.Определение 1.6. С/c называется с основанием S, если для всех разрядоввесомозначной с/c имеет место равенство = ∗ −1 .Вес всегда можно представить через основание в степени, равной номеруразряда, т.е.
= .Для того, чтобы различать числа, заданные в с/с с разными основаниями, будемиспользовать в конце записи числа нижний индекс, который и указывает на основаниес/с. Например, десятичное число 1111,1 записывается как 1111,1 10, а двоичное число1111,1 – как 1111,12, шестнадцатеричное число 40983 – как 4098316 и т.д.Позиционная с/c с основанием S полностью задаётся:- алфавитом А;- количественным эквивалентом цифр в любом фиксированном разряде (обычнов нулевом);- значением основания S.Определение 1.7. Если ∈ {0,1, … , − 1}, то такая с/c называется снатуральным основанием.Определение 1.8. Если ∈ {−, − + 1, … , −1,0,1, … , } , то с/c называетсяс симметричным основанием.В дальнейшем рассматриваются позиционные с/c с натуральным основанием.Позиционные с/с обладают следующими свойствами.а) Любое число Х в позиционной весомозначной с/c с натуральным основаниемS, может быть представлено в виде полинома: = ∗ + −1 ∗ −1 + ⋯ ∗ + ⋯ + 1 ∗ 1 + 0 ∗ 0 + −1 ∗ −1 + −2 ∗∗ −2 + ⋯ + − ∗ − ,где под понимается любая цифра из алфавита А, записанная в i-ом разряде.б) Мощность алфавита равна основанию с/с, т.е.
|| = .в) Наибольший количественный эквивалент цифры из алфавита А на единицуменьше основания ( ) = − 1.1.2. Классификация с/cУпрощенная классификация с/с представлена на рис. 1.1.В дальнейшем рассматриваются позиционные весомозначные с/с с натуральнымоснованием. Для того, чтобы показать основание с/с, в которой представлено число,основание будем приписывать к числу в виде нижнего индекса. Например, число х,представленное в двоичной системе счисления, изображается как х2 .С/cПозиционнаяНепозиционныеtgjpbwbjyysq- унитарная,- римская,pbwbjyysqВесомозначнаяНевесомозначнаяpbwbjyysq- египетская- код с избытком 3С основаниемБез основанияjpbwbjyysqДробноеpbwbjyysq- фиббоначиева (коды золотой пропорции)ЦелоеНатуральноеСимметричное- коды с остаткамиОтрицательноецелоедробноеПоложительноецелоедробноеРис. 1.1. Классификация с/с1.3. Преобразование чиселЧасто для заданного числа , представленного в с/с с основанием S,необходимо найти его представление в с/ с основанием R, т.е.
.Для преобразования числа из одной системы счисления в другую используетсяпроцедура деления/умножения. Операция деления используется для преобразованияцелой части числа, а операция умножения – для преобразования дробной части числа.Правило преобразования целого числа в число .1) Разделить на основание системы счисления, в которую переводитсязаданное число, т.е.
на R. Остаток запомнить.2) Проверить, частное равно нулю? Если частное не равно нулю, то принять егоза новое значение , т.е. присвоить значение текущего частного. Перейтик п.1. В противном случае перейти к п.33) Начиная со старшего разряда, выписать запомненные остатки от деления впорядке, обратном их получению. Полученная запись и есть результатпреобразования.Пример.
Преобразовать десятичное число 10 = 49 в двоичнуюс/с, т.е. найти 2 .49 ÷ 2 = 24, остаток 1,24 ÷ 2 = 12, остаток 0,12 ÷ 2 = 6, остаток 0,Порядок записи результата6 ÷ 2 = 3, остаток 0,3 ÷ 2 = 1, остаток 1,1 ÷ 2 = 0, остаток 1.Результат преобразования: 4910 = 1100012.Процесс преобразования целых чисел всегда завершается за конечное числошагов и дает результат без погрешности.Еще пример: преобразовать десятичное число 10 = 735 в восьмеричнуюс/с, т.е. найти 8 .735÷8=91, остаток 7,91÷8=11, остаток 3,11÷8=1, остаток 3,1÷8=0, остаток 1.Результат преобразования: 73510 = 13378 .Правило преобразования правильного дробного числа в число .1) Умножить на основание системы счисления, в которую исходное числопреобразуется, т.е.
на R. Целая часть результата запоминается.2) Дробную часть результата принять за новое значение и перейти к п.1.3) Процесс умножения прекращается при получении нулевой дробной части илипри достижении заданной точности. Результатом является дробная частьчисла, котораяпредставляет запись, начинаясостаршего разряда,запомненных целых частей в порядке их получения при умножении.В общем случае процедура преобразования дробной части числа являетсяприближенной, т.е. преобразование проводиться с погрешностью.Пример. Преобразовать число 10 = 0,1875 в двоичную с/с, т.е.определить 2 .0,1875 × 2 = 0,3750, целая часть равна 0,0,3750 × 2 = 0,7500, целая часть равна 0,0,7500 × 2 = 1,5000, целая часть равна 1,0,5000 × 2 = 1,0000, целая часть равна 1.Порядок записирезультатаДробная часть результата в последней операции равна нулю. Поэтому процесспреобразования закончен, и результат преобразования: 0,187510 = 0,00112 .1.4.
Преобразование чисел с основанием 2nБолее простое преобразование чисел проводится в случае, если основаниеисходного числа и основание результирующего числа можно представить как2n.Например, основания с/с 2, 4, 8, 16.Рассмотрим два случая:а) преобразование из двоичной с/с в с/с с основанием 2 ,б) преобразование чисел с основанием 2 , в двоичную с/с.Ограничимсярассмотрениемвосьмеричнойишестнадцатеричнойс/с.Основание можно представить как степень двойки: 8= 23 ( = 3), 16 = 24 ( = 4).Преобразование чисел из двоичной с/с в с/с с основанием 2 .Процедура преобразования состоит из двух следующих шагов.1) Исходное двоичное число разбивается на группы из n разрядов, продвигаясьот разделительной запятой влево и вправо. Для восьмеричной с/с = 3, игруппа из трех разрядов называется триадой.