Технология цифровой связи

Решетчатое (треллис) кодирование. При использовании в системах связи реального времени кодов коррекции ошибок достоверность передачи улучшается за счет расширения полосы частот. Как для блочных, так и для сверточных кодов преобразование каждого k-кортежа входных данных в более длинный n-кортеж кодового слова требует дополнительного расширения полосы пропускания. Вследствие этого в прошлом кодирование не было особенно популярно в узкополосных каналах (таких, как телефонные), в которых расширять полосу частот сигнала было нецелесообразно. Однако приблизительно с 1984 года возникает активный интерес к схемам, где модуляция объединяется с кодированием; такие схемы называются решетчатым кодированием (trellis-coded modulation -- ТСМ). Эти схемы позволяют повысить достоверность передачи, не расширяя при этом полосу частот сигнала.

Алгоритм декодирования Витерби. Алгоритм декодирования Витерби был открыт и проанализирован Витерби (Viterbi) в 1967 году. В алгоритме Витерби, по сути, реализуется декодирование, основанное на принципе максимального правдоподобия; однако в нем уменьшается вычислительная нагрузка за счет использования особенностей структуры конкретной решетки кода. Преимущество декодирования Витерби, по сравнению с декодированием по методу "грубой силы", заключается в том, что сложность декодера Витерби не является функцией количества символов в последовательности кодовых слов. Алгоритм включает в себя вычисление меры подобия (или расстояния), между сигналом, полученным в момент времени t₁ и всеми путями решетки, входящими в каждое состояние в момент времени t₁. В алгоритме Витерби не рассматриваются те пути решетки, которые, согласно принципу максимального правдоподобия, заведомо не могут быть оптимальными. Если в одно и то же состояние входят два пути, выбирается тот, который имеет лучшую метрику; такой путь называется выживающим. Отбор выживающих путей выполняется для каждого состояния. Таким образом, декодер углубляется в решетку, принимая решения путем исключения менее вероятных путей. Предварительный отказ от маловероятных путей упрощает процесс декодирования.

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

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

Рассмотрим принцип построения кодера кода Хемминга. Кодирование сводится к нахождению проверочных разрядов путем сложения по модулю 2 соответствующих информационных элементов. Поскольку на вход кодера символы поступают со скоростью k элементов в единицу времени, а на выходе формируется поток со скоростью n элементов в единицу времени, то для согласования скоростей необходимо буферное устройство памяти, содержащее k ячеек. Информация в буферную память записывается в последовательном коде и на (k+1)-м такте в параллельном коде поступает в кодирующее устройство. Сформированная n-разрядная комбинация в параллельном коде записывается в буферный регистр, откуда с нужной скоростью поступает в канал связи. Поскольку скорость работы кодирующего устройства может быть значительно выше, чем скорость поступления входной информации, то кодер всегда работает в реальном масштабе времени передачи информации.

12 Лекция №12. Системы связи с обратной связью

Цель лекции: изучение характеристик систем с обратной связью и рассмотрение структурной схемы с ОС.

Содержание:

а) характеристики систем с обратной связью и их особенности;

б) структурная схема системы с информационной обратной связью (ИОС) и решающей обратной связью (РОС), характеристики и алгоритмы работы.

12.1 Характеристики систем с обратной связью и их особенности

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

В зависимости от назначения ОС различают системы: с решающей обратной связью (РОС), информационной обратной связью (ИОС) и с комбинированной обратной связью (КОС).

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

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

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

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

Обратной связью могут быть охвачены различные части системы (рисунок 12.1):

1) канал связи, при этом по каналу ОС передаются сведения о принимаемом сигнале до принятия какого-либо решения;

2) дискретный канал, при этом по каналу ОС передаются решения, принятые первой решающей схемой PC₁ на основе анализа единичных элементов сигнала;

3) канал передачи данных, при этом по каналу ОС передаются решения, принятые второй решающей схемой РС₂ на основе анализа кодовых комбинаций.

Рисунок 12.1 - Обратная связь в системе ПДС

