Baseband Digital Data Transmission

An eye diagram is an oscilloscope display of a received digital baseband signal. It is made by overlaying many bit intervals on top of each other: the scope is triggered by the symbol clock and the sweep is set to one or two symbol periods. The pattern looks like an eye. Its shape shows at a glance how much ISI and noise the signal has.

   ____________     ____________
  /            \   /            \
 /   .------.   \ /   .------.   \
|   (  open  )   X   (  open  )   |
 \   '------'   / \   '------'   /
  \____________/   \____________/
     ^    ^
     |    best sampling instant
     eye opening (noise margin)

What the eye shows:

• Eye opening (height): the noise margin. A wider vertical opening means more noise can be tolerated.
• Eye width: the time range in which the signal can be sampled without errors.
• Best sampling time: where the eye opening is greatest.
• Slope of the sides: how sensitive the system is to timing error. Steeper sides mean more sensitive.
• Thickness of the crossing (zero-crossing spread): the amount of timing jitter.
• Distortion at the sampling time: the spread of the lines at the top and bottom shows the amount of ISI.

Use: If ISI or noise is severe, the eye closes, and errors become likely. Engineers use the eye diagram to adjust equalisers, choose pulse shaping (e.g. raised-cosine roll-off), set the decision threshold and sampling time, and quickly check the quality of a link.

In an M-ary baseband system, the transmitter does not send one bit per pulse. It groups $k = \log_2 M$ bits into one symbol and sends one of $M$ distinct pulse amplitudes (M-ary PAM) for each symbol. Binary transmission is the special case $M = 2$.

Working

• The bit stream is split into groups of $k$ bits, e.g. $M = 4$ gives 2 bits per symbol.
• Each group is mapped (usually with Gray code) to one of the levels $\pm 1, \pm 3, \dots, \pm (M-1)$ times $A$.
• The receiver samples each symbol and compares it with $M - 1$ thresholds to decide the level, then maps the level back to bits.

 4-ary PAM (Gray coded)
 +3A  --  10
 +1A  --  11
 -1A  --  01
 -3A  --  00
 bits 10 01 11 00 -> levels +3A -1A +1A -3A

Key relations

$$R_s = \frac{R_b}{\log_2 M}, \qquad B_{min} = \frac{R_s}{2} = \frac{R_b}{2 \log_2 M}$$

So for the same bit rate, the needed bandwidth falls by a factor of $\log_2 M$. The bandwidth efficiency rises to $2\log_2 M$ b/s/Hz (Nyquist).

Advantages

• Higher data rate in a band-limited channel (e.g. telephone lines, 2B1Q in ISDN).
• Lower symbol rate, so less ISI and slower symbol timing.

Disadvantages

• For the same peak power, the levels are closer together, so the noise margin is smaller and the error probability rises. Keeping the same error rate needs more transmit power (roughly 6 dB more for each doubling of $M$ at large $M$).
• The receiver needs more decision thresholds and accurate gain control.

M-ary signalling therefore trades power for bandwidth.

Line codes are electrical waveforms used to represent binary data for transmission over a baseband channel. Each code below is shown for the example bits 10110, with bit period $T_b$ and level $V$.

Unipolar (NRZ) code

Binary 1 is sent as $+V$ for the full bit period, and binary 0 as zero voltage. It is simple, but it has a DC component, and long strings of 1s or 0s carry no timing information.

Unipolar NRZ

    1   0   1   1   0  
+V ────|   |───────|   
 0     |───|       |───

Polar (NRZ) code

Binary 1 is sent as $+V$ and binary 0 as $-V$ for the full bit period. There is no DC component for equally likely bits, and it has the best noise immunity of these codes for a given power. Long runs still give no transitions.

Polar NRZ

    1   0   1   1   0  
+V ────|   |───────|   
-V     |───|       |───

Bipolar (AMI) code

Binary 0 is sent as zero voltage. Binary 1s are sent as pulses of alternating polarity, $+V, -V, +V, \dots$, usually half-width (RZ). It has no DC component and narrow bandwidth, and two 1s of the same polarity in a row show an error has occurred. A long run of 0s loses timing; HDB3 and B8ZS solve this.

Bipolar (AMI, RZ)

    1   0   1   1   0  
+V ──|         |─|     
 0   |─────| |─| |─────
-V         |─|         

Unipolar RZ code

Binary 1 is sent as $+V$ for the first half of the bit, then returns to zero. Binary 0 is zero for the whole bit. Each 1 gives a transition that helps timing, but the bandwidth is double that of NRZ and there is a DC component.

Unipolar RZ

    1   0   1   1   0  
+V ──|     |─| |─|     
 0   |─────| |─| |─────

Manchester (split-phase) code

Each bit has a transition at its middle. Binary 1 is $+V$ for the first half and $-V$ for the second half; binary 0 is the reverse. It has no DC component and is self-clocking, which is why it is used in 10 Mb/s Ethernet. The cost is double the bandwidth of NRZ.

Manchester

    1   0   1   1   0  
+V ──|   |───| |─|   |─
-V   |───|   |─| |───| 

Shannon–Hartley theorem

The Shannon–Hartley theorem gives the channel capacity $C$: the highest bit rate that can be sent over a band-limited channel with additive white Gaussian noise (AWGN) with an arbitrarily small error probability.

$$C = B \log_2\!\left(1 + \frac{S}{N}\right)\ \text{b/s}, \qquad N = N_0 B$$

where $B$ is the bandwidth (Hz), $S$ the average signal power, and $N_0/2$ the two-sided noise power spectral density.

If the information rate $R \le C$, a coding scheme exists that makes the error probability as small as we like. If $R > C$, errors cannot be made arbitrarily small, whatever coding is used.

Implications

• Bandwidth–SNR trade-off: the same capacity can be reached with a wide band and low SNR (e.g. spread spectrum) or a narrow band and high SNR (e.g. M-ary QAM).
• Capacity grows linearly with B but only logarithmically with S/N. Doubling the power adds only about $B$ b/s at high SNR.
• It gives a benchmark: practical modems and codes (turbo, LDPC) are judged by how close they come to $C$.
• It proves that error-free communication is possible over noisy channels with proper coding. It does not say how to build the code.

Theoretical limits

• Ideal system: $R = C$. Writing $S = E_b C$:

$$\frac{C}{B} = \log_2\!\left(1 + \frac{E_b}{N_0}\frac{C}{B}\right) \Rightarrow \frac{E_b}{N_0} = \frac{2^{C/B} - 1}{C/B}$$

• As $C/B \to 0$ (infinite bandwidth), $E_b/N_0 \to \ln 2 = 0.693$, i.e. −1.6 dB. This is the Shannon limit: below it, no error-free transmission is possible at any bandwidth.
• Increasing bandwidth alone cannot give unlimited capacity, because noise power $N_0 B$ also grows (shown below).

