The discrete Fourier transform of a recurrent sequence

DOI10.1007/S002000050085MaRDI QIDQ1392663zbMATH OpenOpenAlexFDO

Authors Francis Clarke

Publication date 17 September 1999

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s002000050085

zbMATH Keywords

character sumsfinite fieldsrecurrent sequencessignal theory

Mathematics Subject Classification ID

Recurrences (11B37) Other character sums and Gauss sums (11T24) Finite fields and commutative rings (number-theoretic aspects) (11T99) Numerical methods for discrete and fast Fourier transforms (65T50) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Review text

Let \(F_{q}\) be a finite field, and \((s_{i})_{i \geq 0}\) a maximal period linear recurring sequence in \(F_{q}\) with the primitive characteristic polynomial \[ f(x)=x^{n}-a_{n-1}x^{n-1}- \cdots -a_{0} \in F_{q}[x] \] Let \( \vartheta\) be the primitive element of \(F_{q^{n}}\) such that \[ f(x)= \prod_{i=0}^{n-1} (1- \vartheta^{q^{i}} x), \] \(g= \vartheta^{(q^{n}-1)/(q-1)}=(-1)^{n-1}a_{0}\) the corresponding primitive element of \(F_{q}\), and \(u\) a complex-valued function on \(F_{q}\). Using properties of \textit{P. Langevin}'s character sums [Contemp. Math. 168, 213-216 (1994; Zbl 0821.11063)] the author proves the validity of some easy relations between the discrete Fourier coefficients of the sequences \((u(s_{i}))_{i \geq 0}\) and \((u(g^{i}))_{i \geq 0}\) stated earlier without proof by \textit{H. A. Barker} [Proc. IEEE 332, 556-561 (1991)].

Recommendations

• scientific article; zbMATH DE number 1047548
• ON THE DISTRIBUTION OF POWER RESIDUES AND PRIMITIVE ELEMENTS IN SOME NONLINEAR RECURRING SEQUENCES
• Matrices and linear recurrences in finite fields
• A generalisation of the discrete Fourier transform: determining the minimal polynomial of a periodic sequence

Cited in

(6)

• Character sums and nonlinear recurrence sequences
• On recursive discrete Fourier transformation
• scientific article; zbMATH DE number 54567 (Why is no real title available?)
• A generalisation of the discrete Fourier transform: determining the minimal polynomial of a periodic sequence
• scientific article; zbMATH DE number 1047548 (Why is no real title available?)
• Hadamard transforms of pure-duple rhythms

This page was built for publication: The discrete Fourier transform of a recurrent sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1392663)