[Ψηφιακά Φίλτρα] Απορίες σε ασκήσεις 2019

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[12:00-13:30]

Η γραμματεία είναι ανοιχτή καθημερινά 12:00-13:30

[leukosaraphs!]

Τότε γιατί αναφέρει το αρχείο στην άσκηση? Σε μπερδεύει :Ρ Τι εννοείς σε κάθε βήμα θα βγάζες τον fft? Εγώ βρήκα αυτόν τον αλγόριθμο: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
που μοιάζει στην δομή με τον τρόπο που έχουν οριστεί τα steps στην άσκηση, απλά δεν καταλαβαίνω γιατί το w στο δίνει σαν όρισμα σε κάθε βήμα. Μου φαίνεται στο 3ο πως χρειάζεται μόνο, το οποίο θα καλεί τα προηγούμενα. Άμα θες στείλε pm να το συζητήσουμε :Ρ

γιατι το ειχε απο περυσι και ξεχασε να το βγαλει :Ρ.

η ασκηση θελει να μας βαλει να σκεφτουμε πως οταν γραφουμε μια αποδειξη εχουμε το matlab να μας προσεχει.

ξεκινας απο μια σχεση (αναλυτικη σχεση fft) και σε καθε step γραφεις μια ισοτητα που θα πρεπει να δινει το αρχικο αποτελεσμα (aka τον fft). Ο αλγοριθμος που βρηκες ειναι μια αρχη για να σκεφτεις πως θα σπασεις τα αθροισματα.

[koniotis]

γιατι το ειχε απο περυσι και ξεχασε να το βγαλει :Ρ.

η ασκηση θελει να μας βαλει να σκεφτουμε πως οταν γραφουμε μια αποδειξη εχουμε το matlab να μας προσεχει.

ξεκινας απο μια σχεση (αναλυτικη σχεση fft) και σε καθε step γραφεις μια ισοτητα που θα πρεπει να δινει το αρχικο αποτελεσμα (aka τον fft). Ο αλγοριθμος που βρηκες ειναι μια αρχη για να σκεφτεις πως θα σπασεις τα αθροισματα.

Άνθρωπος κι αυτός, ξεχνάει :Ρ

Dear matlab watch over me please

Μάλλον εννοείς ξεκινάς από μια αναλυτική σχέση για τον dft, τον οποίο σε κάθε step τον χωρίζεις σε αθροίσματα για να πετύχεις εν τέλει τον πιο γρήγορο υπολογισμό του (τον fft δηλαδή) από άποψη πολυπλοκότητας. Σε κάθε βήμα του αλγορίθμου θα συγκρίνεις τον fft που φτιάχνεις με αυτόν που προκύπτει από το matlab ώστε να δεις αν το κάνεις σωστά.Έτσι σε προσέχει το matlab και γι αυτό σου δίνεται το w σαν όρισμα σε κάθε step. Right?

[leukosaraphs!]

Άνθρωπος κι αυτός, ξεχνάει :Ρ

Dear matlab watch over me please

Μάλλον εννοείς ξεκινάς από μια αναλυτική σχέση για τον dft, τον οποίο σε κάθε step τον χωρίζεις σε αθροίσματα για να πετύχεις εν τέλει τον πιο γρήγορο υπολογισμό του (τον fft δηλαδή) από άποψη πολυπλοκότητας. Σε κάθε βήμα του αλγορίθμου θα συγκρίνεις τον fft που φτιάχνεις με αυτόν που προκύπτει από το matlab ώστε να δεις αν το κάνεις σωστά.Έτσι σε προσέχει το matlab και γι αυτό σου δίνεται το w σαν όρισμα σε κάθε step. Right?

ναι. Ουσιαστικα τα step συνδεονται μεταξυ τους (οχι σαν κλησεις συναρτησεων, αλλα σαν λογικη).

[koniotis]

ναι. Ουσιαστικα τα step συνδεονται μεταξυ τους (οχι σαν κλησεις συναρτησεων, αλλα σαν λογικη).

Ωραίος μαν, θενκς. Ξέρεις μήπως μέχρι τι μέγεθος μπορεί να είναι το σφάλμα του norm(y - fft(x))? :Ρ

[leukosaraphs!]

ο Φλώρος από ότι μίλησα ελέγχει έως 10^(-10)...
εγώ πετυχαίνω 10^(-14)

sent from mTHMMY 

[koniotis]

ο Φλώρος από ότι μίλησα ελέγχει έως 10^(-10)...
εγώ πετυχαίνω 10^(-14)

sent from mTHMMY 

Οκ, θενκς και παλι! 

[feoudarxhs]

Στη step2() τα επιστρεφόμενα vectors με τι πρόσημα τα θέλει; Δηλαδή να υπακούν σε yt = yte - yto ή για παράδειγμα το yto να έχει ήδη αλλαγμένα τα πρόσημα ώστε να ισχύει yt = yte + yto;

Επίσης, στη step3() με βάση το σχόλιο που έχει στον κώδικα φαίνεται πως το xk2 το θέλει αφού πολλαπλασιαστεί με το διάνυσμα με τα ω. Όμως, στο pdf με τις εκφωνήσεις των προηγούμενων χρόνων (τότε που δινόταν το fftproof.m) ουσιαστικά όριζε ως xk1 και xk2 μόνο τους DFT του κάτω και άνω τμήματος, κάτι που είναι επίσης λογικό από άποψη απόδειξης. Όντως το άλλαξε πλέον ή είναι λάθος το σχόλιο;

Τέλος, ως top vector να φανταστώ πως εννοεί από N/2 έως N-1 και ως bottom vector από 0 ως Ν/2-1;

[A Caster]

Στη step2() τα επιστρεφόμενα vectors με τι πρόσημα τα θέλει; Δηλαδή να υπακούν σε yt = yte - yto ή για παράδειγμα το yto να έχει ήδη αλλαγμένα τα πρόσημα ώστε να ισχύει yt = yte + yto;

Επίσης, στη step3() με βάση το σχόλιο που έχει στον κώδικα φαίνεται πως το xk2 το θέλει αφού πολλαπλασιαστεί με το διάνυσμα με τα ω. Όμως, στο pdf με τις εκφωνήσεις των προηγούμενων χρόνων (τότε που δινόταν το fftproof.m) ουσιαστικά όριζε ως xk1 και xk2 μόνο τους DFT του κάτω και άνω τμήματος, κάτι που είναι επίσης λογικό από άποψη απόδειξης. Όντως το άλλαξε πλέον ή είναι λάθος το σχόλιο;

Τέλος, ως top vector να φανταστώ πως εννοεί από N/2 έως N-1 και ως bottom vector από 0 ως Ν/2-1;

1) Ως top vector θέλει από 0 έως Ν/2-1 και bot το υπόλοιπο. Δηλαδή fft = [yt;yb] στο ματλαμπ

2)  στο τρίτο θέλει το αποτέλεσμα να είναι: yt=   Xk1 + xk2 , yb = xk1 - xk2. Το xk1 είναι τα even και το xk2 είναι Wk*Xodd

3) στο δεύτερο θέλει: yt = yte + yto, yb= ybe + ybo

[feoudarxhs]

1) Ως top vector θέλει από 0 έως Ν/2-1 και bot το υπόλοιπο. Δηλαδή fft = [yt;yb] στο ματλαμπ

2)  στο τρίτο θέλει το αποτέλεσμα να είναι: yt=   Xk1 + xk2 , yb = xk1 - xk2. Το xk1 είναι τα even και το xk2 είναι Wk*Xodd

3) στο δεύτερο θέλει: yt = yte + yto, yb= ybe + ybo

Οκ ευχαριστώ πολύ! Είναι ακριβώς έτσι τα πρόσημα. Πάντως ξαναλέω πως δεν είναι για κανένα λόγο προφανής η μορφή που αναμένει ο tester και μπορούν να υπάρξουν πάρα πολλές διαφορετικές υλοποιήσεις ακριβώς του ίδιου πράγματος. Είχε αναφέρει στο μάθημα τι αναμένει η δική του υλοποίηση;

[Ap.Mor.]

3) στο δεύτερο θέλει: yt = yte + yto, yb= ybe + ybo

Το yte και το yto είναι n/2. Δε θα έπρεπε να είναι n/4 ώστε το άθροισμα να γίνει n/2 (όπως κάνει ο αλγόριθμος του Tukey )?
Υπάρχει κάπου η ακριβής απόδειξη που πρέπει να υλοποιήσουμε;
Πολύ μπέρδεμααααα! 

[koniotis]

Το yte και το yto είναι n/2. Δε θα έπρεπε να είναι n/4 ώστε το άθροισμα να γίνει n/2 (όπως κάνει ο αλγόριθμος του Tukey )?
Υπάρχει κάπου η ακριβής απόδειξη που πρέπει να υλοποιήσουμε;
Πολύ μπέρδεμααααα! 

