Фонтанні коди

Сьогодні поговоримо про фонтанних коди. Їх ще називають «кодами нефіксованим швидкості». Фонтанний код дозволяє взяти, наприклад, який-небудь файл, і перетворити його в практично необмежену кількість закодованих блоків. Маючи деяку підмножину цих блоків, можна відновити вихідний файл, за умови, що розмір цієї підмножини трохи перевищує розмір файлу. Іншими словами, такий код дозволяє створювати «фонтан» з кодованих даних. Одержувач може відновити вихідні дані, зібравши достатньо «крапель» з фонтану, при цьому неважливо – які саме «краплі» у нього є, і які саме він пропустив.


Чудове властивість фонтанних кодів полягає в тому, що їх застосування дозволяє відправляти дані по ненадійним каналах зв'язку, наприклад, через інтернет, не покладаючись на знання рівня втрати пакетів, і не вимагаючи від одержувача зв'язуватися з відправником для відновлення відсутніх фрагментів даних. Легко помітити, що подібні можливості виявляться вельми до речі в безлічі ситуацій. Серед них, наприклад, відправлення інформації по широкомовним каналах зв'язку, як в системах передачі відео за запитом. До тієї ж категорії завдань відноситься робота протоколу Bittorrent і інших подібних, коли фрагменти файлу поширюються серед великої кількості бенкетів.

Основні принципи
Може здатися, що фонтанні коди повинні бути влаштовані жахливо складно. Але це зовсім не так. Існують різні реалізації цього алгоритму, ми пропонуємо почати з найпростішою з них. Це – так званий код перетворення Лаби, скорочено його зазвичай називають LT-кодом, від Luby Transform Сode. При використанні цього варіанта фонтанних кодів блоки кодують так:

  1. Вибирають з діапазону 1 — k випадкове число d. Діапазон відповідає кількості блоків у файлі. Нижче ми поговоримо про те, як найкраще обрати d.

  2. Вибирають випадковим чином d блоків файлу і комбінують їх. В нашому випадку добре підійде операція XOR.

  3. Передають отриманий на попередньому кроці блок разом з інформацією про те, з яких блоків він був створений.
Як бачите, тут немає нічого складного. Але треба відзначити, що багато чого в цій схемі залежить від так званого розподілу ступенів кодових символів, від того, як вибирають кількість блоків, які треба скомбінувати. До цього питання ми ще повернемося. З опису можна помітити, що деякі з закодованих блоків, фактично, створені з використанням лише одного блоку вихідних даних, в той час як в кодуванні більшості блоків задіяні кілька вихідних блоків.

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

Процедура декодування трохи складніше, хоча вона теж досить проста.

  1. Відновити список вихідних блоків, які були використані для створення закодованого блоку.

  2. Для кожного вихідного блоку з цього списку, якщо вже його декодировали, провести операцію XOR з закодованим блоком і прибрати його зі списку вихідних блоків.

  3. Якщо у списку залишилися, як мінімум, два вихідних блоку, додати закодований блок в область тимчасового зберігання.

  4. Якщо у списку залишився лише один вихідний блок, це означає, що черговий вихідний блок успішно декодирован! Його потрібно додати до декодированному файлу і пройтися за списком тимчасового зберігання, повторюючи цю процедуру для будь-яких вихідних блоків, які містять знайдений блок.
0x48 0x65 0x6C 0x6C 0x6F, world!
Розглянемо приклад декодування для того, щоб краще в усьому розібратися. Припустимо, ми отримали п'ять закодованих блоків, кожен довжиною один байт. Також отримані відомості про те, з яких вихідних блоків кожен з них сконструйований. Ці дані можна представити у вигляді графа.


Граф, представляє отримані дані

Вузли зліва являють собою отримані закодовані блоки. Вузли праворуч – вихідні блоки. Перший з отриманих блоків, 0x48, як виявилося, сформований за участю лише одного вихідного блоку, першого. Таким чином, ми вже знаємо, що це був за блок. Переходячи в зворотному напрямку по стрілках, що вказує на перший вихідний блок, бачимо, що другий і третій закодовані блоки залежать тільки від першого початкового блоку і від одного іншого. А, так як перший вихідний блок вже відомий, можемо зробити над отриманими блоками і першим вихідним блоком операцію XOR і розкодувати ще декілька блоків.


Продовження декодування повідомлення

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


Декодований п'ятий вихідний блок

І, нарешті, тепер можна декодувати останній з останніх вихідних блоків, що, в підсумку, дасть повідомлення, яке відправник хотів передати одержувачу.


Повністю декодированное повідомлення

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

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

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

Ось, коротко, як працюють фонтанні коди, і, зокрема, LT-коди. Треба сказати, що LT-коди – це найменш ефективні з відомих фонтанних кодів, але вони і самі прості для розуміння.

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

Пірингові протоколи використовують функції безпечного хешування, начебто SHA1, при цьому довірена сторона, творець роздачі, надає список достовірних хешів всім учасникам. Кожен бенкет, користуючись цими даними, може перевірити завантажувані фрагменти файлу. Однак, при використанні фонтанних кодів подібна схема роботи ускладнюється. Немає способу обчислити, наприклад, SHA1 хеш закодованого фрагмента, навіть знаючи хеші окремих фрагментів, які взяли участь в його формуванні. І ми не можемо довіряти іншим учасникам обчислення цього хешу за нас, так як вони можуть просто нас обдурити. Ми можемо почекати, поки зберемо весь файл, а потім, користуючись списком неправильних фрагментів, можемо спробувати знайти невірні закодовані фрагменти, але це складно і ненадійно. До того ж, при такому підході, знайти помилки можна тільки у фіналі складання файлу, тобто – це, швидше за все, займе дуже багато часу. Одна з можливих альтернатив полягає в тому, щоб творець роздачі опублікував відкритий ключ і підписував кожен згенерований блок. Таким чином ми можемо перевірити закодовані блоки, але і тут є серйозний мінус. Справа в тому, що тільки творець роздачі може генерувати правильні блоки, а значить ми втрачаємо більшість переваг використання фонтанних кодів. Здається, тут ми зайшли в глухий кут. Однак, є альтернативи, наприклад, вельми хитромудра схема, називана гомоморфным хешуванням. Хоча і вона не ідеальна.

Висновок
Ми розповіли про основи фонтанних кодів. Різновиди цього алгоритму знайшли практичне застосування в тих областях, де його гідності однозначно переважують недоліки. Якщо ця тема вас зацікавила і ви хочете заглибитися в неї, почитайте цей матеріал фонтанним кодами. Крім того, корисно буде ознайомитися з Raptor-кодами, які, трохи ускладнюючи LT-коди, значно покращують їх ефективність. Завдяки їх використанню можна знизити обсяги переданих даних і обчислювальну складність алгоритму.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.