Основная теорема Шеннона для дискретного канала с шумом - раздел Образование, Теория информации и кодирования Формулировка
Для Дискретного Канала В Шумом Существуе...
Формулировка
Для дискретного канала в шумом существует такой способ кодирования, при котором может быть обеспечена безошибочная передача все информации, поступающей от источника сообщений, если только пропускная способность канала превышает производительность источника сообщений, т.е. если выполняется условие:
Vк max [ log2m – H(B/B’)] > Vи * H(A),(4.1)
где H(A) – энтропия источника.
Здесь обозначения соответствуют схеме, изображенной на рис. 4.6.
|
В – символы на входе, а В’ – на выходе канала;
Vи и Vк – скорость поступления символов от источника на вход кодирующего устройства и с выхода кодирующего устройства на вход линии связи.
|
4.6. Схема системы передачи информации через дискретный канал связи с помехами и сопутствующие обозначения.
Доказательство
Согласно полученной ранее формуле, число типичных последовательностей длительностью Т равно:
Nтип(А) = 2Vи*T*H(A) (4.2)
Максимально возможное число различных последовательностей на выходе кодера, которое сможет иметь ту же длительность, Т равна:
N(B) = mVк*T,
где m – объем вторичного алфавита.
Эту формулу можно записать также в виде:
(4.3)
Предположим, что условие теоремы Vк [ log2m – H(B/B’)] > Vи * H(A) выполняется. Тогда, поскольку H(B/B’)>0, неравенство условия теоремы только усилится, если его записать в виде: Vк log2m > Vи * H(A).
Домножим левую и правую части неравенства на Т и сделаем их показателями двойки:
.
Таким образом, возможное число последовательностей длительностью Т на выходе кодера больше числа типичных последовательностей той же длительности, которое может выдать источник.
Если установить однозначное соответствие между последовательностями на выходе кодера с последовательностями на входе, остаются последовательности, которые не могут использоваться для кодирования, т.е. запрещенные кодовые слова. Если все же такая последовательность получается с выхода канала связи – это верный признак ошибки.
Каждому способу кодирования будет соответствовать определенный вариант установки соответствия между каждой из множества типичных последовательностей, генерируемых источником и кодовым словом, взятым из множества разрешенных кодовых слов N(B).
Требуется теперь доказать, что среди всех возможных способов установки этого соответствия существует такой, который обеспечивает однозначную идентификацию любого принятого кодового слова, даже если оно получилось в результате искажения помехой передаваемого слова.
Для доказательства найдем вероятность правильного приема, усредненную по всем возможным способам кодирования, т.е. установки соответствия между принятым и возможно искаженным кодовым словом и закодированной информационной последовательностью.
По условной энтропии H(B/B’) можно найти количество возможных типичных последовательностей на входе канала, которые после искажения в нем могли бы дать определенную последовательность на выходе канала:
Nтип(B/B’) = 2T Vк H(B/B’) . (4.4)
Вывод аналогичен сделанному ранее при исследовании свойств типичных последовательностей. Только в данном случае энтропия символа на выходе канала – функция того, какой символ получен на входе канала – H(B/B’).
Правильный прием возможен только тогда, когда на [Nтип(B/B’)-1] не разрешенных кодовых слов приходится одно разрешенное, т.е. число возможных кодовых слов вообще должно быть в Nтип(B/B’) раз больше числа типичных Nтип(A) последовательностей, которые может выдать источник.
Предположим теперь, что соответствия между типичными последовательностями, выдаваемыми источником, и кодовыми словами устанавливаются равновероятно. Тогда вероятность pразр того, что определенное кодовое слово среди Nтип(А) является разрешенным, равна: pразр=Nтип(А)/N(B) (кодируются только типичные последовательности).
Соответственно, вероятность того, что кодовое слово является запрещенным равна 1- pразр= 1 - Nтип(А)/N(B).
Правильное декодирование возможно только тогда, если среди Nтип(B/B’) кодовых слов только одно выбрано в качестве разрешенного.
Вероятность этого равна:
.
Так как основание степени , то, увеличивая показатель степени с Nтип(B/B’)-1 до Nтип(B/B’), получим неравенство:
. (4.5)
Разложим правую часть этого неравенства в ряд по степеням (ряд Тэйлора[15]):
Поскольку и члены ряда по абсолютной величине убывают, неравенство (5) только усиливается, если отбросить все члены ряда выше первого порядка:
.
Подставив в это выражение выражения (2), (3), (4), получим:
,
где Сk =Vk*log2m-Vk*H(B/B’) – пропускная способность канала связи с учетом потерь информации в результате действия помех (шума).
Заметим, что, если Ck > Vи*H(A) (условие теоремы Шеннона), с ростом Т вероятность ошибки Рош стремится к 0.
Помимо ошибки, возможной при приеме типичных последовательностей, вероятность которой определяется последней формулой, возможны ошибки за счет появления на выходе источника нетипичных последовательностей, кодирование которых вообще не предусматривается описанной процедурой. При вероятностях появления нетипичной последовательности и типичной суммарная вероятность ошибочной передачи равна: .
При , как было показано ранее, .
Если Сk-VиH(A) > 0 (т.е. при условии выполнения теоремы Шеннона), то при и суммарная ошибка .
Поскольку среди всех вариантов кодирования обязательно существует хотя бы один, для которого вероятность ошибки не превышает среднего по всем вариантам кодирования значения , теорему Шеннона можно считать доказанной.
Все темы данного раздела:
Курс лекций
Эффективная организация обмена информации приобретает все большее значение как условие успешной практической деятельности людей. Объем информации, необходимый для нормального функционирования совре
Определение понятия информация
Слово информация происходит от латинского 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. Исполняемый файл программы носит имя Помехо
Новости и инфо для студентов