Sgt/lecture9

บันทึกคำบรรยายวิชา Spectral graph theory นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

Coding Theory

เราต้องการส่งข้อมูลขนาด m บิท แต่ระหว่างการส่งอาจจะเกิดความผิดพลาดทำให้บางบิทไม่ถูกต้อง จึงมีการคิดการส่งเพื่อให้สามารถตรวจจับ / แก้ไขความผิดพลาดได้ โดยส่งข้อมูลที่ encode แล้วและมีขนาด n บิท นั่นคือ

$Encode(\{0,1\}^{m})\rightarrow \{0,1\}^{n}$

Hamming Code คือการ encode ข้อมูลขนาด 4 บิทไปเป็นข้อมูล 7 บิท โดยสามารถรับประกันได้ว่า ถ้าข้อมูลผิดพลาดไปไม่เกิน 1 บิท จะสามารถตรวจจับและแก้ไขได้ โดยให้ข้อมูลอยู่ที่บิทที่ 3,5,6,7 และ ให้

1.บิทที่ 4 เป็น XOR ของบิทที่ 5,6,7

2.บิทที่ 2 เป็น XOR ของบิทที่ 3,6,7

3.บิทที่ 1 เป็น XOR ของบิทที่ 3,5,7

ให้ $b_{i}$ แทนบิทที่ i เราสามารถตรวจจับ/แก้ไขความผิดพลาดไม่เกินหนึ่งบิทได้ดังนี้

a = $b_{4}$ XOR $b_{5}$ XOR $b_{6}$ XOR $b_{7}$, b = $b_{2}$ XOR $b_{3}$ XOR $b_{6}$ XOR $b_{7}$, c = $b_{1}$ XOR $b_{3}$ XOR $b_{5}$ XOR $b_{7}$

ถ้า a,b,c ไม่เท่ากับศูนย์ บิทที่ผิดพลาดคือบิทที่ $a*4+b*2+c$

ซึ่งการสร้าง codeword แบบใดๆนั้นจะมีค่าสองค่าที่ใช้บอกความ"ดี" ของการสร้างนั้นๆ ได้แก่ ค่าอัตราส่วนระหว่างความยาว message ต่อความยาว codeword (เรียกว่า rate)

$r={\frac {m}{n}}$

และค่า Hamming Distance คือจำนวนบิทที่แตกต่างกันที่น้อยที่สุดของคู่ codeword ใดๆ ซึ่งเป็น upperbound ของ จำนวนบิทที่สามารถ correction ได้

เช่น การสร้าง codeword หนึ่งๆ มี Hamming distance เป็น d การสร้างแบบนั้นจะไม่สามารถ correct message ที่ผิดพลาดเกิน d/2 บิทได้ และนิยาม minimum relative distance คือค่า d/n (Hamming distance ต่อความยาว codeword)

เราจะเรียกกระบวนการสร้าง codeword หนึ่งๆว่า asymtotically good ถ้า ไม่ว่า message จะมีความยาวเพิ่มขึ้นอย่างไร ค่า rate และ minimum relative distance จะมากกว่าค่าคงที่ค่าหนึ่งเสมอ

Random Linear Code

ในส่วนนี้ เราจะแสดงให้เห็นว่าถ้าหากเราเขียน message ให้อยู่ในรูปเวคเตอร์ v และสุ่มเมทริกซ์ M ขึ้นมาเพื่อเป็นเมทริกซ์ที่ใช้สร้าง codeword แล้ว

ด้วยความน่าจะเป็นที่สูง เมทริกซ์นั้นจะมีคุณสมบัติ asymtotically good

ทดสอบ

---

---

Reed-Solomon Code

อีกหนึ่งตัวอย่างของการทำ Error Correcting คือ Reed-Solomon Code

สำหรับจำนวนเฉพาะ p หนึ่งๆ และ message ขนาด m $f_{1},f_{2},...,f_{m}\in \mathbb {F} _{p}$ และนิยามฟังก์ชันพหุนาม $Q_{f}(x)=\sum \limits _{i=1}^{m}f_{i}x^{i-1}$

และ code word ขนาด n คือ $Q_{f}(0),Q_{f}(1),Q_{f}(2),...Q_{f}(n-1)$

Reed-Solomon code จะ correct error ได้ p หน่วย

สังเกตุว่าหน่วยย่อยของ Reed-Solomon ไม่ใช่บิท เนื่องจาก correct ที่ระดับ element $f_{i}$

หากจะใช้หน่วยเป็นบิท จะต้องแทน element $f_{i}$ ด้วย $log_{2}p$ บิท และจะ correct ได้เพียง p บิท