03 · สารสนเทศและการเข้ารหัส
บทนี้คือพื้นหินชั้นล่างสุดใต้ทุกข้อความที่หอคอยลำเลียง — ตรึงว่าสัญญาณ (signal) คืออะไร และช่องสัญญาณ (channel) หนึ่งแบกได้มากแค่ไหน
ช่องสัญญาณหนึ่งแบกความประหลาดใจได้มากแค่ไหน
ก่อนปี 1948 วิศวกรทุกคนที่ทำงานกับสายที่มีสัญญาณรบกวน (noise) เชื่อเหมือนกันหมด และเชื่อผิด สัญญาณรบกวนกัดข้อความให้เสียหาย จะสู้ก็ต้องตะโกนดังขึ้นหรือพูดซ้ำ ทางไหนก็ตามคือซื้อความแม่นยำด้วยพลังงานหรือด้วยเวลา และอัตราแลกเปลี่ยนไม่ปรานีใคร — จะกดอัตราความผิดพลาดให้เข้าใกล้ศูนย์ ต้องหน่วงข้อความจนเกือบหยุดนิ่ง ความน่าเชื่อถือ (reliability) กับความเร็วนั่งอยู่คนละข้างของไม้กระดก และนั่นคือธรรมชาติของช่องสัญญาณทางกายภาพ
ไม้กระดกตัวนั้นหักลงเมื่อ Claude Shannon ที่ Bell Labs ตีพิมพ์เปเปอร์สองภาคในฉบับเดือนกรกฎาคมและตุลาคมปี 1948 ของ Bell System Technical Journal (Shannon, 1948) เขาพิสูจน์ว่าทุกช่องสัญญาณมีตัวเลขติดตัวมาหนึ่งตัว — ความจุช่องสัญญาณ (channel capacity) ส่งด้วยอัตราใดก็ตามที่ ต่ำกว่า ตัวเลขนั้น คุณกดความน่าจะเป็นของความผิดพลาดให้ใกล้ศูนย์เท่าไรก็ได้ โดยไม่ต้องช้าลงเลยสักนิด ส่งเกินตัวเลขนั้น ไม่มีอะไรช่วยคุณได้ ไม่ว่าจะเพิ่มพลังงาน เพิ่มการพูดซ้ำ หรือวิธีเข้ารหัส (encoding) แบบใดที่ใครจะคิดขึ้นได้ในอนาคต ไม่ใช่ไม้กระดก แต่เป็นขีดจำกัดความเร็ว ที่มีของฟรีซ่อนอยู่ข้างใต้
กว่าจะไปถึงจุดนั้น Shannon ต้องบอกก่อนว่าข้อความ*คือ*อะไร
สารสนเทศ (information) คือความประหลาดใจ ไม่ใช่ความหมาย ย่อหน้าที่สองของเขาโยนทิ้งสิ่งที่คนอื่นทั้งวงการหวงแหน — "แง่มุมเชิงความหมาย (semantic) เหล่านี้ของการสื่อสารไม่เกี่ยวข้องกับโจทย์ทางวิศวกรรม" ที่สำคัญมีอย่างเดียว คือข้อความหนึ่งคือการ*เลือก*จากชุดข้อความที่เป็นไปได้ และงานของวิศวกรคือสร้างการเลือกนั้นขึ้นใหม่ที่ปลายทาง กรอบใหม่นี้คลอดหน่วยวัดออกมา — "ถ้าใช้ฐาน 2 หน่วยที่ได้จะเรียกว่า binary digit หรือเรียกสั้นๆ ว่า bit คำที่ J. W. Tukey เป็นคนเสนอ" โยนเหรียญเที่ยงตรงหนึ่งครั้งได้หนึ่งบิต (bit) ลูกเต๋าเที่ยงตรงหนึ่งลูกได้ราว 2.6 บิต ข้อความที่ทายได้อยู่แล้วไม่ให้อะไรเลย ยาวแค่ไหนก็ตาม ข้อความที่ทายไม่ได้ให้มาก สั้นแค่ไหนก็ตาม เอนโทรปี (entropy) — ตัว H ของ Shannon — คือค่าเฉลี่ยความประหลาดใจต่อสัญลักษณ์หนึ่งตัวจากแหล่งข้อมูลหนึ่งแหล่ง Harry Nyquist และ Ralph Hartley วนรอบไอเดียนี้ในวารสารเดียวกันมาแล้วเมื่อปี 1924 และ 1928 Shannon ปิดวงด้วยการทำให้มันวัดได้
เอนโทรปีคือพื้นชั้นล่างสุดของการบีบอัด (compression) พอความประหลาดใจมีตัวเลขกำกับ ตัวเลขนั้นก็ผูกมัด ผลลัพธ์การเข้ารหัสแบบไร้สัญญาณรบกวนของ Shannon (Theorem 9 ในเปเปอร์) บอกว่าแหล่งข้อมูลที่มีเอนโทรปี H เข้ารหัสให้ต่ำกว่า H บิตต่อสัญลักษณ์โดยเฉลี่ยไม่ได้ และเข้ารหัสให้ใกล้ H ได้มากเท่าที่ต้องการ ภาษาอังกฤษอยู่ห่างจาก 4.7 บิตต่อตัวอักษรที่ตัวอักษร 26 ตัวเปิดช่องให้อยู่มาก เพราะตัวอักษรทำนายกันเอง — q ตามด้วย u และคุณรู้อยู่ก่อนแล้วว่าประโยคนี้จะจบอย่างไร ช่องว่างระหว่างความจุของตัวอักษรกับเอนโทรปีของภาษา คือสิ่งที่ไฟล์บีบอัดทุกไฟล์กินเข้าไป การบีบอัดจึงไม่ใช่กลที่เล่นกับข้อมูล แต่คือการรูดความที่ทายได้ออกทิ้ง ซึ่งอธิบายสองเรื่องที่ทุกคนเคยเจอ — ไฟล์ที่บีบอัดแล้วบีบซ้ำอีกไม่ได้ และข้อมูลที่สุ่มจริงๆ บีบไม่ลงเลย
ความจุคือขีดจำกัดความเร็ว ความซ้ำซ้อน (redundancy) คือวิธีขับให้ถึงขีดนั้น ทฤษฎีบทช่องสัญญาณที่มีสัญญาณรบกวนของ Shannon (Theorem 11) คือของฟรีที่เขียนไว้อย่างเป็นทางการ และ Theorem 17 ใส่ตัวเลขให้กรณีที่พบบ่อยที่สุด — "ความจุของช่องสัญญาณย่านความถี่ W ที่ถูกรบกวนโดยสัญญาณรบกวนความร้อนสีขาวกำลัง N เมื่อกำลังส่งเฉลี่ยคือ P" คือ C = W log(1 + P/N) บิตต่อวินาที (BSTJ 27, no. 4) สังเกตว่าข้อนี้เปิดทางให้อะไร พูดข้อความซ้ำสามครั้งคือใช้ความซ้ำซ้อนอย่างโง่ๆ ต้นทุนสามเท่าแลกกำไรนิดเดียว Shannon พิสูจน์ว่าความซ้ำซ้อนที่ใช้อย่าง*ฉลาด*ซื้อความน่าเชื่อถือที่เกือบสมบูรณ์แบบมาได้โดยแทบไม่เสียอัตราเลย แต่เขาไม่ได้บอกว่าทำอย่างไร บทพิสูจน์ของเขาแสดงว่ารหัสที่ดีมีอยู่จริง ด้วยการแสดงว่ารหัสที่หยิบมาแบบสุ่มน่าจะดี — บทพิสูจน์เชิงมีอยู่จริง (existence proof) ที่ยื่นโครงการก่อสร้างยาวห้าสิบปีใส่มือวิศวกร
โครงการก่อสร้างนั้น Richard Hamming มีเรื่องส่วนตัวค้างอยู่ ปี 1947 เขาทำงานเสาร์อาทิตย์กับเครื่องคำนวณแบบรีเลย์ของ Bell Labs โดยไม่มีเจ้าหน้าที่ควบคุมสักคน ส่งงานเข้าไปวันศุกร์ กลับมาวันจันทร์ก็พบว่าเครื่องจับข้อผิดพลาดในการอ่านบัตรได้ ทิ้งงานของเขา แล้วเดินหน้าต่อ สองครั้งติดกัน "แม่งเอ๊ย" เขาเล่าว่าคิดแบบนั้น "ถ้าเครื่องหาเจอว่ามีข้อผิดพลาดได้ ทำไมมันถึงหาตำแหน่งที่ผิดแล้วเปลี่ยนค่ารีเลย์จากหนึ่งเป็นศูนย์หรือศูนย์เป็นหนึ่งเองไม่ได้ล่ะ" (IEEE Computer Society) คำตอบกลายเป็น Hamming code (BSTJ 29, no. 2, April 1950: 147–160) — บิตพาริตี (parity bit) วางเรียงไว้จนรูปแบบของการตรวจสอบที่ล้มเหลวสะกดตำแหน่งของบิตที่พลิกออกมาเป็นเลขฐานสอง การตรวจจับ (detection) กลายเป็นการแก้ไข (correction)
จากนั้นรหัสก็เก่งขึ้น การสร้างของ Reed และ Solomon ในปี 1960 บนฟิลด์จำกัด (finite field) (Journal of the SIAM 8: 300–304) ทนความเสียหายที่มาเป็นช่วง (burst) ไม่ใช่แค่บิตพลิกเดี่ยวๆ ซึ่งเป็นสิ่งที่อวกาศห้วงลึกเรียกร้อง JPL ปล่อยยาน Voyager 2 มุ่งดาวยูเรนัสทั้งที่ตัวถอดรหัส Reed–Solomon ของมันยังไม่มีตัวตน โดย "พนันว่าเมื่อถึงเวลาที่ Voyager II ไปถึงดาวยูเรนัสในปี 1986 อัลกอริทึมและอุปกรณ์ถอดรหัสจะพร้อมใช้งานและสมบูรณ์แล้ว ซึ่งพวกเขาคิดถูก!" (NASA TM 102162) ระหว่างนั้น Robert Gallager คิด low-density parity-check code (LDPC) ขึ้นในวิทยานิพนธ์ที่ MIT ปี 1960 ตีพิมพ์ในปี 1962 (IRE Transactions on Information Theory 8: 21–28) แล้วยืนดูมันจางหายไป เพราะถอดรหัสแพงเกินฮาร์ดแวร์ยุคนั้น MacKay และ Neal ขุดมันขึ้นมาใหม่ในปี 1995–96 พร้อมกับ turbo code ของ Berrou, Glavieux และ Thitimajshima (Proc. IEEE ICC, 1993) และกำแพงที่ Shannon ขีดไว้ก็ถูกแตะถึงในที่สุด — ภายในปี 2001 LDPC แบบ irregular เข้าใกล้ความจุเหลือระยะ 0.0045 เดซิเบล (Chung, Forney, Richardson & Urbanke, IEEE Communications Letters 5, 2001) โทรศัพท์ของคุณใช้ทายาททั้งสองสาย — LDPC สำหรับช่องข้อมูล 5G และ polar code ของ Erdal Arıkan ตีพิมพ์ปี 2009 เข้าเป็นมาตรฐานภายในสิบปี สำหรับช่องควบคุม
ความเงียบของชั้นนี้คือรอยรั่ว (leak) ของมันเอง ทุกอย่างข้างต้นไม่สนใจว่าข้อความพูดว่าอะไร คำปฏิเสธความรับผิดชอบของ Shannon เป็นเงื่อนไขที่จำเป็นต่อพลังของทฤษฎี ไม่ใช่การมองข้าม — แต่แปลว่าชั้นนี้ตั้งราคาการส่งผลวินิจฉัยโรคเท่ากับการส่งข้อความสแปม และพูดไม่ได้สักคำว่าอันไหนคุ้มที่จะส่ง ทุกชั้นเหนือขึ้นไปจ่ายค่าความเงียบนี้ด้วยสกุลเงินของตัวเอง — วิทยาการรหัสลับ (cryptography, บทที่ 11) ต้องเติมว่าใครเป็นคนส่ง ฐานข้อมูล (บทที่ 08) ต้องเติมว่ามันหมายความว่าอะไร และ machine learning (บทที่ 12) ใช้ชีวิตทั้งชีวิตไล่กู้ความหมายกลับจากสถิติ — พร้อมกับแอบใช้เอนโทรปีของ Shannon เป็น loss function
เชื่อมโยง
ชั้นข้างเคียง: บทที่ 02 ซึ่งขอบล่าง Ω(n log n) ของการเรียงลำดับคือข้อโต้แย้งเรื่องการนับของบทนี้ที่แฝงตัวมา — log₂(n!) คือจำนวนบิตที่ต้องใช้ระบุลำดับหนึ่งแบบ ชั้นบน: บทที่ 09 ที่ TCP ก่อความน่าเชื่อถือขึ้นจากช่องสัญญาณที่ไม่น่าเชื่อถือ ข้อตกลงเดียวกัน ทำที่ชั้นสูงกว่า บทที่ 08 ที่การบีบอัดและ checksum เฝ้าข้อมูลที่จัดเก็บไว้ บทที่ 11 ที่ความแข็งแกร่งของ cipher นับกันเป็นบิต บทที่ 12 ที่โมเดลซึ่งทายโทเคนถัดไปได้ดี ตามข้อโต้แย้งข้างต้นก็คือตัวบีบอัดตัวหนึ่ง
คำถามที่ยังเปิดอยู่
Shannon ตัดความหมาย (meaning) ออกไปโดยตั้งใจ — และยังไม่มีทฤษฎีสารสนเทศเชิงความหมาย (semantic information) ที่ได้รับการยอมรับเข้ามาแทนสิ่งที่เขาวางทิ้งไว้ แม้คำถามนี้จะกลับมามีชีวิตอีกครั้งเพราะโมเดลภาษาทำให้มันใช้ได้จริง การบีบอัดคือสิ่งเดียวกับความเข้าใจ หรือแค่สัมพันธ์กันเฉยๆ และในแง่กายภาพ — ใกล้ความจุแค่ไหนถึงเรียกว่าใกล้พอที่จะหยุด ในเมื่อเดซิเบลเศษเสี้ยวสุดท้ายตอนนี้กินพลังงานในการถอดรหัสมากกว่าที่ประหยัดได้ตอนส่ง
อ่านต่อ
- Claude Shannon, "A Mathematical Theory of Communication," Bell System Technical Journal 27 (1948): 379–423, 623–656 — ยังคงเป็นการอธิบายไอเดียของตัวเองที่ชัดเจนที่สุด (PDF).
- David MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003 — ฟรีจากเว็บไซต์ของผู้เขียนเอง และเป็นหนังสือที่เชื่อมชั้นนี้เข้ากับบทที่ 12 (inference.org.uk).
- Richard Hamming, "Error Detecting and Error Correcting Codes," Bell System Technical Journal 29, no. 2 (April 1950): 147–160 — คำตอบที่ใช้งานได้จริงชิ้นแรกต่อบทพิสูจน์เชิงมีอยู่จริงของ Shannon (scan).