การตรวจจับข้อผิดพลาดและรหัสการแก้ไข
เรารู้ว่าบิต 0 และ 1 สอดคล้องกับแรงดันไฟฟ้าอนาล็อกสองช่วงที่แตกต่างกัน ดังนั้นในระหว่างการส่งข้อมูลไบนารีจากระบบหนึ่งไปยังอีกระบบหนึ่งอาจมีการเพิ่มสัญญาณรบกวนด้วย ด้วยเหตุนี้อาจมีข้อผิดพลาดในข้อมูลที่ได้รับจากระบบอื่น
นั่นหมายความว่าบิต 0 อาจเปลี่ยนเป็น 1 หรือบิต 1 อาจเปลี่ยนเป็น 0 เราไม่สามารถหลีกเลี่ยงการรบกวนของสัญญาณรบกวนได้ แต่เราสามารถเรียกคืนข้อมูลเดิมได้ก่อนโดยการตรวจสอบว่ามีข้อผิดพลาดหรือไม่จากนั้นจึงแก้ไขข้อผิดพลาดเหล่านั้น เพื่อจุดประสงค์นี้เราสามารถใช้รหัสต่อไปนี้
- รหัสตรวจจับข้อผิดพลาด
- รหัสแก้ไขข้อผิดพลาด
Error detection codes- ใช้เพื่อตรวจจับข้อผิดพลาดที่มีอยู่ในข้อมูลที่ได้รับ (สตรีมบิต) รหัสเหล่านี้มีบิตซึ่งรวมอยู่ (ต่อท้าย) ในสตรีมบิตดั้งเดิม รหัสเหล่านี้ตรวจพบข้อผิดพลาดหากเกิดขึ้นระหว่างการส่งข้อมูลต้นฉบับ (สตรีมบิต)Example - รหัส Parity, รหัส Hamming
Error correction codes- ใช้เพื่อแก้ไขข้อผิดพลาดที่มีอยู่ในข้อมูลที่ได้รับ (สตรีมบิต) เพื่อที่เราจะได้รับข้อมูลต้นฉบับ รหัสแก้ไขข้อผิดพลาดยังใช้กลยุทธ์การตรวจหารหัสข้อผิดพลาดที่คล้ายคลึงกันExample - รหัส Hamming
ดังนั้นในการตรวจจับและแก้ไขข้อผิดพลาดบิตเพิ่มเติมจะถูกผนวกเข้ากับบิตข้อมูลในขณะที่ส่งข้อมูล
รหัสพาริตี
ง่ายต่อการรวม (ต่อท้าย) บิตพาริตีหนึ่งบิตไว้ทางด้านซ้ายของ MSB หรือทางด้านขวาของ LSB ของสตรีมบิตดั้งเดิม รหัสพาริตีมีสองประเภท ได้แก่ รหัสพาริตีและรหัสพาริตีแบบคี่ตามประเภทของพาริตีที่เลือก
แม้แต่ Parity Code
ค่าของบิตพาริตีควรเป็นศูนย์หากมีจำนวนคู่อยู่ในรหัสไบนารี มิฉะนั้นก็ควรเป็นอย่างใดอย่างหนึ่ง ดังนั้นจำนวนคนที่มีอยู่even parity code. แม้แต่รหัสพาริตียังมีบิตข้อมูลและแม้แต่บิตพาริตี
ตารางต่อไปนี้แสดงไฟล์ even parity codesสอดคล้องกับรหัสไบนารี 3 บิตแต่ละรายการ ที่นี่บิตพาริตีรวมอยู่ทางด้านขวาของ LSB ของรหัสไบนารี
| รหัสไบนารี | แม้แต่ Parity bit | แม้แต่ Parity Code |
|---|---|---|
| 000 | 0 | 0000 |
| 001 | 1 | 0011 |
| 010 | 1 | 0101 |
| 011 | 0 | 0110 |
| 100 | 1 | 1001 |
| 101 | 0 | 1010 |
| 110 | 0 | 1100 |
| 111 | 1 | 1111 |
ที่นี่จำนวนบิตที่มีอยู่ในรหัสพาริตีคู่คือ 4 ดังนั้นจำนวนคู่ที่เป็นไปได้ในรหัสพาริตีเหล่านี้คือ 0, 2 และ 4
หากระบบอื่นได้รับรหัสพาริตีที่เป็นเลขคู่เหล่านี้แสดงว่าข้อมูลที่ได้รับไม่มีข้อผิดพลาด บิตอื่น ๆ ที่ไม่ใช่บิตพาริตีจะเหมือนกับของรหัสไบนารี
หากระบบอื่นได้รับรหัสอื่นที่ไม่ใช่เลขคู่ก็จะมีข้อผิดพลาดในข้อมูลที่ได้รับ ในกรณีนี้เราไม่สามารถคาดเดารหัสไบนารีเดิมได้เนื่องจากเราไม่ทราบตำแหน่งบิตของข้อผิดพลาด
ดังนั้นแม้แต่พาริตีบิตก็มีประโยชน์สำหรับการตรวจหาข้อผิดพลาดในรหัสพาริตีที่ได้รับเท่านั้น แต่ไม่เพียงพอที่จะแก้ไขข้อผิดพลาด
รหัสพาริตีแปลก ๆ
ค่าของบิตพาริตีคี่ควรเป็นศูนย์หากมีจำนวนคี่อยู่ในรหัสไบนารี มิฉะนั้นก็ควรเป็นอย่างใดอย่างหนึ่ง ดังนั้นจึงมีคนจำนวนคี่อยู่ในodd parity code. รหัสพาริตีคี่ประกอบด้วยบิตข้อมูลและบิตพาริตีคี่
ตารางต่อไปนี้แสดงไฟล์ odd parity codesสอดคล้องกับรหัสไบนารี 3 บิตแต่ละรายการ ที่นี่บิตพาริตีแปลก ๆ จะรวมอยู่ทางด้านขวาของ LSB ของรหัสไบนารี
| รหัสไบนารี | บิต Parity แปลก ๆ | รหัสพาริตีแปลก ๆ |
|---|---|---|
| 000 | 1 | 0001 |
| 001 | 0 | 0010 |
| 010 | 0 | 0100 |
| 011 | 1 | 0111 |
| 100 | 0 | 1,000 |
| 101 | 1 | 1011 |
| 110 | 1 | 1101 |
| 111 | 0 | 1110 |
ที่นี่จำนวนบิตที่มีอยู่ในรหัสพาริตีคี่คือ 4 ดังนั้นจำนวนคี่ที่เป็นไปได้ในรหัสพาริตีคี่เหล่านี้คือ 1 & 3
หากระบบอื่นได้รับรหัสพาริตีแปลก ๆ เหล่านี้แสดงว่าไม่มีข้อผิดพลาดในข้อมูลที่ได้รับ บิตอื่นที่ไม่ใช่บิตพาริตีคี่จะเหมือนกับของรหัสไบนารี
หากระบบอื่นได้รับรหัสพาริตีอื่นที่ไม่ใช่คี่แสดงว่ามีข้อผิดพลาดในข้อมูลที่ได้รับ ในกรณีนี้เราไม่สามารถคาดเดารหัสไบนารีเดิมได้เนื่องจากเราไม่ทราบตำแหน่งบิตของข้อผิดพลาด
ดังนั้นบิตพาริตีคี่จึงมีประโยชน์สำหรับการตรวจจับข้อผิดพลาดในรหัสพาริตีที่ได้รับเท่านั้น แต่ไม่เพียงพอที่จะแก้ไขข้อผิดพลาด
รหัส Hamming
โค้ด Hamming มีประโยชน์สำหรับทั้งการตรวจจับและแก้ไขข้อผิดพลาดที่มีอยู่ในข้อมูลที่ได้รับ รหัสนี้ใช้พาริตีบิตหลายตัวและเราต้องวางพาริตีบิตเหล่านี้ในตำแหน่งของพาวเวอร์ 2
minimum value of 'k' ซึ่งความสัมพันธ์ต่อไปนี้ถูกต้อง (ถูกต้อง) คืออะไรนอกจากจำนวนพาริตีบิตที่ต้องการ
$$ 2 ^ k \ geq n + k + 1 $$
ที่ไหน
'n' คือจำนวนบิตในรหัสไบนารี (ข้อมูล)
'k' คือจำนวนพาริตีบิต
ดังนั้นจำนวนบิตในโค้ด Hamming จึงเท่ากับ n + k
ปล่อยให้ Hamming codeคือ $ b_ {n + k} b_ {n + k-1} ..... b_ {3} b_ {2} b_ {1} $ & parity bits $ p_ {k}, p_ {k-1}, .... p_ {1} $. เราสามารถวางพาริตีบิต 'k' ในพาวเวอร์ 2 ตำแหน่งเท่านั้น ในตำแหน่งบิตที่เหลือเราสามารถวางรหัสไบนารี 'n' บิตได้
ตามข้อกำหนดเราสามารถใช้ความเท่าเทียมกันหรือความเสมอภาคคี่ในขณะที่สร้างรหัส Hamming ได้ แต่ควรใช้เทคนิคพาริตีเดียวกันเพื่อค้นหาว่ามีข้อผิดพลาดในข้อมูลที่ได้รับหรือไม่
ทำตามขั้นตอนนี้เพื่อค้นหา parity bits.
ค้นหาค่าของ p1ขึ้นอยู่กับจำนวนของตำแหน่งที่อยู่ในตำแหน่งบิต b 3 , b 5 , b 7และอื่น ๆ ทั้งหมดเหล่านี้บิตตำแหน่ง (ต่อท้าย) ในไบนารีเทียบเท่าของพวกเขามี '1' ในค่าสถานที่ของ 2 0
ค้นหาค่าของ p2ขึ้นอยู่กับจำนวนของตำแหน่งที่อยู่ในตำแหน่งบิต b 3 , b 6 , b 7และอื่น ๆ ทั้งหมดเหล่านี้บิตตำแหน่ง (ต่อท้าย) ในไบนารีเทียบเท่าของพวกเขามี '1' ในค่าสถานที่ของ 2 1
ค้นหาค่าของ p3ขึ้นอยู่กับจำนวนของตำแหน่งที่อยู่ในตำแหน่งบิต b 5 , b 6 , b 7และอื่น ๆ ทั้งหมดเหล่านี้บิตตำแหน่ง (ต่อท้าย) ในไบนารีเทียบเท่าของพวกเขามี '1' ในมูลค่าที่ 2 2
ในทำนองเดียวกันให้ค้นหาค่าอื่น ๆ ของพาริตีบิต
ทำตามขั้นตอนนี้เพื่อค้นหา check bits.
ค้นหาค่าของ c 1โดยพิจารณาจากจำนวนของตำแหน่งที่อยู่ในตำแหน่งบิต b 1 , b 3 , b 5 , b 7และอื่น ๆ ทั้งหมดเหล่านี้บิตตำแหน่ง (ต่อท้าย) ในไบนารีเทียบเท่าของพวกเขามี '1' ในค่าสถานที่ของ 2 0
ค้นหาค่าของ c 2ตามจำนวนของตำแหน่งที่มีอยู่ในตำแหน่งบิต b 2 , b 3 , b 6 , b 7และอื่น ๆ ทั้งหมดเหล่านี้บิตตำแหน่ง (ต่อท้าย) ในไบนารีเทียบเท่าของพวกเขามี '1' ในค่าสถานที่ของ 2 1
ค้นหาค่าของ c 3โดยพิจารณาจากจำนวนของตำแหน่งที่อยู่ในตำแหน่งบิต b 4 , b 5 , b 6 , b 7และอื่น ๆ ทั้งหมดเหล่านี้บิตตำแหน่ง (ต่อท้าย) ในไบนารีเทียบเท่าของพวกเขามี '1' ในมูลค่าที่ 2 2
ในทำนองเดียวกันให้ค้นหาค่าอื่น ๆ ของบิตตรวจสอบ
การเทียบเท่าทศนิยมของบิตตรวจสอบในข้อมูลที่ได้รับจะให้ค่าของตำแหน่งบิตซึ่งมีข้อผิดพลาดอยู่ เพียงเติมเต็มมูลค่าปัจจุบันในตำแหน่งบิตนั้น ดังนั้นเราจะได้รับรหัสไบนารีเดิมหลังจากลบพาริตีบิต
ตัวอย่าง 1
ให้เราหาโค้ด Hamming สำหรับรหัสไบนารีd 4 d 3 d 2 d 1 = 1000 พิจารณาแม้กระทั่ง Parity bits
จำนวนบิตในรหัสไบนารีที่กำหนดคือ n = 4
เราสามารถค้นหาจำนวนพาริตีบิตที่ต้องการได้โดยใช้ความสัมพันธ์ทางคณิตศาสตร์ต่อไปนี้
$$ 2 ^ k \ geq n + k + 1 $$
แทนที่ n = 4 ในความสัมพันธ์ทางคณิตศาสตร์ข้างต้น
$$ \ Rightarrow 2 ^ k \ geq 4 + k + 1 $$
$$ \ Rightarrow 2 ^ k \ geq 5 + k $$
ค่าต่ำสุดของ k ที่พึงพอใจความสัมพันธ์ข้างต้นเป็น 3 ดังนั้นเราจำเป็นต้องมีความเท่าเทียมกัน 3 P บิต1พี2และพี3 ดังนั้นจำนวนบิตในโค้ด Hamming จะเป็น 7 เนื่องจากมี 4 บิตในรหัสไบนารีและ 3 พาริตีบิต เราต้องวางพาริตีบิตและบิตของรหัสไบนารีไว้ในโค้ด Hamming ดังที่แสดงด้านล่าง
7-bit Hamming code คือ $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = d_ {4} d_ {3} d_ {2} p_ {3} d_ {1 } p_ {2} bp_ {1} $
โดยการแทนที่บิตของรหัสไบนารีโค้ด Hamming จะเป็น $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 100p_ {3} Op_ {2 } p_ {1} $. ตอนนี้ให้เราหาพาริตีบิต
$$ p_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} = 1 \ oplus 0 \ oplus 0 = 1 $$
โดยการแทนพาริตีบิตเหล่านี้ไฟล์ Hamming code จะเป็น $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $
ตัวอย่าง 2
ในตัวอย่างข้างต้นเราได้รับโค้ด Hamming เป็น $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $ ตอนนี้ให้เราค้นหาตำแหน่งข้อผิดพลาดเมื่อรหัสที่ได้รับคือ $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001111 $
ตอนนี้ให้เราค้นหาบิตตรวจสอบ
$$ c_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} \ oplus b_ {1} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} \ oplus b_ {2} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} \ oplus b_ {4} = 1 \ oplus 0 \ oplus 0 \ oplus1 = 0 $$
ค่าทศนิยมของบิตตรวจสอบให้ตำแหน่งของข้อผิดพลาดในโค้ด Hamming ที่ได้รับ
$$ c_ {3} c_ {2} c_ {1} = \ left (011 \ right) _ {2} = \ left (3 \ right) _ {10} $$
ดังนั้นข้อผิดพลาดจึงปรากฏในบิตที่สาม (b 3 ) ของโค้ด Hamming เพียงเติมเต็มค่าที่มีอยู่ในบิตนั้นและลบพาริตีบิตออกเพื่อให้ได้รหัสไบนารีดั้งเดิม