1. Понятие системы. Признаки системности

Система – это нечто, обладающее системностью.
Признаки системности:

• Структурированность: возможность разделить систему на составные части
• Взаимосвязанность составных частей
• Подчинённость организации всей системы одной цели

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

• Система целостна и обособленна
• Внешняя среда воздействует на систему (U – входы, причины)
• Система воздействует на внешнюю среду (Y – выходы, следствия)
• Выходы зависят от входов        Y = F(U)        

Состояния – некоторые внутренние объекты системы, хранящие в себе всю предысторию о входах.
Введём множества входов, выходов и состояний: U, Y, X
Т – упорядоченное множество последовательности протекающих событий
 - отображение выхода. Связь между состоянием и выходом      Х * Т = У      y(t) = (x(t);t)
 - переходное отображение. Связь между  входом и состоянием          
,                       

2. Классификация систем

U – множество входов; Y – множество выходов; X – множество состояний; Т – упорядоченное множество последовательности протекающих событий.

1. Дискретные: множество Т дискретно: Т={: k = 1,2,… }
2. Непрерывные:  множество Т непрерывно: Т=R
3. Конечный автомат: множество Т дискретно, а множества U, Y, X имеют конечное число элементов
4. Конечномерные: множества U, Y, X являются конечномерными линейными пространствами
5. Стационарные: переходное отображение инвариантно к сдвигу по времени:
6. Гладкие: переходное отображение является решением ОДУ:     
7. Линейные:  и  являются линейными функциями

Другие способы классификации:

• По характеру объектов (технические, биологические, оциальные)
• По виду математического аппарата
• Системы могут быть открытыми (обмениваются с окружающей средой) и закрытыми
• По величине: малые, большие (104 – 107 элементов), ультрабольшие (>107 элементов)
• По сложности. Сложность определяется связями между элементами: 2n(n-1) – кол-во связей

3 . Аксиомы теории систем

Аксиома согласованности: За нулевой промежуток времени система не может перейти в другое состояние                              x() = x(),    =                        x(t)=((t,t), x(t), u(t,t))
Аксиома детерменизма: Состояние системы в момент времени  однозначно определяется состоянием системы в момент времени  и входами, поступившими за промежуток времени от  до  ;     
Аксиома причинности: Одна и та же  причина вызывает одно и то же следствие:         y(t1) = y(t2), если

        

4. Основные понятия теории систем

• Система есть множество входов, множество выходов, множество состояний, связанных оператором переходов (переходным отображением) и оператором выходов (функцией наблюдения).

Т - время U - входы, Y - выходы, X - состояния, ??- оператор переходов, ??- оператор выходов.

2. Система есть нечто целое .
3. Система есть организованное мн-во . ORG - оператор организации; М - множество.
4. Система – это мн-во вещей, св-в и отношений . m - вещи, n – св-ва, r - отношения.
5. Система есть мн-во эл-тов, образующих структуру и обеспечивающих опред. поведение в условиях окружающей среды..???- элементы, SТ - структура, ВЕ - поведение, Е - среда.
6. Это опред-е для биологических и иных саморазвивающихся систем и учитывает генетическое (родовое) начало GN, усл-я сущ-я КD, обменные явл-я МВ, развитие ЕV, функ-ние FС и воспроизведение RР:    .
7. Для организационных систем удобно в определении системы учитывать следующее: , где РL - цели и планы, RO – внешн. ресурсы, RJ – внутр. ресурсы, ЕХ - исполнители, PR - процесс, DТ - помехи, SV - контроль, RD – упр-е, ЕF - эффект.

Элемент – это неотделимая часть системы.
Подсистема – система, являющаяся частью другой системы.
Надсистема – более крупная система, частью которой является рассматриваемая система.
Эмерджентность – цели (ф-ции) комп-ов сист. не всегда совп-т с целями системы
Структура – это совокупность элементов и наиболее существенных связей между ними.
Типы структуры по Богданову:

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

Связь – это существующие взаимоотношения между элементами
Положительная обратная связь: при увеличении выходного сигнала механизм обратной связи срабатывает так, что выходной сигнал продолжает увеличиваться.
Отрицательная обратная связь состоит в том, что выходной сигнал начинает уменьшаться.
Жесткая обратная связь: поправка, подав-я на вход ч-з канал обр. связи, пропорц-на вых-му сигналу.
Гибкаяобратная связь поправка пропорциональна производной выходного сигнала.
Состояние – это моментальная характеристика системы.
Внешняя среда – это множество объектов не входящих в систему, но оказывает воздействие на неё.
Модель – это описание системы, отображающее определенную группу ее свойств.
Равновесие – это способность системы в отсутствии внешнего воздействия сохранять своё состояние.
Устойчивость – это спос-ть системы возвращаться в сост. равновесия при снятии внешних воздействий.
Развитие – повышение уровня системы.  - нулевой уровень организации
Цель – это мыслимый и желательный результат сознательной деятельности.
Вводятся ?- коэфф. целостности (т.е. степень интегрир-ти Эл-тов в систему) и ?- коэфф. использования элементов (т.е. степень самостоятельности элементов). Считается, что при нулевой организованности =0, =1, с ростом организованности  ?растет до 1 в пределе,  ?снижается до 0 в пределе.

5. Основные проблемы теории систем

Идентификация – описание связей между входами, выходами и состояниями. Т. е. нахождение ф-ций наблюдения h и переходного отображения s.
Прогнозирование – предсказание выхода Y по входу U
Управление – определение U для известного значения Х
Диагностирование – определение состояния Х по известным входу u и выходу У
Распознавание – определение U по известному выходу У

6. Качественные методы описания систем

Кач-ые методы сист. ан. Прим-ся, когда отс-ют опис-я закономерностей систем в виде аналитич. завис-тей.
Метод типа мозговой атаки (КГИ). Нацелен на открытие новых идей и достижения согласия группы людей на основе интуитивного мышления. Обычно соблюдаются след-е правила:

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

Методы типа сценариев. Сценарист или группа сц-тов сост-ют письменное опис-е системы, прогноз её развития с указанием нек-х хронологий. (послания президента, предвыборные программы…)
Методы экспертных оценок. Применяя этот метод считают, что мнение группы экспертов надежнее, чем мнение отдельного эксперта. Для количественной оценки степени согласованности мнений экспертов применяется коэффициент конкордации ,  , где m – кол-во эксп-в, n – кол-во измер-ых объектов.  W=0 - полная противоположность, а W= 1 - полное совпад-е ранжировок. Практически достоверность считается хорошей, если W= 0,7...0,8.
Метод «Дельфи». Суть - полный отказ от коллективных обсуждений. В рез-те уменьш-ся влияние таких факторов, как присоед-е к мнению наиболее авторитетного специалиста, нежелание отказаться от публично выраженного мнения, следование за мнением большинства. Прямые дебаты заменены программой последовательных индивидуальных опросов. Ответы экспертов обобщаются и вместе с новой доп. инф-ей поступают в распоряжение экспертов, после чего они уточняют свои первоначальные ответы. Такая процедура повторяется неск-ко раз до достижения приемлемой сходимости совок-ти высказанных мнений.
Методы типа дерева целей. Исп-е иерархической структуры, полученной путём разделения общей цели на подцели, а их, в свою очередь, на боле детальные составляющие — новые подцели, функции и т. д.
Морфологические методы. Основная идея - систематически находить все «мыслимые» варианты решения проблемы или реализации системы путем комбинирования выделенных элементов или их признаков. В систематизированном виде морфологический подход был разработан и применен впервые швейцарским астрономом Ф. Цвикки. Цвикки предложил три метода морфологического исследования.
Первый метод — метод систематического покрытия поля (МСПП), основанный на выделении так называемых опорных пунктов знания в любой исследуемой области и использовании для заполнения поля некоторых сформулированных принципов мышления.
Второй — метод отрицания и конструирования (МОК), базирующийся на идее, заключающейся в том, что на пути конструктивного прогресса стоят догмы и компромиссные ограничения, которые есть смысл отрицать, и, следовательно, сформулировав некоторые предложения, полезно заменить их затем на противоположные и использовать при проведении анализа.
Третий — метод морфологического ящика (ММЯ) состоит в определении всех «мыслимых» параметров, от которых может зависеть решение проблемы, и представлении их в виде матриц-строк, а затем в определении в этом морфологическом матрице-ящике всех возможных сочетаний параметров по одному из каждой строки. Полученные таким образом варианты могут затем подвергаться оценке и анализу с целью выбора наилучшего.
Методика системного анализа. Методики, реализующие принципы системного анализа в конкретных условиях, направлены на то, чтобы формализовать процесс исследования системы, процесс постановки и решения проблемы. Методика системного анализа разрабатывается и применяется в тех случаях, когда у исследователя нет достаточных сведений о системе, которые позволили бы выбрать адекватный метод формализованного представления системы. Общим для всех методик сис. ан-за явл-ся формирование вариантов представления системы (процесса решения задачи), выбор наилучшего варианта, корректировка. Положив в основу методики системного анализа эти три этапа, их затем можно разделить на подэтапы.

7. Количественные методы описания систем

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

• Символич-й (лингвистич-й): исп-ся инструм-ты форм-й лингвистики: предикаты, термы, функторы.
• Теоретико-множественный. Основывается на аппарате булевой алгебры.
• Топологический. Если на элементах рассматриваемых множеств определены некоторые пространственные структуры, то в этом случае приходим к данному подходу.
• Логико-математический. Исп-ся, когда можно представить систему в виде простейшей структуры.
• Теоретико-информационный. Всякая система представляется в виде кодирующего устройства.
• Кибернетический. В нём система представляется в виде совокупности управляемого объекта и управляющего субъекта. Весь процесс функционирования представляется в виде процесса управления.
• Эвристический. Описание системы – имитация или моделирование человеческой деятельности.

8. Теоретико-множественное описание систем

Постулаты:

• Система функц-ет во времени; в каждый момент времени сист. м. нах-ся в одном из возм-х сост-й
• На вход системы могут поступать входные сигналы
• Система способна выдавать выходные сигналы
• Состояние системы в данный момент времени определяется предыдущими состояниями и входными сигналами, поступившими в данный момент времени и ранее
• Выходной сигнал в данный момент времени определяется состояниями системы, относящимися к данному и предшествующим моментам времени.

