- •Балтийский федеральный университет имени Иммануила Канта
- •Расчетно-графическая работа №1 Тема: «Системы счисления».
- •Теоретическая часть
- •Виды сигнала
- •Преобразования сигнала
- •Системы счисления
- •Правила перевода чисел из одной системы счисления в другую
- •Правила перевода целых чисел
- •Правила перевода правильных дробей
- •Правила выполнения простейших арифметических действий
- •Правила сложения
- •Правила вычитания
- •Правила умножения
- •Правила деления
- •Задание
- •Содержание отчета
- •Варианты задания
- •Список литературы
- •Расчетно-графическая работа №2
- •Теоретическая часть
- •Аддитивная (логарифмическая) мера (структурный подход)
- •1.2 Статистический подход к измерению информации
- •Примеры решения задач
- •Задание
- •Содержание отчета
- •Варианты задания
- •Список литературы
- •Расчетно-графическая работа №3
- •Теоретическая часть
- •Кодирование
- •Эффективное кодирование
- •Метод Шеннона-Фано
- •Метод Хаффмана
- •Примеры решения задач
- •Задание
- •Содержание отчета
- •Расчетно-графическая работа №4 Тема: «Разработка формальной грамматики Хомского».
- •1.2 Пример построения грамматики
- •1.3 Представление грамматики в виде графа
- •1.5 Классификация формальных грамматик
- •Примеры решения задач
- •Задание
- •Содержание отчета
- •Варианты задания
- •Список литературы
- •Расчетно-графическая работа №5 Тема: «Нормальные алгоритмы Маркова и машины Тьюринга».
- •Теоретическая часть
- •Нормальные алгоритмы Маркова
- •Машина Тьюринга
- •Примеры задач
- •Задание
- •Содержание отчета
- •Варианты задания
- •Список литературы
- •Расчетно-графическая работа №6 Тема: «Расчет числовых характеристик графов».
- •Теоретическая часть
- •Решение задач
- •Задание
- •Содержание отчета
- •Список литературы
- •Расчетно-графическая работа №7 Тема: «Нахождение кратчайшего остова неориентированного графа по алгоритму Дейкстра».
- •Теоретическая часть
- •Примеры решения задач
- •Задание
- •Содержание отчета
- •Список литературы
- •Расчетно-графическая работа №8 Тема: «Поиск кратчайших путей на неориентированном графе по алгоритму Флойда».
- •Теоретическая часть
- •Задание
- •Содержание отчета
- •Список литературы
- •Расчетно-графическая работа №9 Тема: «Архивирование файлов алгоритмом Зива-Лемпеля-Велча».
- •Теоретическая часть
- •Примеры решения задачи сжатия сообщений
- •Задание
- •Содержание отчета
- •Список литературы
Преобразования сигнала
Для преобразования аналогового сигнала в дискретный используется процедура, которая называется квантованием. Различают два вида квантования – по времени и по уровню (дискретизацию).
Квантование по времени – замена непрерывной (по времени и по уровню) функции x(t) (рис. 4.1а) некоторым множеством непрерывных (по уровню) функций x(ti) (на рис. 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
а) б)
Рис. 4.1. Иллюстрация к квантованию по времени:
а) аналоговый сигнал x(t) до квантования;
б) дискретный (по времени) сигнал x(t) – результат квантования.
Очевидно, дискретизация связана с потерей информации. В самом деле, дискретный сигнал на рис. 1б не показывает, как ведет себя исходный сигнал в моменты времени, например, между t3 и t4. Иначе говоря, дискретизация связана с некоторой погрешностью , которая зависит от шага дискретизации t = ti – ti-1: при малых значениях шага дискретизации число точек замера высоко, и теряется мало информации; очевидно, картина обратная при больших шагах дискретизации. Погрешность дискретизации в каждый момент времени t определяется по формуле:
(t) = x(t) – v(t), (1.1)
где v(t) – функция восстановления, которая по дискретным значениям восстанавливает x(t).
Виды дискретизации различаются по регулярности отсчетов:
равномерная дискретизация, когда t постоянно;
неравномерная дискретизация, когда t переменно, причем этот вид, в свою очередь, делится на подвиды:
адаптивную, когда t меняется автоматически в зависимости от текущего изменения сигнала. Это позволяет увеличивать шаг дискретизации, когда изменения сигнала x(t) незначительны, и уменьшать – в противном случае;
программируемую, когда t изменяется оператором или в соответствии с заранее выставленными условиями, например, в фиксированные моменты времени.
Квантование по уровню - преобразование непрерывных (по уровню) сигналов x(ti) в моменты отсчета ti в дискретные. В результате непрерывное множество значений сигнала x(ti) в диапазоне от xmin до xmax преобразуется в дискретное множество значений xk – уровней квантования (рис. 4.2). Шаг квантования x определяется по формуле:
x = xj – xj-1 .
Можно сказать, что квантование по уровню – это измерение сигнала. В самом деле, по рис. 4.2б видно, что сигнал x(t1) составляет 0 уровней квантования (k = 0), а сигнал x(t4) – 2 уровня квантования (k = 2).
x(t) x(t)
x2
x
x1
xmin
x(t1) x(t1)
t1 t2 t3 t4 t t1 t2 t3 t4 t
а) б)
Рис. 4.2. Иллюстрация к квантованию по уровню:
а) аналоговые по уровню (но дискретные по времени) сигналы x(ti) до квантования;
б) квантованные по уровню сигналы x(ti).
При квантовании по уровню не всегда сигнал x(ti) совпадает с уровнем квантования (см. сигнал x(t2) на рис. 4.2б). В таком случае поступают одним из следующих способов:
x(ti) отождествляют с ближайшим значением (в нашем примере – с x2);
x(ti) отождествляют с ближайшим меньшим (или большим) значением. Тогда при отождествлении с ближайшим большим значением сигнал x(t2) отождествится с x2 независимо от того, насколько близко он к этому уровню квантования находится. При отождествлении с ближайшим меньшим значением сигнал x(t2) отождествится с x1 также независимо от того, насколько близко он к этому уровню квантования находится.
Очевидно, и при квантовании по уровню возникает погрешность квантования (xk):
(xk) = x(ti) - xk. (1.2)
Погрешность квантования по уровню тем меньше, чем меньше шаг квантования.
Виды квантования по уровню:
равномерное, когда диапазон изменения сигнала разбивается на m одинаковых частей. Тогда, зная размер шага квантования, для представления xk достаточно знать число k.
неравномерное, когда диапазон изменения сигнала разбивается на m различных частей.