Capacity with infinite bandwidth

$$C = B \log_2\!\left(1 + \frac{S}{N_0 B}\right)$$

Let $x = \dfrac{S}{N_0 B}$, so $B = \dfrac{S}{N_0 x}$. As $B \to \infty$, $x \to 0$:

$$\begin{aligned} C &= \frac{S}{N_0} \cdot \frac{1}{x} \log_2(1 + x) = \frac{S}{N_0} \log_2 (1+x)^{1/x} \\ C_\infty &= \lim_{x \to 0} \frac{S}{N_0} \log_2 (1+x)^{1/x} = \frac{S}{N_0} \log_2 e \\ &= \frac{S}{N_0} \times 1.4427 \approx 1.44 \frac{S}{N_0} \end{aligned}$$

using $\lim_{x \to 0} (1+x)^{1/x} = e$ and $\log_2 e = 1/\ln 2 = 1.4427$.

So even with infinite bandwidth, the capacity stays finite at $C_\infty \approx 1.44\, S/N_0$ b/s. Capacity can be raised only by raising the signal power or lowering the noise density.

Intersymbol interference (ISI)

ISI is the spreading of each transmitted pulse beyond its own symbol interval because the channel's bandwidth is limited. Tails of earlier and later pulses then add to the sample of the current symbol, which can cause decision errors.

Derivation. The baseband PAM signal at the receiver filter output is

$$y(t) = \mu \sum_{k} a_k \, p(t - kT_b) + n(t)$$

where $a_k$ are the symbols, $p(t)$ is the overall pulse shape (normalised so $p(0) = 1$) and $n(t)$ is noise. Sampling at $t_i = iT_b$:

$$y(t_i) = \underbrace{\mu a_i}_{\text{wanted}} + \underbrace{\mu \sum_{k \ne i} a_k \, p\big((i-k)T_b\big)}_{\text{ISI}} + n(t_i)$$

The middle term is the ISI. It is zero only when $p(nT_b) = 0$ for all $n \ne 0$.

  pulse k-1     pulse k      pulse k+1
     /\           /\           /\
 ___/  \___...___/  \___...___/  \___
          tails overlap at sampling
          instants -> ISI

Ideal solution: Nyquist (sinc) pulse

Nyquist criterion for zero ISI

If $p(t)$ is the overall pulse (transmit filter, channel and receive filter), ISI is zero when

$$p(nT_b) = \begin{cases} 1, & n = 0 \\ 0, & n \ne 0 \end{cases}$$

In the frequency domain this is

$$\sum_{k=-\infty}^{\infty} P\!\left(f - \frac{k}{T_b}\right) = T_b \quad \text{(constant)}$$

That is, copies of the pulse spectrum shifted by multiples of $R_b = 1/T_b$ must add up to a flat spectrum.

The ideal solution uses an ideal rectangular spectrum of bandwidth $B_0 = R_b/2$:

$$P(f) = \frac{1}{2B_0}\,\text{rect}\!\left(\frac{f}{2B_0}\right) \;\Rightarrow\; p(t) = \text{sinc}(2B_0 t) = \frac{\sin 2\pi B_0 t}{2\pi B_0 t}$$

This pulse is zero at every $t = nT_b$ ($n \ne 0$), so ISI is zero. It needs the minimum bandwidth $R_b/2$ (the Nyquist bandwidth).

It is not practical because:

• the brick-wall filter cannot be built, and
• the sinc tails decay only as $1/t$, so a small timing error causes large ISI.

Practical solution: raised-cosine spectrum

The spectrum is given a gradual cosine roll-off from $f_1$ to $2B_0 - f_1$, with roll-off factor $\alpha = 1 - f_1/B_0$ ($0 \le \alpha \le 1$):

$$P(f) = \begin{cases} \dfrac{1}{2B_0}, & |f| < f_1 \\[4pt] \dfrac{1}{4B_0}\left[1 + \cos\dfrac{\pi(|f| - f_1)}{2B_0 - 2f_1}\right], & f_1 \le |f| < 2B_0 - f_1 \\[4pt] 0, & |f| \ge 2B_0 - f_1 \end{cases}$$ $$p(t) = \text{sinc}(2B_0 t)\,\frac{\cos 2\pi\alpha B_0 t}{1 - 16\alpha^2 B_0^2 t^2}, \qquad B_T = B_0(1 + \alpha) = \frac{R_b}{2}(1+\alpha)$$

• It still has zeros at all $nT_b$, so ISI is zero.
• The tails decay as $1/t^3$, so it tolerates timing error well.
• The filter can be built. The cost is extra bandwidth: $\alpha = 0.5$ needs $0.75R_b$, and $\alpha = 1$ needs $R_b$.

Other practical remedies are equalisers (e.g. a tapped-delay-line zero-forcing equaliser) to correct channel distortion, and correlative (duobinary) coding, which allows controlled ISI at the Nyquist bandwidth.

Bit sequence: 1 0 1 1 0 0 1 0 1 0, bit period $T_b$, levels $\pm V$. Each bit is 4 characters wide in the drawings.

Conventions used: Manchester sends 1 as a +V half followed by a −V half, and 0 as −V then +V (Lathi/Haykin; the IEEE 802.3 convention is the opposite). AMI sends alternate 1s as half-width +V and −V pulses, starting with +V, and 0 as no pulse.

Polar NRZ (1 → +V, 0 → −V, full bit)

    1   0   1   1   0   0   1   0   1   0  
+V ────|   |───────|       |───|   |───|   
-V     |───|       |───────|   |───|   |───

Polar RZ (1 → +V, 0 → −V, for half bit, then 0)

    1   0   1   1   0   0   1   0   1   0  
+V ──|     |─| |─|         |─|     |─|     
 0   |─| |─| |─| |─| |─| |─| |─| |─| |─| |─
-V     |─|         |─| |─|     |─|     |─| 

Manchester

    1   0   1   1   0   0   1   0   1   0  
+V ──|   |───| |─|   |─| |───|   |───|   |─
-V   |───|   |─| |───| |─|   |───|   |───| 

AMI (bipolar RZ)

    1   0   1   1   0   0   1   0   1   0  
+V ──|         |─|                 |─|     
 0   |─────| |─| |─────────| |─────| |─────
-V         |─|             |─|             

AMI pulse polarities for the 1s: + − + − + (the 0s are 0).

ISI

Intersymbol interference (ISI) is the overlap of a pulse with the neighbouring symbol intervals. A band-limited channel (or filter) spreads each pulse in time, so the tails of nearby pulses add to the sample of the current symbol:

$$y(iT_b) = \mu a_i + \mu \sum_{k \ne i} a_k\, p\big((i-k)T_b\big) + n(iT_b)$$

The summation term is the ISI. It closes the eye diagram and raises the bit error rate.

Nyquist criterion for zero ISI

If $p(t)$ is the overall pulse (transmit filter, channel and receive filter), ISI is zero when

$$p(nT_b) = \begin{cases} 1, & n = 0 \\ 0, & n \ne 0 \end{cases}$$

In the frequency domain this is

$$\sum_{k=-\infty}^{\infty} P\!\left(f - \frac{k}{T_b}\right) = T_b \quad \text{(constant)}$$

That is, copies of the pulse spectrum shifted by multiples of $R_b = 1/T_b$ must add up to a flat spectrum.

• Ideal Nyquist pulse: $p(t) = \text{sinc}(R_b t)$ with bandwidth $B_0 = R_b/2$ (the minimum possible). It cannot be built, and its slow tails are sensitive to timing error.
• Raised-cosine pulse: bandwidth $B_T = \frac{R_b}{2}(1+\alpha)$, $0 \le \alpha \le 1$. It still gives zero ISI, its tails decay fast, and it can be built.

Duobinary encoding

Duobinary signalling (a correlative-level coding scheme) adds each binary symbol to the one before it. This brings in a controlled amount of ISI that the receiver knows and can remove, and in return the data can be sent at $R_b$ b/s in the minimum Nyquist bandwidth $R_b/2$ with realisable filters.

Encoder: with $a_k = \pm 1$,

$$c_k = a_k + a_{k-1}, \qquad c_k \in \{-2, 0, +2\}$$

This is equal to passing $a_k$ through $H(f) = 1 + e^{-j2\pi f T_b}$. With the ideal Nyquist filter, the overall response becomes

$$H_I(f) = 2\cos(\pi f T_b)\, e^{-j\pi f T_b}, \quad |f| \le \frac{1}{2T_b}$$

This is a smooth half-cosine, which is easy to approximate with a real filter.

 b_k->[Precoder]->[2d-1]-a_k-+---->(+)-c_k->[LPF]-> out
      d_k=b_k XOR d_k-1     |      ^
                            +-[Tb]-+

Decoder (without precoding): $\hat a_k = c_k - \hat a_{k-1}$. One wrong decision then spreads to the bits that follow (error propagation).

Precoding removes this. Use $d_k = b_k \oplus d_{k-1}$ and send $a_k = 2d_k - 1$. Then the receiver decides each bit on its own: $|c_k| = 0 \Rightarrow b_k = 1$, and $|c_k| = 2 \Rightarrow b_k = 0$.

Example: input $b_k$ = 1011001, with initial reference $d_{-1} = 0$ (so $a_{-1} = -1$).

The decoded sequence 1011001 equals the input. Each bit is decided on its own, so there is no error propagation.

Shannon channel capacity theorem

For a channel of bandwidth $B$ Hz with additive white Gaussian noise, the maximum rate of error-free information transfer is

$$C = B \log_2\!\left(1 + \frac{S}{N}\right)\ \text{b/s}$$

where $S/N$ is the signal-to-noise power ratio, with $N = N_0 B$. If the information rate $R \le C$, suitable coding can make the error probability as small as desired. If $R > C$, it cannot. Example: a telephone channel with $B = 3.1$ kHz and $S/N = 30$ dB (1000) has $C = 3100 \log_2 1001 \approx 30.9$ kb/s.

Theoretical limitations

• It gives a limit, not a method. It proves good codes exist but does not show how to build them. Reaching $C$ needs very long code words, so delay and complexity become very large.
• Infinite bandwidth gives finite capacity: as $B \to \infty$, $C \to 1.44\, S/N_0$, because noise power grows with bandwidth.
• Shannon limit: reliable transmission needs $E_b/N_0 \ge \ln 2$ (−1.6 dB), even with unlimited bandwidth.
• Only for AWGN. It assumes Gaussian, white, additive noise and a linear, band-limited channel. Fading, impulse noise, interference and non-linearity are not covered.
• It assumes Gaussian-distributed signals and average power limits. Real systems with fixed constellations fall short of $C$.
• Capacity grows only logarithmically with SNR, so raising power gives diminishing returns.

Bit sequence: 1 0 0 1 0 0 1 1 0 1, bit period $T_b$, levels $\pm V$.

Conventions used: Manchester sends 1 as a +V half followed by a −V half, and 0 as −V then +V (Lathi/Haykin; the IEEE 802.3 convention is the opposite). AMI sends alternate 1s as half-width +V and −V pulses, starting with +V, and 0 as no pulse.

Polar NRZ (1 → +V, 0 → −V)

    1   0   0   1   0   0   1   1   0   1  
+V ────|       |───|       |───────|   |───
-V     |───────|   |───────|       |───|   

Polar RZ (half-width pulses)

    1   0   0   1   0   0   1   1   0   1  
+V ──|         |─|         |─| |─|     |─| 
 0   |─| |─| |─| |─| |─| |─| |─| |─| |─| |─
-V     |─| |─|     |─| |─|         |─|     

Manchester

    1   0   0   1   0   0   1   1   0   1  
+V ──|   |─| |───|   |─| |───| |─|   |───| 
-V   |───| |─|   |───| |─|   |─| |───|   |─

AMI (bipolar RZ)

    1   0   0   1   0   0   1   1   0   1  
+V ──|                     |─|         |─| 
 0   |─────────| |─────────| |─| |─────| |─
-V             |─|             |─|         

AMI: the five 1s get polarities + − + − +. Polar RZ and Manchester give a transition in every bit, which helps clock recovery. AMI has no DC component.

Bit sequence: 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 (15 bits: a 1, ten 0s, then 1101). Each waveform is drawn in two parts: bits 1–8, then bits 9–15.

Polar RZ

1 is sent as a +V pulse for half the bit, and 0 as a −V pulse for half the bit. The line returns to zero in the second half of every bit.

Polar RZ

    1   0   0   0   0   0   0   0  
+V ──|                             
 0   |─| |─| |─| |─| |─| |─| |─| |─
-V     |─| |─| |─| |─| |─| |─| |─| 

    0   0   0   1   1   0   1  
+V             |─| |─|     |─| 
 0   |─| |─| |─| |─| |─| |─| |─
-V ──| |─| |─|         |─|     

Differential Manchester

There is always a transition at the middle of each bit (used for the clock). Data is carried by the start of the bit: 0 = transition at the start, 1 = no transition at the start. The line is assumed to be at −V before the first bit.

Differential Manchester

    1   0   0   0   0   0   0   0  
+V   |─| |─| |─| |─| |─| |─| |─| |─
-V ──| |─| |─| |─| |─| |─| |─| |─| 

    0   0   0   1   1   0   1  
