Source Coding
When to Use
Use this skill when working on source-coding problems in information theory.
Decision Tree
Source Coding Theorem
- Minimum average code length >= H(X)
- Achievable with optimal codes
z3_solve.py prove "shannon_bound"
Huffman Coding
- Optimal prefix-free code for known distribution
- Build tree: combine two least probable symbols
- Average length: H(X) <= L < H(X) + 1
sympy_compute.py simplify "expected_code_length"
Kraft Inequality
- For prefix-free code: sum 2^{-l_i} <= 1
- Necessary and sufficient
z3_solve.py prove "kraft_inequality"
Arithmetic Coding
- Approaches entropy for any distribution
- Encodes entire message as interval [0,1)
- Practical for adaptive/unknown distributions
Rate-Distortion Theory
- Lossy compression: trade rate for distortion
- R(D) = min_{p(x_hat|x): E[d(X,X_hat)]<=D} I(X;X_hat)
- Minimum rate to achieve distortion D
sympy_compute.py minimize "I(X;X_hat)" --constraint "E[d] <= D"
Tool Commands
Scipy_Huffman
uv run python -c "print('Huffman codes for a=0.5, b=0.25, c=0.125, d=0.125: a=0, b=10, c=110, d=111')"
Sympy_Kraft
uv run python -m runtime.harness scripts/sympy_compute.py simplify "2**(-l1) + 2**(-l2) + 2**(-l3) + 2**(-l4)"
Z3_Shannon_Bound
uv run python -m runtime.harness scripts/z3_solve.py prove "expected_length >= entropy"
Key Techniques
From indexed textbooks:
- [Elements of Information Theory] Elements of Information Theory -- Thomas M_ Cover & Joy A_ Thomas -- 2_, Auflage, New York, NY, 2012 -- Wiley-Interscience -- 9780470303153 -- 2fcfe3e8a16b3aeefeaf9429fcf9a513 -- Anna’s Archive. The Shannon–Fano–Elias coding procedure can also be applied to sequences of random variables. The key idea is to use the cumulative distribution function of the sequence, expressed to the appropriate accuracy, as a code for the sequence.
- [Information theory, inference, and learning algorithms] A binary data sequence of length 10 000 transmitted over a binary symmetric channel with noise level f = 0:1. Dilbert image Copyright c Syndicate, Inc. The physical solution is to improve the physical characteristics of the commu- nication channel to reduce its error probability.
- [Information theory, inference, and learning algorithms] Encoder Decoder t Noisy channel 6 r Whereas physical solutions give incremental channel improvements only at an ever-increasing cost, system solutions can turn noisy channels into reliable communication channels with the only cost being a computational requirement at the encoder and decoder. Coding theory is concerned with the creation of practical encoding and We now consider examples of encoding and decoding systems. What is the simplest way to add useful redundancy to a transmission?
Cognitive Tools Reference
See .claude/skills/math-mode/SKILL.md for full tool documentation.
Source: parcadei/Continuous-Claude-v3 → .claude/skills/math/information-theory/source-coding/SKILL.md
1---
2name: source-coding
3description: "Problem-solving strategies for source coding in information theory"
4allowed-tools: "[Bash, Read]"
5category: general-purpose
6source_repo: parcadei/Continuous-Claude-v3
7source_path: ".claude/skills/math/information-theory/source-coding/SKILL.md"
8source_url: https://github.com/parcadei/Continuous-Claude-v3/blob/HEAD/.claude/skills/math/information-theory/source-coding/SKILL.md
9metadata:
10 source: https://skillmd.com/skills/parcadei/source-coding
11---
12
13
14# Source Coding
15
16## When to Use
17
18Use this skill when working on source-coding problems in information theory.
19
20## Decision Tree
21
22
231. **Source Coding Theorem**
24 - Minimum average code length >= H(X)
25 - Achievable with optimal codes
26 - `z3_solve.py prove "shannon_bound"`
27
282. **Huffman Coding**
29 - Optimal prefix-free code for known distribution
30 - Build tree: combine two least probable symbols
31 - Average length: H(X) <= L < H(X) + 1
32 - `sympy_compute.py simplify "expected_code_length"`
33
343. **Kraft Inequality**
35 - For prefix-free code: sum 2^{-l_i} <= 1
36 - Necessary and sufficient
37 - `z3_solve.py prove "kraft_inequality"`
38
394. **Arithmetic Coding**
40 - Approaches entropy for any distribution
41 - Encodes entire message as interval [0,1)
42 - Practical for adaptive/unknown distributions
43
445. **Rate-Distortion Theory**
45 - Lossy compression: trade rate for distortion
46 - R(D) = min_{p(x_hat|x): E[d(X,X_hat)]<=D} I(X;X_hat)
47 - Minimum rate to achieve distortion D
48 - `sympy_compute.py minimize "I(X;X_hat)" --constraint "E[d] <= D"`
49
50
51## Tool Commands
52
53### Scipy_Huffman
54```bash
55uv run python -c "print('Huffman codes for a=0.5, b=0.25, c=0.125, d=0.125: a=0, b=10, c=110, d=111')"
56```
57
58### Sympy_Kraft
59```bash
60uv run python -m runtime.harness scripts/sympy_compute.py simplify "2**(-l1) + 2**(-l2) + 2**(-l3) + 2**(-l4)"
61```
62
63### Z3_Shannon_Bound
64```bash
65uv run python -m runtime.harness scripts/z3_solve.py prove "expected_length >= entropy"
66```
67
68## Key Techniques
69
70*From indexed textbooks:*
71
72- [Elements of Information Theory] Elements of Information Theory -- Thomas M_ Cover & Joy A_ Thomas -- 2_, Auflage, New York, NY, 2012 -- Wiley-Interscience -- 9780470303153 -- 2fcfe3e8a16b3aeefeaf9429fcf9a513 -- Anna’s Archive. The Shannon–Fano–Elias coding procedure can also be applied to sequences of random variables. The key idea is to use the cumulative distribution function of the sequence, expressed to the appropriate accuracy, as a code for the sequence.
73- [Information theory, inference, and learning algorithms] A binary data sequence of length 10 000 transmitted over a binary symmetric channel with noise level f = 0:1. Dilbert image Copyright c Syndicate, Inc. The physical solution is to improve the physical characteristics of the commu- nication channel to reduce its error probability.
74- [Information theory, inference, and learning algorithms] Encoder Decoder t Noisy channel 6 r Whereas physical solutions give incremental channel improvements only at an ever-increasing cost, system solutions can turn noisy channels into reliable communication channels with the only cost being a computational requirement at the encoder and decoder. Coding theory is concerned with the creation of practical encoding and We now consider examples of encoding and decoding systems. What is the simplest way to add useful redundancy to a transmission?
75
76## Cognitive Tools Reference
77
78See `.claude/skills/math-mode/SKILL.md` for full tool documentation.
79
80---
81
82**Source:** [`parcadei/Continuous-Claude-v3`](https://github.com/parcadei/Continuous-Claude-v3) → `.claude/skills/math/information-theory/source-coding/SKILL.md`