Математические основы теории информации и передачи сигналов

ЛЕКЦИИ ПО ДИСЦИПЛИНЕ МАТЕМАТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ И ПЕРЕДАЧИ СИГНАЛОВ АВТОР к.т.н., Шуиарова О.С. ЛЕКЦИЯ 1. Математический аппарат теории информации Цель лекции – знакомство с понятием «информация», этапами обращения информации, видами, структурой информации, задачами теории информации. Задачи лекции - знакомство с понятием «информация», этапами обращения информации, видами, структурой информации - знакомство с задачами теории информации Вопросы, рассматриваемые на лекции 1. Понятие «информация», этапы обращения информации, виды, структура информации, 2. Теории информации, ее задачи. Под информацией нужно понимать существенные и представительные характеристики предметов и процессов материального мира, то есть их отображение в виде чисел, формул, описаний, чертежей, символов, образов и других абстрактных характеристик. Проявляется информация всегда в материально-энергетической форме в виде сигналов. Этапы обращения информации: восприятие, передача, обработка, представление, воздействие. Виды информации. Информацию разделяют: по области знаний, по физической природе восприятия, по метрическим свойствам. В технической области знаний можно выделить две формы информации: параметрическую и топологическую. Существует еще абстрактная форма. Формами параметрической информации являются событие, величина, функция, комплекс. Информация может претерпевать различные структурные преобразования. Последовательность этих преобразований в различных информационных системах может быть различной. Различают натуральную, нормализованную, генерализованную, дискретную и кодированную структуры информации. Задачи теории информации - повышение эффективности функционирования и разработка принципов оптимизации систем передачи информации. Вопросы для самопроверки 1. Дайте определение понятию «информация». 2. В чем проявляется информация? 3. Охарактеризуйте этапы обращения информации в системах. 4. Какие задачи решаются на каждом этапе? 5. По каким признакам можно разделить информацию в общем? 6. Какие формы информации выделяют в технической области знаний? 7. Какие понятия включает параметрическая форма? 8. Какие понятия включает топологическая форма? 9. Охарактеризуйте используемые структуры информации. 10. В чем заключается задачи теории информации? ЛЕКЦИЯ 2. Меры измерения информации Цель лекции – изучение мер измерения информации. Задачи лекции - изучение структурных и семантических мер информации - изучение статистической меры информации, понятия «энтропия» и ее свойств Вопросы, рассматриваемые на лекции 1. Структурные и семантические меры информации 2. Статистическая мера информации, энтропия. Для оценки количества информации используют: 1) структурную теорию, рассматривающую дискретное строение массивов информации и их измерение подсчетом информационных элементов (квантов) или комбинаторным методом, предусматривающим простейшее кодирование массивов информации. 2) семантическую теорию, учитывающую целесообразность, ценность, полезность или существенность информации. 3) статистическую теорию, оперирующую понятием «энтропия», учитывающим вероятность появления и информативность тех или иных сообщений. Структурные меры информации учитывают только дискретное строение информационного комплекса, то есть количество содержащихся в нем информационных элементов (квантов), связей между ними или комбинаций из них. Геометрическая мера – определение количества информации сводится к измерению длины линии, площади или объема геометрической модели данного информационного комплекса в количестве дискретных единиц (квантов). Комбинаторная мера используется, когда требуется оценить возможность передачи при помощи различных комбинаций информационных элементов. Рассматриваются различные виды соединений элементов: сочетания, сочетания с повторением, перестановка, перестановка с повторением, размещения, размещения с повторением. Аддитивная мера (мера Р.Хартли) позволяет вычислить количество информации в двоичных единицах – битах. Семантические меры информации. Содержательность, целесообразность, существенность, актуальность информации. Статистические меры информации рассматривают информацию при вероятностном подходе как сообщение об исходе случайных событий реализации случайных величин и функций. Количество информации ставится в зависимость от первоначальных вероятностей этих событий, величин и функций. Энтропия характеризует неопределенность каждого состояния системы. Количество информации равно энтропии, когда неопределенность ситуации снята полностью. Это есть максимальное количество информации. Это в случае, когда вероятности всех событий будут одинаковы. В общем случае, нужно считать, что количество информации есть уменьшение энтропии вследствие опыта или другого вида познания. Абсолютная избыточность информации есть разность между максимально возможным количеством информации и энтропией. Относительная избыточность равна 1-Н/Нмакс. Вопросы для самопроверки 1. Охарактеризовать использование структурных мер информации. 2. Охарактеризовать использование семантических мер информации 3. Охарактеризовать использование статистических мер информации. 4. Охарактеризовать использование геометрической меры информации. 5. Охарактеризовать использование комбинаторной меры информации. 6. Охарактеризовать использование аддитивной меры информации. 7. Охарактеризовать использование семантических мер информации. 8. Перечислите характеристики информации. 9. Охарактеризуйте понятие «энтропия». 10. Перечислите свойства энтропии. ЛЕКЦИЯ 3. Энтропия Цель лекции – знакомство со свойствами понятия «энтропия» Задачи лекции - знакомство с понятиями «энтропия ансамбля», «энтропия объединения» - изучение свойств энтропии, единицы измерения энтропии Вопросы, рассматриваемые на лекции 1. Энтропия ансамбля. Единица измерения энтропии. Свойства энтропии.. 2. Энтропия объединения. Безусловная энтропия. Источник информации, который в каждый момент времени случайным образом может принять одно из конечного множества состояний, называется дискретным источником. Различные состояния реализуются вследствие выбора их источником. Каждое состояние источника обозначается символом Ui (U1, U2, … Un). Одни состояния выбираются источником чаще, другие – реже. В общем случае, источник характеризуется ансамблем U состояний, то есть полной совокупностью состояний и вероятностей их появления, составляющими в сумме единицу. Мера неопределенности выбора состояния источника может рассматриваться как мера количества информации, получаемой при полном устранении неопределенности относительно состояния источника. Мера должна удовлетворять условиям необходимости монотонного возрастания с увеличением возможностей выбора, аддитивности, непрерывности, являться функционалом распределения вероятностей, независимости от пути выбора состояния в ансамбле. Мера неопределенности выбора дискретным источником состояния из ансамбля U, удовлетворяющая указанным условиям, была предложена К. Шенноном. Ее называют энтропией дискретного источника информации или энтропией конечного ансамбля Н(U). Основание логарифма определяет единицу неопределенности. При а=2 единица неопределенности есть двоичная единица (бит) и представляет собой неопределенность выбора из двух равновероятных состояний. Если а=10, Н в десятичных единицах на одно состояние (дит). Если источником может быть реализовано N равновероятных состояний, вероятность каждого из них равна 1/ N и неопределенность, приходящаяся на каждое состояние источника, равна – log pi. Если вероятности событий различны, неопределенность, приходящаяся на каждое состояние источника, определяется также. Неопределенность, приходящаяся в среднем на одно состояние источника, определяется как сумма – pi log pi от i=1 до N. Свойства энтропии.1. Энтропия является вещественной и неотрицательной величиной, т.к. для любого i(i≤i≤N) pi изменяется в интервале от 0 до 1, log pi отрицателен и, следовательно, –pi log pi положительна; 2. Энтропия – величина ограниченная. Для слагаемых –pi logpi в диапазоне 0>(1-p). Энтропия непрерывно зависит от вероятностей отдельных состояний, что вытекает из непрерывности функции –p logp. Под объединением двух источников информации U и V понимается обобщенный источник информации, характеризующийся вероятностями р(uivj) всех возможных комбинаций состояний ui источника U и vj источника V. 6. Энтропия объединения двух статистически несвязанных источников информации равна сумме безусловных энтропий исходных источников. Энтропия объединения: H(UV)=, где p(ui,vj)-вероятности совместной реализации состояний: ui(1≤i≤N) и vj(1≤j≤k) В случайной статистической независимости источников u и v: p(uivj)=p(ui)p(vj), тогда Н Учитывая, что и , получают H(UV)= H(U)+H(V)=H(V,U). Для энтропии объединения нескольких независимых источников U, V, Z: H(U,V,…,Z)=H(U)+H(V)+…+H(Z). 7. Энтропия характеризует среднюю неопределенность выбора одного состояния из ансамбля. При её определении используют только вероятности состояний, не учитывая их содержания. Поэтому энтропия не может служить средством решения любых задач, связанных с неопределенностью. 8. Энтропия как мера не определенности согласуется с экспериментальными данными, полученными при изучении психологических реакций человека, в частности реакции выбора. Установлено, что время безошибочной реакции на последовательность беспорядочно чередующихся равновероятных раздражителей (напр,загорающихся лампочек) растет с увеличением их числа так же , как энтропия. Это время характеризует неопределенность выбора одного раздражителя. При неравновероятных раздражителях снижается среднее время реакции настолько, насколько уменьшается энтропия. Вопросы для самопроверки 1. Какой источник информации называется дискретным? 2. Что такое ансамбль состояний источника? 3. Каким условиям должна удовлетворять мера неопределенности выбора состояния источника? 4. Что называется энтропией конечного ансамбля Н(U)? 5. Что определяет единицу измерения неопределенности? 6. Как определяется неопределенность, приходящаяся в среднем на одно состояние источника? 7. Поясните свойства энтропии. 8. Что понимается под объединением двух источников информации? 9. Как определяется энтропия объединения двух статистически несвязанных источников информации? 10. Как определяется энтропия объединения нескольких независимых источников U, V, Z? ЛЕКЦИЯ 4. Условная энтропия, ее свойства Цель лекции – знакомство с понятием « условная энтропия», ее свойствами. Задачи лекции - определение энтропии объединения двух статистически связанных источников информации - изучение свойств условной энтропии Вопросы, рассматриваемые на лекции 1. Условные вероятности. Условная энтропия. 2. Определение энтропии объединения двух статистически связанных источников информации При оценке неопределенности выбора часто необходимо учитывать статистические связи, которые имеют место между состояниями двух или нескольких источников, объединенных в рамках одной системы, либо между состояниями, выбираемыми последовательно одним источником. Объединение ансамблей характеризуется матрицей р(U,V) вероятностей р(u ivj) всех возможных комбинаций состояний ui (1 ≤ i ≤ N) ансамбля U и состояний vj (1 ≤ j ≤ k) ансамбля V: (U,V)= Суммируя столбцы и строки матрицы, получим информацию об ансамблях U и V исходных источников u и v: U= , V= Вероятности р(uivj) совместной реализации взаимозависимых состояний ui и vj можно выразить через условные вероятности р(ui/vj) или р(vj/ ui) в соответствии с тем, какие состояния принять за причину, какие за следствие p(uivj)=p(ui)p(vj/ui)=p(vj)p(ui/vj) где p(ui/vj)-вероятность реализации состояний ui ансамбля U при условии, что реализовалось состояние vj ансамбля V; p(vj/ui)-вероятность реализации состояния vj ансамбля V при условии, что реализовалось состояние ui ансамбля U. Тогда энтропия объединения Сумма есть случайная величина, характеризующая неопределенность, приходящуюся на одно состояние ансамбля V при условии, что реализовалось конкретное состояние ui ансамбля U. Это частная условная энтропия ансамбля V , которая обозначается Hui(V): Hui(V)= – . При усреднении по всем состояниям ансамбля U получают среднюю неопределенность, приходящуюся на одно состояние ансамбля V при известных состояниях ансамбля U: HU(V)= – или HU(V)= . HU(V)- полная условная или условная энтропия ансамбля V по отношению к ансамблю U. Энтропия объединения двух статических связанных ансамблей U и V равна безусловной энтропии одного ансамбля плюс условная энтропия другого относительно первого: H(UV)=H(U)+HU(V) или H(UV)=H(V)+HV(U), где HV(U)= и Hvj(U)=. Для объединения любого числа зависимых ансамблей H(UVZ…W)=H(U)+HU(V)+HUV(Z)+…+HUVZ(W) В объединении ансамблей условная энтропия любого ансамбля всегда меньше или равна безусловной энтропии того же ансамбля. Для объединения двух ансамблей U и V данное утверждение принимает вид соотношений: HU(V)≤H(V), HV(U)≤H(U). Объединение двух произвольных ансамблей удовлетворяет соотношению H(UV)≤H(U)+H(V). Для объединения нескольких произвольных ансамблей H(UVZ…W) ≤ H(U) + H(V)+ +H(Z)+ …+H(W). Вопросы для самопроверки 1. Чем характеризуется объединение ансамблей состояний источников? 2. Как получить информацию об ансамблях U и V исходных источников u и v? 3. Как охарактеризовать условную вероятность р(ui/vj)? 4. Как охарактеризовать условную вероятность р(vj/ ui)? 5. Как определяется частная условная энтропия ансамбля? 6. Как определить полную условную энтропию ансамбля V по отношению к ансамблю U? 7. Как определяется энтропия объединения двух статических связанных ансамблей? 8. Как определяется энтропия объединения любого числа зависимых ансамблей? 9. Как соотносятся условная и безусловная энтропии одного ансамбля? 10. Приведите графическое изображение энтропий дискретных источников. ЛЕКЦИЯ 5. Сигналы и их математическое описание Цель лекции – изучение математических моделей сигналов Задачи лекции - изучение видов сообщений, видов сигналов - изучение временной и частотной форм представления сигналов Вопросы, рассматриваемые на лекции 1. Виды сообщений, виды сигналов, математические модели детерминированных сигналов 2. Случайный процесс как модель сигнала, стационарные и эргодические случайные процессы Величины, характеризующие тот или иной информационный процесс, как правило, имеют случайный характер, то есть не могут быть заранее известными. Если случайная величина в области своего существования может принимать только конченое число значений, то ее называют диск етной по множеству. Если же случайная величина может принимать бесконечное число своих значений, то ее называют неп е ывной по множеству. В общем случае получаемые сообщения представляют собой некоторую функцию времени. По виду функции времени все сообщения можно классифицировать следующим образом: – непрерывные по множеству и времени (непрерывные) В этом случае функция, характеризующая передаваемое сообщение, имеет непрерывное множество значений и меняется с течением времени непрерывно (рис.1.1). – непрерывные по времени и дискретные по множеству (рис.1.2); – непрерывные по множеству и дискретные по времени (рис.1.3); – дискретные по множеству и времени (рис. 1.4) Материальными переносчиками информации служат сигналы, представляющие собой физические процессы, удовлетворяют следующим условиям: – допускают возможность управления параметрами процесса в соответствии с выбранным алгоритмом; – могут передаваться по соответствующим линиям связи; – могут быть воспринимаемыми и регистрируемыми соответствующими техническими устройствами. В настоящее время в информационных системах наибольшее распространение имеют сигналы электромагнитной природы. В общем случае всякий сигнал представляет собой изменяющуюся во времени физическую величину (ток, напряжение, напряженность электромагнитного поля). Сигналы могут носить как непрерывный, так и дискретный характер. Однако такое деление имеет достаточно условный характер и определяется, в основном, соотношением между временем действия сигнала и интервалом его восприятия. Непрерывные сигналы. В качестве непрерывных сигналов в системах передачи данных чаще всего используются электромагнитные процессы, изменяющиеся по гармоническому закону: = . У таких сигналов характерными параметрами являются амплитуда, частота, фаза (рис. 1.5). Гармонические сигналы в чистом виде фактически не пригодны для передачи информации, потому что если известны исходные параметры такого процесса в начальный момент времени, то параметры этого процесса также будут известны и в любой последующий момент времени, то есть не будут иметь информационной ценности. Дискретные сигналы Такого типа сигналы реализуются в виде кратковременных отклонений, используемого физического процесса от исходного стационарного состояния. Если в качестве дискретных сигналов используют кратковременные воздействия электрического тока или напряжения, то такие сигналы называются видеоимпульсами (рис. 1.6). Если импульсный сигнал реализуется кратковременным высокочастотным процессом, то такой сигнал называется адиоимпульсом. Огибающая радиоимпульса рассматривается как видеоимпульс (рис.1.7). Форма импульсных сигналов может быть различной, а именно: прямоугольной, трапецеидальной, треугольной, пилообразной, колоколообразной, экспоненциальной. На рисунке 1.8 представлены типовые виды импульсных сигналов Сигналы можно рассматривать как детерминированные и случайные колебания, одни – могут быть определены в любой момент времени, другие – как случайные сигналы и помехи. Математические модели детерминированных сигналов. В зависимости от структуры информационных параметров: 1) непрерывная функция u(t) непрерывного аргумента (времени) 2) непрерывная функция u(t) дискретного аргумента (значения функции определены в определенные моменты времени) 3) дискретная функция u(t) непрерывного аргумента (функция времени, квантованная по уровню) 4) дискретная функция u(t) дискретного аргумента (значения функции определены в определенные моменты времени и принимают конечные значения (значения уровней) Временным представлением сигнала называется такое разложение сигнала, при котором в качестве базисных функций используются единичные импульсные функции (дельта-функции). Эта модель соответствует абстрактному импульсу малой длительности и бесконечно большой амплитуды и позволяет определить такие характеристики, как энергия, мощность и длительность сигнала. Часто используется представление детерминированных сигналов с применением базисных функций е-рt как при преобразовании Фурье, так и при обобщенном преобразовании Фурье (преобразовании Лапласа). Стациона ные и э годические случайные п оцессы. Случайный процесс называется нестационарным, если имеет определенную тенденцию развития и характеристики, зависящие от начала отсчета времени. Эта модель сложна. В качестве мат моделей сигналов и помех может быть использован случайный процесс, который представляется случайной функцией времени, значения которой в каждый момент времени случайны. Для описания сигнала используется мат модель стационарного случайного процесса, который определен и статистически однороден во всем диапазоне времени. Свойство эргодичности стационарного случайного процесса означает, что каждая реализация случайного процесса достаточной продолжительности несет практически полную информацию о свойствах всего ансамбля реализаций. Это позволяет упростить определение статистических характеристик, заменяя среднее значение по ансамблю реализаций средним значением одной реализации за длительный интервал времени. Вопросы для самопроверки 1. Какую случайную величину называют дискретной по множеству? 2. Какую случайную величину называют непрерывной по множеству? 3. Как по виду функции времени можно классифицировать все сообщения? 4. Каким условиям должны удовлетворять сигналы? 5. Какие физические процессы представляют собой сигналы? 6. Перечислите характерные параметры непрерывных сигналов. 7. Чем отличается радиоимпульс от видеоимпульса? 8. Представьте математические модели детерминированных сигналов. 9. Для чего используются временная и частотная формы представления сигнала? 10. Какой случайный процесс используется в качестве мат модели сигнала? ЛЕКЦИЯ 6. Дискретизация информации Цель лекции – изучение видов квантования сигналов Задачи лекции - изучение видов квантования сигналов - изучение теоремы Котельникова и принципа Железнова Вопросы, рассматриваемые на лекции 1. Виды квантования сигналов. Методы дискретизации и восстановления непрерывных функций. Теорема Котельникова и принцип дискретизации Железнова 2. Выбор периода дискретизации Передача информации в информационно – управляющих системах может осуществляться как с помощью непрерывных, так и дискретных сигналов. Использование дискретных сигналов в некоторых случаях оказывается более предпочтительным, так как дискретные сигналы меньше подвержены искажениям при передаче, и эти искажения легче обнаруживаются, также дискретные сигналы более удобны для использования и обработки цифровыми устройствами. С другой стороны, большинство первичных сигналов, снимаемых с датчиков, являются непрерывными, возникает проблема эффективного преобразования непрерывных сигналов в дискретные и наоборот. Процесс (процедура) преобразования непрерывной физической величины в дискретную называется квантованием. 1. Квантование по у овню – в этом случае непрерывная функция, описывающая первичный сигнал заменяется ее отдельными значениями, отстоящими друг от друга на некоторый конечный интервал (уровень). Соответственно, мгновенные значение функции заменяются ее ближайшими дискретными значениями, которые называются у овнями квантования. Интервал между двумя соседними уровнями называется шагом квантования (рис. 1.9). Шаг квантования может быть как постоянным ( авноме ное квантование), так и переменным (не авноме ное квантование). Точность преобразования непрерывного сигнала в дискретный зависит от величины шага квантования. Эта точность оценивается расхождением между истинным значением функции и квантованным. Величина этого расхождения называется ошибкой или «шумом» квантования δк. При передаче сигнала по каналу связи на него могут воздействовать те или иные помехи, искажающие этот сигнал. Если при этом известно максимальное значение помехи (δш max), то можно выбрать шаг квантования q, превосходящий δш max, так, что q>2∙δш max, и затем вторично проквантовать сигнал на приемной стороне, то можно очистить принятый сигнал от помех: q>2∙δш max. Откуда δш max< q/2. Таким образом, повторное квантование позволяет восстановить искаженный помехой сигнал и исключить накопление влияния помех. 2. Квантование по в емени (диск етизация) – в этом случае непрерывная функция x(t) заменяется ее отдельными значениями, взятыми в фиксированные моменты времени. Отсчеты значений первичного сигнала производятся через фиксированные моменты времени ∆t - шаг квантования или шаг диск етизации. Чем меньше выбранный интервал ∆t, тем более точно на приемной стороне может быть воспринята функция. С другой стороны, при слишком мелком шаге дискретизации снижается скорость передачи данных, а также повышаются требования к полосе пропускания канала связи: ∆Fк; так как ∆t и ∆Fк связаны соотношениями: ∆F~1/∆t и ∆F∙∆t~1. При слишком крупном шаге дискретизации уменьшается точность воспроизведения функцией на приеме. 3) В ряде случаев оказывается целесообразным использовать смешанный тип квантования, то есть квантование по уровню и времени. В этом случае сигнал предварительно квантуется по уровню, а отсчеты получившихся квантованных значений производят через заданные промежутки времени ∆t. При этом погрешность такого квантования определяется средним геометрическим значений ошибок квантования по уровню и по времени: Δ = δ2ку+δ2кв. 4) дифференциальное квантование: переход с уровня на уровень осуществляется по правилу: если значение непрерывной функции больше значения дискретной функции на предыдущем интервале Δt, то происходит переход на следующий более высокий уровень, если значение непрерывной функции меньше значения дискретной функции на предыдущем интервале Δt – переход на более низкий уровень. Использование методов и средств квантования сигналов в информационнотелекоммуникационных системах приводит к необходимости выбора оптимального режима квантования, а так же решения задачи последующего восстановления проквантованного сигнала (сообщения) на приемной стороне. Эти задачи, в частности, возникают при цифровой обработке аудио- и видеоинформации, когда требуется обеспечить достижение нужного баланса между качеством передачи и полосой пропускания информационной системы. Одной из таких задач является определение рациональной частоты дискретизации («частоты выборки»), которую можно оценить, используя теорему, доказанную в 1933году В.А. Котельниковым, а несколько позже (1948году) также К. Шенноном. Часто применяются методы дискретизации (квантования по времени) с постоянным шагом дискретизации. Методы равномерной дискретизации получили наиболее широкое распространение потому, что неравномерная дискретизация является крайне неудобной для этих целей, поскольку не позволяет осуществить качественную синхронизацию отдельных устройств систем передачи данных и затрудняет процесс восстановления сигнала на приемной стороне. При использовании равномерной дискретизации возникает вопрос о выборе оптимального шага дискретизации. Все методы дискретизации и восстановления непрерывных функций различаются по следующим основным признакам: регулярности отсчетов (равномерные и неравномерные), критерию выбора отсчетов (частотный, квантованный, корреляционный), оценке точности воспроизведения (критерии наибольшего отклонения, среднеквадратичный, интегральный), способу воспроизведения (с интерполяцией, с экстраполяцией), виду воспроизводящей функции (ряд Котельникова, Фурье, полиномы Чебышева, Хаара, Уолша, степенным полиномам (нулевой, первой и высшей степени)). В 1933 г. академиком В.А. Котельниковым была доказана теорема, играющая важную роль в теории информации (в 1948 году К.Шеннон пришел к аналогичному результату). ТЕОРЕМА: Любая непрерывная функция y(t), частотный спектр которой ограничен сверху некоторым значением частоты f≤Fmax, может быть полностью и безошибочно восстановлена по ее дискретным значениям (отсчетам), взятым через интервал времени ∆t≤(2∙Fmax)-1, при этом функция y(t) может быть представлена в виде следующего ряда: y(t)= , где Ψ(t, tk) – функция отсчетов: п и ; п и ωМ – граничная циклическая частота сигнала («частота Найквиста»): ωM=2π∙Fmax; t – текущее время рассматриваемого процесса y(t), tk– время, когда берутся отсчеты значений функции y(tk): tk=k∆t. Каждая функция отсчетов ψk представляет собой с точки зрения теории сигналов реакцию идеального фильтра низкой частоты, имеющего граничную частоту Fmax, на импульс в форме δ-функции в момент времени t=k∆t, равной мгновенному значению функции y(t) в этот момент времени (рис.1.11). Из данной теоремы следует, что по заданным мгновенным значениям y(k∆t) можно восстановить непрерывное сообщение y(t), пропуская импульсные значения его отсчетов через идеальный П-образный фильтр низкой частоты, имеющий полосу пропускания в диапазоне от 0 до Fmax. Процесс восстановления непрерывного сообщения по заданным выборкам (отсчетам) называется сглаживанием (инте поляцией). Принцип дискретизации Железнова Н.А. используется для определения максимального интервала квантования (интервала между отсчетами) для случайного сигнала: стационарные случайные сигналы могут быть предсказаны системой линейного прогнозирования со среднеквадратичной ошибкой, мало отличающейся от нуля, толь в промежутке времени, равном τ0. То есть, для непрерывного сигнала конечной длительности Т (при Т » τ0) число некоррелированных отсчетов не превышало величины N=Т/ τ0. Следовательно, дискретизация непрерывной функции с интервалом τ0 обеспечивает возможность безошибочного восстановления значений непрерывной функции внутри интервалов τ0 с помощью системы линейного прогнозирования. Принцип дискретизации Железнова Н.А. может быть применен и для нестационарных случайных сигналов, для которых функция корреляции зависит от времени. Для них определяется текущий интервал корреляции, зависящий от эффективной полосы частот мгновенной спектральной плотности. некоррелированные отсчеты для нестационарной случайной функции располагаются неравномерно по оси времени. Железнов доказал, что произвольным нестационарным сигналам могут соответствовать непрерывным квазистационарным сигналам, которые могут быть представлены своими отсчетами через интервалы дискретизации с точностью, близкой к предельной точности, зависящей от структуры корреляционной функции. Выбор периода дискретизации по критерию наибольшего отклонения: в качестве воспроизводящих функций приняты степенные многочлены Лангранжа нулевой (ступенчатая аппроксимация) и первой (линейная аппроксимация) степени. Выбор периода дискретизации по критерию среднеквадратичного отклонения: выбираются точки, для которых среднеквадратичное отклонение будет наибольшим. Ступенчатая, линейная аппроксимация. Адаптивная дискретизация. Кратно-адаптивная дискретизация. Вопросы для самопроверки 1. Какими сигналами осуществляется передача информации в информационно – управляющих системах? 2. В чем преимущества передачи информации дискретными сигналами? 3. Какой процесс называется квантованием? 4. Как осуществляется квантование по уровню? 5. Как осуществляется квантование по времени? 6. Охарактеризуйте все используемые виды квантования. 7. Перечислите основные признаки методов дискретизации. 8. В чем сущность теоремы В.А. Котельникова? 9. В чем сущность принципа дискретизации Железнова Н.А.? 10. Охарактеризуйте критерии выбора периода дискретизации. ЛЕКЦИЯ 7. Аналоговые методы модуляции Цель лекции – изучение аналоговых методов модуляции. Задачи лекции - изучение методов непрерывной модуляции - изучение методов многократной непрерывной модуляции Вопросы, рассматриваемые на лекции 1. Виды переносчиков сигналов и их характеристики. 2. Изучение аналоговых методов модуляции. Для передачи и последующей обработки первичное сообщение необходимо нанести на подходящий материальный носитель. Чаще всего для этого используются процессы электромагнитной природы, имеющие непрерывный либо дискретный характер. Процесс нанесения информации на переносчик сводится к изменению характеристик используемого физического объекта в соответствии с первичным (принимаемым) сообщением. Процесс управления информационными параметрами переносчика называется модуляцией. В зависимости от вида и числа используемых информационных параметров переносчика, могут применяться различные виды модуляции. Обратная операция, заключающаяся в составлении исходного сообщения, называется демодуляцией (детекти ованием). Техническая реализация этих операций осуществляется с помощью функциональных преобразователей сигналов, называемых модулято ами и демодулято ами. Обычно эти устройства в рамках используемой информационной системы (ИС) образуют взаимосвязанную пару («модем»), работающую совместно с генератором сигналов – переносчиков. В зависимости характера их поведения во времени, переносчики информации можно поделить на три типа: стациона ные, га монические пе еносчики (колебания и волны), импульсные последовательности. Стациона ные характеризуются наличием постоянства во времени своего исходного состояния (уровня). Они имеют один информационный параметр - уровень. Модуляция такого рода переносчиков называется п ямой модуляцией (ПМ) (рис. 3.3). К га моническим пе еносчикам (колебания и волны) относят процессы, происходящие в отсутствии модуляции по гармоническому закону (рис.3.4). В качестве информационных параметров могут выступать амплитуда A, частота ω, фаза φ. Соответственно, различают амплитудную, частотную и фазовую модуляции (АМ, ЧМ, ФМ) (рис.3.5). Виды непрерывной модуляции. Если под действием первичного сигнала информационные параметры переносчика изменяются непрерывно, то такая модуляция называется неп е ывной. В качестве переносчика при осуществлении непрерывной модуляции чаще всего используют процессы в виде гармонических колебаний. Амплитудная модуляция и ее особенности. Амплитудная модуляция (АМ) осуществляется путем изменения амплитуды несущей пропорционально мгновенным значениям первичного сигнала (рис.3.7а, б). Аналитически переменный гармонический переносчик (несущая): UH(t) = U0cos (ωt+φ0). Модулируемый нормированной функцией первичный сигнал Uc(t) = cosΩt. Гармоническая функция с изменяющейся во времени амплитудой: UAM(t) = U(t)·cos(ωt+φ) = U0(1+m·cosΩt)·cos(ωt+φ); где m=∆U/U0 – коэффициент (глубина) модуляции. Случай, когда m>1 называется ежимом пе емодуляции, и является нежелательным, поскольку приводит к нелинейным искажениям результирующего (модулируемого) колебания, поэтому практически целесообразными являются режимы при которых m≤1. Спектр полученного АМ-сигнала в случае гармонической модуляции с частотой Ω, кроме несущей ω0, будет содержать частоты (ω0+Ω). Всякое модулируемое колебание уже не является чисто гармоническим и имеет сложный спектральный состав. Спектр АМ-колебаний при гармонической модуляции представлен на рис.3.9. При негармоническом характере первичного модулирующего сигнала в диапазоне ΩН≤ ω ≤Ωв, спектр АМК имеет сложный вид. Он содержит несущую ω 0 и две боковые полосы частот: нижнюю (НБП) и верхнюю (ВБП), содержащие частоты в диапазоне (ω0-Ωв, ω0-Ωн) и (ω0+Ωн, ω0+Ωв), где Ωн,Ωв – нижняя и верхняя границы спектра первичного сигнала (рис.3.10). В зависимости от того осуществляется передача всего спектра амплитудномодулированного сигнала, или только его части, различают такие виды амплитудной модуляции (АМ): 1. Амплитудная модуляция с двумя боковыми полосами (АМ с ДБП) 2. Амплитудная модуляция с одной боковой полосой (АМ с ОБП) 3. Балансовая модуляция (БМ) (амплитудная модуляция без несущей) Из рисунков 3.6. и 3.7 следует, что полезная информация содержится только в боковых полосах НБП и ВБП, где имеются частоты Ω. Мощность каждой из спектральных составляющих АМ-сигнала определяется квадратом ее амплитуды. Соответственно, мощность составляющей на частоте несущей ω 0 WH ~ U02, тогда мощность информационных частот из БП существенно меньше: WБП ~ (m/4)·U02, то есть зависит от глубины m амплитудной модуляции: WБП/WH ~(m2/4)«1 при m‹1. Полярная модуляция является частным случаем амплитудной модуляции – положительные полупериоды несущей модулируются одним первичным сигналом, а отрицательные – другим (рисунок 3,11, а-г). Двукратные непрерывные модуляции. Для повышения помехоустойчивости амплитудной модуляции (АМ) сигналов можно использовать их дополнительную модуляцию еще и по частоте, в этом случае возникает двойная модуляция АМ-ЧМ. При этом сначала первая несущая модулируется по амплитуде на частоте первого переносчика (называемого поднесущей). Полученный в результате этого амплитудно-модулируемый (АМ) сигнал используется для модуляции по частоте второго переносчика (называемого несущей). В некоторых случаях оказывается целесообразным использовать двукратную модуляцию в обратной последовательности ЧМ-АМ. В любом случае частотная модуляция обеспечивает помехоустойчивость, а амплитудная модуляция уменьшает полосу частот (спектр сигналов). В некоторых случаях используют ЧМ-ЧМ. Вопросы для самопроверки 1. Охарактеризуйте параметры переносчиков сигналов. 2. Какой процесс называется модуляцией? 3. Какой процесс называется демодуляцией? 4. Охарактеризуйте параметры непрерывного переносчика. 5. Охарактеризуйте амплитудные методы непрерывной модуляции. 6. Охарактеризуйте частотные методы непрерывной модуляции 7. Как осуществляются двукратные непрерывные модуляции? 8. Как осуществляется техническая реализация операций модуляции и демодуляции? 9. Какие виды двукратной непрерывной используются для повышения помехоустойчивости? 10. Охарактеризуйте методы полярной модуляции. ЛЕКЦИЯ 8. Импульсные методы модуляции. Цель лекции – изучение импульсных методов модуляции. Задачит и лекции - изучение амплитудно-импульсной модуляции - изучение время-импульсной модуляции Вопросы, рассматриваемые на лекции 1. Амплитудно-импульсная модуляция 2. Время-импульсная модуляция Импульсные методы модуляции, их виды. При использовании в качестве переносчиков импульсных последовательностей возникает возможность использования широкого ассортимента импульсных методов модуляции (ИМ): амплитудно-импульсная (АИМ), частотно-импульсная (ЧИМ), фазо-импульсная (ФИМ), широтно-импульсная (ШИМ) (рис.3.6). Модуляция параметров импульсных сигналов называется импульсной модуляцией (ИМ). Амплитудно-импульсная модуляция (АИМ). Частный спектр АИМсигналов в целом подобен спектру АМ. При этом τи= const; Fсл= = const; ∆FАИМ . Получение АИМ представлено на рис.3.12. К время-импульсной модуляции (ВИМ) относятся: частотно-импульсная модуляция, фазо-импульсная модуляция, широтно-импульсная модуляция, КИМ–кодоимпульсная модуляция. Широтно-импульсная модуляция (ШИМ). В данном случае информационным параметром является длительность (ширина импульсов) (рисунок 3.13, а-в). Нужно учитывать, что если ∆FАИМ , то в случае ШИМ ширина спектра сигнала ∆FШИМ Определение полосы пропускания требует учета величины τmin. Помехоустойчивость широтно-импульсной модуляции (ШИМ) существенно выше, чем для амплитудно-импульсной модуляции (АИМ), поэтому данный вид модуляции широко используется как в системах передачи данных, так и в системах автоматического управления (САУ). Фазо-импульсная модуляция (ФИМ). При фазо-импульсной модуляции под воздействием первичного сигнала происходит изменение положения импульсов модулируемой последовательности относительно тактовых позиций, при этом частота, длительность, амплитуда несущей не меняется: ∆t ~ ∆tMAX·sinΩt. Широтно-импульсная и фазоимпульсная модуляции (ШИМ и ФИМ) относятся к общему классу время-импульсной модуляции (ВИМ). Получение ФИМ-сигналов представлено на рисунке 3.14. Частотно-импульсная модуляция (ЧИМ). При получении ЧИМ-сигналов частота следования импульсов Fc (период повторения Tc) изменяется в соответствии с изменениями модулируемого сигнала: Fc Fo·sinΩt (или Tc~TcosinΩt). Кодо-импульсная модуляция (КИМ или ИКМ). В случае импульсно-кодовой модуляции исходные непрерывные сообщения предварительно квантуются по уровню и времени, и затем каждый дискретный уровень проквантованного первичного сигнала передается по каналу связи с помощью кодовых комбинаций двоичного кода, каждая из которых представляет собой группу импульсов постоянной амплитуды и длительности, отображающих числовое значение соответствующего уровня в двоичном коде. В случае импульсно-кодовой модуляции следует учитывать, что чем меньше шаг квантования, тем точнее будет передано исходное сообщение. Импульсно-кодовая модуляция (ИКМ) отличается наибольшей помехоустойчивостью по сравнению с другими видами импульсной модуляции, поэтому она находит наиболее широкое применение в СПД. Разновидностью импульсно-кодовой модуляции является ∆ - модуляция, при которой в каждый момент времени производится передача не текущих значений первичного сигнала, а только знака его приращения относительно предыдущих значений. В отличие от импульсно-кодовой модуляции, здесь каждый отсчет передается только с помощью двух дискретных сигналов, что существенно упрощает передачу, ускоряет ее и уменьшает необходимую полосу частот. Вопросы для самопроверки 1. Что называется импульсной модуляцией? 2. Охарактеризуйте параметры импульсного переносчика информации. 3. В чем заключается амплитудно-импульсная модуляция? 4. Какие методы относятся к время-импульсной модуляции? 5. В чем заключается широтно-импульсная модуляция? 6. В чем заключается частотно-импульсная модуляция? 7. В чем заключается фазо-импульсная модуляция? 8. В чем заключается кодо-импульсная модуляция? 9. В чем заключается Δ-модуляция? 10. Какой вид из импульсных методов модуляции обладает высокой помехоустойчивостью? . ЛЕКЦИЯ 9. Математические модели каналов связи Цель лекции – изучение математических моделей и основных характеристик каналов связи .Задачи лекции - изучение структуры, видов каналов связи, их математических моделей - изучение основных характеристик каналов связи Вопросы, рассматриваемые на лекции 1. Виды каналов связи, их математические модели 2. Основные характеристики каналов связи Каналом связи называется совокупность технических средств и физической среды, способной к передаче посылаемых сигналов, которая обеспечивает передачу сообщений от источника информации к получателю. Основными элементами каналов передачи данных в информационных сетях являются: 1. Оконечное обо удование данных (ООД), которое представляет собой блок, осуществляющий подготовку данных, предназначенный для передачи по каналу и служащий в одном случае источником данных, в другом – приемником. 2. С еда пе едачи данных (СПД), то есть любая физическая среда, способная передавать информацию с помощью соответствующих сигналов. Может представлять электрический или оптический кабель, или открытое пространство (физическое). 3. Аппа ату а пе едачи данных (АПД) представляет аппаратуру, непосредственно связывающую оконечное оборудование данных со средой передачи данных, являющееся пограничным оборудованием передачи данных. К аппаратуре передачи данных относятся модемы, сетевые адаптеры. 4. П омежуточное обо удование сети (ПОС) представляет аппаратуру, применяемую на линиях связи большой протяженности, которая позволяет решать следующие задачи: - улучшение качества сигнала; - обеспечение постоянства структуры канала связи между соседними узлами сети (мультиплексоры, повторители, трансляторы). Совокупность оконченного оборудования данных (ООД) и аппаратуры передачи данных (АПД) называется станцией данных. На рисунке 2.11 представлена типовая схема организации передачи данных 1) По форме представления передаваемой информации электрическими сигналами различают аналоговые и цифровые каналы передачи данных. В аналоговых каналах для согласования параметров среды передачи и сигналов применяют амплитудную, частотную, фазовую и квадратурно-амплитудную модуляцию. В цифровых каналах для передачи данных используют самосинхронизирующиеся коды, а для передачи аналоговых сигналов – кодо-импульсную модуляцию. В цифровых каналах передачи данных используют временное мультиплексирование, в аналоговых – частотное разделение. В наиболее общем случае всякий дискретный канал включает в себя непрерывный как составную часть. 2) Если влиянием мешающих факторов на передачу сообщений в канале можно пренебречь, то такой идеализированный канал называется каналом без помех. В таком канале каждому сообщению на входе однозначно соответствовало определенное сообщение на выходе и наоборот. 3) Если влиянием помех в канале пренебречь нельзя, то имеет место канал при наличии помех. 4) Канал, в котором вероятности отождествления первого сигнала со вторым и второго с первым одинаковы, называется симметричным. 5) Каналом со стиранием называется канал, алфавит сигналов на входе которого, отличается от алфавита сигналов на его выходе. 6) Каналом обратной связи называется дополнительный обратный канал, вводимый в СПД для повышения достоверности передачи (рис. 2.12). Канал связи считается заданным, если известны данные по сообщению на его входе, а также ограничения, которые накладываются на входные сообщения физическими характеристиками каналов. 7) По качеству канала связи: – качественные каналы связи, прокладываемые заново, используются между узлами в локальных сетях (локальные сети отличаются от глобальных малым расстоянием между узлами). – телефонные и телеграфные каналы общего назначения (уже существующие) используются во многих глобальных сетях. 8) По направлению передачи информации различают каналы связи: – симплексные каналы связи (КС) представляет такое представление обмена информацией между передатчиком и приемником, когда по одиночной линии связи (каналу) передаются сообщения только в одном направлении. Этот тип канала связи используется в теле- и радиосетях. – полудуплексные каналы связи (режимы работы) в этом случае 2 узла связи соединены одним каналом связи (линией связи), но по этому каналу происходит передача информации поочередно (попеременно) в противоположных направлениях – так организован режим работы. Этот метод используется в информационно–справочных и запросоответных системах. – дуплексный канал связи предполагает – одновременно два узла связи соединены двумя каналами (прямым и обратным), по которым информация передается одновременно в противоположных направлениях. Такие каналы связи используется в системах с РОС и ИОС. В телекоммуникационных системах различают выделенные (некоммутируемые) и коммутируемые на время передачи каналы связи. 9) В выделенных каналах связи приемо-передающая аппаратура постоянно соединена между собой. Это обеспечивает высокую степень готовности, более высокое качество передачи (связи) и поддержку большого объема трафика. 10) Коммутируемые каналы связи организуются только на время передачи некоторого фиксированного объема информации. Для таких каналов характерна высокая гибкость и сравнительно небольшая стоимость (при малом объеме трафика). Недостатки: потеря времени на коммутацию; возможность блокировки из-за занятости отдельных участков (линий связи); более низкое качество связи; большая стоимость трафика при больших его объемах. Под моделью канала понимается математическое описание канала, позволяющее оценить его характеристики, используемое при построении систем связи без проведения экспериментальных исследований. Для каналов передачи информации используют характеристику, называемую скоостью пе едачи инфо мации по каналам, которая характеризует среднее количество информации, которое может быть передано по каналу связи в единицу времени. Для характеристики каналов связи могут использоваться два варианта понятия скорости передачи: – техническая ско ость пе едачи (скорость манипуляции), характеризуется числом элементарных сигналов, передаваемых по каналу в единицу времени. Она зависит от свойств линий связи и быстродействия аппаратуры каналов. Единицей измерения технической скорости служит 1Бод = 1 символ/с. – инфо мационная ско ость пе едачи определяется средним количеством информации, передающейся в единицу времени. Эта скорость зависит как от характеристик данного канала, так и от характеристик используемых сигналов [бит/с]; Среднее количество информации, выдаваемое источником сообщений в единицу времени называется п оизводительностью источника. П опускной способностью канала связи называется наибольшая скорость передачи информации по этому каналу, достигаемая при самых совершенных способах передачи информации и приема. Пропускная способность, как и скорость передачи информации, измеряется количеством передаваемой информации в единицу времени. По пропускной способности каналы связи можно подразделить на низкоскоростные (глобальных сетей, скорость передачи от 50 до 200 бит/с), среднескоростные (магистральных сетей, объединяющих локальные сети в глобальные (несколько Гбит/с) и высокоскоростные (между узлами локальной сети (достигает 100 Мбит/с и сравнима со скоростью работы узлов). Вопросы для самопроверки 1. Что называется каналом связи? 2. Охарактеризуйте структуру канала связи. 3. Что представляет оконечное оборудование данных? 4. Охарактеризуйте среды передачи данных (СПД). 5. Что представляет аппаратура передачи данных (АПД)? 6. Для решения каких задач используется промежуточное оборудование канала? 7. По какому параметру каналы связи делятся на аналоговые и цифровые? 8. Для чего вводится канал обратной связи? 9. Что понимается под моделью канала? 10. Охарактеризуйте две основные характеристики каналов связи. ЛЕКЦИЯ 10. Информационные характеристики источников сообщений и каналов связи Цель лекции – изучение информационных характеристик источников сообщений и каналов связи .Задачи лекции - изучение информационных характеристик непрерывных и дискретных источников сообщений - изучение информационных характеристик каналов связи Вопросы, рассматриваемые на лекции 1. Информационные характеристики источников сообщений и каналов связи 2. Согласование параметров сигнала и канала связи. сточники неп е ывных сообщений характеризуются ансамблем реализаций случайного процесса. Под конкретным непрерывным сообщением Zт(t) подразумевают некоторую реализацию случайного процесса длительностью Т. Наиболее точной является модель непрерывного сообщения в виде эргодического случайного процесса. Под п оизводительностью источника неп е ывных сообщений Н(Z) понимается минимальное количество информации, которое необходимо создать источнику в единицу времени, чтобы любую реализацию Zт(t) можно было воспроизвести с заданной вероятностью. Неп е ывные КС - каналы, используемые для передачи непрерывных сигналов. Характеристики непрерывных КС случайным образом изменяются во времени. Широко используются гауссовы модели непрерывных КС. Под гауссовым каналом понимают ММ реального КС, построенную при следующих допущениях:1) физические параметры КС являются известными детерминированными величинами; 2) полоса частот ограничена частотой Fк, Гц; 3) в КС действует аддитивная флуктуационная помеха ограниченной мощности с равномерным частотным спектром и нормальным распределением амплитуд; 4) сигналы передаются с постоянной средней мощностью; 5) статистические связи между сигналами и шумом отсутствуют; 6) ширина спектра канала и помехи ограничена полосой пропускания канала. Информационные характеристики каналов связи – скорость передачи и пропускная способность канала связи. Ско ость пе едачи инфо мации по неп е ывному КС – это количество информации, которое передается в среднем принятыми непрерывными сигналами v(t), относительно переданных u(t) в единицу времени. Так как полоса пропускания КС всегда ограничена, непрерывные сообщения на достаточно продолжительном интервале времени Т с некоторой погрешностью могут быть представлены последовательностями отсчетов. Скорость передачи по непрерывному КС Ī(V,U)=limĨ(V,U), где Ĩ(V,U) – средняя скорость передачи информации дискретизированным сигналом. Так как степень воздействия помехи различна, различна и скорость передачи. П опускная способность канала связи – это максимально возможная скорость передачи информации по непрерывному КС с известными техническими характеристиками Сн=max Ī(V,U). Среднее количество информации, передаваемое сигналом vт(t), равно I(V,U)=Н(V)-НU(V), где Н(V) и НU(V) – соответственно априорная и апостериорная энтропии N-мерного случайного вектора V, составляющими которого являются случайные величины V1, V2, ..VN. Ско ость пе едачи инфо мации по диск етному КС – техническая (скорость манипуляции) и информационная (скорость передачи информации). Техническая скорость передачи Vт зависит от свойств ЛС и быстродействия аппаратуры КС. Информационная скорость передачи Ī(V,U) зависит от характеристик КС и от вероятности поступающих на вход символов и их статистической взаимосвязи. При известной Vт Ī(V,U) = Vт·I(V,U), где I(V,U) - среднее количество информации, переносимое одним символом. П опускная способность канала связи Сд равна той максимальной скорости передачи информации по данному каналу связи, которой можно достигнуть при самых совершенных способах передачи и приема Сд= max Ī(V,U)= Vт·I(V,U). При отсутствии помех имеет место равенство I(V,U)= I(U,V)=Н(U). Максимум возможного количества информации на символ равно log m – объем алфавита символов: Сд= Vт·log m. Следовательно, для увеличения скорости передачи информации по дискретному КС без помех до значения, равного пропускной способности КС необходимо, чтобы буквы сообщения преобразовывались в кодере таким образом, чтобы на его выходе различные символы появлялись бы равновероятно, и статистические связи между ними отсутствовали бы. Для увеличения Сд можно увеличить объем алфавита символов m, однако это вызывает сложность технической реализации. П опускная способность диск етного канала связи с помехами: нет однозначного соответствия между множествами V и U. Среднее количество информации, переносимое одним символом I(V,U) = Н(V)-НU(V) = Н(U)-НV(U). Если статистические связи между символами отсутствуют, энтропия сигнала на выходе ЛС Н(V) зависит от вероятности приема символов и логарифма по основанию два от этой вероятности. При наличии статистической связи энтропию определяют с использованием цепей Маркова. Цепь Маркова порядка n характеризует последовательность событий, вероятности которых зависят от того, какие n событий предшествовали данному. Эти n конкретных событий определяют состояние источника, в котором он находится при выдаче очередного знака. При объеме алфавита знаков l число R различных состояний источника не превышает ln. Вероятность выбора источником в состоянии Sq знака Zi обозначается через рq(Zi). Частная энтропия Н(Sq) зависит от рq(Zi). Усредняя эту величину по всем состояниям от 1до l, имеем энтропию источника сообщений Н(Z), характеризующую неопределенность, приходящуюся в среднем на один знак, выдаваемый источником. Если статистические связи между знаками полностью отсутствуют, то после выбора источником знака Zi его состояние не меняется R=1 следовательно, р(Sq)=1, энтропия источника Н(Z) определяется вероятностью р(Zi). Когда корреляционные связи наблюдаются между двумя знаками (простая цепь Маркова), максимальное число возможных состояний источника равно объему алфавита, и энтропия источника будет определяться условной вероятностью р(Zi/Zq). При наличии корреляционной связи между тремя знаками, состояние источника определится двумя предшествующими знаками, и энтропия источника Н(Z) будет определяться условной вероятностью р(Zi/ZkZh). Априорная энтропия характеризует уменьшение количества переданной информации вследствие возникновения ошибки. Скорость передачи информации по КС с помехами Ī(V,U) зависит от Vт и определяется вероятностью р(vjui). Пропускная способность дискретного канала связи с помехами – Сд = max Vт Ī(V,U). Степень загрузки КС определяется коэффициентом использования канала λ= Ī(Z)/Сд. Согласование па амет ов сигнала и канала связи. Чтобы оценить возможность передачи данного сигнала по конкретному каналу нужно соотнести характеристики канала с соответствующими характеристиками сигнала. Характеристиками сигнала являются: Tc – длительность сигнала, [c]; Fc – полоса частот (ширина спектра) сигнала, [Гц]; Hc – уровень превышения сигнала над помехой. Можно ввести понятие «объема сигнала» Vc, как произведение перечисленных характеристик: . Каждый конкретный канал связи обладает физическими параметрами, определяющими возможности передачи по этому каналу тех или иных сигналов. Независимо от конкретного типа и назначения каждый канал может быть охарактеризован тремя основными параметрами: ТК – время доступа канала, [с]; FK – полоса пропускания каналов, [Гц]; НК – допустимое превышение сигнала над помехами в канале. На основании этих параметров может быть получена интегральная характеристика – объем канала Vk: . Путем сравнения указанных параметров канала и сигнала (рисунок 2.13), можно получить необходимое и достаточные условия согласования канала связи и сигнала: . Откуда вытекает, что , то есть Следовательно, необходимое условие согласования сигнала и канала связи автоматически вытекает из достаточного условия. Если канал связи имеет полосу пропускания Fk меньшую, чем ширина спектра сигнала Fc, (Fk Fc), то ширину спектра сигнала можно привести в соответствие с частотными характеристиками канала связи за счет увеличения длительности сигнала: Fc Если широкополосный канал имеет ограниченное время доступа TK2. В этом случае алфавит разбивается не на две, а на q равномерных частей. Методика Шеннона-Фено не всегда приводит к однозначному построению кода, так как при ранжировании деление на подгруппы производится произвольно. От указанного недостатка свободна методика Хаффмена, она гарантирует однозначное построение кода с наименьшим для заданного распределения вероятностей средним числом символов на сообщение. Для случая бинарного кода метод Хаффмена сводится к следующему алгоритму: 1) буквы (знаки) алфавита А  а 1 а 2 а n  располагают в порядке убывания их вероятностей P1  P2  Pn ; 2) два последних самых маловероятных знака или сообщения объединяют в одно вспомогательное сообщение с вероятностью равной сумме вероятностей этих знаков или сообщений Р В  PN1  PN ; 3) полученный алфавит А  а 1 а 2 а n 2 b с вероятностями P1 , P2 , .., Pb снова располагают в порядке убывания вероятностей; 4) снова отбирают два сообщения в новой полученной последовательности, имеющие наименьшую вероятность, объединяют их в одно сообщение и вычисляют их суммарную вероятность; 5) повторяют шаги п.1,2 до тех пор, пока не получат единственное сообщение, вероятность которого равна единице. Кодовые комбинации для символов полученного алфавита z1, z2,…,z8 образуются следующим образом. Символу ставится в соответствие код «0», если символ при объеди/ нении во вспомогательное сообщение занимает верхнее положение (или нижнее), и ставится код «1» – если символ занимает нижнее положение (или верхнее). Кодовые символы записывают при этом справа налево. Более наглядно процесс такого кодирования можно изобразить с помощью кодового дерева. Алгоритм его построения: из точки, имеющей вероятность единица, направляют две ветви, причем ветви с наибольшей вероятностью присваивают символ 1, а с меньшей – 0. Такое последовательное ветвление продолжают, пока не дойдут до вероятности каждой буквы. Двигаясь по дереву, можно записать для каждой буквы её кодовую комбинацию. Недостатки систем эффективного декодирования. Одним из недостатков является различие в длине кодовых комбинаций: если моменты слияния информации с источником неуправляемы, а кодирующее устройство выдает через равные промежутки времени кодовые комбинации различной длины, для эффективного использования канала связи символы должны поступать в него с постоянной скоростью. Для этого на входе кодера источника должно быть предусмотрено буферное устройство – «упругая» задержка, которое должно записать сигналы, номера их поступления и выдавать в тракт канала с постоянной скоростью. Аналогичное устройство должно присутствовать и на приемной стороне. Другой недостаток связан с возникновением задержки в передаче информации. Наибольший эффект достигается при передаче длинными блоками, но это приводит к необходимости накапливать знаки прежде, чем поставить им в соответствие определенные комбинации. Аналогичная задержка возникает при декодировании. Общее время задержки может оказаться достаточно большим, особенно при появлении блока, вероятность которого мала. Это обстоятельство следует учитывать при выборе длины кодируемого блока. Третий недостаток заключается в специфическом влиянии помех на достоверность приёма. Какая-либо одиночная ошибка может превратить передаваемую кодовую комбинацию в другую, не равную ей по длительности, что может привести к неправильному декодированию ряда последующих комбинаций. Этот эффект называют треком ошибки. Специальными методами построения кода стараются свести трек ошибки к минимуму. Четвертый: относительная сложность технической реализации систем эффективного декодирования. Вопросы для самопроверки 1. Охарактеризуйте назначение эффективных кодов. 2. Охарактеризуйте алгоритм построения кода Шеннона - Фено. 3. В чем недостаток алгоритма Шеннона – Фено? 4. Чему равна средняя длина кодовых комбинаций Шеннона – Фено? 5. Охарактеризуйте алгоритм построения кода Хаффмена. 6. Как образуются кодовые комбинации кода Хаффмена? 7. Какие преимущества имеет построение при кодировании кодового дерева? 8. Приведите алгоритм построения кодового дерева. 9. Как образуются кодовые комбинации при построении кодового дерева? 10. Охарактеризуйте недостатки систем эффективного кодирования ЛЕКЦИЯ 13. Помехоустойчивое кодирование Цель лекции – изучение методики построения корректирующих кодов .Задачи лекции - изучение видов корректирующих кодов - изучение методики построения кодов Хэмминга Вопросы, рассматриваемые на лекции 1. Виды корректирующих кодов, коды Хэмминга 2. Особенности адаптивных систем передачи данных Если кодовые комбинации составлены так, что они отличаются друг от друга на кодовое расстояние d ≥ 3, то они образуют корректирующий код, который позволяет по имеющейся в кодовой комбинации избыточности обнаруживать и исправлять ошибки. Корректирующие коды делятся на систематические и несистематические. Систематическим или линейным кодом называется код, имеющий постоянную длину и четкое деление всех кодовых элементов на информационные k и контрольные т элементы, занимающие определенные места в комбинациях. Коды Хэмминга. Эти коды позволяют обнаруживать и исправлять все одиночные ошибки (при d = 3), а также исправлять все одиночные ошибки и обнаруживать все двойные ошибки (при d = 4), но не исправлять их. Рассмотрим код Хэмминга, исправляющий все одиночные ошибки. В качестве исходного кода берется двоичный код на все сочетания с числом информационных символов k, к которому добавляется т контрольных символов. Таким образом, общая длина закодированной комбинации n=k+m. Рассмотрим теперь последовательность кодирования и декодирования по методу Хэмминга. Построение кода. Оп еделение числа конт ольных символов. Для этого можно воспользоваться следующими рассуждениями. При передаче по каналу с шумами может быть или искажен любой из п символов кода, или слово может быть передано без искажений. Таким образом, может быть n+l вариантов искажения (включая передачу без искажений). Используя контрольные символы, мы должны различить все п+1 случаев. С помощью т контрольных символов можно описать 2т событий. Значит, должно быть выполнено условие: 2m ≥ n+1=k+m+1. В табл. 2 представлена зависимость между k и т, полученная из этого неравенства. Таблица 2 Число контрольных символов m в коде Хемминга в зависимости от числа информационных символов k k 1 2 3 4 5 6 7 8 9 10 11 12 13 m 2 3 3 3 4 4 4 4 4 4 4 5 5 Размещение конт ольных символов. Так как произвольное месторасположение контрольных символов будет затруднять проверку принятого кода, для удобства обнаружения искаженного символа целесообразно размещать их на местах, кратных степени 2, т. е. позициях 1, 2, 4, 8 и т. д. Информационные символы располагаются на оставшихся местах. Поэтому, например, для семиэлементной закодированной комбинации можно записать: m1m2k4m3k3k2k1, где k4 – это старший или четвертый разряд исходной кодовой комбинации двоичного кода, подлежащей кодированию; k1 – младший или первый разряд. Оп еделение состава конт ольных символов. Выявление того, какой символ должен стоять на контрольной позиции (1 или 0), производится по коэффициентам при помощи проверки на четность. Рассмотрим определение коэффициентов на примере. В табл. 3 выписывают все кодовые комбинации (исключая нулевую) для четырехразрядного двоичного кода на все сочетания и рядом, справа, сверху вниз проставляют символы комбинации кода Хэмминга. Таблица 3 Кодовые комбинации для четырехразрядного двоичного кода на все сочетания Разряды двоичных чисел Символы кода 4(k4) 3(k3) 2(k2) 1(k1) 1 m1 1 m2 1 1 k4 1 m3 1 1 k3 1 1 k2 1 1 1 k1 Из таблицы 3 составляют таблицу 4, в которую выписывают символы в три строки в следующей закономерности. В первую строку таблицы 4 записываются те символы кода, против которых проставлены единицы в младшем (первом k1) разряде комбинации двоичного кода в таблице 3 (т1,k4, k3 и k1). Во вторую строку проверочных коэффициентов (табл. 4) записываются символы кода, против которых стоит 1 во втором разряде (k2) двоичного кода (т2,k4, k2 и k1). В третью строку табл. 4 записываются символы кода, против которых стоят единицы в третьем разряде двоичных комбинаций (т3,k3, k2 и k1). Таблица 4 Проверочная таблица для кода Хемминга Контрольные Информационные символы кода символы кода т1  k4  k3  k1 т2  k4  k2  k1 т3  k3  k2  k1 В случае кодирования более длинных кодовых комбинаций табл. 3 и табл. 4 должны быть расширены, так как должны быть записаны четвёртая, пятая и т. д. строки проверочных коэффициентов. Для этого нужно лишь увеличить число разрядов двоичного кода в табл. 3. Так, для комбинации m1, m2, к11, т3, k10, k9, k8, m4, k7, k6, k5, k4, k3, k2, k1 табл. 4 будет состоять из четырех строк. Число проверок, а значит и число строк табл. 4 равно числу контрольных символов т. Нахождение состава конт ольных символов п и помощи п ове ок производится следующим образом. Суммируются информационные символы, входящие в каждую строку табл. 4. Если сумма единиц в данной строке четная, то значение символа т, входящего в эту строку, равно 0, если нечетная, то – 1. При помощи первой строки табл. 4 определяется значение символа m1, при помощи второй строки – значение т2, третьей – т3. Декодирование. Для проверки правильности принятой комбинации снова используется метод проверки на четность по коэффициентам табл. 4. Если комбинация принята без искажения, то сумма единиц по модулю 2 дает нуль. При искажении какого-либо символа суммирование при проверке дает единицу. По результату суммирования каждой из проверок составляется двоичное число, указывающее на позицию искаженного символа кода. Например, первая и вторая проверки показали наличие искажения, а суммирование при третьей проверке дало нуль. Число 0112 = 310 означает, что в третьем символе кодовой комбинации, включающей и контрольные символы (счет производится слева направо), возникло искажение, поэтому этот символ нужно исправить на обратный ему, т. е. 1 переправить на 0 или 0 на 1. После этого контрольные символы, стоящие на заранее известных местах, отбрасываются. Дополнительные контрольные символы, которые необходимо посылать для повышения помехоустойчивости кода, увеличивают длину кодовой комбинации, вследствие чего появляются дополнительные или избыточные кодовые комбинации, не используемые непосредственно для передачи информации. Так семиразрядный код принципиально обеспечивает передачу 27 = 128 кодовых комбинаций, однако, количество информационных символов в семиразрядном коде Хэмминга k=4, т. е. полезных информационных посылок всего Nk = 24=16. Остальные 112 кодовых комбинаций из 128 предназначены для обеспечения помехоустойчивости кода и являются запрещенными. Таким образом, избыточность кода Хэмминга достаточно велика. Для семиразрядного кода Хэмминга избыточность (И=m/k) равна 3/4, причем с увеличением разрядности кода, избыточность уменьшается. Код Хэмминга с обнаружением и исправлением одиночной ошибки применяется в том случае, если статистика показывает, что наиболее вероятны одиночные искажения в канале связи. Если с некоторой вероятностью возможно искажение двух символов в кодовой комбинации, то целесообразно применение кода Хэмминга, позволяющего исправить одиночные ошибки, если была только одиночная ошибка, и обнаруживать двойные, если были две ошибки. Однако такой код при возникновении двух ошибок не может сначала обнаружить обе ошибки, а затем одну из них исправить. Этот код строится на базе кода, исправляющего одиночные ошибки путем добавления дополнительного контрольного символа к уже закодированной комбинации, который позволяет производить проверку на четность всей комбинации. Поэтому контрольный символ должен быть равен 1, если число единиц в закодированной комбинации нечетное, и 0, если число единиц четное. При проверках принятой комбинации возможно следующее: 1) ошибок нет (прием верен); это показывает, как общая проверка на четность, так и частные проверки (для примера частных проверок три); 2) одиночная ошибка; общая проверка на четность показывает наличие ошибки (сумма единиц по модулю 2, входящих в кодовую комбинацию, не дает нуль), а частные проверки комбинации без разряда mдоп укажут на номер искаженного символа (нулевое значение числа, полученное в результате проверки, свидетельствует об искажении в дополнительной контрольной позиции); 3) две ошибки; общая проверка на четность укажет на отсутствие ошибок, но частные проверки укажут на наличие ошибок (будет показан номер позиции, где якобы возникла ошибка, однако ее не следует исправлять, необходимо констатировать лишь наличие двух ошибок). Добавление дополнительного контрольного символа к уже закодированной для исправления одиночной ошибки кодовой комбинации увеличивает кодовое расстояние. Особенности адаптивных систем передачи данных. Недостатком многих корректирующих кодов является их слабая приспособленность к условиям передачи данных. Избыточность таких кодов постоянна и выбирается обычно из соображений требуемой верности (достоверности) при наихудших условиях передачи. Если избыточность кода привести в соответствие с реальным состоянием канала в данный промежуток времени, то можно существенно повысить эффективность канала без ущерба для достоверности передачи. Эта идея лежит в основе адаптивного кодирования и адаптивного декодирования. В случае адаптивного декодирования в зависимости от числа ошибок в принимаемых комбинациях, изменяют структуру и параметры алгоритмов декодирования, и функции декодеров. В свою очередь, для обеспечения адаптивного кодирования, кроме выполнения указанных процедур необходимо изменять структуру и параметры кодов, алгоритмов кодирования и самих кодеров. Функции адаптивных декодеров зависят от возможности организации обратного канала связи, а также от характера искажений сигналов, свойств помех, степени распределения ошибок и других факторов. Для построения систем адаптивного кодирования необходимо наличие канала обратной связи, с помощью которого на передающую сторону по- ступает информация о качестве канала и условиях передачи. Системы передачи данных (СПД) без канала обратной связи позволяют, в принципе достигать желаемой верности передачи информации путем использования соответствующих корректирующих кодов. Платой за обеспечение желаемой достоверности служит существенное увеличение длины кодовых комбинаций, а также усложнение аппаратуры систем передачи данных. Недостатком систем без обратной связи является также и то, что источник не получает никаких подтверждений о том, как принята информация в приемниках. Поэтому в таких системах предъявляются очень высокие требования к надежности используемой аппаратуры. Исходя из этого, системы без обратной связи применяются в первую очередь тогда, когда невозможно организовать канал обратной связи или недопустимы задержки при передаче информации. В силу указанных обстоятельств, широкое распространение получили системы с обратной связью, в которых достоверность передачи повышается за счет обнаружения ошибок на приемной стороне и повторения только неправильно принятых кодовых комбинаций. Адаптивное управление повторением информации существенно приближает избыточность кода к информационному пределу. При этом избыточность будет минимальной при отсутствии ошибок и будет увеличиваться с ростом их числа. Системы с обратной связью, в зависимости от способа организации обратной связи, делятся на системы с информационной обратной связью (ИОС), и системы с решающей обратной связью (РОС). Вопросы для самопроверки 1. Какой код называется корректирующим? 2. Благодаря чему корректирующий код имеет способность исправлять ошибки? 3. Как подразделяются корректирующие коды? 4. Какой код называется систематическим или линейным кодом? 5. Для каких целей используют коды Хэмминга? 6. Как влияет кодовое расстояние на возможности кода? 7. Охарактеризуйте алгоритм кодирования по Хэммингу при d=3. 8. Охарактеризуйте алгоритм декодирования по Хэммингу при d=3.. 9. Какие системы передачи данных называются адаптивными? 10. В чем особенности адаптивных систем передачи данных? ЛЕКЦИЯ 14. Блоковые коды Цель лекции – изучение особенностей блоковых кодов Задачи лекции - изучение видов блоковых кодов - изучение принципов построения блоковых кодов Вопросы, рассматриваемые на лекции 1. Виды блоковых кодов. Принципы использования избыточности. Связь корректирующей способности кода с кодовым расстоянием. 2. Геометрическая интерпретация блоковых корректирующих кодов. Показатели качества корректирующего кода. Корректирующие коды отличаются введением избыточности, которая позволяет выбрать передаваемые последовательности символов так, что проверка их на приемной стороне дает возможность обнаружить и исправить ошибки. Это свойство помехоустойчивых кодов проявляется следствием их алгебраической структуры. Алгебраические коды делятся на два больших класса: блоковые и непрерывные. В случае блоковых кодов процедура кодирования заключается в сопоставлении каждой букве сообщения блока из n символов. В операциях по преобразованию принимают участие только символы сообщения, и выходная последовательность не зависит от других символов в передаваемом сообщении. Блоковый код называется равномерным, если длина блока n остается постоянной для всех букв сообщения. Различают разделимые и неразделимые блоковые коды. При кодировании разделимыми кодами выходные последовательности состоят из информационных символов, совпадающих с символами, поступающими на вход кодера канала, и проверочных символов, вводимых кодером канала и служащих для обнаружения и исправления ошибок. При кодировании неразделимыми кодами разделить символы выходной последовательности на информационные и проверочные невозможно. Непрерывными (древовидными) называют такие коды, в которых введение избыточных символов в кодируемую последовательность информационных символов осуществляется непрерывно, без разделения ее на независимые блоки. Непрерывные блоки также могут быть разделимыми и неразделимыми. Наиболее простыми для технической реализации являются рекуррентные (сверточные) коды. П инципы использования избыточности. На вход кодирующего устройства поступает последовательность из k информационных двоичных символов, на выходе ей соответствует последовательность из n двоичных символов, при чем n˃ k. Всего может быть 2k различных входных, 2n различных выходных последовательностей. Из числа 2n выходных последовательностей только 2k соответствуют входным. Это разрешенные кодовые комбинации. 2n - 2k не используются, называются запрещенными. Взаимно независимыми ошибками называются такие искажения в передаваемой последовательности, при которых вероятность появления любой комбинации искаженных символов зависит только от числа искаженных символов r и вероятности искажения одного символа р. Кратностью ошибки называют количество искаженных символов в кодовой комбинации. Связь ко екти ующей способности кода с кодовым асстоянием. Кодовое асстояние. инимальное кодовое асстояние. Для исправления всех ошибок кратности s и одновременного обнаружения всех ошибок кратности r (r≥s) минимальное хеммингово расстояние между разрешенными комбинациями нужно выбирать из условия d≥r+s+1. Геомет ическая инте п етация блоковых ко екти ующих кодов. Показатели качества ко екти ующего кода. Вопросы для самопроверки 1. Охарактеризуйте разновидности блоковых корректирующих кодов. 2. Какие коды называют алгебраическими? 3. Охарактеризуйте разновидности алгебраических кодов. 4. Какой код называется блоковым? 5. Какой блоковый код называется равномерным? 6. Какие коды называют непрерывными (древовидными)? 7. Поясните принципы использования избыточности. 8. Каким образом корректирующая способность кода связана с кодовым расстоянием? 9. Что называют кратностью ошибки? 10. Охарактеризуйте показатели качества корректирующего кода. . ЛЕКЦИЯ 15. Систематические коды Цель лекции – изучение особенностей систематических кодов Задачи лекции - изучение особенностей линейных кодов - изучение принципов построения двоичного группового кода. Вопросы, рассматриваемые на лекции 1. Линейные коды. 2. Двоичный групповой код. Самый большой класс разделимых кодов составляют линейные коды, у которых значения проверочных символов определяются в результате проведения линейных операций над определенными информационными символами. Для случая двоичных кодов каждый проверочный символ выбирают таким, чтобы его сумма с определенными информационными символами была равна нулю. Символ проверочной позиции имеет значение 1, если число единиц информационных разрядов, входящих в данное проверочное равенство, нечетно, и 0, если оно четно. Число проверочных равенств и номера конкретных информационных разрядов, входящих в каждое из равенств, определяются тем, какие и сколько ошибок должен исправлять или обнаруживать данный код. Проверочные символы могут располагаться на любом месте кодовой комбинации. При декодировании определяется справедливость проверочных равенств. В случае двоичных кодов такое определение сводится к проверкам на четность числа единиц среди символов, входящих в каждое из равенств. Совокупность проверок дает информацию о том, имеется ли ошибка, а в случае необходимости и о том, на каких позициях символы искажены. Любой двоичный код является групповым, так как совокупность входящих в него кодовых комбинаций образует группу. Построение двоичного группового корректирующего кода производят, исходя из требуемого объема кода Q, то есть необходимого числа передаваемых команд или дискретных значений измеряемой величины и статистических данных о наиболее вероятных векторах ошибок в используемом канале связи. Вектором ошибки называют n-разрядную двоичную последовательность, имеющую единицы в разрядах, подвергшихся искажению, и нули во всех остальных разрядах. Любую искаженную кодовую комбинацию можно т.о. рассматривать как сумму по модулю 2 исходной разрешенной кодовой комбинации и вектора ошибки. Число информационных разрядов k, необходимое для передачи заданного числа команд обычным двоичным кодом, определяется из неравенства 2k-1≥Q. Далее определяется число проверочных разрядов и номера информационных разрядов, входящих в каждое из равенств для определения символов в проверочных разрядах. Определяют символы опознавателя (некоторая контрольная последовательность символов). Количество подлежащих исправлению ошибок является определяющим для выбора числа избыточных символов n-k, их должно быть достаточно для того, чтобы обеспечить необходимое число опознавателей. Пользуясь таблицей опознавателей одиночных ошибок в каждом из разрядов, определяют символы разрядов, входящие в проверки на четность. Сумма любых двух опознавателей единичных ошибок дает ненулевой опознаватель, что является признаком наличия ошибки. Вопросы для самопроверки 1. Какие коды называют линейными? 2. Как выбирают проверочные символы для случая двоичных кодов? 3. По какому правилу определяется значение символа проверочной позиции? 4. Чем определяется число проверочных равенств? 5. На каких местах кодовой комбинации могут располагаться проверочные символы? 6. Как при декодировании определяется справедливость проверочных равенств? 7. Какой код называют групповым? 8. Что называется требуемым объемом кода? 9. Что называют вектором ошибки? 10. Поясните алгоритм построения двоичного группового кода.. ЛЕКЦИЯ 16. Циклические коды Цель лекции – изучение особенностей циклических кодов Задачи лекции - изучение принципов построения циклических кодов - изучение вопросов использования циклических кодов для обнаружения и исправления ошибок Вопросы, рассматриваемые на лекции 1. Выбор образующего многочлена 2. Обнаружение и исправление ошибок Любой групповой код может быть записан в виде матрицы, включающей k линейно независимых строк по n символов. Циклическим называется код, у которого строки образующей матрицы связаны дополнительным условием цикличности. Все строки образующей матрицы такого кода могут быть получены циклическим сдвигом одной кодовой комбинации, называемой образующей для данного кода. Сдвиг осуществляется справа налево, причем крайний левый символ каждый раз переносится в конец комбинации. Число возможных циклических кодов значительно меньше числа различных групповых кодов. При описании циклических кодов n-разрядные кодовые комбинации представляются в виде многочленов фиктивной переменной х. Показатели степени у х соответствуют номерам разрядов (начиная с нулевого), а коэффициенты при х – в общем случае- элементы поля GF(q). Для двоичных кодов коэффициенты – цифры 0 и 1. Наибольшую степень х в слагаемом с ненулевым коэффициентом называют степенью многочлена. Действия над кодовыми комбинациями сводится к действию над многочленами. Суммирование многочленов осуществляется с приведением коэффициентов по модулю два. Циклический сдвиг многочлена степени n-k без переноса единицы в конец кодовой комбинации соответствует простому умножению на х. Т ебования к об азующему многочлену. Выбо об азующего многочлена по заданному объему кода и заданной ко ектиующей способности. Обна ужение одиночных ошибок. сп авление одиночных ошибок или обна ужение двойных ошибок. Обна ужение ошибок к атности т и и ниже. обнаужение и исп авление независимых ошибок п оизвольной к атности. Обна ужение и исп авление пачек ошибок. етоды об азования циклического кода. ат ичная запись циклического кода. Уко оченные циклические коды. Вопросы для самопроверки 1. Какой код называют циклическим? 2. Какая матрица называется образующей для данного кода? 3. Как может быть получена образующая матрица? 4. Что представляют собой кодовые комбинации при описании циклических кодов? 5. Какой многочлен называют образующим? 6. Какие действия можно произвести над кодовыми комбинациями? 7. Перечислите требования к образующему многочлену. 8. Как осуществляется выбор образующего многочлена для заданной корректирующей способности? 9. Поясните методы образования циклического кода. 10. Какие коды называются укороченными циклическими кодами? ЛЕКЦИЯ 17. Методы сжатия информации Цель лекции – изучение методов сжатия информации. Задачи лекции - изучение методов сжатия информации без потерь - изучение методов LZW и MNP Вопросы, рассматриваемые на лекции 1. Методы сжатия информации без потерь 2. Методы LZW и MNP Передача избыточной информации приводит к нерациональной загрузке каналов связи, расходу энергетических, аппаратурных и вычислительных ресурсов, а также емкости запоминающих устройств. Предпосылкой сжатия данных служит теорема кодирования К. Шеннона для каналов связи без помех: средняя длина кодовых комбинаций может быть сколь угодно близкой к энтропии источника сообщений Н(Х). Методы сжатия обеспечивают снижение избыточности, вызванной как неравной априорной вероятностью символов, так и их взаимной корреляцией. В первом случае для кодирования исходных символов используют неравномерный код. При этом часто появляющиеся символы кодируются более коротким кодом, а менее вероятные – более длинным кодом. Во втором случае, для устранения избыточности, вызванной корреляцией между символами, переходят от кодирования отдельных символов к кодированию групп этих символов. За счет этого происходит укрупнение алфавита источника, то есть увеличение его объема. Общая избыточность при этом не изменяется, избыточность, вызванная корреляцией между символами, переходит в другой вид – обусловленной неравномерностью появления различных групп символов. То есть процесс устранения избыточности сводится к двум операциям – декорреляции (укрупнению алфавита) и кодированию оптимальным неравномерным кодом. Метод сжатия информации с потерями реализуется в формате MPEG 2 и MPEG 3, используется в мультимедиа системах. Методы сжатия данных без потерь используется в телекоммуникационных системах передачи информации. Алго итмы сжатия данных без поте ь: кодирование повторов (для сжатия графических файлов), вероятностные методы сжатия (Шеннона-Фано и Хаффмена - статические и динамические), арифметические методы (строка символов заменяется действительным числом), метод словарей (LZ-LZW). Т ебования к модемной еализации методов сжатия. Алго итм аботы коде а LZW. Сжатие данных в п отоколах MNP (MNP5, MNP7). Вопросы для самопроверки 1. К чему приводит передача избыточной информации? 2. Какая теорема служит предпосылкой сжатия данных? 3. Какие методы сжатия обеспечивают снижение избыточности, вызванной неравной априорной вероятностью символов? 4. Какие методы сжатия обеспечивают снижение избыточности, вызванной взаимной корреляцией между символами? 5. К каким операциям сводится процесс устранения избыточности, вызванной взаимной корреляцией между символами? 6. Охарактеризуйте алгоритмы сжатия данных без потерь. 7. Перечислите требования к модемной реализации методов сжатия. 8. Объясните алгоритм работы кодера LZW. 9. Охарактеризуйте сжатие данных в протоколе MNP5. 10. Охарактеризуйте сжатие данных в протоколе MNP7. ЛЕКЦИЯ 18. Основы криптографии Цель лекции – изучение криптографических систем зашиты информации Задачи лекции - изучение видов криптографических систем защиты информации - изучение методов обеспечения секретности информации Вопросы, рассматриваемые на лекции 1. Криптографические алгоритмы и протоколы защиты информации 2. Виды криптографических систем защиты информации 3. Оценка стойкости криптосистем. Системы шифрования Криптографическим алгоритмом защиты информации называется последовательность действий, обеспечивающая преобразование защищаемой информации по правилу, заданному ключом (шифрование (дешифрование) сообщений, формирование и проверка аутентификаторов сообщений, генерация ключей, необходимых для выполнения других криптоалгоритмов). Нарушение (взлом) криптографического алгоритма – событие, при котором нарушитель, не знающий секретной ключевой информации криптоалгоритма, способен систематически срывать цель защиты информации. Криптографический протокол зашиты информации – совокупность используемых криптографических алгоритмов и правил их выполнения, определяющих порядок взаимодействия участников информационного обмена для достижения определенной цели защиты информации. Криптографические протоколы играют важную роль в криптографии, так как ориентированы на обеспечение безопасного взаимодействия участников информационного обмена. Многочисленные примеры нарушения безопасности информации в современных защищенных информационных системах чаще всего относятся к различным нарушениям (взлому) криптопротоколов. Нарушение (взлом) криптографического протокола - событие, при котором нарушитель, не обладающий возможностью взломать непосредственно сами используемые в протоколе криптоалгоритмы, используя слабости протокола, способен сорвать цель защиты информации. Криптографическая система зашиты информации – совокупность используемых криптографических алгоритмов, протоколов и процедур формирования, распределения, передачи и использования криптографических ключей. Ключи можно рассматривать как выбранные из множества возможных для использованных криптоалгоритмов конкретных пар криптопреобразований, выполняемых участниками информационного обмена. Криптографической стойкостью системы защиты информации называется ее способность противостоять атакам противоборствующей стороны. Классификация к иптог афических систем защиты инфо мации В соответствии с выполняемыми задачами по защите информации можно выделить два основных класса криптографических систем:  криптосистемы, обеспечивающие секретность информации;  криптосистемы, обеспечивающие подлинность (аутентичность) информации.  Криптосистемы, обеспечивающие секретность информации, разделяются на системы шифрования и системы криптографического кодирования информации.  В общем случае шифрование сообщения (информации) есть обратимое преобразование сообщения, не зависящее от самого сообщения, с целью скрытия его содержания. Зашифрованное сообщение называется шифрограммой. Преобразование сообщения в шифрограмму описывается функцией шифрования; преобразование шифрограммы в сообщение описывается функцией дешифрования. Другим методом обеспечения секретности информации является криптографическое кодирование. Криптографическое кодирование информации есть в общем случае преобразование по ключу сообщений в кодограммы, зависящее от самих сообщений, с целью скрытия их содержания. Защита информации по ключу основана на использовании ее избыточности. Термин «криптографическое кодирование» используется, чтобы подчеркнуть отличие этого вида криптографического преобразования от других видов некриптографических преобразований информации, таких как помехоустойчивое кодирование и эффективное кодирование.  Криптосистемы аутентификации информации предназначены для контроля ее подлинности, но в ряде случаев они способны эффективно обеспечить контроль целостности сообщений при различных деструктивных воздействиях.  Данный класс криптосистем может быть разделен в зависимости от решаемой задачи на системы аутентификации информации (сообщений) и системы аутентификации источников информации (корреспондентов, пользователей, сетей, систем и т. п.). Методы аутентификации информации различаются в зависимости от условий обеспечения подлинности информации. Оценка стойкости к иптосистем. При оценке стойкости произвольных криптографических систем защиты информации обычно придерживаются принципа Керкхоффа: стойкость криптосистемы должна быть обеспечена и тогда, когда нарушителю известно полное ее описание. Для оценки стойкости криптографических систем защиты информации используются различные подходы, среди которых наибольший интерес представляют информационно-теоретический, сложностно - теоретический и системный подходы. Среди средств защиты информации от возможных атак нарушителя выделяются средства криптографической защиты информации. На них могут возлагаться следующие основные задачи:  обеспечение секретности (конфиденциальности) передаваемой, обрабатываемой и хранимой информации;  обеспечение целостности передаваемой, обрабатываемой и хранимой информации;  обеспечение подлинности сообщений и корреспондентов (пользователей), а также подлинности взаимодействующих сетей и систем;  установление авторства передаваемых и хранимых сообщений;  обеспечение доступности для законных корреспондентов (пользователей) информации, ресурсов и услуг;  обеспечение целостности самих средств криптографической защиты информации.  Принципы построения криптографических систем защиты информации основаны на использовании математических функций специального вида, которые должны легко вычисляться законными пользователями, знающими «ключ», и очень сложно для всех не обладающих ключом.  одели к иптог афических систем.. Системы шиф ования  Среди криптографических систем, обеспечивающих сохранение информации в тайне, наибольшее распространение получили системы шифрования информации.  Системы шифрования информации разделяются на два больших класса: симметричные и несимметричные.  Для приближения характеристик реальных шифраторов к характеристикам идеального используют сжатие сообщений до шифрования и рандомизацию шифруемых сообщений. Идея рандомизации заключается в уменьшении избыточности шифруемых сообщений за счет специального кодирования, обеспечивающего равную вероятность появления символов, но длина сообщений при этом увеличивается. Основной характеристикой шифра является криптостойкость, которая обычно определяется интервалом времени, необходимым для раскрытия шифра. К шифрам, исполь зуемым для криптографической защиты информации, предъявляется ряд требований:  достаточная криптостойкость (надежность закрытия данных);  простота процедур шифрования и расшифрования;  незначительная избыточность информации за счет шифрования;  нечувствительность к небольшим ошибкам шифрования и др. В той или иной мере этим требованиям отвечают шифры перестановок, шифры замены, шифры гаммирования и шифры, основанные на аналитических преобразованиях шифруемых данных. Шифрование перестановкой заключается в том, что символы исходного текста переставляются по определенному правилу в пределах некоторого блока этого текста. Шифрование заменой (подстановкой) заключается в том, что символы исходного текста заменяются символами того же или другого алфавита в соответствии с заранее обусловленной схемой замены. Возможны моно- и многоалфавитные подстановки. Шифрование гаммированием заключается в том, что символы исходного текста складываются с символами некоторой псевдослучайной последовательности, именуемой гаммой шифра. Примером может служить, поразрядное сложение сообщения и гаммы при формировании криптограммы . Стойкость шифрования определяется в основном длиной (периодом) неповторяющейся части гаммы шифра. Поскольку с помощью ЭВМ можно генерировать гамму шифра очень большой длины, то данный способ является одним из основных для шифрования информации в автоматизированных системах Алго итмы к иптог афической защиты инфо мации согласно ГОСТ 28147-89. В Российской Федерации принят ГОСТ 28147-89 «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования». Этот ГОСТ определяет алгоритм криптографической защиты информации для сетей передачи данных, вычислительных систем, ЭВМ и устройств обработки информации. Он предназначен для шифрования как секретной, так и конфиденциальной информации и не накладывает ограничений на гриф секретности обрабатываемой информации.  Шиф ование и дешиф ование данных в ежиме п остой замены.  Шиф ование и дешиф ование данных в ежиме гамми ования.  Шиф ование и дешиф ование данных в ежиме гамми ования с об атной связью.  Режим вы аботки имитовставки. Вопросы для самопроверки 1. В чем состоит принципиальное отличие криптографических и криптоаналитических методов? 2. Что называют криптографическим ключом? 3. Поясните сущность и сравните между собой криптографический алгоритм, криптографический протокол и криптографическую систему зашиты информации. 4. Что подразумевают под аутентификацией информации? 5. Перечислите криптографические функции? 6. В чем состоит принципиальное отличие симметричных и несимметричных систем шифрования информации? 7. Перечислите режимы защиты информации по ГОСТ28147-89? 8. В чем состоит существенное отличие методов защиты информации?