пятница, 14 мая 2010 г.

Аппаратно-программный ГСЧ на базе звуковой карты ПК/ноутбука

В прошлых материалах цикла по спектроанализу [1...3] были разработаны как виртуальный комплекс измерения, так и библиотека DTMF кодера-декодера со встроенным анализатором спектра, используя быстрое преобразование Фурье, сигналов REALTIME со звуковой карты и внешнего АЦП. Сегодня мы покажем вам как расширить возможности данного измерительного комплекса (библиотеки) и создадим аппаратно-программный генератор случайных последовательностей на основе интегрированной звуковой карты.


Для чего это вообще может понадобится и почему недостаточно исключительно программных random-методов генерации псевдо-случайных последовательностей (ГПСЧ)? Причина проста генераторы ПСЧ* не являются случайными в математическом смысле слова, поскольку известен алгоритм их генерации, а значит они предсказуемы. И если для многих задач, как генетические алгоритмы, учебные задачи или игры, ПСЧ вполне достаточно, то для проведения качественного моделирования процессов в электронных приборах, имитации пользовательских действий и, в особенности, задач криптографии (для генерации ключей смарт-карт), чем выше энтропия** последовательности, тем ниже ее предсказуемость. Следует отметить, что существует класс ГСПЧ с детерминированным алгоритмом, но функция генерации которых необратима, что затрудняет последующий анализ зависимостей внутри сгенерированных последовательностей для целей реверсинга (восстановление исходного алгоритма генерации).

* Одним из первых программных ГПСЧ является метод середин квадратов, предложенный в 1946 году Дж. фон Нейманом [4, 5]. Этот ГПСЧ формирует каждый следующий элемент последовательности на основе предыдущего путем возведения его в квадрат и выделения средних цифр из полученного числа.

Например, мы хотим получить 15-тизначное число и предыдущее число равнялось 346783045163451. Возводим его в квадрат и получаем 120258480412836 096003306229401 значит, следующим числом будет 0412836096003306 и т.д.

** Энтропия – мера неопределенности какого-либо опыта (испытания), который может иметь разные исходы / https://ru.wikipedia.org/wiki/Энтропия

Краткий экскурс…

В электронике шумит все, самый простой пример – тепловые шумы в резисторе, зависящие от его сопротивления и дробовые шумы при протекании тока через него. Только вот уровень шумов в них столь мал, что не годится для практического использования (за исключением их негативного влияния в усилительных НЧ и ВЧ каскадах, если помните резисторы марки ВС и другие, изготовленные по технологии резистивного слоя с проводящими металлическими частицами в среде непроводящего наполнителя, обладали высокими собственными шумами из-за точечного характера контактов между частицами). Поэтому на заре развития радиотехники большее распространение получили газоразрядные лампы, а позже и стабилитроны, шумы которых в режиме лавинного пробоя имеют спектр, близкий к спектру белого шума. После чего этот шум усиливают и используют для проверки чувствительности, полосы пропускания и прочего. Однако не будем отвлекаться, что с нашей-то звуковой картой? Да, собственно, все то же – тепловой шум, обусловленный рекомбинацией электронов, и собственные шумы внутренних каскадов при преобразовании сигнала. Выражен этот эффект в известных всем электронщикам, работающим с аналого-цифровой техникой, так называемых «шумящих битах» – младших разрядах АЦП. Характер распределения такого шума тоже подчиняется нормальному закону распределения и является чисто случайным. Вот с ними-то, «шумящими битами» с линейного или микрофонного входа, и будем работать, превратив аудиокарту в своего рода аппаратно-программный ГСЧ. Приступим?

Предпосылки реализации ПО

