วิธีการคำนวณระยะทางแฮมมิง

ทุกวันนี้ เกือบทุกแง่มุมของชีวิตสมัยใหม่เกี่ยวข้องกับการถ่ายโอนข้อมูลดิจิทัล ไม่ว่าจะระหว่างบุคคลหรือระหว่างเซิร์ฟเวอร์หรือระบบของแต่ละบุคคล เมื่อคุณจัดการบัญชีธนาคารของคุณทางออนไลน์ อัปเดตหน้าโซเชียลมีเดียของคุณ หรือแม้แต่เล่น DVD โดยเชื่อมต่อกับเครื่องเล่นดีวีดี ไปยังโทรทัศน์ของคุณ ข้อมูลจะย้ายจากที่หนึ่งไปยังอีกที่หนึ่งทางดิจิทัล ไม่ว่าจะผ่านทางสายหรือไร้สาย สัญญาณ. ข้อมูลนี้จะถูกส่งต่อจากที่หนึ่งไปยังอีกที่หนึ่ง จะต้องโอนผ่านรหัสคอมพิวเตอร์ ใน "ภาษา" นี้ ข้อมูลจะเคลื่อนผ่านการรวมกันของ 1 และ 0 เรียกว่าไบนารีโค้ด ข้อผิดพลาดในการย้ายรหัสไบนารีจากระบบหนึ่งไปยังอีกระบบหนึ่งอาจหมายความว่าข้อมูลไม่ได้รับการถ่ายทอดอย่างถูกต้อง ซึ่งอาจทำให้เกิดปัญหามากมายสำหรับผู้ใช้คอมพิวเตอร์ ระยะทางแฮมมิงเป็นวิธีทำความเข้าใจว่ารหัสต่างกันอย่างไร สามารถใช้เพื่อแก้ไขข้อผิดพลาดได้

ทีแอล; DR (ยาวเกินไป; ไม่ได้อ่าน)

ระยะห่างของแฮมมิ่งหมายถึงจำนวนจุดที่โค้ดไบนารีสองบรรทัดต่างกัน โดยพิจารณาจากการเพิ่มจำนวนจุดที่โค้ดสองบรรทัดต่างกัน ตัวอย่างเช่น ระยะห่างระหว่างโค้ดเวิร์ดสองคำ 10101010 และ 01011010 คือสี่: แม้ว่านี่อาจไม่ได้มีความหมายมากนักหากไม่มีบริบท แต่อาจหมายความว่าที่จุดสี่จุด ข้อผิดพลาดในรหัสส่งผลให้ไฟล์เสียงไม่สามารถเล่นได้อย่างถูกต้อง ภาพบนโทรทัศน์แสดงไม่ถูกต้อง หรือการทำงานของคอมพิวเตอร์ที่สำคัญ ตีความผิด

ระยะห่างของโค้ดสองบรรทัดที่กำหนดคือจำนวนจุดที่ค่ารหัสไบนารีของบรรทัดต่างกัน (สมมติว่าโค้ดสองบรรทัดมีความยาวเท่ากัน) การทำความเข้าใจครั้งแรกอาจทำให้สับสนเล็กน้อย ลองพิจารณาตัวอย่างง่ายๆ นี้: ข้อความตัวอักษรเดียวถูกส่งจากโทรศัพท์ A ไปยังโทรศัพท์ B เมื่อแปลเป็นรหัสไบนารี บรรทัดของรหัสที่แสดงข้อความบนโทรศัพท์ A จะอ่านว่า "101" และบนโทรศัพท์ B บรรทัดของรหัสอ่าน "010" เมื่อเปรียบเทียบเส้นเหล่านี้ คุณจะเห็นว่ามีสัญลักษณ์ต่างกันในแต่ละจุดทั้งสาม นี่อาจเป็นสัญญาณว่าส่งข้อความไม่ถูกต้อง

ในสถานการณ์ง่ายๆ การคำนวณระยะทางของแฮมมิงเป็นเรื่องง่าย แม้ว่าสิ่งสำคัญที่ต้องจำไว้คือระยะทางของแฮมมิงสามารถคำนวณได้สำหรับเส้นที่มีความยาวเท่ากันเท่านั้น คุณเพียงแค่บวกจำนวนจุดที่เส้นมีค่าต่างกัน ในตัวอย่างข้างต้น ระยะ Hamming จะเป็นสาม เนื่องจากเส้นมีค่าต่างกันในสามจุด การเปรียบเทียบนี้จะใช้เวลานานขึ้น ยิ่งบรรทัดของรหัสไบนารียาวขึ้นเท่านั้น ลองพิจารณาตัวอย่างที่ยาวกว่าเล็กน้อยด้วยโค้ดสองบรรทัด: 100110 และ 110011 โค้ดเหล่านี้มีจุดข้อมูลหกจุด ค่าจะต่างกันในสามจุดนั้น ดังนั้นระยะห่างระหว่างสองเส้นนี้จึงเป็นสามด้วย การคำนวณระยะแฮมมิงด้วยชุดข้อมูลจำนวนมากขึ้นจะซับซ้อนยิ่งขึ้น และต้องใช้สมการและฟังก์ชันที่ซับซ้อน เช่น d=min {d (x, y):x, y∈C, x≠y}

ระยะห่างของ Hamming อาจดูเหมือนไม่เป็นไปตามบริบท อย่างไรก็ตาม เป็นการวัดที่สำคัญสำหรับผู้เขียนโค้ด ระยะการกระแทกสามารถช่วยให้ผู้เขียนโค้ดเขียนโค้ดที่ตรวจจับข้อผิดพลาดและแก้ไขข้อผิดพลาดเหล่านั้นได้ด้วยตัวเอง นอกจากนี้ยังช่วยให้ผู้คนเข้าใจว่าโค้ดมีแนวโน้มที่จะเกิดข้อผิดพลาดอย่างไร ระยะทางแฮมมิงได้รับการตั้งชื่อตามริชาร์ด เวสลีย์ แฮมมิง ผู้พัฒนาการวัดนี้ในช่วงปลายทศวรรษ 1940 เมื่อเขาทำงานที่ Bell Telephone Laboratories แม้ว่าแฮมมิงจะมองข้ามการเฉลิมฉลองของนวัตกรรม แต่อุตสาหกรรมเทคโนโลยีก็สังเกตเห็นและใช้มันเพื่อผลลัพธ์ที่ยอดเยี่ยมในการแก้ไขปัญหาโค้ด เกือบ 50 ปีหลังจากที่ Hamming ค้นพบการวัดนี้ เขาได้รับรางวัล Eduard Rheim Award for Achievement in Technology จากมูลนิธิ Eduard Rheim แห่งเยอรมนีในปี 1996 นอกจากนี้ I.E.E.E. ซึ่งเป็นองค์กรวิชาชีพขนาดใหญ่ในภาคเทคโนโลยี ได้มอบงานประจำปีให้กับ Richard W. เหรียญ Hamming เพื่อเป็นเกียรติแก่เขา