Полная версия

Главная arrow Информатика arrow Архитектура ЭВМ и вычислительных систем

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Информация, кодирование и обработка в ЭВМ

Понятие «информация» является таким же фундаментальным, как понятия «материя», «энергия» и другие философские категории. Это атрибут, свойство сложных систем, связанное с их развитием и самоорганизацией [24, 25]. Известно большое количество различных определений информации, отличие информации от данных, знаний и пр. Мы здесь ограничимся только рассмотрением некоторых практически важных понятий и определений.

Определение и классификация информации

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

В обиходе информацией называют любые данные или факты, которые представляют какой-либо интерес. Например, сообщение о каких-либо событиях, о чьей-либо деятельности и т. п.

«Информировать» в этом смысле означает «сообщить нечто, неизвестное раньше».

В технике под информацией понимают сообщения, передаваемые в форме знаков или сигналов.

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

Приведем несколько определений информации:

  • • отрицание энтропии (Л. Бриллюэн);
  • • мера сложности структур (Моль);
  • • отраженное разнообразие (Урсул);
  • • содержание процесса отражения (Тузов);
  • • вероятность выбора (Яглом);
  • • снятая неопределенность наших знаний о чем-то (К. Шеннон);
  • • обозначение содержания, полученного из внешнего мира в процессе нашего приспособления к нему и приспособления к нему наших чувств (Н. Винер).

Информация может классифицироваться, например, по следующим основаниям:

  • • признаки, отражающие структуру данных и форму представления информации (табл. 1.2);
  • • содержание предметной области применения.

Таблица 1.2. Некоторые классы информации (по структуре и форме)

Основание для классификации

Классы информации

По уровням сложности

Сигнал

Сообщение,

документ

Информационный массив

Информационный ресурс

По типу сигнала

Аналоговая

(непрерывная)

Цифровая

(дискретная)

По уровням доступа и организации

Данные в регистровой памяти

Данные в оперативной памяти

Файлы данных на внешних устройствах

Базы данных

По способам кодирования и представления (данные, файлы и БД)

Цифровая (вычислительные данные, двоичные)

Символьная (алфавитно-цифровая, строчная)

Графическая

По организации данных (файлы и БД)

Табличная

Текстовая

Графическая

Аналоговая информация. Исторически первой технологической формой получения, передачи, хранения информации являлось аналоговое (непрерывное) представление звукового, оптического, электрического или другого сигнала (сообщения). Магнитная аудио- и видеозапись, фотографирование, запись на шеллачные или виниловые грампластинки, проводное и радиовещание — основные способы хранения и передачи информации в аналоговой форме (рис. 1.1). Заметим, что с начала 50-х гг. (а во многом и сейчас) под термином теория информации подразумевались теоретические методы, связанные с обеспечением как можно более точного приема, передачи, записи, воспроизведения, преобразования непрерывных сигналов (основные понятия — линейность, нелинейность, шум, спектр сигнала, полоса пропускания и пр.).

Аналоговый сигнал и его дискретная (цифровая) аппроксимация

Рис. 1.1. Аналоговый сигнал и его дискретная (цифровая) аппроксимация

(оцифровка)

Более чем 50-летнее развитие теории и практики ЭВМ приводит к вытеснению (в том числе и на бытовом уровне) аналоговых устройств и сигналов цифровыми.

Аналого-цифровое (дискретное) преобразование — АЦП (analog-to-digital conversion — ADC) заключается в формировании последовательностей л-разрядных двоичных слов, представляющих с заданной точностью аналоговые сигналы.

Наиболее популярным примером, несомненно, является аудиокомпакт-диск (digital audio CD). В этом случае звуковой сигнал (см. рис. 1.1) преобразуется в дискретную аппроксимацию («многоуровневый ступенчатый сигнал»), при этом вначале происходит квантование во времени, которое заключается в измерении в дискретные промежутки времени необходимого параметра аналогового сигнала.

Затем осуществляется квантование по амплитуде сигнала. При квантовании аналогового сигнала происходит округление его мгновенных значений до некоторой заданной фиксированной величины, называемой уровнем. Наименьшее изменение аналогового сигнала, которое регистрируется устройством, осуществляющим преобразование, называется разрешением.

При квантовании по амплитуде каждая ступенька представляется последовательностью бинарных цифровых сигналов. Принятый в настоящее время стандарт аудио CD использует так называемый «16-разрядный звук с частотой сканирования 44 кГц». Для рис. 1.1 «в переводе на нормальный язык» это означает, что «длина ступеньки» (т) равна 1/44 000 с, а «высота ступеньки» (5) составляет 1/65 536 максимальной громкости сигнала (поскольку 216 = 65 536). При этом частотный диапазон воспроизведения составляет 0—22 кГц, а динамический диапазон — 96 дБ (недостижимое для магнитной или механической звукозаписи качество записи).

Аналого-цифровые (дискретные) преобразователи чаще всего изготавливаются в виде интегральных схем. В необходимых случаях осуществляется обратное — дискретно-аналоговое или цифроаналоговое преобразование — ЦАП (digital-to-analog conversion — DAC).

Цифровая информация. Дискретные сигналы по сравнению с аналоговыми имеют ряд важных преимуществ: помехоустойчивость, легкость восстановления формы, простоту аппаратуры передачи.

В дальнейшем оцифрованный аналоговый сигнал может передаваться или записываться в различных форматах, например:

  • • РСМ (Pulse Code Modulation — им пульс но-кодовая модуляция) — способ цифрового кодирования сигнала с помощью записи абсолютных значений амплитуд A{t) (рис. 1.2, а). Именно в таком виде данные записываются на аудио CD;
  • • ADPCM (Adaptive Delta PCM — адаптивная относительная им пул ьсно-кодовая модуляция) — запись значений сигнала
Примеры кодирования аналоговых сигналов

Рис. 1.2. Примеры кодирования аналоговых сигналов: а — импульсно-кодовая модуляция; б — адаптивная относительная импульсно-кодовая модуляция

не в абсолютных, а в относительных приращениях (АД(/)) амплитуд (рис. 1.2, б и т. д.).

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

При обмене данными по каналам используется три метода передачи данных:

  • • симплексная (однонаправленная) передача (телевидение, радио);
  • • полудуплексная (прием и передача информации осуществляются поочередно);
  • • дуплексная (двунаправленная), каждая станция одновременно передает и принимает данные.

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

При асинхронной передаче каждый символ передается отдельной посылкой (рис. 1.3).

