- •Конспект лекций по дисциплине Теоретические основы информационных процессов
- •Глава 1 Основные понятия теории информационных систем
- •1.1. Основные понятия и определения
- •1.2. Вторичные понятия и определения теории систем
- •1.3. Классификация систем
- •Глава 2 Теорико-вероятностные методы теории информационных процессов
- •Глава 3 Модели и методы описания систем
- •3.1. Методы описания систем
- •3.3. Кибернетический подход к описанию систем
- •3.1. Теоретико-множественный подход к описанию систем
- •3.4. Агрегативное описание систем
- •3.5. Марковские цепи
- •Глава 4 Основы количественной теории информации
- •4.1. Основные понятия теории информации
- •4.2. Количество информации
- •4.3. Энтропия и ее свойства
- •Глава 5 Информационные процессы и сигналы
- •5.1. Общая схема передачи информации в линии связи
- •5.2. Модели сигналов
- •5.3. Передача информации по каналу связи без учета помех
- •5.4. Передача информации по каналу с помехами
- •Глава 6 Помехоустойчивое кодирование сообщений
- •6.1. Общие принципы помехоустойчивого кодирования.
- •6.2. Систематические коды
- •6.3. Циклические коды
5.4. Передача информации по каналу с помехами
До сих пор мы предполагали, что информация, поступившая от кодера/передатчика в канал связи в точности соответствует информации, принятой приемником/декодером из канала. Наличие помех в канале связи приводит к тому, что часть информации при перемещении по каналу теряется, искажается, зашумляется. Информация, принятая приемником, не полностью снимает неопределенность относительно переданной источником, хотя и уменьшает ее. Если на вход канала связи поступил сигнал u, а с выхода канала принят сигнал v, то говорят о взаимной информации I(u,v).
Понятие о канальной матрице
Ситуацию с передачей информации по каналу связи с помехами можно описать, используя аппарат марковских цепей.
Посылку
в канал в момент времени tk
одного из символов ui
представим как нахождение системы в
состоянии i.
Всего таких состояний – Nu.
Прием из канала в следующий момент
времени tk+1
одного из символов vj
представим как переход системы из
состояния i
в
состояние j.
Интервал времени tk+1-tk
равен средней длительности передачи
одного символа τ.
Вероятности нахождения системы в
состоянии i
равны
вероятности генерации источником
символа ui.
Вероятности перехода за время из
состояния i
в состояние j
равны
условной вероятности p(vj|ui)
принятия
символа vj
при условии, что послан символ ui.
Таким образом, функционирование системы
на одном шаге описывается вектором
начальных вероятностей p(ui),
(i=
),
представляющим собой распределение
вероятностей символов первичного
алфавита, и матрицей переходных
вероятностей p(vj|ui)
размером
Nu×Nv.
Матрица переходных вероятностей называется канальной матрицей.
Пропускная способность бинарного симметричного канала с помехами типа «инверсия»
Рассмотрим работу достаточно типичной системы связи, в которой информация передается двоичными сигналами «0» и «1», имеющими разные уровни квантования. Приемное устройство анализирует выход канала в течение промежутка времени, соответствующего длительности элементарного сигнала и вычисляет некоторую скалярную величину µ (уровень принятого сигнала). Решение принимается сравнением µ с некоторым порогом ρ. При µ > ρ принимается решение в пользу «1», в противном случае, при µ < ρ, решением будет «0». При правильном выборе порога ρ вероятности ошибок при передаче сигналов будут одинаковыми, и мы приходим к модели бинарного симметричного канала с инверсией (Б.С.К.И.) Недостаток такой простейшей схемы приема состоит в том, что демодулятор теряет информацию о надежности принимаемых сигналов. Очевидно, значениям µ ≈ ρ соответствуют ненадежные решения, и эти сведения могут быть полезными при последующей обработке информации.
Пропускная способность симметричного канала со стиранием
Рассмотренную выше систему связи можно усовершенствовать, введя «защитный интервал» или «зону стирания». При µ > ρ +Δ решение принимается в пользу 1, а при µ < ρ - Δ принимаются решение в пользу 0. При ρ –Δ < µ < ρ +Δ символ искажается настолько, что становится «неузнаваемым». Получаем модель бинарного симметричного канала со стиранием символа (Б.С.К.С.). Это небольшое изменение заметно повышает эффективность системы, поскольку задача исправления стираний проще задачи исправления ошибок. Один и тот же корректирующий код позволяет исправить примерно в два раза больше стираний, чем ошибок.
Теорема Шеннона для дискретного канала с помехами
Для дискретного канала с помехами К.Шенноном была доказана следующая теорема (вторая теорема Шеннона):
Если производительность источника R ≤ C – ε, где ε – сколь угодно малая положительная величина, то существует способ кодирования, позволяющий передать все сообщения источника со сколь угодно малой вероятностью ошибки.
Если производительность информационной системы меньше пропускной способности канала, то сообщение от этого источника можно преобразовать так, чтобы передавать их по каналу с помехами с любой степенью точности, т. е. за счет существования избыточности в сообщениях, вводимой специальным образом, можно уменьшить вероятность ошибки до сколь угодно малой величины.
С точки зрения технической реализации эта теорема означает, что существует способ кодирования и декодирования, при котором вероятность ошибочного декодирования может быть сколь угодно малой. Если R > С, то таких способов не существует.
Вторая теорема Шеннона является идеологической основой для существования помехоустойчивого (корректирующего) кодирования в каналах связи.
Пропускная способность непрерывного канала связи с помехами
Выше мы обсуждали передачу информации в канале связи посредством дискретных сигналов. Однако при этом непосредственно сам канал связи - проводники, электромагнитное поле, звук, оптоволоконные линии и прочее – свойствами дискретности не обладает. Другими словами, по тем же каналам может передаваться и аналоговая информация – характер передаваемых сигналов определяется передатчиком. Линии связи, основанные на использовании аналоговых сигналов, имеют весьма широкую область практического применения - это радио- и телевизионная связь, телефон и модем, различные телеметрические каналы и тому подобное.
Непрерывным называется канал, который обеспечивает передачу непрерывных (аналоговых) сигналов.
Непрерывные сигналы, поступающие в канал связи из передатчика (Пд) описываются некоторой непрерывной функцией времени X(t).
Теорема Шеннона для непрерывных каналов с помехами
Производительность
источника непрерывных сообщений
пропорциональна энтропии источника
.
Поскольку энтропия источника непрерывных
сигналов – бесконечно большая, то и
производительность такого источника
– бесконечно большая. На практике даже
при безошибочной передаче сигнала по
каналу связи приемник воспринимает
поступивший сигнал с какой-то погрешностью.
Принятое
сообщение Z(t)
и переданное X(t)
называются эквивалентными, если различие
между ними несущественно в смысле
выбранного критерия (обычно это критерий
среднеквадратичного отклонения).
Вводится понятие отклонения ε(t) = x(t)
– z(t),
задается предельная погрешность
.
Если среднее за период отклонение
<
,
то реализации считаются эквивалентными.
Эпсилон-энтропией Hε(X) называется минимальное среднее количество информации, содержащееся в одном отсчете сообщения Z(t) относительно сообщения X(t), при котором эти сообщения еще эквивалентны.
В соответствии с соотношением Hε(X) = min {I(X,Z) | ≥ ε2} эпсилон-энтропия определяет количество существенной информации, содержащейся в одном отсчете непрерывного сообщения.
Производительность
источника определяется как
.
По теореме Котельникова
,
где F
– полоса
пропускания, значит R = 2F∙Hε(X).
Теорема Шеннона для непрерывного канала с помехами (третья теорема):
Если при заданном критерии эквивалентности сообщений производительность источника информации меньше пропускной способности канала, то есть R < C, то существует такой способ кодирования и декодирования в обобщенном смысле (т. е. преобразование сообщения в сигнал и обратно), при котором неточность воспроизведения сообщения сколь угодно близка к . При R > C такого способа не существует.
