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

สุ่มเมทริกซ์ขนาด n แถว m หลัก จะได้ว่าสำหรับค่า d ใดๆ ความน่าจะเป็นที่เมทริกซ์นั้นจะสร้าง codeword ขนาด n สำหรับ message ขนาด m ที่มี minimum distance อย่างน้อย d มีไม่น้อยกว่า $1-{\frac {2^{m}}{2^{n}}}\sum \limits _{i=0}^{d}{\binom {n}{i}}$

---

การพิจารณาค่า distance ต่ำสุด เราสามารถ simplify ได้โดยการพิจารณาว่า สำหรับ message ในรูปเวคเตอร์ b ไม่เท่ากับศูนย์ใดๆ จำนวนบิทที่เป็นค่า 1 มีน้อยที่สุดกี่บิท

พิจารณาแต่ละค่าใน Mb เราพบว่าค่านั้นๆ จะเป็น 0 ด้วยความน่าจะเป็น 1/2 เนื่องจาก M สุ่มแบบ uniform ดังนั้น ความน่าจะเป็นที่ Mb สำหรับ fixed b จะมีบิทที่เป็น 1 ไม่เกิน d บิทนั้น มีค่าเท่ากับ

${\frac {1}{2^{n}}}\sum \limits _{i=0}^{d}{\binom {n}{i}}$ และสำหรับทุก b เราใช้ union bound จึงได้ว่าความน่าจะเป็นที่ สุ่ม M ใดๆแล้ว ทำให้ทุก Mb สำหรับทุก message b มีบิท 1 น้อยกว่า d บิท มีค่าไม่ต่ำกว่า

${\frac {2^{m}}{2^{n}}}\sum \limits _{i=0}^{d}{\binom {n}{i}}$ จึงได้ตามที่ต้องการ

---

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 บิท

Expander Code

ให้ $K_{n,n}$ แทน complete bipartite graph เราต้องการสร้าง d-regular graph G ที่ approximate $K_{n,n}$ นั่นคือ

$(1-\epsilon ){\frac {d}{n}}K_{n,n}\preceq G\preceq (1+\epsilon ){\frac {d}{n}}K_{n,n}$

นั่นคือ eigenvalue $\lambda _{1}\leq \lambda _{2}\leq \cdots \leq \lambda _{2n}$ ของ Laplacian ของกราฟ G มีคุณสมบัติดังนี้ $\lambda _{1}=0\ ,\ \lambda _{2n}=2d\ ,\ |\lambda _{i}-d|\leq \epsilon d\ ;\ 1<i<2n$

เราสามารถสร้างกราฟที่มีคุณสมบัติตามต้องการได้โดยการสร้าง double-cover ของ expander graph โดยนิยามดังนี้

กราฟ H เป็น double-cover ของกราฟ G เมื่อ H เป็นกราฟที่มีจำนวนโหนดและเส้นเชื่อมเป็นสองเท่าของ G โดยสำหรับทุกโหนด u ของ G กราฟ H จะมีโหนด $u_{0},u_{1}$

และสำหรับเส้นเชื่อม $(u,v)$ ใน G จะมีเส้นเชื่อมใน H สองเส้น $(u_{0},v_{1}),(u_{1},v_{0})$ และการบ้านในสัปดาห์นี้คือ การพิสูจน์ข้อความด้านล่าง

ให้ H เป็น double-cover ของ G จะได้ว่าสำหรับทุก eigenvalue $\lambda _{i}$ ของ Laplacian ของ G จะได้ว่า Laplacian ของ H จะมี eigenvalue ที่มีค่าเท่ากับ $\lambda _{i}$ และ $|2d-\lambda _{i}|$

ในสัปดาห์นี้ เราพูดถึงทฤษฎีบทเพิ่มอีกสองทฤษฎีบท

ให้ $G=(U\cup V,E)$ เป็น d-regular bipartite graph ที่ approximate ${\frac {d}{n}}K_{n,n}$

จะได้ว่าสำหรับเซต $S\subset U$ และ $T\subset V$ ใดใด

${\Bigl |}\ |E(S,T)|-{\frac {d}{n}}|S||T|{\Bigr |}\ \leq \ \epsilon d{\sqrt {|S||T|}}$

และจากทฤษฎีบทด้านบนเราได้ทฤษฎีบทนี้

ให้ $|S|=\sigma n$ และ $|T|=\tau n$ ดีกรีเฉลี่ยของ $G(S\cup T)$ มีค่าไม่เกิน ${\frac {2d\sigma \tau }{\sigma +\tau }}+\epsilon d$