SZYMON M. WOŹNIAK

Cyfrowe Przetwarzanie Sygnałów

Edycja: Semestr letni 2023/2024.

Spis treści

  1. Cyfrowe Przetwarzanie Sygnałów
  2. Prowadzący
  3. Zajęcia
  4. (Nie)obecność
  5. Wyrównywanie zaległości
  6. Sala laboratoryjna i zasady obowiązujące podczas zajęć
  7. Grupy laboratoryjne
  8. Harmonogram
    1. Harmonogram A
    2. Harmonogram B
  9. Wymagania wstępne
  10. Literatura
    1. Lista
  11. Zasady oceniania
  12. Moduł CPS.jl
  13. Standardowe kolokwium zaliczeniowe
    1. Forma standardowego problemu
  14. Kolokwium rozszerzające
  15. Ogólne zasady pisania kolokwium
  16. Zawody w obliczaniu dyskretnej transformacji Fouriera
    1. Kryterium
    2. Zasady i wymagania
    3. Zgłoszenia
    4. Przydatne informacje i narzędzia
  17. Zaliczenie poprawkowe
  18. Historia zmian

Prowadzący

Prowadzącym ćwiczenia laboratoryjne jest Szymon Woźniak (konsultacje, kontakt).

Zajęcia

Ćwiczenia laboratoryjne są to cotygodniowe zajęcia poświęcone ćwiczeniu rozwiązywania fundamentalnych problemów z przedmiotu cyfrowego przetwarzania sygnałów. Celem ćwiczeń jest nabycie wiedzy, umiejętności oraz biegłości w rozwiązywaniu owych problemów, a produktem ubocznym tych ćwiczeń powinno być stworzenie modułu (bądź paczki, biblioteki) zawierającego programy komputerowe (funkcje) przydatne przy cyfrowym przetwarzaniu sygnałów.

Zajęcia te prowadzę w trybie konsultacyjnym. Oznacza to, że co do zasady w czasie zajęć powinieneś samodzielnie opracowywać rozwiązania wybranych problemów. Natomiast ja jako prowadzący, który jest obecny w czasie zajęć, mogę Ci pomóc jeżeli zgłosisz taką chęć. Pomoc w głównej mierzę oferuję w postaci dyskusji nad problemem, ale także w postaci wyjaśnienia i doprecyzowania problemu, czy też zweryfikowania poprawności rozwiązania. Od razu zwrócę tutaj uwagę, że problemy (zadania) na zajęciach będą postawione przed Tobą i to Ty jako uczestnik zajęć powinieneś dojść do rozwiązań. Nie należy się spodziewać, że ja jako prowadzący będę prezentował gotowe rozwiązania tych problemów. W końcu to Ty się tutaj pojawiłeś, żeby poćwiczyć. :)

Na początku każdych zajęć będę wypisywał rekomendowane problemy, od których dobrze jest zacząć. A następnie będę proponował kolejne w zależności od tempa pracy grupy lub indywidualnie. Co do zasady masz dowolność w wyborze problemów, kolejności ich wykonywania, oraz tempie, w której będziesz je rozwiązywał. Nie ma żadnych przeciwwskazań, żeby sobie ustalić swój własny harmonogram pracy w ramach tych zajęć. Natomiast w harmonogramie zajęć będzie sugerowana szybkość realizowania materiału laboratoryjnego składająca się także z literatury do przestudiowania. Jeżeli nie wiesz, co robić w czasie zajęć, nie masz pomysłu, który problem powinieneś rozwiązać jako następny, to możesz to zgłosić i postaram się dobrać następne problemy indywidualnie dla Ciebie.

W ramach aktywności na zajęciach możesz się zgłosić, aby omówić wybrany problem, potrzebną teorię do rozwiązania tego problemu, czy też zaprezentować rozwiązanie danego problemu przy tablicy na forum grupy. W czasie pierwszych 12 zajęć można zdobywać tylko plusy (dodatkowe ponadprogramowe punkty) za szeroko pojętą aktywność na rzecz pchania grupy do przodu w czasie zajęć. Zasadnicza część punktów, na podstawie której wystawiana jest ocena końcowe z ćwiczeń laboratoryjnych, zdobywana jest pod koniec semestru poprzez przesłanie zaimplementowanego przez semestr modułu CPS.jl oraz dwa kolokwia. Więcej informacji na temat oceniania znajdziesz w sekcji Zasady oceniana.

W ramach zajęć trwają też zawody w obliczaniu dyskretnej transformacji Fouriera, w których autorzy najszybszych implementacji otrzymają dodatkowe punkty.

(Nie)obecność

Obecność na zajęciach laboratoryjnych jest co do zasady obowiązkowa i będę ją sprawdzał na samym początku zajęć. Jeżeli się spóźnisz na zajęcia, to przypomnij mi, żebym odnotował Twoją obecności, w przeciwnym razie obecność może nie zostać odnotowana.

W przypadku nieobecności na danych zajęciach nie musisz przedstawiać żadnego powodu swojej nieobecności czy też formalnego usprawiedliwienia w jakiejkolwiek postaci. Wręcz jesteś proszony, aby tego nie robić. Powody są różne, a ja jako prowadzący nie jest kompetentny w ich ocenianiu. Proszę samodzielnie ocenić czy dany powód jest istotny, aby nie pojawić się na zajęciach.

Wyrównywanie zaległości

Jeżeli z powodu nieobecności na zajęciach posiadasz zaległości, to Twoim obowiązkiem jest samodzielne wyrównanie tych zaległości.

Sala laboratoryjna i zasady obowiązujące podczas zajęć

Spotkania laboratoryjne odbywają się na kampusie AGH, budynek C-3, sala 310. W sali jest dostępne szesnaście stanowisk komputerowych, w tym jedno dla prowadzącego. Na poniższej mapie zaznaczona jest przybliżona lokalizacja sali laboratoryjnej.

<iframe width="100%" height="250" frameborder="0" scrolling="no" marginheight="0" marginwidth="" src="https://www.openstreetmap.org/export/embed.html?bbox=19.918832480907444%2C50.06506123154253%2C19.92495864629746%2C50.067227152242154&layer=mapnik&marker=50.06614420411814%2C19.921895563602448" style="border: 1px solid black; margin: 0 auto;"></iframe>

Poniżej parę zasad, do których jesteś proszony się stosować w czasie zajęć:

Grupy laboratoryjne

Zajęcia odbywają się co tydzień w każdą środę i czwartek. Możesz uczęszczać tylko i wyłącznie na jedną grupę laboratoryjną. Poniższa tabela zawiera listę wszystkich grup laboratoryjnych w tym semestrze. Zajęcia danej grupy odbywają się przeważnie w przypisanym dniu tygodnia i podanym przedziale czasowym, chyba że organizacja roku na to nie pozwala. Szczegółowa rozpiska zajęć dla danej grupy znajduje się w harmonogramach.

GrupaHarmonogramDzień tygodniaGodzinaIlość stanowiskZajętość
EiT#1BCzwartek13:30 - 15:001512
EiT#2BCzwartek16:45 - 18:151515
EiT#3AŚroda11:30 - 13:001513
EiT#4AŚroda16:45 - 18:151512
EiT#5AŚroda15:00 - 16:301514
EiT#6BCzwartek18:30 - 20:001512
EiT#7BCzwartek15:00 - 16:301513

Harmonogram

Semestr składa się z 19 tygodni i pozwala na realizację wszystkich 14 spotkań laboratoryjnych. Istnieją dwa harmonogramy spotkań laboratoryjnych: A (środowy) oraz B (czwartkowy). Do każdego spotkania laboratoryjnego w harmonogramie jest przypisana informacja dodatkowa, która przeważnie sugeruje główną tematykę danego spotkania.

Dodatkowo następująca notacja została wykorzystana w poniższych tabelach:

Harmonogram A

