Information Theory

01

(IC 1.1) Information theory and Coding - Outline of topics

14 min

02

(IC 1.2) Applications of Compression codes

11 min

03

(IC 1.3) Applications of Error-correcting codes

29 min

04

(IC 1.4) Source-channel separation

12 min

05

(IC 1.5) Examples of source-encoder-channel pipelines

15 min

06

(IC 1.6) A different notion of "information"

18 min

07

(IC 2.1) A puzzle on weighing coins

5 min

08

(IC 2.2) Symbol codes - terminology and notation

13 min

09

(IC 2.3) Symbol codes - definition and examples

14 min

10

(IC 2.4) Decoding - prefix versus non-prefix

16 min

11

(IC 2.5) Prefix codes

15 min

12

(IC 2.6) Prefix codes - remarks and what's next

5 min

13

(IC 2.7) Expected codeword length

13 min

14

(IC 2.8) Kraft-McMillan inequality - statement

13 min

15

(IC 2.9) Kraft-McMillan - proof of (a)

18 min

16

(IC 2.10) Kraft-McMillan - examples for (b)

20 min

17

(IC 2.11) Kraft-McMillan - proof sketch for (b)

12 min

18

(IC 3.1) Entropy as a lower bound on expected length (part 1)

15 min

19

(IC 3.2) Entropy as a lower bound on expected length (part 2)

13 min

20

(IC 3.3) Entropy as a lower bound on expected length (part 3)

17 min

21

(IC 3.4) Remark - an alternate proof

1 min

22

(IC 3.5) Bounds on optimal expected length

13 min

23

(IC 3.6) Example - entropy as a lower bound

3 min

24

(IC 3.7) Block codes for compression

13 min

25

(IC 3.8) Entropy of i.i.d. random variables

8 min

26

(IC 3.9) Source coding theorem (optimal lossless compression)

15 min

27

(IC 3.10) Relative entropy as the mismatch inefficiency

15 min

28

(IC 4.1) Huffman coding - introduction and example

12 min

29

(IC 4.2) Huffman coding - more examples

13 min

30

(IC 4.3) B-ary Huffman codes

12 min

31

(IC 4.4) Weighted minimization with Huffman coding

6 min

32

(IC 4.5) An issue with Huffman coding

11 min

33

(IC 4.6) Optimality of Huffman codes (part 1) - inverse ordering

14 min

34

(IC 4.7) Optimality of Huffman codes (part 2) - weak siblings

21 min

35

(IC 4.8) Optimality of Huffman codes (part 3) - sibling codes

8 min

36

(IC 4.9) Optimality of Huffman codes (part 4) - extension and contraction

18 min

37

(IC 4.10) Optimality of Huffman codes (part 5) - extension lemma

22 min

38

(IC 4.11) Optimality of Huffman codes (part 6) - induction

14 min

39

(IC 4.12) Optimality of Huffman codes (part 7) - existence

23 min

40

(IC 4.13) Not every optimal prefix code is Huffman

9 min

41

(IC 5.1) Arithmetic coding - introduction

6 min

42

(IC 5.2) Arithmetic coding - Example #1

29 min

43

(IC 5.3) Arithmetic coding - Example #2

26 min

44

(IC 5.4) Why the interval needs to be completely contained

25 min

45

(IC 5.5) Rescaling operations for arithmetic coding

23 min

46

(IC 5.6) Encoder for arithmetic coding (infinite-precision)

16 min

47

(IC 5.7) Decoder for arithmetic coding (infinite-precision)

19 min

48

(IC 5.8) Near optimality of arithmetic coding

32 min

49

(IC 5.9) Computational complexity of arithmetic coding

19 min

50

(IC 5.10) Generalizing arithmetic coding to non-i.i.d. models

24 min

51

(IC 5.11) Finite-precision arithmetic coding - Rescaling

31 min

52

(IC 5.12) Finite-precision arithmetic coding - Setup

7 min

53

(IC 5.13) Finite-precision arithmetic coding - Encoder

17 min

54

(IC 5.14) Finite-precision arithmetic coding - Decoder

24 min