Ломакин Д.В., Туркин А.И. Прикладная теория информации и кодирования

Подождите немного. Документ загружается.

Лекция 11

11.1. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ

Появление теории помехоустойчивого кодирования было вызвано необходимостью

надежной передачи сообщений при наличии помех, которые всегда существуют в

реальных системах.

Рассмотрим наипростейший способ повышения надежности передачи сообщений

посредством многократной передачи одного того же сообщения.

Пусть по каналу связи каждое из сообщений

, образующих

множество Х, передается по три раза. Тогда передачу сообщения

x ( 0

x )

можно рассматривать как передачу по каналу связи соответствующего кодового слова

111 x

= (1000 =

). Число различных последовательностей, которые при этом

могут появиться на выходе канала связи, равно 2

= 8. Они образуют множество

которое назовем множеством выходных канальных последовательностей. Кодовые

слова

также можно считать принадлежащими некоторому множеству

которое назовем множеством входных канальных последовательностей. Оно состоит

из 2

последовательностей.

Для отображения характера взаимодействия помехи и сигнала вводится модель

канала связи, с помощью которой устанавливается связь между передаваемой

последовательностью

и принимаемой последовательностью

в виде:

qke

xy l

⊕= ,

где

- вектор ошибок, который представляет собой последовательность из нулей и

единиц. Единица указывает место, где произошла ошибка, а ноль указывает на

отсутствие ошибки. Суммирование производится по модулю два.

Пусть в канале действует единичная ошибка, т.е. вектор

может содержать только

одну единицу. Из-за единичной ошибки кодовое слово

=111 (

=000) может

перейти только в такие последовательности множества

, которое содержит один

ноль (два нуля), что позволяет безошибочно определить какое кодовое слово было

передано, а следовательно и передаваемое сообщение. Таким образом, множество

делится на два непересекающихся подмножества, которые находятся во взаимно

однозначном соответствии с сообщениями

Последовательности множества

, подлежащие передачи реже (Ш и 000)

называются разрешенными, а все остальные запрещенными. Кодирование в сущности

сводится к разбиению множества

на разрешенные и запрещенные

последовательности (кодовые слова). Часто кодом называют множество разрешенных

кодовых слов. Выбор разрешенных кодовых слов (выбор кода) определяет верность

передачи сообщений.

Таким образом, верность передачи сообщения можно повысить за счет увеличения

числа повторений, т.е. за счет существенного снижения скорости передачи

информации. В

рассматриваемом случае скорость передачи

информации уменьшилась в три раза за

счет

трехкратного повторения. Однако в некоторых условиях ошибку декодирования

можно сделать сколь угодно малой посредством выбора соответствующего

(оптимального) кода, если производительность источника будет меньше пропускной

способности канала на любую сколь угодно малую величину. Существование такого

способа кодирования (кода) было доказано К.Шенноном и сформулировано

им в виде

следующих теорем.

Теорема 1

. Если производительность источника Н

меньше пропускной способности

канала С, то существуют такой код и способ декодирования, при которых возможна

передача сообщений со сколь угодно малой вероятностью ошибки, при

неограниченном возрастании длины последовательности n.

Теорема доказывается при следующей мысленной организации способа передачи

сообщений. Подлежащие передаче сообщения представляют собой

последовательности символов, которые вырабатывает в общем случае марковский

источник сообщений, производительность которого равна Н

. При неограниченном

увеличении длины последовательности n источник вырабатывает с вероятностью,

равной единице, типичные последовательности, количество которых равно

2 .

Будем передавать только типичные последовательности (сообщения), а нетипичные

последовательности вообще не будем передавать, соглашаясь с тем фактом, что в

случае передачи нетипичной последовательности всегда имеет место ошибка.

Т.О., вероятность появления ошибки равна вероятности появления нетипичной

последовательности и стремится к нулю при неограниченном увеличении n.

