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.