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

1 СИГНАЛЫ В СЕТЯХ ПЕРЕДАЧИ ИНФОРМАЦИИ 1.1 Модель взаимодействия открытых систем Теория информации занимается построением математических моделей систем передачи/хранения информации и анализом этих моделей с целью определения путей повышения эффективности их функционирования. Основные задачи, которые стоят при этом, заключаются в обеспечении максимальной скорости передачи информации при заданной вероятности ошибок. В начале 80-х годов ряд международных организаций по стандартизации разработали модель, которая сыграла значительную роль в развитии сетей. Эта модель называется моделью взаимодействия открытых систем (Open System Interconnection, OSI) или моделью OSI. Модель OSI определяет различные уровни взаимодействия систем, дает им стандартные имена и указывает, какие функции должен выполнять каждый уровень. В модели OSI (рис. 1.1) средства взаимодействия делятся на семь уровней: прикладной, представительный, сеансовый, транспортный, сетевой, канальный и физический. Каждый уровень имеет дело с одним определенным аспектом взаимо­действия сетевых устройств. 1. На прикладном уровне с помощью специальных приложений пользователь создает документ (сообщение, рисунок и т. п.). 2. На уровне представления операционная система фиксирует местонахождение созданных данных (в оперативной памяти, в файле на жестком диске и т. п.) и обеспечивает взаимодействие со следующим уровнем. 3. На сеансовом уровне компьютер пользователя взаимодействует с локальной или глобальной сетью. Протоколы этого уровня проверяют права пользователя на «выход в эфир» и передают документ к протоколам транспортного уровня. 4. На транспортном уровне документ преобразуется в ту форму, в которой положено передавать данные в используемой сети. Например, он может нарезаться на небольшие пакеты стандартного размера. 5. Сетевой уровень определяет маршрут движения данных в сети. Так, например, если на транспортном уровне данные были «нарезаны» на пакеты, то на сетевом уровне каждый пакет должен получить адрес, по которому он должен быть доставлен независимо от прочих пакетов. 6. Уровень соединения необходим для того, чтобы промодулировать сигналы, циркулирующие на физическом уровне, в соответствии с данными, полученными с сетевого уровня. Например, в компьютере эти функции выполняет сетевая карта или модем. 7. Реальная передача данных происходит на физическом уровне. Здесь нет ни документов, ни пакетов, ни даже байтов - только биты, то есть элементарные единицы представления данных. Восстановление документа из них произойдет постепенно, при переходе с нижнего на верхний уровень на компьютере клиента. Пусть приложение обращается с запросом к прикладному уровню, например к файловой службе. На основании этого запроса программное обеспечение прикладного уровня формирует сообщение стандартного формата. Обычное сообщение состоит из заголовка и поля данных. Заголовок содержит служебную информацию, которую необходимо передать через сеть прикладному уровню машины-адресата, чтобы сообщить ему, какие операции надо выполнить. В нашем случае заголовок, очевидно, должен содержать информацию о месте нахождения файла и о типе операции, которую следует выполнить. Поле данных сообщения может быть пустым или содержать какие-либо данные, например те, которые необходимо записать в удаленный файл. Но для того чтобы доставить эту информацию по назначению, предстоит решить еще много задач, ответственность за которые несут нижележащие уровни. После формирования сообщения прикладной уровень направляет его вниз по стеку представительному уровню. Протокол представительного уровня на основании информации, полученной из заголовка прикладного уровня, выполняет требуемые действия и добавляет к сообщению собственную служебную информацию — заголовок представительного уровня, в котором содержатся указания для протокола представительного уровня машины-адресата. Полученное в результате сообщение передается вниз сеансовому уровню, который в свою очередь добавляет свой заголовок, и т. д. (Некоторые реализации протоколов помещают служебную информацию не только в начале сообщения в виде заголовка, но и в конце, в виде так называемого «концевика».) Наконец, сообщение достигает нижнего, физического уровня, который собственно и передает его по линиям связи машине-адресату. К этому моменту сообщение «обрастает» заголовками всех уровней (рис. 1.2). Когда сообщение по сети поступает на машину-адресат, оно принимается ее физическим уровнем и последовательно перемещается вверх с уровня на уровень. Каждый уровень анализирует и обрабатывает заголовок своего уровня, выполняя соответствующие данному уровню функции, а затем удаляет этот заголовок и передает сообщение вышележащему уровню. В дальнейшем мы будем рассматривать только физический и канальный уровни. Средства физического уровня лежат за пределами компьютера. Физический уровень Физический уровень (Physical layer) имеет дело с передачей битов по физическим каналам связи, таким, например, как коаксиальный кабель, витая пара, оптоволоконный кабель или цифровой территориальный канал. К этому уровню имеют отношение характеристики физических сред передачи данных, такие как полоса пропускания, помехозащищенность, волновое сопротивление и другие. На этом же уровне определяются характеристики электрических сигналов, передающих дискретную информацию, например крутизна фронтов импульсов, уровни напряжения или тока передаваемого сигнала, тип кодирования, скорость передачи сигналов. Кроме этого, здесь стандартизуются типы разъемов и назначение каждого контакта. Функции физического уровня реализуются во всех устройствах, подключенных к сети. Со стороны компьютера функции физического уровня выполняются сетевым адаптером или последовательным портом. Примером протокола физического уровня может служить спецификация 10Base-T технологии Ethernet, которая определяет в качестве используемого кабеля неэкранированную витую пару категории 3 с волновым сопротивлением 100 Ом, разъем RJ-45, максимальную длину физического сегмента 100 метров, манчестерский код для представления данных в кабеле, а также некоторые другие характеристики среды и электрических сигналов. 1.2 Формы представления детерминированных сигналов Понятие «сигнал», если это не оговорено специально, будет использоваться в узком смысле как сигнал, специально создаваемый для передачи сообщения в информационной системе. Основу сигнала составляет какой-либо физический объект или процесс, называемый носителем (переносчиком) информации (сообщения). Носитель становится сигналом в процессе модуляции. Параметры носителя, изменяемые во времени в соответствии с передаваемым сообщением, называют информативными. В зависимости от структуры информационных параметров сигналы подразделяют на дискретные, непрерывные и дискретно-непрерывные. Сигнал считают дискретным по данному параметру, если число значений, которое может принимать этот параметр, конечно (или счетно). Если множество возможных значений параметра образует континиум, то сигнал считают непрерывным по данному параметру. Сигнал, дискретный по одному параметру и непрерывный по другому, называют дискретно-непрерывным. В соответствии с этим существуют следующие разновидности математических представлений (моделей) детерминированного сигнала: • непрерывная функция непрерывного аргумента, например непрерывная функция времени (рис. 1.3,а); • непрерывная функция дискретного аргумента, например функция, значения которой отсчитывают только в определенные моменты времени (рис. 1.3,б); • дискретная функция непрерывного аргумента, например функция времени, квантованная по уровню (рис. 1.3,в); • дискретная функция дискретного аргумента, например функция, принимающая одно из конечного множества возможных значений (уровней) в определенные моменты времени (рис. 1.3,г). 1.3 Классификация сигналов Сигнал – физический процесс, адекватно отображающий передаваемое сообщение. Физической величиной, определяющей сигнал, выступает напряжение или ток. С информационной точки зрения сигналы разделяют на детерминированные и случайные. Детерминированным называется сигнал, значение которого в любой момент времени можно предсказать с вероятностью единица. Такой сигнал является математически абстрактным и в природе не существует. Случайным называется сигнал, мгновенные значения которого заранее не известны и могут быть предсказаны с вероятностью, меньшей единицы. Любой сигнал, несущий информацию, должен рассматриваться как случайный. С другой стороны к случайным сигналам относятся помехи и шумы, воздействующие на радиоэлектронные устройства. Как детерминированные, так и случайные сигналы могут быть непрерывными и дискретными. Непрерывным называется сигнал, существующий в каждой точке некоторого временного интервала, произвольный по величине и непрерывный во времени. Поскольку такой сигнал аналогичен передаваемому сообщению, то эти сигналы называют также аналоговыми. Аналоговые сигналы могут быть импульсными. Импульсным называется сигнал, отличный от нуля на некотором временном интервале и равный нулю вне этого интервала. Иллюстрацией аналоговых сигналов являются видеоимпульс (ВИ) и радиоимпульс (РИ) с высокочастотным (ВЧ) заполнением (рис. 1.4): , (1.1) - частота несущего колебания; является огибающей радиоимпульса. Огибающей называется геометрическое место точек, в которых мгновенные значения сигналов принимают экстремальные значения. Полезной моделью радиотехнических сигналов являются периодические сигналы: , где - любое целое, – любое вещественное положительное число. Дискретным называется сигнал, существующий только в фиксированные моменты времени, т.е. заданный в определенном множестве временных точек. Для других значений времени этот сигнал не определен. Любое значение дискретного сигнала называется отсчетом (или выборкой): . Значения дискретного сигнала в моменты t1, t2 и т. д. совпадают со значением исходного сигнала (рис. 1.5). Цифровой сигнал – сигнал, дискретный во времени и квантованный по уровню. Амплитуда цифрового сигнала может принимать в фиксированный момент времени одно значение из множества допустимых уровней. Число этих уровней (уровней квантования) определяется разрядностью цифрового устройства, обрабатывающего цифровой сигнал. Комплексный сигнал. Комплексный сигнал можно представить в виде: . Тогда комплексно-сопряженный для него сигнал имеет вид: . 1.4 Динамическое представление сигналов Для того чтобы сделать сигнал предметом теоретического исследования, необходимо указать способ математического описания, т. е. требуется создать математическую модель сигнала. В общем случае в качестве математической модели сигнала может выступать любая функциональная зависимость, аргументом которой является время. Наиболее часто при составлении математической модели используется динамическое представление сигналов. Сущность этого метода состоит в том, чтобы реальный сигнал представить в виде суммы элементарных функций, возникающих в последовательные моменты времени. Возможны два способа динамического представления: 1) представление сигнала в виде суммы элементарных ступенчатых функций (рис. 1.6). Высота «ступеньки» совпадает с приращением сигнала за время . 2) представление сигнала в виде суммы элементарных импульсов прямоугольной формы (рис. 1.7). Рассмотрим первый способ динамического представления сигналов. Этот способ основан на использовании функции включения (единичной функции, функции Хевисайда): (1.2) Единичная функция может быть задана со смещением относительно начала отсчета (рис. 1.8) На основе функции включения просто описываются импульсные сигналы прямоугольной формы (рис. 1.9): Сигнал произвольной формы может быть представлен с помощью выражения: Второй способ динамического представления. Этот способ основан на понятии -функции (функции Дирака), которая представляется в следующем виде: (1.3) Смещенная  -функция представлена на рис. 1.10. . Таким образом, -функция всюду равна 0, за исключением точки t = t0, при которой ее значение становится равным . Свойства -функции 1. Площадь под -функцией равна единице: . (1.4) 2. Если произвольную функцию умножить на и результат проинтегрировать, то значение интеграла будет равно значению функции в той точке, где сосредоточен -импульс: , (1.5) В этом состоит фильтрующее свойство -функции. 3. Размерность - функции совпадает с размерностью частоты [1/c]=[Гц]. 1.5 Модуляция Сигналы, поступающие от источника сообщения, не могут быть переданы по радиоканалу. Основная причина заключается в их низкочастотности. Для эффективного излучения электромагнитных волн требуются высокочастотные колебания (ВЧ). Высокочастотное колебание, которое переносит полезный сигнал, называется несущим колебанием (НК). Процесс изменения параметров несущего колебания по закону передаваемого сообщения называется модуляцией, а устройство, выполняющее эту функцию – модулятором (рис. 1.11). В радиотехнике в качестве несущего колебания используется гармоническое колебание. В общем виде модулированный сигнал может быть представлен в виде , (1.6) где - амплитуда сигнала; - частота сигнала; - фаза сигнала. Эти величины являются основными параметрами сигнала. Если при неизменных частоте и фазе переменной оказывается амплитуда сигнала , то получается амплитудно–модулированное (АМ) колебание. Если при неизменных амплитуде и фазе переменной оказывается частота сигнала , то получается частотно–модулированное (ЧМ) колебание. Если при неизменных амплитуде и частоте переменной оказывается фаза сигнала , то получается фазо–модулированное (ФМ) колебание. Виды модуляции бывают непрерывные и дискретные. При дискретной модуляции различают амплитудно–, фазово– и частотно–манипулированные сигналы. 1.6 Спектральный анализ непериодических сигналов Спектральный анализ непериодических сигналов проводится на основе интегрального преобразования Фурье. Преобразование Фурье сигнала u(t) (1.6) дает спектральную плотность или спектр сигнала S() =. (1.7) Обратное преобразование Фурье позволяет перейти от спектральной плотности к сигналу u(t)= . (1.8) Пара преобразования Фурье (1.7) и (1.8) устанавливает взаимно однозначное соответствие между сигналом u(t) и его спектральной плотностью S(). Функция S() является в общем случае комплексной и может быть представлена в виде . Модуль спектральной плотности называется амплитудным спектром: , а ее аргумент - фазовым спектром: . Пример. Найти спектр одиночного прямоугольного импульса, описываемого функцией времени (рис. 1.12): Выражение для спектральной характеристики амплитуд находим в соответствии с прямым преобразованием Фурье (1.7) . Искомый спектр представляет собой модуль этого выражения: Спектр одиночного прямоугольного импульса имеет форму , представленную на рис. 1.13. Пример Определить спектр дельта-функции (рис. 1.10). Запишем выражение для спектральной характеристики дельта-функции, сосредоточенной в точке : . В соответствии со свойством дельта-функции (1.5) имеем , откуда модуль спектральной характеристики . Следовательно, дельта-функции соответствует сплошной равномерный спектр, включающий в себя составляющие бесконечно больших частот (рис. 1.14). 1.7 Распределение энергии в спектре Рассмотрим непериодический сигнал u(t), физическим представлением которого будем считать электрическое напряжение на резисторе с сопротивлением в 1 Ом. Тогда энергия, выделяемая на этом резисторе; . (1.9) В предположении, что интеграл (1.9) сходится, выразим энергию через модуль спектральной характеристики S() сигнала u(t). Квадрат этого модуля можно записать в виде , где - функция, комплексно-сопряженная спектральной характеристике S(j) сигнала u(t). Тогда . После изменения последовательности интегрирования и использования обратного преобразования Фурье (1.8) получим: . Окончательно имеем . (1.10) Соотношение (1.10) известно как равенство Парсеваля. Оказывается, что энергию, выделяемую непериодическим сигналом за время его существования, можно определить, интегрируя квадрат модуля его спектральной характеристики в интервале частот. 1.8 Соотношения между длительностью импульсов и шириной их спектров Анализируя спектр одиночного прямоугольного импульса (см. рис. 1.13), можно установить, что при увеличении его длительности  от 0 до ∞ спектр сокращается от безграничного (у -функции) до одной спектральной линии в начале координат, соответствующей постоянному значению сигнала. Это свойство сокращения ширины спектра сигнала при увеличении его длительности и наоборот справедливо для сигналов любой формы. Оно вытекает непосредственно из особенностей прямого и обратного интегрального преобразования Фурье, у которых показатель степени экспоненциальной функции в подынтегральных выражениях имеет переменные t и  в виде произведения. Другой важный вывод, также являющийся прямым следствием Фурье-преобразования, заключается в том, что длительность сигнала и ширина его спектра не могут быть одновременно ограничены конечными интервалами: если длительность сигнала ограничена, то спектр его неограничен, и, наоборот, сигнал с ограниченным спектром длится бесконечно долго. Справедливо соотношение , где — длительность импульса; — ширина спектра импульса; С — постоянная величина, зависящая от формы импульса (при ориентировочных оценках обычно принимают С = 1). Реальные сигналы ограничены во времени, генерируются и передаются устройствами, содержащими инерционные элементы (например, емкости и индуктивности в электрических цепях), и поэтому не могут содержать гармонические составляющие сколь угодно высоких частот. Поэтому обычно рассматриваются модели сигналов, обладающие как конечной длительностью, так и ограниченным спектром. При этом в соответствии с каким-либо критерием дополнительно ограничивается либо ширина спектра, либо длительность сигнала, либо оба параметра одновременно. В качестве такого критерия используется энергетический критерий, согласно которому практическую длительность Т и практическую ширину спектра выбирают так, чтобы в них была сосредоточена подавляющая часть энергии сигнала (как правило 95% энергии). 1.9 Преимущества цифровой формы представления сигналов. Равномернаяная дискретизация. Теорема Котельникова В связи с широким внедрением цифровой техники непрерывные сигналы, как правило, преобразуются в дискретные. С этой целью каждый непрерывный сигнал подвергается операциям дискретизации по времени и по уровню. Под дискретизацией подразумевают преобразование функции непрерывного времени в функцию дискретного времени, представляемую совокупностью величин, называемых координатами, по значениям которых исходная непрерывная функция может быть восстановлена с заданной точностью. Роль координат выполняют мгновенные значения функции, отсчитанные в определенные моменты времени. Под квантованием подразумевают преобразование некоторой величины с непрерывной шкалой значений в величину, имеющую дискретную шкалу значений. Оно сводится к замене любого мгновенного значения одним из конечного множества разрешенных значений, называемых уровнями квантования. Изменение вида сигнала u(t) (рис. 1.15, а) в результате проведения операции дискретизации показано на рис. 1.15,б, а в результате совместного проведения операций дискретизации и квантования - на рис. 1.15,в. Число уровней квантования на рис. 1.15,в равно 8. Обычно их значительно больше. Передача такого множества различных по уровню импульсов даже на небольшие расстояния применяется крайне редко. Если провести нумерацию уровней, то их передача сведется к передаче чисел. Тогда, выразив эти числа в какой-либо системе счисления, можно обойтись меньшим множеством передаваемых сигналов. Как правило, дискретный сигнал преобразуется в последовательность чисел, выраженных в двоичном коде. Каждое дискретное значение сигнала представляется в этом случае последовательностью сигналов двух уровней. Наличие или отсутствие импульса на определенном месте интерпретируется единицей или нулем в соответствующем разряде двоичного числа. Цифровая форма представления сигнала u(t) (рис. 1.15,а) показана на рис. 1.15,г. Для восьми уровней достаточно трех двоичных разрядов. При передаче и обработке информации в цифровой технике существует принципиальная возможность снижения вероятности получения ошибочного результата до весьма малых значений. Она возникает потому, что при использовании дискретных сигналов, во-первых, применимы такие методы кодирования, которые обеспечивают обнаружение и исправление ошибок, а во-вторых, можно избежать свойственного аналоговым сигналам эффекта накопления искажений в процессе их передачи и обработки, поскольку квантованный сигнал легко восстановить до первоначального уровня всякий раз, когда величина накопленных искажений приблизится к половине кванта. Практическая реализация указанных методов наиболее эффективна при минимальном числе уровней, равном двум. Широкое распространение получили методы дискретизации, при которых сигнал u(t) заменяется совокупностью его мгновенных значений u(tj), взятых в определенные моменты времени tj (j=1, 2,…N) и называемых выборками или отсчетами. Отрезок времени между соседними выборками называют шагом дискретизации. Если он выдерживается постоянным во всем диапазоне преобразования, дискретизация считается равномерной, в противном случае – неравномерной. При построении метода дискретизации необходимо сформулировать критерий выбора отсчетов, установить процедуру восстановления по ним исходного сигнала и определить возникающую при этом погрешность. Решение указанных задач возможно лишь на базе выбора определенной математической модели дискретизируемого сигнала. В вопросе определения величины шага при равномерной дискретизации известно несколько подходов, отличающихся тем, каким параметром характеризуются динамические свойства сигнала. В теоретических исследованиях наибольшее распространение получила модель сигналов в виде процесса, каждая реализация которого представляет функцию с ограниченным спектром. Величина шага дискретизации в этом случае ставится в зависимость от наивысшей частоты спектра. Такой критерий выбора отсчетов принято называть частотным. Правило выбора предельного шага при равномерной дискретизации с использованием модели сигнала с ограниченным спектром в наиболее четкой форме сформулировал и доказал В.А. Котельников в виде теоремы. Теорема устанавливает принципиальную возможность полного восстановления детерминированной функции с ограниченным спектром по ее отсчетам и указывает предельное значение интервала времени между отсчетами, при котором такое восстановление еще возможно. Теорема Котельникова: функция u(t), допускающая преобразование Фурье и имеющая непрерывный спектр, ограниченный полосой частот от 0 до , полностью определяется дискретным рядом своих мгновенных значений, отсчитанных через интервалы времени . Физическая основа теоремы выявляется при рассмотрении связи между формой функции и шириной ее спектра. Только в случае, когда спектр функции безграничен, ее значения в сколь угодно близкие моменты времени могут изменяться произвольно (корреляционная связь между ними отсутствует). Сокращение высокочастотной части спектра до граничной частоты равнозначно устранению из временной функции выбросов, которые могли быть сформированы этими высокочастотными составляющими. При меньших граничных частотах имеем более сглаженные функции времени. Поскольку значения этих функций в моменты времени u(t1) и u(t1+t) в пределах некоторого интервала t не могут изменяться существенно, можно ограничиться значениями функции, взятыми через интервалы t (отсчетами). Таким образом, функция u(t) может быть выражена через ее дискретные значения, взятые в моменты времени tn=nt=n/в : , где функции вида являются базисными функциями и называются функциями отсчетов. Так как при любых целых k и п справедливы соотношения , то . Благодаря этому свойству значения функции u(k) в моменты времени tn=nt представляют собой не что иное, как ее отсчеты. Пример. Определить по теореме Котельникова шаг дискретизации t для детерминированной функции ориентируясь на практическую ширину спектра, содержащую 95 % энергии. По формуле прямого преобразования Фурье (1.7) находим спектральную характеристику , откуда . Практическую ширину спектра определяем, пользуясь условием сосредоточения в спектре 95 % энергии: . Поскольку , имеем аrctgв=0.95 /2=1.49. Тогда в=13.1 рад/с и t= /в=0.24 с. 1.10 Теоретические и практические аспекты использования теоремы Котельникова Процедура теоретического восстановления конкретной реализации u(t) по ее отсчетам сводится к следующему. На передающей стороне в исходной непрерывной функции u(t) через интервалы времени t определяются мгновенные значения u(nt) и передаются в канал связи в виде -импульсов с амплитудами Ап и бесконечно малой длительностью , имеющих площади Ап, равные u(nt). На приемной стороне такая последовательность импульсов пропускается через идеальный фильтр нижних частот, у которого частота среза равна Fв. При длительной передаче сигнал на выходе фильтра будет точно воспроизводить переданный непрерывный сигнал u(t). При этом возникает ряд принципиальных трудностей. Во-первых, реальный сигнал имеет конечную длительность Т и, следовательно, при представлении его в частотной области обладает неограниченным спектром. Однако в силу свойств реальных источников сигналов и ограниченности полосы пропускания реальных каналов спектр сигнала с той или иной степенью точности можно считать ограниченным некоторой предельной частотой Fв. Обычно она определяется на основе энергетического критерия. Спектр ограничивается областью частот от 0 до Fв, в которой сосредоточена подавляющая часть энергии сигнала (80-99 %). Такое ограничение спектра, естественно, приводит к искажению сигнала. Относительная точность воспроизведения сигнала  может быть определена из соотношения: , где Ре — энергия отброшенных высокочастотных составляющих сигнала; Рс — полная энергия сигнала. Таким образом, восстановление ограниченного во времени сигнала по отсчетам, полученным по теореме Котельникова при условии принудительного ограничения спектра сигнала, возможно только приближенно. Ошибка возникает не только за счет принудительного ограничения спектра, но и за счет конечного числа отсчетов в интервале времени Т, которых в соответствии с теоремой Котельникова будет 2FвT. Эта составляющая является следствием пренебрежения вкладом бесконечного числа функций отсчета, соответствующих выборкам за пределами интервала Т, и является погрешностью восстановления исходной функции на интервале Т по ограниченному числу членов ряда Котельникова. Модель сигнала с ограниченным спектром имеет еще одно теоретическое неудобство. Она не может отображать основное свойство сигнала — способность нести информацию. Причина — возможность теоретического предсказания поведения функции с ограниченным спектром на всей оси времени, если она точно известна на сколь угодно малом отрезке времени. Указанные принципиальные трудности устраняются, если рассматривать теорему Котельникова как приближенную для функций с неограниченным спектром. Во-вторых, предполагаемая процедура восстановления вносит весьма существенную дополнительную погрешность. Она возникает потому, что невозможно обеспечить создание импульсов бесконечно малой длительности, как невозможно осуществить их передачу по реальным каналам связи. Кроме того, максимум выходного сигнала, соответствующего реакции идеального фильтра низких частот на дельта-импульс, запаздывает на время, равное бесконечности. За конечное время Т каждая функция отсчета, а следовательно, и их сумма, представляющая собой исходный непрерывный сигнал, будут сформированы лишь приближенно и тем грубее, чем меньше Т. 1.11 Квантование сигналов. Шум квантования Поскольку математической моделью непрерывного сигнала является случайный процесс u(t), мгновенное значение сигнала u= u(ti) представляет собой случайную величину. Диапазон ее изменения, называемый непрерывной шкалой мгновенных значений сигнала, ограничен значениями umin и итах, что отражает условие физической реализуемости сигнала. Непрерывную шкалу мгновенных значений ип=итах - umin сигнала разбивают на п интервалов, называемых шагами квантования. Границами шагов квантования являются значения u0= итin, ui,..., ип-1, un = umax. Из множества мгновенных значений, принадлежащих i-му шагу квантования (ui-1u< ui), только одно значение ui' является разрешенным (i-й уровень квантования). Любое другое из указанного множества значений округляется до ui'. Совокупность величин ui' (i=1, 2, ..., п) образует дискретную шкалу уровней квантования. Если эта шкала равномерна, т. е. разность значений ui' = ui'- ui-1' постоянна на всем протяжении непрерывной шкалы мгновенных значений сигнала и, квантование называют равномерным. Если постоянство значений ui' не выдерживается - квантование неравномерное. Благодаря простоте технической реализации равномерное квантование получило наиболее широкое распространение. В результате замены мгновенного значения сигнала u соответствующим уровнем квантования ui' возникает погрешность = u - ui', которую называют ошибкой квантования. Эта погрешность является случайной величиной. Чаще всего вызывает интерес ее максимальное значение = mах|i| и среднеквадратическое отклонение  для всего диапазона изменения мгновенных значений сигнала. С позиций минимизации наибольшей возможной ошибки квантования непрерывную шкалу мгновенных значений сигнала целесообразно разбить на п одинаковых шагов квантования = (итах ‑ umin)/n и уровни квантования разместить в середине каждого шага (рис. 1.16). При этом максимальная ошибка квантования не превышает 0.5. Если каждый уровень квантования выбран равным нижней (верхней) границе шага квантования, максимальная ошибка квантования возрастает до величины . Шум квантования. При квантовании сигнала по уровню случайный процесс заменяется ступенчатой зависимостью u/(t). Изменяющуюся во времени ошибку квантования (t), также представляющую собой случайный процесс, называют шумом квантования:  (t)=u(t)-u'(t). Сохраняя ранее введенные предположения (о малости шага квантования и равномерности распределения в нем мгновенных значений сигнала) и считая случайные процессы u(t) и  (t) эргодическими, среднеквадратическую ошибку равномерного квантования  можно определить по реализации  (t) (рис. 1.17). В пределах каждого шага квантования  зависимость  (t) заменяется прямой t*tg, где  переменный угол наклона прямой. При размещении уровней квантования в середине каждого шага математическое ожидание ошибки квантования равно нулю, а ее среднеквадратическое значение определяется выражением: . Так как tg = /T, то . При заданной допустимой среднеквадратической ошибке квантования и отсутствии помех число уровней квантования находится из соотношения . Однако при неравномерном законе распределения мгновенных значений сигнала квантование с постоянным шагом не является оптимальным по критерию минимума среднеквадратической ошибки . Квантуя участки с менее вероятными значениями сигнала с большим шагом, указанное значение среднеквадратической ошибки можно уменьшить. 1.12 Амплитудные и фазовые методы ограничения полосы частот В таких системах передачи информации, как радиорелейные, спутниковые и проводные, определяющим требованием является ограничение полосы частот. Требование электромагнитной совместимости радиосредств любой радиотехнической системы и дефицит радиочастотного ресурса являются важнейшими факторами, приводящими к необходимости выполнения определенных норм по уровню внеполосных излучений. С точки зрения эффективного использования радиочастотного ресурса актуальным является ограничение полосы частот именно в передающем устройстве, что показывает необходимость формирования сигналов, отвечающих заданным требованиям. Как известно, фазоманипулированные (ФМн) сигналы, используемые в данных устройствах, обладают широкой полосой частот и высоким уровнем внеполосных излучений. По этой причине, исходя из требований электромагнитной совместимости различных радиосредств, необходимо использовать на выходе передающей части системы фильтры, ограничивающие полосу частот ФМн сигналов. Это приводит к появлению межсимвольной интерференции и существенному искажению ФМн сигналов на входе приемного устройства. Задача уменьшения полосы занимаемых частот и уровня внеполосных излучений может быть решена с помощью выбора определенного вида модуляции, а также оптимизации вида модулирующей функции. Наиболее универсальным и гибким являются специальные методы ограничения занимаемой полосы частот, в которых для снижения уровня внеполосных излучений ФМн сигналов обычно применяют уменьшение амплитуды огибающей или плавное изменение фазы отдельных символов в моменты перескока фазы колебаний. Первые методы ограничения полосы спектра ФМн сигналов называют амплитудными, а вторые - фазовыми. Совместное изменение амплитуды и фазы результирующего колебания относится к амплитудно-фазовым методам. Таким образом, для всех методов ограничения полосы применяется дополнительная амплитудная и/или фазовая модуляция символов исходного ФМн сигнала. Однако при использовании данных методов ограничения полосы в радиотехнических системах возникают энергетические потери по сравнению с системами, где используются классические ФМн сигналы. Величина этих потерь зависит как от применяемого метода ограничения полосы частот, так и от формы модулирующей функции. На практике используются часто для сокращения занимаемой полосы сигналы специальной формы, обладающие следующими значениями нормированной полосы занимаемых частот, содержащей 99 % энергии, и скоростью спада уровня энергетического спектра: Форма огибающей FT99 Скорость спада уровня энергет. спектра Прямоугольная 20.6 1/ Треугольная 2.6 1/ Вида cos(x) 2.54 1/ Вида cos2(x) 2.8 1/ 1.13. Контрольные вопросы 1. Основные уровни модели OSI и их функциональные назначения. 2. Математические модели детерминированных сигналов. 3. Понятие и классификация сигналов. 4. Способы динамического представления сигналов. 5. Свойства -функции. 6. Основные виды модуляции. 7. Прямое и обратное преобразование Фурье. 8. Равенство Парсеваля. 9. Теорема Котельникова. 10. Виды квантования сигналов. Шум квантования. 2 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИНФОРМАЦИИ 2.1 Информационные характеристики источника сообщений. Информация и энтропия Модель системы связи может быть представлена простой структурной схемой (рис. 2.1) Источник информации формирует сообщения о состоянии некоторого физического объекта, подлежащие передаче потребителю. Если бы состояние объекта было известно заранее, не было бы смысла передавать сообщение, оно не несло бы никакой информации. Система связи или устройство хранения, предназначенные для передачи информации, называются каналом связи. Перед поступлением в канал сообщение подвергается преобразованию, называемому кодированием. Если сообщение было закодировано на входе канала, то необходима соответствующая обработка выхода канала – декодирование сообщения с целью перевода информации в форму, приемлемую для получателя. Устройства, осуществляющие кодирование и декодирование сообщений, называют кодером и декодером. Кроме того, в процессе функционирования на систему связи воздействуют шумы или помехи, под действием которых в передаваемых сообщениях возникают ошибки. Основным назначением любой системы передачи информации является передача сообщений. Поэтому наиболее существенной характеристикой системы передачи информации следует считать ее способность передавать без искажений возможно большее количество сообщений в единицу времени. Однако очевидно, что различные сообщения содержат неодинаковое количество сведений. Поэтому необходимо располагать численной мерой количества информации. Мера количества информации характеризует степень уменьшения неопределенности (энтропии) об источнике сообщений. Количество получаемой информации будет тем больше, чем больше имеющаяся вначале неопределенность. До получения информации известно, что объект может принимать одно из множества возможных значений. Чем больше это множество, тем выше неопределенность сообщения. Неопределенность передаваемого сообщения зависит не от смысла возможных сообщений, а от их количества. Передаваемое сообщение указывает на одно из состояний объекта, тем самым уничтожая неопределенность. В качестве меры количества информации, казалось бы, наиболее просто взять число возможных сообщений. Однако такая мера является неудобной в практическом применении. Сообщение из двух букв несет больше информации, чем сообщение из одной буквы. Однако согласно интуитивным представлениям, количество информации пропорционально количеству букв. Это может быть достигнуто, если в качестве меры количества информации принять не число возможных сообщений, а логарифм этого числа. Впервые понятие логарифмической меры количества информации было введено Хартли: , если N=mn, то , (2.1) где n – длина сообщения (число знаков сообщения), m – алфавит источника (количество букв в алфавите). Например, для 5–буквенного слова русского алфавита I=log2mn=nlog2m=5 log233=5 log232=5*5=25 единиц. Достоинства: 1) количество информации пропорционально длине сообщения; 2) обладает свойством аддитивности I(a1,a2,a3)=I(a1)+I(a2)+I(a3)=log232+ log232+ log232=3 log232 3) удобно математически, т.к. при логарифмировании выражение упрощается. Недостатки: введенное понятие не учитывает вероятность появления того или иного события (состояния). 1. Чем неожиданнее событие (меньше вероятность), тем больше оно несет информации. Пример. Сообщение, что 21 декабря в Рязани выпадет снег, несет меньше информации, чем то, что 15 июля в Рязани выпадет снег, т.к. в июле снег маловероятен и, следовательно, это сообщение несет больше информации. 2. Сообщение достоверного события информации не несет. Для p =1 I = 0. Американский инженер Клод Шеннон предложил оценивать меру количества информации в сообщении xi в отличие от вида (2.1) следующим образом: . (2.2) Если в сигнале присутствует m неравновероятных сообщений, то с учетом (2.2) среднее количество информации в таком сообщении , (2.3) что является формулой энтропии. Единица измерения информации зависит от выбора основания логарифма: 2 - бит; 10 - десятичный; e - натуральный логарифм. Обычно используют логарифм по основанию 2. Пример. Бросание игральной кости. Используя формулу (2.3) получаем Бросание монеты . Если количество принятой информации I равно энтропии H, то существующая неопределенность относительно состояния объекта устранена. При отсутствии помехи количество информации определяется следующим образом: I=H. (2.4) Если в канале связи помехи присутствуют или передается неполная информация, то вместо (2.4) используют формулу I=H-H1, (2.5) где H – полная энтропия до получения сообщения, H1 – энтропия после получения сообщения. Пример. Пусть система передачи информации передает сообщение о положении одной фигуры на шахматной доске. Сообщение получено – фигура на черной клетке. Сколько информации несет сообщение? Т.к. неопределенность полностью не устранена, то воспользуемся формулой (2.5). Неопределенность до получения сообщения: . Черных клеток – 32. Следовательно, неопределенность после приема сообщения уменьшилась и составляет . Количество переданной информации определяется согласно (2.5) I=H-H1 =6-5=1 бит. Т.о. информация позволяет уменьшить число возможных вариантов в два раза. Энтропия является мерой количества информации и выражает среднее количество информации, которое несет 1 символ сообщения. Свойства энтропии. 1. Энтропия является вещественной и неотрицательной величиной. Так как.к. , то - отрицателен и, следовательно, 2. Энтропия – величина ограниченная. Для слагаемых в диапазоне очевидно максимальна при равновероятных событиях: , m – количество знаков (букв). 3. Энтропия обращается в нуль лишь в том случае, если вероятность одного из состояний равна единице, тогда вероятность всех остальных событий равна нулю. Это положение соответствует случаю, когда состояние источника полностью определено. 4. Энтропия максимальна, когда все состояния источника равновероятны. 5. Энтропия источника u с двумя состояниями u1 и u2 изменяется от нуля до единицы, достигая максимума при равенстве их вероятностей. 6. Энтропия объединения нескольких статистически независимых источников информации равна сумме энтропий исходных источников. 7. Энтропия характеризует среднюю неопределенность выбора одного состояния из ансамбля. При ее определении используют только вероятности состояний, полностью игнорируя их содержательную сторону. Поэтому энтропия не может служить средством решения любых задач, связанных с неопределенностью. 2.2 Избыточность. Производительность источника дискретных сообщений Избыточность. В качестве элементарных сообщений можно, в частности, рассматривать отдельные символы, вырабатываемые источником, например: буквы алфавита, цифры и т. п. Набор всех возможных символов данного источника называют его алфавитом. Можно говорить также об алфавите канальных символов, то есть символов, с помощью которых передаются сигналы по каналу связи. Например, в случае телеграфа канальными символами являются точки, тире и паузы. Мы знаем, что энтропия независимых сообщений максимальна, когда вероятности всех сообщений равны между собой. Поэтому источник сообщений вырабатывает максимальное количество информации в среднем на один символ, когда все символы данного алфавита независимы и передаются одинаково часто. В действительности это обычно не имеет места. Так, в каждом из существующих языков различные буквы появляются с различными частотами, то есть имеют неодинаковые вероятности. В русском тексте, например, наиболее часто встречаются буквы «о» и «е». Их вероятности равны соответственно 0.11 и 0.09. Наиболее редкая буква «ф» имеет вероятность 0.002. В результате такого неравномерного распределения вероятностей энтропия сообщений, а вместе с тем и количество передаваемой информации, приходящееся на каждую букву текста, значительно уменьшаются. Если бы 32 буквы русского алфавита передавались независимо и с одинаковыми вероятностями, то на каждую букву приходилась бы информация, равная log232, то есть 5 двоичным единицам. Энтропия же, вычисленная с учетом неодинаковых вероятностей, дает 4.3 двоичной единицы на букву. В действительности, количество информации, приходящееся на одну букву, еще меньше. Это обусловлено тем, что буквы связанного текста не являются независимыми, то есть вероятность появления некоторой буквы на очередном месте зависит от того, какие буквы ей предшествуют. Благодаря этому не всякие сочетания букв оказываются возможными. Так, например, невозможно появление мягкого знака после гласной и т. п. Избыточность текста означает, что разные буквы в тексте несут неодинаковое количество информации, так что некоторые буквы оказываются мало существенными или даже совсем ненужными для воспроизведения передаваемых сообщений. Можно, например, записывая слова, пропускать все гласные буквы. При этом в большинстве случаев удастся безошибочно восстановить записанные таким образом слова. Уменьшение избыточности сообщений, как увидим ниже, может быть использовано для более экономной эксплуатации систем связи, т. е. для повышения их эффективности. Мерой избыточности служит величина D, показывающая, насколько хорошо используются знаки данного источника: D = [Hмах(Z) -H(Z)]/[Hmax(Z)], (2.6) где Hмах(Z) - максимально возможная энтропия, равная log(m); H(Z) - энтропия источника. Если избыточность источника равна нулю, то формируемые им сообщения оптимальны в смысле наибольшего количества переносимой информации. Для передачи определенного количества информации I при отсутствии помех в этом случае необходимо k1 = I/[Hmax(Z)] знаков. Последствия от наличия избыточности сообщений неоднозначны. С одной стороны, избыточные сообщения требуют дополнительных затрат на передачу, например, увеличения длительности передач или расширения практической ширины спектра канала связи, что нежелательно. С другой стороны, при использовании сообщений, подчиняющихся априорно известным ограничениям, появляется возможность обнаружения и исправления ошибок, которые приводят к нарушению этих ограничений. Следовательно, наличие избыточности способствует повышению помехоустойчивости сообщений. Высокая избыточность большинства естественных языков обеспечивает, например, надежное общение людей даже при наличии у них акцентов и дефектов речи. Однако при обмене информацией в автоматических системах естественная избыточность подлежит устранению. Это объясняется тем, что алгоритмы обнаружения и исправления ошибок, базирующихся на статистических закономерностях функционирования источника, оказываются слишком сложными для реализации их техническими средствами. В случае необходимости для повышения помехоустойчивости затем вводится «рациональная» избыточность, позволяющая обеспечить обнаружение и исправление наиболее вероятных и опасных по последствиям ошибок простыми техническими средствами. При низком уровне помех в канале связи устранение избыточности приводит к увеличению скорости передачи информации и может дать значительный экономический эффект. Производительность источника дискретных сообщений. Под производительностью источника сообщений подразумевают количество информации, вырабатываемое источником в единицу времени. Эту характеристику источника называют также скоростью создания сообщений или потоком входной информации. Производительность источника I(z) теперь можно выразить формулой Ī(Z) = H(Z) / и (2.7) Как следует из (2.7), повышение производительности источника возможно не только за счет увеличения энтропии, но и за счет снижения средней длительности формирования знака. Длительности знаков желательно выбирать обратно пропорциональными вероятностям их появления. Если длительность выдачи знака не зависит от состояния источника, для всех знаков одинакова и равна , то  и=. Выражение (2.7) для Ī(Z) принимает вид Ī(Z) = H(Z) /. Наибольшая производительность источника в этом случае достигается при максимальной энтропии. 2.3 Информационные характеристики дискретных каналов связи Дискретным каналом называют совокупность средств, предназначенных для передачи дискретных сигналов. Такие каналы широко используются, например, при передаче данных, в телеграфии, радиолокации. Скорость передачи информации по дискретному каналу. Характеризуя дискретный канал связи, используют два понятия скорости передачи: технической и информационной. Под технической скоростью передачи VТ, называемой также скоростью манипуляции, подразумевают число элементарных сигналов (символов), передаваемых по каналу в единицу времени. Она зависит от свойств линии связи и быстродействия аппаратуры канала. С учетом возможных различий в длительностях символов скорость VT=l / cp, (2.8) где  cp — среднее значение длительности символа. При одинаковой продолжительности  всех передаваемых символов в (2.8)  cp=. Единицей измерения технической скорости служит бод - скорость, при которой за одну секунду передается один символ. Информационная скорость, или скорость передачи информации, определяется средним количеством информации, которое передается по каналу в единицу времени. Она зависит как от характеристик данного канала связи, таких как объем алфавита используемых символов, техническая скорость их передачи, статистические свойства помех в линии, так и от вероятностей поступающих на вход символов и их статистической взаимосвязи. При известной скорости манипуляции VT скорость передачи информации по каналу Ī(A,B) задается соотношением Ī(A,B)= VTI(A,B), (2.9) где I(A,B) — среднее количество информации, переносимое одним символом. Пропускная способность дискретного канала без помех. Для теории и практики важно выяснить, до какого предела и каким путем можно повысить скорость передачи информации по конкретному каналу связи. Предельные возможности канала по передаче информации характеризуются его пропускной способностью. Пропускная способность канала СД равна той максимальной скорости передачи информации по данному каналу, которой можно достигнуть при самых совершенных способах передачи и приема: CД = max Ī(A,B) = max VT I(A,B). (2.10) Пропускная способность канала, как и скорость передачи информации по каналу, измеряется числом двоичных единиц информации в секунду (бит/с). Так как в отсутствие помех имеет место взаимнооднозначное соответствие между множеством символов {a} на выходе канала и {b} на его входе, то I(A,B) = =B,A) = H(B). Максимум возможного количества информации на символ равен log m, где m - объем алфавита символов, откуда согласно (2.10)пропускная способность дискретного канала без помех CД =VT log m. (2.11) Следовательно, для увеличения скорости передачи информации по дискретному каналу без помех и приближения ее к пропускной способности канала последовательность букв сообщения должна подвергнуться такому преобразованию в кодере, при котором различные символы в его выходной последовательности появлялись бы по возможности равновероятно, а статистические связи между ними отсутствовали бы. 2.4 Теорема Шеннона для дискретного канала без помех. Методы оптимального кодирования. Можно показать, что при надлежащем кодировании любые сообщения могут передаваться со скоростью, сколь угодно близкой к пропускной способности канала. Таким образом, при любом источнике сообщений пропускная способность канала может быть полностью использована. Теорема Шеннона Если имеется канал с пропускной способностью С, то сообщения любого источника с энтропией Н на символ можно так закодировать, что окажется возможным передавать эти сообщения со скоростью, сколь угодно близкой к С /H символов в секунду, или, что то же самое, С двоичных единиц в секунду. Вторая теорема Шеннона Существует такой способ кодирования, при котором средняя длина кодовой комбинации, приходящаяся на один символ сообщения, определяется следующим образом: ;  >0 – б.м.в., то есть ; при Определение Кодирование, которое обеспечивает скорость передачи информации, близкую к пропускной способности канала, называют оптимальным. Оптимальное кодирование основано на избыточности источника сообщений, связанное с неодинаковыми вероятностями букв. Оптимальное кодирование можно рассматривать с помощью метода Шеннона-Фано и метода Хаффмена. Метод Шеннона-Фано используется для построения, как правило, бинарного кода. Любой оптимальный код должен удовлетворить следующим условиям: 1) вероятности символов на выходе кодера примерно одинаковы; 2) сообщениям меньшей вероятности должны соответствовать кодовые операции большей длины; 3) оптимальный код не должен требовать разделительных знаков. Код Морзе не является оптимальным, так как требует разделительных знаков. Процедура построения кода Шеннона-Фано: 1) все буквы (символы) источника располагают в порядке убывания их вероятности; 2) все символы делим на две группы с соблюдением примерного равенства вероятностей этих групп (делим чертой); 3) символам верхней группы присваиваем знак 1, а символам нижней – 0; xi P(xi) Знаки кодовой операции Кодовые комбинации Длина кодовой комбинации ni х1 1/2 1 1 1 х2 1/4 1 01 2 х3 1/8 1 001 3 х4 1/16 1 0001 4 х5 1/32 1 00001 5 х6 1/32 00000 5 4) каждую группу символов делим на две подгруппы с соблюдением того же примерного равенства вероятностей; 5) символам верхних подгрупп ставим знак 1, а нижних – 0; 6) повторяем пп. 4 и 5 пока в подгруппе не останется по одному сообщению. Проверим на разделительные знаки. Пример: 01, 001, 1, 1, 1, 1, 1, 01,…. х2 х3 х1 х1 х1 х1 х1 х2 Таким образом, разделительные знаки не нужны. Чтобы код не требовал разделительных знаков, никакая его кодовая операция не должна быть началом другой. Вычислим среднюю длину кодовых комбинаций: , то есть в среднем примерно надо два знака для передачи символа. Энтропия: . Получили , но по теореме Шеннона , тогда скорость передачи информации будет равна пропускной способности . Строение кода удобно преобразить в виде кодового дерева. Оно строится так: из узла исходит число ветвей, равное основанию кода. Верхняя ветвь означает знак 1, а нижняя - знак 0. Каждый узел характеризуется порядком начиная от вершины. Рассмотрим на нашем примере построение кодового дерева: х1 1/2 х2 1/4 0 х3 1/8 0 х4 1/16 0 х5 1/32 0 х6 1/32 0 Декодирование надо начинать с вершины. Все кодовые комбинации концевые, поэтому код не требует разделительных знаков. Оптимальное кодирование позволяет повысить скорость передачи информации при наличии канала без помех. Если есть помехи, то достаточно одной ошибки, чтобы неправильно декодировалась не только кодовая операция, но и целая декада. При наличии помех оптимальное кодирование используют как первую ступень перед помехоустойчивым кодированием. Рассмотренная методика Шеннона-Фано не всегда приводит к однозначному построению кода. Ведь при разбиении на подгруппы можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппы. От указанного недостатка свободна методика Хаффмена. Она гарантирует однозначное построение кода, с наименьшим для данного распределения вероятностей средним числом символов на букву. Принцип построения оптимального кода (метод Хаффмена): 1. Все символы располагаются в порядке убывания их вероятностей. 2. Выбираются 2 символа с наименьшими вероятностями и объединяются в одну точку с суммарной вероятностью. 3. С учетом полученной точки анализируются вероятности символов и объединяются очередные два символа с наименьшими вероятностями. 4. Процесс продолжается до тех пор, пока линии, идущие от каждого символа, не сольются в общей точке с суммарной вероятностью, равной единице. Пример. По каналу связи передаются сообщения, состоящие из 8 символов с разными вероятностями. Необходимо оптимальным образом закодировать сообщения. От каждой точки отходят влево две линии. Верхняя линия обозначается «1», а нижняя – «0». Кодом каждого символа будет последовательность знаков, которая встречается на пути от общей точки с вероятностью 1 к соответствующему символу. xi P(xi) Кодовая комбинация Длина кодовой комбинации ni x1 0.5 1 1 x2 0.15 001 3 x3 0.12 011 3 x4 0.1 010 3 x5 0.04 00011 5 x6 0.04 00010 5 x7 0.03 00001 5 x8 0.02 00000 5 Вычислим энтропию: . Вычислим среднюю длину кодовых комбинаций: . Достоинства и недостатки оптимального кодирования Достоинства: повышается скорость передачи информации или уменьшается требуемая пропускная способность канала; уменьшается емкость памяти при записи информации. Недостатки: низкая помехоустойчивость; эффект размножения ошибки; наличие задержки, что усложняет техническую реализацию. 2.5 Дискретный канал связи с помехами. Теорема Шеннона Теорема Шеннона для дискретного канала связи с помехами Пусть дискретный канал связи обладает пропускной способностью С, а источник сообщений производительностью Ī. Если , то существует способ кодирования, при котором сообщения передаются со сколь угодно малой ошибкой. Если , то имеется возможность закодировать сообщения так, что ошибка будет близкой . Не существует способа кодирования, обеспечивающего потери информации меньше . 2.6 Контрольные вопросы 1. Два способа определения количества информации. 2. Энтропия и ее свойства. 3. Производительность источника дискретных сообщений. 4. Техническая и информационная скорости передачи данных. 5. Теорема Шеннона для дискретного канала без помех. 6. Оптимальное кодирование методом Шеннона-Фано. 7. Оптимальное кодирование методом Хаффмена. 8. Достоинства и недостатки оптимального кодирования. 3 ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ 3.1 Кодовое расстояние Помехоустойчивое кодирование заключается в передаче сообщений более длинными кодовыми комбинациями, чем это требовалось при дискретном канале связи без помех, т.е. при безызбыточном кодировании. Помехоустойчивыми (корректирующими) называют коды, позволяющие обнаруживать или исправлять ошибки. Под обнаружением ошибок понимают установления факта ошибки. Под исправлением ошибки понимают нахождение разряда кодовой комбинации, где произошла ошибка, и последующее ее исправление. В первую очередь надо обнаруживать и исправлять ошибки малой кратности, так как они более вероятны. Степень отличия любых двух кодовых комбинаций характеризуется кодовым расстоянием (хэмминговым). Оно выражается числом символов, в которых комбинации отличаются одна от другой, и обозначается через d. Чтобы получить кодовое расстояние между двумя комбинациями двоичного кода, достаточно подсчитать число единиц в сумме этих комбинаций по модулю 2. Например: Минимальное расстояние, взятое по всем парам кодовых разрешенных комбинаций кода, называют минимальным кодовым расстоянием. Любая n-разрядная двоичная кодовая комбинация может быть интерпретирована как вершина n-мерного единичного куба, т.е. куба с длиной ребра, равной 1. При n=2 кодовые комбинации располагаются в вершинах квадрата; при n=3 – в вершинах единичного куба; при n=4 – в вершинах четырехмерного куба: В общем случае n-мерный единичный куб имеет 2n вершин, что равно наибольшему возможному числу кодовых комбинаций. Такая модель дает простую геометрическую интерпретацию кодовому расстоянию между отдельными кодовыми комбинациями, которое соответствует наименьшему числу ребер единичного куба, которые необходимо пройти, чтобы попасть от одной комбинации к другой. Если d=1, то код не может обнаружить и исправлять ошибки (безызбыточный код). Чтобы код обнаруживал все ошибки кратности меньше или равной g, необходимо и достаточно, чтобы его хемминговое расстояние . При этом могут обнаруживаться ошибки большей кратности. Кратность исправляемых ошибок t должна быть меньше, чем : . Следовательно, или – чтобы код исправлял ошибки. Чтобы код исправлял все ошибки кратности, меньшей или равной t, необходимо и достаточно, чтобы его кодовое расстояние . Чтобы код обнаруживал все ошибки кратности g и одновременно исправлял ошибки кратности, меньшей или равной t причем необходимо и достаточно, чтобы его кодовое расстояние: . 3.2 Систематические коды Код называют систематическим, если значения некоторых разрядов определяются передаваемым сообщением. Эти разряды называют информационными, а остальные разряды вводятся для коррекции ошибок, которые называют проверочными. Значения проверочных разрядов определяются линейной суммой некоторого числа информационных разрядов, поэтому коды называют линейными. Систематические коды имеют обозначение (n,k), где n - число разрядов кодовой комбинации; k - число информационных разрядов, где Кодовую комбинацию будем обозначать: Можно представить кодовую комбинацию иначе: . информационные проверочные разряды разряды Информационные k символов определяются передаваемым сообщением, r проверочных формируются из информационных в виде: , где Декодирование систематических кодов производится методом контрольных чисел: на приеме информационная группа отделяется по тому же принципу и формируется вторая проверочная группа ; находится контрольное число: где X - синдром ошибок. Если ошибки отсутствуют, то X = 0; Если ошибки имеются, то X ≠ 0. В режиме исправления ошибок необходимо указать местонахождение ошибочных символов методом контрольных чисел. Так, для кода Хемминга (7,4) контрольные числа сведены в таблицу: ai, bj a1 a2 a3 a4 b1 b2 b3 X 011 101 112 111 100 010 001 Такому распределению контрольных чисел соответствуют коэффициенты Cij: С11= 0 С12= 1 С13= 1 С14= 1 С21= 1 С22= 0 С23= 1 С24= 1 С31= 1 С32= 1 С33= 0 С34= 1 Общее число контрольных чисел должно удовлетворять соотношению: , , или 3.3 Циклические коды Циклические коды – это систематические коды, у которых строки порождающей матрицы обладают свойством цикличности. Свойство цикличности состоит в том, что из одной кодовой комбинации можно получить другую, циклически переместив символ кодовой комбинации в конец. 11010 10101 01011. Общие сведения. Математическое описание В теории циклических кодов принято описывать кодовые комбинации в виде полиномов (многочленов). Например, кодовую комбинацию 01011 можно представить в виде: . Здесь - фиктивная переменная, степень которой показывает номер разряда. В общем случае: . Кодовая комбинация значимости n имеет максимальную степень, равную n-1. Зная полином можно найти кодовую комбинацию, если известно число разрядов (значность кода – n). Циклическая перестановка на один шаг соответствует умножению на . 01011  x3+x+1 x(x3+x+1)= x4+x2+x  10110, что соответствует циклической перестановке. Однако при умножении может быть степень больше, чем , т.е. увеличится значность кода, что нарушит аксиому замкнутости. Умножение производится следующим образом: 1) полиномы перемножаются обычным способом с приведением коэффициентов подобных членов по модулю m (x2+ x2=(11) x2=0*x2=0); 2) если степень произведения не превышает , то результатом умножения считается это произведение; 3) если степень произведения будет больше или равна n, то xn=1 (если xn+2, то xn+2=xnx2=1*x2); x(x4+x2+x)=x5+x3+x2  101100, а была 5-значная кодовая комбинация, поэтому это не правильно. Тогда заменив , получим . Как правило, используют три способа кодирования циклических кодов. Первый способ заключается в умножении образующего полинома g(x) на многочлен, соответствующий исходной последовательности информационных символов m(x), и является наиболее простым: . Образующий полином определяет корректирующую способность кода. Использование данного метода приводит к неразделимому коду, в котором информационные и проверочные символы не занимают постоянных мест в кодовой комбинации, что является большим недостатком этого способа. Пример 1. Пусть кодированию подлежит m(x)=x3+1(1001). Образующий полином g(x)= x3+x+1(1011); n=7; k=4. Выполним следующее действие 1001 1011 1001 1001 0000 1001 1010011 F(x)=1010011= x6+x4+x+1. Второй метод образования последовательностей циклического кода основан на применении метода Питерсона, который заключается в умножении многочлена, соответствующего исходной последовательности информационных символов m(x), на одночлен, соответствующий старшей степени образующего полинома, и в добавлении к результату умножения остатка от деления этого произведения на образующий полином. Метод Питерсона Алгоритм кодирования: 1. Записать -разрядную безызбыточную кодовую комбинацию в виде многочлена ; 2. Исходя из требуемой корректирующей способности кода, выбрать образующий полином: 2 1+x 1+x+x2 3 1+x+x3 1+x+x4 1+x2+x5 3. Сформировать кодовый многочлен , причем все кодовые многочлены должны делиться без остатка на : На приеме имеем , где – многочлен ошибок. Если имеют место ошибки в -м и -м разрядах, то . Основной критерий обнаружения ошибок – неделимость без остатка многочлена на . Если код работает в режиме обнаружения и исправления ошибок, то по виду определяется местонахождение ошибок. Пример 2. m(x)=1001; g(x)=1011; n=7; k=4. 1001 1001000 1011 1000 1011 1010 0000 0100 0000 0000 0000 1000 1001 1011 1001000 0110 0000 110 Тогда F(x)=1001110 = x6+x3+x2+x. Третий способ кодирования основан на свойстве систематических (линейных) кодов, к которым относится и циклический код. Если представить комбинацию циклического кода в виде cn-1, … ,cn-k, cn-k-1, … ,c1,c0, то согласно этому свойству проверочные (cn-k-1, … ,c1,c0) и информационные (cn-1, … ,cn-k) символы систематического кода связаны линейными соотношениями и j-й проверочный символ определяется соотношением , где hi – коэффициенты проверочного многочлена: . Таким образом, символы циклического кода представляются в виде взвешенной суммы k других символов кода (суммирование по модулю 2). Пример 3. Вычислим проверочный многочлен . Для информационного многочлена m(x)=x+1 (0011) имеем c6h0c5h1c4h2c3h3= 1*10*10*11*0=1; c5h0c4h1c3h2c2h3= 0*10*11*11*0=1; c4h0c3h1c2h2c1h3= 0*11*11*11*0=0. Таким образом, F(x)=1001110 = x6+x3+x2+x. 3.4 Контрольные вопросы 1. Понятие кодового расстояния между двумя кодовыми комбинациями. 2. Систематические коды и способы их декодирования. 3. Условие обнаружения и исправления кодом ошибок. 4. Циклические коды. Правила умножения полиномов циклических кодов. 5. Способы построения циклических кодов. Библиографический список 1. Дмитриев В.И. Прикладная теория информации: Учеб. пособие для вузов. М.: Высш.шк., 1989. 320 с. 2. Советов Б.Я. Теория информации. Теоретические основы передачи данных в АСУ. Л.: Изд-во Ленингр. ун-та, 1977. 184 с. 3. Куликовский Л.Ф., Мотов В.В. Теоретические основы информационных процессов: Учеб. пособие. М.: Высш. шк., 1987. 248 с. 4. Игнатов В.А. Теория информации и передачи сигналов: Учеб. пособие для вузов. М.: Радио и связь, 1991. 280 с. 5. Колесник В.Д., Полтырев Г.Ш. Курс теории информации. М.: Наука, 1982. 416 с. 6. Гоноровский И.С. Радиотехнические цепи и сигналы. 1994 7. Питерсон Коды, исправление ошибок … Оглавление 1 СИГНАЛЫ В СЕТЯХ ПЕРЕДАЧИ ИНФОРМАЦИИ 1 1.1 Модель взаимодействия открытых систем 1 1.2 Формы представления детерминированных сигналов 4 1.3 Классификация сигналов 5 1.4 Динамическое представление сигналов. 6 1.5 Модуляция 8 1.6 Спектральный анализ непериодических сигналов 9 1.7 Распределение энергии в спектре 11 1.8 Соотношения между длительностью импульсов и шириной их спектров 11 1.9 Преимущества цифровой формы представления сигналов. Равномерная дискретизация. Теорема Котельникова 12 1.10 Теоретические и практические аспекты использования теоремы Котельникова 15 1.11 Квантование сигналов. Шум квантования 17 1.12 Амплитудные и фазовые методы ограничения полосы частот 18 1.13 Контрольные вопросы 19 2 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИНФОРМАЦИИ 20 2.1 Информационные характеристики источника сообщений. Информация и энтропия. 20 2.2 Избыточность. Производительность источника дискретных сообщений. 23 2.3 Информационные характеристики дискретных каналов связи. 25 2.4 Теорема Шеннона для дискретного канала без помех. Методы оптимального кодирования. 26 2.5 Дискретный канал связи с помехами. Теорема Шеннона. 30 2.6 Контрольные вопросы 30 3 ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ 31 3.1 Кодовое расстояние 31 3.2 Систематические коды. 32 3.3 Циклические коды 33 3.4 Контрольные вопросы 36 Список используемой литературы 36