5. sada úloh (21 b)
Úloha 1 (3 body)
Mějme LFSR v Galoisově tvaru se zpětnou vazbou danou polynomem $x^4+x^3+x+1$, tedy posuvný registr vypadající takto:
+---------->+---------------------->+------------->+
| | | |
| +-----+ | +-----+ +-----+ | +-----+ |
| | | v | | | | v | | v
<--+<-+ +<-+--+ +<----+ +<----+ +<----+
| | | | | | | |
+-----+ +-----+ +-----+ +-----+
Kolika stavů může tento posuvný registr nabývat? Vytvořte orientovaný graf, jehož vrcholy jsou stavy posuvného registru a šipky značí přechod z jednoho stavu do druhého.
Úloha 2 (4 body)
Mějme LFSR ve Fibonacciho tvaru se zpětnou vazbou danou polynomem $x^5+x^4+x^2+x+1$. Registr je ve stavu (1, 1, 1, 1, 1), vypadá tedy takto:
+---------->+---------->+---------------------->+--------------+
| ^ ^ ^ |
| +-----+ | +-----+ | +-----+ +-----+ | +-----+ |
| | | | | | | | | | | | | | v
<--+<-+ 1 +<-+<-+ 1 +<-+<-+ 1 +<----+ 1 +<-+<-+ 1 +-----+
| | | | | | | | | |
+-----+ +-----+ +-----+ +-----+ +-----+
Najděte odpovídající stav odpovídajícího registru v Galoisově tvaru (tj. generuje stejnou posloupnost). Jakou periodu bude mít posloupnost generovaná tímto LFSR?
Úloha 3 (3 body)
Booleovská funkce $f:\mathbb{Z}_2^3\rightarrow\mathbb{Z}_2$ je definovaná tabulkou takto:
$x_1$ |
$x_2$ |
$x_3$ |
$f(x_1,\,x_2,\,x_3)$ |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
Najděte polynom $f \in \mathbb{Z}_2[x_1,\,x_2,\,x_3]$, který této funkci odpovídá. Stručně popište, jak jste postupovali.
Úloha 4 (3 body)
LFSR délky 5 s neznámým polynomem zpětné vazby vygeneroval posloupnost začínající \[1111100011\dots\]
Jak by pokračovala posloupnost, kterou by registr generoval, kdyby začínala \[00001\].
Úloha 5 (4 body)
Mějme LFSR délky $n \in \mathbb{N}$ s polynomem zpětné vazby $\sum^n_{i=0}a_ix^i$. Bud $a^{(t)}=(a_0^{(t)},\, a_1^{(t)},\dots,\, a_{n-1}^{(t)})$ stav registru v čase $t \in \mathbb{N}_0$. Nechť $L:\mathbb{Z}_2^n\rightarrow\mathbb{Z}_2^n$ je lineární zobrazení takové, že pro $t \in \mathbb{N}_0$ platí $a^{t+1}=L(a^{(t)})$. Najděte matici tohoto zobrazení. Jak vypadá matice inverzní.
Úloha 6 (4 body)
Své osobní zadání obdržíte v pátek e-mailem.