Вопросы к экзамену по теории информации

Вопросы на экзамен
Выберите любые три, дайте расширенный ответ
1. Теория информации как наука. Информация, сообщения, сигналы (понятия).
2. Передача информации в информационной системе.
3. Случайные модели в задачах теории информации. Случайная величина.
4. Случайные модели в задачах теории информации. Случайное событие.
5. Измерение информации (меры информации)
6. Информационная мера Шеннона. Энтропия. Условная энтропия.
7. Свойства энтропии дискретного и непрерывного источников информации
8. Избыточность информации. Взаимная информация.
9. Обобщенные характеристики сигналов и каналов
10. Характеристика канала связи без помех. Теорема Шеннона для канала без помех.
11. Характеристика канала связи с помехами. Теорема Шеннона для канала с помехами.
12. Значение результатов Шеннона.
13. Сжатие данных
14. Экономное кодирование
15. Процедуры Шеннона-Фано и Хаффмена
16. Помехоустойчивое кодирование. Основные принципы помехоустойчивого кодирования.
17. Помехоустойчивое кодирование. Помехоустойчивость кода. Корректирующие коды.
18. Помехоустойчивое кодирование. Методы помехоустойчивого кодирования.
19. Дискретизация информации. Теорема Котельникова.
20. Квантование по уровню. Дискретизация по времени.
1. Теория информации как наука. Информация, сообщения, сигналы (понятия).
Информация – лат. Information – разъяснение, изложение, осведомленность; –одно из общих понятий
науки, обозначающее некоторые сведения, совокупность каких-либо данных, знаний. В широком смысле
– отражение реального мира;
В узком смысле – любые сведения, являющиеся объектом хранения, передачи, и преобразования
информации.
Теория информации – это наука о получении, преобразовании, накоплении, отображении и передаче
информации.
Структурная теория информации рассматривает структуру построения отдельных информационных
сообщений. Единица количества информации – элементарная структурная единица квант.
Статистическая теория оценивает информацию с точки зрения меры неопределенности. Основное
внимание уделяется распределению вероятностей, либо появлению сигналов, либо изменению
характеристик этих сигналов и построению на его основе некоторых обобщенных характеристик,
позволяющих оценить количество информации.
Семантическая теория занимается изучением именно смысловых характеристик информации:
ценности, содержательности, полезности. Помогает связать количество и ценность информации с такими
обобщенными характеристиками системы, как эффективность, информационная пропускная способность,
информационная помехоустойчивость.
С технической точки зрения, информация – это сведения, являющиеся объектом хранения, передачи и
преобразования.
Информация – это, прежде всего, сведения, которые должны быть использованы.
Под сообщением понимают информацию, выраженную в определенной форме и подлежащую передаче.
Сообщение – это форма представления информации. Примерами сообщений являются: текст
телеграммы, речь оратора, показания измерительного датчика, команды управления и т.д.
Непрерывные по времени сообщения отображаются непрерывной функцией времени. Дискретные по
времени сообщения характеризуются тем, что поступают в определенные моменты времени и
описываются дискретной функцией t.
Непрерывные множеству сообщения характеризуются тем, что функция, их описывающая, может
принимать непрерывное множество значений. Дискретные по множеству сообщения – это сообщения,
которые могут быть описаны с помощью конечного набора чисел или дискретных значений некоторой
функции.
Сообщение для передачи его в соответствующий адрес должно быть предварительно преобразовано в
сигнал. Под сигналом понимается изменяющаяся физическая величина, отображающее сообщение.
Сигнал – материальный переносчик сообщения, т.е. изменяющаяся физическая величина,
обеспечивающая передачу информации по линии связи.
Квантование по уровню состоит в преобразовании непрерывного множества значений сигнала x(ti) в
дискретное множество значений xk, k=0, …., m-1, X л  X min X max  (III вид сигнала).
Операцию, переводящую непрерывный сигнал во II вид называют квантованием по времени или
дискретизацией.
2. Передача информации в информационной системе.
Система состоит из отправителя информации, линии связи и получателя информации. Сообщение
для передачи его в соответствующий адрес должно быть предварительно преобразовано в сигнал. Под
сигналом понимается изменяющаяся физическая величина, отображающее сообщение. Сигнал –
материальный переносчик сообщения, т.е. изменяющаяся физическая величина, обеспечивающая
передачу информации по линии связи. Физическая среда, по которой происходит передача сигналов от
передатчика к приемнику, называется линией связи.
В современной технике нашли применение электрические, электромагнитные, световые, механические,
звуковые, ультразвуковые сигналы. Для передачи сообщений необходимо принять тот переносчик,
который способен эффективно распределяться по используемой в системе линии связи (FE: по
радиолинии эффективно распределяется только электромагнитные колебания высоких частот – от сотен
кГц до дес. тысяч МГц).
Преобразование сообщений в сигналы, удобные для прохождения по линии связи, осуществляется
передатчиком.
В процессе преобразования дискретных сообщений в сигнал происходит кодирование сообщения. В
широком смысле кодированием называется преобразование сообщений в сигнал. В узком смысле
кодирование – это отображение дискретных сообщений сигналами в виде определенных сочетаний
символов. Устройство, осуществляющее кодирование называется кодером.
При передаче сигналы подвергаются воздействию помех. Под помехами подразумеваются любые
мешающие внешние возмущения или воздействия (атмосферные помехи, влияние посторонних
источников сигналов), а также искажения сигналов в самой аппаратуре (аппаратурные помехи),
вызывающие случайное отклонение принятого сообщения (сигнала) от передаваемого.
На приемной стороне осуществляется обратная операция декодирования, т.е. восстановление по
принятому сигналу переданного сообщения.
Решающее устройство, помещенное после приемника, осуществляет обработку принятого сигнала с
целью наиболее полного извлечения из него информации.
Декодирующее устройство, (декодер) преобразует принятый сигнал к виду удобному для восприятия
получателем.
Совокупность средств, предназначенных для передачи сигнала, называется каналом связи. Одна и та
же линия связи может использоваться для передачи сигналов между многими источниками и
приемниками, т.е. линия связи может обслуживать несколько каналов.
При синтезе систем передачи информации приходится решать две основные проблемы, связанные с
передачей сообщений:
- обеспечение помехоустойчивости передачи сообщений
- обеспечение высокой эффективности передачи сообщений
Под помехоустойчивостью понимается способность информации противостоять вредному воздействию
помех. При данных условиях, т.е. при заданной помехе, помехоустойчивость определяет верность
передачи информации. Под верностью понимается мера соответствия принятого сообщения (сигнала)
переданному сообщению (сигналу).
Под эффективностью системы передачи информации понимается способность системы обеспечивать
передачу заданного количества информации наиболее экономичным способом. Эффективность
характеризует способность системы обеспечить передачу данного количества информации с
наименьшими затратами мощности сигнала, времени и полосы частот.
Теория информации устанавливает критерии оценки помехоустойчивости и эффективности
информационных систем, а также указывает общие пути повышения помехоустойчивости и
эффективности.
Повышение помехоустойчивости практически всегда сопровождается ухудшением эффективности и
наоборот.
3. Случайные модели в задачах теории информации. Случайная величина.
Случайной величиной называется такая переменная величина, которая в результате опыта может
принимать то или иное заранее неизвестное значение  , из известного множества значений Х. Различают
два основных типа случайных величин: дискретные и непрерывные.
Дискретная случайная величина может принимать конечное или бесконечное множество значений
{x1}, которые можно пронумеровать i=1,2,,,,n.
Полной статистической характеристикой случайной величины является закон распределения
вероятностей. В случае дискретной величины  под ним понимается соотношение,
устанавливающее зависимость между возможными значениями дискретной случайной величины и
n
их вероятностями P(xi )  pi , при этом  pi  1.
i 1
Закон распределения дискретной случайной величины можно задать в различных формах: табличной,
графической, аналитической. Универсальной характеристикой, одинаково пригодной для дискретных и
для непрерывных одномерных случайных величин, является функция распределения вероятностей
F ( x ) (интегральная функция распределения), определяющая вероятность P того, что случайная
величина X примет значение меньше некоторого числа x :
F ( x )  P ( X  x ).
Функция распределения обладает следующими свойствами:
1. F ( )  lim F ( x )  0.
x 
2. F ( )  lim F ( x )  1.
x 
3. F ( x )  неубывающая функция, т.е. F ( x 2 )  F ( x1 ) при x 2  x1 .
4. P( x1  X  x 2 )  F ( x 2 )  F ( x1 ) .
Функция распределения дискретной случайной величины представляет собой ступенчатую функцию
со скачками в точках x1,x2,....
Во многих ситуациях невозможно определить закон распределения случайной величины, часто в этом нет
необходимости. В таких ситуациях рассматривают отдельные параметры (числовые характеристики)
этого закона. Наиболее важными числовыми характеристиками случайной величины 
множеством значений X  {x1 , x2 ,..., xn } и законом распределения вероятностей P  { p1 , p2 ,..., pn }
являются:
n
m  m[ ]   xi pi - математическое ожидание;
с
i 1
n
m2  m[ 2 ]   xi2 pi - средний квадрат;
i 1
 2  m[(  m ) 2 ]   ( xi  m ) 2 pi - дисперсия.
n
i 1
Возможные значения непрерывных случайных величин не могут быть заранее перечислены и непрерывно
заполняют некоторый промежуток или даже всю ось. Функция распределения непрерывной случайной
величины представляет собой непрерывную функцию.
Часто предполагают, что функции распределения непрерывных случайных величин дифференцируемы во
всей области возможных значений случайных величин. При таком предположении непрерывная
случайная величина X чаще своего описывается плотностью распределения вероятности p ( x ) , которая
иногда называется дифференциальным законом распределения или дифференциальной функцией
распределения. Плотность вероятности определяется как производная функции распределения:
p( x)  dF ( x) / dx.
Плотность вероятности обладает следующими основными свойствами:
1. Плотность вероятности неотрицательна, т.е. p( x )  0.
2. Вероятность попадания непрерывной случайной величины в интервал ( x1 , x 2 ) равна интегралу от
плотности вероятности в этих пределах:
x2
P( x1  X  x2 )   p( x ) dx  F ( x2 )  F ( x1 ).
x1
3. Интеграл в бесконечных пределах от функции p ( x ) равен единице (условие нормировки):

 p( x)dx  1.

Для непрерывной случайной величины формулы для математического ожидания и дисперсии имеют вид:

mx   xp(x )dx ,


 2x   (x  mx ) 2 p(x )dx.

4. Случайные модели в задачах теории информации. Случайное событие.
Событие - всякий факт, который в результате опыта может произойти или не произойти. Вероятность
события - это число, которое является мерой возможности реализации события. Вероятность P(A)
случайного события A заключена в пределах 0  P ( A)  1.
Достоверное событие U такое, что P (U )  1.
Невозможное событие V такое, что P (V )  0.
Суммой или объединением событий называется событие A, которое происходит тогда и только тогда,
когда происходит, по крайней мере, одно из этих событий. Сумма обозначается
n
A  A1  A2 ... An   Ai .
i 1
Произведением или пересечением событий A1 , A2 ,..., An называется такое событие A, которое
происходит тогда и только тогда, когда происходят события вместе. Произведение обозначается
n
A  A1 A2 ... An   Ai .
i 1
События A1 , A2 ,..., An образуют полную группу событий, если в результате опыта появляется хотя бы одно
из них:
n
 A  U.
