แฮมมิง Code: การตรวจจับและแก้ไขข้อผิดพลาด พร้อมตัวอย่าง

ข้อผิดพลาดคืออะไร?

Transmitข้อมูลอาจเสียหายระหว่างการสื่อสาร อาจได้รับผลกระทบจากสัญญาณรบกวนภายนอกหรือความล้มเหลวทางกายภาพอื่นๆ ในสถานการณ์เช่นนี้ ข้อมูลขาเข้าจะไม่ตรงกับข้อมูลขาออก ความไม่ตรงกันนี้เรียกว่า “ข้อผิดพลาด”

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

ประเภทของข้อผิดพลาด

โดยหลักแล้ว ข้อผิดพลาดของบิตที่เกิดขึ้นเมื่อประมวลผลข้อมูลมีอยู่ 3 ประเภท transmitส่งข้อมูลจากผู้ส่งไปยังผู้รับ แผนภาพด้านล่างแสดงให้เห็นว่าแต่ละประเภทส่งผลต่อลำดับข้อมูลอย่างไร:

• ข้อผิดพลาดบิตเดียว
• ข้อผิดพลาดหลายบิต
• ข้อผิดพลาดระเบิด

ข้อผิดพลาดบิตเดียว

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

ข้อผิดพลาดหลายบิต

เมื่อบิตตั้งแต่สองบิตขึ้นไปของลำดับข้อมูลเปลี่ยนแปลงระหว่างกัน transmitเมื่อส่งไปยังตัวรับและตัวส่งสัญญาณ จะเรียกว่า "ข้อผิดพลาดหลายบิต"

ข้อผิดพลาดประเภทนี้เกิดขึ้นได้ทั้งในเครือข่ายการสื่อสารข้อมูลแบบอนุกรมและแบบขนาน

ข้อผิดพลาดในการระเบิด

การเปลี่ยนแปลงของชุดบิตที่อยู่ติดกันในลำดับข้อมูลเรียกว่า "ข้อผิดพลาดแบบกลุ่ม" (burst error) ความยาวของข้อผิดพลาดแบบกลุ่มจะวัดจากบิตแรกที่เปลี่ยนแปลงไปจนถึงบิตสุดท้ายที่เปลี่ยนแปลง

การตรวจจับข้อผิดพลาดและการแก้ไขข้อผิดพลาดคืออะไร?

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

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

รหัสความซ้ำซ้อนถูกใช้เพื่อค้นหาข้อผิดพลาดเหล่านี้โดยการเพิ่มบิตพิเศษเข้าไปในข้อมูลเมื่อมีการป้อนรหัส transmitได้มาจากแหล่งที่มา บิตเพิ่มเติมเหล่านี้เรียกว่า "รหัสตรวจจับข้อผิดพลาด" รหัสตรวจจับข้อผิดพลาดที่พบได้บ่อยที่สุดสามประเภท ได้แก่:

• การตรวจสอบความเท่าเทียมกัน
• Cyclic Redundancy Check (CRC)
• การตรวจสอบความซ้ำซ้อนตามยาว (LRC)

การตรวจสอบความเท่าเทียมกัน

• เรียกอีกอย่างว่าการตรวจสอบความเท่าเทียมกัน
• เป็นกลไกที่มีประสิทธิภาพและคุ้มค่าสำหรับการตรวจจับข้อผิดพลาด
• ในเทคนิคนี้ บิตส่วนเกินที่เพิ่มเข้าไปในทุกหน่วยข้อมูลเรียกว่า บิตพาริตี โดยจะตั้งค่าบิตนี้เพื่อให้จำนวนรวมของเลข 1 ในหน่วยนั้นเป็นเลขคู่ (พาริตีคู่) หรือเลขคี่ (พาริตีคี่)

ตรวจสอบความซ้ำซ้อนตามยาว

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

วงจรตรวจสอบความซ้ำซ้อน

การตรวจสอบความซ้ำซ้อนแบบวนรอบ (Cyclic Redundancy Check) จะเพิ่มลำดับของบิตที่ซ้ำซ้อนเข้าไปที่ส่วนท้ายของหน่วยข้อมูล เพื่อให้หน่วยข้อมูลที่ได้นั้นหารลงตัวด้วยเลขฐานสองที่กำหนดไว้ล่วงหน้าตัวที่สอง

เมื่อถึงปลายทาง ข้อมูลที่เข้ามาจะถูกหารด้วยจำนวนเดียวกัน หากไม่มีเศษเหลือ แสดงว่าข้อมูลนั้นถูกต้องและได้รับการยอมรับ แต่หากมีเศษเหลือ แสดงว่าข้อมูลนั้นเสียหายระหว่างการส่ง และต้องถูกปฏิเสธ

