Exam Preparation Deck

Question 1

State the lower bound for the probability of error, given the entropy of H(X|Y) by estimating X from Y.

What is the name of that inequality?

Answer 1

Question 2

What is the probability density function of a Gaussian random variable?

Answer 2

Pretty tough to remember, eh?

Question 3

For a source with fixed power level \sigma^2, what is its maximum entropy?

Answer 3

It’s probably not tested before. But just in case.

Question 4

State Shannon’s Channel Coding theorem.

Answer 4

For a channel of capacity C > entropy H, there exists a coding scheme such that source is reliably sent through channel with error rate lower than any arbitrary epsilon.

Question 5

State Noisy Channel Coding Theorem. Which is more effective in increasing capacity: SNR or W?

Answer 5

P is average transmitted power, N_0 is power spectral density of noise and W is bandwidth. One can show that C -> P/N_0 log(e) when W tends to infinity. However C grows without bounds when SNR = P/N_0W is increased.

Question 6

What is a necessary condition for code lengths, such that the resulting code is uniquely decodable?

Please name the inequality.

Answer 6

Question 7

What is the inescapable bound of the frequency-time uncertainty product, given by the uncertainty principle?

How does it show that information is fundamentally quantised?

Answer 7

Bound is 1/4\pi. For any given closed subspace in the time-frequency plane with area A, there could be at most 4A\pi independent quanta of data.

Question 8

State the functional and Fourier form of the Gabor wavelet.

Answer 8

Rule 1: Love Gabor wavelets.

Question 9

Define the KL distance.

Answer 9

KL distance measures the inefficiency of coding optimally in q(x), while the real distribution is p(x).

Question 10

Explain how Fourier/Gabor/DCT transform manages to compress data.

Answer 10

Neighbouring pixels in an image are often highly correlated. These transformation uses decorrelating expansion basis function. As a result, we get non-uniform coefficients, often peaked at very few places. This leads to lower entropy. By Shannon coding theorem, lower code lengths are then possible. Even lossless images can have large compression. If we quantize values coarsely in the encoding (such as JPEG), we can obtain compression factor of 30:1, without much loss in image quality.

Question 11

Define auto-correlation function. How is it able to extract periodic component from noise?

Answer 11

Original signal often is coherent, while noises are not. The auto-correlation function would be able to extract periodic component since noises often average out themselves in the process.

Question 12

What is the ideal function used for retreiving input signal from sampled points?

Given that the sampling frequency is f_s.

Answer 12

Question 13

Describe the compression strategies of JPEG.

Answer 13

1. Splits an image into a uniform grid of non-overlapping tiles, usually 8x8 pixels in size.
2. Performs DCT (Discrete Cosine Transform) on each tile, generating 64 DCT coefficients.
3. Quantize the resulting DCT coefficients, more coarsely for the coefficients associated with higher frequencies.
4. Uses a quantization table to control the relative severity of truncation.
5. Many high frequency components end up being 0 after quantization. The long runs of 0 are captured by run-length encoding.

Question 14

Describe the compression strategies deployed by JPEG-2000.

How does it improve on JPEG?

Does it have any disadvantage?

Answer 14

• Uses Discrete Wavelet Transform, with smoothly attenuating Daubechies wavelets.
• The absence of sharply truncated tile boundaries avoid coarse blocky quantization artifacts.
• Performs much better than JPEG in severe compression, such as 20:1 or 50:1. JPEG only around 10:1.
• Implementation of DWT more complicated, even though Daubechies wavelets are orthogonal. Execution times are slower for both compression and decompression.

Question 15

How does IrisCode work?

Answer 15

• Segmentation (detect iris boundaries) and size normalization performed to extract the iris pattern.
• Regions of iris textures are projected onto 2D Gabor wavelet basis.
• MSBs of real-part and imaginary-part of projection coefficients are encoded.
• The MSBs amount to encoding the phase quandrants.
• The binary pair forms a Gray Code, so that misjudges between any neighbouring quadrants flips only one bit.
• 250 bits of entropy extracted from iris. Hugely discriminating.
• Compact encoding of phase structure allows fast searching and matching. Just use bit-parallel XORs.

Question 16

List two results that proves bandlimited signals have finite degrees of freedom.

Answer 16

1. Nyquist’s sampling theorem: If a signal is strictly bandlimited to some frequency W, sampling it at a rate 2W specfies the signal everywhere.
2. Logan’s theorem: If a function is bandlimited to one octave, i.e. f_max < 2*f_min, then its set of zero-crossings fully specifies the function (up to a scale factor in amplitude).

Question 17

What does it mean for a sequence to be algorithmically random?

Answer 17

A sequence of length n is algorithmically random if the Kolmogorov complexity is at least n.

That is, the shortest program that generates the sequence is the listing of the sequence itself.