i
i 1
События A и B называются несовместными, если их совместное появление невозможно: AB  V .
Два события называются противоположными, если они несовместны и образуют полную группу.
Событие, противоположное событию A, обозначается A .
A  A  U , AA  V .
Когда рассматриваемый опыт имеет N равновозможных исходов, которые несовместны и составляют
полную группу, вероятность события А можно рассчитать по формуле:
m
P ( A)  ,
N
где m - число исходов, которые приводят к наступлению события A.
Частотой или статистической вероятностью P*(A) события A в данной серии испытаний называется
отношение числа опытов n, в которых появилось событие, к общему числу N произведенных опытов:
n
P * ( A)  .
N
По теореме Бернулли при большом числе опытов частота сходится по вероятности к вероятности
события.
Расчеты вероятности сложного события A через вероятности более простых событий A1 , A2 ,..., An
базируются на использовании основных теорем теории вероятностей.
Теорема сложения вероятностей. Вероятность суммы двух событий равна сумме вероятностей этих
событий минус вероятность их произведения:
P ( A  B )  P ( A)  P ( B )  P ( AB ).
Теорема умножения вероятностей. Вероятность совместного появления двух событий равна
произведению вероятности одного из них на условную вероятность другого при условии, что первое
имело место:
P ( AB )  P ( A)  P ( A / B )  P ( B )  P ( A / B ),
где P ( B / A) - условная вероятность события B, т.е. вероятность события B, вычисленная в
предположении, что имело место событие A.
Во многих ситуациях событие A может появиться лишь как случайное следствие одного из несовместных
событий B j , j  1, n, образующих полную группу. В этих случаях безусловная вероятность P(A) события A
при известных вероятностях P ( B j ) и P ( A / B j ), j  1, n определяется по формуле полной вероятности:
n
n
i 1
i 1
P ( A)   P ( AB j )   P ( B j )  P ( A / B j ).
При этих же данных можно найти значения вероятностей событий B j , если предположить, что событие A
уже произошло. Задачи такого типа решаются с помощью формулы Байеса:
n
P( B j / A)  P( B j )  P( A / B j ) / P( A), P ( A)   P ( B j )  P ( A / B j ).
i 1
5. Измерение информации (меры информации)
Мера
информации
Синтаксическая:
шенноновский
подход
компьютерный
подход
Единицы измерения
Примеры
Степень
уменьшения
неопределенности
Единицы
представления
информации
Вероятность события
Бит,байт,Кбайт и т.д.
Семантическая
Тезаурус
Экономически
показатель
Пакет прикладных
программ,ПК,компьютерные
сети
Рентабельность,
производительность и т.д.
Прагматическая
Ценность
использования
Емкость памяти,
производительность ПК,
скорость передачи данных и
т.д. Денежное выражение
Единицы измерения
информации и примеры
Синтаксическая мера
информации
Алгоритмическая Минимальное число Машина Тьюринга
Объем данных Vд. в
внутренних
сообщение измеряется
состояний машины
количеством символов
(разрядов) в этом сообщение. В различных системах счисления один разряд имеет различный вес и
соответственно меняется единица измерения данных:
в двоичной системе счисления единица измерения - бит (bit-binary digit-двоичный разряд);
в десятичной системе счисления единица измерения – дит (десятичный разряд).
Количество информации I на синтаксическом уровне невозможно определить без рассмотрения понятия
неопределенности состояния системы (энтропии системы). Получение информации о какой–либо системе
всегда связано с изменением степени неосведомленности получателя о состоянии этой системы. (теория
Шеннона).
Семантическая мера информации.
Тезаурус- это совокупность сведений, которыми располагает пользователь или система.
В зависимости от соотношений между смысловым содержанием информации S и тезаурусом
пользователя Sp. изменяется количество семантической информации Ic, воспринимаемой пользователем и
включаемой им в дальнейшем в свой тезаурус.
при
Sp≈0 пользователь не воспринимает, не понимает поступающую
информацию; при Sp→ ∞ пользователь все знает, и информация ему не нужна.
Максимальное количество информации Ic потребитель приобретает при согласовании ее смыслового
содержания S со своим тезаурусом Sp ( Sp = Sp opt) ,когда поступающая информация понятна пользователю
и несет ему ранее не известные (отсутствующие в его тезаурусе) сведения.
Относительной мерой количества семантической информации может служить коэффициент
содержательности C, который определяется как отношение количества семантической информации к ее
объему:С= Ic / Vд.
Прагматическая мера информации.Эта мера определяет полезность информации (ценность) для
достижения пользователем поставленной цели. Эта мера также величина относительная, обусловленная
особенностями использования этой информации в той или иной системе. Ценность информации
целесообразно измерять в тех же единицах (или близких к ним), в которых измеряется целевая функция.
Алгоритмическая мера информации.Каждый согласится , что слово 0101….01 сложнее слова 00….0, а
слово, где 0 и 1 выбираются из эксперимента – бросания монеты (где 0-герб,1 –решка),сложнее обоих
предыдущих .
Любому сообщению можно приписать количественную характеристику, отражающую сложность (размер)
программы, которая позволяет ее произвести.
Так как имеется много разных вычислительных машин и разных языков программирования (разных
способов задания алгоритма), то для определенности задаются некоторой конкретной вычислительной
машиной, например машиной Тьюринга.
Сложность слова (сообщения) определяется как минимальное число внутренних состояний машины
Тьюринга, требующиеся для его воспроизведения.
Структурные меры информации: структурная, геометрическая и др. меры информации.
Геометрическая (метрическая):
Единица измерения – метрон (мера точности измеряемого параметра);
Метронная мощность (плотность)физической системы – количество метронов в расчете на
единичный объем координатного пространства;
Применяется и для оценки максимально возможного количества информации в заданных структурных
габаритах - информационной емкости устройств.
Комбинаторная (структурная) возможное количество комбинаций информационных элементов
Перестановки – группы элементов, содержащие все имеющиеся в наличии элементы
Определение количества информации в комбинаторной мере - определение количества возможных или
существующих комбинаций, т.е. оценка структурного разнообразия информационного устройства.
Аддитивная мера – мера Хартли – логарифм числа возможных размещений из h элементов по l
I  log Vhl  l * log h
Позволяет производить суммирование количеств информации отдельных элементов информационного
комплекса. Всегда положительна.
Логарифм с основанием 2 - единица количества информации говорит о том, что произошло одно из двух
равновероятных событий (двоичная единица информации или бит).
Логарифм с основанием 10 - количество информации в дитах, натуральный логарифм с основанием
е=2,71828 – в нитах.
P  h!Количество
h повторений.
P
перестановок
из
h
элементов
   Количество
...
 !  ! !
без
перестановок из h элементов с
повторениями при условии, что один из элементов
повторяется α раз, другой β , последний γ раз.
Сочетания
группы
- по l элементов, образуемые из h разных
элементов, различающиеся между собой самими
элементами.
h!
Cn  Количество сочетаний из h элемен- тов по l (без
l!(повторений).
h  l )!
(h Количество
l  1)!
l!(h  l )!
сочетаний из h разных элементов по l
элементов с повторениями, в которые элементы могут
входить многократно (до группы по l элементов,
образуемые из h разных элементов, различающиеся
между собой либо самими элементами, либо порядком
их следования.
h
Количество размещений из h разных элементов по l
Vhl 
(h  lэлементов
)!
без повторений.
Cnl ( повт) 
размещений из h разных элементов по l
 hl ( повт) Количество
hl
элементов с повторениями.
6. Информационная мера Шеннона. Энтропия. Условная энтропия.
Когда мы решаем задачи кодирования и поиска информации мы, главным образом, имеем дело с
сообщениями. При этом мы имеем дело не с какими-то автономными сообщениями, а с сообщениями,
входящими в некоторое множество. Одним из критериев, определяющих сложность алгоритмов для
решения этих задач, является неопределенность сообщений. Действительно, чем больше элементов во
множестве сообщений, тем больше неопределенность того, какой из них выбран в качестве аргумента
поиска, тем больше сравнений требуется произвести для нахождения элемента. Чем больше
неопределенность сообщения, тем длиннее требуется последовательность знаков, чтобы указать на
выбранное сообщение, т. е. закодировать сообщение. Следовательно, неопределенность сообщений
можно количественно измерить упомянутой предельной сложностью алгоритмов поиска и
кодирования.
Кроме того, любое сообщение несет некоторую информацию. И здесь важнейшим моментом является
понятие количество информации. До получения конкретного сообщения оно характеризуется для
получателя некоторой неопределенностью. После получения сообщения неопределенность исчезает, а мы
обогащаемся некоторыми сведениями. Это можно трактовать как переход неопределенности в
информацию. Следовательно, количество информации можно задать как уменьшение
неопределенности.
Вообще различают типичную и нетипичную последовательность сообщений.
Пусть имеется последовательность из n сообщений s1, s2, .., sn, каждое из которых принадлежит
множеству из N возможных значений {х1,.., хN}. Сообщения независимы и принимают возможные
значения с определенными вероятностями р1,…pN. Рассмотрим свойства таких последовательностей при
п ->∞.
Вообще говоря, последовательность может принимать Nn возможных значений. Однако при больших n
вступают в действие вероятностные законы, в частности, закон больших чисел, и количество
действительно выпадающих значений сокращается. По закону больших чисел при больших n в последовательности должно быть приблизительно np1 значений х1, приблизительно nр2 значений х2, …,
приблизительно npN значений xN, причем точность такой оценки увеличивается с ростом n.
Конкретная последовательность называется типичной, если в ней выполняются вышеприведенные
соотношения, и нетипичной в противном случае.
Вероятность того, что значение x1 встретится n1 раз, значение x2 – n2 раз,… равна
q=p1n1p2n2…pNnN
Поэтому вероятность типичной последовательности для больших n близка к величине
q=p1np1p2np2…pNnpN
Это выражение одинаково для всех типичных последовательностей, следовательно, все типичные
последовательности становятся равновероятными.
При стремлении п к бесконечности суммарная вероятность нетипичных последовательностей
стремится к нулю, а типичные последовательности становятся относительно равновероятными.
(теорема асимптотической равновероятности типичных последовательностей)
Из этой теоремы следует, что с увеличением n из общего числа nN возможных последовательностей
остается
N  1 / q   ( pi npi ) 1
(1)
(типичных) последовательностей.
CN=log2N – 1 + ε (2) – формула для среднего числа сравнений при чистом дихотомическом поиске, где ε =
ограниченная положительная величина.
Объединим (1) и (2) и получим:
N
N
i 1
i 1
npi 1
C N  log ( ( pi ) )  1    n  p log (1 / p )  1   (3)
2
i
2
i
А для одного сообщения
N
C N / n   p log (1 / p )  1 / N   / N (4)
i 1
i
2
i
При n->∞ эта величина стремится к пределу:
N
N  n  p log (1 / p ) (5)
i
i 1
2
i
(5) – формула Шеннона для энтропии сообщений.
Это энтропия, которая по Шеннону является мерой информации.
Энтропия Н — это количественная мера неопределенности сообщений. В соответствии с
приведенными рассуждениями энтропия имеет ясный физический смысл. Она выражает предельно
достижимое среднее число сравнений, необходимых при чистом дихотомическом поиске в
условиях отсутствия помех, или предельно достижимое среднее число двоичных знаков,
необходимых при двоичном кодировании сообщений.
В качестве единицы измерения энтропии (и количества информации), таким образом, выступает
энтропия множества двух равновероятных сообщений. Эта единица измерения называется битом.
К сожалению, такое же название в вычислительной технике имеет совершенно иной объект — двоичный
символ (двоичный разряд). Поэтому следует отличать бит как единицу количества информации от бита
как двоичного символа.
Условная энтропия
Пусть  и  случайные величины с множествами возможных значений:
X= x1 , x2 ,... xN , Y  y1 , y2 ,... yM 
Количество информации H ( ) при наблюдении случайной величины   X  x1 , x2 ,..., xn  с
распределением вероятностей P  p1 , p2 ,..., pn  задается формулой Шеннона:
N
H ( )   pi log l / pi
i l
Условной
энтропией
величины
N
M

H ( )  H ( /  )  H (Y / X )    p(xi y j ) log 2
i 1 j 1
при
наблюдении

величины
называется
1
.
p( y j / x i )
Справедливы соотношения:
N
M
H ( ,  )  H ( )  H ( ), H ( ,  )    p(xi y j ) log 2
i 1 j 1
1
.
p( y j x i )
7. Свойства энтропии дискретного и непрерывного источников информации
Свойства энтропии дискретного источника информации.
Дискретные системы связи - системы, в которых как реализации сообщения, так и реализации сигнала
представляют собой последовательности символов алфавита, содержащего конечное число элементарных
символов.
Пусть 
и 
- случайные величины с множествами возможных значений
X  x1 , x 2 ,..., x n ,
Y  y1 , y 2 ,..., y m .
Количество информации
H( ) при наблюдении случайной величины   X  {x1 , x 2 ,..., x n } с
n
распределением вероятностей P  {p1 , p2 ,..., pn } задается формулой Шеннона: H ( )   pi log 1 / pi .
i 1
Единицей измерения количества информации является бит, который представляет собой количество
информации, получаемое при наблюдении случайной величины, имеющей два равновероятных значения.
Рассмотрим свойства энтропии, вытекающие из формулы Шеннона.
1) Энтропия — неотрицательное вещественное число.
Это свойство — прямое следствие того, что 0 <= pi <= 1, i=1,..., N и свойств функции у = log2 х.
2) Энтропия равна нулю тогда и только тогда, когда ε — детерминированная величина, т. е. когда для
некоторого j = 1 вероятность pj=1. Пусть ε — детерминированная величина,
тогда H ( )  p log (1 / p )   p log (1 / p )
j
2
j
i j
j
2
j
(неопределенности раскрываются по правилу Лопиталя). Пусть теперь Н{£) = 0. Так как слагаемые в
формуле энтропии неотрицательны, то для этого должны выполняться следующие условия:
p log (1 / p )  0, i  1,2,... N Эти условия выполняются только тогда, когда р i = 0 или
i
2
i
Pi == 1. С учетом условия нормировки ∑iPi = 1 возможно только, если для некоторого к, 1 <= к <= N
выполняется условие Pk = 1, Pi≠jt =0, т.е. если ε — детерминированная величина.
Таким образом, только детерминированная система имеет нулевую энтропию.
3) Энтропия максимальна при равновероятных значениях ε, т. е. когда p1 =р2 =… рN = 1/N.- Это
свойство легко доказать, найдя максимум многомерной функции H(ε), например, методом
множителей Лагранжа.
1
При равновероятных значениях ε получаем H ( )   log N  log N , т. е. максимум равен
2
2
i j N
H=log2N. (**)
Это выражение называется формулой Хартли.
Таким образом, неопределенность системы максимальна, когда все ее состояния равновероятны. Это
и понятно: если какое-то из состояний более вероятно, то это уже есть какая-то степень
определенности. Становится также понятно стремление при кодировании и поиске разбивать
исходные множества на подмножества с примерно равными суммарными вероятностями. При этом
получается максимальная энтропия возможных исходов сравнения и, следовательно, сравнение дает
максимальное количество информации.’
4) Энтропия аддитивна
Можно привести следующие доказательства аддитивности энтропии. Сначала приведем доказательство
аддитивности меры Хартли (формула **).
Рассмотрим два источника информации:
A  a, , a2 ,..., aN 
B  b1 , b2 ,..., bM 
При одновременном наблюдении
I  I A  IB
Мера Хартли:
I c  log 2 lc  log 2 NM  log 2 N  log 2 M c
Доказательство аддитивности информационной меры Шеннона.
Пусть А и В независимы, тогда p(ai b j )  pi q j
PA  p1 , p2 ,..., pN 
PB  q1 , q2 ,..., qM 
n
M
H (C )   p (aib j ) log 2
i 1 j 1
N
  (log 2
i 1
N
M
N
M
1
1
1
   p (aib j ) log 2
   p (aib j ) log 2

p (aib j ) i 1 j 1
p (ai ) i 1 j 1
p (b j )
M
M
N
1
1
) p (aib j )   (log 2
) p (aib j )
p (ai ) j 1
p (b j ) i 1
j 1
M
N
 p(a b )  p ,  p(a b )  q