В системах с ИОС также возможны потери верности за счет ошибок в каналах ОС. В укороченных ИОС такие ошибки возникают по причинам, аналогичным вышеизложенным, когда квитанция, соответствующая искаженному сигналу в канале ОС, трансформируется в квитанцию, соответствующую неискаженному сигналу. В результате передатчик не в состоянии обнаружить факт ошибочного приема. В полных ИОС в канале ОС возможны искажения, полностью компенсирующие искажения в прямом канале, в результате чего ошибки не могут быть обнаружены. Поэтому вопросам образования каналов ОС в системах ПДС уделяется очень большое внимание. Каналы ОС обычно образуются в каналах обратного направления связи с помощью методов частотного или временного разделения от каналов передачи полезной информации. Методы ЧРК используют обычно в системах со сравнительно небольшой удельной скоростью передачи, например, при передаче данных со скоростью 600... 1200 бит/с по каналам ТЧ. Во многих системах с РОС применяется структурный метод разделения, когда для сигнала переспроса используется специальная кодовая комбинация, а любая разрешенная кодовая комбинация в приемнике дешифруется как сигнал подтверждения и любая неразрешенная комбинация - как сигнал переспроса. Для защиты от искаженных сигналов, передаваемых по каналам ОС, применяют те же способы, что и для повышения верности полезной информации: корректирующие коды, многократную и параллельную передачи.

12.2 Структурная схема системы с информационной обратной связью (ИОС) и решающей обратной связью (РОС), характеристики и алгоритмы работы

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

Рисунок 12.2 - Структурные схемы ПД с ОС

ПК_пер-передатчик прямого канала; ПК_пр- приемник прямого канала;

ОК_пер- передатчик обратного канала; ОК_пр- приемник обратного канала;

РУ-решающее устойство.

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

В системе с РОС по прямому каналу передаются информационные комбинации длиной п единичных элементов и команды решения, а по каналу обратной связи -- служебные комбинации. В системе с ИОС по прямому каналу передаются информационные комбинации длиной k единичных элементов и команды решения, а по каналу ОС -- проверочные комбинации длиной n--k единичных элементов. При n--k<k система с РОС подобна системе с укороченной ОС, при n--k=k -- системе ИОС с полной ОС. Нередко при сравнении систем с РОС и ИОС игнорируется это обстоятельство и сопоставляются системы с РОС при n--k?k с системой с полной (ретрансляционной) ОС. В результате сравнения несопоставимых систем делается вывод о том, что скорость передачи в системе с РОС указанного типа вдвое выше, чем в рассмотренной системе с ИОС.

Виды системы с РОС: системы с ожиданием служебных сигналов, системы с непрерывной передачей и блокировкой, системы с адресным переспросом. В настоящее время известны многочисленные алгоритмы работы систем с ОС. Наиболее распространенными среди них являются системы: с РОС с ожиданием сигнала ОС; с безадресным повторением и блокировкой приемника и с адресным повторением.

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

Системы с блокировкой осуществляют передачу непрерывной последовательности кодовых комбинаций при отсутствии сигналов ОС по предшествующим S комбинациям. После обнаружения ошибок в (S+1)-й комбинации выход системы блокируется на время приема S комбинаций, в запоминающем устройстве приемника системы ПДС стираются S ранее принятых комбинаций, и посылается сигнал переспроса. Передатчик повторяет передачу S последних переданных кодовых комбинаций.

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

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

13 Лекция №13. Сжатие данных в ЦСС

Цель лекции: изучение алгоритмов сжатия данных и видов сжатия данных.

Содержание:

а) алгоритмы сжатия без потерь;

б) сжатие аудиосигналов;

в) сжатие изображения.

13.1 Алгоритмы сжатия без потерь

