Проблема в разрядности... unsigned long - это 32 бита, а ты сдвигаешь на 60... Тогда уж надо использовать int64_t, там по крайней мере есть эти 60 бит...

После такого описания

int64_t uL = StrToInt(MemoPolinom->Lines->Strings[i]);

компилятор перестал узнавать uL.. скажите, для использования этого типа случаем ничего подключать не нужно?

Нет, в Билдере этот тип называется __int64... Менять надо и тип uL и тип ShiftRegister... Но просто замена ничего не даст, LFSR по-прежнему будет возвращать одни нули... Надо инициализировать регистр сдвига другим значением. У меня при ShiftRegister = 134 все нормально закодировалось...

Ясно, спасибо!

Вот ещё с чем хочу разобраться:

...
int i=0;
        __int64 uL = StrToInt(MemoPolinom->Lines->Strings[i]);
	for (int i = 0; i < MemoPolinom->Lines->Count-1; i++) {
		uL ^= (ShiftRegister >> StrToInt(MemoPolinom->Lines->Strings[i]));
	}
...

если в качестве многочлена рассмотреть (32,7,5,3,2,1,0), то по вышеописанному алгоритму, насколько я поняла, XOR будет производиться над всеми битами, включая 32-й...А нам преподаватель объяснял, что XOR-рить нужно биты, исключая разрядность, т.е. в этом примере исключая 32-й бит..
Тогда получается, что у меня должно быть..

for (int i = 1; i < MemoPolinom->Lines->Count-1; i++)

Если придерживаться этого, я права в исправлении? или я чего-то недопонимаю.., скажите пожалуйста!

Сообщение отредактировано: 18192123 - 23.02.2009 17:55

Стоп, стоп... Если ты используешь __int64, то разрядность у тебя уже не 32, а 64, так что надо XOR-ить и для 32 тоже. Но вот если использовать unsigned long, который имеет размер в 32 бита, то можно и не сдвигать значение на эти самые 32, а все потому, что любое содержимое unsigned long, сдвинутое на 32 бита вправо, будет = 0... То есть, результат не изменится, но будет быстрее не делать ничего, чем прокрутить на 32 бита, а потом сделать XOR, отсюда и это уточнение твоего преподавателя...

Спасибо!! Теперь я поняла!

И наверно последняя трудность в восприятии:

int LFSR(TMemo *MemoPolinom)
{
	int i=0;
        __int64 uL = StrToInt(MemoPolinom->Lines->Strings[i]);
	for (int i = 0; i < MemoPolinom->Lines->Count-1; i++) {
		uL ^= (ShiftRegister >> StrToInt(MemoPolinom->Lines->Strings[i]));
	}
	uL &= 0x00000001;
	uL <<= StrToInt(MemoPolinom->Lines->Strings[0]);
	uL |= (ShiftRegister >> 1);

	ShiftRegister = uL;
	return ShiftRegister & 0x00000001;
}

Почему два раза нужно использовать операцию &? Объясните пожалуйста!

По алгоритму так. Все дело - в том, что первый & используется в процессе составления следующего значения ShiftRegister из предыдущего, а второй - это уже после того, как новое значение ShiftRegister готово, из него берется только последний бит.

вот здесь я до конца и не пойму..
Можете пошагово подробнее объяснить происходящее после цикла..?
Очень хочу во всём разобраться до конца..

Так... Это, похоже, неправильная функция. Правильнее (соответственно тому, что написано в той статье, на которую я давал ссылку выше, и готовой функции LFSR, которая приведена там) будет сделать ее вот так:

int LFSR(TMemo *MemoPolinom)
{
	__int64 uL = 0; // Сначала заносим 0, а не первый сдвиг
	for (int i = 0; i < MemoPolinom->Lines->Count; i++) {
		// XOR-им с предыдущим значением SR, сдвинутым на _все_ заданные сдвиги
		uL ^= (ShiftRegister >> StrToInt(MemoPolinom->Lines->Strings[i]));
	}
	// Оставляем только последний бит от полученного числа
	uL &= 0x0000000000000001;

	// Сдвигаем этот бит влево на _сколько нужно_ (согласно полиному) позиций
	uL <<= StrToInt(MemoPolinom->Lines->Strings[0]);

	// и OR-им со сдвинутым на 1 вправо предыдущим значением SR
	uL |= (ShiftRegister >> 1);

	// Все, у нас теперь в uL получилось новое значение SR, присваиваем его
	ShiftRegister = uL;

	// И возвращаем последний бит этого нового SR как результат функции
	return ShiftRegister & 0x0000000000000001;
}

