การตรวจสอบพาริตี้
การตรวจสอบพาริตี้ เพิ่มบิตหนึ่งตัวที่เรียกว่า บิตพาริตี้ เข้าไปในแต่ละไบต์ มีสองชนิด:
พาริตี้คู่ — จำนวนรวมของ 1 ในไบต์ (รวมถึงบิตพาริตี้) ต้องเป็น คู่ ;
พาริตี้คี่ — จำนวนรวมของ 1 ต้องเป็น คี่ .
ตัวอย่าง (พาริตี้คู่): ข้อมูล 1011001 มี 1 สี่ตัว ซึ่งเป็นคู่อยู่แล้ว ดังนั้นบิตพาริตี้คือ 0:
parity bit + data
0 1011001
Parity bit ถูกเพิ่มเข้าไปเพื่อให้จำนวนของ 1 เป็นคู่ (หรือคี่)
ในการหาความผิดพลาด: ผู้รับจะนับจำนวน 1 หากตกลงใช้พาริตี้คู่แต่ได้รับไบต์ที่มีจำนวน 1 เป็น คี่ แสดงว่าเกิดความผิดพลาดระหว่างการส่งข้อมูล
การตรวจสอบพาริตี้ไม่สามารถตรวจจับความผิดพลาดได้ทุกกรณี หากบิตสองตัวถูกสลับ ค่ารวมอาจยังคงดูถูกต้องอยู่
ตัวอย่างวิธีทำ บิตพาริตี้ตัวเดียวบอกคุณได้ว่า มี ความผิดพลาดเกิดขึ้น แต่ไม่บอก ตำแหน่ง บล็อกพาริตี้ สามารถระบุตำแหน่งบิตที่ผิดได้sending字节 พร้อมกัน พร้อมบิตพาริตี้แถวแต่ละตัว และมี ไบต์พาริตี้ เพิ่มอีกตัวหนึ่งด้านล่างซึ่งเก็บบิตพาริตี้ของแต่ละคอลัมน์ ใช้พาริตี้เลขคู่ในตัวอย่างด้านล่าง และมีบิตหนึ่งตัวถูกเปลี่ยนระหว่างการจัดส่ง จงหาตำแหน่งนั้น
b1 b2 b3 b4 b5 | parity
byte 1 1 0 1 1 0 | 1
byte 2 0 1 1 0 1 | 1
byte 3 1 1 1 1 0 | 1 <- row: odd number of 1s
byte 4 0 0 1 1 0 | 0
------------------------------
parity 0 0 1 1 1 | 1
^ column b3: odd number of 1s
แถว byte 3 ขาดความถูกต้องของพาริตี้เลขคู่ และคอลัมน์ b3 ก็ขาดความถูกต้องเช่นกัน บิตที่ถูกเปลี่ยนคือจุดตัดของทั้งสอง: byte 3, bit b3 การเปลี่ยนกลับจาก 1 เป็น 0 จะซ่อมแซมข้อมูลได้ ตามสมมติฐานความผิดพลาดของบิตเดียวที่กำหนดไว้ แถวและคอลัมน์ที่ล้มเหลวจะชี้ตำแหน่งบิต ทำให้ผู้รับสามารถแก้ไขได้ ความผิดพลาดของหลายบิตอาจหลบพ้นการตรวจจับหรือให้ผลลัพธ์ที่สับสนได้
Checksum
Checksum คือค่าที่คำนวณจากข้อมูลทั้งหมดก่อนการส่ง ผู้รับจะคำนวณ checksum ใหม่จากข้อมูลที่รับมา หากค่าทั้งสองไม่ตรงกัน แสดงว่าเกิดความผิดพลาดและข้อมูลจะถูกส่งใหม่
ขั้นตอน:
ผู้ส่งคำนวณค่าเช็กซัมจากบล็อกข้อมูลโดยใช้อัลกอริทึมที่ตกลงกันไว้;
ส่งค่าเช็กซัมไปพร้อมกับข้อมูล;
ผู้รับคำนวณค่าเช็กซัมอีกครั้งจากข้อมูลที่ได้รับโดยใช้อัลกอริทึมเดียวกัน;
ผู้รับเปรียบเทียบค่าทั้งสอง: หากตรงกันจะยอมรับข้อมูล หากไม่ตรงกันจะขอให้ส่งข้อมูลอีกครั้ง
Echo check
ใน echo check ผู้รับจะส่งข้อมูลกลับไปยังผู้ส่ง ผู้ส่งจะเปรียบเทียบกับต้นฉบับ หากไม่ตรงกัน แสดงว่าเกิดความผิดพลาด (วิธีการนี้ต้องใช้การส่งข้อมูลสองครั้ง จึงมีความช้า)
Automatic Repeat reQuest (ARQ)
Automatic Repeat reQuest (ARQ) ใช้ข้อความที่เรียกว่า การยืนยันการรับ
หลักสูตรเรียกสิ่งนี้ว่า Automatic Repeat Query (ARQ); Automatic Repeat Request เป็นอีกชื่อหนึ่งของวิธีการเดียวกัน ผู้ส่งเริ่มจับเวลา timeout เมื่อส่งแพ็กเก็ต ผู้รับใช้การตรวจสอบข้อผิดพลาดกับแพ็กเก็ตที่ได้รับ หากการตรวจสอบผ่าน จะส่ง Positive Acknowledgement (การยืนยันเชิงบวก) หากตรวจพบข้อผิดพลาด จะส่ง Negative Acknowledgement (การยืนยันเชิงลบ)
ARQ: การตอบกลับเชิงบวกทำให้ส่งต่อไป; การตอบกลับเชิงลบหรือการหมดเวลาทำให้ผู้ส่งส่งใหม่
ลองทำ — แพ็กเก็ต4 ในสามกรณีแยกกัน แพ็กเก็ต4 (A) ผ่านการตรวจสอบข้อผิดพลาดของผู้รับ, (B) ล้มเหลวในการตรวจสอบ, หรือ (C) ไม่เคยมาถึง สำหรับแต่ละกรณี ให้เลือกการตอบกลับของผู้รับและการกระทำถัดไปของผู้ส่ง
คำอธิบายแบบมีขั้นตอน
กรณี
ผู้รับ
ผู้ส่ง
A
ส่งการตอบกลับเชิงบวก
รับได้; หยุดนาฬิกา; สามารถส่งแพ็กเก็ตถัดไปได้
B
ส่งการตอบกลับเชิงลบ
รับได้; ส่งแพ็กเก็ต 4 ใหม่; เริ่มนาฬิกาสงใหม่
C
ไม่มีแพ็กเก็ตให้ตรวจสอบ
หมดเวลา; ส่งแพ็กเก็ต 4 ใหม่; เริ่มนาฬิกาสงใหม่
การตอบกลับเชิงลบอาจทำให้มีการส่งซ้ำก่อนที่นาฬิกาจะหมดเวลา หากไม่มีการยืนยันเชิงบวกก่อนหมดเวลา ผู้ส่งจะทำการส่งซ้ำ นาฬิกาช่วยจัดการกับสถานะเงียบ รวมถึงกรณีแพ็กเก็ตหายหรือการตอบกลับหาย
การถ่ายโอน — ตอบกลับที่หายไป แพ็กเก็ต 4 arrives and passes its check. The receiver sends a positive acknowledgement, but this reply is lost. What does the sender do when its timer expires? Does timeout prove that packet 4 was damaged?
คำตอบ. ผู้ส่งส่งแพ็กเก็ต 4 ใหม่และรีเซ็ตนาฬิกาจับเวลา ผู้รับทราบว่าแพ็กเก็ตมาถึงอย่างสมบูรณ์ แต่ผู้ส่งไม่มีหลักฐานยืนยัน Timeout ไม่บอกให้ผู้ส่งว่าแพ็กเก็ตหรือตอบกลับหายหรือล่าช้า ARQ ขอส่งข้อมูลอีกครั้ง; มันเองไม่ซ่อมแซมบิตที่เสียหาย ใช้การตรวจสอบข้อผิดพลาดเพื่อตัดสินใจว่าจะยอมรับแพ็กเก็ตที่ได้รับหรือไม่
Check digit
Check digit คือตัวเลขเสริมที่วางไว้ท้ายชุดตัวเลข ซึ่งคำนวณจากตัวเลขอื่นๆ ใช้เพื่อตรวจสอบข้อผิดพลาดเมื่อมีการ พิมพ์ตัวเลข
When the number is entered, the check digit is calculated again and compared. Depending on the method, it can detect some of these errors; no check digit guarantees that every entry error is found:
ตัวเลขที่พิมพ์ผิด,
ความผิดพลาดจากการสลับตำแหน่ง (ตัวเลขสองตัวสลับที่ เช่น พิมพ์ 21 เป็น 12),
ตัวเลขที่ขาดหายไปหรือมีตัวเลขเกินมา,
ความผิดพลาดทางการออกเสียง (ตัวเลขที่อ่านเสียงคล้ายกัน เช่น 13 กับ 30).
Check digit ถูกใช้ใน บาร์โค้ด และ ISBN (เลขหนังสือ)
ตัวอย่างแสดงวิธีทำ (ISBN-13) เลข 12 หลักแรกของหมายเลขหนังสือคือ 978034083988 จงคำนวณเลขตรวจสอบ วิธี ISBN-13 คูณเลขแต่ละหลักด้วย 1, 3, 1, 3, … ตามลำดับ บวกผลคูณเข้าด้วยกัน แล้วเลือกเลขตรวจสอบที่ทำให้ผลรวมเป็นพหุคูณของ 10
เลขแต่ละหลัก
9
7
8
0
3
4
0
8
3
9
8
8
น้ำหนัก
1
3
1
3
1
3
1
3
1
3
1
3
ผลคูณ
9
21
8
0
3
12
0
24
3
27
8
24
ผลรวมคือ $139$ หารด้วย 10 ได้เศษ $9$ และ $10 - 9 = 1$ ดังนั้นเลขตรวจสอบคือ 1 (หากเศษเป็น 0 เลขตรวจสอบคือ 0) หมายเลขเต็มคือ 9780340839881
ตอนนี้สมมติว่าเลขหลักที่ 9 และหลักที่ 10 ถูกพิมพ์สลับกัน: ...8 9 3 8 8... ผลคูณของเลขสองหลักนั้นกลายเป็น $9 \times 1 + 3 \times 3 = 18$ แทน $3 + 27 = 30$ ดังนั้นผลรวมของเลข 12 หลักแรกคือ $127$ และ $127 + 1 = 128$ ไม่ เป็นพหุคูณของ 10: จึงตรวจพบข้อผิดพลาดจากการสลับตำแหน่ง