Код Хаффмана. Код Хаффмана (Huffman code) (201 - это свободный от префикса код, который может давать самую короткую среднюю длину кода я для данного входного алфавита. Самая короткая средняя длина кода для конкретного алфавита может быть значительно больше энтропии алфавита источника, и тогда эта невозможность выполнения обещанного сжатия данных будет связана с алфавитом, а не с методом кодирования. Часть алфавита может быть модифицирована для получения кода расширения, и тот же метод повторно применяется для достижения лучшего сжатия. Эффективность сжатия определяется коэффициентом сжатия. Эта мера равна отношению среднего числа бит на выборку до сжатия к среднему числу бит на выборку после сжатия.

Код Лемпеля-Зива -Уэлча. Основной сложностью при использовании кода Хаффмана является то, что вероятности символов должны быть известны или оценены и как кодер, так и декодер должны знать дерево кодирования. Если дерево строится из необычного для кодера алфавита, канал, связывающий кодер и декодер, должен также отправлять кодирующее дерево как заголовок сжатого файла. Эти служебные издержки уменьшат эффективность сжатия, реализованную с помощью построения и применения дерева к алфавиту источника. Алгоритм Лемпеля-Зива (Lempel-Ziv) и его многочисленные разновидности используют текст сам по себе для итеративного построения синтаксически выделенной последовательности кодовых слов переменной длины, которые образуют кодовый словарь.

Алгоритм Хаффмана в факсимильной связи.

Факсимильная передача -- это процесс передачи двухмерного образа как последовательности последовательных строчных разверток. В действительности наиболее распространенными образами являются документы, содержащие текст и цифры. Положение строчной развертки и положение вдоль развертки квантуются в пространственные расположения, которые определяют двухмерную координатную сетку элементов картинки, называемых пикселями. Ширина стандартного документа МККТТ определяется равной 8,27 дюймов (20,7 см ), а длина- 11,7 дюймов (29,2 см), почти 8,5 дюймов на 11,0 дюймов. Пространственное квантование для нормального разрешения составляет 1728 пикселей/строку и 1188 строк/документ. Стандарт также определяет квантование с высоким разрешением с теми же 1728 пикселями/строку, но с 2376 строками/документ. Общее число отдельных пикселей для факсимильной передачи с нормальным разрешением составляет 2 052 864, и оно удваивается для высокого разрешения. Для сравнения, число пикселей в стандарте NTSC (National Television Standards Committee -- Национальный комитет по телевизионным стандартам) коммерческого телевидения составляет 480 х 460, или 307 200. Таким образом, факсимильное изображение имеет разрешение в 6,7 или 13,4 раза больше разрешения стандартного телевизионнго образа.

Сжатие аудиосигналов.

Аудиосжатие широко применяется в потребительских и профессиональных цифр< аудиопродуктах, таких как компакт-диски (compact disc -- CD), цифровая аудиолента (digital audio type -- DAT), мини-диск (mini-disk -- MD), цифровая компакт-кассета (digital compact cassette -- DCC), универсальный цифровой диск (digital versatile disc. DVD), цифровое аудиовещание (digital audio broadcasting -- DAB) и аудиопродукция формате МРЗ от экспертной группы по вопросам движущегося изображения (М< Picture Experts Group -- (MPEG). К тому же сжатие речи в телефонии, в частности, сотовой телефонии, требуемое для экономии полосы частот и сбережения времени, ни батареи, дало начало процессу разработки множества стандартов сжатия речи, личные алгоритмы применимы к речевым и потребительским сигналам более широкой полосы частот. Аудио- и речевые схемы сжатия можно для удобства разделить согласно приложениям, что отражает некоторую меру приемлемого качества.

Адаптивная дифференциальная ИКМ (АДИКМ). Используя прошлые данные для измерения (т.е. квантования) новых переходим от обычной импульсно-кодовой модуляции (pulse-code modulation -- PCM) к дифференциальной (differential PCM -- DPCM). В DPCM предсказание следующего выборочного значения формируется на основании предыдущих значений. Устройства квантования называются мгновенными устройствами квантования или устройствами квантования без памяти, так как цифровые преобразования основаны на единичной (текущей) входной выборке. Этими свойствами были неравновероятные уровни источника и зависимые выборочные значения. Корреляционные характеристики источника можно представить во временной области с помощью выборки его автокорреляционной функции и в частотной области -- его спектром мощности. Если изучается спектр мощности G_x(f) кратковременного речевого сигнала, как изображено на рисунке 9.2, то видим, что спектр имеет глобальный максимум в окрестности от 300 до 800 Гц и убывает со скоростью от 6 до 12 дБ/октаву. Эта операция производится в контуре сказания и сравнения, верхний контур кодера изображен на рисунке 13.2. Кодер корректирует свои предсказания, составляя сумму предсказанного значения и ошибки предсказания.

Рисунок 13.1 - N- отводный дифференциальный импульсно-кодовый модулятор с предсказанием

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

Рисунок 13.2 - Блочная диаграмма: моделирование речи с помощью линейного кодера с предсказанием

Алгоритм сжатия MPEG, уровни 1,2,3.

Международная организация по стандартизации (International Organization for Standardization - ISO) и экспертная группа по вопросам движущегося изображения (Motion Picture Experts Group - MPEG) разработали стандарт аудиосжатия для сигнала, синхронизированного с сжатым видеосигналом, известный как MPEG. В этой схеме объединены свойства MUS1CAM (Masking pattern adaptive Universal Subband Integrated Coding And Multiplexing - универсальные интегральные средства кодирования и уплотнения по поддиапазонам с маскировкой и адаптацией к кодограмме) и ASPEC (Adaptive Spectral Perceptual Entropy Coding -- адаптивное спектрально-восприимчивое кодирование энтропии). В схеме использованы три уровня (коды) увеличивающейся сложности и улучшающейся субъективной производительности. Входные частоты дискретизации равны 32, 44,1 и 48 кГц, а биты на выход подаются со скоростью от 32 до 192 Кбит/с (монофонический канал) или со скоростью от 64 до 384 Кбит/с (стереофонический канал). Стандарт поддерживает режим работы единственного канала, стереорежим, двойственный режим работы канала (для двуязычных аудиопрограмм) и дополнительный совместный стереорежим. В последнем режиме два кодера для левого и правого каналов могут поддерживать друг друга, используя общие статистики с целью снижения скорости передачи бит аудиосигнала, даже большего, чем это возможно при монофонической передаче.

На рисунке 13.3 представлена блочная диаграмма аудиокодера и декодера уровней I и II стандарта MPEG.

На уровне III стандарта MPEG/ISO (MP3) достигается разрешение более высокой частоты, которое весьма точно соответствует критической разрешающей способности человека.

Рисунок 13.3 - Блочная диаграмма аудиокодера и декодера, уровни I и II

Сжатие изображения

Мы часто слышали старое высказывание: Картина стоит тысячи слов. Верно ли оно? 1000 слов содержит 6000 знаков, которые, будучи закодированы как 7-битовые символы ASCII, требуют в общей сложности 42 000 бит. Какого размера образ (или картина) может быть описан с помощью 42 000 бит?

Существует множество стандартов, которые были разработаны для сжатия изображений.

Алгоритм сжатия JPEG. JPEG (Joint Photography Experts Group - объединенная группа экспертов в области фотографии) - это общее название, которое дано стандарту ISO/JPEG 10918-1 и стандарту ITU-T Recommendation T.81 "Цифровое сжатие, постоянных изображений непрерывного тона", JPEG, в основном, известен как основанная на преобразовании схема сжатия с потерями.

Рисунок 13.4 - Блочная диаграмма кодера JPEG

Применение вейвлет - преобразования для сжатия изображений.

Рекурсивный (волновой) алгоритм. Английское название рекурсивного сжатия -- wavelet. На русский язык оно также переводится как волновое сжатие и как сжатие с использованием всплесков. Этот вид архивации известен довольно давно и напрямую исходит из идеи использования когерентности областей.

Заключение

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

Список литературы

1. Скляр Б. Цифровая связь. Теоретические основы и практическое применение: 2-е изд. /Пер. с англ.? М.: Издательский дом «Вильямс», 2003. ? 1104 с.

2. Прокис Дж. Цифровая связь. Радио и связь, 2000.-797с.

3. А.Б. Сергиенко. Цифровая обработка сигналов: Учебник для вузов. - М.:-2002.

4. Шварцман В.О., Емельянов Г.А. Теория передачи дискретной информации. - М.: Связь, 1979. -424 с.

5. Передача дискретных сообщений / Под ред. В. П. Шувалова. - М.: Радио и связь, 1990. -464 с.

6. Емельянов Г. А., Шварцман В. О. Передача дискретной информации. - М.: Радио и связь, 1982. - 240 с.

7. Дмитриев В.И. Прикладная теория информации: Учебник. - М.: Высш.шк., 1989.

8. Тутевич В.Н. Телемеханика: Учебное пособие.- М.: Высш. Шк., 1985. -423 с.

9. Ватолин Д.С. Алгоритмы сжатия изображений. Методическое пособие. Издательский отдел факультета Вычислительной Математики и Кибернетики МГУ им. М.В.Ломоносова (лицензия ЛР № 040777 от 23.07.96), 1999 г. -- 76 с.