บิตพาริตี

Q: ความเท่าเทียมกัน

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

ข้อมูล 7 บิต	(จำนวนบิต 1)	8 บิต รวมทั้งพาริตี
ข้อมูล 7 บิต	(จำนวนบิต 1)	สม่ำเสมอ	แปลก
0000000	0	0000000 0	0000000 1
1010001	3	1010001 1	1010001 0
1101001	4	1101001 0	1101001 1
1111111	7	1111111 1	1111111 0

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

บิตพาริตีช่วยให้มั่นใจได้ว่าจำนวนบิต 1 ทั้งหมดในสตริงเป็นเลขคู่หรือเลขคี่ [ ^{1 ] ดังนั้น}จึงมีบิตพาริตีสองแบบ ได้แก่บิตพาริตีคู่และบิตพาริตีคี่ในกรณีของพาริตีคู่ สำหรับชุดบิตที่กำหนด จะนับบิตที่มีค่าเป็น 1 หากจำนวนนั้นเป็นเลขคี่ ค่าของบิตพาริตีจะถูกตั้งเป็น 1 ทำให้จำนวนรวมของการเกิด 1 ในชุดทั้งหมด (รวมถึงบิตพาริตี) เป็นเลขคู่ หากจำนวน 1 ในชุดบิตที่กำหนดเป็นเลขคู่อยู่แล้ว ค่าของบิตพาริตีจะเป็น 0 ในกรณีของพาริตีคี่ การเข้ารหัสจะกลับกัน สำหรับชุดบิตที่กำหนด หากจำนวนบิตที่มีค่าเป็น 1 เป็นเลขคู่ ค่าของบิตพาริตีจะถูกตั้งเป็น 1 ทำให้จำนวนรวมของ 1 ในชุดทั้งหมด (รวมถึงบิตพาริตี) เป็นเลขคี่ ถ้าจำนวนบิตที่มีค่าเป็น 1 เป็นเลขคี่ จำนวนนั้นก็จะเป็นเลขคี่อยู่แล้ว ดังนั้นค่าของบิตพาริตีจึงเป็น 0 พาริตีเป็นกรณีพิเศษของการตรวจสอบความซ้ำซ้อนแบบวนรอบ (CRC) โดยที่ CRC 1 บิตนั้นสร้างขึ้นจากพหุนามx + 1

ความเท่าเทียมกัน

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

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

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

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

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

การตรวจจับข้อผิดพลาด

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

การตรวจสอบบิตพาริตีนั้นใช้ในบางครั้งสำหรับการส่ง อักขระ ASCIIซึ่งมี 7 บิต โดยเหลือบิตที่ 8 ไว้เป็นบิตพาริตี

ตัวอย่างเช่น บิตพาริตีสามารถคำนวณได้ดังนี้ สมมติว่าอลิซและบ็อบกำลังสื่อสารกัน และอลิซต้องการส่งข้อความ 4 บิตง่ายๆ คือ 1001 ให้กับบ็อบ

ประเภทของพาริตีบิต	สถานการณ์การส่งต่อที่ประสบความสำเร็จ
ความเท่าเทียมกัน	อลิซต้องการส่งต่อหมายเลข 1001 และ 1011 อลิซคำนวณค่าบิตพาริตี: 1+0+0+1 (mod 2) = 0 1+0+1+1 (mod 2) = 1 อลิซเพิ่มบิตพาริตีแล้วส่ง: 1001 0และ 1011 1 บ็อบได้รับ: 10010 และ 10111 บ็อบคำนวณพาริตี: 1+0+0+1+0 (mod 2) = 0 1+0+1+1+1 (mod 2) = 0 บ็อบรายงานว่าการส่งสัญญาณถูกต้องหลังจากสังเกตเห็นผลลัพธ์ที่สม่ำเสมอตามที่คาดไว้
ความเท่าเทียมกันที่คี่	อลิซต้องการส่งต่อหมายเลข 1001 และ 1011 อลิซคำนวณค่าบิตพาริตี: 1+0+0+1 (+ 1 mod 2) = 1 1+0+1+1 (+ 1 mod 2) = 0 อลิซเพิ่มบิตพาริตีแล้วส่ง: 1001 1และ 1011 0 บ็อบได้รับ: 10011 และ 10110 บ็อบคำนวณพาริตีโดยรวม: 1+0+0+1+1 (mod 2) = 1 1+0+1+1+0 (mod 2) = 1 บ็อบรายงานว่าการส่งข้อมูลถูกต้องหลังจากสังเกตเห็นผลลัพธ์ที่ผิดปกติอย่างที่คาดไว้

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

