>>Информатика: Информатика 9 класс. Дополнение к главе 1

Дополнение к главе 1

1.1. Передача информации по техническим каналам связи

Основные темы параграфа:

♦ схема К. Шеннона;
♦ кодирование и декодирование информации;
♦ шум и защита от шума. Теория кодирования К. Шеннона.

Схема К. Шеннона

Американским ученым, одним из основателей теории информации, Клодом Шенноном была предложена схема процесса передачи информации по техническим каналам связи, представленная на рис. 1.3.

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

Связь, при которой передача производится в форме непрерывного электрического сигнала, называется аналоговой связью.

Кодирование и декодирование информации

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

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

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

Шум и защита от шума. Теория кодирования К. Шеннона

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

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

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

Однако нельзя делать избыточность слишком большой. Это приведет к задержкам и удорожанию связи. Теория кодирования К. Шеннона как раз и позволяет получить такой код, который будет оптимальным. При этом избыточность передаваемой информации будет минимально возможной, а достоверность принятой информации - максимальной.

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

Коротко о главном

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

Под кодированием понимается преобразование информации, идущей от источника, в форму, пригодную для ее передачи по каналу связи. Декодирование - это обратное преобразование.

Шум - это помехи, приводящие к потере информации.

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

Вопросы и задания

1. Назовите основные элементы схемы передачи информации, предложенной К. Шенноном.
2. Что такое кодирование и декодирование при передаче информации?
3. Что такое шум? Каковы его последствия при передаче информации?
4. Какие существуют способы борьбы с шумом?

1.2. Архивирование и разархивирование файлов

Основные темы параграфа:

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

Проблема сжатия данных

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

Решение проблемы заключается в сжатии данных, которое ведет к сокращению объема данных при сохранении закодированного в них содержания. Программы, осуществляющие такое сжатие, называются архиваторами. Первые архиваторы появились в середине 1980-х годов XX века. Главной целью их использования была экономия места на дисках, информационный объем которых в те времена был значительно меньше объема современных дисков.

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

Алгоритм сжатия с использованием кода переменной длины

Первая идея: использование кода переменной длины. Данные, подвергающиеся сжатию, специальным образом делят на части (цепочки символов, «слова»). Заметим, что «словом» может быть и отдельный символ (код АSСII). Для каждого «слова» находится частота встречаемости: отношение количества повторений данного «слова» к общему числу «слов» в массиве данных. Идея алгоритма сжатия информации: кодировать наиболее часто встречающиеся «слова» кодами меньшей длины, чем редко встречающиеся «слова». При этом можно существенно сократить объем файла.

Такой подход известен давно. Он используется в азбуке Морзе, где символы кодируются различными последовательностями точек и тире, причем чаще встречающиеся символы имеют более короткие коды. Например, часто используемая буква «А» кодируется так: -. А редкая буква «Ж» кодируется: -. В отличие от кодов одинаковой длины, в этом случае возникает проблема отделения кодов букв друг от друга. В азбуке Морзе эта проблема решается с помощью «паузы» (пробела), которая, по сути, является третьим символом алфавита Морзе, то есть алфавит Морзе не двух-, а трех символьный.

Информация в памяти ЭВМ хранится с использованием двух символьного алфавита. Специального символа-разделителя нет. И все же удалось придумать способ сжатия данных с переменной длиной кода «слов», не требующий символа-разделителя. Такой алгоритм называется алгоритмом Д. Хаффмена (впервые опубликован в 1952 году). Все универсальные архиваторы работают по алгоритмам, подобным алгоритму Хаффмена.

Алгоритм сжатия с использованием коэффициента повторения

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

Программы-архиваторы

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

Добавление файлов в архив;
извлечение файлов из архива;
удаление файлов из архива;
просмотр содержимого архива.

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

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

Пользоваться программами-архиваторами очень просто. Чтобы создать архив, нужно сначала выбрать файлы, которые необходимо в него включить, затем установить необходимые параметры (способ архивации, формат архива, размер тома, если архив многотомный), и, наконец, отдать команду СОЗДАТЬ АРХИВ. Похожим образом происходит обратное действие - извлечение файлов из архива (распаковка архива). Во-первых, нужно выбрать файлы, извлекаемые из архива, во-вторых, определить, куда должны быть помещены эти файлы, и, наконец, отдать команду ИЗВЛЕЧЬ ФАЙЛЫ ИЗ АРХИВА. Подробнее с работой программ-архиваторов вы познакомитесь на практических занятиях.

