Information and Coding Theory - Complete Midterm Guide

วิธีอ่านให้ได้คะแนน

วิชานี้มีแกนเดียวที่ต่อกันเป็นลูกโซ่: เราอยากส่งข้อมูลให้สั้นที่สุดแต่ยังถอดกลับได้ถูกต้อง ดังนั้นต้องวัดก่อนว่าข้อมูลมีความไม่แน่นอนเท่าไร แล้วจึงออกแบบ code ให้เข้าใกล้ขีดจำกัดนั้น

เข้าใจ source และ probability ให้แม่น เพราะทุกสูตรเริ่มจากความน่าจะเป็น
คำนวณ information content และ entropy ให้คล่อง
แยกให้ออกว่า code สั้น, uniquely decodable, instantaneous เป็นคนละเงื่อนไข
ฝึกวาด/อ่าน code tree และตรวจ prefix
ฝึก Huffman และ run-length เพราะเป็นโจทย์คำนวณที่ออกง่าย

สูตรที่ต้องจำก่อน \[ I(x)=-\log_2 P(x) \] \[ H(S)=-\sum_i p_i\log_2 p_i \] \[ L=\sum_{i=1}^{M}p_i\tau_i \] \[ r(S)=1-\frac{H(S)}{\log_2 M} \] \[ \text{Kraft: }q^{-\tau_1}+q^{-\tau_2}+\cdots+q^{-\tau_M}\le 1 \]

Lec1 - ภาพรวม Information Theory

Information Theory คืออะไร

Information Theory คือการนิยาม วัด และใช้ข้อมูลอย่างมีประสิทธิภาพ ในสไลด์เน้นแนวคิดของ Shannon: ไม่สนความหมายส่วนตัวของข้อความ แต่สนด้าน objective ว่าเหตุการณ์นั้นเกิดยากแค่ไหนและต้องใช้ bit เท่าไรในการแทนข้อมูล

Subjective aspect

ความหมายหรือคุณค่าต่อคนรับ เช่น ข่าวเดียวกันอาจสำคัญกับแต่ละคนไม่เท่ากัน

Objective aspect

ปริมาณข้อมูลที่วัดได้จากความน่าจะเป็น ยิ่งเกิดยาก ยิ่งให้ข้อมูลมาก

สิ่งที่วิชานี้ทำ

ทำให้ข้อมูลสั้นลงด้วย source coding และทำให้ส่งผ่านช่องสัญญาณที่มี noise ได้ดีขึ้นด้วย channel coding

Communication Model

Morse model มองการสื่อสารเป็นลำดับจากผู้ส่งไปผู้รับ เช่น voice -> smartphone -> internet -> smartphone -> recipient ส่วน Shannon model เพิ่มความจริงสำคัญว่า channel มี noise ทำให้ข้อมูลเสียหายได้

Source

Transmitter / Encoder

Channel + Noise

Receiver / Decoder

Recipient

Digital idea

คอมพิวเตอร์ประมวลผลด้วย 0 และ 1 จึงต้องแปลงข้อมูลจริงเป็น binary data ก่อนส่ง/เก็บ และแปลงกลับหลังรับ

Source Coding vs Channel Coding

เรื่อง	Source coding	Channel coding
เป้าหมาย	ลดความยาวเฉลี่ยของข้อมูล	ลดโอกาสรับข้อมูลผิดเมื่อมี noise
แนวคิด	ลบ redundancy / compression	เพิ่ม redundancy อย่างควบคุมได้ / error protection
ตัวอย่าง	ZIP, JPEG, MP3, Huffman	repetition code, parity, error-correcting code
จำง่าย	ทำให้สั้น	ทำให้ทน noise

ตัวอย่าง source coding จาก Lec1: code C1 หรือ C2 สั้นกว่า

Information	Probability	C1	C2
Yes	0.3	0	1
No	0.2	1	10
Neither	0.5	10	0

C1 มี average length = 0.3(1)+0.2(1)+0.5(2)=1.5 bits/symbol

C2 มี average length = 0.3(1)+0.2(2)+0.5(1)=1.2 bits/symbol

ดังนั้น C2 ดีกว่า เพราะให้ code สั้นกับเหตุการณ์ที่เกิดบ่อยที่สุดคือ Neither

ตัวอย่าง channel coding: 0 -> 000, 1 -> 111

ถ้า channel ผิด bit ด้วย probability 0.1 และถูกด้วย probability 0.9 การส่ง 000 แล้วตัดสินด้วย majority vote จะถูกเมื่อมี 0 error หรือ 1 error

\[ P(\text{correct})=0.9^3+3(0.1)(0.9^2)=0.729+0.243=0.972 \] \[ P(\text{error})=3(0.1^2)(0.9)+0.1^3=0.028 \]

