- Nazwa przedmiotu:
- Implementacja algorytmów w reprogramowalnych strukturach FPGA
- Koordynator przedmiotu:
- Piotr Sapiecha
- Status przedmiotu:
- Obowiązkowy
- Poziom kształcenia:
- Studia II stopnia
- Program:
- Telekomunikacja
- Grupa przedmiotów:
- Przedmioty techniczne - zaawansowane
- Kod przedmiotu:
- IMAS
- Semestr nominalny:
- 2 / rok ak. 2015/2016
- Liczba punktów ECTS:
- 5
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- 118
- Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- 2
- Język prowadzenia zajęć:
- polski
- Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
- 1
- Formy zajęć i ich wymiar w semestrze:
-
- Wykład30h
- Ćwiczenia0h
- Laboratorium0h
- Projekt15h
- Lekcje komputerowe0h
- Wymagania wstępne:
- - podstawowe wiadomości z teorii układów logicznych,
- podstawowe wiadomości z algorytmów
- Limit liczby studentów:
- 50
- Cel przedmiotu:
- - zapoznanie i zainteresowanie słuchaczy z zaawansowanymi metodami syntezy logicznej,
- pokazanie szeregu zastosowań omawianych metod, na przykładach projektów: szybkich układów arytmetycznych, układów DSP, układów komutacyjnych,
tablic routingu i filtrów pakietów,
- przedstawienie aparatu matematycznego stosowanego podczas projektowania wymienionych algorytmów i układów.
- Treści kształcenia:
- [1] Wykład wprowadzający.
Motywacje i cele wykładu.
[2-3] Szybkie algorytmy i układy arytmetyczne programowe i sprzętowe
algorytmy dodawania: z szybkim obliczaniem przeniesień,
mnożenia: Karatsuby, na drzewach Wallace’a,
realizacje potokowe.
[4-5] Szybkie algorytmy sortowania programowe i sprzętowe
algorytmy: MergeSort, Quicksort,
i sieci: Bitoniczne i Batchera, zastosowania pola komutacyjne: crossbar, knockout, Banyan.
[6-7] Arytmetyka modularna
, twierdzenia Eulera, Chińskie o resztach
, szyfrowanie RSA i ElGamala.
[8] Szybka transformata Fouriera (FFT),
twierdzenie o splocie, szybkie mnożenie wielomianów, filtry typu FIR, IIR.
[9] Algorytmy faktoryzacji liczb naturalnych - bezpieczeństwo szyfru RSA
, metody: Pollarda, sito kwadratowe.
[10-11] Arytmetyka ciał skończonych,
kody korygujące typu: BCH, Reeda-Salomona, algorytm AES, szyfry na krzywych eliptycznych.
[12-14] Problemy NP-trudne, problem SAT i twierdzenie Stephena Cooka,
algorytmy dokładne i aproksymacyjne,
zastosowania w syntezie logicznej:
redukcja zmiennych wejściowych do układu logicznego,
dekompozycja funkcjonalna układu logicznego.
[15] Budowa tablic routingu typu LC-trie, wyszukiwanie wzorców, algorytmy KMP, KR, filtry Blooma, zastosowania w IDS'ach .
- Metody oceny:
- egzamin pisemny i ustny, projekt, referat, prezentacja
- Egzamin:
- tak
- Literatura:
- [1] Uwe Meyer-Baese, Digital Signal Processing with Field Programmable Gate Arrays
[2] Łuba T.(et al.), Programowalne układy przetwarzania sygnałów i informacji
[3] F. Rodríguez-Henríquez, N.A. Saqib, A. Díaz-Pèrez, and C. K. Koc, Cryptographic Algorithms on Reconfigurable Hardware
- Witryna www przedmiotu:
- http://www.zpt.tele.pw.edu.pl/didactics.html
- Uwagi:
Efekty uczenia się
Profil ogólnoakademicki - wiedza
- Efekt imas_w01
- Sprzętowe systemy IDS Wyszukiwanie wielu wzorców, algorytmy KMP, Aho-Corasica, algorytm KR, filtry Blooma.
Weryfikacja: egzamin, projekt
Powiązane efekty kierunkowe:
K_W01, K_W02, K_W03, K_W04, K_W05, K_W06, K_W07
Powiązane efekty obszarowe:
T2A_W01, T2A_W01, T2A_W02, T2A_W03, T2A_W04, T2A_W07, T2A_W03, T2A_W04, T2A_W03, T2A_W04, T2A_W03, T2A_W04, T2A_W07
Profil ogólnoakademicki - umiejętności
- Efekt imas_u01
- Sprzętowe systemy IDS Wyszukiwanie wielu wzorców, algorytmy KMP, Aho-Corasica, algorytm KR, filtry Blooma.
Weryfikacja: egzamin, projekt
Powiązane efekty kierunkowe:
K_U01, K_U02, K_U03, K_U04, K_U05, K_U06
Powiązane efekty obszarowe:
T2A_U01, T2A_U03, T2A_U04, T2A_U02, T2A_U03, T2A_U04, T2A_U05, T2A_U06, T2A_U02, T2A_U07, T2A_U07, T2A_U09
Profil ogólnoakademicki - kompetencje społeczne
- Efekt imas_k01
- Sprzętowe systemy IDS Wyszukiwanie wielu wzorców, algorytmy KMP, Aho-Corasica, algorytm KR, filtry Blooma.
Weryfikacja: egzamin, projekt
Powiązane efekty kierunkowe:
K_K01, K_K02
Powiązane efekty obszarowe:
T2A_K06, T2A_K07