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

На правах рукописи

003458014

Шинкаренко Константин Всеволодович

АЛГОРИТМЫ И ПРОГРАММНЫЕ СРЕДСТВА ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ МУЛЬТИМЕДИА ПОТОКОВ В КОМПЬЮТЕРНЫХ СЕТЯХ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание учёной степени кандидата технических наук

1 5 ЛЕН 2008

Томск-2008

003458014

Работа выполнена в ГОУ ВПО "Томский государственный университет систем управления и радиоэлектроники (ТУСУР)".

Научный руководитель:

заслуженный деятель науки РФ, доктор технических наук, профессор Кориков Анатолий Михайлович

Официальные оппоненты:

доктор технических наук, профессор Спицын Владимир Григорьевич

Ведущая организация:

доктор технических наук, старший научный сотрудник Протасов Константин Тихонович

Новосибирский государственный технический университет

Защита состоится «29» декабря 2008 г. в 1422 часов на заседании совета по защите докторских и кандидатских диссертаций Д 212.269.06 при Томском политехническом университете по адресу: 634034, г. Томск, ул. Советская, 84, институт «Кибернетический центр» ТПУ.

С диссертацией можно ознакомиться в библиотеке Томского политехнического университета по адресу: 634034, г. Томск, ул. Белинского, 55.

Автореферат разослан «28» ноября 2008 г.

Ученый секретарь Совета к.т.н., доцент

Сонькин М.А.

Общая характеристика работы

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

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

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

В наши дни в сфере технологий цифрового телевидения происходят значительные изменения. Все большее количество телезрителей предпочитают пользоваться услугами IPTV для просмотра телепередач. По сравнению с системами спутникового и наземного цифрового телевещания, IPTV предлагает телезрителю ряд удобств, таких как «видео по запросу», пауза в трансляции и последующий просмотр с места остановки, «виртуальный видеомагнитофон» (запись передачи, идущей в определенное время) и т.д. В 2005 году количество пользователей IPTV составляло 200 млн человек, и ожидается, что их количество увеличится до 400 млн человек в 2010 году.

Сети 1Р являются сетями пакетной передачи данных. Одной из наиболее острых актуальных проблем в 1РТУ является проблема потерь пакетов мультимедиа данных при потоковом телевещании, т.е. телевещании в режиме реального времени. Для потокового телевещания по сетям 1Р используются протоколы стека 1Р с негарантированной доставкой: ¿/ДР, ЯТР. Использование данных протоколов обусловлено необходимостью доставки пакетов с как можно меньшей задержкой, для плавного воспроизведения видео и звука. Однако, из-за перегрузок коммутаторов, задержек и помех в сетях 1Р происходят потери пакетов, причем теряется пакет целиком. Такой тип ошибки называют «стиранием». Потери пакетов в 1РТУ ведут к деградации качества восприятия видео, частичной или полной пропаже звука.

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

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

Разработка помехоустойчивых кодов для систем 1РТУ осложнена тем, что код должен отвечать сразу нескольким требованиям, подчас взаимоисключающим и требующим нахождения компромисса:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Реализован программный мультиплексор транспортного потока МРЕС-2 в виде В1гес1Бком> фильтра для объединения и синхронизации цифровых видео и аудио потоков в соответствии со стандартом 1БО 13818-1. Мультиплексор осуществляет анализ структуры мультимедиа потоков и ранжирование транспортных пакетов, для дальнейшей передачи этой информации кодеру НССК. Мультиплексор пригоден для использования в профессиональных системах цифрового телевещания (/Р7У, ЭУВ) в режиме реального времени.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложений. Материал изложен на 142 страницах, содержит 13 таблиц, 31 рисунок и 2 приложения. Список цитируемой литературы содержит 93 наименования.

Содержание работы

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

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

В данной главе изложены принципы компрессии цифровых видео и аудио данных, исследуется структура элементарных цифровых мультимедиа потоков, структура транспортного потока MPEG-2 ISO.

Основными стандартами компрессии мультимедиа данных, используемыми в современных системах потокового телевещания,

являются стандарты сжатия видео Н.264 и MPEG-2, стандарты аудио компрессии ЛАС, MPEG Audio.