ประเภทของข้อผิดพลาดพาริตีบิต	สถานการณ์การส่งข้อมูลล้มเหลว
ความเท่าเทียมกัน เกิดข้อผิดพลาดในบิตที่สอง	อลิซต้องการส่งต่อ: 1001 อลิซคำนวณค่าบิตพาริตี: 1^0^0^1 = 0 อลิซเพิ่มบิตพาริตีแล้วส่ง: 10010 ...เกิดข้อผิดพลาดในการส่งข้อมูล... บ็อบได้รับ: 1 1 010 บ็อบคำนวณพาริตีโดยรวม: 1^1^0^1^0 = 1 บ็อบรายงานการส่งข้อมูลผิดพลาดหลังจากสังเกตเห็นผลลัพธ์ที่แปลกประหลาดไม่คาดคิด
ความเท่าเทียมกัน เกิดข้อผิดพลาดในบิตพาริตี	อลิซต้องการส่งต่อ: 1001 อลิซคำนวณค่าพาริตีคู่ได้ดังนี้: 1^0^0^1 = 0 อลิซส่ง: 10010 ...เกิดข้อผิดพลาดในการส่งข้อมูล... บ็อบได้รับ: 1001 1 บ็อบคำนวณพาริตีโดยรวม: 1^0^0^1^1 = 1 บ็อบรายงานการส่งข้อมูลผิดพลาดหลังจากสังเกตเห็นผลลัพธ์ที่แปลกประหลาดไม่คาดคิด

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

ประเภทของข้อผิดพลาดพาริตีบิต	สถานการณ์การส่งข้อมูลล้มเหลว
ความเท่าเทียมกัน บิตที่เสียหายสองบิต	อลิซต้องการส่งต่อ: 1001 อลิซคำนวณค่าพาริตีคู่ได้ดังนี้: 1^0^0^1 = 0 อลิซส่ง: 10010 ...เกิดข้อผิดพลาดในการส่งข้อมูล... บ็อบได้รับ: 1 1 01 1 บ็อบคำนวณพาริตีโดยรวม: 1^1^0^1^1 = 0 บ็อบรายงานว่าระบบส่งกำลังถูกต้อง ทั้งที่ความจริงแล้วไม่ถูกต้อง

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

การใช้งาน

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

ในการส่งข้อมูล แบบอนุกรม รูปแบบทั่วไปคือ บิตข้อมูล 7 บิต บิตพาริตีคู่ 1 บิต และบิตหยุด 1 หรือ 2 บิต รูปแบบนี้สามารถรองรับอักขระ ASCII 7 บิตทั้งหมดในไบต์ 8 บิตได้ อย่างไรก็ตาม รูปแบบอื่นก็เป็นไปได้เช่นกัน โดยบิตข้อมูล 8 บิตบวกบิตพาริตีสามารถส่งค่าไบต์ 8 บิตทั้งหมดได้

ในบริบทของการสื่อสารแบบอนุกรม ค่าพาริตีมักจะถูกสร้างและตรวจสอบโดยฮาร์ดแวร์อินเทอร์เฟซ (เช่นUART ) และเมื่อได้รับข้อมูลแล้ว ผลลัพธ์จะถูกส่งไปยังโปรเซสเซอร์เช่น CPU (และระบบปฏิบัติการ ด้วย ) ผ่านบิตสถานะในรีจิสเตอร์ฮาร์ดแวร์ใน ฮาร์ดแวร์ อินเทอร์เฟซ การแก้ไขข้อผิดพลาดมักทำได้โดยการส่งข้อมูลซ้ำ ซึ่งรายละเอียดต่างๆ มักจะถูกจัดการโดยซอฟต์แวร์ (เช่น รูทีน I/O ของระบบปฏิบัติการ)

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

อาร์เรย์ RAID

ข้อมูลพาริตีถูกใช้โดยอาร์เรย์ RAID ( redundant array of independent/inexpensive disks ) เพื่อให้เกิดความซ้ำซ้อนหากไดรฟ์ใดไดรฟ์หนึ่งในอาร์เรย์เกิดความเสียหาย ข้อมูลที่เหลืออยู่บนไดรฟ์อื่นๆ สามารถนำมารวมกับข้อมูลพาริตี (โดยใช้ฟังก์ชันบูลีนXOR ) เพื่อสร้างข้อมูลที่หายไปขึ้นมาใหม่ได้

ตัวอย่างเช่น สมมติว่าไดรฟ์สองตัวในอาร์เรย์ RAID 4สามไดรฟ์มีข้อมูลดังต่อไปนี้:

ไดรฟ์ 1:	01101101
ไดรฟ์ 2:	11010100

ในการคำนวณข้อมูลพาริตีสำหรับไดรฟ์ทั้งสอง จะทำการดำเนินการ XOR กับข้อมูลของไดรฟ์ทั้งสอง:

	01101101
เอ็กซ์ออร์	11010100
	10111001