ข้อเสียคือใช้เวลาส่ง 3 เท่า แต่รับผิดพลาดน้อยลง

Sampling Theorem และ Quantization

ข้อมูลจริง เช่น เสียง ภาพ สัญญาณไฟฟ้า มักเป็น analog คือเปลี่ยนต่อเนื่องตามเวลา ถ้าจะใช้ระบบดิจิทัลต้องทำสองขั้น:

Sampling เลือกค่าของสัญญาณที่เวลาบางจุด
Quantization ปัดค่าต่อเนื่องให้เป็นระดับจำกัดตามจำนวน bit

Sampling theorem \[ f_s\ge 2W\ \text{samples/sec} \] \[ T_s\le \frac{1}{2W}\ \text{seconds} \]

ตัวอย่าง quantization 4-bit ช่วง 0 ถึง 5 V

4 bit มี 2^4 = 16 ระดับ ความกว้างแต่ละช่วง = 5/16 = 0.3125 V ถ้าค่า 2.6 V จะอยู่ในช่วง 2.5 ถึง 2.8125 จึงแทนด้วยระดับที่ 8 ถ้านับแบบ 0 ถึง 15

Lec2 - Source Model

Information source คือแหล่งกำเนิดสัญลักษณ์ เช่น ลูกเต๋า ไพ่ ตัวอักษร สถานะเครื่องจักร หรือ pixel ขาวดำ แต่ละผลลัพธ์เรียกว่า source symbol

รูปแบบ source \[ S=\begin{pmatrix}a_1,a_2,\ldots,a_M\\p_1,p_2,\ldots,p_M\end{pmatrix} \] \[ \sum_{i=1}^{M}p_i=1,\quad p_i\ge 0 \]

ตัวอย่าง source

โยนเหรียญ 5 ครั้ง นับจำนวนหัว

source symbols คือ 0,1,2,3,4,5 มี M=6

ถ้าเหรียญยุติธรรม probability คือ 1/32, 5/32, 10/32, 10/32, 5/32, 1/32

ทอยลูกเต๋า

source symbols คือ 1,2,3,4,5,6 และ probability เท่ากันคือ 1/6

แต่ละครั้งเป็นอิสระ -> memoryless, มีผลลัพธ์แยกกันชัดเจน -> discrete, probability ไม่เปลี่ยนตามเวลา -> stationary

คำที่ต้องตอบให้เป็น

memoryless ผลลัพธ์รอบนี้ไม่ขึ้นกับอดีต

discrete สัญลักษณ์เป็นชุดจำกัด/นับได้

stationary distribution ไม่เปลี่ยนตามเวลา

Information Content และ Entropy

Information Content

หลักสำคัญ: เหตุการณ์ที่เกิดยากให้ข้อมูลมาก เหตุการณ์ที่เกิดแน่นอนแทบไม่ให้ข้อมูลเลย

นิยาม \[ I=-\log_2 P\quad\text{bit} \] \[ I=-\log_e P\quad\text{nat} \]

ตัวอย่างไพ่ 52 ใบ

A = ได้ไพ่ 6 ที่ suit เป็น heart มี P=1/52 ดังนั้น I(A)=log2(52)=5.700 bits

B = suit is heart มี P=1/4 ดังนั้น I(B)=2 bits

C = rank เป็น 6 มี P=1/13 ดังนั้น I(C)=log2(13)=3.700 bits

เหตุการณ์ A คือ B ∩ C และในสำรับมาตรฐาน suit กับ rank เป็นอิสระกัน จึงได้ I(A)=I(B)+I(C)

Entropy

Entropy คือ average information content หรือปริมาณข้อมูลเฉลี่ยต่อ source symbol ถ้าค่า entropy สูง แปลว่า source เดายาก/กำกวมมาก

สูตร entropy \[ H(S)=\sum_{i=1}^{M}p_i I_i=-\sum_{i=1}^{M}p_i\log_2 p_i \] \[ \text{unit: bits/source symbol} \]

ตัวอย่าง S = (1/2, 1/3, 1/6)

\[ H(S)=-\frac12\log_2\frac12-\frac13\log_2\frac13-\frac16\log_2\frac16 \] \[ =0.5+\frac13\log_2 3+\frac16\log_2 6=1.459\ \text{bits/symbol} \]

ตัวอย่าง uniform 3 symbols

\[ S=\begin{pmatrix}a_1,a_2,a_3\\\frac13,\frac13,\frac13\end{pmatrix} \] \[ H(S)=\log_2 3=1.585\ \text{bits/symbol} \]

Binary Entropy

\[ S=\begin{pmatrix}a_1,a_2\\p,1-p\end{pmatrix} \] \[ H(p)=-p\log_2 p-(1-p)\log_2(1-p) \]

ถ้า p=0 หรือ p=1 จะรู้ผลแน่นอน entropy = 0 ถ้า p=1/2 จะเดายากที่สุด entropy = 1 bit

ขอบเขตที่ชอบออกสอบ \[ 0\le H(S)\le \log_2 M \]

H=0 เมื่อมีสัญลักษณ์หนึ่งเกิดแน่นอน p=1 ที่เหลือ p=0

H=log2 M เมื่อทุกสัญลักษณ์มี probability เท่ากัน p_i=1/M

Lec3 - Redundancy

Redundancy คือความฟุ่มเฟือยของ source เมื่อเทียบกับกรณีที่ entropy มากที่สุด ถ้า distribution ไม่สม่ำเสมอมาก จะมี redundancy สูง เพราะเราสามารถทายหรือบีบอัดได้มากขึ้น

Relative redundancy \[ r(S)=1-\frac{H(S)}{\log_2 M} \]

Source	H(S)	log2 M	r(S)	ความหมาย
(1/2, 1/3, 1/6)	1.459	1.585	0.079	redundancy ต่ำ
(1/3, 1/3, 1/3)	1.585	1.585	0	ไม่มี redundancy เชิง distribution
(0.9, 0.05, 0.05)	0.569	1.585	0.641	เดาได้บ่อยว่าคือ symbol แรก
(0.99, 0.005, 0.005)	0.091	1.585	0.943	redundancy สูงมาก

ตัวอย่างภาษาอังกฤษในสไลด์: ตัวอักษร E, T, A, O, I, N เกิดบ่อย ส่วน J, Q, X, Z เกิดน้อย ถ้ามองตัวอักษรเป็น memoryless source จะมี redundancy เพราะตัวอักษรไม่ได้เกิดเท่ากันหมด จากความถี่ในสไลด์คำนวณได้ประมาณ H=4.211 bits/letter และ r=0.104 เมื่อเทียบกับ log2(26)

Encoding และ Average Code Length

Coding คือการแปลง source symbol เป็น code word ก่อนส่งหรือเก็บ ส่วน code alphabet คือสัญลักษณ์ที่ใช้สร้าง code word เช่น binary code มี alphabet {0,1} จึงเป็น q=2 code

Average code length \[ L=\sum_{i=1}^{M}p_i\tau_i \]

โดย \(\tau_i\) คือความยาว code word ของ \(a_i\)

ตัวอย่างจาก Lec3: S=(a,b,c,d)=(0.4,0.3,0.2,0.1)

code: a->0, b->10, c->110, d->1110

\[ L=0.4(1)+0.3(2)+0.2(3)+0.1(4)=2\ \text{bits/symbol} \]

Efficient Coding

คำว่า efficient ในบริบทนี้หมายถึงทำให้ average code length สั้นที่สุดเท่าที่ทำได้ โดยยังถอดรหัสกลับได้

ตัวอย่าง 3 symbols

S=(a1,a2,a3) มี probability (1/2,1/3,1/6)

C3: a1->00, a2->01, a3->10 ให้ L=2 bits/symbol

C4: a1->1, a2->01, a3->001 ให้ L=0.5(1)+(1/3)(2)+(1/6)(3)=1.667 bits/symbol

C4 สั้นกว่า แต่ต้องเช็คต่อว่า decode ได้ถูกต้องไหม ซึ่งนำไปสู่หัวข้อถัดไป

Lec4 - Uniquely Decodable และ Instantaneous Code

Uniquely Decodable Code

Code เป็น uniquely decodable ถ้า bit string ที่ได้สามารถถอดกลับเป็น source symbol sequence ได้ทางเดียวเท่านั้น ถ้าถอดได้หลายแบบถือว่าไม่ดี แม้ average length จะสั้นก็ตาม

ตัวอย่าง C1/C2 ไม่ uniquely decodable

ถ้า code มี a1->0, a2->1, a3->10 แล้ว bit string 0100011001 ถอดได้อย่างน้อยสองแบบ:

0 / 10 / 0 / 0 / 1 / 10 / 0 / 1 และ 0 / 1 / 0 / 0 / 0 / 1 / 1 / 0 / 0 / 1

ตัวอย่าง C3 uniquely decodable

C3: a1->00, a2->01, a3->10 เมื่อ encode sequence a1 a3 a1 a1 a2 a3 a1 a2 จะได้ 0010000001100001 และ decode ได้ทางเดียว

Instantaneous Code หรือ Prefix Code

Instantaneous code คือ code ที่ decode ได้ทันทีเมื่ออ่านถึงจุดสิ้นสุดของ code word โดยไม่ต้องมอง bit ถัดไป เงื่อนไขสำคัญคือไม่มี code word ใดเป็น prefix ของ code word อื่น

Instantaneous

รับ bit แล้วเดิน code tree ถึง leaf ก็ปล่อย symbol ได้ทันที