tydzieńdatanr labinformacja dodatkowa
01~~28.02.2024~~--
0206.03.202401Zajęcia organizacyjne.
0313.03.202402Wstęp do języka programowania Julia.
0420.03.202403Modelowanie sygnałów.
0527.03.202404Próbkowanie i kwantyzacja.
0603.04.202405Obliczania dyskretnej transformacji Fouriera.
0710.04.202406Analiza częstotliwościowa sygnałów dyskretnych.
0817.04.202407Analiza częstotliwościowa sygnałów dyskretnych.
0924.04.202408Dyskretne systemy liniowe.
10~~01.05.2024~~-Dzień ustawowo wolny od zajęć dydaktycznych.
1108.05.202409Dyskretne systemy liniowe.
1215.05.202410Projektowanie filtrów.
1322.05.202411Projektowanie filtrów.
14~~29.05.2024~~-Harmonogram zajęć z piątku.
1505.06.202412Zespoły filtrów.
1612.06.202413Standardowe kolokwium zaliczeniowe.
1719.06.202414Kolokwium rozszerzające.
18~~26.06.2024~~--
19~~03.07.2024~~--

Harmonogram B

tydzieńdatanr labinformacja dodatkowa
01~~29.02.2024~~--
0207.03.202401Zajęcia organizacyjne.
0314.03.202402Wstęp do języka programowania Julia.
0421.03.202403Modelowanie sygnałów.
05~~28.03.2024~~-Wakacje wiosenne.
0604.04.202404Próbkowanie i kwantyzacja.
0711.04.202405Obliczania dyskretnej transformacji Fouriera.
0818.04.202406Analiza częstotliwościowa sygnałów dyskretnych.
0925.04.202407Analiza częstotliwościowa sygnałów dyskretnych.
10~~02.05.2024~~-Dzień dodatkowo wolny od zajęć dydaktycznych.
1109.05.202408Dyskretne systemy liniowe.
1216.05.202409Dyskretne systemy liniowe.
1323.05.202410Projektowanie filtrów.
1428.05.2024 <br /> (wtorek)11Projektowanie filtrów.
14~~30.05.2024~~-Dzień ustawowo wolny od zajęć dydaktycznych. <br /> Zajęcia przeniesione na 28.05.2024 (wtorek).
1506.06.202412Zespoły filtórw.
1613.06.202413Standardowe kolokwium zaliczeniowe.
1720.06.202414Kolokwium rozszerzające.
18~~27.06.2024~~--
19~~04.07.2024~~--

Wymagania wstępne

Ćwiczenia laboratoryjne z Cyfrowego Przetwarzania Sygnałów są zajęciami wymagającymi zasadniczej wiedzy z innych kursów. W szczególności powinno się mieć podstawową wiedzę i umiejętności rozwiązywania problemów z następujących przedmiotów:

Ponadto musisz posiadać dwie niezbędne umiejętność:

Braki w wiedzy lub umiejętnościach przedstawionych powyżej mogą przyczynić się do tego, że opanowanie materiału będzie wymagało większego nakładu pracy i czasu niż zostało to przewidziane.

Literatura

Podstawowymi źródłami wiedzy, z których powinieneś korzystać to literatura w postaci książek poświęconych tematowi cyfrowego przetwarzania sygnałów oraz wykład, który jest prowadzony równolegle z ćwiczeniami laboratoryjnymi. Poniżej znajduje się lista rekomendowanych książek z zakresu podstaw liniowych systemów dyskretnych i cyfrowego przetwarzania sygnałów. Kolejność książek w liście według roku wydania.

\[[BG AGH](https://katalogagh.cyfronet.pl/lib/item?id=chamo:21139)\]

</span>

\[[BG AGH](https://katalogagh.cyfronet.pl/lib/item?id=chamo:97153)\]

</span>

\[[BG AGH](https://katalogagh.cyfronet.pl/lib/item?id=chamo:58450)\]

</span>

\[[BG AGH](https://katalogagh.cyfronet.pl/lib/item?id=chamo:148276)\]

</span>

\[[www](http://teledsp.kt.agh.edu.pl/), [BG AGH](https://katalogagh.cyfronet.pl/lib/item?id=chamo:136282)\]

</span>

\[[web](http://www.fourierandwavelets.org/),[pdf](http://www.fourierandwavelets.org/FSP_v1.1_2014.pdf)\]

</span>

Książka "Cyfrowe przetwarzanie sygnałów: od teorii do zastosowań" autorstwa T. P. Zieliński jest sugerowana jako źródło wiedzy pierwszego wyboru. Szczegółowe wykazy rozdziałów do przeczytania przez zajęciami, będą opierały się w głównej mierze na rozdziałach z tej książki. Biblioteka AGH zapewnia dostęp do elektronicznej wersji tej książki dla członków biblioteki. Wymaga to jedynie zalogowania się do systemu biblioteki. Bezpośredni adres www, pod którym dostępna jest książka, znajduje się pod tym >odnośnikiem<.

Lista

W poniższej liście znajdują się sugerowane rozdziały/sekcje/artykuły, z którymi powinieneś się zapoznać. Niektóre z nich są w ramach przypomnienia materiału.

\[[pdf](https://www.analog.com/media/en/training-seminars/tutorials/MT-001.pdf)\]

.

Zasady oceniania

W ramach ćwiczeń laboratoryjnych zastosowano standardową uniwersytecką skalę ocen, zaczynając od 2,0 jako oceny niedostatecznej, przez ocenę dostateczną 3,0, aż do bardzo dobrej 5,0. Progresja pomiędzy oceną 3.0 a oceną 5.0 to 0,5, która stopniowo oznacza osiągi studenta od zadowalających do bardzo dobrych. Zasady oceniania przyjęte dla tych ćwiczeń laboratoryjnych kładą w głównej mierze nacisk na zdobytą wiedzę z przedmiotu oraz umiejętności rozwiązywania problemów z dziedziny cyfrowego przetwarzania sygnałów. Ową wiedzą i umiejętnościami będziesz musiał się wykazać pod koniec semestru podczas dwóch kolokwiów. Pierwszym kolokwium jest Standardowe Kolokwium Zaliczeniowe, które to będzie sprawdzać najbardziej podstawowe umiejętności i wiedzę z naciskiem na umiejętności praktyczne. Drugim kolokwium jest Kolokwium rozszerzające, które rozszerza zakres materiału w stosunku do Standardowego Kolokwium Zaliczeniowego oraz ma ono charakter ogólnoakademicki. Pod koniec semestru będziesz też musiał oddać kod źródłowy modułu CPS.jl implementujący podstawowe funkcje biblioteki do cyfrowego przetwarzania sygnałów, którą to zaimplementowałeś w ciągu semestru. Poniżej znajduje się tabela ze składowymi współczynnika \( \sigma \) na podstawie których zostanie wystawiona ocena końcowa z ćwiczeń laboratoryjnych.

\(i\)Składowe oceny\(\psi_i\)\( \Omega_i \)
1Modul CPS.jl\( 0.10 \)\( 50.0 \)
2Standardowe Kolokwium Zaliczeniowe\( 0.50 \)\( 5.0 \)
3Kolokwium rozszerzające\( 0.40 \)\( 5.0 \)
-\(\sum_{i} \psi_i\)\( 1.00 \)-

Udział \(i\)-tej składowej we współczynniku \(\sigma\) dany jest przez zmienną \(\psi_i\) (waga składowej). Natomiast, maksymalna ilość punktów, którą można otrzymać w semestrze w ramach \(i\)-tej składowej, jest określona przez zmienną \(\Omega_i\). Współczynnik oceny końcowej z ćwiczeń laboratoryjnych \(\sigma\) jest obliczany jako część całkowita przeskalowanej ważonej średniej arytmetycznej składowych współczynnika. Dokładny wzór, z którego obliczany jest współczynnik \(\sigma\) prezentuje się następująco:

\[ \sigma = \left\lfloor 100 \cdot \left( \sum_{i=1}^{3} \frac{\omega_i}{\Omega_i} \cdot{} \psi_i \right) \cdot \left( \sum_{i=1}^{3} \psi_i \right)^{-1} \right\rfloor + \Gamma (p) , \]

gdzie \( \lfloor x \rfloor = \max \\{ k \in \mathbb{Z} : k \leq x \\} \), a \( \omega_i \) oznacza ilość punktów, którą uzyskałeś w ramach \(i\)-tej składowej. Dodatkowo w czasie zajęć można uzyskać plusy za szeroko rozumianą aktywność. Plusy przeliczają się na dodatek do współczynnika \(\sigma\) jako \(\Gamma (p)\), gdzie \(p \in \mathbb{N}\) to liczba plusów otrzymanych w ciągu semestru, a \(\Gamma : \mathbb{N} \rightarrow \mathbb{R}_+\) to niemalejąca funkcja. Krzywa funkcja \(\Gamma\) zostanie ustalona pod koniec semestru na podstawie statystyki przydzielonych plusów we wszystkich grupach. Końcowa ocena z ćwiczeń laboratoryjnych jest bezpośrednio zdeterminowana przez współczynnik oceny \(\sigma\). Poniższa tabela przedstawia zależność między współczynnikiem oceny \(\sigma\) a końcową oceną z ćwiczeń laboratoryjnych.

\(j\)PrzedziałOcena końcowa
1\( \sigma \in (-\infty, 50) \)\( \Longrightarrow \)2.0
2\( \sigma \in \[50, 60) \)\( \Longrightarrow \)3.0
3\( \sigma \in \[60, 70) \)\( \Longrightarrow \)3.5
4\( \sigma \in \[70, 80) \)\( \Longrightarrow \)4.0
5\( \sigma \in \[80, 90) \)\( \Longrightarrow \)4.5
6\( \sigma \in \[90, +\infty) \)\( \Longrightarrow \)5.0

Skal ocen według regulaminu studiów AGH (§ 13. SKALA OCEN).

Moduł CPS.jl

Moduł CPS.jl, to zbiór przydatnych programów komputerowych (funkcji), realizujących obliczenia często wykonywanych operacji w cyfrowym przetwarzaniu sygnałów. Twoim pobocznym zadaniem, a właściwe produktem ubocznym powstałym wskutek rozwiązywania problemów laboratoryjnych, będzie właśnie stworzenie takie modułu w języku programowania Julia.

Struktura tego modułu, to znaczy, nazwy funkcji, argumenty tych funkcji oraz to co te funkcje zwracają, będzie zdefiniowane w niektórych problemach, które będziesz mógł rozwiązać. Istotną kwestią jest to, żeby zachować narzuconą strukturę i jej nie zmieniać ze względu, że Twoje implementacje będą oceniane automatycznie pod koniec semestru.

Spis funkcji podlegających ocenie zostanie opublikowany w późniejszym terminie.

Modułu CPS.jl, który udało Ci się przygotować przez semestr, można przesyłać do oceny przez UPEL, do końca dnia 11.06.2024.

Standardowe kolokwium zaliczeniowe

Standardowe kolokwium zaliczeniowe (SKZ) jest to kolokwium, które ma za zadanie sprawdzić wiedzę oraz umiejętności biegłego rozwiązywania problemów z cyfrowego przetwarzania sygnałów w zakresie podstawowym. Przez zakres podstawowy należy rozumieć pewien elementarny podzbiór wszystkich możliwych problemów. SKZ kładzie nacisk na proste problemy praktyczne i składa się w całości z zadań obliczeniowych, które trzeba wykonać poprzez napisanie programu komputerowego, który oblicza odpowiedź na podstawie danych wejściowych.

Jak sama nazwa wskazuje, kolokwium opisują dwa przymiotniki: standardowe i zaliczeniowe. Przez przymiotnik standardowe należy rozumieć dwie rzeczy. Po pierwsze, wszystkie problemy na SKZ, które trzeba będzie rozwiązać, mają zawsze taką samą formę. A oznacza to, że składają się z następujących elementów:

Po drugie zbiór problemów, które mogą wystąpić na SKZ jest jawny. Przez przymiotnik zaliczeniowe należy rozumieć, że poprzez napisanie tego kolokwium na 5 punktów, można uzyskać zaliczenia laboratorium, to znaczy uzyskać współczynnik \(\sigma = 50\), który to przekłada się na dostateczną (3,0) ocenę końcową z laboratorium. Co do zasady każda osoba otrzymująca zaliczenie, powinna uzyskać 5 punktów za SKZ.

SKZ będzie składać się z 6 losowych problemów, które będzie trzeba wykonać w czasie 40 minut. Czas przewidziany na rozwiązanie każdego problem to 5 minut, plus 10 minut czasu dodatkowego na wszelki wypadek. Za każde poprawne rozwiązanie \(k\)-tego problemu zdobywa się \(z_k = 1\) punktów, natomiast za niepoprawne rozwiązanie \(z_k = 0\) punktów. Końcowa ilość punktów \(\omega_2\), którą można uzyskać w ramach SKZ, oblicza się przez następującą zależność

\[ \omega_2 = \max \left(\thinspace\thinspace\sum_{k=1}^{6} z_k, \thinspace\thinspace 5 \right). \]

Forma standardowego problemu

Jak będzie mniej więcej wyglądała forma standardowego problemu na SKZ? Rozważmy to na przykładowym problemie, który brzmi następująco:

Dany jest wektor \(\mathbf{x} \in \mathbb{R}^N\). Oblicz sumę elementów wektora \(\mathbf{x}\) podniesionych do potęgi \(n \in \mathbb{N}\). Odpowiedź podaj dla następujących wartości wejściowych: <center>x = [0.0, 1.0, 2.0, 3.5, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0]</center> <center>n = 5</center>

Mając taki problem, należy zauważyć, że występują w nim dwie nazwane zmienne: x oraz n. Program komputerowy należy zaimplementować w postaci funkcji o nazwie rozwiazanie_k, gdzie k to numer problemu. Załóżmy na potrzeby przykładu ze k = 1. Funkcja powinna przyjmować argumenty poprzez słowa kluczowe, które to powinny nazywać się tak jak zostały nazwane w treści problemu oraz przyjmować wartości domyślne równe wartością, dla których trzeba podać odpowiedź.

Przykładowe program rozwiązujący ten problem w języku Julia:

function rozwiazanie_1(;
    x = [0.0, 1.0, 2.0, 3.5, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0],
    n = 5,
)
    return sum(x .^ n)
end

Natomiast odpowiedzą jest liczba 221107,21875 otrzymana przez wywołanie funkcji rozwiazanie_1().

Aby otrzymać punkt za rozwiązanie danego zadania, należy:

  1. Udzielić prawidłowej odpowiedzi.

  2. Funkcja obliczająca rozwiązanie musi zwracać udzieloną odpowiedź dla domyślnych argumentów.

  3. Funkcja obliczająca rozwiązanie musi zwracać prawidłowe rozwiązania dla argumentów wejściowych o innych wartościach.

Kolokwium rozszerzające

Kolokwium rozszerzające jest to kolokwium, które ma za zadanie sprawdzić wiedzę oraz umiejętności biegłego rozwiązywania problemów z cyfrowego przetwarzania sygnałów w zakresie rozszerzonym. Przez zakres rozszerzony należy rozumieć zbiór problemów i zadań z dziedziny cyfrowego przetwarzania sygnałów, które można rozwiązać w oparciu o wiedzę wchodzącą w zakres laboratorium, a uzyskaną poprzez studiowanie literatury oraz rozwiązywanie problemów. Kolokwium rozszerzające zasadniczo składa się wyłącznie z zadań otwartych. Typy problemów, które będą mogły się pojawić na kolokwium to opisowe, obliczeniowe, wykaż, wyprowadź i udowodnij.

Jako że przystąpienie do kolokwium rozszerzające nie jest koniecznie do uzyskania zaliczenia z ćwiczeń laboratoryjnych, to będzie trzeba się na nie zapisać. Zapisy odbędą się po ogłoszeniu wyników ze standardowego kolokwium zaliczeniowego. Wraz z zainteresowanymi osobami zostanie ustalony dokładny termin kiedy kolokwium się odbędzie. Domyślnie jest to ostatni (siedemnasty) tydzień zajęć semestru według harmonogramu zajęć.

Ogólne zasady pisania kolokwium

Podczas kolokwium będziesz miał do dyspozycji treść problemów, które należy rozwiązać, kartkę papieru, kopię dozwolonych materiałów pomocniczych, oraz komputer na którym będziesz mógł wykonać niezbędne obliczenia. Na kolokwium powinieneś przyjść z długopisem i legitymacją studencką (lub innym dokumentem potwierdzającym twoją tożsamość). Kolokwium należy rozwiązać samodzielnie, bez pomocy osób trzecich. W czasie trwania kolokwium nie można przy sobie posiadać innych przedmiotów niż wymienione wcześniej, ani żadnych innych niedozwolonych materiałów pomocniczych. Komputer może zostać wykorzystany tylko i wyłącznie do rozwiązania kolokwium. Natomiast, komputer nie może być wykorzystany jako narzędzie do przeglądania niedozwolonych materiałów pomocniczych, komunikacji z osobami trzecimi, lub innych czynności. Jedynymi dozwolonymi programami, które mogą być uruchomione na komputerze w czasie trwania kolokwium, to przeglądarka internetowa oraz edytor tekstu z interpreterem/kompilatorem, bądź zintegrowane środowisko programistyczne. Inne uruchomione programy, będą traktowane jako korzystanie z niedozwolonych materiałów pomocniczych. Podczas kolokwium, w edytorze można stworzyć tylko i wyłącznie jedne pusty plik, w którym zapiszesz swoje rozwiąznaia. Otwieranie innych plików jest niedozwolone i traktowane jako korzystanie z niedozwolonych materiałów pomocniczych. W przeglądarce stron internetowych można mieć otwarte tylko i wyłącznie zakładkę zawierającą treść kolokwium oraz dozwolone materiały pomocniczne. Otwieranie innych stron internetowych jest niedozwolone i traktowane jako korzystanie z niedozwolonych materiałów pomocniczych. Jeżeli nie zastosujesz się do tych zasad, możesz otrzymać ocenę końcową nzal z zajęć. Jedynym dozwolonym materiałem pomocnicznym w czasie trwania kolokwium jest książka "Cyfrowe przetwarzanie sygnałów : od teorii do zastosowań", autorstwa T. P. Zielińskiego. W czasie trwania kolokwium będziesz miał dostęp do kopii tej książki. Korzystanie ze swojej kopii książki jest niedozwolone i traktowane jako korzystanie z niedozwolonych materiałów pomocnicnzych.

Uwaga, korzystanie z dokumentacji języka lub bibliotek/paczek jest dozwolone tylko i wyłącznie z poziomu zintegrowane środowisko programistyczne w którym pracujesz. Otwieranie np. strony internetowej z dokumentacją będzie traktowana jako korzystanie z niedozwoonych materiałów pomocniczych.

Jako rezultat swojej pracy w czasie kolokwium będziesz musiał zdać:

Zawody w obliczaniu dyskretnej transformacji Fouriera

Zawody polegają na napisaniu kodu źródłowego funkcji fft, która obliczy \(N\)-punktową dyskretną transformacje Fouriera (dwustronne widmo częstotliwościowe) dla \( x \in \mathbb{C}^N\), gdzie \( N \in \mathbb{N}^+ \). Wygrywa ten, kto stworzy najszybszą implementację, czyli funkcję, która zwraca poprawny wyniki w jak najkrótszym czasie. Autorzy trzech najszybszych programów otrzymają dodatkowe punkty do współczynnika oceny końcowej \(\sigma\) według poniższej tabeli.

MiejsceBonus
1\(\sigma + 10.0\)
2\(\sigma + 5.0\)
3\(\sigma + 2.5\)

Kryterium

Dla każdego zgłoszonego programu zostanie oszacowana liczba \(N_{\max} \in \mathbb{N}^+\), która będzie określać szybkość danego programu. Im większa liczba \(N_{\max}\), tym dany program jest szybszy. Liczba \(N_{\max}\) dla danego programu zostanie oszacowana jako rozwiązanie następującego problemu,

\[ N_{\max} = \argmax_{N \in \mathbb{N}^+} N \quad \text{pod warunkiem, że} \quad \sum_{n = 1}^{N} \min_i (T_{n,i}) \leq T_{\text{limit}}, \]

gdzie \(T_{n,i}\) to \(i\)-ty czas trwania obliczania \(n\)-punktowej dyskretnej transformacji Fouriera z wykorzystaniem danego programu dla losowego zespolonego sygnału o długości \(n\), a \(T_{\text{limit}} = 0.1\) to limit na łączny czas obliczeniowy. W przypadku otrzymania dwóch takich samych wartości liczby \(N_{\max}\) dla dwóch różnych programów, zostanie przeprowadzona dodatkowe testy z zwiększona wartością \(T_{\text{limit}}\). Jeżeli zwiększenie limitu na łączny czas obliczeniowy nie przyniesie rozstrzygnięcia, to kolejnym wyznacznikiem będzie łączny czas obliczeniowy (mniejszy czas to lepszy wyniki).

Warunkiem koniecznym, aby program uzyskał \(N_{\max} > 0\), jest prawidłowe obliczanie wartości dyskretnego widma częstotliwościowego. W przypadku zwrócenia nieprawidłowych wartości wyjściowych dla badanego wejścia, program otrzymuje \(N_{\max} = 0\). Zwracane przez funkcję wartości, będą porównywane z referencyjną implementacją funkcji fft z modułu FFTW.jl (Fastest Fourier Transform in the West) przy użyciu funkcji isapprox (z biblioteki standardowej Julia) z domyślnymi wartościami argumentów przez słowo kluczowe.

Szacowanie czasów \(T_{n,i}\) dla nadesłanych programów będzie przeprowadzane na komputerach w sali laboratoryjnej z wykorzystaniem Julia v1.10.2.

Zasady i wymagania

  1. Jedna osoba można przesłać tylko jedno zgłoszenie.

  2. Zgłoszenie może być autorstwa tylko jednej osoby.

  3. Zgłoszenie musi być wynikiem samodzielnej pracy autora.

  4. Kod źródłowy funkcji musi być napisany w języku programowania Julia.

  5. Program może korzystać tylko i wyłącznie z jednego procesu i jednego wątku procesora.

  6. Można korzystać tylko i wyłącznie z biblioteki standardowej dostępnej w Julia.

  7. Kod źródłowy programu nie może zajmować więcej niż 128 kilobajtów. Sprowadza się to do tego że w kodzie źródłowym nie można zamieszczać za dużo wcześniej obliczonych wartości liczbowych.

  8. Funkcja fft musi być czysta (bezstanowa), to znaczy, że nie może zapamiętywać stanu między kolejnymi wywołaniami funkcji, czy też korzystać ze zmiennych globalnych.

Zgłoszenia

Zgłoszenie powinno zawierać dwa pliki: FFT.jl oraz algorytm.pdf. Zgłoszenia można nadsyłać do końca dnia 11.06.2024 poprzez UPEL. Zgłoszenie powinno być wysłane jako archiwum zip, w którym znajdują się wspomniane wyżej plik. W pliku algorytm.pdf powinien być dokument zawierający krótki opis przesłanego algorytmu. Do przygotowania dokumentu należy wykorzystać szablon. W pliku FFT.jl powinien znajdować się modułu o nazwie FFT, zawierający informacje o autorze, kod źródłowy funkcji fft oraz ewentualnie funkcje pomocnicze. Szablon pliku FFT.jl poniżej.

module FFT

author = Dict{Symbol, String}(
    :index => "17681830", # Twój numer albumu
    :name  => "Jean Baptiste Joseph Fourier", # Twoje imię i nazwisko
    :email => "transformacja@fourier", # Twój adres poczty elektronicznej AGH
)

# Można dodać inne argumenty wejściowe, ale muszą one mieć wartość domyślną.
# Pierwszy argument pozycyjny musi być wektorem z którego oblicza się DFT.
function fft(x::Vector{ComplexF64})::Vector{ComplexF64}
    missing
end

end

Przydatne informacje i narzędzia

Zaliczenie poprawkowe

Jeżeli nie uda Ci się uzyskać zaliczenia z ćwiczeń laboratoryjnych w terminie podstawowym, przysługuje Ci tylko i wyłącznie jeden termin zaliczenia poprawkowego. Zaliczenie poprawkowe polega na ponownym podejściu do standardowego kolokwium zaliczeniowego.

Dokładana data i harmonogram zaliczenia poprawkowego zostaną ogłoszone pod koniec semestru.

Historia zmian