Алгоритмы и программные средства помехоустойчивого кодирования мультимедиа потоков в компьютерных сетях

Актуальность темы

В настоящее время происходит бурное развитие компьютерных сетей и рост числа сетевых приложений, в том числе для передачи цифровых мультимедиа данных. Цифровое телевещание через Интернет, так называемое IPTV (.Internet Protocol Television, IP телевидение), является одним из наиболее перспективных сетевых приложений. Как и в любой системе передачи данных, в компьютерных сетях существуют помехи, шумы, ведущие к потерям и искажениям данных. Для борьбы с помехами в системах передачи данных применяется помехоустойчивое кодирование. Помехоустойчивое кодирование выполняет важнейшую роль в цифровых системах передачи данных, так как повышает достоверность передаваемых данных путем внесения систематической избыточности согласно некоторому математическому закону (коду).

Теория помехоустойчивого кодирования была основана в середине XX в. и с тех пор превратилась в хорошо проработанную, математически стройную отрасль науки. Теория помехоустойчивого кодирования тесно переплетена с теорией информации. Основоположниками теории помехоустойчивого кодирования стали выдающиеся ученые В. А. Котельников, К. Шеннон, У. Питерсон, П.Элиас. Большинство ранних научных работ в области теории помехоустойчивого кодирования были направлены на поиск «оптимального» кода. «Оптимальный» код с точки зрения теории кодирования должен быть длинным и обладать достаточной глубиной для эффективного исправления ошибок. Этот поиск до сих пор не увенчался успехом, хотя изобретенные несколько десятилетий назад Турбо-коды являются квазиоптимальными.

Одной из важнейших сфер практического применения помехоустойчивого кодирования является цифровое телевидение (ЦТВ). Значимость развития цифрового телевидения прекрасно иллюстрирует тот факт, что решения в этой отрасли принимаются на государственном и международном уровнях. Правительство Российской Федерации в апреле 2006 года официально объявило о том, что к 2015 году в России планируется полностью перейти с аналогового на цифровое телевещание. В связи с этим разрабатывается Федеральная целевая программа «Развитие телерадиовещания в Российской Федерации (2007;2015 гг.)». Большинство европейских стран намерены окончательно перейти на цифровой стандарт телевещания к 2010 году.

В наши дни в сфере технологий цифрового телевидения происходят значительные изменения. Все большее количество телезрителей предпочитают пользоваться услугами /РТУ для просмотра телепередач. Передача цифровых мультимедиа данных к настоящему моменту стала одним из наиболее ресурсоемких сетевых приложений. Несмотря на значительные успехи, достигнутые в области компрессии цифрового видео и аудио, доля мультимедиа данных в общемировом объеме 1Р трафика неуклонно растет. Это обусловлено ростом числа пользователей сети Интернет, внедрением новых технологий 1РТУ, делающих просмотр телепрограмм более комфортным, расширением пропускной способности каналов связи, а также активным стремлением провайдеров телеконтента выйти на рынок услуг 1РТ¥с целью захвата новых сегментов зрительской аудитории. Если еще десять лет назад под «телевизионным приемником» однозначно понимался телевизор, то в наши дни в этой роли все чаще оказывается персональный компьютер, для которого источником цифрового телесигнала являются сети 1Р. По сравнению с системами спутникового и наземного цифрового телевещания, 1РТУ предлагает телезрителю ряд удобств, таких как «видео по запросу», пауза в трансляции и последующий просмотр с места остановки, «виртуальный видеомагнитофон» (запись передачи, идущей в определенное время) и т. д. Количество пользователей 1РТУ составляло 200 млн человек в 2005 году, и ожидается, что их количество увеличится до 400 млн человек в 2010 году [71].

Одной из наиболее острых актуальных проблем в /РТУ является проблема потерь пакетов мультимедиа данных при потоковом телевещании. Классические блоковые и сверточные помехоустойчивые коды оказались не способны решить названную проблему.

Сеть 1Р

Медиа Сервер: источник мультимедиа конггентл

Поток Аудио Видео данных I ИЕЭ1 к