Теперь функция делает абсолютно то же самое, что и та, готовая, которая приведена в статье... Раньше она делала не совсем то, что требовалось.



Сообщение отредактировано: volvo - 24.02.2009 3:26

а разве операция << это не сдвиг влево..? так куда же всё-таки нужно сдвигать...? и почему маска изменилась на 0x0000000000000001..?

Влево, влево надо сдвигать... Код правильный, в комментариях я ошибся... Исправлю.

Потому что тип ShiftRegister изменился на __int64 у тебя... А это - 64 бита. То есть, в 2 раза длиннее, чем было... Можешь, конечно оставить, как есть, можно вообще сделать

return ShiftRegister & 1;

, но я предпочитаю при работе с битовыми операциями записывать маски полностью.

А это будет последний левый бит?

Это будет младший бит (LSB), почему левый? Ясно же видно, что слева - все нули, а единица - самая правая... (вот поэтому я и предпочитаю писать битовые маски полностью, кстати).

А почему мы должны оставлять последний (младший) бит? Ведь насколько я поняла из статьи, левый бит является функцией всех остальных..а получается мы его не берём..?

В статье написано, что . Ты об этом? Единственное, что мне приходит в голову - это вот что: возможно надо делать

int LFSR(TMemo *MemoPolinom)
{
	__int64 uL = 0;
	for (int i = 0; i < MemoPolinom->Lines->Count; i++) {
		uL ^= (ShiftRegister >> StrToInt(MemoPolinom->Lines->Strings[i]));
	}
	uL &= 0x0000000000000001;
	// Не вот так, как ты делаешь...
	// uL <<= StrToInt(MemoPolinom->Lines->Strings[0]);

	// А вот так вот:
	uL <<= (sizeof(__int64) * 8) - 1; // или просто 63

	uL |= (ShiftRegister >> 1);
	ShiftRegister = uL;
	return ShiftRegister & 0x0000000000000001;
}

Чувствуешь разницу? То есть, если 31 в изначальной функции - это не первый член полинома, а (размерность unsigned long в битах) - 1, и надо было ВСЕГДА сдвигать на 31, а не только тогда, когда полином начинается с этого числа, то все становится на свои места.
Тогда действительно при сдвиге на sizeof(unsigned long)*8 - 1 бит тот самый правый бит, который получен как функция от всех остальных, станет самым левым. Тогда все сходится с описанием...

да..я об этом..
уж лучше оставлю сдвиг в зависимости от вида полинома...т.е.

uL <<= StrToInt(MemoPolinom->Lines->Strings[0]);

и исходя из этого последний вопрос:

uL |= (ShiftRegister >> 1);

перед этим мы результат XOR передвинули на количество позиций, определяемое разрядностью регистра сдвига... тогда для чего нужно сдвигать прежнее значение SR на 1 вправо (что это нам даст?) и что даёт OR c имеющимся в uL значением? Объясните пожалуйста!

Сообщение отредактировано: 18192123 - 24.02.2009 7:32

Нет уж, ты все-таки сделай так, как надо, а не так, как тебе хочется. А надо - именно сдвигать на sizeof(ShiftRegister)*8 - 1, вот тебе пример:
Wiki: Linear feedback shift register
Видишь, там напрочь нет 15 в полиноме (нет сдвига вправо на 15 бит), однако, чтобы получить тот самый единственный бит САМЫМ ЛЕВЫМ, производится сдвиг влево на 15 (при 16-битном размере регистра).

Ну ты уж будь последовательна... Только что ты сказала, что тебе плевать на разрядность регистра, тебе удобнее передвигать результат XOR-ов в зависимости от первого элемента полинома... Так что все-таки ты решила?

Если принять, что сдвиг производится в зависимости от разрядности, то... Смотри: Допустим, имеем 8-ми разрядный регистр (для простоты, принцип остается тем же для любой разрядности). Тогда:
SR = 00101011 (какое-то значение регистра)
Допустим, после преобразований и отсечения всех старших бит, получили uL = 00000001... Теперь сдвигаем это значение так, чтобы выделенный бит был старшим: uL = 10000000. И "складываем" (OR) с предыдущим значением SR, сдвинутым на 1 позицию вправо (т.е., с 00010101)... Что имеем в результате?
10000000
00010101
--------
10010101, то есть, старшим битом идет бит, только что вычисленный "как функция от остальных бит регистра", а остальные - просто сдвинутые исходные... А теперь сравни: