Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Системы счисления и перевод чисел из одной системы представления в другую.Стр 1 из 4Следующая ⇒
Задача 1. Количество информации по Хартли рассчитывается по формуле [бит], где N-число возможных состояний объекта; m-основание системы счисления (количество символов, применяемых в алфавите); n-число разрядов в сообщении. Рассчитать количество информации, содержащееся в изображении черной точки. Решение: Для решения этой задачи надо определить число возможных состояний объекта, т.е., например, экрана монитора. Поскольку в задаче это не детализируется, сделаем следующие предположения: 1) нас интересует состояние только одного пикселя, который изображает черную точку; состояние остальных пикселей может быть любым, и для данной задачи несущественно; 2) качество цветопередачи 32 бита (максимальное качество типичного ЖК-монитора). Тогда: N=mn =232 Информация о цвете каждой точки передается 32 битами. Количество информации по Хартли будет равно I= log2N = log2mn = nlog2m = 32log22=32бит.
Задача 2. Подсчитать объем данных, количество информации в сообщении «Я изучаю информатику» и коэффициент информативности сообщения Решение: Не будем учитывать пробелы и различие между большими и малыми буквами, примем размер алфавита 32 символа. Длина сообщения равна 18 символам. 1) Объем данных равен количеству символов в сообщении: Vd = n = 18 символов Или, при двоичном (5-битном) представлении: V = n log2m = 18*log2 (32) = 18*5 = 90 бит. 2) количество информации рассчитаем по Шеннону. Составим таблицу частот повторения символов в сообщении:
Количество информации: , или 3, 68*18 = 66, 3 бит на сообщение. 3) коэффициент информативности сообщения С=1/Vd = 66, 3/90 = 0, 737. Задача 3. Количество информации как разность энтропий рассчитывается по формуле I = Н(α ) - Н(β ) ≤ 1, где Н(α ) априорная энтропия, а Н(β )-апостериорная энтропия. Энтропия системы (объекта), имеющая N возможных состояний, согласно формуле Шеннона, равна , У монеты утяжелили одну сторону и вероятности выпадения сторон стали Р1 = 1/3, Р2 = 2/3. Подсчитать количество информации, которое получаем при выпадении одной из сторон. Решение: Под априорной энтропией в данном случае следует понимать энтропию двух возможных исходов (орел - решка), считая, что априори эти исходы равновероятны. После проведения опытов мы получаем апостериорную энтропию: возможны два исхода, но один из них в два раза более вероятен, чем другой. Количество информации в этом случае равно: I = H(α ) – H (β )= - (½ log2½ + ½ log2½ ) + (⅔ log2⅔ + ⅓ log2⅓ ) = 1 – 0, 9183 = = 0, 0817 бит/символ (т.е. на один исход)
Задача 4. При представлении информации в компьютере или передачи ее по каналам связи информация кодируется числовыми кодами. Одно и то же количество разрядов кода в различных системах счисления может передавать различное количество информации. Эту зависимость можно представить в виде соотношения , где N число возможных состояний объекта; m – основание системы счисления (количество символов, применяемых в алфавите); n – число разрядов в сообщении. Рассчитать количество разрядов двоичного кода, необходимого для кодирования 32 букв алфавита. Решение: N = 32, т.к. требуется закодировать 32 буквы алфавита. m = 2, т.к. код двоичный. Тогда: n = log2 32 = 5 – требуется 5 разрядов.
Задача 5. В двоичной системе счисления единица измерения бит (двоичный разряд). В современных ЭВМ применяется единица байт, равная 8 битам. Рассчитать объем данных в сообщении 10111011, который представлен в виде восьмиразрядного двоичного кода. Объем данных в сообщении Vд = 8 бит =1байт. В десятичной системе счисления единица измерения – дит. Рассчитать объем данных в сообщении 9213452, который представлен в десятичной системе в виде семиразрядного числа. Объем данных в сообщении Vд = 7 дит.
Задача 6. Разработать фасетную систему классификации студентов РГТЭУ
Рассчитать количество двоичных разрядов для фасетной классификации студентов РГТЭУ. Расчет кол-ва информации, системы классификации, алфавит системы, система управления и коды управления Решение: Фасетная классификация – это совокупность нескольких независимых классификаций, осуществляемых одновременно по нескольким различным основаниям. В нашем случае это: факультет, специальность, группа. Университет не является классификационным признаком, т.к. рассматриваются только студенты РГТЭУ. Каждой ячейке фасетной структуры соответствует несколько объектов, идентификатор которого – фамилия студента. Если мы примем, что в университете 4 факультета, на каждом по три специальности, и каждой специальности обучаются студенты 3 групп, получим: требуется 6 двоичных разрядов ( по 2 бита на номер факультета, группы, специальности); количество информации может быть определено как (всего 4*3*3=36 ячеек): I = - (36∙ (1/36)∙ log2(1/36)) = 5, 17 бит на ячейку.
Задача. Представить число 1997 в позиционной системе счисления с основанием 10 (десятичной системе) 1997 = 1х103 + 9× 102 +9× 101 +7× 100. Представить число 1997 в позиционной системе счисления с основанием 2 (двоичной системе) 1997 = 1× 210 +1× 29 +1× 28 +1× 27 +1× 26 +0× 25 +0× 24 +1× 23 +1× 22 +0× 21 +1× 20 = 11111001101. Представить число 1997 в позиционной системе счисления с основанием 8 (восьмеричной системе) 1997 = 3× 83 +7× 82 +1× 81 +5× 80 = 3715. Представить число 1997 в позиционной системе счисления с основанием 16 (шестнадцатеричной системе) 1997 = 7× 162 +12× 161 +13× 160 = 7CD.
Задача. Представить в двоичной форме числа 48, 57, 511, 121. Разложим числа по степенному ряду двойки: Решение: 48 = 32+16=1х25 + 1х24 + 0х23 + 0х22 + 0х21 + 0х20=1100002 57 = 32+ 16+8+1 =1х25 + 1х24+ 1х23 + 0х22 + 0х21 + 1х20 = 1110012 511=256+128+64+32+16+8+4+2+1 = 1х28+1х27 +1х26+1х25+1х24 +1х23+ +1х22 +1х21 +1х20 = 1111111112 121 = 64+32+16+8+4+2+1 = 1х26+1х2 +1х24+ 1х23 + 0х22 + 0х21 + 1х20 = =1111012
Задача. Представить в восьмеричной форме числа 48, 57, 511, 121. Разложим числа по степенному ряду восьмерки: 48 = 6х81 + 0х20 = 608 57 = 56 + 1 = 7х81 + 1х20 = 718 511 = 448 + 56 + 7 = 7х81 + 7х81 + 7х80 = 7778 121 = 64 + 56 + 1 = 1х81 + 7х81 + 1х80 = 1718
Задача. Представить в шестнадцатеричной форме числа 48, 57, 511, 121. Разложим числа по степенному ряду шестнадцати: 48 = 3х161 + 0х160 = 3016 57 = 48 + 9 = 3х161 + 9х160 = 39 16 511 = 256 + 240 + 15 = 1х162 + 15х161 + 15х160 = 1FF 16 121 = 112 + 9 = 7х161 + 9х160 = 19 16
Метод деления. Представление десятичного числа в других системах счисления может проводиться по схеме Горнера. Допустим, что у нас есть целое число D, представленное с помощью основания системы счисления b, т.е. Dn. Процесс представления выполняется в несколько этапов по следующим правилам: 3 Последовательно делить заданное число и получаемые целые части на новое основание счисления до тех пор, пока целая часть не станет меньше основания нового счисления. 4 Полученные остатки от деления, представленные символами нового счисления, записать в виде числа, начиная с последней целой части. Следовательно, на 1 этапе Dn = , где - целая часть от деления, а0 – остаток. Этот остаток является первым младшим разрядом в новой системе счисления. На втором этапе деления получаем выражение вида = и т.д. Задача. Представить по схеме Горнера десятичное число D10 = 147 в двоичном коде D2 = 10010011, в восьмеричном коде D8 =223, в шестнадцатеричном коде D16 = 93. Проверить полученные результаты на инженерном калькуляторе.
Рассмотрим преобразование десятичных чисел в двоичные, восьмеричные или шестнадцатеричные на основе процедуры схемы Горнера, представленной в виде таблицы:
Задача. Самостоятельно записать процедуру перевода D10 =156 в D8 и на основе анализа процедуры преобразования чисел из одной системы счисления (D10) в другую D2, D8, D16 разработать алгоритм этой процедуры.
Решение:
15610 = 100111008 = 2348 = 9С16
Алгоритм процедуры показан на рисунке:
Метод вычитания. 53 25 24 23 22 21 20 -32 ®25____ 1 1 0 1 0 1 21 -16 ®24____________ 5____________________________ -4 ®22________________________________ -1 ®20_________________________________________
Метод умножения (Перевод дробного числа из десятичного счисления в другое счисление). Правило: последовательно умножать данное число и получаемые дробные части произведений на основание новой системы счисления до тех пор, пока дробная часть произведения не станет равна нулю или не будет получено требуемое по условию количество разрядов; полученные целые части являются разрядами числа в новой системе и их необходимо представлять цифрами этой новой системы счисления. Пример. Для преобразования десятичной дроби в двоичный эквивалент используем операцию последовательного умножения на 2. Если первое произведение окажется меньше 1, то запишем в старший разряд двоичной дроби 0. Если первое произведение ³ 1, то старшей цифрой двоичной дроби является 1. Аналогично определим вторую цифру двоичной дроби, причем на два умножается только дробная часть произведении, полученная на предыдущем шаге.
Задача. 0, 6384× 2=1, 2768 ®1 0, 4535× 2=0, 907 ®0 0, 2768× 2=0, 5536 ®0 0, 907× 2=1, 8140 ®1 0, 5536× 2=1, 1072 ®1 0, 8140× 2=1, 6280 ®1 0, 1072× 2=0, 2144 ®0 2, 6280× 2=1, 256 ®1 0, 2144× 2=0, 04288®0 1, 256× 2=0, 512 ®0 0, 0× 2=0, 0 ®0 0, 512× 2=1, 024 ®1 (0, 6384)10 = (0, 101000)2 0, 024× 2=0, 048 ®0 0, 048× 2=0, 096 ®0 0, 096× 2=0, 182 ®0 (0, 4535)10 = (0, 011101000)2
Форматы чисел. Пример. В десятичной системе число 15 может быть записано несколькими способами:
Задача. Имеется 4-х разрядный регистр данных. Сравнить максимальные числа, которые могут быть записаны в регистр, при естественной и нормальной форме записи.
Решение: Если под запись числа отводится 4 байта, т.е. 32 бита, то в естественном представлении один бит отводится под знак числа, (32-1) = 31 бит – под целую частью Максимальное число равно: 231 – 1 = 2147483647 ≈ 2/109 В нормальном представлении один бит отводится под знак мантиссы, один знак – под знак порядка, шесть бит – под значение порядка, (32 – 1 – 1 – 6) = 24 бита – под значение мантиссы. Максимальное число, записанное в мантиссу, есть 0.111…1(24 раза) = 1 – 2-24≈ 1 – 6*10-8 ≈ 1 Максимальное число, записанное в порядок (6 бит), есть 26 – 1 = 64 - 1 = 63. Т.е., максимальное число, записанное в нормальной форме, есть 111…1 000…0 , т.е., 263 – 239≈ 632≈ 9*1018 24 раза 63-24=39 раз Для однозначного представления числа мантиссу нормализуют, т.е. накладывают ограничение < 1. Под значение порядка отводится 7 разрядов и один из них знаковый. Следовательно, значение порядка лежит в интервале, т.е. от-64 до 63. Сместив порядок на 26 = 64 = 4016, получим интервал возможных значений 0 27 -1=127. Смещенный порядок на 4016 называется характеристикой и вычисляется как Рх =Р+40. Если характеристика равна 40, то порядок равен 0; если характеристика меньше 40, то порядок отрицательный; если больше-то положительный. Задача. Представить в нормальной форме Е шестнадцатеричный код числа D10 = 32001, 5 и D10 = -32001, 5. Так как форма Е – это короткий формат (4 байта), то с использованием шестнадцатеричного кода получим: 32001, 510 = +7D01, 816 и -32001, 510 = -7D01, 816. Найдем нормализованные мантиссы и характеристики: m = 0, 7D018 < 1 Рх = 40+4 = 44
m = -0, 7D018 < 1 Рх = 40+4 = 44
Машинные коды чисел. В компьютерах все арифметические операции осуществляются в машинных кодах и могут быть сведены к операции сложения и операциям сдвига вправо или влево. Обычно применяются прямой, обратный и дополнительный коды. Представление чисел в прямом коде осуществляется в виде знакового разряда и абсолютной величины числа. Задача. +2910 = 001111012 -2910 = 10111101 +12710 = 011111112 -12710 = 111111112
Для представления отрицательных чисел или замены операции вычитания на сложение используются обратный и дополнительный коды. Сущность этих кодов заключается в том, что вычитаемое число Х, как отрицательное число, представляется в виде дополнения до некоторой константы С, такого, что С – Х > 0. Обратный и дополнительный коды отличаются выбором этой константы. Для дополнительного кода отрицательное число Z представим как Z = -Х = (10n –Х) - 10n, где Z < 0, Х> 0, n – величина разрядной сетки, а 10n –Х –дополнительный код числа. Для обратного кода отрицательное число Z представим как Z = -Х = (10n – 1 - Х) - 10n +1, где Z < 0, Х> 0, n – величина разрядной сетки, а 10n – 1 - Х –обратный код числа. Для положительного числа прямой, обратный и дополнительный коды будут одинаковыми Ап =Ао =Ад.
Задача. Для числа +31→ Ап =Ао =Ад =0000 0000 0001 11112. Для числа -31→ Ап =1000 0000 0001 11112. Для построения дополнительного кода выбираем константу 1015= 1000 0000 0000 0000 и получаем Ад =1111 1111 1110 00012.
Общие правила образования машинных кодов: -положительное число в прямом, обратном и дополнительном кодах одинаково; -прямой код отрицательных и положительных чисел имеет различие только в знаковом разряде, модуль числа не меняется; -обратный код отрицательного числа получается из прямого кода путем инверсии, т.е. замены 1 на 0 и всех 0 на 1, кроме знакового разряда; -дополнительный код получается из обратного прибавлением 1 к младшему разряду (перенос 1 в знаковый разряд не учитывается); -дополнительный код отрицательного числа получается из прямого кода заменой всех 1 на 0 и всех 0 на 1, кроме 1 самого младшего разряда и следующих за ней 0. Обычно в компьютере числа в естественной форме записи хранятся в дополнительном коде, а числа в нормальной форме хранятся в прямом коде. Обратный код применяется для получения дополнительного кода.
Задача 1. Даны два числа А10 = 126 и В10 = 267. Необходимо найти сумму этих чисел при разных знаках. Для этого перевести А10→ А16→ А2 и В10→ В16→ В2. Решение: А = 7Е16 =11 11102; В = 10В16 = 1 0000 10112. В формате Н эти числа имеют следующий вид: Ап = 0.000 0000 0111 1110; Вп = 0.000 0001 0000 1011; -Ад = 1.111 1111 1000 0010; -Вд =1.111 1110 1111 0100; Выполним сложение чисел, используя соответствующие коды. А+В = S1 Ап = 0.000 0000 0111 1110 + Вп = 0.000 0001 0000 1011 S1 = 0.000 0001 1000 1001
-А-В = S2 -Ад = 1.111 1111 1000 0010 +(-Вд ) =1.111 1110 1111 0100 S2 = 1.111 1110 0111 0111
А-В = S3 Ап = 0.000 0000 0111 1110 +(-Вд ) =1.111 1110 1111 0100 S3 = 1.111 1111 0111 0011
-А +В = S4 -Ад = 1.111 1111 1000 0010 +Вп = 0.000 0001 0000 1011 S4 = 0.000 0000 1000 1101 При получении сумм S2 и S4, образовался перенос из знакового разряда, который следует отбросить. Проверим правильность полученных результатов, осуществив сложение в десятичной системе и сравнив результаты с S1, S2, S3, S4: А+В = 39310 = 18916 = 0.000 0001 1000 10012; -А-В = -39310 = -18916 = 1.111 1110 0111 01112; А-В = -14110 = -8D16 = 1.111 1111 0111 00112; -А+В = 14110 = 8D16 = 0.000 0000 1000 11012.
Задача 2. Даны два десятичных числа А = 27154 и В = 7589. Найти суммы (А+В) и (-А-В) в формате Н. Решение: А = 6А1216 = 0.110 1010 0001 0010; В = 1DА516 = 0.001 1101 1010 01012 Вычислим для этих чисел соответствующие прямые и дополнительные коды: Ап = 0.110 1010 0001 0010; Вп = 0.001 1101 1010 0101; -Ад = 1.001 0101 1110 1110; -Вд = 1.110 0010 0101 1011. Найдем суммы: А+В = S1 Ап = 0.110 1010 0001 0010 + Вп = 0.001 1101 1010 0101 S1 = 1.000 0111 1011 0111 Переведем число S1 из дополнительного кода: вычтем 1 и инвертируем все биты. Получим: ׀ S1׀ = 0.111 1000 0100 10012 = 3079310
S1 = -3079310 Вычисление в десятичных числах дает: 27154 + 7589 = 3474310 Заметим, что -30793 = 34743 – 65536 = 34743 – 216
-А-В = S2 10.000 1111 1111 1100 (перенос) -Ад = 1.001 0101 1110 1110 + -Вд = 1.110 0010 0101 1011 S2 =.0.111 1000 0100 1001 S2 = 0.111 1000 0100 10012 = 3079310 Вычисление в десятичных числах дает: -27154 – 7589 = -3474310 Заметим, что 30793 = -34743 + 65536 = -34743 + 216 Полученные суммы не соответствуют результатам проверки, т.к. при сложении положительных чисел получили отрицательное S1 и при сложении отрицательных чисел получили положительное S2. Это происходит в результате переполнения разрядов и при появлении такой ошибки операционная система компьютера вырабатывает запрос на прерывание программы.
Задача 1. Упростить логическое выражение = =
Задача 2. Упростить логические выражения:
и Решение: 1) =
2) Задача 3. Построить таблицу истинности для логического выражения
Задача 4. Построить таблицу истинности для логического выражения
Задача 4. Булевы выражения - это метод описания принципа работы логической схемы. Таблицы истинности – это другой метод описания работы логической схемы. Синтез (конструирование) логических схем начинается с составления таблицы истинности. Затем информация о правилах работы логической схемы, которая задана в виде таблицы, преобразуется в булево выражение. Основной принцип перехода от таблицы истинности к булеву выражению состоит в том, что в булево выражение включаются те комбинации входных переменных, которые дают единицу выходной переменной в таблице истинности. Разработать булево выражение по таблице истинности, которая имеет следующий вид:
Ответ.
Задача 5. Упростить выражение и построить логическую схему для выражения Решение: Задача 6. Упростить выражение и построить логическую схему для выражения
Задача 7. Сложение двоичных чисел выполняется в соответствии с таблицей истинности
Разработать по этой таблице булево выражение и синтезировать схему полусумматора из базовых логических элементов. Решение: Из таблицы видно, что состояние выхода переноса С1 можно описать булевым выражением С1 = a× b. Следовательно, схемной реализацией этого выражения будет схема И. Состояние выхода полусумматора будет описываться выражением . Задача 8. Разработать по таблице истинности булево выражение и синтезировать схему триггера из базовых логических элементов.
Решение: Для получения булевого выражения для значений Q и составим так называемые карты Карно (слева для Q, справа для ):
Эти диаграммы также, как и таблица, описывают значения Q и . Значения выходных величин следует искать на пересечении строки и столбца по соответствующим значениям входных и выходных величин (чтобы учесть «Предыдущее состояние» при S=R=0. Из этих диаграмм наглядно видно, что Недопустимое значение S=R=1дает при вычислении по этим формулам дает Q= =0, что противоречит логике схемы. Комбинация входных сигналов S=R=1 является запрещенной и требует специальных схемотехнических решений, чтобы её не допустить. Это является недостатком RS-триггера. Преобразуем полученные формулы:
Задача 9. Создать булевы выражения по таблицам истинности и разработать логические схемы:
Решение:
Возможны различные способы построения логических схем, реализующих заданные функции. Выбор того или иного варианта зависит от дополнительных требований к схеме. В частности, схема для Y3, соответствующая последнему выражению, проще, чем исходному, однако для вычисления по ней требуется 4 такта, в то время как по исходному выражению – три. Предположим, что нам требуется построить автомат, реализующий совместное вычисление всех трех функций Y1, Y2, Y3. В этом случае удобнее будет воспользоваться исходными выражениями для функций, т.к. можно будет использовать промежуточные результаты для вычисления нескольких функций. Схема:
Задача 10. Разработать логическую схему 2-х уровнего иерархического управления организацией. Решение: Иерархическая структура – многоуровневая форма организации объектов со строгой соотнесенностью объектов нижнего уровня определенному объекту верхнего уровня. «У подчиненного может быть только один руководитель». Графически представляется в виде дерева.
Задача 1. Количество информации по Хартли рассчитывается по формуле [бит], где N-число возможных состояний объекта; m-основание системы счисления (количество символов, применяемых в алфавите); n-число разрядов в сообщении. Рассчитать количество информации, содержащееся в изображении черной точки. Решение: Для решения этой задачи надо определить число возможных состояний объекта, т.е., например, экрана монитора. Поскольку в задаче это не детализируется, сделаем следующие предположения: 1) нас интересует состояние только одного пикселя, который изображает черную точку; состояние остальных пикселей может быть любым, и для данной задачи несущественно; 2) качество цветопередачи 32 бита (максимальное качество типичного ЖК-монитора). Тогда: N=mn =232 Информация о цвете каждой точки передается 32 битами. Количество информации по Хартли будет равно I= log2N = log2mn = nlog2m = 32log22=32бит.
Задача 2. Подсчитать объем данных, количество информации в сообщении «Я изучаю информатику» и коэффициент информативности сообщения Решение: Не будем учитывать пробелы и различие между большими и малыми буквами, примем размер алфавита 32 символа. Длина сообщения равна 18 символам. 1) Объем данных равен количеству символов в сообщении: Vd = n = 18 символов Или, при двоичном (5-битном) представлении: V = n log2m = 18*log2 (32) = 18*5 = 90 бит. 2) количество информации рассчитаем по Шеннону. Составим таблицу частот повторения символов в сообщении:
Количество информации: , или 3, 68*18 = 66, 3 бит на сообщение. 3) коэффициент информативности сообщения С=1/Vd = 66, 3/90 = 0, 737. Задача 3. Количество информации как разность энтропий рассчитывается по формуле I = Н(α ) - Н(β ) ≤ 1, где Н(α ) априорная энтропия, а Н(β )-апостериорная энтропия. Энтропия системы (объекта), имеющая N возможных состояний, согласно формуле Шеннона, равна , У монеты утяжелили одну сторону и вероятности выпадения сторон стали Р1 = 1/3, Р2 = 2/3. Подсчитать количество информации, которое получаем при выпадении одной из сторон. Решение: Под априорной энтропией в данном случае следует понимать энтропию двух возможных исходов (орел - решка), считая, что априори эти исходы равновероятны. После проведения опытов мы получаем апостериорную энтропию: возможны два исхода, но один из них в два раза более вероятен, чем другой. Количество информации в этом случае равно: I = H(α ) – H (β )= - (½ log2½ + ½ log2½ ) + (⅔ log2⅔ + ⅓ log2⅓ ) = 1 – 0, 9183 = = 0, 0817 бит/символ (т.е. на один исход)
Задача 4. При представлении информации в компьютере или передачи ее по каналам связи информация кодируется числовыми кодами. Одно и то же количество разрядов кода в различных системах счисления может передавать различное количество информации. Эту зависимость можно представить в виде соотношения , где N число возможных состояний объекта; m – основание системы счисления (количество символов, применяемых в алфавите); n – число разрядов в сообщении. |
Последнее изменение этой страницы: 2017-03-14; Просмотров: 365; Нарушение авторского права страницы