j 1
i
j
i
i
i 1
j
j
поэтому
N
H (C )   pi log 2
i 1
1 M
1
  q j log 2
pi j 1
qj
Энтропия непрерывных сообщений
Непрерывные системы передачи информации - системы, в которых как реализации сообщения, так и
реализации сигнала на конечном временном интервале (0, T ) представляют собой некоторые
непрерывные функции времени.
Пусть x (t ) - реализации непрерывного сообщения на входе какого-либо блока схемы связи, y (t ) реализация выходного сообщения (сигнала), p ( x ) - плотность вероятности ансамбля входных сообщений,
p( y ) - плотность вероятности ансамбля выходных сообщений
Формулы для энтропии H непрерывных сообщений получаются путем обобщения формул для энтропии
дискретных сообщений. Если x - интервал квантования (точность измерения), то при достаточно малом
x энтропия непрерывных сообщений






H1 ( X )    p1 ( x ) log p1 ( x )dx  log x  p1 ( x )dx  H ( X )  log x    p1 ( x ) log p1 ( x )x dx ,




где H ( X )    p1 ( x ) log p1 ( x )dx . По аналогии H (Y )    p1 ( y ) log p1 ( y )dy .
8. Избыточность информации. Взаимная информация.
Избыточность информации Сообщения, энтропия которых максимальна, являются оптимальными с
точки зрения символьного количества представляемой информации.
Мерой количественной оценки того, насколько данное реальное сообщение по своей энтропии отличается
от соответствующего ему оптимального сообщения, является коэффициент сжатия.
Н ( )

;
max H ( )
где Н(ξ) – энтропия реального сообщения, max H(ξ) – энтропия соответствующего ему оптимального
сообщения.
Если оптимальное и неоптимальное сообщение характеризуются одинаково общей энтропией, то
n*H(ξ) = n’*max H(ξ), где n – число элементов неоптимального сообщения, n’ – число элементов
оптимального сообщения. Так как средняя на элемент оптимальная энтропия максимальна, то число
элементов неоптимального сообщения больше числа элементов соответственного ему оптимального
сообщения.
Н ( )
n'

 ;
max H ( ) n
таким образом реальные сообщения при одинаковой информативности обладают определенной
избыточностью в элементах по сравнению с оптимальными сообщениями.
Мерой количественной оценки избыточности является коэффициент избыточности.
H ( )
H ( )
n  n' max H ( )  H ( )
 1

1
1
;
n
max H ( )
max H ( )
log 2 N
смысл: это относительный избыток символов при передачи информации данным источником, которая
потребуется по сравнению со случаем использования безызбыточного алфавита. Безызбыточный
алфавит (ρ=0) характеризуется равными вероятностями появления символов. Избыточность приводит к
повышению времени передачи сообщений, излишней загрузке канала связи. Однако, некоторая
избыточность бывает полезной для обеспечения требуемой надежности систем, появления
помехоустойчивости передачи сообщений.
Взаимной информацией величин  и  называется I ( ,  )  H ( )  H ( ).
Справедливы следующие соотношения:
N
M
I ( ,  )    p(xi y j ) log 2
i 1 j 1
p(x i y j )
p(x i ) p( y j )
, I ( ,  )  I ( ,  )  H ( )  H ( ), I ( ,  )  H ( )  H ()  H ( ,  ),
H ( , )  H ( )  H ()  I ( , ),
0  I ( , )  H ( ), 0  I ( , )  H ().
Если  и  независимы, то I ( ,  ) =0.
При расчетах условной энтропии и взаимной информации удобно пользоваться следующими
соотношениями теории вероятностей:
1) теорема умножения вероятностей p(xi y j )  p(xi ) p( y j / xi )  p( y j ) p(xi / y j ) ;
M
N
j 1
i 1
2) формула полной вероятности p(xi )   p(xi , y j ); p( y j )   p(x i , y j );
3) формула Байеса p(x i / y j ) 
p(x i ) p( y j / x i )
p( y j )
p (x i ) p ( y j / x i )
 N
.
 p(x i ) p( y j / x i )
i 1
Свойства взаимной информации. Анализируя соотношение для взаимной информации можно
установить следующие ее свойства (предлагаем провести доказательство самостоятельно):
1) I ( , )  I ( ,  ) , т.е. наблюдая 7], мы получим о £ такое
же количество информации, какое получим о г), наблюдая £;
2) 0  I ( , ) , причем равенство имеет место тогда и только тогда, когда £ и rj статистически
независимы;
3) I ( , )  H ( ) , причем равенство имеет место тогда и только тогда, когда £ и п взаимно однозначны.
9. Обобщенные характеристики сигналов и каналов
Сигнал может быть охарактеризован различными параметрами. Таких параметров, вообще говоря, очень
много, но для задач, которые приходится решать на практике, существенно лишь небольшое их число.
Например, при выборе прибора для контроля технологического процесса может потребоваться знание
дисперсии сигнала; если сигнал используется для управления, существенным является его мощность и так
далее. Рассматривают три основных параметра сигнала, существенных для передачи информации по
каналу. Первый важный параметр - это время передачи сигнала Tс. Второй характеристикой,
которую приходится учитывать, является мощность Pс сигнала, передаваемого по каналу с
определенным уровнем помех Pz . Чем больше значение Pс по сравнению с Pz, тем меньше вероятность
ошибочного приема. Таким образом, представляет интерес отношение Pс /Pz. Удобно пользоваться
логарифмом этого отношения, называемым превышением сигнала над помехой:
Pc
Lc log a( )
Pz
Третьим важным параметром является спектр частот Fc . Эти три параметра позволяют
представить любой сигнал в трехмерном пространстве с координатами L, T, F в виде параллелепипеда
с объемом Tc Fc Lc . Это произведение носит название объема сигнала и обозначается через Vc
VcTcFcLc
Информационный канал можно характеризовать также тремя соответствующими параметрами:
временем использования канала Тк , шириной полосы частот, пропускаемых каналом Fk, и
динамическим диапазоном канала Dk характеризующим его способность передавать различные
уровни сигнала.
Величина Vk  Tk Fk Dk называется емкостью канала.
Неискаженная передача сигналов возможна только при условии, что сигнал по своему объему
«вмещается» в емкость канала.
Следовательно, общее условие согласования сигнала с каналом передачи информации определяется
соотношением Vc  Vk
Однако соотношение выражает необходимое, но недостаточное условие согласования сигнала с каналом.
Достаточным условием является согласование по всем параметрам:
Tc  Tk
Fc  Fk
Dc  D k
Для информационного канала пользуются понятиями: скорость ввода информации, скорость
передачи информации и пропускная способность канала.
Под скоростью ввода информации (потоком информации) V(A) понимают среднее количество
информации, вводимое от источника сообщений в информационный канал в единицу времени. Эта
характеристика источника сообщений и определяется только статистическими свойствами сообщений.
Скорость передачи информации V(X,Y) – среднее количество информации, передаваемое по каналу в
единицу времени. Она зависит от статистических свойств передаваемого сигнала и от свойств канала.
Пропускная способность С – наибольшая теоретически достижимая для данного канала скорость
передачи информации. Это характеристика канала и не зависит от статистики сигнала.
С целью наиболее эффективного использования информационного канала необходимо принимать меры к
тому, чтобы скорость передачи информации была как можно ближе к пропускной способности канала.
Вместе с тем скорость ввода информации не должна превышать пропускную способность канала,
иначе не вся информация будет передана по каналу.
Это основное условие динамического согласования источника сообщений и информационного канала.
Одним из основных вопросов в теории передачи информации является определение зависимости скорости
передачи информации и пропускной способности от параметров канала и характеристик сигналов и
помех. Эти вопросы были впервые глубоко исследованы К. Шенноном.
10. Характеристика канала связи без помех. Теорема Шеннона для канала без помех.
Дискретный канал передачи информации – совокупность средств, предназначенных для передачи
дискретных сигналов.
В канале без помех каждому определенному входному сигналу будет соответствовать один и тот же
сигнал на выходе канала, то есть входные и выходные сигналы связаны однозначной функциональной
зависимостью.
Выходной алфавит символов источника сообщений:
A  ai , A  a1 , a2 ,...., an 
Количество информации, приходящееся в среднем на один символ источника:
n
H ( A)   pi log 2 1 / pi , где pi – вероятность появления символа ai на выходе источника.
i 1
Алфавит символов канала связи:
B  b1 , b2 ,...., bm 
Среднее количество информации, выдаваемое источником в единицу времени – информационная
производительность:
dI ( A) / dt   A H ( A), где  A - среднее число символов, выдаваемое источником в единицу времени.
Скорость передачи информации по каналу:
dl ( B) / dt   B H ( B), где B -среднее число символов, передаваемое по каналу в единицу времени.
Пропускная способность канала:
C k  max dI ( B) / dt , где p  множество всех возможных распределений
 p