Non-instantaneous

ต้องมองข้างหน้าก่อนจึงรู้ว่าควรตัด code word ตรงไหน

ข้อจำง่าย

instantaneous -> uniquely decodable เสมอ แต่ uniquely decodable ไม่จำเป็นต้อง instantaneous

วิธีตรวจ Instantaneous

ดูทุก code word ว่ามีตัวไหนเป็นต้นของอีกตัวหรือไม่
หรือวาด code tree: code word ทุกตัวต้องจบที่ leaf เท่านั้น
ถ้าความยาวเท่ากันหมด มักเป็น instantaneous ทันทีถ้าไม่มี code ซ้ำ

Code C4 จากตาราง a1,a2,a3 ในสไลด์: instantaneous

flowchart TD
  R((root))
  R -- "1" --> A1["a1
code 1"]
  R -- "0" --> N0(( ))
  N0 -- "1" --> A2["a2
code 01"]
  N0 -- "0" --> N00(( ))
  N00 -- "1" --> A3["a3
code 001"]

Code C5 จากตาราง a1,a2,a3 ในสไลด์: non-instantaneous

flowchart TD
  R((root))
  R -- "1" --> A1["a1
code 1"]
  A1 -- "0" --> A2["a2
code 10"]
  A2 -- "0" --> A3["a3
code 100"]

Exercise จาก Lec4: C1-C4 instant หรือไม่

Code	Words	ผล	เหตุผล
C1	0, 01, 011, 0111	ไม่ instant	0 เป็น prefix ของตัวอื่น
C2	0, 01, 110, 001	ไม่ instant	0 เป็น prefix ของ 01 และ 001
C3	0, 10, 110, 111	instant	ไม่มีคำใดเป็น prefix ของอีกคำ
C4	00, 01, 10, 11	instant	fixed length 2 bit

Exercise report Lec4: เปรียบเทียบ C1 และ C2

Symbol	p	C1	C2
a1	1/8	110	0010
a2	3/16	101	000
a3	3/8	00	1
a4	1/16	1111	0011
a5	1/4	01	01

L(C1)=2.4375 bits/symbol, L(C2)=2.1875 bits/symbol

ทั้งสองเป็น prefix code จึง instantaneous และ uniquely decodable แต่ C2 ดีกว่าเพราะ average length สั้นกว่า

Source Extension หรือ Block Coding

Source extension คือการรวมหลาย source symbols เป็นหนึ่ง block แล้วเข้ารหัสทีละ block วิธีนี้ช่วยให้ average code length ต่อ symbol เข้าใกล้ entropy มากขึ้น

ตัวอย่าง S=(a,b)=(1/3,2/3)

ถ้า n=2 จะได้ symbols ของ S^2 คือ aa, ab, ba, bb

\[ S^2=\begin{pmatrix}aa,ab,ba,bb\\\frac19,\frac29,\frac29,\frac49\end{pmatrix} \]

ถ้าให้ code ทุก block ยาว 2 bit เช่น aa->00, ab->01, ba->10, bb->11 จะเป็น instantaneous และ uniquely decodable

ความสัมพันธ์สำคัญ \[ H(S^n)=nH(S) \] \[ \text{consistent symbol-by-symbol: }L_n=nL \] \[ \text{optimal block code: }L_n\le nL \]

ถ้าต้องการ average ต่อ source symbol ให้เอา average ต่อ block หารด้วย n

ตัวอย่าง S=(5/6,1/6), n=2

S^2 มี AA=25/36, AB=5/36, BA=5/36, BB=1/36

ใช้ Huffman code ได้เช่น AA->0, AB->10, BA->110, BB->111

\[ L_2=\frac{25}{36}(1)+\frac{5}{36}(2)+\frac{5}{36}(3)+\frac{1}{36}(3)=\frac{53}{36} \] \[ \frac{L_2}{2}=\frac{53/36}{2}=\frac{53}{72}=0.736\ \text{bits/symbol} \]

ดีกว่า encode A/B ตรง ๆ ที่ใช้ 1 bit/symbol

ตัวอย่าง S=(5/6,1/6), n=3 จาก Lec4/Lec5

Block	Probability	Code ตัวอย่าง
AAA	125/216	0
AAB	25/216	100
ABA	25/216	101
BAA	25/216	110
ABB	5/216	11100
BAB	5/216	11101
BBA	5/216	11110
BBB	1/216	11111

\[ L_3=\frac{430}{216}=1.991\ \text{bits/block} \] \[ \frac{L_3}{3}=\frac{1.991}{3}=0.664\ \text{bits/symbol} \]

Entropy ของ S คือประมาณ 0.650 bits/symbol ดังนั้น block ยาวขึ้นทำให้เข้าใกล้ entropy

Kraft Inequality และ Source Coding Theorem

Kraft Inequality

Kraft inequality เป็นเงื่อนไขจำเป็นและเพียงพอสำหรับการมี q-ary instantaneous code ที่มีความยาว code word ตามที่กำหนด

\[ q^{-\tau_1}+q^{-\tau_2}+\cdots+q^{-\tau_M}\le 1 \]

สำหรับ binary code q=2 จึงเป็น \(2^{-\tau_1}+2^{-\tau_2}+\cdots+2^{-\tau_M}\le1\)

C4: lengths 1,2,3 \[ 2^{-1}+2^{-2}+2^{-3}=\frac12+\frac14+\frac18=\frac78\le 1 \]

Fixed 2-bit 4 symbols \[ 4(2^{-2})=1 \]

เท่ากับ 1 เรียกว่าใช้ leaf เต็มพอดี หรือ perfect code

ขอบเขตของ Average Code Length

สำหรับ q-ary instantaneous code \[ \frac{H(S)}{\log_2 q}\le L \]

สำหรับ binary code q=2 จะได้ \(H(S)\le L\)

Exercise Lec4: L เท่ากับ entropy เมื่อ probability เป็นกำลังของ 1/2

S=(1/2,1/4,1/8,1/16,1/16) และ code lengths คือ 1,2,3,4,4

\[ \tau_i=-\log_2 p_i \] \[ L=\frac12(1)+\frac14(2)+\frac18(3)+\frac1{16}(4)+\frac1{16}(4)=1.875 \] \[ H(S)=\sum_i p_i(-\log_2 p_i)=1.875 \]

Source Coding Theorem

สำหรับ source S เราสามารถสร้าง binary instantaneous code ให้ average code length ต่อ symbol เข้าใกล้ entropy ได้ตามต้องการโดยใช้ source extension ที่ block ยาวพอ

\[ H(S)\le L < H(S)+\varepsilon \]

แนวคิดพิสูจน์: สำหรับ \(S^n\) มี \(H(S^n)=nH(S)\) และมี code ที่ \(L_n < H(S^n)+1\) ดังนั้นหารด้วย \(n\) จะได้ \(L_n/n < H(S)+1/n\) เลือก \(n\) ใหญ่จน \(1/n\) เล็กกว่า \(\varepsilon\)

Lec5 - Huffman Code

Huffman code คือ prefix code ที่ให้ average code length สั้นที่สุด เมื่อรู้ probability ของแต่ละ source symbol เป็นหนึ่งในวิธีหลักของ source coding

Algorithm สร้าง Huffman

เลือกสอง symbol ที่ probability น้อยที่สุด
รวมเป็น node ใหม่ที่มี probability เป็นผลบวก
จัดเรียงใหม่ แล้วทำซ้ำจนเหลือ node เดียว
ใส่ label 0/1 ให้แต่ละ branch แล้วอ่าน code จาก root ไป leaf

สิ่งที่อย่าตกใจ

Huffman มีได้หลายคำตอบ เพราะสลับ 0/1 หรือเลือกคู่ที่ probability เท่ากันต่างกันได้ แต่ average code length จะเท่ากันถ้ายังทำตาม algorithm ถูกต้อง

ตัวอย่างหลัก: S=(0.35,0.20,0.15,0.15,0.10,0.05)

Huffman tree ตัวอย่าง 1 ตาม review slide

flowchart TD
  R((1.00))
  R -- "0" --> A1["a1
0
p=0.35"]
  R -- "1" --> N65((0.65))
  N65 -- "0" --> N35((0.35))
  N35 -- "0" --> A2["a2
100
p=0.20"]
  N35 -- "1" --> A3["a3
101
p=0.15"]
  N65 -- "1" --> N30((0.30))
  N30 -- "0" --> A4["a4
110
p=0.15"]
  N30 -- "1" --> N15((0.15))
  N15 -- "0" --> A5["a5
1110
p=0.10"]
  N15 -- "1" --> A6["a6
1111
p=0.05"]

Symbol	p	Code ตัวอย่าง 1	Code ตัวอย่าง 2
a1	0.35	0	00
a2	0.20	100	10
a3	0.15	101	010
a4	0.15	110	011
a5	0.10	1110	110
a6	0.05	1111	111

\[ L=0.35(1)+0.20(3)+0.15(3)+0.15(3)+0.10(4)+0.05(4)=2.45\ \text{bits/symbol} \] \[ 0.35(2)+0.20(2)+0.15(3)+0.15(3)+0.10(3)+0.05(3)=2.45 \]

Exercise Lec5: S=(1/3,1/5,1/5,2/15,2/15)

หนึ่งใน Huffman code ที่ถูกต้องคือ a->11, b->00, c->01, d->100, e->101

\[ L=\frac13(2)+\frac15(2)+\frac15(2)+\frac{2}{15}(3)+\frac{2}{15}(3) \] \[ L=\frac{34}{15}=2.267\ \text{bits/symbol} \]

Decoding Huffman

การ decode ทำได้โดยใช้ code tree เดิม อ่าน bit ทีละตัวจาก root พอถึง leaf ให้ปล่อย symbol แล้วกลับ root

ตัวอย่างจาก Lec5/Lec7

ถ้า code tree มี a1->0, a2->10, a3->11 และรับ 0101110010

Huffman decoding tree จากสไลด์

flowchart TD
  R((root))
  R -- "0" --> A1["a1
0"]
  R -- "1" --> N1(( ))
  N1 -- "0" --> A2["a2
10"]
  N1 -- "1" --> A3["a3
11"]

แบ่งได้เป็น 0 / 10 / 11 / 10 / 0 / 10

คำตอบคือ a1, a2, a3, a2, a1, a2

Blocked Huffman

Blocked Huffman คือการทำ Huffman กับ source block เช่น S^2 หรือ S^3 แทนการทำทีละ symbol มักทำให้ average code length ต่อ original symbol ลดลง

Lec6 - Run-Length Code

Run-length code ใช้เมื่อข้อมูลมีสัญลักษณ์ซ้ำต่อเนื่องยาว ๆ เช่น scan pixel ขาวดำที่ขาวเยอะมาก เราไม่ส่ง W ทุกตัว แต่ส่งความยาวของช่วง W ก่อนเจอ B โดยใช้ B เป็น delimiter

ตัวอย่าง sequence

WBWWBWWWWBBWWWBWWWWWWBW...

ใช้ B เป็น delimiter จะได้ run length ของ W: 1, 2, 4, 0, 3, 6, ...

Fixed-Length Run-Length Code

ถ้าใช้ code word ยาว L bit จะแทน run length ได้ตั้งแต่ 0 ถึง 2^L - 1 ถ้า run ยาวเกินต้องแบ่งเป็นหลาย code words

\[ N=2^L-1 \] \[ n_N=\frac{1-(1-p)^N}{p} \] \[ l_N=\frac{L}{n_N} \]

ในสไลด์ p คือ probability ของ delimiter B และ 1-p คือ probability ของ W

ตัวอย่าง S=(B,W)=(1/6,5/6), L=2

L=2 แทน run length 0-3 ดังนั้น N=3

\[ n_3=\frac{1-(5/6)^3}{1/6}=\frac{91}{36}=2.5278 \] \[ l_3=\frac{2}{2.5278}=0.7912\ \text{bits/source symbol} \]

Exercise Lec6: S=(B,W)=(1/8,7/8), fixed length L=3,4,5

L	N=2^L-1	n_N	bits/source symbol
3	7	4.8584	0.6175
4	15	6.9205	0.5780
5	31	7.8726	0.6351

L เพิ่มแล้วไม่ได้แปลว่าจะดีขึ้นเสมอ เพราะ code word ยาวขึ้นด้วย

Run-Length Huffman Code

แทนที่จะให้ run length ทุกค่าใช้ code ยาวเท่ากัน เราใช้ Huffman กับ source block ของ run length ทำให้ค่าที่เกิดบ่อยได้ code สั้น

ตัวอย่าง S=(B,W)=(1/6,5/6), N=3

Run-length Huffman tree N=3 ตาม Lec7 review

flowchart TD
  R((1))
  R -- "0" --> WWW["WWW
code 0
125/216"]
  R -- "1" --> N91((91/216))
  N91 -- "0" --> B["B
code 10
36/216"]
  N91 -- "1" --> N55((55/216))
  N55 -- "0" --> WB["WB
code 110
30/216"]
  N55 -- "1" --> WWB["WWB
code 111
25/216"]

Source block	Probability	Code ตัวอย่าง
B	36/216	10
WB	30/216	110
WWB	25/216	111
WWW	125/216	0

\[ \bar L=\frac{125}{216}(1)+\frac{30}{216}(3)+\frac{25}{216}(3)+\frac{36}{216}(2)=\frac{362}{216}=1.676\ \text{bits/block} \] \[ n_3=\frac{91}{36}=2.5278 \] \[ l_3=\frac{1.676}{2.5278}=0.6630\ \text{bits/source symbol} \]

เปรียบเทียบ: fixed-length L=2 ได้ 0.7912 ดังนั้น Huffman ดีกว่า

Run-Length Huffman N=4 สำหรับ S=(1/6,5/6)

Blocks คือ B, WB, WWB, WWWB, WWWW มี probabilities 1/6, 5/36, 25/216, 125/1296, 625/1296

หนึ่งใน Huffman code: WWWW->0, WWWB->100, WWB->101, WB->110, B->111

\[ \bar L=2.0355\ \text{bits/block} \] \[ n_4=3.1065 \] \[ l_4=0.6552\ \text{bits/source symbol} \]

เข้าใกล้ entropy H(1/6,5/6)=0.6500 มากขึ้น

Lec7 - Review และ Mock Test

Mock 1: Smart Home Entropy

โจทย์

สถานะ Normal, Warning, Alert, Emergency มี probability 0.6, 0.2, 0.15, 0.05 ให้สร้าง source S และหา H(S)

\[ S=\begin{pmatrix}\text{Normal},\text{Warning},\text{Alert},\text{Emergency}\\0.6,0.2,0.15,0.05\end{pmatrix} \] \[ H(S)=-0.6\log_2(0.6)-0.2\log_2(0.2)-0.15\log_2(0.15)-0.05\log_2(0.05) \] \[ H(S)=1.533\ \text{bits/source symbol} \]

Mock 2: Biased Coin Block Length 2 + Huffman

Head -> A มี p=0.7, Tail -> B มี p=0.3

Blocks length 2: AA=0.49, AB=0.21, BA=0.21, BB=0.09

หนึ่งใน Huffman code: AA->0, BA->10, BB->110, AB->111

\[ L_2=0.49(1)+0.21(3)+0.21(2)+0.09(3)=1.81\ \text{bits/block} \] \[ \frac{L_2}{2}=\frac{1.81}{2}=0.905\ \text{bits/source symbol} \]

Mock 3: Average Code Length และ Instantaneous

Symbol	p	C1	C2
A	0.22	1010	00
B	0.18	0111	01
C	0.05	0001	10
D	0.12	1100	110
E	0.30	1001	1110
F	0.13	0100	1111

C1 ทุก code ยาว 4 bit ดังนั้น L(C1)=4 bits/symbol และเป็น instantaneous เพราะ fixed length

\[ L(C_2)=0.22(2)+0.18(2)+0.05(2)+0.12(3)+0.30(4)+0.13(4)=2.98 \]

C2 เป็น instantaneous เพราะไม่มี code word ใดเป็น prefix ของอีก code word

Mock 4: Run-Length Fixed L=2

S=(W,B)=(0.83,0.17), ใช้ B เป็น delimiter และ encode run length ของ W

ดังนั้น p ของ delimiter B คือ 0.17, L=2, N=3

\[ n_3=\frac{1-(1-0.17)^3}{0.17}=\frac{1-0.83^3}{0.17}=2.5189 \] \[ l_3=\frac{2}{2.5189}=0.7940\ \text{bits/source symbol} \]

สรุปลง A4 Handwritten Sheet

สไลด์บอกว่า midterm อนุญาต A4 หน้าเดียวเขียนมือ ดังนั้นควรคัดสิ่งต่อไปนี้ลงกระดาษ

สูตร

I=-log2 P
\(H(S)=-\sum_{i=1}^{M}p_i\log_2p_i\)
\(0 \le H(S) \le \log_2M\)
\(r(S)=1-H(S)/\log_2M\)
\(L=\sum_{i=1}^{M}p_i\tau_i\)
\(q^{-\tau_1}+q^{-\tau_2}+\cdots+q^{-\tau_M}\le1\)
binary source coding theorem: \(H(S) \le L < H(S)+\varepsilon\)
source extension: H(S^n)=nH(S)
run length: \(N=2^L-1\)
\(n_N=[1-(1-p)^N]/p\)
run-length fixed: \(l_N=L/n_N\)

วิธีทำโจทย์

Entropy: เขียน p ทุกตัว เช็คผลรวมเป็น 1 แล้วแทนสูตร
Average length: หาความยาว code word ก่อน แล้วคูณ probability
Instantaneous: ตรวจ prefix หรือวาด tree
Huffman: รวมสอง probability น้อยสุดซ้ำจนเหลือ 1
Blocked Huffman: สร้าง block probability ด้วยการคูณ
Run-length: ระบุ delimiter probability p ให้ถูกก่อนคำนวณ

ค่าตัวอย่างจำได้จะเร็ว

H(1/2,1/3,1/6)=1.459
log2 3=1.585, log2 13=3.700
H(5/6,1/6)=0.650
H(0.6,0.2,0.15,0.05)=1.533
Huffman S=(0.35,0.20,0.15,0.15,0.10,0.05) ได้ L=2.45
run-length S=(1/6,5/6), N=3: \(n_3=2.5278\)

Lecture-Only Appendix

ส่วนนี้เก็บรายละเอียดที่อยู่ในสไลด์เรียน แต่ไม่ใช่แกนหลักของสูตร เพื่อให้ mapping กับไฟล์เรียนครบขึ้น

Course Logistics จาก Lec1 และ Lec7

Lec1 p.2 - Evaluation criteria

Assignment / Report 40% และ Mid-term + Final Exam 60% แบ่งเป็น 30% / 30%

รายงานต้องส่งก่อน due date ถ้าส่งช้าคะแนนสูงสุดของงานนั้นเหลือ 7/10 และห้ามคัดลอกจากเพื่อนหรือ ChatGPT ตามเงื่อนไขในสไลด์

Lec7 p.37 - Midterm instruction

เตรียม pencil/pen, eraser หรือ correction tools, scientific calculator และอนุญาต A4 single-sided handwritten reference sheet หนึ่งแผ่น ห้าม printed materials

Assignments และ Exercises ที่เป็นงานส่ง

Lec1 p.12 - Assignment 1

ใช้ตาราง Yes/No/Neither สร้าง random values 100 ค่าใน Excel แล้ว encode ด้วย C1 และ C2 จากนั้นรวมความยาวและเปรียบเทียบ

Lec3 p.8 - Thai letter frequency

ใช้ข้อมูลความถี่พยัญชนะไทยจากเอกสารที่สไลด์อ้างถึง แล้วคำนวณ redundancy \(r(S)\) ด้วย Excel

Lec4 p.11 - Code report

คำนวณ average code length ของ C1/C2, วาด code tree, ตรวจ uniquely decodable / instantaneous และเลือก code ที่ดีกว่า

Lec5 p.17 - 3rd extension Huffman assignment

สร้าง Huffman code ของ \(S^3\) สำหรับ \(S=(A,B)=(5/6,1/6)\) และคำนวณ average code length

Exercise Values ที่ควรจำเพิ่ม

ที่มา	โจทย์/หัวข้อ	ผลลัพธ์สำคัญ
Lec2 p.9	information content เมื่อ \(P=1/2\) และ \(P=1/8\)	\(I=1\) bit และ \(I=3\) bits
Lec2 p.10 / Lec7 p.4	ไพ่ 52 ใบ: suit is heart และ card is an A (Ace)	heart = 2 bits, Ace = \(\log_2 13\) bits
Lec3 p.13-14	C3/C4 สำหรับ sequence \(a_1a_3a_1a_1a_2a_3a_1a_2\)	C3 = 0010000001100001, C4 = 10011101001101
Lec4 p.4	C4: \(a_1\to1,\ a_2\to01,\ a_3\to001\)	เป็น instantaneous จึง uniquely decodable
Lec4 p.22-23	binary instantaneous upper bound	\(H(S)\le L < H(S)+1\), และเมื่อใช้ extension \(H(S)\le L < H(S)+\varepsilon\)
Lec6 p.13-14	fixed run-length \(S=(B,W)=(1/8,7/8)\)	L=3: 0.6175, L=4: 0.5780, L=5: 0.6351 bits/source symbol

Derivation Notes จากสไลด์

Lec2 p.16 - convention ของ \(0\log 0\) \[ \lim_{x\to 0^+}x\log_2 x=0 \]

ดังนั้นเวลา entropy มี term \(0\log 0\) ให้ถือว่า contribution เป็น 0

Lec6 p.10-11 - sum ที่ใช้หา average source-block length \[ \sum_{r=1}^{N} r x^r=\frac{x(1-x^N)}{(1-x)^2}-\frac{Nx^{N+1}}{1-x} \] \[ n_N=\sum_{i=1}^{N} i\,p(1-p)^{i-1}+N(1-p)^N=\frac{1-(1-p)^N}{p} \]

ตรวจความครบตามไฟล์สไลด์

ผมสกัดข้อความจาก PDF ทั้ง 7 ไฟล์และเช็คจำนวนหน้าแล้ว เอกสารนี้ครอบคลุมหัวข้อหลักและโจทย์รีวิวของทุก lecture ดังนี้

Lec1 - 20 หน้า
Introduction, Shannon model, source/channel coding, repetition example, sampling theorem, quantization

Lec2 - 16 หน้า
Source model, memoryless/discrete/stationary, information content, entropy, binary entropy

Lec3 - 14 หน้า
Entropy bound, redundancy, letter frequency, code alphabet, code length, efficient coding

Lec4 - 25 หน้า
Uniquely decodable, instantaneous code, code tree, source extension, Kraft inequality, source coding theorem

Lec5 - 18 หน้า
Huffman code construction, examples, decoding, blocked Huffman, extension source assignment

Lec6 - 17 หน้า
Run-length code, fixed-length run-length, run-length Huffman, average source block length

Lec7 - 41 หน้า
Review answers, Huffman examples, run-length answers, midterm instructions, mock test

สถานะ

ครบตามหัวข้อที่ปรากฏในสไลด์ทั้งหมด และเติมคำอธิบาย/สูตร/ตัวเลขเฉลยที่จำเป็นสำหรับทำข้อสอบ