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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

รหัสการตรวจจับข้อผิดพลาดสามประเภท ได้แก่:

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

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

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

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

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

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

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

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

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

ประวัติความเป็นมาของรหัสแฮมมิง

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

การประยุกต์ใช้รหัส Hamming

ต่อไปนี้เป็นการใช้งานทั่วไปของการใช้โค้ด Hamming:

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

ข้อดีของรหัส Hamming

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

ข้อเสียของรหัส Hamming

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

วิธีเข้ารหัสข้อความใน Hamming Code

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

• การคำนวณจำนวนบิตซ้ำซ้อนทั้งหมด
• การตรวจสอบตำแหน่งของบิตที่ซ้ำซ้อน
• สุดท้ายคือการคำนวณค่าของบิตที่ซ้ำซ้อนเหล่านี้

เมื่อบิตที่ซ้ำซ้อนข้างต้นถูกฝังอยู่ในข้อความ บิตนั้นจะถูกส่งไปยังผู้ใช้

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

สมมติว่าข้อความประกอบด้วย:

• n– จำนวนบิตข้อมูล
• p – จำนวนบิตซ้ำซ้อนที่ถูกเพิ่มเข้าไปเพื่อให้ np สามารถระบุสถานะที่แตกต่างกันอย่างน้อย (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 เป็นเลขคู่หรือคี่

ความเท่าเทียมกันสองประเภทคือ ?

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

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

P1 คือพาริตีบิตสำหรับบิตข้อมูลทุกบิตในตำแหน่งที่การแสดงไบนารี่มี 1 อยู่ในตำแหน่งที่มีความสำคัญน้อยกว่า ไม่รวม 1 Like (3, 5, 7, 9, …. )

P2 คือพาริตีบิตสำหรับบิตข้อมูลทุกบิตในตำแหน่งที่มีการแทนไบนารี่รวม 1 ในตำแหน่งที่ 2 จากขวา ไม่รวม 2 Like (3, 6, 7, 10, 11,…)

P3 คือพาริตีบิตสำหรับทุกบิตในตำแหน่งที่การแทนค่าไบนารี่มี 1 อยู่ในตำแหน่งที่ 3 จากขวา ไม่รวม 4 Like (5-7, 12-15,… )

การถอดรหัสข้อความในรหัส Hamming

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

กระบวนการคำนวณใหม่ดำเนินการตามขั้นตอนต่อไปนี้:

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

ขั้นตอน 1) การนับจำนวนบิตที่ซ้ำซ้อน

คุณสามารถใช้สูตรเดียวกันในการเข้ารหัสคือจำนวนบิตที่ซ้ำซ้อน

2^p - เอ็น + พี + ​​1

ในที่นี้จำนวนบิตข้อมูลและ p คือจำนวนบิตที่ซ้ำซ้อน

ขั้นตอน 2) วางตำแหน่งบิตที่ซ้ำซ้อนทั้งหมดอย่างถูกต้อง

โดยที่ p เป็นบิตซ้ำซ้อนซึ่งอยู่ที่ตำแหน่งบิตที่มีกำลัง 2 เช่น 1, 2, 4, 8 เป็นต้น

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

พาริตีบิตจำเป็นต้องคำนวณตามบิตข้อมูลและบิตที่ซ้ำซ้อน

p1 = ความเท่าเทียมกัน (1, 3, 5, 7, 9, 11…)

p2 = ความเท่าเทียมกัน(2, 3, 6, 7, 10, 11… )

p3 = ความเท่าเทียมกัน(4-7, 12-15, 20-23… )

สรุป

• ข้อมูลที่ส่งอาจเสียหายระหว่างการสื่อสาร
• ข้อผิดพลาดบิตสามประเภทคือ 1) ข้อผิดพลาดบิตเดียว 2) ข้อผิดพลาดหลายบิต 3) ข้อผิดพลาดเบิร์สต์บิต
• การเปลี่ยนแปลงที่เกิดขึ้นในหนึ่งบิตในลำดับข้อมูลทั้งหมดเรียกว่า "ข้อผิดพลาดบิตเดียว"
• ในลำดับข้อมูล หากมีการเปลี่ยนแปลงลำดับข้อมูลตั้งแต่สองบิตขึ้นไปจากตัวส่งไปยังตัวรับ จะเรียกว่า "ข้อผิดพลาดหลายบิต"
• การเปลี่ยนแปลงชุดบิตในลำดับข้อมูลเรียกว่า "ข้อผิดพลาดเบิร์ส"
• การตรวจจับข้อผิดพลาดเป็นวิธีการตรวจจับข้อผิดพลาดที่มีอยู่ในข้อมูลที่ส่งจากเครื่องส่งไปยังเครื่องรับในระบบการสื่อสารข้อมูล
• รหัสการตรวจจับข้อผิดพลาด 1 ประเภท ได้แก่ 2) การตรวจสอบความเท่าเทียมกัน 3) การตรวจสอบความซ้ำซ้อนแบบวนรอบ (CRC) XNUMX) การตรวจสอบความซ้ำซ้อนตามยาว (LRC)
• รหัส Hamming เป็นโค้ดไลเนอร์ที่มีประโยชน์สำหรับการตรวจจับข้อผิดพลาดจนถึงข้อผิดพลาดบิตทันทีสูงสุดสองครั้ง สามารถเกิดข้อผิดพลาดบิตเดียวได้
• รหัส Hamming เป็นเทคนิคที่สร้างโดย RWHamming เพื่อตรวจจับข้อผิดพลาด
• การใช้งานทั่วไปของการใช้โค้ด Hamming ได้แก่ ดาวเทียม หน่วยความจำคอมพิวเตอร์ โมเด็ม โปรเซสเซอร์แบบฝังตัว ฯลฯ
• ประโยชน์ที่ใหญ่ที่สุดของวิธีการโค้ด hamming นั้นมีผลกับเครือข่ายที่มีการสตรีมข้อมูลสำหรับข้อผิดพลาดบิตเดียว
• ข้อเสียเปรียบที่ใหญ่ที่สุดของวิธี hamming code คือสามารถแก้ปัญหาได้เพียงบิตเดียวเท่านั้น
• เราสามารถดำเนินการเข้ารหัสและถอดรหัสข้อความโดยใช้โค้ดแฮมมิง