hamming Code

posted on 06 May 2010 15:51 by pixzar in Network

hamming Code

โดย ศล



ผมนึกตัวเลขตัวหนึ่งไว้ในใจ เป็นตัวเลขที่มีค่าตั้งแต่ 1 ถึง 16 แล้วให้คุณตั้งคำถามใช่หรือไม่ (Yes-No question) คุณใช้คำถามน้อยที่สุดกี่คำถาม คุณอาจตอบได้ทันทีว่า 4 ถ้าคุณเคยรู้หลักการมาก่อน 24 = 16 อาจใช้วิธีแบ่งครึ่ง เช่น “มากกว่า 8 ใช่มั้ย?” ถ้าไม่ใช่ ถามต่อว่า “มากกว่า 4 ใช่มั้ย?” ถ้าใช่ ถามต่อว่า “มากกว่า 6 ใช่มั้ย?” แล้วคุณจะรู้คำตอบเมื่อจบคำถามที่ 4 ยังมีวิธีอื่นอีก คุณอาจขอให้ผมแปลงเลขที่ผมนึกไว้เป็นเลขฐานสอง[1] 4 หลัก เช่นถ้าผมนึกเลข 7 ผมก็แปลงเป็น 0111 จากนั้นคุณถามหลักที่อยู่ขวาสุดคือ 0 ใช่มั้ย? ถัดมาทางซ้ายคือ 1 ใช่มั้ย? เมื่อถามครบทั้ง 4 หลักคุณก็แปลงกลับเป็นเลขฐานสิบ Bravo!

มีโจทย์ที่คล้ายกันจากนิตยสาร KöMaL ของฮังกาเรียน เติมความยากลงไปอีกนิด คืออนุญาตให้ผมมีสิทธิโกหกได้ 1 ครั้ง ซึ่งผมอาจจะโกหกหรือไม่โกหกก็ได้ ดังนั้นคำถามน้อยที่สุดที่คุณใช้คือกี่คำถาม โจทย์ข้อนี้ง่ายมากสำหรับใครก็ตามที่เคยเรียนวิชา Information Theory หรือ Code Theory แต่ KöMaL เป็นนิตยสารเสริมการเรียนรู้คณิตศาสตร์ในระดับมัธยม ดังนั้นน้อง ๆ มัธยมที่ต้องการแก้โจทย์ปัญหาข้อนี้ถ้าไม่มีความรู้เรื่องการเข้ารหัสข้อมูลก็ต้องออกแรงใช้ความคิดใหม่กันพอสมควร บทความปริศนาเกมทายใจเราจะมาดูวิธีการเข้ารหัสตรวจจับและแก้ไขข้อผิดพลาด (Error-Correcting Code) เพื่อหาผลเฉลยของโจทย์ข้อนี้กัน



สมมติว่านกเพนกวินอ้วนต้องการส่งข้อมูลเลขฐานสอง 1010 ให้กับนกเพนกวินผอม ถ้าช่องทางสื่อสารมีข้อผิดพลาดทำให้เลข 1 ตัวหนึ่งเปลี่ยนเป็นเลข 0 ตามรูปที่ 1 เลข 0 สีแดงคือข้อมูลที่ผิดพลาด ถ้านกเพนกวินผอมไม่ตรวจสอบข้อมูลก่อนนำไปใช้ ก็จะได้ข้อมูลที่ผิดไป คำถามจึงเกิดขึ้นกับนกเพนกวินผอมว่าจะต้องตรวจสอบข้อมูลเมื่อไร ตรวจสอบข้อมูลกี่ครั้ง ถ้าต้องถามข้อมูลนกอ้วนใหม่ 10 ครั้ง แล้วได้รับคำตอบไม่ตรงกันทั้ง 10 ครั้ง นกผอมจะทำอย่างไร แต่ถ้าช่องทางสื่อสารค่อนข้างน่าเชื่อถือ นกผอมก็คิดว่าตัวเองไม่จำเป็นต้องถามใหม่ทุกครั้ง หรือหลายครั้ง จะมีเครื่องมือใดที่ช่วยยืนยันความมั่นใจได้อีกบ้างนอกจากความไว้วางใจในความน่าเชื่อถือของช่องทางสื่อสาร



วิธีเรียบง่ายวิธีหนึ่งในการแก้ปัญหาสื่อสารแบบนี้คือการเพิ่มบิตตรวจสอบ รูปที่ 2 เลข 0 สีน้ำเงินคือบิตตรวจสอบที่นกเพนกวินอ้วนสร้างขึ้นมา โดยมีข้อตกลงร่วมกับนกเพนกวินผอมว่าข้อมูลที่แท้จริงคือข้อมูล ซ้ายมือ 4 บิตแรกเท่านั้น และข้อมูลทั้ง 5 บิตมีเลข 1 อยู่จำนวนคู่ตัว (พาริตี้คู่)[2] เมื่อข้อมูลดังกล่าวเดินทางมาถึงเพนกวินผอม ปรากฏว่ามีความผิดพลาดเกิดขึ้นตำแหน่งเดิม (เลข 0 สีแดง) แต่คราวนี้นกเพนกวินผอมสามารถรู้ได้ว่ามีข้อมูลผิดพลาด 1 บิต เพราะจำนวนเลข 1 ไม่เป็นจำนวนคู่ จึงถามกลับด้วย ?#$?! เพื่อขอให้นกอ้วนส่งข้อมูลมาใหม่อีกครั้ง เมื่อนกเพนกวินอ้วนตอบกลับมาและเพนกวินผอมนับ 1 ได้จำนวนคู่ตัวตามที่ตกลงกันไว้ จึงค่อนข้างมั่นใจได้ว่าไม่มีข้อมูลผิดพลาด

แล้วจะเกิดอะไรขึ้นถ้าเหตุการณ์เป็นดังรูปที่ 3 ซึ่งเป็นกรณีที่มีข้อมูลผิดพลาด 2 ตัว



พวกเราคงเห็นด้วยว่าการเพิ่มบิตตรวจสอบเพียงบิตเดียวไม่สามารถตรวจสอบความผิดพลาดกรณีนี้ได้ นกเพนกวินทั้งสองก็ต้องหาวิธีการใหม่ และควรรื้อช่องทางการสื่อสารนั้นทิ้งไปด้วย เพราะกรณีนี้ดูเหมือนมันไม่น่าเชื่อถือเอาเสียเลย แต่อย่างไรก็ตาม จากวิธีการเพิ่มบิตตรวจสอบ 1 บิต เราจะรู้เพียงว่าข้อมูลเกิดข้อผิดพลาด แต่ไม่รู้ว่าข้อผิดพลาดนั้นเกิดขึ้น ณ ตำแหน่งใด

บุคคลแรกที่มีความคิดใช้ลำดับของบิตตรวจสอบความผิดพลาดระบุตำแหน่งบิตที่ผิดพลาดคือ Richard Hamming เพื่อนร่วมงานของ Claude Shannon ผู้ได้รับขนานนามว่าบิดาแห่งทฤษฎีสารสนเทศ (Information Theory) ที่ห้องปฏิบัติการ Bell พูดได้ว่าตั้งแต่ตอนที่ชานอนเริ่มพัฒนาทฤษฎีสารสนเทศเป็นแบบจำลองทางคณิตศาสตร์สำหรับการสื่อสาร ฮัมมิ่งก็ได้ตระหนักถึงความสำคัญของการหาและแก้ไขข้อผิดพลาดของข้อมูลในการสื่อสาร แนวคิดนี้ปัจจุบันก็ยังคงความสำคัญและรู้จักกันดีในนามการเข้ารหัสฮัมมิ่ง หรือ Hamming Code

ถ้าเรามีข้อมูลจริง r บิต และใส่เพิ่มเข้าไปอีก m บิต รวมเป็น n = m+r บิต เขียนแทนด้วย (n,r) และถ้า m บิตนั้นสามารถบอกตำแหน่งที่ผิดพลาดได้ ดังนั้น 2m ≥ n+1 ในกรณีที่ r = 4 เราพบว่า m = 3 สอดคล้องกับเงื่อนไขของอสมการ (27-4 ≥ 7+1) หมายความว่าเราสามารถสร้างข้อมูล (7,4) ที่สามารถแก้ไขข้อผิดพลาด 1 บิตได้ โดยมีวิธีการดังนี้ จากตาราง D7 D6 D5 D3 คือข้อมูลจริง ส่วน P4 P2 P1 คือข้อมูลที่ใส่เพิ่มเข้าไปเป็นบิตพาริตี้คู่



P1 สร้างจาก D7 D5 และ D3, P2 สร้างจาก D7 D6 และ D3, P4 สร้างจาก D7 D6 และ D5 สาเหตุที่ต้องแยกสร้างพาริตี้คู่ 3 ชุดอาจพิจารณาจากแผนภาพรูปที่ 4 ถ้ามีข้อมูลตัวใดตัวหนึ่งเปลี่ยนแปลงจะทำให้บิตพาริตี้อย่างน้อย 1 ตัวเปลี่ยนแปลง เช่น ถ้า D3 เปลี่ยนจะทำให้ P1 และ P2 เปลี่ยน ถ้า D7 เปลี่ยน จะทำให้ P4 P2 และ P1 เปลี่ยน ถ้าบิตพาริตี้เปลี่ยนตัวเดียว หมายความว่ามีเฉพาะตัวมันเองเท่านั้นที่เปลี่ยน

ตัวอย่างจากรูปที่ 1 นกเพนกวินอ้วนต้องการส่ง 1010 ให้นกเพนกวินผอม สามารถสร้างรหัสฮัมมิ่งดังตาราง



ถ้าข้อมูลที่นกเพนกวินอ้วนส่งไปมีความผิดพลาดเกิดขึ้น 1 บิต นกเพนกวินผอมสามารถหาข้อผิดพลาดนั้นและแก้ไขได้เสมอ โดยการตรวจสอบบิตพาริตี้ทั้ง 3 บิต ดังรูปที่ 5



เมื่อเพนกวินผอมได้รับ 1000010 มันจะนำข้อมูล D7 D6 D5 D3 มาตรวจสอบบิตพาริตี้ใหม่อีกครั้ง แล้วเปรียบเทียบกับ P4 P2 P1 บิตพาริตี้ที่เพนกวินอ้วนส่งมาให้ โดยอาจเปรียบเทียบว่า ถ้าตรงกันมีค่าเป็น 0 ถ้าต่างกันมีค่าเป็น 1 (ในทาง logic คือตัวดำเนินการ XOR) จากตัวอย่างรูปที่ 5 นกเพนกวินผอมพบว่า P4 กับ P1 ไม่ตรงกัน เมื่อดูตามรูปที่ 4 มันจึงสรุปได้ทันทีว่า D5 คือบิตที่ผิดพลาด หรือเพนกวินอ้วนอาจนำผลจากการ XOR บิตพาริตี้ของตัวเองกับของเพนกวินอ้วนมาเรียง

(P4, อ้วน XOR P4, ผอม), (P2, อ้วน XOR P2, ผอม), (P1, อ้วน XOR P1, ผอม) = 101

ซึ่งเท่ากับ 5 มันก็จะรู้ว่าบิตลำดับที่ 5 จากทางขวามือคือบิตที่ผิดพลาด และนี่คือเหตุผลว่าเหตุใดตารางสร้าง Hamming Code จึงต้องสลับ D3 กับ P4 ก็เพื่อเอาคำตอบจากการเปรียบเทียบเมื่อแปลงเป็นเลขฐานสองแล้วสามารถชี้ตำแหน่งที่ผิดพลาดได้เลย



น่าทึ่งใช่ไหมครับ เราลองมาดูกลไกที่ซ่อนอยู่เบื้องหลังของหลักการนี้กัน ทำไมการเข้ารหัสฮัมมิ่งจึงแก้ไขข้อผิดพลาด 1 บิตได้ สมมติว่าเรามีข้อมูล 1 บิต (0 หรือ 1) ถ้าเราทำซ้ำข้อมูลนั้นให้กลายเป็น 3 บิต คือ 000 กับ 111 แล้วส่งไปบนช่องทางที่อาจเกิดข้อผิดพลาดได้ 1 บิต ผู้รับจะรู้เสมอว่าข้อมูลที่เราต้องการส่งคืออะไร เหตุผลง่ายๆ คือ ถ้ามันจะเปลี่ยน มันเปลี่ยนแค่ 1 ตัว อีก 2 ตัวไม่เปลี่ยน เช่นถ้าเราได้รับ 011 เราก็รู้ทันทีว่าผู้รับต้องการส่ง 1 บางคนอาจเกิดคำถามว่าทำซ้ำแค่ 2 บิตไม่ได้หรือ? คำตอบคือไม่ได้ครับ เพราะเราไม่รู้ว่า 10 นั้นกลายพันธุ์มากจาก 00 หรือ 11 ดังนั้นสามารถสรุปได้ว่า ถ้ายอมให้มีความผิดพลาดเกิดขึ้นได้ 1 บิต ข้อมูลที่เป็นไปได้ต้องห่างกันอย่างน้อย 3 ช่วงของการกลายพันธุ์ เช่นการเปลี่ยนจาก 000 เป็น 111 ต้องผ่านขั้นตอนการเปลี่ยนทีละบิต (กลายพันธุ์) ตามรูปที่ 6 เราอาจลองพิสูจน์ข้อมูล (7,4) โดยการสร้างความเป็นไปได้ทั้งหมดของข้อมูลขึ้นมา แล้วตรวจสอบว่าแต่ละข้อมูลนั้นห่างกัน 3 ช่วงของการกลายพันธุ์จริงหรือไม่



จากตาราง ถ้าเราได้รับข้อมูล 1110110 เราสามารถตอบได้ทันทีว่าข้อมูลที่ถูกต้องคือ 1100110 เพราะข้อมูล 2 ตัวนี้ห่างกัน 1 ช่วงของการกลายพันธุ์

ย้อนกลับไปที่โจทย์ตั้งต้นของเรา แปลงเลขที่นึกในใจเป็นเลขฐานสอง 4 บิต กำหนดให้เรียงกันเป็น ABCD (เช่นผมนึกเลข 4 = (0100)2, A=0, B=1, C=0, D=0) สามารถโกหกได้ 1 ครั้ง หมายถึงสามารถทำให้ข้อมูลผิดพลาดได้ 1 บิต เราสามารถใส่ข้อมูลเพิ่มเข้าไป 3 บิต เพื่อหาข้อผิดพลาดนั้นได้ ดั้งนั้นคุณตั้งคำถามเพียง 7 คำถาม

1. A = 0 ใช่หรือไม่? (A เป็นจำนวนคู่ใช่หรือไม่?)
2. B = 0 ใช่หรือไม่?
3. C = 0 ใช่หรือไม่?
4. D = 0 ใช่หรือไม่?
5. A+C+D เป็นจำนวนคู่ใช่หรือไม่?
6. A+B+D เป็นจำนวนคู่ใช่หรือไม่?
7. A+B+C เป็นจำนวนคู่ใช่หรือไม่?

ใช้ข้อมูลข้อ 5-7 ตรวจสอบเหมือนตอนตรวจสอบ P4 P2 P1 ถ้าข้อ 1-4 พูดจริง คำตอบข้อ 5-7 จะมีข้อผิดพลาดหรือข้อขัดแย้งไม่เกิน 1 ข้อ แต่ถ้าคำตอบข้อ 5-7 มีข้อผิดพลาดหรือเกิดข้อขัดแย้งมากกว่า 1 ข้อ แสดงว่าในคำตอบข้อ 1-4 มีการพูดโกหก 1 ครั้ง

ก. 5-7 ผิดพลาดหรือขัดแย้งทั้ง 3 ข้อ แสดงว่าโกหกข้อ 1
ข. 5 กับ 6 ผิดพลาดหรือขัดแย้ง แสดงว่าโกหกข้อ 4
ค. 5 กับ 7 ผิดพลาดหรือขัดแย้ง แสดงว่าโกหกข้อ 3
ง. 6 กับ 7 ผิดพลาดหรือขัดแย้ง แสดงว่าโกหกข้อ 2


[1] เลขฐานสองคือเลขที่เขียนโดยใช้เลขโดด 0 กับ 1 ตัวอย่างการแปลงเลข 214 ฐานสิบ เป็นฐานสอง; 214 = (2x102) + (1x101) + (4x100) สังเกตว่าฐานของเลขยกกำลังคือ 10 เราจึงเรียกว่าเลขฐาน 10 เมื่อเปลี่ยนฐานเป็นสอง ค่าของ 214 = (1x27) + (1x26) + (0x25) + (1x24) + (0x23) + (1x22) + (1x21) + (0x20) = (11010110)2 คำว่าบิตเป็นหน่วยของเลขฐานสอง 1 ตำแหน่ง จากตัวอย่าง ตัวเลข 214 สามารถแปลงเป็นเลขฐานสอง 8 บิต (หรือ 8 ตำแหน่ง หรือ 8 หลัก)

[2] การตรวจสอบแบบนี้เรียกว่าการเพิ่มบิตพาริตี้คู่ (even parity bit) คือการเติมบิตสุดท้ายลงไปเพื่อให้จำนวนบิตที่มีค่าเป็น 1 เป็นจำนวนคู่ ในทำนองเดียวกันเราอาจทำเป็นบิตพาริตี้คี่ (odd parity bit) ก็ได้ เช่น 11010110 ถ้าเพิ่มบิตพาริตี้คู่ จะกลายเป็น 110101101 แต่ถ้าเพิ่มบิตพาริตี้คี่ จะเป็น 110101100


บทความนี้ได้รับการพิจารณาตีพิมพ์ใน
MY MATHS issue 39


Comment

Comment:

Tweet

#2 By (202.28.78.146) on 2010-09-28 15:07

sad smile

คณิตศาสตร์

#1 By Chinly-XD on 2010-05-06 15:56