On Functions of Linear Shift Register Sequences (Q3751507)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3987198
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On Functions of Linear Shift Register Sequences |
scientific article; zbMATH DE number 3987198 |
Statements
On Functions of Linear Shift Register Sequences (English)
0 references
1986
0 references
periodic sequences
0 references
linear complexity
0 references
0.8807756
0 references
0.8682628
0 references
0.8646116
0 references
0.86198306
0 references
0.8609179
0 references
0 references
0.8599404
0 references
Let \(S\) be a set of periodic sequences over \(\mathrm{GF}(q)\); the length of the shortest linear shift register over \(\mathrm{GF}(q)\) being able to produce sequences in \(S\), i.e. the degree of the minimum polynomial \(f_S\), is called the linear complexity of \(S\). This paper reviews mainly the author's work on linear complexity of sequences obtained from functions applied to linear shift register sequences. One of the main results is Theorem 3.3 [Herlestam 1982]: \(\deg f\wedge g\leq \deg f\cdot \deg g\) and the equality holds iff \(f\) or \(g\) has mere simple zeros and all zero products \(z(f)z(g)\) are different, where \(f\wedge g\) is the minimum polynomial of \(\{xy: x \in G(f), y \in G(g)\}\), \(G(h)\) is the set of all shift register sequences with \(h\) as feedback polynomial. Some sketches of proofs of the main theorems are also given. The upper bound of \(\deg f\wedge g\) above can be immediately obtained from the reviewer's ''Linear feedback shift register sequences'' (in Chinese) [Comput. Appl. Appl. Math. 10, No. 11, 21--51 (1975), {\S} 5 Theorem 2] and it is very easy to deduce a more precise upper bound from the reviewer's book ''Invertibility of finite automata'' (in Chinese) Beijing: Science Press (1979; Zbl 0609.68041), {\S} 3.6 Theorem 2]. [For the entire collection see Zbl 0583.00050.]
0 references