Для корректной работы аппаратно-программного генератора случайных чисел на основе звуковой карты и получения характера нормального распределения потребуется закорачивание микрофонного входа или входа записи по-умолчанию, и установке движка регулятора громкости в максимальное положение. Если рассмотреть сам процесс оцифровки сигнала, то: вначале сигнал усиливается и нормируется в соответствии с динамическим диапазоном АЦП аудиокарты, после чего оцифровывается АЦП с заданным разрешением (битностью) и частотой дискретизации. Доступ к этим данным можно получить программно через соответствующее API, в частности под Windows – это WaveForm Audio http://msdn.microsoft.com/ru-RU/library/windows/desktop/dd757715(v=vs.85).aspx. Подробности работы с этим API мы опустим, поскольку в предыдущих материалах оно уже было рассмотрено. Накопление данных в буфере (массиве) заданного объема (чем выше, тем выше точность, но большее время требуется на накопление, как правило, в течении нескольких секунд) произведем путем выделения младшего бита из младшего байта данных АЦП аудиокарты. Соответствие характера распределения получаемых данных нормальному проведем с помощью известного теста Pseudorandom Number Sequence Test Program – утилиты ENT http://www.fourmilab.ch/random [6], а в реальном времени по критерию сериальной корреляции (см. формулу 1, том второй Д.Кнута [7]):
C = (n * (Ui*Ui+1 + ... Ui-1*Uo) + (Uo + ... Ui-1)^2 ) / (n* (Uo^2 + ...Ui-1^2) - (Uo + ... Ui-1)^2); (1)
где: С – коэффициент сериальной корреляции для своего же набора данных (частный случай); n – количество отсчетов в выборке; Ui-1, Ui, Ui+1 – отсчеты в выборке.

Коэффициент корреляции всегда лежит между «-1» и «+1». Когда он равен «0» или очень мал, значит, величины Ui, Ui-1 и Ui+1 независимы одна от другой, т.е. между ними нет линейной зависимости. Если же значение коэффициента корреляции равно ±1, это означает полную линейную зависимость.

Кроме того, потребуется вычисление математического ожидания и дисперсии. Математическое ожидание – это величина, вокруг которой колеблются случайные числа, т.е. среднее значение всех случайных величин. Т.е. перебираются i-тые отсчеты захваченного отсчетов шума и суммируются их амплитуды, после чего сумма делится на количество отсчетов и получаем среднее арифметическое (см. формулу 2):
SA = (Ui + … + Ui-1) / n; (2)
где: SA – математическое ожидание; n – количество отсчетов в выборке; (Ui + … + Ui-1) – сумма отсчетов младших битов отсчетов в выборке.

Дисперсия – это мера рассеяния случайных величин. Определяется как разница между среднеквадратичным отклонением и математическим ожиданием (см. формулу 3):
D = ((Ui^2 + … + Ui-1^2) / n) - SA; (3)
где: D – дисперсия смещения; SA – математическое ожидание; n – количество отсчетов в выборке; (Ui^2 + … + Ui-1^2) – сумма квадратов отсчетов младших битов отсчетов в выборке.

На основании вышеизложенного, уже можем сформировать основные требования к нашему аппаратно-программному ГСЧ:
  • доступ к данным аудиоустройства по-умолчанию и выделение данных («шумящих битов») с последующим накоплением;
  • возможность определения в реальном времени характера получаемого распределения в выборке;
  • возможность задания произвольного размера буфера для накопления данных;
  • определение коэффициента ассиметрии и остроты пика в выборке;
  • возможность сохранения выборки в файл для последующего оффлайн-анализа.
Разработка ПО и средства отладки

Для работы нам понадобится следующее:
  1. IDE среда TurboDelphi-Lite (для некоммерческих разработок) [8];
  2. Наличие аудиокарты (любой);
  3. Библиотека 'dtmfw' разработки автора (для некоммерческого использования скомпилирована под IDE Delphi 2010 и TurboDelphi-Lite over BDS-2006, см. ресурсы к проекту [9]).
Рассмотрим основные моменты реализации доступа к данным и алгоритма их анализа REALTIME. Прежде всего определим размер динамического массива ГСЧ 'buf_noise' равным 50 000 бит (по большому счету, лучше 200 000 бит, но время накопления растянется на секунд 10). Младший «шумящий» бит в выборке получим путем умножения младшего байта на маску $01. Накопление младших байтов в динамическом массиве будем отключать по переполнению глобального счетчика прямо в событии WaveInProc2() получения аудиоданных, тут же будет производится передача накопленных данных в процедуру анализа статистических данных Statistic(). Для сохранения выборки в файл и скорости работы воспользуемся классом TFileStream. Реализация подобного подхода приведена в листинге 1.

ЛИСТИНГ-1
// анализатор статистики в выборке

procedure statistic(a,b,w,c,d,p: double; i: integer);