Коротко о главном

Сжатие информации производится с помощью специальных программ-архиваторов.

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

Вопросы и задания

1. В чем различие кодов постоянной и переменной длины?
2. Какими возможностями обладают программы-архиваторы?
3. Какова причина широкого применения программ-архиваторов?
4. Знаете ли вы другие программы-архиваторы, кроме перечисленных в этом параграфе?

И. Семакин, Л. Залогова, С. Русаков, Л. Шестакова, Информатика, 9 класс
Отослано читателями из интернет-сайтов

Открытый урок информатики, школьный план , рефераты информатики , всё школьнику для выполнения домашнего задания, скачать информатику 9 класс

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

Если у вас есть исправления или предложения к данному уроку,

Коды переменной длины

КОДИРОВАНИЕ И СЖАТИЕ ИНФОРМАЦИ

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

Коды переменной длины

Первое правило построения кодов переменной длины, состоит в том, что короткие коды следует присваивать часто встречающимся символам, а длинные – редко встречающимся. При этом коды следует назначать так, чтобы из можно было декодировать однозначно, а не двусмысленно. Например, рассмотрим четыре символа a 1 , a 2 , a 3 , a 4 . Если они появляются в сообщении с равной вероятностью (p = 0,25), то присвоим им четыре двухбитовых кода: 00, 01, 10, 11. Все вероятности равны, поэтому коды переменной длины не сожмут данные. Для каждого символа с коротким кодом найдётся символ с длинным кодом и среднее число битов на символ будет не меньше 2. Избыточность данных равновероятными символами равна 0, и строку таких символов невозможно сжать с помощью кодов переменной длины (или какого-либо другого метода).

Пусть теперь эти четыре символа появляются с разными вероятностями (см. табл. 12.1). В этом случае имеется избыточность, которую можно удалить с помощью кодов переменной длины и сжать данные так, чтобы потребуется меньше 2 бит на символ. Наименьшее среднее число бит на символ равно 1,57, то есть энтропии этого множества символов.

В таблице 12.1 предложен код Код_ 1, который присваивает самому часто встречающемуся символу самый короткий код. Среднее число бит на символ равно 1,77. Это число близко к теоретическому минимуму.

Таблица 12.1

Рассмотрим последовательность из 20 символов

a 1 a 3 a 2 a 1 a 3 a 3 a 4 a 2 a 1 a 1 a 2 a 2 a 1 a 1 a 3 a 1 a 1 a 3 a 1 ,

в которой четыре символа появляются, примерно, с одинаковыми частотами. Этой строке будет соответствовать кодовое слово длины 37 бит:

1|010|01|1|010|010|001|01|1|1|01|01|1|1|010|1|1|01|010|1.

Среднее число бит на символ составляет 1,85, что не слишком далеко от вычисленной минимальной средней длины. Однако если попытаться декодировать последовательность, то окажется, что Код _1 имеет существенный недостаток. Первый бит кодового слова равен 1, поэтому первым символом последовательности может быть только a 1 , так как код никакого другого символа не начинается с 1. Следующий символ равен 0, но коды для символов a 2 , a 3 , a 4 все начинаются с 0, поэтому декодер должен считать следующий символ. Он равен 1, но коды для a 2 и a 3 оба имеют в начале 01. Поэтому декодер не знает, как действовать дальше: декодировать строку как 1|010|01…, то есть a 1 a 3 a 2 …, или как 1|01|001…, то есть a 1 a 2 a 4 .... Дальнейшие биты последовательности не могут исправить положения. Поэтому Код­ _1 является двусмысленным. От этого недостатка свободен Код _2.

