BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Graham H. Norton appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
The Games-Chan algorithm finds the minimal period of a periodic binary sequence of period $2^n$, in $n$ iterations. We generalise this to periodic $q$-ary sequences (where $q$ is a prime power) using generating functions and polynomials and apply this to find the multiplicity of $x-1$ in a $q$-ary polynomial $f$ in $\log_{\,q}°(f)$ iterations.
Our overall goal is to unify and extend some results in the literature related to the approximation of generating functions of finite and infinite sequences over a field by rational functions. In our approach, numerators play a significant role. We revisit a theorem of Niederreiter on (i) linear complexities and (ii) '$n^{th}$ minimal polynomials' of an infinite sequence, proved using partial quotients. We prove (i) and its converse from first principles and generalise (ii) to rational functions where the denominator need not have minimal degree. We prove (ii) in two parts: firstly for geometric sequences and then for sequences with a jump in linear complexity. The basic idea is to decompose the denominator as a sum of polynomial multiples of two polynomials of minimal degree; there is a similar decomposition for the numerators. The decomposition is unique when the denominator has degree at most the length of the sequence. The proof also applies to rational functions related to finite sequences, generalising a result of Massey. We give a number of applications to rational functions associated to sequences.
We derive Bézout identities for the minimal polynomials of a finite sequence and use them to prove a theorem of Wang and Massey on binary sequences with a perfect linear complexity profile. We give a new proof of Rueppel's conjecture and simplify Dai's original proof. We obtain short proofs of results of Niederreiter relating the linear complexity of a sequence s and K(s), which was defined using continued fractions. We give an upper bound for the sum of the linear complexities of any sequence. This bound is tight for sequences with a perfect linear complexity profile and we apply it to characterise these sequences in two new ways.
We consider finite sequences $s\in D^n$ where $D$ is a commutative, unital, integral domain. We prove three sets of identities (possibly with repetitions), each involving $2n$ polynomials associated to $s$. The right-hand side of these identities is a recursively-defined (non-zero) 'product-of-discrepancies'. There are implied iterative algorithms (of quadratic complexity) for the left-hand side coefficients; when the ground domain is factorial, the identities are in effect Bézout identities. We give a number of applications: an algorithm to compute Bézout coefficients over a field; the outputs of the Berlekamp-Massey algorithm; sequences with perfect linear complexity profile; annihilating polynomials which do not vanish at zero and have minimal degree: we simplify and extend an algorithm of Salagean to sequences over $D$. In the Appendix, we give a new proof of a theorem of Imamura and Yoshida on the linear complexity of reverse sequences, initially proved using Hankel matrices over a field and now valid for sequences over a factorial domain.
We show that a straightforward rewrite of a known minimal polynomial algorithm yields a simpler version of a recent algorithm of A. Salagean.
Let $s$ be a finite sequence over a field of length $n$. It is well-known that if $s$ satisfies a linear recurrence of order $d$ with non-zero constant term, then the reverse of $s$ also satisfies a recurrence of order $d$ (with coefficients in reverse order). A recent article of A. Salagean proposed an algorithm to find such a shortest 'two-way' recurrence -- which may be longer than a linear recurrence for $s$ of shortest length $\LC_n$. We give a new and simpler algorithm to compute a shortest two-way linear recurrence. First we show that the pairs of polynomials we use to construct a minimal polynomial iteratively are always relatively prime; we also give the extended multipliers. Then we combine degree lower bounds with a straightforward rewrite of a published algorithm due to the author to obtain our simpler algorithm. The increase in shortest length is $\max\{n+1-2\LC_n,0\}$.
We present a recursive minimal polynomial theorem for finite sequences over a commutative integral domain $D$. This theorem is relative to any element of $D$. The ingredients are: the arithmetic of Laurent polynomials over $D$, a recursive 'index function' and simple mathematical induction. Taking reciprocals gives a 'Berlekamp-Massey theorem' i.e. a recursive construction of the polynomials arising in the Berlekamp-Massey algorithm, relative to any element of $D$. The recursive theorem readily yields the iterative minimal polynomial algorithm due to the author and a transparent derivation of the iterative Berlekamp-Massey algorithm. We give an upper bound for the sum of the linear complexities of $s$ which is tight if $s$ has a perfect linear complexity profile. This implies that over a field, both iterative algorithms require at most $2\lfloor \frac{n^2}{4}\rfloor$ multiplications.