вероятностей символов
алфавита B канала.
Пропускная способность канала (с учетом свойств энтропии):
Ck   B log 2 m
n, m, A , B - технические характеристики канала связи.
Теорема Шеннона для канала без помех
Рассмотрим две фундаментальные теоремы идеального кодирования, носящие имя Шеннона. Первая из
них рассматривает случай отсутствия помех в канале, вторая учитывает наличие помех,
приводящих к ошибкам.
Рассмотрим проблему согласования источника сообщений и канала при передаче последовательности
сообщений. Пусть источник сообщений выдает сообщения с некоторой скоростью u (сообщений/ед.
времени), называемой технической производительностью источника. Пусть по каналу можно передавать
без искажений сообщения со скоростью, не превышающей некоторую величину (сообщений/ед.
k
времени), называемую технической пропускной способностью канала. Очевидно, что если выполняется
условие u < , то канал успевает передать все сообщения, поступающие на его вход от источника, и
k
передача будет вестись без искажений. Что произойдет, если u > ? Можно ли в этом случае обеспечить
k
передачу без искажений? Если исходить только из технических характеристик, то, очевидно, нельзя. А
если учесть информационные характеристики? Ведь нам известно, что если последовательность обладает
информационной избыточностью, то её можно сжать, применив методы экономного кодирования.
Рассмотрим подробнее такую возможность.
Пусть Vu - (информационная) производительность источника, т.е. количество информации,
производимое источником в единицу времени; Ck – (информационная) пропускная способность канала,
т.е. максимальное количество информации, которое способен передать канал без искажений за единицу
времени. Первая теорема Шеннона утверждает, что безошибочная передача сообщений определяется
соотношением Vu и Ck.
Первая теорема Шеннона: если пропускная способность канала без помех превышает
производительность источника сообщений, т.е. удовлетворяется условие
Ck >Vu,
то существует способ кодирования и декодирования сообщений источника, обеспечивающий сколь
угодно высокую надежность передачи сообщений. В противном случае, т.е. если
Ck <Vu
Такого способа нет.
Таким образом, идеальное кодирование по Шеннону по существу представляет собой экономное
кодирование последовательности сообщений при безграничном укрупнении сообщений. Такой способ
кодирования характеризуется задержкой сообщений
  2T ,
поскольку кодирование очередной типичной последовательности может начаться только после получения
последовательности источника длительностью T, а декодирование – только когда принята
последовательность из канала той же длительности T. Поскольку требуется T   , то идеальное
кодирование требует бесконечной задержки передачи информации. В этом причина технической
нереализуемости идеального кодирования по Шеннону. Тем не менее, значение этого результата,
устанавливающего предельные соотношения информационных характеристик источника и канала для
безошибочной передачи сообщений, весьма велико. Исторически именно теорема Шеннона
инициировала и определила развитие практических методов экономного кодирования.
11. Характеристика канала связи с помехами. Теорема Шеннона для канала с помехами.
Выходной алфавит символов источника сообщений:
A  ai , A  a1 , a2 ,...., an 
Количество информации, приходящееся в среднем на один символ источника:
n
H ( A)   pi log 2 1 / pi , где pi – вероятность появления символа ai на выходе источника.
i 1
Среднее количество информации, выдаваемое источником в единицу времени – информационная
производительность:
dI ( A) / dt   A H ( A), где  A - среднее число символов, выдаваемое источником в единицу времени.
Алфавиты символов канала связи:
Bвх  X  x1 , x2 ,..., xm , Bвых  Y  y1 , y2 ,..., yl 
Матрица переходных вероятностей:
l
p( yi / xk ) , где k  1...m, i  1...l ;  p( yi / xk )  1
i 1
Среднее количество информации на один входной и на один выходной символ канала:
m
l
i 1
j 1
H ( X )   p ( xi ) log 2 1 / p ( xi ); H (Y )   p ( y j ) log 2 1 / p ( y j )
Информация, которую несет выход канала о входе:
I (Y , X )  H ( X )  H y ( X )  H (Y )  H x (Y )
где H y ( X ) - ненадежность канала, H x (Y ) - энтропия шума.
Скорость передачи информации по каналу:
dl ( B) / dt  B I ( X , Y ), где B -среднее число символов, передаваемое по каналу в единицу времени.
Пропускная способность канала:
C k  maxdI ( B) / dt, где p  множество всех возможных распределений вероятностей входного
 p