Цифровой Аудио / Аудио ' Виде о Видео Компрессор

Обратный

Мультиплексор МРБС-г Т5

1Р сервер

Сервер 1РТ/

Рис. В.1. Архитектура современной системы 1РТУ. Иллюстрация увеличения нагрузки на сервер вещания в случае наличия обратного канала связи Разработка помехоустойчивых кодов для систем 1РТУ осложнена тем, что код должен отвечать сразу нескольким требованиям, подчас взаимоисключающим и требующим нахождения компромисса: • обладать способностью восстановления данных в случае потери целых пакетов при передаче. При этом помехоустойчивое кодирование должно быть прямым, т. е. не требовать наличия канала обратной связи между источником и получателем, так как запрос и повторная передача пакетов в системах потокового цифрового телевещания невозможна в силу особенностей мультимедиа данных и способа их обработки (см. рис. В.1). Во-первых, передача мультимедиа данных должна производиться без задержек в сети, дабы не нарушить плавность воспроизведения. Во-вторых, даже в гипотетическом случае существования возможности ретрансляции потерянных пакетов, нагрузка на канал связи возрастала бы пропорционально количеству пользователей сервиса, что привело бы в конечном итоге к перегрузке канала и усугублению проблемы потерь пакетов;

• обеспечивать высокую эффективность восстановления от ошибок, и тем самым высокое качество восприятия телевизионных программ;

• обеспечивать, по возможности, регулируемую гибкую схему кодирования, в зависимости от степени зашумленности канала передачи и условий приема потока мультимедиа данных;

• декодирование кода должно осуществляться с использованием недорогих вычислительных ресурсов, поскольку это определяет стоимость приемных устройств, приобретаемых пользователями. В случае, если приемником цифрового ТВ сигнала является персональный компьютер, то логично потребовать, чтобы декодирование на ПК было возможным в режиме реального времени без привлечения дополнительных вычислительных ресурсов;

• обеспечивать как можно меньшую конечную задержку данных {end-to-end delay) в цепи «передатчик — приемник» ТВ сигнала.

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

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

• разработка корректирующего помехоустойчивого кода, позволяющего добиться поставленной цели при соблюдении вышеперечисленных требований, налагаемых системами IPTV;

• разработка алгоритма декодирования помехоустойчивого кода, с использованием минимального объема физической памяти и вычислительных ресурсов процессора;

• проектирование технологии применения помехоустойчивого кода в системах /РТУ с учетом специфики потоков цифровых мультимедиа данных для комплексного повышения эффективности работы систем. Технология должна быть разработана в рамках общепринятых подходов реализации систем /РТУ, а также международных стандартов компрессии и транспортировки цифровых мультимедиа данных, и должна обеспечивать совместимость с существующими программными и аппаратными компонентами современных систем /РТУ.

Объект исследования: системы потокового цифрового телевещания по компьютерным сетям (./РТУ).

Предмет исследования: коды, корректирующие ошибки, а также алгоритмы декодирования, применительно к системам /РТУ. Кроме того, предметом исследования являются принципы и стандарты компрессии, форматы транспортировки цифровых мультимедиа данных, архитектуры современных систем /РТУ.

Методы исследования. В диссертации представлены результаты исследований, полученные с помощью математического (имитационного) моделирования, методов теории вероятности, статистического моделирования. В ходе работы использовались положения теории информации, помехоустойчивого кодирования, учитывались принципы компрессии и стандарты транспортировки цифровых мультимедиа данных. Моделирование осуществлялось средствами объектно-ориентированного языка программирования С++. В процессе программной реализации теоретических результатов использовались методы теории алгоритмов, теории структур данных, объектно-ориентированного и процедурного программирования.

Достоверность полученных в диссертационной работе результатов подтверждается:

• корректным применением методов теории помехоустойчивого кодирования;

• результатами компьютерного (имитационного) моделирования;

• непротиворечивостью результатов с предполагаемыми теоретическими оценками.

Научная новизна:

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

2. Разработан стирающий помехоустойчивый код с детерминированной алгоритмической структурой («неслучайный стирающий код», НССК) для применения в системах 1РТУ, отличающийся от известных стирающих кодов тем, что позволяет учитывать при кодировании приоритет исходных информационных символов (пакетов), обеспечивая более надежную доставку приоритетных пакетов. По сравнению с аналогами, НССК эффективнее восстанавливает данные при кодировании коротких информационных последовательностей, а также обеспечивает высокую эффективность восстановления пакетов от потерь при меньшем кодовом соотношении. Это позволяет снизить задержку данных в цепи «передатчик — приемник» и более экономно использовать канал передачи.

3. Предложена новая технология применения стирающих кодов в системах 1РТУ с целью повышения надежности передачи данных в системе, не имеющая известных аналогов. Отличительной чертой данной технологии является использование НССК на уровне транспортного потока МРЕО-2, что обуславливает возможность применения НССК для уменьшения потерь пакетов в системах 1РТУ без модификации сетевого оборудования и стека протоколов

Р, а также совместимость с программно-аппратными компонентами систем 1РТУ.

Практическая ценность:

1. Программно реализованы алгоритмы кодирования и декодирования кодов ЛТ и НССК, позволяющие восстанавливать пакеты в случае потерь при передаче.

2. Реализована программа ЕгазигеЗЬпиШог для имитационного моделирования стирающих кодов, предназначенная для исследования характеристик стирающих кодов. Программа позволяет оценивать влияние кодовых параметров на эффективность восстановления пакетов стирающими кодами, моделировать каналы с различными условиями передачи (соотношением потерь пакетов), подбирать оптимальные сочетания кодовых параметров для заданных условий передачи и ограничений на длину исходной информационной последовательности.

3. Преимуществами предлагаемой архитектуры являются совместимость с существующими программно-аппаратными компонентами систем 1РТУ (компрессорами, мультиплексорами), а также протоколами стека 1Р.

4. Реализован программный мультиплексор транспортного потока МРЕС-2 в виде Г>/г? фильтра для объединения и синхронизации цифровых видео и аудио потоков в соответствии со стандартом ШО 13 818−1. Мультиплексор осуществляет анализ структуры мультимедиа потоков и ранжирование транспортных пакетов, для дальнейшей передачи этой информации кодеру НССК. Мультиплексор пригоден для использования в профессиональных системах цифрового телевещания {1РТУ, ИУБ) в режиме реального времени.

Основные положения, выносимые на защиту:

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

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

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

Внедрение результатов:

Программный мультиплексор транспортного потока MPEG-2, разработанный и реализованный в рамках данной диссертационной работы, внедрен и используется в качестве коммерческого продукта «MainConcept MPEG Multiplexer» компанией MainConcept GmbH, что подтверждается актом о внедрении.

С докладом на тему «Стирающие помехоустойчивые коды для коррекции ошибок в системах цифрового телевещания» автор занял 1-е место в номинации «За научные результаты, обладающие существенной новизной и среднесрочной (до 5−7 лет) перспективой их эффективной коммерциализации» в рамках Программы «Участник молодежного научно-инновационного конкурса» (У.М.Н.И.К.).

Апробация работы. Основные положения работы докладывались на следующих конференциях и семинарах:

• Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Научная сессия ТУ СУР — 2005», — Томск, 2005.

• XLIII Международная научная студенческая конференция «Студент и научно-технический прогресс», Новосибирский государственный университет (НГУ), 2005.

• Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Научная сессия ТУ СУР — 2007», — Томск, 2007.

• Четвертая Международная научно-практическая конференция «Электронные системы и средства управления», — Томск, 2007.