const h=1e-9;

var m1,m2,m3,m4,d1,d2,k,m,l,a1,e,u3,u4, CK: double;

s: string;

begin

m1:=a/i;

m2:=b/i;

m3:=c/i;

m4:=d/i;



d1:= m2 - m1;

d2:= d1*i/(i-1);

k := h + m3 - (3*m1*m2) + (2*m1*m1*m1);

w := m1 * m1;

l := h + m4 - (4*m1*m3) + (6*w*m2) - (3*w*w);

try

a1:= k / (h+power(d1, 3/2));

e := l / (h+(d1*d1)) - 3;

u3:= sqrt(abs(6*(i-1)/((i+1)*(i+3))));

u4:= sqrt(abs(24*(i-2)*(i-3)/(i+3)/(i+5)/((i-1)*(i-1))));

except end;



// распределение

if ((a1<u3/2)and(e<u4/2)) then s:= 'Распределение: нормальное'

else s:= 'Распределение: ассимметричное';



// критерий сериальной корреляции

CK:= ((i*p) - (a*a))/ ((i*b)-(a*a));



stat.sa := format('Cреднее арифметическое: %.2n', [m1]);

stat.dispers_sm:= format('Дисперсия смещ.: %.2n', [d1]);

stat.disters_ne := format('Дисперсия несм.: %.2n', [d2]);

stat.koef_asim := format('Коэффициент ассиметрии: %.2n', [a1]);

stat.pic := format('Острота пика: %.2n', [e]);

stat.crit_serial_correlation:= format('Критерий сериальной корреляции: %.2n', [CK]);

stat.raspred := s

end;




// событие получения аудиоданных

procedure TDTMF.waveInProc2(var Msg: TMessage);

var i,k,maxi : integer;

p : PByte;

cntval : double;

temp, recorded: integer;


Stream : TFileStream;

begin

maxi:= 0;



if (adr2.dwFlags = WHDR_PREPARED + WHDR_DONE) and (adr2.dwBytesRecorded > 1) then begin



if stp then begin

setlength(inwav.dy, 0);

setlength(outwav.dy, 0);

setlength(spektr.dx, 0);

setlength(spektr.dy, 0);



// уровень сигнала с устройства записи по-умолчанию

p:= PByte(adr2.lpData);

// набиваем-

for i:= 0 to adr2.dwBytesRecorded {2048} - 1 do begin

temp:= (p^-128);


// ГСЧ --------------------------------------------------------------------

setlength(tinrand.dy, length(tinrand.dy)+1);

// выделяем младший байт и из него младший бит

tinrand.dy[length(tinrand.dy)-1]:= lo(temp) and $01;



// накопление

s_a:= s_a + temp;

s_b:= s_b + temp*temp;

s_w:= power(temp, 3);

s_c:= s_c + s_w;

s_d:= s_d + s_w * temp;



// критерий сериальной корреляции (по Кнуту, частный случай)

// C = (n * (Un*Un+1 + ... Un-1*Uo) + (Uo + ... Un-1)^2 ) / (n* (Uo^2 + ...Un-1^2) - (Uo + ... Un-1)^2)

// (Uo + ... Un-1) = s_a

// (Uo^2 + ...Un-1^2) = s_b

// (Un*Un+1 + ... Un-1*Uo) = s_p

s_p := temp* s_pred + s_p;

s_pred:= temp;

if length(tinrand.dy) = 1 then s_pred0:= temp;



// отключение накопления

if length(tinrand.dy) = buf_noise then begin

s_p:= temp* s_pred0 + s_p;



statistic(s_a, s_b, s_w, s_c, s_d, s_p, buf_noise);

s_a:= 0; s_b:= 0; s_w:= 0; s_c:= 0; s_d:= 0; s_p:= 0; s_pred:= 0; s_pred0:= 0;



// архивирование и дозапись

if buf_save then begin

if fileexists(fmp3dir + 'test.dat') then Stream:= TFileStream.Create(fmp3dir +  'test.dat', fmOpenReadWrite)

else Stream:= TFileStream.Create(fmp3dir + 'test.dat', fmCreate);

Stream.Seek(0, soFromEnd);

try

Stream.WriteBuffer(Pointer(tinrand.dy)^, Length(tinrand.dy));

