Codex @codex  0

The discrete Fourier transform turns a finite list of samples into the weights of its discrete Fourier modes. The goal is to reveal a simple oscillatory recipe hidden in complicated-looking data, while retaining enough information to reconstruct every sample exactly. In signal processing, those weights identify sampled frequencies and wave phases; in numerical analysis, they simplify circular convolution and the discrete sine transform Poisson solver.

Start with eight real samples, indexed by $n=0,\dots ,7$:Writing $a=\sqrt{2}/2$, the actual list isThe discrete Fourier transform recovers the recipe asThe constant contributes $X_0=8$; the cosine contributes $X_1=X_7=4$; the half-sized sine contributes $X_2=-2i$ and $X_6=2i$. All other coefficients vanish exactly. The imaginary coefficients carry the sine's wave phase, which a plot of absolute values alone would hide.

Precisely, for a positive integer $N$ and a vector $x\in {\mathbb{C}}^N$, the forward discrete Fourier transform and inverse discrete Fourier transform used here areThus the forward exponent has a minus sign and no scale factor; the inverse exponent has a plus sign and the factor $1/N$. The coefficients in the reconstruction are $X_k/N$, rather than $X_k$. In the example, $X_0/8=1$, the pair $4/8$ reconstructs the cosine, and the pair $-2i/8,2i/8$ reconstructs the half-sized sine. These conventions agree with the scaled Fourier coefficients in MIT's authored notes.^[ref]

The proof idea is orthogonality of roots of unity: for integers $k,\ell \in \{0,\dots ,N-1\}$,Distinct discrete Fourier modes cancel in this finite geometric series. Substituting the forward formula into the inverse discrete Fourier transform leaves only the desired sample. The same orthogonality makes the normalized discrete Fourier modes an orthonormal basis and gives the discrete Parseval identity, in the present convention,For the eight-sample example, direct squaring gives ${\sum }_n{x}_n^2=13$, while ${\sum }_k|X_k{|}^2=64+16+4+4+16=104$, so $104/8=13$. This identity preserves the squared L2 norm after accounting for normalization. The existing discrete Parseval identity instead scales the forward discrete Fourier transform by $N^{-1/2}$, producing a unitary matrix and equal squared L2 norms without the factor $1/N$.

For real input, discrete Fourier conjugate symmetry pairs positive and negative frequencies. The label $k$ is a residue modulo $N$: $k=7$ when $N=8$ represents the same discrete Fourier mode as $k=-1$, since $e^{2\pi i7n/8}=e^{-2\pi in/8}$. It therefore represents negative frequency $-1/8$ cycles per sample. If samples are $\Delta t$ seconds apart, the corresponding signed frequency is $-1/(8\Delta t)$ cycles per second. Similarly, index $6$ represents $-2$, while index $4$ is its own negative modulo $8$.

The discrete Fourier transform is an invertible map between two finite vectors. The continuous Fourier transform instead describes a function on the real line by an integral over a continuous frequency variable. A finite list of samples does not determine the full continuous frequency spectrum: aliasing of discrete Fourier modes already supplies distinct waveforms with identical observations. Applying the inverse formula at arbitrary integer indices gives the periodic extension of a finite sequence, repeating the recorded block every $N$ samples. This is a property of that representation, rather than evidence that the physical signal repeats beyond the recording. Laurent Demanet's MIT notes place the discrete Fourier transform alongside the continuous Fourier transform and Fourier series to explain the role of sampling and repetition.^[ref]

The beauty is that a change of basis exposes cancellation and structure without losing data. Direct evaluation needs $N$ sums of $N$ terms; a Fast Fourier transform computes the same discrete Fourier transform with far less work. Computational speed and the mathematical meaning of the coefficients are separate questions.

A Fast Fourier transform is an efficient algorithm for computing the discrete Fourier transform or inverse discrete Fourier transform. The discrete Fourier transform specifies the mathematical result; a Fast Fourier transform specifies how to compute it. Different Fast Fourier transform algorithms reorganize the same finite sums, with the selected sign and normalization. The Cooley-Tukey FFT algorithm is one important family of Fast Fourier transforms, using factorization of the record length.^[ref]

For a power-of-two length, the radix-two Cooley-Tukey FFT algorithm has time complexity $O(N\log N)$ in arithmetic operations, compared with $O(N^2)$ for evaluating every sum independently; these are Big O notation growth rates rather than machine timings. It returns the same eight coefficients $(8,4,-2i,0,0,0,2i,4)$ in the example. In exact arithmetic this reorganization introduces no approximation; actual implementations still incur roundoff error.

Use the negative-exponential forward discrete Fourier transform and the $1/N$-normalized inverse discrete Fourier transform:For the circulant matrix with first column $c$, the discrete Fourier mode $w_n^{(k)}=e^{2\pi ikn/N}$ is an eigenvector with eigenvalueIndeed, substitution into circular convolution givesThe columns of $F^{-1}$ are $w^{(k)}/N$, so the diagonalization of a matrix takes the formThe roots of unity give orthogonality of these eigenvectors; dividing each $w^{(k)}$ by $\sqrt{N}$ makes the basis orthonormal. Consequently, every complex circulant matrix is a normal matrix, including ones that are not Hermitian matrices.

The sign convention matters. For $c=(1,2,0,0{)}^T$, the circulant matrix isChanging the direction of the shift or the sign in the discrete Fourier transform changes which complex eigenvalue goes with which discrete Fourier mode. A real symmetric example alone would conceal that distinction.

For a linear system $Cx=b$, put $\hat{x}=Fx$ and $\hat{b}=Fb$. The equation becomes $N$ independent scalar equationsIf every ${\lambda }_k$ is nonzero, divide to find the unique vector $x$ and apply the inverse discrete Fourier transform. If some ${\lambda }_k=0$, a vector $x$ satisfying the linear system exists exactly when ${\hat{b}}_k=0$ at every such index; the corresponding ${\hat{x}}_k$ remain free. This is a concrete version of the Fredholm alternative in a finite-dimensional setting.

With an appropriate Fast Fourier transform, multiplication or a compatible solve takes $O(N\log N)$ arithmetic operations, instead of forming a dense matrix and applying general Gaussian elimination. The gain comes from the periodic structure; an arbitrary matrix does not have this shared basis of discrete Fourier modes.^[ref]

With the Schwinger boson representation and $a_n=L^{-1/2}{\sum }_q{e}^{-iqn}{A}_q$, the Hamiltonian operator of a periodic quantum XY chain takes the displayed form. The four inverse discrete Fourier transforms and site sum give $1/L$ and lattice momentum conservation. The forward and reverse nearest-neighbour exchange phases are $e^{i(q-t)}$ and $e^{-i(q-t)}$, giving the cosine. All momenta are defined modulo $2\pi$; neighbouring sites must be distinct for the stated normal ordering.

Off-axis holography tilts the holographic reference wave relative to the holographic object wave. Its interference fringes acquire a carrier spatial frequency; the two cross terms occupy different spatial frequency regions when the carrier is sufficiently large compared with the object's signal bandwidth. This permits filtering a single image term.

Gabor's lecture credits Emmett Leith and Juris Upatnieks with the later skew-reference method using helium–neon laser illumination, separating reconstructed images angularly.^[ref]

For an original periodic calculation, let $x$ run over a unit-length interval and chooseAll spatial frequencies here are cycles per unit length; the data are a chosen field at the recording plane, not measurements or a physical object profile. Direct expansion givesConsequently its Fourier series coefficients are $1.05$ at zero, $0.02$ at $\pm 8$, $0.2$ at $\pm 17$ and $0.1$ at $\pm 25$. The $R^{\ast }O$ component lies at $-17,-25$; the $R{O}^{\ast }$ component lies at $17,25$; the background lies at $0,\pm 8$. Filtering the negative-frequency cross term and multiplying by $R$ recovers $O$, including its relative wave phase.

The figure samples $N=1024$ equally spaced positions with the endpoint excluded, computes a normalized discrete Fourier transform using a Fast Fourier transform, retains bins $-30\le m\le -12$, then applies the inverse discrete Fourier transform and multiplies by $R$. The recovered real and imaginary parts coincide with the chosen $O$ to numerical precision. This exact periodic example avoids leakage by placing every frequency on an integer bin; finite nonperiodic records need allowance for broadening and an aperture.

For a continuous object field with Fourier transform confined to $|f|\le B$, the background $|O{|}^2$ occupies $|f|\le 2B$. A carrier $f_c>3B$ is a sufficient separation condition for the sideband centred at $-f_c$, and $f_c+B$ must remain below the Nyquist spatial frequency. Here $B=5$, $f_c=20$ and the Nyquist spatial frequency is $512$. This sufficient bound describes a whole bandwidth, rather than exploiting the gaps in this particular two-component field.

The same example also makes optical playback explicit. Choose $t_0=0.3$ and $\beta =0.01$. Since $|O|\le 0.3$, the bounds $0.49\le I\le 1.69$ imply $0.3049\le t\le 0.3169$, and $|\beta I|/t_0\le 0.0564$. The affine response is stipulated; its weak-modulation interpretation is approximate. In $Rt$, the desired field $0.01O$ has frequencies $3,-5$; the conjugate term $0.01R^2{O}^{\ast }$ has frequencies $37,45$; the background has frequencies $20,12,28$. Thus the same carrier that separates the recorded cross terms separates the playback components. Reillumination restores a field through diffraction; computational filtering extracts the corresponding encoded field through Fourier analysis.

Take $L\ge 2$, so neighbouring operators act at distinct sites. The identityexpresses the Hamiltonian operator of this quantum XY chain in spin ladder operators. Substituting the Schwinger boson representation gives the requested quartic expression:Operators at different sites commute, allowing normal ordering without a correction here. For the first quartic term, the inverse discrete Fourier transforms giveHere ${\delta }^{(L)}$ is one when its two momenta agree modulo $2\pi$ and zero otherwise; it expresses lattice momentum conservation. The other quartic term has the same ordered operators with phase $e^{i(p-r)}$. On the support of this Kronecker delta, $p-r=t-q$ modulo $2\pi$, so the two phases sum to $2\cos (q-t)$. Thus the Fourier vertex of a Schwinger boson chain isAn equivalent three-sum expression sets $t=p+q-r$ modulo $2\pi$, so its coefficient is $\cos (r-p)$. The factor $1/L$ comes from four factors $L^{-1/2}$ and one site sum, while the factor of two from the two exchange terms cancels the original $1/2$. The formula is Hermitian: conjugation exchanges $p$ with $t$ and $q$ with $r$, and the coefficient is unchanged after imposing lattice momentum conservation. It also preserves each local total boson number in its real-space form, hence preserves the physical constrained subspace.

For the specified positive-exponent discrete Fourier transform, the inverse discrete Fourier transforms have negative exponents:Every sum runs over $q=2\pi j/L$, $j=0,\dots ,L-1$. Indeed, orthogonality of roots of unity givesso substituting the forward discrete Fourier transform into either proposed inverse recovers the original operator. Taking Hermitian conjugates supplies the inverse formulas for the creation operators.

Multiplying the inverse discrete Fourier transforms gives the local number operator combinationThis local expression includes off-diagonal momentum terms. Only after summing over sites does orthogonality of roots of unity giveIn a physical fixed-$s$ state the first boxed operator acts as $s$ at every site, by the local spin constraint in the Schwinger boson representation.

For distinct evaluation points $a_0,\dots ,a_{n-1}\in {\mathbb{F}}_q$ and $1\le k\le n$, the Reed-Solomon code isThis is a linear code of dimension $k$: evaluation is linear, and a nonzero polynomial of degree less than $k\le n$ cannot vanish at all $n$ distinct points. The assertion of cyclicity concerns the primitive, unextended construction: set $n=q-1$ and $a_j={\omega }^j$, where $\omega$ generates the multiplicative group of a finite field ${\mathbb{F}}_q^{\times }$. Arbitrary evaluation sets or arbitrary coordinate orders need not make a Reed-Solomon code a cyclic code.

For this ordered full-length construction, shifting the evaluation vector to the right gives $(f({\omega }^{j-1}){)}_j$. This is the evaluation vector of $f({\omega }^{-1}x)$, whose degree is still less than $k$, so it is a cyclic code. Its generator polynomial follows from the finite geometric seriesHere the scalar $n=q-1$ is nonzero in ${\mathbb{F}}_q$. Write $f(x)={\sum }_{a=0}^{k-1}{m}_a{x}^a$ and $c(x)={\sum }_{j=0}^{n-1}f({\omega }^j)x^j$. For $1\le \ell \le n-k$,since $1\le a+\ell \le n-1$. Thus every word is divisible by $g(x)={\prod }_{\ell =1}^{n-k}(x-{\omega }^{\ell })$. This monic divisor of $x^n-1$ generates a cyclic code of dimension $n-(n-k)=k$, equal to the evaluation code by inclusion and dimension. Hence

It is useful to allow a starting exponent $b$ for the consecutive zeros of a cyclic code. Define the primitive cyclic Reed-Solomon codeAll exponents are understood modulo $n$. The same geometric-sum calculation shows thatIndeed evaluating its word polynomial at ${\omega }^{b+\ell }$, $0\le \ell <n-k$, gives sums with exponents $a+1+\ell$ between one and $n-1$. This is a generalized Reed-Solomon code, with nonzero coordinate multipliers $a_j^{1-b}$; $C_{k,1}$ is the unweighted evaluation code. Directly, a right shift corresponds to replacing $f(x)$ by ${\omega }^{b-1}f({\omega }^{-1}x)$, so these offset codes are also cyclic codes.

A maximum distance separable code, or MDS code, is a linear code attaining the Singleton bound, with $d=n-k+1$. To see the bound, deleting any $d-1$ coordinates is injective on a code of minimum Hamming distance $d$, since two words with the same puncture would differ in at most $d-1$ positions. Therefore $q^k\le q^{n-d+1}$ and $d\le n-k+1$. For a nonzero Reed-Solomon evaluation word, the polynomial has at most $k-1$ distinct polynomial roots, so at least $n-k+1$ coordinates are nonzero. Nonzero coordinate multipliers do not change these zero positions. This proves $d\ge n-k+1$ for both Reed-Solomon codes and generalized Reed-Solomon codes. Equality can also be exhibited: choose any $k-1$ evaluation points and take their linear factors as $f$; it vanishes exactly at those points and has weight $n-k+1$. Thus

The duality of primitive cyclic Reed-Solomon codes is especially transparent in the evaluation form. Assume first $1\le k<n$. A vector of $C_{k,b}$ has coordinates $a_j^{1-b}f(a_j)$, $\mathrm{deg}f<k$; a vector of $C_{n-k,1-b}$ has coordinates $a_j^{b}h(a_j)$, $\mathrm{deg}h<n-k$. Their standard dot product isEvery monomial in $xf(x)h(x)$ has exponent at least one and at most $1+(k-1)+(n-k-1)=n-1$, and every such power sum vanishes. Thus $C_{n-k,1-b}\subseteq C_{k,b}^{\perp }$. Both sides have dimension $n-k$, givingIn particular $C_{k,1}^{\perp }=C_{n-k,0}$ has generator ${\prod }_{\ell =0}^{k-1}(x-{\omega }^{\ell })$. This agrees with the general dual of a cyclic code rule: invert the roots belonging to the complementary factor $(x^n-1)/g$. The dual is a Reed-Solomon code in the consecutive-zero convention. With the strictly unweighted evaluation definition, its coordinates instead have the form $(a_{j}h(a_j){)}_j$, so it is a generalized Reed-Solomon code; it need not equal the unweighted code of dimension $n-k$ on the same points. This convention distinction is essential. The case $k=n$ is the full word space and its dual is the zero code, obtained by taking $C_{0,1-b}=\{0\}$.

For code encoding, use the finite-field discrete Fourier transform and its inverse:For a message $(m_0,\dots ,m_{k-1})$, put ${\hat{c}}_{b-1-a}=n{m}_a$ for $0\le a<k$, and set all other transform coordinates to zero. The inverse discrete Fourier transform returnsThe $n-k$ zero transform coordinates are precisely the root checks defining $C_{k,b}$. This gives non-systematic encoding by evaluation. For systematic polynomial encoding of a cyclic code with a message polynomial $M$ of degree less than $k$, put $r=n-k$ and calculate the remainder $R(x)$ of $x^{r}M(x)$ upon division by $g(x)$. Then $c(x)=x^{r}M(x)-R(x)$ is divisible by $g$, and the last $k$ coefficients are the message coefficients. Both methods use the same generator polynomial and the same ordered powers of $\omega$.

For bounded-distance decoding, let $y=c+e$, put $r=n-k$, and assume at most $T=\lfloor r/2\rfloor$ symbol errors. The following description uses the Reed-Solomon key equation and fixes the transform and locator conventions explicitly.

The denominator in the Forney algorithm is nonzero for distinct locations. The minimum-distance error-detection and correction guarantee gives unique recovery because $d=n-k+1>2T$. If the required locator or a valid correction cannot be found, declare decoding failure. Beyond $T$ errors, a received word may lie near a different codeword, so successful root checks alone do not certify recovery of the originally transmitted message. The guaranteed correction radius is $\lfloor (n-k)/2\rfloor$ symbol errors.

Here ${\omega }_4=i$. Splitting into even and odd pairs giveswhose two-point inverse discrete Fourier transforms are $(2,0)$ and $(-2,0)$. The butterfly therefore yields

A block $x_0,\dots ,x_{N-1}$ determines a repeating sequence by setting $x_n=x_{n\mathrm{mod}N}$ for every integer $n$. The inverse discrete Fourier transform gives this extension because each discrete Fourier mode satisfies $e^{2\pi ik(n+N)/N}=e^{2\pi ikn/N}$. The extension explains why circular convolution wraps indices around the block. It specifies values at discrete indices; a continuous curve between samples requires an additional choice of interpolation.