По поводу статьи о RND и CRC

[REEEBOK]

Добрый день.

RND: Для псевдослучайных величин доказана их хорошая случайность. (Т.е. то, что они близки к нормальному распределению-кажется так- по всем характеристикам). У нас даже лабы такие были. А вот как быть с предложенным методом получения случайного числа - совсем неясно.

CRC: CRC не однозначно характеризует последовательность, а с определенной вероятностью (97% или около того, но я не помню).  ИМХО однозначно информацию может характеризовать только она же сама. В сжатом виде займет меньшем места. А вот метод сжатия (без потерь, хочу заметить) - это другой вопрос.

Такие вот мысли.  

С уважением,
Николай Рябков.

[SkullHead]

насчет статьи вообще - есть пару замечаний\вопросов к автору.
Я насчет RND
Автор говорит, что не будет отыслать читателей к RTFM. А надо бы. Тогда бы и узнал про такие полезные функции rand()/srand() и не занимался бы извращениями сам и не совращал бы на извращения других. А то после таких статей вырастают программисты, которых после приема на работу приходится переучивать.
Интересно, до какого извращения додумался бы автор, если бы ему надо было заиметь случайное число в консольной программе, из которой к мышке не добраться? Или например из какого-нибудь сервиса ?
И вообще, у вас хоть какое-то подобие редактора есть, который просматримает статьи перед их выпуском на сайт?

[Sashok]

У меня несколько замечаний по существу. Не буду коментировать проблему переучивания программистов, поднятую SkullHead,  - не имеет смысла.

Насчет rand/srand полностью согласен - упущение вышло.

Итак:
1. Псевдослучайные числа.
Они названы так не потому, что их список зашит в ПЗУ, а потому, что генерируются с помощью строго детерминированного алгоритма, и величина каждого числа ограничена. Соответственно, последовательность получается периодическая. Именно в этом смысл слова "псевдо".

Или составлялась мутная формула с участием 3 и 5 цифры дробной части числа, сильно зависящего от констант (!) - экспоненты или числа пи.

Да, были такие алгоритмы, а еще и алгоритмы со всякими сдвигами. А потом пришли к выводу, что случайные числа плохо генерировать случайным образом. Если не ошибаюсь, у Кнута приведен пример, когда зубодробительно-бессмысленные операции приводили к тому, что через 8(!) шагов "случайные" числа повторялись. Поэтому, с некоторого времени общепринятым стал "линейный конгруэнтный метод". Идея его очень проста: если числа a, b и n - взаимно просты, то последовательность Xn, такая, что Xк+1=(а * Хк + b) mod(n) при хорошем подборе a, b и n будет пробегать по всем возможным остаткам и, соответственно, иметь период равный n. Да еще желательно, чтобы следующее число не было слишком близко к предыдущему (то есть, a=1 и b=3 при, скажем, n=2**32 - плохой выбор).

Кстати, REEEBOK, распределение при этом получается не нормальное, а равномерное. А нормальное из него надо строить (в Яве это уже сделано в виде стандартной функции).

Друзья программисты - читайте Кнута!!!

2. Собственно случайные числа. Можно, например, сделать генератор, основанный на датчике радиоактивности. Где-то я читал, что такое иногда делается там, где нужна истинная случайность. В большинстве же приложений достаточно, чтобы случайной была начальная точка, а дальше вполне устраивает "хорошая" псевдослучайная последовательность. В качестве такой точки обычно используется внутренний таймер. По крайней мере, гарантированно не будет двух одинаковых стартовых точек. И при этом не важно, есть у нас графическая среда, или нет.

3. CRC
Расшифровывается как Cyclic Redundancy Code, т.е. циклический избыточный код. Алгоритм описан в статье совершенно правильно.
Как и любое средство повышения достоверности передачи информации, оценивается по степени обнаруживаемых и степени автоматически исправляемых ошибок. Скажем, если для простых приложений не брать CRC, а использовать просто XOR для всех байтов, он обнаружит нечетные ошибки и частично четные, но не сумеет ничего исправить. А если добавить XOR "по горизонтали" (то есть всех битов в байте), то однократную ошибку уже можно будет автоматически исправить. Ну, и т.д.

Кстати, "делитель" для CRC тоже должен быть правильно выбран и  есть какая-то математика на эту тему.

[Алексей++]

хм... вторая тема для битья одной статьи  

Интересно, до какого извращения додумался бы автор, если бы ему надо было заиметь случайное число в консольной программе, из которой к мышке не добраться? Или например из какого-нибудь сервиса ?

