ทฤษฎีการเข้ารหัสที่จำเป็น [pdf]

 (cse.buffalo.edu)
16 คะแนน โดย GN⁺ 2025-08-31 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • หนังสือเล่มนี้สรุป แนวคิดแกนหลักของทฤษฎีการเข้ารหัสและพัฒนาการสมัยใหม่ ไว้อย่างครอบคลุม
  • ครอบคลุมหลักการพื้นฐานของ รหัสแก้ไขข้อผิดพลาด โครงสร้างและข้อจำกัดของรหัสหลากหลายแบบ ตลอดจนการประยุกต์ใช้จริง
  • อธิบายรหัสที่ถูกใช้อย่างแพร่หลายในโลกจริงอย่างเข้มข้น ทั้ง ทฤษฎีของ Shannon และรหัส Hamming รวมถึง Reed-Solomon
  • นำเสนอกรณีการใช้งานในระบบไอทีสมัยใหม่อย่างเป็นระบบ เช่น แฮช การตรวจแบบกลุ่ม และการปกป้องข้อมูลชีวมิติ
  • มีทั้งภาคผนวก แบบฝึกหัด และบรรณานุกรม จึงถูกจัดทำให้เป็น หนังสืออ้างอิงที่มีประสิทธิภาพสำหรับทั้งผู้เรียนและผู้ปฏิบัติงาน

คำนำ

  • หนังสือเล่มนี้อ้างอิงจากบันทึกการบรรยายวิชาทฤษฎีการเข้ารหัสของ Venkatesan Guruswami, Atri Rudra และ Madhu Sudan
  • เนื้อหาอิงจากการสอนที่ University of Washington, CMU, University at Buffalo SUNY, Harvard, MIT และที่อื่น ๆ
  • ได้รับการสนับสนุนจาก NSF CAREER grant CCF-0844796
  • มุมมองและผลลัพธ์ของผู้เขียนไม่ได้หมายถึงจุดยืนอย่างเป็นทางการของ NSF
  • ใช้งานได้ภายใต้สัญญาอนุญาต Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License

สรุปสารบัญ

บทที่ 1: คำถามพื้นฐาน

  • เป้าหมายของทฤษฎีการเข้ารหัส นิยามพื้นฐาน และ รหัส
  • การแก้ไขข้อผิดพลาดและแนวคิดเรื่องระยะทางของรหัส รหัส Hamming และขอบเขตต่าง ๆ
  • มีการจัดหมวดหมู่ตระกูลรหัส แบบฝึกหัด และบรรณานุกรม

ภาค I: พื้นฐาน

  • แนะนำโครงสร้างทางคณิตศาสตร์ เช่น รหัสเชิงเส้น finite field และ ปริภูมิเวกเตอร์
  • อธิบายการถอดรหัสรหัส Hamming อย่างมีประสิทธิภาพและรหัสคู่
  • มีแบบฝึกหัดและเอกสารอ้างอิง

บทที่ 3: ความน่าจะเป็นและฟังก์ชันเอนโทรปีฐาน q

  • ทำความเข้าใจ พื้นฐานทฤษฎีความน่าจะเป็น วิธีการเชิงสุ่ม และฟังก์ชันเอนโทรปีฐาน q
  • มีแบบฝึกหัดและบรรณานุกรมที่เกี่ยวข้อง

ภาค II: คอมบิเนโทริกส์

  • อธิบาย ขอบเขตของรหัส และข้อจำกัดต่าง ๆ เช่น Hamming, Gilbert-Varshamov, Singleton, Plotkin
  • การประยุกต์ใช้ Reed-Solomon code, พหุนาม และ finite field
  • แบบจำลองสัญญาณรบกวนของ Shannon และขีดจำกัดของการส่งข้อมูล พร้อมการเปรียบเทียบกับ Hamming
  • ขยายไปสู่ list decoding, Johnson Bound และความจุของ list decoding
  • นำเสนอทฤษฎีขีดจำกัดใหม่ ๆ เช่น Elias-Bassalygo และ linear programming bound

ภาค III: โครงสร้างรหัสที่หลากหลาย

  • รหัสที่อิงกับพหุนาม การใช้ binary field และโครงสร้างรหัสทั่วไป
  • การต่อรหัส (concatenation), Zyablov Bound เทคนิคการต่อรหัสขั้นสูง และบทสรุป
  • กราฟ Expander และ Expander code การขยายระยะทาง และกรณีการใช้งาน