алфавита символов канала
C k   B maxI ( x, y )
n, m, l , A , B - hpy характеристики канала.
Методы повышения помехоустойчивости
В основах всех способов повышения помехоустойчивости информационных систем лежит использование
определенных различий между полезным сигналом и помехой. Поэтому для борьбы с помехами
необходимы априорные сведения о свойствах помехи и сигнала.
В настоящее время известно большое число способов повышения помехоустойчивости систем. Эти
способы удобно разбить на две группы.
I группа – основана на выборе метода передачи сообщений.
II группа – связана с построением помехоустойчивых приемников.
Простым и применяемым способом повышения помехоустойчивости является увеличение отношения
сигнал/помеха за счет увеличения мощности передатчика. Но этот метод может оказаться экономически
не выгодным, так как связан с существенным ростом сложности и стоимости оборудования. Кроме того,
увеличение мощности передачи сопровождается усилением мешающего действия данного канала на
другие.
Важным способом повышения помехоустойчивости передачи непрерывных сигналов
является
рациональный выбор вида модуляции сигналов. Применяя виды модуляции, обеспечивающие
значительное расширение полосы частот сигнала, можно добиться существенного повышения
помехоустойчивости передачи.
Радикальным способом повышения помехоустойчивости передачи дискретных сигналов является
использование специальных помехоустойчивых кодов. При этом имеется два пути повышения
помехоустойчивости кодов:
1.
Выбор таких способов передачи, которые обеспечивают меньшую вероятность искажения кода;
2.
Увеличение корректирующих свойств кодовых комбинаций. Этот путь связан с использованием
кодов, позволяющих обнаруживать и устранять искажения в кодовых комбинациях. Такой способ
кодирования связан с введением в код дополнительных, избыточных символов, что сопровождается
увеличением времени передачи или частоты передачи символов кода.
Повышение помехоустойчивости передачи может быть также достигнуто путем повторной передачи
одного и того же сообщения. На приемной стороне сравниваются полученные сообщения и в качестве
истинных принимаются те, которые имеют наибольшее число совпадений. Чтобы исключить
неопределенность при обработке принятой информации и обеспечить отбор по критерию большинства,
сообщение должно повторяться не менее трёх раз. Этот способ повышения помехоустойчивости связан с
увеличением времени передачи.
Системы с повторением передачи дискретной информации делятся на системы с групповым
суммированием, у которых сравнение производится по кодовым комбинациям, и на системы с
посимвольным суммированием, у которых сравнение осуществляется по символам кодовых комбинаций.
Посимвольная проверка является более эффективной, чем групповая.
Разновидность систем, у которых повышение помехоустойчивости достигается за счет увеличения
времени передачи, являются системы с обратной связью. При наличии искажений в передаваемых
сообщениях информация, поступающая по обратному каналу, обеспечивает повторение передачи.
Наличие обратного канала приводит к усложнению системы. Однако в отличие от систем с повторением
передачи в системах с обратной связью повторение передачи будет иметь место лишь в случае
обнаружения искажений в передаваемом сигнале, т.е. избыточность в целом оказывается меньшей.
Помехоустойчивый прием состоит в использовании избыточности, а также априорных сведений о
сигналах и помехах для решения оптимальным способом задачи приема: обнаружения сигнала, различия
сигналов или восстановления сообщений. В настоящее время для синтеза оптимальных приемников
широко используется аппарат теории статистических решений.
Ошибки приемника уменьшаются с увеличением отношения сигнал/помеха на входе приемника. В связи с
этим часто производят предварительную обработку принятого сигнала с целью увеличения отношений
полезной составляющей к помехе. К таким методам предварительной обработки сигналов относится
метод ШОУ (сочетание широкополосного усилителя, ограничителя и узкополосного усилителя), селекция
сигналов по длительности, метод компенсации помехи, метод фильтрации, корреляционный метод, метод
накопления и др.
Современные технические средства обмена данными и каналообразующая аппаратура
Передатчик – устройство, являющееся источником данных.
Приемник – устройство, принимающее данные.
Приемником могут быть компьютер, терминал или какое-либо цифровое устройство.
Сообщение – цифровые данные определенного формата, предназначенные для передачи.
Это может быть файл базы данных, таблица, ответ на запрос, текст или изображение.
Средства передачи – физическая передающая среда и специальная аппаратура, обеспечивающая
передачу сообщений
Для передачи сообщений в вычислительных сетях используются различные типы каналов связи.
Наиболее распространены выделенные телефонные каналы и специальные каналы для передачи
цифровой информации. Применяются также радиоканалы и каналы спутниковой связи.
Особняком в этом отношении стоят ЛВС, где в качестве передающей среды используются витая пара
проводов, коаксиальный кабель и оптоволоконный кабель.
Чтобы обеспечить передачу информации из ЭВМ в коммуникационную среду, необходимо согласовать
сигналы внутреннего интерфейса ЭВМ с параметрами сигналов, передаваемых по каналам связи. При
этом должно быть выполнено как физическое согласование (форма, амплитуда и длительность сигнала),
так и кодовое.
Технические устройства, выполняющие функции сопряжения ЭВМ с каналами связи, называются
адаптерами или сетевыми адаптерами. Один адаптер обеспечивать сопряжение с ЭВМ одного канала
связи. Кроме одноканальных адаптеров используются и многоканальные устройства – мультиплексоры
передачи данных или просто мультиплексоры.
Мультиплексор передачи данных – устройство сопряжения ЭВМ с несколькими каналами связи.
Мультиплексоры передачи данных использовались в системах телеобработки данных – первом шаге на
пути к созданию вычислительных сетей. В дальнейшем при появлении сетей со сложной конфигурацией и
с большим количеством абонентских систем для реализации функций сопряжения стали применяться
специальные связные процессоры.
Как уже говорилось ранее, для передачи цифровой информации по каналу связи необходимо поток битов
преобразовать в аналоговые каналы, и при приеме информации из канала связи в ЭВМ выполнить
обратное действие – преобразовать аналоговые сигналы в поток битов, которые может обрабатывать
ЭВМ. Такие преобразования выполняет специальное устройство – модем.
Модем – устройство, выполняющее модуляцию и демодуляцию информационных сигналов при передаче
их из ЭВМ в канал связи и при приеме в ЭВМ из канала связи.
Наиболее дорогим компонентом вычислительной сети является канал связи. Поэтому при построении
ряда вычислительных сетей стараются сэкономить на каналах связи, коммутируя несколько внутренних
каналов связи на один внешний. Для выполнения функций коммутации используются специальные
устройств – концентраторы.
Концентратор – устройство, коммутирующее несколько каналов связи на один путем частотного
разделения.
В ЛВС, где физическая передающая среда представляет собой кабель ограниченной длины, для
увеличения протяженности сети используются специальные устройства – повторители.
Повторитель – устройство, обеспечивающее сохранение формы и амплитуды сигнала при передаче его
на большее, чем предусмотрено данным типом физической передающей среды, расстояние.
Существуют локальные и дистанционные повторители. Локальные повторители позволяют соединять
фрагменты сетей, расположенные на расстоянии до 50 м., а дистанционные – до 2000 м.
Теорема Шеннона для канала с помехами
При отсутствии помех ошибки при передаче могут возникать только за счет неоднозначного кодирования
сообщений. Рассмотрим теперь ситуацию, когда в канале действуют помехи, вызывающие искажения
передаваемых символов. Возникающие при этом ошибки носят случайный характер, они действуют при
любой скорости передачи сообщений через канал, в том числе, когда Vu<Vk.
Возникает вопрос, возможен ли такой способ кодирования, при котором сообщения передаются через
канал без ошибок с некоторой ненулевой скоростью Vk.  0 (действие ошибок полностью устраняется при
кодировании)? В первой главе рассматривались методы помехоустойчивости кодирования, основанные на
введении избыточности. Однако для полного устранения ошибок их применение потребовало бы
введения бесконечной избыточности, что привело бы к снижению скорости передачи сообщений до нуля.
Тем не менее, вторая теорема Шеннона утверждает, что такой способ возможен. Тогда возникает
следующий вопрос: чем определяется максимальная скорость передачи сообщений по каналу с помехами?
Оказывается, что, как и для канала без помех, она определяется соотношением информационных
характеристик источника и канала.
Вторая теорема Шеннона: для канала с помехами существует такой способ кодирования, при котором
обеспечивается безошибочная передача всех сообщений источника, если только пропускная способность
канала превышает производительность источника, т.е. Ck>Vu.
Теорема Шеннона для канала с помехами не указывает конкретного способа кодирования,
обеспечивающего достоверную передачу информации со скоростью сколь угодно близкой к пропускной
способности канала, а лишь указывает на принципиальное существование такого способа. Кроме того, как
и в первой теореме, кодирование будет сопровождаться задержкой сообщений не менее 2Т, где T   .
Поэтому идеальное кодирование технически нереализуемо. Однако из формулы для вероятности ошибки
вытекает крайне важный практический вывод: достоверность передачи сообщений тем выше, чем
больше длительность кодируемой последовательности и чем менее эффективно используется
пропускная способность канала, т.е. чем больше запас Ck-Vu.
Теорема Шеннона для канала с помехами оказала огромное влияние на становление правильных взглядов
на возможности передачи сообщений и на разработку технически реализуемых методов
помехоустойчивого кодирования. Шеннон показал, что для безошибочной передачи сообщений вовсе не
обязательно вводить бесконечную избыточность и уменьшать скорость передачи информации до нуля.
Достаточно ввести в сообщения источника такую избыточность, которая равна потерям количества
информации в канале из-за действия помех.
12. Значение результатов Шеннона.
Значение результатов Шеннона для задач передачи, хранения и поиска информации.
Теорема Шеннона и передача информации.
Основное значение результатов Шеннона в этой области состоит в том, что они дают универсальный
критерий, позволяющий сравнивать технически различные устройства и системы с точки зрения
их возможностей по передаче информации. Технически источники сообщений и каналы связи могут
быть существенно разными устройствами по используемым сигналам, способам кодирования сообщений,
форматам данных, скоростным характеристикам. В этих условиях информационная мера Шеннона и
теоремы идеального кодирования позволяют оценить, в какой степени технически различные системы
соответствуют друг другу для решения задачи передачи сообщений. Для этого требуется, исходя из
технических показателей источника и канала, оценить их информационные показатели: информационную
производительность и информационную пропускную способность. Соотношение информационных
показателей и является той идеальной мерой, по которой можно судить о степени соответствия реальных
систем.
Особая заслуга Шеннона состоит в том, что он первым осознал действительную картину влияния
случайных помех на процесс передачи сообщений. Принципиальное действие помех выражается в той
степени, в какой они влияют на информационные показатели системы. Поэтому каналы с одинаковой
пропускной способностью эквивалентны по возможности безошибочной передачи сообщений независимо
от того, действуют ли в них помехи или нет.
Для наглядного пояснения роли теоремы Шеннона прибегнем к следующему сравнению. Пусть имеется
трубопровод для доставки от источника некоторого жидкого продукта. Технические возможности
трубопровода определяются количеством жидкости, которое можно передать по нему в единицу времени.
Производительность источника определим количеством чистого продукта, поступающего от него в
единицу времени, а пропускную способность трубопровода – как максимально возможную скорость
передачи чистого продукта, соответствующую условию, что от источника поступает чистый продукт без
примесей. Аналогом канала с помехами может служить трубопровод с утечкой. Пропускная его
способность будет меньше. Чем в трубопроводе без утечки, на величину утечки продукта за единицу
времени. Можно теперь представить, какой эффект вызвало бы утверждение, что существует такой
способ введения примеси («избыточности») в продукт, при котором, введя количество примеси, равное
утечке в трубопроводе, можно по нему доставлять продукт без потерь со скоростью, отвечающей
пропускной способности трубопровода с утечкой. Именно такой смысл имеет теорема Шеннона
применительно к задаче передачи информации. Продолжая аналогию этого примера, можно сказать, что
такой способ введения примеси требует наличия некоего «отстойника», в котором примесь будет
отстаиваться в течение определенного времени перед подачей в трубопровод (в идеале – бесконечное
время). После такого «отстоя» при движении жидкости по трубопроводу утечку будет уходить только
примесь.
Интерпретация результатов Шеннона для задач хранения и поиска информации. Результаты теорем
Шеннона, традиционно формулируемые для задачи передачи сообщений, легко распространяются на
задачи хранения и поиска информации.
Рассмотрим задачу хранения данных в следующей обобщенной форме. Пусть данные в виде
последовательности записей размещаются в ячейках запоминающего устройства (ЗУ); каждая запись
помещается в отдельную ячейку. Записи, предназначенные для хранения, характеризуются некоторой
совокупностью технических особенностей: размерами, способами кодирования данных, форматами кодов
и т.п. Ячейки ЗУ, в которых размещаются записи, также характеризуются некоторой совокупностью
своих технических особенностей: внутренним представлением данных, способом доступа, системой
меток и рядом технических ограничений на процесс размещения данных. Кроме того, информация,
размещаемая в ячейках ЗУ, может подвергаться воздействию помех, из-за чего в записях появляются
ошибки.
Возникает вопрос, при каких условиях возможно достоверное хранение информации, т.е. получение из ЗУ
данных в том виде, в каком они были туда помещены.
Для ответа на этот вопрос в соответствии с шенноновским подходом необходимо перейти от
технических характеристик к информационным:
- для запоминаемых данных определить среднюю энтропию записи;
- для ЗУ определить максимальное количество информации, которое может быть размещено в ячейке с
учетом ее технических ограничений и действующих в ней помех, то есть определить информационную
емкость ячейки.
Тогда для информационных пользователей будет справедлива следующая формулировка теоремы
Шеннона для задачи хранения информации: для запоминающего устройства (с помехами и без помех)
существует способ сколь угодно достоверного кодирования и декодирования хранимых данных, если
только средняя энтропия записи меньше информационной емкости ячейки.
Если рассмотреть применение идеального кодирования к задаче хранения информации, то станет ясно,
что для этого потребуется ЗУ с потенциально бесконечным числом ячеек, чтобы разместить в нем
типичные последовательности записей сколь угодно большой длины. В этом проявляется техническая
нереализуемость идеального кодирования применительно к задаче хранения информации.
К идеальному результату можно приблизиться, укрупняя хранимые записи. На практике в устройствах
хранения данных для ЭВМ (например, в накопителях на магнитных лентах и дисках) широко применятся
так называемое блокирование записей. При этом группы записей объединяются в блоки, которые
размещаются в ЗУ как некоторые единые укрупненные записи. Этим достигается более экономное
использование информационной емкости ячеек.
Практическая реализация помехоустойчивого хранения информации основана на методах
помехоустойчивого кодирования. Перед помещением записей в ЗУ искусственно увеличивается их
избыточность за счет введения дополнительных контрольных символов. После считывания записей из ЗУ
производится обнаружение и коррекция ошибок.
Рассмотрим теперь задачу поиска в следующей обобщенной форме. Пусть имеется файл, записи которого
идентифицируются ключами. Множество запросов записей образуют последовательность аргументов
поиска. Знания ключей и аргументов поиска могут подвергаться искажением из-за действия случайных
помех при формировании файла и при подготовке запросов.
Возникает вопрос, при каких условиях возможен достоверный поиск информации, т.е. получение на
каждый запрос именно тех записей, которые требуются.
В соответствии с шенноновским подходом перейдем к информационным характеристикам:
- для последовательностей аргументов поиска определим среднюю энтропию аргументов. Если на
аргументы действуют ошибки, то необходимо учесть увеличение средней энтропии вследствие ошибок;
- для множества записей файла определим информационную емкость ключа – максимальное количество
информации, которое может содержаться в ключе файла. Если ключи файла могут содержать случайные
ошибки, то необходимо учесть уменьшение информационной емкости ключа вследствие ошибок.
Тогда для информационных показателей будет справедлива следующая формулировка теоремы Шеннона
для задачи поиска информации:
Для поиска в файле (с помехами и без помех) существует способ сколь угодно достоверного поиска
нужных записей, если только средняя энтропия аргумента меньше информационной емкости ключа.
Применение алгоритма идеального кодирования в данной задаче потребует потенциально бесконечного
укрупнения файла, чтобы производить поиск в качестве аргумента выступают типичные
последовательности исходных аргументов. В этом проявляется техническая нереализуемость идеального
кодирования применительно к задаче поиска информации.
Как упоминалось во второй главе, разработка технически реализуемых способов помехоустойчивого
поиска в настоящее время находится в зачаточном состоянии своего развития. Имеющиеся здесь
результаты существенно скромнее, чем, например, в помехоустойчивом кодировании, где создана
обширная и глубокая математическая теория кодирования. В чем здесь дело? Почему бы не
воспользоваться результатами теории кодирования для решения родственной задачи поиска.
Основная идея помехоустойчивого кодирования состоит в искусственном введении избыточности в
сообщения по подачи их в канал с помехами. В большинстве задач поиска мы имеем дело с естественной
избыточностью сообщений, на которую мы не можем активно воздействовать. Мы получаем уже
искаженный аргумент поиска, например, невнятно произнесенную по телефону фамилию клиента, и
можем рассчитывать только на естественную избыточность языка (естественная избыточность русского
языка, как и большинства европейских языков, оставляет примерно 60 % ).Однако, учитывая
принципиальную разрешимость этой задачи в свете результатов Шеннона, а также последние публикации
по проблемам помехоустойчивого поиска можно надеяться, что эта проблема будет решена и технически.
13. Сжатие данных
Закодированные сообщения передаются по каналам связи, хранятся в запоминающих устройствах,
обрабатываются процессором. Объемы данных, циркулирующих в АСУ, велики, и поэтому во многих
случаях важно обеспечить такое кодирование данных, которое характеризуется минимальной длиной
получающихся сообщений. Эта проблема сжатия данных. Решение её обеспечивает увеличение скорости
передачи информации и уменьшение требуемой памяти запоминающих устройств. В конечном итоге это
ведет к повышению эффективности системы обработки данных.
Существует два подхода (или два этапа) сжатия данных:
сжатие, основанное на анализе конкретной структуры и смыслового содержания данных;
сжатие, основанное на анализе статистических свойств кодируемых сообщений. В отличие от первого
второй подход носит универсальный характер и может использоваться во всех ситуациях, где есть
основания полагать, что сообщения подчиняются вероятностным законам. Далее мы рассмотрим оба этих
подхода.
Сжатие на основе смыслового содержания данных
Эти методы носят эвристический, уникальный характер, однако основную идею можно пояснить
следующим образом. Пусть множество содержит N  2 k элементов. Тогда для кодирования элементов
множества равномерным кодом потребуется k  log 2 N двоичных знаков. При этом будут использованы
все двоичные кодовые комбинации. Если используются не все комбинации, код будет избыточным. Таким
образом, для сокращения избыточности следует попытаться очертить множество возможных значений
элементов данных и с учетом этого произвести кодирование. В реальных условиях это не всегда просто,
некоторые виды данных имеют очень большую мощность множества возможных значений. Посмотрим,
как же поступают в конкретных случаях.
Переход от естественных обозначений к более компактным. Значения многих конкретных данных
кодируются в виде, удобном для чтения человеком. При этом они содержат обычно больше символов, чем
это необходимо. Например, дата записывается в виде «26 января 1982 г.» или в самой краткой форме:
«26.01.82», при этом многие кодовые комбинации, например «33.18.53» или «95.00.11», никогда не
используются. Для сжатия таких данных день можно закодировать пятью разрядами, месяц – четырьмя,
год – семью, т.е. вся дата займет не более двух байтов. Другой способ записи даты, предложенный еще в
средние века состоит в том, чтобы записывать общее число дней, прошедших к настоящему времени с
некоторой точки отсчета. При этом часто ограничиваются четырьмя последними цифрами этого
представления. Например, 24 мая 1967 года записывается в виде 0000 и отсчет дней от этой даты требует,
очевидно, два байта в упакованном десятичном формате.
Аналогичным образом могут быть сжаты номера изделий, уличные адреса и т.п.
Подавление повторяющихся символов. Во многих данных часто присутствуют повторяющиеся подряд
символы: в числовых – повторяющиеся старшие или младшие нули, в символьных – пробелы и т.п. Если
воспользоваться специальным символом, указывающим на повторение, а после него помещать в
закодированном виде число повторений, то тем самым можно уменьшить избыточность, обусловленную
повторениями. Например, подавление повторений может быть произведено по следующей схеме. В коде
ДКОИ-8 большая часть допустимых кодовых комбинаций не используется. Одну из таких комбинаций
(например, с нулем во второй позиции) можно использовать как признак повторения. Тогда байт
следующего вида с последующим байтом кода символа заменяют цепочку повторяющихся символов
Эффективность такого метода определяется числом и размерами участков повторяющихся символов.
Кодирование часто используемых элементов. Некоторые данные, такие как имена и фамилии,
принадлежат множеству возможных значений очень большого размера. Однако в большинстве случаев
используется лишь малая часть возможных значений (действует правило «90/10»-в девяноста процентах
случаев используется 10 процентов возможных значений). Поэтому для сжатия данных можно определить
множество наиболее часто используемых значений, экономно закодировать его элементы и использовать
эти коды вместо обычного представления. В частности, имена людей можно кодировать одним байтом,
что дает 256 возможных кодовых комбинаций. Если при этом использовать первый разряд как признак
пола, то получится 128 женских и 128 мужских имен. Как обеспечить возможность записи имен, не
входящих в закодированные? Для этого можно, например, условиться, что некоторая специальная кодовая
комбинация длиной в один байт означает, что последующие байты содержат полное написание имени в
обычном коде ДКОИ-8.
Аналогичным образом может быть произведено кодирование наиболее употребляемых фамилий (для
этого могут понадобиться 2-байтовые коды). Многие сообщения и файлы содержат текстовые фрагменты
из некоторых областей знаний. В таких текстах можно выделить множество наиболее употребительных
слов, пронумеровать их и закодировать по вышеизложенному способу.
Контекстное сжатие данных. В упорядоченных наборах данных часто совпадают начальные символы
или даже группы начальных символов записей. Поэтому можно закодировать данные, рассматривая их в
контексте с предыдущими. В этом случае сжимаемым элементом данных может предшествовать
специальная кодовая комбинация, характеризующая тип сжатия. Например, возможны комбинации,
указывающие на то, что:
элемент данных совпадает с предыдущим;
элемент данных имеет следующее по порядку значение;
элемент совпадает с предыдущим кроме последнего символа;
элемент совпадает с предыдущим кроме двух (трех, четырех и т.д.) последних символов;
элемент длиной l байтов не имеет связи с предыдущим.
При использовании подобных контекстных символов закодированные данные содержат только отличия
текущих элементов от предыдущих.
Реализация сжатия данных требует специальных или (и) программных затрат, а также затрат
памяти на предварительное кодирование с целью сжатия данных и последующее декодирование для
восстановления первоначальной формы данных. Это означает, что сжатие данных – не всегда
целесообразное мероприятие. Например, в базах данных обычно сжимаются архивные файлы с
невысокой частотой использования. Сжатие применяется также для сокращения размеров
индексных таблиц, используемых для организации поиска информации в индексно-последовательных
файлах.
14. Экономное кодирование
Рассмотрим сжатие на основе статистических свойств данных.
Этот подход называется также теорией экономного или эффективного кодирования. Он представляет
собой универсальный метод, позволяющий сжимать данные, отвлекаясь от их смысла (семантики). А
основываясь только на их статистических свойствах.
Вероятностная модель кодируемых сообщений.
Будем считать, что последовательность, которую нужно закодировать. Составлена из сообщений,
принадлежащих некоторому конечному множеству с известным числом элементов N. Появление
сообщений в последовательности носит вероятностный характер, т.е. каждому i-му сообщению (I=1,2…N)
можно поставить в соответствие вероятность pi его появления (  iN1 pi  1 ) – условие нормировки.
Сообщения кодируются последовательности двоичных знаков (0 и 1). В качестве критерия экономности
кода выступает средняя длина кодового слова, необходимая для кодирования одного сообщения.
Экономное кодирование основано на использовании кодов с переменной длиной кодового слова, которые
мы и рассмотрим.
Коды с переменной длиной кодового слова.
До сих пор рассматривались равномерные коды, у которых кодовое слово всегда содержит одинаковое
число знаков. Однако давно известны и коды, у которых длина кодового слова не постоянна, например
код Морзе.
При использовании таких неравномерных кодов возникает задача выделения отдельных кодовых слов из
закодированной последовательности для однозначного декодирования сообщений. В коде Морзе для
этого предусмотрена специальная кодовая комбинация – разделитель (тройная пауза). Однако более
экономным является использование при кодировании так называемого условия префиксности кода
(условие Фано): никакое кодовое слово не должно являться началом другого кодового слова.
Выполнение этого условия гарантирует однозначное расчленение последовательности на кодовые
слова без применения разделителей. Очередное кодовое слово получается последовательным
считыванием знаков до тех пор, пока получающаяся комбинация не совпадает с одним из кодовых слов.
Префиксный код называется примитивным, если его нельзя сократить, т.е. при вычеркивании любого
знака хотя бы в одном кодовом слове код перестает быть префиксным. Нетрудно видеть, что если код
префиксный и мы выбрали любой набор из нулей и единиц, не входящий в число кодовых слов, то
возможно одно из двух: либо не существует кодового слова, начальный отрезок которого совпадает с
нашим набором, либо (если такое кодовое слово существует), приписав к концу нашего набора нуль или
единицу, мы получим какое-то кодовое слово или начальный отрезок кодового слова.
Двоичное кодирование как равномерным, так и неравномерным префиксным кодом удобно
представлять в виде бинарного кодового дерева. Если мы всегда условимся сопоставлять левой ветви
нуль, а правой – единицу, то каждой свободной вершине дерева будет однозначно соответствовать
некоторый набор двоичных знаков, показывающий, в какой последовательности нужно сворачивать
направо и налево, добираясь до этой вершины из корня дерева. Таким образом, свободной вершине
кодового дерева ставится в соответствие определенное кодовое слово. Например, рассмотренному коду
соответствует дерево, приведенное на рис. 3.
Рис. 3. Кодовое дерево примитивного префиксного кода.
Полезна следующая интерпретация процесса двоичного кодирования. На каждом шаге движения по
кодовому дереву от корня к свободным вершинам происходит выбор одного из двух поддеревьев: правого
и левого. Это соответствует разбиению множества сообщений на два подмножества (правое и левое) с
присвоением им очередных двоичных знаков (единицы и нуля). Так, в рассмотренном примере исходное
множество (0, 1,…,9) было разбито на два подмножества (0,1) и (2,3,…,9). При дальнейшем движении
вправо множество (2,3,…,9) в свою очередь было разбито на два подмножества (2,3,4) и (5,6,…,9), а при
движении влево множество (0,1) было разбито на два подмножества (0) и (1) и т.д. до тех пор, пока во
всех подмножествах не осталось по одному элементу. Таким образом, кодовые комбинации
характеризуют «историю» последовательного разбиения исходного множества сообщений на правые и
левые подмножества.
Минимизация средней длины кодового слова.
Идея использования кодов переменной длины для сжатия данных состоит в том, чтобы сообщениям с
большей вероятностью появления ставить в соответствие кодовые комбинации меньшей длины и,
наоборот, сообщения с малой вероятностью появления кодировать словами большей длины. Средняя
длина кодового слова определяется следующим образом:
N
L   pi li
i 1
,
где li – длина кодового слова для кодирования i-го сообщения
pi - вероятность появления i-го сообщения.
Возникает вопрос, как выбрать кодовые слова, чтобы для заданных вероятностей p1,p2,…..pN обеспечить
по возможности меньшую среднюю длину кодового слова?
Для ответа на этот вопрос учтем тот очевидный факт, что равномерный код, всем кодовым комбинациям
которого соответствуют равновероятные сообщения, является оптимальным, т.е. имеет минимальную
длину кодового слова. На каждом шаге двоичного кодирования производится разбиение множества
сообщений на два подмножества, причем одному из них приписывается единица, а другому – ноль. Таким
образом, на каждом шаге производится кодирование подмножеств равномерным кодом длиной в I
двоичный знак. Отсюда следует принцип: нужно стремиться так производить разбиение на два
подмножества, чтобы суммарные вероятности подмножеств были одинаковыми (или как можно более
близкими друг к другу).
15. Процедуры Шеннона-Фано и Хаффмена
Процедура Шеннона-Фано.
В этом алгоритме используется следующий способ разбиения на два подмножества на каждом шаге
кодирования. Предварительно производится упорядочивание сообщений по убыванию (или возрастанию)
вероятностей pi. Разбиения на множества производится путем выбора разделяющей границы в
упорядоченной последовательности так, чтобы суммарные вероятности подмножеств были по
возможности одинаковыми. На рис. 4 приведено кодовое дерево, построенное этим методом для
рассмотренного выше примера. Для наглядности в вершины дерева записаны подмножества кодируемых
сообщений, а возле вершин – суммарные вероятности соответствующих подмножеств.
Кодовое дерево, построенное процедурой Шеннона-Фано
0,…,
9
0,…,6
28/55
27/55
7,8,9
0,…
,4
0,1
,215/55
55/55
5,6
3,
4
17/55
5
7,8
8
13/55
7
6/55
7/55
8
8
10/55
0,
2
3
4
1
6/55
9/55
8/55
0
1 9/55
11
010
100
101
3/55
3/55
4/55
011
5/55
Процедура Хафмена.
Процедура
простым алгоритмом построения экономного кода, однако, это не
1/55 2/55 Шеннона-Фано
0001 0010 является
0011
всегда самый лучший из возможных алгоритмов. Причина в том, что мы ограничиваем способ разбиения
тем.00000
Что вероятности
событий, отнесенных к первому подмножеству, всегда больше (или всегда меньше)
00001
вероятностей событий, отнесенных ко второму подмножеству. Оптимальный алгоритм, очевидно, должен
учитывать все возможные комбинации событий при разбиении на равновероятные подмножества. Это
обеспечивается в процедуре Хафмана экономного кодирования.
Процедура Хаффмана представляет собой рекурсивный алгоритм, стоящий бинарное кодовое дерево в
обратную сторону, т.е. от конечных вершин к корню. Конечные вершины представляют отдельные
сообщения и их вероятности, корень представляет множество всех сообщений с суммарной вероятностью,
равной единице, а внутренние вершины, а внутренние вершины представляют сгруппированные
подмножества и их суммарные вероятности. Пусть Pm – задача кодирования m  2 сообщений, где
сообщение i имеет вероятность появления pi и p1  p2  ...  pm . Основная идея алгоритма состоит в
том, чтобы объединить два сообщения с наименьшими вероятностями в одно множество и далее решать
'
'
'
задачу Pm-1 c m-1 сообщениями и вероятностями p1  p1  p 2 , p 2  p3 ,..., p m1  p m . Практически кодовое
дерево в явном виде строится в обратном направлении, как показано на рис. 5 для нашего примера.
Кодовое дерево, построенное процедурой Хаффмана.
00000
00001 0001
1100
1101
001
100
0
2
3
4
5
6
7
8
9
101 1 111
01
1/55
2/55
3/55
4/55
5/55
6/55
7/55
8/55
9/55
10/55
0,
3,
6,
1
4
7
0,
1,
2
15/55
0,1
,2,
3/55
5
0,1,
2,5,
9
6/55
18/55
3,4,
6,7,
8
0,
..,
9
3,
4,
8
9/55
Прямой подсчет дает среднее значение длины кодового слова L=3.145, что совпадает с результатом,
полученным с помощью процедуры Шеннона-Фано (это означает, что в данном примере процедура
Шеннона-Фано также оказалась оптимальной).
16. Помехоустойчивое кодирование. Основные принципы помехоустойчивого кодирования.
Основные принципы помехоустойчивого кодирования.
Помехоустойчивые коды – одно из наиболее эффективных средств обеспечения высокой верности
передачи дискретной информации. Создана специальная теория помехоустойчивого кодирования, быстро
развивающаяся в последнее время.
Бурное развитие теории помехоустойчивого кодирования связано с внедрением автоматизированных
систем, у которых обработка принимаемой информации осуществляется без участия человека.
Использование для обработки информации электронных цифровых вычислительных машин предъявляет
очень высокие требования к верности передачи информации.
Теорема Шеннона для дискретного канала с помехами утверждает, что вероятность ошибок за счет
действия в канале помех может быть обеспечена сколь угодно малой путем выбора соответствующего
способа кодирования сигналов. Из этой теоремы вытекает весьма важный вывод о том, что наличие помех
не накладывает принципиально ограничений на верность передачи.
Однако в теореме Шеннона не говорится о том, как нужно строить помехоустойчивые коды.
На этот вопрос отвечает теория помехоустойчивого кодирования.
Рассмотрим сущность помехоустойчивого кодирования, а также некоторые теоремы и определения,
относящиеся к теории такого кодирования.
Под помехоустойчивыми или корректирующими кодами понимают коды, позволяющие обнаружить и
устранить ошибки, происходящие при передаче из-за влияния помех.
Для выяснения идеи помехоустойчивого кодирования рассмотрим двоичный код, нашедший на практике
наиболее широкое применение.
Напомним, что двоичный код – это код с основание m=2.
Количество разрядов n в кодовой комбинации принято называть длиной или значностью кода. Каждый
разряд может принимать значение 0 или 1. Количество единиц в кодовой комбинации называют весом
кодовой комбинации и обозначают  .
Ошибки, вследствие воздействия помех, появляются в том, что в одном или нескольких разрядах кодовой
комбинации нули переходят в единицы и, наоборот, единицы переходят в нули. В результате создается
новая ложная кодовая комбинация.
Если ошибки происходят только в одном разряде кодовой комбинации, то такие ошибки называются
однократными. При наличии ошибок в двух, трех и т.д. разрядах ошибки называются двукратными,
трехкратными и т.д.
Для указания мест в кодовой комбинации, где имеются искажения символов, используется вектор ошибки
_
e . Вектор ошибки n-разрядного кода – это n-разрядная комбинация, единицы в которой указывают
положение искаженных символов кодовой комбинации. Например, если для пятиразрядного кода вектор
_
ошибки имеет e =01100, то это значит, что имеют место ошибки в третьем и четвертом разрядах кодовой
комбинации.
Вес вектора ошибки e характеризует кратность ошибки. Сумма по модулю для искажений кодовой
комбинации и вектора ошибки дает исходную неискаженную комбинацию.
Помехоустойчивость кодирования обеспечивается за счет введения избыточности в кодовые
комбинации. Это значит, что из n символов кодовой комбинации для передачи информации используется
k<n символов. Следовательно, из общего числа N 0  2 n возможных кодовых комбинаций для передачи
информации используется только N  2 k комбинаций. В соответствии с этим все множества
N 0  2 n возможных кодовых комбинаций делятся на две группы. В первую группу входит множество
N  2 k разрешенных комбинаций. Вторая группа включает в себя множество ( N 0  N )  2 n  2 k
запрещенных комбинаций.
Если на приемной стороне установлено, что принятая комбинация относится к группе разрешенных, то
считается, что сигнал пришел без искажений. В противном случае делается вывод, что принятая
комбинация искажена. Однако это справедливо лишь для таких помех, когда исключена возможность
перехода одних разрешенных комбинаций в другие.
В общем случае каждая из N разрешенных комбинаций может трансформироваться в любую из N0
возможных комбинаций, т.е. всего имеется N*N0 возможных случаев передачи (рис.1), из них N случаев
безошибочной передачи (на рис. 1 обозначены жирными линиями), N(N-1) случаев перехода в другие
разрешенные комбинации (на рис. 1 обозначены пунктирными линиями) и N(N0- N) случаев перехода в
запрещенные комбинации (на рис. 7.3 обозначены штрих пунктирными линиями).
Таким образом, не все искажения могут быть обнаружены. Доля обнаруживаемых ошибочных
комбинаций составляет
N (N0  N )
N
 1
