Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

2333

.pdf
Скачиваний:
0
Добавлен:
03.06.2019
Размер:
789.8 Кб
Скачать

Дискретизация непрерывных сигналов. Общие принципы дискретизации и восстановления сигналов? Равномерная дискретизация сигналов. Математическая модель дискретного сигнала. Спектр

реализации импульсной модуляции с целью передачи сигнало

алгоритмов обработки информации. Сущность дискретизации – замена непрерывного сигнала последовательностью импульсов. В общем случае амплитуды импульсов можно задать соотношение с помощью дискретных весовых функций: Восстановление функции ( ) по ее дискретным координатам осуществляется с помощью системы базисных функций Чаще всего весовые и базисные функции выбирают одинаковыми: ( ) ( ) В виду сложности определения { ( )} чаще всего используют методы дискретизации, при котором сигнал заменяют совокупностью его мгновенных значений – отсчетов ( )→ ( ). Роль весовых функций в этом случае играют функции Дирака. ( ) ( − )Δ – шаг дискретизации, может быть неравномерным. При этом: ( ). Восстановление непрерывного сигнала { ( )} базисные функции. Среди неортогональных базисов чаще всего используют степенные полиномы: ( )̂ Σ Если значения аппроксимируемого полинома ( )̂ совпадают со значениями сигналов в точках отсчетов (интерполяция), то используют полиномы Лежандра. Для реализации необходима процедура сдвига на такт дискретизации (задержки). При восстановлении методов экстраполяции используют члены ряда Тейлора. Спектр дискретного сигнала ( ) аналоговый сигнал с ограниченным спектром, т.е. с конечным и компактным ( ) (Фурье образом). Производится процедура

равномерной дискретизации

с

шагом

 

(частотой

 

).

Математическая модель

дискретизированного сигнала: Δ( )

( )∙ШΔ( )

( )∙Σ ( −

)∞

−∞ Σ (

) ( −

)∞

−∞ ШΔ( ) –

гребневая функция –

последовательность единичных импульсов с шагом

. Справка: Фурье образ

дискретной функции

число

импульсов

спектр Видно, что

спектр

дискретного

сигнала есть

непрерывная периодическая функция с периодом . Введем понятие центрального периода: – частота Найквисти (соответственно ). Центральный период функции ( ) называют главным частотным диапазоном. Интуитивно понятно, что если спектр главного диапазона дискретного сигнала совпадает со спектром аналогового сигнала (т.е. он содержит всю полезную информацию о сигнале), то по дискретному спектру в принципе можно точно восстановить исходный аналоговый сигнал. Для того чтобы дискретизация не меняла спектр в главном диапазоне необходимо, чтобы (смотрите рисунок выше). Интерполяционный ряд Котельникова Шеннона дискретного сигнала? Интерполяционный ряд Котельникова Шеннона Спектр дискретного сигнала представляет собой сумму сдвинутых копий спектров аналогового сигнала с шагом сдвига, равным частоте дискретизации. Если спектры не перекрываются, то по центральной копии можно точно восстановить исходный сигнал. Покажем это. Имеем фуры обратной дискретной функции: ( ) ( )∙ Ш ( ) Умножим на Получим непрерывный спектр в ∞ пределах, равный ∙ ( ) в пределах главного частотного диапазона. Обратное преобразование Ф такого спектра должно давать конечный и непрерывный сигнал: имеем произведение функций. Заметим, что: Тогда: Следовательно, получен интерполяционный ряд Котельникова Шеннона. Из формулы следует, что если наибольшая частота в спектре аналогового сигнала ( ) не превышает частоты его дискретизации, то он без потери точности может быть восстановлен посредством ряда Котельникова Шеннона. Дискретная разностная динамическая модель линейной системы (фильтра)? Дискретное преобразование Ф Цифровая обработка сигналов оперирует с дискретно преобразованными сигналами и реализует дискретные алгоритмы. Математический аппарат дискретных преобразований подобен преобразованиям аналоговых сигналов, но имеет существенные отличия, не учет которых может приводить к значительным ошибкам. Дискретное преобразование Ф может быть получено непосредственно из интегральных преобразований Ф заменой интеграла на интегральные суммы. Сдвинутая копия оператора фильтра

