Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лекция 1. Основные понятия теории информации
Получение, передача, обработка и хранение информации являются наиболее динамично развивающимися и перспективными областями человеческой деятельности. Десятки тысяч фирм во всем мире, с годовым оборотом в сотни миллиардов долларов, занимаются исследованием, разработкой, производством, продажей и эксплуатацией разнообразных систем и устройств передачи и хранения информации.
Передача информации является важнейшей задачей в системах связи и телекоммуникаций, компьютерных сетях, телефонии, навигационных и измерительных системах и т.д. Оптимизация информационных систем с точки зрения повышения скорости, достоверности и помехоустойчивости передачи информации возможна только на основе использования положений теории информации.
Теория информации, ориентированная на формализованное описание сообщений, процессов их формирования, передачи и приема развивалась, начиная с исследований Р. Хартли (1928 г.) особенно активно во второй половине XX века. Ее создание позволило решить основные теоретические проблемы и создать эффективные системы передачи сигналов и хранения информации.
Как известно, под информацией понимают совокупность сведений о каких-либо событиях, процессах, явлениях и т.п., рассматриваемых в аспекте их передачи в пространстве и во времени.
Существует несколько взглядов на сущность информации, однако большинство специалистов считает, что существует информация двух типов.
1. Информация техническая, которая передается по каналам связи и отображается на экранах дисплеев. Количество такой информации может быть точно вычислено, и процессы, происходящие с такой информацией, поддаются строгому анализу.
2. Информация семантическая, т.е. смысловая. Такого типа информация содержится, например, в литературном или музыкальном произведении. Хотя для анализа такой информации и предлагаются различные математические модели, количественные оценки на их основе весьма условны и приблизительны.
Информацию передают в виде сообщений. Они выражают информацию в определенной форме и предназначены для передачи от источника к адресату (телеграммы, речь, телеизображение, данные на выходе компьютера, команды системы автоматического управления объектами и т.п.).
Сообщения передают с помощью сигналов, которые являются носителями информации. Основным видом сигналов являются электрические сигналы, хотя в последнее время всё большее распространение получают оптические сигналы, например, в волоконно-оптических линиях передачи информации.
Объекты информационной техники
По функциональному назначению можно выделить следующие основные классы объектов информационной техники:
Структурная схема системы передачи информации показана на рис. 1.
Рис. 1. Структурная схема системы передачи информации
Передатчик преобразует исходное сообщение А(х) в сигнал , где х - независимая переменная. Сообщения и сигналы чаще всего рассматриваются в зависимости от времени (x = t). Роль линии связи может выполнять любая физиче ская среда (воздух, провода, оптическое волокно). В приёмнике полученный сигнал , искаженный влиянием помех, преобразуется в копию сообщения В(х), которая должна быть по возможности наиболее близка к оригиналу А(х).
Следует отметить, что эта модель может служить лишь простейшей иллюстрацией, поскольку не отражает всех действий, которые должны выполняться над информацией в процессе ее передачи от источника к потребителю.
Более полной является модель системы передачи (и хранения) информации, приведенная на рис. 2.
Рис. 2
Кратко охарактеризуем назначение и функции элементов этой модели.
1. Источник информации или сообщения - это физический объект, система или явление, формирующие передаваемое сообщение. Само сообщение - это значение или изменение некоторой физической величины, отражающие состояние объекта. Как правило, первичные сообщения - речь, музыка, изображения, измерения параметров окружающей среды и т.д. - представляют собой функции времени неэлектрической природы. С целью передачи по каналу связи эти сообщения преобразуются в электрический сигнал, изменения которого во времени λ(t) отображают передаваемое сообщение. Значительная часть передаваемых сообщений по своей природе не является сигналами - это массивы чисел, текстовые или иные файлы. Сообщения такого типа можно представить в виде некоторых векторов Λ.
2. Кодер источника. Подавляющая часть исходных сообщений - речь, музыка, изображения и т.д. - предназначена для непосредственного восприятия органами чувств человека и в общем случае плохо приспособлена для их эффективной передачи по каналам связи. Поэтому сообщения (λ(t) или Λ), как правило, подвергаются кодированию. В процедуру кодирования обычно включают и дискретизацию непрерывного сообщения λ(t), то есть его преобразование в последовательность элементарных дискретных сообщений { λi }.
Под кодированием в общем случае понимают преобразование алфавита сообщения A{ λi }, ( i = 1,2…K ) в алфавит некоторым образом выбранных кодовых символов R{ xj }, ( j = 1,2…N
Под кодированием источника будем понимать сокращение объема (сжатие) информации с целью повышения скорости ее передачи или сокращения полосы частот, требуемых для передачи.
Кодирование источника называют экономным, безызбыточным или эффективным кодированием, а также сжатием данных. Под эффективностью в данном случае понимается степень сокращения объема данных, обеспечиваемая кодированием.
Таким образом, на выходе кодера источника по передаваемому сообщению λ(t) или Λ формируется последовательность кодовых символов X, называемая информационной последовательностью, допускающая точное или приближенное восстановление исходного сообщения и имеющая, по возможности, как можно меньший размер.
3. Кодер канала. При передаче информации по каналу связи с помехами в принятых данных могут возникать ошибки.
Кодирование в канале, или помехоустойчивое кодирование, представляет собой способ обработки передаваемых данных, обеспечивающий уменьшение количества ошибок, возникающих в процессе передачи по каналу с помехами. На выходе кодера канала в результате формируется последовательность кодовых символов Y (X), называемая кодовой последовательностью.
4. Модулятор. Функции модулятора - согласование сообщения источника или кодовых последовательностей, вырабатываемых кодером, со свойствами канала связи и обеспечение возможности одновременной передачи большого числа сообщений по общему каналу связи.
Модулятор должен преобразовать сообщения источника (t) () или соответствующие им кодовые последовательности X и Y в сигналы S( t, (t) ), свойства которых обеспечивали бы наиболее эффективную передачу по каналам связи - телефонным, оптическим и т.д.
На сегодня существует большое количество методов модуляции сигналов, самыми простыми из них являются амплитудная, частотная и фазовая модуляции непрерывных сигналов.
5. Канал связи. Назначение канала связи – передача сигналов ит источника к потребителю информации. Проходя по каналу связи сигнал как правило, подвергается ослаблению, приобретает некоторую временную задержку и искажается. Для ослабления влияния этих нежелательных эффектов использует специальные средства.
Приемник. Назначение приемника - с максимально возможной точностью по принятому сигналу U(t) воспроизвести на своем выходе переданное сообщение (t) или .
6. Демодулятор. Для воспроизведения оценки сообщения *(t) или * приемник системы должен по принятому сигналу U(t) и с учетом сведений об использованных при передаче виде сигнала и способе модуляции получить оценку кодовой последовательности Y*((t)), называемую принятой последовательностью r. Эта процедура называется демодуляцией, детектированием или приемом сигнала. Демодуляция должна выполняться таким образом, чтобы принятая последовательность r в минимальной степени отличалась от переданной кодовой последовательности Y .
7. Декодер канала. Принятые последовательности r в общем случае могут отличаться от переданных кодовых слов Y, то есть содержать ошибки. Задача декодера канала - обнаружить и, по возможности, исправить эти ошибки. Процедура обнаружения и исправления ошибок в принятой последовательности r называется декодированием канала. Во тех случаях, когда требования к достоверности принимаемой информации очень велики (в компьютерных сетях передачи данных, в дистанционных системах управления и т.п.), передача без помехоустойчивого кодирования вообще невозможна.
8. Декодер источника. Поскольку информация источника (λ(t) , Λ) в процессе передачи подвергалась кодированию с целью ее более компактного (или более удобного) представления (кодирование источника), необходимо восстановить ее к исходному виду по принятой последовательности X*.
Многоканальная система передачи информации обеспечивает одновременную и взаимно независимую передачу сообщений от многих отправителей по одной общей линии связи.
Узел связи (информационный узел) обеспе чивает:
Информационная сеть является совокупностью информационных узлов, соединенных линиями связи.
На рис. 3. приведен пример графа информационной сети.
Рис. 3. Граф информационной сети (пунктир - возможные линии связи, сплошные - выбранные оптимальные линии связи)
Вершины графа , определяют информационные узлы, дуги - линии связи, координатами которых являются пропускная способность, интенсивность потока сообщений, стоимость канала связи и т.п. Информационную сеть рассматривают как сетевую систему массового обслуживания.
Виды сообщений в информационных системах
В информационных системах используется два типа сообщений.
Дискретное сообщение является последовательностью отдельных символов. Для преобразования дискретного сообщения в сигнал необхо димо выполнить операцию кодирования сообщения, при котором повышается скорость и помехоустойчивость передачи информации.
Непрерывное сообщение определяется непрерывной функцией времени. Непрерывные сообщения можно передавать дискретными методами. Для этого их подвергают дискретизации во времени и квантованию по уровню. На приёмной стороне выполняется восстановление непрерывной функции.
Формирование дискретных сообщений рассматривают как последовательный случайный выбор того или иного символа из алфавита источника сообщений, т.е. как формирование дискретной случайной последовательности.
Формирование непрерывных сообщений представляет собой выбор реализаций (случайных функций) непрерывного случайного процесса.
Основными информационными характеристиками являются количество информации в сообщениях, избыточность сообщений, энтропия, производительность источника сообщений, скорость передачи информации.
Для непрерывных, или аналоговых, сообщений (сигналов)
(min, max), t (0, t), (1)
то есть как само значение функции, так и значение аргумента для таких сообщений определены для любого значения непрерывного интервала как по , так и по t (рис. 4,а,б).
Многие сообщения - команды исполнительным устройствам, телеграфные сообщения, текстовая информация и т. п. - носят дискретный характер. При этом либо алфавит сообщения A (i )представляет собой множество
i = 1 , 2 , . . ., k , i = 1 , K (2)
(сообщения, дискретные или квантованные по уровню, рис. 4,в), либо сами сигналы передаются лишь в дискретные моменты времени
t = t1 , t2 , . . ., tm , i = 1 , M (3)
(дискретные по времени сообщения, рис. 4,г ), либо и то и другое (дискретные по времени и по уровню сигналы, или, как их иначе называют, цифровые сигналы, или сообщения, рис. 4,д, е).
Рис. 4.
Таким образом, можно выделить:
Исключительно важным положением теории связи является так называемая теорема дискретизации, или теорема Котельникова. Она позволяет установить соотношение между непрерывными сигналами и значениями этих сигналов лишь в отдельные моменты времени – так называемыми отсчетами. На использовании этой теоремы строится вся современная цифровая радиотехника – цифровые методы передачи и хранения звуковых и телевизионных сигналов, цифровые системы телефонной и сотовой связи, системы цифрового спутникового телевидения и т.д.
Теорема дискретизации формулируется следующим образом: непрерывная функция Х(t) с ограниченным спектром, то есть не имеющая в своем спектре составляющих с частотами, лежащими за пределами полосы f (-Fm , Fm), полностью определяется последовательностью своих отсчетов в дискретные моменты времени X( ti ), следующих с шагом t < 1/2Fm .
Таким образом, по дискретной последовательности отсчетов функции Х(i t) всегда можно восстановить исходную непрерывную функцию Х(t), если отсчеты брались с интервалом t 1/2Fm. Иначе говоря, любой непрерывный сигнал может быть преобразован в дискретную последовательность, а затем с абсолютной точностью восстановлен по последовательности своих дискретных значений.
Очень часто сообщения передаются сигналами, зависящими не только от времени - λ(t) (речь, музыка и т.п.), но и от других переменных, например, λ(x,y), λ(x,y,t) (статические и динамические изображения и т.п.). В этих случаях справедлива теорема дискретизации для двумерных (или в общем случае - для многомерных) сигналов. Она утверждает: функция двух переменных λ(x,y), спектр которых ограничен значениями fx max и fy max, однозначно определяется своими значениями в равноотстоящих точках плоскости переменных x и y, если интервал дискретизации удовлетворяет условию Δx ≤ 1/(2fx max ), Δy ≤ 1/(2fy max ). Дискретизация двумерной функции иллюстрируется рис. 5.
Рис. 5.
Итак, передачу практически любых сообщений можно свести к передаче их отсчетов, или чисел λi = λ(i t), следующих друг за другом с интервалом дискретизации t 1/2Fm ( или Δx ≤ 1/2fx мах , Δy ≤ 1/2fy мах ). При этом непрерывное (бесконечное) множество возможных значений сообщения λ(t) заменяется конечным числом дискретных значений {λ(i t)}. Однако сами эти числа имеют непрерывную шкалу уровней (значений), то есть принадлежат опять же континуальному множеству. Для абсолютно точного представления таких чисел, например, в десятичной форме, теоретически необходимо бесконечное число разрядов. К счастью, на практике часто нет необходимости в абсолютно точном представлении значений λi , как и любых чисел вообще.
Одной из причин этого является тем, что получатели информации - органы чувств человека, механизмы и т.д. - также обладают конечной разрешающей способностью, то есть не замечают незначительной разницы между абсолютно точным и приближенным значениями воспроизводимого сообщения.
С учетом этих замечаний можно подвергнуть отсчеты λi квантованию.
Процесс квантования состоит в замене непрерывного множества значений отсчетов i ( min , max ) дискретным множеством { (1),...,(m) } из алфавита A{ λi }. При этом точные значения чисел i заменяются их приблизительными (округленными до ближайшего разрешенного уровня) значениями. Интервал между соседними разрешенными уровнями i , или уровнями квантования, = (i+1) - (i) называется шагом квантования.
Различают равномерное и неравномерное квантование. Чаще применяется равномерное квантование (рис. 6), при котором шаг квантования постоянный: = λi - λi-1 = = const; однако иногда определенное преимущество дает неравномерное квантование, при котором шаг квантования i разный для различных λi (рис. 7).
Рис. 6 Рис. 7
Квантование приводит к искажению сообщений. Если квантованное сообщение для отсчета i = (iΔt), обозначить как λiq , то
где i - разность между квантованным сообщением (ближайшим разрешенным уровнем) λiq и истинным значением элементарного сообщения i, называемая ошибкой (или шумом) квантования. Шум квантования приводит к тому, что оценки λ*i, получаемые при приеме, отличаются от истинного значения i.
Поскольку квантование сообщений приводит к потере некоторой части информации, можно определить цену таких потерь d( , λq ) и среднюю величину ошибки, обусловленной квантованием:
В качестве цены потерь используется величина
Средняя ошибка квантования для равномерного N-уровневого квантования с шагом оказывается равной
и выбором шага квантования может быть сделана сколь угодно малой или сведена к любой наперед заданной величине.
Шумы квантования не имеют существенного значения, если эти искажения меньше ошибок, обусловленных помехами и допустимых техническими условиями.
Так, например, при передаче речи и музыки искажения практически не заметны, если все отсчеты случайным образом изменить на 0,1…1%, при передаче изображений - на 1% и т.д. Даже профессиональный эксперт не может заметить искажений в музыкальном произведении, если квантование производится с точностью лучше 0,001% (число уровней квантования N > 100000).
Лекция 2. Математическое описание и энергетические характеристики периодических сигналов.
Передача информации, то есть перенос информации в пространстве и времени, осуществляется сигналами. Сигналами называются физические процессы, параметры которых содержат информацию, т.е. сигналы являются материальными носителями информации. Модуляция заключается в изменении одного или нескольких параметров носителя в соответствии с передаваемой информацией. Эти параметры называются информационными.
В информационных системах в качестве носителей используются электрические сигналы, т.е. ток или напряжение, значения которых меняются по закону, отображающему передаваемое сообщение. Сигналы можно классифицировать по ряду признаков. Так различают дискретные и непрерывные сигналы, которые, в свою очередь, могут быть детерминированными или случайными.
Сигнал называется детерминированным, если он описывается заданной функцией времени. С информационной точки зрения это означает сигнал, соответствующий известному сообщению.
Случайным сигналом называют сигнал, математическим описанием которого является случайная функция времени.
Для образования сигналов используются в основном два типа носителей.
Первый тип носителя – гармоническое колебание, содержащее три параметра – амплитуду, частоту и фазу (Рис. 1а).
Рис.1 а. Гармоническое колебание
Второй тип носителя – последовательность импульсов (Рис. 1б). Здесь параметрами модуляции могут быть: амплитуда импульсов, фаза импульсов, частота импульсов, длительность импульсов или пауз, число импульсов и комбинация импульсов и пауз, определяющая код.
Рис.1 б. Последовательность импульсов
Простейшим периодическим сигналом является гармоническое колебание, определяемое законом:
при . Здесь - постоянные амплитуда, период, частота и фаза. Гармоническое колебание часто представляется также в виде
Чрезвычайно важным является то обстоятельство, что любой сложный периодический сигнал может быть представлен в виде суммы или ряда элементарных гармонических сигналов. Это преобразование осуществляется с помощью ряда Фурье.
Пусть заданная в интервале функция периодически повторяется с частотой , где - период, т.е.
для всех .
Если функция непрерывна (или имеет конечное число разрывов первого рода) в пределах одного периода, то она может быть представлена рядом Фурье в тригонометрической (3 а), или комплексной (3 б) формах
Здесь - постоянная составляющая, и - амплитуды косинусоидальных и синусоидальных членов разложения . Амплитуды могут быть рассчитаны по формулам
Амплитуда (модуль) и фаза (аргумент) - гармоники выражаются через и следующим образом:
.
В свою очередь, входящая в выражение (3б) комплексная амплитуда , связана с и следующими соотношениями
Комплексные амплитуды и являются взаимно сопряженными комплексными величинами. Легко показать, что справедливо соотношение
Совокупность коэффициентов называется спектром сигнала и полностью определяет его энергию.
В тех случаях, когда сигнал представляет собой функцию, четную относительно , т.е. , в тригонометрической записи остаются косинусоидальные члены (это очевидно из соотношения (4 в) ). Для нечетной относительно времени функции , наоборот, в нуль обращаются коэффициенты и ряд содержит только синусоидальные члены.
Структура частотного спектра периодического сигнала полностью определяется двумя характеристиками – амплитудной и фазовой, т.е. модулем и аргументом комплексной амплитуды (формулы (5а) и (5б)). Наглядное представление о “ширине” спектра и относительной величине отдельных его составляющих дает графическое изображение спектра (Рис. 2).
Рис. 2. Спектр периодической функции
На рисунке по оси ординат отложены модули амплитуд, по оси абсцисс – частоты гармоник. Как видно, спектр периодической функции состоит из отдельных “линий”, соответствующих дискретным частотам , в связи с чем и используется термин – линейчатый или дискретный спектр.
Важно понимать, что задание амплитудного спектра еще недостаточно для исчерпывающей характеристики сигнала – необходимо также знать фазы отдельных гармоник.
Если на вход линейной системы, характеристики которой известны, поступает сигнал , то для нахождения выходного сигнала необходимо учесть амплитудные и фазовые изменения, претерпеваемые каждой из гармонических составляющих сигнала при прохождении через рассматриваемую систему. Условие линейности системы позволяет рассматривать прохождение каждой из гармоник сигнала независимо от всех остальных гармоник.
В теории информации вводится понятие коэффициента передачи системы. Он представляет собой отношение комплексной амплитуды сигнала на выходе к комплексной амплитуде сигнала на входе и может быть записан в виде:
Для учета амплитудных и фазовых изменений комплексная амплитуда каждой из гармоник входного сигнала должна быть умножена на .
Если сигнал на входе линейной системы передачи имеет вид:
то сигнал на выходе может быть найден с помощью выражения
где и представляют собой соответственно комплексные амплитуды -й гармоники сигнала на входе и выходе системы передачи. Таким образом, для решения задачи о прохождении сигнала через систему достаточно умножить на комплексный коэффициент передачи .
Для практических приложений является очень важным вопрос о расчете энергетических характеристик сигналов, т.е. необходимо знать, какая часть энергии сигнала соответствует каждой из его гармонических составляющих. Сведения о распределении мощности в спектре сигнала позволяют выбирать полосу пропускания системы передачи информации. В связи с этим рассмотрим вопрос о расчете средней мощности периодического во времени сигнала.
Пусть сигнал представляет собой сложную периодическую функцию времени с периодом . Средней за период мощностью называется величина
где черта над функцией означает операцию усреднения по времени. Разложение сигнала в ряд Фурье
и подстановка этого выражения в формулу (11) позволяет получить выражение для средней мощности сигнала
,
где - постоянная составляющая, - амплитуда -й гармоники сигнала.
Таким образом, суммарную среднюю мощность сигнала можно представить в виде суммы мощностей отдельных гармонических составляющих.
Исследование различных видов модуляции необходимо для определения свойств каналов, улучшения использования мощности передающих устройств, определения потенциальной помехоустойчивости и исследования совместимости различных систем передачи информации.
Общий принцип модуляции состоит в изменении параметров носителя информации в соответствии с передаваемым сообщением. При модуляции меняется форма и ширина спектра передаваемого сигнала, а также устойчивость к воздействию помех.
Если информационный параметр, воздействующий на сигнал-переносчик, изменяется непре рывно, то методы модуляции являются непрерывными (амплитудная, фазовая и частотная модуляции).
Если в качестве сигнала-переносчика используют периодическую последовательность импульсов, то модуляцию называют импульсной (так, при изменении амплитуды или частоты импульсов по закону имеет место амплитудно-импульсная или частотно-импульсная модуляция соответствен но).
Информационный параметр может принимать счётное число значений, при этом модуляцию называют дискретной. К дискретным видам модуляции относятся, например, амплитудная, частотная и фазовая манипуляции. Если значения параметра закодированы и передаются в цифровой форме, то соответствующие виды модуляции носят название цифровой модуляции. Наиболее распространенным видом цифровой модуляции является импульсно-кодовая модуляция, когда значения сигнала в дискретных точках кодируют в цифровой форме.
При создании систем передачи сигналов основными задачами являются разработка методов оптимальной модуляции и демодуляции с точки зрения повышения скорости, достоверности и помехозащищённости передачи информации.
Если в качестве переносчика выбрано гармоническое колебание вида
то можно реализовать три вида модуляции: амплитудную (АМ), частотную (ЧМ) и фазовую (ФМ).
А. Амплитудная модуляция
Амплитудная модуляция (АМ) является самым простым и распространенным видом изменения параметров носителя информации. При АМ огибающая амплитуда гармонического колебания (переносчика) изменяется по закону, совпадающему с законом изменения передаваемого сообщения, частота же и начальная фаза колебания поддерживаются неизменными.
Для амплитудно-модулированного колебания выражение (1) принимает вид
где характер огибающей определяется видом передаваемого сообщения. В простейшем случае, когда модулирующая функция является гармоническим колебанием с частотой (см. Рис. 1)
где - частота модуляции, - фаза модулирующего сигнала, отношение называется коэффициентом модуляции. Таким образом, АМ сигнал описывается выражением
При условии (так называемая неискажающая модуляция) амплитуда модулированного колебания изменяется в пределах от минимальной до максимальной .
Рис.1. Колебание, модулированное по амплитуде гармонической функцией
Для определения свойств канала связи необходимо знать спектр модулированного колебания. Иначе говоря, необходимо установить связь между спектром модулированного колебания и спектром модулирующей функции .
Для простейшего случая гармонической модуляции легко представить выражение (4) в виде:
(использована формула для произведения косинусов двух углов). Первое слагаемое в (5) представляет собой исходное немодулированное колебание с частотой . Второе и третье слагаемые соответствуют новым гармоническим колебаниям, появляющимся в процессе модуляции амплитуды. Их частоты и называются верхней и нижней боковыми частотами модуляции.
Таким образом, к исходному гармоническому колебанию с частотой и амплитудой в результате амплитудной модуляции добавилось два новых с частотами , и амплитудами (Рис. 2).
Если управляющий сигнал обладает более сложным спектром (составлен из некоторого числа гармонических колебаний), каждая составляющая спектра дает свою пару боковых полос. В результате получается спектр, состоящий из двух полос, симметричных относительно несущей частоты .
В общем случае AM сигнал определяется выражением
где - информационный (модулирующий) сигнал, u(t) — сигнал-переносчик, т — коэффициент модуляции.
Построение амплитудного спектра модулированного колебания по заданному спектру передаваемого сообщения поясняется на Рис. 3 и 4. На Рис. 3 изображен спектр управляющего сигнала, а на Рис. 4 - спектр модулированного сигнала.
Рис. 2. Спектр амплитудно-модулированного колебания вида (4).
Рис. 3. Спектр управляющего (модулирующего сигнала)
Рис. 4. Спектр амплитудно-модулированного сигнала при сложной модулирующей функции (см. Рис.3).
Демодуляцию AM сигнала осуществляют путём выделения огибающей сигнала-переносчика на выходе детектора.
Б. Частотная модуляция
При частотной модуляции (ЧМ) информация передается путем модуляции частоты несущего колебания.
В простейшем случае гармонической частотной модуляции мгновенная частота колебания изменяется по закону
,
где называется девиацией частоты. Пример частотно-модулированного сигнала приведен на Рис. 5.
Рис. 5. Пример частотно-модулированного сигнала.
Спектр частотно-модулированного колебания даже в случае простейшей гармонической модуляции значительно сложнее, чем спектр амплитудно-модулированного сигнала. Он состоит из бесконечного числа боковых частот, расположенных попарно симметрично относительно несущей частоты и отличающихся от нее на , где - любое целое число.
Фазовая модуляция
Фазомодулированный (ФМ) сигнал имеет постоянную амплитуду, фаза сигнала изменяется пропорционально информационному сигналу, а именно
где 0 - несущая частота, m - индекс фазовой модуляции.
Для гармонического модулирующего сигнала
и малого индекса модуляции m<<1 формула (7) принимает вид
так как при . После преобразования второго слагаемого в (8) получим
т.е. величины спектральных составляющих идентичны величинам спектральных составляющих сигнала с синусоидальной AM, однако фазовые соотношения между несущей и боковыми составляющими различны.
Принципы амплитудной и частотной манипуляции
Манипуляция относятся к дискретным методам модуляции, в которых информационный параметр принимает счётное число значений.
Амплитудная манипуляция
При амплитудной манипуляции (АМн) информационным параметром является амплитуда сигнала-переносчика, которая изменяется скачкообразно под действием модулирующего сигнала.
Пусть переносчиком выступает гармоническое колебание
а модулирующим сигналом является периодическая последовательность модулирующих импульсов
где - длительность импульсов, - период следования импульсов. Аналитически АМн сигнал определяется выражением
В этом примере амплитуда манипулированного сигнала принимает два значения:
Обычно коэффициент модуляции m при АМн выбирается равным единице, поэтому амплитуда модулированного сигнала изменяется скачком в точках
и принимает два значения и 0. На рис. 6 показаны временные диаграммы модулирующего и манипулированного сигналов.
Рис. 6. Модулирующий и манипулированный сигналы.
Отношение периода следования импульсов к их продолжительности называется скважностью импульсов (в нашем примере ).
Частотная манипуляция
Сигнал с частотной манипуляцией (ЧМн) формируется в результате скачкообразного изменения частоты сигнала-переносчика. Например, при манипуляции со скважностью ЧМн сигнал внутри периода манипуляции определяется как
где - изменение частоты, Т - период изменения частоты (рис. 7).
Рис. 7. Модулирующая функция частотно манипулированного сигнала
Частота сигнала мгновенно изменяется между двумя значениями на оси частот. Результирующий сигнал можно рассматривать как суперпозицию двух модулированных прямоугольной последовательностью импульсов синусоидальных сигналов различной частоты, как показано на Рис. 8.
Рис. 8. Две составляющие частотно - манипулированного сигнала
Часто при манипуляции модулирующие сигналы не являются периодическими и представляют собой случайные последовательности (соответствующие последовательностям нулей и единиц при передаче информации).
Принципы импульсной и цифровой модуляции
При импульсной модуляции в качестве сигнала-переносчика используется периодическая последовательность импульсов
где - амплитуда импульсов, h(t) — функция, описывающая одиночный импульс последовательности, Т - период повторения импульсов, - длительность одного импульса.
В случае амплитудной импульсной модуляции (АИМ) амплитуда импульсов изменяется в соответствии с информационным сигналом , так что передаваемый сигнал определяется выражением
где m - коэффициент модуляции. Сигнал (12) приведен на Рис. 9.
Рис. 9. Модулирующий сигнал (а) и АИМ сигнал (б)
Цифровые методы модуляции
Цифровые методы модуляции используются для передачи кодированных сообщений дискретными методами. Их сущность заключает ся в том, что передаваемый непрерывный сигнал дискретизируется во време ни, квантуется по уровню и полученные отсчеты преобразуются в кодовые комбинации. Полученной по следовательностью кодовых сигналов модулируется высокочастотный сигнал-переносчик. Таким образом, цифровые методы модуляции основаны на дискретизации, квантовании и кодировании.
Достоинствами цифровых методов модуляции являются:
В настоящее время наибольшее распространение получили системы с импульсной кодовой модуляцией (ИКМ), в которых значение сигнала в дискретные моменты времени преобразуется в двоичные цифровые коды.
А. Цифровая амплитудно-импульсная модуляция
Предположим, что кодовое сообщение представляет собой последовательность двоичных трехразрядных чисел в качестве одиночных слов. Таким образом, всего имеется 23 = 8 возможных слов. Каждому из 8 слов ставится в соответствии отдельный сигнал длительностью в три тактовых импульса 3 L. В случае АИМ восемь сигналов имеют форму импульсов с восемью возможными значениями амплитуды как показано на рис. 10. Максимальная амплитуда равна А , минимальная — 0, остальные значения амплитуды кратны величине А/7. Пусть указанный на рисунке сигнал передается по каналу.
Напряжение на входе приемника представляет собой передаваемый сигнал, искаженный помехой.
Рис. 10. Преобразование сигналов при цифровой АИМ
Для восстановления кодовой последовательности приемник усредняет принимаемый сигнал в течение каждого интервала 3 L, что минимизирует влияние шума.
Для того, чтобы принимаемое решение о том, какой уровень был передан на предыдущем интервале, имело высокую достоверность, среднеквадратичное значение шума должно быть мало по сравнению с расстояниями между уровнями .
Б. Импульсно-кодовая модуляция
Различие между импульсно-кодовой модуляцией (ИКМ) и АИМ показано на рисунке 11. Каждый разряд двоичного числа передается в отдельности: 1 - импульсом длительностью L и амплитудой В , а 0 - отсутствием импульса. При одной и той же вероятности ошибок ИКМ система может иметь примерно в 10 раз меньшую мощность сигнала по сравнению с АИМ, а при равных мощностях ИКМ система имеет гораздо лучшие характеристики.
Рис. 11. Преобразование сигналов в ИКМ
В. Фазоимпульсная модуляция
Принцип фазоимпульсной модуляции иллюстрируется на рис. 12. В каждом интервале длительностью 3 L передается один импульс с фиксированной амплитудой, но его длительность составляет всего 3L/8 и он находится в одном из восьми временных положений.
ФИМ система обеспечивает такое же качество, как и ИКМ при снижении на 1/3 средней мощности сигнала, но требуемая полоса частот в этом случае расширяется в три раза. Таким образом, в смысле обмена полосы на соотношение сигнал-шум, ФИМ-система уступает ИКМ-системе.
Рис. 12. Преобразование сигналов при ФИМ
Лекция 4. Характеристики и модели каналов передачи информации
Канал передачи информации (канал связи) представляет совокупность средств, предназначенных для передачи сигналов (сообщений) между различными точками информационной системы. Под средствами понимаются и технические устройства, и линия связи – физическая среда, в которой распространяется сигнал. Канал можно представить как последовательное соединение устройств (блоков), выполняющих различные функции в общей системе передачи информации.
В зависимости от назначения информационной системы каналы делят на телеграфные, телефонные, звукового вещания, передачи данных, телевизионные, телеметрические и т.д.
В зависимости от характера физической среды, в которой распространяются сигналы, выделяют радиоканалы (в частности, космические каналы), и каналы проводной связи (кабельные, волоконно-оптические линии связи, волноводные СВЧ - тракты и т.д.) .
В зависимости от характера связи между сигналами на входе и выходе канала различают линейные и нелинейные каналы.
При использовании электрических сигналов для передачи информации важна классификация каналов по диапазону рабочих частот, так как именно этот фактор определяет пропускную способность канала.
1. На современных кабельных линиях связи применяют сигналы, занимающие полосы частот в диапазоне до нескольких сотен килогерц.
2. Коаксиальные кабели, являющиеся основой сетей магистральной связи, пропускают диапазон частот до сотни мегагерц.
3. При передаче сигналов по радиоканалам используются частоты от
4. В настоящее время благодаря внедрению оптических лазеров освоен и оптический диапазон. В волоконно-оптических линиях связи используются частоты порядка
Для современного этапа развития техники передачи информации характерна тенденция к переходу на все более высокие частоты. Важнейшей причиной этого является необходимость повышения скорости передачи сообщений (увеличение быстродействия систем).
Для теории передачи информации важна классификация каналов связи по характеру сигналов на входе и выходе канала. Различают каналы:
1) непрерывные по уровням, на входе и выходе которых сигнал непрерывен. Примером может служить канал, заданный между выходом модулятора и входом демодулятора в любой системе передачи информации.
2) дискретные по уровням, на входе и выходе которых сигналы дискретны. Примером такого канала является канал, заданный от входа кодирующего устройства до выхода декодера.
3) дискретные со стороны входа и непрерывные со стороны выхода или наоборот. Такие каналы называются дискретно – непрерывными или полунепрерывными. Пример – канал, заданный между входом модулятора и входом демодулятора или между выходом модулятора и выходом декодера.
Структурная схема канала передачи информации приведена на Рис. 1.
Рис. 1. Структурная схема передачи информации
Важно понимать, что всякий дискретный или полунепрерывный канал содержит внутри себя непрерывный канал. Вообще дискретность и непрерывность канала не связана с характером сообщений: можно передавать дискретные сообщения по непрерывному каналу и непрерывные сообщения – по дискретному.
Анализ непрерывных каналов
Так как непрерывные каналы являются основной составной частью всех других каналов, результаты анализа непрерывных каналов широко используются для решения задач анализа и синтеза систем передачи информации. Основными задачами анализа непрерывных каналов являются анализ линейных и нелинейных искажений сигналов в каналах и анализ влияния помех в каналах.
При рассмотрении помех в непрерывных каналах выходной сигнал представляют в виде
где - входной сигнал, - соответственно мультипликативная и аддитивная помехи, - задержка сигнала в канале.
Мультипликативные помехи обусловлены случайными изменениями коэффициента передачи канала из-за изменения характеристик среды, в которой распространяются сигналы.
Аддитивные помехи обусловлены флуктуационными явлениями (случайными колебаниями тока и напряжения), связанными с тепловыми процессами в проводах, резисторах, транзисторах и других элементах схем, наводками под действием атмосферных явлений (грозы и др.) и индустриальных процессов (работа промышленных установок, других линий связи и т.п.). Флуктуационная аддитивная помеха характеризуется “размытостью” энергии спектра в широком диапазоне частот и обусловлена главным образом внутренними шумами элементов аппаратуры (тепловой или белый шум). Средняя мощность теплового шума в полосе частот полезного сигнала равна
,
а спектральная плотность (т.е. мощность, заключенная в единичной полосе частот)
где - постоянная Больцмана, T – абсолютная температура. Флуктуационную помеху невозможно устранить, можно лишь учесть ее характеристики при синтезе такой системы, в которой данная помеха несущественно сказывается на качестве передачи информации.
В настоящее время разработано большое количество моделей непрерывных каналов, наиболее простыми и распространенными из которых являются модель идеального канала и модель гауссовского канала.
Идеальный канал можно применять как модель реального непрерывного канала, если можно пренебречь наличием помех, считать, что преобразование сигналов в канале является детерминированным, а мощность и полосу сигналов – ограниченными. Такая модель слабо отражает реальные условия и ее применяют чаще всего для анализа линейных и нелинейных искажений в многоканальных системах проводной связи.
Гауссовский канал характеризуется следующими допущениями: коэффициент передачи и время задержки сигналов в канале не зависят от времени и являются детерминированными величинами, в канале действует аддитивная флуктуационная помеха – гауссовский “белый шум” . Такая модель позволяет анализировать амплитудные и фазовые искажения сигналов и влияние флуктуационной помехи, и, как следствие, часто применяется как модель реальных каналов проводной связи.
Анализ дискретных каналов
Для анализа дискретных каналов разработан целый ряд специальных математических моделей и методов. Они позволяют определять характеристики дискретных каналов, такие как условные вероятности появления ошибок, полные вероятности появления ошибки и правильного приема, вероятности появления различных символов на выходе дискретного канала и др.
Дискретный канал образуют, например, устройства тракта “вход кодера - выход декодера (см. Рис. 1.). На вход канала поступают символы а с выхода - . Математическая модель дискретного канала определена, если известны следующие характеристики: алфавит и априорные вероятности появления символов сообщений (; - объем алфавита); скорость передачи символов; алфавит символов копии сообщений (; - объем алфавита), априорная условная вероятность появления символа при условии, что был передан символ .
Первые две характеристики определяются свойствами источника сообщений и полосой пропускания непрерывного канала. Объем выходного алфавита определяется способом построения системы передачи информации. Условная вероятность определяется в основном свойствами непрерывного канала. Часто в системе используется “стирание” символов – тогда, когда из-за искажений и помех неясно, какой символ передавался. Решающее устройство декодера выдает символ стирания, если символ настолько отличается от символа источника сообщений, что его нельзя с разумной вероятностью отождествить ни с одним из передаваемых.
Результатом анализа дискретного канала является определение апостериорной условной вероятности 
того, что при получении символа передавался символ .
С помощью этих апостериорных вероятностей и априорных вероятностей рассчитывают полную вероятность появления ошибки в канале, полную вероятность правильного приема, вероятность появления символов на выходе канала, информационные характеристики дискретного канала (скорость передачи информации, пропускную способность, количество принятой информации и др.).
Апостериорная вероятность рассчитывается по формуле Байеса:
Если решающая схема декодера реализует алгоритм определения максимума апостериорной вероятности:
то на выходе декодера появится символ 
, апостериорная вероятность появления которого больше всех остальных.
Характер условных вероятностей полностью определяет свойства дискретного канала. Если для любых пар и эта вероятность не зависит от момента времени t, то канал называют однородным, в противном случае - неоднородным.
Если справедливо условие
то канал называют каналом без памяти, если же нет – говорят, что канал обладает памятью на символов. Является ли канал однородным и без памяти зависит от того, на каком непрерывном канале построен дискретный канал. Например, если непрерывный канал является гауссовым, то построенный на нем дискретный канал является однородным и без памяти.
Несмотря на то, что реальные дискретные каналы являются, как правило, неоднородными и с памятью, модель дискретного однородного канала без памяти находит широкое применение в качестве разумного приближения. Она позволяет упростить анализ и получение исходных данных.
Для математического описания дискретных однородных каналов без памяти используют матрицы вида:
элементами которых являются условные вероятности . Совместно с априорными вероятностями эти вероятности перехода -го символа в -й полностью определяют вероятностные характеристики дискретных каналов.
Математическим аппаратом, позволяющим описывать дискретные каналы, является теория марковских цепей.
Если являются дискретными независимыми символами, то полной характеристикой служит распределение вероятностей появления символа . Так как совокупность образует полную группу, то
(условие нормировки).
Если символы последовательности взаимозависимы (коррелированны), то помимо вероятности появления отдельных символов необходимо задавать условные вероятности появления в последовательности символа при условии, что перед ним появилась группа символов . Последовательности, в которых существуют такие статистические связи между символами, являются марковскими цепями. Если статистическая связь существует только между символами , то марковскую цепь называют простой и ее поведение полностью описывается матрицей (6) при заданных начальных вероятностях . Для эргодической марковской цепи вероятности появления символов в установившемся режиме находят из решения системы алгебраических уравнений
с использованием условия нормировки.
Математическое описание дискретных однородных каналов без памяти основано на теории марковских простых однородных цепей.
Определим вероятностные характеристики двоичного дискретного однородного канала без памяти. В этом случае . Для простоты записи обозначим ,
Вероятности - это условные вероятности правильного приема символов , а - вероятности появления ошибок.
Мы рассмотрим простейший случай, когда искажения сигналов в канале отсутствуют и непрерывный канал является гауссовым. В этом случае изменение формы сигнала обусловлено лишь действием флуктуационной помехи.
Если , то канал называется симметричным. В теории передачи сигналов показано, что для симметричного гауссового канала условная вероятность появления ошибки определяется соотношением
где - функция Лапласа
а в качестве аргументов выступают - разность энергий различаемых сигналов (например, соответствующих нулю и единице),
и - спектральная плотность гауссовского “белого шума”. Следует отметить, что величина имеет специальное название (“отношение сигнал – шум” – “signal – to – noise ratio”) и чрезвычайно широко используется в теории связи. При заданном отношении S/N вероятность ошибочного приема легко найти из (8), используя табулированные значения функции Лапласа.
Безусловную вероятность ошибки можно определить по формуле полной вероятности
Полная вероятность правильного приема сигналов равна
поскольку
Так как символы дискретных сообщений кодируют кодовыми комбинациями, которые включают n элементарных кодовых сигналов, то важно уметь определять вероятность того, что в кодовой комбинации будет некоторое число (q) ошибочно принятых элементарных сигналов. Величину q называют кратностью ошибок. Если все элементарные сигналы в кодовой комбинации независимы, эта вероятность описывается биномиальным распределением (формулой Бернулли)
где - число сочетаний, - вероятность появления ошибки при передачи одного элементарного сигнала. Среднее число ошибок равно
Если , что обычно справедливо для реальных каналов, то максимальной является вероятность того, что ошибок не будет. С ростом q функция монотонно убывает. В связи с этим ошибки большой кратности (q >1) встречаются редко. Этот вывод справедлив для однородных каналов без памяти при условии . Поэтому в первую очередь обращают внимание на обнаружение и исправление ошибок малой кратности.
Лекция 5. Информация и энтропия.
Мера количества информации
Как уже отмечалось, в теории информации изучаются количественные закономерности передачи, хранения и обработки информации. Основное внимание в ТИ уделяется определению средней скорости передачи информации и решению задачи максимизации этой скорости путем применения соответствующего кодирования. Предельные соотношения ТИ позволяют оценить эффективность различных систем связи и установить условия согласования в информационном отношении источника с каналом и канала с потребителем.
Для исследования этих вопросов необходимо прежде всего установить универсальную количественную меру информации, не зависящую от конкретной физической природы передаваемых сообщений. Когда принимается сообщение о каком-либо событии, наши знания о нем изменяются, т.к. мы получаем о этом событии некоторую информацию. Сообщение о хорошо известном событии, очевидно, никакой информации не несет. Напротив, сообщение о малоизвестном событии несет много информации.
Таким образом, количество информации в сообщении о некотором событии существенно зависит от вероятности этого события. В основу определения меры количества информации положен вероятностный подход.
Для количественного определения информации можно, в принципе, использовать любую монотонно убывающую функцию вероятности , где - вероятность сообщения (например ). Однако оказывается более удобным исчислять количество информации в логарифмических единицах, т.е. определять количество информации в отдельно взятом сообщении как
Так как , то величина всегда положительна и конечна. При количество информации равно нулю, т.е. сообщение об известном событии никакой информации не несет. Логарифмическая мера обладает естественным в данном случае свойством аддитивности, согласно которому количество информации, содержащееся в нескольких независимых сообщениях, равно сумме количества информации в каждом из них. Действительно, так как совместная вероятность независимых сообщений
то количество информации в этих сообщениях равно
что соответствует интуитивным представлениям об увеличении информации при получении дополнительных сообщений. Основание логарифма k может быть любым. Чаще всего принимают k = 2, и тогда количество информации выражается в двоичных единицах (“binary digit” - битах).
В двоичных системах передачи информации используется лишь два символа, условно обозначаемых как 0 и 1. В таких системах при независимых и равновероятных символах, когда , каждый из них несет одну двоичную единицу информации
Формула (1) позволяет вычислять количество информации в сообщениях, вероятность которых отлична от нуля. Предполагается, что сообщения дискретны, а их число ограниченно. В таких случаях говорят, что имеется ансамбль сообщений, который описывается совокупностью возможных сообщений и их вероятностей
Ансамбль сообщений образует полную группу событий, поэтому всегда
Если все сообщения равновероятны:
то количество информации в каждом из них определяется величиной
Отсюда следует, что количество информации в сообщении зависит от ансамбля, из которого оно выбирается. До передачи сообщения имеется неопределенность относительно того, какое из m сообщений ансамбля будет передано. После приема сообщения эта неопределенность снижается. Очевидно, что чем больше m, тем больше неопределенность и тем большее количество информации содержится в переданном сообщении.
Рассмотрим пример. Пусть ансамбль возможных сообщений представляет собой алфавит, состоящий из m различных букв. Необходимо определить, какое количество информации содержится в передаваемом слове длиной n букв, если вероятности появления букв одинаковы, а сами буквы следуют независимо друг от друга. Количество информации при передаче одной буквы
Так как все буквы равновероятны, то и количество информации, содержащееся в любой букве, . Так как мы предполагаем, что буквы следуют независимо друг от друга, то количество информации в слове из n букв равно
Для двоичного кода ансамбль элементарных сообщений состоит из двух элементов : 0 и 1 (m = 2). В этом случае сообщение из n элементов несет информацию
В общем случае при передаче сообщений неопределенность снимается не полностью. Так в канале с шумами возможны ошибки. По принятому сигналу только с некоторой вероятностью можно судить о том, что было передано сообщение a. Поэтому после получения сообщения остается некоторая неопределенность, характеризуемая величиной апостериорной вероятности , а количество информации, содержащееся в сигнале , определяется степенью уменьшения неопределенности при его приеме. Если - априорная вероятность, то количество информации в принятом сигнале относительно переданного сообщения a равно
Это выражение можно рассматривать также как разность между количеством информации, поступившим от источника сообщений, и тем количеством информации, которое потеряно в канале за счет действия шумов.
Энтропия источника дискретных сообщений
А. Энтропия источника независимых сообщений
Мы определили количество информации, содержащееся в отдельном сообщении. Во многих случаях, например при согласовании канала с источником информации, возникает необходимость в характеристиках, позволяющих оценивать информационные свойства источника сообщений в целом. Одной из важнейших характеристик такого типа является среднее количество информации, приходящееся на одно сообщение.
В простейшем случае, когда все сообщения равновероятны, количество информации в каждом из них одинаково и равно
При этом среднее количество информации равно . Следовательно, при равновероятных независимых сообщениях информационные свойства источника зависят только от числа сообщений в ансамбле m.
Однако в реальных условиях сообщения, как правило, имеют разную вероятность. Например, буквы О, Е и А встречаются в тексте сравнительно часто, тогда как Щ, Ы и Ъ – достаточно редко. Поэтому знания числа сообщений m в ансамбле недостаточно и требуется иметь сведения о вероятности каждого сообщения . Так как вероятности сообщений неодинаковы, то они несут различное количество информации:
Среднее количество информации, приходящееся на одно сообщение источника, определяется как математическое ожидание :
Величина называется энтропией. Этот термин заимствован из термодинамики, где он характеризует неопределенность состояния физической системы.
В теории информации энтропия также характеризует неопределенность ситуации до передачи сообщения, поскольку заранее неизвестно, какое из сообщений будет передано. Важно понимать, что чем больше энтропия, тем сильнее неопределенность и тем большую информацию в среднем несет одно сообщение источника.
В качестве примера вычислим энтропию источника сообщений, когда ансамбль сообщений состоит лишь из двух сообщений и , характеризуемых вероятностями . Энтропия такого источника в соответствии с (10) будет равна
Зависимость энтропии от величины p приведена на Рис. 1.
Рис. 1. Зависимость энтропии от вероятности
Максимум энтропии имеет место при , т.е. когда ситуация является наиболее неопределенной. При или , что соответствует передаче одного из сообщений или , неопределенность отсутствует. В этих случаях энтропия равна нулю.
Среднее количество информации, содержащееся в последовательности из n сообщений, равно
Отсюда следует, что количество передаваемой информации можно увеличить не только за счет числа сообщений, но и путем повышения энтропии источника, т.е. информационной емкости его сообщений.
Обобщая эти результаты, можно сформулировать основные свойства энтропии источника независимых сообщений:
энтропия максимальна и равна
Б. Энтропия источника зависимых сообщений
Рассмотренный нами источник независимых сообщений является простейшим типом источника. В реальных условиях картина значительно усложняется из-за наличия статистических связей между сообщениями. Примером может служить обычный текст, где появление той или иной буквы зависит от предыдущих буквенных сочетаний. Так например, после сочетания ЧТ вероятность следования гласных букв О, Е или И значительно выше, чем согласных.
Статистическая связь ожидаемого сообщения с предыдущим сообщением количественно оценивается совместной вероятностью или условной вероятностью , которая выражает вероятность появления сообщения при условии, что известно предыдущее сообщение . Количество информации, содержащейся в сообщении при условии, что известно предыдущее сообщение согласно (1) будет равно
Среднее количество информации при этом определяется условной энтропией , которая вычисляется как математическое ожидание информации по всем возможным сообщениям .
Важным свойством условной энтропии источника зависимых сообщений является то, что при неизменном количестве сообщений в ансамбле источника его энтропия уменьшается с увеличением числа сообщений, между которыми существует статистическая взаимосвязь. В соответствии с этим свойством, а также свойством энтропии источника независимых сообщений можно записать неравенства
Таким образом, наличие статистических связей между сообщениями всегда приводит к уменьшению количества информации, приходящейся в среднем на одно сообщение.
Избыточность источника сообщений
Уменьшение энтропии источника с увеличением статистической взаимосвязи (14) можно рассматривать как снижение информационной емкости сообщений. Одно и то же сообщение при наличии взаимосвязи содержит в среднем меньше информации, чем при ее отсутствии. Иначе говоря, если источник создает последовательность сообщений, обладающих статистической связью, и характер этой связи известен, то часть сообщений, выдаваемых источником, является избыточной, так как она может быть восстановлена по известным статистическим связям. Появляется возможность передавать сообщения в сокращенном виде без потери информации. Например при передаче телеграммы из текста исключаются союзы, предлоги, знаки препинания, так как они легко восстанавливаются при чтении телеграммы на основании известных правил построения фраз и слов.
Говорят, что любой источник зависимых сообщений обладает избыточностью. Количественное определение избыточности может быть получено из следующих соображений. Для того чтобы передать количество информации , источник без избыточности должен выдать в среднем сообщений, а источник с избыточностью сообщений.
Поскольку и , то для передачи одного и того же количества информации источник с избыточностью должен использовать большее количество сообщений. Избыточное количество сообщений равно , а избыточность определяется как отношение
Величина избыточности согласно (14) является неубывающей функцией. Для русского языка, например, избыточность составляет порядка 50%.
Коэффициент
называется коэффициентом сжатия. Он показывает, до какой величины можно сжать передаваемые сообщения, если устранить избыточность. В связи с тем, что обладающий избыточностью источник передает излишнее количество сообщений, увеличивается продолжительность передачи и снижается эффективность использования канала связи. Требуется проводить сжатие сообщений, которое реализуется с помощью соответствующего кодирования. Информацию необходимо передавать такими сообщениями, емкость которых используется наиболее полно.
Вместе с тем избыточность источника далеко не всегда является отрицательным свойством. Наличие взаимосвязи между буквами текста дает возможность восстановить его при искажении отдельных букв, т.е. использовать избыточность для повышения достоверности передачи информации.
Лекция 6. Пропускная способность дискретных каналов и эффективность систем передачи информации
Скорость передачи информации и пропускная способность дискретного канала без помех
Так как передача информации происходит во времени, естественно ввести понятие скорости передачи как количество информации, передаваемой в среднем за единицу времени
Здесь - количество информации, содержащейся в последовательности сообщений , общая длительность которых равна T.
Количество информации, создаваемое источником сообщений в среднем за единицу времени, называется производительностью источника . Эту величину удобно выразить через энтропию источника . При можно считать и , где n – число сообщений, а - средняя продолжительность одного сообщения. Подставляя в (1) значения и , получим
Величина для независимых сообщений может быть вычислена как математическое ожидание
где - вероятность сообщения длительностью . Если длительность всех сообщений одинакова и равна , формула (2) принимает вид
Отсюда следует, что наибольшей производительностью обладает источник с максимальной энтропией (см. ф.(12) прошлой лекции), т.е.
Выданная источником информация в виде отдельных сообщений поступает в канал связи, где осуществляется кодирование и ряд других преобразований, в результате которых информация переносится уже сигналами , имеющими другую природу и в общем случае обладающими другими статистическими характеристиками. Для сигналов также может быть найдена скорость передачи по каналу связи
Высокая скорость передачи является одним из основных требований, предъявляемых к системам передачи информации. В реальных условиях всегда существует ряд причин, ведущих к ее ограничению.
Во-первых, в реальном канале число используемых сигналов всегда конечно и энтропия в соответствии с ф.(12) прошлой лекции, есть величина ограниченная
С другой стороны, уменьшение длительности сигнала приводит к расширению спектра, что при учете ограниченной полосы пропускания канала ставит предел уменьшению средней длительности .
Максимально возможная скорость передачи информации по каналу связи называется пропускной способностью канала
Максимум скорости R здесь ищется по всем возможным ансамблям сигналов u .
Пусть число используемых сигналов не превышает m, а их длительность не может быть меньше секунд. Так как и независимы, то по формуле (8) следует искать максимум и минимум , что дает
Для двоичных сигналов m = 2 и пропускная способность
Оптимальное статистическое кодирование сообщений
Для дискретных каналов без помех Шенноном была доказана следующая теорема: если производительность источника меньше пропускной способности канала (), то всегда существует способ кодирования, позволяющий передавать по каналу все сообщения источника. Передачу всех сообщений при осуществить невозможно.
Смысл теоремы сводится к тому, что, как бы ни была велика избыточность источника, все его сообщения могут быть переданы по каналу, если .
Для рационального использования пропускной способности канала необходимо применять соответствующие способы кодирования сообщений.
Статистическим или оптимальным называется кодирование, при котором наилучшим образом используется пропускная способность канала без помех. При оптимальном кодировании фактическая скорость передачи информации по каналу R приближается к пропускной способности C, что достигается путем согласования источника с каналом. Сообщения источника кодируются таким образом, чтобы они в наибольшей степени соответствовали ограничениям, которые накладываются на сигналы, передаваемые по каналу связи. Поэтому структура оптимального кода зависит как от статистических характеристик источника, так и от особенностей канала.
Рассмотрим основные принципы оптимального кодирования на примере источника независимых сообщений, который необходимо согласовать с двоичным каналом без помех. Здесь процесс кодирования заключается в преобразовании сообщений источника в двоичные кодовые комбинации. Поскольку существует однозначное соответствие между сообщениями источника и комбинациями кода, то энтропия кодовых комбинаций равна энтропии источника
а скорость передачи в канале определяется с помощью (6) как
Здесь - средняя длительность кодовой комбинации, которая в общем случае неравномерного кода записывается по аналогии с (3) как
где - длительность одного элемента кода и - число элементов в комбинации, присваиваемой сообщению .
Подстановка в формулу (12) выражений
и (13) дает
в котором числитель определяется исключительно статистическими свойствами источника, а величина - характеристиками канала.
Возникает вопрос: можно ли так закодировать сообщение, чтобы скорость передачи (14) достигала своего максимального значения, равного пропускной способности двоичного канала . Легко заметить, что это условие выполняется, если
что соответствует минимуму и максимуму R.
Одним из кодов, удовлетворяющих условию (33), является код Шеннона – Фано, который мы рассмотрим позднее.
Необходимо подчеркнуть, что при оптимальном способе кодирования в сигналах, передающих сообщения источника, совершенно отсутствует избыточность. Устранение избыточности приводит к тому, что процесс декодирования становится весьма чувствительным к воздействию помех. Это особенно сильно проявляется при оптимальном кодировании зависимых сообщений. Иногда одна единственная ошибка может вызвать неправильное декодирование всех последующих сигналов. Поэтому оптимальные коды применимы только для каналов с чрезвычайно низким уровнем помех.
Скорость передачи информации и пропускная способность дискретных каналов с помехами
Каналы без помех характеризуются тем, что количество принятой на выходе канала информации всегда равно количеству информации, переданной источником сообщений.
При этом, если на вход канала поступил сигнал , то на выходе возникает сигнал , однозначно определяющий переданный сигнал . Количество информации, прошедшее по каналу без помех в случае передачи и приема , равно количеству информации, содержащейся в сигнале :
Здесь величина вероятности характеризует ту неопределенность в отношении сигнала , которая существовала до его передачи. После приема в силу однозначного соответствия между и неопределенность полностью устраняется.
Совершенно другое положение имеет место для каналов, где присутствуют различного рода помехи.
Воздействие помех на передаваемый сигнал приводит к необратимой потере части информации, поступающей от источника сообщений. Так как в канале с помехами принятому сигналу может соответствовать передача одного из нескольких сигналов , то после приема остается некоторая неопределенность в отношении переданного сигнала. Здесь соответствие между и носит случайный характер, и степень неопределенности характеризуется условной апостериорной вероятностью . Количество информации, необходимое для устранения оставшейся неопределенности
очевидно, равно той части информации, которая была потеряна вследствие помех. Количество принятой информации определяется как (см. ф. (9) прошлой лекции)
Для оценки среднего количества принятой информации при передаче одного сообщения выражение (17) необходимо усреднить по всему ансамблю и :
где - совместная вероятность переданного и принятого сигналов, - количество сигналов в ансамбле на входе канала и - количество сигналов в ансамбле на выходе канала (в общем случае ).
Величина характеризует в среднем количество информации, которое содержит принятый сигнал относительно переданного сигнала и называется средней взаимной информацией между и .
Выражение (18) можно представить в виде
где
представляет энтропию источника сигналов и
- условная энтропия или ненадежность.
Формула (19) показывает, что среднее количество принятой информации равно среднему количеству переданной информации минус среднее количество информации , потерянное в канале вследствие воздействия помех.
Понятия скорости передачи информации и пропускной способности используются и для каналов с помехами. В этом случае скорость передачи информации по каналу можно представить в виде
Пропускная способность канала с помехами определяется как максимально возможная скорость передачи при ограничениях, накладываемых на передаваемые сигналы
Для каналов с сигналами одинаковой длительности , пропускная способность равна
где максимум ищется по всем возможным ансамблям сигнала .
Выведем выражение для пропускной способности двоичного канала с помехами, по которому передаются независимые дискретные сигналы с априорными вероятностями . На выходе канала образуются сигналы , при правильном приеме отражающие сигналы . В результате действия помех возможны ошибки, которые характеризуются при передаче условной вероятностью , а при передаче - условной вероятностью .
Будем полагать, что канал симметричен, т.е. для него вероятности переходов одинаковы , а полная вероятность ошибки равна
При этих условиях можно показать, что пропускная способность двоичного симметричного канала равна
На Рис. 1. приведена зависимость пропускной способности канала С от вероятности ошибки для двоичного канала согласно формуле (26)
Рис. 1. Зависимость пропускной способности двоичного канала от вероятности ошибки .
Видно, что увеличение вероятности ошибки приводит к снижению пропускной способности, которая становится равной нулю при = 0,5. В этом случае полностью исчезает какая-либо зависимость между передаваемым и принятым сигналами. Таким образом, значение = 0,5 для бинарного симметричного канала является предельным.
Теорема Шеннона для дискретного канала с помехами
Данная теорема имеет фундаментальное значение для теории и техники передачи информации.
Если производительность источника не превышает пропускной способности дискретного канала с помехами (), то существует способ кодирования, позволяющий передать все сообщения источника со сколь угодно малой вероятностью ошибки. При такая передача невозможна.
Таким образом, наличие помех в канале не препятствует передаче сообщений со сколь угодно малой вероятностью ошибок декодирования, а лишь ограничивает максимальную скорость передачи информации С. Высокая достоверность декодирования и конечная скорость передачи не исключают друг друга.
Вместе с тем теорема не указывает конкретного способа наилучшего кодирования. До сих пор продолжаются поиски способов кодирования, которые позволяли бы с аппаратурой приемлемой сложности достигать предельных возможностей, указанных теоремой Шеннона.
Пропускная способность непрерывного канала. Формула Шеннона
Шенноном была получена также формула для пропускной способности непрерывного канала, в котором помехой является аддитивный шум . Если средние мощности сигнала и шума ограничены величинами , и ширина их спектра равна F, то формула Шеннона имеет вид
Данная формула очень важна, т.к. она показывает те предельные возможности, к которым следует стремиться при разработке систем передачи информации. Формула выведена для равномерных спектров сигнала и шума, но может быть распространена и на более реальный случай неравномерных спектров. Оказывается, при заданных спектрах сигнала и шума максимума пропускной способности можно добиться путем увеличения мощности сигнала на тех частотах, где уменьшается мощность шума и наоборот. Минимальная пропускная способность соответствует равномерному спектру шума, т.е. “белый шум” является самым вредным видом помех.
Эффективность систем передачи информации
Пропускная способность канала связи С является тем пределом, которого можно достигнуть при идеальном кодировании. Естественно, что в реальных каналах скорость передачи всегда будет меньше С. Степень отличия R от С зависит от того, насколько рационально выбрана и эффективно используется та или иная система передачи информации. Наиболее общей оценкой эффективности системы передачи информации является коэффициент использования канала
Для дискретных систем передачи информации справедливо соотношение , где и - эффективность системы кодирования и эффективность системы модуляции соответственно.
Вводя избыточность сообщения и избыточность сигнала , можно показать, что
где - полная избыточность системы. Согласно этому соотношению, эффективность системы (коэффициент использования канала) полностью определяется величиной ее избыточности, т.е. задача повышения эффективности системы передачи информации сводится к задаче уменьшения избыточности сообщения и сигнала.
Избыточность сообщения обусловлена тем, что элементы сообщения не являются равновероятными и между ними имеется статистическая связь. При кодировании можно перераспределить вероятности исходного сообщения так, чтобы распределение вероятностей символов кода приближалось к оптимальному.
Избыточность сигнала зависит от способа модуляции и вида переносчика. Процесс модуляции обычно сопровождается расширением полосы частот сигнала по сравнению с полосой частот передаваемого сообщения. Это расширение полосы и является избыточным.
Говоря об эффективности системы передачи информации, нельзя забывать о ее помехоустойчивости. Устранение избыточности повышает эффективность передачи, но снижает при этом помехоустойчивость. При кодировании в ряде случаев избыточность вводится специально с целью повышения достоверности передачи. Пример такого кодирования являются корректирующие коды, которые мы рассмотрим позднее.
Таким образом, имеется два основных критерия оценки качества систем передачи информации и наиболее совершенной системой считается такая, которая обеспечивает наибольшую эффективность при заданной помехоустойчивости.
Тема. Основы экономного кодирования
Лекция 7. Системы сжатия данных для кодирования
источника информации
Сообщения, передаваемые с использованием систем передачи информации (речь, музыка, телевизионные изображения и т.д.) в большинстве своем предназначены для непосредственного восприятия органами чувств человека и плохо приспособлены для эффективной передачи по каналам связи. Поэтому в процессе передачи, они, как правило, подвергаются кодированию.
Под кодированием понимают преобразование алфавита сообщения A{λi }, ( i = 1,2…K ) в алфавит некоторых кодовых символов R{xj}, ( j = 1,2…N ). Обычно размер алфавита кодовых символов dim R{ xj } существенно меньше размера алфавита источника dimA{ λi }.
Кодирование сообщений может преследовать различные цели - например засекречивание передаваемой информации. При этом элементарным сообщениям i из алфавита A{ λi } ставятся в соответствие последовательности, к примеру, цифр или букв из специальных кодовых таблиц, известных лишь отправителю и получателю информации.
Другим примером кодирования может служить преобразование дискретных сообщений i из одних систем счисления в другие (из десятичной в двоичную, преобразование буквенного алфавита в цифровой и т. д.).
Кодирование в канале, или помехоустойчивое кодирование информации, используется для уменьшения количества ошибок, возникающих при передаче по каналу с помехами.
Наконец, кодирование сообщений может производиться с целью сокращения объема информации и повышения скорости ее передачи. Такое кодирование называют кодированием источника, экономным (эффективным) кодированием или сжатием данных. В этой теме мы рассмотрим именно такое кодирование. Процедуре кодирования обычно предшествуют дискретизация и квантование непрерывного сообщения λ(t), то есть его преобразование в последовательность элементарных дискретных сообщений { λiq }.
Поясним суть процедуры кодирования.
Любое дискретное сообщение i из алфавита источника A{ λi } объемом в K символов можно закодировать последовательностью соответствующим образом выбранных кодовых символов xj из алфавита R{ xj }.
Например, любое число (а i можно считать числом) можно записать в
заданной системе счисления следующим образом:
где - основание системы счисления; - коэффициенты при степенях ; .
Например, значение i = M = 59 в восьмеричной (m = 8) системе счисления запишется в виде
M = 59 = 7·81 + 3·80 =738 .
Если основание кода m = 2, то
M = 59 = 125 + 124 + 123 + 022 + 121 + 120 = 1110112 .
Таким образом, числа 73 и 111011 можно считать, соответственно, восьмеричным и двоичным кодами числа M = 59.
Наибольшее распространение получили двоичные коды, или коды с основанием 2, для которых размер алфавита кодовых символов R{ xj } равен двум, . Двоичные коды содержат только нули и единицы, они очень просто формируются и передаются по каналам связи и, главное, являются внутренним языком компьютеров и без всяких преобразований могут обрабатываться цифровыми средствами. В дальнейшем мы будем рассматривать только двоичные коды.
Самым простым способом задания кодов являются кодовые таблицы, ставящие в соответствие сообщениям i соответствующие им коды (табл. 1).
Таблица 1
|
Буква li |
Число li |
Код с основанием 10 |
Код с основанием 2 |
|
А |
0 |
0 |
000 |
|
Б |
1 |
1 |
001 |
|
В |
2 |
2 |
010 |
|
Г |
3 |
3 |
011 |
|
Д |
4 |
4 |
100 |
|
Е |
5 |
5 |
101 |
|
Ж |
6 |
6 |
110 |
|
З |
7 |
7 |
111 |
Другим наглядным способом описания кодов является их представление в виде кодового дерева (рис. 1).
Рис. 1
Для того, чтобы построить кодовое дерево для данного кода, начиная с некоторой точки - корня кодового дерева - проводятся ветви - 0 или 1. На вершинах кодового дерева находятся буквы алфавита источника, причем каждой букве соответствуют своя вершина и свой путь от корня к вершине. К примеру, букве А соответствует код 000, букве В – 010, букве Е – 101 и т.д.
Код, полученный с использованием кодового дерева, изображенного на рис. 1, является равномерным трехразрядным кодом.
Равномерные коды очень широко используются в силу своей простоты и удобства процедур кодирования-декодирования: каждой букве – одинаковое число бит; при получении заданного числа бит –в кодовой таблице ищется соответствующая буква.
Наряду с равномерными кодами могут применяться и неравномерные коды, когда каждая буква из алфавита источника кодируется различным числом символов, к примеру, А - 10, Б – 110, В – 1110 и т.д.
Кодовое дерево для неравномерного кодирования может выглядеть, например, так, как показано на рис. 2.
Рис. 2.
При использовании этого кода буква А будет кодироваться, как 1, Б - как 0, В – как 11 и т.д. Однако можно заметить, что, закодировав, к примеру, текст АББА = 1001 , его нельзя однозначно декодировать, поскольку такой же код дают фразы: ЖА = 1001, АЕА = 1001 и ГД = 1001. Такие коды, не обеспечивающие однозначного декодирования, называются приводимыми, или непрефиксными, кодами и не могут на практике применяться без специальных разделяющих символов. Примером непрефиксных кодов служит азбука Морзе, в которой кроме точек и тире есть специальные символы разделения букв.
Однако можно построить неравномерные неприводимые коды, допускающие однозначное декодирование. Для этого необходимо, чтобы всем буквам алфавита соответствовали лишь вершины кодового дерева (см. Рис. 3). Здесь ни одна кодовая комбинация не является началом другой, более длинной, поэтому неоднозначности декодирования не будет. Такие неравномерные коды называются префиксными.
Рис. 3
Прием и декодирование неравномерных кодов - процедура гораздо более сложная, чем для равномерных. Возникает вопрос, зачем же используются неравномерные коды?
Рассмотрим пример кодирования сообщений li из алфавита объемом K = 8 с помощью произвольного n-разрядного двоичного кода.
Пусть источник сообщения выдает некоторый текст с алфавитом от А до З и одинаковой вероятностью букв Р(li ) = 1/8.
Кодирующее устройство кодирует эти буквы равномерным трехразрядным кодом (см. табл. 1).
Определим основные информационные характеристики источника с таким алфавитом:
- энтропия источника , ;
- избыточность источника ;
- среднее число символов в коде ;
- избыточность кода .
Таким образом, при кодировании сообщений с равновероятными буквами избыточность выбранного (равномерного) кода оказалась равной нулю.
Пусть теперь вероятности появления в тексте различных букв будут разными (табл. 2).
Таблица 2
|
А |
Б |
В |
Г |
Д |
Е |
Ж |
З |
|
Ра=0.6 |
Рб=0.2 |
Рв=0.1 |
Рг=0.04 |
Рд=0.025 |
Ре=0.015 |
Рж=0.01 |
Рз=0.01 |
Энтропия источника в этом случае, естественно, будет меньшей и составит = 1.781.
Среднее число символов на одно сообщение при использовании того же равномерного трехразрядного кода
Избыточность кода в этом случае будет
,
или довольно значительной величиной (в среднем 4 символа из 10 не несут никакой информации).
В связи с тем, что при кодировании неравновероятных сообщений равномерные коды обладают большой избыточностью, было предложено использовать неравномерные коды, длительность кодовых комбинаций которых была бы согласована с вероятностью появления различных букв. Такое кодирование называется статистическим.
Неравномерный код при статистическом кодировании выбирают так, чтобы более вероятные буквы передавались с помощью более коротких комбинаций кода, менее вероятные - с помощью более длинных. В результате уменьшается средняя длина кодовой группы в сравнении со случаем равномерного кодирования.
Один способ такого кодирования предложен Хаффменом. Построение кодового дерева неравномерного кода Хаффмена для передачи одного из восьми сообщений li с различными вероятностями иллюстрируется табл. 3.
Таблица 3.
|
Буква |
Вероятность Рi |
Кодовое дерево |
Код |
ni |
ni × Pi |
|
А Б В Г Д Е Ж З |
0.6 0.2 0.1 0.04 0.025 0.015 0.01 0.01 |
1 01 001 0001 00001 000001 0000001 00000001 |
1 2 3 4 5 6 7 8 |
0.6 0.4 0.3 0.16 0.125 0.08 0.07 0.08 |
Среднее число символов для такого кода составит
а избыточность кода
т.е. на порядок меньше, чем при равномерном кодировании.
Другим простейшим способом статистического кодирования является кодирование по методу Шеннона-Фано. Кодирование здесь производится так:
Процедура кодирования по методу Шеннона-Фано иллюстрируется табл. 4.
Таблица 4
|
Буква |
Р(i ) |
I |
II |
III |
IV |
V |
Kод |
ni Pi |
|
А |
0.6 |
1 |
1 |
0.6 |
||||
|
Б |
0.2 |
0 |
1 |
1 |
011 |
0.6 |
||
|
В |
0.1 |
0 |
010 |
0.3 |
||||
|
Г |
0.04 |
0 |
1 |
001 |
0.12 |
|||
|
Д |
0.025 |
0 |
1 |
0001 |
0.1 |
|||
|
Е |
0.015 |
0 |
00001 |
0.075 |
||||
|
Ж |
0.01 |
1 |
000001 |
0.06 |
||||
|
З |
0.01 |
0 |
000000 |
0.06 |
Для полученного таким образом кода среднее число двоичных символов, приходящихся на одну букву, равно
,
а избыточность кода составит
то есть также существенно меньшую величину, чем для равномерного кода.
Можно видеть, что как для кода Хаффмена, так и для кода Шеннона-Фано среднее количество двоичных символов, приходящееся на символ источника, приближается к энтропии источника, но не равно ей. Данный результат представляет собой следствие теоремы кодирования без шума для источника (первой теоремы Шеннона), которая утверждает:
Любой источник можно закодировать двоичной последовательностью при среднем количестве двоичных символов на символ источника i, сколь угодно близком к энтропии, и невозможно добиться средней длины кода, меньшей, чем энтропия H(λ).
Эта теорема устанавливает те границы в компактности представления информации, которых можно достичь при правильном ее кодировании.
Цель сжатия данных и типы систем сжатия
Передача и хранение информации требуют больших затрат. Большая часть данных, которые нужно передавать и хранить, не имеет компактное представление. Как правило, эти данные хранятся в форме, обеспечивающей их наиболее простое использование, например: обычные книжные тексты, коды текстовых редакторов (ASCII), двоичные коды данных ЭВМ и т.д. Такое наиболее простое в использовании представление данных требует иногда в сотни раз больше места для хранения и очень широкие полосы частот для передачи. Поэтому сжатие данных – это одно из наиболее актуальных направлений развития современных систем передачи и хранения информации.
Цель сжатия данных - обеспечить компактное представление данных, вырабатываемых источником, для их более экономного сохранения и передачи по каналам связи.
Приведем условную структуру системы сжатия данных:
Данные источникаКодерСжатые данныеДекодерВосстановленные данные
Система сжатия данных состоит из кодера и декодера источника. Кодер преобразует данные источника в сжатые данные, а декодер предназначен для восстановления данных источника из сжатых данных. Восстановленные данные могут либо абсолютно точно совпадать с исходными данными источника, либо незначительно отличаться от них.
Соответственно cуществует два типа систем сжатия данных:
Сжатие без потерь информации
В системах сжатия без потерь декодер восстанавливает данные источника абсолютно точно, таким образом, структура системы сжатия выглядит следующим образом:
Вектор данных X Кодер B (X) Декодер X
Вектор данных источника X, подлежащих сжатию, представляет собой последовательность X = (x1, x2,… xn ) конечной длины. Отсчеты xi - составляющие вектора X - выбраны из конечного алфавита данных A. Таким образом, источник на своем выходе формирует в качестве данных X последовательность длиной n из алфавита A .
Выход кодера - сжатые данные, соответствующие входному вектору X, - можно представить в виде двоичной последовательности B(X) = ( b1,b2,…bk ), размер которой зависит от X. Назовем B(X) кодовым словом, в которое вектор X преобразован кодером. Поскольку система сжатия - неразрушающая, одинаковым векторам Xl = Xm должны соответствовать одинаковые кодовые слова B ( Xl ) = B ( Xm ).
При решении задачи сжатия возникает вопрос об эффективности той или иной системы сжатия. Для двоичного кодирования такой мерой может служить коэффициент сжатия r, определяемый как отношение
где dim A - размер алфавита данных A.
Таким образом, коэффициент сжатия r = 2 означает, что объем сжатых данных составляет половину от объема данных источника. Чем больше коэффициент сжатия r, тем лучше работает система сжатия данных.
Наряду с коэффициентом сжатия r эффективность системы сжатия может быть охарактеризована скоростью сжатия R, определяемой как отношение
R = k/n (2.3)
и измеряемой в "количестве кодовых бит, приходящихся на отсчет данных источника". Система, имеющая больший коэффициент сжатия, обеспечивает меньшую скорость сжатия.
Сжатие с потерей информации
В системе сжатия с потерями (или с разрушением) кодирование производится таким образом, что декодер не в состоянии восстановить данные источника в первоначальном виде. Структурная схема системы сжатия с разрушением выглядит следующим образом:
X Квантователь Xq Неразрушающий кодер B (Xq) Декодер X*
Как и ранее, X = ( x1, x2,… xn ) - вектор данных, подлежащих сжатию. Восстановленный вектор обозначим как X* = ( x1, x2,… xn ). В этой схеме сжатия имеется элемент, который отсутствовал при неразрушающем сжатии, - квантователь.
Квантователь формирует вектор Xq, достаточно близкий к X. Его работа основана на понижении размера алфавита (простейший квантователь производит округление данных до ближайшего целого числа).
Далее кодер подвергает неразрушающему сжатию вектор квантованных данных Xq таким образом, что обеспечивается однозначное соответствие между Xq и B(Xq) (для Xlq = Xm q выполняется условие B (Xlq) = B (Xmq)). Однако система в целом остается разрушающей, поскольку двум различным векторам X может соответствовать один и тот же вектор X*.
Разрушающий кодер характеризуется двумя параметрами - скоростью сжатия R и величиной искажений D, определяемой как
и параметр D является мерой среднеквадратического различия между X* и X.
К сожалению, построить систему разрушающего сжатия, обеспечивающую одновременно снижение скорости R и уменьшение искажений D невозможно. Поэтому целью оптимизации системы сжатия с потерями может быть либо минимизация скорости при заданной величине искажений, либо получение наименьших искажений при заданной скорости сжатия.
Выбор системы сжатия зависит от типа передаваемых данных. При сжатии текстовых данных, компьютерных программ, документов, чертежей и т.п. применяются неразрушающие методы, поскольку необходимо абсолютно точное восстановление исходной информации после ее сжатия. При сжатии речи, музыкальных произведений и изображений, наоборот, чаще используется разрушающее сжатие, поскольку при практически незаметных искажениях оно обеспечивает на порядок, а иногда и на два меньшую скорость R. Как правило разрушающее сжатие обеспечивает существенно более высокие коэффициенты сжатия, чем неразрушающее.
Пример. Пусть источник генерирует цифровое изображение (кадр) размером 512*512 элементов, содержащее 256 цветов. Каждый цвет представляет собой число из множества {0,1,2… 255}. Математически это изображение представляет собой матрицу 512х512, каждый элемент которой принадлежит множеству {0,1,2… 255}. Элементы изображения называют пикселами.
В свою очередь, каждый пиксел из множества {0,1,2… 255} может быть представлен в двоичной форме с использованием 8 бит. Таким образом, размер данных источника в битах составит 8х512х512= 221, или 2,1 Мегабита.
Объяснение. Любое число от 0 до 255 может быть представлено в двоичной системе как , где . Например, число
На жесткий диск объемом в 1 Гигабайт поместится примерно 5000 кадров изображения, если они не подвергаются сжатию (видеоролик длительностью примерно в пять минут). Если же это изображение подвергнуть сжатию с коэффициентом r = 10, то на этом же диске можно сохранить почти часовой видеофильм!
Если необходимо передать исходное изображение по телефонной линии, пропускная способность которой составляет 14000 бит/с. На это придется затратить 21000000 бит/14000 бит/с, или примерно 3 минуты. При сжатии же данных с коэффициентом r = 40 на это уйдет всего 5 секунд.
Лекция 8. Коды без памяти, коды с памятью и арифметическое кодирование
Коды без памяти и алгоритм Хаффмена
Простейшими кодами, на основе которых может выполняться сжатие данных, являются коды без памяти. В коде без памяти каждый символ в кодируемом векторе данных заменяется кодовым словом из префиксного множества двоичных последовательностей или слов.
Префиксным множеством двоичных последовательностей S называется конечное множество двоичных последовательностей, таких, что ни одна последовательность в этом множестве не является префиксом, или началом, никакой другой последовательности в S.
Например, множество двоичных слов S1 = {00, 01, 100, 110, 1010, 1011 } является префиксным множеством двоичных последовательностей, поскольку, если проверить любую из 30 возможных комбинаций (wi wj) из S1, то видно, что wi никогда не явится префиксом (или началом) wj. С другой стороны, множество S2 = { 00, 001, 1110 } не является префиксным множеством двоичных последовательностей, так как последовательность 00 является префиксом (началом) другой последовательности из этого множества - 001.
Таким образом, если необходимо закодировать некоторый вектор данных X = ( x1, x2,… xn ) с алфавитом данных A размера k, то кодирование кодом без памяти осуществляется следующим образом:
Если S = { w1, w2, ... , wk } - префиксное множество, то можно определить некоторый вектор v(S) = ( L1, L2, ... , Lk ), состоящий из чисел, являющихся длинами соответствующих префиксных последовательностей (Li - длина wi ).
Вектор (L1, L2, ... , Lk ), состоящий из неуменьшающихся положительных целых чисел, называется вектором Крафта. Для него справедливо неравенство
. (1)
(неравенство Крафта). Справедливо следующее утверждение: если S - какое-либо префиксное множество, то v(S) - вектор Крафта.
Иными словами, длины двоичных последовательностей в префиксном множестве удовлетворяют неравенству Крафта.
Примеры простейших префиксных множеств и соответствующие им векторы Крафта:
S1 = {0, 10, 11} и v(S1) = ( 1, 2, 2 );
S2 = {0, 10, 110, 111} и v(S2) = ( 1, 2, 3, 3 );
S3 = {0, 10, 110, 1110, 1111} и v(S3) = ( 1, 2, 3, 4, 4 );
S4 = {0, 10, 1100, 1101, 1110, 1111} и v(S4) = ( 1, 2, 4, 4, 4, 4 );
Допустим мы хотим разработать код без памяти для сжатия вектора данных X = ( x1, x2,… xn ) с алфавитом A размером в k символов. Введем в рассмотрение так называемый вектор частот F = ( F1, F2, ... , Fk ), где Fi - количество появлений i-го наиболее часто встречающегося символа из A в X. Закодируем X кодом без памяти, для которого вектор Крафта L = ( L1, L2, ... , Lk ).
Тогда длина двоичной кодовой последовательности B(X) на выходе кодера составит
L*F = L1*F1 + L2*F2 + ... + Lk*Fk . (2)
Лучшим кодом без памяти был бы код, для которого длина B(X) - минимальна. Для разработки такого кода нужно найти вектор Крафта L, для которого произведение L*F было бы минимально.
Эффективный способ поиска оптимального вектора Крафта L (т. е. такого L, для которого произведение L*F) минимально) дает алгоритм Хаффмена,. Код, полученный с использованием оптимального L для F, называют кодом Хаффмена.
Алгоритм Хаффмена реализует общую идею статистического кодирования с использованием префиксных множеств и работает следующим образом:
1. Выписываются в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте.
2. Последовательно объединяются два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагается равной сумме вероятностей составляющих его символов. Затем строится дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него.
3. Прослеживается путь к каждому листу дерева, с помечанием направления к каждому узлу (например, направо - 1, налево - 0) . Полученная последовательность дает кодовое слово, соответствующее каждому символу (рис. 1).
Построим, например, кодовое дерево для сообщения со следующим алфавитом:
A B C D E
10 5 8 13 10
B C A E D
5 8 10 10 13
A E BC D
10 10 13 13
BC D AE
13 13 20
AE BCD
20 26
AEBCD
46
Рис. 1
Таким образом получим таблицу для шифрования
|
A |
B |
C |
D |
E |
|
10 |
000 |
001 |
01 |
11 |
Большим недостатком кода Хаффмена является необходимость иметь таблицы вероятностей для каждого типа сжимаемых данных. Это не представляет проблемы, если известно, что сжимается английский или русский текст; при этом кодеру и декодеру просто предоставляется подходящее для английского или русского текста кодовое дерево. Но в случае, когда вероятность символов для входных данных неизвестна, статистические коды Хаффмена работают неэффективно.
Обычно рассматривают два типа кодов с памятью:
Блочный код делит вектор данных на блоки заданной длины и затем каждый блок заменяют кодовым словом из префиксного множества двоичных слов. Полученную последовательность кодовых слов объединяют в результирующую двоичную строку на выходе кодера. О блочном коде говорят, что он - блочный код k-го порядка, если все блоки имеют длину, равную k.
В качестве примера сожмем вектор данных X = ( 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1 ), используя блочный код второго порядка.
Сначала разобьем вектор X на блоки длины 2: 01, 10, 10, 01, 11, 10, 01, 01.
Будем рассматривать эти блоки как элементы нового “гипералфавита” { 01, 10, 11 }. Чтобы определить, какой код назначить каждому из символов этого нового алфавита, определим вектор частот появлений элементов дополнительного алфавита в последовательности блоков. Получим вектор частот ( 4, 3, 1 ), то есть наиболее часто встречающийся блок 01 появляется 4 раза, следующий по частоте встречаемости блок 10 - три раза и наименее часто встречающийся блок 11 - лишь один раз.
Оптимальный вектор Крафта для вектора частот ( 4, 3, 1 ) - это вектор ( 1, 2, 2 ). Таким образом, кодер для оптимального блочного кода второго порядка применительно к заданному вектору данных X определяется табл. 1.
Таблица 1
|
Таблица кодера |
|
|
Блок |
Кодовое слово |
|
01 |
0 |
|
10 |
10 |
|
11 |
11 |
Заменяя каждый блок присвоенным ему кодовым словом из таблицы кодера, получим последовательность кодовых слов:
0, 10, 10, 0, 11, 10, 0, 0.
Объединяя эти кодовые слова вместе, получим выходную последовательность кодера:
B(X) = ( 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0 ).
Код с конечной памятью при кодировании вектора данных ( X1, X2, ..., Xn ) использует кодовую книгу, состоящую из нескольких различных кодов без памяти. Каждая выборка данных кодируется кодом без памяти из кодовой книги, определяемым значением некоторого числа предыдущих выборок данных.
В качестве примера кодирования кодом с памятью рассмотрим классический пример X = ABRACADABRA. В этой последовательности совершенно очевидна сильная статистическая зависимость между ее очередными символами, которая должна обязательно учитываться при выборе метода кодирования.
Кодер с памятью при кодировании текущего символа учитывает значение предшествующего ему символа. Таким образом, кодовое слово для текущего символа A будет различным в сочетаниях RA, DA и CA (иными словами, код обладает памятью в один символ источника) (табл. 2).
Таблица 2.
|
Кодер |
|
|
Символ, предыдущий символ |
Кодовое слово |
|
(A,-) |
1 |
|
(B,A) |
0 |
|
(C,A) |
10 |
|
(D,A) |
11 |
|
(A,R) |
1 |
|
(R,B) |
1 |
|
(A,C) |
1 |
|
(A,B) |
1 |
Результат кодирования - вектор B(X) = (10111011111011) длиной в 11 бит и скоростью сжатия R = 13/11=1,18 бита на символ данных, тогда как при кодировании равномерным трехразрядным кодом с R = 3 понадобилось бы 33 бита.
Пpи аpифметическом кодиpовании, в отличие от рассмотренных нами методов, когда кодируемый символ (или группа символов) заменяется соответствующим им кодом, результат кодирования всего сообщения пpедставляется одним или парой вещественных чисел в интеpвале от 0 до 1. По меpе кодиpования исходного текста отобpажающий его интеpвал уменьшается, а количество десятичных (или двоичных) разрядов, служащих для его пpедставления, возpастает. Очеpедные символы входного текста сокpащают величину интеpвала исходя из значений их веpоятностей, определяемых моделью. Более веpоятные символы делают это в меньшей степени, чем менее веpоятные, и, следовательно, добавляют меньше разрядов к pезультату.
Поясним идею арифметического кодирования на примере. Пусть нужно закодировать текстовую строку: РАДИОВИЗИР.
Пеpед началом pаботы кодера соответствующий кодируемому тексту исходный интеpвал составляет [0; 1).
Алфавит кодируемого сообщения содержит следующие символы (буквы): { Р, А, Д, И, О, В, З }.
Определим количество (встречаемость, вероятность) каждого из символов алфавита в сообщении и назначим каждому из них интервал, пропорциональный его вероятности. С учетом того, что в кодируемом слове всего 10 букв, получим табл. 3.
Таблица 3.
|
Символ |
Веpоятность |
Интеpвал |
|
А |
0.1 |
0 – 0.1 |
|
Д |
0.1 |
0.1 – 0.2 |
|
В |
0.1 |
0.2 – 0.3 |
|
И |
0.3 |
0.3 – 0.6 |
|
З |
0.1 |
0.6 – 0.7 |
|
О |
0.1 |
0.7 – 0.8 |
|
Р |
0.2 |
0.8 – 1 |
Итак, перед началом кодирования исходный интервал составляет [0 – 1).
После пpосмотpа пеpвого символа сообщения Р кодер сужает исходный интеpвал до нового - [0.8; 1), котоpый модель выделяет этому символу. Таким образом, после кодирования первой буквы результат кодирования будет находиться в интервале чисел [ 0.8 - 1).
Следующим символом сообщения, поступающим в кодер, будет буква А. Если бы эта буква была первой в кодируемом сообщении, ей был бы отведен интервал [ 0 - 0.1 ), но она следует за Р и поэтому кодируется новым подынтервалом внутри уже выделенного для первой буквы, сужая его до величины [ 0.80 - 0.82 ). Другими словами, интервал [ 0 - 0.1 ), выделенный для буквы А, располагается теперь внутри интервала, занимаемого предыдущим символом (начало и конец нового интервала определяются путем прибавления к началу предыдущего интервала произведения ширины предыдущего интервала на значения интервала, отведенные текущему символу). В pезультате получим новый pабочий интеpвал [0.80 - 0.82), т.к. пpедыдущий интеpвал имел шиpину в 0.2 единицы и одна десятая от него есть 0.02.
Следующему символу Д соответствует выделенный интервал [0.1 - 0.2), что пpименительно к уже имеющемуся рабочему интервалу [0.80 - 0.82) сужает его до величины [0.802 - 0.804).
Следующим символом, поступающим на вход кодера, будет буква И с выделенным для нее фиксированным интервалом [ 0,3 – 0,6). Применительно к уже имеющемуся рабочему интервалу получим [ 0,8026 - 0,8032 ).
Пpодолжая в том же духе, имеем:
вначале [0.0 - 1.0 )
после пpосмотpа Р [0.8 - 1.0 )
А [0.80 - 0.82 )
Д [0.802 - 0.804 )
И [0.8026 - 0.8032 )
О [0.80302 - 0.80308 )
В [0.803032 - 0.803038 )
И [0.8030338 - 0.8030356 )
З [0.80303488 - 0.80303506 )
И [0.803034934 - 0.803034988 )
Р [0.8030349772 - 0.8030349880 )
Результат кодирования: интервал [0,8030349772 – 0,8030349880]. На самом деле любое число, заключенное внутри этого интервала, однозначно декодируется в исходное сообщение. К примеру, это можно проверить с числом 0,80303498, удовлетворяющим этим условиям.
Пpедположим, что все что декодер знает о тексте, – это конечный интеpвал [0,8030349772 - 0,8030349880]. Декодеру, как и кодеру, известна также таблица распределения выделенных алфавиту интервалов. Он сpазу же понимает, что пеpвый закодиpованный символ есть Р, так как результат кодирования целиком лежит в интеpвале [0.8 - 1), выделенном моделью символу Р согласно таблице .
Тепеpь повтоpим действия кодера:
вначале [0.0 - 1.0);
после пpосмотpа [0.8 - 1.0).
Исключим из результата кодирования влияние теперь уже известного первого символа Р, для этого вычтем из результата кодирования нижнюю границу диапазона, отведенного для Р, – 0,8030349772 – 0.8 = =0,0030349772 – и разделим полученный результат на ширину интервала, отведенного для Р, – 0.2. В результате получим 0,0030349772 / 0,2 = =0,015174886. Это число целиком вмещается в интервал, отведенный для буквы А, – [0 – 0,1) , следовательно, вторым символом декодированной последовательности будет А.
Поскольку теперь мы знаем уже две декодированные буквы - РА, исключим из итогового интервала влияние буквы А. Для этого вычтем из остатка 0,015174886 нижнюю границу для буквы А 0,015174886 – 0.0 = =0,015174886 и разделим результат на ширину интервала, отведенного для буквы А, то есть на 0,1. В результате получим 0,015174886/0,1=0,15174886. Результат лежит в диапазоне, отведенном для буквы Д, следовательно, очередная буква будет Д.
Исключим из результата кодирования влияние буквы Д. Получим (0,15174886 – 0,1)/0,1 = 0,5174886. Результат попадает в интервал, отведенный для буквы И, следовательно, очередной декодированный символ – И, и так далее, пока не декодируем все символы:
Декодируемое Символ Границы Ширина
число на выходе нижняя верхняя интервала
0,8030349772 Р 0.8 1.0 0.2
0,015174886 А 0.0 0.1 0.1
0,15174886 Д 0.1 0.2 0.1
0,5174886 И 0.3 0.6 0.3
0,724962 О 0,7 0,8 0,1
0,24962 В 0,2 0,2 0,1
0,4962 И 0,3 0,6 0,3
0,654 З 0,6 0,7 0,1
0,54 И 0,3 0,6 0,3
0,8 Р 0,6 0,8 0,2
0.0 Конец декодирования
Мы описали основную идею арифметического кодирования, что касается его практической реализации, то она несколько сложнее.
Отметим лишь одну из проблем. Она состоит в том, что декодеру нужно обязательно каким-либо образом дать знать об окончании процедуры декодирования. Решить эту проблему можно, например, путем в модель источника специального символа конца блока, например #, и прекращать декодирование, когда этот символ появится на выходе декодера.
Лекция 9. Словарные методы кодирования. Кодирование длин повторений и дифференциальное кодирование. Методы сжатия с потерей информации.
Словарные методы кодирования. Метод Лемпела-Зива
Методы Шеннона-Фэно, Хаффмена и арифметическое кодирование называются статистическими методами. Словарные алгоритмы, которые мы кратко рассмотрим, носят более практичный характер.
Практически все словарные методы кодирования пpинадлежат семье алгоритмов из работы Зива и Лемпела, опубликованной в 1977 году. Сущность их состоит в том, что фразы в сжимаемом тексте заменяются указателем на то место, где они в этом тексте уже pанее появлялись.
Это семейство алгоритмов (метод Зива-Лемпела) обозначается как LZ-сжатие. Этот метод быстpо приспосабливается к стpуктуpе текста и кодирует функциональные слова, так как они очень часто в нем появляются. Новые слова и фразы могут формируются из частей ранее встреченных слов.
Декодирование сжатого текста осуществляется напрямую - происходит простая замена указателя готовой фразой из словаря, на которую тот указывает. LZ-метод позволяет добиться хорошего сжатия и способствует очень быстрой работе декодера.
Словарь в неявном виде содержится в обрабатываемых данных, сохраняются лишь указатели на встречающиеся цепочки повторяющихся символов.
Мы рассмотрим лишь одну из наиболее удачных версий данного метода кодирования – алгоритм LZ78.
LZ78 хранит словарь из уже просмотренных фраз. При старте алгоритма этот словарь содержит только одну пустую строку (строку длины нуль). Алгоритм считывает символы сообщения до тех пор, пока накапливаемая подстрока входит целиком в одну из фраз словаря. Как только эта строка перестанет соответствовать хотя бы одной фразе словаря, алгоритм генерирует код, состоящий из индекса строки в словаре, которая до последнего введенного символа содержала входную строку, и символа, нарушившего совпадение. Затем в словарь добавляется введенная подстрока. Если словарь уже заполнен, то из него предварительно удаляют менее всех используемую в сравнениях фразу.
Ключевым для размера получаемых кодов является размер словаря во фразах, потому что каждый код при кодировании по методу LZ78 содержит номер фразы в словаре. Отсюда следует, что эти коды имеют постоянную длину, равную округленному в большую сторону двоичному логарифму размера словаря (это количество бит в байт-коде расширенного ASCII).
Пример. Закодировать по алгоритму LZ78 строку "КРАСНАЯ КРАСКА", используя словарь длиной 16 фраз.
Указатель на любую фразу такого словаря - это число от 0 до 15, для его кодирования достаточно четырех бит.
В последнем примере длина полученного кода равна битам.
В 1984 г. Уэлчем (Welch) путем модификации LZ78 был создан алгоритм LZW, наиболее совершенный из алгоритмов данного семейства.
Пусть длина словаря составляет 16 фраз. Коды сжатого сообщения -
Кодирование длин участков (или повторений) может быть достаточно эффективным при сжатии двоичных данных, например, черно-белых факсимильных изображений, черно-белых изображений, схем и т.п. Оно является одним из элементов известного алгоритма сжатия изображений JPEG.
Идея сжатия данных на основе кодирования длин повторений состоит в том, что вместо кодирования собственно данных подвергаются кодированию числа, соответствующие длинам участков, на которых данные сохраняют неизменное значение.
Предположим, что нужно закодировать двоичное (двухцветное) изображение размером 8 х 8 элементов, приведенное на рис. 1.
Рис. 1
Просканируем это изображение по строкам (двум цветам на изображении будут соответствовать 0 и 1), и получим двоичный вектор данных
X= (0111000011110000000100000001000000010000000111100011110111101111)
длиной 64 бита.
Выделим в векторе X участки, на которых данные сохраняют неизменное значение, и определим их длины. Результирующая последовательность длин участков - положительных целых чисел, соответствующих исходному вектору данных X, - будет иметь вид r = (1, 3, 4, 4, 7, 1, 7, 1, 7, 1, 7, 4, 3, 4, 1, 4, 1, 4).
Теперь эту последовательность, в которой заметна определенная повторяемость (единиц и четверок гораздо больше, чем других символов), можно закодировать каким-либо статистическим кодом, например, кодом Хаффмена без памяти, имеющим таблицу кодирования (табл. 1)
Таблица 1
|
Кодер |
|
|
Длина участка |
Кодовое слово |
|
4 |
0 |
|
1 |
10 |
|
7 |
110 |
|
3 |
111 |
Для того, чтобы указать, что кодируемая последовательность начинается с нуля, добавим в начале кодового слова префиксный символ 0. В результате получим кодовое слово
B (r) = (0101110011010110101101011001110100100)
длиной в 37 бит. При сжатии изображений большего размера и содержащих множество повторяющихся элементов эффективность сжатия является существенно более высокой.
Работа дифференциального кодера основана на том факте, что для многих типов данных разница между соседними отсчетами относительно невелика, даже если сами данные имеют большие значения. Например, нельзя ожидать большой разницы между соседними пикселами цифрового изображения.
Покажем, какое преимущество может дать дифференциальное кодирование (кодирование разности между соседними отсчетами) в сравнении с простым кодированием (кодированием отсчетов независимо друг от друга).
Просканируем 8-битовое (256-уровневое) цифровое изображение, при этом десять последовательных пикселов имеют уровни:
144, 147, 150, 146, 141, 142, 138, 143, 145, 142.
Если закодировать эти уровни пиксел за пикселом каким-либо кодом без памяти, использующим 8 бит на пиксел изображения, получим кодовое слово, содержащее 80 бит.
Предположим теперь, что прежде чем подвергать отсчеты изображения кодированию, мы вычислим разности между соседними пикселами. Эта процедура даст последовательность:
144, 147, 150, 146, 141, 142, 138, 143, 145, 142.
144, 3, 3, - 4, - 5, 1, - 4, 5, 2, -3.
Исходная последовательность может быть легко восстановлена из разностной простым суммированием:
144, 144+3, 147+3, 150–4, 146–5, 141+1, 142–4, 138+5, 143+2, 145-3
144, 147, 150, 146, 141, 142, 138, 143, 145, 142.
Для кодирования первого числа из полученной последовательности разностей отсчетов, как и ранее, понадобится 8 бит, все остальные числа можно закодировать 4-битовыми словами (один знаковый бит и 3 бита на кодирование модуля числа ).
Таким образом, в результате кодирования получим кодовое слово длиной 8 + 9*4 = 44 бита или почти вдвое более короткое, чем при индивидуальном кодировании отсчетов.
Метод дифференциального кодирования широко используется в тех случаях, когда природа данных такова, что их соседние значения незначительно отличаются друг от друга (сами значения могут быть сколь угодно большими).
Это относится к звуковым сигналам, особенно к речи, изображениям, соседние пикселы которых имеют практически одинаковые яркости и цвет и т.п. В то же время этот метод не подходит для кодирования текстов, чертежей или каких-либо цифровых данных с независимыми соседними значениями.
Как уже ранее отмечалось, существуют два типа систем сжатия данных:
При неразрушающем кодировании исходные данные могут быть восстановлены из сжатых в первоначальном виде, то есть абсолютно точно. Такое кодирование применяется для сжатия текстов, баз данных, компьютерных программ и данных и т.п. Все рассмотренные ранее методы кодирования относились именно к неразрушающим.
К сожалению, неразрушающее сжатие имеет невысокую эффективность – коэффициенты неразрушающего сжатия редко превышают 3…5.
Однако очень часто нет необходимости в абсолютной точности передачи исходных данных потребителю. Во-первых, сами источники данных обладают ограниченным динамическим диапазоном и вырабатывают исходные сообщения с определенным уровнем искажений и ошибок.
Во-вторых, передача данных по каналам связи и их хранение всегда производятся при наличии различного рода помех. Поэтому принятое (воспроизведенное) сообщение всегда в определенной степени отличается от переданного, то есть на практике невозможна абсолютно точная передача при наличии помех в канале связи (или в системе хранения).
Наконец, получатели информации - органы чувств человека, исполнительные механизмы и т.д. - также обладают конечной разрешающей способностью, то есть не замечают незначительной разницы между абсолютно точным и приближенным значениями воспроизводимого сообщения.
Кодирование с разрушением учитывает эти особенности и позволяет получить за счет некоторой контролируемой по величине ошибки коэффициенты сжатия, иногда в десятки раз превышающие степень сжатия для неразрушающих методов.
Большинство методов разрушающего сжатия основано на кодировании не самих данных, а некоторых линейных преобразований от них, например, коэффициентов дискретного преобразования Фурье (ДПФ), дискретного косинусного преобразования (ДКП) и т.д.
Рассмотрим в качестве примера популярный метод сжатия изображений JPEG ( “джипег”).
Основную идею кодирования изображений можно понять из следующих простых рассуждений. Рассмотрим некоторый цифровой сигнал (последовательностью отсчетов). Если отбросить в каждом из отсчетов половину двоичных разрядов (например, 4 разряда из восьми), то потеряется половина информации, содержащейся в сигнале.
Если же подвергнуть сигнал преобразованию Фурье, разделить его на две составляющие – НЧ и ВЧ и отбросить половину двоичных разрядов только в высокочастотной составляющей сигнала, то потеря информации составит всего 5%. Этот эффект объясняется тем, что низкочастотные составляющие большинства сигналов (крупные детали) обычно гораздо более интенсивны и несут гораздо больше информации, нежели высокочастотные составляющие (мелкие детали). Это в равной степени относится и к звуковым сигналам, и к изображениям.
Рассмотрим работу алгоритма сжатия JPEG при кодировании черно-белого изображения, представленного набором своих отсчетов (пикселов) с числом градаций яркости в 256 уровней (8 двоичных разрядов). Это самый распространенный способ хранения изображений - каждой точке на экране соответствует один байт (8 бит - 256 возможных значений), определяющий её яркость. 255 - яркость максимальная (белый цвет), 0 - минимальная (черный цвет). Промежуточные значения составляют всю остальную гамму серых цветов (рис. 2).
Рис. 2
Работа алгоритма сжатия JPEG начинается с разбиения изображения на квадратные блоки размером 8х8 = 64 пиксела. Выбор такого размера блока обусловлен тем, что при его малом размере эффект кодирования будет небольшим (при размере 1х1 – вообще отсутствует), а при большом - свойства изображения в пределах блока будут сильно изменяться и эффективность кодирования снова снизится.
На рис. 2 изображено несколько таких блоков (в виде матриц цифровых отсчетов), взятых из различных участков изображения. В дальнейшем эти блоки будут обрабатываться и кодироваться независимо друг от друга.
Второй этап сжатия – применение ко всем блокам дискретного косинусного преобразования – ДКП. Для сжатия данных пытались применить множество различных преобразований, но самым удобным оказалось именно ДКП. Оно позволяет перейти от пространственного представления изображения (набором отсчетов или пикселов) к спектральному представлению (набором частотных составляющих) и наоборот.
Дискретное косинусное преобразование от изображения IMG (x,y) может быть записано следующим образом:
где N = 8, 0 < i < 7 , 0 < j < 7,
или же, в матричной форме,
RES = DCT T*IMG * DCT , (2)
где DCT (ДКП) - матрица базисных (косинусных) коэффициентов для преобразования размером 8х8, имеющая вид:
.353553 .353553 .353553 .353553 .353553 .353553 .353553 .353553
.490393 .415818 .277992 .097887 -.097106 -.277329 -.415375 -.490246
.461978 .191618 -.190882 -.461673 -.462282 -.192353 .190145 .461366
DCT = .414818 -.097106 -.490246 -.278653 .276667 .490710 .099448 -.414486 (3)
.353694 -.353131 -.354256 .352567 .354819 -.352001 -.355378 .351435
.277992 -.490246 .096324 .416700 -.414486 -.100228 .491013 -.274673
.191618 -.462282 .461366 -.189409 -.193822 .463187 -.460440 .187195
.097887 -.278653 .416700 -.490862 .489771 -.413593 .274008 -.092414
Итак, в результате применения к блоку изображения размером 8х8 пикселов дискретного косинусного преобразования получим двумерный спектр, также имеющий размер 8х8 отсчетов. Иными словами, 64 числа, представляющие отсчеты изображения, превратятся в 64 числа, представляющие отсчеты его ДКП-спектра.
Напомним, что спектр сигнала – это величины коэффициентов, с которыми соответствующие спектральные составляющие входят в этот сигнал. Спектральные составляющие часто называют базисными функциями. Для 8х8 ДКП система базисных функций задается формулой
, (4)
а сами базисные функции выглядят подобно приведенным на рис. 3.
Рис. 3
Самая низкочастотная базисная функция, соответствующая индексам (0,0), изображена в левом верхнем углу рисунка, самая высокочастотная – в нижнем правом.
Дискретное косинусное преобразование вычисляется путем поэлементного перемножения и суммирования блоков изображения 8х8 пикселов с каждой из этих базисных функций. В результате, к примеру, компонента DCT-спектра с индексами (0,0) будет представлять собой просто сумму всех элементов блока изображения, то есть среднюю для блока яркость. Можно заметить, что чем ниже и правее в матрице DCT его компонента, тем более высокочастотным деталям изображения она соответствует.
Для того, чтобы получить исходное изображение по его DCT-спектру (выполнить обратное преобразование), нужно теперь базисную функцию с индексами (0,0) умножить на спектральную компоненту с координатами (0,0), прибавить к результату произведение базисной функции (1,0) на спектральную компоненту (1,0) и т.д.
В приведенной ниже табл. 3 видны числовые значения одного из блоков изображения и его ДКП-спектра:
Таблица 3
|
Исходные данные |
|||||||
|
139 |
144 |
149 |
153 |
155 |
155 |
155 |
155 |
|
144 |
151 |
153 |
156 |
159 |
156 |
156 |
156 |
|
150 |
155 |
160 |
163 |
158 |
156 |
156 |
156 |
|
159 |
161 |
161 |
160 |
160 |
159 |
159 |
159 |
|
159 |
160 |
161 |
162 |
162 |
155 |
155 |
155 |
|
161 |
161 |
161 |
161 |
160 |
157 |
157 |
157 |
|
161 |
162 |
161 |
163 |
162 |
157 |
157 |
157 |
|
162 |
162 |
161 |
161 |
163 |
158 |
158 |
15 |
|
Результат DCT |
|||||||
|
235,6 |
-1 |
-12,1 |
-5,2 |
2,1 |
-1,7 |
-2,7 |
1,3 |
|
-22,6 |
-17,5 |
-6,2 |
-3,2 |
-2,9 |
-0,1 |
0,4 |
-1,2 |
|
-10,9 |
-9,3 |
-1,6 |
1,5 |
0,2 |
-0,9 |
-0,6 |
-0,1 |
|
-7,1 |
-1,9 |
0,2 |
1,5 |
0,9 |
-0,1 |
0 |
0,3 |
|
-0,6 |
-0,8 |
1,5 |
1,6 |
-0,1 |
-0,7 |
0,6 |
1,3 |
|
1,8 |
-0,2 |
1,6 |
-0,3 |
-0,8 |
1,5 |
1 |
-1 |
|
-1,3 |
-0,4 |
-0,3 |
-1,5 |
-0,5 |
1,7 |
1,1 |
-0,8 |
|
-2,6 |
1,6 |
-3,8 |
-1,8 |
1,9 |
1,2 |
-0,6 |
-0,4 |
Отметим очень интересную особенность полученного DCT-спектра: наибольшие его значения сосредоточены в левом верхнем углу табл. 3 (низкочастотные составляющие), правая же нижняя его часть (высокочастотные составляющие) заполнена относительно небольшими числами. Чисел этих, правда, столько же, как и в блоке изображения: 8х8 = 64, то есть пока никакого сжатия не произошло, и, если выполнить обратное преобразование, получим тот же самый блок изображения.
Следующим этапом работы алгоритма JPEG является квантование (табл. 4).
Видно, что очень большая доля DCT коэффициентов,- нулевые или имеет очень небольшие значения (1 - 2). Это высокие частоты, которые (обычно) могут быть безболезненно отброшены или, по крайней мере, округлены до ближайшего целого значения.
Квантование заключается в делении каждого коэффициента DCT на некоторое число в соответствии с матрицей квантования. Эта матрица может быть фиксированной либо, для более качественного и эффективного сжатия, получена в результате анализа характера исходной картинки. Чем больше числа, на которые происходит деление, тем больше в результате деления будет нулевых значений, а значит, сильнее сжатие и заметнее потери.
Таблица 4
|
Ранее полученный результат DCT |
|||||||
|
235,6 |
-1 |
-12,1 |
-5,2 |
2,1 |
-1,7 |
-2,7 |
1,3 |
|
-22,6 |
-17,5 |
-6,2 |
-3,2 |
-2,9 |
-0,1 |
0,4 |
-1,2 |
|
-10,9 |
-9,3 |
-1,6 |
1,5 |
0,2 |
-0,9 |
-0,6 |
-0,1 |
|
-7,1 |
-1,9 |
0,2 |
1,5 |
0,9 |
-0,1 |
0 |
0,3 |
|
-0,6 |
-0,8 |
1,5 |
1,6 |
-0,1 |
-0,7 |
0,6 |
1,3 |
|
1,8 |
-0,2 |
1,6 |
-0,3 |
-0,8 |
1,5 |
1 |
-1 |
|
-1,3 |
-0,4 |
-0,3 |
-1,5 |
-0,5 |
1,7 |
1,1 |
-0,8 |
|
-2,6 |
1,6 |
-3,8 |
-1,8 |
1,9 |
1,2 |
-0,6 |
-0,4 |
|
Таблица квантования |
|||||||
|
16 |
11 |
10 |
16 |
24 |
40 |
51 |
61 |
|
12 |
12 |
14 |
19 |
26 |
58 |
60 |
55 |
|
14 |
13 |
16 |
24 |
40 |
57 |
69 |
56 |
|
14 |
17 |
22 |
29 |
51 |
87 |
80 |
62 |
|
18 |
22 |
37 |
56 |
68 |
109 |
103 |
77 |
|
24 |
35 |
55 |
64 |
81 |
104 |
113 |
92 |
|
49 |
64 |
78 |
87 |
103 |
121 |
120 |
101 |
|
72 |
92 |
95 |
98 |
112 |
100 |
103 |
99 |
|
Результат квантования |
|||||||
|
15 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
|
-2 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
-1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Очевидно, что от выбора таблицы квантования будет в значительной степени зависеть как эффективность сжатия – число нулей в квантованном (округленном) спектре ,– так и качество восстановленной картинки.
Таким образом, мы округлили результат DCT и получили в большей или меньшей степени искаженный поблочный спектр изображения.
Следующим этапом работы алгоритма JPEG является преобразование 8х8 матрицы DCT-спектра в линейную последовательность. Но делается это таким образом, чтобы сгруппировать по возможности вместе все большие значения и все нулевые значения спектра. Для этого нужно прочесть элементы матрицы коэффициентов DCT в порядке, изображенном на рис. 4, то есть зигзагообразно - из левого верхнего угла к правому нижнему. Эта процедура называется зигзаг-сканированием.
В результате такого преобразования квадратная матрица 8х8 квантованных коэффициентов DCT превратится в линейную последовательность из 64 чисел, большая часть из которых – это идущие подряд нули. Известно, что такие потоки можно очень эффективно сжимать путем кодирования длин повторений. Именно так это и делается.
На следующем, пятом этапе JPEG-кодирования получившиеся цепочки нулей подвергаются кодированию длин повторений.
И, наконец, последним этапом работы алгоритма JPEG является кодирование получившейся последовательности каким-либо статистическим алгоритмом. Обычно используется арифметическое кодирование или алгоритм Хаффмена. В результате получается новая последовательность, размер которой существенно меньше размера массива исходных данных.
Декодирование данных сжатых согласно алгоритму JPEG производится точно так же, как и кодирование, но все операции следуют в обратном порядке.
После неразрушающей распаковки методом Хаффмена (или LZ, или арифметического кодирования) и расстановки линейной последовательности в блоки размером 8х8 чисел спектральные компоненты деквантуются с помощью сохраненных при кодировании таблиц квантования. Для этого распакованные 64 значения DCT умножаются на соответствующие числа из таблицы. После этого каждый блок подвергается обратному косинусному преобразованию, процедура которого совпадает с прямым и различается только знаками в матрице преобразования. Последовательность действий при декодировании и полученный результат иллюстрируются приведенной ниже табл. 5.
Таблица 5
|
Квантованные данные |
|||||||
|
15 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
|
-2 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
-1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Деквантованные данные |
|||||||
|
240 |
0 |
-10 |
0 |
0 |
0 |
0 |
0 |
|
-24 |
-12 |
0 |
0 |
0 |
0 |
0 |
0 |
|
-14 |
-13 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Результат обратного DCT |
|||||||
|
144 |
146 |
149 |
152 |
154 |
156 |
156 |
156 |
|
148 |
150 |
152 |
154 |
156 |
156 |
156 |
156 |
|
155 |
156 |
157 |
158 |
158 |
157 |
156 |
155 |
|
160 |
161 |
161 |
162 |
161 |
159 |
157 |
155 |
|
163 |
163 |
164 |
163 |
162 |
160 |
158 |
156 |
|
163 |
164 |
164 |
164 |
162 |
160 |
158 |
157 |
|
160 |
161 |
162 |
162 |
162 |
161 |
159 |
158 |
|
158 |
159 |
161 |
161 |
162 |
161 |
159 |
158 |
|
Для сравнения - исходные данные |
|||||||
|
139 |
144 |
149 |
153 |
155 |
155 |
155 |
155 |
|
144 |
151 |
153 |
156 |
159 |
156 |
156 |
156 |
|
150 |
155 |
160 |
163 |
158 |
156 |
156 |
156 |
|
159 |
161 |
161 |
160 |
160 |
159 |
159 |
159 |
|
159 |
160 |
161 |
162 |
162 |
155 |
155 |
155 |
|
161 |
161 |
161 |
161 |
160 |
157 |
157 |
157 |
|
161 |
162 |
161 |
163 |
162 |
157 |
157 |
157 |
|
162 |
162 |
161 |
161 |
163 |
158 |
158 |
15 |
Видно, что восстановленные данные несколько отличаются от исходных. На рис. 5 приведено исходное изображение (слева), а также изображение, сжатое с использованием алгоритма JPEG в 10 раз (в центре) и в 45 раз (справа). Потеря качества в последнем случае вполне заметна, но и выигрыш по объему тоже очевиден.
Рис. 5
Итак, JPEG-сжатие состоит из следующих этапов:
Декодирование производится точно так же, но в обратном порядке.
Лекция 10. Рекурсивный алгоритм сжатия информации, понятие о методах кодирования подвижных изображений и речевых сигналов
Английское название рекурсивного сжатия — wavelet. На русский язык оно переводится как волновое сжатие и как сжатие с использованием всплесков. Ориентирован алгоритм на цветные и черно-белые изображения с плавными переходами. Коэффициент сжатия варьируется в пределах 5 - 100.
Идея алгоритма заключается в том, что вместо кодирования собственно изображений сохраняется разница между средними значениями соседних блоков в изображении, которая обычно принимает значения, близкие к 0.
Так, два числа a2i и a2i+1 всегда можно представить в виде b1i= =(a2i+a2i+1)/2 и b2i=(a2i-a2i+1)/2. Аналогично последовательность ai может быть попарно переведена в последовательность b1,2i.
Рассмотрим пример. Пусть мы сжимаем строку из восьми значений яркости пикселов (ai): (220, 211, 212, 218, 217, 214, 210, 202). Получим следующие последовательности b1i, и b2i: (215.5, 215, 215.5, 206) и (4.5, -3, 1.5, 4). Заметим, что значения b2i достаточно близки к 0. Повторим операцию, рассматривая b1i как a i. Данное действие выполняется как бы рекурсивно, откуда и название алгоритма. Из (215.5, 215, 215.5, 206) получим (215.25, 210.75) (0.25, 4.75). Полученные коэффициенты, округлив до целых и сжав, например, с помощью алгоритма Хаффмана, можно считать результатом кодирования. Заметим, что мы применяли наше преобразование к цепочке только два раза. Реально можно позволить себе применение wavelet-преобразования 4-6 раз, что позволит достичь заметных коэффициентов сжатия.
Алгоритм для двумерных данных реализуется аналогично.
Если у нас есть квадрат из четырех точек с яркостями a2i ,2j , a2i+1 , 2j, a2i , 2j+1 , и a2i+1 , a 2j+1 , то
(1)
Используя эти формулы, для изображения 512х512 пикселов получим после первого преобразования уже 4 матрицы размером 256х256 элементов (рис. 1, 2)
|
Исходное изображение |
B1 |
B2 |
|
B3 |
B4 |
Рис. 1. Рис. 2.
В первой хранится уменьшенная копия изображения, во второй - усредненные разности пар значений пикселов по горизонтали, в третьей - усредненные разности пар значений пикселов по вертикали, в четвертой - усредненные разности значений пикселов по диагонали.
Можно повторить преобразование и получить вместо первой матрицы 4 матрицы размером 128х128.
Повторив преобразование в третий раз, получим в итоге 4 матрицы 64х64, 3 матрицы 128х128 и 3 матрицы 256х256. Дальнейшее сжатие происходит за счет того, что в разностных матрицах имеется большое число нулевых или близких к нулю значений, которые после квантования эффективно сжимаются.
Основной проблемой в работе с подвижными изображениями являются большие объемы данных, с которыми приходится иметь дело. Например, при записи на компакт-диск в среднем качестве на него можно поместить несколько тысяч фотографий, более 10 часов музыки и всего полчаса видео. Видео телевизионного формата требует потока данных примерно 240 Мбит/с (1,8 Гбит/мин). При этом обычные методы сжатия, ориентированные на кодирование отдельных кадров (в том числе и JPEG), не спасают положения, поскольку даже при уменьшении битового потока в 10 - 20 раз он остается чересчур большим для практического использования.
При сжатии подвижных изображений учитывается наличие в них нескольких типов избыточности, в частности:
С середины 80-х гг. многие западные университеты и лаборатории фирм работали над созданием алгоритма компрессии цифрового видеосигнала. Появилось достаточно большое число внутрифирменных стандартов.
В 1992 году был представлен стандарт кодирования MPEG-I. Сейчас используется стандарт MPEG-2.
Технология сжатия видео в MPEG распадается на две части: уменьшение избыточности видеоинформации во временном измерении, основанное на том, что соседние кадры, как правило, отличаются не сильно, и сжатие отдельных изображений.
MPEG сжимает последовательность движущихся образов, используя корреляцию между последовательными движущимися изображениями. Создается три типа изображений: интра-изображения (I – изображения), предсказанные (P-изображения) и изображения двунаправленного предсказания (B- изображения). В MPEG каждое изображение в последовательности может быть полностью сжато с использованием алгоритма JPEG – это I- изображения. Затем процесс сравнивает последовательные I- изображения и идентифицирует часть образа, которая была перемещена. Части образа, которые не были перемещены, переносятся в промежуточное изображение с помощью памяти декодера. После этого процесс отбирает подмножество промежуточных изображений, а затем предсказывает (посредством линейной интерполяции между I-изображениями) и корректирует расположение частей образа, которые были перемещены. Эти предсказанные и скорректированные образы являются P-изображениями. Между I и P изображениями находятся B-изображения, которые включают стационарные части образа, не охваченные движущимися частями (рис. 3)
Рис. 3. Последовательность изображений при сжатии MPEG
Одним из основных понятий при сжатии нескольких изображений является макроблок - матрица пикселов 16х16 элементов (размер изображения должен быть кратен 16). Отдельные макроблоки сжимаются независимо.
Существует достаточно много алгоритмов, сжимающих статические изображения. Из них чаще всего используются алгоритмы на базе дискретного косинусного преобразования. Алгоритм сжатия отдельных кадров в MPEG похож на соответствующий алгоритм для статических изображений - JPEG. При этом к макроблокам применяется ДКП.
Использование векторов смещений блоков. Алгоритм состоит в том, что для каждого блока изображения находят блок, близкий к нему в некоторой метрике (например, по минимуму суммы квадратов разностей пикселов), в предыдущем кадре в некоторой окрестности текущего положения блока. Если минимальное расстояние между блоками в этой метрике меньше некоторого порога, то вместе с каждым блоком в выходном потоке сохраняется вектор смещения - координаты смещения максимально похожего блока в предыдущем I или P- кадре. Если различия больше этого порога, блок сжимается независимо.
Основные объемы передаваемой в системах связи информации приходится на речь – это и проводная телефония, и системы сотовой и спутниковой связи, и т.д. Поэтому эффективному кодированию, или сжатию речи, в системах связи уделяется исключительное внимание.
Рассмотрим основные свойства речевого сигнала как объекта экономного кодирования и передачи по каналам связи и попытаемся пояснить, на каких свойствах сигнала основывается возможность его сжатия.
Речь представляет собой колебания сложной формы, зависящей от произносимых слов, тембра голоса, интонации, пола и возраста говорящего. Спектр речи весьма широк (примерно от 50 до 10000 Гц), но для передачи речи в аналоговой телефонии отказались от составляющих, лежащих за пределами полосы 0,3 - 3,4 кГц, что несколько ухудшило восприятие ряда звуков (например шипящих, существенная часть энергии которых сосредоточена в верхней части речевого спектра), но мало затронуло разборчивость. Ограничение частоты снизу (до 300 Гц) также немного ухудшает восприятие из-за потерь низкочастотных гармоник основного тона.
Следует отметить, что уровень низкочастотных (то есть медленных по времени) составляющих в спектре речевого сигнала значительно выше уровня высокочастотных (быстрых) составляющих. Эта существенная неравномерность спектра является одним из факторов сжимаемости таких сигналов.
Второй особенностью речевых сигналов является неравномерность распределения вероятностей (плотности вероятности) мгновенных значений сигнала. Малые уровни сигнала значительно более вероятны, чем большие. Особенно это заметно на фрагментах большой длительности с невысокой активностью речи. Этот фактор также обеспечивает возможность экономного кодирования – более вероятные значения могут кодироваться короткими кодами, менее вероятные – длинными.
Еще одна особенность речевых сигналов – их существенная нестационарность во времени: свойства и параметры сигнала на различных участках значительно различаются. При этом размер интервала стационарности составляет порядка нескольких десятков миллисекунд. Это свойство сигнала значительно затрудняет его экономное кодирование и заставляет делать системы сжатия адаптивными, то есть подстраивающимися под значения параметров сигнала на каждом из участков.
Простейшими кодерами/декодерами речи являются кодеры/декодеры формы сигнала. Они могут использоваться для кодирования любых, в том числе и неречевых, сигналов.
Простейшим способом кодирования формы сигнала является импульсно-кодовая модуляция – ИКМ, при использовании которой производятся просто дискретизация и равномерное квантование входного сигнала, а также преобразование полученного результата в равномерный двоичный код.
Для речевых сигналов со стандартной для передачи речи полосой 0,3 – 3,5 кГц обычно используют частоту дискретизации Fдискр2Fmax= 8 кГц. Экспериментально показано, что при равномерном квантовании для получения практически идеального качества речи нужно квантовать сигнал не менее чем на 2000 уровней
Используя неравномерное квантование (более точное для малых уровней сигнала и более грубое для больших его уровней), можно достичь того же качества восстановления речевого сигнала, но при гораздо меньшем числе уровней квантования – порядка 128.
С учетом статистических свойств речевого сигнала, а также нелинейных свойств слуха, гораздо лучше различающего слабые звуки, оптимальной является логарифмическая шкала квантования, которая и была принята в качестве стандарта в середине 60-х годов и сегодня повсеместно используется.
Следующим приемом, позволяющим эффективность кодирования, может быть попытка предсказать значение текущего отсчета сигнала по нескольким предыдущим его значениям, и далее, кодирование уже не самого отсчета, а ошибки его предсказания – разницы между истинным значением текущего отсчета и его предсказанным значением. Если точность предсказания достаточно высока, то ошибка предсказания очередного отсчета будет значительно меньше величины самого отсчета и для ее кодирования понадобится гораздо меньшее число бит. Таким образом, чем более предсказуемым будет поведение кодируемого сигнала, тем более эффективным будет его сжатие.
Описанная идея лежит в основе так называемой дифференциальной импульсно-кодовой модуляции - ДИКМ (DPCM) – способа кодирования, при котором кодируются не сами значения сигнала, а их отличия от некоторым образом предсказанных значений, например предсказание текущего отсчета на основе линейной комбинации двух предшествующих и т.д.:
x*i = a k xi – k ,
Эффективность ДИКМ может быть повышена, если предсказание и квантование сигнала будет выполняться не на основе некоторых усредненных его характеристик, а с учетом их текущего значения и изменения во времени, то есть адаптивно. Так, если скорость изменения сигнала стала большей, можно увеличить шаг квантования, и, наоборот, если сигнал стал изменяться медленнее, величину шага квантования можно уменьшить. При этом ошибка предсказания уменьшится и, следовательно, будет кодироваться меньшим числом бит на отсчет. Такой способ кодирования называется адаптивной ДИКМ, или АДИКМ (ADPCM). Сегодня он стандартизован и широко используется при сжатии речи в междугородных цифровых системах связи, в системе микросотовой связи DECT, в цифровых переносных телефонах и т.д.
Лекция 11. Понятие о корректирующих кодах
Классификация корректирующих кодов
Эффективным средством повышения достоверности передачи сообщений в реальных каналах является помехоустойчивое кодирование. Оно основано на применении специальных кодов, которые корректируют ошибки, вызванные действием помех.
Код называется корректирующим, если он позволяет обнаруживать и исправлять ошибки при приеме сообщений.
Код, с помощью которого можно лишь обнаруживать ошибки, называется обнаруживающим. Исправление ошибки при таком кодировании производится путем повторения искаженных сообщений, при этом запрос о повторении передается по каналу обратной связи.
Для того чтобы код обладал корректирующими способностями, в кодовой последовательности должны содержаться дополнительные (избыточные) символы, предназначенные для корректирования ошибок. При этом, чем больше избыточность кода, тем выше его корректирующая способность.
Известно большое количество корректирующих кодов, отличающихся как принципами построения, так и основными характеристиками. Рассмотрим их простейшую классификацию.
Все известные коды делятся на две большие группы: блочные и сверточные (непрерывные). Блочные коды характеризуются тем, что последовательность передаваемых символов разделена на блоки. Операции кодирования и декодирования в каждом блоке производятся отдельно.
Отличительной особенностью непрерывных кодов является то, что первичная последовательность символов, несущих информацию, непрерывно преобразуется по определенному закону в другую последовательность, содержащую избыточное число символов. Здесь процессы кодирования и декодирования не требуют деления групп символов на блоки.
С технической точки зрения главное различие между блочными и сверточными кодами состоит в отсутствии или наличии памяти кодера.
Кодер для блочных кодов делит непрерывную информационную последовательность X на блоки-сообщения длиной k символов.
Кодер канала преобразует блоки-сообщения X в более длинные двоичные последовательности Y, состоящие из n символов и называемые кодовыми словами. Кодер добавляет к каждому блоку-сообщению (n-k) избыточных символов, функция которых состоит в обнаружении (или исправлении) ошибок, возникающих в процессе передачи.
Термин "отсутствие памяти кодера" означает, что каждый блок из n символов зависит только от соответствующего информационного блока из k символов и не зависит от других блоков.
Кодер для свёрточных кодов в каждый момент времени из небольшого текущего блока информационных символов размером в b символов (блока-сообщения) образует блок, состоящий из v кодовых символов (кодовый блок), причем v > b. При этом кодовый блок зависит не только от символьного блока- сообщения, имеющегося на входе кодера в настоящий момент, но и от предшествующих m блоков-сообщений. В этом и состоит наличие памяти в кодере.
Блочное кодирование удобно использовать в тех случаях, когда исходные данные по своей природе уже сгруппированы в какие-либо блоки или массивы.
При передаче по радиоканалам чаще используется сверточное кодирование, которое лучше приспособлено к побитовой передаче данных. Кроме этого, при одинаковой избыточности сверточные коды, как правило, обладают лучшей исправляющей способностью.
Разновидностями как блочных, так и непрерывных кодов являются разделимые и неразделимые коды. В разделимых кодах всегда можно выделить информационные символы, содержащие передаваемую информацию, и контрольные (проверочные) символы, которые являются избыточными и служат исключительно для коррекции ошибок. В неразделимых кодах такое разделение не производится.
Наиболее многочисленный класс разделимых кодов составляют линейные коды, в которых контрольные символы образуются как линейные комбинации информационных символов.
Двоичный код является линейным, если сумма по модулю 2 ( mod2 ) двух кодовых слов также является кодовым словом этого кода.
Принципы помехоустойчивого кодирования
В теории помехоустойчивого кодирования принципиально использование избыточности для корректирования возникающих ошибок.
Рассмотрим вначале блочные коды, причем ограничимся равномерными кодами, в которых число возможных комбинаций равно , где n – значность кода.
В обычном некорректирующем коде без избыточности число комбинаций M выбирается равным числу сообщений алфавита источника и все комбинации используются для передачи информации.
Корректирующие коды строятся так, чтобы число комбинаций M превышало число комбинаций источника . При этом лишь комбинаций из общего числа используются для передачи информации. Эти комбинации называются разрешенными, а остальные - запрещенными. На приемном конце в декодирующем устройстве известно, какие комбинации являются разрешенными, и какие – запрещенными. Поэтому если передаваемая разрешенная комбинация в результате ошибки преобразуется в запрещенную, то такая ошибка будет обнаружена, а при определенных условиях – исправлена. Естественно, что ошибки, приводящие к образованию другой разрешенной комбинации, не обнаруживаются.
Различие между комбинациями равномерного кода принято характеризовать расстоянием, равным числу символов, которыми отличаются комбинации друг от друга. Расстояние между комбинациями и определяется количеством единиц в сумме этих комбинаций по модулю два.
Например:
110011 Ai
010110 Aj
__________________
100101
Для любого кода, естественно, . Минимальное различие между разрешенными комбинациями в данном коде называется кодовым расстоянием .
Расстояние между комбинациями и условно изображено на рисунке ниже, где показаны промежуточные комбинации; каждая из последующих отличается от предыдущей одним символом.
Для того чтобы в результате ошибки комбинация (где “р” означает “разрешенная”) преобразовалась в другую разрешенную комбинацию , должно исказиться d символов. При искажении меньшего числа символов комбинация перейдет в запрещенную комбинацию и ошибка будет обнаружена. Отсюда следует, что ошибка всегда обнаруживается, если ее кратность, т.е. число искаженных символов в комбинации
Минимальное кодовое расстояние, при котором обнаруживаются любые одиночные ошибки, (см. (1)).
Процедура исправления ошибок в процессе декодирования сводится к определению переданной комбинации по известной принятой. Расстояние между переданной разрешенной комбинацией и принятой запрещенной комбинацией равно кратности ошибок g. Если ошибки в символах комбинации происходят независимо друг от друга, то вероятность искажения некоторых конкретных g символов в n-значной комбинации равна
где - вероятность искажения одного символа. Так как обычно , то вероятность многократных ошибок уменьшается с увеличением их кратности, при этом более вероятны меньшие расстояния . В этих условиях исправление ошибок может производиться по следующему правилу. Если принята запрещенная комбинация, то считается переданной ближайшая разрешенная комбинация. Это правило декодирования является оптимальным, так как оно обеспечивает исправление максимального числа ошибок.
Корректирующая способность кода возрастает с увеличением d. При фиксированном числе разрешенных комбинаций увеличение d возможно лишь за счет роста запрещенных комбинаций:
что, в свою очередь, требует избыточного числа символов , где k - количество символов в комбинации кода без избыточности. Количественно избыточность кода определяется как
При независимых ошибках вероятность определенного (конкретного) сочетания g ошибочных символов выражается соотношением (2). Очевидно, полная вероятность ошибки кратности g, учитывающая все сочетания ошибочных символов, равна
Вероятность отсутствия ошибок в кодовой комбинации, т.е. вероятность правильного приема, равна:
а вероятность правильного корректирования ошибок:
где суммирование производится по всем значениям кратности ошибок g, которые обнаруживаются и исправляются при применении рассматриваемого кода.
Таким образом, вероятность некорректируемых ошибок равна:
Анализ этой формулы показывает, что при малой величине и сравнительно небольших значениях n наиболее вероятны ошибки малой кратности, которые и необходимо корректировать в первую очередь.
Вероятность ошибки , избыточность и число символов n являются основными характеристиками корректирующего кода, определяющими, насколько удается повысить помехоустойчивость передачи дискретной информации и какой ценой это достигается.
Общая задача, которая ставится при создании кода, заключается в достижении наименьших значений вероятности ошибок и избыточности. Целесообразность применения того или иного кода зависит также от сложности кодирующих и декодирующих устройств.
Итак, для корректирования ошибок необходимо сравнивать принятую комбинацию со всеми комбинациями данного кода. В результате M сопоставлений делается вывод о переданной комбинации. Такой способ декодирования логически является наиболее простым, однако он требует сложных устройств, в которых должны запоминаться все M комбинаций кода. Поэтому на практике чаще всего используются коды, которые позволяют с помощью ограниченного числа преобразований принятых кодовых символов извлечь из них всю информацию о корректируемых ошибках.
Систематические коды
Систематические коды относятся к блочным разделимым кодам, т.е. к кодам, где операция кодирования осуществляется независимо в пределах каждого блока информационных и контрольных символов.
Систематический код имеет следующий формат
то есть содержит неизменную информационную часть длиной k символов и избыточную (проверочную) длиной n – k символов.
Если обозначить информационные символы буквами , а контрольные – буквами , то любую кодовую комбинацию, содержащую k информационных и r контрольных символов, можно представить последовательностью:
где с и e в двоичном коде принимают значения 0 или 1.
Процесс кодирования на передающем конце сводится к образованию контрольных символов, которые выражаются в виде линейной функции информационных символов. Символы представляют собой суммы по модулю два информационных символов в различных сочетаниях.
Пример. Запишем кодовое слово (4,3)-кода в виде вектора-столбца:
= ( m0, m1, m2, m0+m1+m2 ), (9)
где mi - символы информационной последовательности, принимающие значения 0 и 1, а суммирование производится по модулю 2 ( mod2 ).
Если информационная последовательность источника имеет вид
m = ( 1 0 1 ), (10)
то соответствующая ей кодовая последовательность
U = ( U0, U1, U2, U3 ) = ( 1 0 1 0 ), (11)
где проверочный символ U3 формируется путем суммирования по mod2 символов информационной последовательности m :
U3 = m0 + m1 + m2 . (12)
Нетрудно заметить, что если число единиц в последовательности m четно, то результатом суммирования будет 0, если нечетно - 1, то есть проверочный символ дополняет кодовую последовательность таким образом, чтобы количество единиц в ней было четным.
Если при передаче рассматриваемого (4,3)-кода произошла одна ошибка, то общее число единиц в принятой последовательности r будет нечетным.
Таким образом, признаком отсутствия ошибки в принятой последовательности может служить четность числа единиц. Поэтому такие коды и называются кодами с проверкой на четность.
Если в принятой последовательности r произошло две ошибки, то общее число единиц в ней снова станет четным и ошибка обнаружена не будет. Однако вероятность двойной ошибки значительно меньше вероятности одиночной, поэтому наиболее вероятные одиночные ошибки таким кодом обнаруживаться все же будут.
Несмотря на свою не очень высокую эффективность, коды с проверкой на четность широко используются в системах передачи и хранения информации. Они ценятся за невысокую избыточность: достаточно добавить к передаваемой последовательности всего один избыточный символ − и можно узнать, есть ли в принятой последовательности ошибка. Правда, определить место этой ошибки и, следовательно, исправить ее, нельзя. Можно лишь повторить передачу слова, в котором была допущена ошибка, и тем самым ее исправить.
Инверсный код
Инверсный код обладает значительно лучшими корректирующими способностями по сравнению с кодом с проверкой на четность.
С принципом функционирования данного кода удобно ознакомиться на примере двух комбинаций
11000,11000 и 01101,10010.
В каждой комбинации символы до запятой являются информационными, а последующие – контрольными. Если количество единиц в информационных символах четное, т.е. сумма этих символов по модулю два равна нулю, то контрольные символы представляют собой простое повторение информационных. В противном случае, когда число единиц нечетное и сумма символов равна 1, контрольные символы получаются из информационных путем инвертирования, т.е. путем замены всех 0 на 1 и наоборот.
При декодировании происходит сравнение принятых информационных и контрольных символов. Если сумма единиц в принятых информационных символах четная, то соответствующие друг другу информационные и контрольные символы суммируются по модулю два. В противном случае производится такое же суммирование, но с инвертированными контрольными символами. Другими словами, производится r проверок на четность. Ошибка обнаруживается, если хотя бы одна проверка на четность дает 1.
Анализ показывает, что при наименьшая кратность необнаруживаемой ошибки . Причем не обнаруживаются только те ошибки четвертой кратности, которые искажают одинаковые номера информационных и контрольных символов. Например, если передана комбинация
10100, 10100
а принята
10111,10111,
то такая четырехкратная ошибка обнаружена не будет.
Инверсный код обладает высокой обнаруживающей способностью, однако она достигается ценой сравнительно большой избыточности, которая составляет 0,5.
Еще одна простая и часто используемая схема кодирования может быть построена следующим образом.
Предположим, что нужно передать девять информационных символов m = ( m0 , m1 , ..., m8 ). Эти символы можно расположить в виде квадратной матрицы ( табл. 1), и добавить к каждой строке и каждому столбцу этой таблицы по проверочному символу (проверка на четность).
Таблица 1
|
m0 |
m1 |
m2 |
P1 = m0 +m1 +m2 |
|
m3 |
m4 |
m5 |
P2 = m3 +m4 +m5 |
|
m6 |
m7 |
m8 |
P3 = m6 + m7 + m8 |
|
m0 +m3 +m6 |
m1+ m4 +m7 |
m2 +m5 +m8 |
m0 + m0 + m1 + m1 +…. + m8 + m8 |
Таким образом, по строкам и по столбцам этой таблицы будет выполняться правило четности единиц.
Если в процессе передачи по каналу с помехами в этой таблице произойдет одна ошибка (например в символе m4), то проверка на четность в соответствующей строке и столбце (в нашем примере - P2 и P5) не будет выполняться.
Иными словами, координаты ошибки однозначно определяются номерами столбца и строки, в которых не выполняются проверки на четность. Этот код способен не только обнаруживать, но и исправлять ошибки (если известны координаты ошибки, то ее исправление состоит просто в замене символа на противоположный: 0 на 1, или 1 на 0 ).
Описанный метод кодирования, называемый итеративным, оказывается полезным в случае, когда данные естественным образом формируются в виде массивов, например, на шинах ЭВМ, в памяти, имеющей табличную структуру, и т.д. При этом размер таблицы не имеет значения (3х3 или 20х20.
Недостатком итеративного кода является большая избыточность. Если в простом коде с проверкой на четность для обнаружения ошибки приходится добавлять к информационной последовательности всего один символ, то для того, чтобы код стал исправлять однократную ошибку, в нашем примере понадобилось к девяти информационным символам добавить еще семь проверочных .
Напомним основные понятия двоичной арифметики.
Полем называется множество математических объектов, которые можно складывать, вычитать, умножать и делить.
Для простейшего поля, состоящего из двух элементов − нуля - 0 и единицы - 1 операции сложения и умножения определяются следующим образом:
0+0=0, 0× 0=0;
0+1=1, 0× 1=0;
1+0=1, 1× 0=0;
1+1=0, 1× 1=1.
Определенные таким образом операции сложения и умножения называются сложением и умножением по модулю 2 ( mod2 ) (обратите внимание, что из равенства 1+1 = 0 следует, что -1 = 1 и, соответственно, 1+1=1-1, а из равенства 1×1=1 − что 1:1=1).
Мы рассмотрели несколько простейших корректирующих кодов, а сейчас опишем формальное правило, по которому осуществляется кодирование, то есть преобразование информационной последовательности в кодовое слово.
Простейшим способом задания корректирующих кодов является табличный, при котором каждой информационной последовательности просто назначается кодовое слово из таблицы кода (табл. 1)
Таблица 1
|
m |
U |
|
000 |
0000 |
|
001 |
0011 |
|
010 |
0101 |
|
011 |
0110 |
|
100 |
1001 |
|
101 |
1010 |
|
110 |
1100 |
|
111 |
1111 |
(В этом примере - Последний символ в U – сумма предыдущих трех)
Такой способ описания кодов применим для любых кодов, но при больших k размер кодовой таблицы оказывается слишком большим для использования на практике.
Другим способом задания линейных блочных кодов является использование так называемой системы проверочных уравнений, определяющих правило, по которому символы информационной последовательности преобразуются в кодовые символы. Для того же примера система проверочных уравнений будет выглядеть следующим образом:
U0 = m0, U1 = m1, U2 = m2, U3 = m0 + m1 + m2.
Однако наиболее удобным и наглядным способом описания линейных блочных кодов является их задание с использованием порождающей матрицы, являющейся компактной формой представления системы проверочных уравнений:
|
|
1 0 0 … 0 |
P00 P01 . . . . P0, n- k- 1 |
|
|
G = |
0 1 0 … 0 |
P10 P11 . . . . P1, n- k- 1 |
|
|
……… |
……………… |
|
|
|
|
0 0 0 … 1 |
Pk- 1, 0 Pk- 1, 1 . . . . Pk- 1, n- k- 1 |
|
|
единичная матрица I |
матрица Р k*(n- k) |
Линейный блочный систематический (n,k)-код полностью определяется матрицей G размера k * n с двоичными матричными элементами. При этом каждое кодовое слово является линейной комбинацией строк матрицы G, а каждая линейная комбинация строк G - кодовым словом.
Пусть m = (m0 , m1 ,. . . , mk -1) будет тем блоком-сообщением, который необходимо закодировать с использованием данного кода.
Тогда соответствующим ему кодовым словом U будет
U = m× G .
С учетом структуры матрицы G символы кодового слова U будут такими:
для i = 0, 1, 2,. . . , k- 1 Ui = mi ; (1.12)
для i = k, k+1,. . . , n Ui = m0× P0j + m1× P1j + m2× P2j +…+ mk- 1× Pk- 1, j . (1.13)
Иными словами, k крайних левых символов кодового слова совпадает с символами кодируемой информационной последовательности, а остальные (n - к) символов являются линейными комбинациями символов информационной последовательности.
Определенный таким образом код называется линейным блочным систематическим (n,k) - кодом с обобщенными проверками на четность, а задающая его матрица G называется порождающей матрицей кода.
Применим данный алгоритм к семизначному коду Хемминга, являющегося систематическим линейным кодом с расстоянием , каждая комбинация которого содержит четыре информационных и три контрольных символа (так называемый (7,4)-код Хемминга). Коды Хемминга позволяют исправлять все одиночные ошибки.
Пусть m = (m0, m1, m2, m3) будет тем сообщением, или информационной последовательностью, которую нужно закодировать.
Порождающая матрица G для (7. 4)-кода Хемминга имеет вид
|
1 |
0 |
0 |
0 |
1 |
1 |
0 |
|
|
G(7,4) = |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
|
|
0 |
0 |
1 |
0 |
1 |
1 |
1 |
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
Тогда символы соответствующего кодового слова определяются следующим образом :
|
1 |
0 |
0 |
0 |
1 |
1 |
0 |
||
|
U = m× G = ( m0 m1 m2 m3 ) |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
= |
|
0 |
0 |
1 |
0 |
1 |
1 |
1 |
||
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
= (m0 , m1 , m2 , m3 , m0 + m2 + m3 , m0 + m1 + m2 , m1 + m2 + m3 ), (1.15)
Например, для m = ( 1 0 1 1 ) соответствующее кодовое слово будет иметь вид U = ( 1 0 1 1 1 0 0 ), для m = ( 1 0 0 0 ) - U = ( 1 0 0 0 1 1 0 ).
Линейный систематический блочный код может быть определен также с использованием так называемой проверочной матрицы H, обладающей следующим свойством:
- если некоторая последовательность U является кодовым словом, то
U* HT = 0. (1.17)
Другими словами, проверочная матрица H ортогональна любой кодовой последовательности данного кода.
Проверочная матрица имеет размерность (n-k)*n и следующую структуру :
|
P00 |
P10 |
… |
Pk-1, 0 |
1 |
0 |
0 |
… |
0 |
||
|
P01 |
P11 |
… |
Pk-1, 1 |
0 |
1 |
0 |
… |
0 |
||
|
H = |
P22 |
P12 |
… |
Pk-1, 2 |
0 |
0 |
1 |
… |
0 |
, (1.18) |
|
… |
… |
… |
… |
… |
… |
… |
… |
… |
||
|
P0, n-k-1 |
P1, n-k-1 |
… |
Pk-1, n-k-1 |
0 |
0 |
0 |
… |
1 |
||
|
PT |
I1(n-k)´(n-k) |
где PT - транспонированная подматрица P из порождающей матрицы G ;
I1(n-k)´(n-k) - единичная матрица соответствующего размера.
Видно, что единичная и проверочная подматрицы в G и H поменялись местами, кроме того, изменился их размер.
Для рассматриваемого нами в качестве примера (7,4)-кода Хемминга проверочная матрица H имеет вид
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
||
|
H(7,4)= |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
. (1.19) |
|
|
0 |
1 |
1 |
1 |
0 |
0 |
1 |
Проверочная матрица позволяет легко определить, является ли принятая последовательность кодовым словом данного кода.
Если принята последовательность символов c = (1011001), то
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
T |
|
|
c* HT = (1011001) |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
= (1 1 0) ¹ 0 . |
|
0 |
1 |
1 |
1 |
0 |
0 |
1 |
Отсюда можно сделать вывод, что последовательность c = (1011001) не является кодовым словом данного кода.
Рассмотрим другой пример. Допустим, принята последовательность d = (0010111), тогда
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
T |
|
|
d × HT = (0010111) |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
= (0 0 0) = 0 , |
|
0 |
1 |
1 |
1 |
0 |
0 |
1 |
то есть двоичная последовательность d принадлежит коду с проверочной матрицей H.
Прежде чем говорить об обнаружении и исправлении ошибок корректирующими кодами, определим само понятие ошибки и методы их описания.
Пусть U = ( U0 , U1 ,… Un ) является кодовым словом, переданным по каналу с помехами, а r = ( r0 , r1 , ... rn ) - принятой последовательностью, возможно, отличающейся от переданного кодового слова U. Отличие r от U состоит в том, что некоторые символы ri принятой последовательности могут отличаться от соответствующих символов Ui переданного кодового слова. Например, U = ( 0 0 0 1 0 0 0 ) , а r = ( 0 0 0 0 0 0 0 ) , то есть произошла ошибка в четвертом символе (бите) кодового слова, 1 перешла в 0 .
Для описания возникающих в канале ошибок используют вектор ошибки, обычно обозначаемый как e и представляющий собой двоичную последовательность длиной n с единицами в тех позициях, в которых произошли ошибки.
Так, вектор ошибки e = ( 0 0 0 1 0 0 0 ) означает однократную ошибку в четвертой позиции (четвертом бите).
Тогда при передаче кодового слова U по каналу с ошибками принятая последовательность r будет иметь вид
r = U + e , (1.21)
например: U = ( 0 0 0 1 0 0 0 ),
e = ( 0 0 0 1 0 0 0 ), (1.22)
r = ( 0 0 0 0 0 0 0 ) .
Приняв вектор r, декодер сначала должен определить, имеются ли в принятой последовательности ошибки. Если ошибки есть, то он должен выполнить действия по их исправлению.
Чтобы проверить, является ли принятый вектор кодовым словом, декодер вычисляет (n-k)-последовательность, определяемую следующим образом :
S = ( S0 , S1 , … , Sn-k-1 ) = r HT. (1.23)
При этом r является кодовым словом тогда, и только тогда, когда S = (00..0), и не является кодовым словом данного кода, если S 0. Следовательно, ненулевое значение S служит признаком наличия ошибок в принятой последовательности. Поэтому вектор S называется синдромом принятого вектора r.
Некоторые сочетания ошибок, используя синдром, обнаружить невозможно. Например, если переданное кодовое слово U под влиянием помех превратилось в другое действительное кодовое слово V этого же кода, то синдром S = V HT = 0 . В этом случае декодер ошибки не обнаружит и, естественно, не попытается ее исправить.
Сочетания ошибок такого типа называются необнаруживаемыми. При построении кодов необходимо стремиться к тому, чтобы они обнаруживали наиболее вероятные сочетания ошибок.
Для рассматриваемого в качестве примера линейного блочного систематического (7,4)-кода Хемминга синдром определяется следующим образом:
пусть принят вектор r = ( r0 , r1 , r2 , r3 , r4 , r5 , r6 ), тогда
|
1 0 1 1 1 0 0 |
T |
|
|
S = r H(7,4)T = ( r0, r1, r2, r3, r4, r5, r6 ) |
1 1 1 0 0 1 0 |
= |
|
0 1 1 1 0 0 1 |
= (r0 + r2 + r3 + r4 ), ( r0 + r1 + r2 + r5 ), ( r1 + r2 + r2 + r6 ), (1.23)
или
S0 = r0 + r2 + r3 + r4 ,
S1 = r0 + r1 + r2 + r5 , (1.24)
S2 = r1 + r2 + r2 + r6 .
Покажем, как можно использовать синдром принятого вектора не только для обнаружения, но и для исправления ошибок.
Пусть U = ( U0 , U1 , …, Un-1 ), e = ( е0 , е1, …, еn-1 ) и r = ( r0 , r1, r2 , …, rn-1) являются передаваемым кодовым словом, вектором-ошибкой и принятым вектором соответственно. Тогда
r = U + e (1.25)
и синдром
S = rHT = (U + e ) HT = U HT + e HT = 0 + e HT = e HT , (1.26)
поскольку для любого кодового слова U HT = 0.
Таким образом, синдром принятой последовательности r зависит только от ошибки, имеющей место в этой последовательности, и совершенно не зависит от переданного кодового слова. Задача декодера, используя эту зависимость, определить элементы (координаты) вектора ошибок. Найдя вектор ошибки можно восстановить кодовое слово как
U* = r + e . (1.27)
На примере одиночных ошибок при кодировании с использованием линейного блочного (7,4)-кода покажем, как вектор ошибки связан с синдромом, и как, имея синдром, локализовать и устранить ошибки при передаче.
Найдем значения синдрома для всех возможных одиночных ошибок в последовательности из семи символов:
e_ = ( 0000000 ),
|
1011100 |
T |
|
|
e_ HT = ( 0000000 ) |
1110010 |
= (000); |
|
0111001 |
e0 = ( 1000000 ),
|
1011100 |
T |
|
|
e0 HT = ( 1000000 ) |
1110010 |
= (110); |
|
0111001 |
e1 = ( 0100000 ),
|
1011100 |
T |
|
|
e1 HT = ( 0100000 ) |
1110010 |
= (011); |
|
0111001 |
e2 = ( 0010000 ),
|
1011100 |
T |
|
|
e2 HT = ( 0010000 ) |
1110010 |
= (111); |
|
0111001 |
e3 = ( 0001000 ),
|
1011100 |
T |
|
|
e3 HT = ( 0001000 ) |
1110010 |
= (101); |
|
0111001 |
e4 = ( 0000100 ),
|
1011100 |
T |
|
|
e4 HT = ( 0000100 ) |
1110010 |
= (100); |
|
0111001 |
e5 = ( 0000010 ),
|
1011100 |
T |
|
|
e5 HT = ( 0000010 ) |
1110010 |
= (010); |
|
0111001 |
e6 = ( 0000001 ),
|
1011100 |
T |
|
|
e6 HT = ( 0000001 ) |
1110010 |
= (001). |
|
0111001 |
Все возможные для (7,4)-кода одиночные ошибки и соответствующие им векторы синдрома приведены в табл. 2.
Таблица 2
|
Вектор ошибки |
Синдром ошибки |
|
1000000 |
110 |
|
0100000 |
011 |
|
0010000 |
111 |
|
0001000 |
101 |
|
0000100 |
100 |
|
0000010 |
010 |
|
0000001 |
001 |
Из этой таблицы видно, что существует однозначное соответствие между сочетанием ошибок (при одиночной ошибке) и его синдромом, то есть, зная синдром, можно совершенно однозначно определить позицию кода, в которой произошла ошибка.
Например, если синдром, вычисленный по принятому вектору, равен ( 111 ), это значит, что произошла одиночная ошибка в третьем символе, если S = ( 001 ) – то в последнем, и т.д.
Если место ошибки определено, то устранить ее не представляет труда.
Пусть теперь в принятой последовательности будет не одна, а, например, две ошибки, возникшие во второй и шестой позициях e = ( 0100010 ). Соответствующий синдром определится как
S = ( 0100010 ) = (001).
Однако синдром S = ( 001 ) соответствует также и одиночной ошибке в седьмой позиции ( e6 ). Следовательно, наш декодер не только не исправит ошибок в позициях, в которых они произошли, но и внесет ошибку в ту позицию, где ее не было. Таким образом, видно, что (7,4)-код не обеспечивает исправления двойных ошибок, а также ошибок большей кратности.
Это обусловлено свойствами самого кода.
Приведем несколько типичных примеров использования эффективного кодирования в системах связи. Один из типичных случаев характерен для систем, в которых требуются очень мощные коды. Под мощными кодами понимаются коды с длинными блоками и большим кодовым расстоянием. Обычный метод реализации таких кодов состоит в каскадировании двух или более простых кодов.
Еще одной интересной проблемой является кодирование для каналов, в которых ошибки возникают не независимо, а пакетами. Рассмотренные ранее методы кодирования при этом становятся совершенно неэффективными, поскольку все их характеристики определялись исходя из того, что ошибки в отдельных символах независимы друг от друга.
Каскадные коды были впервые предложены в качестве метода практической реализации кода с большой длиной блока и высокой корректирующей способностью. Эта цель достигается введением нескольких уровней кодирования, обычно – двух.
Основную идею каскадного кодирования с двумя уровнями иллюстрирует рис. 1.
Рис. 1
В этой схеме комбинацию внутреннего кодера, канала и внутреннего декодера иногда называют суперканалом, аналогично, комбинацию внешнего и внутреннего кодеров - суперкодером, а комбинацию внутреннего и внешнего декодеров – супердекодером.
Длина каскадного кода получается равной N1 = N·n двоичных символов, где N - длина внешнего кода, а n - длина внутреннего кода. При этом информационная длина кода составляет K1 = K · k двоичных символов, а скорость кода R1 = R · r. Несмотря на то, что общая длина кода получается большой и, соответственно, значительно возрастает его исправляющая способность, его декодирование может выполняться с помощью двух декодеров, рассчитанных на длины составляющих его кодов n и N. Это позволяет многократно снизить сложность декодера в сравнении с тем, если бы такая исправляющая способность достигалась одноуровневым кодированием.
Простейшей иллюстрацией к каскадному кодированию является итеративный код, рассмотренный ранее. Этот код состоит из простых кодов с проверкой на четность (по строкам и столбцам), но в то же время обладает исправляющей способностью. На практике, конечно, используются гораздо более сложные коды.
Обычно внешнее кодирование выполняется блочными кодами, а внутреннее сверточными кодами.
Построенный каскадный код эквивалентен линейному двоичному коду с минимальным расстоянием .
Использование каскадных кодов позволяет сделать скорость передачи сколь угодно близкой к пропускной способности канала. Они во многих отношениях наиболее перспективны среди известных блоковых помехоустойчивых кодов.
Каскадное кодирование широко применяется на практике, в частности, при помехоустойчивом кодировании речевой информации в системе сотовой связи формата GSM.
Все рассмотренные ранее методы кодирования и примеры расчета их эффективности относились к каналам без памяти, то есть к каналам, в которых вероятность ошибки постоянна и не зависит от времени. На практике же ошибки обычно группируются так называемыми пакетами. При постоянной средней вероятности ошибок на большом интервале времени значение Pош на отдельных коротких интервалах может значительно превышать среднее значение - Pош ср. Использование традиционных методов кодирования-декодирования потребовало бы в этом случае применения сложных кодов с большой исправляющей способностью и, соответственно, большой избыточностью.
В каналах с памятью ошибки могут возникать группами и их оказывается слишком много для исправления в конкретном временном интервале. Примером являются каналы с замираниями, когда сигнал поступает на приемник по двум или более путям различной длины. В итоге суммарный сигнал оказывается искаженным. Таким эффектом обладают каналы мобильной беспроводной связи. Во многих системах появление групповых ошибок могут стимулировать импульсные помехи.
Одно из возможных решений в таких случаях заключается в использовании достаточно простого кода, рассчитанного на исправление одиночных ошибок, вместе с парой устройств, выполняющих чередование (интерливинг – “interleaving” перемежение) закодированных символов перед их передачей в канал и восстановление (дечередование) после приема. При такой обработке кодовой и принятой последовательностей ошибки на входе декодера распределяются более равномерно.
Чередование битов кодированного сообщения перед передачей и обратная операция после приема приводят к рассеянию пакета ошибок во времени и они становятся для декодера случайно распределенными. Таким образом происходит как бы превращение канала в канал без памяти, и, следовательно, появляется возможность эффективно использовать коды с коррекцией случайных ошибок, рассмотренные ранее.
Структурная схема системы с чередованием показана на рис. 2.
Рис. 2
Устройство чередования в этой схеме переупорядочивает (переставляет) символы передаваемой последовательности некоторым детерминированным образом в пределах нескольких блоков. Требуемый промежуток чередования определяется длительностью пакета ошибок. С помощью устройства восстановления производится обратная перестановка, восстанавливающая исходный порядок следования символов.
Следует отметить, что имеется два способа чередования-восстановления. Первый способ – периодическое чередование. Он проще, но при изменении характера помех может оказаться неустойчивым. Более сложное – псевдослучайное чередование, которое обладает при нестационарных ошибках гораздо большей устойчивостью.
Периодическое чередование
При периодическом чередовании функция перестановок периодична с некоторым периодом.
Типичное блочное устройство чередования работает следующим образом. Кодовые символы записываются в матрицу, имеющую N строк и M столбцов построчно, а читаются из нее по столбцам. На приемной стороне операция выполняется в обратном порядке: запись производится по столбцам, а чтение - по строкам. При этом происходит восстановление исходного порядка следования символов. Естественно, что процедуры перемежения и дечередования должны быть синхронизированы.
При таком перемежении достигается следующее: любой пакет ошибок длиной m ≤ M переходит на выходе устройства восстановления в одиночные ошибки, каждая пара которых разделена не менее чем N символами. Правда, при этом любая периодическая с периодом M одиночная ошибка превращается в пакет, но вероятность такого преобразования очень мала, хотя и существует.
Проиллюстрируем алгоритм периодического чередования на следующем примере. Пусть передается 7 кодовых слов, каждое из которых состоит из 7 кодовых символов. Допустим, наш код способен исправлять однобитовые ошибки в любой 7-символьной последовательности. Если пакет ошибок имеет длительность, равную длине одного кодового слова (7 символов), то он способен уничтожить информацию в одном или двух кодовых словах. На рис. 3 приводится один из возможных алгоритмов чередования. Вначале в результате перемешивания битов кодовые символы перемешиваются (Ри3, б)). Полученный поток преобразуется в модулированный сигнал и передается по каналу. В результате импульсной помехи образуется групповая ошибка длиной в 7 символов. В процессе приема восстанавливается исходный порядок битов. Так как ошибки перераспределились по одной на каждое слово, поток легко декодируется любым традиционным способом.
Рис. 3. Пример процедуры чередования битов:
а) исходные кодовые слова, содержащие по 7 символов,
б) при передаче сообщения, подвергнутого битовому чередованию, возникла группа ошибок длительностью 7 символов,
в) пакет ошибок перераспределяется после восстановления, в результате каждое слово имеет всего по одной ошибке.
Рис. 4. Реализация процедуры чередования в рассмотренном примере
Псевдослучайное чередование
При псевдослучайном чередовании блоки из L символов записываются в память с произвольной выборкой, а затем считываются из нее псевдослучайным образом. Порядок перестановок, одинаковый для устройств чередования и восстановления, можно записать в ПЗУ и использовать его для адресации.
Как и для периодического чередования, существует вероятность того, что ошибки будут следовать таким образом (синхронно с чередованием), что одиночные ошибки будут группироваться в пакеты. Но такая вероятность чрезвычайно мала (если, конечно, это не организованная помеха и противник не знает порядка перемежения). Случайное же совпадение порядка следования перестановок при перемежении и импульсов помехи при достаточной длине L практически невероятно.
Адаптивные корректирующие коды
Существенным недостатком многих корректирующих кодов является их слабая приспособленность к изменяющимся условиям передачи информации. Избыточность таких кодов постоянна и выбирается обычно из соображений обеспечения требуемой верности при наихудших условиях передачи. Если избыточность кода привести в соответствие с реальным состоянием канала в контролируемом интервале времени, можно существенно повысить эффективность использования каналов без снижения достоверности. Эта идея лежит в основе адаптивных корректирующих кодов.
Различают методы адаптивного декодирования, когда в зависимости от числа ошибок в принимаемых кодовых комбинациях изменяют структуру или параметры алгоритмов декодирования и функции схем декодеров, и методы адаптивного кодирования, когда наряду с этим изменяют структуру или параметры кодов, алгоритмов кодирования и схем кодеров.
Для построения схем адаптивного кодирования требуется канал обратной связи, по которому на передающую сторону направляют информацию о качестве канала и об условиях приема.
Обнаружение ошибок адаптивными кодами систем без обратной связи позволяет обеспечить практически любую заданную достоверность при относительно невысокой сложности оборудования, но часть информации теряется, так как комбинации с обнаруженными ошибками потребителю не выдаются. Исправление ошибок также позволяет обеспечить достоверность передачи, но при отсутствии потерь информации. Платой за это является значительное увеличение длины кодовых комбинаций – до десятков тысяч разрядов, а также существенное усложнение аппаратуры. Недостатком систем без обратной связи является и то, что передатчик не получает никаких подтверждений о том, как принята информация приемником. Системы без обратной связи находят применение в случаях, когда канал обратной связи невозможно организовать, или когда недопустимы задержки при передаче информации. К таким системам относятся, например, некоторые системы спутниковой связи.
Наиболее широкое распространение получили системы с обратной связью, в которых повышение достоверности достигается обнаружением ошибок на приемном конце и повторением только неправильно принятых комбинаций. Адаптивное управление повторением информации существенно приближает избыточность кода к информационному пределу.
Основными задачами, которые решают при построении систем с адаптивными алгоритмами кодирования и декодирования, являются:
Теория адаптивного корректирующего кодирования интенсивно развивается, так как она позволяет более полно учесть реальные условия передачи информации.
На приемной стороне о передаваемых сигналах обычно имеются некоторые предварительные (априорные) сведения. Могут быть известны, например, частота несущей, вид модуляции и т.п. - абсолютно неизвестный сигнал нельзя было бы принять.
Известные параметры сигнала используются в приемнике для лучшего отделения сигналов от помех. Чем больше мы знаем о сигнале, тем совершеннее могут быть методы приема.
Изменения параметров сигналов, переносящих информацию (информационных параметров) на приемной стороне, как правило, неизвестны.
В зависимости от вида и назначения системы передачи информации при приеме сигналов возникают следующие основные задачи:
1. При обнаружении сигналов задача сводится к получению ответа на вопрос, имеется ли на входе приемника сигнал или нет, точнее, имеется ли на входе сигнал плюс шум или только шум. С такой задачей очень часто встречаются в радиолокации, встречается она также и в системах передачи дискретной информации.
2. При передаче двух сигналов возникает задача не обнаружения, а различения сигналов. Здесь, очевидно, необходимо ответить на вопрос, имеется ли на входе приемника сигнал . Ответ на этот вопрос определяется уже не свойствами каждого сигнала в отдельности, а их различием. Сигналы могут отличаться один от другого своими параметрами. Очевидно, следует стремиться к тому, чтобы различие было наибольшим и устойчивым к воздействию помех. Передача двоичным кодом, в котором каждому символу (1 и 0) соответствует определенный сигнал (), не равный нулю, называется передачей с активной паузой. Случай различения многих сигналов принципиально мало отличается от случая различения двух сигналов.
3. Задача восстановления сообщения принципиально отличается от задач обнаружения и различения сигналов. Она состоит в том, чтобы получить выходной сигнал , наименее отличающийся от переданного сообщения . При этом сообщение заранее неизвестно: известно лишь, что оно принадлежит к некоторому множеству или является реализацией некоторого случайного процесса.
Функциональная схема обработки дискретных сигналов приведена на рис. 1.
Рис. 1. Функциональная схема обработки дискретных сигналов
Принятый сигнал, искаженный помехой, в приемнике подвергается определенной обработке, детектируется и для опознания поступает на решающее устройство. Очевидно, что вероятность правильного опознавания сигналов существенно зависит от отношения сигнала к помехе S/N на входе решающего устройства. В связи с этим основной задачей обработки сигналов в приемнике является увеличение отношения сигнал/шум. Обработка сигналов, как правило, сводится к тем или иным методам фильтрации.
В каскадах обработки производится также усиление сигналов до величин, при которых могут нормально работать детектор и решающее устройство.
В обычном приемнике непрерывных сигналов детекторная обработка сигналов осуществляется с помощью резонансных усилителей, обеспечивающих необходимую частотную избирательность. Функции последетекторной обработки при этом выполняются видеоусилителем (или усилителем низкой частоты). Решающее устройство в таких приемниках отсутствует. Вместо него на выходе имеется устройство, воспроизводящее или записывающее (регистрирующее) принятое сообщение.
В системах передачи дискретных сообщений основными видами обработки сигналов в приемнике являются фильтрация со стробированием, и интегрирование .
При стробировании данного элемента сигнала производится отсчет его текущего значения (напряжения или тока) в определенный момент времени. Выбираемый момент времени соответствует той части элемента сигнала, которая в наименьшей степени подвержена искажениям. Момент стробирования лучше выбирать тогда, когда полезный сигнал имеет максимальное значение. Стробирование производится при помощи специальных сигналов, поступающих от системы синхронизации.
Фильтрация принимаемых сигналов обычно она выполняется дважды – до и после детектора.
Операция интегрирования может рассматривать либо как процесс накопления (суммирования), либо как определение среднего значения сигнала. Интегрирование, также как и фильтрация, может осуществляться либо до, либо после детектора.
Методы приема можно классифицировать по видам применяемых детекторов, по способам додетекторной и последетекторной обработки. Различают когерентный и некогерентный методы приема:
Когерентный прием сигналов осуществляется при следующих условиях: передаваемые сигналы st (х), i = 1,..., т, полностью известны, канал связи имеет известные параметры, помеха п(х) носит аддитивный характер, синхронизация сигналов является идеальной. Для некогерентного приема характерно нарушение хотя бы одного из этих условий.
Остановимся кратко на одном из эффективных и широко применяемых методов борьбы с помехами – методе накопления. Сущность метода заключается в том, что сигнал или его элементы многократно повторяются. В приемнике информации отдельные образцы сигнала сличаются (обычно суммируются), и так как различные образцы по разному искажаются помехами, в силу независимости помех можно восстановить сигнал с большой достоверностью. В простейшей форме метод накопления часто применяется при телефонном разговоре, когда переспрашивают и повторяют одно и то же слово по несколько раз.
В условиях сильных помех при использовании двоичного кода каждая кодовая комбинация также передается несколько раз и на приеме решение выносится “по большинству”, например:
|
Передаваемая комбинация |
01001 |
|
1-ая принятая комбинация |
00001 |
|
2-ая принятая комбинация |
11010 |
|
3-ая принятая комбинация |
01101 |
|
Воспроизведенная комбинация |
01001 |
Заметим, что можно получить n образцов сигнала не путем их повторения, а путем передачи по независимым каналам, разделенным по частоте, или каким-либо иным способом.
Критерии оптимального приема сигналов
Для систем связи чрезвычайно важным является выбор оптимальной решающей схемы, позволяющей распознавать принимаемые сигналы. В связи с этим необходимо предварительно выяснить, в каком смысле понимается оптимальность.
Следует отметить, что выбор критерия оптимальности приема сигналов не является универсальным и зависит от поставленной задачи и условий работы системы.
Рассмотрим два часто используемых критерия оптимального приема.
А. Критерий максимального правдоподобия
Пусть на вход приемника поступает сумма сигнала и помехи
где - сигнал, которому соответствует кодовый символ , - аддитивная помеха. На основании анализа колебания приемник воспроизводит сигнал . При наличии помех это воспроизведение не может быть совершенно точным. По принятой реализации сигнала приемник вычисляет апостериорное распределение , содержащее все сведения, которые можно извлечь из принятой реализации сигнала .
При передаче дискретных сообщений широко используется критерий максимального правдоподобия, согласно которому принимается решение, что передан сигнал , для которого апостериорная вероятность имеет наибольшее значение, т.е. регистрируется сигнал , если выполняются неравенства
При использовании такого критерия полная вероятность ошибочного решения будет минимальной.
С помощью формулы Байеса
неравенства (1) можно записать в виде
или
Функцию называют функцией правдоподобия. Чем больше значение этой функции при данной реализации сигнала x, тем правдоподобнее предположение, что передавался сигнал s. Отношение, входящее в последнее неравенство
называют отношением правдоподобия. Пользуясь этим понятием, правило решения (5) можно записать в виде
Таким образом, данный критерий сводится к сравнению отношений правдоподобия (6).
Рассмотрим вопрос о реализации решающей схемы декодирования при использовании метода максимального правдоподобия.
Пусть является переданным кодовым словом некоторого двоичного блочного (n,k)-кода, а - последовательность, принятая на выходе канала с помехами.
Принятая последовательность из-за действия шумов может отличаться от переданной, то есть по отдельным символам приемник мог принять неправильные решения (вместо нулей – единицы и наоборот).
Декодер канала на основе принятой последовательности должен принять решение относительно переданного кодового слова.
Приемник не принимает решений относительно того, какой из символов ri ( 0 или 1 ) в данный момент принят, а отдает декодеру весь принятый сигнал x(t) и предоставляет ему право принимать решения.
Обозначим через − l-е кодовое слово используемого кода; - принятый сигнал, содержащий одно из кодовых слов и помеху.
Оптимальный декодер должен учитывать всю имеющуюся информацию об используемом коде, канале связи и помехах, действующих в этом канале, и обеспечивать максимальную вероятность правильных ответов о том, какие кодовые слова были переданы по каналу связи.
Оптимальный по критерию Байеса декодер должен выбирать в качестве решения кодовое слово U* = Uk, которое максимизирует условную вероятность P(Uk/x) того, что была передана последовательность Uk, если принята данная реализация сигнала x.
Оказывается, что значение P (Uk / x) принимает максимальное значение в том случае, когда минимальна величина
называемая евклидовым расстоянием между этим кодовым словом и принятым сигналом.
Таким образом, оптимальный декодер должен вычислить евклидовы расстояния между принятым сигналом x и всеми возможными кодовыми словами Uk данного кода и принять решение в пользу кодового слова Ul , минимизирующего dl 2 , то есть наиболее похожего на принятый сигнал.
Структурная схема декодера максимального правдоподобия, реализующего данное правило декодирования, приведена на рис. 2.
Рис. 2. Структурная схема декодера максимального правдоподобия
Метод максимального правдоподобия чаще применяется при использовании сверточных кодов, чем при использовании блочных кодов. Это связано со сложностью реализации декодеров максимального правдоподобия в случаях блочных кодов больших размеров.
Несмотря на естественность и простоту, критерий максимального правдоподобия имеет недостатки. Первый – для построения решающей схемы необходимо знать априорные вероятности передачи различных символов кода (см. (3). Второй – ошибки считаются одинаково нежелательными (имеют одинаковый вес). В некоторых случаях такое допущение неправильно – например, при передаче чисел ошибка в первых значащих цифрах более опасна, чем в последних. Второго из перечисленных недостатков лишен критерий среднего риска.
Б. Критерий среднего риска
Пусть при передаче используются т сигналов .
Потери, которые возникают при ошибочном решении, что был принят сигнал , когда на самом деле передавался , обозначим как . Естественно принять .
Условный риск при передаче определяется следующим образом
т.е. определяется суммой вероятностей ошибок с учётом потерь .
Если — априорная вероятность передачи сигналов или средняя частота, с которой сигналы передаются в канал, тогда средний риск при передаче одного сигнала из т возможных равен
Очевидно, что качество канала передачи сообщений тем выше, чем меньше средний риск R.
Критерий среднего риска является одним из наиболее общих. Он также принадлежит к типу байесовских критериев, поскольку основан на априорно известных вероятностях передачи отдельных сигналов и условной вероятности на при емной стороне.
Оптимизация процесса передачи требует выбора соответствующих сигналов и границ областей принятия решений, таких, чтобы выполнить условие R -> min. При длительной эксплуатации канал, построенный согласно критерию минимума среднего риска будет наиболее «экономичным» из всех возможных, т.к. сумма штрафов за ошибки в нём минимальна.
Практика построения современных систем передачи информации показывает, что наиболее дорогостоящими звеньями трактов передачи являются линии связи (кабельные, волоконно-оптические, сотовой мобильной радиосвязи, радиорелейной и спутниковой связи и т.д.).
Поскольку экономически нецелесообразно использовать дорогостоящую линию связи для передачи информации единственной паре абонентов, возникает необходимость построения многоканальных систем передачи, обеспечивающих передачу большого числа сообщений различных источников информации по общей линии связи. (Часто используется также термин “множественный доступ”). Многоканальная передача возможна в тех случаях, когда пропускная способность линии C не меньше суммарной производительности источников информации
где - производительность - го источника, а - число каналов (независимых источников информации). Многоканальные системы, так же как и одноканальные, могут быть аналоговыми и цифровыми. Для унификации аналоговых многоканальных систем за основной или стандартный канал принимают канал тональной частоты, обеспечивающий передачу сообщений с полосой частот 300 3400 Гц, соответствующей спектру телефонного сигнала. В цифровых системах передачи распространение получили цифровые каналы со скоростью 64 Кбит/с.
Многоканальные аналоговые системы формируются путем объединения каналов тональной частоты в группы, обычно кратные 12 каналам. Цифровые системы передачи, используемые на сетях связи, формируются в соответствии с принятыми иерархическими структурами.
Общий принцип построения системы многоканальной передачи поясняет структурная схема на рис. 1.
Рис. 1. Структурная схема многоканальной системы передачи информации
В этой системе первичные сигналы каждого источника с помощью индивидуальных передатчиков (модуляторов) преобразуются в соответствующие сигналы .
Совокупность канальных сигналов на выходе устройства объединения образует групповой сигнал , связанный с сигналами оператором объединения .
Наконец, с учетом частотного диапазона линии связи сигнал с помощью группового передатчика преобразуется в линейный сигнал , который и поступает в линию связи (ЛС).
На данном этапе будем считать, что помехи в канале отсутствуют, а канал не вносит искажения в принимаемый линейный сигнал , где - коэффициент передачи канала, который часто можно считать равным единице. Тогда на приемном конце ЛС линейный сигнал с помощью группового приемника Пр может быть вновь преобразован в групповой сигнал . Канальными или индивидуальными приемниками из группового сигнала выделяются соответствующие канальные сигналы , которые посредством детектирования преобразуются в предназначенные индивидуальным получателям сигналы .
Канальные передатчики вместе с устройствами объединения образуют аппаратуру объединения (уплотнения) каналов (АОК).
Групповой передатчик, линия связи и групповой приемник Пр составляют групповой тракт передачи, который вместе с аппаратурой объединения и разделения каналов составляет систему многоканальной связи (множественного доступа).
Индивидуальные приемники Пр системы, наряду с выполнением обычной операции преобразования канальных сигналов в соответствующие первичные сигналы (?), должны обеспечить выделение сигналов из группового сигнала с допустимыми искажениями. Аппаратуру индивидуальных приемников, обеспечивающую эту операцию, называют аппаратурой разделения каналов (АРК).
Для того чтобы разделяющие устройства были в состоянии различать сигналы отдельных каналов, должны существовать определенные признаки, присущие только сигналу данного канала. Такими признаками в общем случае могут быть параметры переносчика, например, амплитуда, частота или фаза в случае модуляции синусоидального переносчика, или временное положение, длительность или форма сигнала при модуляции импульсных переносчиков. Соответственно будут различаться и способы разделения сигналов: частотный, временной, фазовый, разделение по форме сигналов и др.
Для разделения канальных сигналов на приемной стороне требуется соответствующее число разделяющих устройств, причем k-е разделяющее устройство должно выполнять операцию выделения своего k-го сигнала. В идеальном случае это устройство должно откликаться (реагировать) только на “свой” сигнал и давать нулевые отклики на сигналы всех других каналов. В реальных случаях при разделении сигналов возникают переходные помехи.
Условие идеального разделения выполняется лишь для так называемых ортогональных сигналов, удовлетворяющих условиям
во временной области, либо условиям
в частотной области. В этих выражениях являются Фурье – образами сигналов , а - некоторые отличные от нуля константы.
Типичными ортогональными сигналами являются сигналы с неперекрывающимися спектрами, а также неперекрывающиеся во времени сигналы.
Распределение по каналам, характеризующееся ортогональными спектрами, для которых выполняется условие (2), называют уплотнением с временным разделением (time-division multiplexing TDM) или множественным доступом с временным разделением (time-division multiple access - TDMA). Распределение по каналам, характеризующееся ортогональными сигналами, для которых выполняется условие (3), называют уплотнением с частотным разделением (frequency-division multiplexing FDM) или множественным доступом с частотным разделением (frequency-division multiple access - FDMA).
Понятие о частотном, временном и фазовом разделении сигналов
А. Частотное разделение сигналов
Рассмотрим основные этапы преобразования сигналов, спектры которых занимают неперекрывающиеся полосы частот (рис. 2)
Рис. 2. Образование спектра группового сигнала при многоканальной передаче информации с частотным разделением каналов
Сначала в соответствии с передаваемыми сообщениями первичные индивидуальные сигналы со спектрами модулируют переносчики – несущие частоты каждого канала. Эта операция выполняется с помощью модуляторов канальных передатчиков. Полученные на выходе частотных фильтров спектры канальных сигналов занимают соответственно полосы частот . Необходимо выбирать несущие частоты так, чтобы полосы не перекрывались – при этом условии сигналы взаимно ортогональны. Спектры суммируются в 1-м устройстве объединения сигналов и их совокупность поступает на 2-й групповой модулятор M. Суммарная полоса частот группового сигнала . В групповом модуляторе спектр с помощью колебания несущей частоты переносится в область частот, отведенную для передачи данной группы каналов – таким образом, групповой сигнал преобразуется в линейный сигнал . При этом может использоваться любой вид модуляции, обеспечивающий необходимую помехоустойчивость передачи.
На приемной стороне тракта линейный сигнал поступает на групповой демодулятор (приемник Пр), который преобразует спектр линейного сигнала в спектр группового сигнала . Спектр группового сигнала затем с помощью канальных приемников и входящих в них частотных фильтроввновь разделяется на отдельные полосы и затем с помощью демодуляторов преобразуется в спектры сообщений , предназначенные получателям.
Для того чтобы без помех разделить сигналы при частотном разделении, каждый из фильтров должен пропустить без ослабления лишь те частоты, которые принадлежат сигналу данного канала и полностью подавить сигналы всех других каналов. На практике это недостижимо и при разделении каналов возникают взаимные помехи. Для снижения помех до допустимого уровня приходится вводить защитные частотные интервалы (см. Рис. 3)
Рис. 3. Введение защитных частотных интервалов между отдельными каналами
В современных системах многоканальной телефонной связи каждому каналу выделяется полоса частот 4 кГц, хотя ширина спектра передаваемых речевых сигналов составляет 3,1 кГц.
Временной способ разделения каналов
При временном разделении каналов групповой тракт предоставляется поочередно для передачи сигналов каждого канала многоканальной системы посредством специального коммутатора.
Сначала передается сигнал 1-го канала, затем следующего и так далее до последнего, после чего процедура многократно повторяется.
На приемной стороне устанавливается аналогичный коммутатор, который подключает групповой канал поочередно к приемникам различных каналов. Приемник - го канала подключается только на время передачи - го сигнала, и отключается во время передачи других сигналов. Для нормальной работы системы необходимо обеспечить синхронное переключение каналов на передающей и приемной сторонах.
В качестве канальных сигналов в системах с временным разделением каналов используются неперекрывающиеся во времени последовательности модулированных импульсов (например, по амплитуде)
Совокупность канальных сигналов образует групповой сигнал. На рис. 4 для простоты рассмотрена система с 2 каналами.
Рис. 4. Выделение полезного сигнала при временном разделении каналов
Групповой сигнал поступает на коммутатор приемной стороны, действие которого можно сравнить с “временным фильтром”; в результате временной фильтрации на выходе - го приемника выделяются лишь импульсы - го канала. Полученные после демодуляции сообщения поступают к получателю.
Для снижения уровня взаимных помех приходится вводить защитные временные интервалы.
Системы с временным разделением каналов несколько уступают системам с частотным разделением по эффективности использования частотного спектра, однако имеют преимущество в простоте аппаратуры.
Системы с временным разделением каналов находят широкое применение при передаче непрерывных сообщений с помощью аналоговых видов импульсной модуляции, но особенно в цифровых системах с импульсно – кодовой модуляцией.
Разделение сигналов по фазе
При этом типе разделения каналов передаваемые сигналы отличаются по фазе. Оказывается, что на одной несущей частоте при произвольных значениях амплитуд и фаз колебаний можно обеспечить лишь двухканальную передачу (с разностью фаз переносчиков ), что существенно ограничивает область использования данного типа разделения каналов.
Пропускная способность многоканальных систем передачи информации
Предельная пропускная способность системы передачи (бит/с) в пределах полосы пропускания тракта передачи при наличии стационарного гауссовского шума со средней мощностью и сигналов со средней мощностью определяется по формуле Шеннона
При многоканальной передаче возникают специфические переходные помехи между каналами, обусловленные неидеальностью разделяющих устройств на приемной стороне, а также искажениями в групповом тракте передачи. С учетом этого, для многоканальных систем формула Шеннона должна быть модифицирована и принимает вид
где - так называемый коэффициент взаимных переходных помех между каналами, определяемый, как правило, экспериментальным путем, а F – общая полоса пропускания многоканальной системы передачи информации.
Из формулы (5) следует, что переходные помехи ограничивают пропускную способность многоканальной системы. При реальных значениях коэффициента увеличение мощности сигнала сначала приводит к увеличению пропускной способности (как и в одноканальном случае), но дальнейшее увеличение мощности практически не приводит к увеличению С. Практика проектирования аппаратуры многоканальной связи показывает, что для снижения уровня взаимных помех приходится вводить защитные частотные интервалы между каналами, занимающие до 20% общей полосы пропускания системы передачи информации.
Множественный доступ с частотным разделением
в спутниковых системах
Большинство спутников связи расположено геостационарной орбите, т.е. на круговой орбите, лежащей в плоскости экватора на высоте от уровня моря примерно 35,8 тыс. км. Эта орбита отличается тем, что находящийся на ней спутник вращается синхронно с Землей и неподвижен относительно ее поверхности (периоды обращения Земли и спутника равны). Три спутника, расположенных через 120 градусов друг от друга, позволяют охватить территорию всего земного шара (за исключением полярных областей (рис. 5)
Рис. 5. Иллюстрация геостационарной орбиты (вид с полюса)
Большинство спутниковых систем связи используют ретрансляторы (“транспондеры”) отличающиеся тем, что сигналы “земля – спутник” усиливаются, сдвигаются по частоте и ретранслируются на Землю без обработки сигнала и демодуляции. Согласно международным соглашениям разрешено использовать любой спутник, работающий в диапазоне 500 МГц. Как правило, такой спутник имеет 12 транспондеров с шириной полосы 36 МГц каждый. Наиболее распространенные транспондеры работают в режиме FDM/FM/FDMA (уплотнение с частотным разделением, частотная модуляция, множественный доступ с частотным разделением). Это соответствует следующим этапам.
1. FDM. Сигналы обрабатываются с использованием FDM, в результате чего формируется составной многоканальный сигнал
2. FM. Составной сигнал модулируется несущей и передается на спутник.
3. FDMA. Поддиапазоны полосы транспондера (36 МГц) могут распределяться между различными пользователями. Каждому пользователю выделяется определенная полоса, на которой он получает доступ к транспондеру.
Основным преимуществом технологии FDMA по сравнению с TDMA является простота. Каналы FDMA не требуют синхронизации или централизованного распределения времени, причем каждый из каналов независим от остальных.
Множественный доступ с временным разделением
На рис. 6. приведен пример использования технологии TDMA в спутниковой связи. Время разбито на интервалы, называемые кадрами (frame). Каждый кадр делится на временные интервалы, которые могут быть распределены между пользователями.
Рис. 6. Иллюстрация технологии TDMA
Каждая наземная передающая станция транслирует информацию в виде пакетов таким образом, чтобы они поступали на спутник в соответствии с установленным расписанием. После принятия транспондером такие пакеты ретранслируются на Землю вместе с информацией от других передающих станций. Принимающая станция детектирует и разуплотняет данные соответствующего пакета, после чего информация поступает к соответствующим пользователям.
Схема TDM/TDMA является чрезвычайно эффективной в том случае, когда требования пользователя можно предвидеть, а поток данных значителен (временные интервалы практически всегда заполнены). В случае неравномерного или случайного потока данных этот метод себя не оправдывает.
λq
λq
ξ(t)
ξ(t)
Δ(λ)
е
д
tn
tn
t2
t1
t2
t1
t2
t1
tn
λM
λ2
λ1
λM
λ2
λ1
λM
λ2
λ1
t
t
t
t
t
t
г
в
б
а
λ(t)
(t)
λ(t)
λ(t)
λ(t)
λmax
λmin
λmax
λmin
λmax
λmin
Амплитуды модулирующих сигналов
An
A4
A3
A2
A1
A
0 20 30 40 … … … n0
a0/2
λ
λ
t
t
t
t
Δ(λ)
Δ
Δ
+1
+2
+N/2
-1
-2
-N/2
1
0
0
0
0
З
А
bi2
a i2
bk1
a k1
x(t)
S(t)
Непрерывный канал
Демодулятор
Декодер
Модулятор
Кодер
1
1
1
Б
В
Г
Д
Е
Ж
1
1
0
0
А
Б
В
1
0
Г
0
Д
1
0
1
C
B
0
0
0
1
1
1
E
A
D
8 пикселов
8 пикселов
|
231 |
224 |
224 |
217 |
217 |
203 |
189 |
196 |
|
210 |
217 |
203 |
189 |
203 |
224 |
217 |
224 |
|
196 |
217 |
210 |
224 |
203 |
203 |
196 |
189 |
|
210 |
203 |
196 |
203 |
182 |
203 |
182 |
189 |
|
203 |
224 |
203 |
217 |
196 |
175 |
154 |
140 |
|
182 |
189 |
168 |
161 |
154 |
126 |
119 |
112 |
|
175 |
154 |
126 |
105 |
140 |
105 |
119 |
84 |
|
154 |
98 |
105 |
98 |
105 |
63 |
112 |
84 |
|
42 |
28 |
35 |
28 |
42 |
49 |
35 |
42 |
|
49 |
49 |
35 |
28 |
35 |
35 |
35 |
42 |
|
42 |
21 |
21 |
28 |
42 |
35 |
42 |
28 |
|
21 |
35 |
35 |
42 |
42 |
28 |
28 |
14 |
|
56 |
70 |
77 |
84 |
91 |
28 |
28 |
21 |
|
70 |
126 |
133 |
147 |
161 |
91 |
35 |
14 |
|
126 |
203 |
189 |
182 |
175 |
175 |
35 |
21 |
|
49 |
189 |
245 |
210 |
182 |
84 |
21 |
35 |
|
154 |
154 |
175 |
182 |
189 |
168 |
217 |
175 |
|
154 |
147 |
168 |
154 |
168 |
168 |
196 |
175 |
|
175 |
154 |
203 |
175 |
189 |
182 |
196 |
182 |
|
175 |
168 |
168 |
168 |
140 |
175 |
168 |
203 |
|
168 |
168 |
154 |
196 |
175 |
189 |
203 |
154 |
|
168 |
161 |
161 |
168 |
154 |
154 |
189 |
189 |
|
147 |
161 |
175 |
182 |
189 |
175 |
217 |
175 |
|
175 |
175 |
203 |
175 |
189 |
175 |
175 |
182 |
амплитуда
DCT-спектр
Ai
Aj
110011
010011
010111
010110
dij =3
k
n-k
n
Внешний кодер
Внутренний кодер
Канал
Внешний декодер
Вход
Выход
(n,k)
(N,k)
Суперканал
Внутренний декодер
Кодер
Устройство чередования
Канал с пакетами ошибок
Устройство восстановления
Декодер
Вход данных
Выход данных
К декодеру
Принимаемые сигналы
схема
додетек-торной
обработки
детектор
схема последетекторной обработки
Решающее устройство
d1
d2
dm
min
Если
ПСN
АОК
АРК
ИС1
М1
ИС2
М2
ИСN
МN
Ф1
Ф2
ФN
Д1
Д2
ДN
ПС1
ПС2
М
ЛС
П
b1(t)
b2(t)
bN(t)
Пр1
Пр2
ПрN
uГ(t)
uл(t)
sл(t)
uN(t)
u1(t)
sГ(t)
SN(f)
f
SГ(f)
S1(f)
S2(f)
f1
f2
fN
f1
f2
fN
SГ(f)
f
fзащ
SГ(t)
t
S1(t)
S2(t)
t
t
t2
t1
Земля
Спутник 1
Спутник 2
Спутник 3
Наземные терминалы
Кадры
Передаваемые пакеты энергии в радиочастотном диапазоне
Спутник