Код _2 обладает так называемым префиксным свойством, которое можно сформулировать так: если некоторая последовательность битов выбрана в качестве кода какого-либо символа, то ни один код какого-либо другого символа не должен иметь в начале эту последовательность (код символа не может быть префиксом кода другого символа). Если строка 01 является кодом для a 2 , то другие коды не должны начинаться с 01. Поэтому коды для a 3 и a 4 должны начинаться с 00. Естественно для этого выбрать 000 и 001.

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

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

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

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

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

Условно переменные разделим на входные (то, что дано), выходные (результат: то, что нужно получить) и промежуточные, необходимые в процессе вычислений. Например, для программы вычисления наибольшего общего делителя (алгоритм Евклида), входные переменные m и n, промежуточная переменная r. Выходная переменная тоже n. Эти переменные должны иметь тип «натуральные числа». Но такого типа в Паскале нет. Поэтому придется использовать какой-то целый тип. От размера типа зависит диапазон чисел, для которых можно использовать программу. Если описать переменные так:

то самым большим числом на входе можно взять 32767 = 2 16 – 1.

Важно! Значение переменных, описанных в разделе Var , не определено. Иногда можно встретить определение переменной как ячейки памяти, в которой содержится значение переменной. Подразумевается, что описание переменной связывает адрес этой ячейки с именем переменной, то есть имя используется как адрес ячейки памяти, где содержится значение. Но само значение еще не определено.

В алгоритме Евклида значение остатка r сравнивается с нулем. 0 – целая константа. Можно (но не обязательно) определить константу со значением 0, например, так:

В процессе компиляции в тексте программы идентификатор Zero будет заменен своим числовым значением.

Тип константы Zero не очевиден. Ноль есть в любом целочисленном типе. В разделе констант можно описать типизированную константу, указав и тип и значение:

Zero: integer = 0;

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

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

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

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

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

Таблица 3.1

Буква

Как видно из этого примера и табл. 3.1, чаще встре­чающиеся буквы имеют более короткий код.

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

А как быть с компьютерной кодировкой, где исполь­зуется двоичный алфавит? Одним из простейших, но весьма эффективных способов построения кодов разной длины, не требующих специального разделителя, явля­ется алгоритм Д.Хаффмена (D.A. Huffman, 1952 г.). С помощью этого алгоритма строится двоичное дерево, которое позволяет однозначно декодировать двоичный код, состоящий из символьных кодов различной длины. Двоичным называется дерево, из каждой вершины ко­торого выходят две ветви. На рис. 3.2 приведен при­мер такого дерева, постро­енного для алфавита англий­ского языка с учетом часто­ты встречаемости его букв. Полученные, таким обра­зом, коды можно свести в таблицу.

Таблица 3.2

Буква	Код Хаффмена

С помощью табл. 3.2 легко кодировать текст. Так, например, строка из 29 знаков

WENEEDMOR ESNOWFORBE TTERSKIING преобразуется в код: 011101 100 1100 100 100 110110001111101011100 ОНО 1100 1110 011101 01001 1110 1011 011100 100 001001 100 10110110 110100011 1010 1010 1100 00001, который при размещении его в памяти побайтно при­мет вид:

01110110 01100100 10011011 00011111 01011100 01101100 11100111 01010011 11010110 1110010000100110 01011011 01101000 11101010 10110000 001

Таким образом, текст, занимающий в кодировке ASCII 29 байт, в кодировке Хаффмена займет только 16 байт.

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

Нетрудно догадаться, что изображенное дерево пред­ставляет собой сокращенный вариант кода Хаффмена. В полном объеме в нем должны быть учтены все возмож­ные символы, встречающиеся в тексте: пробелы, знаки препинания, скобки и др.

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

Коротко о главном

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

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

Алгоритм сжатия по Хаффмену представляется в виде двоичного дерева.

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

Вопросы и задания

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

За счет чего коды переменной длины позволяют "сжимать" текст?

Закодируйте с помощью ASCII-кодов и кодов Хафф­мена следующий текст: HAPPYNEWYEAR. Подсчитай­те в обоих случаях требуемый объем памяти.

4. Раскодируйте с помощью двоичного дерева (см.рисунок) следующий код:

11110111 10111100 00011100 00101100 10010011 01110100 11001111 11101101 001100

Двоичное дерево алфавита английского языка, используемое для кодирования методом Хаффмена