Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: По поводу статьи о RND и CRC  (Прочитано 34816 раз)
0 Пользователей и 1 Гость смотрят эту тему.
REEEBOK
Гость
« : 31-05-2004 14:37 » 

Добрый день.

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

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

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

С уважением,
Николай Рябков.
Записан
SkullHead
Гость
« Ответ #1 : 31-05-2004 15:02 » 

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

us
Offline Offline
Пол: Мужской

« Ответ #2 : 31-05-2004 18:08 » 

У меня несколько замечаний по существу. Не буду коментировать проблему переучивания программистов, поднятую 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 тоже должен быть правильно выбран и  есть какая-то математика на эту тему.
Записан

Если бы окружающие нас объекты содержали столько же ошибок, сколько программы, цивилизация обрушилась бы от первого порыва ветра...
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #3 : 01-06-2004 02:06 » 

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

Цитата

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


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

SkullHead,
Цитата

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

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

Цитата

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

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

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

Chaa
Помогающий

ru
Offline Offline
Пол: Мужской

« Ответ #4 : 02-06-2004 09:58 » 

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

ru
Offline Offline
Блондинка...


WWW
« Ответ #5 : 02-06-2004 18:34 » 

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

Стену можно пробить только головой. Все остальное орудия.
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 02-06-2004 21:29 » 

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

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

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Anonymous
Гость
« Ответ #7 : 03-06-2004 00:01 » 

А что авторы последних двух постов предыдущие сообщения вообще не читали? Там же это все уже обсуждалось.
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #8 : 03-06-2004 02:12 » 

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

а то люди решат, что это я дерзю  Ага
Записан

Алёна
Молодой специалист

ru
Offline Offline
Блондинка...


WWW
« Ответ #9 : 03-06-2004 08:16 » 

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

rand() и srand()
я не знаю.

Цитата

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


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

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


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

Стену можно пробить только головой. Все остальное орудия.
Алёна
Молодой специалист

ru
Offline Offline
Блондинка...


WWW
« Ответ #10 : 03-06-2004 08:19 » 

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

Стену можно пробить только головой. Все остальное орудия.
Сдава
Гость
« Ответ #11 : 09-06-2004 15:41 » 

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

ru
Offline Offline
Сообщений: 13


« Ответ #12 : 09-06-2004 18:55 » 

Цитата

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


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

Цитата

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


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

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

Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #13 : 10-06-2004 09:01 » 

Цитата: Алексей1153

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

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


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

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))
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #14 : 10-06-2004 14:19 » 

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

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

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

Цитата

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


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



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

Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #15 : 10-06-2004 14:50 » 

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #16 : 10-06-2004 14:58 » 

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #17 : 10-06-2004 19:46 » 

Sla,
 
Цитата

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


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

 :arrow:
Цитата

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

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

:arrow:
Цитата

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

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

:arrow:
Цитата

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

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

:arrow:
Цитата

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


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

RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #18 : 10-06-2004 20:27 » 

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

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #19 : 11-06-2004 16:45 » 

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

RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #20 : 12-06-2004 16:32 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #21 : 14-06-2004 10:50 » 

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

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #22 : 14-06-2004 18:52 » 

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

Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #23 : 19-10-2004 10:12 » 

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines