Контрольные задания. 1. Перевести число 137 в 8-ричную, 6-ричную и двоичную систему счисления

1. Перевести число 137 в 8-ричную, 6-ричную и двоичную систему счисления.

2. Перевести 0.715₍₁₀₎ в 2-ную, 3-ную, 5-ричную системы счисления.

3. Перевести 103.65₍₇₎, 11101.101₍₂₎, 216.52₍₈₎ в десятичную систему счисления.

4. Определить, какое число больше:

FD5(₁₆₎ или 8419₍₁₀₎; 22₍₈₎ или 44₍₅₎; 11011011101₍₂₎ или 51_(6).

5. Перевести число 15364₍₈₎ в X₍₂₎, X₍₁₆₎,X₍₄₎; число BAD₍₁₆₎ в X₍₂₎, X₍₈₎, X₍₄₎; число 10111101011101₍₂₎ ® в X₍₈₎, X₍₁₆₎, X₍₄₎.

6. В какой системе счисления справедливо равенство?

315 + 62 = 410

163 + 240 = 423

121 + 40 = 211

7. Представить в дополнительном коде в соответствующих системах счисления числа:

А = 3629_(10), С = - 210112_(3), В = -5710₍₁₀₎, D = 211101₍₃₎

8. Представить в дополнительном коде в формате Shortint числа

А = 53 и А = - 53₍₁₀₎; В = 47 и В = - 47₍₁₀₎.

9. Найдите значения чисел А, В, если их дополнительные коды

ДК(А)= 0 2371₍₁₀₎, ДК(А)= 1 2371₍₁₀₎, ДК(В)= 1 2302₍₅₎, ДК(В)= 0 2302₍₅₎.

6. Обработка чисел в компьютере

6.1 Выполнение операций сложения

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

При этом знаковый разряд участвует в операциях по правилам двоичного сложения. Покажем это на примерах.

Пример 1. Найти сумму (X + Y), если:

1) X = 126₍₁₀₎ 0 126

Y = - 26₍₁₀₎ 1 974

0 100

знак результата + (код 0), результат +100₍₁₀₎.

2) X = - 512₍₁₀₎ 1 488

Y = - 390₍₁₀₎ 1 610

1 098

Знак результата (-) (код 1), результат в дополнительном коде. Перевод отрицательного числа из дополнительного кода в прямой дает результат - 902₍₁₀₎.

3) X = - 850₍₁₀₎ 1 150

Y = + 429₍₁₀₎ 0 429

1 579

знак (-), результат в ДК, обратный перевод в прямой код - 421_(10).

4) X = - 2101₍₃₎ 1. 0122

Y = + 1011₍₃₎ 0. 1011

1. 1210

результат (-), результат - 1020₍₃₎.

5) X = + 500₍₁₀₎ 0 500

Y = + 739₍₁₀₎ 0 739

1 239

!!! Признак переполнения – отрицательный знак результата при сложении двух положительных чисел и наоборот – положительный знак результата при сложении двух отрицательных чисел.

6) X = - 500₍₁₀₎ 1 500

Y = - 739 ₍₁₀₎ 1 261

0 761

Пример 2. Представить числа в ДК с учетом разрядной сетки 1 байт и выполнить операцию сложения.

X = - 3₍₁₀₎ 11111101

Y = + 3₍₁₀₎ 00000011

00000000 ® +0

6.2 Сложение нормализованных чисел

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

Даны два нормализованных числа – A = m _A × р^{k A}, B = m _B × р^{k B}.

Алгоритм сложения чисел в форме с ПЗ.

1. Проверить равенство порядков слагаемых k _A^, k _B. Если порядки не равны, то увеличить меньший порядок до большего.

2. Если меньший порядок был увеличен на m единиц, то необходимо мантиссу этого числа сдвинуть на m разрядов вправо с потерей младших разрядов.

3. Провести сложение мантисс.

4. Проверить условие нормализации мантиссы результата, и провести ее, если условие не соблюдается.

Пример 3.Пустьпод мантиссу отводится n =5 разрядов.

