Завадостійке кодування мультимедіа даних в комп'ютерних мережах

Размещено на http://www.allbest.ru/

Військовий інституту телекомунікацій та інформатизації

ЗАВАДОСТІЙКЕ КОДУВАННЯ МУЛЬТИМЕДІА ДАНИХ В КОМП'ЮТЕРНИХ МЕРЕЖАХ

Коротков М.М., Стрюк О.Ю., Сидоркін П.Г.,

Терещенко В.І., Очіченко Р.А.

Мультимедіа дані, як і будь-які інші повідомлення, що передаються в комп'ютерних мережах, представляють собою файли кінцевого розміру. Файли пересилаються по мережі послідовністю пакетів, розмір яких визначається стандартами і існуючими архітекторами мережі. Бажано, щоб одержувач прийняв кожен з пакетів без помилок. Однак частина пакетів може бути доставлена одержувачу з помилковими битами, а частина - втрачена в мережі. Такі пакети в теорії перешкодостійкого кодування вважають стертими, а в якості базової математичної моделі для опису каналу з перешкодами в комп'ютерних мережах використовуються модель каналу з стирання (erasure channel) пакетів. Для виявлення одержувачем помилок в пакетах відправник використовує код.

Для будь-якого коду існує ймовірність того, що помилку не буде виявлена. Помилка не буде виявлена в разі, якщо передане кодове слово було перетворено в каналі в інше кодове слово. Це перетворення прийнято називати трансформацій кодових слів. У моделі каналу зі стиранням нехтують ймовірністю помилково прийнятого пакета, обумовленої трансформацією кодових слів. Для більшості мережевих приложеній (IР-мовлення, IР Multicas-сервіс, одночасна передача даних з декількох сайтів в Інтернет і т.д.) Така зневага виправдано надзвичайно малою вірогідністю трансформації. Кожне мережеве застосування має свою специфіку, і в даній статті в якості мережевого додатку розглядається IР телемовлення.

Нові способи доставки даних і архітектури систем телемовлення по мережах IР (далі коротко IРТV, Internet Protocol Television) породили принципово нові труднощі. Однією з найбільш гострих і актуальних проблем є проблема втрат пакетів даних в системах IРТV реального часу, або «живого» мовлення. Втрати даних ведуть до деградації якості сприйняття телепрограм: втрати звуку, розсипання зображення на дратівливі «квадратики», десинхронизації звуку та зображення. Сутність проблеми в тому, що для «живого» телемовлення доводиться використовувати протоколи IР з негарантованої доставкою пакетів, такі як UDP (User Datagram Protocol), RTP (Real Time Protocol), оскільки повторна передача пакетів ( так звана схема ARQ, Automatic Repeat reQuest) неможлива через великі затримок на дану операцію, неприпустимих при «живому» телемовленні. Крім того, запити на пересилку, особливо в топології «один - багатьом», приведуть до додаткових навантажень на канал зв'язку і, можливо, подальшої деградації сервісу. Втрати пакетів в негарантованих протоколах відбуваються через колізії, затримок в мережах, «просідання» пропускної здатності каналів і т.п.

Відзначимо, що класичні перешкодостійкі коди не здатні вирішити названу проблему. Згорткові коди виправляють окремі бітові помилки. Блокові коди, в тому числі коди Рида Соломона, здатні виправляти пачки помилок в окремо взятому пакеті. Але в разі втрати пакета цілком вони безсилі.

В даний час можна говорити про створення нового класу перешкодостійких кодів для каналів зі стиранням - стирають кодів. Кодами з цього класу можна закодувати повідомлення кінцевого розміру потенційно необмеженим потоком незалежних пакетів. Це властивість нового класу кодів принципово відрізняє його від класичних блокових або загортальних, перешкодостійких кодів із заданою швидкістю (fixed rate). Для кодів з нового класу з'явився термін «rateless» (нефіксованим швидкості). Їх називають також фонтанними кодами (Digital Fountain Codes). Історично першим і найбільш ідейно цікавим га rateless кодом вважається LT код. Код був створений М. Лаби (Michael Luby) в 2002 р і найбільш докладно описаний в [1]. Свою назву він отримав від «Luby Transform» (Лаби Трансформ, ЛТ).

