ИННОВАЦИИ БИЗНЕСУ

Результат выполнения научно-исследовательской работы.

Кодирование в параметрической системе кодовых множеств [1,2] позволяет предложить алгоритмически эффективную реализацию ранговой перестановочной схемы (mtf), в которой при перемещении кодируемого сообщения на первую позицию в списке одновременно производится перемещение вниз по списку не всех предшествующих ему до перемещения элементов, а только тех, длины кодовых слов которых могут измениться. Так как при использовании указанной параметрической системы кодовых множеств могут измениться лишь длины кодовых слов сообщений, перемещаемых между подмножествами [2], то общее число выполняемых перестановок сокращается до величины , где -наименьшее целое большее или равное . Алгоритм может применяться также с фиксированными кодами переменной длины, однако в этом случае избыточность кодирования несколько увеличится.

Для быстрого доступа к индексам кодируемых сообщений алгоритм использует массив tbl[n,2], первый элемент которого хранит ранг соответствующего индексу сообщения, а второй ссылку, необходимую для выполнения обменов.

1.mtf-алгоритм кодера:

1.1. Инициализировать рабочие переменные и получить код сообщения из таблицы tbl.

dword pres = 0; s = 1;

byte n = 0;

basetype pcode = c; ctrans; ingruppos; code= tbl[c][0];

1.2. Выполнить цикл межгрупповых перестановок.

while ( !( code < s="" )="">

{

m = s - pres;

ingruppos = (basetype) ( keys[n]++ % m + pres ) ;

ctrans = tbl[ingruppos][1];

tbl[ingruppos][1] = pcode;

tbl[pcode][0] = ingruppos;

pcode =ctrans;

pres = s;

s <=>

n++;

}

1.3. Присвоить новые значения крайним переставляемым элементам:

tbl[code][1] = pcode;

tbl[pcode][0] = code;

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

return code;

Число итераций приведенного алгоритма не превышает , где - максимальная мощность кодируемого алфавита. Например, для алфавита из 65536 сообщений кодер выполнит на одно сообщение в худшем случае всего 16 циклов из нескольких элементарных операций целочисленной арифметики и назначений. Вектор keys длины [log ₂(n)+1] поддерживает для каждой из log ₂(n)+1 групп с равными длинами кодовых слов отдельный циклически изменяемый внутригрупповой указатель, используемый для выбора очередного элемента группы для обмена. Перестановочная схема декодирования симметрична и имеет те же оценки " память/время ":

2.mtf-алгоритм декодера:

2.1.Инициализированть рабочие переменные и получить индекс сообщения из таблицы tbl по его ранговому коду code.

dword pres = 0; s = 1;

byte n = 0;

basetype pcode = c; ctrans; ingruppos; c = tbl[code][1];

2.2. Выполнить цикл межгрупповых перестановок.

while ( !( code < s="" )="">

{

m = s - pres;

ingruppos = (basetype) ( keys[n]++ % m + pres ) ;

ctrans = tbl[ingruppos][1];

tbl[ingruppos][1] = pcode;

tbl[pcode][0] = ingruppos;

pcode =ctrans;

pres = s;

s <=>

n++;

}

2.3. Присвоить новые значения крайним переставляемым элементам:

tbl[code][1] = pcode;

tbl[pcode][0] = code;

2.4.Вернуть исходный код декодируемого сообщения для последующего его вывода в выводной поток декод\ера.

return c;

Литература:

1. Гаджиев Ю.А. Параметрически адаптивный ранговый код. Вестник Дагестанского государственного технического университета. Технические науки. Вып. 1., Махачкала, 1997, стр. 3033.

2. Гаджиев Ю.А. Об избыточности кодирования в параметрически адаптивной ранговой схеме. Вестник Дагестанского государственного технического университета. Технические науки. Вып. 2., Махачкала, 1998, стр. 23-26.