Рассмотрены современные системы наземного и спутникового ЦТВ, исследованы помехоустойчивые коды, применяемые в этих системах: коды Рида-Соломона, сверточные коды, Турбо-коды. Сделан вывод о непригодности применения классических блоковых и сверточных кодов для решения проблемы потерь пакетов целиком, имеющей место быть в системах IPTV.

В диссертации рассматриваются современные подходы к реализации систем IPTV, сделан обзор протоколов стека IP, представляющих интерес в контексте данной работы

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

Коды ЛТ строятся следующим образом. Допустим, исходное сообщение состоит из К символов. В качестве символа может выступать сетевой пакет данных, либо транспортный пакет MPEG-2 ISO, - требуется лишь, чтобы все пакеты имели равную длину. Кодовые символы в стирающих кодах генерируются как результат операции «исключающее или» (XOR) над d исходными символами. Величину d называют степенью кодового символа. Данная величина может принимать значения от 1 до некоторого максимального значения G. Исходные символы, использованные для генерации некоторого кодового символа i, будем называть «соседями» (neighbors).

Введем также понятие плотности распределения степени кодовых символов p(d): p(d) есть вероятность того, что кодовый символ будет иметь степень d.

Процесс генерации кодовых символов для кода ЛТ состоит в следующем:

• случайным образом выбрать степень d кодового символа, используя плотность распределения p(d);

• выбрать случайным образом d различных исходных символов в качестве соседей кодового символа;

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

Описание алгоритма декодирования кода ЛТ приведено в диссертации.

Важнейшей задачей в проектировании стирающих кодов является разработка распределения степеней кодовых символов. Для кодов J1T зарубежными учеными было предложено робастное распределение для степени кодовых символов (Robust Soliton Distribution). Исходя из соображений удобства практической реализации кодов, для задания закона распределения степени кодовых символов используется функция плотности распределения.

Плотность робастного распределения /¡(d') задается формулой:

M(d)=r(d)+T(d) . (О

jrP(d) + T(d)

где

С MK,d = \ T(d) =

l</(d-l)

л d

I-log (S/5),d = K/S К

0 ,d>KIS

В последней формуле S определяется выражением S(K,S) = c\n(K/S)jK

Параметрами функции плотности робастного распределения являются: К - количество исходных символов; с - параметр распределения; рекомендуется задавать 0 < с < 1; <5 - параметр, определяющий вероятность успешного декодирования; процесс декодирования будет успешно завершен с вероятностью 1-<5.

С целью изучения возможностей восстановления пакетов кодом JIT были программно реализованы кодер - декодер JIT и проведено имитационное моделирование работы кодов на наборе значений кодовых параметров с, <5, К, а также при различных значениях интенсивности потерь пакетов. Результаты моделирования приведены в третьей главе.

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

На основе анализа вероятности восстановления исходных символов при кодировании кодом ЛТ в диссертации сформулированы следующие проблемы применения кодов ЛТ в системах 1PTV: • неприемлемо длительная задержка ТВ сигнала между приемником и передатчиком, вызванная необходимостью буферизации большого числа исходных пакетов, поскольку эффективность ЛТ

начинает проявляться только для большого числа исходных символов, порядка 5000 - 10000. Это свойство ЛТ кодов подтверждается экспериментально;

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

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

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

Количество кодовых пакетов для НССК потенциально может быть неограниченным, но для моделирования использовалось ограничение конкретной величиной N. Величина N определяется исходя из максимально дозволенного переизбытка кодовых пакетов относительно числа К исходных символов как N = К ■ р, где /3 немногим более 1 (задается программно либо по усмотрению пользователя, исходя из ограничений, накладываемых приложением).

Для определения количества пакетов с той или иной степенью код НССК использует робастное распределение //(¿) (1). Однако, распределение модифицировано путем введения дополнительных проверочных пакетов для опорных пакетов. Обозначим модифицированное распределение Дня определения степеней

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

восстановления от степени кодового пакета имеет максимум, т.е. находится значение Ц при котором производная аппроксимирующего полинома обращается в 0. Полученное таким образом значение D масштабируется на число кодовых пакетов со степенью ti[d¡], для которых генерируются проверочные пакеты. Обозначим данное значение D как Dr Количество пакетов с данной степенью определяется через допустимое количество избыточных пакетов V=N-Kкак 7

К

Очередь исходных символов обозначим кратко ОИС. Очередь кодовых символов назовем ОКС. Будем использовать индексы для обращения к символам в ОКС и ОИС. Количество вхождений /-го исходного символа в кодовые символы в качестве «соседа» назовем мерой защищенности исходного пакета. Обозначим меру защищенности переменной R[f],f= 0,..., К-1.

Ниже приведен алгоритм кодирования НССК.

Шаг 1. Определить количество кодовых символов, предназначенных для кодирования со степенями d0¡ .... dmax согласно n(d¡) = //(</,)-N, где N— целевое количество кодовых символов.

Шаг 2. Выбрать n[d0] исходных пакетов с наивысшим приоритетом. Закодировать их как опорные символы со степенью 1. Можно записать это действие на языке псевдо-Си как

for(i = 0; i < «[do]; i++)

{

OKCfl] = ouc[fj;

h

где/ обозначает индекс исходного символа из ОИС.

Шаг 3. Произвести кодирование всех символов, закодированных на шаге 1, согласно следующей процедуре:

for(i =0; i <Z0 ;i++) { r= rand(Rmin); R[r]++; OKC[i + n{do\] = ОИС[г]; for(h=0;h<D0;h++) {

r = rand(Rm¡n); R[r]++;

OKCfi + n[d0]] = О КС [i + n[do\] XOR OHCfr];

}

}

Шаг 4. Обозначим через WR подмножество всех исходных символов, обладающих на некотором шаге кодирования мерой защищенности R. Среди них подмножество символов с максимальной мерой защищенности обозначим как WMax, с минимальной - WMm.

Задать i = 2.

Шаг 4.1 Выполнять действия 4.1.1 и 4.1.2 n[di\ раз:

Шаг 4.1.1. Сгенерировать очередной к-й кодовый символ как результат операции XOR над одним символом из М'шх одним из

M'max-i ••■> одним из Wr.h и одним символом из WMM где L=MAX -d,

OKCfk] = WMAX[j„] XOR WMAX.,fj,] XOR... XOR WL.,[j,.i] XOR WMIN[j,J;

Шаг 4.1.2. Увеличить на единицу значения Л[/',] для всех у'„ t=0...L (здесь индексы ], являются индексами исходных пакетов в ОИС).

Шаг 4.2. Обновить подмножества WR, а также максимальное и минимальное значения R. Увеличить i на единицу.

Если i стало равным dmax+\, либо общее число кодовых символов достигло желаемого количества N, выход.

Если не все исходные пакеты хотя бы один раз вовлечены в процесс кодирования, перейти на Шаг 4.1. Иначе перейти на Шаг 5.

Шаг 5. т=/;

\vhile(k<N) {

for(v=0;v <Zm ;v++J { r= rand(n[dm]); R[r]++; OKCfk] = ОИС[г]; for(h=0;h< Dm,h++) {

r = rand(n[dm\); R[r]++; OKCfk] = OKCfk] XOR OHCfr];

}

}

k++;

Если все пакеты из n[dm] вовлечены в кодирование на данном

шаге, т++; }

Выход.

Отметим, что чем выше приоритет исходного пакета, выбираемого из WMIN, тем ниже должна быть степень кодового пакета, при которой он будет впервые вовлечен в кодирование.

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

при передаче. Количество пакетов, подлежащих стиранию, определялось параметром модели PLR (Packet Loss Ratio, отношение потерь пакетов). Индексы пакетов, подлежащих стиранию, определялись случайным образом, согласно равномерному распределению. Параметры кодов ЛТ и НССК с, д, К, N, а также параметр модели системы передачи данных PLR, варьировались в заданных пределах.

В качестве критерия оценки эффективности ЛТ и НССК в данном эксперименте используется процент успешно восстановленных декодером исходных пакетов. Достоверность эксперимента обеспечивается тем, что для каждого набора значений пяти вышеперечисленных параметров производились по 1000 запускам моделирования для кодов ЛТ и НССК, и проводилось усреднение полученных для каждого запуска значений процента восстановленных пакетов.

Эксперимент подтвердил, что коды ЛТ могут быть использованы в компьютерных сетях для исправления потерь пакетов, но характеристики ЛТ кодов не удовлетворяют требованиям, предъявляемым системами IPTVk помехоустойчивым кодам.

Коды ЛТ обеспечивают уверенное восстановление пакетов лишь при значениях К порядка 5000 - 10000, в то время как коды НССК эффективны, в том числе, при малых К порядка 100 - 1000, что очень важно с точки зрения возможностей применения стирающих кодов в системах IPTV. За счет детерминированной алгоритмической структуры коды НССК более надежны, нежели коды ЛТ, так как для ЛТ при превышении некоторого критического уровня PLR происходит резкое падение количества восстановленных пакетов (см. рис. 1). С помощью кодов ЛТ может быть достигнута столь же высокая эффективность восстановления данных от потерь, как с помощью НССК, но за счет большего избытка кодовых пакетов, что увеличит нагрузку на сеть передачи данных.

На рис. 1, 2 проиллюстрированы полученные экспериментально результаты работы кодов ЛТ и НССК соответственно. Столбцы гистограмм показывают процент восстановленных исходных пакетов. Значения параметров плотности робастного распределения вероятности одинаковы и равны с=0.05,5=0.05 для обоих кодов. Число исходных пакетов #=100... 10000, процент потерь пакетов PLR-0..A5. Избыток кодовых пакетов для иллюстрируемого примера равен 10% от числа исходных пакетов К.

Рис. 2. Процент успешно восстановленных пакетов для кода НССК В данной главе рассмотрены также вопросы практической реализации систем IPTV с использованием НССК. В качестве уровня интеграции с НССК был выбран транспортный поток MPEG-2 (MPEG-2 Transport Stream, MPEG-2 TS), в связи с тем, что фактически MPEG-2 TS является наиболее распространенным форматом, используемым в профессиональных системах IPTV во всем мире. Предлагаемая архитектура системы IPTV с использованием НССК приведена на рис. 3.

Рис. 3. Архитектура системы 1РТУс применением НССК

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

Транспортные пакеты содержат данные различных типов: служебные таблицы для демультиплексирования потока, аудиоданные, видео кадры различных типов (/, Р, В кадры). Помимо собственно кодера НССК, важной отличительной чертой предлагаемой архитектуры является наличие модуля ранжирования транспортных пакетов (рис. 3). Модуль ранжирования назначает приоритет 75 пакетам на основе вспомогательной информации о типе содержимого пакетов, обеспечиваемой модулем синтаксического разбора. Наивысший приоритет имеют пакеты с аудио данными и опорными (/кадрами) видео. Более низкий приоритет имеют Р-кадры видео. Низший приоритет назначается 2?-кадрам видео. Служебные таблицы используются для передачи декодерам параметров кодера. При кодировании НССК в качестве кодовых пакетов со степенью 1 выбираются пакеты с наивысшим приоритетом, для кодовых пакетов со степенью 2-е приоритетом 2, и т. д., до тех пор, пока все исходные пакеты не будут вовлечены в процесс кодирования, согласно алгоритму кодирования НССК. За счет этого ранжирование пакетов призвано повысить эффективность помехоустойчивого кодирования для уменьшения влияния потерь пакетов на качество телепрограмм в 1РТУ.

Перемежитель (рис. 3) отвечает за индексацию кодовых пакетов для восстановления приемником порядка их следования, а также за

перемежение кодовых пакетов с различными степенями во избежание потерь пачек кодовых пакетов со степенью 1.

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

В заключении перечислены основные результаты, полученные в диссертационной работе.

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

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

3. Реализована программа ЕгазигеБтиЫог для имитационного моделирования и исследования характеристик стирающих кодов. Программа позволяет оценивать влияние кодовых параметров на эффективность восстановления пакетов стирающими кодами ЛТ и НССК, моделировать каналы с различными условиями передачи, подбирать оптимальные сочетания кодовых параметров для заданных условий передачи и ограничений на длину исходной информационной последовательности.

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

5. Реализован программный мультиплексор транспортного потока MPEG-2 в виде DirectShow фильтра для объединения и синхронизации цифровых видео и аудио потоков в соответствии со стандартом ISO 13818-1. Мультиплексор осуществляет синтаксический анализ структуры мультимедиа потоков, для дальнейшей передачи этой информации кодеру НССК. Мультиплексор пригоден для использования в профессиональных системах цифрового телевещания (IPTV., DVB) в режиме реального времени.

В приложениях приведены список используемых сокращений и акт о внедрении.

Список работ, опубликованных по теме диссертации

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

2. Шинкаренко К.В. Однопроходный режим компрессии видеоданных // Доклады ТУСУРа. - Томск, 2005. - Т. И. - № 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 11th IEEE Workshop on Design and Diagnostic of Electronic Circuits and Systems (DDECS08). -Bratislava, 2008. - P. 30 - 34.

Доступен также: [Электронный ресурс]. - Режим доступа: -http://ieeexplore.ieee.org/XpIore/Iogin.jsp?ur[==/stamp/stamp.jsp?arnumber= 4538751&isnumber=4538735. - 11.11.2008.

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

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

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

ь*

Тираж 100. Заказ 1106. Томский государственный университет систем управления и радиоэлектроники. 634050, г. Томск, пр. Ленина, 40.

Введение.

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

1.1. Задача помехоустойчивого кодирования.

1.2. Цифровое телевидение: история развития и современное состояние.

1.3. Обзор литературных источников.

1.4. Принципы компрессии и структура потока цифровых мультимедиа данных.

1.4.1. Принципы компрессии видео.

1.4.2. Стандарт видео компрессии Н.264.

1.4.3. Принципы компрессии аудио.

1.4.4. Транспортный поток MPEG-2.

1.5. Современные подходы к реализации систем IPTV.

1.5.1. Протоколы RTP/RTCP.

1.5.2. Протокол UDP.

1.6. Классификация и характеристики помехоустойчивых кодов, применяемых в ЦТВ.

1.6.1. Блоковые коды.

1.6.2. Сверточные коды.

1.6.3. Турбо-коды.

1.7. Критерии оценки эффективности помехоустойчивого кодирования в системах IPTV.

Выводы по главе 1.

2. Стирающие коды и возможности их применения в системах IPTV.

2.1. Понятие стирания. Модели стирающего канала.

2.1.1. Модель двоичного стирающего канала.

2.1.2. Модель Гилберта для стирающего канала.

2.1.3. Модель канала с независимыми случайными стираниями.

2.2. Стирающие коды Лаби Трансформ (ЛТ). Алгоритм кодирования.

2.2.1. Алгоритм декодирования кодов ЛТ.

2.2.2. Идеальное распределение вероятности для степеней кодовых символов.

2.2.3. Робастное распределение вероятности для степеней кодовых символов.

2.3. Оценка вероятности восстановления пакетов при использовании ЛТ

2.4. Анализ возможностей применения кодов ЛТ в 1РТУ. Экспериментальная реализация кодов ЛТ.

2.5. Систематические стирающие коды (ССК).

Выводы по главе 2.

3. Разработка стирающих кодов для систем потокового цифрового телевещания по сетям/Р.

3.1. Неслучайные стирающие коды (НССК). Алгоритм кодирования.

3.1.1. Задание кода НССК с помощью порождающих матриц.

3.2. Экспериментальные результаты моделирования работы НССК.

3.3. Аспекты практического применения НССК в системах 1РТ¥.

3.3.1. Ранжирование пакетов в транспортном потоке МРЕС-2.

3.3.2. Восстановление исходного порядка пакетов при кодировании НССК транспортного потока МРЕС-2.

3.4. Оценка вычислительной сложности алгоритмов кодирования и декодирования ЛТ и НССК.

Выводы по главе

Актуальность темы. В настоящее время происходит бурное развитие компьютерных сетей и рост числа сетевых приложений, в том числе для передачи цифровых мультимедиа данных. Цифровое телевещание через Интернет, так называемое 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 в виде Г>/г£<?/57гс7и> фильтра для объединения и синхронизации цифровых видео и аудио потоков в соответствии со стандартом ШО 13818-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=4538751 &isnumber=4538735. - 11.11.2008.

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

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

12.Шинкаренко К.В. Программа моделирования помехоустойчивого кодирования стирающими кодами ErasureSimulator // Отраслевой фонд алгоритмов и программ. Свидетельство об отраслевой регистрации разработки № 11720. Номер государственной регистрации: 50200802200.-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, что подтверждается актом о внедрении.

135

Заключение

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

1. Артюшенко В.М., Шелухин О .И., Афонин М.Ю. Цифровое сжатие видеоинформации и звука. — М.: Дашков и Ко, 2003. — 426 с.

2. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. -М.:Мир, 1986. 576 с.

3. Бородин Л.Ф. Введение в теорию помехоустойчивого кодирования. Монография, 21.5 усл.п.л., М.: Советское радио, 1968 г.

4. Варшамов P.P. Оценка границ для кодов, корректирующих ошибки // Доклады Академии наук СССР. 1957.-Т.117.-№ 5.-С.89- 121.

5. Варгаузин В.А. Помехоустойчивое кодирование в пакетных сетях // ТелеМультиМедиа. -2005. -№ 3. ~ С.10 16.

6. Варгаузин В.А., Протопопов Л.Н. Турбо-коды и итеративное декодирование: принципы, свойства, применение // ТелеМультиМедиа. 2000. №34. - С.ЗЗ - 38.

7. Вентцель Е.С. Теория вероятностей: М.: «Наука», 1969. - 576 с.

8. Гнеденко Б.В. Курс теории вероятностей: Эдиториал УРСС, 2001. -320 с.

9. Зубарев Ю. Б., Золотарёв В.В., Жуков С. Е., Строков В.В., Овечкин Г.В. Многопороговые декодеры для высокоскоростных спутниковых каналов связи: новые перспективы // Электросвязь. 2005. — №2. С.10—12.

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

11. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

12. Питерсон У. Коды, исправляющие ошибки: Пер. с англ. под ред. Добрушина Р. М.: Мир, 1972. - 338 с.

13. Проакис Дж. Цифровая связь. М.: Радио и связь, 2000.

14. Рид И.С., Соломон Г. Полиномиальные коды над некоторыми конечными полями. В кн.: Кибернетический сборник. Вып. 7. — М., ИЛ, 1963, С. 74-79.

15. Финк Л.Н. Теория передачи дискретных сообщений. М.: Изд-во "Советское радио", 1970.

16. Форни Д. Каскадные коды. М.: Мир, 1970.

17. Шеннон К. Работы по теории информации и кибернетике. М:, ИЛ, 1963,-С. 243-332.

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

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

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

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

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

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

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

25. Шинкаренко К.В., Кориков A.M. Помехоустойчивое кодирование мультимедиа данных в компьютерных сетях // Известия Томского политехнического университета. 2008. - Т. 313. - № 5. — С.

26. Шинкаренко К.В., Кориков A.M. Применение неслучайных стирающих кодов в IP телевещании // Известия Томского политехнического университета. -2008. Т. 313. - № 5. - С.

27. Byers J., Luby M., and Mitzenmacher M. A digital foundation approach to asynchronous reliable multicast // IEEE J. Selected Areas Comm., V. 20, pp. 1528-1540, 2002.

28. Bahl L. R., J. Cocke, F. Jelinek, and J. Raviv. Optimal decoding of linear codes for minimizing symbol error rate, IEEE Trans. Inform. Theory 20(2): 248-287 (March 1974).

29. Berrou С., Glavieux A., and Thitimajshima P. Near Shannon limit error-correcting coding and decoding: Turbo codes // In Proc. of 1993 IEEE Int. Communications Conf. Geneva, 1993. - P. 1064-1070.

30. Bolot J.C. End-to-end packet delay and loss behavior in the Internet // In Proc. Of ACM Sigcomm'93. San Fransisco, CA. - P. 189-199.

31. Costello D. J., J. Hagenauer, et al. Applications of Error-Control Coding. IEEE Transactions on Information Theory, 1998. V. 44. — № 6 (October). -P.77-102.

32. Dholakia A. Convolutional codes. John Wiley & Sons, England, 2001, P.431.

33. Elias P., Coding for noisy channels, Proc. IRE Conv. Ree., 1955, part 4, P.37-46.

34. Furht B. A Survey of Multimedia Compression Techniques and Standards. Part II: Video Compression // Journal of Real-Time Imaging, Vol. 1, No. 5, November 1995, pp. 319-338.

35. Gray R.M. Entropy and Information Theory. Stanford University, SpringerVerlag, New York, 1990, P.284.

36. Gallager R. G. Low Density Parity Check Codes. M.I.T. Press, 1963, Monograph.

37. Hamming R.S. Error detecting and error correcting codes. Bell Syst. Tech. J., 1950.-V.29.-P. 147-160.

38. Hoffman D., G.Fernando, V. Goyal, M. Civanlar. RTP Payload Format for MPEG1/MPEG2 Video, RFC 2250, January 1998.

39. Hoffman D., Leonard D. et al. Coding Theory The Essentials: Marcel Dekker Inc, New York, 1992.

40. Luby M. LT Codes // Proc. of the 43rd Annual IEEE Symp. on Foundations of Computer Science (FOCS). 2002. - P. 271-282.

41. MacKay D.J.C., Information Theory, Inference, and Learning Algorithms. Электронный ресурс. — Режим доступа:http://www.inference.phy.cam.ac.uk/mackay/itila/book.html. 14.05.2008.

42. MacKay D.J.C. Fountain codes // IEE Proc.-Commun., 2005. V. 152. - № 6 (December). - P. 1062-1068.

43. Mathys P. Theory and Practice of Error Control Coding. Электронный ресурс. — Режим доступа: —http://www.colorado.edu/~ecen5682/index.html. 11.10.2007.

44. Maymounkov М. Online codes. Электронный ресурс. — Режим доступа: -http://www.csc.cs.nyu.edu/~petar/oncodes.pdf. 12.10.2007.

45. Mitzenmacher М. Digital Fountains: A Survey and Look Forward. — Information Theory Workshop 2004.

46. Pennebaker, W. В., J. I,. Mitchell, C. Fogg and D. McCall, MPEG Digital Video Compression Standard, Chapman & Hall, 1997.

47. Puri A. and Chen T. Multimedia Systems, Standards and Networks: Marcel Dekker, 2000.

48. Puducheri S., Kliewer J., Fuja Т. E. Distributed LT Codes. Department of Electrical Engineering, University of Notre Dame, Notre Dame, IN 46556, USA, 2006.

49. Rao, K. R. and 3. 5. Hwang, Techniques and Standards for Image, Video and Audio Coding, Prentice Hall, 1997. P. 382.

50. Richardson I. E. G. H.264 and MPEG-4 Video Compression. John Wiley & Sons, England, 2003. P.281.

51. Richardson I.E.G., Video Codec Design, John Wiley & Sons, 2002.

52. Shinkarenko K., Vlcek K. Architecture of Channel Coding Effectiveness Estimation System // In Proc. of 6th Electronic Circuits and Systems Conference. Bratislava, 2007. - P. 165 - 169.

53. Shinkarenko K., Vlcek K. Design of Erasure Codes for Digital Multimedia Transmitting // In Proc. of 11th IEEE Workshop on Design and Diagnostic of Electronic Circuits and Systems (DDECS08). Bratislava, 2008. - P. 30 - 34.

54. Shokrollahi A. Raptor codes // IEEE/ACM Trans. Networking (TON). 2006. -V. 14.-P. 2551-2567.

55. Viterbi J., Error bounds for convolutional codes and an asymptotically optimal decoding algorithm, IEEE Trans. Inform. Theory 13. 1967, — P. 260-269.

56. Viterbi A.J. An Intuitive Justification and a Simplifed Implementation of the MAP Decoder for Convolution Codes, IEEE Journal On Selected Areas In Communications, 2003. — V.16. №.2.

57. Vlchek K., Advanced Error-Control Coding Methods Enhance Reliability of Transmission and Storage Data Systems, RADIOENGINEERING, 2003. -V.12. -№. l.-P.

58. Wesel R. D., Convolutional Codes. University of California at Los Angeles, California. Wiley Encyclopedia of Telecommunications, 1993.

59. Wicker S. В., Error control systems for digital communication and storage. 1995.

60. Wbatckinson J., The engineers Guide to Compression, Snill and Wilcox Handbook Series, 2003.

61. Wozencraft J. M. Sequential decoding for reliable communication, Proc. IRE Conv. Rec. part 2, 1957. - P. 11-25.

62. Yajnik M., Kurose J., Towsley D. Packet Loss Correlation in the MBone Multicast Network: ExperimentalMeasurements and Markov ChainModel //

63. Yeung R. W., A first course in information theory. Kluwer Academic/Plenum Publishers, 2002.

64. Yun Q. Shi, Huifang Sun. Image and Video Compression for Multimedia Engineering: Fundamentals, Algorithms and Standards. New York, CRC Press, 1999, 463 c.

65. Телемультимедиа.ру. Электронный ресурс. Режим доступа: — www.telemultimedia.ru. - 19.07.2008.

66. Gartner 2007 Press-releases. Электронный ресурс. Режим доступа: http://www.gartner.com/it/page.jsp?id=501276. - 25.09.08.

67. Новостной портал «Лента.ру». Электронный ресурс. Режим доступа: - http://www.lenta.ru/news/2006/04/06/digitaltv/. - 04.06.2006.

68. ETSI EN 300 421 VI. 1.2: Digital Video Broadcasting (DVB); Framing structure, channel coding and modulation for 11/12 GHz satellite services, (1997-08).

69. ETSI TR 102 033, Digital Video Broadcasting (DVB); Architectural Framework for the Delivery of DVB services Over IP-based Networks, April 2002.

70. ISO/IEC 11172-1 : Information technology Coding of moving pictures and associated audio for digital storage media at up to about 1,5 Mbit/s - Part 1 : Systems. - 1993.

71. ISO/IEC 11172-2: Information technology Coding of moving pictures and associated audio for digital storage media at up to about 1,5 Mbit/s - Part 2: Video. - 1993.

72. ISO/IEC 13818-1: Information technology Generic coding of moving pictures and associated audio information: Systems. Третье издание, 2007.

73. ISO/IEC 13818-2: Information technology Generic coding of moving pictures and associated audio information: Video. - 2000.

74. ISO/IEC 13818-3: Information technology Generic coding of moving pictures and associated audio information: Audio. — 2000.

75. ISO/IEC 13818-7:2003. Information technology Generic coding of moving pictures and associated audio information — Part 7: Advanced Audio Coding (AAC).- 1997.

76. ISO/IEC 14496-2: Information technology Coding of audio-visual objects -Part 2: Visual. -2001.

77. ISO/IEC 14496-4: Information technology Coding of audio-visual objects -Part 4: Advanced Audio Coding. - 2001.

78. ISO/IEC 14496-10: Information technology Coding of audio-visual objects -- Part 10: Advanced Video Coding. - 2005.

79. ISO/IEC 15938, Information technology multimedia content description interface (MPEG-7). - 2002.

80. IETF RFC 3550: RTP: A Transport Protocol for Real-Time Applications. -2003.

81. IETF RFC 3559: Multicast Address Allocation MIB. 2003.

82. IETF RFC 3640: RTP Payload Format for Transport of MPEG-4 Elementary Streams. 2003.

83. IETF RFC 3605: Real Time Control Protocol (RTCP) attribute in Session Description Protocol (SDP). 2003.

84. ITU-R Draft new Recommendation ITU-R BS. 10/20., Method for objective measurements of perceived audio quality. 1998.

85. ITU-T H.263. Video coding for low bit rate communication. 2005.

86. ITU-T Recommendation J. 143. User requirements for objective perceptual video quality measurements in digital cable television. 2000.

87. RFC 768. User Datagram Protocol. 1980.

88. SCTE 42 2002, IP Multicast for Digital MPEG Networks. 2002.

89. Компрессия.ру. Электронный ресурс. Режим доступа: -www.compression.ru. - 06.11.2008.