Теория информационных систем

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

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

Сообщения передают с помощью сигналов, которые являются носителями информации. Основным видом сигналов являются электрические сигналы. В последнее время всё большее распространение получают оптические сигналы, например, в волоконно-оптических линиях передачи информации.

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

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

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

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



2. Методы и модели описания систем

Методы описания систем классифицируются в порядке возрастания формализованности - от качественных методов, с которыми в основном и связан был первоначально системный анализ, до количественного системного моделирования с применением ЭВМ. Разделение методов на качественные и количественные носит, конечно, условный характер.

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

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

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



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

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

Методы типа мозговой атаки. это метод систематической тренировки творческого мышления нацеленный на открытие новых идей и достижений.

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

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

Метод делфи -предполагает полный анализ коллективных обсуждений. В методе прямые дебаты заменены тщательно разработанной программой последовательных индивидуальных опросов, проводимых в форме анкетирования.

Метод дерева целей. Термин “дерево целей” подразумевает использование иерархической структуры, полученной путём разделения общей цели на отдельные составляющие.

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

1) Метод систематического покрытия поля(выделение опорных пунктов знания в любой исследуемой области и использовании для заполнения поля некоторых сформулированных принципов мышления.)

2) Метод отрицания и конструирования( на пути конструктивного прогресса стоят догмы и компромиссные ограничения, которые есть смысл отрицать)

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

Методики системного анализа.

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

Количественные методы описания информационных систем.

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

При проектировании информационных систем достаточно трудно определиться, какие явления считать основными, какие факторы - главными, т.к. в процессе функционирования одного и того же реального объекта можно получить различные математические описания, в зависимости от поставленной задачи. С учётом этого, математических моделей сложной информационной системы может быть сколь угодно много, поэтому все они определяются принятым уровнем абстрагирования. Наиболее пригодными являются следующие уровни абстрактного описания систем:1) символический; 2) теоретико-множественный;3) абстрактно-алгебраический; 4) топологический;5) логико-математический;6) теоретико-информационный;7) динамический;8) эвристический.

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

4. Понятие информации. Объекты информационной системы

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

По функциональному назначению можно выделить основные классы объектов информационной техники:

1)сети и системы связи и телекоммуникаций;

2)информационно-измерительные системы;

3)системы преобразования информации;

4)информационно-поисковые системы и системы хранения информации на основе баз данных;

5)системы экспериментального наблюдения и управления объектами.

Обобщённая структурная схема системы передачи информации

Передатчик преобразует исходное сообщение A(x) в сигнал , где x - независимая переменная. Сообщения и сигналы чаще всего рассматриваются в зависимости от времени. Роль линии связи может выполнять любая физическая среда . В приёмнике полученный сигнал, искаженный влиянием помех, преобразуется в копию сообщения B(x), которая должна быть по возможности наиболее близка к оригиналу A(x).

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

Узел связи (информационный узел) - более сложная система, поскольку помимо многоканальной передачи (приёма) информации он обеспечивает:

1выбор кратчайшего пути между источником и получателем сообщения;

2соблюдение системы приоритетов;

3накопление и хранение информации при отсутствии свободных каналов передачи;

4компьютерное управление всеми перечисленными функциями в автоматическом режиме.

5. Виды сообщений в информационных системах

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

Непрерывное сообщение определяется непрерывной функцией времени. Непрерывные сообщения можно передавать дискретными методами. Для этого непрерывный сигнал (сообщение) подвергают дискретизации во времени иквантованию по уровню. На приёмной стороне выполняется восстановление непрерывной функции по дискретным отсчётам.

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

Формирование непрерывных сообщений представляет собой выбор реализаций (случайных функций) непрерывного случайного процесса.

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

6. Определение количества информации. Формула Шеннона.

Количество информации, которое переносит символ: I₁=logm=-logP .

Здесь количество информации связано с вероятностью появления символа. В реальных сообщениях символы a_i появляются с различными вероятностями P(a_i) , поэтому I_i=-logP(a_i)..

