# http://colinraffel.com/wiki/

### Site Tools

columbia_ee_dqe_practice_exams

# Columbia EE DQE Practice Exams

This page contains possible answers for the 2008-2010 DQEs, which were sent out for practice for the 2012 exam. Please note that these answers may be incorrect and/or incomplete; no answer key was provided.

## 2008

### Signals, Systems, and Communications

#### Problem 1

a) The difference equation is $y[n] = x[n] - x[n - 4]$ with impulse response $h[n] = \delta[n] - \delta[n-4]$. This corresponds to a transfer function of $H(z) = 1 - z^{-4}$. The magnitude will approach zero when $1 = z^{-4}$ (the zeros). This will occur at $z = e^0, e^{\pm 2\pi/4}, e^{\pm \pi}, e^{\pm 6\pi/4}, \ldots$. The transfer function will approach infinity as $z \rightarrow 0$, so there is a fourth-order pole at $z = 0$. When $z = e^{\pm (2n + 1) \pi/4}, n = 0, 1, 2, \ldots$, $z^{-4} = j$. So, $|H(e^{j\omega})|$ will be 1 at these points and 0 at the zeros. The frequency response will look like a full-wave rectified sine wave with period $\pi$.

b) The phase will jump from $-\pi$ to $\pi$ at each zero. At $z = e^{\pm (2n + 1) \pi/4}, n = 0, 1, 2, \ldots$, $H(z) = 1 - e^{\pm(2n + 1)} \rightarrow \angle H(z) = 0$. So, the phase will look like a sawtooth wave with period $\pi/2$, starting at $\pi$ and sloping linearly to $-\pi$ at $\pi/2$.

c) Any signals which are 4-sample periodic, i.e., $x[n] = x[n-4]$.

d) The difference equation is $y[n] = x[n] + \frac{4}{5}x[n - 4]$ with impulse response $h[n] = \delta[n] + \frac{4}{5}\delta[n-4]$. This corresponds to a transfer function of $H(z) = 1 + \frac{4}{5}z^{-4} = (z^2 + \frac{2i}{\sqrt{5}})(z^2 - \frac{2i}{\sqrt{5}})$$= (z - \frac{1-i}{\sqrt[4]{5}})(z + \frac{1-i}{\sqrt[4]{5}})(z - \frac{i-1}{\sqrt[4]{5}})(z - \frac{i-1}{\sqrt[4]{5}})$. These four zeros will have magnitude $\frac{\sqrt{2}}{\sqrt[4]{5}}$ and phase $\pi/4, 3\pi/4, 5\pi/4, 7\pi/4$. This system will be zero for signals where $x[n] = -\frac{4}{5}x[n-4]$. These signals will oscillate with a period of 4 samples and exponentially decay by a factor of $4/5$ each period.

#### Problem 3

(1) $\phi(t) = f_1(t)\cos(\omega_c t) + f_2(t)\sin(\omega_c t)$. If the communications channel has an impulse response $h(t)$, then we have $g_1(t) = (h(t)\ast\phi(t))\cos(\omega_ct) = h(t)\ast f_1(t)\cos^2(\omega_c t) + h(t)\ast f_2(t)\sin(\omega_c t)\cos(\omega_c t)$. Similarly, $g_2(t) = h(t)\ast f_2(t)\sin^2(\omega_c t) + h(t)\ast f_1(t)\cos(\omega_c t)\sin(\omega_c t)$

(2) Taking Fourier transforms:

$\mathcal{F}$f_1(t)$ = F_1(t)$, $\mathcal{F}$f_2(t)$ = F_2(t)$

$\mathcal{F}$\cos(\omega_c t)$ = \sqrt{\frac{\pi}{2}}(\delta(\omega - \omega_c) + \delta(\omega + \omega_c))$

$\mathcal{F}$\cos(\omega_c t)\cos(\omega_c t)$ = \mathcal{F}$\cos(\omega_c t)$\ast\mathcal{F}$\cos(\omega_c t)$$$= \frac{\pi}{2}(2\delta(\omega) + \delta(\omega + 2\omega_c) + \delta(\omega - 2\omega_c))$

$\mathcal{F}$\sin(\omega_c t)$ = j\sqrt{\frac{\pi}{2}}(\delta(\omega - \omega_c) - \delta(\omega + \omega_c))$

$\mathcal{F}$\sin(\omega_c t)\sin(\omega_c t)$ = \mathcal{F}$\sin(\omega_c t)$\ast\mathcal{F}$\sin(\omega_c t)$$$= \frac{-\pi}{2}(2\delta(\omega) - \delta(\omega + 2\omega_c) - \delta(\omega - 2\omega_c))$

$\mathcal{F}$\sin(\omega_c t)\cos(\omega_c t)$ = \mathcal{F}$\sin(\omega_c t)$\ast\mathcal{F}$\cos(\omega_c t)$$$= \frac{\pi j}{2}(- \delta(\omega + 2\omega_c) + \delta(\omega - 2\omega_c))$

Given this derivation, the equations derived above (for example $g_2(t) = h(t)\ast f_2(t)\sin^2(\omega_c t) + h(t)\ast f_1(t)\cos(\omega_c t)\sin(\omega_c t)$) indicate that the input to each filter will be the corresponding system input, convolved in the frequency domain by either $\sin^2$ or $\cos^2$ and $\sin\cos$. The former frequency-domain convolutions will result in a baseband signal in the filter input (due to the $\delta(\omega)$ term in the $\cos^2$ and $\sin^2$ Fourier transforms), while the latter will not. As a result, because $\omega_c \gg \omega_0$ (the signal bandwidth), the baseband signal will be isolated. The resulting outputs, then, will be proportional to $h(t)\ast f_1(t)$ and $h(t)\ast f_2(t)$.

(3) I don't know the terms “constellation and decision diagrams” or “symbol error probability expression”.

### Digital Computing Systems

#### Problem 1

1. (a) $11\bar{1}0.\bar{1}\bar{1} = 27 + 9 - 3 + 0 - \frac{1}{3} - \frac{1}{9} = 32 \frac{5}{9}$

(b) $\bar{1}\bar{1}10.11 = -27 - 9 + 3 + 0 + \frac{1}{3} + \frac{1}{9} = -32 \frac{5}{9}$

© $\bar{1}\bar{1}10 = -27 - 9 + 3 + 0 = -33$

(d) $0.1111\ldots = \frac{1}{3} + \frac{1}{9} + \frac{1}{27} + \ldots = \sum_{n=1}^{\infty}\left(\frac{1}{3}\right)^n = \frac{1}{3}\frac{1}{1 - \frac{1}{3}} = \frac{1}{2}$

(e) $10\bar{1}\bar{1}01.10\bar{1}010\bar{1}010\bar{1}0\ldots =$$243 + 0 - 27 - 9 + 0 + 1 + \frac{1}{3} + 0 - \frac{1}{27} + 0 + \frac{1}{243} + 0 + \ldots =$$208 + \frac{1}{3}\sum_{n=1}^{\infty}\left(\frac{1}{9}\right)^n = 208 \frac{3}{8}$

2. (a) $1\bar{1}0\bar{1} + 1\bar{1}0\bar{1} = (27 - 9 + 0 - 1) + (27 - 9 + 0 - 1) = 34 = 11\bar{1}1$

(b) $1\bar{1}0\bar{1} - \bar{1}110 = (27 - 9 + 0 - 1) - (-27 + 9 + 3 + 0) = 17 - (-15) = 32 = 11\bar{1}\bar{1}$

© $1\bar{1}0\bar{1} \ctimes 1\bar{1}0\bar{1} = (27 - 9 + 0 - 1)\ctimes(27 - 9 + 0 - 1) = 289 = 11\bar{1}\bar{1}01$

3. If the leftmost nonzero digit is 1, it's positive, otherwise, it's negative, because $3^n > \sum_{m = 0}^{n-1} 3^m$

4. All nonzero digits should switch sign - this corresponds to flipping all of the signs in the nonzero terms of the sum corresponding to its base-10 representation, thereby negating it.

#### Problem 3

##### Part 1

a) Truth table:

A B C D Y
0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 0
0 1 1 1 1
1 0 0 0 1
1 0 0 1 0
1 0 1 0 1
1 0 1 1 1
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0

$(A + \bar{B} + C + D)(A + \bar{B} + \bar{C} + D)(\bar{A} + B + C + \bar{D})(\bar{A} + \bar{B} + C + D)$$(\bar{A} + \bar{B} + C + \bar{D})(\bar{A} + \bar{B} + \bar{C} + D)(\bar{A} + \bar{B} + \bar{C} + \bar{D})$ This is not minimal form…

b) 2-input NOR gate truth table:

A B Y
0 0 1
0 1 1
1 0 1
1 1 0

An inverter can be made by tying the two inputs of the NAND gate together. An AND can be made by putting a NAND inverter at the output of a NAND. An OR can be made out of three NAND gates; gates A and B have their inputs tied together and take input, their outputs go to another NAND gate. Using these basic rules the function can be realized with 19 NAND gates (and maybe reduced some with some care).

c) Using the B, C, and D inputs as the input selection bits, the A input can be wired to every input optionally through an inverter. When the the output should be the opposite of A for some B, C, and D according to the truth table, an inverter should be used. Otherwise A should be connected directly to the corresponding multiplexer input.

##### Part 2

a) For each of the three levels of one input, there are three possible levels for the other input, resulting in nine possible input combinations.

b) For each pair of input levels, there are three possible output levels. There are nine possible input level pairings. This results in $3^9$ possible functions.

c) For each pair of input levels, there are two possible output levels. There are four possible input combinations, so there are $2^4$ possible functions.

## 2009

### Circuits and Electronics

#### Problem 2

* The op amp will work to make its inputs equal - in this case, this corresponds to setting the negative input to zero volts. Since $V_p = 0$, $V_{out} = A(0-V_m) = -999V_m$. Note that $V_1 = V_m$ because they are at the same node in the circuit. The current through the capacitor is expressed by $I_0 = C\frac{d(V_1-1V)}{dt}$ because it is connected to the 1V power supply. I'm stuck at this point.

#### Problem 3

(a) The first pair of pFET and nFET transistors serve as an inverter because when $V_{in}$ is low, the pFET will have 2.5V on its drain and the nFET will be high-impedance; when $V_{in}$is high, the nFET will have 0V on its drain and the pFET will be high-impedance. Similarly, for the second pair of FETs, when $V_{out}$ is low, the pFET will have 2.5V on its drain and the nFET will be low impedance, and when $V_{out}$ is high, the nFET will have 0V on its drain and the pFET will be high impedance. So, when $V_{in}$ is low, the output of the first pair of FETs will be high, and the inverter will set $V_{out}$ to low, which will cause the second pFET to also send 2.5V to the inverter input. Assuming the inverter switches from high to low at exactly 1.25V, as $V_{in}$ increases,

The Schmitt trigger is useful for signals which are to be used as logic signals but are not always exactly “high” or “low”. In other words, if a signal which is meant to be treated as a logic “low” actually has some fluctuation, the Schmitt trigger will “ignore” spurious high signals caused by fluctuations as long as they are less than the “on” threshold - and this threshold can be more forgiving in either direction. It essentially requires a more affirmative “high” or “low” to make the corresponding change on the output.

(b) If $V_T$ is 0.5V and -0.5V for the nFETs and pFETs respectively, then $I_{dst} = \frac{\beta}{2}(V_{gs} - 0.5V)$ and $I_{dst} = \frac{\beta}{2}(V_{sg} - 0.5V)$, respectively.

### Signals, Systems, and Communications

#### Problem 1

(a) The Nyquist frequency is twice the highest frequency present in $x(t)$, which corresponds to $250(2) = 500$ Hz.

(b) If the signal is sampled at $T = 1/f$, then sampling will be equivalent to convolving the frequency domain representation with an impulse train with period $2\pi f$. If $f$ is above the Nyquist limit (500 Hz), the convolution of each impulse with the spectrum doesn't overlap, and we can achieve perfect reconstruction for general signals with a lowpass filter at the Nyquist frequency. Because we are using a bandpass filter here, we can allow for aliasing that would cause non-perfect reconstruction with a lowpass filter. However, we must avoid having the copies of the bandlimited spectral slices overlap, or else we will not be able to reconstruct them from their sum. So, we seek a frequency $f$ such that the spectrum from $\pm 400\pi$ to $\pm 500\pi$ is maintained - the aliased terms cannot overlap in this range. The lowest sampling frequency for which this is true is 125 Hz. At this frequency, there is no overlap between convolutions of each of the impulses, although there is aliasing in the baseband (between $-500\pi$ and $500\pi$). However, if the bandpass filter is set with $\omega_1 = 400\pi$ and $\omega_2 = 500\pi$, then only the uncorrupted original signal will be maintained. The amplitude $A$ can be set to 1 because the spectral magnitude will be maintained.

#### Problem 3

(a) Assuming (without loss of generality) that $t$ is a discrete variable and $T$ is an even integer, we can compute the DTFT to determine the sun-of-sinusoid representation of $x(t)$: $X(\omega) = \sum_{n = -\infty}^{\infty}x(n)e^{-j\omega n}$. Defining $u_M(t) = 1, 0 \le t \le M; 0 \mathrm{\;otherwise}$, $U_M(\omega) = \sum_{n = -\infty}^{\infty}u_M(n)e^{-j\omega n} = \sum_{n=0}^M e^{-j\omega n}$. This is the sum of a geometric series, so we have $U_M(\omega) = \frac{1 - e^{-j\omega(M+1)}}{1 - e^{-j\omega}}$. Then $x(t) = \delta(t)\ast u_{T/2}(t) - \delta(t+T/2)\ast u_{T/2}(t) + \delta(t+T)\ast$$u_{T/2}(t) - \delta(t - T/2)\ast u_{T/2}(t) + \delta(t-T)\ast u_{T/2}(t) - \delta(t + 3T/2)\ast u_{T/2}(t) + …$$= u_{T/2}(t) + u_{T/2}(t) \ast \sum_{n=1}^{\infty} (-1)^n(\delta(t + nT/2) + \delta(t - nT/2))$ which has a Fourier transform $X(\omega) = U_{T/2}(\omega) + U_{T/2}(\omega)\sum_{n=1}^{\infty}(-1)^n (e^{j\omega nT/2} + e^{-j\omega nT/2})$.

I know, from memory, that the harmonic series of a square wave is proportional to the sum of a sinusoid at the fundamental frequency (here $1/T$) and scaled odd harmonics.

(b) When the delay corresponds to an integer multiple of the period of one of the harmonics, that harmonic will be canceled out. As a result, for very short delays, the energy will be close to the full signal energy, as only very high harmonics (low energy) will be canceled out. As the delay approaches the square wave period, the energy cancellation corresponding to this delay-period match up will become more drastic, until a period of $T$ is reached, at which point the signal will be fully cancelled out. After this point, the energy signal will be periodic, as the addition of a delay of one period will not affect the energy.

© Rather than having many “dips” in the energy plot corresponding to nulled harmonics, it would have dips were the delay was an integer multiple of each of the three harmonics (including the fundamental as the “zeroth” harmonic).

## 2010

### Circuits and Electronics

#### Problem 1

(Making all of the assumptions listed) As the input signal goes negative, $C_1$ will be charged. When the signal goes positive, $D_1$ will be reverse biased so $C_1$ will not be able ti discharge. $D_2$ then sees the input voltage in series with the voltage on $C_1$. This series voltage will charge $C_2$ towards twice the input voltage. After a few cycles, $C_2$ will be fully charged. The load on $V_{out}$ will discharge $C_2$ while $C_1$ is charging.

#### Problem 3

(a) The four-resistor ladder on the left is creating a series of nodes where the voltages are $3V_{dd}/4$, $2V_{dd}/4$, and $V_{dd}/4$. So, when $V_{in}$ is between $V_{dd}/4$ and $2V_{dd}/4$ (for example), the top two comparators will output a logical 0 because $V_{in} < 2V_{dd}/4 < 3V_{dd}/4$, but the bottom comparator will output a logical 1. This will cause the upper OR gate to output 0 and the lower OR gate to output a 1. This behavior is summarized (for $V_{dd} > 0$) for all input levels below ($C_1, C_2, C_3$ correspond to the output of the bottom, middle, and top comparators respectively).

$V_{in}$ $C_1$ $C_2$ $C_3$ $B_1$ $B_0$
$V_{in} < V_{dd}/4$ 0 0 0 0 0
$V_{dd}/4 < V_{in} < 2V_{dd}/4$ 1 0 0 0 1
$2V_{dd}/4 < V_{in} < 3V_{dd}/4$ 1 1 0 1 1
$3V_{dd}/4 < V_{in}$ 1 1 1 1 1

Note that because $C_3$ is only high when both $C_2$ and $C_1$ are high, $B_0$ and $B_1$ will already be high, so the output will not change once $V_{in} > 2V_{dd}/4$. However, when $V_{dd}$ is negative (which is in some ways a misnomer as $V_{dd}$ is normally used to denote the positive supply rail), the interpretation of the circuit changes as follows:

$V_{in}$ $C_1$ $C_2$ $C_3$ $B_1$ $B_0$
$V_{in} < 3V_{dd}/4$ 0 0 0 0 0
$3V_{dd}/4 < V_{in} < 2V_{dd}/4$ 0 0 1 1 1
$2V_{dd}/4 < V_{in} < V_{dd}/4$ 0 1 1 1 1
$V_{dd}/4 < V_{in}$ 1 1 1 1 1

The resistor ladder and comparators is pretty clearly a linear voltage level quantizer.

(b) I'm not sure why the outputs are connected to the OR gates in the way they are.

### Signals, Systems and Communications

#### Problem 1

1. If the system is causal, then $h[n] = 0, n < 0$. If it's stable, $\sum_{n=-\infty}^{\infty}|h[n]| < \infty$. Note that $C_{hh}[l] = C_{hh}[-l]$ because $C_{hh}[l] = \sum_{k=-\infty}^{\infty}h[k]h[k+l] = \sum_{m=-\infty}^{\infty}h[m-l]h[m] = C_{hh}[-l]$. For a simple case, say that we know that $h[0] = a, h[1] = b$ (this could be deduced when $C_{hh}[l] = 0, |l| > 1$). Then $C_{hh}[0] = a^2 + b^2, C_{hh}[1] = ab, C_{hh}[-1] = ba$. Substituting, we have $C_{hh}[0] = a^2 + \frac{C_hh[1]^2}{a^2} \rightarrow 0 = a^4 - C_{hh}[0]a^2 + C_hh[1]^2$. Note that this is a quadratic equation in which the variable itself is quadratic, so there will be four solutions. This serves as a counterexample - in general we cannot recover $h[n]$ from $C_{hh}$.

As another example, note that the inverse z-transform of the magnitude frequency response of the filter is $C_{hh}$ because $a\star a \rightarrow \bar{A}A$. In other words, only the magnitude response is specified. Given a filter with a certain magnitude response, it is possible to create another filter with the same magnitude response by cascading the original filter with an all-pass filter. As a result, the filter cannot be unique given only this information.

2. A system of this form is characterized by the difference equation $y[n] = x[n] + \sum_{k=1}^{N}a_k y[n-k]$ and has an infinite impulse response $h[k]$. Note that the system being stable implies that $|a_k| < 1$. For a simple case, assume $a_1 = b; a_k = 0, k > 1$. Then $h[n] = b^n$ and $C_{hh}[0] = \sum_{k=\infty}^{\infty}h[k]h[k] = \sum_{k=0}^{\infty}b^{2k} = \frac{1}{1 - b^2}$. This gives us an explicit formula for $a_1$ and thus all of $a_k$. If $a_1 = b; a_2 = c; a_k = 0, k > 2$, then $h[n] = 1, b, b^2 + c, b^3 + 2bc, b^4 + 3b^2c + c^2, b^5 + 4b^3c + 3bc^2, …$

#### Problem 3

a) For a simple first-pass, assume that $0 < \Delta < T$. If $\Delta = T/N$, then this sampling is equivalent to sampling the signal $x(t/N) = y(t)$ (in the figure, the signal is sampled with $\Delta = T/7$, which results in a signal with period $7T$). As proof, note that the samples will occur at $y(0) = x(0), y(1) = x(T + T/N) = x(T/N), y(2)$$= x(2T + 2T/N) = x(2T/N), \ldots$, and $y(N) = x(NT + NT/N) = x(T) = x(0)$. $y(t)$ repeats itself with a period of $N$. In other words, when $\Delta = T/N$, $a = 1/N =$