Специальный “генератор”, производительность которого равна

)(

xH ,

вырабатывает входные канальные последовательности из n независимых символов.

Используются не все, а только типичные входные канальные последовательности,

количество которых равно

)(

xnH

. Нетипичные последовательности нет смысла

использовать, поскольку они появляются с вероятностью, равной нулю, при

неограниченном увеличении n. Множество

входных типичных

последовательностей разбивается на разрешенные и запрещенные последовательности.

Кодлирование осуществляется посредством установления взаимно однозначного

соответствия между разрешенными последовательностями и типичными

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

В теореме утверждается, что при

)/()(

©©

yxHxHCH

−=〈 существует такое

разбиение множества

x на разрешенные и запрещенные последовательности

(существует такой код), при котором вероятность ошибки будет меньше любой сколь

угодно малой наперед заданной величины, если выбрать достаточно большую длину

последовательности n. Докажем, что условие

〈

является необходимым для

передачи сообщения со сколь угодно малой вероятностью ошибки. Доказательство

достаточности не проводим из-за его громоздкости [ ].

С позиций внешнего наблюдателя передающую и приемную части можно

рассматривать как одну сложную систему, а передачу отдельного символа как

реализацию некоторого состояния

yxyx

©©

),( ∈ сложной системы.

Если количество переданных и принятых символов n достаточно велико, то с

вероятностью, близкой к единице, будут появляться типичные последовательности

, и типичные последовательности состояний сложной системы ),(

количество которых соответственно равно:

)(©

2)(

xnH

xQ ≈

)(

2)(

YnH

YQ ≈

),(©

2),(

YxnH

YxQ ≈

Указанные множества типичных последовательностей обозначим соответственно

через

Yx )(

. С учетом равентства )/()(),(

©©

YxHYHYxH += ,

которое следует из ( ), количество типичных последовательностей

)/()/()/()()/()(©

2)(2)(2222)(

xYnHYxnHxYnHxnHYxnHYnH

xQYQYxQ ====

(11.1.1)

Если множества x

’

и Y статистически независимы, то

)()(22)(

©)()(©

xQYQYxQ

xnHYnH

== .

Наличие статистической зависимости между множествами x

’

и Y уменьшает число

типичных последовательностей

)(

YxQ , поскольку всегда,

)/()(

©©

YxHxH > и )./()(

xYYYH >

Таким образом, в образовании типичной последовательности

Yxxx ),(),(

∈

состояний сложной системы могут участвовать все типичные последовательности

∈ и

∈ , но не во всех сочетаниях (рис. 11.1.1).

Обозначим через

)/(

xYQ

число типичных последовательностей

y , которые в

сочетании с типичной последовательностью

могут образовать типичные

последовательности

).,(

Тогда общее число типичных последовательностей

∑

)(

)/()(

xYQYxQ

Можно доказать, что

)/(

xYQ

не зависит от номера типичной последовательности k

. Поэтому (последнее равенство) можно переписать в виде:

)/()()(

xYQxQYxQ

Отсюда с учетом (11.1.1) получим

)/(

)(

),(

)/(

xYnH

YxQ

xYQ ==

В результате аналогичных рассуждений можно получить, что

)/(

)(

),(

)/(

YxnH

YxQ

yxQ ==

Таким образом, при передаче входной канальной последовательности

вероятностью, равной единице будет принята последовательность

y ,

принадлежащая подмножеству

)(

,содержащему

)/(

xYnH

последовательностей.

Аналогично, если была принята последовательность

y , то с вероятностью, близкой к

единице была передана последовательность

,принадлежащая подмножеству )(

содержащему

)/(

yxnH

последовательностей (рис. 11.1.1). Декодирование с

вероятностью, равной единице будет безошибочным только в том случае, если

разрешенные последовательности выбирать таким образом, чтобы соответствующие

подмножества

)(

не пересекались. Максимальное количество непересекающихся

подмножеств равно

,22

)/(

)(

)]/()([

nCxYHYHn

xYQ

N ≈≈≈

−

где пропускная способность канала

xYHYHC

log

)/()(

=−=

определяется максимальным количеством канальных последовательностей N

(разрешенных последовательностей), которые безошибочно могут быть переданы по

каналусвязи.

Очевидно, количество типичных последовательностей, которые вырабатывает

источник сообщений должно быть меньше N :

22 =< . Отсюда CH

< .

Теорема 2.

Если CH

, то среди кодов, обеспечивающих сколь-угодно малую

вероятность ошибки, существует код, при котором скорость передачи информации R

сколь угодно близка к скорости создания информации

H .

Доказат ельство теоремы приведено в работе [ 7 ].

Идея доказательства состоит в следующем. Скорость передачи информации ( на

символ ) определяется как

)/( YxHHR

−

где

)/( YxH - апостериорная энтропия переданного сообщения на символ, или

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

)/( YxH

может быть меньше сколь угодно малой величины, если выбрать достаточно большое

значение n . Отсюда следует, что R сколь угодно мало отличается от

H при

неограниченном увеличении n.

Из теоремы следует, что С можно интерпретировать как предельную скорость

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

Теорема 3.

(Обратная теорема).

Если скорость создания информации

H больше пропускной способности канала С,

то никакой код не может обеспечить сколь угодно малую вероятность ошибки.

Минимальное рассеяние информации на символ, достижимое при

> , равно

− ; никакой код не может обеспечить меньшего рассеяния информации.

Доказательство имеется в [ 7 ].

В теоремах не затрагиваются вопросы построения оптимального кода. Тем не менее

значение их огромно, поскольку, обосновав принципиальную возможность такого

кодирования, они мобилизовали усилия ученых на разработку конкретных кодов.

Лекция 12

ПЕРЕДАЧА НЕПРЕРЫВНЫХ СООБЩЕНИЙ

12.1. Дискретизация непрерывных сообщений и сигналов.

Произвольную кусочно непрерывную функцию

t()

, изображающую сообщение

или сигнал, можно разложить в обобщенный ряд Фурье по полной системе

ортонормированных функций ...)(...)()()(

1100

+= tCtCtCtx

если энергия функции

∫

∞

∞−

= dttxE

)(

конечна [ 9 ].

Бесконечная система действительных функций

),...(...,),(

называется

ортогональной на отрезке [ a, b ], если

∫

dttt 0)()(

ϕϕ

при

≠

а отдельная функция

)(t

называется нормированной, если

∫

dtt 1)(

Система нормированных функций в которой каждые две различающихся функции

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

функции

t()

ограничиваются, как правило, конечным числом членов ряда. При

заданной системе функций

)(t

и при фиксированном числе членов ряда n

значения коэффициентов

можно выбрать такими, при которых среднеквадратичная

ошибка аппроксимации

∫

∑

⎥

⎦

⎤

⎢

⎣

⎡

−

dttCtx

)()(

достигает минимума. Минимум среднеквадратичной ошибки достигается в том случае,

когда коэффициенты ряда определяются по формуле

∫

dtttxC )()(

. Ряд, с

определяемыми таким образом коэффициентами, называется обобщенным рядом

Фурье.

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

членов в ряде среднеквадратичную ошибку можно сделать сколь угодно малой.

Таким образом, по счетному множеству коэффициентов

C можно с определенной

точностью восстановить соответствующую функцию

t()

можно заменить

передачей последовательности коэффициентов

CCC ,...,,

. Указанную

последовательность можно интерпретировать как вектор в n - мерном Евклидовом

пространстве с координатами

CCC ,...,,

квадрат длины которого

∑

C„

Последнее равенство является обобщением теоремы Пифагора на случай n-мерного

пространства. Путем непосредственных вычислений легко установить, что энергия

сигнала

∫

∑

≈=

CdttxE

)(

Таким образом, дискретизацией называется замена непрерывной функции

t()

последовательностью коэффициентов

CCC ,...,,

... (вектором).

Выбор системы ортогональных функций

)(t

определяется целью и физической

сущностью решаемой задачи, а не чисто математическими умозаключениями.

С целью передачи сигнала по каналу связи широко применяется разложение

функции

t()

в ряд Котельникова, которое позволяет существенно упростить

определение коэффициентов

C .

Согласно теореме Котельникова произвольная функция

)(tx

с ограниченным

спектром, может быть тождественно представлена счетнывм числом ее значений,

взятых через интервал времени

t =Δ

где F - верхняя граничная частота спектра

сигнала. В этом случае функции

)(

)(sin

)(

tntF

Δ−

−

образующие систему ортогональных функций, отличаются друг от друга только

сдвигом по оси времени t на величину кратную

=Δ

, при этом каждая из них

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

остальных функций равны нулю. Коэффициенты разложения определяются по

формуле

∫

∞

∞−

= dtttx

)()(

которую в результате тождественных преобразований можно привести к виду:

)( tixC

Δ= , то есть

C коэффициент равен значению функции

t()

в момент,

когда функция

)(t

достигает своего максимального значения.

Если дискретизации подлежит нормальный (гауссов) случайный процесс,

энергетический спектр которого имеет прямоугольную форму, то коэффициенты

будут статистически независимыми случайными величинами, которые совпадают со

значениями случайной функции

t()

, взятыми с шагом Δt [ 9 ].

Таким образом, непрерывные сообщения можно передавать в цифровом виде, то есть

в виде последовательности чисел, при этом каждое число приближенно выражает

величину соответствующего коэффициента

C .

12.2. Энтропия системы с непрерывным множеством состояний

Система называется непрерывной по данному описывающему ее параметру, если

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

перенумеровать: они непрерывно переходят одно в другое, причем каждое отдельное

состояние имеет вероятность, равную нулю, а распределение вероятностей

характеризуется некоторой плотностью

)(xP . Например, генератор шума,

напряжение на выходе которого может принимать любое значение, является

непрерывной системой по указанному параметру.

Попытаемся ввести количественную меру определенности непрерывной случайной

величины Х через энтропию

)(

дискретной случайной величины

, которая

получается в результате квантования непрерывной величины Х по уровню.

Математически квантование можно представить как нелинейное преобразование

непрерывной величины Х (рис. 12.2.1). Вся область возможных значений величины Х

разбивается на интервалы с длиной, равной

xΔ . Каждому интервалу ставится в

соответствие некоторое значение

x , принадлежащее дискретному множеству

Вероятность появления значения

x равна вероятности попадания случайной

величины Х в соответствующий интервал. Чем меньше интервал квантования

тем точнее дискретная величина

отображает свойства непрерывной величины Х

. Поэтому в качестве количественной меры неопределенности случайной величины Х

логично использовать значение энтропии

)(

при x

стремящимся к нулю :

xdxxPxPxxPxxPxH

Δ−−=ΔΔ−=

∫

∑

∞

∞−

→Δ

∞

−∞=

→Δ

loglim)(log)(])(log[)(lim)(

©©

(12.2.1)

Первый член в (12.2.1) не зависит от

- степени точности, с которой

определяется состояние системы. От

зависит только второй член ( xΔ− log ),

который стремится к бесконечности при

стремящимся к нулю. Это и

естественно, поскольку чем точнее мы хотим задать состояние системы, тем большую

неопределенность мы должны снять.

Таким образом, мы убедились, что система с непрерывным множеством состояний

не допускает введения конечной абсолютной меры неопределенности. Однако можно

ввести количественную меру неопределенности указанной системы по отношению к

другой непрерывной

системе, состояния которой описываются случайной величиной

Y с некоторым стандартным распределением. В качестве последнего (эталонного)

удобно использовать равномерное в некотором интервале d распределение

пидугихy дляк отоог

()

рр , р

−<<

⎧

⎨

⎪

⎩

⎪

энтропия

)(

YH согласно (12.2.1) равна

∫

−

Δ−=Δ−=

logloglog

log

)(

xdxdy

Относительной (дифференциальной) энтропией случайной величины Х называется

величина

dxxdPxPYHxHxH ])(log[)()()()(

©©

∫

∞

∞−

−=−=

В частности, если интервал d = 1, то

∫

∞

∞−

−= dxxPxPxH )(log)()(

Выясним физический смысл относительной энтропии

)(xH .

Пусть источник сообщений вырабатывает последовательность значений случайной

величины Х. После квантования получим последовательность значений случайной

величины

©©©©

...,,...,,,

21 nk

iiii

xxxx

При неограниченном увеличении длины последовательности с вероятностью, равной

единице, появляются только типичные последовательности, число которых

xnHxxnHxnxnHxnH

⋅====

Δ−Δ−

2222

)()log()(log)()(

где

xV )(Δ=Δ - число элементарного n - мерного кубика. Конец вектора,

изображающего типичную последовательность, является внутренней точкой этого

кубика. Произведение

)(

xnH

QV =⋅Δ равно объему некоторой области в n -

мерном пространстве, внутренние точки которой изображают концы типичных

векторов (последовательностей). При

, стремящимся к нулю, число типичных

последовательностей стремится к бесконечности, в объем каждого элементарного

кубика стремится к нулю. При этом объем

, занимаемый типичными

последовательностями, остается постоянным, равным

)(

xnH

Энтропию в дискретном случае можно было определить через число типичных

последовательностей:

log

lim)(

∞→

Аналогично относительную энтропию можно определить через объем

занимаемый

типичными последовательностями:

log

lim)(

0→Δ

∞→

= .

В отличие от дискретного случая относительная энтропия может быть не только

положительной, но и отрицательной, а также равной нулю. Чем больше объем

V ,

занимаемой типичными последовательностями, тем больше неопределенность того,

какая из них появится. Единичному объему (

V =1) соответствует энтропия

(неопределенность), равная нулю (

)(xH =0). Это значение принимается за начало

отсчета относительной энтропии.

В частности, относительная энтропия случайной величины с равномерным на

единичном интервале ( d = 1 ) распределением равна нулю:

0log)(

dxH .

В этом случае область n - мерного пространства, занимаемая типичными

последовательностями, примерно совпадает с областью определения всех

последовательностей и имеет форму куба единичного объема (

V =

d =1).

Лекция 13

13.1. Экстремальные свойства энтропии

Одной из основных характеристик, используемых при проектировании

информационных систем, является энтропия. Поэтому часто возникает необходимость

определения закона распределения случайной величины

, при котором энтропия

)( XH имеет максимальное значение. Например, эффективность искусственно

создаваемых помех тем выше, чем больше значение энтропии

)( XH . Поэтому при

заданной мощности генератора целесообразно выбирать тот закон распределения

помехи, при котором значение энтропии

)( XH максимально.

Для дискретного множества

было установлено, что при равномерном

распределении вероятностей энтропия

)( XH имеет максимальное значение, равное

mlog . Однако, в случае систем с непрерывным множеством состояний аналогичная

задача не имеет решения, если на непрерывную случайную величину

априори не

наложить некоторые ограничения. Например, можно ограничить дисперсию или

область определения случайной величины.

Экстремальные свойства относительной энтропии удобно интерпретировать через

объем подпространства, который занимают типичные последовательности. Согласно

равенству

)(

xnH

V ≈ , чем больше объем указанного пространства, тем больше

относительная энтропия

)( XH (больше неопределенность того, какая изтипичных

последовательностей будет выбрана).

Приведем несколько примеров.

1. Пусть известно, что область

возможных значений случайной величины

ограничена интервалом

],[ ba , )( bxa

≤

. Найдем распределение, обладающее при

этом максимальной относительной энтропией. В данном случае область определения

всех возможных последовательностей представляет собой

n - мерный куб, сторона

которого равна

−

. Очевидно энтропия )( XH будет иметь максимальное

значение, если подобласть определения типичных последовательностей будет

совпадать с областью определения всех последовательностей. Только в этом случае

объем

V имеет максимальное значение

ab )( − , равное объему n - мерного куба,

сторона которого равна

−

. При этом энтропия

)log(

log

lim)( ab

−==

∞→

Приведенные рассуждения не являются строгим доказательством последнего

равенства. Строгое доказательство можно найти в литературе [8,10,11].

2. Если на случайную величину

наложить следующие ограничения:

а) область возможных значений неограничена

)(

∞

≤

−

∞ x ;

б) известно среднее значение величины