Среднее количество информации H(A), которое приходится на один символ источника сообщений можно найти усреднением по всему объему алфавита

Эта величина называется энтропией источника дискретных сообщений. Формула носит название формулы Шеннона.

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

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

H_max=mPlogP=m(1/m)log(1/m)=logm .

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



,

где P(/a_i)- условная вероятность появления символа a_j после символа a_i..

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

7. Информационные характеристики источников дискретных сообщений

Рассмотрим свойства условной энтропии с учётом неравновероятного появления символов и статистической взаимосвязи между ними.

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

H(A,A^r)=-, где P() - вероятность совместного появления символов и Количество информации, которое приходится на слог равно logP() .

Выражение для энтропии совместного появления двух символов

где H(A) - энтропия источника, - условная энтропия источника. Среднее количество информации, которое переносят два соседних символа, равно сумме среднего количества информации, которое переносит первый из них, и среднего количества информации, которое переносит второй при условии, что первый уже появился.

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

.

Если символы a_i и взаимозависимы, то H(A^r/A)<H(A^r). Для источников с независимыми символами.

Корреляционные связи могут существовать между (L+1) символами, тогда источник имеет память на L символов.

8. Принципы кодирования информации

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

Теорема Шеннона для эффективных кодов (без доказательства): для канала без помех всегда можно создать систему эффективного кодирования дискретных сообщений, у которой среднее количество двоичных кодовых сигналов на один символ сообщения будет приближаться как угодно близко к энтропии источника сообщений.

Корректирующее (помехоустойчивое) кодирование имеет целью повышение верности передачи информации путём обнаружения и исправления ошибок.

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

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

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

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

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

Число символов в кодовой комбинации называется значностью кода.

Оператор кодирования показывает, какую кодовую комбинацию присваивают каждому элементу сообщения.

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

Для равномерного кода общее число различных кодовых комбинаций равно где b - основание кода, n - значность кода.

9. Классификация сигналов и методов модуляции

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

Управление информационным параметром сигнала в соответствии с передаваемым сообщением называют модуляцией.

Если информационный параметр сигнала-переносчика изменяется непрерывно, то методы модуляции являются непрерывными. В качестве сигнала-переносчика часто используют периодическую последовательность импульсов, тогда модуляцию называют импульсной. Информационный параметр может принимать счётное число значений, при этом модуляцию называют дискретной. К дискретным видам модуляции относятся, например, амплитудная, частотная и фазовая манипуляции. Если значения параметра закодированы и передаются в цифровой форме, то соответствующие виды модуляции носят название цифровой модуляции. Наиболее распространенным видом цифровой модуляции является импульсно-кодовая модуляция, когда значения сигнала в дискретных точках кодируют в цифровой форме.

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



13. Виды каналов передачи информации

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

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

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

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

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

По характеру сигналов на входе и выходе каналов различают :

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

2) дискретные по уровням, на входе и выходе которых сигналы дискретны. Примером такого канала является канал, заданный от входа кодирующего устройства до выхода декодера.

3) дискретные со стороны входа и непрерывные со стороны выхода или наоборот. Такие каналы называются дискретно - непрерывными или полунепрерывными. Пример - канал, заданный между входом модулятора и входом демодулятора или между выходом модулятора и выходом декодера. Всякий дискретный или полунепрерывный канал содержит внутри себя непрерывный канал. Вообще дискретность и непрерывность канала не связана с характером сообщений: можно передавать дискретные сообщения по непрерывному каналу и непрерывные сообщения - по дискретному.

10. Амплитудная модуляция