а) А₍₁₀₎ = 0.13840 × 10³

В₍₁₀₎ = 0.16430 × 10¹

Порядок числа В необходимо увеличить на 2, при этом мантиссу В сдвигаем вправо на 2 разряда (теряя младшие разряды).

В¹ = 0.00164 А+В¹

0.13840

0.00164

0.14004 - мантисса удовлетворяет условиям нормализации.

Ответ: А + В = 0.14004 × 10³

б) А₍₂₎ = 0.11011 × 2³

В₍₂₎ = 0.11111 × 2⁵

Порядок числа А необходимо увеличить на 2, при этом мантиссу А сдвигаем вправо на 2 разряда (теряя младшие разряды).

m_А’ = 0.00110.

Выполняем сложение мантисс

0.00110

0.11111

1.00101 – мантисса результата не удовлетворяет условиям нормализации (больше 1).

Проведем нормализацию результата и увеличение порядка.

Ответ: А + В = 0.10010 × 2⁶

!Из-за ошибок усечения (отбрасывания) младших разрядов при сложении вещественных чисел не выполняется ассоциативность сложения, то есть (а + b) + c ¹ a + (b + c)

Пример 4. Найти сумму чисел, если для представления мантиссы отведено 4 разряда: 2 ½ + 1/8 + 1/8.

2 ½ = 0.1010 × 2² 0,1010 × 2²

1/8 = 0.1000 × 2^-2 0,0000 × 2² (после выравнивания порядков)

Проведем сложение в порядке, указанном в задании.

2 ½ + 1/8 0,1010 × 2²

0,0000 × 2²

0.1010 × 2² - результат равен первому слагаемому

Добавляем к результату еще 1/8:

0.1010 × 2²

0.0000 × 2²

0.1010 × 2²

Ответ: 0.1010 × 2².

Поменяем порядок сложения:

1/8 + 1/8 0,1000 × 2^-2

0,1000 × 2^-2

1,0000 × 2^-2 ® 0,1000 × 2^-1

Добавляем к результату 2 ½.

0,1010 × 2² 0.1010

0,1000 × 2^-1 0.0001

0.1011 × 2²

Ответ: 0.1011 × 2² – правильный результат.

Следовательно, при сложении вещественных чисел важен порядок их сложения. Проблема состоит в том, что при сложении большого и малого числа малое число может отсекаться.

Поэтому общее правило сложения звучит так:

– сначала складываем небольшие числа, надеясь, что в сумме, они дадут число, которое можно сложить с большим.

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

6.3 Выполнение операции умножения

6.3.1 Общий алгоритм умножения

В компьютере операция умножения сводится к операциям сложения и сдвига. Алгоритм умножения для любой позиционной системы счисления приведен на рисунке 6.1.

В зависимости от того, с какого разряда начинается умножение, сдвиг сумматора будет вправо или влево:

- если с младшей цифры – то сумматор сдвигается вправо;

- если со старшей цифры – то сумматор сдвигается влево.

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

Пример 5. Найти произведение чисел.

а) 321₍₁₀₎ * 23₍₁₀₎

со старшей цифры множимого с младшей цифры

321 321

23 23

642 963

963642

7383 7383

Ответ: 321₍₁₀₎ * 23₍₁₀₎ = 7383₍₁₀₎.

б) 110110₍₂₎*1011₍₂₎

110110 110110

1011 1011

110110 110110

000000 110110

110110 000000

110110110110.

1001010010 1001010010

Ответ: 110110₍₂₎*1011₍₂₎ = 1001010010₍₂₎ .

Умножение с младших разрядов более предпочтительно, так как при сдвиге сразу формируется очередной младший разряд произведения.

6.3.2 Особенности умножения в форме с плавающей запятой

Напомним, что число в форме с плавающей запятой представляется в виде X _(р) = ± m _(р) ×10^{± kр},

где m – мантисса, k – порядок, р – основание системы счисления ^.

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

Последовательность шагов при умножении чисел (X= m_x × p^kx,Y= m_y × p^ky)

в форме с плавающей запятой:

1. определяется мантисса произведения m_* = m_x × m_y с условием нормализации. Нарушение нормализации может быть только вправо (0 после точки) и только на 1 разряд;

2. определяется порядок произведения k*= (k_x + k_y) с учетом нормализации мантиссы;

3. знак произведения определяется на основе знаков сомножителей следующим образом:

0 + 0 = 0,

0 + 1 = 1,

1 + 0 = 1,

1 + 1 = 0,

то есть знак произведения равен двоичной сумме знаков сомножителей – Знак * = знак x Å знак y.

Получающийся после умножения код имеет 2 n разрядов. Его приходится округлять до n разрядов (ограничение разрядной сетки). Для правильного округления в сумматоре надо иметь, по крайней мере, (n+ 2) разряда. Все сдвиги, выходящие за эти разряды можно терять, экономя время на сложении частичных произведений.

Однако в «больших» компьютерах используются схемы, позволяющие получить все 2 n разрядов. Делается это в целях повышения точности, так как округление при умножении дает быстрое накопление погрешности.

6.4 Деление чисел

Деление – наиболее трудоемкая операция и встречает при своей реализации наибольшие трудности.

Общая схема деления состоит из однотипных шагов (рисунок 6.2).

Для получения очередной k -ой цифры частного необходимо:

1) из остатка, полученного после определения (k -1) цифры (для 1-го шага таким остатком является делимое), последовательно вычитают делитель до получения после вычитания первого отрицательного числа. Очередная цифра частного равна этому числу вычитаний;

2) к полученному отрицательному результату добавляется делитель (восстановление остатка). Полученное число образует остаток для следующего шага;

3) сдвигают либо делитель на 1 разряд вправо, либо остаток на 1 разряд влево и переходят к п.1.

Вычитание делителя сводится к операции сложения в дополнительном коде, как было показано выше. Операции со знаком выполняются по правилам двоичной арифметики.

Число вычитаний в каждом цикле не более р – основание системы счисления. Число циклов – не более n +3. 3 дополнительных разряда – один, соответствует первой цифре частного, нужен для определения переполнения, два других – последние разряды частного для правильного округления результата до n разрядов.

Пример 6. Разделить 59₍₁₀₎/27₍₁₀₎.

Дополнительный код делителя ДК(27₍₁₀₎) = 1.73₍₁₀₎

	знак	разряд 1	разряд 2	частное
,,
всего было 2 вычитания, в частное записываем 2.
			результат >0, продолжаем вычитание
			результат >0, продолжаем вычитание
				результат <0, формируем цифру частного
				восстановление остатка
всего было 1 вычитание, в частное записываем 1				сдвигаем делитель, начинаем вычитание
			результат >0, продолжаем вычитание
			результат <0, формируем цифру частного
				восстановление остатка
				продолжаем процесс…

Ответ: 59₍₁₀₎/27₍₁₀₎ = 2.1.. ₍₁₀₎

Контрольные вопросы.

1. Представить в дополнительном коде и выполнить операции сложения А+В в соответствующих системах счисления:

А = 3629₍₁₀₎ А = - 210112₍₃₎

В = -5710₍₁₀₎ В = 211101₍₃₎.

2. Представить в ДК и выполнить в формате Shortint операцию А+В.

А = 53 А = - 53₍₁₀₎ А = -53₍₁₀₎ А = 53₍₁₀₎

В = 47 В = 47₍₁₀₎ В = - 47₍₁₀₎ В = -47₍₁₀₎.

3. Представить в форме ПЗ и выполнить операции А+В, А-В для чисел:

А = 113,5₍₁₀₎, В = 9964 ₍₁₀₎ (4 разряда под мантиссу);

А = 11101,101₍₂₎, В = 10,1101₍₂₎ (8 разрядов под мантиссу).

7. Кодирование графической и звуковой информации

7.1 Представление изображений

По сравнению с методами кодирования/хранения символов и чисел способы представления графической информации находятся в начале своего развития и не настолько стандартизированы.