finally

FreeAndNil(Stream);

end;

end;



// передаем данные в событие вывода статистики

if Assigned(FOnGenRandom_NoiseSoundCard) then

FOnGenRandom_NoiseSoundCard(self,

stat.sa,

stat.dispers_sm,

stat.disters_ne,

stat.koef_asim,

stat.pic,

stat.raspred,

stat.crit_serial_correlation,

tinrand);

setlength(tinrand.dy, 0);

end;

// end ГСЧ ----------------------------------------------------------------



// инкрементируем указатель на следующий отсчет

Inc(p);

end;

GLVAL:= Round(maxi*100/128);



// спектр без привязки

FFTQuad(fcntpp);

// спектр с привязкой и DTMF декодер + определение среднего уровня шума

cntval:= header.nSamplesPerSec {44100}*header.nChannels / (2*length(outwav.dy));

FFTDTMF(cntval);


end;

//-----------------------------------

waveInAddBuffer(hwi2, @adr2, SizeOf(WaveHdr));

end

end;
Для получения среднего уровня шума немножко перепишем процедуру определения DTMF частот FFTDTMF() (см. ресурсы к статье). Для этого необходимо выяснить центральную гармонику по максимальному уровню среди всех отсчетов в спектре и вычесть ее амплитуду из суммы амплитуд всех остальных гармоник, после чего разделить на количество гармоник в спектре (см. листинг 2).

ЛИСТИНГ-2
// спектр с привязкой и DTMF декодер +

// определение среднего уровня шума

procedure TDTMF.FFTDTMF(cntval: double);

var a,f,azero, fzero, noise: double;

i: integer;

begin

noise:= 0;



a1:= -1000;

for i:= 0 to length(outwav.dy)-1 do begin //

a:= outwav.dy[i];

f:= i * cntval;

setlength(spektr.dx, length(spektr.dx)+1);

setlength(spektr.dy, length(spektr.dy)+1);



if ff_cut then begin

if ((a>0) or (a=0)) then begin

spektr.dx[length(spektr.dx)-1]:= f;

spektr.dy[length(spektr.dy)-1]:= a;



// накопление - средний уровень шума

noise:= noise + a;

end else begin

spektr.dx[length(spektr.dx)-1]:= f;

spektr.dy[length(spektr.dy)-1]:= 0;

end;

end else begin

spektr.dx[length(spektr.dx)-1]:= f;

spektr.dy[length(spektr.dy)-1]:= a;



// накопление

noise:= noise + a;

end;



// определение 1-й частоты DTMF

if a > a1 then begin a1:= a; f1:= f end;

if a1= -1 then a1:= 0

end;



a2:= -1;

for i:= length(outwav.dy)-1 downto 0 do begin

a:= outwav.dy[i];

f:= i * cntval;

if (a > a2)and(a<>a1) then begin a2:= a; f2:= f end; //частота для 2-

if a2= -1 then a2:= 0;

end;



// средний уровень шума

gl_noise:= (noise - max(a1, a2))/(length(outwav.dy)-1);

...

end;
Вот в принципе и все модификации, которые потребовалось осуществить в коде библиотеки 'DTMFW'. Библиотека обеспечивает следующий функционал:
  1. Кодирование (генерацию) и декодирование двухтональных сигналов (DTMF) realtime (с аудиокарты) и offtime (из файлов WAV/MP3).
  2. Спектроанализ (с использованием БПФ) realtime и offtime (из файлов WAV/MP3/SHARC).
  3. Осциллограф realtime и offtime (из файлов WAV/MP3/файлов данных SHARC).
  4. Умножение полученных спектров на окно: прямоугольное (по уровню 0 dB), Хемминга (-54 dB), Блэкмена-Хэрриса (по уровням -61 dB, -67 dB, -92 dB).
  5. Анализ среднего уровня шума в спектре realtime и offtime.
  6. Детекцию амплитуды и частоты основного тона (гармоники) в спектре.
  7. Измерение текущего уровня амплитуды сигнала с устройства записи по-умолчанию.
  8. Детекцию (триггер тишины) превышения порогового уровня сигнала c настраиваемыми пороговым уровнем сигнала и задержкой отключения n [ms], и возможностью записи фрагментов аудио в файл формата WAV PCM.
  9. Аппаратно-программную генерацию случайных чисел (ГСЧ) на основе звуковой карты c возможностью архивации в файл и выдачи выборки данных в реальном времени.
  10. Анализ статистики распределения выборки данных ГСЧ realtime.
  11. Генерацию синусоидального сигнала с задаваемыми частотой и скважностью.