приводит к периодизации ее спектра. → приводит к периодизации функции времени. Надо иметь в виду, что есть дискретизация непрерывного спектра ( ) дискретной функции ( ), дискретизация непрерывной функции ( ). И при восстановлении непрерывных функций по дискретным значениям (отсчетам) соответствия гарантированы только при выполнении условий теоремы Котельникова Шеннона. Для дискретных преобразований ( ) ( ) и функция и ее спектр дискретны и периодичны, а числовые массивы их представления соответствуют заданию на главных периодах , где– количество отсчетов, при этом: Выше приведенные условия являются условиями информационной равноценности динамических и частотных форм представления дискретных сигналов. Другими словами, число отсчетов функции и спектра функции этой должны быть одинаковыми. При реализации обработки массивов отсчетов часто принимают а преобразование Ф выполняют по (номер шага по частоте) на главных периодах. Для четных Для нечетных границы главного периода по частоте (± ) устанавливаются равными ДПФ дискретные преобразования Ф. В вычислительных операциях на ЭВМ для исключения отрицательных частотных аргументов ( ) и использования идентичных алгоритмов прямого и обратного преобразования Ф, главный период спектра принимается в интервале [ , , т.е. ( ≤ ≤ ), а суммируется производная от до ( − ). Для ДПФ справедливы все свойства интегральных преобразований Ф, но следует учитывать периодичность дискретных функций и спектров. Так произведению дискретных спектров будет соответствовать свертка периодезированых функций во времени и наоборот. Такая свертка называется циклической. БПФ. При вычислении ПФ среди множителей ( и ) есть много периодически повторяющихся значений. Алгоритм БПФ группирует слагаемые с одинаковыми множителями в пирамидальный алгоритм, что значит уменьшение числа операций. Пример . Нерекурсивные цифровые фильтры. Структурная схема. Разностная модель. Импульсная характеристика? Общие понятия. В одномерной дискретной линейной системе связь между входом и выходом (входной и выходной дискретными последовательностями значений сигнала – отсчетами), задается линейным оператором преобразования Это выражение отображает краткую запись линейного разностного уравнения: где ,

комплексные коэффициенты. Положим , что всегда может быть выполнено соответствующей

цифровых последовательностей значений сигналов, приведем его к виду: Оператор, представленный правой частью данного уравнения, получил название цифрового фильтра (ЦФ), а выполняемая им

операция

цифровой

фильтрации данных (информации, сигналов). Если хотя бы один из

коэффициентов или

зависит от переменной , то фильтр называется параметрическим, т.е. с

переменными параметрами. Ниже мы будем рассматривать фильтры с постоянными коэффициентами (инвариантные по аргументу). Основные достоинства цифровых фильтров по сравнению с

анал контроля и калибровки, т.к. их работоспособность не зависит от дестабилизирующих факторов

олько входных

большом диапазоне частот, для чего достаточно только изменять частоту дискретизации данных. Нерекурсивные фильтры. При нулевых значениях коэффициентов уравнение ( . . ) переходит в уравнение линейной дискретной ения выходных отсчетов свертки ( . . ) для любого аргумента определяются текущим и "прошлыми" значениями входных отсчетов. Такой фильтр называется

нерекурсивным цифровым фильтром (НЦФ). Интервал суммирования по получил название "окна"

фильтра. Окно фильтра составляет + отсчет, фильтр является односторонним каузальным, т.е. причинно обусловленным текущими и "прошлыми" значениями входного сигнала, и выходной сигнал не может опережать входного. Каузальный фильтр может быть реализован физически в реальном

масштабе времени. При

, а также при для фильтра ( . . ), проведение фильтрации возможно только

при задании начальных

условий для точек ( ),

, , … , Как правило, в качестве начальных условий

принимаются нулевые

значения, или продление отсчетов входных сигналов или его тренда по

распоряжении фильтра могут находиться как "прошлые", так и "будущие" значения входной последовательности отсчетов относительно текущей точки вычислений , при этом уравнение ( . . ) будет

НЦФ на единичный входной импульс (а равно и на любой произвольный входной сигнал) всегда конечна и ограничена размером окна фильтра, такие фильтры называют также фильтрами с конечной тличается от техники выполнения обычной дискретной свертки двух массивов данных. Для операции фильтрации

Ассоциативность: Фильтрация однозначно определяет выходной сигнал ( ) для установленного значения входного сигнала ( ) при известном значении импульсного отклика фильтра ( ). Рекурсивные цифровые фильтры. Разностная модель. Импульсная характеристика? Рекурсивные фильтры. Фильтры, которые описываются полным разностным уравнением ( . . ) принято называть рекурсивными цифровыми фильтрами (РЦФ), так как в вычислении текущих выходных значений участвуют не только входные данные, но и значения выходных данных фильтрации, вычисленные в предшествующих циклах расчетов. С учетом последнего фактора рекурсивные фильтры называют также фильтрами с обратной связью, положительной или отрицательной в зависимости от знака суммы коэффициентов am. Полное окно фильтра состоит из нерекурсивной части bn, ограниченной в работе текущими и "прошлыми" значениями входного сигнала (на ЭВМ возможно использование и “будущих” отсчетов сигнала) и рекурсивной части am, которая работает с "прошлыми" значениями выходного сигнала. Техника вычислений приведена на рис. . . . ИМПУЛЬСНАЯ РЕАКЦИЯ ФИЛЬТРОВ. Функция отклика. Если на вход нерекурсивного фильтра подать импульс Кронекера, расположенный в точке k 0, то на выходе фильтра мы получим его реакцию на единичный входной сигнал (формула . . ), которая определяется весовыми коэффициентами bn оператора фильтра: Для рекурсивных фильтров реакция на импульс Кронекера зависит как от коэффициентов bn фильтра, так и от коэффициентов обратной связи am. С использованием формулы ( . . ): Функция h(k), которая связывает вход и выход фильтра по реакции на единичный входной сигнал и однозначно определяется оператором преобразования фильтра, получила название импульсного отклика фильтра (функции отклика). Для рекурсивных фильтров длина импульсного отклика, в Рис. . . . Рекурсивный ЦФ. принципе, может быть бесконечной. Если произвольный сигнал на входе фильтра представить в виде линейной комбинации взвешенных импульсов Кронекера то сигнал на выходе фильтра можно рассматривать как суперпозицию запаздывающих импульсных реакций на входную последовательность взвешенных импульсов: Для нерекурсивных фильтров пределы суммирования в последнем выражении устанавливаются непосредственно по длине импульсного отклика 7- Информационное содержание сигналов. Статистические меры количества информации. Среднее количество информации. Частное количество информации? Информационные меры соответствуют трем основным направлениям в теории информации: a) Структурная теория информации рассматривает дискретное строение массивов информации и их измерение методом подсчета информационных элементов-квантов (дискретные

log ; - число квантов b) Статистическая теория информации оперирует мерами неопределенности сигналов, систем и их изменений в процессе преобразований. c) Семантическая теория учитывает ценность или существенность информации. Статистическая теория информации Статистическая теория информации рассматривает пространство дискретных сигналов с конечным множеством состояний. Пусть имеем преобразователь или канал связи. Графическая модель: В общем случае ≠ , но мы будем считать, чтоДля однозначного преобразования: → → … При наличии шумов возможны искажения сигналов, порождающие условные вероятности Математической моделью преобразователя канала может быть матрица: Для полного описания необходимо знать вероятность Для однозначного преобразования: Для оценки взаимосвязи статистических ансамблей и вводится мера → количество информации Шеннон предположил меру количества информации в паре ( , ) частное количество информации: с точностью до множителя Логарифмическая мера выбрана в связи с тем, что позволяет реализовать предположение, что количество информации от нескольких источников (независимых) обладает свойством аддитивности (например, символа в сигнале). Для однозначных преобразований: Для независимых Вывод, вытекающий из концепции определения количества информации: если полученное значение сигнала не зависит от значения входного сигнала, то Среднее количество информации ( , ) – вероятность появления – количество информации Случай однозначного преобразования Замечания: ( , ) может иметь любой знак. ( , )≥0. Докажем это. Учтем свойство Равенство при е. при отсутствии связи, что понятно. Что требовалось доказать. 8- Энтропия дискретных ансамблей сообщений. Свойства энтропии дискретных ансамблей сообщений. Условная энтропия дискретных ансамблей. Основные свойств?. Информационная энтропия Информационная энтропия – это мера разнообразия сигналов или состояния системы (разнообразие ≡ неопределенность).

