МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
Інститут КНІТ
Кафедра ПЗ
ЗВІТ
До лабораторної роботи № 3
З дисципліни: “ Цифрова обробка сигналів ”
На тему: “ Дискретне перетворення Фур’є”
Лектор:
Гавриш В.І.
Виконав:
ст. гр. ПЗ-34
Третяков К.В.
Прийняв:
Коцун В.І.
« ____ » ________ 2019 р.
∑= ________________
Львів-2020
Тема: Дискретне перетворення Фур’є
Мета: Розробити комп’ютерну програму для виконання дискретного перетворення Фур’є (ДПФ) та оберненого дискретного перетворення Фур’є (ОДПФ).
Завдання
Реалізувати на мові програмування С++ (за згодою керівника лабораторних занять можна використати іншу мову програмування):
1. Підпрограму (процедуру чи функцію), що виконуватиме обчислення одного ( k -го) члена ряду Фур’є для ДПФ:
a. Студенти з парними номерами: у тригонометричній формі.
b. Студенти з непарними номерами: у експоненціальній формі.
2. Підпрограму (процедуру чи функцію), що обчислюватиме коефіцієнт Фур’є як суму ряду з N членів.
3. Підпрограму (процедуру чи функцію) для обчислення усіх N компонентів ДПФ.
4. При складанні підпрограм оцінювати такі показники:
a. Час обчислення.
b. Кількість операцій (множення, додавання).
5. Головну програму для обчислення ДПФ з довільною вхідною множиною значень сигналу.
6. Передбачити модифікацію підпрограм з п.1-5, що буде обчислювати як пряме ДПФ так і ОДПФ.
Оформити звіт про виконання лабораторної роботи.
Хід роботи
App.py
from utils.reader import read_input_values
from utils.dft import dft, idft, calculate_dft_operation_count, calculate_idft_operation_count
input_values = read_input_values()
print(f"Input values: {input_values}")
print()
dft_output_values = dft(input_values)
print(f"DFT output values: {dft_output_values}")
print(f"DFT operation count: {calculate_dft_operation_count(len(input_values))}")
print()
idft_output_values = idft(dft_output_values)
print(f"IDFT output values: {idft_output_values}")
print(f"IDFT operation count: {calculate_idft_operation_count(len(input_values))}")
reader.py
from typing import List
DEFAULT_VALUES = [0.3536, 0.3536, 0.6464, 1.0607, 0.3536, -1.0607, -1.3536, -0.3536]
def read_input_values() -> List[float]:
if input("Do you want default input values (y/n): ").strip().lower() == 'y':
return DEFAULT_VALUES
print("Write END for finishing writing values")
result = []
while True:
value = input("Enter value: ")
if value.strip() == "END":
break
if is_float(value):
result.append(float(value))
else:
print("Invalid value")
return result
def is_float(val):
try:
num = float(val)
except ValueError:
return False
return True
duration_calculator.py
from typing import Callable
from datetime import datetime
def duration_calculator(func: Callable) -> Callable:
def wrapper(*args, **kwargs):
start = datetime.now()
result = func(*args, **kwargs)
print_duration(start, datetime.now())
return result
return wrapper
def print_duration(start: datetime, end: datetime):
elapsed_time = end - start
print(f"Start at {start}, finished at {end}, elapsed time {elapsed_time.total_seconds()}s")
dft.py
from typing import List, Dict
from math import sin, cos, pi
from utils.complex import Complex
from utils.duration_calculator import duration_calculator
@duration_calculator
def dft(values: List[float]) -> List[Complex]:
result = []
for i in range(len(values)):
value = Complex()
for j in range(len(values)):
value.real += values[j] * cos(2 * pi * i * j / len(values))
value.img -= values[j] * sin(2 * pi * i * j / len(values))
result.append(value)
return result
@duration_calculator
def idft(values: List[Complex]) -> List[float]:
result = []
for i in range(len(values)):
value = 0.0
for j in range(len(values)):
value += (values[j].real * cos(2 * pi * i * j / len(values))) - (values[j].img * sin(2 * pi * i * j / len(values)))
result.append(value / len(values))
return result
def calculate_dft_operation_count(value_count: int) -> Dict:
return {
"+": value_count * value_count,
"-": value_count * value_count,
"*": value_count * value_count * 8,
"/": value_count * value_count * 2,
"sin": value_count * value_count,
"cos": value_count * value_count
}
def calculate_idft_operation_count(value_count: int) -> Dict:
return {
"+": value_count * value_count,
"-": value_count * value_count,
"*": value_count * value_count * 8,
"/": value_count * value_count * 2 + value_count,
"sin": value_count * value_count,
"cos": value_count * value_count
}
Рис.1. Демонстрація роботи програми
Висновок
Виконуючи цю лабораторну роботу, я розробив комп’ютерну програму для виконання дискретного перетворення Фур’є (ДПФ) та оберненого дискретного перетворення Фур’є (ОДПФ).