เนื้อหา
- TL; DR (ยาวเกินไปไม่ได้อ่าน)
- Hamming Distance คืออะไร?
- วิธีการคำนวณระยะทาง Hamming
- ทำไม Hamming Distance มีประโยชน์หรือไม่
วันนี้เกือบทุกแง่มุมของชีวิตสมัยใหม่เกี่ยวข้องกับการถ่ายโอนข้อมูลดิจิตอลไม่ว่าจะเป็นระหว่างบุคคลหรือระหว่างเซิร์ฟเวอร์หรือระบบบุคคล เมื่อคุณจัดการบัญชีธนาคารของคุณออนไลน์ให้อัพเดตหน้าโซเชียลมีเดียของคุณหรือแม้แต่เล่นดีวีดีด้วยเครื่องเล่น DVD ที่เชื่อมต่อกับโทรทัศน์ของคุณข้อมูลจะถูกย้ายจากที่หนึ่งไปอีกที่หนึ่งแบบดิจิทัลไม่ว่าจะผ่านสายไฟหรือสัญญาณไร้สาย เพื่อให้ข้อมูลนี้ผ่านจากที่หนึ่งไปยังอีกที่หนึ่งจะต้องมีการถ่ายโอนผ่านรหัสคอมพิวเตอร์ ใน "ภาษา" ข้อมูลนี้จะเคลื่อนย้ายผ่านการรวมกันของ 1s และ 0s หรือที่รู้จักกันในชื่อรหัสไบนารี่ ข้อผิดพลาดในรหัสไบนารีที่ย้ายจากระบบหนึ่งไปยังอีกระบบหนึ่งอาจหมายถึงว่าข้อมูลไม่ได้รับการถ่ายทอดอย่างถูกต้องซึ่งอาจทำให้เกิดปัญหามากมายสำหรับผู้ใช้คอมพิวเตอร์ ระยะทางในการรับส่งข้อมูลเป็นวิธีการทำความเข้าใจว่ารหัสแตกต่างกันอย่างไร ซึ่งสามารถใช้เพื่อแก้ไขข้อผิดพลาด
TL; DR (ยาวเกินไปไม่ได้อ่าน)
ระยะทางของฮามมิ่งหมายถึงจำนวนของจุดที่โค้ดไบนารี่สองบรรทัดแตกต่างกันโดยพิจารณาจากการเพิ่มจำนวนสปอตที่โค้ดสองบรรทัดต่างกัน ตัวอย่างเช่นระยะห่างระหว่าง codewords ทั้งสอง 10101010 และ 01011010 คือสี่: แม้ว่าสิ่งนี้อาจไม่ได้มีความหมายอะไรมากหากไม่มีการแย้งนี่อาจหมายความว่าเมื่อถึงสี่จุดข้อผิดพลาดในโค้ดทำให้ไฟล์เสียงไม่สามารถเล่นได้อย่างถูกต้อง โทรทัศน์แสดงผิดหรือฟังก์ชั่นคอมพิวเตอร์ที่สำคัญถูกตีความผิด
Hamming Distance คืออะไร?
ระยะห่างของ Hamming ของโค้ดสองบรรทัดที่ระบุคือจำนวนคะแนนที่ค่ารหัสไบนารี่ไลน์ต่างกัน (สมมติว่าโค้ดทั้งสองนั้นมีความยาวเท่ากัน) นี่อาจเป็นเรื่องสับสนเล็กน้อยที่จะเข้าใจในตอนแรกดังนั้นให้พิจารณาตัวอย่างง่ายๆนี้: คำหนึ่งจะถูกส่งจากโทรศัพท์ A ไปยังโทรศัพท์ B เมื่อแปลเป็นรหัสไบนารี่แล้วบรรทัดของรหัสที่แทนบนโทรศัพท์ A จะอ่าน "101" และบนบรรทัด B โค้ดจะอ่านว่า "010" เมื่อเปรียบเทียบกับเส้นเหล่านี้คุณจะเห็นว่ามีสัญลักษณ์ที่แตกต่างกันในแต่ละจุดสามจุด นี่อาจเป็นสัญญาณว่าไม่ได้ส่งอย่างถูกต้อง
วิธีการคำนวณระยะทาง Hamming
ในสถานการณ์ง่าย ๆ การคำนวณระยะทาง Hamming นั้นเป็นเรื่องง่าย แต่สิ่งสำคัญที่ต้องจำก็คือระยะทาง Hamming นั้นสามารถคำนวณได้เฉพาะเส้นที่มีความยาวเท่ากัน คุณเพียงแค่เพิ่มจำนวนจุดที่เส้นมีค่าแตกต่างกัน ในตัวอย่างด้านบนระยะ Hamming จะเป็นสามเนื่องจากเส้นมีค่าต่างกันในสามจุด การทำการเปรียบเทียบนี้จะใช้เวลานานมากขึ้นทำให้สายของไบนารีโค้ดยาวขึ้น ลองพิจารณาตัวอย่างที่ยาวขึ้นเล็กน้อยด้วยโค้ดสองบรรทัด: 100110 และ 110011 บรรทัดของโค้ดเหล่านี้มีจุดข้อมูลหกจุด ค่าต่างกันในสามจุดเหล่านั้นดังนั้นระยะทางของแฮมมิงระหว่างสองบรรทัดนี้จึงเท่ากับสาม การคำนวณระยะทาง Hamming พร้อมชุดข้อมูลขนาดใหญ่จะมีความซับซ้อนมากขึ้นและเกี่ยวข้องกับการใช้สมการและฟังก์ชันที่ซับซ้อนเช่น d = min {d (x, y): x, y∈C, x ≠ y}
ทำไม Hamming Distance มีประโยชน์หรือไม่
ระยะทาง Hamming สามารถดูได้โดยพลการ อย่างไรก็ตามมันเป็นการวัดที่สำคัญสำหรับโคเดอร์ ระยะทางในการทำ Hamming สามารถช่วยผู้เขียนโค้ดที่ตรวจจับข้อผิดพลาดและแก้ไขข้อผิดพลาดเหล่านั้นด้วยตนเอง นอกจากนี้ยังสามารถช่วยให้ผู้คนเข้าใจว่ารหัสผิดพลาดง่ายเพียงใด ระยะทางของแฮมมิงนั้นถูกตั้งชื่อตาม Richard Wesley Hamming ซึ่งเป็นผู้พัฒนาการวัดในช่วงปลายทศวรรษที่ 1940 เมื่อเขาทำงานที่ Bell Telephone Laboratories แม้ว่า Hamming มองข้ามการเฉลิมฉลองของนวัตกรรม แต่อุตสาหกรรมเทคโนโลยีก็สังเกตเห็นและใช้มันเพื่อผลที่ยอดเยี่ยมเมื่อแก้ไขปัญหารหัส เกือบ 50 ปีหลังจาก Hamming ค้นพบการวัดเขาได้รับรางวัล Eduard Rheim สำหรับความสำเร็จในด้านเทคโนโลยีโดย Eduard Rheim Foundation ของเยอรมนีในปี 1996 นอกจากนี้ IEEE องค์กรมืออาชีพขนาดใหญ่ในภาคเทคโนโลยียังมอบรางวัลประจำปีของ Richard W. Hamming Medal เพื่อเป็นเกียรติแก่เขา