Стартовые биты предупреждают приемник о начале передачи. Затем передается символ. Для определения достоверности передачи используется бит четности (бит четности равен 1, если количество единиц в символе нечетно, и 0 — в противном слу-

0

1

1

0

1

0

0

##

-1— г

Два стартовых бита

Передаваемый символ

четности бит

а

ГГ ТГ тг гг

Бнты Поле данных я Код Символ

синхронизации (передаваемые символы) обнаружения окончания

ошибки передачи

Рис. 1.3. Асинхронная (а) и синхронная (б) передача данных

чае. Последний бит («стоп-бит») сигнализирует об окончании передачи.

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

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

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

Примеры дискретных сигналов

Рис. 1.4. Примеры дискретных сигналов: а — двоичный; б — троичный; в — биполярный; г — элементы импульсного

сигнала

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

Реальный импульсный сигнал (рис. 1.4, г) характеризуется амплитудой ио, длительностью импульсов /и, передним фронтом /ф1, задним фронтом /ф2 и периодом повторения Г. Отношение длительности периода Т к длительности импульсов /и называется скважностью.

Измерение количества информации

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

В качестве единицы информации Клод Шеннон предложил принять один бит (от англ, bit — binary digit — двоичная цифра).

В вычислительной технике битом называют наименьшую «порцию» памяти компьютера, необходимую для хранения одного из двух знаков 0 и 1, используемых для машинного представления данных и команд.

Поскольку бит — слишком мелкая единица измерения, на практике чаще применяется более крупная единица — байт, равная восьми битам. В частности, восемь бит требуется для того, чтобы закодировать любой из 256 символов ASCII (256 = 28).

«Имеют хождение» также более крупные производные единицы информации: килобайт (Кбайт, КВ)=103 байт, мегабайт (Мбайт, МВ)= 103 Кбайт, гигабайт (Гбайт, GB) = 103 Мбайт, терабайт (Тбайт, ТВ) = 103 Гбайт, петабайт (Пбайт, РВ) = 103 Тбайт.

Заметим, что часто возникает неоднозначность в интерпретации, например, 1 Мбайта, который может рассматриваться как 1000 Кбайт (десятичный мегабайт), так и 1024 Кбайт (бинарный мегабайт). В табл. 1.3 приведены последствия такой неоднозначности.

Таблица 1.3. Отклонения, возникающие при одинаковом прочтении десятичных и двоичных префиксов единиц измерения информации

Префикс

Сокращение

Подразумеваемое

Десятичное

Относительное

двоичное значение

значение

отклонение

КИЛО

К

2io

ю3

1,024 = 1024/1000

мега

м

220

10е

1,0486 = 1 048 576/1 000 000

гига

г

го

со

о

10е

1,0737

тера

т

240

ю12

1,0995

пета

п

250

1015

1,1259

экса

э

2бо

ю18

1,1529

зетта

3

270

1021

1,1806

йотта

и

280

ю24

1,2089

Очевидно, что чем больше изображаемое число, тем большего значения может достигать расхождение, вызванное неоднозначным пониманием использованного префикса. В частности, разница между «двоичным» и «десятичным» килобайтом составляет 2,4 %, но между «двоичным» и «десятичным» гигабайтом — уже более 7 %. Для того чтобы разрешить эту путаницу, было предложено ввести двоичные префиксы.

В марте 1999 г. МЭК — Международная электротехническая комиссия (International Electrotecnical Comission — IEC) предложила новый стандарт для обозначения двоичных чисел. Префиксы МЭК схожи с привычными префиксами СИ (Международной системы измерения физических единиц) — они начинаются одинаково, но второй слог двоичных префиксов — бы (от англ. binary — «двоичный»). Стандарт был утвержден, но введенные названия используются нерегулярно, очевидно, из-за их необычности: «килобит» звучит привычнее, нежели «кибибит». Российский ГОСТ 8.417—2002 («Единицы величин») также определяет свое написание двоичных префиксов для байтов (табл. 1.4).

Таблица 1.4. Соответствие префиксов МЭК и ГОСТ 8.417—2002

Префикс

Сокращения МЭК для битов/байтов

Сокращение

ГОСТ 8.417—2002 (для байтов)

Значение

Киби, KiB

Kibibit, Кибибит, KibiByte, KiB, КиБ

Кбайт

210 =1024

Миби, MiB

Mibibit, Мибибит, MibiByte, MiB, МиБ

Мбайт

220 = 1 048 576

Гиби, GiB

Gibibit, Гибибит, GibiByte, GiB, ГиБ

Гбайт

230 = 1 073 741 824

Тиби, TiB

Тибибит, Gibibit, TibiByte, TiB, ТиБ

Тбайт

240 = 1 099 511 627 776

Пиби, PiB

Пибибит, ПиБ

Пбайт

250

Эксби

Эксбибит, ЭиБ

Эбайт

2бо

Зиби

Зибибит, ЗиБ

Збайт

270

Йоби

Йобибит, ЙиБ

Йбайт

о

со

CNJ

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

Двоичные префиксы используются:

  • • обычно в файловых менеджерах и другом программном обеспечении для краткого определения размеров файлов — если программа сообщает, что размер файла равен 100 Кбайт (100 КВ), то это соответствует приблизительно
  • 102,4 тыс. байт;
  • • производителями различных видов полупроводниковых запоминающих устройств (ОЗУ, ПЗУ, флэш-память), например «карта Secure Digital на 1 Гбайт»;
  • • емкость компакт-дисков (например, «700 Мбайт») задается обычно в «двоичных мегабайтах»;
  • • согласно ГОСТ 8.417—2002 приставки К-, М- и Г- (прописными буквами) применительно к байтам имеют двоичное значение.

Приставки «кило», «мега», «гига» трактуются как десятичные:

  • • в телекоммуникационных приложениях, например «канал на 128 килобит в секунду»;
  • • как исторически сложившаяся терминология при указании объема жестких дисков (диск на «40 гигабайт» имеет размер 40 млрд байт). Сторонники противоположного подхода обвиняют фирмы-производители в завышении цифр объема носителей с помощью более мелкой единицы («коммерческий мегабайт»);
  • • емкость DVD (4,7 гигабайт) также задается в десятичных гигабайтах;
  • • при неформальном общении (например, про файл в 100 тысяч байт могут сказать «файл в 100 килобайт»).

Есть и иные примеры, в частности, размер трехдюймовой дискеты в 1,44 Мбайт (включая служебные данные — загрузочный сектор, и таблицы FAT) задается в двоично-десятичных мегабайтах (один мегабайт равняется 1 024 000 байтам).

Для описания скорости передачи данных можно использовать термин бод. Число бод равно количеству значащих изменений сигнала (потенциала, фазы, частоты), происходящих в секунду. Первоначально бод использовался в телеграфии. Для двоичных сигналов нередко принимают, что бод равен биту в секунду, например 1200 бод = 1200 бит/с. Однако единого мнения о правильности использования этого термина нет, особенно при высоких скоростях, где число бит в секунду не совпадает с числом бод.

Кодирование символьной информации

Код {code) — совокупность знаков, символов и правил представления информации. Рассмотрим методы дискретного представления информации, или кодирования (которые, надо сказать, появились задолго до вычислительных машин). Первым широко известным примером является азбука Морзе (табл. 1.5), в которой буквы латиницы (или кириллицы) и цифры кодируются сочетаниями из «точек» и «тире». Воспользуемся данным кодом для иллюстрации основных понятий, связанных с кодированием (не вдаваясь в теорию кодирования).

Таблица 1.5. Фрагменты кода Морзе

Символ входного алфавита

Мнемоническое обозначение по МСС

Кодовая (знаковая) комбинация

А

alfa

В

bravo

• • ?

С

Charlie

D

delta

? ?

Е

echo

Y

yankee

  • • ? •
  • ?

Z

zulu

? ?

1

one

?

9

nine

  • ? ? •
  • ?

* Международный Свод Сигналов.

Кодируемые (обозначаемые) элементы входного алфавита обычно называют символами.

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

Кодирующие (обозначающие) элементы выходного алфавита называются знаками; количество различных знаков в выходном алфавите назовем значностью (-арностью, -ично-стью, например «бинарный» или «двоичный» код); количество знаков в кодирующей последовательности для одного символа — разрядностью кода.

Пространственно-временное расположение знаков кода приводит к понятиям параллельных или последовательных кодов. При последовательном коде каждый временной такт предназначен для отображения одного разряда слова. Здесь все разряды слова фиксируются по очереди одним и тем же элементом и проходят через одну и ту же линию передачи (например, радио- или оптические сигналы либо передача данных по двум проводам, двухжильному кабелю).

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

Для последовательного кода характерно временное разделение каналов при передаче информации, для параллельного — пространственное. В зависимости от применяемого кода различаются устройства параллельного и последовательного действия.

Применительно к азбуке Морзе (АМ):

  • символами являются элементы языкового алфавита (буквы К—Ъ или А—Я) и цифровой алфавит (здесь — цифры 0-9);
  • • знаками являются «точка» и «тире» (или «+» и «-» либо «1» и «0», короче — два любых разных знака);
  • • поскольку знаков два, АМ является двузначным (бинарным, двоичным) кодом, если бы их было 3, то мы имели бы дело с троичным, тернарным, трехзначным кодом;
  • • поскольку число знаков в АМ колеблется от 1 (буквы Е, Т) до 5 (цифры), здесь имеет место код с переменной разрядностью (в АМ часто встречающиеся в тексте символы обозначены более короткими кодовыми комбинациями, нежели редкие символы);
  • • поскольку знаки передаются последовательно (электрические импульсы, звуковые или оптические сигналы разной длины, соответствующие «точкам» и «тире»), АМ есть последовательный код.

Первые опыты телеграфной и радиосвязи осуществлялись именно посредством АМ, причем приемное устройство записывало импульсы переменной длины в виде «точек» и «тире» на движущуюся телеграфную ленту, однако уже в начале XX в. был осуществлен переход на 5-разрядный (5-битовый) телеграфный код.

В табл. 1.6, 1.7 приводится перечень наиболее известных кодов, некоторые из них использовались первоначально для связи, кодирования данных, а затем для представления информации в ЭВМ.

Таблица 1.6. Характеристики некоторых наиболее известных кодов

Наименование кода

Расшифровка/

перевод

Другие

названия

Разряд

ность

Комментарий

Baudot

Код Бодо

IA-1 — international alphabet № 1

5

В прошлом — европейский стандарт для телеграфной связи

М2

МККТТ-2

CCITT-2

IA-2

5

Телеграфный код, предложенный Международным Комитетом по телефонии и телеграфии (МККТТ) и заменивший код Бодо

ASCII-7

American Standard Code for Information Interchange

ISO-7

IA-5, USASCII, ANSI X3.4

7

Код для передачи данных, поддерживает 128 символов, включающих прописные и строчные символы латиницы, цифры, специальные значки и управляющие символы. После добавления некоторых национальных символов (10 бинарных комбинаций) был принят Международной организацией по стандартизации (150) как стандарт 180-7

ASCII-8

To же

8

Для внутреннего и внешнего представления данных в вычислительных системах. Включает стандартную часть (128 символов) и национальную (128 символов).

В зависимости от национальной части кодовые таблицы различаются

EBCDIC

Expanded Binary Coded Decimal Information Code

8

Предложен фирмой 1ВМ для машин серий 1ВМ/360-375 (внутреннее представление данных в памяти), а затем распространившийся и на системы других производителей

Hollerith

Код

Холлерита

Код перфокарт (ПК)

12

Предложен для ПК (1913 г.), затем использовавшийся для кодирования информации перед вводом в ЭВМ с ПК

UNICODE

UNIversal

Code

16

Поскольку в 16-разрядном иМСООЕ можно закодировать 65 536 символов вместо 128 в А8С11, то отпадает необходимость в создании модификаций таблиц кодов. NN10006 охватывает 28 000 букв, знаков, слогов, иероглифов национальных языков мира

Таблица 1.7. Фрагменты некоторых кодовых таблиц (указаны 16-ричные коды символов)

Символ

IA-2

Бодо

IS0-7

EBCDIC

ASCII-8

Холлерит

А

03

10

41

Cl

А1

900

в

19

Об

42

С2

А2

880

с

16

43

СЗ

АЗ

840

D

09

44

С4

А4

820

а

61

81

Е1

b

62

82

Е2

с

63

83

ЕЗ

d

64

84

Е4

. (точка)

1C

05

842

, (запятая)

ОС

09

242

: (двоеточие)

зв

4 0А

? (вопрос)

10

0D

3F

6F

5F

206

Избыточные коды

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

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

Широко используется для обнаружения ошибок в блоках данных также код с циклическим контролем — циклический избыточный код обнаружения ошибок (Cyclic Redundance Check — CRC). Здесь вычисляется контрольная сумма содержимого блока данных перед его передачей, включается в одно из полей блока, а затем повторно вычисляется после передачи. Несовпадение результатов свидетельствует об ошибке в передаваемом содержимом.

Корректирующие коды. В ответственных приложениях, требующих повышенной надежности хранения информации, применяются более серьезные, чем контроль четности, методы обеспечения целостности данных. К ним относятся корректирующие коды (Error Correction Code — ЕСС), позволяющие не только обнаруживать ошибки, но и восстанавливать искаженную информацию за счет ее избыточности. Так, существуют модули памяти со схемами ЕСС, в которых для хранения контрольной информации используется не один, а два бита, в которых хранится остаток от деления числа на 4 (деление по модулю 4). Благодаря этим данным схема ЕСС умеет обнаруживать и исправлять одиночные искаженные биты, а также обнаруживать (но не исправлять) двойные ошибки. Модули памяти с ЕСС обычно стоят заметно дороже и применяются в основном в серверах. В общем случае ЕСС применяются во всех современных дисковых и ленточных накопителях. За счет информационной избыточности закодированных данных удается восстанавливать поврежденные блоки информации длиной в сотни байт. Наиболее широко применяются помехоустойчивые коды Рида — Соломона (Reed — Solomon), а также код Хемминга, позволяющий исправлять одиночные ошибки, появляющиеся в блоках данных.

Кодирование и обработка чисел

Кроме кодирования символов, в ЭВМ очевидную важность имеет кодирование и представление чисел.

Системы счисления. Человек привык считать предметы десятками, сотнями: десять единиц образуют десяток, десять десятков — сотню, десять сотен — тысячу и т. д. Это — десятичная система счисления, которая не является единственно возможной (известна, например, двенадцатеричная система счисления).

Система счисления — способ именования и изображения чисел с помощью символов, имеющих определенные количественные значения. В зависимости от способа изображения чисел системы счисления делятся на:

  • • непозиционные;
  • • позиционные.

Непозиционные системы счисления. В такой системе цифры не меняют своего количественного значения при изменении их расположения в числе.

Самый простой и очевидный пример — система счисления, где количество обозначается I (палочкой/единицей):

  • 1 = 1;
  • 2 = П;
  • 5 = 11111;
  • 10 = I I I I I I I I I I.

Пусть далее следующие символы (цифры в гипотетической системе счисления) соответствуют числам (в десятичной системе счисления):

Я - 1;

— — 6;

га — 12;

* - 24;

Щ - 60;

4 - 365,

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

Тогда 444 можно записать по крайней мере двумя способами:

(365 + 60+ 12 + 6 +1);

^ЯсЗД2Я (6 + 1 + 365 + 60 + 12), т. е. сЗД^^Я = —Яс$21Ц?•

Такая система счисления является непозиционной, так как цифры не меняют своего количественного значения при изменении их расположения в числе.

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

Десятичная система счисления является позиционной, так как значение каждой цифры зависит от ее места (позиции) в числе.

Например,

  • 23 = 2 х 10 + 3;
  • 32 = 3 х 10 + 2

и 23 ф 32

Римская система счисления является смешанной, так как значение каждой цифры частично зависит от ее места (позиции) в числе. Так, в числах

VII

VI

IV

V обозначает 5, а I обозначает 1. Но, с другой стороны, важно, как цифры расположены относительно друг друга:

VII = 5 + 1 + 1 = 7;

VI = 5 + 1 = 6;

IV = 5 — 1=4.

Наиболее естественный способ представления числа в компьютерной системе заключается в использовании строки битов, называемой двоичным числом — числом в двоичной системе счисления (символ также может быть представлен строкой битов, или символа).

Основание позиционной системы счисления — количество (Р) различных цифр, используемых для изображения числа в позиционной системе счисления. Значения цифр лежат в пределах от 0 до Р - 1.

В общем случае запись любого числа N в системе счисления с основанием Р будет представлять собой ряд (многочлен) вида:

= ат , X Рт~1 + ат 2 X Рт~2 + ... + 0кхРк+ ...

... + и | х Р + #0 X Р + ... + С1_ | х Р + С1_2 х Р + ... + С1_5 х Р . (1.1)

Нижние индексы определяют местоположение цифры в числе (разряд):

  • • положительные значения индексов — для целой части числа разрядов);
  • • отрицательные значения — для дробной (у разрядов).