есть такое извращение   - в случае, если юзер давит на клаву - между нажатиями клавиш время ааабсолютно неодинаково. Вы,SkullHead,  думаете у меня не было компьютера без мыши (и жёсткого диска, кстати тоже)?
Но - я забыл упомянуть - я не предлагаю этот способ получения RND как универсальный, а именно только для приложений, где много используется мышь и клава - то есть в играх, к примеру

SkullHead,

читателей к RTFM. А надо бы.

идите, читайте. Что непонятно будет - спрашивайте.

И вообще, у вас хоть какое-то подобие редактора есть, который просматримает статьи перед их выпуском на сайт?

нет. Есть только рецензенты - иначе никакого обучения не будет

Sashok, спасибо за замечания и дополнения

[Chaa]

Функции rand() и srand() генерируют случайные числа. Но у этих чисел есть серьезная проблема - они предсказуемы. Т. е. как заметил Sashok, Xk+1 = f(Xk), следовательно, зная одно случайное число, мы можем предсказать все последующие. Получается, что числа не такие уж и случайные. Поэтому существуют т. н. случайные числа криптографического качества, у которых нет данного свойства.
Под Windows для получения случайных чисел криптографического качества следует использовать функцию CryptGenRandom().
Кстати во многих программах генерации RSA ключей просят поводить пользователя мышью по экрану для сбора случайных данных, это как раз то, о чем и писал автор статьи.

[Алёна]

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

[npak]

Алёна, существует практика инициализации последовательности чисел текущим значением ситстемного вызова.

Для ряда приложений в криптографии такая случайность недостаточна.  Поэтому используют более случайные величины, такие как скорость воздуха внутри жёсткого диска, или число событий при распаде радиоактивного изотопа.  Подробное обсуждение проблемы случайных чисел есть на сайте www.random.org (или по ссылкам оттуда).

[Anonymous]

А что авторы последних двух постов предыдущие сообщения вообще не читали? Там же это все уже обсуждалось.

[Алексей++]

Гость, надо было хоть представиться  

а то люди решат, что это я дерзю  

[Алёна]

Гость,  Я со случайными числами последний раз сталкивалась лет семь назад, поэтому функций

rand() и srand()

я не знаю.

А что авторы последних двух постов предыдущие сообщения вообще не читали? Там же это все уже обсуждалось.

А я не догадалась Что это именно то.

Можно поподробнее написать что это за функции и для чего они сейчас применяются.  Можно даже сослаться на  RTFM если есть такое желание


P.S. Жду подробностей.

[Алёна]

Алексей1153,  А где вторая тема по обсуждению этой статьи ? А то я что то не сталкивалась с ней

[Сдава]

Что касается CRC - то еще для большей надежности сумма в самом начале инициализируется всеми единицами, если CRC16 - 0xFFFF
 подобных статей в инете, и не только,  много

[Алексей++]

А где вторая тема по обсуждению этой статьи ?

которая в "Обсуждение/Заказ статей"  - два слова из трёх букв

Что касается CRC - то еще для большей надежности сумма в самом начале инициализируется всеми единицами, если CRC16 - 0xFFFF

то есть первые два байта сообщения затираются единицами?  

и хде тут повышение надёжности, поясните пожалуйста,

[Sla]

то есть первые два байта сообщения затираются единицами?  

и хде тут повышение надёжности, поясните пожалуйста,

Для тех кто не понял:

proc    Crc16 strsend {
  set sumcrc 0xFFFF
  foreach tmp $strsend {
   set sumcrc [expr $tmp ^ $sumcrc]
   for {set j 0} {$j<8} {incr j} {
     if {[expr $sumcrc & 1]} then {set sumcrc [expr $sumcrc >> 1 ]
                                   set sumcrc [expr $sumcrc ^ 0xa001]
     } else {set sumcrc [expr $sumcrc >>1 ]}
   }

  }
  return $sumcrc
}
Это из работающего application
Существует еще и табличный метод вычисления CRC
его преимущество - скорость
недостаток - объем кода (необходимо хранить 512 байт (для CRC16))

[Алексей++]

Sla, ладно, про затирание двух байт проехали, оказывается имелось в виду добавление в начало мессаги двух байт 0xff, 0xff.

Про повышение надёжности теперь поясните

кроме того, моя application (из примеров) - тоже работающая

Существует еще и табличный метод вычисления CRC
его преимущество - скорость
недостаток - объем кода (необходимо хранить 512 байт (для CRC16))

если на выходе - 16 битная CRC, какой смысл использовать для его вычисления 4096 бит?



ЗЫ. Sla, нет, я не огрызаюсь. Критика - вещь полезная. Просто обсуждение статьи плавно перешло в обсуждение методов вычисления CRC - вот я и отвечаю в соответствии с.

[Sla]

Про надежность завтра расскажу Я подготовлюсь, литературу почитаю
А про скорость сегодня
Заранее вычисляется таблица .CRC (которая по сути представляет все возможные комбинации с маской), а потом выбирается по индексу из таблицы. Так что быстрее? восемь раз двигать или один раз из таблицы?
А если девайс тормозит? и двигать надо 16 разрядное число, а если у тебя 8-разрядное ядро?

Да и еще. Маска которая применяется в CRC тоже не с фонаря берется
Если видно у меня она 0xA001, в статье не помню,  но другая

[Sla]

В продолжение.
message не должен иметь первых FFFF
crcsum=0xFFFF
а потом известный алгоритм
возможна ситация когда CRC считается на лету:
байт получили - сложили и т.д
или
байт отдали - сложили

[Алексей++]

Sla,
 

Так что быстрее? восемь раз двигать или один раз из таблицы?

 :arrow:
арифмитический сдвиг на 1 бит 16-битногочисла - несколько тактов (>4 - в документации).
а индексация и ЧТЕНИЕ ИЗ ОЗУ - я не думаю, что быстрее...

 :arrow:

Маска которая применяется в CRC тоже не с фонаря берется

не спорю. Подскажешь как - буду благодарен, базара нет

:arrow:

А если девайс тормозит?

не суть важно.
(хотя - такой уже давно пора выкинуть)

:arrow:

и двигать надо 16 разрядное число, а если у тебя 8-разрядное ядро?

проблем нет - используй команды циклического сдвига. Младший байт двигается арифметически, старший - сразу после него, без очищения флага переноса, - циклически. Но, да, тогда эффективность по времени снижается в 2
раза. Но - выбери ты 16-ти разрядный или частоту вдвое повысь

:arrow:

возможна ситация когда CRC считается на лету:
байт получили - сложили и т.д

в статье - самое что ни есть на лету. Третий байт буфера принимает по очереди байты - а они хоть откуда могут туда поступать. Можно ведь не заранее получить всю мессагу - а добывать по байту. Теме не менее , для контроля нужно всё сообщение целиком

[RXL]

арифмитический сдвиг на 1 бит 16-битногочисла - несколько тактов (>4 - в документации).
а индексация и ЧТЕНИЕ ИЗ ОЗУ - я не думаю, что быстрее...

Во-первых, таблица преобразует 8 бит за раз, а не по одному биту. Во-вторых, наличие условного перехода ( if(bit 0) .... ), в "однобитовом" варианте, вызывает частую перезагрузку конвеера (prescott-ах - 31-а ступень, в northwood - 21). Так где быстрее работает?

[Алексей++]

RXL, а что за таблица такая хитрая?

[RXL]

Алексей1153, ни чего хитрого.
Рекомендую: http://www.vsu.ru/~reb/library/security/crcguide.pdf
Там и о теории, и о различных методах вычислений, в том числе и табличном.

[Sla]

Выбор полинома - ой!  было это в годах 1988-89, помнятся такие слова как кодовое расстояние.
Но это не важно.
Если у тебя, например контроллер, 8-разрядный - девайс не выбросишь;
частоту не повысишь
Выбор базы - дело сложное
Скорость - точность - цена - и т.д
процесс может быть критечен ко времени
АЦП по рерыванию работает, ЦАП, ШИМ и т.д. и озу 256 байт, то в озу таблица не хранится, она прошивается в коде.
Две-три  команды чтобы вытянуть из таблицы
и 9*8 команд чтобы сдвинуть, так что быстрее?
Я могу кинуть алгоритм расчета таблиц
Можно посеть эти ссылки

http://www.microconsultants.com/tips/crc/crc.txt  
http://www.embedded.com/internet/0001/0001connect.htm
Ссылки живые - проверял

Для CRC есть еще ограничения и для размера блока, который необходимо закрыть CRC
Обещал про надежность
Если в начале сообщеия будет много нулей то тогда появится "дырка", но опять же давно было - надо литературу поднимать

[Алексей++]

убедили, однако . Но вникнуть по некоторым зависящим от меня причинам сейчас не могу. Только через недельку...

[Sla]

Если кому-то еще интересно
то здесь классная статья