Последействие – тенденции, определяющие поведение системы в будущем, зависят не только от того, в каком состоянии находится система в настоящий момент времени, но и в той или иной степени от ее поведения в предыдущие моменты времени.
Принцип физической реализуемости: система не реагирует в данный момент времени на «будущие» факторы и воздействия внешней среды.
Для описания систем ее подсистемы (или элементы) перечисляются с помощью некоторых множеств Vi и устанавливается характер связей между ними. , Vi – i-тая компонента декартова произведения  называемая объектом системы S, I- множество индексов. Или иначе:
Абстрактно-алгебраические модели описывают связи как семейство отношений (унарных, бинарных ... n-арных)
Под отношением, введенным на множестве А, понимается подмножество декартового произведения конечной степени  данного множества A, т.е. подмножество кортежей  из n элементов множества A. Подмножество  называется n-местным или n-арным отношением в множестве A. Число n называется рангом или типом отношения R. Множество всех n-арных отношений в множестве A относительно операций  и  является булевой алгеброй.
Функциональные модели определят связи как множество отображений.
Если множество индексов  конечно, то разобьем его два подмножества  и  В общем случае пересечение этих подмножеств может быть не пусто  и . Множество  назовем причинами, а множество  назовем следствиями. Тогда система . Система  называется функциональной, если она представляется в виде отображения .
Временные модели в качестве одного из объектов системы  вводят множество моментов времени .
Если элементы одного из объектов системы есть функции, например , то этот объект называют функциональным. В случае, когда области определения всех функций для данного объекта V одинаковы, т.е. каждая функция отображает  в , , то  называется индексирующим множеством для n. Если индексирующее множество линейно-упорядочено, то его называют множеством моментов времени. Функции, определенные на множестве моментов времени, принято называть (абстрактными) функциями времени. Объект, элементами которого являются временные функции, называют временным объектом, а системы определенные на временных объектах – временными системами.

9. Кибернетический подход к описанию систем

Кибернетический подход к описанию систем состоит в том, что всякое целенаправленное поведение рассматривается как управление. Управление — в кибернетическом смысле — это обобщение приемов и методов, накопленных разными науками об управлении искусственными объектами и живыми организмами. Язык управления — это использование понятий «объект», «среда», «обратная связь», «алгоритм» и т.д. Основы современной кибернетики заложил Н.Винер.
В данном случае субъект ощущает на себе воздействие среды Q и объекта Y. Если состояние среды Q он изменить не может, то состоянием объекта Y он может управлять с помощью специально организованного воздействия U.
Состояние объекта  влияет на состояние потребностей субъекта. Потребности субъекта , где  – состояние i-й потребности субъекта, которая выражается неотрицательным числом, характеризующим насущность, актуальность этой потребности. Свое поведение субъект строит так, чтобы минимизировать насущность своих потребностей, т.е. решает задачу многокритериальной оптимизации: , где R – ресурсы субъекта. Допустим - оптимальное поведение субъекта. Способ  позволяющий определить  называется алгоритмом управления: .
Структурная схема системы управления
Эта схема иллюстрирует процесс управления, где Dq и Dy — датчики, измеряющие состояние среды и объекта соответственно. Результаты измерений Q'=Dq(Q) и Y'=Dy(Y) образуют исходную информацию {Q', Y'} для Устройства Управления, которое на этой основе вырабатывает команду управления и, являющуюся лишь информацией о том, в какое положение должны быть приведены управляемые входы объекта.
Процесс управления — это информационный процесс, заключающийся в сборе информации о ходе процесса, передаче ее в пункты накопления и переработки, анализе поступающей, накопленной и справочной информации, принятии решения на основе выполненного анализа, выработке соответствующего управляющего воздействия и доведении его до объекта управления.
Система управления — совокупность взаимодействующих между собой объекта управления и органа управления, деятельность которых направлена заданной цели управления.
В СУ решаются четыре основные задачи управления:

1. Стабилизация. Задачами стабилизации системы являются задачи поддержания ее выходных величин вблизи некоторых неизменных заданных значений, несмотря на действие помех. Например, стабилизация напряжения и частоты тока в сети вне зависимости от изменения потребления энергии.
2. Выполнение программы. Задача выполнения программы возникает в случаях, когда заданные значения управляемых величин изменяются во времени заранее известным образом.

• Слежение
• Оптимизация

10. Понятие агрегата в теории систем

Пусть T – фиксированное подмножество действительных чисел (множество рассматриваемых моментов времени), Z,U,Y,X – множества любой природы. Элементы указанных множеств: – момент времени; - входной сигнал;  - управляющий сигнал; – выходной сигнал;  - состояние. Состояния, входные, управляющие и выходные сигналы, рассматриваемые как функции времени, обозначим x(t), u(t), z(t) и y(t).
Агрегат - объект <T,U,Z,Y,X,H,G>, где H,G – операторы. Операторы переходов и выходов H и G реализуют функции x(t) и y(t) и представляют собой обобщение переходного отображения  и функции наблюдения.
Предположение 1. Будем предполагать, что за конечный интервал времени в агрегат поступает конечное число входных и управляющих сигналов и вырабатывается конечное число выходных сигналов.
Операторы переходов. Наряду с состоянием x(t) будем рассматривать также точки x(t+0). Договоримся считать, что для любого t1>t момент . Аналогично: x(t-0) означает, что  Вид оператора H зависит от того, содержит ли рассматриваемый интервал времени моменты т.н. особых состояний агрегата или не содержит.
Особые состояния - состояния агрегата в момент получения входного либо управляющего сигналов или выдачи выходного сигнала. Все остальные состояния агрегата будем называть неособыми.
Предположение 2. Из особых состояний агрегат может переходить в новое состояние скачком.
Пусть x(t*) – некоторое особое состояние агрегата, а – последний управляющий сигнал . Примем следующие обозначения для операторов, являющихся частными видами оператора H и определяющих состояние агрегата в момент t*+0. Если t* - момент поступления входного сигнала u, то
Аналогично, если t* - момент поступления управляющего сигнала z, то
При одновременном поступлении u и z
Если t* - момент выдачи выходного сигнала y, то
В интервале между особыми состояниями, значение x(t) определяется при помощи операторов Q, вид которых в общем случае зависит от особого состояния, являющегося для данного интервала времени начальным состоянием:  Здесь t* - момент особого сост-я, явл-ся исходным для данного интервала времени. То есть H является общим обозначением операторов Q,V’,V’’,V и W.
Оператор выходов. Во множестве X состояний x(t) агрегата выделим класс подмножеств {Xy} (подмножества состояний, влекущих за собой необходимость выдачи выходного сигнала), обладающих следующими свойствами. Выходной сигнал y выдается в момент t’ в двух случаях, когда:
1) x(t?)IXy; x(t?-0)IXy                                 2) x(t?+0)IXy, но x(t’)IXy.
Тогда, оператор G можно представить в виде совокупности двух операторов: функциональный оператор G?, вырабатывающего выходной сигнал y=G?[x(t?),zs] и логический оператор G’’, проверяющего для каждого t принадлежность x(t) к одному из подмножеств Xy. Заметим, что в общем случае, оператор G?  является случайным оператором. Это значит, что данным t, x(t), z ставится в соответствие не одно определенное значение выходного сигнала, а некоторое множество значений y с соответствующим распределением вероятностей, задаваемых оператором G?.
Процесс функционирования агрегата. Агрегат функционирует следующим образом. В начальный момент времени t0 заданы начальное состояние агрегата x0 и начальное значение управляющего сигнала z0.
Пусть t1 и t2 – моменты поступления первого u1 и второго u2 входных сигналов, t1 – момент поступления первого управляющего сигнала z1 и, для определенности t1<t1<t2, t' – момент выдачи первого выходного сигнала (пусть t’<t1).

11. Кусочно-линейные агрегаты

Рассмотрим некоторое конечное или счетное множество I. Пусть I={0,1,2,…}. I – мн-во осн. Сост., а Эл-ты nII – осн. сост-я. Каждому осн. сост-ю nI I соотв-ет нек. целое неотрицательное число ||n|| - ранг осн. сост-я (размерность вектора n-го состояния). Кроме того, каждому nII соотв-ет выпуклый многогранник X(n) (мн-во допустимых значений для состояния n) в евклидовом пространстве размерности ||n||. X = EX(n), т.е. пространство состояний X можно представить состоящим из всевозможных пар вида , где nII, а x(n) - вектор размерности ||n||, приним-щий значения из многогранника X(n). Вектор x(n)-вектор координат. Если ||n||=0 для нек. nII, то это означает, что в данном состоянии n координаты не определяются.
Процесс функционирования КЛА
Опишем процесс изменения внутренних состояний во времени, предпологая отсутствие поступления u. Пусть в момент времени t0 агрегат находится в состоянии x(t0)=(n,x(n)(0)),где x(n)(0) - внутренняя точка многогранника X(n). Тогда при t>t0 точка x(n)(t) перемещается внутри многогранника X(n) до тех пор, пока не достигнет его границы. Пусть это произойдет в момент t1, который назовем «особым». Тогда при t0<t?t1 «движение» агрегата описывается следующими законами: n(t)=n=const данному значению n соответствует вектор a(n) (скорость изменения координат) размерности ||n||
 
Значение особого момента t1 определяется траекторией x(t) может быть найдено из соотношения

Предположим, что X(n) содержит m граней. Эти грани могут быть заданы линейными уравнениями:
, где xi (n) – компоненты вектора x(n), i=1.. ||n||.

Обозначим   
Пусть t=min{tj;tj>0}, Тогда  t1=t0+t. То есть t – это время, за которое агрегат может достичь ближайшей грани многогранника и прийти к смене состояния, а t1 – ближайший особый момент времени.
В момент t1 состояние кусочно-линейного агрегата изменяется скачкообразно. Значение x(t1+0) является случайным. В момент t1 м. выдаваться выходной сигнал y (см. оператор G). Содержание y зависит от состояния x(t1). Подмножество Xy, введенное в общем определении агрегата, в данном случае совпадает . Множество Y имеет структуру, аналогичную X, т.е. выходные сигналы y представляются y=(l,y(l)), где l-элемент некоторого не более чем счетного множества, y(l) – вектор, принимающий значения из евклидова пространства размером, зависящим от l.
Для КЛА множество U структурно аналогично множествам X и Y, т.е. u=(m, u(m)), где m-элемент конечного или счетного множества, а u(m)- действительный вектор, размерность которого зависит от m. Следующее описание поведения КЛА можно рассматривать как раскрытие действия оператора V’.
Пусть в момент t состояние агрегата x(t)=(n,x(n)) и в этот момент поступает входной сигнал u=(m,u(m)). При этом сост. агрегата меняется скачкообразно. Значение x(t+0) является случайным, задаваемым распределением P2, которое зависит от x(t) и u. Рассм-ый момент может выдаваться выходной сигнал, содержание и необходимость выдачи которого зависит не только от состояния x(t) (и, быть может, x(t+0)), но и от содержания поступившего входного сигнала u.
В виде КЛА могут быть формализованы процессы передачи и обмена данными в сетях связи, системы массового обслуживания, процессы движения на дорогах, дискретные производственные процессы, и т.д.

12. Понятие марковской цепи

Функционирование многих объектов представляет собой последовательность переходов их из одного состояния в другое (ЭВМ, каналы передачи информации…).
Система называется системой с дискретными состояниями, если множество ее состояний конечно, а переходы из одного состояния в другое осуществляются скачком.
Последовательность состояний такой системы называется цепью
Простейшей характеристикой случайного процесса, являющегося цепью, служит набор вероятностей состояний p1(t), p2(t),…, pn(t), где pi(t) – вероятность того, что в момент t система находится в состоянии i. p1(t)+p2(t)+…+ pn(t)=1
Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени t0 вероятность любого состояния системы в будущем (при t > t0) зависит только от ее состояния в настоящем (при t = t0) и не зависит от того, каким образом система пришла в это состояние. Это принцип отсутствия последействия.
Переход системы из одного состояния в другое является в общем случае случайным событием. Последовательность смены состояний является потоком событий.
Поток событий является ординарным, если события происходят поодиночке (нет двух одновременных событий). Поток называется стационарным, если его вероятностные характеристики не изменяются во времени. Чаще всего применяются пуассоновские потоки событий, то есть имеющие неизменную интенсивность (плотность) – среднее число событий в единицу времени постоянно. l = const

13. Дискретные марковские цепи

Рассмотрим случайный марковский процесс с дискретными состояниями и дискретным временем. Такой процесс описывает систему S с конечным числом состояний, причем переходы возможны только в фиксированные моменты времени t1, t2,…, tk. Процесс функционирования представим в виде цепи

Случайная последовательность является дискретной марковской цепью, если для каждого шага вероятность перехода из любого состояния Si в любое состояние Sj (i, j = 1, 2, … N) не зависит от того, как система пришла в состояние Si (принцип отсутствия последействия)
Каждому переходу системы из состояния Si в состояние Sj в момент времени tk соответствует переходная вероятность pij (tk). Это условная вероятность pij (tk) = P(Sj(tk) | Si(tk-1)). Очевидно, для каждого номера шага k возможные переходы образуют полную группу событий, т.е.  ,   
Дискретная марковская цепь называется однородной, если переходные вероятности не зависят от номера шага: pij (tk) = pij. Полным описанием однородной марковской цепи могут служить квадратная матрица переходных вероятностей:
и вектор вероятностей всех начальных состояний P(0) = [pi(0)] = [p1(0), p2(0)… pN(0)]
Переходные вероятности, соответствующие невозможным переходам, равны нулю, вероятности, расположенные на главной диагонали, соответствуют тому факту, что система не изменила своего состояния. Для однородной марковской цепи найдем вектор вероятностей всех состояний для любого k-го шага. В соответствии с формулой полной вероятности вероятность i-го состояния на 1-м шаге равна:
,   i = 1..N.  Или в матричной форме: P(1) = P(0)PП….Аналогично, для для k-го шага .                                                                                  Обозначим элемент матрицы , как
Если возможен переход из состояния Si в состояние Sj за k шагов, то pij(k)>0. Если при этом возможен и обратный переход за произвольное число шагов, то состояния Si и Sj называются сообщающимися.
Состояние Si называется возвратным, если вероятность того, что система, выйдя из этого состояния, вернется в него за конечное число шагов хотя бы один раз, равна единице, и невозвратным, если вероятность возврата за конечное число шагов меньше единицы.

14. Эргодические и поглощающие марковские цепи

Сообщающиеся состояния, находящиеся на последней ступени, называются эргодическим подмножеством состояний. В частном случае, эргодическое множество может состоять из одного элемента, который называется поглощающим. Если все эргодические подмножества цепи состоят только из одного поглощающего состояния, такая цепь называется поглощающей.
Из поглощающего состояния нельзя перейти ни в какое другое. В матрице переходных вероятностей поглощающему состоянию соответствует строка, в которой все переходные вероятности pij=0, кроме одной (диагональной) pii=1.
Для определения стационарных вероятностей pi нахождения системы в состоянии Si нужно составить систему N линейных алгебраических уравнений с N неизвестными. причем искомые вероятности удовлетворяют условию нормировки 

Поглощающие марковские цепи характеризуются тем, что эргодическое подмножество состоит из единственного элемента, который и является поглощающим. В установившемся режиме независимо от начального состояния вероятность нахождения поглощающей марковской цепи в поглощающем состоянии близка к единице, а вероятности остальных состояний близки к нулю. Для примера на рисунке p1=p2 =p3=0, p4=1. В связи с этим для исследования интересен только переходный режим.

 15. Непрерывные марковские цепи. Дифференциальное уравнение Колмогорова

Случайный процесс с непрерывным временем называется непрерывной марковской цепью, если поведение системы после произвольного момента времени t зависит только от состояния в этот момент времени и не зависит от истории процесса, предшествующей моменту t. (принцип отсутствия последействия).
Пусть система в момент времени t находится в состоянии Si. Рассмотрим элементарный промежуток времени ?t, примыкающий к моменту времени t. Вероятность перехода из состояния Si в Sj за промежуток ?t обозначим pij(?t).
Назовем плотностью вероятности перехода величину ?ij

То есть при малых Dt вероятность перехода pij(Dt) » lij(t) Dt.
Если все плотности вероятности перехода не зависят от t, то такой марковский процесс называется однородным: lij(t) = lij = const (и неоднородным – в противном случае).
Пусть известны плотности вероятностей переходов lij для всех пар состояний Si и Sj. Определим вероятности состояний системы pi(t). Для момента времени t+Dt справедливо соотношение:

Из свойства матрицы переходных вероятностей (сумма вероятностей по строке  = 1) следует:

Подставив это в предыдущее выражение, получим:

Разделим обе части равенства на Dt и устремим его к нулю:

Получили систему дифференциальных уравнений А.Н.Колмогорова

Интегрирование этой системы по времени позволит вычислить функции pi(t).
 

16. Основные понятия теории информации

Информация – свойство материи, состоящее в том, что в результате взаимодействия объектов между их состояниями устанавливается определенное соответствие.
Сообщение – совокупность символов конечного алфавита, являющаяся формой выражения информации.
Передача информации – процесс перемещения сообщения от источника к приемнику посредством вещества или энергии.
Сигнал – материальный носитель информации, обладающий переменными параметрами (звук, свет, радио сигналы, напряжение, угловое или линейное перемещение и т.д.). Сигнал называется непрерывным (или аналоговым), если его параметр может принимать любое значение в пределах некоторого интервала. Сигнал называется дискретным, если его параметр может принимать конечное число значений в пределах некоторого интервала.
Символ – это элемент некоторого конечного множества отличных друг от друга сущностей.
Алфавитом называется набор символов, в котором установлен порядок их следования,
Верность передачи информации – мера соответствия принятого сообщения переданному.
Переработка информации – выполнение формальных операций над входными величинами, над параметрами сигнала в соответствии с заданным алгоритмом.
Хранение информации – фиксация параметров носителя информации.
Помехоустойчивость – способность системы передачи информации противостоять воздействию помех.
Скорость передачи информации – количество информации, переданное в единицу времени.
Пропускная способность – наибольшая достижимая скорость передачи информации для данной информационной системы.

17. Количественные меры информации

Количество информации – мера неопределённости, устраненной при получении сообщения.
Кол-во инф-ции в сообщении о некотором событии сущ-но зависит от вероятности этого события.
Пусть m – мощность алфавита, n - число символов сообщ-я. Тогда сущ-ет mn разл. сообщений длиной n.
Количественные меры информации

• I=mn
• Мера Хартли:   I=n .log2m

nmin=1        mmin=2           Imin = nmin log mmin = 1*log22 = бит
Мера Хартли не учитывает вероятностный характер сообщения

• Мера К.Шеннона: если символ появляется в сообщении с вероятностью 1, он не несёт информации. В случае равновероятных символов  p=1/m. Количество информации, содержащееся в сообщении из 1-го элемента

Любое сообщение можно представить в виде одного символа соответствующего алфавита. Формулу Шеннона м-но распространить на все сообщения, учитывая, что P - вероятность сообщения.
Допустим, поступил ансамбль из n независимых сообщений: а1, а2,… аn с вер-ми p(a1), p(a2),…, p(an) Совместная вероятность ансамбля P = P(a1, a2,…,an) = P(a1)?*P(a2)*?…*?P(an).
I = - logP= -? Т.о. мера Шеннона обладает свойством аддитивности.

18. Кол-во информации для случая равновероятных символов в сообщении

Пусть m – мощность алфавита, n - число символов сообщ-я. Вероятность каждого символа равна p. Вероятность n символов равна Р = n*p .
По формуле Шеннона
С учетом того, что для равновероятных символов   p=1/m   имеем   I = log m

19. Кол-во информации для случая неравновероятных независимых символов в сообщении

Пусть m – мощность алфавита, n - число символов сообщ-я и каждый i-ый символ встречался niраз. . Вероятность появления i-го символа pi. То есть, статистика сообщения следующая:

Тогда вероятность появления ni раз символа ai будет Pini, а вероятность появления всего сообщения будет . Но вер-ть pi можно определить апостериорно, исходя из частоты, если сообщение длинное: .    Тогда  .   Отсюда  

20. Кол-во информации для случая неравновероятных зависимых символов в сообщении

В реальных условиях отсчеты, образующие сообщения, взаимосвязаны.
1) снимается квантованный по уровню и времени электронный сигнал:
2) количество заглавных букв в тексте связано с количеством точек;
3) количество заголовков пакета связано с количеством контрольных сумм и т.д.
Поэтому Р сообщения надо считать с использованием совместных вероятностей.
Если учитывать взаимосвязь между парами символов (ai, aj), то следует исп-ть совместную вероятность появления пары p(ai, aj)= pij.   
Если учитывать взаимосвязь м-ду 3-мя символами, то

 21. Энтропия и ее свойства

Энтропия – мера неопределенности случайного состояния некоторой системы.
Свойства:

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

      ,

2. Энтропия - величина неотрицательная и ограниченная.

Докажем неотрицательность:
Докажем ограниченность: 

3. Энтропия системы, имеющей m равновероятных состояний, максимальна и равна.

Пусть все символы равновероятны:           

4. Совместная энтропия независимых источников сообщений равна сумме энтропий

Пусть источник А порождает ансамбль Na сообщений (a1, a2,…, aNa), источник B порождает ансамбль Nb сообщений (b1, b2,…, bNb), источники независимы. Общий алфавит источников представляет собой множество пар вида (ai, bj), общая мощность алфавита: Na x Nb.
Совместная энтропия композиции двух источников равна:   
Поскольку A и B независимы, то P(ai,bj) = P(ai) P(bj), a log P(ai,bj) = log P(ai) + log P(bj)

Изменим порядок суммирования

Учитывая, что  и

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

Пусть имеются зависимые источники А и В.             A:   Na = (a1, a2, …,aNa),   B:   Nb = (a1, a2, …,aNb)
Энтропия такой композиции   H(A,B) =
;        

Свойства условной энтропии:

• Условная энтропия величина неотрицательная

H(B|A) >= 0,   H(B|A) = 0,          только если любое сообщение A будет полностью определять сообщение В Н(А|B) = 0  

• Если А и В независимы, то     H(B|A) = H(B)              0 <= H(B|A) <= H(B)

Пример:  В буфере ИС ожидает обработку 6 заданий. На обработку в случайном порядке отправляется 2 задания. Найти энтропию запроса на этот ресурс.
А – посылка на обработку 1-го задания
В – посылка на обработку 2-го задания
…………….

23. Энтропия непрерывных сообщений

Рассмотрим систему, где качественные признаки состояния изменяются непрерывно. Вероятность нахождения системы в состоянии х (т.е. сигнал принимает значение х) характеризуется плотностью вероятности f(x) Разбиваем диапазон возможного изменения сигнала на дискреты размером ?x.
Вероятность нахождения системы в i-й дискрете равна  . Тогда  энтропия системы  
Величина Н* называется приведенной или ифференциальной энтропией. При уменьшении ?х Н стремится к ?. Это естественно, т.к. чем точнее мы хотим задать состояние системы, тем большую степень неопределенности мы должны устранить. (на сколько сантиметров Вася выше Пети? А на сколько миллиметров?). Дифференциальная энтропия не является мерой количества информации, хотя и характеризует степень неопределенности, присущую источнику.

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

Идеальные сообщения, имеющие максимальную энтропию, оптимальны в том смысле, что в них на один символ приходится наибольшее количество информации.
В реальных сообщениях символы всегда коррелированны, вследствие чего количество информации, приходящееся на один символ будет меньше, чем в идеальных. Соотношение реальных и оптимальных сообщений выражается посредством коэффициента сжатия (относительная энтропия) где n0 и np – количество символов оптимального и реального сообщения. Одно и то же количество информации I(s) может содержаться в сообщении, состоящим из np символов с энтропией Нр(s) или из n0 символов с энтропией Н0(s)

25. Избыточность сообщения

Коэффициент избыточности выражается так
       
Он показывает, какая часть реального сообщения является излишней и могла бы не передаваться, если бы сообщение было организовано оптимально.

26. Экономичность источников информации

Энтропию можно увеличивать за счет обеспечения равновероятности символов алфавита, а также за счет увеличения мощности алфавита. Однако увеличение мощности алфавита приводит к сложностям приема-передачи информации (непрерывный сигнал передается и воспринимается с погрешностями), к увеличению избыточности сообщений (в языках программирования ряд команд применяется редко).
Существует теоретический оптимум для мощности алфавита. Пусть имеется источник с алфавитом мощности m. Тот же алфавит можно получить, используя 2 источника с алфавитами m/2 или 3 источника с алфавитами m/3 и т.д. При каком m общая энтропия будет максимальной, если k m = const, где k – количество независимых источников, а m – это мощность алфавита каждого источника? (Под езависимыми источниками можно понимать и независимые сигналы одного источника)
Пусть k m = а. Энтропия композиции независимых источников равна
          
Найдём максимум энтропии, для чего продифференцируем по m:
 ;   loge = logm;   m = e
Оптимальная мощность алфавита – 2.718281828459045, то есть примерно 3

 27. Производительность источников информации

Производительность источника – кол-во инф-ции, порождаемое источником в среднем за 1-цу времени
Пусть Н – энтропия источника, m – мощность алфавита, pi (i=1, 2,…, m) – вероятность появления i-го символа, ?i – длительность генерации i–го символа.
Рассмотрим процесс генерации n символов. В среднем, один символ генерируется за время . На генерацию n символов будет затрачено время Т=nM[?]. Кол-во инф-ции, порожденное источником за это время равно: I = nH. Производительность источника:
Если все символы генерируются за одно и то же время ?, то   
Максимальной производительностью обладает источник с максимальной энтропией  

28. Общая схема передачи информации в линиях связи

Линии связи – совокупность устр-в, обеспечивающих преобр-е первичного сообщения от источника информации в сигналы заданной физической природы, из передачу, приём и представление потребителю.
Источник информации – субъект, порождающий информацию и представляющий её в виде сообщения
Субъект – оперирует первичным алфавитом
Кодер - преобразует сообщение первичного алфавита в сообщение вторичного алфавита
Передатчик – инициирует некоторый нестационарный процесс, обеспечивающий
распространение сигналов в канале связи.
Канал связи – материальная среда, а также физический процесс, посредством которого осуществляется передача физического сигнала.
Любой реальный канал связи подвержен внешним воздействиям, а также в нем могут происходить  внутренние процессы, в результате которых искажаются передаваемые сигналы и, следовательно, связанная с ними информация. Такие воздействия называются шумами (помехами).
Приёмник – устройство воспринимающее сигнал
Декодер – вып-ет обратное преобразование сообщения вторичного алфавита в сообщение первичного алфавита и передаёт его получателю  информации. 

29. Модели сигналов. Методы дискретизации непрерывных сигналов

Для передачи сообщения сигнал должен изменять свои физические параметры во времени.
Модулируется (для непрерывных сигналов) и квантование (для дискретных сигналов) – процесс изменения параметров сигнала под воздействием сообщения.
Модуляция непрерывных сигналов
Непрерывные сигналы могут изменять параметры в любой момент времени x(t)=А sin(?t+?)

• Амплитудная модуляция   Хam(t)=А(t) sin(?t+?),   причем амплитуда часто сама изменяется по гармоническому закону:  А(t)=А0 + Аm sin(?t+?) 
• Частотная модуляция Хчм(t)=А sin(?(t)t+?), причем частота сама изменяется по гармоническому закону: ?(t) = ?0 + ?0 cos ?t, где ?0 называется частотной девиацией
• фазовая модуляция Хфм(t)=А sin(?t+?(t)).  Можно показать, что ?(t)t+??= ?0 t + ?(t) + ?0.

 Т. о., частотная и фазовая модуляция – это два варианта технической реализации одного метода модуляции, называемого угловой модуляцией.
Квантование дискретных сигналов
Дискретные сигналы могут изменять свои параметры лишь в дискретный момент времени

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

,    где   
Аk – элемент дискретного множества возможного уровня сигналов
tk = k ?t

• По времени: ,   

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

30. Теорема Котельникова

Сигнал x(t), имеющий ограниченный спектр, лежащий в диапазоне от 0 до , может быть передан с любой степенью точности с помощью последовательности своих дискретных значений, следующий друг за другом с интервалом 
  - ряд Фурье
максимальная частота  , содержится в аргументическом представлении функции и является границей спектра. Т.о         

31. Пропускная способность дискретного канала связи без помех

Пропускная способность – наибольшая достижимая скорость передачи информации для данной информационной системы.
Пусть M– первичный алфавит, которым оперирует источник информации, а m – вторичный алфавит, используемый при передаче сообщения по каналу связи. Пропускная способность канала связи опред-ся формулой:

V – частота снятия отсчетов (кол-во элементарных сигналов в единицу времени).
V=n/T=1/?, где  ? – средняя длительность элементарного сигнала.
 (бит в секунду)
Для двоичных сигналов m = 2, следовательно
Когда речь идет о дискретизации непрерывных сигналов, стараются, чтобы t соответствовала условию теоремы Котельников, т.е.
  При этом существует т.н. предел Найквиста, определяющий максимальную частоту
непрерывного сигнала, передаваемого по каналу с ограниченной пропускной способностью. Он получается из следующих соображений:
 Величину F называют частотой манипуляции.

32. Скорость передачи информации по дискретному каналу без помех

Если передатчик выдает V элементарных сигналов в единицу времени, а средняя длина кода одного знака первичного алфавита составляет k сигналов вторичного алфавита, то отношение V/k будет выражать число знаков первичного алфавита, ранслируемых передатчиком за единицу времени. Если с каждым из них связано среднее количество информации Н, то можно найти общее количество информации, передаваемой по каналу связи за единицу времени – эта величина называется скоростью передачи.
?, где Н – энтропия источника информации:  
Размерностью J, как и C, является бит/с. Каково соотношение этих характеристик? Выразим V из (1), получим:

Согласно теории Шеннона при любом способе кодирования
, хотя может быть сколь угодно близкой к этому значению. Следовательно, всегда J C, т.е. скорость передачи информации по каналу связи не может превысить его пропускной способности.
Пример 1. Первичный алфавит состоит из трех знаков с вероятностями p1 = 0,2; p2 = 0,7; p3 = 0,1. Для передачи по каналу без помех используются равномерный двоичный код. Частота тактового генератора 500 Гц. Какова пропускная способность канала и скорость передачи?
Решение. Поскольку код двоичный, m = 2; C =V = 500 бит/с. Энтропия источника: H = – 0,2·log20,2 – 0,7·log20,7 – 0,1·log20,1 = 1,16 бит Поскольку код равномерный K H/log22 = 2 (т.е. для кодирования каждого знака первичного алфавита всегда используется 2 бита). Следовательно, получаем:
бит в секунду

 33. Эффективное неравномерное кодирование сообщений. 1-я теорема Шеннона

Теорема Шеннона для каналов без помех
Для дискретных каналов без помех К. Шенноном была доказана следующая  теорема
Если производительность источника Ru = C – ?, где ? – сколь угодно малая величина, то всегда существует способ кодирования, позволяющий передавать по каналу все сообщения источника. Передачу всех сообщений при Ru > C осуществить невозможно.
Как бы ни была велика избыточность источника, все его сообщения могут быть переданы по каналу, если Ru < C.
Для рационального использования пропускной способности канала необходимо применять соответствующие способы кодирования.
Эффективным статистическим кодированием называется кодирование, при котором статистические характеристики источника информации согласуются с характеристиками канала связи. При эффективном кодировании фактическая скорость передачи информации приближается к пропускной способности канала.
Рассмотрим основные принципы оптимального кодирования для двоичного канала без помех. Пусть источник генерирует последовательность символов ai, i=1,m. Вероятность каждого символа P(ai). Кодер преобразует символ ai в двоичную последовательность длиной ni. Средняя длительность кодовой комбинации вычисляется так:: , где ?0 – длительность одного элемента кода.
V/K -среднее число знаков первичного алфавита, транслируемых за единицу времени. Соответственно, величина K/V – это средняя длительность трансляции одного знака первичного алфавита, т.е. ?.
Значит, скорость передачи в канале
. Подставляя выражения для среднейдлительности и энтропии, получим:
В этом выражении числитель определяется исключительно статистическими свойствами источника, а ?0 – свойствами канала связи. Возникает вопрос: можно ли так закодировать сообщение, чтобы скорость передачи достигала своего максимального значения? Максимальная скорость передачи определяется пропускной способностью канала связи. Для двоичного канала:
Чтобы J равнялось С надо чтобы ni = - log P(ai). Этому свойству удовлетворяет, например, код Шеннона-Фано.
Пример 1. Первичный алфавит состоит из трех знаков A, B, C с
вероятностями pA = 0,2; pB = 0,7; pC = 0,1. Для передачи по каналу без помех используются код Шеннона-Фано. Частота тактового генератора 500 Гц. Какова пропускная способность канала и скорость передачи?
Решение. Поскольку код Шеннона-Фано – двоичный, m = 2; C =V = 500 бит/с. Энтропия источника: H = – 0,2·log20,2 – 0,7·log20,7 – 0,1·log20,1 = 1,16 бит Длительность одного бинарного знака ?0=1/V=0.002 c.
Закодируем первичный алфавит кодом Шеннона-Фано:A>10, B>0, C>11, длины кодов будут равны: nA = 2; nB = 1; nC = 2 Следовательно, получаем:
По сравнению с равномерным двоичным кодом скорость передачи возросла на 54% и приблизилась к пропускной способности. Средняя длина кодового слова = 1.3
Пример 2. Можно ли с помощью кодирования еще больше увеличить скорость передачи?
Решение. Первичный алфавит из примера №1 будем кодировать по парам символов (это так называемое укрупнение кодов). Пары символов, их вероятности, коды и длины кодовых последовательностей приведены в таблице:
Средняя длина кодового слова для пары равна 2.42, следовательно, для одного
символа – 1.21. Скорость передачи: 479  21 . 1 002 . 0
16 . 1 J =?= бит в секунду.