Σκέψου ότι για να γίνει σωστά ένας DFT (στην προκειμένη περίπτωση ο fft) χρειάζεσαι όλα τα στοιχεία του διακριτού σου σήματος x(δηλαδή n στοιχεία), οπότε τα yte, yto (αντίστοιχα και τα ybe,ybo) πρέπει να λαμβάνουν υπόψην όλα τα n στοιχεία του x όταν προκύψει το άθροισμα yte + yto, άρα θα έχει το καθένα n/2 στοιχεία x. Τα yte και yto ορίζονται με n/2 μέγεθος γιατί αντιστοιχούν στα πρώτα n/2 στοιχεία του FFT. Δεν σπας δηλαδή το άθροισμα των στοιχείων x με ζυγούς δείκτες σε 2 επιμέρους αθροίσματα με n/4 στοιχεία x το καθένα. Σε νοιάζει μόνο το πού ανήκει το συγκεκριμένο στοιχείο του fft(πάνω ή κατω), δεν σπας το άθροισμα περαιτέρω δηλαδή, σπάς τον πίνακα y απλά. Τα yte, yto και ybe,ybo διαφέρουν μόνο στο σε ποια στοιχεία του FFT αναφέρονται, όχι του x. Γενικά, ξεχώρισε τους δείκτες του x και του y στο άθροισμα για να καταλάβεις, είναι λίγο μπέρδεμα η αλήθεια είναι δεδομένου κι ότι η εκφώνηση δεν είναι πολύ κατατοπιστική. Ελπίζω να βοήθησα

Ακολούθα τον Tukey

[00128419]

Εχει ασχοληθει κανεις με το δευτερο ερωτημα; πως γινεται να επαληθευσουμε την τιμη των flops?

[leukosaraphs!]

Εχει ασχοληθει κανεις με το δευτερο ερωτημα; πως γινεται να επαληθευσουμε την τιμη των flops?

για μεγεθος σηματος x , n=8, πρεπει να βγαλεις 120.

[Ap.Mor.]

...
Ακολούθα τον Tukey

Για ποιον αλγόριθμο του tukey λες;
Για τον αλγόριθμο decimation in frequency όταν κάνει το διαχωρισμό στο τελικό σήμα το κάνει σε ολόκληρο το αποτέλεσμα σε odd και even.
Εμάς εδώ μας λέει ότι βγάζουμε από τον dft του top και του bottom odd και even. (κάπως κουλό μου φαίνεται δηλαδή αυτό που ζητάει σε σχέση με τον dif fft.)
τα steps στην απόδειξη είναι βήματα κάποιας αναδρομικής διαδικασίας;
Πραγματικά έχω μπερδευτεί. Δε μπορώ να καταλάβω τι θέλει!

[koniotis]

Για ποιον αλγόριθμο του tukey λες;
Για τον αλγόριθμο decimation in frequency όταν κάνει το διαχωρισμό στο τελικό σήμα το κάνει σε ολόκληρο το αποτέλεσμα σε odd και even.
Εμάς εδώ μας λέει ότι βγάζουμε από τον dft του top και του bottom odd και even. (κάπως κουλό μου φαίνεται δηλαδή αυτό που ζητάει σε σχέση με τον dif fft.)
τα steps στην απόδειξη είναι βήματα κάποιας αναδρομικής διαδικασίας;
Πραγματικά έχω μπερδευτεί. Δε μπορώ να καταλάβω τι θέλει!

Για τον radix-2 dit (decimation in time) λέω. Αυτό πρέπει να κάνεις εν τέλει.
Στο 1ο κομμάτι τα βήματα είναι απλά για να σε βοηθήσουν να σκεφτείς πώς θα το κάνεις. Δεν καλείς προηγούμενα βήματα σε επόμενα, δηλαδή είναι ανεξάρτητα. Τώρα στο 2ο κομμάτι δεν ξέρω ακόμα τι παίζει, δεν έχω ασχοληθεί. Εκεί χρειάζεται αναδρομή αλλά δεν ξέρω τι αναδρομή ακριβώς.
Ουσιαστικά σου ζητάει:
1ο βήμα: Βρες τον dft αφού πρώτα τον σπάσεις σε πάνω και κάτω τμήματα (αυτό το κάνει για να καταλάβεις στο βήμα 3 ότι μπορείς να βρεις τα y(j+n/2) με χρήση των y(j)).
2ο βήμα: Βρες τον dft αφού πρώτα τον σπάσεις σε αθροίσματα με δείκτες για το x ζυγούς και μονούς αντίστοιχα, ενώ παράλληλα να σπάσεις τον dft σε πάνω και κάτω. Θα μπορούσε εδώ να σου πει σπάσε απλά τον dft σε μονά ζυγά, απλά για να βάλει και τη λογική του πάνω - κάτω σου λέει γράψε ξεχωριστά τις ίδιες στην ουσία σχέσεις(αλλάζεις μόνο τα j στα w) για τα y(j) και για τα y(j+n/2) όπου j = 0,...,n/2-1, με τα κατάλληλα j (τα j αναφέρονται στο y, όχι στο x). Μπερδεύει αρκετά η εκφώνηση, ισχύει.
3ο βήμα: Βρες επιτέλους τον fft χρησιμοποιώντας μόνο τις πρώτες n/2 τιμές του fft (εδώ κάνεις χρήση των μονών-ζυγών ουσιαστικά και της λογικής πάνω-κάτω "σωστά"). Το βήμα 3 είναι το βελτιωμένο βήμα 2 ας το πούμε .