+V   |─| |─| |───|   |─| |───| 
-V ──| |─| |─|   |───| |─|   |─

HDB3 (High Density Bipolar 3)

HDB3 is AMI, except that every run of four 0s is replaced:

• 000V if the number of pulses since the last substitution is odd,
• B00V if it is even.

V (violation) has the same polarity as the pulse before it. B follows the normal AMI rule. This makes successive V pulses alternate, so no DC builds up.

• Bit 1 → +.
• Zeros 2–5: 1 pulse since start (odd) → 000V = 0 0 0 +.
• Zeros 6–9: 0 pulses since the last V (even) → B00V = − 0 0 −.
• Zeros 10–11 → 0 0.
• 1101 → + − 0 +.

HDB3 pulses: + 0 0 0 + − 0 0 − 0 0 + − 0 +

HDB3 (half-width pulses)

    1   0   0   0   0   0   0   0  
+V ──|             |─|             
 0   |─────────────| |─| |─────────
-V                     |─|         

    0   0   0   1   1   0   1  
+V             |─|         |─| 
 0   |─────────| |─| |─────| |─
-V ──|             |─|         

B8ZS (Bipolar with 8-Zero Substitution)

B8ZS is AMI, except that every run of eight 0s is replaced by 000VB0VB. Taking the previous pulse as +, the substitute is 0 0 0 + − 0 − +.

• Bit 1 → +.
• Zeros 2–9 → 0 0 0 + − 0 − +.
• Zeros 10–11 → 0 0.
• 1101: the last pulse was +, so this gives − + 0 −.

B8ZS pulses: + 0 0 0 + − 0 − + 0 0 − + 0 −

B8ZS (half-width pulses)

    1   0   0   0   0   0   0   0  
+V ──|             |─|             
 0   |─────────────| |─| |─────| |─
-V                     |─|     |─| 

    0   0   0   1   1   0   1  
+V ──|             |─|         
 0   |─────────| |─| |─────| |─
-V             |─|         |─| 

Bandwidth comparison

HDB3 and B8ZS need about half the bandwidth of polar RZ and differential Manchester, and they still keep timing information when long strings of 0s occur.

Assumptions: upper and lower case are treated as the same letter, and the space is counted as a symbol because it must also be sent. The message "engineer ko betha arulai ke thaha" has 33 symbols, with 14 distinct symbols.

Huffman encoding

Huffman procedure: list the symbols by probability. Repeatedly combine the two least probable entries into one node whose weight is their sum, until only one node is left. In each merge, the first group listed gets bit 0 and the second group gets bit 1. Each symbol's code word is read from the root down to that symbol.

Merge steps (weights are counts out of 33):

1. {g} (1) + {b} (1) → 2
2. {o} (1) + {l} (1) → 2
3. {i} (2) + {u} (1) → 3
4. {n} (2) + {k} (2) → 4
5. {t} (2) + {r} (2) → 4
6. {o, l} (2) + {g, b} (2) → 4
7. {i, u} (3) + {h} (3) → 6
8. {t, r} (4) + {n, k} (4) → 8
9. {space} (5) + {o, l, g, b} (4) → 9
10. {e} (5) + {a} (5) → 10
11. {t, r, n, k} (8) + {i, u, h} (6) → 14
12. {e, a} (10) + {space, o, l, g, b} (9) → 19
13. {e, a, space, o, l, g, b} (19) + {t, r, n, k, i, u, h} (14) → 33

Average code length:

$$\bar L = \sum p_i l_i = \frac{118}{33} = 3.5758\ \text{bits/symbol}$$

Here the numerator is the total number of bits in the encoded message: $5(3) + 5(3) + 5(3) + 3(3) + 2(4) + 2(4) + 2(4) + 2(4) + 2(4) + 1(5) + 1(5) + 1(5) + 1(5) + 1(4) = 118$ bits.

Entropy:

$$H = -\sum p_i \log_2 p_i = 3.5419\ \text{bits/symbol}$$

Efficiency:

$$\eta = \frac{H}{\bar L} = \frac{3.5419}{3.5758} = 0.9905 = 99.05\%$$

Redundancy $= 1 - \eta = 0.95\%$.

A fixed-length code for 14 symbols needs $\lceil \log_2 14 \rceil = 4$ bits/symbol ($\eta = 88.55\%$). Huffman saves 10.61% of the bits.

Answer: average length = 3.576 bits/symbol, entropy = 3.542 bits/symbol, transmission efficiency η ≈ 99.05%.

Codeword for the received message "Engineer Ko Betha Ke Ke"

Each character (including the 4 spaces) is replaced by its code from the table above:

Full codeword (83 bits for 23 characters):

000 1010 01110 1100 1010 000
000 1001 010 1011 01100 010
01111 000 1000 111 001 010
1011 000 010 1011 000

The Huffman code is a prefix code, so the receiver can decode this bit stream without separators.

Weighted Huffman coding builds the Huffman tree from the actual symbol counts (weights) in the message. Assumptions: case is ignored, and the space is counted as a symbol. The message "mississippi is missing" has 22 symbols and 7 distinct symbols: i = 7, s = 7, space = 2, m = 2, p = 2, g = 1, n = 1.

Huffman tree construction

Huffman procedure: list the symbols by probability. Repeatedly combine the two least probable entries into one node whose weight is their sum, until only one node is left. In each merge, the first group listed gets bit 0 and the second group gets bit 1. Each symbol's code word is read from the root down to that symbol.

1. {n} (1) + {g} (1) → 2
2. {m} (2) + {space} (2) → 4
3. {n, g} (2) + {p} (2) → 4
4. {n, g, p} (4) + {m, space} (4) → 8
5. {s} (7) + {i} (7) → 14
6. {s, i} (14) + {n, g, p, m, space} (8) → 22

                    (22)
                0 /      \ 1
              (14)        (8)
            0/   \1     0/   \1
           s:7   i:7  (4)     (4)
                     0/ \1   0/  \1
                   (2)  p:2  m:2  sp:2
                  0/ \1
                 n:1  g:1

Code table

Efficiency

Average code length:

$$\bar L = \sum p_i l_i = \frac{54}{22} = 2.4545\ \text{bits/symbol}$$

Here the numerator is the total number of bits in the encoded message: $7(2) + 7(2) + 2(3) + 2(3) + 2(3) + 1(4) + 1(4) = 54$ bits.

Entropy:

$$H = -\sum p_i \log_2 p_i = 2.4002\ \text{bits/symbol}$$

Efficiency:

$$\eta = \frac{H}{\bar L} = \frac{2.4002}{2.4545} = 0.9779 = 97.79\%$$

Redundancy $= 1 - \eta = 2.21\%$.

