Генератор псевдослучайных чисел

Лабораторный практикум

«Случайные процессы в задачах обработки и защиты информации»

 

 

Выполнил: аспирант Федотов А.А.

Лабораторная работа 1

Генератор псевдослучайных чисел

 

 

Цель работы

 

Разработка программного генератора псевдослучайных чисел (ГСПЧ) с использованием конгруэнтного метода.

 

Задания к работе

1. Изучите мультипликативный конгруэнтный метод построения ГСПЧ и рекомендации по выбору его параметров. Выберите в соответствии с этими рекомендациями значения параметров ГСПЧ.

2. Напишите программу для вычисления и вывода n чисел, порожденных генератором. В программе должна быть реализована функция выбора длины псевдослучайной последовательности (выбор n). Также, в программу должно быть включено сравнение с функцией random() построением графика функции r(n), где r – псевдослучайное число, n – номер числа.

3. Оценить полученный результат визуально на графике r(n) в сравнении с графиком функции random(). Результат должен быть схожим при одинаковом размере выборки.

 

Содержание отчета о работе:

1. цель работы

2. формулы генерации псевдослучайных чисел (для выбранных значений )

3. скриншоты, отражающие сравнение вашей функции r(x) и random(x) на графиках

4. скриншоты, содержащие сгенерированную псевдослучайную последовательность в текстовом виде (не менее 20 чисел).

5. Полный листинг программы

 

Рекомендации по выполнению лабораторной работы

 

Пример программы-генератора и сравнение со встроенной функцией С++ random() изображен на рис. 1

 

Рис. 1 Конгруэнтный генератор и сравнение его работы с функцией random(x)/x

Для построения графиков необходимо использовать компонент Chart, поместив его на форму:

Затем добавить сам график двойным кликом мыши на установленном объекте и в открывшемся окне нажать Add, выбрав тип графика Point, галочку 3D убрать.

 

Перейти на вкладку Series и установить следующие параметры для графика:

Далее, Создать объекты Button, Memo, Edit, Label, чтобы привести программу к виду на рис 1.

 

Каждое последующее случайное число рассчитывается на основе предыдущего случайного числа по следующей формуле:

= mod(k · + b, M).

M — модуль (0 < M);

k — множитель (0 ≤ k < M);

b — приращение (0 ≤ b < M);

r0 — начальное значение (0 ≤ r0 < M).

 

По этой формуле генерируются псевдослучайные целые числа. Для приведения их к виду с плавающей запятой от 0 до 1 (X), следует разделить на M:

X= /M;

В языке программирования C++ существует функция, позволяющая генерировать псевдослучайные последовательности чисел по равномерному закону распределения. Такой функцией является random(x); где x – максимальное возможное значение псевдослучайного числа, например, функция random(10); генерирует число, имеющее возможные значения в интервале [0,10]. Данная функция генерирует только целочисленные значения.

Циклический вызов данной функции позволяет сгенерировать необходимую псевдослучайную последовательность, например конструкция:

for (int i=0;i<10;i++)

Series2->AddXY(i,(double)random(10000)/10000);

строит на графике псевдослучайную последовательность из 10 чисел, имеющих значения от 0 до 1. Деление на 10000 производится для того, чтобы привести целые числа, выводимые функцией random() к типу с плавающей запятой (по аналогии с делением на M). Данная функция является аналогом той, которую создаем в данной лабораторной работе, поэтому ее удобно использовать для проверки корректности работы.

По нажатию кнопки программа должна начать генерацию любого количества чисел, указанного пользователем, для этого необходимо кликнуть 2 раза на объекте Button1 и вписать код в открывшуюся конструкцию. Считывание числа N из компоненты Edit1 следует следующим образом:

N=StrToFloat(Edit1->Text); // преобразование строки в численное значение

Остаток от деления находится в С++ следующим образом:

a=b%c; // a,b,c – переменные типа long

Выводить числа последовательно в компоненту Memo необходимо следующим образом:

Memo1->Lines->Add (ri); // ri – ваше псевдослучайное число

Их отображение удобно делать сразу следующей строкой для сравнения с функцией random на втором графике:

Series1->AddXY(i,ri);

Series2->AddXY(i,(double)random(10000)/10000);

Лабораторная работа 2

Анализ качества ГСПЧ

Цель работы

 

Анализ равномерности распределения и статистической независимости чисел на выходе ГСПЧ.

 

Проверка длины периода

Поскольку последовательность чисел на выходе мультипликативного конгруэнтного ГСПЧ периодическая, она не может характеризоваться равномерным распределением и независимостью чисел в строгом смысле, но при большой длине l периода этот недостаток не приводит к ошибкам более существенным, чем, скажем, ограниченная длина разрядной сетки ЭВМ.

Выявление периода последовательности или, что то же самое, в последовательности и определение его длины l – непростая задача, поскольку некоторое число первых членов последовательности может и не принадлежать его периодической части.

Определенную информацию о периодичности можно получить, если запомнить и в процессе генерации выборки последовательно сравнивать с ним числа , i=2,3,…,n. При первом совпадении определяется длина периода l = i-1. Если для совпадения не произошло, то либо , либо периодическая часть последовательности начинается при i > 1.

 

Контрольные вопросы

1. Как по выборке случайной величины рассчитываются оценки ее м.о. и дисперсия?

2. Как проверяется равномерность распределения чисел с помощью частотного теста?

3. Как проверяется статистическая независимость чисел на выходе ГСПЧ?

 

Задания к работе

1. Изучите способы анализа равномерности распределения и независимости чисел на выходе ГСПЧ.

2. Дополните программу из лабораторной работы №1 следующим функционалом:

- тестирование равномерности распределения ГСПЧ частотным методом разбиения на 10 интервалов (построить два графика , для n=100 и n=10000, где - частота встречаемости случайной величины на i-интервале);

- проверка равномерности распределения нахождением м.о. и дисперсии по формулам (6) и (7) (для n=100 и n=10000);

- (дополнительно, по усмотрению студента) проверка статистической независимости по формуле (8). Построить график Rg(n), для n от 10 до 1000;

3. По рассчитанным оценкам сделайте вывод о пригодности ГСПЧ. Если ГСПЧ не пригоден, подберите для него более подходящие параметры a,m.

 

Содержание отчета о работе

1. Цель работы;

2. формулы для расчета статистических оценок, применяемых для анализа качества ГСПЧ;

3. результаты расчета оценок (скриншоты), показывающие в графическом виде зависимость этих оценок от длины n выборки;

4. вывод о пригодности ГСПЧ для его использования в статистическом моделировании.

5. листинг программы

 

Рекомендации по выполнению лабораторной работы

 

Для выполнения данной работы следует обратиться к программе, написанной в лабораторной работе №1 и добавить в программу функции, соответствующие данной работе.

 

1. Откройте проект с программой в C++ Builder 6 (лабораторная работа №1);

2. Добавьте на форму объект PageControl с вкладки Win32:

 

 

3. Нажмите правой кнопкой мыши на данном объекте и выберите пункт NewPage (для создания двух вкладок – 2 клика);

4. Растяните данный объект по размеру формы приложения, оставив свободное место для него перемещением имеющихся объектов в любое свободное пространство на форме;

 

5. Переместите все существующие объекты на объект PageControl использованием выделения и копированием их у буфер обмена сочетанием клавиш ctrl+x и вставкой в PageControl с помощью ctrl+c. Переименуйте вкладки TabSheet1 и TabSheet2 в «Генерация чисел» и «Проверка генератора» соответственно (для этого кликните по объекту PageControl и слева, в object tree view выберите TabSheet1, переименуйте его в параметре Caption окна Object Inspector на «Генерация чисел»).

 

6. Последующие работы будут добавляться наращиванием функционала данной программы добавлением новых вкладок;