34. Теоремы побуквенного бинарного кодирования

Прямая теорема Для алфавита X ={x, p(x)} с энтропией H существует побуквенный
неравномерный префиксный двоичный код со средней длиной кодовых слов K ? H +1.
Обратная теорема Для любого однозначно декодируемого двоичного кода алфавита
X={x, p(x)} с энтропией H средняя длина кодовых слов K удовлетворяет неравенству K ? H.

35. Передача информации по каналу с помехами

H (г)– априорная энтропия передатчика сообщения.
H (v | u) – апостериорная энтропия, которая учитывает утечку информации при передаче из-за разрушения ее помехами. Называется ненадежность канала.
H(v)- энтропия приемника (выхода) канала.
H(u | v)характеризует постороннюю информацию, вносимую помехами.
Называется энтропия шума.
Пусть передатчик сигнала оперирует алфавитом Nu, порождая сигналы ui, а приемник сигнала обладает алфавитом Nv и воспринимает сигналы vi. Тогда

А информация, перемещаемая по каналу связи, определяется так:

Рассмотрим два крайних случая. Первый – абсолютно зашумленный канал, выходной сигнал абсолютно не зависит от входного (обрыв связи). При этом

Второй случай – отсутствие шумов. При этом наблюдается жесткая статистическая связь между входом и выходом P(vj|ui)=1, log P(vj|ui)=0. H(v|u)=0,     I(u,v) = H(v) = H(u).
Скорость передачи информации в канале с помехами определяется аналогично каналу без помех
где ? – средняя длительность передачи одного символа первичного алфавита. Пропускная способность также определяется по аналогии с каналом без помех, с учетом потерь информации из-за помех.

36. Пропускная способность бинарного симметричного канала с помехами типа «инверсия»

Передатчик генерирует сигнал «0» или «1», имеющие разные уровни квантования. Приемное устройство анализирует выход канала в течение промежутка времени, соответствующего длительности элементарного сигнала и вычисляет некоторую скалярную величину µ. Решение принимается сравнением µ с некоторым порогом ?. При µ > ? принимается решение в пользу «1», в противном случае, при µ < ?, решением будет «0».
Пусть на вход канала подаются сигналы двух типов (u1 и u2 – например, импульс и пауза) и они же принимаются на выходе, т.е. {u} = {v}, Nu = Nv. Безошибочный прием сигнала означает, что при посылке u1  принимается v1, а при посылке u2 принимается v2  Пусть, далее, вероятность ошибки передачи для обоих сигналов одинакова и равна p; тогда, вероятность безошибочной передачи равна 1 - p. Т. е. можно записать:
P(v1|u1) = P(v2|u2) = 1 – p, P(v2|u1) = P(v1|u2) = p,
В виде графа такой канал можно представить так:

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

Такой канал называется двоичным симметричным.
Найдем пропускную способность канала. Потребуется вычислить I(u,v) (или I(v,u)) и установить ее максимум как функции p.
Вычислим энтропию сигнала:  H(v) = - P(v1) logP(v1) – P(v2) logP(v2)
и энтропию шума:   H(v|u) = -P(u1) (P(v1|u1) logP(v1|u1) + P(v2|u1) logP(v2|u1)) – 
-  P(u2) (P(v1|u2) logP(v1| u2) + P(v2|u2) logP(v2|u2)).
Подставляя вероятности из матрицы перехода,получим: H(v|u)= - P(u1) ((1-p) log (1-p) + plogp) - P(u2)* *(plogp + (1-p) log (1-p)) =  -(P(u1) + P(u2)) ((1-p) log (1-p) + plogp)) = -(1-p) log (1-p) - plogp)
При заданных вероятностях ошибок энтропия H(v|u) – величина постоянная. Максимум можно искать, варьируя вероятностями P(vi). Известно, что для бинарной системы энтропия будет максимальна, если сигналы равновероятны, и равна при этом 1. H(v) = 1. Значит, пропускная способность будет равна

Максимального значения равного 1/? функция C достигает при p = 0 (отсутствие помех) и при p = 1 –канал полностью инвертирует входные сигналы - это не служит препятствием для однозначной идентификации посланного сигнала по принятому.
Во всех остальных ситуациях (при 0 < p < 1) C< 1/?. При p = 0,5
пропускная способность становится равной 0. ( 0,5 означает, что независимо от того, какой сигнал был послан, на приемном конце с равной вероятностью может появиться любой из двух допустимых сигналов. Ясно, что передача в таких условиях оказывается
невозможной.
Поскольку канал двоичный, 1/? = 1/?0 = C0 (это пропускная способность двоичного канала без помех). Произведя соответствующую замену, получим: 
Выражение в скобках не превышает 1, следовательно, справедливо соотношение:
С C0, т.е. можно считать доказанным, что наличие помех снижает пропускную способность (и даже может сделать ее равной 0).
Пример. Наск-ко снижается проп-я спос-ть канала, если ср. частота появления ошибки при передаче сообщения в двоичном симметричном канале составляет 1 ошибочный сигнал на 100 переданных?
Решение. Очевидно, вероятность появления ошибки передачи p = 0,01; Следовательно, получаем:

т.е. пропускная способность канала снизилась приблизительно на 8%.

37. Пропускная способность бинарного симметричного канала с помехами типа «стирание»

Рассмотренную выше систему связи можно усовершенствовать, введя «защитный интервал» или «зону стирания». При µ > ? +? решение принимается в пользу 1, а при µ < ? - ? принимаются решение в пользу 0. При ? –? < µ < ? +? символ искажается настолько, что становится «неузнаваемым». Получаем модель Б.С.К.С. Это небольшое изменение заметно повышает эффективность системы, поскольку задача исправления стираний проще задачи исправления ошибок. Один и тот же корректирующий код позволяет исправить примерно в 2 раза больше стираний, чем ошибок.
Перейдем к моделированию Б.С.К.С. Рассмотрим двоичный канал (на входе сигналы u1 и u2 с вероятностями появления p(u1) и p(u2), соответственно). На приемном конце канала связи любой из них с вероятностью p может быть интерпретирован как противоположный (см. предыдущий раздел), но, помимо этого, с вероятностью q искажения в канале оказываются такими, что принятый знак не идентифицируется ни с одним из поступающих на вход. В таком случае можно считать, что принят новый сигнал v3, появление которого можно интерпретировать как пропажу (стирание) входного сигнала – по этой причине канал назван двоичным симметричным со стиранием. Тогда


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

Расчет условной энтропии шума дает: H(v|u) = -P(u1) (P(v1|u1) log P(v1|u1) + P(v2|u1) log P(v2|u1) + +P(v3|u1) log P(v3|u1)) – P(u2) (P(v1|u2) log P(v1|u2) + P(v2|u2) log P(v2|u2) + P(v3|u2) log P(v3|u2)).
Подставляя вероятности из матрицы перехода, получим:
H(v|u) = - P(u1) ((1-p-q) log (1-p-q) + p log p – q log q) - P(u2) (p log p + (1-pq) log (1-p-q) + q log q) = -(P(u1) + P(u2)) ((1-p-q) log (1-p) + p log p + q log q)) = -(1-p-q) log (1-p-q) - p log p – q log q
Таким образом, I(u,v) = H(v) + (1-p-q) log (1-p-q) + p log p + q log q
Поскольку H(v|u) не зависит от значений априорных вероятностей, I(u,v) достигает максимума при таких вероятностях, когда наибольшее значение приобретает энтропия H(v). Для нахождения H(v) необходимо знать вероятности всех сигналов, появляющихся на выходе из канала (обозначим эти вероятности qj (j = 1,2,3)).
Вероятность появления v3 (стирания) уже установлена: q3 = q. Для v1 вероятность q1 = p(u1)·(1 – p – q) + p(u2)·p; аналогично для v2 находим q2 = p(u2)·p + p(u2)·(1 – p – q). Тогда

Поскольку q определяется особенностями канала и не зависит от априорных вероятностей сигналов на входе, наибольшим H(v) будет при максимальном значении выражения – q1·log2 q1 – q2·log2 q2,
причем, при любых p(u1) и p(u2) справедливо q1 + q2 = 1 – q (так как ? q = 1)
Можно показать (аналогично доказательству третьего свойства энтропии), что указанное выражение достигает максимума при условии q1 = q2 = 0,5·(1 – q). Тогда
приведя подобные:

Окончательно для пропускной способности двоичного симметричного канала со стиранием имеем:
C = C0((1-q) (1-log(1-q)) + (1-p-q) log(1-p-q) + p log p)
Проанализируем полученный результат. С = С(p,q), причем, C будет уменьшаться при увеличении как p, так и q. Если вероятности p и q отличны от 0, то, как видно из полученного выражения, C < C0. В реальных двоичных каналах со стиранием p < q, т.е. вероятность такого искажения входного сигнала, при котором его невозможно распознать, выше вероятности такого искажения, при котором сигнал становится похожим на второй из используемых сигналов. В тех ситуациях, когда p пренебрежимо мала и единственным искажением оказывается «стирание» сигнала, пропускная способность оказывается равной: C = С0·(1 – q). График этой функции представлен на рис.
 Полученный результат представляется вполне закономерным: при p = 0 из V двоичных сигналов, передаваемых по каналу за единицу времени, в среднем V·q будет «стираться», но при этом остальные V·(1– q) сигналов будут на приемном конце расшифровываться без потерь, и с каждым из них связан ровно 1 бит информации.
Заканчивая рассмотрение характеристик реального дискретного канала передачи информации, мы можем сделать следующие заключения:
* Помехи, существующие в реальном канале связи, приводят к снижению его пропускной способности (по сравнению с аналогичным каналом без помех).
* Пропускная способность реального канала может быть рассчитана по известным априорным и апостериорным вероятностям. Для их определения требуются статистические исследования передачи информации в канале.

38. Вторая теорема Шеннона и ее значение для помехоустойчивого кодирования

Если производительность источника R ? C – ?, где ? – сколь угодно малая положительная величина, то существует способ кодирования, позволяющий передать все сообщения источника со сколь угодно малой вероятностью ошибки.
Если производительность ИС меньше пропускной способности канала, то сообщение от этого источника можно преобразовать так, чтобы передавать их по каналу с помехами с любой степенью точности, т. е. за счет существования избыточности в сообщениях, вводимой специальным образом, можно уменьшить вероятность ошибки до сколь угодно малой величины.
С точки зрения технической реализации эта теорема означает, что существует способ кодирования и декодирования, при котором вероятность ошибочного декодирования может быть сколь угодно малой. Если R > C, то таких способов не существует.
Вторая теорема Шеннона является идеологической основой для существования помехоустойчивого (корректирующего) кодирования в каналах связи.

 39. Пропускная способность непрерывного канала связи

Непрерывным называется канал, который обеспечивает передачу непрерывных сигналов.
Непрерывные сигналы, поступающие в канал связи из передатчика (Пд) описываются некоторой непрерывной функцией времени X(t).
максимальная информация, передаваемая по непрерывному каналу в условиях гауссовых аддитивных помех равна:
Для получения пропускной способности кол-во информации на один отсчет нужно умножить на частоту снятия отсчетов.

Учитывая, что мощность сигналов P пропорциональная дисперсии, получим:
Во избежание потерь информации при дискретизации частоту снятия отсчетов надо выбирать, исходя из теоремы Котельникова, с интервалом     Отсюда ?.
Это формула Шеннона для непрерывного канала с помехами. Для реального гауссовского канала с ограниченной мощностью сигнала пропускная способность оказывается несколько иной, чем по формуле Шеннона. В этом случае С канала может быть рассчитана по формуле:
? – коэффициент, учитывающий ухудшение информационных свойствприменяемого класса сигналов по сравнению с идеальным гауссовским сигналом: 0 до?1. Как показывают расчеты, ? ??0.3 для экспоненциального сигнала. Для импульсных сигналов ? ??0.03. Для идеального гауссовского сигнала ? = 1, и применяется классическая формула Шеннона.
Пропускная способность определяется отношением мощностей сигнала и помех, а также шириной спектра полезного сигнала. Ограничение пропускной способности непрерывного канала связано с тем, что любые используемые для связи сигналы имеют конечную мощность.
C = 0 только при PX = 0. Т.е. непрерывный канал обеспечивает передачу информации даже в том случае, если уровень шумов превышают уровень сигнала – это используется для скрытой передачи.

40. Третья теорема Шеннона. Эпсилон-энтропия

Производительность источника непрерывных сообщений пропорциональна энтропии источника  
Поскольку энтропия источника непрерывных сигналов – бесконечно большая, то и производительность такого источника – бесконечно большая. На практике даже при безошибочной передаче сигнала по каналу связи приемник воспринимает поступивший сигнал с какой-то погрешностью. Принятое сообщение Z(t) и переданное X(t) называются эквивалентными, если различие между ними несущественно в смысле выбранного критерия (обычно это критерий СКО). Вводится понятие отклонения , задается
предельная погрешность ?. Если ?, то реализации считаются эквивалентными.
Эпсилон-энтропией  называется минимальное среднее количество информации, содержащееся в одном отсчете сообщения Z(t) относительно сообщения X(t), при котором они еще эквивалентны.
В соответствии с соотношением  эпсилон-энтропия определяет количество существенной информации, содержащейся в одном отсчете непрерывного сообщения.
Производительность источника определяется как ?  По теоремеКотельникова   (F – полоса пропускания), значит ) R=2F 
Теорема Шеннона для непрерывного канала с помехами (третья теорема)
Если при заданном критерии эквивалентности сообщений  ?производительность этого источника меньше пропускной способности канала, т. е. R < C, то сущ-ет такой способ код-я и декодирования в обобщенном смысле, при котором неточность воспроизведения сообщения сколь угодно близка к ?. При R > C такого способа не сущ-ет.

41. Основные принципы помехоустойчивого кодирования

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

• Использование избыточности. В закодированном сообщении всегда присутствуют дополнительные символы, необходимые для обеспечения помехоустойчивости.
• Принцип усреднения. Проверочные символы зависят от нескольких информационных символов. Т.о. информация, содержащаяся в сообщении распространяется и на избыточные символы.

Мощность алфавита источника – М. При бинарном равномерном кодировании для любого первичного символа алфавита требуется  бит.               .
Пусть М=40. Длина равномерного бинарного кода k>= log2M =6. С помощью 6 бит можно получить 26=64 кодовых комбинаций. Они будут считаться разрешенными, хотя нек. из них и не соотв-ют символам исходного алфавита.
Помехоустойчивость достигается добавлением к k информационным разрядам r проверочных. Т.о. общая длина кодовой комбинации становится  n = k + r.   n – кодовое слово ((n,k)-код).
Sr = 2k – разрешённые входные комбинации
 - все возможные комбинации для кодового слова длиной n
   - запрещённые комбинации.
Появление запрещённой комбинации на выходе канала связи свидетельствует о наличии ошибки. На вход канал подаются только разрешённые комбинации. Если в результате помех одна разрешённая комбинация ошибочно перейдёт в другую, то ошибка не будет обнаружена. Поэтому стоит задача разработки кодов, для которых вероятность перехода из одной разрешённой комбинации в другую разрешённую комбинацию будет сведена к минимуму. 

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

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

Блочные – передаваемые двоичные сообщения формируются в блоки…..
Непрерывные – сообщ. представл. собой послед-ть бит, не разделённую на блоки (свёрточные, цепные)
Разделимые – можно чётко разделить информационные и проверочные биты
Неразделимые – информационные и проверочные биты не разделяются
Систематические (линейные) – проверочные биты явл-ся линейной посл-тью информационных бит
Несистематические – проверочные биты являются или нелинейными информационными битами или же зависимости между информационными и проверочными битами нет.
С постоянным весом – доля проверочных бит в общем кол-ве бит постоянна
С переменным весом - доля проверочных бит в общем кол-ве бит непостоянна
Примеры простейших кодов:

• Код с проверкой на чётность. Относится к блочным линейным (n,n-1) кодам.

Если m = {m1, m2, … ,mk} – входная кодовая комбинация, выходное кодовое сообщение будет иметь вид
U =                                  m = (101)       U = (1010)
Признак отсутствия ошибки – чётное кол-во единиц. Двойная ошибка не будет обнаружена.
Линейные коды замкнуты, т.е. сумма 2-х кодовых комбинаций данного кода тоже является кодовой комбинацией данного кода:         

• Итеративный код.    m = {m1, m2, … ,m9}

Т.о. если произойдёт ошибка в одном из разрядов (например m4), это сразу даст нам нечётность во 2-й строке и 1-ом столбце. Т.е. мы определим координату ошибки (локализуем ошибку).

43. Порождающая и проверочная матрицы блочного кода

Порождающая матрица:
Систематические коды относятся к группе блочных разделимых кодов. Для систематического кода сумма по модулю два двух разрешенных комбинаций также дает разрешенную комбинацию (свойство замкнутости). Все разрешенные комбинации систематического (n,k)-кода можно получить, располагая k-
значными исходными комбинациями. При этом:

• в число исходных комбинаций не должна входить тривиальная (нулевая);
• все исходные комбинации должны быть линейно независимы, т.е. ни одна из них не может быть получена путем суммирования других;
• для обеспечения требуемой корректирующей способности минимальное кодовое расстояние dmin исходных комбинаций должно удовлетворять условиям Хемминга: dmin =  2 * t  + 1,  где t – кратность ошибки

Получение кодовых комбинаций производится с помощью порождающих матриц, состоящих из k строк и n столбцов: 
В канонической форме кода элементы первых k столбцов служат для информационных целей, а оставшихся – для проверочных. Порождающую матрицу G можно представить в виде двух подматриц –
информационной Ik и проверочной P. , где  ,  
Информационную подматрицу берут в виде квадратной единичной матрицы, при этом проверочная подматрица P должна строиться с соблюдением следующих условий:
1) вес (количество единиц) каждой строки подматрицы должен быть не менее dmin-1
2) все строки должны быть различны
3) кодовое расстояние между любыми двумя строками подматрицы должно быть не менее dmin-2
(Пример…)
Проверочная матрица:
Проверочная матрица Н ортогональна любой разрешенной комбинации кода.
Правила построения проверочной матрицы:

• В порождающей матрице G выделяют информационную квадратную подматрицу I и проверочную подматрицу P.
• Проверочную подматрицу транспонируют, получая подматрицу PT.
• Справа к подматрице PT приписывают квадратную единичную матрицу размера r х r.

Получается матрица . Чтобы обнаружить ошибку нужно вычислить синдром ошибки: s = H·u. Если синдром равен нулю, то комбинация передана безошибочно, в противном случае ошибка существует.По виду синдрома можно локализовать, а значит, исправить ошибку. Синдром будет иметь размерность r. Т.  е. каждой ошибке можно сопоставить свой синдром.

44. Характеристики помехоустойчивых кодов

n - значность кода - количество разрядов в каждой кодовой. Символы каждого разряда могут принимать значения 0 или 1.
? – вес - количество единиц в кодовой комбинации.
Например, кодовая комбинация 100101100 имеет значность n = 9 и вес ? = 4.
d - cтепень отличия двух любых кодовых комбинаций (расстояние Хемминга) - число разрядов, в которых комбинации отличаются одна от другой. Для определения кодового расстояния надо просуммировать по модулю 2 две кодовые комбинации и определить вес суммы. (Пример)
При передаче возникают в кодовых комбинациях возникают ошибки типа «инверсия». Если ошибка произошла в одном разряде блока, она называется однократной, при ошибках в двух, трех и т.д. разрядах они называются двукратными, трехкратными и т.д.
e - вектор ошибки. Используют для описания возникающих в канале ошибок. Представл. собой  двоичную последовательность длиной n с единицами в тех позициях, в которых произошли ошибки. Вес вектора ошибки равен кратности ошибки. (Пример…)
Пусть по каналу связи передается кодовое слово U , в рез-те принята возможно ошибочная посл-ть . Если е – вектор ошибок, то = U e , или, что то же самое, e = U, U =   e
Помехоустойчивость кодирования обеспечивается за счет введения избыточности. Это значит, что из n символов кодовой комбинации для передачи информации используется k < n символов.
F - коэффициент избыточности кода –отношение количества проверочных битов к длине кода.
Всего возможных кодовых слов – 2n, из них безошибочными могут быть 2k. Разрешенных комбинаций
Sр = 2k, запрещенных Sf = S – Sр=2n - 2k. Если на приемной стороне установлено, что принятая комбинация относится к разрешенным, то считается, что сообщение прошло без искажений, а если принята запрещенная комбинация, то делается вывод, что произошла ошибка. Однако, если посланная комбинация, претерпев искажения, попала в множество разрешенных комбинаций, такая ошибка обнаружена не будет.
               
