- •«Калининградский государственный технический университет»
- •230100.62 «Информатика и вычислительная техника» и
- •230700.62 «Прикладная информатика»
- •Оглавление
- •Введение
- •1. Основные понятия информатики и информации
- •1.1. Информатизация общества
- •1.2. Понятие информатики
- •1.3. Понятие и характерные черты информации
- •1.4. Классификация информации
- •1.5. Свойства информации
- •2. Кодирование информации
- •2.1. Виды сигнала как материального носителя информации
- •2.2. Преобразования сигнала
- •2.3. Системы счисления
- •2.4. Правила перевода чисел
- •2.4.1. Правила перевода целых чисел
- •2.4.2. Правила перевода правильных дробей
- •2.4.3. Правило перевода неправильных дробей
- •2.5. Правила выполнения простейших арифметических действий
- •2.6. Кодирование дискретного сигнала
- •2.7. Кодирование по образцу
- •2.7.1. Прямые коды
- •2.7.2.Ascii-коды
- •2.7.3. Коды, учитывающие частоту информационных элементов
- •2.7.4. Коды Грея
- •2.8. Криптографическое кодирование
- •2.8.1. Метод простой подстановки
- •2.8.2. Метод Виженера
- •2.9. Эффективное кодирование
- •2.9.1. Универсальные методы
- •2.9.1.1. Метод Шеннона-Фано
- •2.9.1.2. Метод Хаффмена
- •2.9.1.3. Повышение эффективности кодирования универсальными кодами
- •2.9.1.4. Декодирование эффективных кодов
- •2.9.2. Специальные методы эффективного кодирования
- •2.9.2.1. Методы эффективного кодирования числовых последовательностей
- •2.9.2.2. Методы эффективного кодирования словарей
- •Основной вспомогательный
- •2.9.2.3. Методы эффективного кодирования естественно-языковых текстов
- •2.10. Помехозащитное кодирование
- •2.10.1. Искажение кодовых комбинаций
- •2.10.2. Кодовое расстояние и корректирующая способность кода
- •2.10.3. Коды, исправляющие ошибки
- •3. Измерение дискретного сигнала
- •3.1. Структурный подход к измерению информации
- •3.1.1. Геометрическая мера
- •3.1.2. Комбинаторная мера
- •3.1.3. Аддитивная мера
- •3.2. Статистический подход к измерению информации
- •3.3. Семантический подход к измерению информации
- •3.3.1. Целесообразность информации
- •3.3.2. Полезность информации
- •3.3.3. Истинность информации
- •3.4. Качество информации
- •Технические средства информатики
- •4.1. Структура компьютера и принципы его функционирования
- •4.2. Виды современных компьютеров
- •4.3. Структурные элементы компьютера
- •4.3.1. Память
- •4.3.1.1. Внутренняя память
- •4.3.1.2. Внешняя память
- •4.3.2. Устройство управления
- •4.3.3. Арифметико-логическое устройство
- •4.3.3.1. Формы представления целых чисел
- •4.3.3.2. Формы представления вещественных чисел
- •4.3.3.3. Коды представления числовых данных
- •4.3.3.4. Принципы выполнения арифметической операции сложения
- •Приложение 1. Положения комбинаторики, используемые в измерении информации
2.2. Преобразования сигнала
Для преобразования аналогового сигнала в дискретный используется процедура, которая называется квантованием. Она включает два последовательных этапа: квантование по времени и квантование по уровню (дискретизацию).
Квантование по времени – замена непрерывной (по времени и по уровню) функции x(t) (рис. 2.1а) некоторым множеством непрерывных (по уровню) функций x(ti) (на рис. 2.1б i = {1,2,3,4}).
x x
x(t3) x(t3)
x(t2) x(t4) x(t2) x(t4)
x(t1) x(t1)
x(t)
t1 t2 t3 t4 t t1 t2 t3 t4 t
а) б)
Рис. 2.1. Иллюстрация к квантованию по времени:
а) аналоговый сигнал x(t) до квантования;
б) дискретный (по времени) сигнал x(t) – результат квантования.
Очевидно, дискретизация связана с потерей информации. В самом деле, дискретный сигнал на рис. 2.1б не показывает, как ведет себя исходный сигнал в моменты времени, например, между t3и t4. Иначе говоря, дискретизация связана с некоторой погрешностью, которая зависит от шага дискретизацииt = ti– ti-1: при малых значениях шага дискретизации число точек замера высоко, и теряется мало информации; очевидно, картина обратная при больших шагах дискретизации. Погрешность дискретизациив каждый момент времени t определяется по формуле:
(t) = x(t) – v(t),
где v(t) – функция восстановления, которая по дискретным значениям восстанавливает x(t).
Виды дискретизации различаются по регулярности отсчетов:
равномерная дискретизация, когда t постоянно;
неравномерная дискретизация, когда t переменно, причем этот вид, в свою очередь, делится на подвиды:
адаптивную, когда t меняется автоматически в зависимости от текущего изменения сигнала. Это позволяет увеличивать шаг дискретизации, когда изменения сигналаx(t) незначительны, и уменьшать – в противном случае;
программируемую, когда t изменяется оператором или в соответствии с заранее выставленными условиями, например, в фиксированные моменты времени.
Квантование по уровню- преобразование непрерывных (по уровню) сигналовx(ti) в моменты отсчета tiв дискретные. В результате непрерывное множество значений сигналаx(ti) в диапазоне отxmin до xmax преобразуется в дискретное множество значенийxk – уровней квантования (рис. 2.2). Шаг квантованияxопределяется по формуле:x=xj – xj-1.
Можно сказать, что квантование по уровню – это измерение сигнала. Введем на оси ординат мерную шкалу и спроецируем на нее сигналы x(ti) (рис. 2.2б).
6 5 4 3 2 1 0
x(t3) x(t3)
x(t2) x(t4) x(t2) x(t4)
x(t1) x(t1)
t1 t2 t3 t4 t t1 t2 t3 t4 t
а) б)
Рис. 2.2. Иллюстрация к квантованию по уровню:
а) аналоговые по уровню (но дискретные по времени) сигналы x(ti) до квантования;
б) квантованные по уровню (измеренные) сигналы x(ti).
Видно, что сигнал x(t1) составляет 3 уровня квантования, сигналx(t3) – 6 уровней,x(t4) – 5 уровней квантования. В то же время сигналx(t2) попадает в промежуток между 4 и 5 и не может быть однозначно измерен. В таком случае поступают одним из следующих способов:
x(ti) отождествляют с ближайшим значением (в нашем примере – с 4), тогда в результате процедуры квантования формируется одномерный массив {3,4,6,5};
x(ti) отождествляют с ближайшим меньшим (или большим) значением. Тогда при отождествлении с ближайшим большим значением сигналx(t2) отождествится с 5 независимо от того, насколько близко он к этому уровню квантования находится. При отождествлении с ближайшим меньшим значением сигналx(t2) отождествится с 4 также независимо от того, насколько близко он к этому уровню квантования находится. В первом случае сформируется массив {3,5,6,5}, во втором - {3,4,6,5}.
Очевидно, и при квантовании по уровню возникает погрешность квантования (xk):
(xk) =x(ti) -xk.
Погрешность квантования по уровню тем меньше, чем меньше шаг квантования.
Виды квантования по уровню:
равномерное, когда диапазон изменения сигнала разбивается на m одинаковых частей. Тогда, зная размер шага квантования, для представления xkдостаточно знать число k.
неравномерное, когда диапазон изменения сигнала разбивается на m различных частей.