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

เรารู้ว่าบิต 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 เพียงเติมเต็มค่าที่มีอยู่ในบิตนั้นและลบพาริตีบิตออกเพื่อให้ได้รหัสไบนารีดั้งเดิม