เราทำได้!
“จุดประสงค์ของหลักสูตรนี้คือเพื่อเตรียมคุณให้พร้อมสำหรับอนาคตทางเทคนิคของคุณ”
สวัสดีฮับ จำบทความที่ยอดเยี่ยม (+219, 2588 บุ๊กมาร์ก, อ่าน 429 ครั้ง)?
ดังนั้น Hamming (ใช่ ใช่ การตรวจสอบตนเองและการแก้ไขตนเอง ) มีทั้งหมด เขียนตามการบรรยายของเขา เราแปลเพราะผู้ชายพูดความคิดของเขา
นี่คือหนังสือที่ไม่ใช่แค่เกี่ยวกับไอที แต่เป็นหนังสือเกี่ยวกับสไตล์การคิดของคนเจ๋งๆ อย่างไม่น่าเชื่อ “มันไม่ใช่แค่การส่งเสริมการคิดเชิงบวกเท่านั้น มันอธิบายถึงเงื่อนไขที่เพิ่มโอกาสในการทำงานที่ยอดเยี่ยม”
ขอบคุณ Andrey Pakhomov สำหรับการแปล
ทฤษฎีสารสนเทศได้รับการพัฒนาโดย C. E. Shannon ในช่วงปลายทศวรรษที่ 1940 ผู้บริหารของ Bell Labs ยืนกรานว่าเขาเรียกมันว่า "ทฤษฎีการสื่อสาร" เพราะ... นี่เป็นชื่อที่ถูกต้องกว่ามาก ด้วยเหตุผลที่ชัดเจน ชื่อ "ทฤษฎีสารสนเทศ" มีผลกระทบต่อสาธารณะมากกว่ามาก ซึ่งเป็นสาเหตุที่แชนนอนเลือกชื่อนี้ และเป็นชื่อที่เรารู้จักจนถึงทุกวันนี้ ชื่อนี้บ่งบอกว่าทฤษฎีเกี่ยวข้องกับข้อมูล ซึ่งเป็นสิ่งสำคัญเมื่อเราก้าวลึกเข้าไปในยุคข้อมูลข่าวสาร ในบทนี้ ผมจะกล่าวถึงข้อสรุปหลักหลายประการจากทฤษฎีนี้ โดยจะให้หลักฐานที่ไม่เข้มงวด แต่ให้หลักฐานตามสัญชาตญาณของบทบัญญัติบางข้อของทฤษฎีนี้ เพื่อให้คุณเข้าใจว่าจริงๆ แล้ว "ทฤษฎีสารสนเทศ" คืออะไร คุณสามารถนำไปใช้ได้ที่ไหน และที่ไหนไม่
ก่อนอื่น “ข้อมูล” คืออะไร? แชนนอนเปรียบเสมือนข้อมูลกับความไม่แน่นอน เขาเลือกลอการิทึมลบของความน่าจะเป็นของเหตุการณ์เป็นการวัดเชิงปริมาณของข้อมูลที่คุณได้รับเมื่อมีเหตุการณ์ที่มีความน่าจะเป็น p เกิดขึ้น ตัวอย่างเช่น ถ้าฉันบอกคุณว่าสภาพอากาศในลอสแอนเจลิสมีหมอกหนา ค่า p ก็ใกล้กับ 1 ซึ่งไม่ได้ให้ข้อมูลอะไรมากนัก แต่ถ้าบอกว่าฝนตกที่มอนเทอเรย์ในเดือนมิถุนายน ข้อความจะมีความไม่แน่นอนและจะมีข้อมูลเพิ่มเติม เหตุการณ์ที่เชื่อถือได้ไม่มีข้อมูลใดๆ เนื่องจากบันทึก 1 = 0
ลองดูรายละเอียดเพิ่มเติมนี้ แชนนอนเชื่อว่าการวัดข้อมูลเชิงปริมาณควรเป็นฟังก์ชันต่อเนื่องของความน่าจะเป็นของเหตุการณ์ p และสำหรับเหตุการณ์อิสระ ควรเป็นส่วนเสริม - จำนวนข้อมูลที่ได้รับอันเป็นผลมาจากการเกิดเหตุการณ์อิสระสองเหตุการณ์ควรเท่ากับ จำนวนข้อมูลที่ได้รับอันเป็นผลมาจากการเกิดขึ้นของกิจกรรมร่วมกัน ตัวอย่างเช่น ผลลัพธ์ของการทอยลูกเต๋าและการทอยเหรียญ มักจะถือเป็นเหตุการณ์ที่เป็นอิสระ ให้เราแปลข้อความข้างต้นเป็นภาษาคณิตศาสตร์ ถ้า I (p) คือจำนวนข้อมูลที่มีอยู่ในเหตุการณ์ที่มีความน่าจะเป็น p ดังนั้นสำหรับเหตุการณ์ร่วมที่ประกอบด้วยเหตุการณ์อิสระสองเหตุการณ์ x ที่มีความน่าจะเป็น p1 และ y ที่มีความน่าจะเป็น p2 ที่เราได้รับ
(x และ y เป็นเหตุการณ์อิสระ)
นี่คือสมการโคชีเชิงฟังก์ชัน ซึ่งเป็นจริงสำหรับ p1 และ p2 ทั้งหมด ในการแก้สมการเชิงฟังก์ชันนี้ ให้สมมุติว่า
พี1 = พี2 = พี
สิ่งนี้ให้
ถ้า p1 = p2 และ p2 = p แล้ว
ฯลฯ การขยายกระบวนการนี้โดยใช้วิธีมาตรฐานสำหรับเลขชี้กำลัง สำหรับจำนวนตรรกยะทั้งหมด m/n ต่อไปนี้จะเป็นจริง
จากความต่อเนื่องที่สมมติของการวัดข้อมูล ฟังก์ชันลอการิทึมเป็นเพียงคำตอบต่อเนื่องเดียวของสมการคอชีเชิงฟังก์ชัน
ในทฤษฎีสารสนเทศ เป็นเรื่องปกติที่จะถือว่าฐานลอการิทึมเป็น 2 ดังนั้นตัวเลือกไบนารี่จึงมีข้อมูลเพียง 1 บิตเท่านั้น ดังนั้นข้อมูลจึงวัดจากสูตร
เรามาหยุดและทำความเข้าใจกับสิ่งที่เกิดขึ้นข้างต้นกันดีกว่า ก่อนอื่น เราไม่ได้กำหนดแนวคิดของ "ข้อมูล" เราเพียงแต่กำหนดสูตรสำหรับการวัดเชิงปริมาณ
ประการที่สอง มาตรการนี้ขึ้นอยู่กับความไม่แน่นอน และแม้ว่าจะเหมาะสมตามสมควรสำหรับเครื่องจักร เช่น ระบบโทรศัพท์ วิทยุ โทรทัศน์ คอมพิวเตอร์ ฯลฯ แต่ไม่ได้สะท้อนถึงทัศนคติปกติของมนุษย์ต่อข้อมูล
ประการที่สาม นี่เป็นการวัดแบบสัมพันธ์ ขึ้นอยู่กับสถานะปัจจุบันของความรู้ของคุณ หากคุณดูกระแส “ตัวเลขสุ่ม” จากเครื่องสร้างตัวเลขสุ่ม คุณจะถือว่าตัวเลขถัดไปแต่ละตัวมีความไม่แน่นอน แต่ถ้าคุณรู้สูตรการคำนวณ “ตัวเลขสุ่ม” ก็จะทราบตัวเลขถัดไป ดังนั้นจึงไม่ มีข้อมูล
ดังนั้นคำจำกัดความของข้อมูลของแชนนอนจึงเหมาะสมกับเครื่องจักรในหลายกรณี แต่ดูเหมือนจะไม่เหมาะกับความเข้าใจของมนุษย์ในคำนี้ ด้วยเหตุนี้เองจึงควรเรียก "ทฤษฎีสารสนเทศ" ว่า "ทฤษฎีการสื่อสาร" อย่างไรก็ตาม มันสายเกินไปที่จะเปลี่ยนคำจำกัดความ (ซึ่งทำให้ทฤษฎีได้รับความนิยมในช่วงแรก และยังทำให้ผู้คนคิดว่าทฤษฎีนี้เกี่ยวข้องกับ "ข้อมูล") ดังนั้นเราจึงต้องอยู่กับพวกเขา แต่ในขณะเดียวกันคุณต้อง เข้าใจอย่างชัดเจนว่าคำจำกัดความของข้อมูลของแชนนอนนั้นแตกต่างจากความหมายที่ใช้กันทั่วไปเพียงใด ข้อมูลของแชนนอนเกี่ยวข้องกับบางสิ่งที่แตกต่างไปจากเดิมอย่างสิ้นเชิง กล่าวคือ ความไม่แน่นอน
ต่อไปนี้เป็นสิ่งที่ควรคำนึงถึงเมื่อคุณเสนอคำศัพท์ใดๆ คำจำกัดความที่เสนอ เช่น คำจำกัดความของข้อมูลของแชนนอน สอดคล้องกับแนวคิดเดิมของคุณอย่างไร และมีความแตกต่างอย่างไร แทบจะไม่มีคำใดที่สะท้อนถึงวิสัยทัศน์เกี่ยวกับแนวคิดครั้งก่อนของคุณได้อย่างแน่นอน แต่ท้ายที่สุดแล้ว คำศัพท์ที่ใช้นั้นสะท้อนความหมายของแนวคิด ดังนั้นการทำให้บางสิ่งบางอย่างเป็นทางการผ่านคำจำกัดความที่ชัดเจนมักจะทำให้เกิดอุปสรรค
พิจารณาระบบที่ตัวอักษรประกอบด้วยสัญลักษณ์ q ที่มีความน่าจะเป็น pi ในกรณีนี้ จำนวนข้อมูลโดยเฉลี่ย ในระบบ (ค่าที่คาดหวัง) เท่ากับ:
สิ่งนี้เรียกว่าเอนโทรปีของระบบที่มีการแจกแจงความน่าจะเป็น {pi} เราใช้คำว่า "เอนโทรปี" เนื่องจากรูปแบบทางคณิตศาสตร์เดียวกันปรากฏในอุณหพลศาสตร์และกลศาสตร์ทางสถิติ นี่คือเหตุผลว่าทำไมคำว่า “เอนโทรปี” จึงสร้างบรรยากาศที่มีความสำคัญรอบๆ ตัวมันเอง ซึ่งท้ายที่สุดแล้วก็ไม่สมเหตุสมผล สัญกรณ์ทางคณิตศาสตร์รูปแบบเดียวกันไม่ได้หมายความถึงการตีความสัญลักษณ์แบบเดียวกัน!
เอนโทรปีของการแจกแจงความน่าจะเป็นมีบทบาทสำคัญในทฤษฎีการเข้ารหัส ความไม่เท่าเทียมกันของกิ๊บส์สำหรับการแจกแจงความน่าจะเป็นที่แตกต่างกันสองค่า ไพ และ ฉี เป็นหนึ่งในผลลัพธ์ที่สำคัญของทฤษฎีนี้ เราจึงต้องพิสูจน์สิ่งนั้น
การพิสูจน์จะขึ้นอยู่กับกราฟที่ชัดเจน, รูปที่. 13.I ซึ่งแสดงให้เห็นว่า
และความเท่าเทียมกันจะเกิดขึ้นก็ต่อเมื่อ x = 1 ขอให้เราใช้ความไม่เท่าเทียมกันกับแต่ละเทอมของผลรวมทางด้านซ้าย:
หากตัวอักษรของระบบการสื่อสารประกอบด้วยสัญลักษณ์ q แล้วนำความน่าจะเป็นของการส่งผ่านสัญลักษณ์แต่ละตัว qi = 1/q แล้วแทนที่ q เราจะได้มาจากอสมการของกิ๊บส์
รูปที่ 13.I
ซึ่งหมายความว่าหากความน่าจะเป็นในการส่งสัญลักษณ์ q ทั้งหมดเท่ากันและเท่ากับ - 1 / q เอนโทรปีสูงสุดจะเท่ากับ ln q มิฉะนั้นจะถือว่าความไม่เท่าเทียมกันยังคงอยู่
ในกรณีของโค้ดที่สามารถถอดรหัสได้ไม่ซ้ำกัน เรามีความไม่เท่าเทียมกันของ Kraft
ตอนนี้ถ้าเรานิยามความน่าจะเป็นหลอก
แน่นอนที่ไหน = 1 ซึ่งตามมาจากอสมการของกิ๊บส์
และใช้พีชคณิตเล็กน้อย (จำไว้ว่า K ≤ 1 เพื่อที่เราจะได้ทิ้งเทอมลอการิทึม และอาจทำให้อสมการแข็งแกร่งขึ้นในภายหลัง) เราจะได้
โดยที่ L คือความยาวโค้ดเฉลี่ย
ดังนั้น เอนโทรปีจึงเป็นขอบเขตขั้นต่ำสำหรับโค้ดอักขระต่อสัญลักษณ์ใดๆ ที่มีความยาวโค้ดเวิร์ดเฉลี่ย L นี่คือทฤษฎีบทของแชนนอนสำหรับช่องสัญญาณที่ปราศจากการรบกวน
ตอนนี้ให้พิจารณาทฤษฎีบทหลักเกี่ยวกับข้อจำกัดของระบบการสื่อสารที่ข้อมูลถูกส่งเป็นกระแสของบิตอิสระและสัญญาณรบกวนที่มีอยู่ เป็นที่เข้าใจกันว่าความน่าจะเป็นของการส่งผ่านที่ถูกต้องของหนึ่งบิตคือ P > 1/2 และความน่าจะเป็นที่ค่าบิตจะถูกกลับด้านระหว่างการส่ง (จะเกิดข้อผิดพลาด) เท่ากับ Q = 1 - P เพื่อความสะดวกเรา สมมติว่าข้อผิดพลาดนั้นเป็นอิสระจากกัน และความน่าจะเป็นของข้อผิดพลาดจะเท่ากันสำหรับแต่ละบิตที่ส่ง นั่นคือ มี "สัญญาณรบกวนสีขาว" ในช่องสัญญาณการสื่อสาร
วิธีที่เรามีกระแสข้อมูลยาวของ n บิตที่เข้ารหัสเป็นข้อความเดียวคือส่วนขยาย n มิติของโค้ดหนึ่งบิต เราจะกำหนดค่าของ n ในภายหลัง พิจารณาข้อความที่ประกอบด้วย n บิตเป็นจุดในปริภูมิ n มิติ เนื่องจากเรามีช่องว่าง n มิติ - และเพื่อความง่าย เราจะถือว่าแต่ละข้อความมีความน่าจะเป็นที่จะเกิดขึ้นเท่ากัน - มีข้อความที่เป็นไปได้ M (M จะถูกกำหนดในภายหลังด้วย) ดังนั้นความน่าจะเป็นของข้อความใดๆ ที่ส่งคือ
(ผู้ส่ง)
กำหนดการ 13.II
ต่อไปให้พิจารณาแนวคิดเรื่องความจุของช่องสัญญาณ ความจุของช่องสัญญาณหมายถึงจำนวนข้อมูลสูงสุดที่สามารถส่งผ่านช่องทางการสื่อสารได้อย่างน่าเชื่อถือ โดยคำนึงถึงการใช้การเข้ารหัสที่มีประสิทธิภาพสูงสุด โดยไม่ต้องลงรายละเอียด ไม่มีข้อโต้แย้งว่าข้อมูลสามารถส่งผ่านช่องทางการสื่อสารได้มากกว่าความสามารถ สิ่งนี้สามารถพิสูจน์ได้สำหรับช่องสัญญาณไบนารีแบบสมมาตร (ซึ่งเราใช้ในกรณีของเรา) ความจุของช่องสัญญาณเมื่อส่งบิตจะถูกระบุเป็น
โดยที่เมื่อก่อน P คือความน่าจะเป็นที่จะไม่มีข้อผิดพลาดในบิตที่ส่งใดๆ เมื่อส่งบิตอิสระ ความจุของช่องสัญญาณจะได้รับจาก
หากเราอยู่ใกล้ความจุของช่องสัญญาณ เราจะต้องส่งข้อมูลจำนวนเกือบเท่านี้สำหรับแต่ละสัญลักษณ์ ai, i = 1, ..., M โดยพิจารณาว่าความน่าจะเป็นที่จะเกิดขึ้นของสัญลักษณ์ ai แต่ละอันคือ 1 / M เราได้รับ
เมื่อเราส่งข้อความ M ใด ๆ ที่น่าจะเป็นไปได้เท่ากันเราก็มี
เมื่อส่ง n บิต เราคาดว่าข้อผิดพลาด nQ จะเกิดขึ้น ในทางปฏิบัติ สำหรับข้อความที่ประกอบด้วย n บิต เราจะมีข้อผิดพลาด nQ โดยประมาณในข้อความที่ได้รับ สำหรับ n ขนาดใหญ่ การแปรผันแบบสัมพัทธ์ (รูปแบบ = ความกว้างของการแจกแจง )
การกระจายจำนวนข้อผิดพลาดจะแคบลงเรื่อยๆ เมื่อ n เพิ่มขึ้น
ดังนั้น จากฝั่งตัวส่งสัญญาณ ฉันจึงนำข้อความ ai มาส่งและวาดทรงกลมรอบๆ โดยมีรัศมี
ซึ่งมากกว่าจำนวนข้อผิดพลาด Q ที่คาดไว้เล็กน้อยด้วยจำนวนเท่ากับ e2 (รูปที่ 13.II) ถ้า n มีขนาดใหญ่พอ ก็มีความน่าจะเป็นเล็กน้อยที่จุดข้อความ bj จะปรากฏที่ฝั่งผู้รับซึ่งขยายออกไปเลยทรงกลมนี้ ลองร่างสถานการณ์ตามที่ฉันเห็นจากมุมมองของเครื่องส่งสัญญาณ: เรามีรัศมีใด ๆ จากข้อความที่ส่ง ai ถึงข้อความที่ได้รับ bj โดยมีความน่าจะเป็นของข้อผิดพลาดเท่ากับ (หรือเกือบเท่ากัน) กับการแจกแจงแบบปกติถึงค่าสูงสุด ของเอ็นคิว สำหรับ e2 ใดๆ ที่กำหนด มี n มากจนความน่าจะเป็นที่จุดผลลัพธ์ bj อยู่นอกทรงกลมของฉันจะน้อยเท่าที่คุณต้องการ
ตอนนี้เรามาดูสถานการณ์เดียวกันจากฝั่งของคุณ (รูปที่ 13.III) ที่ฝั่งผู้รับจะมีทรงกลม S(r) ที่มีรัศมี r เท่ากันรอบๆ จุดที่ได้รับ bj ในปริภูมิ n มิติ เช่นว่าถ้าข้อความที่ได้รับ bj อยู่ในทรงกลมของฉัน ข้อความ ai ที่ส่งโดยฉันก็จะอยู่ภายในทรงกลมของคุณ ทรงกลม
จะเกิดข้อผิดพลาดได้อย่างไร? ข้อผิดพลาดอาจเกิดขึ้นในกรณีที่อธิบายไว้ในตารางด้านล่าง:
รูปที่ 13.III
ที่นี่เราจะเห็นว่าหากในทรงกลมที่สร้างขึ้นรอบจุดที่ได้รับ มีอย่างน้อยหนึ่งจุดที่สอดคล้องกับข้อความที่ไม่ได้เข้ารหัสที่เป็นไปได้ แสดงว่าเกิดข้อผิดพลาดระหว่างการส่ง เนื่องจากคุณไม่สามารถระบุได้ว่าข้อความใดที่ถูกส่งไป ข้อความที่ส่งนั้นปราศจากข้อผิดพลาดเฉพาะในกรณีที่จุดที่สอดคล้องกับข้อความนั้นอยู่ในทรงกลม และไม่มีจุดอื่นที่เป็นไปได้ในโค้ดที่ให้มาซึ่งอยู่ในทรงกลมเดียวกัน
เรามีสมการทางคณิตศาสตร์สำหรับความน่าจะเป็นของข้อผิดพลาด Pe หากมีการส่งข้อความ ai
เราสามารถโยนตัวประกอบแรกในเทอมที่สองทิ้งไป โดยเอามันเป็น 1 เราก็เลยได้อสมการ
เป็นที่ชัดเจนว่า
ด้วยเหตุนี้
สมัครใหม่กับภาคเรียนสุดท้ายทางด้านขวา
เมื่อมีขนาดใหญ่พอ เทอมแรกก็สามารถมีขนาดเล็กได้ตามต้องการ โดยน้อยกว่าจำนวน d บางตัว ดังนั้นเราจึงมี
ตอนนี้เรามาดูกันว่าเราจะสร้างโค้ดทดแทนอย่างง่าย ๆ เพื่อเข้ารหัสข้อความ M ที่ประกอบด้วย n บิตได้อย่างไร เนื่องจากไม่รู้ว่าจะสร้างโค้ดได้อย่างไร (ยังไม่มีการคิดค้นโค้ดแก้ไขข้อผิดพลาด) แชนนอนจึงเลือกการเข้ารหัสแบบสุ่ม พลิกเหรียญสำหรับแต่ละ n บิตในข้อความ และทำซ้ำขั้นตอนสำหรับข้อความ M โดยรวมแล้วจำเป็นต้องทำการพลิกเหรียญ nM ดังนั้นจึงเป็นไปได้
พจนานุกรมรหัสที่มีความน่าจะเป็นเท่ากัน ½nM แน่นอนว่ากระบวนการสุ่มในการสร้าง Codebook หมายความว่ามีความเป็นไปได้ที่จะเกิดรายการซ้ำ รวมถึงจุดโค้ดที่จะอยู่ใกล้กันและเป็นสาเหตุของข้อผิดพลาดที่อาจเกิดขึ้น เราต้องพิสูจน์ว่าถ้าสิ่งนี้ไม่เกิดขึ้นด้วยความน่าจะเป็นที่มากกว่าระดับความผิดพลาดเล็กๆ น้อยๆ ใดๆ ที่เลือกไว้ แล้วค่า n ที่กำหนดก็มากเพียงพอ
จุดสำคัญคือแชนนอนเฉลี่ยรหัสหนังสือที่เป็นไปได้ทั้งหมดเพื่อค้นหาข้อผิดพลาดโดยเฉลี่ย! เราจะใช้สัญลักษณ์ Av[.] เพื่อแสดงค่าเฉลี่ยของชุดโค้ดบุ๊คแบบสุ่มที่เป็นไปได้ทั้งหมด แน่นอนว่าการหาค่าเฉลี่ยเหนือค่าคงที่ d จะให้ค่าคงที่ เนื่องจากการหาค่าเฉลี่ยแต่ละเทอมจะเหมือนกับเทอมอื่นๆ ในผลรวม
ซึ่งสามารถเพิ่มขึ้นได้ (M–1 ไปที่ M)
สำหรับข้อความใดๆ เมื่อหาค่าเฉลี่ยจาก Codebook ทั้งหมด การเข้ารหัสจะทำงานผ่านค่าที่เป็นไปได้ทั้งหมด ดังนั้นความน่าจะเป็นโดยเฉลี่ยที่จุดหนึ่งอยู่ในทรงกลมคืออัตราส่วนของปริมาตรของทรงกลมต่อปริมาตรรวมของพื้นที่ ปริมาตรของทรงกลมคือ
โดยที่ s=Q+e2 <1/2 และ ns ต้องเป็นจำนวนเต็ม
เทอมสุดท้ายทางขวาจะใหญ่ที่สุดในผลรวมนี้ ขั้นแรก เรามาประมาณค่าของมันโดยใช้สูตรสเตอร์ลิงสำหรับแฟกทอเรียล จากนั้น เราจะดูค่าสัมประสิทธิ์ที่ลดลงของคำที่อยู่ตรงหน้า โปรดทราบว่าค่าสัมประสิทธิ์นี้จะเพิ่มขึ้นเมื่อเราเลื่อนไปทางซ้าย และดังนั้นเราจึงสามารถ: (1) จำกัดค่าของผลรวมให้อยู่ที่ผลรวมของความก้าวหน้าทางเรขาคณิตด้วย ค่าสัมประสิทธิ์เริ่มต้นนี้ (2) ขยายความก้าวหน้าทางเรขาคณิตจากเทอม ns ไปเป็นจำนวนอนันต์ของเทอม (3) คำนวณผลรวมของความก้าวหน้าทางเรขาคณิตอนันต์ (พีชคณิตมาตรฐาน ไม่มีนัยสำคัญ) และสุดท้ายได้ค่าจำกัด (สำหรับค่าที่มากเพียงพอ น):
สังเกตว่าเอนโทรปี H(s) ปรากฏในเอกลักษณ์ทวินามอย่างไร โปรดทราบว่าส่วนขยายอนุกรมของ Taylor H(s)=H(Q+e2) ให้ค่าประมาณที่ได้รับโดยคำนึงถึงเฉพาะอนุพันธ์ลำดับแรกเท่านั้นและไม่สนใจอนุพันธ์ตัวอื่นๆ ทั้งหมด ตอนนี้เรามารวบรวมนิพจน์สุดท้าย:
ที่ไหน
สิ่งที่เราต้องทำคือเลือก e2 โดยที่ e3 < e1 แล้วเทอมสุดท้ายจะเล็กตามใจชอบ ตราบใดที่ n มีขนาดใหญ่พอ ด้วยเหตุนี้ ข้อผิดพลาด PE โดยเฉลี่ยจึงสามารถได้รับเพียงเล็กน้อยตามที่ต้องการ โดยความจุของช่องสัญญาณจะใกล้เคียงกับ C โดยพลการ
หากค่าเฉลี่ยของรหัสทั้งหมดมีข้อผิดพลาดเล็กน้อยเพียงพอ จะต้องมีรหัสที่เหมาะสมอย่างน้อยหนึ่งรหัส ดังนั้นจึงมีระบบการเข้ารหัสที่เหมาะสมอย่างน้อยหนึ่งระบบ นี่เป็นผลลัพธ์ที่สำคัญที่แชนนอนได้รับ - "ทฤษฎีบทของแชนนอนสำหรับช่องสัญญาณที่มีเสียงดัง" แม้ว่าควรสังเกตว่าเขาได้พิสูจน์สิ่งนี้ในกรณีทั่วไปมากกว่าช่องสมมาตรไบนารีธรรมดาที่ฉันใช้ สำหรับกรณีทั่วไป การคำนวณทางคณิตศาสตร์มีความซับซ้อนกว่ามาก แต่แนวคิดไม่ได้แตกต่างกันมากนัก ดังนั้นบ่อยครั้งมากที่คุณสามารถเปิดเผยความหมายที่แท้จริงของทฤษฎีบทได้โดยใช้ตัวอย่างของกรณีใดกรณีหนึ่ง
มาวิจารณ์ผลลัพธ์กัน เราพูดซ้ำแล้วซ้ำอีก: “สำหรับ n ที่มีขนาดใหญ่เพียงพอ” แต่ n ใหญ่แค่ไหน? มีขนาดใหญ่มากหากคุณต้องการให้ใกล้กับความจุของช่องสัญญาณและต้องแน่ใจว่าการถ่ายโอนข้อมูลถูกต้อง! จริงๆ แล้วมีขนาดใหญ่มากจนคุณจะต้องรอเป็นเวลานานมากในการสะสมข้อความที่มีบิตเพียงพอที่จะเข้ารหัสในภายหลัง ในกรณีนี้ขนาดของพจนานุกรมรหัสสุ่มจะมีขนาดใหญ่มาก (ท้ายที่สุดแล้วพจนานุกรมดังกล่าวไม่สามารถแสดงในรูปแบบที่สั้นกว่ารายการทั้งหมดของบิต Mn ทั้งหมดได้แม้ว่าข้อเท็จจริงที่ว่า n และ M จะมีขนาดใหญ่มากก็ตาม)!
รหัสแก้ไขข้อผิดพลาดหลีกเลี่ยงการรอข้อความที่ยาวมาก จากนั้นจึงเข้ารหัสและถอดรหัสผ่านสมุดโค้ดขนาดใหญ่มาก เนื่องจากจะหลีกเลี่ยงสมุดโค้ดด้วยตนเองและใช้การคำนวณแบบธรรมดาแทน ตามทฤษฎีง่ายๆ รหัสดังกล่าวมีแนวโน้มที่จะสูญเสียความสามารถในการเข้าใกล้ความจุของช่องสัญญาณและยังคงรักษาอัตราข้อผิดพลาดต่ำ แต่เมื่อรหัสแก้ไขข้อผิดพลาดจำนวนมาก รหัสก็จะทำงานได้ดี กล่าวอีกนัยหนึ่ง หากคุณจัดสรรความจุช่องสัญญาณบางส่วนเพื่อแก้ไขข้อผิดพลาด คุณจะต้องใช้ความสามารถในการแก้ไขข้อผิดพลาดเป็นส่วนใหญ่ กล่าวคือ ต้องแก้ไขข้อผิดพลาดจำนวนมากในแต่ละข้อความที่ส่ง มิฉะนั้น คุณจะสูญเสียความสามารถนี้ไป
ในขณะเดียวกัน ทฤษฎีบทที่พิสูจน์แล้วข้างต้นก็ยังไม่ไร้ความหมาย! มันแสดงให้เห็นว่าระบบการส่งข้อมูลที่มีประสิทธิภาพต้องใช้รูปแบบการเข้ารหัสที่ชาญฉลาดสำหรับสตริงบิตที่ยาวมาก ตัวอย่างคือดาวเทียมที่บินไปไกลกว่าดาวเคราะห์ชั้นนอก ขณะที่พวกเขาเคลื่อนตัวออกจากโลกและดวงอาทิตย์ พวกเขาถูกบังคับให้แก้ไขข้อผิดพลาดในบล็อกข้อมูลมากขึ้นเรื่อยๆ: ดาวเทียมบางดวงใช้แผงโซลาร์เซลล์ซึ่งให้พลังงานประมาณ 5 W ดาวเทียมดวงอื่นใช้แหล่งพลังงานนิวเคลียร์ซึ่งให้พลังงานเท่ากัน พลังงานต่ำของแหล่งจ่ายไฟ จานส่งสัญญาณขนาดเล็ก และจานรับสัญญาณบนโลกที่มีขนาดจำกัด ระยะทางมหาศาลที่สัญญาณต้องเคลื่อนที่ ทั้งหมดนี้ต้องใช้รหัสที่มีการแก้ไขข้อผิดพลาดในระดับสูงเพื่อสร้าง ระบบการสื่อสารที่มีประสิทธิภาพ
กลับไปที่ปริภูมิ n มิติที่เราใช้ในการพิสูจน์ข้างต้นกัน ในการพูดคุยกัน เราได้แสดงให้เห็นว่าปริมาตรเกือบทั้งหมดของทรงกลมกระจุกตัวอยู่ที่พื้นผิวด้านนอก ดังนั้นจึงเกือบจะแน่ใจว่าสัญญาณที่ส่งไปนั้นจะอยู่ใกล้กับพื้นผิวของทรงกลมที่สร้างขึ้นรอบๆ สัญญาณที่ได้รับ แม้ว่าจะมีค่าค่อนข้างมาก รัศมีเล็กๆ ของทรงกลมดังกล่าว ดังนั้นจึงไม่น่าแปลกใจที่สัญญาณที่ได้รับหลังจากแก้ไขข้อผิดพลาดจำนวนมากโดยพลการ nQ กลับกลายเป็นว่าใกล้กับสัญญาณโดยไม่มีข้อผิดพลาดโดยพลการ ความสามารถในการเชื่อมโยงที่เรากล่าวถึงก่อนหน้านี้เป็นกุญแจสำคัญในการทำความเข้าใจปรากฏการณ์นี้ โปรดทราบว่าทรงกลมที่คล้ายกันซึ่งสร้างขึ้นสำหรับรหัส Hamming ที่แก้ไขข้อผิดพลาดจะไม่ทับซ้อนกัน มิติที่เกือบตั้งฉากจำนวนมากในปริภูมิ n มิติแสดงให้เห็นว่าเหตุใดเราจึงสามารถใส่ทรงกลม M ในอวกาศโดยมีการทับซ้อนกันเพียงเล็กน้อย หากเราอนุญาตให้มีการทับซ้อนกันเล็กๆ น้อยๆ โดยพลการ ซึ่งอาจนำไปสู่ข้อผิดพลาดเพียงเล็กน้อยในระหว่างการถอดรหัส เราจะได้รับการวางตำแหน่งทรงกลมที่หนาแน่นในอวกาศ Hamming รับประกันการแก้ไขข้อผิดพลาดในระดับหนึ่ง Shannon - ความน่าจะเป็นของข้อผิดพลาดต่ำ แต่ในขณะเดียวกันก็รักษาปริมาณงานจริงไว้ใกล้กับความจุของช่องทางการสื่อสารโดยพลการ ซึ่งรหัส Hamming ไม่สามารถทำได้
ทฤษฎีสารสนเทศไม่ได้บอกเราถึงวิธีการออกแบบระบบที่มีประสิทธิภาพ แต่ชี้ทางไปสู่ระบบการสื่อสารที่มีประสิทธิภาพ มันเป็นเครื่องมืออันมีค่าสำหรับการสร้างระบบการสื่อสารแบบเครื่องต่อเครื่อง แต่ดังที่ได้กล่าวไว้ข้างต้นว่ามีความเกี่ยวข้องเพียงเล็กน้อยกับวิธีที่มนุษย์สื่อสารกัน ขอบเขตของการถ่ายทอดทางพันธุกรรมก็เหมือนกับระบบการสื่อสารทางเทคนิคนั้นยังไม่เป็นที่ทราบแน่ชัด ดังนั้นจึงยังไม่ชัดเจนว่าทฤษฎีข้อมูลจะนำไปใช้กับยีนได้อย่างไร เราไม่มีทางเลือกอื่นนอกจากต้องพยายาม และหากความสำเร็จแสดงให้เราเห็นถึงธรรมชาติของปรากฏการณ์นี้ ความล้มเหลวก็จะชี้ไปที่ลักษณะที่สำคัญอื่นๆ ของธรรมชาติของข้อมูล
อย่าพูดนอกเรื่องมากเกินไป เราได้เห็นแล้วว่าคำจำกัดความดั้งเดิมทั้งหมด ไม่มากก็น้อย จะต้องแสดงถึงแก่นแท้ของความเชื่อดั้งเดิมของเรา แต่คำจำกัดความเหล่านั้นมีลักษณะที่บิดเบือนไปบ้าง ดังนั้นจึงใช้ไม่ได้ เป็นที่ยอมรับกันโดยทั่วไปว่าท้ายที่สุดแล้ว คำจำกัดความที่เราใช้จะเป็นตัวกำหนดแก่นแท้ แต่สิ่งนี้เพียงบอกเราถึงวิธีการประมวลผลสิ่งต่าง ๆ และไม่ได้สื่อความหมายใด ๆ ให้กับเราเลย วิธีการสมมุติฐานซึ่งได้รับความนิยมอย่างมากในแวดวงคณิตศาสตร์ ทำให้ในทางปฏิบัติไม่เป็นที่ต้องการมากนัก
ตอนนี้เราจะดูตัวอย่างการทดสอบ IQ โดยที่คำจำกัดความเป็นแบบวงกลมตามที่คุณต้องการให้เป็น และผลที่ตามมาคือทำให้เข้าใจผิด มีการสร้างการทดสอบที่ควรวัดความฉลาด จากนั้นจะมีการแก้ไขเพื่อให้สอดคล้องกันมากที่สุด จากนั้นจึงเผยแพร่และปรับเทียบด้วยวิธีการง่ายๆ เพื่อให้ "ความฉลาด" ที่วัดได้ปรากฏว่ามีการกระจายตามปกติ (บนกราฟการปรับเทียบ) คำจำกัดความทั้งหมดจะต้องได้รับการตรวจสอบอีกครั้ง ไม่เพียงแต่เมื่อมีการเสนอครั้งแรกเท่านั้น แต่ยังต้องตรวจสอบในภายหลังอีกด้วย เมื่อนำมาใช้ในการสรุปผล ขอบเขตคำจำกัดความเหมาะสมกับปัญหาที่กำลังแก้ไขมากน้อยเพียงใด คำจำกัดความที่ให้ไว้ในการตั้งค่าเดียวถูกนำมาใช้บ่อยแค่ไหนในการตั้งค่าที่แตกต่างกันออกไป เรื่องนี้เกิดขึ้นค่อนข้างบ่อย! ในมนุษยศาสตร์ซึ่งคุณจะต้องเผชิญในชีวิตอย่างหลีกเลี่ยงไม่ได้สิ่งนี้เกิดขึ้นบ่อยกว่า
ดังนั้น วัตถุประสงค์ประการหนึ่งของการนำเสนอทฤษฎีสารสนเทศนี้ นอกเหนือจากการแสดงให้เห็นถึงประโยชน์ของทฤษฎีข้อมูลแล้ว คือการเตือนคุณถึงอันตรายนี้ หรือเพื่อแสดงให้คุณเห็นอย่างชัดเจนถึงวิธีการใช้มันเพื่อให้ได้ผลลัพธ์ที่ต้องการ เป็นที่ทราบกันมานานแล้วว่าคำจำกัดความเบื้องต้นจะกำหนดสิ่งที่คุณพบในท้ายที่สุดในระดับที่มากกว่าที่คิดไว้มาก คำจำกัดความเบื้องต้นต้องการความสนใจจากคุณเป็นอย่างมาก ไม่เพียงแต่ในสถานการณ์ใหม่เท่านั้น แต่ยังรวมถึงในพื้นที่ที่คุณทำงานมาเป็นเวลานานด้วย สิ่งนี้จะช่วยให้คุณเข้าใจว่าผลลัพธ์ที่ได้นั้นเป็นเรื่องซ้ำซากและไม่ใช่สิ่งที่มีประโยชน์มากน้อยเพียงใด
เรื่องราวอันโด่งดังของ Eddington เล่าถึงผู้คนที่ใช้อวนจับปลาในทะเล หลังจากศึกษาขนาดของปลาที่จับได้ พวกเขาก็กำหนดขนาดปลาขั้นต่ำที่พบในทะเล! ข้อสรุปของพวกเขาขับเคลื่อนโดยเครื่องมือที่ใช้ ไม่ใช่จากความเป็นจริง
จะยังคง ...
ใครต้องการความช่วยเหลือในการแปล เค้าโครง และการตีพิมพ์หนังสือ - เขียนเป็นข้อความส่วนตัวหรืออีเมล [ป้องกันอีเมล]
อย่างไรก็ตาม เรายังได้เปิดตัวการแปลหนังสือเจ๋งๆ อีกเล่มด้วย - )
เรากำลังมองหาโดยเฉพาะ ผู้ที่จะช่วยแปล . (โอนไป 10 นาที 20 คนแรกได้ไปแล้ว)
เนื้อหาหนังสือและบทแปล
- ข้อมูลเบื้องต้นเกี่ยวกับศิลปะแห่งการทำวิทยาศาสตร์และวิศวกรรมศาสตร์: การเรียนรู้ที่จะเรียนรู้ (28 มีนาคม 1995)
- "รากฐานของการปฏิวัติดิจิทัล (ไม่ต่อเนื่อง)" (30 มีนาคม 1995)
- "ประวัติศาสตร์คอมพิวเตอร์ - ฮาร์ดแวร์" (31 มีนาคม 1995)
- "ประวัติศาสตร์คอมพิวเตอร์ - ซอฟต์แวร์" (4 เมษายน 1995)
- "ประวัติศาสตร์คอมพิวเตอร์ - แอปพลิเคชัน" (6 เมษายน 1995)
- "ปัญญาประดิษฐ์ - ตอนที่ 7" (1995 เมษายน XNUMX)
- "ปัญญาประดิษฐ์ - ตอนที่ 11" (1995 เมษายน XNUMX)
- "ปัญญาประดิษฐ์ III" (13 เมษายน 1995)
- "อวกาศ n มิติ" (14 เมษายน 1995)
- "ทฤษฎีการเข้ารหัส - การเป็นตัวแทนของข้อมูลส่วนที่ 18" (1995 เมษายน XNUMX)
- "ทฤษฎีการเข้ารหัส - การเป็นตัวแทนของข้อมูลส่วนที่ 20" (1995 เมษายน XNUMX)
- "รหัสแก้ไขข้อผิดพลาด" (21 เมษายน 1995)
- "ทฤษฎีสารสนเทศ" (25 เมษายน 1995)
- "ตัวกรองดิจิทัล ตอนที่ 27" (1995 เมษายน XNUMX)
- "ตัวกรองดิจิทัล ตอนที่ 28" (1995 เมษายน XNUMX)
- "ตัวกรองดิจิทัล ตอนที่ 2" (1995 พฤษภาคม XNUMX)
- "ตัวกรองดิจิทัล ตอนที่ 4" (1995 พฤษภาคม XNUMX)
- "การจำลองส่วนที่ 5" (1995 พฤษภาคม XNUMX)
- "การจำลองส่วนที่ 9" (1995 พฤษภาคม XNUMX)
- "การจำลองส่วนที่ 11" (1995 พฤษภาคม XNUMX)
- "ไฟเบอร์ออปติก" (12 พ.ค. 1995)
- "การสอนโดยใช้คอมพิวเตอร์ช่วย" (16 พ.ค. 1995)
- "คณิตศาสตร์" (18 พ.ค. 1995)
- "กลศาสตร์ควอนตัม" (19 พ.ค. 1995)
- "ความคิดสร้างสรรค์" (23 พฤษภาคม 1995) การแปล:
- "ผู้เชี่ยวชาญ" (25 พฤษภาคม 1995)
- "ข้อมูลไม่น่าเชื่อถือ" (26 พฤษภาคม 1995)
- "วิศวกรรมระบบ" (30 พฤษภาคม 1995)
- “คุณได้สิ่งที่คุณวัด” (1 มิถุนายน 1995)
- (มิถุนายน 2, 1995) แปลเป็นชิ้นๆ ในเวลา 10 นาที
- Hamming “คุณและงานวิจัยของคุณ” (6 มิถุนายน 1995)
ใครต้องการความช่วยเหลือในการแปล เค้าโครง และการตีพิมพ์หนังสือ - เขียนเป็นข้อความส่วนตัวหรืออีเมล [ป้องกันอีเมล]
ที่มา: will.com