;

в) задана дисперсия

случайной величины

, то закон распределения,

доставляющий максимум энтропии

)(xH

, будет нормальным.

3. В случае, когда

может принимать только положительные значения 0)(( =xp

при

)0<x и первый момент

равен a , максимальное значение энтропии )(xH

достигается при

⎟

⎠

⎞

⎜

⎝

⎛

xp exp

)(

13.2. Взаимная информация для систем с непрерывным множеством состояний

Представим непрерывные множества

в виде суммы счетного множества

непересекающихся интервалов

. Будем говорить, что система

)(, BA находится

i - ом (

- ом) состоянии, если оно определяется значением случайной величны

)( yx , принадлежащей

- му интервалу

)(

∈

Проквантовав таким образом непрерывные случайные величины, мы получим два

дискретных множества

ΔΔ

YX ,

, которые тем точнее описывают непрерывные

множества, чем меньше интервалы

xΔ и

yΔ .

Вероятность нахождения системы

)(, BA в

- ом (

- ом) состоянии равна

jjii

yybyyPxxbxxP

≈

Δ∈Δ

≈

∈ )()((,)()( ,

а совместная вероятность

jiji

yxyxbyyxxP

=Δ∈

∈

),(),( .

Теперь согласно (2.5.1), можно определить взаимную информацию

i - м элементом

множества

X и

- м элементом множества

Y как

yyPxxP

yyxxP

Δ∈Δ∈

()(

),(

log

Разделив числитель и знаменатель на произведение

получим:

⎥

⎦

⎤

⎢

⎣

⎡

∈

⎥

⎦

⎤

⎢

⎣

⎡

Δ∈

Δ∈Δ∈

ΔΔ

)(

),(

log

yyP

xxP

yyxxP

Переходя к пределу при

yΔ стремящихся к нулю, получим взаимную

информационную плотность

)()(

),(

log),(

ybxb

yxb

yxi =

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

бесконечно малыми интервалами

xΔ и

yΔ , которые стягиваются соответственно в

точки

Взаимная информационная плотность является случайной величиной, среднее

значение которой равно

∫∫

∞

∞−

= dxdy

ybxb

yxb

yxbyxI

)()(

),(

log),(),(

Величину

),( yxI

часто называют средней взаимной информацией или просто

взаимной информацией.

В качестве примера вычислим взаимную информацию, которой обмениваются два

абонента, разговаривающие по телефону. Напряжение, развиваемой на выходе

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

Это напряжение представляет собой нормальный случайный процесс

)(tX с

дисперсией, равной

В результате действия помех, слушающий абонент, вместо поступившей в линию

реализации

)()( tXtx

∈

примет реализацию )()()( tntxty

где

)(tn - реализация нормального шума, дисперсия которого равна

. Тогда

случайный процесс

)(tY

, которому принадлежит реализация

)(ty

, будет имет

нормальный закон распределения как сумма двух случайных процессов снормальным

(гауссовским) распределением. Поскольку процесс

)(tX и шум статистически

независимы, то дисперсия

)(tY будет равна

222

XNY

σσσ

+= . Теперь можно

вычислить взаимную информацию между двумя случайными величинами

которые равны значениям случайных процессов

)(tX

)(tY

в некоторый

фиксированный момент времени

t .

При вычислении взаимной информации по формуле

)/()(),( XYHYHYXI

−

(13.2.1)

нам понадобятся следующие распределения случайной величины

)(

eyb

σπ

−

)(

)/(

exyb

σπ

−

= .

Энтропия

2log

log

2log)(log)(

ybYH

σπ

=+=−=

При этом было использовано равенство

Условная энтропия

∫∫

∞

∞−

∞

∞−

−= dxdyxybxybxbXYH ])/(log)/()[()/(

Усредняя

xyb

log

)(

2log)/(log

σπ

−

+=−

сначала по

, то есть вычисляя выражение в квадратных скобках, получим

.2log

log

)(

2log)/(log

xyb

σπ

−

+=−

При этом было использовано равенство

)(

=− .

Поскольку выражение в квадратных скобках не зависит от

, то

2log

)/(

eXYH

σπ

= .

Подставляя в (3.3.1) вычисленные энтропии

)(YH и )/( XYH , получим

)1log(

),(

YXI

+= .

ПРОПУСКНАЯ СПОСОБНОСТЬ ГАУССОВСКОГО КАНАЛА СВЯЗИ

Канал будем называть гауссовским, если он удовлетворяет следующим условиям:

1) полоса пропускания канала ограничена частотой

F , 2) шум в канале имеет

нормальный (гауссовский) закон распределения, 3) энергетический спектр шума

