0.1 Digital multitone modulation

Digital multitone modulation

We present the digital multitone modulation scheme and demonstrate its suitability for demodulation via FFAST.

Digital multitone modulation scheme

Let a finite alphabet $\mathbb{A}=\{a_1,a_2,\cdots a_{\left|\mathbb{A}\right|}\}$ be given, where each symbol $a\in \mathbb{A}$ is associated with a unique sequence of $B$ ordered bits, $b_{B-1},\cdots ,b_1,b_0$ , where $B=\lceil {log}_2\left|\mathbb{A}\right|\rceil$ and $b_i\in \{0,1\}$ for $i=0,\cdots ,B-1$ . For example, let $\mathbb{A}$ be the set of all lowercase letters in the English alphabet and associate each letter with its order in the alphabet. In this case, the binary sequence `01101' corresponds to the thirteenth letter, “m".

Generally speaking, Digital Multitone (DMT) Modulation is a “parallel communication scheme in which several carriers of different frequencies each carry narrowband signals simultaneously” [link] . These narrowband signals are usually sinusoids that encode the binary sequence associated with each symbol. If a bit is “high", then the corresponding sinusoid is expressed in the output signal; otherwise the bit is “low" and the sinusoid is not expressed. More precisely, given a symbol $a\in \mathbb{A}$ with the corresponding binary sequence $b_{B-1},\cdots ,b_1,b_0$ , the message signal $m\left(t\right)$ is defined to be

for some fundamental carrier frequency, $f_0$ .

In our previous example where $\mathbb{A}$ is the English alphabet and the letter “m" corresponds to “01101”, the message signal $m\left(t\right)$ is the sum of the first, third, and fourth harmonics, as shown in the figure below:

In our computational experiments, we use digital multitone modulation to encode 8-bit Extended ASCII values. An Extended ASCII table can be found here . Below are several symbols and their digital multitone modulation signals.

Sparsity in digital multitone modulation

Sparse FFT algorithms only achieve low runtime complexity if the input signal is sparse in its Fourier representation; that is, if for a length- $N$ signal, there are $k$ nonzero DFT coefficients with $k<<N$ . FFAST, the sparse FFT algorithm that we will be using, requires the sparsity constraint $k<N^{\frac{1}{3}}$ . Recall that the message signal, $m\left(t\right)$ , is defined as

so that the Nyquist frequency is $2B{f}_0$ . In order to ensure signal sparsity, the sampling frequency should be a multiple of the fundamental carrier frequency so that each of the sinusoidal components falls into a single frequency bin. This type of “on-the-grid" sampling may be expressed as

where $N$ is the length of the sampled signal. Note that in [link] each sinusoid contributes two DFT coefficients. Thus, $k=2B$ if all bits are high so that the sparsity condition may be expressed as $2B<N^{\frac{1}{3}}$ .

Sampling plays a large role in signal sparsification. There are many sampling methods that ensure sparsity and we present two different methods. The first method involves padding the input signal to achieve sparsity. Consider sampling at the Nyquist frequency so that $f_s=2B{f}_0$ . As stated, this sampled signal is not necessarily sparse – in fact, $k=N$ if all bits are high! However, periodizing the sampled signal sufficiently many times will result in higher frequency resolution by placing zero-value coefficients in between the nonzero coefficients, thus sparsifying the signal. This method results in a spectrum with nonzero coefficient few and far between. Second, consider sampling at a sufficiently high rate to satisfy the sparsity condition; that is, $f_s>8B^3{f}_0$ . First note that $8B^3{f}_0>2B{f}_0$ so that aliasing does not occur. This method results in a compact spectrum where only the first and last $B$ coefficients are nonzero. See the figure below for a spectra that are characteristic of these methods.

It should be noted that there are many sampling methods that ensure signal sparsity but for the purposes of this project, we care only that the signal is sparse. Sampling schemes are discussed further in [link] .