- 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. 2018/2019
- 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
- Charakterystyka imas_w01
- Kryptograficzne układy sprzętowe Obliczenia w ciałach skończonych, potęgowanie Montgomerego. Algorytmy asymetryczne: Dieffiego-Hellmana i RSA. Algorytmy symetryczne AES.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_W02, K_W03
Powiązane charakterystyki obszarowe:
I.P7S_WG
- Charakterystyka imas_w01
- Tablice routingu Budowa tablic routingu z wykorzystaniem struktur LC-trie.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_W03
Powiązane charakterystyki obszarowe:
I.P7S_WG
- Charakterystyka imas_w01
- Kodery i dekodery Kody korygujące błędy. Kody typu: BCH , Reeda-Salomona, oraz Reeda-Mullera.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_W07
Powiązane charakterystyki obszarowe:
I.P7S_WG
- Charakterystyka imas_w01
- Sprzętowe systemy IDS Wyszukiwanie wielu wzorców, algorytmy KMP, Aho-Corasica, algorytm KR, filtry Blooma.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_W07
Powiązane charakterystyki obszarowe:
I.P7S_WG
- Charakterystyka imas_w01
- Szybkie i potokowe układy arytmetyczne. Technika sum prefiksowych: układy sumujące i odejmujące, komparatory, drzewa Wallace’a, sumator n liczb, układy mnożące, metoda Karaczuby, metoda Newtona, układy dzielące.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_W06, K_W07
Powiązane charakterystyki obszarowe:
I.P7S_WG
- Charakterystyka imas_w01
- Szybkie sieci sortujące Zasada 0/1. Sieci bitoniczne, oraz sieci Batchera typu odd-even.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_W07
Powiązane charakterystyki obszarowe:
I.P7S_WG
- Charakterystyka imas_w01
- Układy sprzętowe realizyjące transformatę FFT oraz filtry Implementacja szybkiej transformaty Fouriera w sprzęcie, zastosowanie twierdzenia o splocie, filtry: implementacja filtrów FIR, IIR, arytmetyka rozproszona.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_W06, K_W07
Powiązane charakterystyki obszarowe:
I.P7S_WG
- Charakterystyka imas_w01
- Pola komutacyjne Pola typu: crossbar, knockout, Banyan, Closa, Sunshine, komutatory współdzielące medium.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_W07
Powiązane charakterystyki obszarowe:
I.P7S_WG
Profil ogólnoakademicki - umiejętności
- Charakterystyka imas_u01
- Pola komutacyjne Pola typu: crossbar, knockout, Banyan, Closa, Sunshine, komutatory współdzielące medium.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_U05
Powiązane charakterystyki obszarowe:
I.P7S_UW
- Charakterystyka imas_u01
- Kryptograficzne układy sprzętowe Obliczenia w ciałach skończonych, potęgowanie Montgomerego. Algorytmy asymetryczne: Dieffiego-Hellmana i RSA. Algorytmy symetryczne AES.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_U01
Powiązane charakterystyki obszarowe:
I.P7S_UK
- Charakterystyka imas_u01
- Tablice routingu Budowa tablic routingu z wykorzystaniem struktur LC-trie.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_U06
Powiązane charakterystyki obszarowe:
III.P7S_UW.1.o, III.P7S_UW.3.o
- Charakterystyka imas_u01
- Kodery i dekodery Kody korygujące błędy. Kody typu: BCH , Reeda-Salomona, oraz Reeda-Mullera.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_U06
Powiązane charakterystyki obszarowe:
III.P7S_UW.3.o
- Charakterystyka imas_u01
- Sprzętowe systemy IDS Wyszukiwanie wielu wzorców, algorytmy KMP, Aho-Corasica, algorytm KR, filtry Blooma.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_U06
Powiązane charakterystyki obszarowe:
III.P7S_UW.3.o
- Charakterystyka imas_u01
- Szybkie i potokowe układy arytmetyczne Technika sum prefiksowych: układy sumujące i odejmujące, komparatory, drzewa Wallace’a, sumator n liczb, układy mnożące, metoda Karaczuby, metoda Newtona, układy dzielące.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_U06
Powiązane charakterystyki obszarowe:
III.P7S_UW.3.o
- Charakterystyka imas_u01
- Szybkie sieci sortujące Zasada 0/1. Sieci bitoniczne, oraz sieci Batchera typu odd-even.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_U06
Powiązane charakterystyki obszarowe:
III.P7S_UW.3.o
- Charakterystyka imas_u01
- Układy sprzętowe realizyjące transformatę FFT oraz filtry Implementacja szybkiej transformaty Fouriera w sprzęcie, zastosowanie twierdzenia o splocie, filtry: implementacja filtrów FIR, IIR, arytmetyka rozproszona.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_U06
Powiązane charakterystyki obszarowe:
III.P7S_UW.1.o, III.P7S_UW.3.o
Profil ogólnoakademicki - kompetencje społeczne
- Charakterystyka imas_k01
- Kodery i dekodery Kody korygujące błędy. Kody typu: BCH , Reeda-Salomona, oraz Reeda-Mullera.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_K01, K_K02
Powiązane charakterystyki obszarowe:
I.P7S_KO, I.P7S_KK, I.P7S_KR
- Charakterystyka imas_k01
- Kodery i dekodery Kody korygujące błędy. Kody typu: BCH , Reeda-Salomona, oraz Reeda-Mullera.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_K01, K_K02
Powiązane charakterystyki obszarowe:
I.P7S_KO, I.P7S_KK, I.P7S_KR
- Charakterystyka imas_k01
- Szybkie sieci sortujące Zasada 0/1. Sieci bitoniczne, oraz sieci Batchera typu odd-even.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_K01, K_K02
Powiązane charakterystyki obszarowe:
I.P7S_KO, I.P7S_KK, I.P7S_KR
- Charakterystyka imas_k01
- Pola komutacyjne Pola typu: crossbar, knockout, Banyan, Closa, Sunshine, komutatory współdzielące medium.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_K01, K_K02
Powiązane charakterystyki obszarowe:
I.P7S_KO, I.P7S_KK, I.P7S_KR
- Charakterystyka imas_k01
- Tablice routingu Budowa tablic routingu z wykorzystaniem struktur LC-trie.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_K01, K_K02
Powiązane charakterystyki obszarowe:
I.P7S_KO, I.P7S_KK, I.P7S_KR
- Charakterystyka imas_k01
- Sprzętowe systemy IDS Wyszukiwanie wielu wzorców, algorytmy KMP, Aho-Corasica, algorytm KR, filtry Blooma.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_K01, K_K02
Powiązane charakterystyki obszarowe:
I.P7S_KO, I.P7S_KK, I.P7S_KR
- Charakterystyka imas_k01
- Szybkie i potokowe układy arytmetyczne Technika sum prefiksowych: układy sumujące i odejmujące, komparatory, drzewa Wallace’a, sumator n liczb, układy mnożące, metoda Karaczuby, metoda Newtona, układy dzielące.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_K01, K_K02
Powiązane charakterystyki obszarowe:
I.P7S_KO, I.P7S_KK, I.P7S_KR
- Charakterystyka imas_k01
- Układy sprzętowe realizyjące transformatę FFT oraz filtry Implementacja szybkiej transformaty Fouriera w sprzęcie, zastosowanie twierdzenia o splocie, filtry: implementacja filtrów FIR, IIR, arytmetyka rozproszona.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_K01, K_K02
Powiązane charakterystyki obszarowe:
I.P7S_KO, I.P7S_KK, I.P7S_KR
- Charakterystyka imas_k01
- Kryptograficzne układy sprzętowe Obliczenia w ciałach skończonych, potęgowanie Montgomerego. Algorytmy asymetryczne: Dieffiego-Hellmana i RSA. Algorytmy symetryczne AES.
Weryfikacja: egzamin, projekt
Powiązane charakterystyki kierunkowe:
K_K01, K_K02
Powiązane charakterystyki obszarowe:
I.P7S_KO, I.P7S_KK, I.P7S_KR