- •Тема 1. Информация, информатика и информационная технология лекция 1.3. Информатика и информационная технология
- •История развития информатики
- •Понятие информационной технологии и новой информационной технологии.
- •Информационный ресурс и его составляющие
- •Виды информационных процессов.
- •Тема 1. Информация, информатика и информационная технология лекция 1.1. Понятие информации и её измерение
- •Понятия информации, сообщения и данных
- •Меры количества информации
- •Качество информации
- •Тема 3. Информационно-логические основы построения эвм лекция 3.1. Позиционные системы счисления
- •Основные понятия систем счисления
- •Представление целых неотрицательных чисел
- •Перевод целых чисел
- •Представление дробных чисел
- •Перевод дробных чисел
- •Арифметические действия над числами
- •Представление отрицательных двоичных чисел.
- •Тема 3. Информационно-логические основы построения эвм лекция 3.2. Представление информации в эвм
- •Представление символьной информации
- •ФорМы записи чисел
- •2.1. Естественная форма
- •2.2. Нормальная форма
- •Форматы Представления чисел
- •3.1. Формат с фиксированной точкой
- •3.2. Формат с плавающей точкой
- •3.3. Двоично-десятичный код
- •Выполнение арифметических операций с числами с фиксированной и плавающей запятой
- •4.1. Действия над числами, представленными в естественной форме (с фиксированной запятой)
- •4.2. Действия над числами, представленными в нормальной форме (c плавающей запятой)
- •Тема 1. Информация, информатика и информационная технология лекция 1.2. Виды и характеристики сигналов
- •Понятие сигнала.
- •Классификация линий связи.
- •Виды сигналов.
- •Тема 2. Каналы передачи данных и их характеристики лекция 2.2. Синхронизация данных и характеристики каналов связи
- •Синхронный способ передачи данных
- •Асинхронная передача данных
- •Характеристики каналов связи
- •Тема 2. Каналы передачи данных и их характеристики лекция 2.2. Синхронизация данных и характеристики каналов связи
- •Синхронный способ передачи данных
- •Асинхронная передача данных
- •Характеристики каналов связи
- •Тема 2. Каналы передачи данных и их характеристики лекция 2.3. Модуляция и спектры сигналов
- •Аналоговые каналы для передачи цифровой информации
- •Амплитудная модуляция
- •Фазовая модуляция
- •Тема 6. Помехоустойчивое кодирование.
- •Общие принципы использования избыточности для обеспечения помехоустойчивости кодов.
- •Связь обнаруживающей и корректирующей способности кода с кодовым расстоянием.
- •Избыточность кода.
- •Краткая характеристика блоковых и непрерывных кодов.
- •Тема 4. Функциональная и структурная организация эвм лекция 4.1. Функциональные части персональной эвм. Микропроцессор
- •Структура персонального компьютера
- •Системный интерфейс
- •Микропроцессор (мп).
- •2.1. Структура микропроцессора
- •2.2. Микропроцессоры фирмы Intel
- •Тема 3. Информационно-логические основы построения эвм лекция 3.4. Программное управление эвм
- •Понятие и свойства алгоритма
- •Структура команд
- •Виды машинных команд
- •Понятие архитектуры и структуры эвм
- •Работа процессора эвм
- •Тема 5. Внешние устройства эвм лекция 5.2. Устройства ввода информации (уви)
- •Классификация устройств ввода информации
- •Устройства ручного ввода текста
- •2.1. Конструкция клавиатуры
- •2.2. Алгоритм формирования символа на дисплее
- •2.3. Подключение клавиатуры
- •Устройства автоматического ввода текста
- •3.1. Магнитный и оптический способы восприятия текста
- •3.2. Систематизация средств автоматического чтения письменных знаков.
- •3.3. Принципы автоматического чтения текстовой информации
- •Координатные манипуляторы
- •4.1. Мыши
- •4.2. Трекбол, или перевернутая мышь
- •4.3. Джойстики
- •4.4. Световое перо
- •Устройства ввода графической информации (увги)
- •5.1. Дигитайзеры
- •5.2. Видеодигитайзеры
- •Сканеры
- •6.1. Общие положения
- •6.2. Типы обрабатываемых изображений
- •6.3. Растровые файлы стали меньше.
- •6.4. Аппаратные и программные интерфейсы.
- •6.5. Принципы работы сканера.
- •6.6. Основные типы конструкций сканеров.
- •6.7. Качество изображения
- •6.8. Интеллектуальность сканера
- •Тема 5. Внешние устройства эвм лекция 5.1. Внешняя память персональной эвм
- •Общая характеристика внешней памяти
- •Организация данных на устройствах с прямым и последовательным доступом
- •Основные характеристики взу
- •Магнитные диски
- •4.1. Логическая структура
- •4.2. Накопители на гибких магнитных дисках
- •4.3. Накопители на жестких магнитных дисках
- •Накопители на оптических дисках
Тема 6. Помехоустойчивое кодирование.
Общие принципы использования избыточности для обеспечения помехоустойчивости кодов.
Для обеспечения высокой достоверности передачи информации по каналу с помехами применяют помехоустойчивое кодирование.
Помехоустойчивые коды должны обеспечивать как обнаружение, так и исправление ошибок (корректирующие коды), т.е. кодирование должно осуществляться так, чтобы сигнал, соответствующий последовательности символов, после воздействия на него предполагаемой в канале помехи оставался ближе к сигналу, соответствующему конкретной переданной последовательности символов, чем к сигналам, соответствующим другим возможным последовательностям. Степень близости обычно определяется по числу разрядов, в которых последовательности отличаются друг от друга.
Это достигается ценой введения при кодировании избыточности (избыточных, дополнительных символов), которая позволяет так выбрать передаваемые последовательности символов, чтобы они удовлетворяли дополнительным условиям, проверка которых на приемной стороне дает возможность обнаружить и исправить ошибки.
Начнем эту серьезную тему со старого анекдота. Беседуют два пенсионера:
-Вы не могли бы сказать номер вашего телефона? – говорит один.
-Вы знаете, признается другой, - я, к сожалению, точно его не помню.
-Какая жалость, сокрушается первый, - ну скажите хотя бы приблизительно…
Действительно, просьба поражает своей нелепостью. Совершенно очевидно, что в 6-значном наборе цифр достаточно ошибиться в одном символе, чтобы остальная информация стала абсолютно бесполезной. Однако представим себе, что тот же самый телефон написан словами русского языка и, скажем, при передаче этого текста часть букв потеряна.
Рассмотрим например телефонный номер 34-33-44. Соответственно запись «трицть четре трцать три сорк чтре», в которой имеется не один, а несколько пропущенных символов, по-прежнему легко читается. Это связано с тем, наш язык имеет определенную избыточность, которая с одной стороны, увеличивает длину записи, а с другой – повышает надежность ее передачи. Это же свойство обеспечивает надежное общение людей даже при наличии у них дефектов речи. Объясняется это тем, что вероятность появления каждого последующего символа в цифровой записи телефона одинакова, в то время как в тексте, записанном словами русского языка, это не так. Очевидно, например, что твёрдый знак в русском языке появляется значительно реже, чем, например, буква «а». (Наиболее вероятно появление в русском языке буквы «о» p=0,096, наименее вероятно – буква «ф» p=0,002) Более того, некоторые сочетания букв более вероятны, чем другие, а такие, как два твердых знака подряд, невозможны в принципе, и т.д. Зная, какова вероятность появления какой-либо буквы в тексте, и сравнив её с максимальной, можно установить, насколько экономичен или избыточен данный способ кодирования (в нашем случае русский язык).
Мы уже знаем, что количество информации в сообщении тем больше, чем больше его неопределенность (энтропия). Для любой системы кодирования можно оценить её максимально возможную энтропию (информационную ёмкость) Hmax , которая соответствует случаю равновероятности появления символов в коде и равна, как вы уже знаете, , где N – объём алфавита символов кода. Для русского языка Hmax = 5 (если буквы е и ё неразличимы). Также можно определить действительную энтропию H. Для русского языка H 1,5 бит. Случай H < Hmax означает, что каждый символ (в русском языке буква) несет меньше информации, чем максимально возможно. Это явление называют избыточностью R (или редунданцией - redundancy) и вычисляют как отношение:
Измерение избыточности естественных языков дает потрясающие результаты: она составляет 80%, а это свидетельствует о том, что практически 80% передаваемой с помощью языка информации является избыточной, т.е. лишней. Любопытен и тот факт, что показатели избыточности разных языков очень близки. Данная цифра примерно определяет теоретический предел сжатия текстовых файлов.
Факт избыточности свидетельствует с одной стороны о возможности перехода к системе кодирования, которая уменьшила бы избыточность передаваемого сообщения, что в свою очередь уменьшит размер сообщения и длительность его передачи (коды сжатия, эффективные коды). С другой стороны использование избыточных сообщений, т.е. сообщений подчиняющихся априорно известным ограничениям (условиям, правилам) позволяет обнаружить и исправить ошибки передачи, которые приводят к нарушению этих ограничений. Следовательно наличие избыточности способствует повышению помехоустойчивости сообщений.
Все помехоустойчивые коды можно разделить на два типа:
обнаруживающие (проверочные EDC – Error Detection Code);
корректирующие (ECC – Error Correction Code).
У подавляющего большинства существующих в настоящее время помехоустойчивых кодов избыточность является следствием их алгебраической структуры. В связи с этим их называют алгебраическими кодами. Алгебраические коды можно подразделить на два больших класса: блоковые и непрерывные.
В случае блоковых кодов процедура кодирования заключается в сопоставлении каждой букве сообщения (или, что чаще, последовательности из k двоичных символов, соответствующих этой букве) блока из n двоичных символов. Блоковый код называют равномерным, если n остается постоянным для всех букв сообщения. Отношение k/n определяют как относительную скорость кода.
Различают разделимые и неразделимые блоковые коды. При кодировании разделимыми кодами выходные последовательности состоят из символов, роль которых может быть четко разграничена. Это, во-первых, k информационных символов, совпадающих с символами последовательности, поступающей на вход кодера, во-вторых, (n-k) избыточных (проверочных) символов, вводимых в исходную последовательность кодером, и служащих для обнаружения и исправления ошибок.
При кодировании неразделимыми кодами разделить символы выходной последовательности на информационные и проверочные невозможно.
Непрерывными (древовидными) называют такие коды, в которых введение избыточных символов в кодируемую последовательность информационных символов осуществляется непрерывно, без разделения ее на независимые блоки.
Рассмотрим принципы использования избыточности для обнаружения ошибок. Пусть на вход кодера поступает последовательность из k информационных двоичных символов. На выходе ей соответствует последовательность из n двоичных символов, причем n>k.
Всего может быть 2k различных входных и 2n различных выходных последовательностей. Из общего числа 2n выходных последовательностей только 2k последовательностей соответствуют входным. Назовем их разрешенными кодовыми комбинациями. Остальные 2n-2k возможные выходные последовательности для передачи не используются. Они могут возникнуть лишь в результате ошибки передачи. Назовем их запрещенными комбинациями.
Каждая из 2k разрешенных комбинаций в результате действия помех может трансформироваться в любую другую, всего имеется 2k2n возможных случаев передачи. В это число входят (рис. 6.1.):
2k случаев безошибочной передачи ( );
2k(2k-1) случаев перехода в другие разрешенные комбинации, что соответствует необнаруживаемым ошибкам ( );
2k(2n-2k) случаев перехода в неразрешенные комбинации, которые могут быть обнаружены ( ).
С ледовательно, часть обнаруживаемых ошибочных кодовых комбинаций от общего числа возможных случаев передачи составляет:
Рис. 6.1. Трансформация передаваемых кодовых комбинаций.
Рассмотрим теперь случай исправления ошибок.
Л юбой метод помехоустойчивого кодирования можно рассматривать как правило разбиения всего множества запрещенных кодовых комбинаций на 2k непересекающихся подмножеств Mi, каждое из которых ставится в соответствие одной из разрешенных комбинаций. При получении запрещенной комбинации, принадлежащей подмножеству Mi, принимается решение, что передавалась разрешенная комбинация Ai. Ошибка будет исправлена в тех случаях, когда полученная комбинация действительно образовалась из Ai, т.е. в (2n-2k) случаях. Т.е. отношение числа исправляемых кодом ошибочных кодовых комбинаций к числу обнаруживаемых ошибочных комбинаций равно:
Способ разбиения на подмножества зависит от того, какие ошибки должны исправляться данным конкретным кодом.
Большинство разработанных до настоящего времени кодов предназначено для корректирования взаимно-независимых ошибок определенной кратности и пачек (пакетов) ошибок.
Взаимно-независимыми ошибками будем называть такие искажения в передаваемой последовательности символов, при которых вероятность появления любой комбинации искаженных символов зависит только от числа искаженных символов r и вероятности искажения одного символа p. Эти ошибки чаще всего вызываются флуктуационными помехами.
Кратностью ошибки называют количество искаженных символов в кодовой комбинации. Наиболее вероятны ошибки меньшей кратности. Их и следует обнаруживать и исправлять в первую очередь.
При взаимно-независимых ошибках вероятность искажения любых r символов в n-разрядной кодовой комбинации
где количество способов, которыми можно выбрать из n элементов r (число сочетаний из n по r)