Глава 1. Информация и информационные процессы

Глава 1. Информация и информационные процессы

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

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

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

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

q полезность;

q понятность;

q актуальность;

q полнота;

q достоверность.

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

В настоящее время принято выделять социальную информацию — многоуровневое знание, которое характеризует:

q общественные процессы в целом — экономические, политические, социальные, демографические, культурно-духовные;

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

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

Количество информации

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

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

(1.1)

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

Если источник информации формирует одно из четырех сообщений (K = 4), то количество информации в соответствии с формулой (1.1) равно двум битам. И далее все просто — 8 сообщений приводят к трем битам, 16 сообщений к четырем и т. д.

Количество информации определяет минимальное количество двоичных разрядов (каждый двоичный разряд принимает значение 0 либо 1), которыми можно закодировать K сообщений. Например, если источник информации может выдавать одно из 32 сообщений, то в соответствии с формулой (1.1) количество информации равно 5-ти битам. Для того чтобы закодировать каждое сообщение набором из нулей и единиц, потребуется 5 разрядов. В этом случае каждому сообщению будет сопоставлен уникальный (для каждого сообщения свой особенный) набор из 5 двоичных разрядов (5 бит).

Понятно, что один бит — слишком малая величина информации, поэтому чаще используют другую — байт, которая представляет собой группу (совокупность) из восьми битов. Это уже существенная порция информации, и байтом можно без проблем закодировать буквы алфавита (практически во всех языках народов мира алфавит не такой уж большой), цифры и необходимые дополнительные символы. Если в формулу (1.1) подставить I = 8, то получим, что K = 256. Такого количества различных символов вполне достаточно для передачи букв текста.

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

q один килобайт (1 Кбайт) — составляет 2¹⁰ байтов или 1024 байта;

q один мегабайт (1 Мбайт) — составляет 2²⁰ байтов или 1024 килобайта;

q один гигабайт (1 Гбайт) — составляет 2³⁰ байтов или 1024 мегабайта.

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

Пример

Вопрос: сколько различных последовательностей длиной 7 символов можно составить из цифр 0 и 1? Решение несложное, и здесь мы должны воспользоваться формулой (1.1). Учитывая исходные данные, запишем а далее в соответствии с определением логарифма по основанию два получим K = 128.

Пример

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

Пример

Будем считать, что каждый символ текстового сообщения кодируется одним байтом. Вопрос заключается в определении количества информации в сообщении " Не ошибается тот, кто ничего не делает! ". Для начала необходимо подсчитать число символов в данной фразе, что мы и сделаем — получается 39. Каждый символ несет 8 бит (один байт) информации. После этого следует использовать соотношение (1.2), в котором в качестве N выступает 39, а по условию задания равно 8 бит. В результате перемножения 39 на 8 получим 312 бит. Это и является ответом на вопрос о емкости рассматриваемого информационного сообщения.

Пример

Сколько информации несет сообщение о том, что тетраэдр при подбрасывании падает на синюю грань (для определенности отметим, что у тетраэдра четыре грани, а цвета выберем такие — синий, зеленый, красный и желтый)? Поскольку вероятности выпадения граней одинаковы, то вероятность (P) падения тетраэдра на синюю грань равна ¼. Подставив это значение в соотношение (1.3), получим 2 бита.

Пример

Допустим, в корзине 16 шаров, которые пронумерованы числами (1, 2, ..., 16). Человек должен случайным образом извлечь один шар. Вероятности извлечения шаров одинаковы. Сколько информации несет сообщение о том, что был извлечен шар под номером 9? Здесь, учитывая, что P = 1/16 для каждого шара, то в соответствие с формулой (1.3) получим 4 бита.

Соотношение (1.3) определяет количество информации, доставляемое получателю конкретным сообщением. Однако существует еще одно соотношение, определяющее среднее количество информации, доставляемое получателю от источника информации. В 1948 г. американский математик К. Шеннон предложил формулу для вычисления среднего количества информации от источника для сообщений с различными вероятностями:

(1.4)

где — вероятность i-го сообщения, а суммирование производится по всем сообщениям (общее количество которых — K). Для используется термин " энтропия источника сообщений".

Пример

