Information theory

Question 1

What is the relationship between a probability of an event and the amount of information it contains?

Answer 1

A certain event contains zero information.
An event with zero probability contains infinite information
IA = -log PA
IA is the information in event A, PA is the probability

Question 2

How many bits do you need for 4, 8 equiprobable messages?

Answer 2

4 - requires 4 distinct binary pulse patterns (2 bits)
8 - requires 8 distinct binary pulse patterns (3 bits)

Question 3

How can you calculate the information contained by message of different symbols with different independent probabilities

Answer 3

Ii = log_2(1/Pi) bits
Say you had message X = ABC, sum log_2(1/Pi) of A B and C

Question 4

What is the entropy?

Answer 4

Entropy H is the average information. H = sum(i=1 to n) of Pi*log_2(1/Pi)

Question 5

What is the rate of information transmission?

Answer 5

R = rH bits per second
r is the symbol rate
H is the entropy (average information per symbol)

Question 6

What is Shannon’s theorem?

Answer 6

Says that R<=C, ie. rate of information transmission is less than channel capacity.
C is the max rate of reliable transmission through the channel without error.

Question 7

What is the Hartley-Shannon theorem?

Answer 7

C = Blog_2(1+S/N) bits per second
C = channel capacity
B = channel bandwidth
S/N = mean square signal to noise ratio. Needs to be not in dB. dB = 10 log_10(x)

Question 8

What is the maximum error rate for a binary system?

Answer 8

50%

Question 9

How does an extended source work?

Answer 9

If you consider a message of individual symbols to be divided into blocks of n symbols, you can consider this a source of K^n alphabet symbols where K is the number of symbols in the original alphabet. Then Hnew = nH

Question 10

How can data be source encoded?

Answer 10

Source encoding means representing information efficiently. This can be done by representing frequent symbols with short codewords and rare symbols with longer codewords

Question 11

What are the two requirements of source encoders?

Answer 11

The codewords are in binary form
The source code is uniquely decodable.

Question 12

How can we calculate the coding efficiency of a source encoder?

Answer 12

ƞ = Lmin/Lavg
L is codeword length
Lavg is calculated by the sum of (probabilities times the number of bits in each codeword)

Question 12

What is a prefix code?

Answer 12

A code in which no codeword is the prefix of any other codeword. It is always uniquely decodable and has a decision tree as you receive more and more bits. The end of the codeword is always recognisable. H <= Lavg < H+1

Question 13

What is Huffman coding?

Answer 13

It is a procedure for creating prefix codes that assigns longer codewords to symbols with more information. It however requires statistical knowledge of the source.

Question 14

What is Lempel-Zev coding?

Answer 14

Takes care of the fact that you might not know the statistics of the data you are encoding.
Uses fixed length codes to represent a variable number of source symbols.
Only has true advantage with long data strings.

Question 15

What is channel coding?

Answer 15

Aims to increase the resistance of the communication to channel noise by introducing redundancy.
Understood by block codes - message is divided into blocks k bits long mapped onto an n bit block where n>k

Question 16

What is repetition coding?

Answer 16

Each bit in a message is repeated several (n) times where n is an odd integer
Improved reliability is at cost of decreased code rate

Question 17

What is error control coding?

Answer 17

If a channel has capacity C, there exists a coding technique to transmit over the channel with arbitrarily probability of error.
This is done through the addition of redundancy which adds complexity and increases bandwidth.

Question 18

What is a linear block code?

Answer 18

A code is linear if any two codewords can be added in mod-2 to produce a third codeword in the code.
The block consists of a message vector m and a parity vector b and a code vector c.
c = [b|m] or [m|b] (could go either way around)

Question 19

What are repetition codes?

Answer 19

The simplest type of linear block codes where all the parity bits are repetitions of the single message bit per block.

Question 20

In Hamming coding, how long is each part of the block? How many distinct message words are there?

Answer 20

A family of linear block codes where:
block length n = 2^m -1
message bits k = 2^m - m - 1
parity bits n-k=m
m>= 3
There are 2^k distinct message words
They are single error correcting binary perfect codes.

Question 21

What is forward error correction?

Answer 21

A form of error control that provides coding gain but adds complexity and requires greater bandwidth for the same message rate. Two types include block coding and convolutional coding.

Question 22

Draw the binary symmetric channel

Question 23

How can you calculate the code rate?

Answer 23

Code rate = rate of message data / rate of codeword = m/c

Question 24

Given the parity check matrix or generator matrix, how can you find the other one?

Answer 24

Parity check H = [ I : P’ ]
Generator G = [ P : I ]
Look for I in one of them to identify P. Then make the other.

Question 25

How does Hamming coding work? Sketch G. What is the relationship between G and c?

Answer 25

1

Question 26

How can you know if a linear block code received is a valid codeword?

Answer 26

Multiply the received codeword by the transpose of the parity check matrix. Equals 0 if it is a valid codeword. Equals something else means there is an error.
cH’=0

Question 27

How can you work out the block error probability for a repetition code?

Answer 27

Say a block has 5 bits. Probability of getting the block wrong = probability of getting 3 bits wrong + probability of getting 4 bits wrong. + probability of getting 5 bits wrong.
Eg. probability of 3 bits wrong = (Perror^3)(Pnoerror^2)(5 choose 3)

Question 28

What is the relationship between H and G in linear block coding?

Answer 28

HG’ = 0
GH’ = 0

Question 29

What are syndrome errors and how can you write down all the syndrome errors for a Hamming code?

Answer 29

A received signal r = c + e where e is an error vector.
The syndrome is the result of multiplying the parity check transpose with the received message. By looking at the list of syndromes that correspond to codewords, we can work out which bit had a likely error.
s = rH’, s is the syndrome vector
s = [0 0 0] if no error.

See 2

Question 30

What is SNR and SIR?

Answer 30

Signal to Interference Ratio - interference from other reflected signals travelling different paths
Signal to Noise Ratio - background noise (thermal, ratio)

Question 31

How can you calculate the signal to noise ratio, linear or dB?

Answer 31

SNR (dB) = 10 log_10 (mean s^2/ mean n^2)
S/N (linear) = mean s^2 / mean n^2

note we are squaring the voltages

Question 32

How can you calculate the rms voltage arising from thermal noise at a given temperature across a resistor R?

Answer 32

mean v^2 = 4kTRB
T = temp in K
R = resistance
B = bandwidth
k = Boltzmann’s constant

Don’t forget to square root

Question 33

How can you calculate the power of noise across a certain bandwidth?

Answer 33

Integrate the power spectral density across the bandwidth. (multiply B by n^2 for AWGN)

Question 34

What is noise figure?

Answer 34

The ratio of input S/N ratio to output S/N ratio, based on the idea that a device like an amplifier will add noise to the amplified signal.

F = (S/N)o/ (S/N)i

Question 34

What is noise temperature?

Answer 34

The effective temperature of a white thermal noise source at the input of a device that represents all the noise in the device.

Question 35

What does the cascaded noise figure equation show?

Answer 35

The overall noise figure of a cascade of amplifiers can be calculated using the equation, with the noise figures and gains of the first, second amplifiers etc. being F1 G1, F2 G2….
Says you should put your best amplifier first.

Question 36

What are the key features of convolution coding?

Answer 36

Code rate = 1/2 (one bit in, two bits out)
Constraint is 3 (how many steps each bit is in the system for)