ое сообщение имеет смысл,

-

передачи сообщения, будут тем больше, чем больше была неопределенность состояния системы. Аналогия с термодинамической энтропией: согласно второму закону термодинамики, энтропия замкнутой системы (Больцман): − Σ ln Где - общее число молекул, - число молекул со скоростями Частота событий: Тогда: Учитывая переход l Возвращаемся к энтропии ансамбля значений сигнала, принимаем: - совпадает со средним количеством информации при однозначном преобразовании сигнала. Теорема: ( ) имеет вид: ( ) − Σ log , Если требуется выполнение

объединения стат. зависимых событий определяется суммой энтропий, где энтропия каждой

количества невозможных состояний не изменяет энтропию системы. Энтропия равномерно распределенного сигнала Энтропия ансамбля значений сигнала не превышает энтропию равномерно распределенного сигнала. Для доказательства воспользуемся свойством: ln ≤ − Следовательно, имеем: Что требовалось доказать. Вывод: для того, чтобы иметь возможность передать тем же набором сигналов максимально возможную информацию, надо стремиться, чтобы значения сигналов были равновероятны. Основные свойства энтропии . Энтропия есть величина вещественная, ограниченная и неотрицательная . Энтропия равна нулю тогда и только тогда, когда все вероятности состояний, кроме одной, равны нулю, а эта единственная, соответственно, равна единице. . Энтропия максимальна, если все состояния системы или элементов сообщения равновероятны: 4. Энтропия объединения статистически независимых сообщений определяется суммой энтропий каждого сообщения (теорема сложения энтропий) Или в общем виде: Условная энтропия Условная энтропия ( , ) по определению есть энтропия, определенная при условии, что стали известны исходы (состояния)