В соответствии с методами, применяемыми для их представления, все изображения можно разделить на 2 категории: растровые (bitmap techniques) и векторные (vectortechniques).

Растровые изображения представляют собой набор точек, которые называются пикселами (pixel). Самое простое представление имеет вид длинной последовательности битов, каждый из которых равен 0 или 1 (белый/черный) цвет пиксела. Цветные изображения намного сложнее, так как каждый пиксел должен быть представлен комбинацией битов, обозначающей его цвет.

Для отображения цвета многие внешние устройства компьютера (факсы, видеокамеры, сканеры) представляют цвет пиксела в виде комбинации трех составляющих: красный (Red), зеленый (Green) и синий (Blue) – RGB. Этот же подход с использованием 3-х составляющих цвета используется также в мониторе ПК.

Для представления интенсивности каждого цвета используется 1 байт. В этом случае для представления целого пиксела требуется 3 байта.

Формат, в котором одному пикселу соответствует 3 байта, подразумевает, что для изображения 1024´720 точек потребуется несколько мегабайтов памяти (1024*720*3 = 2 211 840 байт» 2.2МБ). Для того чтобы уменьшить требования к памяти, разработаны различные схемы сжатия.

Одна из них – GIF (Graphic Interchange Format). Этот стандарт сжатия решает проблему путем сокращения количества цветов, которые могут быть приписаны пикселу, до 256. Это означает, что значение каждого пиксела можно представить с помощью 1 байта, а не трех.

Каждому из 256 значений при помощи таблицы, которая называется палитрой, ставится в соответствие определенное сочетание RGB цветов. Изменяя палитру, можно менять цвета изображения.

Одному из цветов в формате GIF обычно присваивается значение «прозрачный», то есть через любой участок изображения, которому присвоен этот цвет, виден фон.

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

Другой стандарт сжатия – JPEG (Joint Photographic Experts Group) – очень эффективен для представления цветных фотографий.

В действительности стандарт JPEG включает в себя несколько способов представления, у каждого из которых своя задача. Например, в ситуациях, когда требуется предельная точность, формат JPEG предоставляет метод «без потерь», при котором не происходит потери информации во время кодирования изображения. В соответствии с этим алгоритмом хранится различие между соседними пикселами, а не интенсивность пикселов. Такой подход основывается на предположении, что в большинстве случаев различие между соседними пикселами можно представить более коротким двоичным кодом, чем их значение (относительное кодирование). Различия записываются при помощи кода переменной длины.

Но применение этого метода не дает изображений, размер которых можно легко менять, и поэтому используется редко. Вместо него используется базисный стандарт JPEG, который сокращает размер кода изображения, используя для определения состояния пикселов 2 параметра: яркость и цвет.

Причина такого разделения в том, что человеческий глаз более чувствителен к изменению яркости, чем к изменению цвета (например, 2 синих фона: на одном яркая синяя точка, на другом – зеленая точка той же яркости, что и фон. Человеческий глаз быстрее обнаружит яркую синюю точку, чем зеленую). Базисный формат использует это свойство человеческого глаза и кодирует каждую компоненту яркости, но при этом изображение разделяется на блоки размером 4 пиксела, и записывается только средний цвет каждого блока. Следовательно, в окончательном представлении сохраняются все быстрые изменения яркости, но при этом стираются быстрые изменения цвета.

Дополнительное пространство экономится при записи изменений яркости и цвета, а не их фактических значений. Степень различия соседних пикселов можно представить более коротким двоичным кодом, чем тот, который потребовался бы для записи фактических значений цвета. Например, для последовательности кодов (970 980 500) изменение значение может быть закодировано так: (970(база), +10, -320).

При помощи стандарта JPEG можно кодировать высококачественные цветные изображения, используя двоичный код, который занимает примерно в 20 раз меньше памяти, чем код формата «три байта на пиксел».

Растровый формат представления изображений имеет один недостаток, а именно – размер изображения не может быть произвольно изменен. В сущности, единственный способ увеличить изображение – увеличить размер пикселов. Но это приводит к «зернистому» искажению изображения.

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