ภาค IV: อัลกอริทึม

  • วิธีถอดรหัสอย่างมีประสิทธิภาพสำหรับ Reed-Solomon, Reed-Muller และรหัสต่อ
  • วิธีบรรลุความจุของช่องสัญญาณ BSCp และโครงสร้างรหัสชั้นใน/ชั้นนอก
  • Polar code, หลักการ Polarization, การติดตั้งใช้งาน encoder/decoder และความสามารถด้าน list decoding
  • อธิบายรหัสที่เข้ารหัสได้ในเวลาเชิงเส้นและรองรับการกู้คืนเฉพาะที่

ภาค V: การประยุกต์ใช้

  • ทฤษฎีของแฮชและการป้องกันการชนกัน, ฟังก์ชันแฮชแบบเกือบสากล, การพิสูจน์ความเป็นเจ้าของข้อมูล
  • แนวคิด Fuzzy Vault เพื่อปกป้องการยืนยันตัวตนทางชีวภาพ เช่น ลายนิ้วมือ
  • การทำให้ Group Testing เป็นแบบจำลองอย่างเป็นทางการ ขอบเขตต่าง ๆ และการประยุกต์กับอัลกอริทึม data stream
  • ความซับซ้อนของปัญหาการเข้ารหัส: ปัญหา nearest codeword, การถอดรหัสที่อาศัย preprocessing, การประมาณค่า, ปัญหาระยะทางต่ำสุด เป็นต้น
  • หัวข้อสนับสนุนด้านความซับซ้อนเชิงคำนวณ เช่น communication complexity, randomness, pseudorandomness, hardcore predicates และปัญหาความยากเชิงเฉลี่ย

ภาคผนวก

  • ตารางสัญลักษณ์ อสมการและสมการที่มีประโยชน์ สัญกรณ์เชิงอะซิมพ์โทติก พื้นฐานของอัลกอริทึมและความซับซ้อน
  • แนะนำ อัลกอริทึมเชิงพีชคณิต, finite field และการคำนวณพหุนาม
  • สรุปแนวคิดสำคัญของทฤษฎีสารสนเทศ เช่น เอนโทรปี เอนโทรปีมีเงื่อนไข และข้อมูลร่วมกัน