, усредненные по этим исходам: Для фиксированного значения условная энтропия: - это есть

случайная величина, усредним ее по величине с вероятностями Смысл условной энтропии (

) состоит

в том, какую энтропию имеют (дают) сообщения , когда уже известна энтропия . Свойства

условной

энтропии . Если и статически независимы, то ( ) ( ) . Если и статистически четко связаны (функциональная связь), то ( ) 0 Это обозначает, что сообщение не несет никакой новой информации, кроме той, что содержится в сообщениях . . Энтропия системы (сообщений) никогда не возрастает вследствие получения знаний состояния системы , т.е.: ( )≤ ( ) При этом смотрите свойство : ( ) ( ) для статистически независимых ансамблей. 9- Информационное содержание дискретных сигналов. Количество информации как мера снятой неопределенности. Взаимосвязь энтропии и количества информации в дискретных ансамбля? Количество информации, как мера снятой неопределенности Для установления связи между информацией и энтропией рассмотрим процесс получения информации. Для приема сигнала неопределенность его состояния определяется энтропией: Отметим, что ( ) совпадает по виду со средним количеством информации, содержащимся в элементе сообщения. Далее происходит наблюдение сигнала. Если шумов нет, то после приема мы точно фиксируем сообщение, т.е. значение посланного сигнала. Следовательно, после приема неопределенность становится равной нулю. В этом случае мы можем считать, что полученная информация численно равна априорной энтропии сигнала. Если имеется шум, то и после акта приема сигнала остается неопределенность, характеризуемая энтропией принятого сигнала. Тогда мы можем считать, количество переданной информации есть апр.− апостер. Таким образом понятие энтропии является первичным, количество информации вторичным, определяемым как мера изменения неопределенности, т.е. энтропии. 0- Энтропия непрерывных сигналов. Дифференциальная энтропия? Энтропия непрерывных сообщений Для сообщений с дискретным множеством состояний мы определили энтропию в виде суммы. Обобщим выражение энтропии для непрерывных сигналов. для дискретных сигналов. Если – непрерывный сигнал, то Т.е. если непрерывный сигнал представить дискретным с шагом Запишем энтропию непрерывного сигнала: Дифференциальная энтропия или ядро энтропии Рассмотрим сигнал, равномерно распределенный на интервале [0, ]. Для него энтропия: Таким образом, дифференциальная энтропия Д( ) может быть определена, как разность энтропий сигнала с распределением ( ) и сигнала с равномерным распределением на интервале [0, ], т.е. Д( ) (

энтропией По аналогии с дискретными ансамблями, вводится условная энтропия непрерывных сигналов (имеется в виду дифференциация энтропии). При этом, как и для дискретного случая: ( , ) ( )+ ( ) ( )+ ( ) ( , ) Д( ) −∫∫ ( , )log [ ( , ) ( )] −∫∫ ( , )log ( ) −∫∫ ( ) ( )log ( )

- Энтропия нормально - и равномерно-распределенных сигналов? Принцип экстремума энтропии Определим виды функций плотности распределения вероятности ( ), обеспечивающие max ( ) при определенных ограничениях. Это имеет важное значение для оценки max скорости передачи информации при наличии помех. . Область изменения неограниченна, а дисперсия задана, т.е.: (задана) Это случай ограничения мощности сигнала. Вариационная задача с ограничениями Решение дает нормальный закон распределения. Найдем энтропию сигнала. Учитываем, что: . Область возможных значений ограничена интервалом [ , ], а дисперсия произвольна. Решение – равномерное распределение на Напомним, что дисперсия равномерно распределенного сигнала: Если сравним два сигнала – нормальный и равномерно-распределенный – с одинаковыми энтропиями, то из при одинаковой информативности сообщений средняя мощность сигнала при равномерном распределении амплитуд должна быть на 4 % больше мощности сигнала при нормальном распределении амплитуд (например, при сообщениях с амплитудной модуляцией). - Количество информации в непрерывном зашумленном и квантованном сигналах? Количество информации в сигнале при наличии помех Информационная модель канала приема передачи дискретного сигнала

может базироваться на следующих характеристиках: энтропия множества отправляемых символов (элементов сообщения) энтропия множества принимаемых символов – энтропия множества всевозможных пар ( , ) символов – энтропия множества отправляемых символов, оставшаяся после приема символа ) – энтропия множества принятых символов при условии, что известен отправленный символ - математическое ожидание - математическое ожидание – количество информации, полученное при приеме : ее количество информации в объекте относительно объекта

