ผลต่างระหว่างรุ่นของ "Sgt/lecture9"

รุ่นแก้ไขเมื่อ 12:06, 16 เมษายน 2558

Spectral Graph Theory
บทนำและทบทวนพีชคณิตเชิงเส้น (ณัฐวุฒิ) เนื้อหา: Eigenvector, Eigenvalue คุณสมบัติของ Eigenvalue ต่อกราฟ (ธานี,ณัฐวุฒิ) เนื้อหา: ผลหาร Rayleigh, คุณสมบัติของเมตริกซ์ Laplacian ทดลอง: วาดกราฟจาก Eigenvector คุณสมบัติของ Eigenvalue ต่อกราฟ[2] (ภัทร) เนื้อหา: Eigen value properties คุณสมบัติของ Eigenvalue ลำดับที่สองบนกราฟต่างๆ (ธานี) เนื้อหา: Second eigen value Cheeger Inequality (ศุภชวาล) เนื้อหา: Cheeger Inequality การทดลอง Cheeger Inequality และ Effective Resistance (ธานี) เนื้อหา: Effective Resistance ทดลอง: หา cut ที่มีคุณสมบัติตรงกับ Cheeger Inequality Random Walks และ Psuedo Random Generator (ศุภชวาล) เนื้อหา: Random Walks Psuedo Random Generator[2] (ภัทร) เนื้อหา: Psuedo Random Generator Coding Theory และ Expander code (ธานี) เนื้อหา: Coding Theory Expander graph from Linear coding (ภัทร) เนื้อหา: Expander construction Chebyshev polynomial (ศุภชวาล) เนื้อหา: Chebyshev polynomial Preconditioning (ธานี) เนื้อหา: Preconditioning
แก้ไขกล่องนี้ • แก้ไขสารบัญ

บันทึกคำบรรยายวิชา 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$

@@ แถว 5: / แถว 5: @@
 เราต้องการส่งข้อมูลขนาด m บิท แต่ระหว่างการส่งอาจจะเกิดความผิดพลาดทำให้บางบิทไม่ถูกต้อง
-จึงมีการคิดการส่งเพื่อให้สามารถตรวจจับ / แก้ไขความผิดพลาดได้
+จึงมีการคิดการส่งเพื่อให้สามารถตรวจจับ / แก้ไขความผิดพลาดได้ โดยส่งข้อมูลที่ encode แล้วและมีขนาด n บิท นั่นคือ
-โดยส่งข้อมูลที่ encode แล้วและมีขนาด n บิท นั่นคือ <math>Encode(\{0,1\}^m) \rightarrow \{0,1\}^n</math>
+<math>Encode(\{0,1\}^m) \rightarrow \{0,1\}^n</math>
+[http://en.wikipedia.org/wiki/Hamming_code Hamming Code] คือการ encode ข้อมูลขนาด 4 บิทไปเป็นข้อมูล 7 บิท โดยสามารถรับประกันได้ว่า ถ้าข้อมูลผิดพลาดไปไม่เกิน 1 บิท จะสามารถตรวจจับและแก้ไขได้ โดยให้ข้อมูลอยู่ที่บิทที่ 3,5,6,7 และ ให้
+.บิทที่ 4 เป็น XOR ของบิทที่ 5,6,7
+.บิทที่ 2 เป็น XOR ของบิทที่ 3,6,7
+.บิทที่ 1 เป็น XOR ของบิทที่ 3,5,7
+ให้ <math>b_i</math> แทนบิทที่ i เราสามารถตรวจจับ/แก้ไขความผิดพลาดไม่เกินหนึ่งบิทได้ดังนี้
+a = <math>b_4</math> XOR <math>b_5</math> XOR <math>b_6</math> XOR <math>b_7</math>,
+b = <math>b_2</math> XOR <math>b_3</math> XOR <math>b_6</math> XOR <math>b_7</math>,
+c = <math>b_1</math> XOR <math>b_3</math> XOR <math>b_5</math> XOR <math>b_7</math>
+ถ้า a,b,c ไม่เท่ากับศูนย์ บิทที่ผิดพลาดคือบิทที่ <math>a*4 + b*2 + c</math>
 == Random Linear Code ==

ผลต่างระหว่างรุ่นของ "Sgt/lecture9"

รุ่นแก้ไขเมื่อ 12:06, 16 เมษายน 2558

เนื้อหา

Coding Theory

Random Linear Code

Reed-Solomon Code

Expander Code

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