หลังจากพิจารณาคอมพิวเตอร์และการทำงานของมันแล้ว เราจะหันมาดูปัญหา การแทนข้อมูล—จะทำอย่างไร หรือถามว่าจะแทนข้อมูลที่เราต้องการประมวลผลอย่างไร ความหมายของสัญลักษณ์ขึ้นอยู่กับวิธีที่มันถูกประมวลผล — ไม่มีความหมายโดยตัวมันเองในบิตที่เครื่องใช้ ในภาษาสังเคราะห์ที่กล่าวถึงในบทที่ 4 เกี่ยวกับประวัติซอฟต์แวร์ การแยกคำสั่งออกเป็นส่วนๆ แทบจะเหมือนกันสำหรับทุกคำสั่ง และสิ่งนี้เป็นจริงสำหรับภาษาโปรแกรมส่วนใหญ่; “ความหมาย” ของคำสั่งใดๆ ถูกกำหนดโดยซับรูทีนที่สอดคล้องกัน。

เพื่อทำให้ปัญหาการแทนข้อมูลง่ายขึ้น ตอนนี้เราจะพิจารณาเฉพาะปัญหาการส่งข้อมูลจากที่นี่ไปยังที่นั่นเท่านั้น ซึ่งโดยเนื้อแท้เหมือนกับการส่งจากตอนนี้ไปยังตอนหลัง นั่นคือ storage (การเก็บข้อมูล). การส่งผ่านทางเวลาและทางพื้นที่เป็นปัญหาเดียวกัน โมเดลมาตรฐานของระบบแสดงใน Figure 10.1.

สรุป: Figure 10.1—Information system

เริ่มจากด้านซ้ายของ Figure 10.1 คือแหล่งข้อมูล เราไม่ลงรายละเอียดว่าแหล่งข้อมูลคืออะไร อาจเป็นสตริงของตัวอักษร ตัวเลข สมการทางคณิตศาสตร์ โน้ตดนตรี หรือสัญลักษณ์ที่ใช้แทนท่าทางการเต้น—ไม่ว่าแหล่งจะเป็นอะไร หรือ “ความหมาย” ที่ผูกกับสัญลักษณ์เหล่านั้นเป็นอย่างไร ก็ไม่อยู่ในขอบเขตของทฤษฎีนี้ เราสมมติเพียงว่ามีแหล่งข้อมูล และเพียงการสมมตินั้นก็ให้เราได้ทฤษฎีทั่วไปที่ทรงพลังและนำไปประยุกต์ใช้ได้กว้าง การละรายละเอียดเฉพาะเจาะจงนี่เองที่ขยายขอบเขตการใช้งาน

เมื่อในช่วงปลายทศวรรษ 1940 C.E. Shannon สร้าง information theory (ทฤษฎีสารสนเทศ) มีความเห็นทั่วไปว่าเขาน่าจะเรียกมันว่า communication theory (ทฤษฎีการสื่อสาร) แต่เขายืนยันใช้คำว่า “information” และคำนี้เองก็เป็นแหล่งของทั้งความสนใจและความผิดหวังในทฤษฎี ผู้คนอยากได้ทฤษฎีของ “information” แต่จริงๆ แล้วมันเป็นเพียงทฤษฎีของสตริงของสัญลักษณ์เท่านั้น อีกครั้ง เราสมมติเพียงว่ามีแหล่งข้อมูลดังกล่าว และเราจะเข้ารหัสมันเพื่อการส่งต่อ

ตัวเข้ารหัสแบ่งเป็นสองส่วน ส่วนแรกเรียกว่า source encoding (การเข้ารหัสต้นทาง) ซึ่งตามชื่อหมายความว่าจะปรับให้เข้ากับแหล่ง—แหล่งต่างๆ อาจต้องการรูปแบบการเข้ารหัสที่ต่างกันได้

ส่วนที่สองของกระบวนการเข้ารหัสเรียกว่า channel encoding (การเข้ารหัสช่องสื่อสาร) และมันถูกปรับให้เข้ากับช่องทางที่จะส่งสัญลักษณ์ที่เข้ารหัส ดังนั้นในลักษณะนี้ ด้วยอินเทอร์เฟซร่วม เราสามารถมีแหล่งข้อมูลหลากหลายที่ถูกเข้ารหัสไปยังอินเทอร์เฟซร่วมก่อน แล้วข้อความจะถูกเข้ารหัสต่อเพื่อให้เหมาะกับช่องทางเฉพาะที่ใช้อยู่

ต่อไป หากมองไปทางขวาใน Figure 10.1 ช่องสื่อสารถือว่ามี “random noise added” เสียงรบกวนทั้งหมดของระบบถูกรวมไว้ที่นี่ สมมติว่าตัวเข้ารหัสสามารถจำแนกสัญลักษณ์ที่เข้ามาได้อย่างถูกต้องโดยไม่มีข้อผิดพลาด และสมมติด้วยว่าเครื่องถอดรหัสทำงานโดยไม่มีข้อผิดพลาดเช่นกัน นี่เป็นอุดมคติ แต่สำหรับวัตถุประสงค์เชิงปฏิบัติหลายกรณี มันค่อนข้างใกล้เคียงกับความเป็นจริง

ถัดมา การถอดรหัสทำในสองขั้นตอน จากช่องสื่อสารไปยังมาตรฐาน แล้วจากมาตรฐานกลับไปยังรหัสต้นทาง สุดท้ายส่งไปยังซิงก์หรือปลายทาง อีกครั้ง เราไม่ถามว่าซิงก์ทำอะไรกับมัน

ตามที่กล่าวไว้ก่อนหน้านี้ ระบบนี้คล้ายกับการส่งสาร เช่น ข้อความโทรศัพท์จากฉันถึงคุณ โปรแกรมวิทยุหรือทีวี และกรณีอื่นๆ เช่น ตัวเลขในรีจิสเตอร์ของคอมพิวเตอร์ที่ถูกส่งไปยังอีกที่หนึ่ง อีกครั้ง การส่งผ่านทางอวกาศมีลักษณะเหมือนการส่งผ่านทางเวลา นั่นคือ storage (การเก็บข้อมูล) หากคุณมีข้อมูลและต้องการใช้มันในภายหลัง คุณจะเข้ารหัสเพื่อเก็บและเก็บมันไว้ เมื่อคุณต้องการค่อยถอดรหัสขึ้นมาใช้งานในภายหลัง ในระบบการเข้ารหัสมีระบบที่เป็นตัวตน (identity) ซึ่งไม่ได้เปลี่ยนการแทนข้อมูลเลย

ความแตกต่างพื้นฐานระหว่างทฤษฎีประเภทนี้กับทฤษฎีปกติในฟิสิกส์คือการสมมติไว้แต่แรกว่าจะมี “noise” เนื่องจากข้อผิดพลาดจะเกิดขึ้นในอุปกรณ์ใดๆ แม้ในกลศาสตร์ควอนตัม noise จะปรากฏขึ้นในขั้นตอนหลังในรูปของหลักความไม่แน่นอน (uncertainty principle) ไม่ใช่เป็นสมมติฐานเริ่มต้น และในทุกกรณี “noise” ในทฤษฎีข้อมูลไม่เหมือนกับความไม่แน่นอนใน QM

เพื่อความสะดวก เราจะสมมติว่ารูปแบบการแทนข้อมูลในระบบเป็นแบบไบนารี รูปแบบอื่นๆ ก็จัดการได้ในลักษณะเดียวกัน แต่ความทั่วไปนั้นไม่คุ้มกับการเพิ่มสัญกรณ์

เริ่มจากสมมติว่าสัญลักษณ์ที่เข้ารหัสมีความยาวตัวแปร เช่นเดียวกับรหัสมอร์สแบบคลาสสิกที่ใช้จุดและขีด ตัวอักษรที่พบบ่อยจะสั้น ส่วนที่หายากจะยาว วิธีนี้เพิ่มประสิทธิภาพของรหัส แต่ควรสังเกตว่ามอร์สเป็นรหัสเตนาร์ (ternary) ไม่ใช่ไบนารี เพราะมีช่องว่างนอกเหนือจากจุดและขีด หากสัญลักษณ์ของรหัสทั้งหมดมีความยาวเท่ากัน เราเรียกว่าเป็น block code

คุณสมบัติพื้นฐานข้อแรกที่ต้องการคือความสามารถในการถอดรหัสข้อความได้อย่างเฉพาะเจาะจงเมื่อไม่มี noise ถูกเพิ่ม — อย่างน้อยดูเหมือนจะเป็นคุณสมบัติที่พึงประสงค์ แม้ในบางกรณีอาจละได้เล็กน้อย สิ่งที่ส่งคือสตรีมของสัญลักษณ์ซึ่งผู้รับเห็นเป็นเส้นของ 0s และ 1s เราเรียกสัญลักษณ์สองตัวติดกันว่า second extension สามตัวว่า third extension และโดยทั่วไปถ้าเราส่ง n สัญลักษณ์ ผู้รับจะเห็นการขยายที่เป็น n_th ของสัญลักษณ์พื้นฐาน ไม่ทราบค่า _n ผู้รับต้องแบ่งสตรีมออกเป็นหน่วยที่แปลได้ และคุณต้องการให้การแบ่งส่วนนั้นเฉพาะเจาะจงเพื่อกู้ข้อความต้นทางที่ฉันส่งให้คุณ

จะใช้พยัญชนะชุดเล็กสำหรับตัวอย่างการเข้ารหัส; โดยทั่วไปพยัญชนะมีขนาดใหญ่กว่า โดยปกติพยัญชนะในภาษาเชิงธรรมชาติจะอยู่ระหว่าง 16 ถึง 36 ตัว ทั้งตัวพิมพ์ใหญ่และพิมพ์เล็ก พร้อมด้วยตัวเลขและเครื่องหมายวรรคตอนมากมาย เช่น ascii มี 128 = 27 สัญลักษณ์ในอักษร

มาลองพิจารณารหัสพิเศษหนึ่งที่มีสัญลักษณ์สี่ตัว _s_1, _s_2, _s_3, _s_4:

ถ้าคุณรับ

สรุป: what will you do? Is it _s_1_s_1_s_4, or is it _s_2_s_4? You cannot tell; the code is not uniquely decodable, and hence is unsatisfactory.

ในทางกลับกัน รหัส

สรุป: is uniquely decodable. Let us take a random string and see what you would do to decode it. You would construct a decoding tree of the form shown in Figure 10.2. The string

สามารถแยกออกเป็นสัญลักษณ์ได้ดังนี้

ทุกครั้งที่คุณมาถึงจุดแตกแขนง (node) ให้อ่านสัญลักษณ์ถัดไป และเมื่อถึงใบไม้ของต้นไม้ให้ส่งสัญลักษณ์ที่สอดคล้องออกมา แล้วกลับไปที่จุดเริ่มต้น.

สรุป: > Each time you come to a branch point (node) you read the next symbol, and when you come to a leaf of the tree you emit the corresponding symbol and return to the start.

เหตุที่ต้นไม้นี้เป็นได้เพราะไม่มีสัญลักษณ์ใดเป็น prefix ของอีกสัญลักษณ์หนึ่ง ดังนั้นคุณจึงรู้เสมอว่าเมื่อใดที่สัญลักษณ์ปัจจุบันสิ้นสุดลง

สรุป: The reason why this tree can exist is that no symbol is the prefix of any other, so you always know when you have come to the end of the current symbol.

หัวข้อถัดไปคือ instantaneously decodable codes. เพื่อให้เห็นว่าคืออะไร ลองพิจารณารหัสข้างต้นที่ตัวเลขถูกกลับด้าน

สรุป: The next topic is instantaneously decodable codes. To see what this is, consider the above code with the digits reversed end for end.

เรามาพิจารณาสองตัวอย่างของการเข้ารหัสสัญลักษณ์ชุดเดียวกัน s_i การเข้ารหัสแรกคือ

สรุป: We now turn to two examples of encoding the same symbols, _s_i. The first encoding is

สรุป: which will have the decoding tree shown in Figure 10.3.

การเข้ารหัสที่สองมาจากแหล่งเดียวกัน แต่เรามี

โดยมีต้นไม้แสดงใน Figure 10.4

สรุป: with the tree shown in Figure 10.4.

สรุป: Figure 10.4—Second decoding tree for _s_1 through _s_5.

โดยที่ p_i คือความน่าจะเป็นของสัญลักษณ์ s_i และ l_i คือความยาวของสัญลักษณ์ที่เข้ารหัส สำหรับรหัสที่มีประสิทธิภาพ ค่านี้ L ควรจะเล็กที่สุดเท่าที่จะทำได้ หาก _p_1 = 1/2, _p_2 = 1/4, _p_3 = 1/8, _p_4 = 1/16, และ _p_5 = 1/16 แล้วสำหรับรหัส #1 เราได้

และสำหรับรหัส #2

สรุป: and for code #2

หากคำศัพท์ส่วนใหญ่มีความน่าจะเป็นในการเกิดเท่ากัน การเข้ารหัสที่สองจะมีความยาวเฉลี่ยน้อยกว่าการเข้ารหัสแรก ให้ p_i = 1/5 สำหรับทุก _i ดังนั้นรหัส #1 มี

สรุป: If most of the code words are of the same probability of occurring, then the second encoding will have a smaller average code length than the first encoding. Let p_i = 1/5 for all _i. Then code #1 has

สรุป: while code #2 has

เราจะหันไปที่ Kraft inequality ซึ่งให้ขีดจำกัดความยาว l_i ของสัญลักษณ์รหัส ในฐาน 2, อสมการของ Kraft คือ

สรุป: We now turn to the Kraft inequality, which gives a limit on the lengths _l_i of the code symbols of a code. In base 2, the Kraft inequality is

สรุป: When examined closely, this inequality says there cannot be too many short symbols or else the sum will be too large.

สรุป: Figure 10.5—The trivial cases for Kraft inequality.

สรุป: To prove the Kraft inequality for any instantaneously uniquely decodable code we simply draw the decoding tree, which of course exists, and apply mathematical induction. If the tree has one or two leaves, as shown in Figure 10.5, then there is no doubt the inequality is true. Next, if there are more than two leaves we decompose the trees of length m (for the induction step) into two trees, and by the induction suppose the inequality applies to each branch of length m – 1 or less. By induction the inequality applies to each branch, giving K' and K" for their sums. Now when we join the two trees each length increases by 1, hence each term in the sum gets another factor of 2 in the denominator, and we have

อสมการของ Kraft ใช้ได้กับรหัสที่ไม่ใช่แบบทันทีทันใด ตราบเท่าที่พวกมันถอดรหัสได้เฉพาะเจาะจง

สรุป: The Kraft inequality applies to non-instantaneous codes, provided they are uniquely decodable.

โดยที่ N_k คือจำนวนสัญลักษณ์ที่มีความยาว k และผลรวมเริ่มจากความยาวขั้นต่ำของการขยายที่เป็น n_th ของสัญลักษณ์ ซึ่งคือ _n และสิ้นสุดที่ความยาวสูงสุด nl โดยที่ l คือความยาวสูงสุดของสัญลักษณ์รหัสใดๆ แต่จากความสามารถในการถอดรหัสเฉพาะเจาะจงต้องเป็นว่า N_k ≤ 2^k ผลรวมจึงกลายเป็น

สรุป: where N_k is the number of symbols of length _k, and the sum starts from the minimum length of the n_th extension of the symbols, which is _n, and ends with the maximum length nl, where l is the maximum length of any single code symbol. But from the unique decodability it must be that N_k ≤ 2_k. The sum becomes

เนื่องจากเราเห็นแล้วตามที่กล่าวว่าจะทำให้เห็นว่า instantaneous decodability ไม่เสียอะไร เราจึงยึดรหัสที่ถอดรหัสได้ทันทีและละเว้นรหัสที่ถอดรหัสได้เฉพาะเจาะจงเท่านั้น—ความทั่วไปของพวกมันไม่ได้ให้ประโยชน์ใดๆ

สรุป: Since we now see, as we said we would show, that instantaneous decodability costs us nothing, we will stick to them and ignore merely uniquely decodable codes—their generality buys us nothing.

แล้วความยาว 1, 2, 2, 3 ล่ะ? เรามี

ดังนั้นไม่! มีความยาวสั้นเกินไปจำนวนมาก

สรุป: hence no! There are too many short lengths.

เรามีผลรวมของ Kraft

สรุป: We have the Kraft sum