Амплитудно-модулированный (АМ) сигнал в общем случае определяется выражением о(x)=[1+mи(x)]s(x), где и(x)- информационный (модулирующий) сигнал, s(x) - сигнал-переносчик, m - коэффициент модуляции. При гармоническом модулирующем сигнале его спектр, как и спектр сигнала-переносчика, представляет собой две дельта-функции. Свертка спектров S(u) и (u) приводит к переносу спектра (u) на более высокую (так называемую несущую) частоту u₀. Если модулирующий сигнал имеет сложную форму и, следовательно, протяженный спектр, образованный множеством пар дельта-функций с различными положениями на частотной оси, то в результате переноса спектра на несущую частоту u₀ образуются соответствующие спектральные порядки. Можно показать, что вся полезная информация содержится в спектральном порядке в окрестности частоты u₀. Демодуляцию АМ сигнала осуществляют путём выделения огибающей сигнала-переносчика при его детектировании и фильтрации нижних частот на выходе детектора. Ширина полосы пропускания фильтра должна соответствовать ширине спектра (u), чтобы обеспечить минимальные спектральные искажения восстановленного сигнала.



11.Фазовая модуляция

Фазовая модуляция -- один из видов модуляции колебаний, при которой фаза несущего колебания управляется информационным сигналом.

Фазомодулированный (ФМ) сигнал имеет постоянную амплитуду, фаза сигнала изменяется пропорционально информационному сигналу, а именно

о(x)=Acos[2рu₀x+mи(x)],(1) где u₀ - несущая частота, m - индекс фазовой модуляции.

Пусть модулирующий сигнал является гармоническим, и(x)=cos(2рu_mx), и индекс модуляции m<<1. При этом выражение (1) можно переписать в виде

.(2)

читывая, что при После преобразования второго слагаемого в (2) получим (3)

Величины спектральных составляющих идентичны величинам спектральных составляющих сигнала с синусоидальной АМ, однако фазовые соотношения между несущей и боковыми составляющими различны. Меньшие векторы медленно вращаются в противоположных направлениях вокруг быстро вращающегося большого вектора, а ж(x) представляет собой проекцию суммы векторов на горизонтальную ось. Однако в отличие от случая АМ сигнала сумма меньших векторов всегда перпендикулярна большему вектору. При этом, если векторы боковых составляющих малы (m << 1), длина суммарного вектора близка по величине амплитуде несущей A, но результирующий вектор вращается с переменной скоростью.

Фазовые соотношения в данной векторной диаграмме указывают простой способ генерирования ФМ сигналов с малым индексом модуляции при произвольном модулирующем сигнале (x).



12. Частотная модуляция

При частотной модуляции изменяется мгновенная (локальная) частота u(x) сигнала-переносчика s(x) в соответствии с информационным сигналом (x), а именно и(x)=Acos[2рu(x)x].

При синусоидальной ЧМ модулирующий сигнал имеет вид

и(x)=-asin(2рu_mx).

Значение a представляет собой максимальную девиацию мгновенной угловой частоты относительно несущей угловой частоты 2рu₀. Простейший демодулятор для ЧМ сигналов или частотный дискриминатор представляет собой резонансный контур, настроенный, например, ниже несущей частоты. Изменения мгновенной частоты во входном модулированном сигнале преобразуются в изменения амплитуды сигнала на выходе резонансного контура. Эти амплитудные изменения нетрудно выделить при помощи обычного детектора огибающей.

В реальных системах неконтролируемые изменения амплитуды в ЧМ-сигнале вызываются шумами, помехами, “замираниями” радиоволн и другими факторами. В связи с этим на входе дискриминаторов необходимо включать ограничитель, который представляет собой нелинейное устройство. Ограничитель совместно с включенным на его выходе резонансным усилителем практически устраняет амплитудные изменения огибающей узкополосного сигнала, сохраняя при этом фазовые изменения.

Усилитель высокой частоты (УВЧ) усиливает принятый сигнал, внутренний гетеродин (генератор) вырабатывает гармонический “опорный” сигнал, который перемножается в смесителе с принятым сигналом. В результате формируется сигнал на промежуточной частоте, которая является постоянной при синхронной перестройке частот настройки УВЧ и гетеродина. Усилитель промежуточной частоты УПЧ обеспечивает высокий коэффициент усиления сигнала.