Максимальное целое число, которое может быть представлено в т разрядах:

Минимальное значащее, не равное 0 число, которое можно записать в 5 разрядах дробной части:

N.

ПИП

Имея в целой части числа т разрядов, а в дробной — 5, можно записать />"'+5 разных чисел.

Двоичная система счисления (основание Р= 2) использует для представления информации две цифры — 0 и 1.

Существуют простые правила перевода чисел из одной системы счисления в другую, основанные, в том числе, и на выражении (1.1).

Например, двоичное число 101110,101 равно десятичному числу 46,625:

101110,1012 = 1 х25 + 0х24+ 1 х23+ 1 х22+ 1 х21 + 0х2° +

+ 1 X 2“1 + 0 X 2'2 + 1 X 2-3 = 46,62510.

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

Например, двоичное число 010000012 равно 6510. Действительно, 64 х 1 + 1 х 1 = 65.

Вес

128

64

32

16

8

4

2

1

Цифра

0

1

0

0

0

0

0

1

Таким образом, для перевода числа из позиционной системы счисления с любым основанием в десятичную систему счисления можно воспользоваться выражением (1.1).

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

Л'цел = (((-Км х ат_2) X Р+ ... + а2) X Р+ а{) х Р+ а0);

Мдр = Р~1 х (Я-1 + х (я-2 + Р~1 х _з + ... + Р~1 X (а_5+ + Р~1 х аД...))).

Алгоритм перевода числа из десятичной системы счисления в систему счисления с основанием Р, основанный на этих выражениях, позволяет оперировать числами в той системе счисления, из которой число переводится, и может быть сформулирован следующим образом (при переводе смешанного числа следует переводить его целую и дробную части отдельно):

  • • для перевода целой части числа ее, а затем целые части получающихся частных от деления следует последовательно делить на основание Р до тех пор, пока очередная целая часть частного не окажется равной 0. Остатки от деления, записанные последовательно справа налево, образуют целую часть числа в системе счисления с основанием Р;
  • • для перевода дробной части числа ее, а затем дробные части получающихся произведений следует последовательно умножать на основание Р до тех пор, пока очередная дробная часть произведения не окажется равной 0 или не будет достигнута нужная точность дроби. Целые части произведений, записанные после запятой последовательно слева направо, образуют дробную часть числа в системе счисления с основанием Р.

Пусть требуется перевести смешанное число (например, 46,625) из десятичной в двоичную систему счисления.

  • 1. Переводим целую часть числа:
  • 46 : 2 = 23 (остаток 0);
  • 23 : 2 = 11 (остаток 1);
  • 11 : 2 = 5 (остаток 1);
  • 5:2 = 2 (остаток 1);
  • 2:2=1 (остаток 0);
  • 1:2 = 0 (остаток 1).

Записываем остатки последовательно справа налево — 101110, т. е.

  • 4610 = 101 1 102.
  • 2. Переводим дробную часть числа:
  • 0,625 х 2 = 1,250;
  • 0,250 x 2 = 0,500;
  • 0,500 х 2 = 1,000 (дробная часть равна 0 => стоп).

Записываем целые части получающихся произведений после запятой последовательно слева направо — 0,101, т. е.

0,62510 = 0,1012.

Окончательно: 46,625|0= 101110,1012.

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

Таблица 1.8. Перевод цифр из двоичной системы счисления в восьмеричную, шестнадцатеричную и десятичную и наоборот

Триада

Восьмеричная

цифра

Тетрада

Шестнадцатеричная

цифра

Десятичное

число

Двоично-десятичная

запись

000

0

0000

0

0

0000-0000

001

1

0001

1

1

0000-0001

010

2

0010

2

2

0000-0010

011

3

ООН

3

3

0000-0011

100

4

0100

4

3

0000-0100

101

5

0101

5

5

0000-0101

110

6

оно

6

6

0000-0110

111

7

0111

7

7

0000-0111

1000

8

8

0000-1000

1001

9

9

0000-1001

1010*

А

10

0001-0000

1011*

В

11

0001-0001

1100*

С

12

0001-0010

1101*

и

13

0001-0011

1110*

Е

14

0001-0100

1111*

Г

15

0001-0101

* Запрещены в двоично-десятичном представлении.

Шестнадцатеричная система счисления часто используется при программировании. Перевод чисел из шестнадцатеричной системы счисления в двоичную весьма прост — он выполняется поразрядно.

Для изображения цифр, больших 9, в шестнадцатеричной системе счисления применяются буквы А = 10, В = 11, С = 12, в = 13, Е = 14, Е = 15.

Например, шестнадцатеричное число Е17В в двоичной системе имеет вид: 1111000101111011, а в десятичной — 61819.

Двоично-десятичная система счисления получила большое распространение в современных компьютерах ввиду легкости перевода в десятичную систему и обратно. Она используется там, где основное внимание уделяется не простоте технического построения машины, а удобству работы пользователя. В двоично-десятичной системе счисления основанием системы счисления является число 10, но каждая десятичная цифра (0, 1, ..., 9) кодируется четырьмя двоичными цифрами.

Двоично-десятичная система не экономична с точки зрения реализации технического построения машины (примерно на 20 % увеличивается требуемое оборудование), но более удобна при подготовке задач и при программировании.

Представление чисел в ЭВМ

В ЭВМ применяются две формы представления чисел:

  • • естественная форма, или форма с фиксированной запятой (точкой) — ФЗ (ФТ);
  • • нормальная форма, или форма с плавающей запятой (точкой) — ПЗ (ПТ).

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

Например, пусть числа представлены в десятичной системе счисления и имеют пять разрядов в целой части числа (до запятой) и пять — в дробной части (после запятой). Числа, записанные в такую разрядную сетку, имеют вид:

+00721.35500;

+00000.00328;

-10301.20260.

Эта форма наиболее проста, естественна, но имеет небольшой диапазон представления чисел.

Диапазон значащих чисел N в системе счисления с основанием Р при наличии т разрядов в целой части и 5 разрядов в дробной части числа (без учета знака числа) будет таким:

р~5< уу< Рт - г.

Например, при Р- 2, т = 10 и у = 6 числа изменяются в диапазоне 0,015 < УУ< 1024. Если в результате операции получится число, выходящее за допустимые пределы, произойдет переполнение разрядной сетки, и дальнейшие вычисления теряют смысл. В современных компьютерах естественная форма представления используется как вспомогательная и только для целых чисел.

В памяти ЭВМ числа с фиксированной точкой хранятся в трех форматах:

  • • полуслово — это обычно 16 бит или 2 байта;
  • • слово — 32 бита или 4 байта;
  • • двойное слово — 64 бита или 8 байтов.

Отрицательные числа с ФТ записываются в разрядную сетку

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

Плавающая запятая (точка). В форме представления с плавающей запятой (точкой) число изображается в виде двух групп цифр:

  • • мантисса;
  • • порядок.

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

уу=±4/х Р±г,

где М — мантисса числа < 1);

г — порядок числа (целое число);

Р — основание системы счисления.

Например, приведенные ранее числа в нормальной форме запишутся следующим образом:

+0,721355 х 103;

+0,328 х Ю"3;

-0,103012026 х 105.

Нормальная форма представления обеспечивает большой диапазон отображения чисел и является основной в современных компьютерах. Так, диапазон значащих чисел в системе счисления с основанием Р при наличии т разрядов у мантиссы и ? разрядов у порядка (без учета знаковых разрядов порядка и мантиссы) будет:

р т Хр-(Р5< N <( - Р'”)х Р'А).

Например, при Р= 2, т = 22 и 5 = 10 диапазон чисел простирается примерно от Ю'300 до Ю300. Для сравнения отметим, что количество секунд, которые прошли с момента образования планет Солнечной системы, составляет около 1018.

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

Нормализованным называют такое число, в старшем разряде мантиссы которого стоит единица (следовательно, для нормализованных двоичных чисел 0,5 < М < 1).

Нормализованные, т. е. приведенные к правильной дроби, числа:

Ю,3510 = 0,103510 х 102;

0,00007245с = 0,7245с х 8“4;

Р5С,9В16 = 0,Р5С9В16 х 163.

Алгебраическое представление двоичных чисел. Для алгебраического представления чисел, т. е. для их представления с учетом знака, в вычислительных машинах используются специальные коды:

  • • прямой;
  • • обратный;
  • • дополнительный.

При этом два последних кода позволяют заменить операцию вычитания на операцию сложения с отрицательным числом. Дополнительный код обеспечивает более быстрое выполнение операций, поэтому в ЭВМ применяется чаще именно он.

Знак числа обычно кодируется двоичной цифрой, при этом:

  • • код 0 означает знак + (плюс);
  • • код 1 означает знак - (минус).

Пр ямой код числа N обозначим [N]пp.

Пусть N = а, а2, а3, ..., ат, тогда:

  • • при УУ> 0 [УУ]пр = 0, ах, а2, аъ, ..., ат;
  • • при N< 0 [ЛПпр = 1, ах, а2, а3, ..., ат;
  • • при N=0 имеет место неоднозначность [0]пр = 0, 0... = 1,0...

Если при сложении в ЭВМ оба слагаемых имеют одинаковый знак, то операция сложения выполняется обычным путем. Если при сложении слагаемые имеют разные знаки, то сначала необходимо выявить большее по абсолютной величине число, из него произвести вычитание меньшего по абсолютной величине числа, и разности присвоить знак большего числа.

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

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

Обратный код числа ./Vобозначим [УУ]обр.

Пусть N = ах, а2, а3, ..., ат и а обозначает инверсию а, т. е. если а = 1, то а = 0, и наоборот. Тогда:

  • • при ТУ > 0 [ЛПобр = 0, ах, а2, а3, ..., ат;
  • • при N <0 [ЛПобр= 1, ах, а2, а3, ..., ат;
  • • при N=0 имеет место неоднозначность [0]обр = 0,00...О =

= 1,11-1.

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

Например,

для N= 1011 [УУ]обр = 0,1011;

для УУ=-1011 [УУ]обр = 1,0100.

Дополнительный код числа N обозначим [Лфоп.

Пусть, как и выше, N = ах, а2, а3, ..., ат и а обозначает величину, обратную а (инверсию а), т. е. если а = 1, то а = 0, и наоборот. Тогда:

  • • при N > 0 [ЛПдоп = 0, йу а2, ау ..., ат,
  • • при УУ< 0 ДОП = 1, а2, а3, ..., ат + 0,00... 1.

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

Например,

для УУ= 1011 [УУ]Д0П = 0,1011;

для ^=-1100 [ЛДдоп = 1,0100;

для УУ=-0000 [УУ]Д0П = 10,0000 = 0,0000 (1 исчезает). Неоднозначности в изображении 0 нет.

Эмпирическое правило: для получения дополнительного кода отрицательного числа необходимо все символы этого числа инвертировать, кроме последней (младшей) единицы и тех нулей, которые за ней следуют.

Данные, обрабатываемые в современных процессорах. Подводя итоги вышеизложенному, приведем типы данных (табл. 1.9), используемые в процессорах Intel (Pentium) и AMD (Кб—К8).

Таблица 1.9. Примеры некоторых реальных типов данных современных процессоров

Вид данного

Английский

эквивалент (или расшифровка)

Пояснения

Форматы данных, обрабатываемых блоками АЛУ 32-разрядных процессоров

1. Двоичные и строковые

Бит

Bit Mm

дає'

бит

нимальная единица информации. Бит в памяти за-гся базой (адресом слова) и смещением (номером а в слове)

Битовое поле

Bit Field Гру

чем

ппа до 32 смежных бит, располагающихся не более в 4 байтах

Битовая строка

Bit String Наб

ор смежных бит длиной до 4 Гбит

Байт

Byte 8 бит Др,

О

Строки байт, слов и двойных слов

Bit String, Byte Дли

String, Word String, Double Word String

ной до 4 Гбайт

Числа без знака

Unsigned Byte/ Без

Word/Double Word/ (8/1 QuadWord

знака — байт/слово/двойное/учетверенное слово 6/32/64 бит)

Целые числа со знаком

Integer Byte/ Co:

Word/Double Word/ Еди QuadWord етсг

СЯ E

знаком — байт/слово/двойное/учетверенное слово, ничное значение самого старшего бита (знак) явля-1 признаком отрицательного числа, которое хранит-дополнительном коде

2. Двоично-десятичные числа (BCD — Binary Coded Decimal)

8-разрядные

упакованные

Packed BCD Сод

ержат два десятичных разряда в одном байте

8-разрядные

неупакованные

Unpacked BCD Сод

бит

при

ержат один десятичный разряд в байте (значения

7 : 4 при сложении и вычитании несущественно,

умножении и делении они должны быть нулевыми)

4 3 0

Английский эквивалент (или расшифровка)

Вид данного

Пояснения

Двоично-десятичные 80-битовые упакованные числа

18 десятичных разрядов и знак

Форматы данных, обрабатываемых блоками ПЗ и векторными (ММХ/ХММ)

1. Действительные числа в формате с ПЗ

Формат

IEEE-754,

одинарная

точность

Бит знака

Порядок (8 бит)

Мантисса (24 бита)

II

01

1

1

1

1

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

  • 31 30
  • 2322

Номера битов

Single Precision 32 бит —24 бит мантисса, 8 бит порядок

Формат

IEEE-754,

двойная

точность

Double Precision 64 бит — 52 бит мантисса, 11 бит порядок

Бит знака

І Порядок (11 бит)

-и-

Мантисса (52 бита)

  • 63 62
  • 52 51

Номера битов

Повышенная

точность

Extended Precision

  • 80 бит — 64 бит мантисса, 15 бит порядок
  • 2. Упакованные целые числа, со знаком и без

(64 разрядаММХ)

Восемь упакованных байт

Packed byte (В)

63

О

Байт 7 Байт 6 Байт 5 Байт 4

Вайт 3 Байт 2 Байт 1 Байт 0

Четыре упакованных слова

Packed word (W)

63

О

Слово 3 Слово 2

Слово 1 Слово 0

Два упакованных двойных

Packed

63

О

doubleword (D)

Двойное слово 1

Двойное слово 0

слова

Учетверенное

Quadword (Q)

63

О

слово

3. Упакованные вещественные числа (64 разряда

3DNow!)

2 х 32 бита.

Два упакованных двойных слова

63

О

Формат

Двойное слово 1

Двойное СЛОВО 0

IEEE-754

с ПЗ одинарной точности

4. Упакованные вещественные и целые числа (128 разрядов — SSE, AMD64)

Формат SSE

Четыре числа одинарной точности с ПЗ

Окончание табл. 1.9

Вид данного

Английский эквивалент (или расшифровка)

Пояснения

Формат SSE2

Два двойной

127 0

точности с ПЗ

« «

Целое на 128 бит

127 0

« «

Два целых

127 0

(2 х 64 бита)

« «

Четыре целых

127 0

(4 х 32 бита)

« «

Восемь коротких с (8 х 16 бит)

127 0

Формат SSE2

16 байт (16x8 бит)

127 0

Указатели*

Длинный указатель (48 бит)

16-битовый селектор (или сегмент) и 32-битовое смещение

Короткий указатель

32-битовое смещение

Простой указатель

32 бит, единственный тип указателя для 8086 и 80286. 16-битовый селектор (или сегмент) и 16-битовое смещение

* Указатель (пойнтер, pointer) — данное, содержащее адрес некоторой переменной в оперативной памяти. В языках программирования обычно присутствует функция РТР (X), определяющая адрес переменной х.

Разновидности «машинной арифметики»

Обычная двоичная арифметика. Двоичные операции выполняются над двоичными числами в арифметико-логических устройствах (АЛУ) компьютеров. Базовой операцией является сложение, которое непосредственно выполняется электронной схемой сумматора (см. рис. 2.11—2.13). Вычитание также выполняется как сложение, однако вычитаемое (отрицательное число) представлено в дополнительном или другом коде. Умножение реализуется как серия сложений со сдвигами (перемещение цифр на более старшую или младшую позицию), деление — вы-питания со сдвигами. В каждый момент в операции участвуют только два числа. Вот четыре возможные операции сложения сочетаний двоичных цифр:

Первая цифра 0 0 1 1

Вторая цифра 0 10 1

Результат 01 1 10

Заметим, что перенос единицы в следующую позицию (в старшую сторону) происходит только в случае сложения двух единиц.

Рассмотрим примеры двоичного суммирования совместно с их десятичными эквивалентами:

1 = 2

2 + 2=4

6 + 3=9

10 + 5 = 15

37 + 22 =

1

10

ПО

1010

100101

1

10

+ 11

+ 101

+10110

10

100

1001

1111

111011

Вот, далее, четыре возможные операции вычитания двоичных цифр:

Первая цифра 0 1(0) 1 1

Вторая цифра 0 10 1

Результат 01 10

Отметим, что заем единицы в старшем разряде требуется только тогда, когда единица вычитается из нуля.

Рассмотрим примеры двоичного вычитания совместно с их десятичными эквивалентами:

-1=1

5-3=2

10-2 =8

15-9=6

43-18=:

10

101

1010

1111

101011

-1

-10

-10

1001

-10010

10

100

1001

1111

11001

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

Как уже известно, дополнительный код используется для вычитания чисел в компьютерах и позволяет эту операцию свести к сложению чисел. Правила выполнения вычитания с дополнительным числом следующие. Чтобы число А вычесть из числа В, достаточно сложить В с дополнительным числом к А и отбросить перенос в соседний старший разряд. Например, чтобы вычесть 623 из 842, достаточно сложить 842 с 377 и, отбросив перенос, получим 219 (842 - 623 = 219).

Таким образом, важнейшее преимущество двоичной арифметики заключается в том, что она позволяет все арифметические действия свести к одному — сложению, а это значительно упрощает устройство процессора ЭВМ.

Двоично-десятичная арифметика. В этом случае для записи одного десятичного разряда используется четыре двоичных бита (тетрада). Иногда встречается название, пришедшее из англоязычной литературы — нибл. С помощью четырех битов можно закодировать шестнадцать цифр. Лишние комбинации в двоично-десятичном коде являются запрещенными. Соответствие двоично-десятичного кода и десятичных цифр приведено в табл. 1.8.

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

Двоично-десятичная коррекция заключается в дополнительном суммировании числа ОНО - шесть (число запрещенных комбинаций) с тетрадой, в которой произошло переполнение или перенос в старшую тетраду. Вот два примера:

1) 18 + 13 = 31

2)19 + 19 = 38

Сложение тетрад 0001 1000

0001 0011

Коррекция

  • 0010 1011
  • 0000 0110

Сложение тетрад 0001 1001

0001 1001

Коррекция

  • 0011 0010
  • 0000 0110

0010 1011

0011 0001

0011 0010

0011 1000

Циклическая арифметика (WrapAround). Если при сложении двух чисел (например, в 8-разрядном сумматоре) возникает единица переполнения:

11111110,

+000000112

  • 100000001,
  • 0000000012

которая не помещается в разрядной сетке (в данном примере — 8 бит), то происходит «сбрасывание» этого промежуточного результата до остатка от его деления (в данном примере до 1) на максимальное число в разрядной сетке (здесь — 2х = 256). Просьба к читателю перевести оба операнда в десятичную форму и удостовериться в истинности данного утверждения.

Такой эффект возникает в «циклической» (или «модульной») арифметике — сложение, умножение и пр. по модулю N (mod N), когда результат образуется путем получения остатка от деления «истинного» результата операции на основание модуля — число N (на рис 1.5, a N= «Максимум» — «Минимум»).

t

Результат

а

Диаграммы к определению арифметики циклической (а)

Рис. 1.5. Диаграммы к определению арифметики циклической (а)

и с насыщением (б)

Saturation arithmetic — SArith («арифметика насыщения») — версия арифметики, в которой результат операции ограничен интервалом между максимальным и минимальным значениями. Если результат больше максимума, он устанавливается («clamped») в максимум, если меньше минимума — то в минимум. Дальнейшее суммирование с максимумом или вычитание из минимума не меняет результата (рис. 1.5, б).

Например, если интервал допустимых значений находится между -100 и +100, то следующие операции дают такие результаты (см. также табл. 1.10):

  • 60 + 43 = 100; (60 + 43)- 150 = -50; 43 - 150 = -100;
  • 60+ (43 - 150) = -40;
  • 10 х 11 = 100; 99 х 99 = 100; 30 х (5 - 1) = 100;
  • 30 х 5 - 30 х 1 = 70.

Таблица 1.10. Примеры пределов для арифметики с насыщением

Размер данного

Десятичное представление

Шестнадцатеричное

Нижний предел

Верхний предел

Нижний предел

Верхний предел

Байт со знаком

-128

+ 127

80i6

7F16

Байт без знака

0

255

0

FF16

Слово со знаком

-32768

+32767

800016

7FFFi6

Слово без знака

0

65535

0

FFFFie

Векторные операции над упакованными данными («упакованная арифметика» — packed arithmetic). Принцип упакованных данных создает предпосылки для их параллельной обработки (архитектуры MMX, 3DNow!, SSE). Возьмем в качестве примера единицу звуковой информации — 16-разрядный элемент трека CD (см. рис. 1.1). Четыре элемента можно разместить в 64-раз-рядном регистре процессора. При выполнении «упакованной» команды из регистров / и j параллельно выбирается по элементу, над ними одновременно выполняется арифметическая или логическая операция (например, «+»), и результат записывается в регистр к (рис. 1.6, а — MMX-команда paddus [w], упакованное сложение беззнаковых слов с насыщением).

Аз

А2

А

А0

} ’

Регистр.-

г г1м '

вз

В2

В,

Во

' ’

Регистр;

г J

Ф + в3

А-) + В1

А] + Д,

А0 + Д0

а

Аз

а2

ф

Ао

'

Регистр^

г

в,

В2

В

Во

'

Регистру

'

Л2 а3

X

о

1

>

В-, В^

в0 в]

б

Регистр^ Регистр^

Рис. 1.6. Примеры векторных операций: а — команда paddus; б — hsubps

«Горизонтальная» и «вертикальная» и арифметика. В то время как команды обычной векторной арифметики можно было бы отнести к более или менее строго вертикальным (между регистрами) операциям (рис. 1.6, а), в архитектуре ББЕЗ была введена возможность работать горизонтально (внутри регистра). Были добавлены команды сложения/вычитания по отношению к наборам (векторам) значений, расположенных в пределах единственного регистра, которые улучшают эффективность цифровой обработки сигналов и трехмерных преобразований (рис. 1.6, б — ББЕЗ-команда нзивРБ — НогігопІаІ-БиЬітасІ-Раскесі-Б^Іе — горизонтальное вычитание упакованных слов одинарной длины). Например, при обработке звукового сигнала команду НАзивРБ можно использовать для получения относительного кодирования (см. рис. 1.2, б) из абсолютного (см. рис. 1.2, а).

Необходимо заметить, что наряду с рассмотренными здесь арифметическими операциями, в системах команд компьютеров присутствуют также и логические операции (описываются ниже), в частности, операции на рис. 1.6 могли бы быть поразрядными логическими (см. табл. 1.21).

Двоичное кодирование мультимедиа-информации

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

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

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

Цветные изображения могут представляться в различных режимах: 16 цветов, 256 цветов, 65 536 цветов (high color), 16 777 216 цветов (true color) — табл. 1.11. Очевидно, что количество бит на точку (пиксель), например, режима true color равно:

/= log265 536 = 16 бит = 2 байта.

Таблица 1.11. Характеристики различных стандартов представления графики

Разрешение

16 цветов

256 цветов

65 536 цветов

16 777 216 цветов

640 х 480

150 Кбайт

300 Кбайт

600 Кбайт

900 Кбайт

800 х 600

234,4 Кбайт

468,8 Кбайт

937,5 Кбайт

1,4 Мбайт

1024 x 768

384 Кбайт

768 Кбайт

1,5 Мбайт

2,25 Мбайт

1280 x 1024

640 Кбайт

1,25 Мбайт

2,5 Мбайт

3,75 Мбайт

Наиболее распространенной разрешающей способностью экрана является разрешение 800 на 600 точек, т. е. 480 000 точек.

Рассчитаем необходимый для режима true color объем видеопамяти:

V= 2 байта х 480 000 = 960 000 байт = 937,5 Кбайт.

Аналогично рассчитывается объем видеопамяти, необходимый для хранения битовой карты изображений при других видеорежимах.

В видеопамяти памяти компьютера хранится битовый план (bit map), являющийся двоичным кодом изображения, отсюда он считывается процессором (не реже 50 раз в секунду) и отображается на экран.

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

Различные звуковые карты могут обеспечить как 8-, так и 16-битовые выборки. При замене непрерывного звукового сигнала его дискретным представлением в виде ступенек 8-битовые карты позволяют закодировать 256 различных уровней дискретизации звукового сигнала, соответственно 16-битовые — 65 536 уровней.

Частота дискретизации аналогового звукового сигнала (количество выборок в секунду) также может принимать различные значения (5,5, 11, 22 и 44 кГц). Таким образом, качество звука в дискретной форме может быть очень плохим (качество радиотрансляции) при 8 битах и 5,5 кГц и весьма высоким (качество аудиоСО) при 16 битах и 44 кГц.

Можно оценить объем моноаудиофайла с длительностью звучания 1 с при среднем качестве звука (16 бит, 22 кГц). Для этого 16 бит на одну выборку необходимо умножить на 22 000 выборок в секунду, что дает в результате 43 Кбайт.

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

Сжатие данных (data compression) — процесс, обеспечивающий уменьшение объема данных. Сжатие позволяет резко уменьшить объем памяти, необходимой для хранения данных, сократить (до приемлемых размеров) время их передачи. Особенно эффективно сжатие изображений. Сжатие данных может осуществляться как программным, так и аппаратным или комбинированным методами.

Сжатие текстов связано с более компактным расположением байтов, кодирующих символы. Определенные результаты дает статистическое кодирование, в котором наиболее часто встречающиеся символы имеют коды наименьшей длины. Здесь также используется счетчик повторений пробелов. Что же касается звука и изображений, то объем представляющей их информации зависит от выбранного шага квантования и числа разрядов аналого-цифрового преобразования. В принципе, здесь используются те же методы сжатия, что и при обработке текстов. Если сжатие текстов происходит без потери информации, то сжатие звука и изображения почти всегда приводит к ее некоторой потере. Сжатие широко используется при архивировании данных.

Сжатие изображений (image compression) — процесс минимизации данных, составляющих изображение. Минимизация количества информации, предоставляющей изображение или видеофильм прежде всего, осуществляется при выборе шага квантования и разрядности кодов. При этом, естественно, происходит определенная (допустимая) потеря информации. Затем происходит сжатие изображения, представленного дискретным сигналом.

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

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

Допускается потеря той информации, которая в решении поставленной задачи считается несущественной. Например, можно при обработке изображений удалить из аналогового сигнала частоты, которые находятся вне спектра, воспринимаемого глазом человека (до 10 000 цветов, 256 оттенков серого цвета). Нередко допускается игнорирование цвета каждого второго пикселя либо группа пикселей заменяется одним со средним значением цвета. Осуществляется также групповое кодирование. Его сущность заключается в кодировании групп одинаковых пикселей (например, небо без облаков на картине).

Размер файла сжатого дискретного неподвижного изображения зависит от четырех параметров: площади изображения, квадрата разрешения, числа бит, необходимых для представления пикселя и коэффициента сжатия. В видеофильме к этому еще добавляется число образующих его неподвижных изображений. Выбор коэффициентов сжатия — компромисс между пропускной способностью системы (скоростью переноса файлов) и качеством восстанавливаемого изображения. Чем выше коэффициент сжатия, тем ниже это качество. При этом следует иметь в виду, что при очень высокой разрешающей способности и большом коэффициенте сжатия можно получить изображение с низкой разрешающей способностью. Поэтому выбор указанных параметров обосновывается технико-экономическим анализом и алгоритмом сжатия. Что касается качества изображения, то оно зависит от конкретной поставленной задачи. Например, в системах телеконференций основной объем необходимой информации содержится в речи, тогда как качество изображения может играть вторую роль.

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

Существует немало технологий сжатия/восстановления изображений. Наиболее популярная из них предложена Объединенной группой экспертов в области фотографии (JPEG) и позволяет сократить размеры графического файла в 10—20 раз. Благодаря специальным процессорам и алгоритмам удается также сжимать видеосюжеты.

Кодирование видеоинформации. В связи с большим объемом информации, содержащейся в видеопотоке (до 6 Мбайт/с), для записи информации в ЭВМ обычно применяют кодирование со сжатием потока данных на входе с использованием алгоритмов семейства МРЕО/ЗРЕО (табл. 1.12).

Таблица 1.12. Характеристики представления видеоинформации в различных форматах

Формат

Тип данных (размер изображения)

Длительность записи (CD/DVD), мин

1

VCD

288 х 384

63

2

S-VCD

СО

Г-*-

LO

X

о

со

"3-

32

3

DVD

576 х 720

59

4

VHS

"3-

со

со

X

со

со

см

5

S-VHS

540 х 720

6

Internet High Speed

"3-

X

со

03

Стандарт MPEG (Motion Picture Expert Group) включает несколько компонентов: системного потока, описывающего структуру смешанного аудио- и видеопотока, а также MPEG-video и MPEG-audio.

В случае MPEG-video сжатие достигается за счет четырех факторов.

1. Использование составляющих YUV вместо обычных RGB (красный, зеленый, синий).

Вместо элементарных цветов кодируется яркость (luminance, Y) и цветность (chrominance, U & V), причем цветность «прорежена» по вертикали и горизонтали в 2 раза по сравнению с яркостью (децимация). При этом вместо сильно коррелированных сигналов RGB получаются практически некоррелированные YUV, и за счет децимации достигается двукратное сжатие.

2. Дискретно-косинусное преобразование с последующим квантованием.

При этом квадраты пикселей (8 х 8) подвергаются двумерному дискретно-косинусному преобразованию (DCT), которое родственно преобразованию Фурье, различие заключается в наборе базисных функций (в преобразовании Фурье — это синусы и косинусы, в DCT — косинусы). Это преобразование переводит пространственное представление сигнала в частотное. Результат преобразования подвергается квантованию, т. е. огрублению точности, при этом коэффициент квантования для более высоких пространственных частот выбирается более высоким, чем для низких, с учетом особенностей восприятия. При этом высокие пространственные частоты передаются с меньшей точностью, чем низкие частоты. При квантовании многие пространственные частоты не кодируются и не передаются.

3. Устранение временной избыточности с компенсацией движения.

Это означает, что для ликвидации избыточности, заключающейся в большой корреляции между соседними кадрами, передается разность между ними. Кадры видеопотока разбиваются на несколько типов — Intra (/), которые кодируются полностью, Predicted (Р), для которых кодируется различие с предыдущим I-или Р-кадром, и Bidirectional (В), для которых в качестве опорных (reference) используются /- и/или Р-кадры, между которыми он находится. Обычно /-кадры следуют 1 или 2 раза в секунду, и между двумя опорными кадрами лежат 2—4 В-кадра. Типичная последовательность кадров (GOP — Group of Pictures) имеет вид: IBBPBBPBBPBBIBBP. В общем случае вид последовательности выбирается кодером и может зависеть или нет от содержания кадров. Поскольку изображение на соседних кадрах обычно сдвинуто, применяется компенсация движения, т. е. кодируется отклонение («разность») от некоторого сдвинутого опорного изображения. Кодирование выполняется макроблоками (16 х 16 — яркость, 8 х 8 — цветность), для каждого макроблока находится свой вектор движения.

4. Квазиоптимальное кодирование.

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

MPEG-1 проектировался из расчета на поток 120 Кбайт/с размером 288 х 354 при 25 кадрах в секунду, хотя он не ограничен этим и допускает существенно больший поток при произвольном размере кадра.

MPEG-2 проектировался с учетом опыта использования MPEG-1 и ориентируется на вещание, так как содержит средства для маскирования ошибок.

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

Типы и структуры данных

Типы данных (табл. 1.13). Классификация информационных единиц, обрабатываемых на ЭВМ, включает следующие аспекты:

  • • типы данных, или совокупность соглашений о программно-аппаратурной форме представления и обработки, а также ввода, контроля и вывода элементарных данных;
  • • структуры данных — способы композиции простых данных в агрегаты и операции над ними;
  • • форматы файлов — представление информации на уровне взаимодействия операционной системы с прикладными программами.

Таблица 1.13. Типы и структуры данных в некоторых системах программирования и управления данными

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

информации

Система — язык программирования, СУБД, ИПС

Algol

Cobol

PL/1

FoxBase/

Clipper

Adabas/

Natural

Oracle/ SQL

STAIRS,

IRBIS,

ISIS

Тип данных

Целое короткое (2 байта)

Smallint

Целое нормальное (4 байта)

Integer

Computa-

tonal

Int

N (x)

N (x)

Int

Целое длинное (8 байт)

Double

Действительное нормальное (4 байта)

Real

Computa

tional

Float

N(x.y)

N(x.y)

Float

Real

Действительное двойное (8 байт)

Float

Double

Двоичное

Binary

B (x)

Окончание табл. 1.13

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

информации

Система — язык программирования, СУБД, ИПС

Algol

Cobol

РІЛ

FoxBase/

Clipper

Adabas/

Natural

Oracle/ SQL

STAIRS,

IRBIS,

ISIS

Типы данных

Десятичное упакованное (2 цифры на байт)

РІС(9)

Decimal

P(x)

Десятичное распакованное (1 цифра на байт)

РІС(X)

N (x)

U(x)

Логическое

Boolean

4-

Logical

Символьное

РІС(А)

Char

C(x)

A (x)

Char

4-

Длинный текстовый или бинарный объект (BLOB)

Memo

VarGrafic

VarChar

Дата

Date

Date

Время

Time

Структуры

Массивы

Array

Dim

Dimen

tion

VAR(n)

Записи

(структуры)

4-

+

+

4-

+

Множественные (векторные) ПОЛЯ записи

MU

4-

Групповые ПОЛЯ записи

4-

4-

GR

4-

Повторяющиеся группы в записи

PE

Текстовые ПОЛЯ (параграфы, предложения, слова)

4-

Ранние языки программирования (ЯП), а точнее, системы программирования (СП) — РоїТгап, А1§о1, будучи ориентированы исключительно на вычисления, не содержали развитых систем типов и структур данных.

В ЯП А1§о1 символьные величины и переменные вообще не предусматривались, в некоторых реализациях строки (символы в апострофах) могли встречаться только в операторах печати данных.

Типы числовых данных ЯП Algol: integer (целое число), Real (действительное) — различаются диапазонами изменения, внутренними представлениями и применяемыми командами процессора ЭВМ (соответственно арифметика с фиксированной и плавающей точкой). Нечисловые данные представлены типом boolean — логические, имеющие диапазон значений {true, false}.

Позже появившиеся ЯП (СП) Cobol, PL/1, Pascal вводят новые типы данных:

  • • символьные (цифры, буквы, знаки препинания и пр.);
  • • числовые символьные для вывода;
  • • числовые двоичные для вычислений;
  • • числовые десятичные (цифры 0—9) для вывода и вычислений.

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

Уместно привести пример представления числовой информации в различных перечисленных формах. Пусть задано число 13510 = 2078 = 8716 = 1000001112, тогда:

  • • внутренняя стандартная форма представления (тип Binary для обработки в двоичной арифметике) сохраняется (1000001112). Объем — 1 байт, или 8 двоичных разрядов;
  • • внутренняя форма двоично-десятичного представления (тип Decimal, каждый разряд десятичного числа представляется двоично-десятичной, в 4 бита, комбинацией). Представление 135 есть 001 011 1012. Объем — 2,5 байта, 12 двоичных разрядов;
  • • символьное представление (тип Alphabetic, для вывода) — каждый разряд представляется байтом в соответствии с кодом ASCII (табл, приложения 2). Представление 135 есть - 00110001 00110011 001101012. Объем - 3 байта.

Некоторые системы программирования (Fortran IV, например) поддерживают операции над комплексными числами вида Z=A + Bi (где А, В — действительные коэффициенты, / — мнимая единица). Очевидно, для размещения таких чисел необходим как минимум двойной расход оперативной памяти (по одному слову для размещения действительной и мнимой частей при обычной точности и по два слова при двойной точности). Кроме того, очевидно, что процессоры обычных универсальных ЭВМ вряд ли поддерживают операции над такими числами, в связи с этим операции над ними требуют написания соответствующих подпрограмм или эмуляции комплексной арифметики.

Появление систем управления базами данных и систем программирования для разработки НС приводит к появлению ряда других типов данных:

  • дата и время;
  • бинарные (Binary Large Object — BLOB) и текстовые объекты без внутренней структуры (интерпретация возлагается на прикладные программы).

Понятие типа данных ассоциируется также с допустимыми значениями переменной и операциями над ними, например, данные типа время (чч:ММ:СС) или дата (гг/мм/дд) предполагают определенные диапазоны значений каждого из разрядов, а также машинные или эмулируемые операции (сложение/вычитание дат и/или моментов времени). Основной причиной «проблемы 2000 г.» («Problem Y2K») являлась не столько двухразрядная запись года в базах данных, сколько встроенные в огромное количество программ (часто недокументированных) операции над данными типа Date - ГГ/ММ/ДД.

Структуры данных. В языке Algol были определены два типа структур: элементарные данные и массивы (векторы, матрицы, тензоры, состоящие из арифметических или логических переменных). Основным нововведением, появившимся первоначально в Cobol, (затем PL/1, Pascal и пр.) являются агрегаты данных (структуры, записи), представляющие собой именованные комплексы переменных разного типа, описывающих некоторый объект или образующих некоторый достаточно сложный документ.

Рассмотренные выше экзотические типы данных (комплексные числа), очевидно, занимают промежуточное положение между элементарными переменными и массивами (структурами).

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

Появление СУБД и АН ПС приводит к появлению новых разновидностей структур:

  • • множественные поля данных;
  • • периодические групповые поля;
  • • текстовые объекты (документы), имеющие иерархическую структуру (документ, сегмент, предложение, слово).
 
<<   СОДЕРЖАНИЕ   >>