7. Перейдите на вкладку «Проверка генератора» и установите 3 новых объекта Chart с добавлением в каждый из них по одному графику Series. Дайте название каждому из графиков как указано на изображении (двойной клик на объекте Chart, на вкладке Titles)

 

8. Графики будут соответствовать следующим результатам: первые 2 графика для проверки частотным методом. Один график – зависимость частоты встречаемости случайной величины на каждом из интервалов разбиения, от номера интервала для N=100, другой – для N=10000. Третий график будет соответствовать зависимости коэффициента корреляции Rg от N (N следует брать от 10 до 10000).

 

9. Добавьте на форму кнопку Button, в поле caption дайте ей название («Начать тестирование ГСПЧ»). Добавьте 2 компонента Memo:

 

10. Вам необходимо на кнопку «Начать тестирование ГСПЧ» назначить необходимые действия для заполнения всех трех графиков.

11. Первым, что должна выполнить программа – сгенерировать первые 100 псевдослучайных чисел. Код можете скопировать с кнопки, генерирующей числа из первой лабораторной работы в кнопку «Начать тестирование ГСПЧ», но с изменением одного параметра – генерация фиксированного количества чисел, равному 100.

12. Код необходимо модифицировать так, чтобы сгенерированные числа записывались в массив. Инициализация массива на 100 чисел в С++ выглядит следующим образом:

float A[100];

13. По нажатию кнопки заполнение массива псевдослучайными числами можно реализовать следующим образом:

…

for (int i=0;i<100;i++)

{

//Здесь вы генерируете случайное число Х с помощью кода из лаб.№1//

A[i]= X; // присваиваем i-му элементу массива значение Х

}

….

14. Проверьте, правильно ли заполнился массив A[i] выводом его содержимого в компонент Memo:

for (int i=0;i<100;i++)

Memo2->Lines->Add(A[i]);

15. Следующий этап – подсчет количества случайных величин в интервалы равной длины, составляющие всю сгенерированную последовательность. Разобьем последовательность на 10 интервалов: 0-0,1; 0,1-0,2; 0,2-0,3; 0,3-0,4; 0,4-0,5; 0,5-0,6; 0,6-0,7; 0,7-0,8; 0.8-0,9; 0,9-1,0. Реализация подсчета числа попавших чисел в интервалы может быть получена путем нахождения целого числа от умножения элемента A[i] (случайная величина) на 10 и прибавлением единицы. Например, если случайное число «0,25» умножить на 10 и отбросить дробную часть, то мы получим число 2, добавив единицу, получим номер интервала, равный 3 (действительно, 0,25 находится в интервале 0,2-0,3). Для проверки правильности подсчета, установите еще один компонент Memo и выводите в него значения номеров интервалов. Проинициализировав новый массив B[10], содержащий информацию о каждом из интервалов, можно реализовать подсчет случайных чисел в каждом из интервалов следующим образом (выделение целой части можно сделать указанием (int) перед выводом числа):

for (int i=0;i<100;i++)

{

Memo2->Lines->Add(A[i]); //выводим случайную величину

buff=A[i]*10+1; // определяем номер интервала, которому она принадлежит

Memo3->Lines->Add((int)buff); //выводим номер этого интервала

B[(int)buff]+=1; //добавляем к счетчику единицу

}

случайная величина номер интервала

16. В массиве B[i] у нас теперь подсчитано количество попавших чисел для каждого из интервалов. Выведем на первый график значения из массива B:

for (int i=0;i<10;i++)

Series4->AddXY(i,B[i]/100); // отношение попавших в интервал значений к общему их числу(определение fi)

17. Сделаем копию блока кода для N=100 и поместим его следующим за текущим.

18. В скопированном блоке внесем изменения, которые позволят генерировать 10000 значений и подсчитывать их число в каждом из десяти интервалов (заменим в циклах 100 на 10000).

19. Отобразим на втором графике частоты встречаемости случайных величин на каждом из 10 интервалов:

 

 

20. Как видим, при переходе к N=10000 частотная составляющая приближается к вероятности попадания на каждый из интервалов, а именно: 1/k=0,1.

21. поместим на форму 4 компонента Edit для вывода значений м.о. и дисперсии для N=100 и N=10000

 

 

22. Найдем значения м.о. для N=100 и N=10000 по формуле (6). Выводить полученные значения необходимо следующим образом:

Edit9->Text=Mx; // Mx – найденное м.о. для 100 чисел, Edit может быть у вас под другим номером

Edit10->Text=Mx;// найденное м.о. для 10000 чисел, Edit может быть у вас под другим номером

23. Сгенерируйте несколько выборок и следите за получаемыми значениями Mx. Для N=10000 они должны быть ближе к 0,5, чем при N=100.

24. В остальные 2 поля выводите значения дисперсии для N=100 и N=10000 по формуле (7).

 

25. Значение дисперсии с ростом N должно стремиться к 0,83333333 (1/12) и быть ближе к нему у выборки с N=10000.

26. (дополнительно, по усмотрению студента) Рассчитайте значение Rg корреляции между парами чисел из выборки (g взять равным единице) при N от 10 до 1000 (генерируем 10 чисел, считаем Rg по формуле (8), выводим это значение на график, потом генерируем 11 чисел, считаем Rg и выводим на график, потом 12, 13 чисел и т.д. до 1000). Полученная кривая должна отражать приближение коэффициента корреляции Rg к нулю с ростом N:

 

27. Подпишите оси на вкладке Axis каждого из графиков как указано на рисунке:

Лабораторная работа 3

Цель работы

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

 

Краткие сведения из теории

1. Общая схема реализации случайных величин

Случайная величина (сл.в.) с заданным законом распределения вероятностей всегда может быть получена путем подходящего преобразования стандартного случайного числа. При моделировании на ЭВМ такое подходящее преобразование выполняется над стандартным псевдослучайным числом и в результате получается псевдослучайная величина с требуемым распределением.

2. Метод обращения

Методом обращения можно получить сл.в. x с любой функцией распределения вероятностей (ф.р.в.) имеющей обратную функцию . Метод обращения сводится к тому, чтобы сгенерировать стандартное случайное число z и вычислить x по формуле

(10)

Тогда сл.в. х будет иметь распределение .

Если на «вход» формулы (10) подавать последовательность стандартных случайных чисел, то на «выходе» получится последовательность независимых сл.в., имеющих ф.р.в. .

Для конкретной ф.р.в. F выражение обратной функции можно получить известным из школьного курса математики способом, состоящим в разрешении уравнения относительно x.

Докажем метод обращения. Пусть F – некоторая ф.р.в. Тогда F – монотонно неубывающая функция, принимающая значения в интервале [0,1]. Пусть она имеет обратную функцию . Определим х через стандартную сл.в. z в виде и найдем ф.р.в. сл.в. х. По определению (P – вероятность). Но . Таким образом, , что и требовалось.

В качестве примера рассмотрим использование метода обращения для реализации экспоненциальной сл.в.

 

3. Реализация экспоненциальной сл.в. методом обращения

Ф.р.в. экспоненциальной сл.в. имеет вид:

(11)

Отсюда

В соответствии с методом обращения запишем уравнение или, с учетом (11)

и, решая его относительно найдем формулу для генерации сл.в.

(12)

В полученной формуле разность 1-z, как и сама величина z, является стандартным случайным числом. Этот факт позволяет упростить формулу для генерации , полагая

(13)

Назовем экспоненциальную сл.в. с м.о., равным единице, нормированной и обозначим через . Тогда для u=1 и для генерации можно использовать формулу

(14)

3. Применение линейных преобразований

Под линейным преобразованием (ЛП) сл.в. х будем понимать сл.в. y, полученную из х умножением на константу A и добавлением константы B:

Очевидно,

,

(15)

При построении генераторов сл.в. часто используется свойство ЛП y сохранять вид закона распределения сл.в. х. Так, например, если экспоненциальную сл.в. умножить на константу, то получится снова экспоненциальная сл.в. Нормальная или равномерно распределенная сл.в. не меняет вида закона распределения как при умножении на константу, так и при добавлении константы.

Генератор (14) нормированной экспоненциальной сл.в. достаточен для реализации экспоненциальных сл.в. с любыми м.о. . Для получения экспоненциальной сл.в. с м.о. M достаточно вычислить ее в виде .

Сл.в. , являющаяся ЛП стандартной сл.в. z, имет равномерное распределение на интервале (B,A+B) и, в соответствии с (15), имеет , .

4. Реализация нормальной сл.в. методом суммирования

Плотность распределения вероятностей нормальной сл.в. х с м.о. M и дисперсией имеет вид:

(16)

Соответствующая ф.р.в

Не выражается в элементарных функциях, что затрудняет непосредственное использование метода обращения. Поэтому для реализации нормальной сл.в. часто применяют метод суммирования, основанный на центральной предельной теореме теории вероятностей. Из этой теоремы вытекает, что сумма Sn достаточно большого числа n стандартных случайных чисел будет иметь распределение, достаточно близкое к нормальному.

Поскольку м.о. суммы Sn и ее дисперсия равны сумме м.о. и сумме дисперсий ее слагаемых, то . Применим к Sn линейное преобразование, чтобы получить нормированную центрированную сл.в. Х (с м.о. 0 и дисперсией 1). Очевидно для этого надо положить или, заменяя Sn,

(17)

На практике часто принимают n=12, т.к. во-первых, при таком числе слагаемых Х имеет распределение, весьма близкое к нормальному, и, во-вторых, значительно упрощается вид формулы (17). При n=12 из (17) получаем формулу для генерации нормированной центрированной сл.в.

(18)

 

Нормальную сл.в. с м.о. M и дисперсией можно получить из по формуле:

В отличие от метода обращения, метод суммирования является приближенным.

6. Применение функциональных преобразований сл.в.

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

Так, например, эрланговская сл.в., имеющая распределение Эрланга k-го порядка, вводится как сумма k независимых экспоненциальных сл.в. , которые имеют одинаковые м.о.:

(19)

Эту формулу можно непосредственно использовать для генерации при наличии генератора для . Если в (19) суммируются нормированные сл.в. , то, очевидно, ,

Аналогично сл.в. (хи-квадрат), имеющая распределение с k степенями свободы, вводится как сумма k независимых сл.в. , имеющих нормированное центрированное нормальное распределение:

(20)

.

Из (20) ясно, как она может быть реализована при моделировании на ЭВМ.

Распределением Стьюдента с k степенями свободы называют распределение сл.в.

(21)

где - независимые нормированные центрированные нормальные величины.

 

7. Генераторы дискретных сл.в.

Если x – дискретная сл.в., то ее закон распределения вероятностей задается обычно путем указания вероятностей p1,p2… для каждого ее возможного значения x1,x2… соответственно.

Для реализации дискретной сл.в. интервал (0,1) разбивают на подынтервалы имеющие длину . Такое разбиение всегда возможно, поскольку для дискретной сл.в. p1+p2+…=1. Далее сл.в. х может быть сгенерирована по следующему алгоритму:

1. генерируется стандартная сл.в. z;

2. определяется номер i подынтервала , в который попало значение z;

3. принимается

В зависимости от значения z сл.в. х будет принимать различные значения из множества При этом вероятность принять некоторое значение равно, очевидно, вероятности того, что z попадет в подынтервал , т.е. . Следовательно для всех i=1,2,3… Это доказывает, что реализуется сл.в. х с требуемым распределением вероятностей.

При моделировании на ЭВМ вместо стандартной сл.в. z используется псевдослучайное число r. Строится сетка из значений вероятностей в зависимости от подынтервала i, точки которой рассчитываются по формуле:

(22)

Затем генерируется псевдослучайное число r и определяется, в какой интервал оно попало. Очевидно, формула Пуассона подразумевает различные длины интервалов, и в какие-то из них псевдослучайная величина будет попадать чаще, что и позволит построить плотность распределения Пуассона.

Для того, чтобы запрограммировать генерацию чисел по любому закону распределения д.с.в. (в данном случае – Пуассоновский), необходимо:

1. Сгенерировать псевдослучайное число Xi (код можно взять из лаб.1 и 2);

2. После генерации числа, вписать цикл while с условием «пока сгенерированное число Xi больше Pi»;

3. В цикле while рассчитывать значение Pi по формуле (22), с каждым последующим i значение Pi будет расти до тех пор, пока не достигнет Xi;

4. Когда значение Pi превысит сгенерированное число Xi, произойдет выход из цикла;

5. После выхода из цикла while следует зафиксировать последнее значение i (для Pi) и отразить на графике это значение i по горизонтальной оси, и соответствующее ему значение Xi.

6. Повторить пункты 1-5 10000 раз.

 

Аналогично реализуются генераторы других дискретных псевдослучайных величин, например, бернуллиевская сл.в. c распределением вероятностей:

для нее

Либо, геометрическое распределение:

. В данном случае

 

Контрольные вопросы

1. В чем заключается общий принцип реализации случайных (псевдослучайных) величин с заданными законами распределения вероятностей?

2. Как реализуется случайная величина по методу обращения?

3. Как при генерации сл.в. используют линейные преобразования?

4. Как можно реализовать нормальную сл.в.?

5. В каких случаях для реализации сл.в. со сложными законами распределения используются функциональные преобразования сл.в., имеющие более простые распределения?

6. Каким образом можно построить генератор дискретной случайной величины?

Задания к работе

Изучите методы синтеза генераторов сл.в. с заданными законами распределения.

- Напишите программу, реализующую генератор псевдослучайной величины, закон распределения которой указан в табл.1 (для вашего номера варианта), а также генератор чисел, распределенных по закону Пуассона.

 

 

Обеспечьте в программе:

- генерацию n значений псевдослучайной величины (рекомендуется n=10000);

- определение и вывод частот встречаемости случайной величины (плотность распределения) на каждом из интервалов и их последующее сравнение со значениями в табл.2 и 3;

- по результатам сравнения с табличными значениями сделайте вывод о соответствии характера распределения случайных величин требуемому закону распределения. Разница между сгенерированными значениями и табличными не должна превышать 0,1.

Отчет должен содержать:

1. цель работы;

2. закон распределения моделируемой случайной величины (указать вариант, формулы);

3. таблицу для сравнения частот встречаемости сл.в. на каждом из интервалов вашего генератора с данными в табл.2 и 3 (при увеличении выборки N, они должны сходиться к вероятностям, указанным в таблицах).

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

Обратим внимание на данные из таблицы для экспоненциального закона распределения и сравним табличные значения с полученными:

-	.6321	.2325	.0855	.0315	.0116	.0043	.0016	.0006	.0002	.0001
-	.6340	.2280	.0880	.0310	.0100	.0050	.0020	.0000	.0000	.0000

Обратим внимание на данные из таблицы для закона Пуассона и сравним табличные значения с полученными:

.0183	.0733	.1465	.1954	.1954	.1563	.1042	.0595	.0298	.0132	.0053
.0180	.0750	.1420	.1960	.1970	.1520	.1060	.0610	.0330	.0120	-

 

5. вывод о соответствии статистических характеристик реализованной псевдослучайной величины требуемым (разница не должна превышать 0,1).

6. Исходный код программы.

 

 

Вариант	Название распределения вероятностей	Закон распределения	Параметры распределения
1.	Нормальное		M – любое (удобнее брать M>3, чтобы избежать работы с отрицательными числами) D=1
2.	Хи-квадрат с k степенями свободы		k=4
3.	Стьюдента с k степенями свободы		k=4
4.	Экспоненциальное		u=1
5.	Эрланга k-го порядка		k=3 u=1
Для всех	Пуассона		M=4

Табл.1

(-1,0]	(0,1]	(1,2]	(2,3]	(3,4]	(4,5]	(5,6]	(6,7]	(7,8]	(8,9]	(9,10]
Нормальное распределение, M=1, D=1:
.3413	.3413	.1359	.0214	.0013	.00003	-	-	-	-	-
Хи-квадрат:
-	.0902	.1740	.1780	.1518	.1187	.0881	.0633	.0443	.0305	.0207
Стьюдента с 4 степенями свободы:
.3131	.3131	.1288	.0381	.0119	.0044	.0018	.0008	.0004	-	-
Экспоненциальное, u=1:
-	.6321	.2325	.0855	.0315	.0116	.0043	.0016	.0006	.0002	.0001
Эрланга 3 порядка, u=1:
-	.0803	.2430	.2535	.1851	.1135	.0627	.0323	.0159	.0075	.0035

Табл.2

Вероятности значений 0,…,10 дискретных сл.в.
Распределение Пуассона, m=4:
.0183	.0733	.1465	.1954	.1954	.1563	.1042	.0595	.0298	.0132	.0053

Табл.3

Лабораторная работа 4

 

Генератор гармонического сигнала. Преобразование Фурье.

Цель работы

Разработка программного генератора гармонического сигнала заданной частоты с функцией разложения сигнала в спектр с помощью дискретного преобразования Фурье (ДПФ).

Краткие сведения из теории

В основе преобразования Фурье (ПФ) лежит чрезвычайно простая, но исключительно плодотворная идея – почти любую периодическую функцию можно представить суммой отдельных гармонических составляющих (синусоид и косинусоид с различными амплитудами A, периодами Т и, следовательно, частотами ω). Пример одной из таких функций S(t), состоящей из гармоник Сi(t), приведен на рис. 1.

 

Рис. 1. Представление прямоугольного импульса суммой гармонических составляющих

 

Понятия «изобразить в частотной области некую функцию от времени» и «нарисовать спектр этой функции» – равнозначны. Если скользнуть по рис. 1 взглядом по горизонтали слева направо, то свершится переход от какой-либо функции времени к ее спектру. А нижняя часть рисунка есть иллюстрация одного из основных принципов ПФ – спектр суммарной функции времени равен сумме спектров ее гармонических составляющих.

Неоспоримым достоинством ПФ является его гибкость – преобразование может использоваться как для непрерывных функций времени, так и для дискретных. В последнем случае оно называется дискретным ПФ – ДПФ.

Для получения дискретной функции времени надо подвергнуть процессу дискретизации непрерывную функцию времени. Это изображено на рис. 2. Вырезаем отдельные значения из непрерывной функции, выстраивая дискретную функцию времени. Период одного цикла его работы называется «периодом дискретизации», или «интервалом дискретности».

 

Рис. 2. Дискретное представление непрерывной функции

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

, (1)

где - амплитуда, - частота, - фаза

Ещё одно название данного сигнала – монохроматический.

Важность понятия гармонического сигнала объясняется тем, что любой периодический сигнал (например, последовательность прямоугольных или треугольных импульсов) всегда может быть представлен конечной или бесконечной суммой гармонических сигналов – это есть теорема Фурье о разложение в ряды. Само собой разумеется, что каждый гармонический сигнал (гармоника), входящий в сумму имеет свою амплитуду и значение начальной фазы.

Гармонический сигнал конечной длительности (здесь частота 100 кГц). В повседневной практике – это простейший сигнал синусоидальной формы, который выдаёт генератор частоты, то есть сигнал, имеющий длительность много больше периода синусоиды.

 

Исходный сигнал

Спектр сигнала

Пусть у нас есть функция синуса x = sin(t).

Максимальная амплитуда этого колебания равна 1. Если умножить его на некоторый коэффициент A, то получим тот же график, растянутый по вертикали в A раз: x = Asin(t).

 

Период колебания равен 2π. Если мы хотим у