จุดเด่นและคุณค่าการใช้งาน

  • ให้ทั้งพื้นฐานทางทฤษฎีและแนวทางประยุกต์ใช้จริงของอัลกอริทึมแก้ไขข้อผิดพลาด ซึ่งเป็นสิ่งจำเป็นใน การสื่อสารข้อมูลสมัยใหม่ การจัดเก็บข้อมูล และระบบเข้ารหัสลับ
  • ครอบคลุมตั้งแต่แนวคิดพื้นฐาน แนวโน้มล่าสุด ไปจนถึงการใช้งานจริง ถ่ายทอดความรู้ได้กว้างสำหรับนักพัฒนาใหม่ นักวิจัย และผู้ปฏิบัติงานด้านไอที
  • แต่ละบทมีแบบฝึกหัดและบรรณานุกรม จึงเหมาะต่อการเรียนรู้และการศึกษาด้วยตนเอง
  • สามารถนำไปใช้ได้อย่างอิสระเพื่อวัตถุประสงค์ทางวิชาการและไม่เชิงพาณิชย์ ตามเงื่อนไขของสัญญาอนุญาต Creative Commons

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-08-31
ความคิดเห็นจาก Hacker News

  • อยากย้ำว่า "The Mathematical Theory of Communication" ของ Claude Shannon เป็นเอกสารพื้นฐานของทฤษฎีสารสนเทศที่อธิบายได้เข้าใจง่ายมากจนแม้ไม่มีพื้นฐานคณิตศาสตร์ลึกก็อ่านได้ ลิงก์

    • อยากบอกว่า Shannon เป็นบุคคลที่ยอดเยี่ยมมากสำหรับการเริ่มต้นฝึกวิธีคิดแบบคณิตศาสตร์ เขาได้อนุมานแนวคิดเรื่อง information entropy ขึ้นมาในตอนแรกโดยไม่ได้ให้ความหมายใดเป็นพิเศษ แต่ยึดจากคุณสมบัติที่จำเป็นเท่านั้น น่าทึ่งที่นิยามซึ่งเกิดขึ้นแทบจะโดยบังเอิญนี้กลับสอดคล้องเกือบพอดีกับ thermodynamic entropy ในฟิสิกส์ และ Von Neumann เป็นคนชี้ให้เห็นและตั้งชื่อนี้ให้ คณิตศาสตร์มักดำเนินไปตามตรรกะแบบ "ถ้าต้องเป็นไปตามกฎเหล่านี้" ซึ่งเป็นหนึ่งในเหตุผลที่หลายคนรู้สึกว่ามันยาก บทความของ Shannon เป็นเพียงการวางโครงกระดูกของ coding theory และไม่มีการนำไปทำจริงอยู่ในบทความนั้น ฉันเคยจัดชมรมอ่านหนังสือที่อ่านฉบับหนังสือของบทความนี้ด้วยกันที่สตาร์ตอัปเก่า และอยากแนะนำว่าเป็นประสบการณ์ที่ดีมากสำหรับการทำความเข้าใจทั้งทฤษฎีสารสนเทศและคณิตศาสตร์โดยรวม

  • สาขาการบีบอัดแบบไม่สูญเสียข้อมูลมีความเกี่ยวข้องใกล้ชิดกับ generative AI มาก ถ้าเพิ่มเนื้อหาในส่วนนี้อีกก็น่าจะน่าสนใจ อยากแนะนำวิทยานิพนธ์ปริญญาเอกที่อธิบายความเชื่อมโยงระหว่างการบีบอัดแบบไม่สูญเสียข้อมูลกับแมชชีนเลิร์นนิงได้ดี ลิงก์

    • จริง ๆ ก็ไม่จำเป็นต้องจำกัดไว้แค่การบีบอัดแบบไม่สูญเสียข้อมูล แทบทุกอย่างในแมชชีนเลิร์นนิงสามารถเข้าใจได้ว่าเป็นการบีบอัดรูปแบบหนึ่ง (ส่วนใหญ่คือการบีบอัดแบบสูญเสียข้อมูล) ตัวอย่างเช่น ถ้าส่งเฉพาะ semantic embedding ผ่านช่องทาง ก็ยังทำงานได้แม้ไม่มีข้อความต้นฉบับทั้งหมด เพราะในค่า embedding มีข้อมูลมากพออยู่แล้ว การจัดประเภทข้อมูลก็ท้ายที่สุดคือกระบวนการเก็บไว้เพียงตัวแทนแฝงของหมวดหมู่ทั่วไปและทิ้งส่วนที่เหลือไป ในกรณีของ generative AI มันกลับทำงานได้ดีเพราะเราทำ 'การบีบอัดแบบสูญเสียข้อมูล' จงใจทิ้งข้อมูลบางส่วนไป แล้วให้อนุมานช่องว่างนั้น จึงเปิดทางให้เกิดการทำให้ทั่วไปได้ LLM แบบไม่สูญเสียข้อมูลจริง ๆ แล้วไม่ได้มีอะไรน่าสนใจมากนักในแง่การใช้งานจริง อย่างไรก็ตาม บทความที่แนะนำนี้พิเศษมากเพราะเป็นงานที่ว่าด้วยการบีบอัดแบบไม่สูญเสียข้อมูลซึ่งพบได้ยากแม้แต่ในวงการแมชชีนเลิร์นนิง

  • มีตำราดี ๆ ที่ทำขึ้นไม่นานนี้ชื่อ <i>Information Theory: From Coding to Learning</i> มีเวอร์ชัน PDF ออนไลน์ด้วย น่าจะใช้ประกอบการอ่านได้ดี ลิงก์

    • อยากแนะนำ <i>Information Theory, Inference, and Learning Algorithms</i> ของ David MacKay ด้วย ลิงก์

  • เพื่อตอบคำถามที่ว่า "coding" ในที่นี้หมายถึงอะไร คำว่า coding ที่นี่หมายถึงการ encode/decode ซึ่งเป็นการแปลงข้อมูลจากรูปแบบหนึ่งไปสู่อีกรูปแบบหนึ่ง ระบบลักษณะนี้เรียกว่า code และถูกออกแบบมาเพื่อให้ทนต่อการรบกวน การดัดแปลง หรือการดักฟังระหว่างการส่งข้อมูล กล่าวคือ code (coding) ถูกใช้ในหลายสาขา เช่น การบีบอัดข้อมูล การเข้ารหัส การตรวจจับและแก้ไขข้อผิดพลาด การส่งและการจัดเก็บข้อมูล ลิงก์

    • โดยเฉพาะหนังสือที่กล่าวถึงนี้มุ่งเน้นไปที่ error correcting code โดยจะเพิ่มข้อมูลพิเศษเข้าไปเพื่อให้สามารถกู้คืนส่วนที่สูญหายได้เมื่อส่งข้อความ ความยากที่ต้องแก้คือการออกแบบข้อมูลเพิ่มเติมที่สามารถกู้ข้อผิดพลาดได้มากพอ โดยมี overhead ต่ำที่สุดและใช้เวลาในการคำนวณที่สมเหตุสมผล เทคโนโลยีแบบนี้ถูกใช้งานจริงในหลายที่มาก เช่น WiFi, ฮาร์ดไดรฟ์, QR code, RAM เป็นต้น ตัวอย่างเช่น ECC ใน ECC RAM ก็คือ error correcting code นั่นเอง และใน DDR5 เทคโนโลยีนี้ก็ถูกบังคับใช้บางส่วนเมื่อไม่นานมานี้

  • ในเมื่อกำลังแชร์อีบุ๊ก CS ฟรีกันอยู่ ก็อยากแนะนำหนังสือ Algorithms ของ Jeff E. อย่างมากเช่นกัน เป็นหนังสือที่ต้องอ่านสำหรับคนที่อยากเรียนอัลกอริทึมหรือทบทวนทักษะ ลิงก์

  • ฉันอ่านหนังสือเล่มนี้ไปแล้วสองสามบทและพอใจมาก วางแผนว่าจะค่อย ๆ อ่านต่อไปในช่วงหลายสัปดาห์หรืออาจหลายเดือนข้างหน้า

  • ถ้าอยากศึกษาทฤษฎีสารสนเทศและ coding theory ให้ลึกขึ้น ก็อยากแนะนำแหล่งข้อมูลต่อไปนี้ด้วย สำหรับ error correcting code คือ "Error-Correcting Codes" ของ W. Wesley Peterson และ E. J. Weldon, Jr. และสำหรับพีชคณิตนามธรรม (โดยเฉพาะ field theory) คือ "Commutative Algebra" ของ Oscar Zariski และ Pierre Samuel

    • คำสั่ง LaTeX ใช้งานที่นี่ไม่ได้

  • ถ้าจะยกหนังสือสำหรับผู้เริ่มต้นที่อยากแนะนำสักไม่กี่เล่ม

    1. <i>An Introduction to Information Theory, Symbols, Signals and Noise</i> ของ John R. Pierce - เป็นงานคลาสสิกที่ดีสำหรับทำความเข้าใจแนวคิดและสร้างสัญชาตญาณ หนังสือเล่มอื่นของผู้เขียนคนนี้ก็ดีมากเช่นกัน
    2. <i>Information Theory: A Tutorial Introduction</i> ของ James V. Stone - เป็นหนังสือเริ่มต้นที่อ่านง่ายและดีมาก บทช่วยสอนอื่น ๆ ของผู้เขียนก็น่าสนใจ
    3. <i>A Student's Guide to Coding and Information Theory</i> ของ Stefan Moser และ Po-ning chen - เป็นคู่มือที่กระชับและชัดเจน และหนังสือเล่มอื่นในชุดเดียวกันก็น่าแนะนำ

  • ทุกครั้งที่มีใครบอกว่า "นี่คือสิ่งจำเป็น" สำหรับฉันที่เคยแค่ได้แตะหัวข้อนั้นผิว ๆ ตอนเรียนในภาควิชา มันเป็นช่วงเวลาที่ชวนหวั่นเล็กน้อยเสมอ

    • คำว่า 'จำเป็น' ในรายวิชานี้ไม่ได้หมายความว่านักศึกษาวิทยาการคอมพิวเตอร์ทุกคนต้องรู้ แต่หมายถึงว่ามันบรรจุแก่นแท้ของ coding theory เอาไว้ ผู้เขียนร่วมของหนังสือเล่มนี้สอนวิชานี้อยู่ที่มหาวิทยาลัยของเราโดยตรง และวิชานี้เป็นวิชาเลือกสำหรับชั้นปีสูงที่มีเนื้อหาคณิตศาสตร์เข้มข้นมาก ในหลักสูตรวิทยาการคอมพิวเตอร์ 4 ปี โดยมากจะมีเพียงนักศึกษาปีสุดท้ายส่วนน้อยมากที่เรียน และเพื่อน ๆ รอบตัวฉันที่เคยลงเรียนวิชานี้ล้วนเป็นคนที่ชอบพิสูจน์ทางคณิตศาสตร์ พวกเขาสนุกกับวิชานี้

    • ถ้ามีคำว่า "จำเป็น" หรือ "เบื้องต้น" อยู่ในชื่อ ก็เป็นสัญญาณล่วงหน้าว่ามีตำราที่อัดแน่นมากรออยู่