ข้อมูลพาริตีที่ได้คือ10111001จะถูกจัดเก็บไว้ในไดรฟ์ที่ 3

หากไดรฟ์ใดไดรฟ์หนึ่งในสามตัวเกิดความเสียหาย ข้อมูลจากไดรฟ์ที่เสียหายสามารถกู้คืนได้บนไดรฟ์สำรอง โดยการนำข้อมูลจากไดรฟ์ที่เหลือมาทำการ XOR เช่นเดียวกัน เช่น หากไดรฟ์ที่ 2 เกิดความเสียหาย ข้อมูลของไดรฟ์นั้นสามารถกู้คืนได้โดยใช้ผลลัพธ์จากการ XOR ของข้อมูลจากไดรฟ์ที่เหลืออีกสองตัว คือ ไดรฟ์ที่ 1 และไดรฟ์ที่ 3:

ไดรฟ์ 1:	01101101
ไดรฟ์ 3:	10111001

ดังต่อไปนี้:

	01101101	ไดรฟ์ 1
เอ็กซ์ออร์	10111001	ไดรฟ์ 3
	11010100	ไดรฟ์ 2 ที่สร้างขึ้นใหม่

ผลลัพธ์ของการคำนวณ XOR นั้นจะให้ค่าที่อยู่ในไดรฟ์ 2 จากนั้นค่า11010100จะถูกจัดเก็บลงในไดรฟ์ 2 ซึ่งเป็นการซ่อมแซมอาร์เรย์ให้สมบูรณ์

ตรรกะ XOR ยังเทียบเท่ากับพาริตีคู่ (เพราะa XOR b XOR c XOR ... สามารถถือได้ว่าเป็น XOR( a , b , c , ...) ซึ่งเป็นตัวดำเนินการ n-ary ที่จะเป็นจริงก็ต่อเมื่อจำนวนอาร์กิวเมนต์เป็นเลขคี่เท่านั้น) ดังนั้นแนวคิด XOR ข้างต้นจึงใช้ได้กับอาร์เรย์ RAID ขนาดใหญ่ที่มีพาริตีเช่นกัน โดยใช้ดิสก์จำนวนเท่าใดก็ได้ ในกรณีของอาร์เรย์ RAID 3 ที่มีไดรฟ์ 12 ตัว ไดรฟ์ 11 ตัวจะเข้าร่วมในการคำนวณ XOR ที่แสดงข้างต้นและให้ค่าที่จัดเก็บไว้ในไดรฟ์พาริตีเฉพาะ

ใน ระบบ RAID-DPมี การใช้ส่วนขยายและรูปแบบต่างๆ ของกลไกบิตพาริตี เช่น "พาริตีคู่" "พาริตีสอง" หรือ "พาริตีแนวทแยง"

ประวัติศาสตร์

แทร็กพาริตีมีอยู่ในอุปกรณ์จัดเก็บข้อมูลเทปแม่เหล็ก ตัวแรก ในปี 1951 พาริตีในรูปแบบนี้ ซึ่งใช้กับสัญญาณขนานหลายสัญญาณ เรียกว่าการตรวจสอบความซ้ำซ้อนตามขวาง (transverse redundancy check ) ซึ่งสามารถรวมกับพาริตีที่คำนวณจากบิตหลายบิตที่ส่งผ่านสัญญาณเดียว เรียกว่าการตรวจสอบความซ้ำซ้อนตามยาว (longitudinal redundancy check ) ในบัสแบบขนาน จะมีบิตตรวจสอบความซ้ำซ้อนตามยาวหนึ่งบิตต่อสัญญาณขนานหนึ่งสัญญาณ

ระบบตรวจสอบความถูกต้องของข้อมูล (Parity) ยังถูกนำมาใช้ในระบบป้อนข้อมูลด้วยเทปกระดาษ ( เทปเจาะรู ) อย่างน้อยบางระบบ (ซึ่งมาก่อนระบบเทปแม่เหล็ก) ในระบบที่จำหน่ายโดยบริษัท ICL (เดิมชื่อ ICT) ของอังกฤษ เทปกระดาษกว้าง 1 นิ้ว (25 มม.) มีตำแหน่งรูเจาะ 8 ตำแหน่ง โดยตำแหน่งที่ 8 ใช้สำหรับตรวจสอบความถูกต้องของข้อมูล 7 ตำแหน่งแรกใช้สำหรับข้อมูล เช่น ASCII 7 บิต ส่วนตำแหน่งที่ 8 จะมีรูเจาะตามจำนวนรูที่เจาะสำหรับข้อมูล

ดูเพิ่มเติม

ลิงก์ภายนอก

วิธีการต่างๆ ในการสร้างบิตพาริตี รวมถึงการดำเนินการบิตอื่นๆ

1 ] ดังนั้น