Допустим, что мы подбрасываем монету с дефектом, а именно, орлом она выпадает чаще, чем решкой. Для определенности положим, что вероятность выпадения решки равна 0.3, а вероятность выпадения орла — 0.7. Вопрос заключается в том, какое количество информации в среднем мы получаем после выполнения очередного броска?

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

Процесс передачи информации

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

Сообщение, подлежащее передаче, может представлять собой последовательность букв, образующих слова. Оно может быть также речевым сообщением или музыкальным произведением. Наконец, сообщением может быть изображение (фотография). В самом словосочетании " источник сообщений" подчеркивается то обстоятельство, что система связи позволяет передать сообщение, выбранное из множества возможных элементарных сообщений для данной системы. Это множество возможных элементарных сообщений называется алфавитом источника сообщений. А количество возможных элементарных сообщений представляет собой мощность источника сообщений. Так, если источник сообщений формирует сочетания букв русского языка, то совокупность букв является алфавитом источника, а мощность такого источника информации равна 32 (если не делать различий между е и ё, то в русском языке 32 буквы).

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

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

Рис. 1.1. Процесс передачи битов информации во времени

Рис. 1.2. Искажения в процессе передачи информации

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

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

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

Пример

Скорость передачи через модемное соединение равна 56 Кбит/c. Передача текстового файла через это соединение заняла 2 секунды. Требуется определить, сколько символов содержал переданный текст, если на каждый символ отводится 8 бит.

Известно, что 1 Кбит составляет 1024 бита. Таким образом, за 2 секунды передается: 56 × 1024 × 2, что дает 114 688 бит. По условию для каждого символа отводится 1 байт или 8 бит. В результате требуется разделить 114 688 бит на 8 бит, что приводит к ответу 14 336 символов.

Кроме преобразования битов в сигналы модемы выполняют еще несколько полезных функций. Одна из них связана с уплотнением информации. Поясним это на примере. Допустим, мы передаем сообщение, составленное из букв некого алфавита. При этом одни буквы встречаются в сообщении значительно чаще, чем другие. Для конкретности пусть в алфавите источника информации будут только три буквы — A, B и С. При этом статистика говорит о том, что частота появления буквы А в тексте составляет 50% (для любой буквы конкретного алфавита такую статистику легко подсчитать — необходимо взять толстую книгу и проанализировать суммарное количество различных букв). Для букв B и С будем считать, что частоты появления составляют по 25%. Очевидно, что если для передачи букву А закодировать одним битом (скажем единицей), а другие буквы двумя битами (В — 00, С — 01), то количество битов в большом сообщении в среднем будет меньше по сравнению с ситуацией, когда на каждую букву приходится одинаковое количество битов.

Так, в рассматриваемом случае при передаче сообщения из 1000 букв потребуется в среднем: 500 букв умножить на 1 бит плюс 500 букв умножить на 2 бита. В результате это составит 1500 бит (в среднем! ). При выделении же на каждую букву целых двух бит понадобится 2000 бит. Понятно, что при больших передаваемых объемах информации подобный выигрыш существенен. И модемы данную процедуру, которая называется эффективным кодированием, выполняют.

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

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

Глава 2. Системы счисления

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

Численная информация в компьютере имеет две важные особенности:

q числа записываются в двоичной системе счисления (а не в привычной десятичной);

q для записи и обработки чисел отводится конечное количество разрядов (в " некомпьютерной" арифметике такое ограничение отсутствует).

Виды систем счисления

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

q унарная;

q непозиционные;

q позиционные.

Унарной называется система счисления, в которой для записи чисел используется только один знак — I (" палочка" ). Следующее число получается из предыдущего добавлением новой I, а их количество (сумма) равно самому числу. Именно такая система применяется для начального обучения детей счету (можно вспомнить " счетные палочки" ).

Из непозиционных наиболее распространенной можно считать римскую систему счисления. В ней некоторые базовые числа обозначены прописными латинскими буквами: 1 — I, 5 — V, 10 — X, 50 — L, 100 — C, 500 — D, 1000 — M. Все другие числа строятся из комбинаций базовых в соответствии со следующими правилами:

q если цифра меньшего значения стоит справа от большей цифры, то их значения суммируются; если слева — то меньшее значение вычитается из большего;

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

q цифры V, L и D могут использоваться в записи числа не более одного раза.

Например, запись XIX соответствует десятичному числу 19, а MDXLIX — десятичному числу 1549. Запись чисел в такой системе громоздка и неудобна, но еще более неудобным оказывается выполнение в ней даже самых простых арифметических операций. Отсутствие нуля и знаков для чисел больших M не позволяют римскими цифрами записать любое число. По указанным причинам в настоящее время римская система используется лишь для нумерации. Римская система является аддитивной, т. к. значение числа образуется только при помощи сложения или вычитания значений цифр его образующих.

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

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

Как вы знаете, числа бывают дробные и целые. И для последовательности объяснения мы разберем сначала только целые числа, а затем приведем необходимые сведения и по дробным числам. Целое число Z можно определить так:

Z = aM – 1 × bM – 1 + … + a1 × b1 + a0 × b0,

(2.1)

где b_i — символы, обозначающие цифры, при этом 0 £ b_i £ a – 1. Здесь предполагается для определенности Z < a^M, а M > 0. Индекс i представляет собой номер позиции цифры или, более правильно, номер разряда. Так, если исходное число большое, то разрядов в числе много (соответственно, в маленьких числах разрядов мало). Из коэффициентов b_i при степенях основания строится сокращенная запись числа:

Z = bM – 1...b1b0.

(2.2)

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

q Z₁₀ — число Z в десятичной системе счисления;

q Z₈ — число Z в восьмеричной системе счисления.

В дальнейшем в этой главе мы так и будем поступать — там, где есть неопределенность, нижним индексом будем подчеркивать основание системы счисления.

Минимально значение a равно двум, что соответствует двоичной системе счисления. Цифрами в этом случае являются 0 и 1, а представление числа рассматривается по степеням двойки. Интерес именно к этой системе счисления связан с тем, что (об этом мы поговорим дальше) любая информация в компьютерах представляется с помощью двух состояний — 0 и 1, которые легко реализуются технически. Например, вариант числа в двоичной системе может выглядеть так:

Z = 11012 = 1 × 23 + 1 × 22 + 0 × 21 + 1 × 20.

(2.3)

Наряду с двоичной системой, в компьютерах используются восьмеричная (с основанием 8) и шестнадцатеричная (с основанием 16). В нашей обычной жизни наиболее распространенной и привычной является десятичная система счисления (a = 10), в которой для записи чисел используется 10 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. Приведем пример числа в десятичной системе счисления:

Z = 27210 = 2 × 102 + 7 × 101 + 2 × 100.

(2.4)

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

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

Дробные числа

Мы сознательно в начале главы ограничили наши действия только целыми числа. Теперь приведем соотношение и методику работы с дробными числами. Для начала скорректируем соотношение (2.1) следующим образом:

Z = aM – 1 × bM – 1 + … + a1 × b1 + a0 × b0 + a–1 × b–1 + a–2 × b–2 + …

(2.7)

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

Z₁₀ = 1 × 2³ + 1 × 2² + 0 × 2¹ + 0 × 2⁰ + 1 × 2^–1 + 0 × 2^–2 + 1 × 2^–3.

После выполнения технических действий результат выглядит так: Z₁₀ = 12.625.

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

q перевод целой части числа из десятичной системы счисления в двоичную (эту процедуру мы рассматривали выше);

q перевод дробной части из десятичной системы счисления в двоичную.

Второй алгоритм нам еще не встречался, и сейчас мы его разберем. Пусть исходное число выглядит следующим образом:

Z₁₀ = w × y,

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

1. Умножим y на 2, что в результате дает целую компоненту и дробную часть; при этом целая часть представляет цифру b_–1 при весе a^–1 в соотношении (2.7).

2. Дробную часть, полученную от предыдущего действия, следует умножить на 2; целая часть результата умножения представляет цифру b_–2 при весе a^–2.

3. Дробную часть, полученную от предыдущего действия, следует умножить на 2; после этого целая часть представляет цифру b_–3 при весе a^–3.

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

Проиллюстрируем сказанное на примере. Пусть задача заключается в переводе числа 11.7 из десятичной системы счисления в двоичную. Первый этап связан с переводом целой части в двоичную систему счисления (рис. 2.2). В результате знакомый алгоритм нам дает число 1011₂. Второй этап связан с переводом дробной части (0.7) также в двоичную систему счисления. И здесь используем описанный в этом разделе алгоритм для перевода дробной части числа:

1. 0.7 умножаем на 2, что дает 1.4; в итоге целая часть результата представляет вес b_–1 = 1.

2. Дробная часть от предыдущей операции умножается на 2, что приводит к результату 0.8, и после этого целая часть результата составляет b_–2 = 0.

3. Дробная часть от предыдущей операции умножается на 2, что приводит к результату 1.6; поэтому 1 представляет цифру b_–3.

4. Если точность в три двоичных знака после запятой достаточна, то процесс перевода можно завершить.

Рис. 2.2. Перевод целой части числа в двоичную систему счисления

Таким образом, приближенный перевод 11.7 из десятичной системы в двоичную дает: 1011.101₂. Если это число перевести обратно в десятичную систему, то получим 11.625. Для достижения большей точности при переводе из десятичной системы счисления в двоичную следует продолжить алгоритм преобразования дробной части. Таким образом, даже если исходное дробное число не получится абсолютно точно перевести в двоичную систему счисления, то за счет большого количества разрядов (после точки) можно получить очень близкое число к исходному.

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

Действия над числами

Важной особенностью представления чисел в вычислительной технике является то, что, в отличие от записи числа на бумаге, компьютерные ячейки имеют ограниченный размер и, следовательно, вынуждают нас использовать при записи чисел и действиях с ними конечное количество разрядов. Рассмотрим двоичную систему счисления. Например, при восьмиразрядной сетке (восемь двоичных разрядов для представления информации) число 7₁₀ записывается следующим образом — 0000 0111₂ .

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

q 0 + 0 = 0;

q 1 + 0 = 1;

q 0 + 1 = 1;

q 1 + 1 = 0 и единица переноса добавляется к следующему разряду (принимает участие при сложении в следующем разряде).

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

Рис. 2.3. Сложение на восьмиразрядной сетке

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

Теперь рассмотрим вычитание двоичных чисел. Аналогично сложению вычитание двух чисел в двоичной системе счисления выполняется поразрядно, при этом правила таковы:

q 0 – 0 = 0;

q 1 – 0 = 1;

q 1 – 1 = 0;

q 0 – 1 = 1 — связано с тем, что единица берется из следующего (старшего) разряда (из него происходит заем бита).

Таким образом, при вычитании, если это требуется (когда нужно вычесть единицу из нуля в очередном разряде) мы должны забрать единицу заема из старшего разряда. Фактически в этом случае из старшего разряда единица вычитается. Если же единицы в старшем разряде не оказывается, то мы должны забрать ее из следующего старшего разряда и т. д. Подобное действие называется " произвести заем из старшего разряда". Проиллюстрируем сказанное на примере (рис. 2.4).

Рис. 2.4. Вычитание на восьмиразрядной сетке

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

Описанные здесь действия стандартные и выполняются вычислительной системой на аппаратном уровне.

Логические операции

Простейшей операцией булевой алгебры является операция " отрицание" , соответствующая используемой в обычной речи частице " не". Для обозначения отрицания используется знак Ø. Как уже говорилось, для обозначения высказываний мы будем использовать латинские буквы. Например, обозначим высказывание " идет дождь" буквой " p". Тогда запись Ø p представляет — " неверно, что идет дождь". Итак, если p — истинно (равно 1), то Ø p — ложно (равняется 0). Действие операции " отрицание" можно представить в виде таблицы истинности (табл. 3.1).

Таблица. 3.1. Таблица истинности для операции отрицания

p	Ø p

 

Следующая операция — дизъюнкция. Это логическое сложение соответствует слову " или" в обычной речи. Дизъюнкция обозначается Ú, а ее содержание определяется табл. 3.2. Здесь перечисляются различные возможные значения двух переменных p и q, а в третьем столбце записывается результат дизъюнкции.

Таблица. 3.2. Таблица истинности для операции дизъюнкция

p	q	p Ú q

 

123456Следующая ⇒

Поделиться: