Как я могу оценить содержание энтропии этого входа?
У меня есть генератор треугольников 1 кГц, который я измеряю от микроконтроллера PIC с использованием аналогового входа. Источник частоты для треугольной волны и аналоговый захват являются отдельными источниками частоты. АЦП захватывает со скоростью 100 кбит / с с 12 [править:10] используемых битов точности.
Я хочу оценить энтропию, содержащуюся в аналоговых выборках с целью генерации истинных случайных чисел. Два источника энтропии, которые я определил, - это шум Кельвина и смещение источника частоты.
Из захваченного сигнала я могу непрерывно различать около двух частот в секунду, и я буду фиксировать в среднем одно событие нарушения порога входа Кельвина в секунду. Так что моя оценка составляет около двух бит энтропии в секунду.
Может кто-нибудь придумать способ оправдать большую оценку энтропии?
На основе ответов на аналогичные вопросы, уже размещенные на SO, я добавлю следующие пояснения:
Меня не особенно интересуют другие идеи об источниках энтропии, поскольку мне все равно придется ответить на этот же вопрос для этих альтернативных источников.
Анализ самих данных для автокорреляции или других мер случайности не является правильным ответом, поскольку они будут дико оптимистичными.
3 ответа
Вы рассматривали алгоритм "минимальной энтропии"? Я понимаю, что это было упомянуто в публикации NIST, SP800-90, и включено в черновик пересмотренной части B, в котором содержится обширная информация о тестировании источников энтропии на качество энтропии (стр. 61 содержит алгоритм "минимальной энтропии").
Я добился определенного прогресса, который может помочь другим.
Основной ресурс http://en.wikipedia.org/wiki/Johnson%E2%80%93Nyquist_noise
Емкость штырька будет ограничивать количество измеряемого теплового шума до 20 мкВ в пределах полосы частот АЦП. Это должно быть более или менее одинаково для довольно большого разнообразия контроллеров. Используйте резистор ~10К между сигналом и выводом. Меньшие значения уменьшат шум, но увеличат возможную частоту дискретизации.
Сигнал не должен быть случайным. Он просто должен быть равномерно распределен в пределах как минимум нескольких шагов дискретного ввода. Обратите внимание, что вывод в GPIO в том же домене синхронизации, что и вход, может не соответствовать этому требованию.
Для 10-АЦП с динамическим диапазоном 3,3 В каждый дискретный шаг составляет 3 мВ. Энтропия на выборку составляет около 20 мкВ / 3 мВ = 0,006 бит на выборку.
Также обратите внимание, что для этого не требуется аналоговый вход. Вы могли бы сделать это с цифровым входом, но размер ячейки был бы намного больше (1 В?), И ответ был бы больше как 0,000018 бит на выборку. Таким образом, взятие входной выборки каждую миллисекунду для генерации 64-битного случайного начального числа займет около часа.
Ваш вопрос не по теме, если мы говорим об энтропии "физика". Но мы могли бы так же легко сэмплировать ваш аналоговый сигнал, превратить его в цифровую форму сигнала, а затем обсудить возможность ввода в информационно-теоретическом контексте.
Простой и удивительно точный метод измерения энтропии в цифровом сигнале состоит в том, чтобы попытаться сжать его, используя лучшие доступные методы. Чем выше степень сжатия, тем меньше содержание информации.
Если ваша цель состоит в том, чтобы генерировать случайные биты для получения начального числа (как упоминалось в одном из других ответов), полезным подходом является сжатие случайных чисел, взятых из окружающей среды (нажатия клавиш, движения мыши, ваша аналоговая система), с использованием обычного сжатия. алгоритм, а затем отказаться от словаря. То, что остается, будет иметь значительный информационный контент.