Найважливішою відмінністю стирають кодів від блокових і сверточних кодів є можливість відновлення цілого пакета в разі його втрати. В даний час стирають коди вже знайшли застосування в комерційних продуктах для комп'ютерних мереж, що поставляються, наприклад, компанією Digital Fountain.

Аналіз наявних на даний момент джерел показав, що є лише поодинокі спроби застосування стирають кодів IРТV [2]. Розмовляти про більш-менш цілісної технології IРТV із застосуванням стирають кодів поки не доводитися. Можна виділити лише стандарт мобільного телемовлення DVB-H (Digital Video Broadcasting Handheld) [3], який має на увазі використані стирають кодів Raptor [4], розроблених на основі кодів ЛТ з урахуванням специфіки мобільного телемовлення.

Дана стаття присвячена аналізу можливості застосування стирають кодів в системах IРТV. У статті пропонуються нові перешкодостійкі стираючи коди для зменшення втрат мультимедіа даних в IР телемовленні.

Принципи побудови стирають кодів. Коди ЛТ.

Припустимо, що ми маємо вихідне повідомлення, що складається з К вихідних символів, або пакетів. Довжини всіх символів еквівалентні і рівні L. Кодові символи в пральних кодах генерується як результат операції «виключне або» (XOR) над d вихідними символами. Величину d називають ступенем кодового символу. Дана величина може приймати значення від 1 до деякого максимального значення G.

Вихідні символи, використані для генерації деякого кодового символу i, будемо назвати сусідами (neighbors) [1].

Введемо також розподіл ймовірностей степенем p(d): p(d) є ймовірність того, що кодовий символ матиме ступінь d. Розподіл ступенів може бути задано як аналітично, так і табличному вигляді набору значень р (1), р (2),..., p(G-1), p(G). стирач код мультимедіа перешкодостійкий

Далі наведено опис процесу генерації кодових символів для коду ЛТ згідно [1] в нашому перекладі:

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

* вибрати випадковим чином d різних вихідних символів в якості сусідів кодового символу;

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

Виникає питання, скільки кодових символів необхідно згенерувати для відновлення вихідного повідомлення. Оскільки кодові символи є незалежними один від одного, то потенційно процес генерації може тривати як завгодно довго до тих пір, поки всі користувачі не отримають достатньої кількості кодових символів для відновлення вихідного повідомлення повністю. У цьому полягає «фонтанне» властивість ЛТ кодів. Приклад породжує графа ЛТ коду показна на рис. 1.

Теоретично для успішного відновлення всіх символів вихідного повідомлення повинно вистачити W=K.ln(R/) кодових символів, причому 1- є ймовірність успішного відновлення всіх вихідних символів, К - кількість вихідних символів [4].

Рис. 1 Приклад породжує графа ЛТ коду

Наведемо алгоритм декодування ЛТ кодів [1] в нашій інтерпретації.

Черга всіх отриманих приймачем кодових символів позначимо через ОКС. Введемо поняття ООС - черги оброблюваних символів, ступінь яких дорівнює 1 на деякій ітерації декодування. Черга декодованих, або, коректніше, відновлених символів назвемо ОВС.

Спочатку ОВС порожня. Серед ОКС знаходимо всі символи зі ступенем 1 і переміщаємо їх в ООС. Далі ітеративна обробляємо кожен і-й символ в ООС (ООСі), виробляючи такі дії:

* відновлюємо вихідний символ, який є єдиним «сусідом» для ООС [в належний символ в ОВС, т.е. копіюємо вміст ОВСі символу в належний вихідний символ ОВСk;

* знаходимо серед кодових символів в ООС символи, в які і-й символ входить в якості сусіда. Виробляємо операцію XOR над змістом знайденого символу в ОКС (позначимо його ОКСі) і поточним і-м символом, зменшуємо степінь ОКСj на 1.

* якщо ступінь ОКСj стала дорівнювати 1, і такого символу немає ні в ОВС, ні в ООС, то переміщаємо ОКСj в ООС.

* видаляємо ООСі з ООС.

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

Щоб запобігти невдалу ситуацію, необхідно належним чином розробити розподіл ступенів кодових символів. Це є найважливішим завданням в проектуванні стирають кодів. Для ЛТ кодів М. Лаби запропонував Robust Soliton Distribution - робастний розподіл [1, 4].

Робастний розподіл µ(d) задається формулою:

Размещено на http://www.allbest.ru/