Невипадкові стирають коди

Для вирішення вищезазначених проблем були запропоновані нові стирають коди, названі «невипадкові стирають коди» (НССК). Вперше робота, присвячена НССК, була опублікована в [4]. Мотивацією до створення НССК стало те, що при низьких значеннях К не працюють статистичні властивості, складові основу теорії ЛТ коду. Тому необхідно контролювати кількість входжень вихідних символів в кодові пакети, забезпечуючи велику робастної і підвищуючи ефективність коду.

Код НССК використовує модифіковане робастное розподіл (Robust Soliton Distribution [1, 4, 5]) м'(d). Робастний модифікованого розподілу додатково підвищена шляхом збільшення числа пакетів зі ступенем 3 на 30% від числа пакетів зі ступенем 1 (виведено емпірично). У поточній реалізації НССК кількість кодових символів обмежена конкретною величиною N, яка визначається виходячи з максимально дозволеного надлишку кодових пакетів відносно числа K вихідних символів як N=Kв, де в — величина, трохи більше 1 (задається виходячи з особливостей каналу передачі).

Черга вихідних символів позначимо коротко ЧВС, як і раніше. Черга кодових символів позначимо ЧКС. Будемо використовувати індекси для звернення до символів в ЧКС і ЧВС. Кількість входжень вихідного символу f в кодові символи як «сусіда» назвемо мірою захищеності вихідного пакета. Позначимо міру захищеності змінній R[f], f=0,…, K-1.

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

Крок 1. Визначити кількість кодових символів, призначених для кодування зі степеням d0,…, dmax згідно:

N[d1] = µ[d1] N,.

де N — цільове кількість кодових символів.

Крок 2. Вибрати n[d0] вихідних пакетів з найвищим пріоритетом. Закодувати їх як опорні символи зі ступенем 1. Можна записати це дію мовою псевдо-Сі як for (i=0; i < n[d0]; i+ +).

{OKC[i] = OИС[fi]; },.

де fi позначає індекс вихідного символу з ЧВС.

Крок 3. Провести кодування всіх символів, закодованих на кроці 1, за такою процедурою:

for (i =0; i < n[d0]/3; i++).

{.

OKC[i+n[d0]]=OИС[f3i] XOR OИС[f3i+1] XOR OИС[f3i+2];

R[f3i]=2; R[f3i+1]=2; R[f3i+2]=2;

}.

Крок 4. Позначимо через WR підмножина всіх вихідних символів, що володіють на певному етапі кодування мірою захищеності R. Серед них підмножина символів з максимальною мірою захищеності позначимо як WMAX, з мінімальною — WMIN.

Задати I = 2.

Крок 4.1. Виконувати дії 4.1.1 і 4.1.2 n[di] раз:

Крок 4.1.1. Згенерувати черговий к-й кодовий символ як результат операції XOR над одним символом з WМАХ, одним з WМАХ-1,…, одним з WL-1, і одним символом з WMIN, де L=MAX-di, т. е. виконати дію:

ОКС[k]=WMAX[j0] XOR WMAX-1[j1] XOR… XOR.

WL-1[jL-1] XOR WMIN[jL];

Крок 4.1.2. Збільшити на одиницю значення R[jt] для всіх jt, t=0…L (тут індекси jt є індексами вихідних пакетів в ЧВС).

Крок 4.2. Оновити підмножини WR, а також максимальне і мінімальне значення R. Збільшити i на одинцю. Якщо i стало рівним dmax+1, або загальне число кодових символів досягло бажаного кількості N, вихід. Інакше перейти на Крок 4.1.

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

Найважливішим є те, що рядки матриці індексів вихідних пакетів J в ідеалі повинні бути лінійно незалежними, або, по крайній мірі, мати якомога менше комбінацій лінійно залежних векторів-рядків.

Породжує графом коду НССК є граф із систематичною структурою. Приклад подібного графа наведений на рис. 3. Приклад алгоритму вибору індексів «сусідів» з підмножин може бути знайдений в [6].

Рис. 3 Приклад породжує графа коду НССК