14. Информационные характеристики дискретных каналов. Идеальные дискретные каналы. Теорема Шеннона для идеального дискретного канала.

Пропускная способность канала C определяется как C=V_maxH, где V - скорость передачи электрических кодовых сигналов, H - энтропия сообщения.

Коэффициент использования канала

?=V/C, 0 ?1, так как 0

Идеальные дискретные каналы

Кодер обеспечивает преобразование предаваемых символов в электрические кодовые сигналы. В идеальном канале между элементами кодовых сигналов на входе и выходе существуют однозначное соответствие (ошибки в канале отсутствуют). Скорость передачи информации равна производительности кодера

C_k=V_kH_k[бит/с],

гдеV_k=1/L - скорость передачи элементарных кодовых сигналов [сигн./с], H_k - энтропия кодера [бит/сигн.], L - длительность элементарного кодового сигнала.

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

C=V_max=V_klogm_k

где m_k - основание кода. Пропускная способность является предельной характеристикой канала. Если основание кода равно m_k и для передачи одного элементарного кодового сигнала необходимо время L, то для передачи кодовой комбинации длиной n сигналов потребуется время T = nL. Общее число кодовых комбинаций длительностью T равно N(T)= Следовательно, максимальное количество информации в одной кодовой комбинации H_max=n·logm_k Пропускная способность равна

.

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

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

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

15. Информационные характеристики дискретных каналов. Реальные дискретные каналы. Теорема Шеннона для реальных дискретных каналов

Информационные характеристики дискретных каналов

Пропускная способность канала C определяется как C=V_maxH, где V - скорость передачи электрических кодовых сигналов, H - энтропия сообщения.

Коэффициент использования канала

?=V/C, 0 ?1, так как 0

Реальные дискретные каналы

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

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

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

C=maxV_k[H(A₁)-H(A₁/A₂)]=maxV_k[H(A₂)-H(A₂/A₁)],

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

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

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



16. Пропускная способность реальных каналов

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

C=maxV_k[H(A₁)-H(A₁/A₂)]=maxV_k[H(A₂)-H(A₂/A₁)],

С помощью этого соотношения можно определить пропускную способность реального двоичного симметричного канала без памяти. Предположим, что известна вероятность P₀ появления ошибки в канале. Определим значение max[H(A₂)-H(A₂/A₁)]. Для двоичного канала max H(A₂)=log2=1 бит/сигн. Условная энтропия H(A₂/A₁) - это энтропия помехи, формула которой - H(A₂/A₁) =-[(1-P₀)log(1-P₀)+P₀logP₀].

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

C₂=V_k[1+P₀logP₀+(1-P₀)log(1-P₀)].

Пропускную способность m-ичного реального канала определяют аналогично

C_m=V_k[logm_k+P₀logP₀(m_k-1)^-1+(1-P₀)log(1-P₀)].

Средняя длина кодовых комбинаций в двоичном и m-ичном реальных каналах определяется неравенством:

n₀₂>, .

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

Избыточность двоичного кода : r₂>P₀logP₀+(1-P₀)log(1-P₀),

избыточность многопозиционного кода

17. Информативность символа. Двоичные коды. Оптимальное кодирование. Теорема (Хартли)

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

Двоичные коды Алфавит языка компьютера состоит из нуля и единицы, а словами являются последовательности нулей и единиц, называемые двоичными словами. Число элементов двоичного слова называется ее длиной. Память компьютера состоит из ячеек, называемых битами, в каждом из которых записан либо 0, либо 1. Биты объединяются в восьмерки, называемыми байтами. Таким образом каждый байт памяти компьютера хранит двоичное слово длины 8. А всего имеется 2⁸ = 256 различных байтовых слов, как следует из леммы (Общее количество двоичных слов длины n равно 2ⁿ).

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

