Преобразование генератора M-последовательности из формы Фибоначчи в форму Галуа. Может кому-нибудь пригодится. Получилось так, что к процессору ЦОС подключено устройство со встроенной схемой самотестирования с генератором псевдослучайной последовательности на регистре сдвига с линейной обратной связью (РСЛОС). Устройство передает 16 разрядные слова каждое из которых является следующим состоянием РСЛОС. Соответственно надо принять данные от устройства, в процессоре сгенерировать такую же последовательность и сравнить. Причем РСЛОС сделан в форме Фибоначчи (проверяется несколько бит, а изменяется только один).
Вот собственно его алгоритм:
uint32_t p,f,ffb;
// 16 разрядный РСЛОС занимает младшую половину 32 битного слова
f=initstate; // начальное состояние
ffb=0x00006FFF; // полином обратной связи FibonacciFeedBack
/* следующее состояние */
p=parity(f&ffb); // parity - бит паритета
f>>=1;
f|=p;
Все бы ничего но в процессоре нет команды вычисления паритета или подсчета единиц. Можно конечно вычислить паритет способом вроде этого:
p=f&ffb;
p^=p<<8;
p^=p<<4;
p^=p<<2;
p^=p<<1;
p&=0x8000;
Но это как-то длинно и не распараллеливается. Наука говорит что РСЛОС в форме Галуа (проверяется один бит, а изменяется несколько) генерирует такую же ДВОИЧНУЮ ВЫХОДНУЮ последовательность хотя и состояния самого регистра не совпадают с состояниями РСЛОС Фибоначчи. Частично с помощью теории, частично методом научного тыка у меня получился такой алгоритм:
uint32_t p,g,gfb,i;
/*сам РСЛОС располагается в старшей половине слова, а в младшей хранится двоичная выходная последоательность*/
g=initstate; // начальное состояние, младшая половина 32 битного слова
gfb=0xFFF60000; // полином обратной связи GaloisFeedBack зеркальный относительно FibonacciFeedBack
/*инициализация РСЛОС так чтобы он генерировал нужную последовательность*/
for (i=16; i>0; i--){
p=g&1;
g>>=1;
if (p) g^=gfb;
};
g=(g&0xFFFF0000)|(initstate&0x0000FFFF);
/* следующее состояние */
p=g&0x10000;
g>>=1;
if (p) g^=gfb;
Здесь уже следующее состояние вычисляется гораздо проще.
Чего нибудь внятного по преобразованию РСЛОС из одной формы в другую в интернете мне не попалось, поэтому решил описать то что у меня получилось.
Если кто-то видел толковое описание такого преобразования - поделитесь ссылкой.
И есть еще вопрос: может для проверки не надо генерировать идентичную М-последовательность, а можно вычислять какую-нибудь простую функцию от данных?
Хотя и не похоже что может быть что либо проще трех команд вычисления следующего состояния в форме Галуа (причем, две из них выполняются параллельно).