แฮมมิงคืออะไร Code?

รหัสแฮมมิง (Hamming code) เป็นรหัสเชิงเส้นที่ใช้ตรวจจับข้อผิดพลาดระดับบิตได้สูงสุดถึงสองบิต และแก้ไขข้อผิดพลาดระดับบิตเดียวได้ โดยทั่วไป การแก้ไขข้อผิดพลาดในลักษณะนี้จะทำงานที่เลเยอร์การเชื่อมโยงข้อมูล (data link layer) โดยการจัดเฟรมข้อมูลและตรวจสอบความสมบูรณ์ของข้อมูลระหว่างโหนดที่อยู่ติดกัน

ในรหัสแฮมมิง (Hamming code) แหล่งข้อมูลจะเข้ารหัสข้อความโดยการเพิ่มบิตส่วนเกิน บิตส่วนเกินเหล่านี้จะถูกแทรกและสร้างขึ้นในตำแหน่งเฉพาะในข้อความเพื่อดำเนินการตรวจจับและแก้ไขข้อผิดพลาด

ประวัติของแฮมมิง Code

• รหัสแฮมมิง (Hamming code) เป็นเทคนิคที่คิดค้นโดย อาร์.ดับเบิลยู. แฮมมิง (RW Hamming) เพื่อตรวจจับและแก้ไขข้อผิดพลาด
• สามารถนำไปใช้กับหน่วยข้อมูลที่มีความยาวใดๆ ก็ได้ และใช้ความสัมพันธ์ระหว่างบิตข้อมูลและบิตสำรอง
• แฮมมิงทำงานเกี่ยวกับปัญหาการแก้ไขข้อผิดพลาดและพัฒนาอัลกอริทึมที่มีประสิทธิภาพมากขึ้นเรื่อยๆ
• ในปี ค.ศ. 1950 เขาได้ตีพิมพ์รหัสแฮมมิง (Hamming code) ซึ่งยังคงใช้กันอย่างแพร่หลายในปัจจุบันในแอปพลิเคชันต่างๆ เช่น หน่วยความจำ ECC

การประยุกต์ใช้แฮมมิง Code

ต่อไปนี้คือตัวอย่างการใช้งานรหัสแฮมมิงที่พบได้ทั่วไป:

• ดาวเทียม
• หน่วยความจำคอมพิวเตอร์ (ECC RAM)
• โมเด็ม
• พลาสม่าแคม
• เปิดตัวเชื่อมต่อ
• ลวดป้องกัน
• โปรเซสเซอร์ฝังตัว

ข้อดีของแฮมมิง Code

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

ข้อเสียของแฮมมิง Code

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

วิธีการเข้ารหัสข้อความด้วยการเข้ารหัสแบบแฮมมิง Code

กระบวนการที่ผู้ส่งใช้ในการเข้ารหัสข้อความประกอบด้วยสามขั้นตอนดังต่อไปนี้:

• คำนวณจำนวนบิตส่วนเกินทั้งหมด
• กำหนดตำแหน่งของบิตส่วนเกิน
• คำนวณค่าของบิตส่วนเกินแต่ละบิต

เมื่อบิตส่วนเกินถูกฝังไว้ในข้อความแล้ว รหัสคำที่สมบูรณ์จะถูกส่งไปยังผู้รับ

ขั้นตอนที่ 1) คำนวณจำนวนบิตส่วนเกินทั้งหมด

สมมติว่าข้อความนั้นประกอบด้วย n บิตข้อมูลและ p บิตส่วนเกินที่เพิ่มเข้ามาเพื่อให้ 2^p สามารถระบุสถานะที่แตกต่างกันได้อย่างน้อย (n + p + 1) สถานะ

ในที่นี้ (n + p) แสดงถึงตำแหน่งของข้อผิดพลาดในแต่ละตำแหน่งบิต (n + p) และสถานะพิเศษหนึ่งสถานะบ่งชี้ว่าไม่มีข้อผิดพลาด เนื่องจากบิตพาริตี p บิตสามารถบ่งชี้ได้ 2^p รัฐ 2^p ต้องมีค่าอย่างน้อยเท่ากับ (n + p + 1)

ขั้นตอนที่ 2) นำส่วนที่เกินมาใส่ในตำแหน่งที่ถูกต้อง

บิตส่วนเกินจำนวน p บิตจะถูกวางไว้ในตำแหน่งบิตที่เป็นกำลังของ 2 เช่น 1, 2, 4, 8 และ 16 โดยจะเรียกบิตเหล่านี้ว่า p₁ (ที่ตำแหน่ง 1) น₂ (ที่ตำแหน่ง 2) น₃ (ที่ตำแหน่งที่ 4) และอื่นๆ

ขั้นตอนที่ 3) คำนวณค่าของบิตส่วนเกินแต่ละบิต

บิตส่วนเกินแต่ละบิตคือบิตพาริตี ซึ่งทำให้จำนวนเลข 1 ในกลุ่มนั้นเป็นเลขคู่หรือเลขคี่ พาริตีมีสองประเภท ได้แก่:

• ความเท่าเทียมกัน: จำนวนรวมของเลข 1 ในตำแหน่งที่ครอบคลุมจะถูกทำให้เป็นเลขคู่
• ความเท่าเทียมกันที่แปลกประหลาด: จำนวนรวมของเลข 1 ในตำแหน่งที่ถูกปิดบังนั้นเป็นเลขคี่

บิตพาริตีแต่ละบิตครอบคลุมชุดตำแหน่งเฉพาะ ซึ่งกำหนดโดยการแสดงเลขฐานสองของหมายเลขตำแหน่ง:

• p₁ ตรวจสอบทุกตำแหน่งที่มีค่าไบนารีเป็น 1 ในบิตที่มีค่าน้อยที่สุด — ตำแหน่งที่ 1, 3, 5, 7, 9, 11 และต่อไปเรื่อยๆ
• p₂ ตรวจสอบทุกตำแหน่งที่มีค่าไบนารีเป็น 1 ในบิตที่สองนับจากด้านขวา — ตำแหน่งที่ 2, 3, 6, 7, 10, 11 และต่อไปเรื่อยๆ
• p₃ ตรวจสอบทุกตำแหน่งที่มีค่าไบนารีเป็น 1 ในบิตที่สามนับจากด้านขวา — ตำแหน่งที่ 4 ถึง 7, 12 ถึง 15 และอื่นๆ

ตัวอย่างการทำงาน (7,4): พิจารณาบิตข้อมูลทั้งสี่บิต 1011ต้องใช้บิตพาริตีสามบิต (2³ = 8 ≥ 4 + 3 + 1) ทำให้ได้รหัสคำเจ็ดบิตที่จัดเรียงเป็น p₁ p₂ d₁ p₃ d₂ d₃ d₄การวางข้อมูลทำให้ตำแหน่งที่ 3, 5, 6, 7 มีค่าเท่ากับ 1, 0, 1, 1 โดยใช้หลักความเท่าเทียมกันแบบคู่: p₁ ครอบคลุมตำแหน่งที่ 1, 3, 5, 7 (บิต 1, 0, 1 → p)₁ = 0); p₂ ครอบคลุม 2, 3, 6, 7 (บิต 1, 1, 1 → p)₂ = 1); p₃ ครอบคลุม 4, 5, 6, 7 (บิต 0, 1, 1 → p)₃ = 0) transmitดังนั้น รหัส ted คือ 0110011.

วิธีถอดรหัสข้อความในภาษาแฮมมิง Code

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

• นับจำนวนบิตที่ซ้ำซ้อน
• จัดวางบิตส่วนเกินทั้งหมดให้ถูกต้อง
• ทำการตรวจสอบความเท่าเทียมกัน (parity check)

ขั้นตอนที่ 1) นับจำนวนบิตที่ซ้ำซ้อน ใช้สูตรเดียวกับที่ใช้ในการเข้ารหัส: 2^p ≥ n + p + 1 โดยที่ n คือจำนวนบิตข้อมูล และ p คือจำนวนบิตส่วนเกิน

ขั้นตอนที่ 2) จัดวางบิตส่วนเกินทั้งหมดให้ถูกต้อง บิตส่วนเกินแต่ละบิตจะอยู่ที่ตำแหน่งบิตที่เป็นกำลังของ 2 เช่น 1, 2, 4 และ 8

ขั้นตอนที่ 3) ดำเนินการตรวจสอบความเท่าเทียมกัน (Parity Check) บิตพาริตีจะถูกคำนวณใหม่จากบิตข้อมูลและบิตส่วนเกินที่ได้รับ:

• p₁ = parity(1, 3, 5, 7, 9, 11, …)
• p₂ = parity(2, 3, 6, 7, 10, 11, …)
• p₃ = parity(4–7, 12–15, 20–23, …)

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

คำถามที่พบบ่อย