Например, нужно внести в компьютер данные переписи населения РК таким образом, чтобы они занимали как можно меньше памяти. Рассмотрим для начала только данные о поле граждан. Для того чтобы кодировать пол человека достаточно одного бита. Например, можно обозначать женский пол 0, а мужской -1. Получается очень компактный способ кодирования, более того, лучшего способа кодирования пола не существует.

Двоичным кодированием множества М называется отображение с, ставящее в соответствие каждому элементу множества х М двоичное слово с(х) -- его код. Кодирование называется однозначным, если коды различных элементов множества М различны.

Лемма Множество М допускает однозначное двоичное кодирование с длинами кодов не превосходящими n в том и только том случае, когда число элементов множества М не превосходит 2ⁿ.

Теорема Хартли: Информативность символа m-элементного алфавита равна log m

18. Формула Шеннона. Информативность равномерных распределений. Информативность двузначных распределений

Обозначим через W множество слов данного словаря, которые не противоречат известным нам параметрам. Обозначим через А алфавит языка. Для любого s А и любого натурального k, обозначим через s_W(k) количество слов из W, имеющих на k-ом месте букву s. Совокупность чисел { s_W(k) | s А, k N} назовем букво-местным распределением словаря W. Частотой буквы s на позиции k назовем отношение , где | W | -- число слов в W.

И при любом натуральном к совокупность частот { | s А } назовем частотным распределением k-ой позиции словаря W.

Информативность равномерных распределений. Знание k-ой позиции ровно вдвое облегчает задачу идентификации слова, поскольку оно ровно вдвое сужает область поиска.

Если же на k-ом месте встречаются поровну n букв, то, чем больше n -- тем больше информации несет позиция. При этом логично предположить, что количество информации k-ой позиции выражается формулой Хартли: то есть равно log₂ n.

Информативность двузначных распределений. Пусть теперь рассматриваемое распределение содержит лишь два символа с различными частотами: п экземпляров первого символа аит экземпляров второго символа b. Таким образом информативность рассматриваемого распределения выражается формулой:

Равномерное распределение наиболее информативно.

Формула Шеннона выражающая информативность источника информации с т символьным алфавитом и данной частотной характеристикой f₁, f₂,…f_m, где f_i выражает частоту или вероятность появления i-го символа, так что все частоты неотрицательны и их сумма равна единице выглядит следующим образом

19. Энтропия. Энтропия распределения. Условная энтропия

Под энтропией понимается мера неопределенности распределения.

Энтропия распределения f₁, f₂,…,f_m обозначается H(f₁,…,f_m) и выражается формулой точно такой же формулой как его информативность.

Энтропия распределения р₁,…, р_п равна нулю в том и только том случае, когда все Pi за одним единственным исключением равны нулю. Таким образом нулевая энтропия означает полную детерминированность источника. Чем выше энтропия тем больше возможностей представляет данное распределение. Равномерное распределение имеет наибольшую энтропию среди всех распределений с данным числом исходов. Условная энтропия источника относительно согласованного с ним источника равна нулю в том и только том случае, когда функционально зависит от . Два источника информации независимы в том и только том случае, когда энтропия их совместного распределения равна сумме энтропии источников.

20. Сжатие информации. Алгоритм Хаффмена

Различные буквы встречаются в тексте с существенно разными частотами. Поэтому следует кодировать буквы таким образом, чтобы те, которые встречаются чаще кодировались более коротко, а те которые встречаются реже кодировались длиннее. Если код неравномерный, то возникает проблема: как понять где кончился код одного символа и начался код другого. Эта проблема может быть решена, если код обладает следующим свойством: код одного символа не может быть началом кода другого символа. Код удовлетворяющий этому условию называется префиксным. Существует способ сжатия всех файлов с частотными характеристиками ..., который обеспечивает сжатие сколь угодно близкое к | log + ... log | бит на символ и не существует способа сжатия всех файлов с частотными характеристиками ..., который обеспечивает сжатие лучше чем | log + ... log | бит на символ. Код Хаффмена -- это двоичный префиксный код. Кодирование по Хаффмену определяется рекурсивно. Если имеется всего два символа в тексте, то один из них кодируется нулем, а другой кодируется единицей. Можно доказать, что алгоритм Хаффмена дает наилучший возможный двоичный префиксный код.