. А также: При этом ( ) – среднее количество информации, потерянное из-за воздействия помех. Напомним: . для дискретного сигнала: . для непрерывного сигнала: Свойства количества информации( , ) ( , ) - Каналы передачи информации. Модели каналов. Передача информации по непрерывному и дискретному каналам? Модели каналов передачи информации Сообщения в ИИС и системах связи передаются непрерывными или дискретными сигналами (во времени). Информационные каналы классифицируютс канала является линейная система, характеризуемая: импульсной переходной функцией ( ) или

частотной функцией ( ). Основной характеристикой непрерывного канала является полоса пропускания. Эффективный частотный диапазон или полоса пропускания: п п На практике для передачи сигнала по непрерывному каналу, как правило, используют методы модуляции. В этом случае полоса пропускания канала выбирается исходя из потребности передачи модулированного

сигнала. Передача информации по непрерывному каналу ---

Оценка измерение X(t) по отсчетам

(дискретам) -

 

Скорость создания (генерации) информации источником. ( )

– реализация случайного процесса –

интервал наблюдения – полоса частот сигнала (реализации) или спектр плотности случайного процесса ( ) Учитывая, что собственная (полная) энтропия непрерывного сигнала стремиться к нулю, будем считать, что процесс получения информации от ( ) осуществляется по отсчетам и при этом с

дискретизации, необходимо при формировании отсчетов обеспечить условия Котельникова (т.е. отсчетов за время ). Информация, снимаемая за один отсчет: ( ) - -энтропия сигнала За время имеем отсчетов и получаем за счет измерения информацию: За единицу времени, т.е. скорость генерации информации: Г ( ) Введем некоторые допущения: . Пусть ошибка измерений нормальна с дисперсией ; . Пусть сигнал на каждом отсчете нормален (белый шум) с дисперсией и полосой . Тогда скорость генерации информации: Передача информации по дискретному каналу Дискретный канал – это канал, по которому производится передача сигналов, имеющих дискретное множество состояний, т.е. сообщений. При этом дискретной является также сама передача сигналов во времени. Входной алфавит – алфавит источника сообщений, например – число сообщений, - буквы алфавита. Для того, чтобы передавать по линиям связи с помощью элементарных сигналов, используют процедуру кодирования, например, используя системы счисления, т.е. →{ }, где - элементы кода, а { } - кодовая комбинация. Элементы ≡ символы, например, двоичные. Алфавит кода короче алфавита входного, например, для двоичного кода он состоит из двух символов «0» и « ». Таким образом, для передачи одного сообщения требуется передать пачку символов кода сообщения. Иногда число сообщений не равно длине входного алфавита, если используется начальное кодирование исходных сообщений. например, сообщения: { , , ,…, } Входной алфавит: Для передачи сообщений по дискретному каналу можно использовать разные по форме сигналы, например, бинарные или многоуровневые: Бинарные сигналы Дискретный многоуровневый сигнал В данном разделе мы не будем изучать, как аналоговым сигналом производится и передается импульсный

ремя передачи одного

символа: – длительность символа информации. Скорость создания информации измеряется в символах в секунду: с⁄, симв. с. бод

Для двоичного сигнала бод бит сек. Для многоуровневого сигнала скорость бит сек. бодlog , – число уровней. При этом за время по каналу может быть передана информация Где: информация, передаваемая одним символом. количество информации в битах, созданное источником за время . - потери информации за время (в канале). Тогда реальная скорость передачи информации по дискретному каналу с шумом: Пропускная способность дискретного канала с шумом: max Максимальная величина выбирается по всем источникам информации. Как мы видим, понятие пропускной способности применимо как для непрерывных, так и для дискретных каналов. Для непрерывного канала значение пропускной способности соответствует передачи белого шума с ограниченным спектром. В целом, величина пропускной способности определяет возможность передачи сигналов при наличии шумов со сколь угодно малой вероятностью ошибки. 4- Непрерывные каналы. Производительность источника сигналов. Скорость передачи и пропускная способность канала? Передача информации по непрерывному каналу Причин пот

)

– реализация случайного процесса – интервал наблюдения – полоса частот сигнала (реализации) или спектр плотности случайного процесса ( ) Учитывая, что собственная (полная) энтропия непрерывного сигнала стремиться к нулю, будем считать, что процесс получения информации от ( )

избежание потери информации вследствие дискретизации, необходимо при формировании отсчетов обеспечить условия Котельникова (т.е. отсчетов за время ). Информация, снимаемая за один отсчет:

--- Оценка измерение X(t) по отсчетам (дискретам) --- измеритель

 

( ) - -энтропия сигнала За время

имеем отсчетов и получаем за счет измерения информацию:

 

За единицу времени, т.е.

скорость генерации информации: Г ( ) Введем некоторые допущения: . Пусть ошибка измерений нормальна с дисперсией ; 4. Пусть сигнал на каждом отсчете нормален (белый шум) с дисперсией и полосой . Тогда скорость генерации информации: ( ) log Г Скорость передачи и пропускная способность канала Считаем полосу пропускания канала достаточной, т.е. п> ( – полоса сигнала). Потеря информации в отсутствии динамических искажений будет обусловлена только наличием шума. Считаем также, что измерительное устройство на выходе канала имеет погрешность, значительно меньшую, чем дисперсия приведенного к выходу канала шума . Далее используем тот же подход к анализу скорости получения информации, что и при анализе скорости ее генерации, т.е. через отсчеты. Только в нашем случае для каждого отсчета: ( , ) Д( )− Д( ⁄) При этом: Д( ⁄) Д( ) Тогда за время : Скорость передачи информации: п ( Д( )− Д( )) Пропускная способность канала: max п max ( Д( )− Д( )) max – по всем возможным законам распределения и . Предположим корректность аддитивной модели шума: + в том числе для любого отсчета, а также распределение по нормальному закону в диапазоне (белые шумы), т.е.: дисперсия → шума Следовательно, Где – мощность сигнала (~ ), ш – мощность шума(~ ) 5- Передача информации по дискретному каналу. Скорость генерации информации на выходах источника сообщений и кодера. Идеальный и реальный каналы. Скорость передачи информации и пропускная способность в идеальном ДК.? Передача информации по дискретному каналу Дискретный канал – это канал, по которому производится передача сигналов, имеющих дискретное множество состояний, т.е. сообщений. При этом дискретной является также сама передача сигналов во времени. Входной алфавит – алфавит источника сообщений, например { ,…, },– число сообщений, - буквы алфавита. Для того, чтобы передавать по линиям связи с помощью элементарных сигналов, используют процедуру кодирования, например, используя системы счисления, т.е. →{ }, где - элементы кода, а { } - кодовая комбинация. Элементы ≡ символы, например, двоичные. Алфавит кода короче алфавита входного, например, для двоичного кода он состоит из двух символов «0» и « ». Таким образом, для передачи одного сообщения требуется передать пачку символов кода сообщения. Иногда число сообщений не равно длине входного

алфавита, если используется начальное кодирование исходных сообщений. например, сообщения: { , , ,…, } Входной алфавит: Для передачи сообщений по дискретному каналу можно использовать разные по форме сигналы, например, бинарные или многоуровневые: Бинарные сигналы Дискретный многоуровневый сигнал В данном разделе мы не будем изучать, как аналоговым сигналом

задать среднее время передачи одного символа: с Σ ( ) – длительность символа влияние помех на достоверность передаваемой информации. Скорость создания информации измеряется в символах в секунду: с⁄, симв. с. бод Для двоичного сигнала бод бит сек. Для многоуровневого сигнала скорость бит сек. бодlog , – число уровней. При этом за время по

( , ) – информация, передаваемая одним символом.( ) - количество информации в битах, созданное источником за время . - потери информации за время (в канале). Тогда реальная скорость передачи информации по дискретному каналу с шумом: ) Пропускная способность дискретного канала с шумом: Максимальная величина выбирается по всем источникам информации. Как мы видим, понятие пропускной способности применимо как для непрерывных, так и для дискретных каналов. Для непрерывного канала значение пропускной способности соответствует передачи белого шума с ограниченным спектром. В целом, величина пропускной способности определяет возможность передачи сигналов при наличии шумов со сколь угодно малой вероятностью ошибки. 6- Статистическое (эффективное) кодирование. Понятие оптимального кода. Избыточность кода. Постановка задачи эффективного кодирования. Оптимальная средняя длина кодового слова? Кодирование информации (сообщений) в дискретном канале. Введем следующие понятия и обозначения: – множество входных/ исходных сообщений, – алфавит входных сообщений, – алфавит передаваемых/ выходных сообщений, – множество передаваемых/ выходных кодовых слов над алфавитом выходных сообщений. Кодирование есть отображение Г: → , в частном случае предметом кодирования может быть построение Г : → . Пример: Множество сообщений – слова русского языка, их количество приблизительно равно 00000={ }. Кодировать слова неудобно из-за их количества. Использует алфавит грамматики русского языка ={ }= а,б,в,г,д,… буквы. Тогда Г : → , т.е. кодировать будем буквы русского алфавита. Для передачи по каналу связи (КС) следует использовать алфавит минимальной длины, например, двоичный, т.е. ={0, }. Символы алфавита образуют кодовые слова. В зависимости от условий передачи и принципов кодирования кодовые

иметь различное число значений (для двоичного кода - ). Цели и задачи кодирования . Обеспечение физических условий передачи сигналов по каналам связи (КС) . Обеспечение информационной и энергетической эффективности передачи . Повышение помехозащищенности передачи информации Задача 1.→ использование алфавита в коде передаваемого сообщения минимальной длины. Задача 2.→ построение эффективных кодов (оптимальное кодирование). Задача 3.→ построение корректирующих кодов. Оптимальное кодирование в отсутствии шумов Оптимальное ≡ эффективное кодирование реализует принципы: 1. использование для максимально вероятных сообщений кодов минимальной длины, 2. минимизации средней длины кодовых слов без проверки информации о сигнале. Имеем: → – кодовое слово, имеет длину символов. → ( ) → ( ) – индивидуальная информация в сообщении . Считаем символы в слове - статистически независимыми. Идея оптимизации →̅ . Пусть алфавит передачи содержит символов. Считаем значение символов равновероятным. Энтропия одного символа в коде :=Σ log1 =Σ1 log =log Максимальная информация на символ в кодовом слове: Индивидуальное количество информации в слове Оптимальная длина кода для сообщения Средняя оптимальная длина слова в кодах: ( ) - энтропия сообщений { } Для двоичного кода =2 и log =1

Цель эффективного кодирования – приближение: →̅ опт̅ . Оценка избыточности/ эффективности кода:и= −̅ опт̅ ̅В реальности оптцелое, тогда ( )log ≤ опт≤ ( )log +1 ( )log ≤ опт̅ ≤ ( )log +1 Что не всегда корректно, достаточно и дроби. Методы оптимального кодирования приводят в общем слу

кодовая комбинация не является началом более длинной кодовой комбинации). 17Методы и алгоритмы построения эффективных кодов. Метод Шеннона – Фэно. Метод Хаффман?. Алгоритмы эффективного кодирования 1. Метод Шеннона-Фено а) Для равновероятных сигналов т.е. =̅ опт= ( ), при этом 1= ( )= ( ) =1̅ бит/ симв. Для равновероятных сообщений длины кодовых слов одинаковы, код – оптимален. б) Для неравновероятных сообщений Код оптимален ср= ( ); =2, =1 так как удается разбить на равновероятные блоки. в) Для неравновероятных сообщений, когда не удается разбить всегда на равновероятные блоки: the same, но ср> опт= ( ) г) Кодирование по блокам. Если не удается разбить на более-менее равновероятные блоки, то можно кодировать сообщения блоками:1≈0.75 бит/ симв. ср→ опт 2. Метод Хафмена Метод состоит в построении кодового дерева с наиболее длинными ветвями, соответствующими наименее вероятным сигналам. Порядок

и т.д. ( )= опт=2,417 бит =2̅ .45 симв. 1=0.986 бит/ симв 18Равномерные блоковые коды. Избыточность. Разрешенные и запрещенные кодовые комбинации. Число вариантов безошибочной и ошибочной передач, обнаруживаемых и необнаруживаемых ошибок?. Способы представления кодов:

(алгебра многочленов) Двоичные двухразрядные: Троичный двухразрядный: Двоичный трехразрядный: 19Помехоустойчивое кодирование. Блоковые коды. Обнаружение и исправление ошибок. Кодовое расстояние. Кратность ошибок. Вектор ошибок? Помехоустойчивые кодировки Основные возможности – теоремы Шеннона. Идея: кодирование должно осуществляться таким образом, чтобы после воздействия шума на приемной стороне искаженный код оставался ближе к исходному коду, чем к другим возможным посылаемым кодам. Тогда есть возможность обнаружить и даже исправить ошибку в передаче. Такие коды – помехозащищенные, они могут быть корректирующими ошибки или обнаруживающими ошибки. У большинства помехозащищенных кодов их возможности являются следствием их алгебраической структуры. Алгебраические коды, в отличие о кодов Вагнера, которые корректируют ошибки, исходя из оценки вероятностей ошибок, подразделяются на блоковые и непрерывные коды. Блоковые коды. Исходный код – разрядов (символов). Помехоустойчивый код > разрядов, при этом ( − ) - число избыточных символов. Если= оят из последовательных символов,

(информационные и проверочные отделить невозможно) Блоковые коды На входе кодера – булевы исходные сообщения, закодированные -разрядным цифровым кодом. На выходе кодера – - разрядные коды, причем > , т.к. вводим избыточность. Имеем следующую модель передачи на участке источник-кодер-канал: →2 кодовых слов →2 кодовых слов Число случаев безошибочной передачи - 2 . Число случаев переходов в другие разрешенные комбинации - 2 (2 −1). Число случаев обнаруживаемых ошибочных передач - 2 (2 −2 ). Следовательно, часть обнаруживаемых ошибок от общего числа случаев передач: 2 (2 −2 )2 2 =1−2 2 Кодовое расстояние Наличие избыточности приводит к тому, что при приеме мы можем получить неразрешенные комбинации, что позволит обнаружить и откорректировать ошибку. При этом принимаем очевидное предположение, что чем выше кратность (число) ошибок, тем ниже их вероятность. Для реализации процедур коррекции кодов мы должны принять меру близости полученного кода к исходным. Кодовое расстояние по Хэммингу:

= { } - сумма единиц в коде. Например, Понятие минимального кодового расстояния. Декодирование после приема заключается в том, что принятая кодовая комбинация отождествляется с той разрешенной, к которой она наиболее близка ( = min). Очевидно, при =1 все кодовые комбинации являются разрешенными и обнаружить ошибку невозможно. Пример при =3: При d=2 одиночные ошибки не могут перевести код в другую разрешенную комбинацию, т.е. ошибка может быть обнаружена. – разрешенная комбинация - запрещенная комбинация В общем случае, для обнаружения ошибок кратности необходимо: ≥ +1 А теперь рассмотрим условие обнаружения ошибок в коде. При d=2 этого сделать нельзя. Возьмем d=3,n=3: Разрешенные комбинации

При получении одной из трех нижних кодовых комбинаций, мы считаем, что был отправлен код 111. Т.е. получили возможность исправления. Вектор ошибок - кодовая комбинация, имеющая «1» в разрядах, подвергшихся искажению, и «0» во всех остальных разрядах. Любую искаженную кодовую комбинацию можно рассматривать как -сумму разрешенной кодовой комбинации и вектора ошибки. Возвратимся к примеру. Разрешенные комбинации Искаженные комбинации Вектор ошибок Концепция построения помехозащищенного ( , ) кода. 20Блоковые коды. Корректирующая способность кода и ее связь с минимальным кодовым расстоянием. Оценки необходимой разрядности блоковых кодов? Графическая интерпретация Единичные ошибки на окружности d=1, ошибки s – кратные на окружности d=s. Для исправления необходимо: ≥2 +1 Для задачи обнаружения ошибок кратности и исправления ошибок кратности , требуется: ≥ + +1, > Геометрическая интерпретация Оценки необходимой разрядности кода для обеспечения возможности построения помехозащищенного кода. o Хэмминг: o Плоткин: верхняя граница для кодового расстояния для заданных значений , : o Разрядность, необходимая для передачи сообщений (000 не используется): Код Хэмминга →( , ) код с =3, позволяющий исправлять все однократные ошибки. Для него количество информационных разрядов: =log[2 ( +1)⁄]= −log( +1) Уравнение имеет целочисленные решения =0,1,4,11,26, которые определяют коды 21Построение двоичного линейного блокового группового кода. Опознаватели ошибок. Уравнения связи и проверочные равенства для кода Хэмминга (7,4)?. Оценки необходимой разрядности кода для обеспечения возможности построения помехозащищенного кода. o Хэмминг: o Плоткин: верхняя граница для кодового расстояния для заданных значений , : ⁄ o Разрядность, необходимая для передачи сообщений (000 не используется): Код Хэмминга →( , ) код с =3, позволяющий исправлять все однократные ошибки. Для него количество информационных разрядов: =log[2 ( +1)⁄]= −log( +1) Уравнение имеет целочисленные решения =0,1,4,11,26, которые определяют коды Граница Варшамова-Гильберта - определяет существование группового кода, с кодовым расстоянием, не меньшим d, и с числом избыточных символов, не превышающем ( − ). (Групповые) блоковые помехозащищенные коды обычно обозначают, как (n,k) коды, где: k – число информационных разрядов; n – общее число разрядов; ( − ) – дополнительные избыточные или поверочные разряды. Пример: Имеем три сообщения =3; для их передачи достаточно k=2, т.к. 2 −1=22−1=3. Введем избыточность, необходимую для обнаружения одиночных ошибок ( = +1=2). Для этого достаточно ввести один дополнительный разряд. Тогда получим: (011011) → (01 110 211 3) Самый простой принцип задания дополнительных разрядов и соответственно поверки наличия ошибки при приеме следующий:= 1 2 То есть: Тогда на приемной стороне достаточно при получении кодовой комбинации проверить выполнение равенства (проверка на четность): 1 2 =0 Опознаватель кода (7,4). Вектор ошибок Опознаватель 22Представление линейных блоковых кодов в матричном виде. Порождающая матрица кода. Каноническая форма порождающей матрицы линейного блокового кода? Представление линейных кодов в матричном виде В теории кодирования строки и столбцы

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Калькулятор

Сервис бесплатной оценки стоимости работы

  1. Заполните заявку. Специалисты рассчитают стоимость вашей работы
  2. Расчет стоимости придет на почту и по СМС

Нажимая на кнопку, вы соглашаетесь с политикой конфиденциальности и на обработку персональных данных.

Номер вашей заявки

Прямо сейчас на почту придет автоматическое письмо-подтверждение с информацией о заявке.

Оформить еще одну заявку