Ссылка на файл: >>>>>> http://file-portal.ru/1 основные понятия теории информации/
Лекции по теории информационных процессов и систем - файл Глава 3. Основы теории информации.doc
П.1. Основные понятия общей теории информации
Тема 1.1 Основные понятия теории информации
Виды и структура информации. Геометрическая, комбинаторная и аддитивная мера Хартли. Связь энтропии с количеством информации. Количество информации дискретных сообщений. Определение бита и байта. Субьект - часть управляющей системы, оказывающая активное воздействие на ее работу. Обьект - пассивная часть как информационной так и управляющей системы. Сообщения передаются в систему связи в непрерывном аналоговом или дискретном цифровом виде. Различают геометрическую, комбинаторную и аддитивную меры информации. Применяется для оценки возможностей аппаратуры пропускная способность каналов связи, объем запоминающих устройств и т. Применяется для количественных оценок хранения и передачи конкретной информации в зависимости с ее статистических характеристик. Применяется при оценке эффективности логического опыта путем введения: Количество информации в комбинаторной мере вычисляется как количество комбинаций элементов. Например число сочетаний из трехбуквенного алфавита А, Б, В по 2 будет равно 3: Число возможных перестановок h эле ментов: Например число перестановок букв А, Б, В будет равно 6: АБВ, АВБ, БАВ, БВА, ВАБ, ВБА. Размещения из h элементов по l различаются составом элементов и их порядком. Например число размещений букв А, Б, В по 2 будет равно 6: АБ, БА, АВ, ВА, БВ, ВБ. При применении комбинаторной меры возможное количество информации Q заключается не в простом подсчете квантов, как в геометрическом представлении, а в определении количества осуществляемых комбинаций. Количество представляемой информации при том же количестве элементов можно существенно повысить. Определение аддитивной меры исходит из позиционной системы счисления. Глубиной h будем называть количество различных элементов знаков, букв содержащемся в принятом алфавите. Глубина числа соответствует основанию системы счисления и кодирования. Длиной l числа называется количество разрядов кода, необходимых и достаточных для представления чисел нужной величины Q. АА, АБ, АВ, БА, ББ, БВ, ВА, ВБ, ВВ. Вследствие показательного закона зависимости Q от l число Q не является удобной мерой для оценки информационной емкости. Поэтому Хартли ввел аддитивную двоичную логарифмическую меру, позволяющую вычислять количество информации I в двоичных единицах: Если количество разрядов длина числа равна единице, принята двоичная система счисления глубина h алфавита равна двум и используется двоичный логарифм, то потенциальное количество информации равно одному биту. Ансамблем называется полная группа событий, с известным распределением вероятностей, составляющих в сумме единицу. Энтропия H характеризует неопределенность априорного состояния ансамбля событий, а количество информации I - мера снятие неопределенности при получении сообщения о событии. Количественно мера информация совпадает с мерой измерения энтропии. Например, ансамбль знаний студента до лекции был: Ситуация априорно характеризовалась энтропией Н1. Рассмотрим ансамбль случайных дискретных событий Х: Очевидно, что чем меньше априорная вероятность i -го события снег в Африке , тем большую информацию несет сообщение этого события, и наоборот, чем вероятнее событие лекция закончится до обеда , тем меньше информации в сообщении о событии. Мера измерения количества информации для дискретных случайных сообщений впервые была предложена Шенноном в г, а затем более строго была определена советским ученым Хинчиным А. Количество информации, содержащееся в конкретном сообщении о событии x i: Двоичная единица, соответствующая основанию, равному двум, называется битом. В вычислительной технике используется двоичная система счисления, поэтому основание логарифма для вычисления количество информации будет равно двум. Энтропия H характеризует неопределенность априорного состояния ансамбля событий, а. В нашей области науки и техники используется двоичная система счисления, поэтому основание логарифма для вычисления количество информации будет равно двум. Свойства количества информации дискретных сообщений: Количество информации детерминированных сообщений равно нулю. Количество информации максимально, если сообщения равновероятны. В случае неравных вероятностей количество информации по Шеннону меньше информационной емкости ансамбля. Рассмотрим основные характеристики систем передачи данных по каналу связи без ошибок: Среднее количество информации, передаваемое по каналу в единицу времени, называется скоростью передачи информации: Одним из важнейших вопросов проектирования системы передачи данных является согласование V и C: Впервые эти вопросы были исследованы Шенноном, показавшим, что основным условием динамического согласования источника сообщений и информационного канала является соотношение: Рассмотрим это соотношение на примере дискретного канала без помех. В любом реальном канале всегда присутствуют помехи. Однако, если уровень помех так мал, что вероятность искажения приблизительно равно нулю, то можно считать, что: Таким образом, максимальная скорость передачи информации по каналу, равная в пределе С, обеспечивается при равномерном распределении статистической независимости символов алфавита сигналов. Необходимо различать C и V X. О степени приближения скорости передачи информации V X к пропускной способности канала утверждает теорема Шеннона для дискретного канала без помех. Первая теорема Шеннона об эффективности передачи информации по каналу связи. Под кодированием в широком смысле слова подразумевается представление сообщений в форме, удобной для передачи по данному каналу. Обратная операция называется декодированием. Кодирование, учитывающее статистические особенности источника сообщений называется статистическим эффективным кодированием. В настоящее время разработано большое количество различных способов оптимального статистического кодирования. Все они должны обеспечивать решение двух основных задач: Для двоичного канала с отсутствием статистических связей между символами этим требованиям удовлетворяет код Шеннона-Фано. В соответствии с этим, построение кода выполняется по следующей последовательности: А все буквы алфавита выписывают столбцом в порядке убывания вероятности;. Для двоичного канала этим требованиям удовлетворяет код Шеннона-Фано. Оценим скорость передачи информации для методов: Это удалось получить потому, что значения P Z i заданы так, что подгруппы точно делились пополам. Рассмотренная процедура кодирования, основанная на методе Шеннона-Фано, не всегда является однозначной , так как возможны различные варианты разбиения сообщения на подгруппы с близкими вероятностями пример: Две последние буквы объединяются в одну вспомогат. Процесс продолжается до получения единственной буквы. Так как принимаемые из канала сообщения, вследствие воздействия помех, отличаются от передаваемых в канал ,то рассмотрим две системы дискретных сигналов: А Для канала без помех: Б Для канала с помехами: Виды каналов с помехами. Количество информации, предаваемой по каналу с помехами. А неопределенность относительно x i до получения y j характеризуется его энтропией: Для канала без помех, получив y j из канала связи, мы полностью сняли о нем неопределенность, то есть получили количество информации: Для определения среднего кол-ва инф. Проведя соответствующие преобразования, получим: Среднее количество информации, получаемое из канала связи при наличии помех равно разности безусловной энтропии, характеризующей начальную неопределенность сообщений до принятия сообщения и условной энтропии, характеризующей остаточную неопределенность после получения сообщения. Таким образом, полученное сообщение y j не снизило на сколько-нибудь неопределенность относительно x i. Информационные характеристики реальных каналов связи лежат между двумя предельными случаями: Скорость передачи и пропускная способность дискретного канала с помехами. Определим C для бинарного симметричного канала связи. Для дискретного канала с помехами доказана теорема вторая теорема Шеннона: Следствием теоремы является утверждение, что не существует метола кодирования, позволяющего вести передачу информации со скоростью выше C и с малой вероятностью ошибки. Таким образом, данная теорема устанавливает соотношения при передаче по каналу с помехами между скоростью сообщений создаваемых источником V, пропускной способностью канала C и достоверностью передачи. Следует отметить, что данная теорема не отвечает на вопрос: При использовании статистического кодирования осуществляется: А выравнивание вероятности появления 0 и 1;. Б статистическая независимость 0 и 1;. Используя коды, контролирующие ошибки, для данного канала можно построить такую систему связи, что вероятность ошибки на выходе будет сколь угодно мала. Однако Шеннон не указал, как найти подходящие коды, а лишь доказал их существование. Помехоустойчивыми называются коды, позволяющие обнаруживать или исправлять ошибки, происходящие при передаче информационных сообщений по каналам. Однако коды БЧХ и Рида-Соломона еще далеки от кодов предсказанных Шенноном при большой длине блока происходит резкое увеличение избыточности. На основе кодов БЧХ разработана методика построения н. Значение проверочных разрядов определяется: Но поскольку вес вектора e: По аналогии с кодами, обнаруживающими ошибки: Минимальное расстояние равно наименьшему из всех расстояний по Хэммингу между различными парами кодовых слов, то есть. При прохождении кодовой комбинации по каналу связи под влиянием помех возможно изменение кодовой последовательности. Ошибки проявляются в том, что в одном или нескольких разрядах кодовой комбинации: Пакеты ошибок характеризуются длиной пакета l. Пакетом ошибок длины l называется комбинация ошибок, расположенных среди l последовательных компонент, первая и последняя из которых отличны от 0. Рассмотрим проблему поиска методов построения кодов с заданными параметрами n , k и корректирующими свойствами. Простые коды с проверкой на четность. Коды с низкой избыточностью и плохими корректирующими характеристиками: Простые коды с повторением. Коды с высокой избыточностью и хорошими корректирующими возможностями. Ввод операции инверсии а не просто повторения позволяет не только обнаруживать, но и при некоторых допущениях P одиночн. Для наглядности и оценки корректирующих способностей кодов рассмотрим геометрическую модель двоичного кода. Самый большой класс разделимых блочных кодов составляют систематические или линейные коды. Для двоичных кодов в качестве линейной операции используются сложение по mod 2. Основное свойство линейного кода: Линейные коды образуют алгебраическую группу по отношению к операции сложения по mod 2. В этом смысле они являются групповыми кодами. Для построения групповых кодов то есть перехода от информационных разрядов к полному кодовому слову, включающему также и проверочные разряды, целесообразно использовать специальные матрицы: На практике установлено, что в качестве информационной матрицы И удобно брать единичную матрицу в канонической форме: Остальные комбинации кода строятся при помощи образующей матрицы. Коды, обнаруживающие одиночную ошибку. Построение кодовой комбинации E в матричной форме имеет вид: Построить образующую матрицу и кодовую комбинацию для линейного кода, исправляющие одиночные ошибки при передаче собщений. Групповой код построен по матрице. Покажем процесс исправления ошибки в произвольном разряде корректирующего кода. Определим соответствие между ошибкой в определенном разряде принятой комбинации и видом проверочного синдрома. Пусть информация принята верно, то есть ни один из разрядов a i , b j не исказился. Это подтверждает необходимый и достаточный признак принятия правильной информации. Мы видим, что проверочная матрица H состоит из двух частиц матрицы П и единичной матрицы. Данная методика построения проверочной матрицы является одинаковой для всех образующих матриц. Мы рассмотрели групповые линейные коды и процедуры кодирования и декодирования, в основе которых лежит построение порождающей S и проверочных матриц H. Наряду с решением вопроса построения линейного кода с заданной корректирующей способностью, существенным является вопрос об избыточности и простоте структурной реализации. С этой точки зрения линейные коды разделяются на совершенные плотно упакованные и несовершенные линейные коды. С точки зрения простой структурной реализации: Важным вопросом на практике является структурная реализация кодирующих и декодирующих устройств. Поэтому для сравнения рассмотрим коды, Хэмминга, обладающие аналогичной корректирующей способностью, но с точки зрения структурной реализации дающие несколько другие результаты. Из определения Н, в которой каждая строка равна синдрому ошибки. Структурная реализация линейных кодов и Хэмминга это кодирование и декодирование. Для исправления одиночной и обнаружения двойной ошибки, кроме проверок по контрольным позициям, следует проводить еще одну проверку на четность. Недостаток групповых линейных кодов: Более совершенными являются циклические коды. Коды, удовлетворяющие условию циклического сдвига, называются циклическими. Применение циклического кода основано на записи любой кодовой комбинации в виде полинома. Это основное свойство позволяет определить наличие ошибки в кодовой комбинации. Многочлен P x степени n называется простым , если он не делится без остатка ни на какой многочлен степени меньшей, чем n аналогия с простым числом. Приведение подобных членов осуществляется сложением по mod 2. Аппаратное умножение двоичных многочленов. Набор остатков от деления строже. При этом, вес каждого. Последнее делится на 1,2,4. В таблице неприводимых многочленов находим,. Это основное свойство используется для обнаружения и коррекции ошибок в принятых кодовых комбинациях. С учетом данных соотношений процедура кодирования существенно упрощается и представляется в виде: В P x примитивный двоичный полином. А с помощью образующей матрицы. Пример построения матрицы для кода 15,11 с выбором в качестве образующего полинома: Перед описанием этапа декодирования введем следующие обозначения: Исправление ошибки путем сложения проверочного синдрома с кодовой комбинацией: Методика построения кодов БЧХ аналогична общей методике построения ц. Последовательность построения P x для кодов БЧХ тоже, что и для обычных ц. Методика выбора построения образующего полинома основана на понятии корня двоичного многочлена и теоремы БЧХ. Понятие корня двоичного многочлена. Корни полинома получены Питерсеном и сведены в специальную таблицу. Для построения полинома кодов БЧХ используется теорема БЧХ: Если взять в качестве порождающего. Методика этапов кодирования и декодирования кодов БЧХ отличается от кодов, исправляющих одиночные ошибки, только выбором образующего многочлена. Методика выбора порождающего полинома для кодов БЧХ. Выбор неприводимых многочленов в качестве сомножителей образующего полинома т. Этап декодирования аналогичен ц. При выборе в качестве пор. Необходимо закодировать и передать: Циклический сдвиг на 4 позиции. После этого получаем направленную кодовую комбинацию. Наряду с независимыми ошибками в каналах часто действуют т. Рассмотрим устройство кода обнаруживающих пакеты ошибок серии ошибок длиной l. Примеры векторов пакетов ошибок: Лемма 2 Всякий полином, имеющий сомножитель который содержит четное число членов, также имеет четное число членов. Коэффициенты при которых 0 и 1 т. Рассмотрим возможности определения ошибок как независимых так и пакетов ошибок. Поэтому отношение числа не обнаруживаемых ошибок к общему числу ошибок определяется как. В канале могут действовать любые сочетания ошибок. Имеем циклический код, содержащий к информационных и r проверочных разрядов, образованный с помощью примитивного многочлена G x степени r. Циклический код данного вида позволяет: А0 обнаруживать все одиночные ошибки. A2 все нечетные ошибки если G x имеет четное число членов;. A3 все пакеты ошибок длиной: А4 всевозможные сочетания ошибок кроме. Операции кодирования и декодирования осуществляются над непрерывной последовательностью символов. Кодирование каждого a i осуществляется индивидуально. Для блочных кодов возможности обнаружения и исправления определяются избыточностью, которая введена в данную кодовую комбинацию. Поскольку ошибки встречаются относительно редко, то избыточность большинства кодовых комбинаций не используется. В то же время при появлении пачки ошибок введенной избыточности не хватает. Корректирующие способности кода определяются параметром, который называется шагом сложения: Рассмотрим процедуры кодирования и декодирования и через основной параметр t определим структуру и основные параметры цепного кода. Структурная схема кодирующего устройства. Структурная схема декодирующего устройства. Наличие не сравнения является признаком ошибки. Данная проверка проводится в соответствии с формулами: Проверка элемента a i. При этом возможны следующие варианты: При этом a i принят правильно, и он проходит без всякой коррекции. Главная Новости Правила О нас Контакты. Главная Рефераты Контрольные работы Курсовые работы Дипломные работы Другие работы О нас. Основные понятия теории информации Категория: Информатика, кибернетика и программирование Описание: Разомкнутую систему называют информационной, а замкнутую - управляющей. Основные определения Субьект - часть управляющей системы, оказывающая активное воздействие на ее работу. Сочетания из h элементов по l различаются составом элементов. Их возможное число равно: Аддитивная мера Хартли Определение аддитивной меры исходит из позиционной системы счисления. Передача информации по каналу без помех. Первая теорема Шеннона и её следствие. В реальных условиях передача сообщений происходит при воздействии помех. Помехи искажают сообщения, вследствие чего сообщения на приёмной стороне будут в той или иной степени отличаться от переданных, то есть будет иметь место неполная достоверность передачи. Для определения основных параметров К. В настоящее время основные выводы теории информации получены применительно к каналам без памяти. В дальнейшем будем рассматривать каналы без памяти. Практически все реальные каналы являются нестационарными. Исследования нестационарных каналов является более сложным и трудоемким процессом, поэтому при анализе они представляются как последовательность стационарных каналов. То есть, для конкретных отрезков времени нестационарные каналы апроксимируются стационарными. Дискретный канал, по которому передаются только два элементарных сигнала, называют бинарным. Среднее количество информации о всем множестве X , содержащееся в принятом сообщении y j: Вторая теорема Шеннона и её следствие. При практической реализации эффективных кодов неизбежна задержка в передаче информации. Основная идея кодирования Помехоустойчивыми называются коды, позволяющие обнаруживать или исправлять ошибки, происходящие при передаче информационных сообщений по каналам. Количество разрядов n в кодовой комбинации называется длиной кода длиной блока. Образующая и проверочная матрицы. Определение проверочного синдрома S i в соответствии с видом проверочной матрицы П. Исправление коррекция [инверсия] ошибочной позиции. Структурная реализация линейных кодов и Хэмминга это кодирование и декодирование 6. Отсюда, основное свойство циклического кода: Процедура кодирования состоит в умножении кодовой комбинации из информационных символов на образующий многочлен G x. Виды двоичных многочленов, их свойства. Сложение, умножение и деление двоичных многочленов. Для исключения каждый раз операция деления на практике построение циклического кода осуществляется при помощи образующей матрицы G n , k аналогично групповым кодам. После построения образующей матрицы процедура определения проверочных разрядов аналогична этой процедуре линейных групповых кодов: В данном случае остаток R x от деления E x на P x играет роль проверочного синдрома. Коррекция ошибки и циклический сдвиг на d разрядов вправо. Последовательность построения циклических кодов, исправляющих одиночные ошибки. Определение количества проверочных разрядов и длина кодовой комбинации: Выбор образующего полинома, удовлетворяющего следующим условиям: Количество корней многочлена равно степени полинома. Количество корней a 1 , a 2 , a Определение количества информационных разрядов: Определение количества проверочных разрядов: Обнаруживающая способность циклических кодов для всевозможных ошибок. В рекуррентных кодах, так же как и в блоковых, проверочные символы получаются в результате проведения линейных операций чаще всего суммирование по mod 2 над определенными информационными символами. Структуру рекуррентного кода, размещение проверочных и информационных символов в общий кодовой последовательности рассмотрим на примере цепных кодов. Структурная схема декодирующего устройства Примечание: Структурная схема реализации цепного кода. А также другие работы, которые могут Вас заинтересовать Доклад Необходимость синхронизации процессов и потоков. В многозадачной ОС синхронизация процессов и потоков необходима для исключения конфликтных ситуаций при обмене данными между ними разделении данных доступе к процессору и устройствам вводавывода. Пренебрежение вопросами синхронизации процессов выполняющихся в многозадачной системе может привести к неправильной их работе или даже к краху системы. Доклад Способы реализации взаимных исключений путем запрещения прерываний, использования блокирующих переменных, системных вызовов Это самый простой но и самый неэффективный способ так как опасно доверять управление системой пользовательскому потоку который может надолго занять процессор а при крахе потока в критической области крах потерпит вся система потому что прерывания никогда не будут разрешены. Для синхронизации потоков одного процесса программист может использовать глобальные блокирующие переменные к которым все потоки процесса имеют прямой Доклад Назначение и использование семафоров Для решения задачи введем три семафора: Использование семафоров для синхронизации потоков Здесь операции Р и V имеют следующее содержание: Ре если есть свободные буферы то уменьшить их количество на 1 если нет то перейти в состояние Доклад Взаимные блокировки процессов. Методы предотвращения, обнаружения и ликвидации тупиков Тупиковые ситуации надо отличать от простых очередей хотя и те и другие возникают при совместном использовании ресурсов и внешне выглядят похоже: Проблема тупиков включает в себя решение следующих задач: Другой более гибкий подход динамического предотвращения тупиков заключается в использовании определенных правил при назначении ресурсов процессам. Доклад Функции ОС по управлению памятью. Функциями ОС по управлению памятью являются: Программист при написании программы в общем случае обращается Доклад Методы распределения памяти без использования диска фиксированными, динамическими, перемещаемыми разделами Рассмотрим наиболее общие подходы к распределению памяти которые были характерны для разных периодов развития ОС. Классификация методов распределения памяти 5. Доклад Понятие виртуальной памяти, ее назначение. Необходимым условием для того чтобы программа могла выполняться является ее нахождение в оперативной памяти. Уже давно пользователи столкнулись с проблемой размещения в памяти программ размер которых превышает имеющуюся в наличии свободную память. Доклад Страничное распределение оперативной памяти Чтобы упростить механизм преобразования адресов размер страницы обычно выбирается равным 2n: Смежные виртуальные страницы не обязательно располагаются в смежных физических страницах. Запись таблицы называемая дескриптором страницы включает следующую информацию: Доклад Сегментное распределение оперативной памяти Рассмотрим каким образом сегментное распределение памяти реализует эти возможности рис. Во время загрузки процесса система создает таблицу сегментов процесса аналогичную таблице страниц в которой для каждого сегмента указывается: Необходимость синхронизации процессов и потоков. Способы реализации взаимных исключений путем запрещения прерываний, использования блокирующих переменных, системных вызовов. Поток при входе в критическую секцию запрещает все прерывания а при выходе из критической секции снова их разрешает. Пусть буферный пул состоит из N буферов каждый из которых может содержать одну запись рис. Методы предотвращения, обнаружения и ликвидации тупиков. Методы предотвращения обнаружения и ликвидации тупиков. Функции ОС по управлению памятью. Сама ОС обычно располагается в самых младших или старших адресах памяти. Методы распределения памяти без использования диска фиксированными, динамическими, перемещаемыми разделами. Методы распределения памяти без использования диска фиксированными динамическими перемещаемыми разделами. Понятие виртуальной памяти, ее назначение. Понятие виртуальной памяти ее назначение. В общем случае размер виртуального адресного пространства не является кратным размеру страницы поэтому последняя страница каждого процесса дополняется фиктивной областью. Сегментное распределение оперативной памяти.
Тыква цукат описание
Как сделать гирлянду из ткани
Транснефть тесты при приеме на работу
Тема 1.1 Основные понятия теории информации
Залить фундамент под построенный дом
Партнерские роды отзывы мужей
Пицца оплата кредитной картой
Тема 1.1 Основные понятия теории информации
Как объяснить ребенку что лучше
Робби уильямс party russian перевод
Лекции по теории информационных процессов и систем - файл Глава 3. Основы теории информации.doc
Баскетбол россия суперлига таблица
Сотрудничество выгодные условия
Проблемы армии сша
П.1. Основные понятия общей теории информации
Сколько нужно спать чтобы выспаться таблица