21. Информационная зависимость. Совместное распределение. Условная и взаимная информация. Функциональная зависимость

Совместное распределение. Всякий способ согласования позволяет рассматривать пару источников как один составной источник информации, алфавитом которого служит произведение АВ. Частотная характеристика составного источника называется совместным распределением пары источников. в виде матрицы (двумерного массива) частот, f_ij где f_ij -есть частота, с которой встречается пара (А[i], B[j]), состоящая из i-гo символа алфавита А и j-гo символа алфавита В.

Условная и взаимная информация Пусть H₁ и Н₂ энтропии двух согласованных источников,Н₁₂- энтропия их совместного распределения. H₁= (Н₁₂- H₁) +(Н₁+Н₂-Н₁₂)- 2 скобки соответственно условная и взаимная информация. Условная информация второго источника по отношению к первому -- это та добавочная информация, которую несет второй источник по сравнению с первым. Взаимная инф - та часть информации второго источника, которая уже содержится в первом источнике.

Функциональная зависимость. Источник информации с алфавитом В функционально зависит от согласованного с ним источника информации с алфавитом А, если имеется функция f:AB, такая что всякий раз, когда порождает некоторый символ Ј А, источник порождает f(a).

22. Информационная зависимость. Критерий независимости

Будем говорить, что матрица является тензорным произведением строк p₁ …p_m, и q₁…q_n, если f_ij=p_iq_j при любых i, j.

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

23. Относительное кодирование. Случайные последовательности

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

Случайные последовательности. Можно также рассматривать зависимость символа от пары предыдущих и т.д. Наличие таких зависимостей позволяет сжать файл. Случайная последовательность символов -- такая которая не имеет зависимостей. Ее нельзя сжать.

24. Защита информации. Избыточность. Контроль четности. Контрольная сумма. Локализация ошибки. Кодирование. Декодирование

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

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

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

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

Код Хэмминга позволяет найти ошибку в последовательности битов при условии, что ошибок не больше одной. Если требуется передать п -- битов, а передается N > п. В переданном тексте, кроме п битов информации должно оставаться место для информации о позиции ошибки -- одном из N мест, то есть logN + 1 бит (нулевая возможность -- отсутствие ошибок). Таким образом . Видно, что количество дополнительных битов логарифмически зависит от длины кодовой

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

Энтропийное кодирование -- кодирование последовательности значений с возможностью однозначного восстановления с целью уменьшения объёма данных (длины последовательности) с помощью усреднения вероятностей появления элементов в закодированной последовательности.

Декодирование - преобразование зашифрованной информации в понятный, пригодный для непосредственного использования вид.

25. Агрегатное описание систем

Агрегат - унифицированная схема, получаемая наложением дополнительных ограничений на множества состояний, сигналов и сообщений и на операторы перехода, а так же выходов. Агрегат - объект, определенный множествами T, X, U, Y, Z и операторами H и G реализующими функции z(t) и y(t). Структура операторов H и G является определяющей для понятия агрегата.

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

Автономный агрегат - агрегат который не может воспринимать входных и управляющих сигналов.

Неавтономный агрегат - общий случай.

Частные случаи агрегата:

· кусочно-марковский

· кусочно-непрерывный агрегат

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

Представление реальных систем в виде агрегатов неоднозначно, вследствие неоднозначности выбора фазовых переменных.

· Иерархические системы. Иерархический принцип построения модели как одно из определений структурной сложности.

· Вертикальная соподчиняемость. Система представляется комплексом моделей - технологические, информационные и т.п. со своими наборами переменных.

