การตรวจจับและแก้ไขข้อผิดพลาด (ชั้นเชื่อมโยงข้อมูล)

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

Definition

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

Scope

หัวข้อนี้ครอบคลุมเทคนิคการเข้ารหัสที่ใช้ในชั้นเชื่อมโยงข้อมูลเพื่อจัดการกับข้อผิดพลาดของบิต: การตรวจสอบพาริตีแบบง่าย, พาริตีสองมิติ, เช็คซัมอินเทอร์เน็ต, และการตรวจสอบความซ้ำซ้อนแบบวนรอบ (CRC) สำหรับการตรวจจับ และรหัสแก้ไขข้อผิดพลาดแบบส่งต่อ เช่น รหัสแฮมมิงสำหรับการแก้ไข นอกจากนี้ยังกล่าวถึงการแลกเปลี่ยนระหว่างค่าใช้จ่ายส่วนเกินของความซ้ำซ้อนกับความแข็งแกร่งของการตรวจจับหรือการแก้ไข และการใช้งานของแต่ละเทคนิค โดยไม่รวมถึงความน่าเชื่อถือที่สร้างขึ้นในชั้นที่สูงกว่าซึ่งอาศัยการส่งซ้ำ ซึ่งเป็นการเสริมการเข้ารหัสมากกว่าการแทนที่

Core questions

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

Key concepts

• การตรวจสอบพาริตี
• พาริตีสองมิติ
• เช็คซัมอินเทอร์เน็ต
• การตรวจสอบความซ้ำซ้อนแบบวนรอบ (CRC)
• พหุนามตัวสร้าง
• การแก้ไขข้อผิดพลาดแบบส่งต่อ
• รหัสแฮมมิง
• ข้อผิดพลาดแบบกลุ่ม
• ค่าใช้จ่ายส่วนเกินของการเข้ารหัส

Key theories

ความซ้ำซ้อนสำหรับการตรวจจับข้อผิดพลาด

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

การแก้ไขข้อผิดพลาดแบบส่งต่อ

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

ขีดความสามารถของช่องสัญญาณและการสื่อสารที่เชื่อถือได้

ทฤษฎีสารสนเทศระบุว่าทุกช่องสัญญาณที่มีสัญญาณรบกวนมีขีดความสามารถที่ต่ำกว่านั้น การสื่อสารที่เชื่อถือได้โดยพลการเป็นไปได้ด้วยการเข้ารหัสที่เหมาะสม ซึ่งกำหนดขีดจำกัดพื้นฐานที่รหัสควบคุมข้อผิดพลาดในทางปฏิบัติเข้าใกล้

Clinical relevance

การควบคุมข้อผิดพลาดเป็นสิ่งที่มองไม่เห็นแต่มีอยู่ทั่วไป: CRC ปกป้องเฟรม Ethernet และ Wi-Fi, เช็คซัมปกป้องส่วนหัว IP และการขนส่ง, และการแก้ไขข้อผิดพลาดแบบส่งต่อเป็นสิ่งจำเป็นในกรณีที่การส่งซ้ำมีค่าใช้จ่ายสูงหรือไม่สามารถทำได้ เช่น ในลิงก์อวกาศห้วงลึก, สื่อจัดเก็บข้อมูล, และการสตรีมผ่านเครือข่ายไร้สายที่มีการสูญเสีย การรักษาสมดุลที่เหมาะสมระหว่างการตรวจจับกับการแก้ไขจะส่งผลต่อความน่าเชื่อถือและประสิทธิภาพในระบบการสื่อสารและการจัดเก็บข้อมูล

History

ทฤษฎีสารสนเทศของ Claude Shannon ในปี 1948 ได้สร้างการมีอยู่ของการเข้ารหัสที่เชื่อถือได้จนถึงขีดความสามารถของช่องสัญญาณ และรหัสของ Richard Hamming ในปี 1950 ได้ให้แผนการแก้ไขข้อผิดพลาดเดี่ยวที่เป็นไปได้ในทางปฏิบัติเป็นครั้งแรก การตรวจสอบความซ้ำซ้อนแบบวนรอบและรหัสที่แข็งแกร่งขึ้นตามมา และกลายเป็นมาตรฐานในการจัดเฟรมชั้นเชื่อมโยงข้อมูล และตั้งแต่นั้นมา สาขาวิชานี้ก็ได้ผลิตรหัสที่มีประสิทธิภาพ (เช่น รหัสเทอร์โบและ LDPC) ที่เข้าใกล้ขีดจำกัดของ Shannon

Key figures

• Claude Shannon
• Richard Hamming

Seminal works

• shannon1948
• hamming1950
• kurose2021

Frequently asked questions

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

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

ทำไมเครือข่ายจึงใช้ CRC แทนพาริตีแบบง่าย?

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