- •1. Понятие информатики
- •2. Понятие и характерные черты информации
- •Свойства информации
- •3. Виды сигнала как материального носителя информации
- •Преобразования сигнала
- •4. Системы счисления
- •5. Правила перевода чисел
- •Правила перевода целых чисел
- •Правила перевода правильных дробей
- •Правило перевода неправильных дробей
- •6. Кодирование по образцу
- •0001011101000011
- •0010 0000 0001 0010
- •2 0 1 2
- •00010100
- •Ascii-коды
- •Коды, учитывающие частоту информационных элементов
- •Коды Грея
- •7. Криптографическое кодирование
- •Метод простой подстановки
- •Метод Виженера
- •8. Эффективное кодирование
- •Универсальные методы
- •Метод Шеннона-Фано
- •Метод Хаффмена
- •9. Повышение эффективности кодирования универсальными кодами
- •Декодирование эффективных кодов
- •10. Специальные методы эффективного кодирования
- •Методы эффективного кодирования числовых последовательностей
- •2 14 18 27 34
- •2 12 4 9 7.
- •55556666888888
- •5(4)6(4)8(6),
- •Методы эффективного кодирования словарей
- •Методы эффективного кодирования естественно-языковых текстов
- •11. Помехозащитное кодирование
- •Искажение кодовых комбинаций
- •Кодовое расстояние и корректирующая способность кода
- •12. Коды, исправляющие ошибки
- •13. Измерение дискретного сигнала
- •Структурный подход к измерению информации
- •Геометрическая мера
- •Комбинаторная мера
- •Аддитивная мера
- •14. Статистический подход к измерению информации
- •Семантический подход к измерению информации
- •Полезность информации
- •Истинность информации
- •15. Структура компьютера и принципы его функционирования
- •16. Устройство управления
- •17. Арифметико-логическое устройство
- •18.Формы представления целых чисел
- •Формы представления вещественных чисел
- •Коды представления числовых данных
- •19.При сложении целых чисел последовательность шагов следующая:
- •20.Правило сложения вещественных чисел.
Преобразования сигнала
Для преобразования аналогового сигнала в дискретный используется процедура, которая называется квантованием. Она включает два последовательных этапа: квантование по времени и квантование по уровню (дискретизацию).
Квантование по времени – замена непрерывной (по времени и по уровню) функции 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 различных частей.