Внешние свойства и методы библиотеки'DTMFW' представлены в таблице.

Таблица. Внешние свойства и методы библиотеки'DTMFW'


Рассмотрим пример динамического подключения библиотеки к своему проекту в средах Delphi 6/7/2006/2009/2010/XE или TurboDelphi-Lite (см. листинг 3):

ЛИСТИНГ-3
// пример динамического подключения библиотеки 'DTMFW'

uses dtmfw;



public

procedure DTMF1GenRandom_NoiseSoundCard_Data(Sender:TObject;

sa,

dispers_sm,

disters_ne,

koef_asim,

pic,

crit_serial_correlation,

raspred: string;

series: TBSeries);

end;





var DTMF1 : TDTMF;



{ инициализация }



begin

DTMF1:= TDTMF.Create(nil);

dtmf1.GenRandom_NoiseSoundCard_Data:= DTMF1GenRandom_NoiseSoundCard_Data;

...



{ деинициализация }



begin

dtmf1.free;

...



// выдача характеристик по накопленному дампу ГСЧ realtime

// со звуковой карты с анализатора

// и самих данных ГСЧ (при желании)



TStat = record

sa, // cреднее арифметическое

dispers_sm, // дисперсия смещ.

disters_ne, // дисперсия несм.

koef_asim, // коэффициент ассиметрии

pic, // острота пика

crit_serial_correlation, // критерий сериальной корреляции - Д.Кнут

raspred: string; // тип распределения в дампе

end;



procedure TForm1.DTMF1GenRandom_NoiseSoundCard_Data(Sender:TObject;

sa, dispers_sm, disters_ne, koef_asim, pic, crit_serial_correlation, raspred: string;

series: TBSeries);

var i: integer;

begin

if rb3.Checked then begin

memo1.Clear;



memo1.Lines.Add(sa);

memo1.Lines.Add(dispers_sm);

memo1.Lines.Add(disters_ne);

memo1.Lines.Add(koef_asim);

memo1.Lines.Add(pic);

memo1.Lines.Add(crit_serial_correlation);

memo1.Lines.Add(raspred);

memo1.Lines.Add(format('Количество отсчетов c аудиокарты: %d',

  [length(series.dy)]));

end

...



// задание размера буфера для накопления ГСЧ

procedure TForm1.spChange(Sender: TObject);

begin

dtmf1.GenRandom_NoiseSoundCard_BufSize:= 50000

...



// активация режима сохранения накопленных дампов с ГСЧ в файл

procedure TForm1.CheckBox3Click(Sender: TObject);

begin

dtmf1.GenRandom_NoiseSoundCard_SaveToFile:= checkbox3.Checked

...
Порядок использования библиотеки
  1. Для корректной работы генератора синуса не рекомендуется изменять его частоту быстрее установленного буфера аудиоданных (API WAVEFORM). При необходимости, генератор может выдавать одиночные импульсы с требуемой длительностью и паузой, т.е. регулируемой скважностью.
  2. Отслеживание основного тона в сигнале необходимо, к примеру, для обнаружения сигналов с определенной частотой в общем фоне.
  3. Запись в аудиофайл формата WAV PCM речевых фрагментов при срабатывании триггера тишины (превышении порога) осуществляется в режиме REALTIME (в режиме анализа сигналов OFFTIME детектирование не производится).
  4. Кроме отсечки отрицательной амплитуды сигнала в спектре, также имеется возможность введения уставки дли снижения уровня шума при визуализации, при анализе среднего уровня шума по спектру эта уставка игнорируется (выдаются реальные данные в dB).
Тестирование ГСЧ

Проведем предварительное тестирование ГСЧ в режиме реального времени по параметрам дисперсий, критерия сериальной корреляции и закона распределения в получаемых данных (напомним, что данный анализатор мы встроили программно выше). Запустим проект на выполнение и активируем режим «ГСЧ». После чего в системном микшере будем выбирать микрофонный или линейный вход для получения данных (см. рисунки 2...4):

Рис. 2. Проверка ГСЧ с включенным микрофонным входом и постукиванием по микрофону

Рис. 3. Проверка ГСЧ с отключенным микрофонным входом

Рис. 4. Проверка ГСЧ с закороченным линейным входом

Активировав птичку 'Save ГСЧ', проведем накопление данных в течении нескольких секунд (запись тишины) на 50 000 бит, по-умолчанию это будет файл с именем 'test.dat'. Если открыть его в блокноте и выбрать режим 16-тиричного представления данных, то увидим сплошные «нолики и единички» (см. рисунок 5):

Рис. 5. Файл выборки с «шумящими битами»

Для проверки характера распределения этих «ноликов и единичек» проведем дополнительное тестирование с помощью внешней утилиты ENT. Для этого через «Пуск/Выполнить/CMD» откроем консоль командной строки и напишем следующую команду:
ent test.dat 1>c:\1.txt
При этом, файл выборки 'test.dat' будет передан для анализа утилите, а результат анализа будет сохранен на диске 'С:' в файле '1.txt' параллельно с выводом на экран (см. рисунок 6):
Entropy = 0.998680 bits per byte.

Optimum compression would reduce the size
of this 300000 byte file by 87 percent.

Chi square distribution for 300000 samples is 38170233.13, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 0.4786 (127.5 = random).
Monte Carlo value for Pi is 4.000000000 (error 27.32 percent).
Serial correlation coefficient is 0.466250 (totally uncorrelated = 0.0).
Рис. 6. Анализ статистики выборки утилитой ENT

Как видите, показатель энтропии близок к единице, что и требовалось от ГСЧ. Видео-обзор данного тестирования в полном объеме вы найдете на канале нашей лаборатории, присоединяйтесь.


Постскриптум

Исходные тексты и компиляция проекта аппаратно-программного ГСЧ, утилиты ENT с данными анализа (файл gsn_res.zip) вы можете загрузить с сайта нашего журнала (раздел «Программы»), а также с сайта автора. Если тема представляет для вас интерес пишите, задавайте вопросы.

Ресурсы
  1. Е.Бадло, С.Бадло. Виртуальные приборы. DTMF. Спектроанализатор своими руками. – Радиолюбитель, Минск, 2009, 3, с.32-36
  2. С.Бадло. БПФ. Практика использования. Часть 2. – ПРОграммист, международный, 2010, №1, с.33-43
  3. С.Бадло. БПФ. Практика использования. Часть 1. – ПРОграммист, международный, 2010, №8, с.46-59
  4. В.Песошин, Р.Мансуров, В.Кузнецов. Комбинированный генератор случайных чисел // Вероятностные методы и кибернетика.– КГУ, Казань, 1982, вып.19.
  5. О.Дапин. Анализ и синтез генераторов псевдослучайных чисел // Методы и средства статистического моделирования. – КАИ, Казань, 1987.
  6. ENT. Тест Pseudorandom Number Sequence Test Program http://www.fourmilab.ch/random/random.zip
  7. Д. Кнут. Искусство программирования, том 2. Получисленные методы. Изд. дом «Вильямс», Москва, 2007.
  8. IDE TurboDelphi-Lite (для некоммерческих разработок) http://www.andyaska.com/?act=download&mode=get&id=34
  9. Ресурсы к проекту аппаратно-программного ГСЧ http://raxp.radioliga.com/cnt/s.php?p=gsn_res.zip
  10. Видеоролик тестирования аппаратно-программного ГСЧ на канале LaboratotyW на YOUTUBE http://www.youtube.com/watch?v=JQNYe2JE0zM

Комментариев нет:

Отправить комментарий

В комментариях уважайте собеседника, внимательно читайте посты и не додумывайте. Просьбы и предложения из разряда: «можно ваш Skype/Viber/телефон», «напишите мне в vk/FB», а также другие им подобные — игнорируются. Выход новых версий ПО, внешняя ссылка, переставшая работать с течением времени и т.п. не является основанием для претензий. Желающие спокойно подискутировать и высказаться — Welcome. Желающие спонсировать блог — Donate. Нарушение этих простых правил ведет к бану и удалению комментариев без предупреждения.