• 11й1 IEEE Workshop on «Design and Diagnostics of Electronic Circuits and Systems» (DDECS'08), Bratislava, Slovak Republic, 2008. (Международный симпозиум IEEE «Разработка и диагностика электронных устройств и систем», -Братислава, Словакия, 2008.)

• 15-я Всероссийская межвузовская конференция «Микроэлектроника и информатика-2008», — Московский институт электронной техники (МИЭТ), Москва. Доклад отмечен дипломом 1 -й степени.

• Научно-практическая конференция «Электронные системы и средства управления», — Томск, ТУ СУР, 2008. Доклад занял 1-е место в рамках Программы «Участник молодежного научно-инновационного конкурса» (У.М.Н.И.К.).

Публикации. По теме исследования автором опубликованы 12 работ, в том числе 3 статьи в научных периодических журналах, из них 1 в журналах перечня ВАК [6], 2 работы опубликована в зарубежных изданиях, в том числе одна в сборнике докладов международного симпозиумов IEEE [9], 6 докладов опубликованы в материалах научных конференций и семинаров. Программа ErasureSimulator зарегистрирована в Отраслевом фонде алгоритмов и программ (ОФАП).

1. Шинкаренко К. В. Статистическое мультиплексирование MPEG-2 видеопотоков с переменным битрейтом для эффективного использования канала передачи данных // Информационные системы. — Томск, 2004. — С. 123 — 129.

2. Шинкаренко К. В. Однопроходный режим компрессии видеоданных // Доклады ТУСУРа. — Томск, 2005. — Т. 11. — № 3. — С. 110 — 114.

3. Шинкаренко К. В. Статистическое мультиплексирование видеопотоков с переменной скоростью передачи данных для эффективного использования канала связи // Материалы XLIII науч. студенч. конф. «Студент и научно-технический прогресс»: Информационные технологии. — Новосибирск, 2005. -С. 52.

4. Шинкаренко К. Алгоритм мультиплексирования транспортного потока MPEG-2 // Сб. науч. докл. конференции «Сибресурс-12−2006»). — Тюмень, 2006. -С. 90−94.

5. Шинкаренко К. Коррекция ошибок в системах цифрового мультимедиавещания // Материалы докладов Всероссийской науч.-техн. конф. студентов, аспирантов и молодых ученых «Научная сессия ТУСУР-2007». -Томск, 2007. — С. 189 — 192.

6. Кориков A.M., Шинкаренко К. Критерии оптимизации помехоустойчивых кодов для цифрового телевещания //Вычислительные технологии. — Томск, 2007.-Т. 12.-№ 1.-С. 86−95.

7. Шинкаренко К., Кориков A.M., Оптимизация помехоустойчивого кодирования для цифрового телевещания // Сб. науч. докл. Международной науч.-практ. конф. «Электронные системы и средства управления». — Томск, 2007.-С. 91 -94.

8. Shinkarenko К., Vlcek К. Architecture of Channel Coding Effectiveness Estimation System (Архитектура системы оценки эффективности помехоустойчивого кодирования) // In Proc. of 6th Electronic Circuits and Systems Conference. — Bratislava, 2007. — P. 165 — 169.

9. Shinkarenko K., Vlcek K. Design of Erasure Codes for Digital Multimedia Transmitting (Разработка стирающих кодов для передачи цифрового мультимедиа) // In Proc. of llth IEEE Workshop on Design and Diagnostic of Electronic Circuits and Systems (DDECS08). — Bratislava, 2008. — P. 30 — 34.

Доступен также: [Электронный ресурс]. — Режим доступа: — http://ieeexplore.ieee.org/Xplore/login.jsp?url=/stamp/stamp.jsp?arnumber=4 538 751 &isnumber=4 538 735. — 11.11.2008.

Ю.Шинкаренко К. Применение стирающих кодов в системах цифрового телевещания // Сб. науч. докл. 15-й Всероссийской науч.-техн. конф. «Микроэлектроника и информатика-2008». — Москва, 2008. — С. 248.

11 .Шинкаренко К. Стирающие помехоустойчивые коды для коррекции ошибок в системах цифрового телевещания // Сб. науч. докл. Науч.-практ. Конф. «Электронные системы и средства управления-2008», — Томск, 2008. — С.181 — 188.

12.Шинкаренко К. В. Программа моделирования помехоустойчивого кодирования стирающими кодами ErasureSimulator // Отраслевой фонд алгоритмов и программ. Свидетельство об отраслевой регистрации разработки № 11 720. Номер государственной регистрации: 50 200 802 200.-2008.

Личный вклад. Основные результаты и положения, выносимые на защиту, выполнены автором лично. Предлагаемые помехоустойчивые коды, технология их применения в IPTV, программная реализация кодов ЛТ и НССК и алгоритмов декодирования, а также программа ErasureSimulator для моделирования работы стирающих кодов, разработаны автором лично. Автором лично проведено моделирование работы стирающих кодов JIT и НССК при помощи программы ErasureSimulator с целью получения экспериментальных результатов. Научный руководитель принимал участие в постановке целей и задач исследований, обсуждении полученных результатов.

Благодарности. Автор выражает глубокую благодарность научному руководителю Корикову А. М. за помощь в работе над диссертацией, статьями, решении организационных вопросов, и научный опыт, переданный в процессе совместной деятельности.

Автор признателен коллегам из компаний ЗАО «Элекард» и MainConcept GmbH, Ковлягину В., Сергееву С. Н., Милякову А.

Кроме того, хотелось бы поблагодарить профессора К. Влчека из университета Томаша Бати, г. Злин, Чехия, в котором автор проходил стажировку, за ценный практический опыт работы с профессиональными системами цифрового телевещания и организацию моего участия в международных симпозиумах IEEE.

Основные результаты диссертации состоят в следующем:

1. Исследованы современные подходы к реализации систем IPTV: стандарты компрессии и транспортировки цифровых мультимедиа данных, сетевые протоколы, используемые для передачи по сетям IP, общие вопросы проектирования архитектуры систем IPTV. По итогам исследования выявлены актуальные для IPTV проблемы потерь при передаче данных, выяснены причины их происхождения, и сформулированы задачи, подлежащие решению для уменьшения количества потерь пакетов в системах IPTV. Для решения данной задачи возникла необходимость поиска соответствующего помехоустойчивого кода.

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

3. Обоснована перспективность использования в системах IPTV стирающих кодов. Объектом исследования были выбраны стирающие коды Лаби Трансформ, как наиболее идейно целостные из известных аналогов стирающие коды. Были программно реализованы кодер и декодер ЛТ, создана программа ErasureSimidator для оценки эффективности работы стирающих кодов на модели стирающего канала. Анализ свойств кодов ЛТ показал, что коды ЛТ обладают недостатками, осложняющими их применимость к решению поставленных задач, что было подтверждено экспериментально.

4. Доказана необходимость разработки новых стирающих кодов, которые бы наиболее полно учитывали специфику систем 1РТУ и структуру мультимедиа потоков.

В этой связи были разработаны новые неслучайные стирающие коды — т.н. «неслучайные стирающие коды», НССК. В отличии от известных аналогов, коды НССК обеспечивают высокую эффективность восстановления на малых длинах исходных информационных последовательностей, что обуславливает возможность их применения в системах 1РТУ. Кроме того, коды НССК используют детерминированный алгоритм выбора степеней кодовых символов на основе экспериментально полученной таблицы полиномиальных функций, что позволяет достигать большей эффективности исправления стираний по сравнению с известными аналогами. В ходе работы была создана экспериментальная реализация кодов НССК. Результаты моделирования, полученные с помощью программы Ега8иге8тиШог, показали, что разработанные коды обладают высокой эффективностью исправления стираний.

5. Выполнена концептуальная проектировка архитектуры системы телевещания по компьютерным сетям с использованием кода НССК. Архитектура обладает высокой универсальностью в плане взаимодействия со сторонними компонентами, и разработана в рамках существующих современных систем потокового телевещания.

6. Экспериментально проведена оценка вычислительной сложности кодирования НССК. Полученные результаты показали, что требования к ресурсам для осуществления операций кодирования и декодирования НССК не являются критичными для современных компьютеров.

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

Разработанный и реализованный в рамках данной диссертационной работы программный .О/гесйЭДом/ мультиплексор транспортного потока МРЕО-2 внедрен и используется в качестве коммерческого продукта

MainConcept MPEG Multiplexer" компанией MainConcept GmbH, что подтверждается актом о внедрении.

Заключение

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