Пусть всего Sр разрешенных комбинаций. Каждая из них при передаче может трансформироваться в любую из S возможных комбинаций, т.е. всего имеется S·Sр возможных вариантов передачи. Из них Sр вариантов безошибочной передачи, Sр·(Sр – 1) вариантов ошибочной трансформации в другие разрешенные комбинации и Sр·(S – Sр) вариантов трансформации в запрещенные комбинации. Только передача в запрещенные варианты может быть обнаружена. Доля обнаруживаемых ошибок составляет
Обнаруженную ошибку можно исправить, если для каждой запрещенной комбинации можно указать единственную исходную комбинацию. Т. о., ошибка исправляется в S – Sр случаях, равных количеству запрещенных комбинаций. Доля исправляемых ошибочных комбинаций от числа обнаруживаемых составляет:
Эти две величины характеризуют корректирующую способность кода.
Пусть p – вероятность появления ошибки при передаче отдельного бита кодовой комбинации. Для оценки вероятности возникновения ошибки при передаче кодовой комбинации, состоящей их n бит необходимо принять определенные исходные предположения, которые называются математической моделью ошибок. Будем считать появление ошибки в каждом отдельном знаке кода случайным событием, которое не зависит от того, с ошибками или без были переданы предыдущие биты. Тогда:
1 – p – вероятность безошибочной передачи отдельного бита;
(1 – p)n – вероятность безошибочной передачи цепочки n бит;
Pn = 1 – (1 – p)n – вероятность появления хотя бы одной ошибки в комбинации n бит. При малых p можно воспользоваться соотношением Бернулли; тогда.
 - вер-ть ошибки с заданной кратностью t (формула биноминального распределения)
- вероятность появления ошибки кратности от 1 до t.

 45. Длина и кодовое расстояние блочного кода. Их влияние на корректирующую способность

Связь между корректирующей способностью кода и кодовым расстоянием
Наименьшее расстояние между разрешенными кодовыми комбинациями dmin обеспечивает корректирующие свойства кода.
Пусть необходимо построить код, обнаруживающий все ошибки кратности ? и меньше. Построить такой код – это значит из множества S возможных комбинаций выбрать Sp разрешенных комбинаций так, чтобы любая сумма по модулю 2 с любым вектором ошибок с весом ? ? ? не дала бы в результате никакой другой разрешенной комбинации. Для этого необходимо, чтобы наименьшее кодовое расстояние удовлетворяло условию
Рассмотрим код со значностью n=3.

Все возможные комбинации этого кода:

Матрица кодовых расстояний:

Для того, чтобы код обеспечивал обнаружение однократных ошибок, необходимо
из 8 возможных комбинаций выбрать в качестве разрешенных такие, расстояние
между которыми было бы не менее dmin=2. Например А2 = 001, А3 = 010, А5 = 100, А8 = 111. Любая однократная ошибка переводит разрешенную комбинацию в запрещенную.
Для обнаружения двукратных ошибок наим. кодовое расст-е должно быть dmin=3. А3=010 и А6=101.
Код, исправляющий однократные ошибки:

При dmin=2 подмножества запрещённых комбинаций пересекаются => нельзя однозначно установить, какая комбинация была послана – А2 или А3. Если же dmin= 3, имеется однозначное соответствие принятой и переданной комбинации => при dmin=3 обеспечивается исправление всех однократных ошибок.
В общем случае, для исправление ошибок кратности t минимальное кодовое расстояние должно удовлетворять условию dmin ? 2t + 1.
Связь между корректирующей способностью кода и длиной кода
Обычная последовательность выбора кода следующая:

• исходя из мощности M первичного алфавита, определяется количество информационных разрядов;
• задается возможная кратность ошибок, подлежащих обнаружению и исправлению;
• опред-ся кол-во доп-ых проверочных разрядов, которые вместе с инф-ми определят длину кода n.

М - мощность первичного алфавита М.  Необходимое количество информационных битов k >= log2M.
Пусть необходимо исправить ошибки кратности от 1 до t.
 - число возможных ошибок кратности t в коде длиной n.
- кол-во ошибок кратности от 1 до t
Эти Е ошибок могут проявиться в 2k возможных входных последовательностях. Полное число ошибочных комбинаций, подлежащих исправлению, равно Е•2k. Код длиной n обеспечивает исправление не более 2n - 2k комбинаций. Необходимое условие для возможности исправления ошибок  Е•2k ? 2n - 2k
Отсюда     ;     r = n – k;        ;      ;         
- граница Хемминга: связывает число проверочных бит и значность кода.

46. Кодирование по Хеммингу

В отличие от канонического систематического кода, в коде Хемминга информационные и проверочные биты не разнесены в отдельные подматрицы, а чередуются. При этом биты кодовой комбинации получают номера, начиная с 1, слева направо. Контрольными (проверочными) оказываются биты с номерами 1, 2, 4, 8 и т.д. – все остальные являются информационными. Цель этих перестановок – сделать так, чтобы синдром ошибки непосредственно указывал на локализацию ошибок.
Код Хемминга начинают строить с проверочной матрицы H, т. к. ее вид очевиден: столбцы представляют собой набор синдромов, соответствующих номеру столбца. Затем строят порождающую матрицу G, исходя из того, что матрицы H и G ортогональны: H? GT = 0 и G? HT = 0 .
Построим код Хемминга для (7,4)-кода:

 
- проверочная матрица. В ней на 1-м, 2-м и 4-м местах стоят столбцы единичной матрицы, а на остальных – столбцы, соответствующие информационным разрядам кода.

Выделим подматрицу, соответствующую информационным разрядам и повернем её по часовой стрелке. Получим проверочную подматрицу порождающей матрицы ;  
Поставим столбцы матрицы P на 1, 2 и 4-е место, а остальные столбцы будут столбцами единичной матрицы. Получим порождающую матрицу
(Пример)

47. Циклические коды. Кодирование с помощью порождающего полинома.

При циклическом сдвиге разрешённой  комбинации получается другая разрешённая кодовая комбинация.
 разрешённым комбинациям
Циклические коды обычно им-т полиномиальное представление f(x)=an-1xn-1 + an-2xn-2 +…+ a2x2+a1x + a0
Например, кодовое слово 11010 представляется в виде полинома x4+x3+x
Наибольшая степень х в слагаемом с ненулевым коэффициентом называется степенью полинома. Действия над кодовыми комбинациями сводятся к действиям над полиномами, причем операция сложения производится по модулю 2. Множество таких полиномов и действий над ними образуют поле Галуа порядка 2 (GF(2)).
Циклический сдвиг коэффициентов полинома получается умножением полинома на x с одновременным вычитанием двучлена xn+1. Действительно, пусть f(x)=1•xn-1+an-2xn-2+…+a2x2+a1x+a0.
Тогда f(x)•x – (xn+1) = xn+an-2xn-1+ … +a2x3+a1x2+a0x – xn+1 = an-2xn-1+ … +a2x3+a1x2+a0x +1
Т. о., если в качестве исходного взять некоторый полином g(x), то разрешенные комбинации можно получать посл-но умножая g(x) на х и вычитая (xn+1)
При таком способе построения полином g(x) называется порождающим. Он определяет св-ва кода. Требуют, чтобы порождающий полином g(x) был делителем двучлена (xn+1), тогда любой кодовый полином будет делится на  g(x). Тогда можно будет легко проверить, является ли комбинация разрешенной. Достаточно проверить ее делимость на полином g(x).
Основные свойства циклических кодов:
1. В циклическом (n,k)-коде каждый кодовый полином должен иметь степень не более n-1.
2. Существует полином g(x) степени (n-k), называемый порождающим полиномом кода.
3. Каждый кодовый полином Uu(x) является кратным g(x), т. е. U(x) = m(x)•g(x).
Кодирование с использованием циклических кодов

• U(x) = m(x) •g(x), где m(x) = mk-1xk-1+mk-2xk-2+…+m0,   g(x) – порождающий полином степени (n-k). Полученный таким способом код теряет свойство систематичности.
• Используется процедура деления полиномов и вычисления остатков. Для каждой пары полиномов С(х) и g(x) существует единственная пара полиномов q(x) и , таких, что С(х) = q(x)? g(x).

m(x)?xn-k = q(x)?g(x) ;               .xn-k ? m(x) = q(x)? g(x)    (1)
Т.к. пара g(x),  - единственна, полином  (1) однозначно связан с входным полиномом m(x). Т.о. кодирование всодится к получению полинома
 Т. о. старшие разряды  занимают символы m, а млардшие - .
Т. о., кодовое слово циклического кода состоит из неизменной информационной части m и (n-k) проверочных символов. Проверочные символы являются коэффициентами полинома, т. е. остатком от деления m(x)?xn-k на порождающий полином g(x).
Пример.
 g(x) = x3+x+1, m=(1110);   m (x)= x3+ x2 + x;   m(x) ? xn-k =m(x) ? x3 =( x3+ x2 +x) ? x3 = x6 + x5 +x4.
Разделим x6 + x5 +x4 на порождающий полином g(x). Получим q(x) = x3 + x2;   = х2
Т. о., кодовый полином  будет иметь вид: U(x) = x6 + x5 + x4;        U(x) = (1110100)

48. Циклическое кодирование с помощью сдвиговых схем

Алгоритм кодирования, основанный на делении полиномов, можно реализовать, используя схему деления. Она представляет собой регистр сдвига, в котором цепи обратной связи замкнуты в соответствии c коэффициентами порождающего полинома g(x)

Кодирование в схеме выполняется следующим образом:
k символов информационной последовательности m через переключатель, находящийся в верхнем положении, один за другим передаются в выходной регистр и одновременно с этим записываются в регистр проверочных символов, в котором благодаря наличию цепей обратной связи g0 ... gn-k-1 формируется остаток от деления xn-k?m(x) на g(x) — проверочные символы. Начиная с (k+1)-го такта переключатель переводится в нижнее положение, и из сдвигового регистра выводятся (n-k) проверочных символов (цепь обратной связи при этом разомкнута).
Пример: закодируем сообщение m=(0011). Порождающий полином будет иметь вид g(x) = x3+ x +1.

В этой схеме отсутствуют элементы в цепях, где значения коэффициентов обратной связи gi равны нулю, там же, где коэффициенты передачи gi равны единице, цепь просто замкнута.
Вычисление синдрома и исправление ошибок в циклических кодах
Пусть U(x) и  - полиномы, соответствующие переданному кодовому слову и принятой посл-ти. Разделив  на g(x), получим = q(x)*?g(x)?s(x),         где  q(x) -  частное,  а s(x) - остаток.
Если  является кодовым полиномом, то он делится на g(x) без остатка, т. е. s(x) = 0.
Следовательно, s(x)<>?0 является синдромом принятой последовательности. В общем случае синдром s(x) имеетвид
Схема вычисления синдрома подобна схемам кодирования.

Синдромный многочлен S(x) однозначно связан с многочленом ошибки e(x), т. е. с его пом-ю можно локализовать ошибку в принятой последовательности.
Пусть e(x) - полином вектора ошибки. Тогда полином принятой посл-и = U(x)?e(x).
Учтем, что    и    .
Тогда 
т. е. синдром S(x) есть остаток от деления полинома ошибки e(x) на порождающий полином g(x).
Следовательно, по синдрому S(x) можно однозначно определить e(x) и исправить ошибку.

