- •Федеральное агентство по образованию
- •1.2. Измерение информации
- •1.2.1. Структурные меры информации
- •1.2.2. Статистическая мера информации.
- •2. Кодирование информации
- •2.1. Контрольная работа – часть 1
- •2.1.1. Позиционные системы счисления
- •2.1.2. Смешанные системы счисления
- •2.1.3. Перевод числа из одной системы счисления в другую
- •2.1.4. Код Грея
- •2.1.5. Форма постановки задания
- •2.1.6. Рекомендации по решению задач
- •2.1.7. Примеры решения задач
- •2.1.8. Пример задания по контрольной работе – часть 1
- •2.2. Контрольная работа – часть 2
- •2.2.1. Избыточность сообщений
- •2.2.2. Теоретические основы эффективного кодирования
- •2.2.3. Построение эффективного кода по методам Шеннона-Фано и Хаффмена
- •2.2.4. Теоретические основы помехоустойчивого кодирования
- •2.2.5. Классификация помехоустойчивых кодов
- •2.2.6. Общие принципы использования избыточности при построении корректирующих кодов
- •2.2.7. Коды, обнаруживающие ошибки
- •2.2.8. Примеры решения задач
- •2.2.9. Пример задания по контрольной работе – часть 2
- •2.3. Контрольная работа – часть 3
- •Краткие теоретические сведения
- •2.3.1. Линейные коды, обнаруживающие и исправляющие ошибки
- •2.3.2. Построение двоичного линейного кода
- •2.3.3. Кодирование
- •2.3.4. Синдромный метод декодирования
- •2.3.5. Кодирующее и декодирующее устройства
- •2.3.6. Матричное представление линейных кодов
- •2.3.7. Циклические коды
- •2.3.8. Выбор образующего многочлена
- •2.3.9. Формирование разрешенных кодовых комбинаций
- •2.3.10. Декодирование циклических кодов
- •2.3.11. Схемы деления на образующий многочлен
- •2.3.12. Примеры решения задач
- •2.3.13. Пример задания по контрольной работе – часть 3
- •3. Оформление контрольной работы
- •3.1. Пример оформления отчета по контрольной работе
- •4. Варианты заданий
Федеральное агентство по образованию
ПСКОВСКИЙ ГОСУДАРСТВЕННЫЙ
ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ
А.И. Спиридонов
КОДИРОВАНИЕ ИНФОРМАЦИИ ЦИФРОВОЕ, ЭФФЕКТИВНОЕ И ПОМЕХОУСТОЙЧИВОЕ
Методические указания по выполнению контрольных работ для студентов заочной формы обучения специальностей
230101 «Вычислительные машины, комплексы, системы и сети»,
230201 «Информационные системы и технологии»
Рекомендовано к изданию научно-методическим советом Псковского государственного политехнического института
Псков, издательство ППИ
2010
СОДЕРЖАНИЕ
ВВЕДЕНИЕ 4
1.1. Понятия информации и сообщения 5
1.2. Измерение информации 6
2. Кодирование информации 9
2.1. Контрольная работа – часть 1 10
2.2. Контрольная работа – часть 2 21
2.3. Контрольная работа – часть 3 39
3. ОФОРМЛЕНИЕ КОНТРОЛЬНОЙ РАБОТЫ 68
4. ВАРИАНТЫ ЗАДАНИЙ 70
СПИСОК ЛИТЕРАТУРЫ 100
ВВЕДЕНИЕ
Теория кодирования является одним из разделов теории информации, изучающим способы отображения сообщений с помощью символов некоторого алфавита. Являясь составной частью теории информации, теория кодирования базируется на ее основных положениях, поэтому в настоящем методическом пособии сначала рассматриваются некоторые понятия теории информации, а затем вопросы кодирования.
1.1. Понятия информации и сообщения
Понятие информации
Информация наряду с материей и энергией является первичным понятием мира и поэтому в строгом смысле не может быть определена. Сам термин «информация» происходит от лат. «informatio» – разъяснение, осведомление.
Имеется множество определений понятия информации. В наиболее общем понимании информация есть отражение реального мира; это сведения, которые один реальный объект содержит о другом реальном объекте. В узком практическом понимании информация есть все сведения, представляющие интерес, подлежащие регистрации и обработке.
Понятие информации связано не с реальными вещами, а их моделями, отражающими сущность реальных вещей в той степени, в какой это необходимо для практических целей. В общем виде информация о различных природных явлениях и процессах может быть представлена в виде тех или иных полей. Математически такие поля описываются с помощью функций типа:
, (1.1)
где – физическая величина, характеризующая поле в момент временив точке пространства.
Если все величины, входящие в приведенное соотношение, могут принимать непрерывный ряд значений, измеряемых вещественными числами, то такую информацию называют непрерывной. Если же установить минимальные шаги измерения всех величин, характеризующих поле , то получим так называемое дискретное представление информации.
Практически точность любых измерений, как и человеческое восприятие, всегда ограничена, поэтому фактически, даже имея дело с непрерывной информацией, человек воспринимает ее в дискретном виде. Кроме того, любая непрерывная информация может быть аппроксимирована дискретной информацией с любой степенью точности, поэтому дискретную информацию можно считать универсальной формой ее представления.
Понятие сообщения
Информация, зафиксированная в определенной форме, называется сообщением. Как и информация, сообщения бывают непрерывными и дискретными.
Непрерывное сообщение– это некоторая физическая, чаще всего электрическая величина, принимающая любые значения в заданном интервале и изменяющаяся в произвольные моменты времени.
Дискретное сообщениепредставляет собой последовательность отдельных элементов, разграниченных во времени и выбранных из некоторого набора. Физическая природа этих элементов безразлична; важно лишь, чтобы набор элементов был конечным и фиксированным.
Набор, из которого выбирают элементы, слагающие дискретное сообщение, называют алфавитом, а сами элементы –буквами,знакамиилисимволами. Число различных букв в алфавите называют егообъемом.
Дискретные сообщения часто разбивают на отдельные блоки конечной длины. Такие блоки, по аналогии с обычным языком, называют словами.
Процесс описания смыслового содержания информации с помощью символов (букв) называется кодированием. Обратный процесс, т.е. выявление смыслового содержания информации в принятых символах, называютдекодированием.
При обработке информации часто возникает необходимость представлять буквы одного алфавита с большим объемом в другом алфавите с меньшим объемом. Операция перехода от первичного алфавита к вторичному также называется кодированием.
Поскольку объем вторичного алфавита меньше объема первичного, то каждому знаку первичного алфавита соответствует некоторая последовательность знаков вторичного алфавита, обычно называемая кодовой комбинацией. Число символов в кодовой комбинации называется еезначностью, а число ненулевых символов –весом. Операцию сопоставления кодовой комбинации соответствующего ей знака первичного алфавита также называют декодированием.
Для того чтобы потребитель информации мог распознать сообщение, т.е. отождествить символы с какими-либо объектами или процессами реального мира, он должен обладать определенными сведениями (алфавит, правило построения кода и т.п.).
Сведения, которыми располагает потребитель информации до ее получения и на знание которых рассчитывает отправитель, называют априорными(доопытными).
Сведения, которыми располагает потребитель после информационного обмена, называют апостериорными(послеопытными).