равномерен в полосе пропускания канала и имеет значение, равное

N , 4) мощность

сигнала

)(tx фиксирована и равна

, 5) сигнал )(tx и шум )(tn

статистически независимы, 6) канал аддитивен, то-есть выходной сигнал

)()()( tntxty ==

Пропускная способность канала

)]/()([max

)(

XYHYHC

−

Частная энтропия

)/( xYH равна энтропии шума )(NH , поскольку из равенства

y +=

следует, что значения

и n находятся во взаимно однозначном

соответствии при фиксированном значении

. Энтропия )/( XYH , которая

получается в результате усреднения частной энтропии

)/( xYH

по всем значениям

, также равна )(NH . Отсюда )()(max

)(

NHYHC

−

= . Максимальное значение

энтропии

)(YH доставляет гауссовский закон распределения случайной величины

при заданном значении дисперсии

222

NXY

σσσ

+= . Дисперсия

равна сумме

дисперсий

, поскольку сигнал и шум статистически независимы. При этом

случайная величина

с необходимостью должна иметь гауссовский закон

распределения как разность

−= случайных величин с гауссовскими

законами распределения. Тогда значение пропускной способности будет равно

значению взаимной информации

),( YXI

, которая определяется выражением

)1log(

qC += [ бит/символ ] ,

где

называется отношением сигнал/шум.

Если отсчеты процесса

)(tY

на основании теоремы Котельникова выбрать с шагом

=Δ

, то за 1 секунду будет передано 2F отсчетов. Эти отсчеты в случае

гауссовского шума статистически независимы и поэтому пропускуную способность

канала можно определить следующим образом:

)1log(2

qFFCC

+==

[бит/С]

Заданного значения

C можно достигнуть как за счет увеличения

q (мощности

передатчика при заданной мощности шума) так и за счет увеличения полосы

пропускания канала

F . Однако, компенсировать возможное сокращение полосы

пропускания канала за счет увеличения мощности передатчика, как правило,

нецелесообразно, поскольку

C зависит от

q по логарифмическому закону, а от F

по линейному. Более эффективным является увеличение значения

C за счет

увеличения

F . Однако, следует иметь в виду, что с увеличением полосы пропускания

канала увеличивается и мощность шумов, попавших в канал, что приводит к

снижению отношения сигнал/шум. Если шум в канале считать белым, то мощность

шума

N 0

)1log(

Пропускная способность

C сначала быстро растет с ростом F , а затем

асимптотически стремится к пределу

log

∞

[бит/С].

Согласно второй теореме К.Шеннона надежная передача сообщений в принципе

возможна при

∞

CR . Умножая неравенство на время передачи сообщения

получим

TCRTI

log

=<=

∞

то-есть количество информации

, которое надежно можно передать по каналу,

должно быть меньше

log

, где TE

= - энергия сигнала. В частности, для

передачи 1 бита информации необходима энергия,равная

693,0log/ NeNE

≈> .

8.4. ЭПСИЛОН - ЭНТРОПИЯ

Проблема передачи непрерывного сообщения заключается в получении его копии на

приемном пункте и, в сущности, сводится к процедуре воспроизведения сообщения на

основе полученной информации. Очевидно, в данном случае не существует способа,

позволяющего получить точную копию передаваемого сообщения, поскольку это

требует бесконечной точности его воспроизведения, причем неограниченное

увеличение точности требует неограниченного

увеличения количества передаваемой

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

Поэтому о передаче непрерывного сообщения имеет смысл говорить только в том

случае, когда задана точность его воспроизведения.

Передача непрерывного сообщения

)(tx

сводится к передаче последовательности

его значений взятых в дискретные моменты времени. Все возможные значения

функции

)(tx в некоторый момент времени образуют множество

Пусть случайная величина

имеет равномерное на отрезке

[

]

ba, распределение.

Тогда распределение дискретной случайной величины

также будет равномерным,

если все интервалы на которые разбит отрезок

[]

ba, , имеют одну и ту же длину. При

таком разбиении энтропии

)(

XH достигает своего максимального значения,

равного

Nlog , где

- число элементов в множестве

Количество взаимной информации между множествами

, определяемое

равенством

)/()(),(

111

XXHXHXXI −= ,

равно энтропии

)(

XH , поскольку неопределенность )/(

XXH , с которой

значение случайной величины

определяет значение случайной величины

равна нулю. Поэтому для воспроизведения значения случайной величины

точностью

xΔ

требуется количество информации, равное )(

XH .

Пронумеруем все элементы множества

числами от 1 до

и запишем их в m -

ичной системе счисления. Минимальное количество разрядов

, некоторое при этом

потребуется, удовлетворяет неравенству:

1loglog

≤

NnN

Если величина

log окажется целым числом, то количество информации,

необходимое для воспроизведения значения случайной величины

с заданной

точностью, непосредственно равно в

m - ичных единицах количеству символов n

(разрядов), передаваемых по каналу связи. Повышение точности требуют уменьшения

длины интервала

xΔ , а, следовательно, и увеличения количества передаваемой

информации.

Более универсальной мерой точности воспроизведения по сравнению с

является

среднеквадратичная ошибка

[

]

)( XX

−

которую при неравномерном распределении случайной величины

можно

минимизировать не только путем увеличения количества интервалов

, но и путем

изменения их длины. При этом энтропия

)(

XH также будет изменяться.

Таким образом, количество информации, которое требуется для воспроизведения

значения случайной величины

с заданной точностью (с заданной

среднеквадратичной ошибкой), зависит от выбранной меры точности и от характера

статистической зависимости между множествами

(от преобразования

случайной величины

в случайную величину

), в частности, от того, каким

образом выбраны длины интервалов

и их количество. Канал, устанавливающий

связь между множествами

, описывается условной вероятностью

)/(

XXp и, в сущности, представляет собой устройство квантования.

Определим ε - энтропию как минимальное по

)/(

XXp количество информации,

необходимое для воспроизведения значения случайной величины

с заданной

точностью при заданном распределении

)(xp источника:

),(min)(

)/(

XXIXH

XXp

Следует напомнить, что пропускная способность канала

C была определена как

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

)/(

XXp , а по

распределению источника

)(xp при заданной статистической связи между

множествами

(при заданном распределении )/(

XXp .

При квантовании непрерывной величины

указанная ε - энтропия равна

энтропии

)(

XH . Поскольку NXH log)(

≤ , то передача информации в виде

чисел, записанных в

m - ичной системе счисления и имеющих число разрядов, равное

)(log N

, не будет экономной. Поэтому целесообразно предварительно осуществить

экономное кодирование сообщений, в роли которых должны выступать элементы

множества

Отметим, что ε - энтропия также используется и в качестве количественной меры

производительности источника непрерывных сообщений, при этом, очевидно, нельзя

говорить о производительности источника не задав точность воспроизведения.

Таким образом, производительность источника можно определить как минимальное

количество информации

)( XH

, необходимое в единицу времени для

воспроизведения непрерывного сообщения

)(tx c заданной точностью, где ν - число

отсчетов сообщения

)(tx , передаваемых за единицу времени.

Кроме квантования существует много других способов преобразования непрерывной

величины

. В частности, множество

может представлять собой результаты

измерений величины

. Пусть непрерывная величина

с некоторой

погрешностью η воспроизводит нормально распределенную случайную величину

xx . Тогда при заданной дисперсии

погрешности (при заданной

среднеквадратичной ошибке) ε - энтропия нормальной величины

равна [ 8 ]

log

)(

XH = ,

где

- дисперсия случайной величины

6.3. Вычисление пропускной способности канала со стиранием.

Приемное устройство на основе анализа реализации принятого сигнала выносит

решение о том, какая буква (сообщение) была передана. В некоторых случаях

создается такая помеховая обстановка, что вынести решение в пользу той или иной

буквы не представляется возможным. В этом случае целесообразнее вообще не

принимать решение о том, какая буква была передана

. Указанный отказ от решения θ

является тоже решением и входит в множество решений

наравне со всеми

остальными решениями. Вынужденный отказ от решения часто возникает в проводных

каналах связи при нарушении контакта (обрыве). В этом случае сигнал просто не

проходит на выход канала и мы вынуждены отказаться от принятия решения даже в

случае отсутствия внешних помех.

Вычислим пропускную способность канала, диаграмма переходных вероятностей

которого

изображена на рис. 6.3.1

)3,2( ==

Указанный канал описывается матрицей:

⎟

⎠

⎞

⎜

⎝

⎛

−−

θθ

,,1

Поскольку строки матрицы различаются только перестановкой чисел

p ,

pp −−

1 , то соответствующий канал симметричен по входу.

Для симметричного по входу канала условная энтропия

)/( XYH не зависит от

вида распределения источника сообщений и полностью определяется параметрами

канала

p и

p . Согласно (6.2.1)

)]1log()1(loglog[)/(

θθθθ

ppppppppXYH

−

−+

−

−=

llll

(6.3.1)

Поэтому пропускная способность канала

)/()(max XYHYHC

−

(6.3.2)

Вычислим

)(max YH

, энтропия

)(YH

определяется через вероятности:

θθθ

pppppp

ppppppyp

=−+=

=−−−+=

=−+

−

)1()(

)1)(1()(

)1()1()(

где обозначения

введены для сокращения записи. Из последнего равенства

следует, что безусловнгая вероятность

)(

равна условной вероятности

)(

Принимая во внимание, что

ppp , имеем:

]log)1log()1(log[

]logloglog[)(

1111

2211

θθθθ

θθ

pppppppp

ppppppYH

+−−−−+−=

−=

Отсюда следует, что

)(YH

зависит от

( от распределения источника ) только

через

Значение

, при котором

)(YH

достигает своего максимального значения,

определяется из уравнения

)(

∂

которое для данного случая имеет вид:

log)21(

−

−−

Последнее уравнение распадается на два уравнения:

log

021

−−

−

Если параметры канала

p и

p удовлетворяют первому уравнению, то-есть

p =0,5 (1-

p ), то пропускная способность канала C =0. При этом

ppp ==

независимо от значения вероятности

Решением второго уравнения является

p =0,5 (1-

p ). Поскольку

=++

ppp

то

p =0,5 (1 -

p ). Последние равенства имеют место только при

=0,5.

Таким образом,

)(YH

достигает своего максимального значения, равного

{

}

]1)1)[log(1(log)(max

−

θθθθ

ppppYH

при равномерном распределении источника

5,0)()(

xpxp .

Подставляя полученный результат в (6.3.2) и учитывая (6.3.1), получим:

llll

ppppppppC log)1log()1()]1log(1)[1(

−

θθθθ

(6.3.3)

Для канала со стиранием без ошибок (например, для проводного канала без внешних

помех) пропускная способность

−

1 [ бит/символ ].

Она получается из (6.3.3) при вероятности ошибки

p =0.

Рассмотрим реализацию одного простого канала со стиранием. Пусть по каналу

требуется передать последовательность из нулей и единиц. В качестве сигнала

(переносчика) возьмем последовательность элементарных посылок напряжения.

Положительная посылка будет соответствовать единице, а отрицательная - нулю. Одна

из реализаций

)(

tU сигнала изображена на рис. 6.3.2. Напряжение на выходе канала

(рис. 6.3.3)

)()()(

tntUtU

= где )(tn - реализация нормального (гауссова)

шума.

ПОНЯТИЕ ИНФОРМАЦИИ В КАТЕГОРИАЛЬНОМ ЭЙДОСЕ УНИВЕРСУМА

Д.В.Ломакин

Понятие информации как философская категория может быть осмыслено

только в совокупности с другими категориями, которые имеют не меньшую степень

общности. Эти категории образуют категориальный эйдос (цельный смысловой лик

вещи) Универсума, который является наиболее общим понятием из всех, доступных

человеческой мысли. Логически последовательное развертывание категориального

содержания Универсума позволяет установить его системоиерархическую

организацию и поэтому любую вещь, в том числе и человека, будем рассматривать как

некоторую систему, которая на правах элемента входит в соответствующую

надсистему.

Таким образом, Универсум можно представить как многоуровневую,

многоплановую систему, каждый уровень которой организован не только общими, но

и специфическими для данного уровня законами, причем, нижележащий уровень

является

субстратом (материей), некоторым фоном, на котором проявляется,

организуется вышележащий уровень.

Новая система зарождается в недрах надсистемы как некоторая ее

потребность (значимость или смысл), обусловленная развитием структур надсистемы.

Зарождающаяся система - это хрупкий росток будущего, судьба которого существенно

зависит от окружающей среды и той “ниши” которую зарождающаяся система

занимает в надсистеме. Эта

ниша регламентирует эволюцию системы, ее становление,

определяет свободу системы и является ее причиной.

Становление системы заканчивается ставшим фактом, функции которого

удовлетворяют потребности надсистемы. С этого момента система становится

“зрелой”, замкнутой системой, в которой потребность надсистемы, “ниша”

проявляется как ее апофатическая сущность. С другой стороны сущность

(проявленная, положенная) ставшей системы

своеобразным образом (идеально) бытует

в ее структуре, определяется структурными связями и отношениями. Замкнутость не

означает изолированность системы. Это прежде всего замкнутость взаимосвязей

внутри системы, это то, что Гегель называет “для себя бытие”. В математике

примерами замкнутых систем могут служить группы, замкнутые пространства.

Любая система прежде чем быть реализованной, проявленной,

организованной

на некотором уровне должна существовать в виде определенной

структуры на вышележащем уровне, например, в виде доктрины на ментальном

уровне. Структура самой доктрины включает в себя идею, концепцию, программу и

механизм реализации (см., например, Л.А.Зеленов “Методология социального

проектирования”, 1995). Существенным моментом этой структуры является то, что она

аналогична “тетрактиде А”

Лосева А.Ф. Особенность доктрины и “тетрактиды А”

заключается в том, что кроме гегелевской триады - тезис, антитезис, синтез, они

содержат метод реализации, который Лосев А.Ф. называет четвертым началом, первым

трем началам Лосева А.Ф., очевидно, соответствует идея, концепция и программа.

Таким образом, структура является необходимым звеном в механизме

реализации

любой идеи (сущности), т.е. идея должна быть сначала положена,

определена на вышележащем уровне. Эту функцию выполняет интеллектуальная

деятельность, в результате которой создаются конкретные доктрины и новые проекты.

Структура является инвариантной по отношению к своему носителю (синалу)

и поэтому может перемещаться (рефлексия) с носителя на носитель, подвергаться

преобразованию или просто

оставаться в относительном покое. Указанные

преобразования структур, сопровождают любую человеческую деятельность, но то,

что именно структуры подвергаются преобразованию, первоначально не было

осмысленно и поэтому то, что подвергалось преобразованию было названо

информацией.

Таким образом, информация - это структура или упорядоченное множество.

Понятие информации возникло как отражение факта свободного “движения” структур,

а поскольку

принцип организации структуры один и тот же на всех уровнях,

доступных человеческой мысли, то и понятие информации применимо для описания

всех этих уровней, причем этим принципом по Лосеву А.Ф. является число как

принцип организации любой вещи.

Каждая структура как сущность может проявляться (материализоваться) в

своем разнообразии форм, которое характеризует

степень организации структуры.

Поэтому возникает возможность количественного сравнения структур через

разнообразие форм их реализации. Поскольку проявление сущности в той или иной

форме, как правило, случайно, то и разнообразие воспринимается как хаос. Отсюда

следует, что хаос (неопределенность) является мерой структурности, и поэтому в

классической теории информации количество информации (степень наличия

структурности) определяется

как мера снятой неопределенности. Каждая структура

потенциально содержит в себе все свое разнообразие форм реализации и поэтому

может быть принята за единицу измерения информации. Практически это

разнообразие обнаруживает себя как разнообразие состояний системы, в которой

реализована данная структура. Сбор информации о системе - есть определение ее

возможных состояний, образующих “отраженное разнообразие”,

которое на

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

проект или доктрина, причем каждое состояние системы также является системой как

некоторая замкнутая определенность.

Элементарной моделью иерархической организации Универсума является

позиционная запись числа, где каждый разряд, соответствует определенному уровню, а

значение разряда определяет количество состояний системы на

данном уровне.

Таким образом, определены качественная и количественная стороны понятия

информации и его место в категориальном эйдосе Универсума.