49. Получение порождающих полиномов

Синдромный полином есть остаток от деления полинома ошибки e(x) на порождающий полином g(x). Для исправления ошибок необходимо выбрать такой порождающий полином, у которого количество различных остатков не меньше числа возможных ошибок. Только в этом случае все ошибки можно локализовать.
Корректирующая способность кода будет тем выше, чем больше различных остатков может быть образовано при делении кодового полинома на порождающий полином. Наибольшее количество остатков обеспечивают т.н. неприводимые полиномы. Неприводимый полином в алгебре полей Галуа – это аналог простых чисел.
Неприводимым называется полином, который делится без остатка только на 1 и сам на себя.
Если неприводимый многочлен имеет степень p, то он дает 2p-1 остатков. Приводимые полиномы той же степени дают меньшее количество разных остатков. Иногда при выборе подходящего неприводимого полинома бывает полезно следующее свойство двучлена xn+1. Если n = 2p-1, то двучлен xn+1 можно разложить на неприводимые полиномы степени не больше p. (Например x15+1= 1 24 x - +1=(x+1)(x2+x+1)(x4+x3+1)(x4+x+1)(x4+x3+x2+x+1).)
Можно сформулировать следующие правила составления порождающих полиномов:
1) порождающий полином должен быть неприводимым;
2) порождающий полином должен быть делителем двучлена xn+1;
3) степень полинома должна быть настолько большой, чтобы количество остатков превышало количество ошибок,которые требуется локализовать;
4) число ненулевых членов полинома не должно быть меньше минимального кодового расстояния.
Пример. Выбрать порождающий полином циклического кода, исправляющего однократные ошибки и позволяющего передать 2000 различных сообщений. Определим необходимое количество информационных разрядов. k?log 2000. k=11.
По правилу Хемминга  для исправления однократных ошибок требуется 4 проверочных разряда, => надо строить (15,11)-код. В (15,11)-коде возможно возникновение 15 одиночных ошибок, =>нужен порождающий полином 4-й степени, т. к. при этом полиноме получаются 24-1=15 различных остатков от деления. Из разложения двучлена x15+1, приведенного выше, выбираем порождающий полином g(x)=(x4+x+1), так как он проще
Примеры неприводимых полиномов 1, 111, 1011, 10011, 100101, 1000011

50. Непрерывные помехоустойчивые коды. Импульсная переходная характеристика.

Импульсная переходная характеристика (ИПХ) – это реакция кодера на воздействие в виде ?-функции. ? = (10000…)
Например, для (8,4)-кода L = 3. Значит, последовательность ? = (10000…) будет кодироваться так: u = (11 00 00 01 00 00 …). Это и будет импульсная переходная характеристика кода. Обозначается: Н(8,4) = (11 00 00 01). Для кодирования надо просуммировать с соответствующим сдвигом реакцию кодера на каждый входной разряд.
Например, пусть входная последовательность m = (1101000…). Каждая единица входной последовательности вызывается реакцию в виде ИПХ.
Просуммируем реакции:
11 00 00 01
A 11 00 00 01
A    11 00 00 01    
u=(11 11 00 10 01 00 01 00 …)
При декодировании полученная последовательность разделяется на информационную и проверочную. Вычисляется ИПХ информационной последовательности и получается контрольная последовательность. Если контрольная и проверочная последовательности совпадают, значит ошибки нет.
Для нашего примера из полученной последовательности ы=(11 11 00 10 01 00
01 00 …) выделяется информационная в=(1101000 …) и вычисляется контрольная c=(11 11 00 10 01 00 01 00 …). Сравниваем c с полученной ы и убеждаемся, что ошибок нет.
Если в процессе передачи произошла ошибка в пределах L кадров, ее можно локализовать, вычислив синдромную последовательность. Для каждой ИПХ имеется свой синдромный кадр длиной L+1. Позиция, в которой синдромный кадр совпадает с синдромной последовательностью, является позицией ошибки. Допустим, принята последовательность, содержащая ошибки:
ы=(11 01 00 10 01 10 01 00 00…).
Выделяем из нее информационную последовательность: в=(100101000…).
Строим контрольную последовательность c=(11 00 00 10 00 11 01 00 01…)  Вычисляем синдромную последовательность, сравнивая проверочные символы принятой последовательности ы и контрольной последовательности c.
S=(010011001…). Синдромный кадр для данного кода равен S0=(1001) – это проверочные символы ИПХ. Сдвигая синдромный кадр вдоль синдромной последовательности, обнаруживаем, что они совпадают во второй и шестой
позиции. Следовательно, ошибки локализованы 2-м и 6-м разрядом.

51. Неалгебраические способы противодействия помехам.

Существует ряд методов противодействия помехам, использующих статистические характеристики сообщений, а также учитывающие последствия неверного декодирования. Пусть по каналу связи передается некоторое сообщение U из алфавита A, а принимается кодовая последовательность U, содержащая искажения вследствие помех, то есть по отдельным символам приемник мог принять неправильные решения.
Пусть Ul ? l-е кодовое слово используемого кода; Uli ? i-й символ этого кодового слова; U - принятый сигнал, содержащий одно из кодовых слов и помеху.
Известны априорные вероятности передачи кодовых слов – P(Ul) Оптимальный декодер должен учитывать всю имеющуюся информацию об используемом коде, канале связи и помехах, действующих в этом канале, и обеспечивать максимальную вероятность правильных ответов о том, какие кодовые слова были переданы по каналу связи. Такой критерий оптимальности - называется критерием максимума апостериорной вероятности.
Декодер максимума апостериорной вероятности должен выбирать в качестве решения кодовое слово U* = Uj, которое максимизирует условную вероятность P(Uj|U) — вероятность того, что была передана последовательность Uj, если принята данная реализация сигнала U. U*=arg max{P(Uj|U);UjIA}
Поскольку P(Uj |U)? P(U) = P(U|Uj )? P(Uj), то по формуле Байеса P(Uj |U) = P(U|Uj )? P(Uj)/P(U).
P(U) – это полная безусловная вероятность появления сообщения U. P(U)= ?P(U|Uj )? P(Uj).
Пример. Источник генерирует 3 кодовых слова: u1=(0 1 0), u2=(0 0 1), u3=(1 1 1) с вероятностями p1=0.4, p2=0.4, p3=0.2. Принята комбинация u=(1 1 0). Зная, что вероятность искажения одного бита ри=0.1, определить оптимальное по критерию максимума апостериорной вероятности переданное слово.
Оптимальное решение – то, которое максимизирует величину P(ui|u;i=1,2,3).
По формуле Байеса P(ui|u) = P(u|ui)·P(ui)/ ?P(u|ui ) ?P(ui).
P(u|u1)=0.1·0.9·0.9=0.081 (вероятность того, что исказится только первый бит)
P(u|u2)=0.1·0.1·0.1=0.001 (вероятность того, что исказится первый, второй и третий биты)
P(u|ui)=0.9·0.9·0.1=0.081 (вероятность того, что исказится только третий бит)
P(u)= ?P(u/ui ) ?P(ui) = 0.081·0.4+0.001·0.4+0.081·0.2=0.049
P(u1|u)=0.081·0.4/0.049=0.66
P(u2|u)=0.001·0.4/0.049=0.01
P(u3|u)=0.081·0.2/0.049=0.33.
Максимум апостериорной вероятности достигается для первого слова - и1. Следовательно, это решение и будет принято.
Если считать, что все кодовые слова равновероятны - P(Uj) = const, а также, что безусловная плотность P(U) не зависит от Uj , то максимуму P (Uj |U) соответствует максимум P (U|Uj ), так называемой функции правдоподобия — условной вероятности того, что сигнал примет значение U, если передавалось кодовое слово Uj . Декодер максимального правдоподобия выбирает решение, максимизирующее функцию правдоподобия: U*=arg max{P(U|Uj );UjIA} Более развитые методы декодирования учитывают еще и последствия от ошибок декодирования.
Представьте, что кодовое слово u3=(1 1 1) является сигналом боевой тревоги, тогда последствия от ошибочного декодирования могут быть очень велики, несмотря на то, что вероятность такой ошибки – мала.
Для этого вводится т.н. функция потерь L(U,Uj).
Функция потерь L(U,Uj) – это мера негативных последствий при декодировании, являющихся результатом того, что вместо истинного переданного сообщения Uj принимается решение о приеме сообщения U.
В соответствии с критерием Байеса надо декодировать так, чтобы
минимизировать средние потери от ошибочного декодирования. Средние потери от принятия решения U при получении сообщения U вычисляются по формуле:
W(U|U) = ?j L(U,Uj)·P(Uj|U). Декодер Байеса выбирает решение,
минимизирующее средние потери: U*=arg min{W(U|U);UIA}
Пример. Кодовые слова из предыдущего примера имеют следующий смысл: и1 – проверка, и2 – учебная тревога, и3 – боевая тревога. Потери от ошибок декодирования сведены в матрицу потерь L(U,Uj):           L(U,Uj)=
UjUU1 U2 U3                U1 0 5 10
U2 8 0 10
U3 40 20 0
W(U1|U) = ?jL(U1,Uj)·P(Uj|U)=8·0.01+40·0.33=13.28
W(U2|U) = ?jL(U2,Uj)·P(Uj|U)=5·0.66+20·0.33=9.9
W(U3|U) = ?jL(U3,Uj)·P(Uj|U)=10·0.66+10·0.01=6.7
Минимальные средние потери при решении U*=u3
Декодер Байеса имеет достаточно универсальный характер, так его вид зависит от функции потерь. Задавая функцию потерь тем или иным способом, можно получать различные критерии декодирования. Например, если функция потерь представляет собой кодовое расстояние между истинным и принимаемым сообщением (L(U,Uj)=?UkAUjk), то критерий Байеса превращается в критерий максимального правдоподобия.
Это примеры так называемого жесткого декодирования, когда в приемнике сначала принимается решение относительно значения символов принятой последовательности, а уже затем – относительно значения кодового слова. При жестком декодировании по принятому сигналу сначала определяются символы принятой последовательности U, а потом эта последовательность поочередно сравнивается со всеми кодовыми словами данного кода. Решение принимается в пользу кодового слова, оптимизирующего принятый критерий декодирования. В мягких декодерах выносятся решения относительно Ul непосредственно на основе принятого сигнала с учетом статистических характеристик дискретизации аналогового сигнала. Поскольку в процессе мягкого декодирования информация о сигнале учитывается в большей мере (решение принимается по всему сигналу сразу, а не по частям, для каждого символа в отдельности, и только потом – для всей принятой последовательности), то качество мягкого декодирования должно быть, по идее, выше. Однако реализация жесткого декодера является гораздо более простой – действия выполняются над нулями и единицами. Поэтому такие декодеры используются чаще, хотя и несколько проигрывают мягким декодерам в вероятности правильного декодирования. Еще один подход к декодированию – использование совокупности критериев и формирование так называемых компромиссных решений на основе теории компромиссов В.Парето.