A fixed-length code for 7 symbols needs $\lceil \log_2 7 \rceil = 3$ bits/symbol ($\eta = 80.01\%$). Huffman saves 18.18% of the bits.

Answer: $\bar L = 2.455$ bits/symbol, $H = 2.400$ bits/symbol, transmission efficiency η ≈ 97.79%. The whole message takes 54 bits, compared with 66 bits using a 3-bit fixed code.

Bit sequence: 1 1 0 0 1 1 0 0 0 0 0 1 (12 bits), bit period $T_b$, levels $\pm V$.

Unipolar RZ

1 is sent as +V for the first half of the bit, then 0. A 0 is sent as no pulse.

Unipolar RZ

    1   1   0   0   1   1   0   0   0   0   0   1  
+V ──| |─|         |─| |─|                     |─| 
 0   |─| |─────────| |─| |─────────────────────| |─

Manchester

Every bit has a transition at its middle. 1 = +V then −V, and 0 = −V then +V (Lathi/Haykin convention; IEEE 802.3 uses the opposite).

Manchester

    1   1   0   0   1   1   0   0   0   0   0   1  
+V ──| |─|   |─| |───| |─|   |─| |─| |─| |─| |───| 
-V   |─| |───| |─|   |─| |───| |─| |─| |─| |─|   |─

HDB3

HDB3 is AMI, except that every run of four 0s is replaced by 000V (if an odd number of pulses have been sent since the last substitution) or B00V (if even). V has the same polarity as the previous pulse. B follows the AMI rule (opposite to the previous pulse).

• Bits 1 to 6 (110011): AMI gives + − 0 0 + −.
• Bits 7 to 10 (0000): 4 pulses have been sent since the start, which is even, so this becomes B00V. The previous pulse is −, so B = + and V = +: + 0 0 +.
• Bits 11 and 12 (01): 0 stays 0. The 1 must be opposite to the last pulse (+), so it is −.

HDB3 pulses: + − 0 0 + − + 0 0 + 0 −

HDB3 (half-width pulses)

    1   1   0   0   1   1   0   0   0   0   0   1  
+V ──|             |─|     |─|         |─|         
 0   |─| |─────────| |─| |─| |─────────| |─────| |─
-V     |─|             |─|                     |─| 

Aim of source coding

Source coding represents the output of an information source with as few bits as possible, while still allowing the receiver to recover it exactly (lossless coding) or acceptably (lossy coding). Its aims are:

• Remove redundancy: give short code words to frequent symbols and long ones to rare symbols, so the average code length $\bar L$ approaches the entropy $H$ (Shannon's source coding theorem: $\bar L \ge H$).
• Raise efficiency $\eta = H/\bar L$ towards 100%.
• Lower the bit rate, which saves bandwidth, storage and transmission power.
• Produce a uniquely decodable (prefix) code so the receiver can decode it without separators.

Examples are Huffman, Shannon–Fano and LZW coding, as well as speech and image compression.

Huffman coding of "Kun Mandir Ma Janchhau Yatri"

Assumptions: case is ignored, and the space is counted as a symbol. The message has 28 symbols and 14 distinct symbols.

Huffman procedure: list the symbols by probability. Repeatedly combine the two least probable entries into one node whose weight is their sum, until only one node is left. In each merge, the first group listed gets bit 0 and the second group gets bit 1. Each symbol's code word is read from the root down to that symbol.

Merge steps:

1. {d} (1) + {c} (1) → 2
2. {k} (1) + {j} (1) → 2
3. {y} (1) + {t} (1) → 2
4. {i} (2) + {h} (2) → 4
5. {r} (2) + {m} (2) → 4
6. {d, c} (2) + {u} (2) → 4
7. {y, t} (2) + {k, j} (2) → 4
8. {space} (4) + {n} (3) → 7
9. {r, m} (4) + {i, h} (4) → 8
10. {y, t, k, j} (4) + {d, c, u} (4) → 8
11. {space, n} (7) + {a} (5) → 12
12. {y, t, k, j, d, c, u} (8) + {r, m, i, h} (8) → 16
13. {y, t, k, j, d, c, u, r, m, i, h} (16) + {space, n, a} (12) → 28

Average code length:

$$\bar L = \sum p_i l_i = \frac{101}{28} = 3.6071\ \text{bits/symbol}$$

Here the numerator is the total number of bits in the encoded message: $5(2) + 4(3) + 3(3) + 2(4) + 2(4) + 2(4) + 2(4) + 2(4) + 1(5) + 1(5) + 1(5) + 1(5) + 1(5) + 1(5) = 101$ bits.

Entropy:

$$H = -\sum p_i \log_2 p_i = 3.5801\ \text{bits/symbol}$$

Efficiency:

$$\eta = \frac{H}{\bar L} = \frac{3.5801}{3.6071} = 0.9925 = 99.25\%$$

Redundancy $= 1 - \eta = 0.75\%$.

A fixed-length code for 14 symbols needs $\lceil \log_2 14 \rceil = 4$ bits/symbol ($\eta = 89.50\%$). Huffman saves 9.82% of the bits.

Answer: $\bar L = 3.607$ bits/symbol, $H = 3.580$ bits/symbol, efficiency η ≈ 99.25%. The message needs 101 bits instead of 112 bits with a 4-bit fixed code.

Line codes for 1101010111

Bit period $T_b$, levels $\pm V$. Bipolar NRZ is drawn as full-width pulses whose polarity alternates for each 1. Manchester uses 1 = +V then −V, and 0 = −V then +V.

Unipolar RZ

    1   1   0   1   0   1   0   1   1   1  
+V ──| |─|     |─|     |─|     |─| |─| |─| 
 0   |─| |─────| |─────| |─────| |─| |─| |─

Bipolar NRZ (1s alternate +V/−V, 0 = 0)

    1   1   0   1   0   1   0   1   1   1  
+V ────|       |───|           |───|   |───
 0     |   |───|   |───|   |───|   |   |   
-V     |───|           |───|       |───|   

Polar NRZ

    1   1   0   1   0   1   0   1   1   1  
+V ────────|   |───|   |───|   |───────────
-V         |───|   |───|   |───|           

Manchester

    1   1   0   1   0   1   0   1   1   1  
+V ──| |─|   |───|   |───|   |───| |─| |─| 
-V   |─| |───|   |───|   |───|   |─| |─| |─

Communication impairments

Impairments are the effects of the channel that make the received signal differ from the transmitted one.

• Attenuation: the signal loses energy with distance. Example: a voice signal on a long copper line becomes weak, so repeaters or amplifiers are needed.
• Distortion: different frequency components are attenuated or delayed by different amounts, so the pulse shape changes. Example: pulses spread on a band-limited telephone line and cause ISI.
• Noise: unwanted random signals add to the signal. Examples are thermal noise in receivers, crosstalk between adjacent pairs in a cable, and impulse noise from lightning or switching.

Bit sequence: 1 0 0 1 1 1 0 1 0, bit period $T_b$, levels $\pm V$. The first 1 is taken as positive for the bipolar codes. Bipolar NRZ uses full-width pulses whose polarity alternates for each 1. AMI uses the same alternation with half-width (RZ) pulses.

a) Polar RZ

