![](/user_photo/2706_HbeT2.jpg)
- •2. Задачи теории информации и кодирования
- •3. Формы представления информации. Модель системы передачи информации
- •4. Схема дискретной системы передачи
- •5. Понятие энтропии
- •6. Математические модели дискретных сигналов (абгш, канал с замиранием и т.Д.)
- •7.Понятие битовой ошибки (bit-error-rate)
- •8. Помехоустойчивое кодирование. Классификация помехоустойчивых кодов
- •Классификация помехоустойчивых кодов
- •9. Блоковые коды
- •10. Кодирующая способность блокового кода Расстояние Хэмминга
- •11. Примеры кодирования простыми блоковыми арифметическими кодами
- •12. Определение количества корректирующих символов блоковых кодов
- •13. Систематические групповые коды
- •14. Коды Хэмминга
- •15.Циклические коды. Представление двоичного кода в виде полинома
- •16. Идея построения циклических кодов
- •Алгебраическое описание
- •17. Порождающий полином циклического кода
- •18. Алгоритм получения разрешенных комбинаций циклического кода из простого линейного кода
- •19. Алгоритм определении я ошибки в цикличном коде
- •20. Схемная реализация циклического кодирования
- •21. Сверточные коды. Представление двоичного кода виде полинома
- •22. Схема сверточного кодера
- •23. Типы декодера сверточного кода.
- •24. Последовательные каскадные коды
- •25. Параллельные каскадные коды
- •26. Bpsk, qpsk модуляция
- •27. Система кодирования с адаптивной модуляцией
- •28. Система дискретной связи с адаптивной модуляцией и кодированием
4. Схема дискретной системы передачи
Модель системы передачи дискретной информации
Модель системы передачи дискретной информации содержит источник сообщений, кодер, генератор М-последовательности, модулятор, блок внесения ошибки, демодулятор, датчик М-последовательности, декодер и приемник сообщений (см. фиг. 1). Источник сообщений представляет собой последовательность символов, передача которых осуществляется. Перед передачей исходная последовательность кодируется с помощью кода Хэмминга, исправляющего однократные ошибки, дополненного битом проверки на четность. Перед сообщением в канале связи находится М-последовательность, которая выполняет функции синхронизации приемника и передатчика, позволяя определить начало сообщения. Модулятор заменяет каждый бит, передаваемый в канал, группой таких битов заданной заранее длины. Все полученные биты искажаются ошибкой. Демодулятор принимает группы искаженных бит и заменяет их одним битом, значение которого определяется по методу большинства. Датчик М-последовательности определяет начало приема сообщения. Декодер производит обнаружение и исправление внесенных в сообщение ошибок. Приемник сообщений представляет собой буфер, в котором хранится принятое сообщение.
5. Понятие энтропии
Информацио́нная энтропи́я — мера неопределённости или непредсказуемости информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.
Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии n-ого порядка, см. ниже) встречаются очень редко, то неопределённость уменьшается еще сильнее.
Для иллюстрации понятия информационной энтропии можно также прибегнуть к примеру из области термодинамической энтропии, получившему название демона Максвелла. Концепции информации и энтропии имеют глубокие связи друг с другом, но, несмотря на это, разработка теорий в статистической механике и теории информации заняла много лет, чтобы сделать их соответствующими друг другу.
Энтропия — это количество информации, приходящейся на одно элементарное сообщение источника, вырабатывающего статистически независимые сообщения.
Формальные определения
Информационная двоичная энтропия для независимых случайных событий x с n возможными состояниями (от 1 до n, p — функция вероятности) рассчитывается по формуле:
Эта
величина также называется средней
энтропией сообщения.
Величина
называетсячастной
энтропией,
характеризующей только i-e
состояние.
Таким образом, энтропия события x является суммой с противоположным знаком всех произведений относительных частот появления события i, умноженных на их же двоичные логарифмы[1]. Это определение для дискретных случайных событий можно расширить для функции распределения вероятностей.
Определение по Шеннону
Шеннон предположил, что прирост информации равен утраченной неопределённости, и задал требования к её измерению:
мера должна быть непрерывной; то есть изменение значения величины вероятности на малую величину должно вызывать малое результирующее изменение функции;
в случае, когда все варианты (буквы в приведённом примере) равновероятны, увеличение количества вариантов (букв) должно всегда увеличивать значение функции;
должна быть возможность сделать выбор (в нашем примере букв) в два шага, в которых значение функции конечного результата должно являться суммой функций промежуточных результатов.
Поэтому функция энтропии H должна удовлетворять условиям:
определена и непрерывна для всех
, где
для всех
и
. (Нетрудно видеть, что эта функция зависит только от распределения вероятностей, но не от алфавита.)
Для целых положительных n, должно выполняться следующее неравенство:
Для целых положительных bi, где
, должно выполняться равенство:
Шеннон показал,[источник не указан 276 дней] что единственная функция, удовлетворяющая этим требованиям, имеет вид:
где K — константа (и в действительности нужна только для выбора единиц измерения).
Шеннон
определил, что измерение энтропии (),
применяемое к источнику информации,
может определить требования к минимальной
пропускной способности канала, требуемой
для надёжной передачи информации в виде
закодированных двоичных чисел. Для
вывода формулы Шеннона необходимо
вычислитьматематическое
ожидание
«количества информации», содержащегося
в цифре из источника информации. Мера
энтропии Шеннона выражает неуверенность
реализации случайной переменной. Таким
образом, энтропия является разницей
между информацией, содержащейся в
сообщении, и той частью информации,
которая точно известна (или хорошо
предсказуема) в сообщении. Примером
этого является избыточность
языка —
имеются явные статистические закономерности
в появлении букв, пар последовательных
букв, троек и т. д. (см. цепи
Маркова).
Определение энтропии Шеннона связано с понятием термодинамической энтропии. Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.
Определение с помощью собственной информации
Также можно определить энтропию случайной величины, введя предварительно понятия распределения случайной величины X, имеющей конечное число значений:[2]
и собственной информации:
I(X) = − log PX(X).
Тогда энтропия определяется как:
От основания логарифма зависит единица измерения информации и энтропии: бит, трит, нат или хартли.