· Разбитие сложной проблемы на более простые: слой выбора способа действия, слой адаптации, слой самоорганизации.

· Многоэшелонные системы. Состоят из четко выраженных подсистем, некоторые из них являются принимающими решения, иерархия подсистем и принятия решений.

· Декомпозиция на подсистемы - функционально-целевой принцип, декомпозиция по принципу сильных связей.

информационный система сигнал сообщение

26. Что называется информационной системой?

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

- ИС предназначены для сбора, хранения и обработки информации.

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

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

27. Что понимается под моделями 1 -го, 2-го, 3-го уровней?

28. Что называется структурой информационной системы?

Структуру ИС составляет совокупность отдельных ее частей, называемых подсистемами. Подсистема -- это часть системы, выделенная по какому-либо признаку. Если общую структуру ИС рассматривать как совокупность подсистем независимо от сферы применения, то в этом случае подсистемы называют обеспечивающими.

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

29. По каким признакам ИС классифицируется?

По функциональному признаку и по уровням управления.

По функциональному признаку: производственная, маркетинговая, финансовая, кадровая.

По уровню управления:

* информационные системы оперативного (операционного) уровня - бухгалтерская, банковских депозитов, обработки заказов, регистрации билетов, выплаты зарплаты;

* информационная система специалистов - офисная автоматизация, обработка знаний (включая экспертные системы);

* информационные системы тактического уровня (среднее звено) - мониторинг, администрирование, контроль, принятие решений;

* стратегические информационные системы - формулирование целей, стратегическое планирование.

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

30.Какими бывают системы по принципам управления в подчиненности?

ѕ Информационные системы оперативного (операционного) уровня

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

ѕ Информационные системы специалистов

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

ѕ Информационные системы тактического уровня (среднее звено)

Основные функции этих информационных систем:

* сравнение текущих показателей с прошлыми показателями;

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

* обеспечение доступа к архивной информации и т.д.

ѕ Стратегические информационные системы

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

31. Что такое децентрализованная система?

Иерархичность структуры управления. Управление в БС может быть централизованным и децентрализованным. Централизованное управление предполагает концентрацию функции управления в одном центре БС. Децентрализованное -- распределение функции управления по отдельным элементам. Типичные БС, встречающиеся на практике, относятся, как правило, к промежуточному типу, когда степень централизации находится между двумя крайними случаями: чисто централизованным и чисто децентрализованным.

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



32.Какие вводятся характеристики для классификации ВС по структуре? Что они характеризуют?

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

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

По назначению вычислительные системы делят на универсальные и специализированные. Универсальные ВС предназначаются для решения самых различных задач. Специализированные системы ориентированы на решение узкого класса задач.

По типу вычислительные системы можно разделить на многомашинные и многопроцессорные ВС. Исторически многомашинные вычислительные системы (ММС) появились первыми. Уже при использовании ЭВМ первых поколений возникали задачи повышения производительности, надежности и достоверности вычислений.

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

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

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

По методам управления элементами ВС различают централизованные, децентрализованные и со смешанным управлением. Помимо параллельных вычислений, производимых элементами системы, необходимо выделять ресурсы на обеспечение управления этими вычислениями. В централизованных ВС за это отвечает главная, или диспетчерская, ЭВМ (процессор). Ее задачей является распределение нагрузки между элементами, выделение ресурсов, контроль состояния ресурсов, координация взаимодействия. Централизованный орган управления в системе может быть жестко фиксирован, или эти функции могут передаваться другой ЭВМ (процессору), что способствует повышению надежности системы. Централизованные системы имеют более простые ОС. В децентрализованных системах функции управления распределены между ее элементами. Каждая ЭВМ (процессор) системы сохраняет известную автономию, а необходимое взаимодействие между элементами устанавливается по специальным наборам сигналов. С развитием ВС и, в частности, сетей ЭВМ интерес к децентрализованным системам постоянно растет.