1 → +V for half the bit, 0 → −V for half the bit, then return to 0.

Polar RZ

    1   0   0   1   1   1   0   1   0  
+V ──|         |─| |─| |─|     |─|     
 0   |─| |─| |─| |─| |─| |─| |─| |─| |─
-V     |─| |─|             |─|     |─| 

b) Bipolar NRZ

0 → 0 V. Each 1 → full-width pulse with polarity alternating + − + − +.

Bipolar NRZ

    1   0   0   1   1   1   0   1   0  
+V ────|           |───|       |───|   
 0     |───────|   |   |   |───|   |───
-V             |───|   |───|           

c) AMI

0 → 0 V. Each 1 → half-width pulse with polarity alternating + − + − +.

AMI (RZ)

    1   0   0   1   1   1   0   1   0  
+V ──|             |─|         |─|     
 0   |─────────| |─| |─| |─────| |─────
-V             |─|     |─|             

d) Manchester

Transition at every mid-bit: 1 → +V then −V, 0 → −V then +V.

Manchester

    1   0   0   1   1   1   0   1   0  
+V ──|   |─| |───| |─| |─|   |───|   |─
-V   |───| |─|   |─| |─| |───|   |───| 

Statement

Shannon's channel capacity theorem (Shannon–Hartley law): for a channel of bandwidth $B$ Hz with additive white Gaussian noise of power $N = N_0 B$ and average signal power $S$, the channel capacity is

$$C = B \log_2\!\left(1 + \frac{S}{N}\right)\ \text{bits/s}$$

If the information rate $R \le C$, there is a coding scheme that sends the information with an arbitrarily small probability of error. If $R > C$, the error probability cannot be made small, whatever coding is used.

Implications in communication systems

1. Upper bound on data rate. No modem or code can beat $C$. Real designs are judged by how close they get, e.g. LDPC/turbo codes come within about 1 dB.
2. Bandwidth–power exchange. The same $C$ can come from a large $B$ with low SNR, or a small $B$ with high SNR.
   • Spread spectrum and CDMA work at very low SNR by using wide bandwidth.
   • High-order QAM (e.g. 256-QAM in cable modems) uses high SNR to pack more bits into a narrow band.
3. Error-free transmission over noisy channels is possible. Noise limits the rate, not the accuracy. This motivates channel coding (error-correcting codes).
4. Diminishing returns from power. $C$ grows only logarithmically with $S/N$. At high SNR, doubling the power adds only about 1 bit/s/Hz.
5. Limited gain from bandwidth. As $B \to \infty$, $C \to 1.44\, S/N_0$, so capacity stays finite because noise grows with bandwidth.
6. Shannon limit. The minimum $E_b/N_0$ for reliable communication is $\ln 2 = -1.6$ dB. This is the benchmark for power-efficient systems such as deep-space links.
7. Design guide. It tells designers the best spectral efficiency $C/B$ for a given SNR, e.g. 3.46 b/s/Hz at 10 dB.

Example: a telephone channel with $B = 3.1$ kHz and SNR = 30 dB has $C = 3100 \log_2(1001) \approx 30.9$ kb/s. This is close to the speed of the V.34 modem (33.6 kb/s), whose real SNR is slightly higher.

The maximum error-free data rate is the channel capacity, given by the Shannon–Hartley theorem for an AWGN channel:

$$C = B \log_2\!\left(1 + \frac{S}{N}\right)$$

Given

• Bandwidth $B = 1$ MHz $= 10^6$ Hz
• $(S/N)_{dB} = 10$ dB

Step 1: Convert SNR to a ratio

$$\frac{S}{N} = 10^{(S/N)_{dB}/10} = 10^{10/10} = 10$$

Step 2: Capacity

$$\begin{aligned} C &= 10^6 \log_2 (1 + 10) = 10^6 \log_2 11 \\ &= 10^6 \times \frac{\ln 11}{\ln 2} = 10^6 \times \frac{2.3979}{0.6931} \\ &= 10^6 \times 3.4594 \\ &= 3.459 \times 10^6\ \text{b/s} \end{aligned}$$

Interpretation

• The spectral efficiency is $C/B = 3.46$ b/s/Hz.
• Any rate up to about 3.46 Mb/s can, in theory, be sent with an arbitrarily small error probability using suitable (possibly very long) channel codes. Rates above this cannot be sent error-free.
• A practical scheme reaching this rate would need more than 2 bits/symbol at the Nyquist rate of $2B = 2$ Msymbols/s. That calls for multilevel signalling, e.g. M-ary with $M \ge 4$, together with strong coding.
• The "10 dB at the input of the channel decoder" means that the SNR is measured where decoding happens, so it is the SNR that sets the capacity.

Answer: Maximum error-free data rate $C \approx 3.46$ Mb/s.

Information

The amount of information in an event measures the uncertainty it removes: the less likely the event, the more information its occurrence gives. For a symbol $x_k$ with probability $p_k$, the self-information is

$$I(x_k) = \log_2 \frac{1}{p_k} = -\log_2 p_k\ \text{bits}$$

Properties:

• $I = 0$ when $p_k = 1$ (a certain event gives no information).
• $I \ge 0$, and $I(x_j) > I(x_k)$ if $p_j < p_k$.
• For independent events, information adds: $I(x_j x_k) = I(x_j) + I(x_k)$.

Units: bits (base 2), nats (base $e$) or decits (base 10). Example: a fair coin toss gives $\log_2 2 = 1$ bit.

Average information (entropy) of a long sequence

Consider a discrete memoryless source with alphabet $\{x_1, x_2, \dots, x_M\}$ and probabilities $\{p_1, p_2, \dots, p_M\}$, where $\sum p_k = 1$. The symbols are statistically independent.

Step 1. Take a long message of $N$ symbols ($N \to \infty$). By the law of large numbers, symbol $x_k$ occurs about

$$n_k = p_k N \text{ times}$$

Step 2. Each occurrence of $x_k$ carries $\log_2 (1/p_k)$ bits. So the information from all occurrences of $x_k$ is

$$I_k = n_k \log_2 \frac{1}{p_k} = N p_k \log_2 \frac{1}{p_k}$$

Step 3. The symbols are independent, so the information adds. The total information in the message is

