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

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

• 1. Функциональная схема системы передачи информации, назначение ее составляющих.
• 2. Основные виды сигналов, используемых при передаче информации.
• 3. Кодирование и модуляция в системах передачи информации.
• 4. Энтропия. Основные свойства энтропии.
• 5. Количество информации. Основные свойства количества информации.
• 6. Условная энтропия и ее свойства.
• 7. Дифференциальная энтропия и ее свойства.
• 8. Помехи и искажения в каналах передачи информации.
• 9. Модели источников дискретных сообщений.
• 10. Энтропия дискретного источника. Полная и частная энтропия.
• 11. Энтропия дискретного источника при наличии статистической связи между знаками.
• 12. Энтропия дискретного источника в отсутствии статистических связей между знаками.
• 13. Избыточность и производительность дискретного источника сообщений.
• 14. Производительность дискретного источника сообщений, пути ее повышения.
• 15. Модели дискретных каналов передачи информации.
• 16. Скорость передачи информации по дискретному каналу. Пропускная способность дискретного канала без помех.
• 17. Эпсилон -производительность непрерывного источника сообщений.
• 18. Модели непрерывных каналов передачи информации.
• 19. Скорость передачи информации по непрерывному каналу.
• 20. Пропускная способность непрерывного канала передачи информации.
• 21. Согласование физических характеристик сигнала и канала передачи информации.
• 22. Согласование статистических свойств источника сообщений и канала передачи информации.
• 23. Эффективное кодирование. Теорема Шеннона о кодировании в канале без помех.
• 24. Эффективное кодирование. Методы эффективного кодирования.
• 25. Кодирование информации при передаче по дискретному каналу с помехами.
• 26. Помехоустойчивое кодирование. Разновидности помехоустойчивых кодов.
• 27. Блоковые коды.
• 28. Сверточные коды. Особенности декодирования.

================================================================
Теперь пробую отетить на эти ворпосы. Список литературы и источников - после ответов. (Хэмминг - "Теория кодирования и теория информации")

================================================
1. Функциональная схема системы передачи информации, назначение ее составляющих.

В наиболее общем виде схема преставима следующим образом -

ИСТОЧНИК->КОДИРОВАНИЕ->КАНАЛ(+ШУМ)->ДЕКОДИРОВАНИЕ->ПОЛУЧАТЕЛЬ

"получатель" также называют приёмником.
=================================================
2. Основные виды сигналов, используемых при передаче информации.

=================================================
4. Энтропия. Основные свойства энтропии.

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

G=E[i=1;q](log[r](1/Pi)); где E[i=1;q] - это сумма от 1 до q; log[r] - логарифм по основанию r.

Математические свойства энтропии.

1) Из формулы следует, что энтропия не может быть отрицательной.
2) Если рассматривать вероятности распределения двух случайных величин Xi и Yi, то можно прийти к ФУНДАМЕНАТАЛЬНОМУ НЕРАВЕСТВУ:
E[i=1;q](log[2](Xi/Yi)) 3) Если мы хотим получить максимальную энтропию ,необходимо использовать неравенсво -
H(S) 4) Энтропия суммы нескольких статистически независииых источников равна сумме энтропий этих источников.
==============================================================

5. Количество информации. Основные свойства количества информации.

Получение информации связано с некоторой неожиданностью, так как не известно заранее - каким будет сообщение.
В связи с этим (грубо говоря) количество информации получаемое при приёме некоего сообщения (возм. - символа) определяется следующим образом -
I=log[2](1/Pi); где Pi - вероятность появления данного сообщения (не больше единицы).
Свойства:
По формуле видим, что количество информации не может быть отрицательным, так как (1/Pi>=1).
Если мы использаем основание 2 для логарифма, то получаемая единица информации называется БИТ, а если использается экспонента "е" -то такая единица информации называется НАТ.
==============================================================

6. Условная энтропия и ее свойства.

Понятие условной энтропии связано с понятием энтропии марковского процесса - иначе говоря изначально рассматривается вероятность появления некоторого сообщения,
с учётом того, что известно о появлении некоторого другого сообщения.
Условная энтропия источника S c Si символами задаётся выражением:

H(S|Si1,Si2....,Sim)=E(s)(P(Si|Si1,Si2......Sim)*log[2](1/P(Si|Si1,Si2......Sim)))

- в данном случае записана формула для энтропии дискретного источника при условии, что мы уже наблюдали последовательность символов (Si1,Si2......Sim).

Если рассматриваются две статичтически зависиые величины, то энтропия объединения двух статистически связанных переменных величин равна сумме энтропии первого ансамбля и энтропии второго относительно первого. ((добавить формулы) см. формулы в лекциях.)

Свойства условной энтропии -
1) Условная энтропия всегда меньше или равна безусловной для той же функции распределения вероятностей, это связано с тем, произведением вероятностей (Si1,Si2......Sim).
2) Если имеется однозначная связь межнду появлением некоторой последовательности сообщений (условием) и появлением некоторого другого сообщения, то ксловная энтропия при налии данного условия становится равной нулю.
3) Если статистические связи между двумя переменными величинами отсутсвуют, то условная энтропия их объединения не будет меньше безусловной энтропии их\
объединения.
================================================================

7. Дифференциальная энтропия и ее свойства.

Дифференциальная энтропия - это энтропия непрерывного источника, значение которой можно получить, зная плотность распределения сигнала непрерывного источника.
Определяется по формуле:

h(U)=S[-&;+&](f(х)*log[2](f(x)dx); где f(x) - плотность распределения непрерывного источника.

Свойства дифференциальной энтропии:
1) Дифференциальная энтропия является относительной мерой неопределенности, (значение дифференциальной энтропии зависит от масштаба случайной величины u')
так как для непрерывного источника с учётом бесконечности его меры неопределённости можно по разному подходить к понятию количества информации.
Наиболее простой из них - замена непрерывного сообщения дискретным с интервалом дискретизации по Котельникову (нет формулы)
2) Дифференциальная энтропия не зависит от конкретной неопределенной величины u, не зависит от изменения этих значений на какое-либо определенную постоянную величину. (следует из формулы.)
3) Соотношение для дифференциальной энтропии объединения статистически зависимых случайных величин соответствует соотношению для дискретных источников.

=============================================================

9. Модели источников дискретных сообщений.

Для построения модели источника дискретных сообщений необходимо знать следующие величины:
1) Объём алфавита знаков.
2) Вероятность появления отдельных знаков при передаче сообщений + учёт зависимости между их появлениями(если таковая присутствует).

На практике обычно встречаются источники "с памятью" - то есть такие источники, в которых формирование очередного знака сообщения не которым образом зависит, от предыдущих последоватльностей символов. Для описания функционирования таких источников используются математические модели - ЦЕПИ МАРКОВА.
Цепь Маркова порядка n характеризует последовательность событий, вероятности которых , зависили от того, какие n событий предшествовали данному событию.
То есть используется понятие условной вероятности.
По отношению к характеристикам зависимостей между символами можно выделить следующие модели:
1) Статистические связи между знаками отстутствуют, в этом случае с появлением любого знака источник не меняет своего состояния и его энтропия - энтропия дискретного источника с учётов только вероятностей появления знаков.
2) Коореляционные(т.е. ститисческие взаимосвязи двух или нескольких случайных величин) связи наблюдаются только между двумя символами - это ПРОСТАЯ ЦЕПЬ МАРКОВА -
вероятность появления последующего символа зависит только от предыдущего. (формула условной вероятности с поправкой на статист. взаимосвязь)
3) Цепь Маркова 3-его порядка. - присутствуют стат. вхаимосвязи между символом и двумя предыдущими.
=============================================================
10. Энтропия дискретного источника. Полная и частная энтропия.

Дискретный источник сообщений это такой источник к который в каждый момент времени принимает одно из своих возможных состояний, причём число этих состояний ограничено.
Его энтропия - это :

G=E[i=1;q](log[r](1/Pi)); где E[i=1;q] - это сумма от 1 до q; log[r] - логарифм по основанию r. (обычно логариф по основанию 2)

%ПОлная и частная энтропии.
Различают два вида энтропии - полную и частную.
% Частная энтропия - это условнаая энтропия источника, прикоторой условие чётко определено - то есть известен факт выбора конкретного предыдущего сообщения (одного из возможных). (добавить формулы)
% ПОлная энтропия - это условная энтропия источника с учётом всех статисчиских взаимосвязей между сообщениями. (добавить формулы)
============================================================

============================================================
13. Избыточность и производительность дискретного источника сообщений.
Мера избыточности показывает, насколько полно (эффективно) используются знаки данного источника
Избыточность источника - следствие физических свойств источника.
Естественная избыточность источника устраняется, а в случае необходимости увеличения помехоустойчивости при передаче сообщений вводится так называемая рациональная избыточность, позволяющая обнаружить и устранить ошибки.

Производительность источника сообщений - количество информации, вырабатываемое источником в единицу времени (скорость создания сообщений, поток входной информации).
===========================================================
14. Производительность дискретного источника сообщений, пути ее повышения.
Наибольшая производительность источника будет достигаться при максимальной энтропии.
============================================================
15. Модели дискретных каналов передачи информации.

Дискретными называются каналы, входные и выходные сигналы которых принимают конечное число мгновенных значений.
Канал без памяти - такой канал, в котором статистическая зависимость между последовательностями символов отсутствует.
Канал c памятью - такой канал,в котором где статистическая зависимость между последовательностями символов присутствует.
============================================================
16. Скорость передачи информации по дискретному каналу. Пропускная способность дискретного канала без помех.

Пропускной способностью дискретного канала называют ту максимальную скорость передачи информации по этому каналу, которую можно достичь при самых совершенных способах передачи и приема.
Пропускная способность канала измеряется - число двоичных единиц информации / сек
Для увеличения скорости передачи информации по дискретному каналу без помех последовательность букв сообщения должна быть подвергнута такому преобразованию, при котором различные символы в выходной последовательности кода появлялись бы по возможности равновероятно и отсутствовали бы статистические связи между этими символами.
Расширение объема алфавита => увеличение пропускной способности, но увеличивается сложность технической реализации.
============================================================
17. Эпсилон -производительность непрерывного источника сообщений.

Эпсилон-производительность непрерывного источника сообщений - минимальное количество информации, которое необходимо создать источнику в единицу времени, чтобы любую реализацию Zi(t) можно было воспроизвести с заданной вероятностью v.
============================================================
20. Пропускная способность непрерывного канала передачи информации.
Пропускная способность непрерывного канала связи - максимально возможная скорость передачи информации по непрерывному каналу связи.
(+основные параметры канала и сигнала)
============================================================
21. Согласование физических характеристик сигнала и канала передачи информации.

Основных параметров канала:
1)время, в течение которого он предоставлен пользователям для передачи информации Tк;
2)ширина полосы пропускания канала Fк;
3)допустимое превышение уровня помехи над уровнем сигнала Hк, характеризуется разностью максимально допустимого сигнала в канале. В проводных каналах определяется правильным напряжением и уровнем перекрестных помех. В радиоканале определяется возможностью появления канала на определенном расстоянии от той точки, где осуществляется передача.
Vк=Tк*Fк*Hк - объем канала;

Основных параметров сигнала:
1)длительность сигнала Tc;
2)ширина спектра сигнала Fc;
3)превышение сигнала над помехой Hc=log (Pu/Pe), связано с дальностью передачи информации: чем больше Hc, тем меньше вероятность ошибочного приема сигнала.
Vc=Tc*Fc*Hc - объем сигнала.
Для принципиальной возможности неискаженной передачи конкретного сигнала по заданному каналу:
Необходимое условие: Vc Достаточное условие: Tc

Предельное количество информации, которое возможно передать по каналу за заданный промежуток времени: Imax(V, U)=Tk*Fk*log(1+Pu/Pe)
В предельном случае, когда Pu/Pe велико, можно получить значение, близкое к объему канала.

=============================================================
22. Согласование статистических свойств источника сообщений и канала передачи информации.

=============================================================
23. Эффективное кодирование. Теорема Шеннона о кодировании в канале без помех.
Теорема.
При любой производительности источника сообщений, меньшей пропускной способности канала существует способ кодирования, позволяющий передавать по каналу все сообщения, вырабатываемые источником.В то же время - не существует способа кодирования, обеспечивающего передачу сообщения без их неограниченного накопления, если
производительность источника больше пропускной способности канала.

=============================================================
24. Эффективное кодирование. Методы эффективного кодирования.

Учитывая статистические свойства источника сообщений можно минимизировать среднее количество символов для отображения одного знака сообщения.
Методы:
1) Метод Хафменна.
2) Метод Шеннона-Фано.

=============================================================
25. Кодирование информации при передаче по дискретному каналу с помехами.

=============================================================
26. Помехоустойчивое кодирование. Разновидности помехоустойчивых кодов.

Корректирующие коды — коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием помех, а также при её хранении.
Структурированные последовательности делятся на три подкатегории:

Коды обнаружения и исправления ошибок
1)Блоковые коды. (+доп. информация)
2)Линейные коды общего вида — такой код, что множество его кодовых слов образует k-мерное линейное подпространство.
3)Линейные циклические коды -Циклическим кодом является линейный код, обладающий следующим свойством: если v является кодовым словом, то его циклическая перестановка также является кодовым словом. Посравнению с линейными кодами общего вида такие коды легче декодировать.
4)Коды БЧХ
Код Боуза — Чоудхури — Хоквингема
являются подклассом циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния (Хэмминга) кода есть очень сложная задача.
5)Коды CRC - систематические коды для ОБНАРУЖЕНИЯ ошибок.
6)Свёрточные коды
7) Каскадное кодирование - последновательное применения ряда методов кодирования , для объединения их преимуществ.
8) Турбо-код — параллельный каскадный блоковый систематический код, способный исправлять ошибки, возникающие при передаче цифровой информации по каналу связи с шумами.

=============================================================

27. Блоковые коды.
Структурированные последовательности делятся на три подкатегории:

* блочные;
* свёрточные;
* турбокоды.
*Равномерный - блоковый код, если размер блока остается постоянным для всех символов сообщения.
*Разделимый - блоковый код, выходные последовательности формируются таким образом, что роль символов может быть отчетливо разграничена: можно определить какие символы информационные, а какие избыточные.
*Неразделимый - блоковый код, невозможно разделить символы на информационные и проверочные.

При использовании блочных кодов исходные данные делятся на блоки из k бит, которые называют информационными битами, или битами сообщения.
В процессе кодирования каждый k-битовый блок данных преобразуется в больший блок из n бит, который называется кодовым битом, или канальным символом.
К каждому блоку данных кодирующее устройство прибавляет (n - k) бит, которые называются избыточными битами, или контрольными битами. Если n - k = 1, то контрольный бит называется битом чётности, или битом паритета.
Блочные коды обозначаются как (n,k).

============================================================

28. Сверточные коды. Особенности декодирования.

Свёрточный код - это код позволяющий корректировать ошибки, в котором
1) на каждом такте работы кодера k символов входной полубесконечной последовательности преобразуются в n > k символов выходной.

2) в преобразовании также участвуют m предыдущих символов;

3) выполняется свойство линейности (если двум кодируемым последовательностям x и y соответствуют кодовые последовательности X и Y, то кодируемой последовательности a*x+b*y соответствует a*X+b*Y).

Сверточные коды используются для надежной передачи данных: видео, мобильной связи, спутниковой связи. Они используются вместе с кодом Рида Соломона и другими кодами подобного типа. До изобретения турбо-кодов такие конструкции были наиболее действенными и удовлетворяли пределу Шеннона.
«В этом коде последовательность кодовых символов не разделяется на отдельные кодовые комбинации. В поток информационных символов включаются корректирующие символы так, что между каждыми двумя информационными символами помещается один корректирующий. Обозначая информационные символы через ai, а корректирущие через bi получаем такую последовательность символов:
a1b1a2b2a3b3......и т.д.

Особенности декодирования.

Свёрточные коды эффективно работают в канале с белым шумом, но плохо справляются с пакетами ошибок. Более того, если декодер ошибается, на его выходе всегда возникает пакет ошибок.

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

Принятие решений о том, что принятая искажённая последовательность соответствует переданной, основывается на принципе максимального правдоподобия.
Улучшением декодера максимального правдоподобия являются декодеры, построенные по алгоритму декодирования Витерби.
(добавить информацию)

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