Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
126
Оглавление
|
[1] Предисловие [2] Лекция 1. Информация. Начальные понятия и определения [2.0.0.1] Изменение характеристики носителя, которая используется для представления информации, называется сигналом, а значение этой характеристики, отнесенное к некоторой шкале измерений, называется параметром сигнала. [3] Лекция 2. Необходимые сведения из теории вероятностей [4] Лекция 3. Понятие энтропии [5] Лекция 4. Энтропия и информация [6] Лекция 5. Информация и алфавит [7] Лекция 6. Постановка задачи кодирования. Первая теорема Шеннона. [8] Лекция 7. Способы построения двоичных кодов. Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды. [9] Лекция 8. Способы построения двоичных кодов. Другие варианты [10] Лекция 9. Системы счисления. Представление чисел в различных системах счисления. Часть 1 [11] Лекция 10. Системы счисления. Представление чисел в различных системах счисления. Часть 2. [12] Лекция 11. Кодирование чисел в компьютере и действия над ними [13] Лекция 12. Передача информации в линии связи [14] Лекция 13. Обеспечение надежности передачи информации. [15] Лекция 14. Способы передачи информации в компьютерных линиях связи [16] Лекция 15. Классификация данных. Представление данных в памяти компьютера [17] Лекция 16. Классификация структур данных [18] Лекция 17. Организация структур данных в оперативной памяти и на внешних носителях [19] Контрольные вопросы [20] Список литературы [21] Линия связи [22] Источник информации [23] Получатель информации [24] Кодирующее устройство [25] Декодирующее устройство [26] Канал связи |
Во второй половине XX века началась и по настоящее время продолжается стремительная информатизация общества. Информатизация – это процесс создания, развития и всеобщего применения информационных средств и технологий, обеспечивающих достижение и поддержание уровня информированности всех членов общества, необходимого для улучшения качества труда и жизни в обществе. Научным фундаментом процесса информатизации является научная дисциплина – теоретическая информатика.
Целями данного учебного пособия являются:
Среди учебной литературы имеется множество книг по курсу информатики. Однако, круг вопросов, рассматриваемых в имеющихся учебных пособиях, зачастую не вполне соответствует учебной программе по дисциплине «Теория информации», утвержденной вузом для конкретного направления подготовки. Отличие данного пособия от имеющихся состоит, прежде всего, в ориентации на конкретную программу обучения студентов направления подготовки 230700.62 «Прикладная информатика». Данное учебное пособие представляет собой конспект лекций, читаемых студентам, обучающимся по указанному направлению подготовки.
Данный курс может быть использован как лекторами, так и студентами при самостоятельной работе.
1. Информация и данные
Термин «информация» происходит от латинского informatio, что означает разъяснение, осведомление, изложение. Информация есть отражение реального мира с помощью сведений (сообщений).
Сообщение – это форма представления информации в виде речи, текста, изображения, цифровых данных, графиков, таблиц и так далее
В широком смысле информация – это общенаучное понятие, включающее в себя обмен сведениями между людьми, обмен сигналами между живой и неживой природой, людьми и устройствами.
Информация – это сведения об объектах и явлениях окружающей среды, их параметрах, свойствах и состоянии, которые уменьшают имеющуюся о них степень неопределенности, неполноты знаний.
Наряду с понятием информации в информатике часто употребляется понятие «данные». Между «информацией» и «данными» есть отличие.
Данные могут рассматриваться как признаки или записанные наблюдения, которые не используются, а только хранятся. В том случае, когда эти данные используются для уменьшения неопределенности о чем-либо, данные превращаются в информацию. Таким образом, информацией являются используемые данные.
Пример. Напишите на листе десять номеров телефонов в виде последовательности десяти чисел и покажите их Вашему другу. Он воспримет эти цифры как данные, так как они не предоставляют ему никаких сведений. Затем после каждого номера укажите имя и фамилию. Для Вашего друга непонятные сначала цифры обретут определенность, и превратятся из данных в информацию, которую можно использовать.
При работе с информацией всегда имеется ее источник и потребитель (получатель). Пути и процессы, обеспечивающие передачу сообщений от источника информации к потребителю, называются информационными коммуникациями.
2. Адекватность и формы адекватности информации
Для потребителя информации очень важной характеристикой является ее адекватность.
Адекватность информации – это определенный уровень соответствия создаваемого с помощью полученной информации образа реальному объекту, процессу, явлению и так далее
В реальной жизни вряд ли возможна ситуация, когда Вы сможете рассчитывать на полную адекватность информации. Всегда присутствует некоторая степень неопределенности. От степени адекватности информации реальному состоянию объекта или процесса зависит правильность принятия решений человеком.
Пример. Вы успешно закончили школу и хотите продолжить образование по выбранному направлению. Поговорив с друзьями, Вы узнаете, что подобную подготовку можно получить в разных ВУЗах. В результате таких бесед Вы получаете весьма разноречивые сведения, которые не позволяют Вам принять решение в пользу того или иного варианта, то есть полученная информация неадекватна реальному состоянию дел. Для того, чтобы получить более достоверные сведения, Вы покупаете справочник для поступающих в ВУЗы, из которого Вы получаете исчерпывающую информацию. В этом случае можно говорить, что информация, полученная Вами из справочника, адекватно отражает направления обучения в ВУЗах и реально помогает Вам определиться в окончательном выборе.
Существуют три формы адекватности информации:
Синтаксическая адекватность. Она отображает формально-структурные характеристики информации и не затрагивает ее смыслового содержания. На синтаксическом уровне учитываются тип носителя и способ представления информации, скорость передачи и обработки, размеры кодов представления информации, надежность и точность преобразования этих кодов и так далее Информацию, рассматриваемую только с синтаксических позиций, обычно называют данными, так как при этом не имеет значения смысловая сторона. Эта форма адекватности способствует восприятию внешних структурных характеристик, то есть синтаксической стороны информации.
Семантическая (смысловая) адекватность. Эта форма определяет степень соответствия образа объекта самому объекту. Семантический аспект предполагает учет смыслового содержания информации. На этом уровне анализируются те сведения, которые отражает информация. Эта форма служит для формирования понятий и представлений, выявления смысла, содержания информации и ее обобщения.
Прагматическая (потребительская) адекватность. Она отражает отношение информации и ее потребителя, соответствие информации цели управления, которая на ее основе реализуется. Прагматический аспект рассмотрения связан с ценностью, полезностью использования информации при выработке потребителем решения для достижения своей цели. С этой точки зрения анализируются потребительские свойства информации. Эта форма адекватности непосредственно связана с практическим использованием информации.
3. Качество информации
Возможность и эффективность использования информации обусловлены следующими потребительскими показателями качества:
Репрезентативность информации связана с правильностью ее отбора и формирования в целях адекватного отражения свойств объекта. Важнейшее значение здесь имеет обоснованность отбора существенных признаков и связей отображаемого явления. Нарушение репрезентативности информации приводит к существенным ее погрешностям.
Содержательность информации отражает семантическую (смысловую) емкость, равную отношению количества семантической информации в сообщении к объему обрабатываемых данных, то есть .
Достаточность (полнота) информации означает, что она содержит минимальный, но достаточный для принятия правильного решения состав (набор показателей). Понятие полноты информации связано с ее смысловым содержанием (семантикой) и прагматикой. Как неполная, то есть недостаточная для принятия правильного решения, так и избыточная информация снижает эффективность принимаемых пользователем решений.
Доступность информации восприятию пользователя обеспечивается выполнением соответствующих процедур ее получения и преобразования. Например, в информационной системе информация преобразовывается в доступной и удобной для восприятия пользователя форме. Это достигается, в частности, и путем согласования ее семантической формы с тезаурусом пользователя. (Тезаурус – это совокупность сведений, которыми располагает пользователь или система).
Актуальность информации определяется степенью сохранения ценности информации в момент ее использования и зависит от динамики изменения ее характеристик и от интервала времени, прошедшего с момента возникновения данной информации.
Своевременность информации означает ее поступление не позже заранее назначенного момента времени, согласованного с временем решения поставленной задачи.
Точность информации определяется степенью близости получаемой информации к реальному состоянию объекта, процесса, явления и так далее
Достоверность информации определяется ее свойством отражать реально существующие объекты с необходимой точностью.
Устойчивость информации отражает ее способность реагировать на изменения исходных данных без нарушения необходимой точности. Устойчивость информации, как и репрезентативность, обусловлена выбранной методикой ее отбора и формирования.
4. Понятие об информационном процессе
Информация – категория нематериальная. Следовательно, для существования и распространения в материальном мире она должна быть обязательно связана с какой-либо материальной основой. Без материальной основы информация не может проявиться, передаваться и сохраняться, например, восприниматься и запоминаться нами.
Материальный объект или среда, которая служит для представления или передачи информации, называется ее материальным носителем.
Материальным носителем информации может быть бумага, воздух, лазерный диск, электромагнитное поле и пр.
Хранение информации связано с некоторой характеристикой носителя, которая не меняется с течением времени, например, намагниченные области поверхности диска или буква на бумаге, а передача информации связана, наоборот, с характеристикой, которая изменяется с течением времени, например, амплитуда колебаний звуковой волны или силы тока в проводах. Таким образом, хранение информации связано с фиксацией состояния носителя, а распространение связано с процессом, который протекает в носителе. Состояния и процессы могут иметь физическую, химическую, биологическую или иную основу – главное, что они материальные.
Важно, что не с любым процессом можно связать передачу информации. В частности, стационарный процесс, то есть процесс с неизменными в течение времени характеристиками, информацию не переносит. Например, постоянный электрический ток, ровное горение лампы, или равномерный гул свидетельствуют лишь о том, что нечто функционирует. Иное дело, если лампу включать и выключать, то есть изменять ее яркость, – чередованием вспышек и пауз можно представить и передать информацию (например, посредством азбуки Морзе). Таким образом, для передачи информации необходим нестационарный процесс, то есть процесс, характеристики которого могут изменяться. При этом информация связывается не с существованием процесса, а с изменением какой-либо его характеристики.
Изменение характеристики носителя, которая используется для представления информации, называется сигналом, а значение этой характеристики, отнесенное к некоторой шкале измерений, называется параметром сигнала.
В табл. 1 приведены примеры процессов, используемых для передачи информации, и связанных с ними сигналов.
Табл. 1. Передача информации в различных средах
|
Среда |
Процесс (носитель) |
Сигнал |
Параметры синала |
|
Воздух |
Звуковая волна |
Изменение частоты и громкости звуковых колебаний |
Значения частоты и громкости звука |
|
Диэлектрик |
Электромагнитная волна |
Изменение частоты, амплитуды и фазы ЭМ волн |
Значения частоты, амплитуды и фазы ЭМ волн |
|
Провода (телефонные, компьютерные сети) |
Электрический ток |
Изменение частоты и амплитуды электрических колебаний в линии связи |
Значения частоты и амплитуды электрических колебаний в линии связи |
Одиночный сигнал не может содержать много информации. Поэтому для передачи информации используется ряд следующих друг за другом сигналов.
Последовательность сигналов называется сообщением.
Можно сказать, что сообщение является материальной оболочкой для представления информации при передаче. Сообщение служит переносчиком информации, а информация является содержанием сообщения.
Соответствие между сообщением и содержащейся в нем информацией называется правилом интерпретации сообщения.
Это соответствие может быть однозначным и неоднозначным. В первом случае сообщение имеет лишь одно правило интерпретации. Например, по последовательности точек, тире и пауз в азбуке Морзе однозначно восстанавливается переданная буква. Неоднозначность соответствия между сообщением и информацией возможна в двух ситуациях:
Обсудим понятие «информационный процесс». Вообще термин «процесс» применяется в тех случаях, когда некоторое качество, характеризующее систему или объект, меняется с течением времени в результате внешних воздействий или каких-то внутренних причин. У нематериальной информации с течением времени могут изменяться только ее содержание и материальная оболочка, то есть сообщение. В связи с этим существует определение информационного процесса:
Информационный процесс – это изменение с течением времени содержания информации или представляющего это содержание сообщения.
Существуют следующие виды информационных процессов:
Все перечисленные события происходят с сообщением, то есть с материальной оболочкой информации. И с этих позиций возможны лишь два типа процессов:
Несколько слов о хранении информации. Хранение связывается с фиксацией параметров материального носителя, которые далее с течением времени не меняются. Запись информации на носитель (непосредственно в момент фиксации параметров) и ее последующее считывание попадают под определение информационного процесса. Но само хранение не является информационным процессом. Хранение следовало бы назвать информационным состоянием, однако, такое понятие в информатике не используется.
С передачей информации связана пара сопряженных понятий – источник и приемник информации.
Источник информации – это субъект или объект, порождающий информацию и представляющий ее в виде сообщения.
Приемник информации – это субъект или объект, принимающий сообщение и способный правильно его интерпретировать.
Сочетание «субъект или объект» означает, что источники и приемники информации могут быть одушевленными или неодушевленными.
Источник информации должен не только породить информацию, но и иметь возможность инициировать какой-то нестационарный процесс и связать информацию с его параметрами, то есть создать сообщение. Например, если человек что-то придумал, но держит это в своем мозге и не излагает это, он не является источником информации.
В определении приемника информации важно то, что факт приема сообщения еще не означает получение информации. Информация может считаться полученной только в том случае, если приемнику известно правило интерпретации сообщения. Другими словами, понятия «приемник сообщения» и «приемник информации» не тождественны. Например, слыша речь на незнакомом языке, человек оказывается приемником сообщения, но не приемником информации.
Для связи с внешним миром и восприятия информации у человека имеются 5 органов чувств. Однако человек может использовать для передачи и приема информации иные процессы, им не воспринимаемые, например, радиволны. В этом случае человек использует промежуточные устройства, преобразующие сообщения в радиоволны и обратно – радиопередатчики и радиоприемники. Промежуточные устройства–преобразователи получили название технические средства связи, а в совокупности с соединяющей их средой они называются линией связи. К линиям связи относятся телеграф, телефон, радио, телевидение, компьютерные телекоммуникации и так далее При использовании таких средств возникает необходимость преобразования сообщения из одного вида в другой без существенной для получателя потери информации, а также возникает проблема увязки скорости передачи сообщения (то есть интервала следования и величины отдельных сигналов) с возможностями линии связи и приемника.
5. Формы представления информации
Передача информации производится с помощью сигналов, а самим сигналом является изменение некоторой характеристики носителя с течением времени. При этом в зависимости от особенностей изменения этой характеристики (то есть параметра сигнала) с течением времени выделяют два типа сигналов:
Сигнал называется непрерывным (или аналоговым), если его параметр может принимать любое значение в пределах некоторого интервала.
Если – значение параметра сигнала, а – время, то зависимость будет непрерывной функцией, а производная конечна во всех точках внутри области определения функции .
Примерами непрерывных сигналов являются речь, изменение показаний термометра (параметр сигнала – высота столба ртути – имеет непрерывный ряд значений) и так далее
Сигнал называется дискретным, если его параметр может принимать конечное число значений в пределах некоторого интервала.
Дискретные сигналы могут быть описаны дискретным и конечным множеством значений параметров . Производная бесконечна по модулю в точках , в которых происходит смена значения параметра сигнала, и равна нулю во всех других точках .
Примерами устройств, использующих дискретные сигналы, являются книги, электронные часы, цифровые измерительные приборы, табло, бытовая электроника, компьютерная техника и так далее
Поскольку последовательность сигналов есть сообщение, качество прерывности–непрерывности сигналов переносится и на сообщение – существуют понятия «непрерывное сообщение» (построенное из непрерывных сигналов) и «дискретное сообщение» (построенное из дискретных сигналов).
Однако, строго говоря, нет оснований приписывать качество непрерывности или дискретности самой информации, так как информация – категория нематериальная и не может обладать свойством непрерывности или дискретности. Тем не менее, в информатике существуют и используются сочетания «непрерывная информация» и «дискретная информация». Эти понятия нужно понимать только как сокращение полных фраз: «информация, представленная посредством непрерывных сигналов» и «информация, представленная посредством дискретных сигналов».
Принципиальным и важнейшим различием непрерывных и дискретных сигналов является то, что дискретные сигналы можно обозначить, то есть приписать каждому значению из конечного множества возможных значений параметра сигнала знак, который будет отличать данный сигнал от другого.
Знак – это элемент некоторого конечного множества отличных друг от друга сущностей.
Теоретически можно было бы обойтись без требования конечности, однако, это не имело бы никакого практического применения, поскольку за конечное время всегда можно передать только сообщения, построенные из конечного числа знаков.
Природа знака может быть любой – жест, рисунок, буква, сигнал светофора, определенный звук и так далее Природа знака определяется носителем сообщения и формой представления информации в сообщении.
Вся совокупность знаков, используемых для представления дискретной информации, называется набором знаков. Набор есть дискретное множество знаков.
Набор знаков, в котором установлен порядок их следования, называется алфавитом. Алфавит – это упорядоченная совокупность знаков. Порядок следования знаков в алфавите называется лексикографическим. Благодаря этому порядку между знаками устанавливаются отношения «больше–меньше»: для двух знаков и принимается, что , если порядковый номер знака в алфавите меньше, чем порядковый номер знака .
Примером алфавита может служить совокупность арабских цифр 0,1…9 – с помощью этого алфавита можно записать любое число в системах счисления от двоичной до десятичной. Если к этому алфавиту добавить знаки «+» и «–», то сформируется набор знаков, применимый для записи любого целого числа, как положительного, так и отрицательного. Однако, этот набор нельзя будет считать алфавитом, если в нем не заданы порядковые номера следования знаков «+» и «–». Наконец, если добавить знак разделителя разрядов («.» или «,»), то такой набор знаков позволит записать любое вещественное число.
При передаче сообщения параметр сигнала должен меняться, поэтому минимальное количество различных его значений равно двум. Следовательно, алфавит содержит минимум два знака (такой алфавит называется двоичным).
Верхней границы числа знаков в алфавите не существует; примером могут служить иероглифы, каждый из которых обозначает целое понятие, и общее их количество исчисляется десятками тысяч.
Знаки, используемые для обозначения фонем человеческого языка, называются буквами, а их совокупность – алфавитом языка.
Сами по себе знак или буква не несут никакого смыслового содержания. Однако такое содержание им может быть приписано – в этом случае знак будет называться символом. Например, массу в физике принято обозначать буквой – следовательно, является символом физической величины «масса» в формулах. Иероглифы – тоже символы, поскольку наделены смыслом. Символами являются и пиктограммы в комьютерных интерфейсах, обозначающие в компьютерных программах объекты или действия.
Таким образом, понятия «знак», «буква» и «символ» не тождественны.
6. Преобразование сообщений
Вернемся к обсуждению информационных процессов, связанных с преобразованием одних сигналов в другие.
Поскольку имеются два типа сообщений, то между ними, очевидно, возможны четыре варианта преобразований:
Осуществимы и применяются на практике все четыре вида преобразований. Обсудим их.
Непрерывное 1 () Непрерывное 2 (). Примеры устройств, в которых осуществляется преобразование : микрофон (звуковые колебания преобразуется в электрические колебания); аудио- и видеомагнитофон (чередование областей намагниченности ленты превращается в электрические сигналы, которые затем преобразуются в изображение и звук); телекамера (изображение и звук превращаются в электрические сигналы); радиоприемник и телевизионный приемник (радиоволны преобразуются в электрические сигналы, а затем в звук и изображение). Особенностью преобразования является то, что оно всегда сопровождается частичной потерей информации. Потери связаны с помехами (шумами), которые порождает само информационное техническое устройство и которые воздействуют извне. Эти помехи примешиваются к основному сигналу и искажают его. Параметр аналогового сигнала может иметь любые значения (из некоторого интервала), при этом невозможно определить, был ли сигнал искажен или он изначально имел такой параметр. В ряде устройств искажение происходит в силу особенностей преобразования в них сообщения. Например, в черно-белом телевидении теряется цвет изображения; телефонная связь пропускает звук в более узком частотном интервале, чем частотный интервал человеческого голоса; кино- и видеоизображение оказываются плоскими, они утратили объемность.
Непрерывное 1 () Дискретное 2 (). С математической точки зрения перевод сигнала из аналоговой формы в дискретную означает замену описывающей его непрерывной функции времени на некотором временном интервале конечным множеством (массивом) , где , причем есть количество точек разбиения временного интервала. Подобное преобразование называется дискретизацией непрерывного (аналогового) сигнала. Дискретизация непрерывного сигнала осуществляется посредством двух операций: развертки по времени и квантования по величине параметра сигнала.
Развертка по времени состоит в том, что наблюдение за параметром сигнала производится не непрерывно, а лишь в определенные моменты времени с интервалом времени ,
.
Квантование по величине – это отображение вещественных значений параметра сигнала в конечное множество чисел, кратных некоторой постоянной величине – шагу квантования .
Совместное выполнение обеих операций эквивалентно нанесению сетки на график . В качестве пар значений выбираются узлы сетки, расположенные наиболее близко к . Таким образом, любое сообщение, описанное функцией , может быть преобразовано в дискретное, то есть представлено посредством некоторого алфавита.
При дискретизации может происходить потеря части информации, связанной с особенностями функции . Однако можно выполнить преобразование сообщения с необходимой, заданной точностью.
Существует теорема отсчетов, доказанная в 1933 году В. А. Котельниковым:
Непрерывный сигнал можно полностью отобразить и точно воссоздать по последовательности измерений или отсчетов величины этого сигнала через одинаковые интервалы времени , меньшие или равные половине периода, соответствующего максимальной частоте , имеющейся в непрерывном (аналоговом) сигнале:
. (2.1)
Строго говоря, теорема касается только тех линий связи, в которых для передачи информации используются колебательные или волновые процессы. Однако действие большинства практических устройств связи основано именно на этих процессах.
Другая формулировка теоремы отсчетов:
Развертка по времени может быть осуществлена без потери информации, связанной с особенностями непрерывного (аналогового) сигнала, если шаг развертки удовлетворяет условию (2.1).
Еще одна формулировка теоремы отсчетов:
Частота отсчетов должна быть больше или равной удвоенной максимальной частоте , имеющейся в непрерывном (аналоговом) сигнале:
. (2.2)
Пример. Для точной передачи речевого сигнала с частотой до при дискретной записи должно производиться не менее отсчетов в секунду, то есть величина частоты отсчетов должна быть, как минимум, .
Пример. В телевизионном сигнале максимальная частота . Следовательно, для точной передачи сигнала в цифровой форме потребуется, как минимум (и достаточно) миллионов отсчетов в секунду, то есть частота отсчетов должна быть как минимум .
Как было сказано выше, дискретизация имеет и другую составляющую – квантование. Шаг квантования определяется чувствительностью приемника информации (приемного устройства). Любой получатель сообщения – человек или устройство – всегда имеет конечную предельную точность распознавания величины параметра сигнала.
Пример. Человеческий глаз в состоянии различить около 16 миллионов цветовых оттенков. Следовательно, при квантовании цвета нет смысла делать большее число градаций.
Пример. При передаче речи достаточной оказывается точность около 1 от максимальной громкости звука. Следовательно, для амплитуды звуковых колебаний достаточен шаг квантования . Следовательно, алфавит для обозачения всех градаций громкости должен содержать 100 знаков (этого достаточно).
Указанные выше соображения по выбору шага развертки по времени и квантования по величине параметра сигнала лежат в основе оцифровки звука и изображения. Примерами устройств, в которых происходят преобразования сообщений из аналовой формы в дискретную и наоборот, являются: сканер, модем, устройства для цифровой записи звука и изображения, лазерный проигрыватель.
Преобразование сигналов типа и может осуществляться без потери содержащейся в них информации.
Дискретное 1 () Дискретное 2 (). Такое преобразование состоит в том, что при представлении сигналов происходит переход от одного алфавита к другому. Такая операция называется перекодировкой и может осуществляться без потерь информации. Пример ситуации, в которой осуществляется перекодировка: чтение–запись с компьютерных носителей информации (например, с одного носителя на другой).
На первый взгляд, непрерывные и дискретные сообщения оказываются равноправными. Однако на самом деле это не так. Сохранение информации в преобразованиях и обеспечивается именно благодаря участию в этих преобразованиях дискретного представления. Другими словами, преобразование сообщений без потерь информации возможно только в том случае, если хотя-бы одно из сообщений является дискретным. В этом проявляется несимметричность видов сообщений и преимущество дискретной формы.
Другие достоинства дискретной формы представления сообщений:
Универсальность есть следствие того, что любые дискретные сообщения, составленные в различных алфавитах, посредством обратимого кодирования можно привести к единому алфавиту. Это позволяет выделить некоторый алфавит в качестве базового (из соображений удобства, простоты, компактности) и представить в нем любую дискретную информацию. Тогда устройство, работающее с информацией в базовом алфавите, оказывается универсальным в том смысле, что оно может быть использовано для переработки любой иной исходной дискретной информации. Таким базовым алфавитом является двоичный алфавит, а использующим его универсальным устройством является компьютер.
Несимметричность непрерывной и дискретной информации имеет глубокую основу. Дело в том, что информация, порождаемая и существующая в природе, хаотическая и неупорядоченная, поскольку никем и ничем не регулируется ее появление, существование, использование. Чаще всего она непрерывна по форме представления (размеры, форма, цвет и другие физические, химические характеристики). Напротив, дискретная информация – это информация, прошедшая обработку – отбор, упорядочение, преобразование; она предназначена для дальнейшего применения человеком или техническим устройством. Дискретная информация даже может не иметь прямого отношения к природе и материальным объектам, например, законы математики. Дискретная информация – это уже частично осмысленная информация, то есть имеющая для кого-то смысл и значение, а также имеющая более высокий статус с точки зрения пользы.
Информатика имеет дело не с любой информацией и не с информацией вообще, а лишь с той информацией, которая кому-то необходима. Отсюда понятна приоритетность дискретной формы представления информации по отношению к непрерывной в решении задач автоматизации обработки информации. В дальнейшем мы будем исследовать только информацию, представленную дискретно с помощью некоторого алфавита. При этом нет необходимости рассматривать физические особенности передачи и представления информации, характер процессов и конкретные виды сигналов. Полученные результаты будут справедливы для любой дискретной (представленной с помощью дискретного сообщения) информации независимо от сообщения, с которым связана эта информация.
1. Понятие вероятности
В естественных науках изучаются явления, исход которых определяется однозначными причинно-следственными связями, выраженными с помощью математического понятия аргумент–функция. Например, электросопротивление цепи и напряжение на ее концах однозначно задают силу тока. Причем, сколько раз ни повторялся бы опыт, результат измерения силы тока окажется одинаковым (в пределах погрешности измерений).
Однако часто приходится иметь дело с явлениями, исход которых неоднозначен и зависит от факторов, которые мы не знаем или не можем учесть (математически описать). Простейший и традиционный пример – предсказание результата бросания монеты, то есть выпадение «орла» или «решки». Подобной же оказывается ситуация с выигрышем по лотерейному билету, получением определенной карты в карточных играх, результат спортивной встречи, количество пассажиров в автобусе и так далее
Явления (события), исход которых не может быть однозначно определен до того, как они произошли, называются случайными.
Раздел математики, в котором строится понятийный и математический аппарат для описания случайных событий, называется теорией вероятностей.
Будем называть отдельный повтор случайного явления опытом, а интересующий нас исход этого явления – благоприятным событием (или благоприятным исходом). Тогда, если – это общее число опытов, – это количество благоприятных исходов случайного события , то отношение есть доля благоприятных исходов в проведенной серии опытов или относительная частота появления благоприятного исхода. Однако в разных сериях при небольшом количестве опытов в каждой серии значение частоты может оказаться различной. Например, в серии из 3 опытов по бросанию монеты 2 раза выпал орел и 1 раз – решка. Если благоприятным исходом считать выпадение орла, то относительная частота получается равной . В другой же серии из 3 опытов результат может оказаться совершенно иным, например, все 3 раза выпадет решка, и, следовательно, частота появления орла оказывается равной .
Однако, частота стремится к некоторой определенной (и постоянной) величине в том случае, если количество опытов будет велико, и в предельном случае стремится к бесконечности. Эта величина называется вероятностью случайного события :
. (3.1)
Это определение вероятности называется частотным; оно применимо для возможных исходов, образующих дискретный набор.
Альтернативой случайному событию является событие, которое обязательно произойдет (например, наступление лета после весны) – это достоверное событие. Для достоверного события и .
События, которые никогда не могут произойти, называются невероятными, для них и . Например, невозможно вынуть красный шар из урны с белыми и черными шарами.
Случайные события располагаются между невероятными и достоверными:
. (3.2)
Выражение (3.2) – это условие нормировки вероятностей.
Еще раз отметим, что для достаточно точного определения вероятности случайного события нужно провести как можно больше опытов, в идеале – серию бесконечного числа опытов. Однако практически осуществить бесконечное число опытов невозможно. Поэтому для определения вероятности случайного события приходится применять другие соображения. Часто такие соображения недоказуемы, хотя верны и интуитивно понятны.
Часто рассматривается ситуация, в которой несколько независимых исходов случайного события принимаются равновероятными. В частности, принимается, что при условии однородности материала кубика и правильности его формы равновероятно выпадение любой из его 6 граней. Таким образом, если у случайного события могут быть равновероятных исходов, то вероятность наступления любого из них есть (табл. 2)
. (3.3)
Табл. 2. Вероятности равновероятных исходов опыта
|
Случайное событие |
Число возможных равновероятных исходов, |
Интересующий нас исход |
Вероятность интересующего нас исхода, |
|
Бросание монеты |
Выпадение орла |
||
|
Бросание игральной кости |
Выпадение грани с «5» |
||
|
Вытаскивание карты из колоды 36 карт |
Вытаскивание дамы пик |
Формула (3.3) обобщается на ситуацию, когда благоприятное событие осуществляется несколькими способами () из равновероятных исходов (очевидно, ), тогда (табл. 3)
. (3.4)
Табл. 3. Вероятности событий, осуществляющихся несколькими из равновероятных исходов
|
Случайное событие |
Интересующий нас исход |
|||
|
Бросание игральной кости |
Выпадение четной цифры |
|||
|
Вытаскивание карты из колоды 36 карт |
Вытаскивание туза |
|||
|
Вытаскивание любой пиковой карты |
||||
|
Доставание шара из ящика с 10 шарами, из которых 5 красных, 3 зеленых, 2 черных |
Доставание красного шара |
2. Сложение вероятностей независимых несовместных событий
Условимся обозначать знаком «» – логическое «или», знаком «» – логическое «и». Знак – означает «не A».
Пусть среди всех возможных равновероятных исходов опыта благоприятными оказыаются любое из событий или .
Пусть события и независимы (между ними отсутствуют причинно-следственные связи, не влечет за собой и наоборот).
Кроме того, пусть события и несовместны (они не могут наступить одновременно, или одно из них не может наступить, если наступило другое).
Пусть из общего числа возможных равновероятных исходов опыта событие осуществляется способами, а событие осуществляется способами. Тогда: , .
Справшивается, как найти вероятность интересующего нас сложного события ? – сумма событий и . Ясно, что общее число способов, которым может реализоваться событие , равно . Тогда получаем:
.
Таким образом,
Вероятность любого из двух независимых и несовместных событий равна сумме их вероятностей:
. (3.5)
Пример. Какова вероятность вынуть красный или зеленый шар из коробки с 10 шарами, в которой 5 красных, 3 зеленых и 2 черных шара?
Вероятность вынуть красный: , вероятность вынуть зеленый: , следовательно, .
Формула (3.5) обобщается на произвольное число благоприятных условий. Пусть из несовместных исходов опыта имеются благоприятных исходов, причем вероятности каждого из благоприятных исходов равны , где . Тогда вероятность наступления любого из этих благоприятных исходов равна
. (3.6)
Поскольку ясно, что в результате опыта с возможными исходами какой-либо исход обязательно произойдет, то вероятность сложного события , состоящего в наступлении любого исхода, равна единице (то есть достоверно):
. (3.7)
Формула (3.7) – это условие нормировки.
Если возможных исходов в опыте всего два (), то наступление одного исхода означает ненаступление другого . В этом случае исход является противоположным исходу , то есть («не »). Из условия нормировки (3.7) следует, что в таком опыте один из двух возможных исходов обязательно произойдет, то есть наступление исхода или исхода есть событие достоверное: , поэтому:
. (3.8)
События и называются дополнительными.
Пример. Какова вероятность не вытащить пиковую даму из колоды 36 карт? Вероятность вытащить (событие ) эту карту равна . Вероятность не вытащить ее (событие ) равна .
3. Умножение вероятностей независимых совместных событий
Совместные события могут произойти одновременно. Также события совместны, если одно из них может произойти, если произошло другое.
Пусть событие реализуется способами из равновероятных исходов одного опыта, а событие реализуется способами из равновероятных исходов другого опыта, независимого от первого.
Спрашивается, какова вероятность одноврменного наступления обоих событий и , или, что то же самое, наступления одного из этих событий при условии, что другое произошло? То есть надо определить вероятность сложного события . – это произведение событий и .
Ясно, что каждому из исходов первого опыта соответствуют исходов второго опыта, или наоборот, каждому из исходов второго опыта может соответствовать любой из исходов первого опыта. Поэтому общее количество возможных равновероятных исходов этих независимых обоих опытов равно произведению .
Также из тех же соображений ясно, что число возможных благоприятных (интересующих нас) исходов равно .
Таким образом, вероятность совместного наступления событий и определяется следующим образом:
.
Таким образом, вероятность одновременного (совместного) наступления двух благоприятных исходов независимых событий равна произведению их вероятностей:
. (3.9)
Пример. Какова вероятность выбросить 2 раза подряд по 6 очков в двух бросках кубика (или, что эквивалентно, при однократном броске двух кубиков)? Поскольку , то .
Формула (3.9) может быть обобщена на произвольное число совместных благоприятных событий (исходов) в независимых опытах. Если вероятности наступления этих событий в каждом из опытов , , …, , то вероятность их совместного наступления будет равна:
. (3.10)
Поскольку, , то, очевидно, , то есть вероятность совместного наступления событий не может превышать вероятность любого из них.
4. Нахождение среднего для значений случайных независимых величин
Рассмотрим ситуацию, когда случайное явление – это числовое значение некоторой величины. Например, число, указанное на грани игрального кубика; сумма выигрыша в лотерею и так далее Пусть этих значений и они образуют дискретный ряд , , …, . Среди этих значений могут оказаться одинаковые. Пусть таких групп одинаковых значений имеется . Очевидно, что . Спрашивается, каково среднее значение величины ? (Например, сколько в среднем очков выпадет при одном броске кубика?)
Будем исходить из определения среднего значения:
. (3.11)
Однако эта же сумма может быть получена, если провести суммирование по группам одинаковых значений. Пусть в каждой группе одинаковых значений по . Тогда:
.
Так как – вероятность появления результата из группы , то получаем:
. (3.12)
Пример. Найти среднее количество очков, выпадающее при однократном броске игральной кости (кубика).
Так как все , а количество очков принимает значения , по формуле (3.12) получаем:
.
Величина (3.12) – это взвешенное среднее для выборки , , …, .
5. Понятие условной вероятности
Отметим, что события и могут быть зависимыми – это наиболее общий случай. Зависимость случайных событий означает, что одно из них оказывает влияние на другое.
Например, Вы случйно встретили знакомого на вечеринке (событие ); однако Ваше появление на этой вечеринке также событие, строго говоря, случайное (событие ). Таким образом, случайное событие оказывается следствием случайного события .
Заметим, что вероятность любого случайного события зависит от каких-то условий, при которых возможно его наступление или ненаступление. Например, условием того, что вероятность выпадения всех цифр игральной кости одинакова и равна , является ее правильная геометрическая форма и однородность материала. Если условия изменятся (например, форма будет не куб, а параллелепипед), то изменится и вероятность.
Вероятность события при условии, что влияющее на него событие имело место, называется условной вероятностью.
Обозначать условную вероятность будем .
Вероятность событий, для которых условия не изменяются в различных сериях опытов, называется безусловной.
Случайные события и независимы, если их условные вероятности равны безусловным, то есть
и . (3.13)
Перечислим некоторые свойства условной вероятности:
6. Общая формула для вероятности произведения событий
Теперь при нахождении вероятности произведения событий рассмотрим наиболее общий случай, когда события и могут быть зависимыми.
Пусть из равновероятных исходов опыта событие реализуется способами. Из этих исходов исходов являются благоприятными для наступления события , связанного с событием . Тогда .
Пример. Имеется 3 урны, содержащие белые и черные шары. В первой урне 2 белых и 4 черных шара, во второй – 3 белых и 3 черных, в третьей – 4 белых и 2 черных. Из одной из урн (неизвестно, из какой) наугад вынут шар. Какова вероятность того, что вынут из первой урны при условии, что шар оказался белым?
Пусть событие – вытаскивание белого шара, а – то, что он вынут из первой урны. Из всех имеющихся шаров событию благоприятствуют шаров; из них лишь шара благоприятствуют событию . Таким образом, получаем: .
Вероятность совместного выполнения событий и равна
.
Итак, окончательно получаем:
. (3.14)
Выражение (3.14) является наиболее общим правилом умножения вероятностей. В частном случае независимости событий и из формулы (3.14) при условии (3.13) получаем формулу (3.9).
Пример. На карточках отдельными буквами написано слово «ПАПАХА». Карточки переворачивают, перемешивают и случайным образом открывают 4 из них. Какова вероятность получить таким путем слово «ПАПА»?
Пусть событие – извлечение первой «П», событие – извлечение второй «А», – третьей «П» и – четвертной «А». Тогда интересующее нас событие можно записать как . Его вероятность можно найти, применяя несколько раз формулу (3.14).
;
;
;
;
;
Итак, получаем:
.
7. Общая формула для вероятности суммы событий
Обобщим формулу для вероятности наступления суммарного события (3.5) на ситуацию, когда отдельные события и могут оказаться совместными, то есть происходить одновременно. В этом случае получается, что .
Пусть событие выполняется при исходах из равновероятных возможных исходов опыта, а событие выполняется при исходах из тех же возможных исходов опыта. Однако из-за того, что возможно совместное выполнение событий и , исходы и могут оказаться не полностью различимыми, то есть среди них могут быть одни и те же исходы. Тогда суммарное количество благоприятных исходов (когда выполняется или ) . Следовательно,
,
то есть получаем .
Определим конкретное значение величины .
Пусть среди исходов и имеются общих исходов, то есть таких, когда события и наступают одновременно. Вероятность совместного события (одновременного наступления и ) равна
. (3.15)
Общее количество различных благоприятных исходов равно . Тогда вероятность равна
. (3.16)
Таким образом, окончательно получаем:
. (3.17)
В частном случае, когда события и несовместны, , и вместо (3.16) или (3.17) мы получаем формулу (3.5).
Пример. Какова вероятность вынуть из колоды 36 карт козыря или туза, если одна из мастей объявлена козырной? Событие – получение козыря – имеет вероятность , поскольку карт одной масти в колоде имеется 9. Событие – получение туза – имеет вероятность , поскольку тузов 4. Однако один туз является козырным (то есть события и реализуются одновременно, а такой вариант по условию задачи мы не рассматриваем как благоприятное событие); вероятность его появления равна . Тогда, согласно формуле (3.17), получаем: .
С учетом формул (3.14) и (3.16) можно получить самое общее правило сложения вероятностей:
. (3.18)
1. Энтропия как мера неопределенности
Случайные события могут быть описаны с использованием понятия «вероятность». Соотношения теории вероятностей позволяют найти (вычислить) вероятности как одиночных случайных событий, так и исходов сложных опытов, объединяющих несколько независимых или связанных между собой событий. Однако описать случайные события можно не только в термнах вероятностей.
То, что событие случайно, означает отсутствие полной уверенности в его наступлении. Это создает неопределенность в исходах опытов, в результате которых данное событие может произойти. Безусловно, степень неопределенности различна для разных ситуаций. Например, если опыт состоит в определении возраста случайно выбранного студента 1-го курса дневного отделения ВУЗа, то с большой степенью уверенности можно лишь утверждать, что он окажется менее 30 лет. При этом с меньшей уверенностью можно утверждать, что возраст произвольно выбранного студента окажется менее 17 лет. Таким образом, существует неопределенность в исходе опыта, который состоит в проверке возраста случайно выбранного студента.
Для практики важно иметь возможность произвести численную оценку неопределенности исходов разных опытов. Попробуем ввести такую количественную меру неопределенности.
Начнем с простой ситуации, когда опыт имеет равновероятных исходов. Очевидно, что неопределенность каждого из них зависит от , то есть мера неопределенности является функцией числа исходов .
Можно сразу указать некоторые свойства этой функции:
Попробуем определить явный вид функции . Будем обозначать опыты со случайными исходами маленькими греческими буквами , и так далее, а отдельные исходы опытов (события) – латинскими заглавными буквами , и так далее
Рассмотрим два независимых опыта и с количествами равновероятных исходов соответственно и .
Пусть имеет место сложный опыт, который состоит в одновременном выполнении опытов и . Число возможных равновероятных его исходов равно . Очевидно, неопределенность исхода такого сложного опыта будет больше неопределенности опыта , поскольку к ней добавляется неопределенность опыта . Естественно обозначить неопределенность этого сложного опыта как . С другой стороны, меры неопределенности отдельных опытов и составляют соответственно и . В случае сложного опыта проявляется общая (суммарная) неопределенность совместных событий. Однако из независимости и следует, что в сложном опыте неопределенности каждого из и никак не могут повлиять друг на друга. Следовательно, мера суммарной неопределенности должна быть равна сумме мер неопределенности каждого из опытов, то есть мера неопределенности аддитивна:
. (4.1)
Теперь задумаемся о том, каким может быть явный вид функции , чтобы она удовлетворяла следующим свойствам:
Легко увидеть, что такому набору свойств удовлетворяет логарифмическая функция , причем доказано, что она единственная из всех существующих классов функций.
Таким образом,
За меру неопределенности опыта с равновероятными исходами принимается число .
Отметим, что выбор основания логарифма в данном случае принципиального значения не имеет, так как в силу известной формулы преобразования логарифма от одного основания к другому:
.
Изменение значения основания логарифма связано с выбором единицы измерения неопределенности. Удобным основанием оказывается число 2. В этом случае за единицу измерения неопределенности принимается неопределенность, содержащаяся в опыте, имеющем лишь два равновероятных исхода: , поэтому .
Единица измерения неопределенности называется бит.
1 бит – это неопределенность, заключенная в опыте с двумя равновероятными исходами.
Таким образом, нами установлен явный вид функции, описывающей меру неопределенности исхода опыта, имеющего равновероятных исходов:
. (4.2)
Величина меры неопределенности получила название энтропия. Будем ее обозначать H.
Вновь рассмотрим опыт с равновероятными исходами. Поскольку каждый исход случаен, он вносит свой вклад в неопределенность всего опыта. Но так как все исходов равновероятны, разумно допустить, что каждый из этих исходов вносит в опыт одинаковую долю неопределенности. Из свойства аддитивности неопределенности, а также из свойства (4.2) следует, что неопределенность, вносимая одним исходом равна
,
где – вероятность любого из отдельных исходов.
Таким образом, неопределенность, вносимая каждым из равновероятных исходов, равна:
. (4.3)
Теперь обобщим формулу (4.3) на ситуацию, когда исходы опыта неравновероятны и имеют вероятности , где .
Тогда неопределенность, вносимая -м исходом равна
.
По свойству аддитивности неопределенности (энтропии) общая неопределенность опыта равна
. (4.4)
Введенная таким образом величина (4.4), как уже было сказано, называется энтропией опыта .
Энтропия является мерой неопределенности результата опыта, в котором проявляются случайные события, и равна средней неопределенности всех возможных его исходов.
Для практики формула (4.4) важна тем, что позволяет сравнить неопределенности различных опытов со случайными исходами.
Пример 1. Имеются два ящика, в каждом из которых по 12 шаров. В первом – 3 белых, 3 черных и 6 красных; во втором – каждого цвета по 4. Опыты состоят в вытаскивании по одному шару из каждого ящика. Что можно сказать относительно неопределенностей исходов этих опытов? Согласно формуле (4.4) находим энтропии обоих опытов:
;
;
Таким образом, , то есть неопределенность результата в опыте выше, и, следовательно, предсказать его исход можно с меньшей долей уверенности, чем результат опыта .
2. Свойства энтропии
. (4.5)
Энтропия сложного опыта, состоящего из нескольких независимых опытов, равна сумме энтропий отдельных опытов.
Приведем доказательство формулы (4.5).
Пусть опыт имеет исходов , , …, , которые реализуются с вероятностями , , …, , а опыт имеет исходов , , …, с вероятностями , , …, . Сложный опыт имеет исходов типа , где , . Поэтому (см. (4.4)):
. (4.6)
Поскольку опыты и независимы, то независимыми окажутся события в любой паре . Поэтому:
, на основании чего
Таким образом, формулу (4.6) перепишем так:
;
;
.
Известно, что по условию нормировки вероятностей
и ,
Из формулы (4.4) следует, что
и .
Поэтому окончательно имеем:
,
что и требовалось доказать.
Теперь рассмотрим ситуацию, когда имеются два опыта с одинаковым числом исходов , в одном случае () они равновероятны, а в другом () – нет. Каково соотношение энтропий этих опытов? Примем без доказательства следующее утверждение:
. (4.7)
При прочих равных условиях наибольшую энтропию имеет опыт с равновероятными исходами.
Другими словами, энтропия максимальна в опытах, где все исходы равновероятны.
Кстати, результат, полученный в рассмотренном выше примере 1, иллюстрирует справедливость формулы (4.7).
Здесь усматривается аналогия (имеющая глубинную первооснову!) с понятием энтропии, используемым в физике. Впервые понятие энтропии было введено в 1865 году немецким физиком Рудольфом Клаузиусом: энтропия – это функция состояния термодинамической системы, описывающая направленность самопроизвольных процессов в системе. Клаузиус сформулировал II начало термодинамики. В частности, он показал, что энтропия достигает максимума в состоянии равновесия системы. Позднее, в 1872 году Людвиг Больцман, развивая статистическую теорию, связал энтропию системы с вероятностью ее (системы) состояния, дал статистическое (вероятностное) толкование II-му началу теормодинамики. В частности, Больцман показал, что вероятность максимальна у полностью разупорядоченной (равновесной) системы (аналогия с опытом, имеющим равновероятные исходы). Энтропия и термодинамическая вероятность тоже связаны логарифмической зависимостью. В физике энтропия мера беспорядка в системе. При этом беспорядок понимается как отсутствие знания о характеристиках объекта (например, координат и скорости молекулы газа); с ростом беспорядка в системе возрастает энтропия, то есть возрастает наше незнание о системе, другими словами, уменьшаются наши знания о системе.
3. Условная энтропия
Найдем энтропию сложного опыта в том случае, если опыты не являются независимыми, то есть если на исход опыта оказывает влияние результат опыта . Например, пусть в ящике всего два разноцветных шара и опыт состоит в извлечении первого, а опыт – в извлечении второго из них. В этом случае результат опыта полностью снимает неопределенность сложного опыта , то есть оказывается, что , но не . Сумма проявляется лишь для независимых событий!
Связь между зависимыми опытами и состоит в том, что какие-то из исходов могут оказывать влияние на исходы , то есть некоторые пары событий и не являются независимыми. Вернемся к формуле (4.6) для энтропии сложного опыта:
.
В случае зависимых событий: , где – это вероятность наступления исхода опыта при условии, что в опыте имел место исход .
В этом случае по свойству логарифма:
.
После подстановки в формулу (4.6) получаем:
;
;
Устанавливаем порядок суммирования, по аналогии с интегрированием:
В этой формуле:
, так как какое-то из событий обязательно произойдет после того, как произошло событие , поэтому:
;
, в результате
.
,
таким образом,
;
Величины
(4.8)
имеют смысл энтропии опыта при условии, что в опыте реализовался исход . Величину будем называть условной энтропией.
Величина
(4.9)
имеет смысл средней условной энтропии опыта при выполнении опыта . Окончательно получаем для энтропии сложного опыта при условии, что в нем могут быть зависимые исходы:
. (4.10)
Полученное выражение представляет собой общее правило нахождения энтропии сложного опыта. Совершенно очевидно, что выражение (4.5) является частным случаем формулы (4.10) при условии независимости опытов и .
Относительно условной энтропии можно сделать следующие утверждения:
. (4.11)
Другими словами, опыт может либо не оказывать никакого влияния на энтропию опыта (если опыты независимы), либо может понижать энтропию опыта (то есть повысить определенность, повысить наше знание об исходах опыта ). Таким образом, условная энтропия не превосходит безусловную.
3. Из соотношений (4.10) и (4.11) следует, что
, (4.12)
причем равенство реализуется только при независимости опытов и .
Пример. В ящике имеются 2 белых и 4 черных шара. Из ящика извлекают последовательно два шара без возврата. Найти энтропию, связанную с первым и вторым извлечениями, а также энтропию обоих извлечений.
Будем считать опытом извлечение первого шара. Он имеет два исхода. Первый исход – вынут белый шар; его вероятность . Второй исход – – вынут черный шар; его вероятность . По формуле (4.4) сразу находим:
.
Опыт – также имеет два исхода. – вынут белый шар, – вынут черный шар, однако вероятности этих исходов зависят от того, каким был исход опыта . Именно,
При : и ;
При : и .
Итак, энтропия, связанная со вторым опытом, является условной, и, согласно, формуле (4.8), получаем:
;
.
По формуле (4.9) получаем:
.
По формуле (4.10) получаем:
.
Ответ: , , .
1. Объемный подход к измерению количества информации
Объем данных в сообщении измеряется количеством символов (разрядов) в этом сообщении. В различных системах счисления один разряд имеет различный вес. Также в различных системах счисления различны единицы измерения объема данных.
В двоичной системе счисления единица измерения количества информации – бит (bit – binary digit – двоичная цифра, двоичный разряд). В десятичной системе счисления единица измерения – дит (десятичный разряд).
Создатели компьютеров отдают предпочтение именно двоичной системе счисления потому, что в техническом устройстве наиболее просто реализовать два противоположных физических состояния. Имеется в виду некоторый физический элемент, имеющий два различных состояния: намагниченность в двух противоположных направлениях; прибор, пропускающий или не пропускающий электрический ток; конденсатор, заряженный или незаряженный; и т.п.
В компьютере бит является наименьшей возможной единицей информации. Объем данных, записанных двоичными знаками в памяти компьютера или на внешнем носителе информации, подсчитывается просто по количеству требуемых для такой записи двоичных символов. При этом, естественно, невозможно нецелое число битов.
Для удобства использования введены и более крупные, чем бит, единицы количества информации:
8 бит = 1 байт;
1024 байта = 1 килобайт (Кбайт);
1024 килобайта = 1 мегабайт (Мбайт);
1024 магабайта = 1 гигабайт (Гбайт);
Кроме объемного подхода к измерению количества информации (в этом случае уместно говорить о количестве данных) существует вероятностный подход к измерению количества информации.
2. Энтропийный подход к измерению количества информации
Как выяснено в предыдущей лекции, предшествующий опыт может уменьшить количество исходов последующего опыта и, следовательно, уменьшить его неопределенность. Разность величин и , очевидно, показывает, какие новые сведения относительно опыта мы получаем, произведя опыт . Эта величина называется информацией относительно опыта , содержащейся в опыте :
. (5.1)
Данное выражение открывает возможность численного измерения количества информации, поскольку оценивать энтропию мы уже умеем. Из формулы (5.1) легко получить ряд следствий:
Следствие 1. Поскольку единицей измерения энтропии является бит, то в этих же единицах может быть измерено количество информации.
Следствие 2. Пусть опыт , то есть просто произведен опыт сам по себе. Поскольку результат его несет полную информацию о себе самом, неопределенность исхода этого опыта полностью снимается, то есть . Тогда из (5.1) следует: .
Тогда можно считать, что энтропия опыта равна той информации, которую мы получаем в результате его осуществления.
Отметим ряд свойств информации:
. (5.2)
Таким образом, информация опыта равна среднему значению неопределенности, содержащейся в каком-либо одном его исходе).
Пример. Какое количество информации требуется, чтобы узнать исход броска монеты?
По формуле (5.2):
;
– вероятность выпадения герба;
– вероятность выпадения решки;
.
Пример. Игра. Некто задумал целое число в интервале от 0 до 3. Наш опыт состоит в угадывании этого числа. На наши вопросы Некто может отвечать лишь «Да» или «Нет» (то есть давать бинарные ответы). Какое количество информации должны мы получить, чтобы узнать задуманное число, то есть полностью снять начальную неопределенность? Как правильно построить процесс угадывания?
Исходами (их всего 4) в данном случае являются: – задуман 0; – задумана 1; – задумана 2; – задумана 3. Конечно, предполагается, что вероятности быть задуманными у всех чисел одинаковы, поэтому , где .
.
По формуле (5.2):
.
Таким образом, для полного снятия неопределенности опыта (для угадывания задуманного числа) нам необходимо 2 бит информации.
Выясним, какие вопросы необходимо задать, чтобы процесс угадывания был оптимальным, то есть содержал минимальное число вопросов. Здесь удобно воспользоваться так называемым выборочным каскадом (рис. 1):
Рис. 1. Выборочный каскад
Таким образом, для решения этой задачи оказалось достаточно двух вопросов. Совпадение между количеством информации и числом вопросов с бинарными ответами неслучайно.
Количество информации численно равно количеству вопросов с равновероятными бинарными вариантами ответов, которые необходимо задать, чтобы полностью снять неопределенность задачи.
В рассмотренном примере два полученных ответа в выборочном каскаде полностью сняли начальную неопределенность. Подобная процедура позволяет определить количество информации в любой задаче, интерпретация которой может быть сведена к парному выбору. Данное утверждение перестает быть справедливым в том случае, если каждый из двух возможных ответов имеет разную вероятность – такая ситуация будет рассмотрена позднее.
Получим следствие формулы (5.2) для случая, когда все исходов опыта равновероятны. Именно такие опыты и рассматривались в примерах 1 и 2. В этом случае все
,
и, следовательно, формулу (5.2) можно переписать так:
.
Таким образом,
. (5.3)
Эта формула была выведена в 1928 году инженером Р. Хартли (США) и носит его имя. Она связывает количество равновероятных состояний и количество информации в сообщении о том, что какое-то из этих состояний реализовалось.
Смысл формулы: если некоторое множество сожержит элементов и принадлежит этому множеству, то для его выделения (однозначной идентификации) среди прочих требуется количество информации, равное (см. приведенные выше примеры с броском монеты и с угадыванием задуманного числа из некоторого интервала).
Частным случаем применения формулы (5.3) является ситуация, когда число возможных состояний (исходов опыта) можно представить в виде . Именно эта ситуация реализовалась в рассмотренных выше двух примерах. Подставляя в формулу (5.3), получаем:
. (5.4)
Анализируя результаты решения задач в примерах, можно прийти к выводу, что число как раз равно количеству вопросов с бинарными равновероятными ответами. Число этих вопросов и определяет количество информации об опыте (о результате (исходе) опыта).
Пример. Случайным образом вынимается карта из колоды в 32 карты. Какое количество информации требуется, чтобы угадать, что это за карта?
Для данной ситуации возможных исходов . Значит, , следовательно, .
Попытаемся понять смысл полученных в данном разделе результатов. Необходимо выделить ряд моментов.
,
то есть информация равна убыли энтропии.
В частном случае, если изначально равновероятных исходов в опыте было , а в результате передачи информации неопределенность в исходе (результате) опыта уменьшилась, и число исходов стало (очевидно, что ), то из (5.1) получается:
.
Таким образом, можно дать следующее определение понятия информации:
Информация – это содержание сообщения, понижающего неопределенность некоторого опыта с неоднозначным исходом; убыль связанной с этим опытом энтропии является количественной мерой информации.
В случае равновероятных исходов некоторого опыта информация равна логарифму (по основанию 2) отношения числа возможных исходов этого опыта до и после получения информации.
В теории информации энтропия также отражает неопределенность, однако, это неопределенность иного рода – она связана с незнанием результата опыта с набором случайных возможных исходов.
Таким образом, между энтропией в физике и информатике много общего. Однако необходимо осознавать и различие. Совершенно очевидно, что в дальнейшем в данном курсе мы будем использовать понятие энтропии в аспекте теории информации.
Докажем это.
Пусть с выбором одного из элементов множества , содержащего элементов, связано информации, а с выбором одного из элементов множества , содержащего элементов, связано информации. Пусть второй выбор никак не связан с первым, тогда при объединении множеств число возможных состояний (вариантов общего выбора) будет . Тогда для определения (отбора) определенной (конкретной) комбинации элементов потребуется количество информации:
,
что и требовалось доказать.
Однако представим, что мы одновременно угадываем шесть целых чисел, каждое из которых находится в интервале от 0 до 6 включительно. Таким образом, необходимо отгадать одну из возможных комбинаций, которых в этой ситуации всего
, где .
Но полученное число комбинаций меньше, чем (хотя и больше, чем ). Следовательно, для угадывания всей шестизначной комбинации требуется информации, то есть нужно задать 17 вопросов. В среднем на угадывание одного из элементов (чисел), входящих в эту шестизначную комбинацию, приходится вопроса, что близко к значению .
Таким образом, величина , определяемая описанным выше способом, показывает, сколько в среднем необходимо сделать парных выборов (задать вопросов с равновероятными бинарными ответами) для установления результата опыта (полного снятия неопределенности), когда число возможных исходов велико ().
Рассмотрим опыт, реализующийся посредством двух случайных событий. Поскольку их (этих случайных событий) всего два, очевидно, что они являются дополнительными друг другу. Если эти события равновероятны, то их вероятности , поэтому информация, связанная с опытом, в результате которого появляется одно из этих событий, равна , как следует из (5.2) и из формулы Хартли. Однако, если вероятности этих событий различны (, ), то из формулы (5.2) получаем функцию:
.
На рис. 2 представлен график функции .
Видно, что при и при функция . В частности, кривая симметрична относительно прямой и достигает максимума .
Рис. 2. График функции I(p).
Если теперь считать, что событие «1» – это утвердительный ответ на бинарный вопрос, а событие «2» – это отрицательный ответ на этот бинарный вопрос, то приходим к следующему заключению:
Ответ на бинарный вопрос может содержать не более 1 бит информации. При этом информация равна 1 бит только в случае равновероятных бинарных ответов; в остальных случаях информация меньше 1 бит.
Пример. При угадывании результата броска игральной кости задается вопрос: «Выпало 6?» Какое количество информации содержит ответ?
Утвердительный ответ имеет вероятность .
Отрицательный ответ имеет вероятность .
Таким образом, по формуле (5.2):
;
;
.
Таким образом, больше неопределенности (необходимой для ее снятия информации) связано с теми событиями (исходами опыта), которые менее вероятны. Действительно, то, что произойдет именно , мы почти наверняка знали и до опыта; поэтому реализация этого исхода добавляет мало к нашей осведомленности о результате опыта. Наоборот, исход – весьма редкий (трудноожидаемый); неопределенности с ним связано больше, поэтому и информации надо получить больше, чтобы узнать, что произойдет именно событие . Однако при многократных повторах опыта такое количество информации мы получать не будем, так как событие маловероятно и будет происходить редко. Среднее же количество информации на один исход, то есть информация об опыте, согласно формуле (5.2) равна .
Рассматривая формы представления информации (сообщений), отметили то обстоятельство, что естественной для органов чувств человека являетя аналоговая форма представления сообщений. Универсальной все же следует считать дискретную форму представления информации с помощью некоторого набора знаков. В частности, именно таким образом представленная информация обрабатывается компьютером, передается по компьютерным линиям связи.
В устной речи это достигается посредством использования различных фонем (звуков), по которым и отличаются знаки речи. В письменности это достигается с помощью различного начертания букв и дальнейшего анализа написанного.
Как данная задача может решаться техническим устройством, рассмотрим позже. Сейчас для нас важно, что можно реализовать некоторую процедуру, посредством которой можно выделить из сообщения тот или иной знак.
Необходимо отметить, что для нас (для приемника сообщения) появление конкретного знака (буквы) в конкретном месте сообщения – событие случайное. Следовательно, узнавание (отождествление с эталоном) знака требует получения некоторой порции информации, то есть снятия неопределенности, связанной с появлением этого знака. Эту информацию можно связать с самим знаком и считать, что знак несет в себе (содержит) некоторое количество информации.
Попробуем оценить это количество информации.
Предположим, что появление всех знаков (букв) алфавита в сообщении равновероятно (в реальности это не так).
В английском алфавите с учетом знака «пробел» имеется знаков, для русского алфавита с учетом пробела . Для оценки информации, приходящейся на один знак алфавита, применим формулу Хартли:
.
Таким образом, ; .
Получается, что в нулевом приближении со знаком русского алфавита в среднем связано больше информации, чем со знаком английского алфавита. Это, безусловно не означает, что английский язык – язык Шекспира и Диккенса – беднее, чем язык Пушкина и Достоевского. Лингвистическое богатство языка определяется количеством слов и их сочетаний, и никак не связано с числом букв в алфавите.
Продолжим анализировать количество информации, связанное с одним символом алфавита.
Рассмотрим следующий набор знаков на основе русского алфавита. В рассматриваемый алфавит включен знак «пробел» для разделения слов. Кроме того, в этом алфавите буквы «е» и «ё» не различаются (часто так принято в печатных текстах), знаки «ь» и «ъ» также не различаются (так принято в телеграфном кодировании). В результате получаем алфавит из 32 знаков. Рассмотрим таблицу средних частот появления знаков такого алфавита, то есть таблицу вероятностей появления этих знаков в сообщениях (табл. 4). Эта таблица построена на основе статистического исследования, обработки большого количества различных сообщений.
Табл. 4. Таблица вероятностей появления знаков русского алфавита в сообщениях
|
Знак |
пробел |
о |
е, ё |
а |
и |
т |
н |
с |
|
Относит. частота |
0.175 |
0.090 |
0.072 |
0.062 |
0.062 |
0.053 |
0.053 |
0.045 |
|
Знак |
р |
в |
л |
к |
м |
д |
п |
У |
|
Относит. частота |
0.040 |
0.038 |
0.035 |
0.028 |
0.026 |
0.025 |
0.023 |
0.021 |
|
Знак |
я |
ы |
з |
ь, ъ |
б |
г |
ч |
й |
|
Относит. частота |
0.018 |
0.016 |
0.016 |
0.014 |
0.014 |
0.013 |
0.012 |
0.010 |
|
Знак |
х |
ж |
ю |
ш |
ц |
щ |
э |
ф |
|
Относит. частота |
0.009 |
0.007 |
0.006 |
0.006 |
0.004 |
0.003 |
0.003 |
0.002 |
Аналогичные подсчеты можно произвести и для других языков.
Если расположить все буквы языка в порядке убывания вероятностей их появления, то получатся следующие последовательности:
|
Английский язык: |
«Пробел», E, T, A, O, N, R, … |
|
Немецкий язык: |
«Пробел», E, N, I, S, T, R, … |
|
Французский язык: |
«Пробел», E, S, A, N, I, T, … |
Для оценки информации, связанной с выбором одного знака алфавита с учетом неравной вероятности их появления в сообщении (текстах) можно воспользоваться формулой (5.2) из предыдущей лекции:
.
Из этой формулы, в частности, следует, что если – вероятность (относительная частота – в большом количестве сообщений) знака номер данного алфавита из знаков, то среднее количество информации, приходящейся на один знак, равно:
. (6.1)
Формула (6.1) – это знаменитая формула К. Шеннона, с работы которого «Математическая теория связи» (1948 год) принято начинать отсчет возраста информатики, как самостоятельной науки.
Следует отметить, что и в нашей стране практически в то же время велись подобные исследования. Например, в том же 1948 году вышла работа А.Н. Колмогорова «Математическая теория передачи информации».
В общем случае информация, которая содержится в сообщении, может зависеть от того, в какой момент времени оно достигает приемника. Например, несвоевременное сообщение о погоде, очевидно, не несет той же информации, что и своевременное.
Однако возможно существование сообщений, в которых содержащаяся в них информация не зависит от времени поступления. В частности, такая ситуация реализуется в том случае, если вероятность встретить в сообщении какой-либо знак номер не зависит от времени, точнее, она одинакова во все моменты времени и равна относительной частоте появления этого знака во всей последовательности знаков. Поэтому вероятности знаков (относительные частоты) определяются для сообщений (текстов), содержащих большое число символов с тем, чтобы проявились статистические закономерности, и далее эти вероятности считаются неизменными во всех сообщениях данного источника.
Сообщения, в которых вероятность появления каждого отдельного знака не меняется со временем, называются шенноновскими сообщениями, а порождающий их отправитель – шенноновским источником.
Если сообщение является шенноновским, то набор знаков (алфавит) и связанная с каждым знаком информация известны заранее. В этом случае интерпретация сообщения, представляющего собой последовательность сигналов, сводится к задаче распознавания знака, то есть к выявлению, какой именно знак находится в данном месте сообщения. При этом количество информации, содержащееся в знаке, служит мерой затрат по его выявлению.
Теория информации строится именно для шенноновских сообщений, поэтому в дальнейшем мы будем считать это исходным положением (условием использования) теории и рассматривать только такие сообщения.
Формула Шеннона позволяет оценить количество информации на один знак в алфавите уже в первом приближении. Применение формулы Шеннона (6.1) к алфавитам дает следующие средние значения информации, приходящейся на один знак:
|
для русского языка: |
; |
|
для английского языка: |
; |
|
для французского языка: |
; |
|
для немецкого языка: |
; |
|
для испанского языка: |
. |
Таким образом, учет различий в вероятностях появления букв в сообщениях приводит к уменьшению среднего информационного содержания буквы.
Английский, немецкий, французский, испанский языки принадлежат к романо-германской языковой группе и основаны на одном алфавите. Несовпадение значений средней информации на один знак в этих языках является следствием того, что частоты появления одинаковых букв в разных языках различны.
Учет в английских словах двухбуквенных сочетаний понижает среднюю информацию на знак до значения , учет трехбуквенных сочетаний понижает среднюю информацию на знак до значения . К. Шеннон сумел приблизительно оценить и .
Аналогичные исследования для русского языка показывают, что учет двухбуквенных сочетаний понижает среднюю информацию на знак до значения , а учет трехбуквенных сочетаний понижает среднюю информацию на знак до значения .
Последовательность , , , … является убывающей в любом языке. Эстраполируя эту последовательность на учет бесконечного числа корреляций, можно оценить предельную информацию на знак в данном языке , которая будет отражать минимальную неопределенность, связанную с выбором знака алфавита без учета семантических (смысловых) особенностей языка.
Величина средней информации на знак в нулевом приближении является другим предельным случаем, поскольку характеризует наибольшую информацию, которая может содержаться в знаке данного алфавита.
К. Шеннон ввел величину, которую назвал относительной избыточностью языка:
. (6.2)
Избыточность является мерой бесполезно совершаемых альтернативных выборов при чтении текста. Эта величина показывает, какую долю лишней информации содержат тексты на данном языке; лишней в том смысле, что она определяется структурой самого языка и, следовательно, может быть восстановлена без явного указания в буквенном виде.
Исследования Шеннона для английского языка дали значения , , откуда для избыточности получилось
.
Подобные оценки показывают, что и для других европейских языков, в том числе для русского языка, избыточность составляет 60–70. Это означает, что в принципе возможно почти трехкратное сокращение текстов без ущерба для их содержательной стороны и выразительности. Например, телеграфные тексты делаются короче за счет отбрасывания союзов и предлогов без ущерба для смысла. В телеграфных текстах используются однозначно интерпретируемые сокращения «ЗПТ» и «ТЧК» вместо полных слов (эти сокращения приходится использовать, поскольку знаки «.» и «,» не входят в телеграфный алфавит). Однако такое «экономичное» представление слов снижает разборчивость языка, уменьшает возможность понимания речи при наличии шума (а это одна из проблем передачи информации по линиям связи). Также сокращения снижают возможность локализации и исправления ошибки при ее возникновении.
Отметим, что избыточность языка имеет полезные функции. Избыточность есть определенная страховка и гарантия разборчивости сообщений (текстов). Избыточность позволяет восстановить текст, даже если он содержит большое число ошибок или неполон (например, при отгадывании кроссвордов, при игре «Поле чудес»).
Теория кодирования информации является одним из разделов теоретической информатики. К основным задачам, решаемым в данном разделе информатики, необходимо отнести следующие:
Как отмечалось при рассмотрении исходных понятий информатики, для представления дискретных сообщений используется некоторый алфавит. Однако часто однозначное соответствие между содержащейся в сообщении информацией и его (сообщения) алфавитом отсутствует.
В целом ряде практических приложений возникает необходимость перевода сообщения из одного алфавита в другой, причем такое преобразование не должно приводить к потере информации.
Введем ряд определений.
Будем считать, что источник информации представляет информацию в форме дискретного сообщения, используя для этого алфавит, который мы условимся называть первичным алфавитом. Далее это сообщение попадает в устройство, преобразующее и представляющее сообщение в другом алфавите – этот алфавит мы назовем вторичным алфавитом.
Код – это правило, описывающее соответствие знаков или сочетаний знаков первичного алфавита знакам или сочетаниям знаков вторичного алфавита.
При этом существует и другое определение:
Код – это набор знаков или сочетаний знаков вторичного алфавита, используемый для представления знаков или сочетаний знаков первичного алфавита.
Кодирование – это перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов.
Декодирование – это операция, обратная кодированию, то есть восстановление информации в первичном алфавите по полученной последовательности кодов.
Кодер – это устройтство, обеспечивающее выполнение операции кодирования.
Декодер – это устройство, производящее декодирование.
Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечивает возврат к исходной информации без каких-либо ее потерь.
Примером обратимого кодирования является представление знаков в телеграфном коде и их восстановление (получателем) после передачи.
Примером необратимого кодирования может служить перевод с одного естественного языка на другой. При этом обратный перевод, вообще говоря, не восстанавливает исходного текста. Здесь важно понимать, что исходная информация восстанавливается с потерями как в смысловом отношении, так и в смысле искажения в форме представления (полученная после обратного перевода последовательность знаков первичного алфавита практически всегда уже другая по сравнению с исходным текстом).
Безусловно, для практических задач, связанных со знаковым представлением информации, возможность восстановления информации по ее коду является необходимым условием применимости кода, поэтому в дальнейшем мы ограничимся только рассмотрением обратимого кодирования.
Кодирование информации предшествует передаче и хранению информации. При этом хранение информации связано с фиксацией некоторого состояния носителя информации, а передача информации связана с процессом изменения состояния носителя информации (среды), то есть с сигналами. Эти состояния или сигналы мы будем называть элементарными сигналами. Совокупность элементарных сигналов и составляет вторичный алфавит.
Сейчас мы не будем обсуждать технические стороны передачи и хранения сообщения, то есть не будем обсуждать то, каким образом технически реализованы передача и прием последовательности сигналов или фиксация состояний носителя информации (запись информации).
Попробуем сделать математическую постановку задачи кодирования информации.
Пусть первичный алфавит состоит из знаков со средней информацией на знак , а вторичный алфавит состоит из знаков со средней информацией на знак . Пусть также исходное сообщение, представленное в первичном алфавите, содержит знаков, а закодированное сообщение (представленное во вторичном алфавите) содержит знаков. Таким образом, исходное сообщение содержит информации, а закодированное сообщение содержит информации.
Операция обратимого кодирования может увеличить количество информации в сообщении, но не может его уменьшить:
.
Это неравенство можно переписать как или
.
Отношение характеризует среднее число знаков вторичного алфавита, которое приходится использовать для кодирования одного знака первичного алфавита.
Величину будем называть длиной кода или длиной кодовой цепочки:
.
Из предыдущего неравенства следует, что , поэтому:
. (7.1)
Обычно на практике процедуру кодирования реализуют таким образом, что выполняется условие
,
поэтому , то есть один знак первичного алфавита представляется несколькими знаками вторичного алфавита.
Способов построения кодов при фиксированных алфавитах и существует множество. Поэтому возникает проблема выбора (или построения) наилучшего варианта кода – будем называть его оптимальным кодом.
Выгодность применения оптимального кода при передаче и хранении информации – это экономический фактор, так как более эффективный код может позволить затратить на передачу сообщения меньше энергии и времени. В случае применения оптимального кода при передаче информации может меньшее время заниматься линия связи. Применение оптимального кода при хранении информации может позволить использовать меньше площади поверхности (объема) носителя информации.
При этом следует осознавать, что выгодность кода не всегда идентична временной выгодности всего процесса «кодирование–передача– декодирование». Возможна ситуация, когда за использование эффективного кода при передаче информации придется расплачиваться тем, что операции кодирования и декодирования будут занимать больше времени и/или иных ресурсов (памяти технического устройства, если эти операции производятся с его помощью).
Как следует из условия (7.1), минимально возможное значение средней длины кода равно:
. (7.2)
Данное выражение следует воспринимать как соотношение оценочного характера, устанавливающее нижний предел длины кода. Однако, из (7.2) неясно, в какой степени в реальных схемах кодирования возможно приближение величины к значению .
По этой причине для теории кодирования и теории связи важное значение имеют теоремы, доказанные Шенноном. Первая теорема Шеннона затрагивает ситуацию с кодированием при отсутствии помех, искажающих сообщение. Вторая теорема Шеннона относится к реальным линиям связи с помехами и будет обсуждаться нами позже.
Первая теорема Шеннона, или основная теорема о кодировании при отсутствии помех, формулируется так:
При отсутствии помех всегда возможен такой вариант кодирования, при котором среднее число знаков кода, приходящихся на один знак первичного алфавита, будет сколь угодно близко к отношению средних информаций на знак первичного и вторичного алфавитов.
Данная теорема утверждает принципиальную возможность оптимального кодирования, то есть построения кода со средней длиной, имеющей значение .
Однако необходимо сознавать, что из самой этой теоремы никоим образом не следует, как такое кодирование осуществить практически. Для разработки практической реализации оптимального кодирования должны привлекаться дополнительные соображения, которые мы обсудим далее.
Из (7.2) видно, что имеются два пути сокращения величины :
К. Шеннон подробно рассмотрел следующую частную ситуацию. В этой ситуации при кодировании сообщения учитывается различная вероятность появления знаков в первичном алфавите, то есть величина информации, приходящейся на знак первичного алфавита, рассчитывается в первом приближении: . Однако корреляции знаков первичного алфавита не учитываются. Источники подобных сообщений называются источниками без памяти (на корреляции знаков первичного – своего – алфавита). Если при этом обеспечена равная вероятность появления знаков вторичного алфавита, то, как следует из (7.2), для минимальной средней длины кода оказывается справедливым соотношение:
. (7.3)
В качестве меры превышения над можно ввести относительную избыточность кода :
.
С учетом (7.2) последнюю формулу можно переписать в виде
, (7.4)
причем .
Величина показывает, как сильно операция кодирования увеличила длину исходного сообщения. Очевидно, что при .
Таким образом, решение проблемы оптимизации кодирования состоит в нахождении таких схем кодирования, которые обеспечили бы приближение средней длины кода к значению , а относительной избыточности кода – к нулю. Чем меньше значение , тем возникает меньше избыточной информации, то есть информации, связанной с кодированием; более выгодным оказывается код и более эффективной становится операция кодирования.
Используя понятие избыточности кода, можно построить иную формулировку первой теоремы Шеннона:
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором избыточность кода будет сколь угодно близкой к нулю.
Наиболее важной для практики оказывается ситуация, когда во вторичном алфавите , то есть когда для представления кодов в линии связи используется лишь два типа сигналов. Такое кодирование называется двоичным кодированием. Технически это наиболее просто реализуемый вариант. Например, существование напряжения в проводе (импульс) или его отсутствие (пауза); наличие или отсутствие отверстия на перфокарте; наличие или отсутствие намагниченной области на дискете и так далее
Знаки двоичного алфавита принято обозначать «0» и «1», эти знаки нужно воспринимать как буквы. Удобство двоичных кодов также и в том, что при равных длительностях и вероятностях каждый элементарный сигнал (0 или 1) несет в себе ровно 1 бит информации ().
В случае двоичного вторичного алфавита (обозначим ) из формулы (7.3) получаем:
,
и первая теорема Шеннона получает еще одну (третью) формулировку:
При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.
Таким образом, при кодировании сообщений источника без памяти двоичными знаками равной вероятности по формуле (7.4) находим:
. (7.5)
При декодировании двоичных сообщений возникает проблема выделения из потока сигналов (последовательности импульсов и пауз) кодовых слов (групп элементарных сигналов), соответствующих отдельным знакам первичного алфавита. При этом приемное устройство фиксирует интенсивность и длительность сигналов, а также может соотносить последовательность поступающих сигналов с эталонными последовательностями (с таблицей кодов).
Отметим следующие особенности двоичного вторичного алфавита, используемого при кодировании:
Комбинации перечисленных особенностей вторичного алфавита определяют основу конкретного способа кодирования сообщений. Однако, даже при одинаковой основе возможны различные варианты построения кодов, которые будут отличаться своей эффективностью.
1. Постановка задачи оптимизации неравномерного кодирования
При двоичном кодировании знаки первичного алфавита (например, русского) кодируются комбинациями символов двоичного алфавита (то есть «0» и «1»). В случае неравномерности кодирования длины кодов (комбинаций символов вторичного алфавита, представляющих буквы первичного алфавита) могут различаться. Соответственно, длительности передачи отдельных кодов тоже могут различаться. Длительности элементарных сигналов (например, импульсов и пауз) при этом одинаковы (). Очевидно, что для передачи информации, в среднем приходящейся на один знак первичного алфавита, необходимо время . Таким образом, задачу оптимизации неравномерного кодирования можно сформулировать следующим образом:
Необходимо построить такую схему кодирования, в которой суммарная длительность кодов при передаче (или суммарное число кодов при хранении) данного сообщения была бы наименьшей.
За счет чего возможна такая оптимизация? Очевидно, что суммарная длительность сообщения будет меньше, если применить следующий подход:
Тем знакам первичного алфавита, которые встречаются в сообщении чаще, присвоить меньшие по длине коды, а тем знакам первичного алфавита, частота которых меньше – присвоить коды более длинные.
Другими словами, коды знаков первичного алфавита, вероятность которых в сообщении выше, следует строить из возможно меньшего числа элементарных сигналов, а длинные коды использовать для знаков первичного алфавита с малыми вероятностями.
Параллельно должна решаться проблема различимости кодов.
Допустим, что на выходе кодера (кодирующего устройства) получена, например, следующая последовательность элементарных сигналов:
00100010000111010101110000110
Каким образом такая последовательность элементарных сигналов может быть декодирована?
Если бы код был равномерным, приемное устройство (декодер) просто отсчитывало бы заданное (фиксированное) число элементарных сигналов и интерпретировало их в соответствии с кодовой таблицей.
При использовании неравномерного кодирования возможны два подхода к обеспечению различимости кодов.
Первый подход состоит в использовании специальной комбинации элементарных сигналов, которая интерпретируется декодером как разделитель знаков.
Второй подход состоит в применении префиксных кодов.
Ниже рассмотрим подробнее каждый из подходов.
2. Неравномерный код с разделителем
Условимся, что разделителем отдельных кодов букв первичного алфавита будет последовательность 00 (признак конца знака), а разделителем слов будет последовательность 000 (признак конца слова, он же – пробел). Таким образом, возможными оказываются, например, следующие правила построения кодов:
В соответствии с перечисленными выше правилами построим кодовую таблицу для букв русского алфавита, основываясь на данных о вероятностях появления отдельных букв (табл. 5). Таким образом, буквы с наибольшими частотами появления расположим в таблице выше. Каждой букве с номером будет соответствовать символов вторичного (двоичного) алфавита.
Формула, по которой можно найти среднюю длину кода для русских букв при данном способе кодирования, имеет вид:
.
Для русского языка, как указывалось раньше, . Поэтому избыточность рассмотренного выше кода составляет:
.
Это означает, что при данном способе кодирования будет передаваться в виде кодов приблизительно на 14 больше информации, чем содержит исходное сообщение.
Аналогичные вычисления для английского языка дают для средней длины кода для буквы первичного алфавита значение , что при приводит к избыточности кода в размере .
Табл. 5. Кодовая таблица для букв русского алфавита
|
Буква |
Код |
Буква |
Код |
||||
|
Пробел |
000 |
174 |
3 |
Я |
1011000 |
18 |
7 |
|
О |
100 |
90 |
3 |
Ы |
1011100 |
16 |
7 |
|
Е |
1000 |
72 |
4 |
З |
1101000 |
16 |
7 |
|
А |
1100 |
62 |
4 |
Ь, Ъ |
1101100 |
14 |
7 |
|
И |
10000 |
62 |
5 |
Б |
1110000 |
14 |
7 |
|
Т |
10100 |
53 |
5 |
Г |
1110100 |
13 |
7 |
|
Н |
11000 |
53 |
5 |
Ч |
1111000 |
12 |
7 |
|
С |
11100 |
45 |
5 |
Й |
1111100 |
10 |
7 |
|
Р |
101000 |
40 |
6 |
Х |
11010100 |
9 |
8 |
|
В |
101100 |
38 |
6 |
Ж |
10101100 |
7 |
8 |
|
Л |
110000 |
35 |
6 |
Ю |
10110000 |
6 |
8 |
|
К |
110100 |
28 |
6 |
Ш |
10110100 |
6 |
8 |
|
М |
111000 |
26 |
6 |
Ц |
10111000 |
4 |
8 |
|
Д |
111100 |
25 |
6 |
Щ |
10111100 |
3 |
8 |
|
П |
1010000 |
23 |
7 |
Э |
11010000 |
3 |
8 |
|
У |
1010100 |
21 |
7 |
Ф |
11010100 |
2 |
8 |
3. Коды без разделителя. Условие Фано
Рассмотрев один из вариантов двоичного неравномерного кодирования, попробуем найти ответ на следующий вопрос: возможно ли такое кодирование без использования разделительных знаков?
Суть этой проблемы состоит в нахождении такого варианта кодирования сообщения, при котором последующее выделение из сообщения каждого отдельного знака (то есть декодирование) оказывается однозначным без специальных указателей разделения знаков.
Наиболее простыми и употребимыми кодами без разделителя являются так называемые префиксные коды, которые удовлетворяют следующему условию – условию Фано: Сообщение, закодированное с использованием неравномерного кода может быть однозначно декодировано, если никакой из кодов в данном сообщении не совпадает с префиксом* (началом) какого-либо иного более длинного кода.
Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр.
Если условие Фано выполняется, то при прочтении (декодировании, расшифровке) закодированного сообщения путем сопоставления с таблицей кодов всегда можно точно указать, где заканчивается один код и начинается другой.
Пример 1. Являются ли коды, представленные в табл. 4, префиксными? Коды, представленные в табл. 4, не являются префиксными. См., например, коды букв «О» и «Е», «А» и «Н», «С» и «М», «Д» и «Ч».
Пример 2. Имеется таблица префиксных кодов (табл. 6). Требуется декодировать следующее сообщение, закодированное с использованием этой приведенной кодовой таблицы:
00100010000111010101110000110
Табл. 6. Таблица префиксных кодов
|
А |
Л |
М |
Р |
У |
Ы |
|
10 |
010 |
00 |
11 |
0110 |
0111 |
Декодирование производится циклическим повторением следующих действий:
Применение данного алгоритма к предложенному выше закодированному сообщению дает:
00100010000111010101110000110
|
00 |
10 |
00 |
10 |
00 |
0111 |
010 |
10 |
11 |
10 |
00 |
0110 |
|
м |
а |
м |
а |
м |
ы |
л |
а |
р |
а |
м |
у |
Таким образом, доведя процедуру декодирования до конца, можно получить сообщение: «мама мыла раму».
Таким образом, использование префиксного кодирования позволяет делать сообщение более коротким, поскольку нет необходимости передавать разделители знаков.
Однако условие Фано не устанавливает конкретного способа формирования префиксного кода, оставляя поле для деятельности по разработке наилучшего из возможных префиксных кодов.
4. Префиксный код Шеннона–Фано
Рассмотрим вариант кодирования, который был предложен в 1948 – 1949 гг. независимо К. Шенноном и Р. Фано.
Рассмотрим схему кодирования (как она строится) Шеннона–Фано на следующем примере.
Пусть имеется первичный алфавит , состоящий из шести знаков: , где . Пусть вероятности появления этих знаков в сообщениях таковы: , , , , и . Расположим эти знаки в таблице в порядке убывания вероятностей.
Разделим знаки на две группы так, чтобы суммы вероятностей в каждой из этих двух групп были бы приблизительно равными. При этом в 1-ю группу попадут и , а остальные – во 2-ю группу. Знакам первой группы присвоим первый слева разряд их кодов «0», а первым слева разрядом кодов символов второй группы пусть будет «1».
Продолжим деление каждой из получающихся групп на подгруппы по той же схеме, то есть так, чтобы суммы вероятностей на каждом шаге в обеих подгруппах делимой группы были бы возможно более близкими. Таким образом будем получать по одному следующие разряды кодов символов . Эти следующие разряды будем приписывать справа к уже имеющимся.
Вся эта процедура может быть схематически изображена в табл 7.
Табл. 7. Построение кода Шеннона-Фано
|
Знак |
Разряды кода |
Код |
||||
|
1-й |
2-й |
3-й |
4-й |
|||
|
0.30 |
0 |
0 |
00 |
|||
|
0.20 |
0 |
1 |
01 |
|||
|
0.20 |
1 |
0 |
10 |
|||
|
0.15 |
1 |
1 |
0 |
110 |
||
|
0.10 |
1 |
1 |
1 |
0 |
1110 |
|
|
0.05 |
1 |
1 |
1 |
1 |
1111 |
Видно, что построенные коды знаков удовлетворяют условию Фано, следовательно, такое кодирование является префиксным.
Найдем среднюю длину полученного кода по формуле
,
где – число разрядов (символов) в коде, соответсвующем символу .
Из таблицы видно, что , , .
Таким образом, получаем:
.
Таким образом, для кодирования одного символа первичного алфавита потребовалось в среднем 2.45 символов вторичного (двоичного) алфавита.
Определим среднее количество информации, приходящееся на знак первичного алфавита в первом приближении (с учетом различной вероятности появления этих знаков в сообщениях). Применим формулу Шеннона:
.
Найдем избыточность полученного двоичного кода:
,
то есть избыточность – около 2.5.
Выясним, является ли полученный код оптимальным. Нулей в полученных кодах – 6 штук, а единиц – 11 штук. Таким образом, вероятности появления 0 и 1 далеко не одинаковы. Следовательно, полученный код нельзя считать оптимальным.
5. Префиксный код Хаффмана
Способ оптимального префиксного двоичного кодирования был предложен Д. Хаффманом. Схему построения кодов Хаффмана мы рассмотрим на том же примере, на котором рассматривали построение кодов Шеннона–Фано.
Пусть имеется первичный алфавит , состоящий из шести знаков: , где . Пусть вероятности появления этих знаков в сообщениях таковы: , , , , и . Расположим эти знаки в таблице в порядке убывания вероятностей.
Создадим новый вспомогательный алфавит , объединив два знака с наименьшими вероятностями и заменив их одним (новым) знаком. Вероятность этого нового знака будет равна сумме вероятностей тех исходных знаков, которые в него вошли. Остальные знаки исходного алфавита включим в новый вспомогательный алфавит без изменений. Расположим знаки полученного алфавита для удобства в порядке убывания. В алфавите на 1 знак меньше, чем в исходном алфавите .
Продолжим таким же образом создавать новые алфавиты до тех пор, пока в последнем полученном вспомогательном алфавите не останется два знака. В нашем случае получается 4 (четыре) вспомогательных алфавита: , , и . Результат действий по созданию вспомогательных алфавитов можно представить в виде табл. 8:
Табл. 8. Вспомогательные алфавиты
|
, |
, |
, , |
, , , |
|
|
, |
, , |
, |
, , |
|
|
, |
, |
, , |
||
|
, |
, |
|||
|
, |
||||
Для удобства можно было работать только с таблицей вероятностей, не обращая внимание на содержание алфавитов (табл. 9):
Табл. 9. Таблица вероятностей
Последовательность предпринятых действий по объединению и упорядочиванию знаков для формирования вспомогательных алфавитов можно показать стрелками (табл. 10).
Табл. 10. Последовательность действий при формировании вспомогательных алфавитов
Теперь эту таблицу продублируем, однако, для простоты (чтобы освободить место для письма) не будем переписывать вероятности, подразумевая, что они остаются на своих местах – в своих клетках. Вместо вероятностей будем писать коды. Приписывать очередной разряд будем справа, как и в случае кодов Шеннона–Фано.
Последовательность действий (в направлении, обратном направлению стрелок) выглядит следующим образом.
Символам алфавита присвоим сверху вниз 0 и 1, то есть символы и из алфавита получат коды «0» и «1» соответственно (табл. 11):
Табл 11. Построение кода Хаффмана
|
0 |
||||
|
1 |
||||
Символ (то есть символ из алфавита ) наследует по стрелке код «1». Коды для и строим следующим образом. Первый слева разряд их кода наследуется по стрелке от – то есть «0». Вторые слева их разряды будут «0» и «1» сверху вниз для и соответственно (табл. 12):
Табл 12. Построение кода Хаффмана (продолжение)
|
1 |
0 |
|||
|
00 |
1 |
|||
|
01 |
||||
Аналогично строятся коды и далее (табл. 13).
Табл 13. Построение кода Хаффмана (продолжение)
|
00 |
00 |
00 |
1 |
0 |
|
10 |
10 |
01 |
00 |
1 |
|
11 |
11 |
10 |
01 |
|
|
010 |
010 |
11 |
||
|
0110 |
011 |
|||
|
0111 |
Последовательность действий
Итак, полученные коды выглядят так (табл. 14):
Табл 14. Код Хаффмана
|
Знак |
Код |
|
|
0.30 |
00 |
|
|
0.20 |
10 |
|
|
0.20 |
11 |
|
|
0.15 |
010 |
|
|
0.10 |
0110 |
|
|
0.05 |
0111 |
Полученные коды удовлетворяют условию Фано, то есть являются префиксными и, следовательно, не требуют разделителя.
Найдем среднюю длину полученного кода:
.
Таким образом, для кодирования одного символа первичного алфавита потребовалось в среднем 2.45 символов вторичного (двоичного) алфавита, как и в случае кода Шеннона–Фано.
Избыточность полученного двоичного кода равна:
,
то есть избыточность также около 2.5.
Посмотрим, является ли этот код оптимальным. Нулей в полученных кодах – 8 штук, а единиц – 9 штук. Таким образом, вероятности появления 0 и 1 существенно сблизились (0.47 и 0.53 соответственно). Следовательно, полученный код оптимален.
Более высокая эффективность кодов Хаффмана по сравнению с кодами Шеннона–Фано становится очевидной, если сравнить избыточности этих кодов для какого-либо естественного языка. При кодировании русского алфавита кодами Хаффмана средняя длина кода оказывается равной , при этом избыточность кода равна , то есть не превышает 1, что заметно меньше избыточности кода Шеннона–Фано.
Код Хаффмана важен в теоретическом отношении, поскольку в теории информации доказано, что он является самым экономичным из всех возможных, то есть ни для какого метода алфавитного кодирования длина кода не может оказаться меньше, чем код Хаффмана.
Таким образом, можно заключить, что существует способ построения оптимального неравномерного алфавитного кода.
Код Хаффмана, кроме теоретического, имеет и практическое значение. Метод Хаффмана и его модификация – метод адаптивного кодирования (динамическое кодирование Хаффмана) – широко применяются в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах и факсах.
1. Равномерное алфавитное двоичное кодирование. Байтовый код
В случае равномерного алфавитного кодирования двоичный код первичного алфавита строится цепочками равной длины, то есть со всеми знаками первичного алфавита A связано одинаковое количество информации, равное . Формировать признак конца строки не требуется, приемное устройство просто отсчитывает оговоренное заранее количество элементарных сигналов и интерпретирует цепочку (устанавливает, какому знаку первичного алфавита она соответствует), соотнося ее с таблицей кодов. Длину кода (соответствующего одному символу первичного алфавита) задают, исходя из известной формулы .
При идентификации кодовой цепочки недопустимы сбои. Например, пропуск (непрочтение) одного элементарного сигнала приведет к сдвигу всей кодовой последовательности и неправильной ее интерпретации. Эта проблема решается путем синхронизации передачи данных или иными способами.
С другой стороны, применение равномерного кода оказывается одним из средств контроля правильности передачи данных. Дело в том, что факт поступления лишнего элементарного сигнала или, наоборот, поступление неполного кода сразу интерпретируется как ошибка.
Примером равномерного алфавитного кодирования является телеграфный код Бодо, пришедший на смену азбуке Морзе.
Код Бодо применим для кодирования сообщений, первичный алфавит которых содержит не более 32-х символов. Тогда , и выбирают , то есть каждый знак первичного алфавита содержит 5 бит информации и кодируется цепочкой из 5 двоичных знаков.
В русском алфавите 34 буквы (с пробелом), именно по этой причине пришлось «сжать» алфавит и объединить в один знак «е» и «ё», а также «ь» и «ъ». После такого сжатия как раз , однако, не остается свободных кодов для знаков препинания, поэтому в телеграммах знаки препинания отсутствуют или заменяются буквенными аббревиатурами. Это не является существенным ограничением, поскольку, как указывалось выше, избыточность языка позволяет легко восстановить информационное cодержание сообщения.
Условие , очевидно, выполняется для языков, основанных на латинском алфавите ().
Избыточность кода Бодо для русского языка , для английского – .
Другим важным для нас примером использования равномерного алфавитного кодирования является представление символьной (знаковой) информации в компьютере.
Чтобы задать (определить) необходимую длину кода (для каждого символа первичного алфавита), необходимо начать с установления количества знаков в этом самом первичном алфавите. Компьютерный алфавит должен включать в себя:
Таким образом, получаем, что общее число символов в первичном компьютерном алфавите штук.
Теперь можно оценить длину кодовой цепочки, представляющей каждый символ первичного компьютерного алфавита:
. Таким образом, .
Поскольку длина кода выражается целым числом, очевидно, необходимо и достаточно принять .
Именно такой способ кодирования принят в компьютерных системах: любому символу ставится в соответствие код из 8 двоичных разрядов (8 бит). Эта последовательность сохраняется и обрабатывается как единое целое, то есть отсутствует доступ к отдельному биту, а имеется доступ к этой последовательности 8 битов как к целому. По этой причине разрядность устройств компьютера, предназначенных для хранения или обработки информации, кратна 8.
Совокупность восьми связанных битов получила название байт.
Представление символов байтами называется байтовым кодированием.
Байт наряду с битом может использоваться как единица измерения количества информации в сообщении. Один байт соответствует количеству информации в одном знаке алфавита в предположении их равновероятного распределения. Этот сопособ измерения количества информации называется объемным. 1 байт принят в качестве единицы измерения количества информации в международной системе единиц СИ.
Наряду с байтом для измерения количества информации используются более крупные производные единицы – килобайт, мегабайт, гигабайт, терабайт:
1 Кбайт = 210 байт = 1024 байт;
1 Мбайт = 220 байт = 1024 Кбайт;
1 Гбайт = 230 байт = 1024 Мбайт;
1 Тбайт = 240 байт = 1024 Гбайт.
Использование 8-битных цепочек позволяет закодировать символов, что превышает оцененное выше значение числа компьютерных символов. Следовательно, использование байтового кодирования символов первичного (здесь – компьютерного) алфавита дает возможность употребить оставшуюся часть ( возможных символов) для представления дополнительных символов.
Пусть имеется некоторое сообщение (последовательность знаков). Оценка количества информации на знак первичного алфавита согласно вероятностному подходу (с помощью формулы Шеннона) дает , а объемная мера равна . Соотношение между этими величинами таково:
.
Это соотношение следует из формулы
.
2. Международные системы байтового кодирования текстовых данных. Универсальная система кодирования текстовых данных
Для успешной работы с информацией недостаточно только условиться о длине кода. Ясно, что способов кодирования, то есть вариантов сопоставления знакам первичного алфавита восьмибитных цепочек очень много. По этой причине для совместимости технических устройств и обеспечения возможности обмена информацией между многими потребителями требуется согласование кодов. Подобное согласование осуществляется в форме стандартизации кодовых таблиц.
Первым таким международным стандартом, который применялся на больших вычислительных машинах, был EBCDIC (Extended Binary Coded Decimal Interchange Code) – «расширенная двоичная кодировка десятичного кода обмена». Эта система кодирования исторически тяготеет к «большим» машинам.
В персональных компьютерах и телекоммуникационных системах применяется международный байтовый код ASCII (American Standard Code for Information Interchange) – «американский стандартный код обмена информацией», разработанный в 1963 году. В своей первоначальной версии это – система семибитного кодирования. Она ограничивалась одним естественным алфавитом (английским), цифрами и набором различных символов, включая «символы пишущей машинки» (привычные знаки препинания, знаки математических действий и др.). В следующей версии фирма IBM перешла на расширенную 8-битную кодировку.
В первой половине кодовой таблицы ASCII (номера кодов от 0 до 127) первый бит всех кодов 0. В эту часть кодовой таблицы ASCII входят коды прописных и строчных английских букв, цифры, знаки препинания и знаки математических операций, а также некоторые управляющие коды (номера этих кодов от 0 до 31), вырабатываемые при использовании клавиатуры.
В табл. 15 приведены некоторые ASCII-коды:
Табл. 15. Примеры ASCII-кодов
|
Знак, Клавиша |
Код двоичный |
Код десятичный |
Знак, клавиша |
Код двоичный |
Код десятичный |
|
A (лат) |
01000001 |
65 |
1 |
00110001 |
49 |
|
B (лат) |
01000010 |
66 |
9 |
00111001 |
57 |
|
Z |
01011010 |
90 |
[Esc] |
00011011 |
27 |
|
0 |
00110000 |
48 |
[Enter] |
00001101 |
13 |
Вторая часть кодовой таблицы ASCII – она считается расширением основной – охватывает коды в интервале от 128 до 255 (первый бит этих кодов 1). Вторая часть кодовой таблицы ASCII используется для представления символов национальных алфавитов (например, русского), а также символов псевдографики. С помощью символов псевдографики можно создавать таблицы, несложные схемы и др.
Для второй части кодовой таблицы ASCII также имеются стандарты, например, для символов русского языка. Для представления букв русского языка (кириллицы) в рамках кода ASCII было предложено несколько версий. Первоначально был разработан ГОСТ под названием КОИ-7 (код обмена информацией, семизначный), оказавшийся по ряду причин неудачным; ныне он практически не используется.
Как в основной части кодовой таблицы, так и в ее расширении коды букв и цифр соответствуют их лексикографическому порядку (то есть порядку следования в алфавите) – это обеспечивает возможность автоматизации обработки текстов и ускоряет ее.
Для кодирования символов русского языка также существует код Windows-1251. Эта кодировка была введена компанией Microsoft. Учитывая распространение операционных систем и других продуктов этой компании в России, она глубоко закрепилась и нашла широкое распространение. Эта кодировка используется на большинстве локальных компьютеров, работающих на платформе Windows.
Другая распространенная кодировка русских символов носит название КОИ-8 (код обмена информацией, восьмизначный). Сегодня кодировка КОИ-8 имеет широкое распространение в компьютерных сетях на территории России и в Российском секторе глобальной сети Internet.
Существует международный стандарт, в котором предусмотрена кодировка символов русского алфавита. Этот стандарт кодировки называется ISO (International Standard Organization – Международный институт стандартизации). На практике данная кодировка используется редко.
На компьютерах, работающих в операционных системах MS-DOS, могут действовать еще две кодировки (кодировка ГОСТ и кодировка ГОСТ-альтернативная). Первая из них считалась устаревшей даже в годы появления персональной вычислительной техники, но вторая используется и по сей день.
В настоящее время появился и находит все более широкое применение еще один международный стандарт кодировки – Unicode. Его особенность в том, что в нем использовано 16-битное кодирование, то есть для представления каждого символа отводится 2 байта. Такая длина кода обеспечивает включение в первичный (здесь – компьютерный) алфавит 65536 знаков. Это, в свою очередь, позволяет создать и использовать единую для всех распространенных алфавитов кодовую таблицу.
Переход на данную систему кодирования долгое время сдерживался из-за недостаточности ресурсов средств вычислительной техники (в системе кодирования Unicode все текстовые документы автоматически становятся вдвое длиннее). Во второй половине 90-х годов технические средства достигли необходимого уровня обеспеченности ресурсами, и сегодня мы наблюдаем перевод документов и программных средств на универсальную систему кодирования (Unicode).
3. Алфавитное кодирование с неравной длительностью элементарных сигналов. Код Морзе
В качестве примера использования данного варианта кодирования рассмотрим телеграфный код Морзе («азбука Морзе»). В нем каждой букве или цифре сопоставляется некоторая последовательность кратковременных импульсов – точек и тире, разделяемых паузами. Длительности импульсов и пауз различны: если продолжительность импульса, соответствующего точке, обозначить , то продолжительность импульса тире составляет . При этом длительность паузы между точкой и тире равна , а пауза между буквами в слове равна (длинная пауза). Пауза между словами (пробел) длится .
Итак, в коде Морзе имеется три вида элементарных сигналов разной длительности: короткий импульс, длинный импульс, длинная пауза. Таким образом, код Морзе является троичным.
Под знаками кода Морзе следует понимать следующее:
«» означает «короткий импульс + короткая пауза»;
«» означает «длинный импульс + короткая пауза»;
«0» означает длинную паузу – признак конца буквы;
«00» означает двойную длинную паузу – признак пробела.
Свой код Морзе разработал в 1838 году, то есть задолго до работ Шеннона, до исследования относительной частоты (вероятности) появления различных букв в текстах. Однако Морзе правильно выбрал принцип кодирования – буквы, которые встречаются чаще, должны иметь более короткие коды, чтобы сократить общее время передачи сообщения. Относительные частоты букв английского алфавита он оценил простым подсчетом литер в ячейках типографской наборной машины. Поэтому самая распространенная английская буква «E» получила код «точка».
При составлении кодов Морзе для букв русского алфавита учет относительной частоты букв не производился, что, естественно, повысило его избыточность.
В табл. 16 ниже представлен код Морзе для русского алфавита. Признак конца буквы («0») в кодах не отображается, но он учтен в величине длины кода буквы № i.
Табл. 16. Код Морзе для русского алфавита
|
Буква |
Код |
Буква |
Код |
||||
|
Пробел |
00 |
174 |
2 |
Я |
|
18 |
5 |
|
О |
|
90 |
4 |
Ы |
|
16 |
5 |
|
Е |
|
72 |
2 |
З |
|
16 |
4 |
|
А |
|
62 |
3 |
Ь, Ъ |
|
14 |
5 |
|
И |
|
62 |
3 |
Б |
|
14 |
5 |
|
Т |
|
53 |
2 |
Г |
|
13 |
4 |
|
Н |
|
53 |
3 |
Ч |
|
12 |
5 |
|
С |
|
45 |
4 |
Й |
|
10 |
5 |
|
Р |
|
40 |
4 |
Х |
|
9 |
5 |
|
В |
|
38 |
4 |
Ж |
|
7 |
5 |
|
Л |
|
35 |
5 |
Ю |
|
6 |
5 |
|
К |
|
28 |
4 |
Ш |
|
6 |
5 |
|
М |
|
26 |
2 |
Ц |
|
5 |
5 |
|
Д |
|
25 |
4 |
Щ |
|
4 |
5 |
|
П |
|
23 |
4 |
Э |
|
4 |
6 |
|
У |
|
21 |
4 |
Ф |
|
3 |
5 |
Среднее значение длины кода Морзе имеет значение
.
Полагая появлние знаков вторичного алфавита (элементарных сигналов кода Морзе) равновероятным, получаем, что средняя информация на знак троичного алфавита Морзе равна
.
Для русского алфавита в первом приближении (с учетом вероятностей появления русских букв в текстах) средняя информация на знак (на букву) русского алфавита равна .
Как известно, избыточность кода вычисляется по формуле
.
В нашем случае , – троичный алфавит Морзе, , .
Таким образом,
,
то есть избыточность кода Морзе для русского языка составляет приблизительно 22 .
Избыточность кода Морзе для английского языка около 19 .
Код Морзе имел в недалеком прошлом весьма широкое распространение в ситуациях, когда источником и приемником сигналов являлся человек, а не техническое устройство; при этом на первый план выдвигалась не экономичность кода, а удобство его восприятия человеком.
4. Блочное двоичное кодирование
Вернемся к проблеме оптимального кодирования.
Наилучший результат (наименьшая избыточность) был получен при кодировании по методу Хаффмана – для русского алфавита избыточность оказалась менее 1. При этом указывалось, что код Хаффмана улучшить невозможно. На первый взгляд это противоречит первой теореме Шеннона, утверждающей, что всегда можно предложить такой способ кодирования, при котором избыточность будет сколь угодно малой величиной. На самом деле это противоречие возникло из-за того, что до сих пор мы ограничивались алфавитным кодированием. При алфавитном кодировании передаваемое сообщение представляет собой последовательность кодов отдельных знаков первичного алфавита. Однако возможны варианты кодирования, при которых кодовая комбинация относится сразу к нескольким буквам первичного алфавита или даже к целому слову первичного языка, то есть к блоку. Кодирование блоков понижает избыточность кода. В этом легко убедиться на простом примере.
Пусть имеется словарь некоторого языка, содержащий слов (это, безусловно, более, чем солидный словарный запас!). Поставим в соответствие каждому слову равномерный двоичный код. Очевидно, длина кода может быть найдена из соотношения . Таким образом, для кодирования любого слова необходимо и достаточно двоичных разрядов (14 бит). Следовательно, каждое слово кодируется комбинацией из 14 нулей и единиц – получатся своего рода двоичные иероглифы. Например, пусть слову «Информатика» соответствует код 10101011100110, слову «наука» соответствует код 00000000000001, а слову «интересная» – код 00100000000010. Тогда кодовая последовательность
101010111001100010000000001000000000000001
будет означать «Информатика интересная наука».
Легко оценить, что при средней длине русского слова буквы (5.3 буквы + пробел между словами) средняя информация на знак первичного алфавита оказывается равной , что более чем в 2 раза меньше, чем 5 бит при равномерном алфавитном кодировании. Для английского языка такой метод кодирования дает на знак. Таким образом, кодирование слов оказывается более выгодным, чем алфавитное (кодирование отдельных букв).
Можно кодировать сочетания букв – блоки букв. В принципе, такие блоки можно считать словами равной длины, не имеющими, однако, смыслового содержания. Удлиняя блоки, теоретически можно добиться того, что средняя информация на знак кода будет сколь угодно приближаться к минимальному значению , а избыточность будет стремиться к нулю.
5. Кодирование графических данных
Если рассмотреть с помощью увеличительного стекла черно-белое графическое изображение, напечатанное в газете или книге, то можно увидеть, что оно состоит из мельчайших точек, образующих характерный узор, называемый растром.
Поскольку линейные координаты и индивидуальные свойства каждой точки (яркость) можно выразить с помощью целых чисел, то можно сказать, что растровое кодирование позволяет использовать двоичный код для представления графических данных.
Общепринятым на сегодняшний день считается представление черно-белых иллюстраций в виде комбинации точек с 256 градациями серого цвета, и, таким образом, для кодирования яркости любой точки обычно достаточно восьмиразрядного двоичного числа ().
Для кодирования цветных графических изображений применяется принцип декомпозиции произвольного цвета на основные составляющие. В качестве таких составляющих используют три основных цвета: красный (Red, R), зеленый (Green, G) и синий (Blue, B).
На практике приближенно считается (хотя теоретически это не совсем так), что любой цвет, видимый человеческим глазом, можно получить путем смешивания этих трех основных цветов. Такая система кодирования называется системой RGB по первым буквам названий этих основных цветов.
Для кодирования яркости каждой из трех (R, G, B) основных составляющих цвета используют 256 значений (восемь двоичных разрядов, один байт), как это принято для полутоновых черно-белых изображений. Поэтому для кодирования цвета одной точки необходимо затратить разряда. То есть нужный цвет получается путем смешивания трех основных цветов, каждый из которых имеет свою яркость, выражающуюся одним из 256 значений. При этом система кодирования обеспечивает однозначное кодирование (определение) различных цветов, что на самом деле близко к чувствительности человеческого глаза. Режим представления цветной графики с использованием 24 двоичных разрядов называется полноцветным (True Color). Обозначают 24 bpp (bits per pixel – битов на пиксел, или, что тоже самое, на точку).
Если уменьшить количество двоичных разрядов, используемых для кодирования цвета каждой точки, то можно сократить объем данных, но при этом диапазон кодируемых цветов заметно сокращается. Кодирование цветной графики 16-разрядными двоичными числами (16 bpp) называется режимом High Color. При этом возможно однозначно закодировать цветов.
При кодировании информации о цвете точки с помощью 8 бит данных можно передать только цветов.
6. Кодирование звуковой информации
Приемы и методы работы со звуковой информацией пришли в вычислительную технику наиболее поздно. К тому же, в отличие от числовых, текстовых и графических данных, у звукозаписей не было столь же длительной истории кодирования. В итоге методы кодирования звуковой информации двоичным кодом далеки от стандартизации. Множество отдельных компаний разработали свои корпоративные стандарты, но, если говорить обобщенно, то можно выделить два основных направления в кодировании звуковой информации.
Метод FM (Frequency Modulation) основан на том, что теоретически любой сложный звук можно представить в виде суммы простейших гармонических колебаний разных частот. Каждое из этих колебаний представляет собой синусоиду, следовательно, может быть описано числовыми параметрами, то есть кодом. В природе звуковые колебания имеют непрерывный спектр, то есть звуковые сигналы в природе являются аналоговыми. Разложение этих сигналов в гармонические ряды и представление в виде дискретных цифровых сигналов выполняют специальные устройства – аналого-цифровые преобразователи (АЦП). Обратное преобразование для воспроизведения звука, закодированного числовым кодом, выполняют цифро-аналоговые преобразователи (ЦАП). При таких преобразованиях неизбежны потери информации, связанные с методом кодирования, поэтому качество звукозаписи методом FM обычно получается не вполне удовлетворительным и соответствует качеству звучания простейших электромузыкальных инструментов. В то же время данный метод кодирования обеспечивает весьма компактный код, и поэтому он применялся еще в годы, когда ресурсы средств вычислительной техники были явно недостаточны.
Метод таблично-волнового (Wave-Table) синтеза лучше соответствует современному уровню развития техники. Если говорить упрощенно, то можно сказать, что в заранее подготовленных таблицах хранятся образцы звуков для множества различных музыкальных инструментов (и не только для них). Такие образцы звуков называют сэмплами. Числовые коды выражают тип инструмента, номер его модели, высоту тона, продолжительность и интенсивность звука, динамику его изменения, некоторые параметры среды, в которой происходит звучание, а также прочие параметры, характеризующие особенности звука. Поскольку в качестве образцов используются «реальные» звуки, то качество звука, полученного в результате таблично-волнового синтеза, получается очень высоким и приближается к качеству звучания реальных музыкальных инструментов.
Одним из основных направлений применения компьютеров были и остаются разнообразные вычисления. Обработка числовой информации ведется и при решении задач, на первый взгляд, не связанных с какими-то расчетами, например, при использовании компьютерной графики или звука. В связи с этим встает вопрос о выборе оптимального представления чисел в компьютере.
Безусловно, можно было бы использовать 8-битное (байтовое) кодирование отдельных цифр, а из них составлять числа. Однако такое кодирование не будет оптимальным, что легко увидеть из следующего простого примера. Пусть имеется двузначное число «13»; при 8-битном кодировании отдельных цифр в кодах ASCII его представление выглядит следующим образом: 00110001 00110011, то есть код имеет длину 16 бит; если же воспользоваться представлением числа 13 в двоичнной системе счисления, то получим 4-битную цепочку: 1101.
Важно, что представление чисел определяет не только способ записи данных (букв или чисел), но и допустимый набор операций над ними. В частности, буквы могут быть только помещены в некоторую последовательность (или исключены из нее) без изменения их самих. Над числами же возможны операции, изменяющие само число (например, извлечение корня или сложение с другим числом).
Представление чисел в компьютере имеет следующие особенности:
Следствия, к которым приводят эти особенности, и будут нами рассмотрены далее.
1. Системы счисления
Начнем с некоторых общих замечаний относительно понятия число.
Можно считать, что любое число имеет значение (содержание) и форму представления. Отметим, что это весьма напоминает порядок использования переменных в компьютерных программах – там переменные тоже имеют значение и имя.
Значение числа задает его отношение к значениям других чисел («больше», «меньше», «равно»). Следовательно, значения чисел определяют порядок записи чисел на числовой оси.
Форма представления определяет способ записи числа с помощью предназначенных для этого знаков. При этом значение числа является инвариантом, то есть не зависит от способа его представления. Число с одним и тем же значением может быть записано по-разному, то есть отсутствует взаимно однозначное соответствие между представлением числа и его значением. Способ представления числа определяется выбранной (используемой) системой счисления.
Система счисления – это правило записи чисел с помощью заданного набора специальных знаков – цифр.
Существуют различные системы, которые можно объединить в несколько групп:
Унарная – это система счисления, в которой для записи чисел используется только один знак – I («палочка»). Следующее число получается из предыдущего добавлением новой I; их количество (сумма) равно самому числу. Такая система применяется для начального обучения счету. Именно унарная система определяет значение целого числа количеством содержащихся в нем единиц. Для записи числа в унарной системе в дальнейшем будем использовать обозначение .
Из непозиционных систем счисления наиболее распространенная – римская система счисления. В ней базовые числа обозначены заглавными латинскими буквами:
1 – I, 5 – V, 10 – X, 50 – L, 100 – C, 500 – D, 1000 – M.
Все другие числа в римской системе строятся комбинацией базовых в соответствии со следующими правилами:
Например, запись XIX соответствует числу 19, MDXLIX – числу 1549.
Запись чисел в римской системе громоздка и неудобна, но еще более неудобным оказывается выполнение в ней даже самых простых арифметических операций. Отсутствие нуля и знаков для чисел больше M не позволяют римскими цифрами записать совершенно произвольное число. По этим причинам теперь римская система используется лишь для нумерации.
Общим для унарной и римской систем счисления является то, что значение числа в них определяется посредством операций сложения и вычитания базисных цифр, из которых составлено число. Такие системы относятся к аддитивным.
В настоящее время для представления чисел применяют, в основном, позиционные системы счисления.
Позиционными называются системы счисления, в которых значение каждой цифры в изображении числа определяется ее положением (позицией) в ряду других цифр.
Наиболее распространенной и привычной является десятичная система счисления, в которой для записи чисел используются 10 цифр:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Число представляет собой краткую запись многочлена, в который входят степени некоторого другого числа – основания системы счисления.
Пример. , здесь основанием является число «10».
Число K единиц какого-либо разряда, объединяемых в единицу более старшего разряда, называют основанием позиционной системы счисления, а сама система счисления называется K-ичной.
Числа можно записать как суммы степеней не только числа 10, но и любого другого числа, большего 1. Например, в Древнем Вавилоне использовалась система счисления с основанием 60. Деление часа на 60 минут, а минуты на 60 секунд заимствовано именно из этой системы счисления. А то, что человечество выбрало в качестве основания очень распространенной системы счисления число 10, вероятно, связано с тем, что природа наделила людей десятью пальцами.
Запись произвольного числа X в K-ичной позиционной системе счисления основывается на представлении этого числа в виде полинома:
, (10.1)
где каждый коэффициент может является одним из базисных чисел K-ичной системы и изображается цифрой. В качестве базисных чисел берутся последовательные целые числа от 0 до включительно.
Позиционное представление чисел является аддитивно-мультипликативным, поскольку значение числа определяется операциями сложения и умножения.
Главной особенностью позиционного представления является то, что в нем посредством конечного набора знаков (цифр, разделителя десятичных разрядов и обозначения знака числа) можно записать неограниченное количество различных чисел. В позиционных системах гораздо легче, чем в других, осуществляются операции умножения и деления. Именно эти обстоятельства обусловили доминирование позиционных систем при обработке чисел человеком и компьютером.
Арифметические действия над числами в любой позиционной системе счисления производятся по тем же правилам, что и в десятичной системе, так как все они основываются на правилах выполнения действий над соответствующими полиномами. При этом нужно только пользоваться теми таблицами сложения и умножения, которые имеют место при данном основании системы счисления.
Отметим, что во всех позиционных системах счисления с любым основанием K умножение на число вида (m – целое число) сводится просто к перенесению запятой у множимого числа на m разрядов вправо или влево (в зависимости от знака числа m), так же как и в десятичной системе счисления.
Для указания того, в какой системе счисления записано число, условимся при его изображении основание системы счисления указывать в виде нижнего индекса при нем, например, .
2. Десятичная система счисления
Десятичная позиционная система счисления основана на том, что десять единиц каждого разряда объединяются в одну единицу соседнего старшего разряда. Таким образом, каждый разряд имеет вес, равный степени 10. Например, в записи числа 343.32 цифра 3 повторена три раза, при этом самая левая цифра 3 означает количество сотен (ее вес равен 100); а самая правая цифра 3 означает количество десятых долей единицы (ее вес равен 0.1), так что последовательность цифр 343.32 представляет собой сокращенную запись следующего выражения:
.
Десятичная запись любого числа X в виде последовательности цифр
основана на представлении этого числа в виде полинома:
. (10.2)
3. Двоичная система счисления
В современной вычислительной технике, в устройствах автоматики и связи широко используется двоичная система счисления. Это – позиционная система счисления с наименьшим возможным основанием. В ней для представления (изображения) числа используются только две цифры: 0 и 1.
Приозвольное двоичное число X представляется в виде полинома:
. (10.3)
Примеры изображения десятичных чисел в двоичной системе:
|
. |
Таблица сложения чисел в двоичной системе имеет вид:
Таблица умножения чисел в двоичной системе имеет вид:
4. 8- и 16-ричная системы счисления
Неудобство использования двоичной системы счисления заключается в громоздкости записи чисел. Это неудобство не имеет существенного значения для ЭВМ. Однако, если возникает необходимость кодировать информацию «вручную», например, при составлении программы на машинном языке, то предпочтительнее оказывается пользоваться восьмеричной или шестнадцатеричной системой счисления.
В 8-ричной системе счисления базисными числами являются 0, 1, 2, 3, 4, 5, 6, 7 (всего 8 цифр). Запись любого числа в этой системе основывается на его разложении по степеням числа восемь с коэффициентами, являющимися указанными выше базисными числами (от 0 до 7).
Например, десятичное число 83.5 в 8-ричной системе будет изображаться в виде 123.4. Действительно, эта запись по определению означает представление числа в виде следующего полинома:
.
В 16-ричной системе счисления базисными являются числа от нуля до пятнадцати. Эта система отличается от рассмотренных ранее тем, что в ней общепринятых арабских цифр не хватает для обозначения всех базисных чисел, поэтому приходится вводить в употребление новые символы. Для обозначения первых десяти чисел от нуля до девяти используются арабские цифры, а для следующих целых чисел от десяти до пятнадцати используются буквенные обозначения:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f.
Обозначения a, b, c, d, e, f соответствуют десятичным числам 10, 11, 12, 13, 14, 15.
Например, десятичное число 175.5 в 16-ричной системе будет заисываться в виде af.8. Действительно:
.
5. Смешанные системы счисления
В ряде случаев числа, заданные в системе счисления с основанием P, приходится изображать с помощью цифр другой системы счисления с основанием Q, которое меньше P. Такая ситуация возникает, например, когда в ЭВМ, способной непосредственно воспринимать только двоичные числа, необходимо изобразить десятичные числа, с которыми мы привыкли работать. В этих случаях используются смешанные системы счисления, в которых каждый коэффициент P-ичного разложения числа записывается в Q-ичной системе. В такой системе P называется старшим основанием, Q – младшим основанием, а сама смешанная система называется (Q-P)-ичной.
Для того, чтобы запись числа в смешанной системе счисления была однозначной, для представления любой P-ичной цифры отводится одно и то же количество Q-ичных разрядов, достаточное для представления любого базисного числа P-ичной системы.
Пример. В смешанной двоично-десятичной системе счисления для изображения каждой десятичной цифры отводится четыре двоичных разряда. Например, десятичное число в двоично-десятичной системе запишется в виде 1001 0010 0101. Здесь последовательные четверки (тетрады) двоичных разрядов изображают цифры 9, 2, 5 записи числа X в десятичной системе. Следует отметить, что, хотя в двоично-десятичной записи и используются только цифры 0 и 1, эта запись отличается от двоичного изображения данного числа X. Приведенный выше двоичный код из 12 разрядов в двоичной системе счисления изображает десятичное число 2341, а не 925, то есть .
Условимся изображать принадлежность числа к (Q-P)-ичной системе счисления с помощью нижнего индекса (Q-P) при данном числе, например, .
Аналогично рассмотренной выше двоично-десятичной системе счисления можно использовать и другие смешанные системы счисления при различных значениях P и Q.
Допустим, имеется число (в общем случае вещественное, имеющее целую и дробную части), записанное в P-ичной системе:
.
Необходимо это число представить в (Q-P)-ичной системе (). Другими словами, каждый коэффициент (это числа существенно целые) нужно записать Q-ичной системе, то есть представить в виде
.
Для этого необходимо определить количество разрядов, то есть количество значащих цифр в Q-ичном представлении каждого числа . Для представления каждого выбирается одинаквое достаточное количество разрядов. Очевидно, это необходимое и достаточное количество разрядов определяется так:
. (10.4)
Разумеется, число в общем случае не всегда целое, поэтому должно быть целым превосходящим .
В общем случае запись какого либо числа X в (Q-P)-ичной системе не совпадает с изображением этого числа X в Q-ичной системе. Однако такое совпадение имеет место, когда , где - целое положительное число. В этом случае изображение числа X в P-ичной системе является просто сокращенной записью изображения этого же числа X в Q-ичной системе.
Рассмотренное выше свойство некоторых смешанных систем широко используется на практике для сокращенной записи чисел, заданных в системе счисления с небольшим основанием. Для этого в исходной записи числа разряды объединяются вправо и влево от точки в группы некоторой длины (добавляя в случае необходимости левее старшей или правее младшей значащих цифр соответствующее количество нулей), и каждая такая группа записывается одной цифрой другой системы (с большим основанием).
Например, пусть дано число .
Представим его в 4-ичной системе. Итак, . Таким образом, каждая цифра 4-ичного представления соответствует двум разрядам 2-ичного представления: 10 11 10. 102. При этом: ; ; ; . Таким, .
Представим это же число в 8-ричной системе: , то есть каждые три разряда исходного двоичного числа будут соответствовать одному разряду 8-ричного числа. Поэтому в исходном числе надо приписать два нуля справа (чтобы было как минимум 3 разряда после запятой): 101 110. 100. При этом: ; ; . Итак, получаем: .
Представим это же число в 16-ричной системе. , поэтому исходное число надо разбить на группы по четыре двоичных разряда. Для этого надо дописать три нуля справа от младшего разряда и два нуля слева от страшего разряда (чтобы количества разрядов как до, так и после запятой делились на четыре нацело): = 0010 1110. 10002. При этом ; ; . Таким образом, .
Подчеркнем, что значение целого числа, то есть общее количество входящих в него единиц, не зависит от способа представления этого числа и остается одинаковым во всех системах счисления. Различаются только формы представления одного и того же количественного содержания числа. Например, . Другими словами, размер стипендии не станет больше от того, что при ее начислении вместо десятичной будут использовать, например, двоичную систему счисления.
6. Понятие экономичности системы счисления
Число с K разрядами в P-ичной системе счисления, очевидно, будет иметь наибольшее значение в том случае, если все цифры числа окажутся максимальными, то есть равными . Тогда значение максимального числа в этой системе будет равно
. (10.5)
K цифр
Здесь была применена формула для суммы первых членов геометрической прогрессии :
, причем , .
Количество разрядов числа при переходе от одной системы счисления к другой в общем случае меняется. Если (где – не обязательно целое), то из (10.5) получаем и количества разрядов в представлениях числа X в системах P и Q будут различаться в раз. Логарифмируя по любому основанию обе части равенства , получаем:
. (10.6)
Для примера сравним количество цифр в числе и его представлении в двоичной системе счисления: , то есть двоичная запись требует семь цифр вместо двух в десятичной, . Действительно, , то есть на каждый из двух десятичных разрядов приходится разрядов двоичных, поэтому двухразрядное десятичное число будет представлено двоичным числом, содержащим разрядов, но количество разрядов – число целое, поэтому количество цифр надо округлить в большую сторону, то есть получаем семь.
Введем понятие экономичности представления числа в данной системе счисления.
Под экономичностью системы счисления будем понимать то количество чисел, которое можно записать в данной системе с помощью определенного количества цифр.
Речь в данном случае идет о максимально возможном количестве сочетаний цифр, которые интерпретируются как различные числа.
Поясним на примере. Пусть в распоряжении имеется 12 цифр, или 12 «ячеек», которые можно заполнить разными цифрами. Можно разбить эти 12 цифр на 6 групп по две цифры, и считать, что эти цифры – 0 и 1. Каждая группа соответствует одному разряду, т.е таким образом можно записать шестиразрядное двоичное число, а всего различных шестиразрядных двоичных чисел может быть (число различных сочетаний из двух разных по шесть).
Можно разбить заданное количество (то есть 12) цифр на 4 группы по 3 цифры и положить, что эти 3 цифры в каждой группе такие: 0, 1, 2, то есть представляют собой цифры 3-ичной системы счисления. Каждая группа из четырех соответствует одному разряду 3-ичного числа, а всего различных четырехразрядных 3-ичных чисел существует . Аналогично можно произвести другие разбиения; при этом число групп определит разрядность числа, а количество цифр в группе – основание системы счисления. Результаты различных разбиений этих 12 «ячеек»проиведены в табл. 17.
Из приведенных в таблице оценок видно, что наиболее экономичной оказывается троичная система счисления.
В 60-х годах 20-го века в нашей стране была построена вычислительная машина «Сетунь», которая работала в троичной системе счисления. Предпочтение все же отдается двоичной системе, так как по экономичности она оказывается второй после троичной, а технически она реализуется гораздо проще остальных.
Табл. 17. Количество чисел, представимых двенадцатью цифрами различных систем счисления
|
Основание системы счисления, P |
2 |
3 |
4 |
6 |
12 |
|
Разрядность числа, k |
6 |
4 |
3 |
2 |
1 |
|
Колич-во различных чисел, N |
1. Задача перевода числа из одной системы счисления в другую
При решении задач с помощью ЭВМ исходные данные обычно задаются в десятичной системе счисления; в этой же системе, как правило, нужно получить и окончательные результаты. Так как в современных ЭВМ данные кодируются в-основном в двоичных кодах, то часто возникает необходимость перевода чисел из десятичной в двоичную систему счисления и наоборот.
При рассмотрении правил перевода чисел из одной системы счисления в другую ограничимся системами счисления, у которых базисными числами являются последовательные целые числа от 0 до включительно (P – основание системы счисления).
Задача перевода числа из одной системы счисления в другую заключается в следующем. Пусть известна запись числа Z в системе счисления с основанием P:
,
где – цифры P-ичной системы (), n и m – положительные целые числа.
Требуется найти запись этого же числа Z в системе счисления с другим основанием Q:
,
где – искомые цифры Q-ичной системы (), l и k – положительные целые числа.
Ограничимся случаем положительного числа Z, так как перевод любого числа сводится к переводу его модуля и приписыванию числу нужного знака.
При рассмотрении правил перевода нужно учитывать, по правилам какой арифметики (P-ичной или Q-ичной) должен быть осуществлен перевод, то есть в какой системе должны быть выполнены необходимые для перевода действия.
Полагая, что нам наиболее удобно проводить вычисления с P-ичными числами, условимся считать, что перевод должен осуществляться средствами P-ичной арифметики (например, чаще всего, десятичной).
2. Перевод Q P целых чисел
Решение задачи перевода произвольного числа Z, заданного в системе счисления с основанием Q, в систему счисления с основанием P сводится к вычислению полинома вида
. (11.1)
Для получения P-ичного изображения выражения (1) необходимо все цифры и число представить в P-ичном виде и выполнить арифметические действия в P-ичной системе счисления.
Пример. Перевести число в десятичную систему счисления.
Для перевода запишем число Z в виде и выполним все необходимые действия в десятичной системе:
.
Пример. Перевести число в десятичную систему счисления.
Для перевода запишем число Z в виде . Числа и в десятичном виде запишутся как 10 и 15. Таким образом, воспользуемся десятичной арифметикой: .
3. Перевод P Q целых чисел
Пусть известна запись целого числа N в P-ичной системе счисления:
,
то есть
. (11.2)
Требуется перевести это число N в систему счисления с основанием Q, то есть представить в виде
,
где – искомые цифры Q-ичной системы ().
Таким образом,
. (11.3)
Сначала определим коэффициент .
Разделим обе части равенства (3) на число Q, причем в левой части при делении воспользуемся P-ичной арифметикой, т.к. число N нам уже дано в P-ичном виде:
. (11.4)
Так как , то величина
(11.5)
есть дробная часть числа , а величина
(11.6)
есть целая часть числа . Таким образом, из (5) получаем:
. (11.7)
Теперь определим коэффициент .
Разделим (6) на Q:
, (11.8)
причем P-ичное число делим на Q по правилам P-ичной арифметики.
Аналогично изложенному выше имеем:
, (11.9)
. (11.10)
Таким образом, обозначив , можно записать рекуррентные формулы для определения коэффициентов :
, (11.11)
, (11.12)
где .
Фактически, – это остаток от целочисленного деления на в результате использования P-ичной арифметики.
Этот процесс, описываемый формулами (11.11), (11.12), должен продолжаться до тех пор, пока не будет получено .
Подчеркнем, что все операции здесь выполняются в P-ичной системе счисления, поэтому все коэффициенты также будут получены в этой же P-ичной системе. Поэтому по окончании процесса (11.11), (11.12) надо все коэффициенты записать в Q-ичном виде.
Пример. Перевести число в двоичную систему счисления.
;
;
;
;
;
;
Итак, .
Пример. Перевести число в 16-ричную систему счисления.
Для удобства величины будем записывать в скобках после результата целочисленного деления числа на .
Из формул (11.11), (11.12), при получаем:
;
;
.
Таким образом, ; ; . В результате получаем .
4. Перевод P Q дробных чисел
Пусть необходимо перевести в Q-ичную систему счисления дробь X, заданную в P-ичной системе счисления. Так как , то число X в Q-ичной системе можно представить в виде полинома:
, (11.13)
где – искомые коэффициенты Q-ичного разложения числа X.
Определим коэффициент .
Умножим равенство (11.13) по правилам P-ичной арифметики на Q:
. (11.14)
Так как , то в (11.14) можно выделить целую и дробную части:
;
.
Теперь определим коэффициент .
. (11.15)
Умножим обе части (11.15) на Q:
. (11.16)
Теперь в (11.16) выделим целую и дробную части:
;
,
и так далее.
Таким образом, «просматривается» процедура нахождения коэффициентов с помощью следующих рекуррентных формул:
; (11.17)
, (11.18)
где , а также принято .
Процесс нахождения коэффициентов с помощью формул (11.17), (11.18) прожолжается до тех пор, пока не достигается .
Пример. Перевести число в двоичную систему счисления.
Применение формул (11.17), (11.18) приводит к последовательности действий:
, поэтому ;
, поэтому ;
, поэтому ;
, поэтому ;
, поэтому ;
, поэтому ;
, поэтому ;
, поэтому ;
и так далее, то есть получаем бесконечную периодическую дробь.
Таким образом, в результате перевода точной десятичной дроби получаем бесконечную периодическую двоичную дробь:
, где в скобках указан период полученной дроби.
6. Перевод чисел между 2-ичной, 8-ричной и 16-ричной системами счисления
Интерес к двоичной системе счисления вызван тем, что именно эта система используется для представления чисел в компьютере. Однако двоичная запись оказывается громоздкой по сравнению с другими системами, и, кроме того, она плохо воспринимается и запоминается человеком из-за зрительной однородности (все числа состоят из нулей и единиц). Поэтому в нумерации ячеек памяти компьютера, в записи кодов команд, нумерации регистров и устройств и пр. используются системы счисления с основаниями 8 и 16. Выбор последних обусловлен тем, что переход от них к двоичной системе и обратно осуществляется, как будет показано ниже, весьма простым способом.
Напомним соответствие цифр различных систем счисления (табл. 18).
Табл. 18. Соответствие цифр различных систем счисления
|
Представление чисел в различных системах счисления |
|||
|
10-ная |
2-ичная |
8-ричная |
16-ричная |
|
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
|
2 |
10 |
2 |
2 |
|
3 |
11 |
3 |
3 |
|
4 |
100 |
4 |
4 |
|
5 |
101 |
5 |
5 |
|
6 |
110 |
6 |
6 |
|
7 |
111 |
7 |
7 |
|
8 |
1000 |
10 |
8 |
|
9 |
1001 |
11 |
9 |
|
10 |
1010 |
12 |
A |
|
11 |
1011 |
13 |
B |
|
12 |
1100 |
14 |
C |
|
13 |
1101 |
15 |
D |
|
14 |
1110 |
16 |
E |
|
15 |
1111 |
17 |
F |
Для перевода чисел между системами и надо пользоваться следующими правилами:
Правило 1
Для преобразования числа из системы Q в систему (l – целое положительное число) достаточно целую часть данного числа разбить на группы по l цифр справа налево от точки и дробную часть числа разбить на группы по l цифр слева направо от точки, дописывая при необходимости недостающее (до l) количество незначащих нулей в крайней слева и в крайней справа группах цифр. После этого каждую из полученных групп цифр независимо перевести в P-ичную систему счисления.
Пример. Перевести число в 8-ричную систему счисления.
, поэтому . Таким образом, .
Правило 2
Для преобразования числа из системы (l – целое положительное число) в систему Q достаточно каждую цифру числа представить в виде l-разрядного Q-ичного числа, дополняя его при необходимости незначащими нулями слева до группы в l цифр.
Пример. Перевести число в 2-ичную систему счисления.
, поэтому . Таким образом, каждую 16-ричную цифру числа надо представить в виде 4-разрядного 2-ичного числа: .
Переводы , очевидно, удобно осуществлять через промежуточный переход к двоичной системе счисления.
Пример. .
Докажем приведенные выше правила. Очевидно, что оба правила взаимно однозначны, обратимы. Поэтому достаточно доказать правило 2.
Рассмотрим P-ичное число, сокращенная запись которого имеет вид
. (11.19)
Это означает, что
.
(11.20)
Так как , то (11.20) перепишем так:
. (11.21)
Представим в Q-ичной системе каждый из коэффициентов :
, (11.22)
где .
Подставим (11.22) в (11.21):
(11.23)
или, после элементарных преобразований,
(11.24)
Каждая скобка в (11.23) соответствует P-ичной цифре из (11.19), причем каждая эта цифра представлена в Q-ичной системе в виде Q-ичного числа
,
содержащего l Q-ичных разрядов.
Всего в искомом Q-ичном представлении числа Z будет Q-ичных разрядов (цифр).
1. Нормализованные числа
Вещественное число X может быть представлено в двух формах – естественной и нормализованной.
В естественной форме в представлении числа X имеется целая и дробная части, между которыми помещается разделитель (запятая или точка), например, 123.4567. Такая форма записи называется «представление числа с фиксированной точкой (запятой)». Такая запись неудобна для очень больших или очень малых чисел. Кроме того, использование такой формы представления в компьютере вызывало бы снижение точности вычислений из-за необходимости приведения в соответствие разрядов обрабатываемых чисел и связанных с этим округлений. Также использование такой формы могло бы породить ситуацию, называемую переполнением, когда старший разряд числа не умещается в отведенной разрядной сетке. По указанным причинам вещественные числа в компьютере представляются в нормализованном виде (другое название – «представление числа с плавающей точкой (запятой)»). Главным достоинством представления числа в форме с плавающей точкой является автоматическое масштабирование числа на каждом этапе обработки. Это обеспечивает максимально возможную точность вычислений, а также избавляет от необходимости принимать специальные меры по предотвращению переполнения. Представление числа с плавающей точкой универсально для всех чисел, кроме чисел целого типа (то есть например, кроме типов Integer, Word, Byte).
Десятичное число называется нормализованным, если оно представлено в следующем виде:
. (12.1)
В этой записи величина называется мантиссой нормализованного десятичного числа; значения мантиссы лежат в интервале . Величина называется порядком нормализованного десятичного числа и является целым десятичным числом.
Примеры нормализованных десятичных чисел:
;
.
Понятие нормализованного числа следует отличать от понятия числа в нормальной форме. Последняя достаточно часто используется при записи чисел в физико-математических, технических дисциплинах и отличается от нормализованного представления тем, что мантисса лежит в интервале в интервале . Например, .
При нормализации происходт выделение «составляющих» числа: его знака, мантиссы, порядка и его знака. Это создает значительные удобства при хранении и обработке чисел в компьютере.
Аналогично нормализации десятичного числа можно в нормализованной форме представить и число в произвольной P-ичной системе счисления:
. (12.2)
При этом значения мантиссы лежат в интервале (первая значащая цифра мантиссы всегда ненулевая, как минимум, является единицей), а показатель степени представляется в системе .
Например, для :
,
причем в случае мантисса располагается в промежутке , что соответствует десятичному интервалу .
2. Преобразование числа из естественной формы в нормализованную
При нормализации различаются ситуации и .
При для нормализации необходимо перемещать разделитель разрядов (точку или запятую) влево по числу до тех пор, пока не исчезнет целая часть числа, но первая цифра после разделителя разрядов будет ненулевой. Каждое перемещение разделителя на 1 разряд влево эквивалентно делению числа на P, и, чтобы число не менялось, показатель степени (порядок числа) необходимо увеличивать на единицу при каждом сдвиге. Эта операция называется нормализацией влево и обозначается .
Пример. ; ;
(напомним, что ).
При для нормализации чисел используют операцию нормализации вправо (). Очевидно, числа, меньшие, чем , необходимо умножать на P с одновременным уменьшением показателя на единицу, пока первая цифра после разделителя не станет ненулевой.
Пример. ;
.
Подчеркнем, что порядок числа (показатель степени) должен записываться в той же системе счисления P, в которой записана мантисса нормализуемого числа . Также изменение значения при нормализации числа должно производиться по правилам той же самой P-ичной арифметики.
3. Преобразование нормализованных чисел
Подобно задаче о преобразовании целых и дробных чисел, можно поставить задачу о преобразовании P-ичного нормализованного числа в Q-ичное нормализованное число. Практическое значение такого преобразования состоит в том, что в компьютере все вещественные числа хранятся и обрабатываются в нормализованном двоичном представлении. Следовательно, при их вводе в компьютер осуществляется перевод , а при выводе – обратный перевод .
Пусть имеется число . Это число необходимо представить в форме . Очевидно, что преобразование не затронет знака мантиссы и знака порядка числа. Таким образом, для осуществления преобразования необходимо установить соответствие между и . Разумеется, что
. (12.3)
Для осуществления преобразования можно перейти к естественной форме числа в системе P, перевести число в систему Q, а затем нормализовать полученное Q-ичное число. Однако в таком варианте действий может теряться точность числа, а также возможно переполнение, если целая часть числа не уместится в отведенную разрядную сетку. Во избежание этого не надо переходить к естественной форме числа . Надо постепенно, шаг за шагом выделять в числе степени числа Q, пока число не примет вид , где . Это позволит избежать громоздких (многоразрядных) записей больших целых частей чисел. Затем числа и можно перевести в Q-ичную форму. Таким образом, процедура перевода выглядит так:
. (12.4)
Пример. Выполнить преобразование .
, где многоточие означает поэтапное выделение степеней двойки. Для порядка числа получаем: , а для мантиссы числа . Таким образом, окончательно получаем: .
Пример. Выполнить преобразование .
, где многоточие означает постепенное выделение степеней десятки.
4. Кодирование и обработка целых чисел без знака
Будем исходить из того, что для записи числа в устройствах компьютера выделяется фиксированное количество двоичных разрядов. Память компьютера имеет байтовую структуру, однако размер одной адресуемой ячейки памяти обычно составляет несколько байт. Например, в IBM-совместимых компьютерах ячейка памяти объединяет 2 байта, то есть 16 двоичных разрядов. Такая комбинация связанных соседних разрядов, обрабатываемых совместно, называется машинным словом. Для представления числа в арифметико-логическом устройстве процессора, где формируется результат операции, имеется еще один дополнительный одноразрядный регистр памяти – так называемый регистр переноса, который можно рассматривать как 17-й бит в результате операции.
Конечный размер разрядной сетки порождает понятие «наибольшее целое число», которого в обычном (немашинном) представлении чисел просто не существует. Если количество разрядов равно k, а основание системы счисления равно P, то из P различных цифр в сочетаниях по k цифр можно составить различных комбинаций, то есть различных чисел. Так как первое (наименьшее) целое положительное число есть нуль, то есть , то максимальное целое число без знака равно .
Пример. При (двоичная система) и получаем .
Целых чисел, удовлетворяющих условию в компьютере не существует, поэтому появление в ходе вычислений чисел, превышающих , должно интерпретироваться как ошибка. В языках программирования тип числа, в частности, задает количество отводимых для записи числа ячеек памяти (следовательно, задается разрядность числа). В языке PASCAL целые числа без знака, для которых отводится 2 байта (то есть 16 разрядов), определены как тип Word. Выход за границу возможен только путем увеличения количества разрядов, отводимых для записи числа, но это порождает новый тип со своим (более высоким) значением .
Рассмотрим, как с беззнаковыми числами выполняются арифметические операции в двоичной системе счисления.
Сложение производится согласно таблице сложения, которая имеет вид:
; ; ; .
Место в памяти, где сохраняется переносимая в старший разряд единица до того, как она будет использована в операции (то есть перенесена в старший разряд), называется битом переноса.
Пример. Найти сумму чисел и .
|
0010011010010100 0011000000111001 0 0101011011001101 |
Пример. Найти сумму чисел и .
|
1111111111111110 0000000000000011 1 0000000000000001 |
В последнем примере в результате сложения получилось число, превышающее на максимально возможное . Результат ошибочен, о чем свидетельствует появление единицы в регистре переполнения. Возникновение такой ситуации в ходе выполнения программы, написанной на языке, где предусмотрено строгое описание типа переменных, приводит к прекращению работы программы и выводу сообщения об ошибке. В программах, предназначенных для обработки числовой информации (например, Excel, MathCad), при переполнении разрядной сетки производится автоматическое преобразование целого числа в вещественный тип и число становится вещественным нормализованным. Таким образом, регистр переполнения служит индикатором корректности вычислений.
Умножение производится согласно таблице умножения:
; ; ; .
Последовательность действий при умножении аналогична используемой при работе в привычной десятичной системе счисления.
Пример. Найти произведение .
|
1101 101 1101 0000 1101 1000001 |
Как и в операции сложения, при умножении чисел с ограниченной разрядной сеткой может возникнуть переполнение. Решается эта проблема рассмотренными выше способами.
5. Кодирование и обработка целых чисел со знаком
Кодирование целых чисел, имеющих знак, можно осуществить двумя способами.
Первый способ называется прямым кодом. При этом один (старший) разряд в машинном слове (напомним, здесь машинное слово – 16 разрядов) отводится для записи знака числа; при этом условились кодировать знак «+» нулем, а знак «» единицей. Под запись самого числа, очевидно, остается 15 двоичных разрядов, что обеспечивает наибольшее значение числа . Однако прямое кодирование усложняет вычисления. Например, операция сложения двух чисел с разными знаками должна быть заменена операцией вычитания меньшего из большего с последующим присвоением результату знака большего по модулю числа. Таким образом, такая операция сопровождается рядом проверок условий и выработкой признаков, в соответствии с которыми выбирается то или иное действие.
Второй способ кодирования целых чисел со знаком называется дополнительным кодированием. Идея построения дополнительного кода такова: на оси целых чисел ( – всего 65536 чисел), помещающихся в машинное слово (в 16 разрядов) сместим положение нуля к середине интервала. При этом числа из первой половины () интервала будем считать положительными, а числа из второй половины () будем считать отрицательными. Судить о знаке числа можно по его величине, и в явном виде выделение знака не требуется.Оказывается, что принадлежность кода к интервалу кодов положительных или отрицательных чисел также видна по состоянию старшего бита – у кодов положительных чисел его значение «0», а у кодов отрицательных – «1». Это напоминает представление чисел с помощью прямого кода, но принцип построения дополнительного кода другой. Применение дополнительного кода позволяет заменить вычитание чисел их суммированием в дополнительном коде.
Рассмотрим вычитание числа , что эквивалентно прибавлению .
При наличии k разрядов можно закодировать чисел в P-ичной системе счисления. При этом максимальное k-разрядное P-ичное число есть , а число (оно содержит разрядов) можно считать нулем, так как первые слева (младшие) k разрядов (битов) в числе нулевые, а старший, единичный бит в нем уже не входит в отведенную разрядную сетку. Таким образом, можно записать:
. (12.5)
Однако вычесть из будет удобнее, если (12.5) преобразовать:
, (12.6)
причем число есть максимальное P-ичное k-разрядное число , каждая его цифра равна :
, (12.7)
, (12.8)
Цифры числа Z обозначим :
. (12.9)
Таким образом, с учетом (12.8) и (12.9), выражение (12.7) легко преобразуется:
. (12.10)
Величина (12.10) называется дополнением целого k-разрядного числа Z в системе счисления P.
Пример. ;
.
Важным свойством дополнения является то, что его сумма с исходным числом в заданной разрядной сетке равна нулю, то есть
. (12.11)
Пример. ;
.
В этом примере единица в скобках должна быть отброшена, так как она выходит за отведенную разрядную сетку.
Из (12.11) логично заключить, что
, (12.12)
значит, при имеем
. (12.13)
Поэтому дополнительный код (DС) двоичных чисел в компьютере надо строить согласно следующему правилу:
Пример. Построить дополнительный двоичный код числа .
;
Пример. Построить дополнительный двоичный код числа .
.
Кстати, используя результаты этих примеров, легко убедиться, что
.
Прямые и дополнительные коды целых чисел со знаком сопоставлены в табл. 19.
В компьютере используется интервал целых чисел со знаком, закодированных дополнительным двоичным кодом. Именно таким является диапазон значений чисел типа Integer в языке PASCAL.
В компьютере перевод в дополнительный код осуществляется автоматически при вводе чисел. Именно в таком виде числа хранятся в ОЗУ и участвуют в арифметических операциях.
Еще раз отметим, что операция вычитания как самостоятельная отсутствует; она заменяется сложением уменьшаемого (то есть его дополнительного кода) с дополнением вычитаемого, то есть имеет место сложение содержимого двух ячеек памяти.
О знаке результата судят по значению старшего (первого слева) бита, как и в прямом двоичном коде (см. таблицу): «0» соответствует знаку «+», «1» соответствует знаку «».
Если результат отрицательный, то прямой код модуля числа получают из дополнительного кода в обратном изложенному порядке: -я цифра числа равна разности значения P и -й цифры числа .
Табл. 19. Прямые и дополнительные коды целых чисел со знаком
|
Прямой десятичный код |
Прямой 16-разрядный двоичный код |
Дополнительный 16-разрядный двоичный код |
|
|
32 768 |
— |
1000 0000 0000 0000 |
Совпадает с дополнением модуля |
|
32 767 |
1111 1111 1111 1111 |
1000 0000 0000 0001 |
|
|
32 766 |
1111 1111 1111 1110 |
1000 0000 0000 0010 |
|
|
… |
… |
… |
|
|
3 |
1000 0000 0000 0011 |
1111 1111 1111 1101 |
|
|
2 |
1000 0000 0000 0010 |
1111 1111 1111 1110 |
|
|
1 |
1000 0000 0000 0001 |
1111 1111 1111 1111 |
|
|
0 |
0000 0000 0000 0000 |
0000 0000 0000 0000 |
Совпадает с прямым кодом |
|
+1 |
0000 0000 0000 0001 |
0000 0000 0000 0001 |
|
|
+2 |
0000 0000 0000 0010 |
0000 0000 0000 0010 |
|
|
+3 |
0000 0000 0000 0011 |
0000 0000 0000 0011 |
|
|
… |
… |
… |
|
|
+32 766 |
0111 1111 1111 1110 |
0111 1111 1111 1110 |
|
|
+32 767 |
0111 1111 1111 1111 |
0111 1111 1111 1111 |
6. Кодирование и обработка вещественных чисел
Как известно, в компьютере для записи числа отводится конечное число разрядов. Для целых чисел это обстоятельство привело к появлению понятия наибольшего целого числа . Каждому целому числу, не превышающему по модулю наибольшего, взаимно однозначно соответствует одно представление в машинном коде, и поэтому результат выполнения операции над целыми числами будет точным (если нет переполнения).
Ситуация радикальным образом меняется в случае представления и обработки вещественных чисел. На математической числовой оси вещественные числа образуют непрерывное множество (континуум), поэтому на любом (на сколь угодно малом) интервале вещественной оси содержится бесконечное количество значений. В машинном представлении количество возможных значений чисел конечно и составляет , где P – основание используемой в машине системы счисления, k – количество отведенных разрядов.
Вещественные числа в компьютере заменяются их кодами, которые образуют конечное дискретное множество; каждый код оказывается представителем интервала значений континуума .
Из данного обстоятельства вытекает ряд следствий:
если , то ;
если , то ;
если , то .
Основной формой представления кодов вещественных чисел в компьютере является двоичная нормализованная. При этом записываться и храниться в памяти компьютера должны все составляющие нормализованной формы числа: знак числа, мантисса, знак порядка числа, порядок, что, разумеется, требует нескольких ячеек памяти. Например, числа типа Real языка PASCAL размещаются в 6 байтах (3 ячейки по 16 бит), то есть каждое число занимает 48 двоичных разрядов. Непосредственное распределение компонентов нормализованного числа по разрядам определяется конструктивными особенностями компьютера и программным обеспечением. Ниже приведен пример размещения вещественного нормализованного числа в двух ячейках памяти (32 разряда) (рис. 3):
|
32 |
31 |
30 |
29 |
28 |
27 |
26 |
25 |
24 |
23 |
… |
2 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
… |
0 |
1 |
Рис. 3. Размещение вещественного нормализованного числа в ячейках памяти ЭВМ
Поскольку значение мантиссы лежит в интервале , то нуль из разряда целых и разделитель разрядов в представление не включаются, то есть представление мантиссы содержит только цифры дробной части. Более того, можно не сохранять первую значащую цифру двоичной мантиссы (старший разряд из дробной части), поскольку она всегда «1» (но, естественно, перед вычислениями она восстанавливается!). Это дает возможность хранить дополнительный разряд, то есть на один разряд повысить точность обработки.
В ходе выполнения арифметических операций производится нормализация промежуточных и конечного значений, состоящая в сдвиге разделителя разрядов вправо или влево с одновременным соответствующим изменением порядка числа. Именно поэтому такая форма представления чисел называется представлением «с плавающей точкой».
Как и в случае целых чисел, для кодов вещественных чисел существует понятие переполнения, однако возникает оно не после заполнения разрядной сетки (это предотвращается нормализацией числа), а после заполнения всех разрядов порядка. Изначальной причиной погрешности в обработке кодов вещественных чисел является ограниченность разрядной сетки. Величина погрешности зависит от количества имеющихся разрядов. Уменьшить погрешность можно за счет расширения разрядной сетки, то есть выделения большего количества ячеек памяти для записи числа. Например, в языке PASCAL определен вещественный тип Extended, числа которого занимают по 10 байт (80 бит). Наличие нескольких вариантов представления вещественных чисел в языках программирования (различные вещественные типы) позволяет оптимизировать программу. Повышение точности вычислений требует больших ресурсов памяти; при этом возрастает время вычислений.
1. Общая схема передачи информации в линии связи
Использование информации для решения каких-либо задач, безусловно, сопряжено с необходимостью ее распространения, то есть с необходимостью осуществления процессов передачи и приема информации. При этом приходится решать проблему согласования метода кодирования с характеристиками канала связи, а также обеспечивать защиту передаваемой информации от возможных искажений.
Источник информации определен как объект или субъект, порождающий информацию и имеющий возможность представить ее в виде сообщения, то есть последовательности сигналов в материальном носителе. Другими словами, источник информации связывает информацию с ее материальным носителем. Передача сообщения от источника к приемнику всегда связана с некоторым нестационарным процессом, происходящим в материальной среде – это условие является обязательным, поскольку сама информация материальным объектом не является.
Способов передачи информации существует множество: почта, телефон, радио, телевидение, компьютерные сети и пр. Однако при всем разноообразии конкретной реализации способов связи в них можно выделить общие элементы: источник и получатель информации, кодирующее и декодирующее устройства, преобразователь кодов в сигналы и преобразователь сигналов в коды, канал связи, а также источники шумов (помех) и факторы, обеспечивающие защиту от шумов (см. схему на рис. 4).
Понимать схему нужно следующим образом. Источник, порождающий информацию, для передачи должен представить ее виде сообщения, то есть последовательности сигналов. При этом для представления информации он дожен использовать некоторую систему кодирования. Устройство, выполняющее операцию кодирования информации, может являться подсистемой источника информации. Например, наш мозг порождает информацию и он же кодирует эту информацию с помощью языка (например, русского), а затем представляет информацию в виде речевого сообщения посредством органов речи. Компьютер обрабатывает и хранит информацию в двоичном представлении, но при выводе ее на экран монитора он же – компьютер – производит ее перекодировку пользователю виду.
Возможна ситуация, когда кодирующее устройство оказывается внешним по отношению к источнику информации, например, телеграфный аппарат или компьютер по отношению к человеку – работающему на нем оператору. Далее коды должны быть переведены в последовательность материальных сигналов, то есть помещены на материальный носитель – эту операцию выполняет преобразователь. Преобразователь может быть совмещен с кодирующим устройством (например, телеграфный аппарат), но может быть и самостоятельным элементом линиии связи (например, модем, преобразующий электрические дискретные сигналы с частотой компьютера в аналоговые сигналы с частотой, на которой их затухание в телефонных линиях будет наименьшим).
К преобразователям относят также устройства, которые переводят сообщение с одного носителя на другой. Например:
Рис. 4. Общая схема передачи информации
В общем случае при преобразовании выходные сигналы воспроизводят не полностью все особенности входного сообщения, а лишь его наиболее существенные стороны, то есть при преобразовании часть информации теряется. Например, полоса пропускания частот при телефонной связи находится в промежутке от 300 до 3400 Гц, в то время как частоты, воспринимаемые человеческим ухом, лежат в интервале от 16 до 20000 Гц.
Таким образом, телефонные линиии «обрезают» высокие частоты, что приводитк искажениям звука; в черно-белом телевидении при преобразовании сообщения в сигналы теряется цвет изображения. Именно в связи с этими проблемами возникает задача выработки такого способа кодирования сообщения, который обеспечивал бы возможно более полное представление исходной информации при преобразовании, и, в то же время, этот способ был бы согласован со скоростью передачи информации по данной линии связи.
После преобразователя сигналы поступают в канал связи и распространяются в нем. Понятие канала связи включает в себя материальную среду, а также физический или иной процесс, посредством которого осуществляется передача сообщения, то есть распространение сигналов в пространстве с течением времени.
В табл. 20 приведены примеры некоторых каналов связи.
Табл. 20. Примеры каналов связи
|
Канал связи |
Среда |
Носитель сообщения |
Процесс, используемый для передачи сообщения |
|
Почта |
Среда обитания человека |
Бумага |
Механическое перемещение носителя |
|
Телефон, компьютерные сети |
Проводник |
Электрические заряды |
Перемещение зарядов (ток) |
|
Радио, телевидение |
Электромагнитное поле |
Электромагнитные волны |
Распространение электромагнитных волн |
|
Зрение |
|||
|
Слух |
Воздух |
Звуковые волны |
Распространение звуковых волн |
|
Обоняние, вкус |
Воздух, пища |
Химические вещества |
Химические реакции |
|
Осязание |
Поверхность кожи |
Ввоздействующий на кожу объект |
Теплопередача, давление |
Любой реальный канал связи подвержен внешним воздействиям, а также в нем могут происходить внутренние процессы, в результате которых искажаются передаваемые сигналы, и, следовательно, связанные с этими сигналами сообщения. Такие воздействия называются шумами (помехами). Источники помех могут быть внешними и внутренними. К внешним помехам относятся, например, так называемые «наводки» от мощных потребителей электричества или атмосферных явлений; одновременное действие нескольких близкорасположенных однотипых источников сообщений (одновременный разговор нескольких человек). К помехам могут привоить и внутренние особенности данного канала связи, например, физические неоднородности носителя; процессы затухания сигнала в линии связи, существенные при большой удаленности приемника от источника.
Если уровень помех оказывается соизмеримым с мощностью несущего информацию сигнала, то передача информации по данному каналу оказывается невозможной. Даже шумы относительно низких уровней могут вызвать существенные искажения передаваемого сигнала.
Существуют и применяются различные методы защиты от помех. Например, используется экранирование элетрических линий связи; улучшение избирательности примного устройства и так далее Другим способом защиты от помех является использование специальных методов кодирования информации.
После прохождения сообщения по каналу связи сигналы с помощью приемного преобразователя переводятся в последовательность кодов, которые декодирующим устройством представляются в форме, необходимой для примника информации (в воспринимаемой приемником форме). На этапе приема, как и при передаче, преобразователь может быть совмещенным с декодирующим устройством (например, радиоприемник или телевизор) или существовать отдельно от декодирующего устройства (преобразователь модем может существует отдельно от компьютера).
Понятие «линия связи» объединяет элементы представленной на рис. 1 схемы между источником и приемником информации. Характеристиками любой линии связи являются скорость, с которой возможна передача сообщения в ней, а также степень искажения сообщения в процессе передачи.
Далее рассмотрим те параметры линии связи, которые относятся непосредственно к каналу связи, то есть характеризуют среду и процесс передачи.
2. Характеристики канала связи
Ограничим дальнейшее рассмотрение каналами связи, передача сообщений по которым осуществляется за счет электрических импульсов – с практической точки зрения (использование в компьютерных линиях связи) такие каналы связи представляют наибольший интерес.
Ширина полосы пропускания. Любой преобразователь, работа которого основана на использовании колебаний, может формировать и пропускать сигналы из ограниченной области частот. Весь доступный для использования частотный спектр разделен на диапазоны (ДВ, СВ, КВ1, КВ2, УКВ, ДМВ, МВ), в пределах которых каждая передающая станция занимает свой поддиапазон, чтобы не мешать вещанию других.
Интервал частот, используемый данным каналом связи для передачи сигналов, называется шириной полосы пропускания.
Для построения теории передачи информации важна не сама ширина полосы пропускания, а максимально возможное значение частоты из данной полосы, поскольку именно этим значением определяется возможная скорость передачи информации по каналу связи.
Длительность элементарного импульса. Длительность элементарного импульса может быть определена из следующих соображений. Если параметр сигнала меняется синусоидально, то за один период колебаний T сигнал будет иметь одно максимальное значение и одно минимальное. Аппроксимируем синусоиду прямоугольными импульсами (см. рис. 5) и за нулевой уровень сигнала примем минимальное значение сигнала. Получается, что сигнал (аппроксимированный) принимает всего два значения – максимальное (импульс) и минимальное (пауза).
Рис. 5. Аппроксимация периодического сигнала прямоугольными импульсами.
Импульс и паузу можно счистать элементарными сигналами; при выбранной здесь аппроксимации их длительности одинаковы:
. (13.1)
Таким образом, частота определяет минимальную длительность элементарного сигнала (импульса или паузы). Последовательность элементарных сигналов связывают с определенными кодами. Использовать сигналы большей, чем , длительности, в принципе, возможно, однако это снизит скорость передачи информации по каналу.
Пропускная способность канала. Если с передачей одного импульса, длящегося , связано количество информации , то отношение к , очевидно, отражает среднее количество информации, передаваемое по каналу за единицу времени. Эта величина называется пропускной способностью канала:
. (13.2)
Если выражено в битах, а – в секундах, то единицей измерения величины С является бит/с. Раньше эта единица называлась бод, однако это название не прижилось и более не используется. Производными единицами являются:
,
,
.
Величину можно установить из следующих соображений. Если на один знак первичного алфавита приходится количество информации , причем каждый знак этого первичного алфавита кодируется количеством K знаков вторичного алфавита (то есть длина кода, другими словами, суммарное количество импульсов и пауз, приходящееся на знак первичного алфавита, равно K), то, очевидно,
. (13.3)
Подстановка (13.3) в (13.2) дает:
. (13.4)
Величина определяется по формуле Шеннона:
, (13.5)
где – общее количество знаков в первичном алфавите, – вероятность появления -го знака первичного алфавита в сообщении.
Таким образом, окончательно получаем:
. (13.6)
Пример. Первичный алфавит состоит из трех знаков с вероятностями , , . Для передачи по каналу без помех используется равномерный двоичный код. Частота тактового генератора . Какова пропускная способность канала?
.
Величина K в случае двоичного кодирования (два вида знаков вторичного алфавита – импульсы и паузы) определяется так:
, поэтому , так как длина кода – число целое.
. Следовательно, из (13.6) получаем:
.
Скорость передачи информации. Пусть по каналу связи за время t передано количество информации I. Можно ввести величину скорости передачи информации J:
. (13.7)
Размерностью величины J, как и величины C, является бит/с. Каково соотношение этих характеристик? Так как – это минимальная длительность элементарного сигнала, то C – это максимальная скорость передачи информации по данной линии связи, то есть или .
Максимальная скорость передачи информации по каналу связи равна его пропускной способности.
3. Влияние шумов на пропускную способность канала
Отличичие реального канала связи от идеального в том, что в реальном канале присутствуют шумы, снижающие пропускную способность канала.
Рассмотрим типичную ситуацию использования элементарных сигналов двух типов (импульс и пауз) равной длительности. После прохождения сигнала по идеальному каналу на выходе импульс «1» интерпретируется именно как импульс, а пауза «0» – как пауза. Следовательно, связанная с этими сигналами информация не изменяется. Иная ситуация в реальном канале: из-за шумов при передаче может произойти искажение сигнала, в результате чего вместо 1 на выходе может быть получен 0, а вместо 0 может оказаться 1. Пусть вероятности таких искажений для 0 и 1 одинаковы и равны p. Тогда вероятность того, что исходный сигнал придет без искажений, очевидно, равна . Следовательно, при интерпретации (распознавании) конечного сигнала возникает неопределенность, которая может быть охарактеризована средней энтропией:
. (13.8)
Эта неопределенность приведет к уменьшению количества информации, содержащейся в сигнале, на величину H:
. (13.9)
Длительность импульса определяется частотой тактового генератора и, разумеется, не зависит от шумов в канале связи, поэтому из (13.2):
. (13.10)
Подставляя (13.8) в (13.10), получаем:
. (13.11)
Из (13.2) следует, что отношение пропускной способности канала с помехами к пропускной этого же канала без учета помех равно
. (13.12)
На рис. 6 показана зависимость в случае двоичного кода, когда с импульсом или паузой связано количество информации .
Рис. 6. Зависимость от p.
При получается . Это связано с тем, что в данном случае на приемном конце линии связи с одинаковой вероятностью появляются нули и единицы независимо от того, каков был сигнал на входе, так что передача по линии связи в таких условиях вообще невозможна.
Максимального значения пропускная способность достигает при , что соответствует отсутствию помех, а также при , то есть при таких помехах, которые каждый входной сигнал 1 переводят в 0 на выходе, а каждый входной 0 переводят в 1 на выходе. Ясно, что помехи такого рода не мешают распознаванию сигнала, который был на входе линии связи.
Таким образом, наличие помех (шумов) в канале связи приводит не только к искажению передаваемого сообщения и частичной утрате передаваемой информации, но и к уменьшению пропускной способности канала. Влияние шумов определяется соотношением мощности полезного (несущего информацию) сигнала и мощности помех.
Приведем в табл.21 характеристики некоторых каналов связи.
Табл. 21. Пропускные способности некоторых каналов связи
|
Вид связи |
, Гц |
, бит/с |
|
Телеграф |
120 |
640 |
|
Телефон |
||
|
Телевидение |
||
|
Слух человека |
Из сопоставления данных видно, что пропускная способность телефонного канала связи совпадает с пропускной способностью органов слуха чекловека. Однако она существенно выше скорости обработки информации мозгом человека, которая составляет не более 50 бит/с. Другими словами, в мозг может поступать избыточная информация.
1. Постановка задачи обеспечения надежности передачи
Все реальные каналы связи подвержены воздействию помех. Означает ли это, что надежная (то есть без потерь) передача по ним информации невозможна в принципе? К. Шеннон доказал теоретическую возможность передачи сообщения без потерь информации по реальным каналам, если обеспечить выполнение ряда условий. Задача была сформулирована в виде теоремы, которая затем получила строгое математическое доказательство. Ранее была представлена первая теорема Шеннона, касающаяся кодирования информации при передаче по идеальному каналу связи. Критерием оптимальности кодирования служила избыточность кода. Эту избыточность можно сделать сколь угодно малой (близкой к нулю), применяя блочное кодирование по методу Хаффмана.
Вторая теорема Шеннона касается реальных каналов связи и гласит:
При передаче информации по каналу с шумом всегда существует способ кодирования, при котором сообщение будет передаваться со сколь угодно высокой достоверностью, если скорость передачи не превышает пропускной способности канала.
Последняя часть определения, относится и к идеальному каналу – в любом случае, если скорость передачи превышает пропускную способность канала, происходит потеря информации. Смысл данной теоремы в том, что при передаче по реальным каналам можно закодировать сообщение таким образом, что действие шумов не приведет к потере информации. Это достигается за счет повышения избыточности кода, то есть за счет увеличения длины кодовой цепочки. Безусловно, при этом возрастает время передачи, что следует считать платой за надежность. При этом в теореме и в ее доказательстве не указывается, каким образом следует осуществлять такое кодирование. Вторая теорема Шеннона лишь утверждает, что существует принципиальная возможность такого кодирования, причем поиск необходимого кода – это отдельная задача.
Для примера оценим, какова вероятность возникновения ошибки, но не при передаче, а при хранении информации (что не меняет сути дела). Тем самым подчеркнем важность учета влияния помех не только на передачу, но и на хранение информации. Рассмотрим следующую ситуацию. Пластмассовые корпуса микросхем памяти в компьютерах содержат в малых количествах примеси, претерпевающие -распад. Попадая в полупроводниковые элементы памяти, -частицы могут вызвать изменение их состояний, то есть искажение хранимой информации. Как часто можно ожидать такого сбоя? Лабораторные эксперименты показали, что «время наработки на отказ» отдельно взятого элемента памяти превышает миллион лет. Казалось бы, это обстятельство не дает оснований для беспокойства. Однако следует учесть, что общее количество подобных элементов в памяти компьютера весьма велико. Например, память емкостью 1 Мбайт содержит приблизительно двоичных элементов (это соответствует количеству бит в 1 мегабайте). Следовательно, время появления ошибки в таком объеме памяти составит приблизительно
.
Предположив, что оперативная память персонального компьютера составляет 48 Мбайт, можно заключить, что время появления ошибки составляет уже около 1 дня. Нужно отметить, что в настоящее время нет экономичных технических способов исключения влияния этих ионизирующих излучений на элементы памяти. Поэтому проблема защиты информации от искажений не только при передаче, но и при хранении весьма актуальна.
Решение проблемы, как уже было сказано, состоит в использовании таких методов кодирования информации, которые позволили бы контролировать правильность передачи (или хранения) информации, а при обнаружении ошибки эти методы должны позволять исправлять ее.
Общим условием осуществимости обнаружения и исправления ошибки является использование только равномерных кодов. Во-первых, в этом случае недополучение одного из битов будет сразу свидетельствовать об ошибочности передачи, то есть постоянство длины кодовой цепочки является дополнительным средством контроля правильности передачи. Во-вторых, часто для увеличения скорости передачи используется параллельная (одновременная) передача нескольких (фиксированного, постоянного количества) бит по шинам (с фиксированной, разумеется, шириной).
Надежность передачи обеспечивается тем, что наряду с битами, непосредственно кодирующими сообщение (информационными битами), передаются (или хранятся) дополнительные биты (контрольные биты). При равномерном кодировании сообщения длина кодовой цепочки на знак (или группу знаков) первичного алфавита складывается из длины информационной части и числа контрольных битов . Определим избыточность L сообщения для реального канала связи:
. (14.1)
Избыточность сообщения – это величина, показывающая, во сколько раз требуется удлинить сообщение, чтобы обеспечить его надежную (безошибочную) передачу (хранение).
Таким образом, величина L характеризует эффективность кодирования при передаче по реальным каналам. Если какие-то два способа кодирования обеспечивают одинаковую надежность передачи, то при равных надежностях предпочтение должно быть отдано тому способу, при котором избыточность окажется наименьшей. Однако надо отметить, что для практики важна еще и простота того или иного способа кодирования.
Далее рассмотрим отдельно две ситуации:
2. Коды, обнаруживающие одиночную ошибку
Задача обнаружения ошибки может быть решена довольно легко. Достаточно просто передавать каждую букву сообщения дважды. Например, при необходимости передачи слова «гора» можно передать «ггоорраа». При получении искаженного сообщения, например, «гготрраа» с большой вероятностью (практически, достоверно) можно догадаться, каким было исходное слово. Конечно, возможно такое искажение, которое делает неоднозначным интерпретацию полученного сообщения. Однако цель такого способа кодирования состоит не в исправлении ошибки, а в обнаружении факта искажения и в повторной передаче подозрительной на наличие ошибки части сообщения. Недостаток данного способа обеспечения надежности состоит в том, что относительная избыточность сообщения оказывается очень большой – очевидно, .
Так как должен быть установлен только факт наличия ошибки, можно предложить и другой способ, позволяющий с высокой вероятностью обнаружить ошибку в сообщении. Суть этого способа заключается в следующем. На входе в канал связи производится подсчет числа единиц в двоичной кодовой последовательности – во входном сообщении. Если число единиц оказывается нечетным, то в хвост передаваемого сообщения добавляется «1», а если нет, то «0». Таким образом, к сообщению добавляют так называемый контрольный бит четности, чтобы суммарное количество единиц вместе с этим контрольным битом было четным. На принимающем конце канала связи производится аналогичный подсчет числа единиц, и если контрольная сумма единиц в принятой кодовой последовательности оказывается нечетной, то делается вывод о том, что при передаче произошло искажение информации, в противном случае принятая информация признается правильной. Разумеется, этот способ отнюдь не совершенен и применяется, когда вероятность ошибки не очень велика. При контроле на четность единственный способ получить достоверную информацию – это повторная передача сообщения.
Избыточность сообщения при контроле на четность равна:
. (14.2)
На первый взгляд кажется, что путем увеличения можно сколь угодно приближать избыточность сообщения к ее минимальному значению , стремящемуся к единице. Однако с ростом растет вероятность парной ошибки, которая контрольным битом четности не отслеживается, а также при обнаружении ошибки потребуется заново передавать много информации. Поэтому обычно или , следовательно, или соответственно.
3. Коды, исправляющие одиночную ошибку
По аналогии с предыдущим пунктом можно было бы предложить простой способ установления факта наличия ошибки – передавать каждый символ сообщения трижды, например, «гггооорррааа» – тогда при получении, например, сообщения «гггооопррааа» ясно, что ошибочной является буква «п» и ее следует заменить на «р». Безусловно, при этом предполагается, что вероятность появления парной ошибки невелика. Такой метод кодирования приводит к огромной избыточности сообщения , что неприемлемо с экономической точки зрения.
Прежде, чем обсуждать метод кодирования, позволяющий локализовать и исправить ошибку передачи, произведем некоторые количественные оценки. Как указывалось в предыдущей лекции, наличие шумов в канале связи ведет к частичной потере передаваемой информации на величину возникающей неопределенности. В случае передачи одного бита исходного сообщения эта неопределенность составляет
, (14.3)
где p – вероятность появления ошибки в сообщении (искажения этого бита, то есть его инверсии в случае двоичного кодирования нулями и единицами). Для восстановления информационного содержания сообщения следует дополнительно передать количество информации не менее величины ее потерь, то есть вместо передачи каждого 1 бита следует передавать бит. При этом избыточность сообщения составит как миимум
. (14.4)
Эта избыточность является минимальной; в случае передачи сообщения по каналу, характеризуемому определенной вероятностью возникновения ошибки, при избыточности, меньшей минимальной, восстановление информации оказывается невозможным.
Выражение (14.4) указывает нижнюю границу избыточности, необходимой для восстановления информации. Однако поиск конкретного способа осуществления кодирования, при котором ошибка может быть локализована (то есть определено, в каком конкретно бите она находится) и устранена – отдельная задача, которую мы теперь и обсудим. Изложенный ниже метод кодирования был предложен в 1948 году Р. Хеммингом; построенные по этому методу коды получили название «коды Хемминга».
Основная идея такого кодирования состоит в добавлении к информационным битам нескольких битов четности, каждый из которых контролирует определенные информационные биты. Если пронумеровать все передаваемые биты (вместе с битами четности) слева направо (напомним, что информационные биты нумеруются справа налево – от 0 до 7), то контрольными (проверочными) оказываются биты, номера которых равны степени 2, а остальные биты являются информационными. Например, для 8-битного информационного кода «01101101» передаваемый код (код Хемминга) будет 12-битным, так как к информационному коду добавятся 4 контрольных бита – 1-й, 2-й, 4-й и 8-й (рис. 7):
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
|
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
Рис. 7. Построение кода Хемминга
Принцип выделения контролируемых битов такой: для любого номера n проверочного (контрольного) бита, начиная с него, n битов подряд оказываются проверяемыми (контролируемыми), затем – группа из n непроверяемых бит, и так далее – происходит чередование групп. В число контролируемых (проверяемых) битов входит и сам контрольный (проверочный).
Состояние контрольного (проверочного) бита устанавливается при кодировании таким образом, чтобы суммарное количество единиц во всех контролируемых им битах было бы четным.
Таким образом, контрольный (проверочный) бит может содержать как нуль, так и единицу.
Номера контролируемых (прверяемых) битов для каждого контрольного приведены в табл. 22:
Табл. 22. Контрольные и контролируемые биты
|
Контрольные (проверочные) биты |
Контролируемые (проверяемые) биты |
|||||||||||
|
1 |
1 |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
17 |
19 |
21 |
… |
|
2 |
2 |
3 |
6 |
7 |
10 |
11 |
14 |
15 |
18 |
19 |
22 |
… |
|
4 |
4 |
5 |
6 |
7 |
12 |
13 |
14 |
15 |
20 |
21 |
22 |
… |
|
8 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
24 |
25 |
26 |
… |
|
16 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
… |
|
32 |
32 |
33 |
34 |
35 |
36 |
37 |
38 |
39 |
40 |
41 |
42 |
… |
Контрольный бит (бит четности) признается неверным, если сумма единиц в контролируемых им битах (включая его самого) нечетна.
Если контрольный бит оказался неверным, значит, в каком-то из контролируемых им битов имеется ошибка.
Существует общее свойство кодов Хемминга: Ошибка содержится в бите, номер которого является суммой номеров неверных контрольных битов, указавших на ее наличие.
На основании сказанного можно сформулировать простой алгоритм проверки и исправления передаваемой кодовой последовательности в представлении Хемминга:
Избыточность кодов Хемминга для различных длин передаваемых кодовых последовательностей приведена в табл. 23:
Табл. 23. Избыточность кодов Хемминга для передаваемых кодовых последовательностей различной длины
|
Число информационных битов, |
Число контрольных битов, |
Избыточность, L |
|
8 |
4 |
1.50 |
|
16 |
5 |
1.31 |
|
32 |
6 |
1.06 |
Количество контрольных битов определяется следующим образом (см. таблицу выше):
. (14.5)
Из сопоставления данных этой таблицы видно, что выгоднее (с меньшей избыточностью) передавать и хранить более длинные последовательности битов. При этом избыточность не должна оказаться меньше, чем минимально допустимая для выбранного канала связи.
Данный способ кодирования требует увеличения объема памяти компьютера приблизительно на одну треть при 16-битной длине машинного слова (см. таблицу), однако такой способ позволяет автоматически исправлять одиночные ошибки. Поэтому, оценивая время наработки на отказ этого способа, следует исходить из вероятности появления парной ошибки внутри одной кодовой последовательности (то есть сбои должны произойти в двух битах одновременно). Расчеты показывают, что для указанного ранее количества () двоичных ячеек в памяти объемом 1 Мбайт среднее время до появления сбоя при таком способе кодирования (код Хемминга) составляет более 80 лет, что, безусловно, можно считать вполне приемлемым с практической точки зрения.
1. Параллельная передача данных
Для одновременной передачи нескольких сигналов, очевидно, требуется линия связи, количество проводников в которой совпадает с числом передаваемых сигналов. Такая линия связи называется шиной. Количество проводников в шине определяет ширину или разрядность шины.
Например, во внутренних линиях связи компьютера могут использоваться 16-ти и 32-х разрядные шины. Шина обеспечивает наиболее быстрый способ передачи информации, поскольку за два такта тактового генератора передается целое машинное слово.
В общем случае, если – частота тактового генератора, h – разрядность шины, n – число тактов, за которые осуществляется передача 1 импульса (бита) по проводнику, то пропускная способность канала параллельной передачи будет:
. (15.1)
Параллельный способ передачи используется во внутренних линиях связи компьютера (на материнской плате; при обмене информацией с устройствами внешней памяти – магнитными и оптическими дисками), в линиях связи с внешними устройствами, подключаемыми к параллельному порту компьютера (LPT-порту): с принтером, плоттером и др.
Несмотря на достоинства, у параллельного способа передачи имеются недостатки:
2. Последовательная передача данных
Для передачи информации на большие расстояния, например, при объединении компьютеров в сети, используется последовательный способ передачи. Возможны два режима последовательной передачи:
При синхронной передаче каждый передаваемый бит сопровождается импульсом синхронизации, информирующим приемник информации о наличии в линии информационного бита. Синхронизирующие импульсы управляют приемом информации. В этом случае между передатчиком и приемником должны быть протянуты минимум три провода: один – для передачи данных, второй – для передачи синхроимпульсов, третий – общий заземленный.
Если расстояние между источником и приемником составляет несколько метров (и более), то каждый из сигналов (информационный и синхронизирующий) приходится посылать по специальному экранированному кабелю, что значительно увеличивает стоимость линии. Этот способ передачи не получил широкого распространения.
Асинхронный способ передачи не требует синхронизации действий приемника и передатчика; по этой причине для связи достаточно линии из двух проводников; причем оказывается необязательным использование специализированных компьютерных линий, а можно использовать даже телефонные линии. При асинхронной передаче источник и приемник должны быть согласованы по скорости передачи.
Передача производится машинными словами, состоящими из информационных битов и нескольких служебных битов. Рассмотрим пример передачи 8-битного слова с одним контрольным битом четности. В отсутствие передачи в линиии поддерживается уровень сигнала, соответствующий логической единице (например, +5 В) (рис. 8).
|
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
||||||||
|
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
Рис. 8. Асинхронный способ передачи данных
Вся передаваемая цепочка битов (стартовый бит, информационные биты, бит четности и стоповый бит) называется кадром. Передача нового кадра может начаться сразу после стопового бита. Новый стартовый бит может быть послан через любой интервал времени (не обязательно кратный ).
Так как количество битов в кадре превосходит количество информационных битов в нем, это приводит к увеличению избыточности кода и увеличению времени передачи. Поскольку биты передаются по очереди, скорость передачи ниже, чем в параллельном способе (при той же самой частоте тактового генератора). Тем не менее, и в последовательных линиях связи скорость передачи может достигать единиц Гбит/с – такой скорости более чем достаточно для передачи, например, телевизионного сигнала. Неоспоримым преимуществом последовательного способа передачи данных является то, что его применимость не ограничена дальностью передачи.
3. Связь компьютеров по телефонным линиям
Применение телефонных линий для осуществления связи между удаленными на большие расстояния компьютерами диктуется, в первую очередь, экономическими соображениями. Иначе потребовалась бы прокладка специальных компьютерных линий и содержание служб, поддерживающих работоспособность этих линий. Проще использовать уже имеющиеся телефонные линии. Итак, наличие двухпроводных линий и большие расстояния однозначно определяют единственно возможный способ передачи – последовательный. Однако телефонные линии предназначены для передачи аналоговых электрических сигналов с частотой не выше 3400 Гц. При передаче по таким линиям сигналов с частотами, на которых работает компьютер (~1000 МГц), они будут испытывать значительные искажения и быстро затухать. По этой причине передача осуществляется в соответствии со схемой, представленной на рис 9.
На приемном конце линии связи происходит обратная цепочка действий:
Асинхронный преобразователь располагается в самом компьютере в виде блока, осуществляющего обмен последовательным кодом с любым внешним устройством. Иначе асинхронный преобразователь называется COM-портом. Помимо модема к COM-порту подключаются, например, мышь, джойстик и пр.
Отметим, что название «модем» происходит от сокращения слов «модуляция» и «демодуляция». В модеме может использоваться амплитудная, частотная или фазовая модуляция электрических сигналов с частотой до 3000 Гц. Например, при частотной модуляции для представления 0 и 1 могут использоваться сигналы с частотами 1070 Гц и 1270 Гц.
Для увеличения скорости передачи современные модемы используют сложные методы модуляции, при которых каждый передаваемый элементарный сигнал кодирует не один, а несколько битов.
Рис. 9. Схема линии связи
При передаче данных по последовательным линиям связи возможны три режима:
Симплексная линия обеспечивает передачу только в одном направлении, например, от датчика к устройству обработки информации.
Полудуплексная связь обеспечивает передачу и получение информации в обоих направлениях, но не одновременно – если передает один модем, другой в это время только получает.
Дуплексный режим связи обеспечивает передачу и получение данных в обоих направлениях одновременно. Поскольку связь осуществляется по двухпроводной телефонной линии, приходится использовать вторую пару частот для связи в обратном направлении, например, 2025 Гц и 2225 Гц для представления нуля и единицы соответственно.
1. Классификация данных
Как было отмечено ранее, параллельно с термином «информация» при описании информационных процессов часто используется термин «данные». Определим его следующим образом:
Данные – это сведения, характеризующие какую-то систему, явление, процесс или объект, представленные в определенной форме и предназначенные для дальнейшего использования.
К данному определению необходимо сделать следующие замечания, разъясняющие соотношение между понятиями «информация» и «данные»:
При решении практических задач с помощью технических устройств формы представления информации всегда конкретны, в этой информации кто-то заинтересован, и поэтому употребление термина «данные» вполне оправдано.
Содержание понятия «данные» весьма обширно. Оно охватывает как какую-то отдельную величину, например год рождения человека, так и показания какого-либо датчика или производственные сведения фирмы. В компьютерных системах любая информация, представленная в допустимой для компьютера форме – тексты, рисунки, музыка и др. – считается данными. В информатике к данным относятся также тексты программ.
Данные имеют несколько классификационных признаков: данные бывают различных типов, делятся на простые и структурированные, подразделяются на переменные и постоянные, могут являться входными, промежуточными и выходными.
Ниже рассмотрим подробнее каждый из перечисленных классификационных признаков.
Тип данных определяет:
Допустимый набор типов данных и их особенности определяются программной системой или языком программирования, на котором система написана. При этом возможности различных языков по разнообразию допустимых типов данных, а также по построению новых типов данных различаются весьма сильно. Ясно, что чем более широкой и гибкой оказывается типизация данных в языке программирования, тем больше возможностей предоставляется пользователю при решении задач оптимального представления, хранения и применения данных. Типизация данных влияет и на компактность самой исполняемой программы.
Следующим классификационным признаком является деление даных на элементарные (простые) и структурированные (сложные). К элементарным данным относятся символы, числа (целые и вещественные) и логические данные. Общей и обязательной особенностью одиночных данных является то, что каждое из них имеет одно значение и собственное имя. Значение – это содержимое тех ячеек памяти, где данное располагается. Имя (его называют также идентификатор) – это обозначение данного в тексте программы. Правила построения идентификаторов элементарных данных определяются языком программирования.
Из элементарных данных строятся структурированные данные.
Структурированные данные – это информационный массив, включающий в себя элементарные данные и связи между ними.
Структура данных – это перечень объединяемых элементарных данных, их характеристики и особенности связей между ними.
Одним из примеров структурированных данных является телефонный справочник.
Перечень допустимых структур данных определяется языком программирования или прикладной программой. Этот перечень может быть фиксированным (нерасширяемым), как в языке BASIC или прикладных программах без встроенных возможностей программирования. В развитых языках программирования (PASCAL, C и др.) и ряде прикладных программ наряду с зарезервированными типами структур данных допускается создание новых типов; при этом элементами структуры могут быть сложные (структурированные) данные.
Сложные (структурированные) данные, как и элементарные, имеют значения и идентификаторы (имена). Значения размещаются в ячейках памяти по определенным схемам. Правила построения идентификатора устанавливаются языком программирования или прикладной программой. Исключение составляют правила формирования имен файлов – эти правила задаются операционной системой и должны соблюдаться всеми работающими в ней программами и языками программирования. Например, в MS-DOS в качестве имен файлов допустимы комбинации из латинских букв, цифр и некоторых специальных символов общей длиной не более 8 знаков; в Windows-95 (и выше) разрешены имена файлов длиной до 255 знаков.
По возможности изменения значений данных (как простых, так и структурированных) при их обработке данные подразделяют на переменные и постоянные (константы). Из названия очевидно, что переменные могут изменять свое значение в ходе исполнения программы, а константы – нет. На уровне операционной системы различие между переменными и постоянными величинами отсутствует, поэтому у них одинаковый порядок размещения в памяти и доступа к ним. Различие между переменными и константами подчеркивается в языках программирования и в созданных с их помощью прикладных программах.
В зависимости от того, на каком этапе обработки информации данные используются, они подразделяются на входные, промежуточные и выходные.
Входные данные – это данные, необходимые для исполнения программы и вводимые в компьютер до начала работы или в процессе работы программы. Входные данные могут быть предварительно записаны на некотором носителе и вводиться в компьютер с него, поступать по линиям связи от каких-либо датчиков или с других компьютеров, вводиться пользователем программы.
Промежуточные данные – это данные, формирующиеся в ходе исполнения программы; чаще всего они пользователю недоступны, не отображаются на устройствах вывода, но существуют в памяти компьютера. Идентификаторы промежуточным данным присваивают разработчики программы или задает сама программа по заложенным в нее правилам.
Выходные данные – это данные, являющиеся результатам работы программы, ради них и производится обработка входных данных. Выходные данные, предназначенные для человека, представляются в удобной для него форме (тексты, рисунки, звуки); при хранении выходных данных на носителях или при передаче их по сетям сохраняется двоичный компьютерный формат их представления. Таким образом, работу программы можно рассматривать как действия по преобразованию входных данных в выходные через необходимые для этого промежуточные.
С точки зрения самой программы все эти виды данных – входные , промежуточные, выходные – равноправны, то есть обрабатываются только в соответствии с их типом, а не в соответствии с функциональным назначением.
Представление данных при их хранении и обработке требует решения трех основных задач:
Выделяют три уровня представления данных – концептуальный, логический и физический.
На концептуальном уровне определяется общая структура информационного массива; эта структура называется моделью данных. Известны и используются несколько моделей данных: иерархическая, сетевая, реляционная, объектно-ориентированная. В соответствии с выбранной моделью данных строится информационная система, в которой данные будут храниться, а также строятся программы, ведущие обработку данных (манипулирование данными).
Логический уровень определяет способы представления элементарных данных, их перечень при объединении их в структуру, а также связи между ними в рамках выбранной модели данных.
Физический уровень определяет форматы размещения созданной логической структуры данных на материальных носителях информации (бумаге, магнитных или оптиеских дисках, в микросхемах памяти и так далее).
2. Представление элементарных данных в ОЗУ
Как уже было сказано, различными типами элементарных данных являются символы, целые числа, вещественные числа и логические данные. Логический и физический уровни их представления определяются конструктивными особенностями ОЗУ (оперативного запоминающего устройства) компьютера. Так как память компьютера имеет байтовую структуру, то к байтовой структуре и «привязывается» представление данных. Для представления значений элементарных данных в памяти компьютера используется машинное слово. Термин «машинное слово» в информатике имеет два определения:
Машинное слово – это совокупность двоичных элементов, обрабатываемая в компьютере как единое целое;
Машинное слово – это данные, содержащиеся в одной ячейке памяти компьютера.
С технической точки зрения машинное слово объединяет запоминающие элементы, каждый из которых служит для записи 1 бита информации, в единую ячейку памяти. Количество таких объединяемых элементов кратно 8 (1 байт содержит 8 бит). Например, в отечественной ЭВМ «БЭСМ-6» длина машинного слова составляла 48 бит (6 байт), в машинах IBM – 16 бит (2 байта). Доступ к машинному слову в операциях записи и считывания данных осуществляется по номеру ячейки памяти, который называется адресом ячейки.
Запоминающие устройства, в которых доступ к данным осуществляется по адресу ячейки, где они хранятся, называются устройствами с произвольным доступом.
В англоязычной литературе вместо термина «ОЗУ» используется термин «RAM», который означает «Random Access Memory» – «память с произвольным доступом». Время поиска нужной ячейки, а также продолжительность операций считывания или записи в запоминающем устройстве с произвольным доступом одинаково для всех ячеек, независимо от их адреса.
Для логического уровня представления элементарных данных важно то, что представление значений любых элементарных данных должно быть ориентировано на использование машинных слов определенной и единой для данного типа компьютера длины, так как представление элементарных данных на физическом уровне производится именно в ячейках ОЗУ. На ВЗУ (внешнем запоминающем устройстве) элементарные данные самостоятельно не представлены и доступ к ним отсутствует.
Рассмотрим особенности представления различных типов элементарных данных с помощью 16-битного машинного слова.
Для представления символов (литерных данных) машинное слово делится на группы по 8 бит, в которые и записываются двоичные коды символов. Ясно, что в 16-битном машинном слове могут быть записаны одновременно два символа (рис. 10):
|
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
Рис. 10. Представление символов в памяти ЭВМ
Значениями одиночных литерных данных являются коды символов. Множество допустимых значений данных этого типа для всех кодировок, основанных на таком однобайтовом представлении, составляет . Совокупность символов образует алфавит, то есть для символов установлен лексикографический порядок следования в соответствии с числовым значением кода; это позволяет определить над множеством символьных данных операции математических отношений «больше», «меньше», «равно». Непосредственно над одиночной символьной переменной определена только одна операция – изменение значения с одного кода на другой. Все остальные возможные действия производятся над сложными данными (например, типа String в языке программирования PASCAL).
В представлении целых чисел со знаком (например, тип Integer в языке PASCAL) старший бит (15-й) отводится под запись знака числа (0 соответствует «+», 1 соответствует «–»), а остальные 15 разрядов (с 0-го по 14-й) отводятся под запись двоичного кода числа (рис. 11):
|
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
Рис. 11. Представление целого числа со знаком в памяти ЭВМ
При этом возможные значения чисел ограничены интервалом .
Наряду с описанным используется и другой формат представления целых чисел – беззнаковый. Этот формат применим для записи положительных целых чисел. В этом случае под запись числа отводятся все 16 двоичных разрядов, и интервал разрешенных значений . В языке PASCAL такой числовой тип называется Word. Помимо математических отношений, над целыми числами определены операции сложения, вычитания, умножения, целочисленного деления и нахождения остатка от целочисленного деления.
Представление в ОЗУ вещественных чисел с плавающей точкой характеризуется тем, что при записи число переводится в нормализованную форму с выделением порядка, мантиссы и их знаков. Для представления числа отводится несколько машинных слов. Ситуация, соответствующая числовому типу Single языка PASCAL, когда для представления числа отводятся два машинных слова, проиллюстрирована ниже (рис. 12):
|
31 |
30 |
29 |
28 |
27 |
26 |
25 |
24 |
23 |
22 |
… |
5 |
4 |
3 |
2 |
1 |
0 |
|
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
… |
0 |
0 |
0 |
0 |
1 |
0 |
Рис. 12. Представление вещественного числа в ОЗУ
Этой формой представления охватывается диапазон модулей мантиссы с 7-ю десятичными цифрами мантиссы. Запись мантиссы располагается с 0-го по 23-й разряд. Так как мантисса выбирается такой, чтобы ее модуль отвечал условию , то значение «0 целых» не отображается, а значение самого старшего отображаемого разряда мантиссы всегда «1». В процессе выполнения операций может произойти переполнение разрядной сетки (на 1 разряд) или, наоборот, ее освобождение (то есть в первом отображаемом разряде окажется 0). По этой причине после каждой операции с числами в такой форме производится нормализация результата, которая состоит в таком изменении порядка числа и сдвиге мантиссы, чтобы первой значащей цифрой в записи модуля мантиссы снова оказалась 1. Изменение порядка в представлении числа эквивалентно перемещению разделителя целой и дробной частей числа, поэтому такая форма и получила название «с плавающей точкой». Благодаря применению представления с плавающей точкой производится автоматическое масштабирование чисел в ходе вычислений, что снижает погрешность их обработки. Над вещественными числами определены не только все четыре арифметические операции, но и операции преобразования вещественного числа к целому (например, операции round и trunc в языке PASCAL).
Логические данные могут принимать одно из двух значений – 0 (что соответствует логическому False) и 1 (что сответствует логическому True, причем принимается True>False). Для записи логических данных было бы достаточно отвести всего один двоичный разряд, однако в ОЗУ компьютера отсутствует доступ к отдельному биту, поэтому для представления логических данных используется целый байт, в младший разряд которого и помещается значение логического данного. Таким образом, в машинном слове логические данные располагаются в 0-м и 8-м разрядах (битах)
(рис. 13):
|
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Рис. 13. Представление логических данных в ОЗУ
Над логическими данными определены операции: логическое умножение (конъюнкция, ), логическое сложение (дизъюнкция, ), логическое отрицание (). Примером определения логических данных может служить тип Boolean в языке программирования PASCAL.
В заключение подчеркнем, что значения элементарных данных формируются в ходе исполнения программы и имеют физическое представление в ОЗУ. В отличие от значений идентификаторы данных существуют только на логическом уровне и используются для обозначения данных в тексте программы. При трансляции программы с языка программирования в машинный код имена (идентификаторы) данных заменяются номерами ячеек, в которых данные размещаются. Таким образом, при исполнении программы обращение к данным производится по адресу ячейки, а не по идентификатору. Адреса могут быть абсолютными – в этом случае они не изменяются при загрузке программы в ОЗУ (именно такой способ адресации данных применяется в исполняемых программных файлах с расширением .com). Однако в силу некоторых особенностей распределения памяти компьютера размер таких программ не может превышать 64 Кбайт. В исполняемых файлах с расширением .exe на этапе трансляции устанавливаются относительные адреса данных, которые конкретизируются непосредственно при размещении программы в ОЗУ – это несколько замедляет начало исполнения программы, зато снимает указанное выше ограничение на размер программы.
В некоторых прикладных программах в качестве элементарных данных используются данные таких, например, типов, как «Data» или «Денежный» в MS Excel или MS Access. Однако эти типы являются самостоятельными только для пользователя программы; самой же программой они сводятся к некоторой комбинации рассмотренных выше типов элементарных данных.
Можно указать ряд причин, поясняющих необходимость и удобство организации данных в некоторую структуру:
Перечисленные причины приводят к тому, что в современных языках и системах программирования резервируется широкий спектр различных структур данных, и, помимо этого, предусматривается возможность создания структур, необходимых пользователю.
Относительно структур данных необходимо сделать следующие общие замечания:
1. Классификация и примеры структур данных
Структурирование данных предполагает существование (или установление) между ними каких-то отношений (связей). В зависимости от характера этих отношений можно выделить несколько классификационных признаков структур данных:
Сначала рассмотрим отношение порядка. Структуры данных делятся на упорядоченные и неупорядоченные. В упорядоченных структурах элементы размещаются по порядку в соответствии со значением некоторого признака. Наиболее простым признаком является порядковый номер элемента; установление порядка в соответствии с номером называется нумерацией. При этом если весь набор элементарных данных имеет общий идентификатор (например, M), то отдельным данным присваиваются собственные идентификаторы – индексы (например, или ). Вообще, в качестве индекса может выступать любой знак из конечного алфавита. Лексикографический порядок индексов определяет отошение следования между элементами структуры, состоящей из элементарных данных, то есть элемент следует после , а элемент следует после . Примером структур, в которых упорядочение производится по номеру элемента, являются массивы. Порядковый номер элемента данных можно считать внешним признаком этого элемента, который может присваиваться элементу независимо от значения элемента. Например, регистрационный номер документа определяется только временем его поступления в учреждение, а не его содержанием. Помимо нумерации в структурах данных используется упорядочение по значению некоторого внутреннего признака, например, размещение фамилий в алфавитном порядке или предприятий в порядке убывания их рентабельности – такое упорядочение называется ранжированием.
Примером неупорядоченных структур являются множества – в них не определен порядок элементов; единственное, что можно установить в этом случае для каких-то конкретных данных, так это их принадлежность (или непринадлежность) выбранному множеству.
Следующим классификационным признаком структур данных является однородность. К однородным относятся структуры, содержащие элементарные данные только одного типа. Неоднородные структуры объединяют данные разных типов. Примерами однородных структур являются массивы, множества, стеки. Примером неоднородных структур могут служть записи.
Еще одним классификационным признаком структур данных является характер отношений между элементами. По взаимной подчиненности элементов структуры данных подразделяются на линейные и нелинейные. В линейных структурах все элементы равноправны. К таким структурам относятся массив, множество, стек, очередь. В нелинейных структурах между элементами существуют отношения подчиненности или они могут быть связаны логическими условиями. В качестве примеров нелинейных структур можно привести деревья, графы.
Далее рассмотрим и охарактеризуем некоторые структуры данных: массив, стек, очередь, дерево, граф.
Массив. Упорядоченная линейная совокупность однородных данных называется массивом.
Комментарии к определению:
Мерность (размерность) массива – это количество индексов (сам индекс – величина переменная), определяющих положение элемента в массиве.
Так, если индекс единственный, массив называется одномерным; часто такой массив называют вектором, строкой или столбцом. Для обозначения элементов ономерного массива используется обозначение , в языках программирования приняты обозначения m[i] или m(i).
Массив, элементы которого имеют два индекса, называется двумерным или матрицей. Элементы матрицы обозначаются , m[i,j] или m(i,j). Первый индекс (i) – это номер строки, второй индекс (j) – это номер стобца, на пересечении которых находится данный элемент массива. Массивы с тремя индексами называются трехмерными, с четырьмя – четырехмерными и так далее Максимальная мерность массива либо может быть ограничена синтаксисом языка программирования, либо может не иметь такого ограничения.
Размер массива – это максимальные значения индексов элементов. Размер массива указывается в блоке описания программы; при исполнении программы для хранения элементов массива резервируется необходимый объем памяти. Если в процессе исполнения программы размер массива не изменяется (или не может быть изменен), то в этом случае говорят о статическом массиве (массиве фиксированного размера). Если определение размера массива происходит по ходу выполнения программы, то такой массив называется динамическим (или динамически описываемым).
Допустимый набор операций над элементами массива определяется типом данных (элементарных или структурированных, в зависимости от ситуации), из которых массив сформирован. В некоторых языках программирования над массивом в целом определена операция присваивания M:=<значение>, когда всем элементам массива присваивается одинаковое значение. Возможна операция присваивания для двух одинаковых по типу, размерности и размеру массивов M2:=M1, когда производится поэлементное присваивание значений, то есть , где , .
Существуют символьные массивы – они называются строками или строковыми данными (например, тип String в языке программирования PASCAL). С ними возможен целый набор операций, неопределенных для одиночных символьных данных: операция конкатенации (объединения) строк с формированием новой строки, операция замещения части строки, определения числовых (количественных) характеристик строки.
Стек. Существует структура данных, в которой элемент, помещенный в нее первым, выходит последним, и наоборот, тот элемент, который последним входит, выходит первым (рис. 14). Такая структура данных получила название стек (или магазин – по сходству с магазином стрелкового оружия). «Стек» на аглийском означает «стопка».
Рис. 14. Стек
Эти структуры реализуются в виде специальным образом организованных областей ОЗУ компьютера. Часто стек называют памятью типа LIFO (Last-In First-Out). В стеке ячейки памяти (или регистры стековой памяти) соединяются друг с другом таким образом, что занесение данных в стек возможно только через первую ячейку (вершину стека), при этом содержимое остальных ячеек сдвигается вниз, по направлению к дну стека по мере его заполнения. Извлекаться первым будет содержимое ячейки, которая была заполнена последней – то есть ячейки, ближайшей к вершине стека.
Стек – это упорядоченная сруктура равноправных данных, поэтому стек является линейной структурой данных. В ячейках стека могут содержаться данные разных типов, поэтому стек – структура в общем случае неоднородная.
Очередь. Отличие очереди от стека в том, что извлечение информации из очереди производится по принципу «первым вошел – первым вышел», то есть со дна структуры. Извлекается первым содержимое той ячейки, которая была заполнена первая (рис. 15).
Рис. 15. Очередь
Способы организации данных в виде стека и очереди оказываются удобыми, например, при работе с подпрограммами в сложных программах.
Дерево. Дерево или иерархия является примером нелинейной структуры. В ней элемент каждого уровня (за исключением самого верхнего) входит в один и только один элемент более высокго уровня. Элемент самого высокого уровня называется корнем, а элементы самых нижних уровней называются листьями (рис. 16):
Рис. 16. Дерево
Отдельные элементы иерархической структуры могут быть как однородными, так и неоднородными. Примером иерархической структуры организации данных может служить файловая структура в запоминающих устройствах компьютера.
Граф. Часто отношения между данными представляются в виде графа – совокупности точек и линий, причем каждая линия соединяет две точки. Точка получает смысл элемента структуры (данных), а линии – смысл отношения между элементами.
Точки называются вершинами графа, линии называются ребрами графа.
Ребро, соединяющее две конкретные вершины, называется инцидентным этим вершинам, а сами эти вершины называются смежными; причем они инцидентны этому ребру.
Число ребер, инцидентных вершине, называется степенью вершины.
Если два ребра инцидентны одной и той же паре вершин, то эти ребра называются кратными.
Ребро, у которого совпадают обе вершины, называется петлей.
Граф задается списком вершин и списком ребер, в котором для каждого ребра указывается пара инцидентных для него вершин.
Например, для графа на рис. 17: список вершин {1,2,3,4}; список ребер: a(1,2), b(1,4), c(2,4), d(2,3), e(3,4), f(2,3), g(4,4); смежные пары вершин: (2,3), (2,4), (1,2), (1,4), (3,4); ребро g является петлей; ребра d и f – кратные; степени вершин 2 и 4 равны 4; степень вершины 3 равна 3; вершины 1 – равна 2.
Рис. 17. Неориентированный граф
Ребро, соединяющее вершины, может иметь направление – тогда это ребро называется ориентированным и изображается стрелкой (рис. 18).
Граф, в котором все ребра ориентированные, называется ориентированным; ребра ориентирванного графа называются дугами.
Дуги называются кратными, если они соединяют одни и те же вершины и совпадают по направлению. При обозначении дуги всегда первой указывается вершина, из которой дуга начинается, например, (2,3) на рис. 18.
Рис. 18. Ориентированный граф
Маршрут – это последовательность ребер, в которой конец предыдущего ребра совпадает с началом следующего ребра. Маршрут, в котором конечная вершина совпадает с начальной, называется циклом.
Граф называется связным, если между любыми двумя его вершинами имеется маршрут.
Граф является упорядоченной, нелинейной, неоднородной структурой.
Понятие графа, благодаря наглядности и высокой общности в информатике выступает в качестве основного средства описания структур данных, систем, порядка выполнения действий. Примером графа может служить блок-схема программы.
2. Понятие логической записи
Логическая запись – это поименованная совокупность элементарных данных, имеющая смысловую завершенность.
Примером записи может служить строка из списка студентов:
|
Фамилия |
Год рождения |
Год поступления в ВУЗ |
Курс |
Номер зачетной книжки |
Логическая запись объединяет не разрозненные по смыслу данные, а только те, что характеризуют некоторую систему или объект – именно в этом смысле следует понимать слова «смысловая завершенность» в определении. Запись отражает совокупность свойств (атрибутов) системы или объекта.
Логическая запись имеет многоуровневую структуру. Элементами самого нижнего уровня являются элементарные данные. Элементарные данные хранятся и считываются целиком, доступ к их частям невозможен.
Совокупности элементарных данных, имеющих определенный смысл, но не обладающих смысловой завершенностью, образуют поля, каждое из которых соответствует одному атрибуту системы (объекта). Каждое поле характеризуется типом элементарных данных, из которых оно строится, а также информационным размером (количеством байт, которое отводится для представления этого поля в записи). Поля записи связаны между собой. Связи между ними могут носить функциональный характер, когда значение одного поля посредством некоторого преобразования (правила) определяет значение друго поля; кроме того, связи между полями могут быть причинно-следственными.
Логические записи сами могут быть объединены в структуры, которые определяются моделью данных. Например, совокупность записей из приведенного выше примера может образовать массив данных, который будет называться базой данных. Возможны и более высокие структурные объединения, например, объединения баз данных – структуры, элементами которых будут являться базы данных. Программные системы, позволяющие создавать и использовать базы данных, называются системами управления базами данных (СУБД). Логическая запись имеет собственный идентификатор, по которому можно обратиться к записи в целом. Поля также имеют свои идентификаторы, по которым поля становятся доступными для просмотра или изменения значения. Идентификатор поля строится из идентификатора базы данных, идентификатора в нее входящей записи и собственно поля, входящего в эту запись. Таким образом, существует иерархическая многоуровненвая структура данных (рис. 19).
Рис. 19. Иллюстрация многоуровневой иерархической структуры данных.
Каждый выше расположенный уровень содержит низлежащие в качестве составных элементов. В этой иерархии запись является первым элементом структуры, обладающим смысловой завершенностью.
1. Организация структур данных в ОЗУ
Структура информационного массива определяется один раз на этапе его создания и в процессе использования уже не изменяется. В языках программирования это достигается описанием структуры в блоке описаний программы, в СУБД (системах управления базами данных) – установлением перечня и последовательности полей записи на начальном этапе создания базы данных. Всякое изменение структуры данных (например, введение дополнительного поля записи или удаление имеющегося поля) эквивалентно созданию новой структуры.
Что же касается количества записей в структурированном информационном массиве, то при представлении его в ОЗУ компьютера возможны две ситуации:
В случае последовательного представления данные (отдельные записи) размещаются в соседних последовательно расположенных ячейках памяти. На размещение одной записи может потребоваться несколько ячеек (машинных слов), но их количество одинаково для каждой записи (на рис. 20 на запись приходится две ячейки); идентификатор записи однозначно связывается с номером ячейки, начиная с которой запись начинается.
|
№ записи |
№ ячейки |
Содержание записи |
|
1 |
4000 |
Запись А |
|
4001 |
||
|
2 |
4002 |
Запись В |
|
4003 |
||
|
3 |
4004 |
Запись С |
|
4005 |
а)
|
№ записи |
№ ячейки |
Содержание записи |
|
1 |
4000 |
Запись А |
|
4001 |
||
|
2 |
4002 |
Запись R |
|
4003 |
||
|
3 |
4004 |
Запись В |
|
4005 |
||
|
4 |
4006 |
Запись С |
|
4007 |
б)
|
№ записи |
№ ячейки |
Содержание записи |
|
1 |
4000 |
Запись А |
|
4001 |
||
|
2 |
4002 |
Запись R |
|
4003 |
||
|
3 |
4004 |
Запись С |
|
4005 |
в)
Рис. 20. Последовательное динамическое размещение данных в ОЗУ: а – начальное размещение; б – после добавления новой записи; в – после удаления записи.
Физический порядок следования записей полностью соответствует логическому. Такая совокупность записей называется последовательным списком. Для его хранения в ОЗУ выделяется блок ячеек фиксированного размера. Когда от обрабатывающей программы поступает команда «Добавить запись», происходит увеличение размера массива, при необходимости происходит перезапись массива в ОЗУ (возможно, с изменением адресов данных). При изъятии каких-то записей по команде «Удалить запись» соответствующие ячейки очищаются и после перезаписи все содержимое следующих ячеек сдвигается в направлении удаленной записи на количество ячеек, приходящихся на одну запись.
Связное представление данных основано на том, что в записи присутствует дополнительное поле, в котором размещается особое данное – указатель адреса, то есть ссылка на то место в ОЗУ, где располагается следующая запись. При этом физический порядок размещения записей может не соответствовать логическому – записи располагаются в любых свободных ячейках ОЗУ, причем не обязательно подряд (то есть непосредственно другом за другом). Такие структуры данных называются связными списками. Их удобство состоит в гибкости структуры – без перезаписи остальных элементов данных в другие (соседние) ячейки можно легко добавлять новые или исключать имеющиеся записи. Для этого достаточно лишь изменить состояние поля указателя адреса (рис. 21).
а)
б)
в)
Рис. 21. Связное динамическое размещение данных в ОЗУ: а – начальное размещение; б – после добавления новой записи; в – после удаления записи.
Недостаток этого способа представления информационного массива в ОЗУ состоит в том, что в нем невозможно напрямую обратиться к нужной записи – поиск ее осуществляется по цепочке переходов, что увеличивает время доступа к данным.
2. Иерархия структур данных на внешних носителях
Основными информационными единицами при сохранении данных на внешних носителях (ВЗУ) являются:
Логическая запись при хранении на внешних носителях является той же информационной единицей, что и при хранении в ОЗУ. Отличие состоит в том, что при хранении на внешнем носителе запись является минимальным и неделимым элементом представления данных. Это означает, что после размещения записи на носителе отсутствует доступ к ее отдельным полям, а операции переноса на носитель (сохранение) и считывание с него производятся целиком со всей записью. Поскольку обработка записей при их хранении не происходит, не требуется и подчеркивать различия типов данных. Запись может состоять из одного элементарного данного, группы данных или содержать структурированные данные. Единственной характеристикой отдельной записи на носителе является ее длина, а допустимые операции над записью – перенос на носитель и считывание с него.
После размещения данных на носителе они превращаются в физическую запись.
Физическая запись – элемент поверхности носителя, на котором в соответствии с физическими принципами функционирования носителя размещаются данные, составляющие логическую запись.
Файл – определенным образом оформленная совокупность физических записей, рассматриваемая как единое целое и имеющая описание в системе хранения информации.
Комментарии к определению понятия файла:
Любые файлы содержат данные, закодированные с помощью двоичного алфавита. Однако способы кодирования и назначение файлов могут быть различными. По этой причине файлам приписывается еще одна характеристика – тип. Тип входит в идентификатор файла и указывается в виде расширения имени, например: Глава_5.doc, proba.pas, calc.exe.
Принципиально различными по типам являются:
Тип файла и его имя являются частью описания файла.
Самым верхним уровнем представления данных на внешних носителях являются структуры файлов – каталоги (в операционной системе MS Windows каталоги называются папками); в них помещаются файлы, объединенные каким-то признаком, например, принадлежностью к одной программной системе или одной информационной базе. Как правило, каталоги допускают образование вложенных структур – подкаталогов (каталогов внутри каталогов). Каталоги образуют иерархическую структуру, поэтому используется термин «дерево каталогов»; каталог, располагающийся на вершине иерархии (включающий в себя все каталоги на носителе), называется корневым.
Создает и поддерживает файловые структуры, производит все операции с файлами и каталогами особая часть операционной системы – файловая система.
3. Особенности устройств хранения информации
Не вдаваясь глубоко в техническую сторону, рассмотрим некоторые особенности устройств, используемых для хранения информации в компьютерах.
Устройства, выполняющие операции, связанные с сохранением и считыванием данных на материальных носителях, называются внешними запоминающими устройствами (ВЗУ) или устройствами внешней памяти.
Любое ВЗУ реализует один из двух возможных принципов размещения данных – последовательный доступ или прямой доступ.
Последовательный доступ используется при сохранении информации на ленточных носителях, например, магнитной или бумажной ленте; в этом случае записи размещаются одна за другой, то есть последовательно; для того чтобы отыскать нужную запись, требуется просмотреть все предыдущие записи, подобно поиску кадра на фотопленке или песни на аудиокассете.
Для реализации прямого доступа на носителе должны быть обозначены (пронумерованы) области для записи информации – такие области называются блоками (секторами). Блок, подобно ячейке ОЗУ, служит контейнером для размещения данных. Обратиться к данным для записи-считывания можно по номеру (идентификатору) блока. Операция разделения поверхности носителя на блоки называется форматированием; форматирование производится в обязательном порядке и предшествует использованию носителя. Блок обычно имеет строго определенную для данного носителя информационную емкость. Например, для сменного магнитного диска емкостью 1.44 Мбайт емкость одного блока составляет 512 байт. Блок может содержать только целое число физических записей; из-за этого часть блока, имеющая длину меньше, чем размер записи, не может использоваться и оказывается пустой. Например, при длине записей по 150 байт в один блок размером 512 байт поместятся 3 записи, а 62 байта останутся свободными и не будут использоваться. На носителях большой емкости, например, жестких магнитных дисках (HDD или винчестерах) блоки объединяются в группы – кластеры (например, на современных IBM-совместимых компьютерах кластер объединяет 8 блоков). В этом случае при чтении-записи применяется адресация по номерам кластеров; это уменьшает общее количество адресов и, следовательно, ускоряет поиск и доступ к нужному файлу.
На дисковых носителях имена файлов хранятся отдельно от физических записей. В определенном месте диска при его форматировании создается специальная область, в которой располагается таблица размещения файлов – FAT (File Allocation Table). В эту таблицу заносятся имена и атрибуты файлов (дата и время создания файла, размер), а также номер кластера, с которого начинается размещение файла на носителе. Обращение к файлу происходит в два этапа: сначала с помощью файловой таблицы по имени файла находится номер кластера, затем считывающе-записывающая головка ВЗУ устанавливается над найденным файлом и производит операции. Содержание файловой таблицы можно просмотреть с помощью команд операционной системы (например, команда dir в MS DOS).
При обмене данными между ВЗУ и ОЗУ данные пересылаются не отдельными записями, а блоками, размер которых совпадает с размером блока на ВЗУ – 512 байт. Для организации обмена в ОЗУ выделяется специальная область – буфер обмена; размер буфера обмена устанавливается при конфигурировании операционной системы компьютера. При пересылке данных из ОЗУ в ВЗУ данные сначала из ОЗУ пересылаются в буфер обмена, а затем целым блоком отправляются в подготовленный блок (сектор) ВЗУ. Считывание данных идет обратным путем. Обмен данными между ОЗУ и ВЗУ может идти, минуя центральный процессор, одновременно с обменом может производиться обработка данных.
* Термин «префикс» означает «приставка».
Да
Да
Нет
Нет
Да
Нет
X > 1 ?
X > 0 ?
X > 2 ?
X = 0
X = 1
X = 2
X = 3
Вопрос 1
Вопрос 2
Ответ 1
Ответ 2
Результат
Регистр переполнения
+
Регистр переполнения
+
+
+
Номер бита
Мантисса
Порядок числа
Бит знака
числа
Бит знака
порядка
Преобразователь «коды сигналы»
Преобразователь «сигналы коды»
Защита
от шумов
Шумы
(помехи)
t
EMBED PBrush
Импульс
Пауза
T
EMBED Equation.3
Уровень «0»
EMBED Equation.3
EMBED PBrush
P
Номера битов кода Хемминга
Номера
информационных
битов
Контрольные
(проверочные) биты
Нет пересылки
Нет пересылки
Номера информационных битов
Стартовый
бит
Стоповый
бит
Бит четности
Асинхронный преобразователь 1
Компьютер 1
Модем 1
Модем 2
Компьютер 2
Асинхронный преобразователь 2
Аналоговый сигнал в телефонной линии
Последовательный код
Параллельный код
Номера разрядов машинного слова
1-й байт (код символа 1)
2-й байт (код символа 2)
Номера разрядов машинного слова
Двоичный код числа
Знак числа
Номера разрядов машинного слова
Двоичный код мантиссы
Двоичный код
порядка
Знак мантиссы
Знак порядка
Номера разрядов машинного слова
1-е логическое значение
2-е логическое значение
Корень
Лист 1
Лист 2
Лист 4
Лист 3
Лист 5
g
4
f
a
e
b
c
2
3
1
d
f
a
b
c
e
1
2
3
4
5
Объединение баз данных
База данных
Запись
Поля записи
Элементарные данные
Указатель адреса следующей ячейки
Адрес ячейки
315
Содержание А
1023
1023
Содержание B
707
707
Содержание C
…
315
Содержание А
1023
1023
Содержание B
3333
707
Содержание C
…
333
Содержание R
707
315
Содержание А
3333
707
Содержание C
…
3333
Содержание R
707