Formula sheet

r

Bits carried per signal element, dimensionless

Data elements

Count of bits

Signal elements

Count of signal elements used to carry them

r = 1 is one bit per pulse. r below 1 means it takes more than one signal element to carry a bit — the cost the biphase line codes in the next topic pay for a guaranteed transition every interval.

Bit rate

Data rate, bits per second (bps)

Signal rate

Baud rate, signal elements per second (baud)

Follows directly from the two rate definitions on this page — bits per second equals (bits per signal element) times (signal elements per second). Nyquist's log2(L) term, in the next topic, is this same relationship for the special case where every signal element carries an equal share of L levels.

C

Channel capacity, bits per second

B

Bandwidth, hertz

P

Received signal power

N

Noise power

P/N is a POWER ratio, not decibels. If a question gives you dB, convert first with SNR = 10^(dB/10).

B

Bandwidth, hertz

L

Number of distinct signal levels

Assumes a noiseless channel. L must be at least 2 — one level carries no information.

dB

Signal-to-noise ratio in decibels

Ten, not twenty. The 20 log10 form is for amplitude or voltage ratios, not power.

Bit Rate

bps

Sampling Rate

samples per second

bits per sample

count, fixed by the precision chosen

r

Bits carried per signal element

L

Number of distinguishable signal levels — amplitudes, frequencies or phases, depending on the scheme

f_{\max}

Highest frequency present in the original analog signal, hertz

This is the condition PCM's sampling step must meet to make accurate reconstruction possible. Telephone voice is taken as topping out at 4000 Hz, which is where the 8000 samples/s figure below comes from.

n

Number of channels multiplexed

B_{\text{ch}}

Bandwidth of one channel, hertz

B_{\text{guard}}

Bandwidth of one guard band, hertz

For n channels there are n-1 guard bands between them — one fewer than the number of channels, because a guard band only sits between two neighbours.

T_{\text{slot}}

Duration of one input slot, seconds

R_{\text{in}}

Input data rate, bps

n

Number of input slots per frame

T_{\text{out slot}}

Duration of one output slot, seconds

k

Message length in bits

n

Codeword length in bits, message plus redundancy

Lower rate means better protection and lower throughput. It is a direct trade.

n-k

Number of redundancy bits added

M(x)

The message as a polynomial

x^{n-k}

Shift left by the number of redundancy bits, appending zeros

R(x)

The remainder after dividing by the generator g(x)

The generator has length (n-k)+1 and is known to both sender and receiver.

d_min

The minimum Hamming distance of the code — the smallest number of bit positions in which any two valid codewords differ

s

Number of errors the code is guaranteed to detect

t

Number of errors the code is guaranteed to correct

Standard result in coding theory. Lecture 3 does not derive this — it is included because Hamming-distance questions are still fair game in the exam.

T_{fr}

Frame transmission time, seconds

T_p

Maximum one-way propagation time across the collision domain, seconds

This is the whole reason Ethernet has a minimum frame size. A frame shorter than 2Tp could finish transmitting before a collision at the far end gets back to tell the sender about it.

m

Number of collisions this frame has suffered so far

K

Randomly chosen backoff multiplier, redrawn after every collision

The range doubles with each collision until it caps at m = 10 (K up to 1023), and the station gives up after 16 attempts. Both cap numbers are standard IEEE 802.3, not lecture content — see the note on the page.

d

Maximum distance between the two furthest stations, metres

v

Propagation speed in the medium, metres per second

T_p

Maximum one-way propagation time, seconds

Propagation-delay-only figure. The real limit for 10 Mbps Ethernet is under half of this — see the collision domain section.

HLEN

Header Length field, counted in 4-byte (32-bit) words

HLEN = 5, the minimum with no options, gives 5 x 4 = 20 bytes, exactly the fixed part.

Lecture 5's own figure: about 4295 million addresses total, of which about 3706 million are described as usable.

\wedge

Bitwise logical AND, applied bit by bit across all 32 bits

This single operation is what a router performs on every packet it forwards.

x

Number of host bits, that is 32 minus the prefix length

The minus 2 removes the network address and the broadcast address. It does NOT apply to /31 or /32.

b

Number of bits borrowed from the host portion

Fragmentation Offset

Value stored in the 13-bit offset field, counted in 8-byte units

The field never stores a byte count directly. Always multiply the field's value by 8 to get the real position in the original datagram.

Compare against IPv4's 2^32. The jump is not "a bit more room" — it is enough that address exhaustion stops being a design constraint at all.

D_x(y)

Cost of the least-cost path currently known from node x to destination y

c_{x,v}

Direct link cost from x to a neighbour v

D_v(y)

Neighbour v's own estimated least-cost-path cost to y

The minimum is taken only over v ranging across the direct neighbours of x.

D(v)

Current best-known cost from the source to node v

D(w)

Cost from the source to the node w just added to N'

c_{w,v}

Direct link cost from w to v

Applied to every v adjacent to w and not yet in N', on every iteration.

N

Send window size, in frames

m

Number of bits in the sequence number field

The lecture states the window must be strictly less than 2^m, not equal to it — see the Pitfall below.

rwnd

Receive window advertised to the sender, in bytes

rwnd shrinks as more bytes arrive from the sender and grows as the receiving process pulls bytes out of the buffer.

cwnd

Congestion window, set by the sender based on network conditions

rwnd

Receive window, set by the receiver based on its buffer

n

Number of round-trip times elapsed since slow start began

Starting cwnd is taken as 1 MSS (2^0); each RTT with all ACKs received doubles it, until cwnd reaches ssthresh.

i

Congestion window size when congestion avoidance began

n

Number of round-trip times elapsed since congestion avoidance began

Growth is additive here, one MSS per RTT, unlike slow start's exponential growth.

L

Object (packet) length in bits

R

Link bandwidth in bps

a

Average arrival rate in requests per second

rho

Traffic intensity (utilisation), dimensionless

D

Average delay in seconds, including queueing

The slide quotes the M/M/1 behaviour in words (small near 0, large near 1, infinite above 1). The form of D here is read from its own worked numbers, 2.165 s and 0.66 ms, because the equation glyphs did not extract.

Packet length

Size of the packet in bits

Transmission rate

Rate of the link in bits per second (bps)

Distance

Length of the link in metres

Propagation speed

Speed of the signal in the medium, in metres per second

Processing delay and queuing delay have no formula in the lecture, only definitions.

R

Link rate in bits per second (bps)

w_i

Weight of class i

\sum_j w_j

Sum of the weights of all classes

R_i

Rate class i receives, in bps

The formula's symbols are partly garbled in the lecture text. This reading is consistent with the weight examples the lecture gives.

r

Rate at which tokens enter the bucket, in tokens per second

t

Length of the time interval, in seconds

c

Capacity of the bucket, in tokens

One token is removed for every cell of data sent.

r

Token rate, in tokens per second

t

Length of the time interval, in seconds

c

Bucket capacity, in tokens

The lecture gives the result in packets per second.

x

Numerical value of the plaintext letter, a=0 up to z=25

k

The secret key, an integer modulo 26

C

Numerical value of the ciphertext letter, A=0 up to Z=25

Decryption subtracts the key: x = (C - k) mod 26.

p, q

Two large prime numbers, for example 1024 bits each

n

The modulus, the product pq

z

The product (p-1)(q-1)

e

Public exponent, e < n, with no common factors with z

d

Private exponent, chosen so that ed mod z = 1

Public key is (n, e). Private key is (n, d).

m

Message as a number, m < n

c

Ciphertext as a number

e, d

Public and private exponents

n

The modulus