$$I_{total} = \sum_{k=1}^{M} I_k = N \sum_{k=1}^{M} p_k \log_2 \frac{1}{p_k}$$

Step 4. The average information per symbol, called the entropy, is

$$H = \frac{I_{total}}{N} = \sum_{k=1}^{M} p_k \log_2 \frac{1}{p_k} = -\sum_{k=1}^{M} p_k \log_2 p_k\ \text{bits/symbol}$$

Information rate: if the source emits $r$ symbols/s, then $R = rH$ bits/s.

Properties of entropy

• $0 \le H \le \log_2 M$.
• $H = 0$ when one symbol has $p = 1$ (no uncertainty).
• $H = \log_2 M$ (the maximum) when all symbols are equally likely.
• For a binary source with $P(1) = p$: $H(p) = -p\log_2 p - (1-p)\log_2(1-p)$, which peaks at 1 bit when $p = 0.5$.

Example: a source with probabilities $\tfrac12, \tfrac14, \tfrac18, \tfrac18$ has

$$H = \tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 1.75\ \text{bits/symbol}$$

Source encoding removes redundancy from the source output to cut the number of bits. Channel encoding adds controlled redundancy so that errors caused by the channel can be detected or corrected.

 Source -> [Source enc.] -> [Channel enc.]
        -> [Modulator] -> Channel

Example: text is first Huffman-coded to make it smaller (source coding). A Hamming (7,4) code is then added so that single-bit errors can be corrected (channel coding).

Inter symbol interference

Inter symbol interference (ISI) is distortion in which the energy of one symbol spreads into the time slots of nearby symbols. It happens because the channel and filters have limited bandwidth, so pulses get wider in time. At a sampling instant, the received sample then holds tails of other pulses as well as the wanted symbol:

$$y(iT_b) = \mu a_i + \underbrace{\mu \sum_{k \ne i} a_k\, p\big((i-k)T_b\big)}_{\text{ISI}} + n(iT_b)$$

Nyquist criterion for zero ISI

If $p(t)$ is the overall pulse (transmit filter, channel and receive filter), ISI is zero when

$$p(nT_b) = \begin{cases} 1, & n = 0 \\ 0, & n \ne 0 \end{cases}$$

In the frequency domain this is

$$\sum_{k=-\infty}^{\infty} P\!\left(f - \frac{k}{T_b}\right) = T_b \quad \text{(constant)}$$

That is, copies of the pulse spectrum shifted by multiples of $R_b = 1/T_b$ must add up to a flat spectrum.

Nyquist pulse shaping for mitigation of ISI

1. Ideal Nyquist channel (minimum bandwidth). Choose a rectangular spectrum of width $B_0 = R_b/2$:

$$P(f) = \frac{1}{R_b}\,\text{rect}\!\left(\frac{f}{R_b}\right) \;\Rightarrow\; p(t) = \frac{\sin \pi R_b t}{\pi R_b t}$$

The sinc pulse is 1 at $t = 0$ and 0 at every other $nT_b$, so ISI is zero. $B_0 = R_b/2$ is the Nyquist bandwidth, and $R_b = 2B_0$ is the Nyquist rate. In practice it fails because the brick-wall filter cannot be built and the tails decay only as $1/|t|$, so any timing jitter adds up to large ISI.

2. Raised-cosine pulse shaping (practical). The spectrum rolls off smoothly with a cosine shape, with odd symmetry about $B_0$, so the folded spectrum is still flat:

$$p(t) = \text{sinc}(2B_0 t)\,\frac{\cos(2\pi\alpha B_0 t)}{1 - 16\alpha^2B_0^2t^2}$$ $$B_T = B_0(1 + \alpha) = \frac{R_b}{2}(1 + \alpha)$$

 P(f)
  |______
  |      \       alpha = 0   : brick wall, B = Rb/2
  |       \      alpha = 0.5 : B = 0.75 Rb
  |        \__   alpha = 1   : B = Rb
  +--------+--+---> f
          B0  B0(1+a)

The pulse shaping is usually split equally between transmitter and receiver as root-raised-cosine filters, which also gives matched filtering. Any ISI that remains because the channel is not ideal is removed with equalisers.

Bit sequence: 1 0 0 1 1 0 1 1 0 1, bit period $T_b$, levels $\pm V$.

Unipolar NRZ

1 → +V for the full bit, 0 → 0 V.

Unipolar NRZ

    1   0   0   1   1   0   1   1   0   1  
+V ────|       |───────|   |───────|   |───
 0     |───────|       |───|       |───|   

Polar RZ

1 → +V for half the bit, 0 → −V for half the bit, then 0.

Polar RZ

    1   0   0   1   1   0   1   1   0   1  
+V ──|         |─| |─|     |─| |─|     |─| 
 0   |─| |─| |─| |─| |─| |─| |─| |─| |─| |─
-V     |─| |─|         |─|         |─|     

AMI

0 → 0 V. The 1s are half-width pulses of alternating polarity: + − + − + −.

AMI (RZ)

    1   0   0   1   1   0   1   1   0   1  
+V ──|             |─|         |─|         
 0   |─────────| |─| |─────| |─| |─────| |─
-V             |─|         |─|         |─| 

Manchester

1 → +V then −V, 0 → −V then +V. There is a transition at every mid-bit.

Manchester

    1   0   0   1   1   0   1   1   0   1  
+V ──|   |─| |───| |─|   |───| |─|   |───| 
-V   |───| |─|   |─| |───|   |─| |───|   |─

Huffman code construction

Arrange the symbols by probability and repeatedly combine the two smallest. In each merge, the first group gets bit 0 and the second gets bit 1.

1. $x_4$ (0.15) + $x_5$ (0.10) → 0.25
2. $x_2$ (0.19) + $x_3$ (0.16) → 0.35
3. {x2,x3} (0.35) + {x4,x5} (0.25) → 0.60
4. {x2..x5} (0.60) + $x_1$ (0.40) → 1.00

              (1.00)
           0 /      \ 1
        (0.60)      x1 (0.40)
       0/    \1
   (0.35)    (0.25)
   0/  \1    0/  \1
  x2   x3   x4   x5

Efficiency

$$\begin{aligned} \bar L &= \sum p_i l_i = 0.40 + 0.57 + 0.48 + 0.45 + 0.30 = 2.20\ \text{bits/symbol} \\ H &= -\sum p_i \log_2 p_i \\ &= 0.4(1.3219) + 0.19(2.3959) + 0.16(2.6439) \\ &\quad + 0.15(2.7370) + 0.1(3.3219) \\ &= 2.1498\ \text{bits/symbol} \\ \eta &= \frac{H}{\bar L} = \frac{2.1498}{2.20} = 0.9772 = 97.72\% \end{aligned}$$