NN 0
N0
Для использования данного кода в качестве исправляющего множество запрещенных кодовых
комбинаций разбивается на N непересекающихся подмножеств Mk . Каждое из множеств Mk ставится в
соответствие одной из разрешенных комбинаций.
Если принятая запрещенная комбинация принадлежит подмножеству Mi , то считается, что передана
комбинация Ai
Ошибка будет исправлена в тех случаях, когда полученная комбинация действительно образовалась из
комбинации Ai. Таким образом, ошибка исправляется в ( N 0  N ) случаях, равных количеству
запрещенных комбинаций. Доля исправляемых ошибочных комбинаций от общего числа
обнаруживаемых ошибочных комбинаций составляет
N0  N
1
 .
N (N0  N ) N
Способ разбиения на подмножества зависит от того, какие ошибки должны исправляться данным кодом.
Связь исправляющей способности кода с кодовым расстоянием.
Для оценки степени различия между двумя произвольными комбинациями данного кода используется
характеристика, получившая название расстояния между кодовыми комбинациями. Наименьшее
расстояние между разрешенными кодовыми комбинациями называют кодовым расстоянием и обозначают
dmin . Это очень важная характеристика кода, ибо именно она характеризует его корректирующие
способности.
Рассмотрим это на конкретных примерах.
Пусть необходимо построить код, обнаруживающий все ошибки кратностью t и ниже.
Построить такой код – это значит, из множества N0 возможных комбинаций выбрать N разрешенных
комбинаций так, чтобы любая из них в сумме по модулю два с любым вектором ошибок с весом e  t
не дала бы в результате никакой другой разрешенной комбинации. Для этого необходимо, чтобы кодовое
расстояние удовлетворяло условию
7.29
d min  t  1
В общем случае для устранения ошибок кратности  кодовое расстояние должно удовлетворять условию
7.31
d min  t    1
Аналогично рассуждая, можно установить, что для исправления всех ошибок кратности не более  и
одновременного обнаружения всех ошибок кратности не более t (при t>  ) кодовое расстояние должно
удовлетворять условию
7.32
d min  t    1
При этом нужно иметь в виду, что если обнаруженная кодом ошибка исправлена быть не может, т.е. в
данном случае код только обнаруживает ошибку.
17. Помехоустойчивое кодирование. Помехоустойчивость кода. Корректирующие коды.
Помехоустойчивость кода.
Минимальное кодовое расстояние некоторого кода определяется как минимальное расстояние Хэмминга
между любыми разрешенными кодовыми словами этого кода. У безызбыточного кода минимальное
кодовое расстояние dmin=1. Чем больше минимальное кодовое расстояние, тем больше избыточность кода.
Максимальное кодовое расстояние кода, очевидно, равно его размеру, т.е. числу двоичных разрядов в
кодовом слове.
Непосредственные вычисления кодовых расстояний у рассмотренного выше кода, построенного методом
контрольных сумм, дают следующие значения показателей: dmin=3 и dmax=7.
Очевидно, что  -кратная ошибка приводит к тому, что искаженная кодовая комбинация отодвигается от
исходной на расстояние d   . В то же время ошибка не может быть обнаружена, если она переводит
одну разрешенную кодовую комбинацию в другую, тоже разрешенную. Следовательно, способность кода
обнаруживать все ошибки некоторой кратности зависит от минимального расстояния между
разрешенными кодовыми словами: чем больше минимальное кодовое расстояние, тем большей кратности
требуется ошибка для перевода любой разрешенной кодовой комбинации в другую разрешенную. Таким
образом, можно утверждать, что код с минимальным кодовым расстоянием dmin способен обнаруживать
любые ошибки кратностью   d min  1.
У рассмотренного выше кода dmin=3, следовательно, он может обнаруживать любые однократные и
двукратные ошибки.
Способность кода исправлять обнаруженные ошибки состоит в возможности однозначного отнесения
запрещенной кодовой комбинации к единственной разрешенной. Для этого необходимо, чтобы
минимальное кодовое расстояние превышало расстояние, порождаемое действием двух любых ошибок.
Действительно, в этом случае запрещенные кодовые комбинации, получающиеся в результате ошибок из
одного кодового слова, никогда не совпадут с запрещенными комбинациями, получающимися в
результате ошибок из любого другого кодового слова, а тем более – с другими разрешенными кодовыми
словами. Таким образом, необходимо, чтобы выполнялось условие
d min  2  1, откуда
d 1
следует   min
2
У рассмотренного выше кода, построенного методом контрольных сумм, dmin=3, следовательно, он может
исправлять только любые однократные ошибки.
Рассмотрим n-разрядный код, основанный на n-кратном повторении каждого передаваемого символа. У
него dmin= n. Следовательно, максимальная кратность обнаруживаемых ошибок равна, что соответствует
случаю искажения всех символов, кроме одного. Максимальная кратность исправляемых ошибок равна
(n-1)/2, что соответствует искажению «почти» половины всех символов. Это соответствует фиксации
ошибки при обнаружении хотя бы одного неодинакового символа и исправлению ошибки на основе
определения, каких значений больше.
Рассмотрим n-разрядный код, основанный на введении одного разряда контроля четности. У него dmin= 2,
и, следовательно, максимальеная кратность обнаруживаемых ошибок равна 1, а исправляемых – 0 (код не
способен исправлять ошибки).
Граница Хэмминга. Рассмотрим задачу немного иначе. Возьмём n-разрядный код и зададимся вопросом о
том, сколько контрольных разрядов должно быть в каждом кодовом слове, чтобы код мог исправлять все
ошибки заданной максимальной кратности  (разумеется,   n ).
Возьмём какое-либо разрешенное кодовое слово и подсчитаем общее число кодовых комбинаций,
порождаемых из него всевозможными ошибками кратностью не выше  . Ситуация отсутствия ошибок
дает одну (исходную комбинацию). Все однократные ошибки, искажающие 1 из n разрядов, очевидно,
порождают n комбинаций. Все двукратные ошибки, искажающие 2 из n разрядов, очевидно, порождают
C n2 комбинаций, где C nm  n! / m!(n  m)! - число сочетаний из n по m. Аналогичным образом все m-кратные
ошибки, искажающие m из n разрядов, порождают C nm комбинаций. Учитывая, что формально
C n0  1 и C n1  n , получаем следующую формулу для числа кодовых комбинаций, приходящихся на каждое
разрешенное кодовое слово:

1  n  C m2  ...  C n   C nm .Общее число кодовых комбинаций n-разрядного кода составляет 2 n ,
m 0
следовательно, чтобы комбинации, порождаемые из одного разрешенного кодового слова, не переходили
в комбинации, порождаемые из другого, и могли быть исправлены, необходимо, чтобы число
2n
разрешенных кодовых слов Q удовлетворяло условию Q  
.
m
 Cn
m 0
Это есть так называемая граница Хэмминга для числа разрешенных кодовых слов.
Граница Хэмминга позволяет определить минимальное число контрольных разрядов, необходимых для
исправления ошибок с заданной максимальной кратностью. Пусть в n-разрядном коде k информационных
разрядов, тогда число разрешенных кодовых слов составляет Q  2 k . Подставляя это значение в формулу
для границы Хэмминга, получаем

2 n  k   C nm ,
m 0
откуда

n  k  log 2  C nm
m 0
Величина n-k, как раз и есть минимальное число контрольных разрядов.
Коды, у которых число контрольных разрядов в точности совпадает с границей Хэмминга, называются
совершенными. Совершенные коды обладают минимальной избыточностью при заданном уровне
способности исправлять ошибки. В построенном выше примере 7-разрядного кода, исправляющего все
однократные ошибки, использовалось 3 контрольных разряда. Подставляя параметры кода в полученную
формулу, убеждаемся, что 3 – это минимальное количество контрольных разрядов, необходимое для
решения задач, следовательно, код совершенный. Для более сложных случаев (большей кратности
ошибок) не всегда удается построить совершенный код.
Классификация корректирующих кодов.
Математическая теория корректирующих кодов бурно развилась в 50-60-х годах XX века в обширную и
практически важную самостоятельную науку, базирующуюся на казавшихся самыми абстрактными и
далекими от практики разделах современной математики.
У большинства известных в настоящее время корректирующих кодов помехоустойчивость
обеспечивается за счет их алгебраических свойств, в связи с чем их называют алгебраическими кодами.
Алгебраические коды подразделяются на два больших класса: блоковые и непрерывные (реккурентные).
В случае блоковых кодов кодирование заключается в сопоставлении каждому символу сообщения блока
из n символов. Различают разделимые и неразделимые блоковые коды. В разделимых кодах четко
разграничены информационные и контрольные (проверочные) символы. В неразделимых кодах все
символы выполняют функции как информационных, так и контрольных.
Непрерывными (рекуррентными ) называются такие коды, в которых введение избыточных символов в
кодируемую последовательность осуществляется без разделения её на блоки. Непрерывные коды также
могут быть разделимыми и неразделимыми.
Большой класс разделимых кодов составляют систематические коды, у которых значения проверочных
символов определяются в результате линейных операций над определенными информационным
символами. Для случая двоичных кодов каждый проверочный символ выбирается таким, чтобы его сумма
по модулю 2 с определенными информационными символами стала равной нулю, т.е. обеспечивалась
четность некоторой контрольной суммы. Проверочные символы могут располагаться на любом месте
кодовой комбинации. Их число и соответствующие проверочные равенства (контрольные суммы)
определяются тем, какие и сколько ошибок должен обнаруживать или исправлять код.
18. Помехоустойчивое кодирование. Методы помехоустойчивого кодирования.
Методы помехоустойчивого кодирования.
Рассмотрим простые практические способы построения кодов, способных обнаруживать и исправлять
ошибки. Ограничимся рассмотрением двоичных каналов и равномерных кодов.
Метод контроля четности. Это простой способ обнаружения некоторых из возможных ошибок. Будем
использовать в качестве разрешенных половину возможных кодовых комбинаций, а именно те из них,
которые имеют четное число единиц (или нулей). Однократная ошибка при передаче через канал
неизбежно приведет к нарушению четности, что и будет обнаружено на выходе канала. Очевидно, что
трехкратные, пятикратные и вообще ошибки нечетной кратности ведут к нарушению четности и
обнаруживаются этим методом, в то время как двукратные, четырехкратные и вообще ошибки четной
кратности – нет.
Практическая техника кодирования методом контроля четности следующая. Из последовательности
символов, подлежащих передаче через канал, выбирается очередной блок из k-1символов, называемых
информационными, и к нему добавляется k-й символ, называемый контрольным. Значение
контрольного символа выбирается так, чтобы обеспечить четность получаемого кодового слова, т.е.
чтобы сделать его разрешенным.
Метод контроля четности представляет значительную ценность и широко применяется в тех случаях, в
которых вероятность появления более одной ошибки пренебрежимо мала (во многих случаях, если
наверняка знать, что кодовое слово принято с ошибкой, имеется возможность запросить повторную
передачу). В то же время избыточность кода увеличивается минимально и незначительно при больших k(в
k/( k-1)раз).
Метод контрольных сумм. Рассмотренный выше метод контроля четности может быть применен
многократно для различных комбинаций разрядов передаваемых кодовых слов – и это позволит не только
обнаруживать, но и исправлять определенные ошибки.
Пример:
Будем из входной последовательности символов брать по четыре информационных символа а1а2а3а4,
дополнять их тремя контрольными символами а5а6а7 и получившееся семисимвольное слово посылать в
канал. Контрольные символы будем подбирать так, чтобы были четными следующие суммы:
s1= а1 +а2 +а3 + a5,
s2= а1 +а2 +а4 + a6,
s3= а1 +а3 +а4 + a7.
В каждую сумму входит по оному контрольному символу, поэтому данное требование всегда выполнимо.
Благодаря «маленьким хитростям», предусмотренным при формировании контрольных сумм, проверка их
четности на выходе канала позволяет однозначно установить, была ли допущена при передаче
однократная ошибка и какой из разрядов был при этом искажен (ошибками большей кратности
пренебрегаем). Действительно, если один из семи символов был искажен, то, по крайней мере, одна из
сумм обязательно окажется нечетной, т.е. четность всех контрольных сумм s1, s2, s3 свидетельствует об
отсутствии однократных ошибок. Далее, лишь одна сумма будет нечетной в том, (и только в том) случае,
если искажен входящий в эту сумму один из трех контрольных символов (a5, a6 или a7). Нечетность двух
или трех сумм означает, что искажен тот из информационных символов а2, а3 или а4, который входи в обе
эти суммы. Наконец, нечетность всех трех сумм означает, что неверно принят входящий во все суммы
символ а1.
Итак, в данном примере метод контрольных сумм, увеличивая длину кода в 7/4=1,75 раза за счет введения
избыточности, позволяет исправить любую однократную ошибку (но не ошибку большей кратности).
Основываясь на этой идее, в принципе, можно построить коды, исправляющие все ошибки большей (но
всегда ограниченной) кратности.
19. Дискретизация информации. Теорема Котельникова.
Классификация сигналов по дискретно-непрерывному признаку. Проблемы дискретизации
информации
Классификация сигналов по дискретно-непрерывному признаку
Все сообщения по характеру изменяющиеся во времени можно разделить на непрерывные и
дискретные. Непрерывные по времени сообщения отображаются непрерывной функцией времени.
Дискретные по времени сообщения характеризуются тем, что поступают в определенные моменты
времени и описываются дискретной функцией t.
Сообщения также можно разделить на непрерывные и дискретные по множеству. Непрерывные
множеству сообщения характеризуются тем, что функция, их описывающая, может принимать
непрерывное множество значений. Дискретные по множеству сообщения – это сообщения, которые
могут быть описаны с помощью конечного набора чисел или дискретных значений некоторой функции.
Дискретности по множеству и времени не связаны друг с другом. Рассмотрим возможные типы
сообщений подробнее.
Пусть сигнал описывается функцией X (t)
1) непрерывные по множеству и времени, или просто непрерывные; (рис. 1.2)
2) непрерывные по множеству и дискретные по времени; (рис. 1.3)
3) дискретные по множеству и непрерывные по времени; (рис. 1.4)
4) дискретные по множеству и времени, или просто дискретные; (рис. 1.5)
Проблема дискретизации
Согласно строгому определению математического словаря, "дискретность (от лат. discretus –
разделенный, прерывистый) – прерывность; противопоставляется непрерывности. Напр., дискретное
изменение к.-л. величины во времени – это изменение, происходящее через определенные
промежутки времени (скачками); система целых (в противоположность системе действительных
чисел) является дискретной".
Для большей наглядности дополним данное определение рядом примеров. Дискретными являются
показания цифровых измерительных приборов, например, вольтметра (сравните со "старыми",
стрелочными приборами). Очевидным (в самом изначальном смысле этого слова!) образом дискретной
является распечатка матричного принтера, а линия, проводимая графопостроителем, напротив, является
непрерывной. Дискретным является растровый способ представления изображений, тогда как
векторная графика по своей сути непрерывна. Дискретна таблица значений функции, но когда мы
наносим точки из нее на миллиметровую бумагу и соединяем плавной линией, получается непрерывный
график. Механический переключатель диапазонов в приемниках был сконструирован так, чтобы он
принимал только фиксированные положения, а вот регулятор громкости вращался плавно, т.е.
непрерывно.
Какое отношение приведенные выше рассуждения имеют к хранению информации в компьютере? Самое
непосредственное! Компьютер по определению способен хранить только дискретную информацию. Его
память, как бы велика она не была, состоит из отдельных битов, а значит дискретна. А из этого
немедленно следует, что существует проблема преобразования естественной информации в пригодную
для компьютера дискретную форму. В литературе ее называют проблемой дискретизации или
квантования информации.
Названная проблема всегда рассматривается при изложении принципов хранения звуковой информации,
но обычно умалчивается во всех остальных случаях. Непрерывная величина ассоциируется с
графиком функции, а дискретная – с таблицей ее значений. При рассмотрении этих двух объектов
Признаки
разной природы делается вывод о том, что с уменьшением интервала
дискретизации (или, что то же
дискретизации
самое, с увеличением количества точек в таблице) различия между ними существенно уменьшаются.
Последнее означает, что при таких условиях дискретизированная величина хорошо описывает исходную
(непрерывную).
Регулярн
ость
отсчетов
Критерий
Базисные
функции
Принцип
ы
приближе
ния
Ряд
Фурье
Интерполяц
ия
Ряд
Котельн
икова
Экстраполя
ция
оценк
и
Равноме
рные
Максима
точно
льный
Неравные
Среднеква
сти
дратичный
Случайные
Адаптивн
ые
Интеграль
ный
Полино
мы
Чебыше
ва
Комбиниров
анный
Классификация методов дискретизации.
Формулировка теоремы Котельникова: Произвольный сигнал,
спектр которого не содержат частот выше Fв, Гц, может быть полностью в
осстановлен, если известны отсчётные значения этого сигнала, взятые
через равные промежутки времени1/(2Fв) с.
20. Квантование по уровню. Дискретизация по времени.
Квантование по уровню состоит в преобразовании непрерывного множества значений сигнала x(ti) в
дискретное множество значений xk, k=0, …., m-1, X л  X min X max  .
Рассмотрим вначале непрерывное сообщение, представляющее собой процесс
с дискретным
временем, т.е. совокупность отсчетов непрерывной случайной величины Х. Одна из возможных
реализаций такого процесса представлена на рисунке 3.1.
Истинные значения сигнала в каждый момент времени показаны точками. Предположим, что все
возможные (или по крайней мере наиболее вероятные) значения отсчетов процесса сосредоточены в
диапазоне от xmin до xmax. Разобьем весь этот диапазон на конечное число
интервалов
и границы этих интервалов хк-1, хк, хк+1 и т.д. будем считать разрешенными значениями уровней
отсчетов процесса. При этом число разрешенных уровней Ny=N-1.
Процедура округления истинного значения отсчета до значения ближайшего разрешенного уровня
называется квантованием или дискретизацией по значению (уровню) (округленные значения сигнала на
рисунке показаны кружочками). Очевидно, что после осуществления операции квантования непрерывная
случайная величина Х превращается в дискретную, т.е. имеющую конечное число возможных значений, а
непрерывное сообщение - в последовательность элементарных дискретных сообщений источника с
объемом алфавита Nу. Из определения операции квантования следует, что ей присуща неизбежная потеря
информации, обусловленная наличием погрешности квантования
. Значение этой погрешности
(а, следовательно, и количество теряемой из-за нее информации) является контролируемым и может быть
сделано необходимо малым путем выбора достаточного количества Nу разрешенных уровней шкалы
квантования (вследствие соответствующего уменьшения шага квантования
). Таким образом,
непрерывные сообщения, описываемые процессом с дискретным временем, с помощью квантования
отсчетов процесса с контролируемой точностью могут быть преобразованы в дискретные.
Дискретизация по времени
Рассмотрим теперь другой тип непрерывных сообщений, описываемый процессами с непрерывным
временем. Реализация такого процесса x(t) показана на рисунке 3.2.
Очевидно, что если осуществить его дискретизацию , т.е. замену всей совокупности значений процесса
отдельными его мгновенными значениями, выбранными в определенные "разрешенные" моменты
времени
, то он превращается в уже рассмотренный процесс с дискретным временем X¶(t). На
первый взгляд дискретизация приводит к необратимым существенным потерям информации,
обусловленным <отбрасыванием> большей части мгновенных значений процесса. Однако, как будет
видно из дальнейших рассуждений, дело обстоит не совсем так (почти совсем ни так).
Ввиду особой важности процедуры дискретизации для процессов передачи и преобразования
непрерывных сообщений рассмотрим ее более подробно.
Практическая реализация процесса дискретизации может быть осуществлена с помощью упрощенной
схемы, показанной на рисунке 3.3.а.
Электронный ключ управляется последовательностью коротких, но имеющих конечную длительность t,
импульсов uу(t), следующих с периодом Dt, равным шагу дискретизации, т.е. интервалу времени между
соседними выбираемыми в процессе дискретизации значениями сигнала. На время действия импульса
ключ замыкается, и выход схемы оказывается подключенным к входу.
Дискретизация по времени состоит в преобразовании сигнала x(t), непрерывного аргумента t в сигнал
x(ti) дискретного аргумента ti.