ถ้าผลรวมของ Kraft น้อยกว่า 1 แสดงว่ามีความสามารถในการสื่อสารส่วนเกิน เพราะสามารถเพิ่มสัญลักษณ์อีกตัว หรือทำให้สัญลักษณ์บางตัวสั้นลงได้ และด้วยเหตุนี้ความยาวเฉลี่ยของรหัสจะน้อยลง

โปรดสังเกตว่าหากอสมการของ Kraft เป็นจริง ไม่ได้หมายความว่ารหัสนั้นถอดรหัสได้เฉพาะเจาะจง เพียงแต่มีรหัสที่มีความยาวสัญลักษณ์ดังกล่าวซึ่งถอดรหัสได้เฉพาะเจาะจง หากคุณกำหนดตัวเลขฐานสองตามลำดับตัวเลข โดยแต่ละตัวมีความยาวที่ถูกต้อง l_i ในบิต คุณจะพบรหัสที่ถอดรหัสได้เฉพาะเจาะจง ตัวอย่างเช่นให้ความยาว 2, 2, 3, 3, 4, 4, 4, 4 เรามีสำหรับอสมการของ Kraft

สรุป: Note if the Kraft inequality is met, that does not mean the code is uniquely decodable, only there exists a code with those symbol lengths which is uniquely decodable. If you assign binary numbers in numerical order, each having the right length _l_i in bits, then you will find a uniquely decodable code. For example, given the lengths 2, 2, 3, 3, 4, 4, 4, 4, we have for Kraft’s inequality

ฉันเห็นว่าจำเป็นต้องชี้ให้เห็นถึงวิธีที่เราจริงๆ ทำเมื่อสื่อสารแนวคิด ดังนั้นฉันอยากจะส่งความคิดจากหัวของฉันไปยังหัวของคุณ ฉันเปล่งคำบางคำซึ่งคุณควรจะรับความคิดนั้นได้ แต่ถ้าคุณพยายามส่งความคิดนั้นไปยังเพื่อน คุณอาจใช้คำที่ต่างออกไปอย่างแน่นอน ในความหมายหนึ่ง “ความหมาย” ไม่ได้อยู่ในคำเฉพาะที่ฉันใช้ เพราะคุณอาจใช้คำต่างกันเพื่อสื่อความคิดเดียวกันอย่างแน่นอน ดูเหมือนคำต่างกันสามารถสื่อ “information” เดียวกันได้ แต่ถ้าคุณบอกว่าไม่เข้าใจข้อความ มักจะมีชุดคำต่างๆ ถูกใช้โดยแหล่งในครั้งที่สองหรือแม้กระทั่งครั้งที่สามของการนำเสนอนั้น ดังนั้นอีกครั้ง ในบางแง่ “ความหมาย” ไม่ได้อยู่ในคำที่ฉันใช้จริงๆ แต่คุณใส่ข้อมูลประกอบจำนวนมากเมื่อคุณแปลจากคำของฉันไปสู่แนวคิดที่คุณคิดว่าฉันพูดไว้ในหัวของคุณ

สรุป: I feel it necessary to point out how things are actually done by us when we communicate ideas. Thus I want, at this time, to get an idea from my head into yours. I emit some words from which you are supposed to get the idea. But if you later try to transmit this idea to a friend you will emit, almost certainly, different words. In a real sense, the “meaning” is not contained in the specific words I use, since you will probably use different words to communicate the same idea. Apparently different words can convey the same “information.” But if you say you do not understand the message then usually a different set of words is used by the source in a second or even third presentation of the idea. Thus again, in some sense, the “meaning” is not contained in the actual words I use, but you supply a great deal of surrounding information when you make the translation from my words to your idea of what I said inside your head.

สรุป: We have learned to “tune” the words we use to fit the person on the receiving end; we to some extent select according to what we think is the channel noise, though clearly this does not match the model I am using above, since there is significant noise in the decoding process, shall we say. This inability of the receiver to “hear what is said” by a person in a higher management position but to hear only what they expect to hear is, of course, a serious problem in every large organization, and is something you should be keenly aware of as you rise towards the top of the organization. Thus the representation of information in the formal theory we have given is mirrored only partly in life as we live it, but it does show a fair degree of relevance outside the formal bounds of computer usage where it is highly applicable.