03 · Information & Coding
03 · สารสนเทศและการเข้ารหัส
This chapter is the bedrock floor beneath every message the tower moves — it fixes what a signal is, and how much of one a channel can carry.
บทนี้คือพื้นหินชั้นล่างสุดใต้ทุกข้อความที่หอคอยลำเลียง — ตรึงว่าสัญญาณ (signal) คืออะไร และช่องสัญญาณ (channel) หนึ่งแบกได้มากแค่ไหน
How much surprise can a channel carry?
ช่องสัญญาณหนึ่งแบกความประหลาดใจได้มากแค่ไหน
Before 1948, every engineer working on a noisy line believed the same thing, and it was wrong. Noise corrupts messages; to fight it you shout louder or you repeat yourself. Either way you buy accuracy with power or with time, and the exchange rate looked merciless: to drive the error rate near zero you had to slow the message near to a stop. Reliability and speed were a seesaw, and that was simply the nature of physical channels.
ก่อนปี 1948 วิศวกรทุกคนที่ทำงานกับสายที่มีสัญญาณรบกวน (noise) เชื่อเหมือนกันหมด และเชื่อผิด สัญญาณรบกวนกัดข้อความให้เสียหาย จะสู้ก็ต้องตะโกนดังขึ้นหรือพูดซ้ำ ทางไหนก็ตามคือซื้อความแม่นยำด้วยพลังงานหรือด้วยเวลา และอัตราแลกเปลี่ยนไม่ปรานีใคร — จะกดอัตราความผิดพลาดให้เข้าใกล้ศูนย์ ต้องหน่วงข้อความจนเกือบหยุดนิ่ง ความน่าเชื่อถือ (reliability) กับความเร็วนั่งอยู่คนละข้างของไม้กระดก และนั่นคือธรรมชาติของช่องสัญญาณทางกายภาพ
Then Claude Shannon, at Bell Labs, published a paper in two parts, in the July and October 1948 issues of the Bell System Technical Journal, and the seesaw broke (Shannon, 1948). Every channel, he proved, has a number attached to it — its capacity. Send at any rate below that number and you can push the probability of error as close to zero as you like, without slowing down at all. Send above it and nothing saves you: not more power, not more repetition, not any coding scheme anyone will ever invent. Not a seesaw. A speed limit, with a free lunch underneath it.
ไม้กระดกตัวนั้นหักลงเมื่อ Claude Shannon ที่ Bell Labs ตีพิมพ์เปเปอร์สองภาคในฉบับเดือนกรกฎาคมและตุลาคมปี 1948 ของ Bell System Technical Journal (Shannon, 1948) เขาพิสูจน์ว่าทุกช่องสัญญาณมีตัวเลขติดตัวมาหนึ่งตัว — ความจุช่องสัญญาณ (channel capacity) ส่งด้วยอัตราใดก็ตามที่ ต่ำกว่า ตัวเลขนั้น คุณกดความน่าจะเป็นของความผิดพลาดให้ใกล้ศูนย์เท่าไรก็ได้ โดยไม่ต้องช้าลงเลยสักนิด ส่งเกินตัวเลขนั้น ไม่มีอะไรช่วยคุณได้ ไม่ว่าจะเพิ่มพลังงาน เพิ่มการพูดซ้ำ หรือวิธีเข้ารหัส (encoding) แบบใดที่ใครจะคิดขึ้นได้ในอนาคต ไม่ใช่ไม้กระดก แต่เป็นขีดจำกัดความเร็ว ที่มีของฟรีซ่อนอยู่ข้างใต้
To get there, Shannon first had to say what a message is.
กว่าจะไปถึงจุดนั้น Shannon ต้องบอกก่อนว่าข้อความ*คือ*อะไร
Information is surprise, not meaning. His second paragraph throws away the thing everyone else cared about: "These semantic aspects of communication are irrelevant to the engineering problem." What matters is only that a message is a selection from a set of possible messages, and the engineering job is to reproduce the selection at the far end. That reframing gives the unit: "If the base 2 is used the resulting units may be called binary digits, or more briefly bits, a word suggested by J. W. Tukey." One fair coin flip is one bit; one fair die is about 2.6. A message you could have predicted carries none, however long it is, and a message you could not carries a great deal, however short. Entropy — Shannon's H — is just the average surprise per symbol from a source. Harry Nyquist and Ralph Hartley had circled this in the same journal in 1924 and 1928; Shannon closed the circle by making it a measure.
สารสนเทศ (information) คือความประหลาดใจ ไม่ใช่ความหมาย ย่อหน้าที่สองของเขาโยนทิ้งสิ่งที่คนอื่นทั้งวงการหวงแหน — "แง่มุมเชิงความหมาย (semantic) เหล่านี้ของการสื่อสารไม่เกี่ยวข้องกับโจทย์ทางวิศวกรรม" ที่สำคัญมีอย่างเดียว คือข้อความหนึ่งคือการ*เลือก*จากชุดข้อความที่เป็นไปได้ และงานของวิศวกรคือสร้างการเลือกนั้นขึ้นใหม่ที่ปลายทาง กรอบใหม่นี้คลอดหน่วยวัดออกมา — "ถ้าใช้ฐาน 2 หน่วยที่ได้จะเรียกว่า binary digit หรือเรียกสั้นๆ ว่า bit คำที่ J. W. Tukey เป็นคนเสนอ" โยนเหรียญเที่ยงตรงหนึ่งครั้งได้หนึ่งบิต (bit) ลูกเต๋าเที่ยงตรงหนึ่งลูกได้ราว 2.6 บิต ข้อความที่ทายได้อยู่แล้วไม่ให้อะไรเลย ยาวแค่ไหนก็ตาม ข้อความที่ทายไม่ได้ให้มาก สั้นแค่ไหนก็ตาม เอนโทรปี (entropy) — ตัว H ของ Shannon — คือค่าเฉลี่ยความประหลาดใจต่อสัญลักษณ์หนึ่งตัวจากแหล่งข้อมูลหนึ่งแหล่ง Harry Nyquist และ Ralph Hartley วนรอบไอเดียนี้ในวารสารเดียวกันมาแล้วเมื่อปี 1924 และ 1928 Shannon ปิดวงด้วยการทำให้มันวัดได้
Entropy is the floor of compression. Once surprise has a number, the number binds. Shannon's noiseless coding result (Theorem 9 in the paper) says a source of entropy H cannot be encoded in fewer than H bits per symbol on average, and can be encoded in arbitrarily close to H. English is nowhere near the 4.7 bits per character that a 26-letter alphabet would allow, because letters predict each other — q is followed by u, and you already knew how this sentence would end. That gap between the alphabet's capacity and the language's entropy is exactly what every compressed archive eats. Compression is therefore not a trick performed on data; it is the removal of predictability. Which explains two things everyone has noticed: a compressed file does not compress again, and truly random data does not compress at all.
เอนโทรปีคือพื้นชั้นล่างสุดของการบีบอัด (compression) พอความประหลาดใจมีตัวเลขกำกับ ตัวเลขนั้นก็ผูกมัด ผลลัพธ์การเข้ารหัสแบบไร้สัญญาณรบกวนของ Shannon (Theorem 9 ในเปเปอร์) บอกว่าแหล่งข้อมูลที่มีเอนโทรปี H เข้ารหัสให้ต่ำกว่า H บิตต่อสัญลักษณ์โดยเฉลี่ยไม่ได้ และเข้ารหัสให้ใกล้ H ได้มากเท่าที่ต้องการ ภาษาอังกฤษอยู่ห่างจาก 4.7 บิตต่อตัวอักษรที่ตัวอักษร 26 ตัวเปิดช่องให้อยู่มาก เพราะตัวอักษรทำนายกันเอง — q ตามด้วย u และคุณรู้อยู่ก่อนแล้วว่าประโยคนี้จะจบอย่างไร ช่องว่างระหว่างความจุของตัวอักษรกับเอนโทรปีของภาษา คือสิ่งที่ไฟล์บีบอัดทุกไฟล์กินเข้าไป การบีบอัดจึงไม่ใช่กลที่เล่นกับข้อมูล แต่คือการรูดความที่ทายได้ออกทิ้ง ซึ่งอธิบายสองเรื่องที่ทุกคนเคยเจอ — ไฟล์ที่บีบอัดแล้วบีบซ้ำอีกไม่ได้ และข้อมูลที่สุ่มจริงๆ บีบไม่ลงเลย
Capacity is a speed limit, and redundancy is how you drive at it. Shannon's noisy-channel theorem (Theorem 11) is the free lunch stated formally, and Theorem 17 puts a number on it for the commonest case: "The capacity of a channel of band W perturbed by white thermal noise of power N when the average transmitter power is P" is C = W log(1 + P/N) bits per second (BSTJ 27, no. 4). Note what this licenses. Repeating a message three times is redundancy spent stupidly — it triples your cost for a modest gain. Shannon proved that redundancy spent cleverly buys near-perfect reliability at almost no cost in rate. He did not, however, say how. His proof shows that good codes exist by showing that a randomly chosen code is probably good — an existence proof that handed engineers a construction project lasting fifty years.
ความจุคือขีดจำกัดความเร็ว ความซ้ำซ้อน (redundancy) คือวิธีขับให้ถึงขีดนั้น ทฤษฎีบทช่องสัญญาณที่มีสัญญาณรบกวนของ Shannon (Theorem 11) คือของฟรีที่เขียนไว้อย่างเป็นทางการ และ Theorem 17 ใส่ตัวเลขให้กรณีที่พบบ่อยที่สุด — "ความจุของช่องสัญญาณย่านความถี่ W ที่ถูกรบกวนโดยสัญญาณรบกวนความร้อนสีขาวกำลัง N เมื่อกำลังส่งเฉลี่ยคือ P" คือ C = W log(1 + P/N) บิตต่อวินาที (BSTJ 27, no. 4) สังเกตว่าข้อนี้เปิดทางให้อะไร พูดข้อความซ้ำสามครั้งคือใช้ความซ้ำซ้อนอย่างโง่ๆ ต้นทุนสามเท่าแลกกำไรนิดเดียว Shannon พิสูจน์ว่าความซ้ำซ้อนที่ใช้อย่าง*ฉลาด*ซื้อความน่าเชื่อถือที่เกือบสมบูรณ์แบบมาได้โดยแทบไม่เสียอัตราเลย แต่เขาไม่ได้บอกว่าทำอย่างไร บทพิสูจน์ของเขาแสดงว่ารหัสที่ดีมีอยู่จริง ด้วยการแสดงว่ารหัสที่หยิบมาแบบสุ่มน่าจะดี — บทพิสูจน์เชิงมีอยู่จริง (existence proof) ที่ยื่นโครงการก่อสร้างยาวห้าสิบปีใส่มือวิศวกร
The construction project. Richard Hamming had a personal stake. Working weekends on Bell Labs' relay computer in 1947, with no operator present, he would submit a job on Friday and return Monday to find that the machine had detected a card-reading error, dumped his work, and moved on. Twice in a row. "Dammit," he recalled thinking, "if a machine can find out that there is an error, why can't it locate where it is and change the setting of the relay from one to zero or zero to one?" (IEEE Computer Society). The answer became the Hamming codes (BSTJ 29, no. 2, April 1950: 147–160) — parity bits arranged so that the pattern of failed checks spells out the position of the flipped bit in binary. Detection had become correction.
โครงการก่อสร้างนั้น Richard Hamming มีเรื่องส่วนตัวค้างอยู่ ปี 1947 เขาทำงานเสาร์อาทิตย์กับเครื่องคำนวณแบบรีเลย์ของ Bell Labs โดยไม่มีเจ้าหน้าที่ควบคุมสักคน ส่งงานเข้าไปวันศุกร์ กลับมาวันจันทร์ก็พบว่าเครื่องจับข้อผิดพลาดในการอ่านบัตรได้ ทิ้งงานของเขา แล้วเดินหน้าต่อ สองครั้งติดกัน "แม่งเอ๊ย" เขาเล่าว่าคิดแบบนั้น "ถ้าเครื่องหาเจอว่ามีข้อผิดพลาดได้ ทำไมมันถึงหาตำแหน่งที่ผิดแล้วเปลี่ยนค่ารีเลย์จากหนึ่งเป็นศูนย์หรือศูนย์เป็นหนึ่งเองไม่ได้ล่ะ" (IEEE Computer Society) คำตอบกลายเป็น Hamming code (BSTJ 29, no. 2, April 1950: 147–160) — บิตพาริตี (parity bit) วางเรียงไว้จนรูปแบบของการตรวจสอบที่ล้มเหลวสะกดตำแหน่งของบิตที่พลิกออกมาเป็นเลขฐานสอง การตรวจจับ (detection) กลายเป็นการแก้ไข (correction)
Then the codes got good. Reed and Solomon's 1960 construction over finite fields (Journal of the SIAM 8: 300–304) survives bursts of damage rather than isolated flips, which is what deep space demanded: JPL launched Voyager 2 toward Uranus knowing its Reed–Solomon decoders did not yet exist, "gambl[ing] that by the time Voyager II would reach Uranus in 1986, decoding algorithms and equipment would be both available and perfected. They were correct!" (NASA TM 102162). Robert Gallager had meanwhile invented low-density parity-check codes in his 1960 MIT thesis, published them in 1962 (IRE Transactions on Information Theory 8: 21–28), and watched them vanish — too expensive to decode on the hardware of the day. They were rediscovered by MacKay and Neal in 1995–96, alongside the turbo codes of Berrou, Glavieux and Thitimajshima (Proc. IEEE ICC, 1993), and the wall Shannon had drawn was finally reached: by 2001 an irregular LDPC code came within 0.0045 decibels of capacity (Chung, Forney, Richardson & Urbanke, IEEE Communications Letters 5, 2001). Your phone uses both descendants — LDPC for 5G data channels, and Erdal Arıkan's polar codes, published in 2009 and standardized within a decade, for the control channels.
จากนั้นรหัสก็เก่งขึ้น การสร้างของ 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 เข้าเป็นมาตรฐานภายในสิบปี สำหรับช่องควบคุม
And the floor's silence is its leak. Everything above is indifferent to what a message says. Shannon's disclaimer was a precondition for the theory's power, not an oversight — but it means this floor can price the transmission of a diagnosis and of a spam message identically, and has nothing to say about which was worth sending. Every floor above pays for that silence in its own currency: cryptography (11) must add who sent it, databases (08) must add what it means, and machine learning (12) spends its whole existence trying to recover meaning from statistics — while quietly using Shannon's entropy as its loss function.
ความเงียบของชั้นนี้คือรอยรั่ว (leak) ของมันเอง ทุกอย่างข้างต้นไม่สนใจว่าข้อความพูดว่าอะไร คำปฏิเสธความรับผิดชอบของ Shannon เป็นเงื่อนไขที่จำเป็นต่อพลังของทฤษฎี ไม่ใช่การมองข้าม — แต่แปลว่าชั้นนี้ตั้งราคาการส่งผลวินิจฉัยโรคเท่ากับการส่งข้อความสแปม และพูดไม่ได้สักคำว่าอันไหนคุ้มที่จะส่ง ทุกชั้นเหนือขึ้นไปจ่ายค่าความเงียบนี้ด้วยสกุลเงินของตัวเอง — วิทยาการรหัสลับ (cryptography, บทที่ 11) ต้องเติมว่าใครเป็นคนส่ง ฐานข้อมูล (บทที่ 08) ต้องเติมว่ามันหมายความว่าอะไร และ machine learning (บทที่ 12) ใช้ชีวิตทั้งชีวิตไล่กู้ความหมายกลับจากสถิติ — พร้อมกับแอบใช้เอนโทรปีของ Shannon เป็น loss function
Connections
เชื่อมโยง
Beside this floor: 02, whose Ω(n log n) sorting bound is this chapter's counting argument in disguise — log₂(n!) is the number of bits needed to name one ordering. Above: 09, where TCP builds reliability out of an unreliable channel — the same bargain, made at a higher floor; 08, where compression and checksums guard stored data; 11, where a cipher's strength is counted in bits; 12, where a model that predicts the next token well is, by the argument above, a compressor.
ชั้นข้างเคียง: บทที่ 02 ซึ่งขอบล่าง Ω(n log n) ของการเรียงลำดับคือข้อโต้แย้งเรื่องการนับของบทนี้ที่แฝงตัวมา — log₂(n!) คือจำนวนบิตที่ต้องใช้ระบุลำดับหนึ่งแบบ ชั้นบน: บทที่ 09 ที่ TCP ก่อความน่าเชื่อถือขึ้นจากช่องสัญญาณที่ไม่น่าเชื่อถือ ข้อตกลงเดียวกัน ทำที่ชั้นสูงกว่า บทที่ 08 ที่การบีบอัดและ checksum เฝ้าข้อมูลที่จัดเก็บไว้ บทที่ 11 ที่ความแข็งแกร่งของ cipher นับกันเป็นบิต บทที่ 12 ที่โมเดลซึ่งทายโทเคนถัดไปได้ดี ตามข้อโต้แย้งข้างต้นก็คือตัวบีบอัดตัวหนึ่ง
Open questions
คำถามที่ยังเปิดอยู่
Shannon deliberately excluded meaning — and no accepted theory of semantic information has replaced what he set aside, though the question is now live again because language models make it practical. Is compression the same thing as understanding, or merely correlated with it? And on the physical side: how close to capacity is close enough to stop, given that the last fraction of a decibel now costs more energy in decoding than it saves in transmission?
Shannon ตัดความหมาย (meaning) ออกไปโดยตั้งใจ — และยังไม่มีทฤษฎีสารสนเทศเชิงความหมาย (semantic information) ที่ได้รับการยอมรับเข้ามาแทนสิ่งที่เขาวางทิ้งไว้ แม้คำถามนี้จะกลับมามีชีวิตอีกครั้งเพราะโมเดลภาษาทำให้มันใช้ได้จริง การบีบอัดคือสิ่งเดียวกับความเข้าใจ หรือแค่สัมพันธ์กันเฉยๆ และในแง่กายภาพ — ใกล้ความจุแค่ไหนถึงเรียกว่าใกล้พอที่จะหยุด ในเมื่อเดซิเบลเศษเสี้ยวสุดท้ายตอนนี้กินพลังงานในการถอดรหัสมากกว่าที่ประหยัดได้ตอนส่ง
Go deeper
อ่านต่อ
- Claude Shannon, "A Mathematical Theory of Communication," Bell System Technical Journal 27 (1948): 379–423, 623–656 — still the clearest exposition of its own ideas (PDF).
- David MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003 — free from the author's site, and the book that connects this floor to chapter 12 (inference.org.uk).
- Richard Hamming, "Error Detecting and Error Correcting Codes," Bell System Technical Journal 29, no. 2 (April 1950): 147–160 — the first working answer to Shannon's existence proof (scan).
- 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).