Information and coding introduction
Введено| English | Значение |
|---|---|
| entropy/ˈentrəpi/ | энтропия |
| Hamming code | код Хэмминга |
| syndrome | syndrome |
| channel capacity | ёмкость канала |
The edges of the map
- How few bits can a source be squeezed into? How many bits can a channel carry?
- Information theory answers both, and codes move real systems towards those limits.
Entropy
- Entropy 熵 $H = \sum p\log_{2}(1/p)$ measures a source's average surprise, in bits per symbol.
- It is the fewest bits per symbol any code can average. The gap between $H$ and a fixed-length code is redundancy.
A source has four equally likely symbols. What is its entropy, in bits?
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
$4 \times \tfrac{1}{4}\log_{2}4 = 2$ bits. Equal probabilities give the most surprise.
A source has probabilities 1/2, 1/4 and 1/4. What is its entropy, in bits? Give 1 decimal place.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
$0.5 \times 1 + 0.25 \times 2 + 0.25 \times 2 = 1.5$ bits.
Huffman coding
- Huffman's method merges the two least likely symbols again and again, building a tree. Likely symbols get short codewords.
- When every probability is a power of 1/2, the average length equals $H$ exactly; otherwise it is within one bit.
What codeword lengths does Huffman give for probabilities 1/2, 1/4, 1/4?
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Merge the two 1/4s into 1/2, then merge with the other 1/2. The average, 1.5 bits, equals H.
Worked example: the quartile source
- Probabilities 1/2, 1/4, 1/8, 1/8: $H = 0.5 + 0.5 + 0.375 + 0.375 = 1.75$ bits, against 2 bits for fixed length.
- Huffman gives lengths 1, 2, 3, 3, which average exactly 1.75 bits.
Huffman coding always reaches the entropy exactly.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Only when every probability is a power of 1/2. Otherwise the average is within one bit of H.
Channel codes
- A channel code adds redundancy on purpose, so the receiver can find and fix errors.
- The Hamming code 汉明码 (7,4) adds 3 parity bits to 4 data bits. It corrects any single error, at rate 4/7.
Worked example: Hamming (7,4)
- Data 1011 encodes to 0110011, with parity bits in positions 1, 2 and 4.
- Flip bit 5: the three parity checks fail in the pattern 101, which is 5 in binary. The syndrome 伴随式 names the wrong bit.
A Hamming (7,4) receiver computes the syndrome 110. Which bit position is wrong?
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
110 in binary is 6. Flip bit 6 and the word is corrected.
Channel capacity
- Channel capacity 信道容量 $C = B\log_{2}(1 + S/N)$ is the most any code can carry without errors.
- Capacity grows in proportion to bandwidth but only with the log of power.
A 1 MHz channel has an SNR of 15 (a ratio). What is its capacity, in Mbit/s?
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
$C = 10^{6} \times \log_{2}16 = 4$ Mbit/s.
Worked example: the modem ceiling
- A 3 kHz phone line at 30 dB SNR: $C = 3000 \times \log_{2}(1001) = 29.9$ kbit/s, the dial-up limit.
- 10 dB more SNR adds only about 3.3 bit/s per hertz.
Three common slips
- The wrong log. Bits need $\log_{2}$.
- "Huffman always reaches $H$." Only when every probability is a power of 1/2.
- Capacity as a guarantee. Codes approach it; none beat it.
Match each idea to the limit it sets.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
Source coding removes redundancy; channel coding adds it back on purpose; capacity bounds both.
Recap
- $H = \sum p\log_{2}(1/p)$ is the floor for source coding.
- Hamming (7,4) fixes one error per block at rate 4/7.
- $C = B\log_{2}(1 + S/N)$ is the ceiling for the channel.