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

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

Алгоритм основан на использовании в mtf-моделях не одного множества двоичных кодовых слов переменной длины, как это делается в известных реализациях, а некоторого класса определяемых параметром w таких множеств, отличающихся дифференциацией длин кодовых слов внутри множества.

Алгоритм кодирования:

lbound=0; // нижняя граница параметра

hbound=log₂n; // верхняя граница параметра

w=hbound; // начальное значение параметра

while( НеКонецВходногоПотока )

{

c=ОчереднойСимволВходногоПотока;

r =mtf_e( c ) ;

code=Кодировать (r,w) ;

ВывестиВВыходнойПоток (code) ;

if(r<>^w){if(w>lbound)w=w- 1; }

else if(r > 2 ^w)if(w < hbound="">) w = w + 1;

}

Функция Кодировать(r,w)

{

if( r < 2="">^w) ngroup = 0 ;

elsengroup = integer ( log ₂ (r/2 ^{(w - 1 )} ) );

codegroup ={ (ngroup - 1)дв.единицизатемдв.нуль,если( ngroup < hbound="" -="" m="" )="">};

if( ngroup == 0 )

{fixcode = r ; fixcodelen = w }

else{ fixcode = r - integer ( log ₂ r );

fixcodelen = ngroup + w -1 }

code =Объединить(codegroup, fixcodelen

младших разрядовfixcode);

returncode;

}

Алгоритм декодирования:

lbound= 0; // нижняя граница параметра

hbound=log₂n; // верхняя граница параметра

w=hbound;// начальное значение параметра

while(НеКонецВходногоПотока)

{

r=ВвестиИДекодировать (w) ;

c =mtf_d ( r ) ;

ВывестиВВыходнойПоток( c ) ;

if(r < 2="">^w){if(w > lbound ) w = w - 1; }

else if(r > 2 ^w)if(w < hbound="">) w = w + 1;

}

Функция ВвестиИДекодировать(w)

{

ngroup=0;

while((ngroup<>₂n-w) && НеКонецВходногоПотока)

{

b=БитВходногоПотока;

if(b== 0 )break;

ngroup = ngroup + 1 ;

}

if(ngroup == 0 ) fixcodelen = w ;

else fixcodelen = ngroup + w - 1 ;

fixcode =ЧитатьИзВходногоПотока(fixcodelen) ;

//параметр-числобит

if(ngroup == 0 ) r = fixcode ;

else r = fixcode + 2 ^(ngroup+w-1);

}

Функция mtf_e выполняет перестановку индекса кодируемого сообщения и возвращает его текущий ранг (до перестановки), mtf_d - возвращает исходный индекс сообщения по его рангу, после чего производит перестановку. Детали реализации перестановочной схемы mtf несущественны.

Алгоритм может быть применен также для кодирования любого счетного индексированного множества упорядоченных по вероятности сообщений. Теоретическая граничная оценка ожидаемой длины кодового слова в этом случаеlg=h(q)+2 [1]. Практическая -l»h(q)+0,7. При кодировании неупорядоченного по вероятности множества сообщений избыточность приблизительно равна избыточности равномерного кода.

Литература:

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