Comparison with fixed-length coding

Five symbols need $\lceil \log_2 5 \rceil = 3$ bits each:

$$\eta_{fixed} = \frac{H}{3} = \frac{2.1498}{3} = 0.7166 = 71.66\%$$

Huffman coding saves $3 - 2.2 = 0.8$ bits/symbol (about 26.7%). Its efficiency is close to the entropy limit.

Minimizing error in duo-binary coding

In duobinary signalling the received sample is $c_k = a_k + a_{k-1}$, so the decoder normally finds the present bit by subtracting the previous decision: $\hat a_k = c_k - \hat a_{k-1}$. One wrong decision then spoils all the following decisions. This is called error propagation. It is reduced or removed by:

• Precoding: before the duobinary filter, form $d_k = b_k \oplus d_{k-1}$ (modulo-2 sum). The receiver can then decide each bit from the present sample alone: if $|c_k| < 1$ (i.e. $c_k = 0$) then $\hat b_k = 1$; if $|c_k| > 1$ ($c_k = \pm 2$) then $\hat b_k = 0$. An error stays in one bit only.
• Using the correct decision thresholds ($\pm 1$) for the three-level signal and good receive filtering to keep noise low.

Information and entropy

• Information: the information carried by a message $m_k$ of probability $p_k$ is $I_k = \log_2 \frac{1}{p_k}$ bits. A less likely message carries more information; a certain message ($p_k = 1$) carries none.
• Entropy: the average information per symbol of a source with $M$ symbols:

$$H = \sum_{k=1}^{M} p_k \log_2 \frac{1}{p_k}\ \text{bits/symbol}, \qquad 0 \le H \le \log_2 M$$

Upper limit of channel capacity as $B \to \infty$

By the Shannon–Hartley theorem, with signal power $S$ and white noise of one-sided PSD $N_0$ (noise power $N = N_0 B$):

$$C = B\log_2\left(1 + \frac{S}{N_0 B}\right)$$

Multiply and divide by $S/N_0$ and put $x = \dfrac{S}{N_0 B}$:

$$\begin{aligned} C &= \frac{S}{N_0}\cdot\frac{N_0 B}{S}\log_2\left(1+\frac{S}{N_0B}\right) = \frac{S}{N_0}\cdot\frac{1}{x}\log_2(1+x) \\ &= \frac{S}{N_0}\log_2 (1+x)^{1/x} \end{aligned}$$

As $B \to \infty$, $x \to 0$ and $\lim_{x\to 0}(1+x)^{1/x} = e$. Therefore

$$C_\infty = \lim_{B\to\infty} C = \frac{S}{N_0}\log_2 e = 1.44\,\frac{S}{N_0}\ \text{bits/s}$$

So increasing bandwidth does not give unlimited capacity, because noise power also grows with $B$. Capacity saturates at $1.44\,S/N_0$.

Putting $S = E_b C$ at the limit gives $\dfrac{E_b}{N_0} = \ln 2 = 0.693$, i.e. −1.6 dB (the Shannon limit): no system can communicate error-free below this $E_b/N_0$.

Answer: $C_\infty = 1.44\,S/N_0$ bits/s.

Line codes convert the bit stream into electrical pulses. Conventions used (bit period $T_b$, amplitude $V$):

• Polar NRZ: 1 → $+V$, 0 → $-V$ for the full bit.
• Polar RZ: 1 → $+V$, 0 → $-V$ for the first half bit, then 0.
• Manchester: 1 → $+V$ then $-V$ (high-to-low at mid-bit); 0 → $-V$ then $+V$.
• AMI: 0 → 0 V; successive 1s alternate $+V$, $-V$ (first 1 taken as $+V$, full-width pulses).

Bit sequence: 1 1 0 1 0 1 0 1 1 1

bits  1   1   0   1   0   1   0   1   1   1  

Polar NRZ:
+V  |‾‾‾‾‾‾‾‾    ‾‾‾‾    ‾‾‾‾    ‾‾‾‾‾‾‾‾‾‾‾‾
 0  |
-V  |        ____    ____    ____

Polar RZ:
+V  |‾‾  ‾‾      ‾‾      ‾‾      ‾‾  ‾‾  ‾‾
 0  |  --  --  --  --  --  --  --  --  --  --
-V  |        __      __      __

Manchester:
+V  |‾‾  ‾‾    ‾‾‾‾    ‾‾‾‾    ‾‾‾‾  ‾‾  ‾‾
 0  |
-V  |  __  ____    ____    ____    __  __  __

AMI (bipolar NRZ):
+V  |‾‾‾‾        ‾‾‾‾            ‾‾‾‾    ‾‾‾‾
 0  |        ----    ----    ----
-V  |    ____            ____        ____

Level in each bit (a pair means first half, second half):

Observations: polar NRZ has a DC component when 1s are more frequent (here seven 1s); Manchester has a transition in every bit, so it carries timing; AMI has zero average value because its marks alternate.

A message is the actual symbol or sequence of symbols sent by the source (a letter, a word, a sample value). Information is the measure of the uncertainty removed when that message is received; it depends only on how probable the message is, not on its meaning.

Message vs information

Relation between message, information and entropy

1. Information of one message. If message $m_k$ occurs with probability $p_k$, its information content is

$$I_k = \log_2\frac{1}{p_k}\ \text{bits}$$

Properties: $I_k \ge 0$; $I_k = 0$ for $p_k = 1$; $I_k > I_j$ if $p_k < p_j$; for independent messages $I(m_k m_j) = I_k + I_j$.

2. Entropy = average information per message. A source emits $M$ different messages with different information. In a long sequence of $N$ messages, $m_k$ appears about $N p_k$ times, so the total information is

$$I_{total} = \sum_{k=1}^{M} N p_k \log_2\frac{1}{p_k}$$

Dividing by $N$:

$$H = \frac{I_{total}}{N} = \sum_{k=1}^{M} p_k \log_2\frac{1}{p_k}\ \text{bits/message}$$

So entropy is the expected (mean) value of the information, $H = E[I_k]$. It lies in $0 \le H \le \log_2 M$, with the maximum when all messages are equally likely.

3. Information rate. If the source sends $r$ messages per second, the information rate is $R = rH$ bits/s.

Example

A source sends four messages with probabilities $\tfrac12, \tfrac14, \tfrac18, \tfrac18$.

$$H = \tfrac12(1)+\tfrac14(2)+\tfrac18(3)+\tfrac18(3) = 1.75\ \text{bits/message}$$

A message sequence of 1000 symbols therefore carries about $1000 \times 1.75 = 1750$ bits of information, although each individual message carries 1, 2 or 3 bits. The message is the carrier; information is what it carries; entropy is the average amount carried per message.