Однако векторный формат не обеспечивает фотографического качества изображений, которое доступно в растровом формате. Именно поэтому растровый формат используется в современных цифровых камерах.

7.2 Представление звука

При наиболее распространенном способе кодирования звуковой информации амплитуда сигнала измеряется через равные промежутки времени и записываются полученные значения. Вопросы, связанные с преобразованием непрерывного сигнала в дискретный («оцифровывание» звука) частично рассматривались в 1 главе пособия. В частности, повторим теорему Котельникова о точках отсчета: непрерывный сигнал можно полностью отобразить и точно воссоздать по последовательности измерений или отсчетов величины этого сигнала через одинаковые интервалы времени, меньше или равные половине периода максимальной частоты, имеющейся в сигнале.

Этот способ кодирования используется не первый год в дальней телефонной связи (через спутник). Частота дискретизации в этом случае – 8000 отсч./сек. Такой частоты недостаточно для высокой точности воспроизведения музыки. Для получения качественного звучания на современном компакт-диске используется частота дискретизации 44100 отсч/сек.

Для данных, полученных при каждом отсчете, отводится 16 бит памяти (или 32 - для стереозаписей). Следовательно, для хранения 1 сек требуется порядка 1млн. бит.

В музыкальных синтезаторах, компьютерных играх и звуковых сигналах, сопровождающих веб-страницы, широко используется более экономная система кодирования, которая называется цифровым интерфейсом музыкальных инструментов (MIDI – Musical Instrument Digital Interface).

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

Это означает, что для кларнета, играющего ноту «ре» в течение двух секунд, потребуется 3 байта (инструмент, нота, длительность), а не более 2-х млн. бит, как в случае дискретизации с частотой 44100 отсчетов.

Стандарт MIDI скорее похож на нотную запись, которую читает исполнитель, чем на само исполнение. Издержки метода – музыкальная запись в стандарте MIDI может звучать по-разному в исполнении различных музыкальных синтезаторов.

В заключение отметим, что исследования в области сжатия данных представляют собой широкое поле деятельности. Существует множество различных техник сжатия звуковых и видеоданных. Например, группой Motion Picture Experts Groupe (MPEG – Экспертная группа по вопросам движущегося изображения), входящей в состав ISO, были разработаны методы, подобные тем, которые используются в стандарте JPEG, для того чтобы ввести стандарты кодирования (сжатия) движущихся изображений. Согласно этому стандарту сначала кодируется первое изображение последовательности, подобно тому, как это делается в базисном стандарте JPEG, а затем при помощи методов относительного кодирования записываются оставшиеся изображения.

Контрольные вопросы.

1. В чем состоят преимущества векторной графики по сравнению с растровой? Каковы преимущества растровой графики?

2. Предположим, что стереозапись одного часа музыки закодирована с частотой дискретизации 44100 отс./сек. Как размер закодированного сигнала соотносится с емкостью компакт-диска?

3. Какая особенность человеческого глаза используется стандартом JPEG?ек. отс./жим, что стереозапись одного часа музыки закодирована с частотой дисктеризации я.му, как это делаетсяя

Список литературы

1. Брукшир Дж. Информатика и вычислительная техника. 7-е изд. – СПб.: Питер, 2004. – 620с.

2. Стариченко Б.Е. Теоретические основы информатики: Учебное пособие для вузов. – 2-е изд. – М.: Горячая линия – Телеком, 2003. – 312 с.

3. Острейковский В.А. Информатика: Учеб. для вузов. М.: Высшая школа, 2001. – 511 с.

4. Таненбаум Э. Архитектура компьютера. 4-е изд. – СПб.: Питер, 2003. – 704 с.

5. Вальциферов Ю.В., Дронов В.П. Введение в информатику./Моск. гос. ун-т экономики, статистики и информатики. – М.: МГУЭСИ, 2000. – 67с.

6. Колемаев В.А., Калинина В.Н. Теория вероятностей и математическая статистика: Учебник. /Под ред. В.А.Колемаева. – М.: ИНФРА-М, 2001. – 302 с.

Учебное издание