Пропускная способность дискретного канала связи с шумом - раздел Образование, Теория информации и кодирования Исследуем Теперь Пропускную Способность Дискретного Канала Связи С Шумом....
Исследуем теперь пропускную способность дискретного канала связи с шумом.
Существует большое количество математических моделей таких каналов. Простейшей из них является канал с независимой от передаваемой информации помехой, имеющей независимые во времени значения. Последнее означает, что влияние помехи на различные буквы передаваемого сообщения не зависят друг от друга. Будем рассматривать канал без стирания с алфавитом объема m (не двоичный симметричный канал ДСМК, так как m не равно 2).
Если в канале без помех среднее количество информации, получаемой с выхода канала в единицу времени, соответствует среднему количеству информации, содержащейся во входном сообщении той же длительности, то в канале связи с шумом это соответствие нарушается. При наличии помехи скорость передачи информации через канал может быть меньше скорости ее поступления на его вход, так как часть информации за счет помех в канале может теряться.
Помехи нарушают взаимно-однозначное соответствие между символами на входе и выходе канала, что приводит к появлению на выходе канала остаточной неопределенности об информации, поступившей на вход канала.
Количество переданной информации при этом вычисляется согласно формуле Шеннона как разность между априорной и апостериорной энтропиями:
I = Hапр – Напост ,
,
где bi – i-я буква из алфавита объемом m.
Hапост = Н(B/B’) – средняя условная энтропия 1 буквы на входе канала связи с шумом относительно 1 буквы, принятой на выходе канала связи. Найдем эту энтропию.
В результате искажения передаваемые буквы bi превращаются в другие bi’ из того же алфавита. Вероятность такого превращения можно описать графом, называемым канальной матрицей(рис. 4.5).
Рис. 4.5. Канальная матрица.
Каждому ребру этого графа соответствует условная вероятность p(bi/bj’) – вероятность того, что на вход канала поступал символ bi при условии, что на выходе был получен символ bj’ (выходные символы обозначаются со штрихом).
Неопределенность (энтропия) того, какой символ был на входе канала связи по символу полученному на выходе находится согласно определению энтропии по формуле: H(bi/bj’)=-log2 p(bi/bj’).
Нас интересует средняя неопределенность независимо от сочетания входной и выходной буквы. Вероятность такого сочетания – совместная вероятность p(bi,bj’).
Использую совместную вероятность, среднюю условную энтропию получаем в виде:
.
Учитывая, что (формула Байеса)
и
,
получим:
.
Значение условной энтропии H(B/B’) характеризует потери информации в канале и названа К. Шенноном ненадежностью канала.
Из выведенной выше формулы следует, что ненадежность канала зависит от статистических характеристик входного сообщения В (вероятностей р(bi)), а также от искажений, описываемых условными вероятностями p(bj’/bi).
Подставив теперь выражения для априорной и апостериорной энтропии в формулу среднего количества информации на символ сообщения, получим:
.
После преобразований получим:
.
Заметим, что эта формула симметрична относительно bi и bi’, поэтому
I = H(B) – H(B/B’) = H(B’) – H(B’/B) ,
т.е., во-первых:
среднее количество информации на символ равно разности энтропии на входе и неопределенности на выходе относительно входа;
во-вторых:
оно равно разности неопределенности (энтропии) на выходе и неопределенности того, что получено на выходе, если известно, что было передано на входе канала.
Пропускная способность получается путем максимизации скорости передачи информации по каналу связи путем подбора вероятностей p(bi).
Cк = Vк max * I = Vк max*[H(B) – H(B/B’)] .
Вообще и уменьшаемое H(B) и вычитаемое H(B/B’) в этой формуле зависят от p(bi), однако большинство авторов зависимостью вычитаемого H(B/B’) от p(bi) ввиду его малости пренебрегают и учитывают зависимость Ск только от уменьшаемого H(B).
Известно, что энтропия H(B) максимальна при равенстве всех вероятностей p(bi). Это равенство возможно только при условии p(bi)=1/m. В результате получаем, что пропускная способность дискретного канала связи с шумом равна Cк = Vк [log2m – H(B/B’)] .
Посмотрим теперь, как влияет шум на пропускную способность канала связи.
Ненадежность канала H(B/B’) будет минимальна и равна 0, если шума нет. Тогда символы на входе и выходе всегда совпадают. Это значит, что:
.
В этом случае H(B/B’)=0, а пропускная способность Ск max совпадает с пропускной способностью канала связи без шума, что и следовало ожидать.
Если же шум настолько велик, что все символы на выходе могут появляться равновероятно не зависимо от того, какой символ подавался на вход канала связи, т.е. если p(bi/bj’)=1/m и p(bj’)=1/m, то I=0.
Это несложно доказать.
.
А так как I=H(B)-H(B/B’), где H(B)=log2m, то I=log2m-log2m=0.
Для доказательства очень важной теоремы, доказанной еще в 40-х годах 20 века Шенноном для дискретного канала с шумом, введем понятие типичных последовательностей и рассмотрим их свойства.
Все темы данного раздела:
Курс лекций
Эффективная организация обмена информации приобретает все большее значение как условие успешной практической деятельности людей. Объем информации, необходимый для нормального функционирования совре
Определение понятия информация
Слово информация происходит от латинского informare – изображать, составлять понятие о чем-либо, осведомлять.
Информация наряду с материей и энергией является первичны
Фазы обращения информации
Система управления состоит из объекта управления, комплекса технических средств, состоящего из компьютера, входящих в его состав устройств ввода-вывода и хранения информации, устройств сбора переда
Некоторые определения
Данные или сигналы, организованные в определенные последовательности, несут информацию не потому, что они повторяют объекты реального мира, а по общественной договоренности о кодировании, т.е. одно
Меры информации
Прежде, чем перейти к мерам информации, укажем, что источники информации и создаваемые ими сообщения разделяются на дискретные и непрерывные. Дискретные сообщения слагаются из конечно
Геометрическая мера
Определение количества информации геометрическим методом сводится к измерению длины линии, площади или объема геометрической модели данного носителя информации или сообщения. По геометрическим разм
Аддитивная мера (мера Хартли)
Аддитивную меру можно рассматривать как более удобную для ряда применений комбинаторную меру. Наши интуитивные представления об информации предполагают, чтобы количество информации увеличивалось пр
Энтропия и ее свойства.
Существует несколько видов статистических мер информации. В дальнейшем будем рассматривать только одну их них ─ меру Шеннона. Мера Шеннона количества информации тесно связана с понятие
Энтропия и средняя энтропия простого события
Рассмотрим подробнее понятие энтропии[1] в разных вариантах, так как оно используется в шенноновской теории информации. Энтропия - мера неопределенности некоторого опыта. В простейшем случае его ис
Метод множителей Лагранжа
Если нужно найти экстремум (максимум, минимум или седловую точку) функции n переменных f(x1, x2, …, xn), связанных k<n условиями зависимости, котор
Вывод формулы среднего значения энтропии на букву сообщения
Предположим, имеется сообщение, состоящее из n букв: , где j=1, 2, …, n ─ номера букв в сообщении по порядку, а i1, i2, … ,in номера букв
Энтропия сложного события, состоящего из нескольких зависимых событий
Теперь предположим, что элементы сообщения (буквы) взаимозависимы. В этом случае вероятность появления последовательности из нескольких букв не равна произведению вероятностей появ
Избыточность сообщения
Как отмечалось, энтропия максимальна, если вероятности сообщений или символов, из которых они составлены, одинаковы. Такие сообщения несут максимально возможную информацию. Если же сообщение имеет
Содержательность информации
Мера содержательности[5] обозначается cont (от английского Content ─ содержание).
Содержательность события I выражается через функцию меры содержательности его о
Целесообразность информации
Если информация используется в системах управления, то ее полезность разумно оценивать по тому эффекту, который она оказывает на результат управления. В связи с этим в 1960 г. советским ученым А.А.
Динамическая энтропия
Здесь энтропия рассматривается как функция времени. При этом преследуется цель – избавиться от неопределенности, т.е. добиться положения, когда энтропия равна 0. Такая ситуация характерна для задач
Энтропия непрерывных сообщений
Исходные данные часто представляются в виде непрерывных величин, например, температура воздуха или морской воды. Поэтому представляет интерес измерение количества содержащейся в таких сообщениях ин
Первый случай (значения сл. величины ограничены интервалом)
Случайная величина a ограничена интервалом [b,c]. В этом случае определенный интеграл ее плотности распределения вероятностей (дифференциального закона распределения вероятностей) на
Второй случай (заданы дисперсия и математическое ожидание сл. величины)
Предположим теперь, что область определения значений случайной величины не ограничена, но задана ее дисперсия D и математическое ожидание M. Заметим, что дисперсия прямо пропорциональ
Квантование сигналов
Непрерывные сигналы – носители информации – представляют собой непрерывные функции непрерывного аргумента – времени. Передача таких сигналов может выполняться при помощи непрерывных каналов связи,
Виды дискретизации (квантования)
Наиболее простыми и часто используемыми видами квантования являются:
· квантование по уровню (будем говорить просто квантование);
· квантование по времени (будем называть
Критерии точности представления квантованного сигнала
В результате обратного преобразования из непрерывно-дискретной формы в непрерывную получается сигнал , отличающийся от исходного на величину ошибки . Сигнал называется воспроизводящей функц
Элементы обобщенной спектральной теории сигналов
Обобщенная спектральная теория сигналов объединяет методы математического описания сигналов и помех. Эти методы позволяют обеспечить требуемую избыточность сигналов с целью уменьшения влияния помех
О практическом использовании теоремы Котельникова
Возможную схему квантования-передачи-восстановления непрерывного сигнала можно представить в виде, изображенном на рис. 2.5.
Рис. 2.5. Возможная схема квантования-передачи-
Выбор периода дискретизации (квантования по времени) по критерию наибольшего отклонения
В результате квантования по времени функции x(t) получается ряд значений x(t1), x(t2), … квантуемой величины x(t) в дискретные моменты времени t
Интерполяция при помощи полиномов Лагранжа
Воспроизводящая функция в большинстве случаев рассчитывается по формуле: , где − некоторые функции. Эти функции обычно стремятся выбрать так, чтобы
. (2.14)
В этом случае ,
Оценка максимального значения ошибки при получении воспроизводящей функции на основе полинома Лагранжа
Найдем погрешность интерполяции. Представим ее виде:
, (2.16)
где K(t) – вспомогательная функция, которую надо найти.
Для произвольного t* имеем:
(
Обобщение на случай использования полиномов Лагранжа произвольного порядка
Интерполяция полиномами n-го порядка рассматривается аналогично предыдущим случаям. При этом наблюдается значительное усложнение формул. Обобщение приводит к формуле следующего вида:
Выбор интервала дискретизации по критерию среднеквадратического отклонения
Рассмотрим случай дискретизации случайного стационарного эргодического процесса x(t) с известной корреляционной функцией . Восстанавливать будем при помощи полиномов Лагранжа. Наиболее часто
Оптимальное квантование по уровню
Рисунком 2.13 иллюстрируется принцип квантования по уровню[7].
Рис. 2.13. Квантование по уровню.
Это квантование сводится к замене значения исходного сигнала уровн
Расчет неравномерной оптимальной в смысле минимума дисперсии ошибки шкалы квантования.
Рис. 2.19. Обозначения
Зададимся теперь числом шагов квантования n, границами интервала (xmin, xmax
Общие понятия и определения. Цели кодирования
Кодирование − операция отождествления символов или групп символов одного кода с символами или группами символов другого кода.
Код (франц. code), совокупность зна
Элементы теории кодирования
Некоторые общие свойства кодов[8].
Рассмотрим на примерах. Предположим, что дискретный источник без памяти, т.е. дающий независимые сообщения – буквы – на выходе, име
Неравенство Крафта
Теорема 1. Если целые числа n1, n2, …, nk удовлетворяют неравенству
, (3.1)
существует префиксный код с алфавитом объемом m,
Теорема 2.
Формулировка. Пусть задан код с длинами кодовых слов n1, n2, … , nk и с алфавитом объема m. Если код однозначно декодируем, неравенство Крафта удовле
Теорема 3.
Формулировка. При заданной энтропии H источника и объеме m вторичного алфавита существует префиксный код с минимальной средней длиной nср min
Теорема о минимальной средней длине кодового слова при поблочном кодировании (теорема 4)
Рассмотрим теперь случай кодирования не отдельных букв источника, а последовательностей из L букв.
Теорема 4.
Формулировка. Для данного дискретного источника
Оптимальные неравномерные коды
Определения.
Неравномерными называют коды, кодовые слова которых имеют различную длину.
Оптимальность можно понимать по-разному, в зависимости о
Лемма 1. О существовании оптимального кода с одинаковой длиной кодовых слов двух наименее вероятных кодируемых букв
Формулировка. Для любого источника с k>=2 буквами существует оптимальный (в смысле минимума средней длины кодового слова) двоичный код, в котором два наименее вероятных сло
Лемма 2. Об оптимальности префиксного кода нередуцированного ансамбля, если префиксный код редуцированного ансамбля оптимален
Формулировка. Если некоторый префиксный код редуцированного ансамбля U'является оптимальным, то соответствующий ему префиксный код исходного ансамбля т
Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.
Рассмотрим алфавит из восьми букв. Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждой буквы требуется три символа.
Наибольший эффек
Параметры эффективности оптимальных кодов
Таких параметров 2: коэффициент статистического сжатия и коэффициент относительной эффективности. Оба параметра характеризуют степень уменьшения средней длины кодового слова. При этом средняя длина
Особенности эффективных кодов.
1. Букве первичного алфавита с наименьшей вероятностью появления ставится в соответствие код с наибольшей длиной (лемма 1), т.е. такой код является неравномерным (с разной длиной кодовых слов). В р
Помехоустойчивое кодирование
Как следует из названия, такое кодирование предназначено для устранения вредного влияния помех в каналах передачи информации. Уже сообщалось, что такая передача возможна как в пространстве, так и в
Простейшие модели цифровых каналов связи с помехами
Свойство помехоустойчивых кодов обнаруживать и исправлять ошибки в сильной степени зависит от характеристик помех и канала передачи информации. В теории информации обычно рассматривают две простые
Расчет вероятности искажения кодового слова в ДСМК
Положим, кодовое слово состоит из n двоичных символов. Вероятность неискажения кодового слова, как несложно доказать, равна:
.
Вероятность искажения одного символа (однокра
Общие принципы использования избыточности
Для простоты рассмотрим блоковый код. С его помощью каждым k разрядам (буквам) входной последовательности ставится в соответствие n-разрядное кодовое слова. Количество разного вида
Граница Хэмминга
Граница Хэмминга Q, определяет максимально возможное количество разрешенных кодовых слов равномерного кода при заданных длине n кодового слова и корректирующей способности кода КСК
Избыточность помехоустойчивых кодов
Одной из характеристик кода является его избыточность. Увеличение избыточности в принципе нежелательно, т.к. увеличивает объемы хранимых и передаваемых данных, однако для борьбы с искажениями избыт
Линейные коды
Рассмотрим класс алгебраических кодов, называемых линейными.
Определение: Линейными называют блоковые коды, дополнительные разряды которых образуются
Определение числа добавочных разрядов m.
Для определения числа добавочных разрядов можно воспользоваться формулой границы Хэмминга:
.
При этом можно получить плотноупакованный код, т.е. код с минимальной при заданных пар
Построение образующей матрицы
Линейные коды обладают следующим свойством: из всего множества 2k разрешенных кодовых слов, образующих, кстати, группу, можно выделить подмножества из k слов, обладающих св
Порядок кодирования
Кодовое слово КС получается путем умножения матрицы информационной последовательности ||X|| на образующую матрицу ||OM||:
||KC1*n|| = ||X
Порядок декодирования
В результате передачи кодового слова через канал оно может быть искажено помехой. Это приведет к тому, что принятое кодовое слово ||ПКС|| может не совпасть с исходным ||КС||.
Двоичные циклические коды
Вышеприведенная процедура построения линейного кода имеет ряд недостатков. Она неоднозначна (МДР можно задать различным образом) и неудобна в реализации в виде технических устройств. Этих недостатк
Некоторые свойства циклических кодов
Все свойства циклических кодов определяются образующим полиномом.
1. Циклический код, образующий полином которого содержит более одного слагаемого, обнаруживает все одиночные ошибки.
Построение кода с заданной корректирующей способностью
Существует несложная процедура построения кода с заданной корректирующей способностью. Она состоит в следующем:
1. По заданному размеру информационной составляющей кодового слова длиной
Матричное описание циклических кодов
Циклические коды можно, как и любые линейные коды, описывать с помощью матриц.
Вспомним, что KC(X) = gm(X)*И(Х) .
Вспомним также на примере порядок умножения пол
Выбор образующего полинома
Ясно, что полиномы кодовых слов КС(Х) должны делиться на образующий полином g(X) без остатка. Циклические коды относятся к классу линейных. Это означает, что для этих кодов существует
Виды каналов передачи информации
Рассмотрим каналы, отличающиеся по типу используемых в них линий связи.
1. Механические, в которых для передачи информации используется перемещение каких-либо твердых, жид
Пропускная способность каналов связи
Эта тема является одной из центральных в теории информации. В ней рассматриваются предельные возможности каналов связи по передаче информации, определяются характеристики каналов, влияющие на эти в
Типичные последовательности и их свойства
Будем рассматривать последовательности статистически независимых букв. Согласно закону больших чисел, наиболее вероятными будут последовательности длиной n, в которых при количества N
Основная теорема Шеннона для дискретного канала с шумом
Формулировка
Для дискретного канала в шумом существует такой способ кодирования, при котором может быть обеспечена безошибочная передача все информации, поступающей от источ
Обсуждение основной теоремы Шеннона для канала с шумом
Теорема Шеннона для канала с шумом не указывает на конкретный способ кодирования, обеспечивающий достоверную передачу информации со скоростью, сколь угодно близкой с пропускной способности канала с
Пропускная способность непрерывного канала при наличии аддитивного шума
Рассмотрим следующую модель канала:
1. Канал способен пропускать колебания с частотами ниже Fm.
2. В канале действует помеха n(t), имеющая нормальный (гау
Шаг 2. Ввод текстовых файлов в Excel-таблицу с разбиением каждой строки текста на отдельные символы.
При вводе ранее сохраненного текстового файла следует указать тип файла *.*. Это позволит во время выбора видеть в списке все файлы. Укажите свой файл. После этого на экран будет выведено окно М
Шаг 4. Находим среднюю энтропию, приходящуюся на 1 букву сообщения.
Как описано в теоретическом введении, средняя энтропия находится по формулам 1 и 2. В обоих случаях нужно найти вероятности появления букв или двухбуквенных комбинаций..
Вероятности можно
Шаг 8. Напишем отчет о выполненной работе с описанием всех вычислений и о том, как они выполнялись. Прокомментируйте результаты.
Результаты вычислений представьте в виде таблицы:
<Язык 1>
<Язык
Подключение возможности использования нестандартных функций.
Программное управление приложениями, входящими в состав Microsoft Office, осуществляется при помощи так называемых макросов.
Слово Макрос – греческого происхождения. В перево
Создание нестандартной функции
Перед созданием нестандартных функций нужно открыть файл в рабочей книгой, содержащей информацию, которую нужно обработать с применением этих нестандартных функций. Если ранее эта рабочая книга был
Запись голоса и подготовка сигнала.
Запись начинается и заканчивается нажатием кнопки Record (рис. 5), помеченной красный кружком. В процессе записи кнопка Recоrd выглядит вдавленной и более светлой (подсвеченной).
Импорт текстовых данных в Excel
Двойным кликом откройте текстовый файл с экспортированные из программы Wavosaur данными (рис. 23).
Рис. 23. Примерный вид данных
Видно, что экспортированные
Квантование по уровню сводится к замене значения исходного сигнала уровнем того шага, в пределы которого это значение попадает.
Квантование по уровню – необходимое условие преобразования непрерывного сигнала в цифровую форму. Однако одного лишь квантования по уровню для этого недостаточно – для преобразования в цифровую фор
Коды Хаффмена
На этом алгоритме построена процедура построения оптимального кода, предложенная в 1952 году доктором Массачусетского технологического института (США) Дэвидэм Хаффменом[17]:
5) буквы перви
Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.
Рассмотрим алфавит из восьми букв. Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждой буквы требуется три символа.
Наибольший эффек
Параметры эффективности оптимальных кодов
Таких параметров 2: коэффициент статистического сжатия и коэффициент относительной эффективности. Оба параметра характеризуют степень уменьшения средней длины кодового слова. При этом средняя длина
Особенности эффективных кодов.
5. Букве первичного алфавита с наименьшей вероятностью появления ставится в соответствие код с наибольшей длиной (лемма 1), т.е. такой код является неравномерным (с разной длиной кодовых слов). В р
Выполнение работы
Лабораторная работа №4 выполняется под управлением специально написанной управляющей программы. Эта управляющая программа написана на языке Visual Basic 6. Исполняемый файл программы носит и
Построение образующей матрицы
Линейные коды обладают следующим свойством: из всего множества 2k разрешенных кодовых слов можно выделить подмножества из k слов, обладающих свойством линейной независимост
Порядок кодирования
Кодовое слово КС получается путем умножения матрицы информационной последовательности ||X|| на образующую матрицу ||OM||:
||KC1*n|| = ||X
Порядок декодирования
В результате передачи кодового слова через канал оно может быть искажено помехой. Это приведет к тому, что принятое кодовое слово ||ПКС|| может не совпасть с исходным ||КС||.
Выполнение работы
Лабораторная работа №5, как и работа №4, выполняется под управлением управляющей программы, написанной на алгоритмическом языке Visual Basic 6. Исполняемый файл программы носит имя Помехо
Новости и инфо для студентов