310200-Introduction to Computer Systems

เนื้อหาที่ใช้สอบ - ทุกเรื่องที่มีการสอนในชั้นเรียน เน้นที่เนื้อหาหลังสอบกลางภาค

ประกอบด้วย
... - การบีบอัดข้อมูลแบบต่างๆ
Compression :
Data1 -----Compression------>Data2
Data2 -----Discompression--->Data3
ถ้า Data3LZ77
-Triple ×××××× (x,y,z)
x : ตำแน่งที่นับจาขวาไปซ้าย
y : จำนวนตัวที่ต้องตัดมาเพิ่มข้างขวาข้อมูล โดยนับจากตำแน่งที่ได้นับช้ายไปขวา
z : ค่าตัวเดียวที่ต้องเพิ่มสุดทัายข้างขวาขัอมูล

---

- หน่วยเก็บข้อมูลความจุสูง (Mass storage) หรือหน่วยความจำรอง เน้นที่ HDD
HDD : Hard Disk Drive
-ความจุสูงมาก
-อยู่ใน Harddisk มีจากแม่เลข mixed by metal : Fe,Co,Ni,Sn ที่เก็บข้อมูลเป็น Sector และ Track
-Platter : จากแม่เลขใน HDD **ถ้ามี Platter มาก แล้วการคนหาข้อมูลจาก Sector และ Track ก็ได้เร็วขื้น
-Sector is the smallest area on platter which is 1 sector = 512 byte (HHD of standard PC)
-มีความรอบคงที่ Constance RPM (Round Per Minute)
-(รีม)Track อยู่ตรงกันของ Platter เป็นวงกลม หลายวง ที่มี่ปริมาตรไม่เหมือนกัน
-[รีมใน กับ รีมนอก] Track-in's round speed < Track-out's round speed -Track-in มีความหน้าแน่นสูง และ ความเสียหายขัอมูลสูง High Data lossing -การทำบันทึกขัอมูลไปอยู่ใน Sector ต้องมีห้ว อาน/เขียน เลือนมาบันทึกบน Track ที่มี Sector ว่าง -เลือน อาน/เขียน ข้าบ 1Track ใช้เวลา 10^-3 sec = 1ms ---> Seek time ดังนั้น ถ้าข้อมูลอยู่ใน Track
เดียวกัน และใกล้กัน ทำให้ประยัดเวลาในการคนหาข้อมูลนั้น
-ใช้โปรแกรม "Defragmentor" เพื่อ Repair sector และก่อนการทำวิธีนี้ต้อง Backup Data first for avoid losing data while Defragmentor if the electric was switched off .
-การคนหาข้อมูลจาก Sector อยู่ใน Track หนึ่งที่ห้วอาน/เขียนบน Track นั้นด้วย คือมีการเกิดกรณี 2อย่างคือ
Best case : หน้าที่วิงอยู่ชิ่ดข้างหลัง ห้วอาน/เขียน (sector)-----> |(ห้วอาน/เขียน)
Worst case : หน้าที่วิงอยู่ผ่าน หรือ บน อาจจะตรงกันเลย ห้วอาน/เขียน (sector)---|--> ----|>
-if RPM faster ---> Rotational delay slower
-ลัษณะของHHDที่ควรดู
+ มี Platter หลายชั้น ทำให้การใช้งายดีขื้น
+ความจุใหญ่ large of capacity
+Seek time (ms) เวลาที่ Track รอบได้หนึ่งรอบ
+Rotational delay
+Controller card [add more]
+Transfer rate : อัตราการรับส่งข้อมูล
+เส้นเชื่อมต่อ IDE , ATA , SATA -----> Cable connection

การแบ่ง Track & Sector
1* จัดจำนวนแม่เหล้า ---- Hard Format : [ HHD was done since factory ]
2*แบ่ง Partition แบ่งได้หลาย partitions -----> Logical drive for store Data.
-----> Primary drive for store OS.
3*each partition : create file system .
.MS --> FAT-32 , FAT-16 , NTFS{lose capacity high} <"format">
.Unix --> FAT-32 , FAT-16 , NTFS <"mkfs">

---

- แฟ้มภาพและการบีบอัดแฟ้มภาพ
RGB : Red Green Blue ----> mixed = 16 Milion color ----> human's eye able to see !! :)
[BMP] Bit map :
- 3 byte(24bit)/px
- Size = (width * length) px * 3byte/px= ? byte
[Gif] Graphic Interchange Format
-Color palette has 256 color with using no mixed color
-1byte/px
-Size = (width * length) px*1byte/px +3*256 = ? byte
-Lossy Compression
[JPG] The Joint Photographic Expert Group {In Unix ==> JPEG}
-ISO color : Internetional Standard Organization
-Relative encoding compression used ==> variable-length code
-Loseless Compression
-Use as Set : 1Set = 6byte / 4px ; 1Set ===> Pixel brightness & Pixel color
-1 Set : compressed as 4 px there are : 4 value of px-brightness & 2 px-color = 6value
-Size = (width * length) px * 6byte / 4 px = ? byte

---

- สถาปัตยกรรมแบบ John Von Neumann
-แนวความคิด : ออกแบบคำสั่งให้เป็นรหัสในรูปของเลขฐานสอง and จัดเก็บในหน่วยความจำได้
-กำหนดให้คำสั่งในโปรแกรมที่จะใช้ในการประมวลผลมีลักษณะเช่นเดียวกับข้อมูลที่ต้องการประมวลผล
1.Fetch : จากนั้นจึงทำการออกแบบให้หน่วยควบคุมสามารถอ่านรหัสคำสั่งดังกล่าวนี้จากหน่วยความจำ
2.Decode : ถอดรหัส เพื่อเลือกวงจรที่จะใช้ดำเนินการกับข้อมูล and ดำเนินการกับข้อมูลนั้น
3.Execute : การเปลี่ยนแปลงวิธีการทำงานหรือโปรแกรมจะทำได้ง่ายขึ้นโดยการบรรจุโปรแกรมใหม่ลงแทนที่โปรแกรมเก่าในหน่วย ความจำ แทนที่จะใช้การเชื่อมต่อวงจรแบบเดิม
**Fetch , Decode ,Execode ====> Stored-program Concept [ for nowday computer ]
Stored-program Concept :
==> ชัดเจน
==> ตรงไปตรงมา
------->จนทำให้ผู้คนในยุคต่อมาสงสัยว่า เพราะเหตุใดผู้สร้างคอมพิวเตอร์ในสมัยก่อนหน้านี้จึงนึกไม่ถึง ที่เป็นเช่นนี้เพราะว่า ในระยะแรกๆทุกคนมีความคิดเหมือนกันว่า Program และ Data เป็น "อะไร" (entity)
Processing :
::::: Program ------> Control Unit "CU" :: หน่วยควบคุม
::::: Data-----------> RAM :: หน่วยความจำ

---

ภาษา Assembly
เนื่องจากคำสั่งที่หน่วยประมวลผลสามารถดำเนินการได้ เป็นคำสั่งที่มีการเข้ารหัสในรูปของเลขฐานสอง หรือเรียกว่าคำสั่งภาษาเครื่อง คำสั่งในลักษณะนี้เป็นคำสั่งที่ยากต่อการจดจำ, ทำความเข้าใจ และเขียนโปรแกรม เช่นคำสั่งของหน่วยประมวลผลกลางในตระกูล 80x86 คำสั่งหนึ่งคือ
00000001 11010000
เป็นคำสั่งกำหนดให้หน่วยประมวลผลทำการบวกค่าในเรจิสเตอร์สองตัวที่ระบุ และเก็บผลบวกที่ได้ไว้ที่เรจิสเตอร์ตัวแรก คำสั่งเช่นนี้ถึงแม้ว่าจะใช้เลขฐานสิบหก คือ 01D016 แทนเลขฐานสองก็ไม่ช่วยให้เกิดความชัดเจนขึ้นได้แต่อย่างใด ดังนั้นเพื่อให้สามารถเขียนโปรแกรมได้ง่ายจึงมีการกำหนดสัญลักษณ์ในลักษณะเป็นชื่อย่อขึ้นใช้แทนคำสั่งและข้อมูล เรียกว่า Mnemonic โดยแยกเป็นสัญลักษณ์แทนคำสั่ง เรียกว่า Opcode, และกำหนดสัญลักษณ์แทนข้อมูล (เรจิสเตอร์และตำแหน่งในหน่วยความจำ) เพื่อใช้เป็น Operand ของคำสั่ง เช่น กำหนดให้ใช้สัญลักษณ์ ADD แทนคำสั่งบวก และกำหนดให้ใช้ชื่อ AX และ DX แทนชื่อเรจิสเตอร์ ดังนั้นคำสั่ง
00000001 11010000
จึงแทนได้ด้วยสัญลักษณ์
ADD AX, DX
คำสั่งในลักษณะนี้เรียกว่าคำสั่งภาษา Assembly โดยมีคำสั่ง ADD ทำหน้าที่เป็น Opcode ค่าในเรจิสเตอร์ AX เป็นตัวตั้ง และค่าในเรจิสเตอร์ DX เป็นตัวบวก กล่าวอีกนัยหนึ่งคือ AX และ DX ทำหน้าที่เป็น Operand ของคำสั่ง ADD เมื่อนำคำสั่งในลักษณะนี้มารวมกัน จะได้โปรแกรมภาษา Assembly โปรแกรมนี้หน่วยประมวลผลไม่สามารถทำงานได้โดยตรง จึงต้องมีการแปลโปรแกรมภาษา Assembly เป็นภาษาเครื่องที่สมนัยกันเสียก่อนโดยใช้ตัวแปลภาษา Assembly ซึ่งชื่อเรียกเฉพาะว่า Assembler และด้วยเหตุที่ชุดคำสั่งสำหรับหน่วยประมวลผลต่างรุ่นต่างยี่ห้อมีความแตกต่างกัน ดังนั้น Assembler ของหน่วยประมวลผลจึงแตกต่างกันออกไป และไม่สามารถใช้ทดแทนกันได้
ในการอธิบายในส่วนต่อไปจะใช้คำสั่งภาษา Assembly แทนคำสั่งภาษาเครื่อง และ

---

- หน่วยประมวลผลกลาง CPU
-คำสั่งภาษาเครื่องที่หน่วยประมวลผลกลางแต่ละตัวสามารถถอดรหัสได้มีจำนวนไม่มากนัก คำสั่งที่มีทั้งหมดของหน่วยประมวลตัวใดตัวหนึ่ง เรียกว่าชุดคำสั่ง (Instruction set)
-CISC : Complex Instruction Set Computing ====> Intel Company (Pentium)
+ดีควรสามารถทำงานกับคำสั่งได้เป็นจำนวนมาก Lots of intructions
+จะมีคำสั่งบางส่วนซ้ำซ้อนกัน Some intructions are complex
+นำคำสั่งมาเขียนเป็นโปรแกรมทำได้ง่ายกว่า bring instruction to write program easily
+Normal , Heat increasing faster than RISC
-RISC : Reduced Instruction Set Computing ====> IBM , Motorola , Apple Computer Company ============(PowerPC)==============
+คำสั่งภาษาเครื่องน้อย
+เฉพาะคำสั่งเท่าที่จำเป็นเท่านั้น
+ใช้งานได้ดี เร็ว และอย่างมีประสิทธิภาพ ใช้นานไม่ค่อยรอน ไม่ซ้ำซ้อน วงจรน้อย Good , Fast , Effectly , Cool ,
Machine Language ===> 3 part are : Data transfer , Arithmetic/Logic , Control
การทำงาน
----Fetch--->Decode---->Execute----->Fetch---............
คำสั่ง
-CISC
-RISC

- โปรแกรมและโพรเซส; โครงสร้างและการทำงาน
- ระบบปฏิบัติการ; ชนิด ความสำคัญ องค์ประกอบและการทำงาน

ลักษณะข้อสอบ
- เป็นข้อสอบอัตนัย ตอบคำถามโดยการอธิบาย จำนวน 20 ข้อ คะแนนเต็ม 60 คะแนน
คำแนะนำ - ก่อนตอบ ศึกษาความต้องการของคำถามให้ดี พยายามคิดถึงเรื่อง
ที่เกี่ยวข้อง เขียนทุกเรื่องที่นึกได้ พยายามจัดกลุ่ม เรียบเรียง แล้ว
ค่อยลงมือเขียนคำตอบจริง ริมกระดาษด้านซ้ายขวาของข้อสอบ
ใช้ทดได้

หมายเหตุ
คะแนนสอบกลางภาคยังไม่เสร็จ และคงไม่เสร็จจนถึงวันสอบ มีงานอื่นแทรกเข้ามามาก



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

1. ในกรณีที่ต้องการเขียนข้อมูลจำนวนมากลงในจานแม่เหล็กที่ใช้ประกอบด้วยด้วยจานหลายจาน ควรเขียนข้อมูล
ให้เต็มแผ่นหนึ่งก่อนแล้วค่อยเขียนลงในแผ่นต่อไป หรือควรเขียนให้เต็ม cylinder หนึ่งก่อนแล้วค่อยเขียนใน  cylinder
ถัดไป จงอภิปราย พร้อมให้เหตุผลประกอบ
::การเขียนข้อมูลจำนวนมากลงในจานแม่เหล็กที่ใช้ประกอบด้วยหลายจาน ควรเขียนข้อมูลให้เต็ม cylinder หนึ่งก่อนแล้วค่อยเขียนใน cylinder ถัดไป
  เพราะว่า ห้วอานห้วเขียนแต่ละจานเลือนมาอานข้อมูลตรงกัน​ cylinder ถ้าข้อมูลที่เขียนอยู่ใน cylinder เดียวกัน จะทำให้การอานมีการสะดวก และ   เร็วขื้น
2. โปรแกรมประยุกต์สำหรับจองที่นั่งของสายการบินซึ่งต้องมีการปรับปรุงข้อมูลอยู่เสมอ
 ควรใช้สื่อข้อมูลความจุสูงชนิดใดในการดำเนินการ จงอธิบายพร้อมให้เหตุผลประกอบอย่างชัดเจน  ?????????????
3. ในบางครั้งเมื่อทำการพิมพ์เอกสารเพิ่มเติมอีกหนึ่งบรรทัดโดยใช้โปรแกรมประมวลคำ (word processor)
เมื่อทำการจัดเก็บปรากฏว่าขนาดของแฟ้มยังมีขนาดคงเดิม แต่ในบางครั้งการพิมพ์ตัวอักษรเพิ่มลงไปเพียงตัวเดียว ??????????????
กลับทำให้แฟ้มมีขนาดใหญ่ขึ้นมาก จงอธิบายปรากฏการณ์ที่เกิดขึ้นดังกล่าวนี้
4. รหัส ascii ของอักษรตัวพิมพ์ใหญ่ (uppercase) และอักษรตัวพิมพ์เล็ก (lowercase) 
ในภาษาอังกฤษมีความสัมพันธ์กันหรือไม่ อย่างไร
ในรหัส ascii เป็นเลขฐานสอง
a = 01 0 00001    A = 01 1 00001
b = 01 0 00010    B = 01 1 00010
.             .
.             .
.             .
.             .
z = 01 0 11010     Z = 01 1 11010
สรุปว่า 
ความสัมพันธ์ของ uppercase & lowercase คือมีความแตต่างกันตรงบิตตำแน่งที่ 6 คือ upercase มีค่าเป็น 1 & lowercase มีค่าเป็น 0
5. การจัดเก็บโดยใช้รหัส ascii ของตัวเลข และการจัดเก็บโดยใช้เลขฐานสอง (Binary notation) 
สามารถจัดเก็บค่าของจำนวนได้สูงสุดเท่ากันหรือไม่ หากไม่เท่ากันแตกต่างกันอย่างไร จงอธิบาย
6. จงเปรียบเทียบจุดเด่น และ จุดด้อย ของการแทนภาพแบบ Bit map และ vector 
 Bit map : 
  -ทำให้รูปภาพไม่ชัดเหมือนเดิม เมือมีการ​ Zooming image หรือ การ Increassing size of image
 Vector : 
  -รักษาความส้วยและชัดของรูปภาพ เมือมีการ​ Zooming image หรือ การ Increassing size of image
7. จงเข้าหรัสของข้อมูลนี้ด้วยวิธีการ LZ77 (ให้ถือว่าข้อความที่ต้องการให้เข้ารหัส มีตัวอักษรต่องเนื่องกันไป
ไม่มีวรรค เครื่องหมายเว้นวรรคที่แทรกไว้ทุก 4 ตัวอักษร เพื่อให้อ่านและตรวจสอบได้ง่าย 
  bbab bbaa baba abab aaba baa a
==>bbab bbaa baba aba(10,8,a)
==>bbab bbaa ba(5,4,a) (10,8,a)
==>bbab bba (5,2,a)(5,4,a) (10,8,a)
==>bbab (4,2,a) (5,2,a)(5,4,a) (10,8,a)
8. ภาพขนาด 1024*1024 จุดภาพ ทำการบีบอัดโดยใช้วิธีการ GIF จะได้ภาพที่มีขนาดเท่าใด
[GIF] ==> Size = 1024*1024 px * 1byte /px + 3*256byte =2^20+768 byte ~ 1.001MB
และในกรณีที่ใช้วิธีการ JPEG จะได้ภาพที่มีขนาดเท่าใด จงแสดงวิธีการคำนวนโดยชัดเจน
[JPEG] Size = 1024*1024 px * 6 byte / 4 px = 1.5*2^20 byte =1.5 MB
9. จงอธิบายหลักการทั่วไปของการบีบอัดข้อมูลโดยใช้วิธีการตามมาตรฐานของ JPEG baseline standard มาพอเข้าใจ ?????????????

แบบฝึกหัดเรื่อง Hamming code
1. ตัวอักษร c มีรหัส ascii เป็น 0110 0011 (ฐานสอง) หรือ 63 (ฐานสิบหก)หากนำข้อมูลเฉพาะ
    7 บิตล่างคือ 110 0011 มาเข้ารหัสสร้างเป็น frame ข้อมูลขนาด 11 บิต โดยใช้ Hamming code 
    ชนิด 7/11 จงแสดง frame ข้อมูลที่ได้จากการเข้ารหัส
::: Hamming code ชนิด 7/11 คือมีการเพิ่มให้ 4 บิตอยู่ในตำแน่ง 1 2 4 8
==> 110 _ 001_1 _ _
---->บีตที่มีค่าเป็น1 คือ ตำแน่งที่ 
3   = 0011 
5   = 0101
10 = 1010       [ XOR ]
11 = 1011
------------
          0111  ====>เอาไปแทนตำแน่งที่ว่าง    ได้ 110[0]001[1]1[1][1] = 1100 0011 111
2. ผู้รับได้รับ frame ข้อมูลที่มีการเข้ารหัสแบบ Hamming code ชนิด 7/11 เป็น 110 0010 1100
    frame ข้อมูลดังกล่าวถูกต้องหรือไม่ หากไม่ถูกต้องผิดที่บิตใด และข้อมูลที่ได้รับเป็นตัวอักษร
    ใด 
::: Hamming code ชนิด 7/11 เป็น 110 0010 1100 frame
คือ 110[0]011[1]1[0][0] เอาตำแน่งบิตที่มีค่าเป็น 1 เช่ร
3   = 0011 
4   = 0100
5   = 0101      [XOR]
6   = 0110
10 = 1010
11 = 1011
-----------
         0101 แสดงว่ามีการผิดผลาด บีตตรงตำแน่งที่ 0101ฐานสอง คือ ตำแน่งที่ 5 ต้องเปลียน 1 ไป 0
ดังนั้น frame ข้อมูลที่ถูกต้องมีรหัล 110[0]010[1]1[0][0] และ ข้อมูลที่ได้รับคือ 0110 0101ขนาด 8 บีต  เป็นอักษร e อยู่ในรหัด ASCII
3. ผู้รับได้รับ frame ข้อมูลที่มีการเข้ารหัสแบบ Hamming code ชนิด 7/11 เป็น 101 0011 1101
    frame ข้อมูลดังกล่าวถูกต้องหรือไม่ หากไม่ถูกต้องผิดที่บิตใด และข้อมูลที่ถูกต้องเป็นอย่างไร
::: Hamming code ชนิด 7/11 เป็น 101 001 1101 frame
คือ 101 [0]011 [1]1[0][1] เอาตำแน่งบิตที่มีค่าเป็น 1 เช่ร
1   = 0001 
3   = 0011
4   = 0100      [XOR]
5   = 0101
6   = 0110
9   = 1001
11 = 1011
-----------
         0111 แสดงว่ามีการผิดผลาด บีตตรงตำแน่งที่ 0111ฐานสอง คือ ตำแน่งที่ 7 ต้องเปลียน 0 ไป 1
ดังนั้น frame ข้อมูลที่ถูกต้องมีรหัล 101 0111 1101 และ ข้อมูลที่ได้รับคือ 101 1111 ขนาด 7 บีต
1. หน่วยความจำหลัก หน่วยความจำลอง (สื่อเก็บข้อมูลความจุสูง) และ รีจิสเตอร์ ต่างก็ทำหน้าที่เป็นหน่วยความจำ
เช่นเดียวกัน หน่วยความจำทั้งสามแบบนี้มีที่ใช้งานแตกต่างกันอย่างไร
:::  +หน่วยความจำหลัก Main Memory ทำหน้าที่เก็บข้อมูล และ โปรแกรมที่กำลังจะต้องใช้ในเวลาต่อมา
      หลักการของมันคือขัอมูลหาย เมือไฟดับ 
     +หน่วยความจำรอง Second Storage มีหน้าที่เก็บข้อมูล ข้อมูลและโปรแกรมที่ยังไม่ได้ใช้ในขณะปัจจุบันไว้ แต่ข้อมูลไม่หายเมือไฟดับ 
     +เรจิสเตอร์ Register มีหน้าที่จัดเก็บหน่วยประมวลผลจาก CPU ที่กำลัง executed หรือ decoded 
2.คำกล่าวที่ว่า "คำสั่งเคลื่อนย้ายข้อมูลไม่ตรงกับการทำงานจริง" เป็นคำกล่าวที่ถูกต้องหรือไม่ อย่างไร
 จงอภิปรายพร้อมทั้งให้เหตุผลประกอบอย่างชัดเจน

3. จงอธิบายความแตกต่างที่สำคัญระหว่างการประมวลผลแบบ Real-sharing 
และการประมวลผลชนิดโต้ตอบกับผู้ใช้(Interactive)

4. จงอธิบายความแตกต่างที่สำคัญระหว่างระบบ Time-shareing และ Multitasking

5. โปรแกรมประยุกต์ (Applications) และโปรแกรมอรรถประโยชน์ (Utiltties) มีความแตกต่างที่สำคัญอย่างไร 
จงอธิบายโดยสังเขป พร้อมยกตัวอย่างประกอบ
+   โปรแกรมประยุกต์ เป็นโปรแกรมมีคุณสัมบัติทั้วไปกับผู้ใช้ทุกประเภท และทำให้ผู้ใช้ได้งายและงายเข้าใจ เช่ร MS-word , Ms-excel , Note pad ,.....

7. Virtual memory คืออะไร และมีความสำคัญอย่างไรต่อระบบ


8. จงสรุปกระบวนการ Bootstrapping ให้ได้ใจความสมบูรณ์

9. จงสรุปความแตกต่างระหว่างโปรแกรมและโพรเซส

10. เมื่อเกิสัญญาณขัดจังหวะ (Interrupt) ขึ้น หน่วยประมวลผลกลางมีขั้นตอนในการดำเนินการอย่างไร
 จงสรุปเขียนเป็นขั้นตอนวิธีที่ชัดเจน

Haffman Encoding

Huffman tree generated from the exact frequencies of the text "this is an example of a huffman tree". The frequencies and codes of each character are below. Encoding the sentence with this code requires 135 bits. (This assumes that the code tree structure is known to the decoder and thus does not need to be counted as part of the transmitted information.)

In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffmanwhile he was a Ph.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".

Huffman coding uses a specific method for choosing the representation for each symbol, resulting in a prefix code (sometimes called "prefix-free codes", that is, the bit string representing some particular symbol is never a prefix of the bit string representing any other symbol) that expresses the most common source symbols using shorter strings of bits than are used for less common source symbols. Huffman was able to design the most efficient compression method of this type: no other mapping of individual source symbols to unique strings of bits will produce a smaller average output size when the actual symbol frequencies agree with those used to create the code. A method was later found to design a Huffman code in linear time if input probabilities (also known as weights) are sorted.^{[citation needed]}

For a set of symbols with a uniform probability distribution and a number of members which is a power of two, Huffman coding is equivalent to simple binary block encoding, e.g., ASCII coding. Huffman coding is such a widespread method for creating prefix codes that the term "Huffman code" is widely used as a synonym for "prefix code" even when such a code is not produced by Huffman's algorithm.

Although Huffman's original algorithm is optimal for a symbol-by-symbol coding (i.e. a stream of unrelated symbols) with a known input probability distribution, it is not optimal when the symbol-by-symbol restriction is dropped, or when the probability mass functions are unknown, not identically distributed, or not independent (e.g., "cat" is more common than "cta"). Other methods such as arithmetic coding and LZW coding often have better compression capability: both of these methods can combine an arbitrary number of symbols for more efficient coding, and generally adapt to the actual input statistics, the latter of which is useful when input probabilities are not precisely known or vary significantly within the stream. However, the limitations of Huffman coding should not be overstated; it can be used adaptively, accommodating unknown, changing, or context-dependent probabilities. In the case of known independent and identically-distributed random variables, combining symbols together reduces inefficiency in a way that approaches optimality as the number of symbols combined increases.

History

In 1951, David A. Huffman and his MIT information theory classmates were given the choice of a term paper or a final exam. The professor, Robert M. Fano, assigned a term paper on the problem of finding the most efficient binary code. Huffman, unable to prove any codes were the most efficient, was about to give up and start studying for the final when he hit upon the idea of using a frequency-sorted binary tree and quickly proved this method the most efficient.^[1]

In doing so, the student outdid his professor, who had worked with information theory inventor Claude Shannon to develop a similar code. Huffman avoided the major flaw of the suboptimal Shannon-Fano coding by building the tree from the bottom up instead of from the top down.

[edit]Problem definition

[edit]Informal description

Given

A set of symbols and their weights (usually proportional to probabilities).

Find

A prefix-free binary code (a set of codewords) with minimum expected codeword length (equivalently, a tree with minimum weighted path length from the root).

[edit]Formalized description

Input.
Alphabet , which is the symbol alphabet of size n.
Set , which is the set of the (positive) symbol weights (usually proportional to probabilities), i.e. .

Output.
Code , which is the set of (binary) codewords, where c_i is the codeword for .

Goal.
Let  be the weighted path length of code C. Condition:  for any code .

[edit]Samples

Input (A, W)	Symbol (ai)	a	b	c	d	e	Sum
	Weights (wi)	0.10	0.15	0.30	0.16	0.29	= 1
Output C	Codewords (ci)	010	011	11	00	10
	Codeword length (in bits) (li)	3	3	2	2	2
	Weighted path length (li wi )	0.30	0.45	0.60	0.32	0.58	L(C) = 2.25
Optimality	Probability budget (2-li)	1/8	1/8	1/4	1/4	1/4	= 1.00
	Information content (in bits) (−log2 wi) ≈	3.32	2.74	1.74	2.64	1.79
	Entropy (−wi log2 wi)	0.332	0.411	0.521	0.423	0.518	H(A) = 2.205

For any code that is biunique, meaning that the code is uniquely decodeable, the sum of the probability budgets across all symbols is always less than or equal to one. In this example, the sum is strictly equal to one; as a result, the code is termed a complete code. If this is not the case, you can always derive an equivalent code by adding extra symbols (with associated null probabilities), to make the code complete while keeping it biunique.

As defined by Shannon (1948), the information content h (in bits) of each symbol a_i with non-null probability is

The entropy H (in bits) is the weighted sum, across all symbols a_i with non-zero probability w_i, of the information content of each symbol:

(Note: A symbol with zero probability has zero contribution to the entropy. When w = 0,  is an indefinite form; so byL'Hôpital's rule:

.

For simplicity, symbols with zero probability are left out of the formula above.)

As a consequence of Shannon's source coding theorem, the entropy is a measure of the smallest codeword length that is theoretically possible for the given alphabet with associated weights. In this example, the weighted average codeword length is 2.25 bits per symbol, only slightly larger than the calculated entropy of 2.205 bits per symbol. So not only is this code optimal in the sense that no other feasible code performs better, but it is very close to the theoretical limit established by Shannon.

Note that, in general, a Huffman code need not be unique, but it is always one of the codes minimizing L(C).

[edit]Basic technique

A source generates 4 different symbols{a₁,a₂,a₃,a₄} with probability{0.4;0.35;0.2;0.05}. A binary tree is generated from left to right taking the two least probable symbols and putting them together to form another equivalent symbol having a probability that equals the sum of the two symbols. The process is repeated until there is just one symbol. The tree can then be read backwards, from right to left, assigning different bits to different branches. The final Huffman code is:

Symbol	Code
a1	0
a2	10
a3	110
a4	111

The standard way to represent a signal made of 4 symbols is by using 2 bits/symbol, but theentropy of the source is 1.73 bits/symbol. If this Huffman code is used to represent the signal, then the average length is lowered to 1.85 bits/symbol; it is still far from the theoretical limit because the probabilities of the symbols are different from negative powers of two.

The technique works by creating a binary tree of nodes. These can be stored in a regular array, the size of which depends on the number of symbols, n. A node can be either a leaf node or an internal node. Initially, all nodes are leaf nodes, which contain the symbol itself, the weight (frequency of appearance) of the symbol and optionally, a link to a parent node which makes it easy to read the code (in reverse) starting from a leaf node. Internal nodes contain symbol weight, links to two child nodes and the optional link to a parent node. As a common convention, bit '0' represents following the left child and bit '1' represents following the right child. A finished tree has up to n leaf nodes and n − 1 internal nodes. A Huffman tree that omits unused symbols produces the most optimal code lengths.

The process essentially begins with the leaf nodes containing the probabilities of the symbol they represent, then a new node whose children are the 2 nodes with smallest probability is created, such that the new node's probability is equal to the sum of the children's probability. With the previous 2 nodes merged into one node (thus not considering them anymore), and with the new node being now considered, the procedure is repeated until only one node remains, the Huffman tree.

The simplest construction algorithm uses a priority queue where the node with lowest probability is given highest priority:

1. Create a leaf node for each symbol and add it to the priority queue.
2. While there is more than one node in the queue:
   1. Remove the two nodes of highest priority (lowest probability) from the queue
   2. Create a new internal node with these two nodes as children and with probability equal to the sum of the two nodes' probabilities.
   3. Add the new node to the queue.
3. The remaining node is the root node and the tree is complete.

Since efficient priority queue data structures require O(log n) time per insertion, and a tree with nleaves has 2n−1 nodes, this algorithm operates in O(n log n) time.

If the symbols are sorted by probability, there is a linear-time (O(n)) method to create a Huffman tree using two queues, the first one containing the initial weights (along with pointers to the associated leaves), and combined weights (along with pointers to the trees) being put in the back of the second queue. This assures that the lowest weight is always kept at the front of one of the two queues:

1. Start with as many leaves as there are symbols.
2. Enqueue all leaf nodes into the first queue (by probability in increasing order so that the least likely item is in the head of the queue).
3. While there is more than one node in the queues:
   1. Dequeue the two nodes with the lowest weight by examining the fronts of both queues.
   2. Create a new internal node, with the two just-removed nodes as children (either node can be either child) and the sum of their weights as the new weight.
   3. Enqueue the new node into the rear of the second queue.
4. The remaining node is the root node; the tree has now been generated.

It is generally beneficial to minimize the variance of codeword length. For example, a communication buffer receiving Huffman-encoded data may need to be larger to deal with especially long symbols if the tree is especially unbalanced. To minimize variance, simply break ties between queues by choosing the item in the first queue. This modification will retain the mathematical optimality of the Huffman coding while both minimizing variance and minimizing the length of the longest character code.

Here's an example using the French subject string "j'aime aller sur le bord de l'eau les jeudis ou les jours impairs":

[edit]Main properties

The probabilities used can be generic ones for the application domain that are based on average experience, or they can be the actual frequencies found in the text being compressed. (This variation requires that a frequency table or other hint as to the encoding must be stored with the compressed text; implementations employ various tricks to store tables efficiently.)

Huffman coding is optimal when the probability of each input symbol is a negative power of two. Prefix codes tend to have inefficiency on small alphabets, where probabilities often fall between these optimal points. "Blocking", or expanding the alphabet size by grouping multiple symbols into "words" of fixed or variable-length before Huffman coding helps both to reduce that inefficiency and to take advantage of statistical dependencies between input symbols within the group (as in the case of natural language text). The worst case for Huffman coding can happen when the probability of a symbol exceeds 2⁻¹ = 0.5, making the upper limit of inefficiency unbounded. These situations often respond well to a form of blocking called run-length encoding; for the simple case of Bernoulli processes, Golomb coding is a provably optimal run-length code.

Arithmetic coding produces some gains over Huffman coding, although arithmetic coding has higher computational complexity. Also, arithmetic coding was historically a subject of some concern over patent issues. However, as of mid-2010, various well-known effective techniques for arithmetic coding have passed into the public domain as the early patents have expired.

[edit]Variations

Many variations of Huffman coding exist, some of which use a Huffman-like algorithm, and others of which find optimal prefix codes (while, for example, putting different restrictions on the output). Note that, in the latter case, the method need not be Huffman-like, and, indeed, need not even bepolynomial time. An exhaustive list of papers on Huffman coding and its variations is given by "Code and Parse Trees for Lossless Source Encoding"[1].

[edit]n-ary Huffman coding

The n-ary Huffman algorithm uses the {0, 1, ... , n − 1} alphabet to encode message and build an n-ary tree. This approach was considered by Huffman in his original paper. The same algorithm applies as for binary (n equals 2) codes, except that the n least probable symbols are taken together, instead of just the 2 least probable. Note that for n greater than 2, not all sets of source words can properly form an n-ary tree for Huffman coding. In this case, additional 0-probability place holders must be added. This is because the tree must form an n to 1 contractor; for binary coding, this is a 2 to 1 contractor, and any sized set can form such a contractor. If the number of source words is congruent to 1 modulo n-1, then the set of source words will form a proper Huffman tree.

[edit]Adaptive Huffman coding

A variation called adaptive Huffman coding involves calculating the probabilities dynamically based on recent actual frequencies in the sequence of source symbols, and changing the coding tree structure to match the updated probability estimates.

[edit]Huffman template algorithm

Most often, the weights used in implementations of Huffman coding represent numeric probabilities, but the algorithm given above does not require this; it requires only a way to order weights and to add them. The Huffman template algorithm enables one to use any kind of weights (costs, frequencies, pairs of weights, non-numerical weights) and one of many combining methods (not just addition). Such algorithms can solve other minimization problems, such as minimizing  , a problem first applied to circuit design [2].

[edit]Length-limited Huffman coding

Length-limited Huffman coding is a variant where the goal is still to achieve a minimum weighted path length, but there is an additional restriction that the length of each codeword must be less than a given constant. The package-merge algorithm solves this problem with a simple greedyapproach very similar to that used by Huffman's algorithm. Its time complexity is O(nL), where L is the maximum length of a codeword. No algorithm is known to solve this problem in linear or linearithmic time, unlike the presorted and unsorted conventional Huffman problems, respectively.

[edit]Huffman coding with unequal letter costs

In the standard Huffman coding problem, it is assumed that each symbol in the set that the code words are constructed from has an equal cost to transmit: a code word whose length is N digits will always have a cost of N, no matter how many of those digits are 0s, how many are 1s, etc. When working under this assumption, minimizing the total cost of the message and minimizing the total number of digits are the same thing.

Huffman coding with unequal letter costs is the generalization in which this assumption is no longer assumed true: the letters of the encoding alphabet may have non-uniform lengths, due to characteristics of the transmission medium. An example is the encoding alphabet of Morse code, where a 'dash' takes longer to send than a 'dot', and therefore the cost of a dash in transmission time is higher. The goal is still to minimize the weighted average codeword length, but it is no longer sufficient just to minimize the number of symbols used by the message. No algorithm is known to solve this in the same manner or with the same efficiency as conventional Huffman coding.

[edit]Optimal alphabetic binary trees (Hu-Tucker coding)

In the standard Huffman coding problem, it is assumed that any codeword can correspond to any input symbol. In the alphabetic version, the alphabetic order of inputs and outputs must be identical. Thus, for example,  could not be assigned code , but instead should be assigned either  or . This is also known as the Hu-Tucker problem, after the authors of the paper presenting the first linearithmic solution to this optimal binary alphabetic problem, which has some similarities to Huffman algorithm, but is not a variation of this algorithm. These optimal alphabetic binary trees are often used as binary search trees.

[edit]The canonical Huffman code

If weights corresponding to the alphabetically ordered inputs are in numerical order, the Huffman code has the same lengths as the optimal alphabetic code, which can be found from calculating these lengths, rendering Hu-Tucker coding unnecessary. The code resulting from numerically (re-)ordered input is sometimes called the canonical Huffman code and is often the code used in practice, due to ease of encoding/decoding. The technique for finding this code is sometimes called Huffman-Shannon-Fano coding, since it is optimal like Huffman coding, but alphabetic in weight probability, likeShannon-Fano coding. The Huffman-Shannon-Fano code corresponding to the example is {000,001,01,10,11}, which, having the same codeword lengths as the original solution, is also optimal.

[edit]Model reconstruction

Decompression generally requires transmission of information in order to reconstruct the compression model (methods such as adaptive Huffman do not, although they typically produce less than optimal code lengths). Originally, symbol frequencies were passed along to the decompressor, but this method is very inefficient, as it can produce an unacceptable level of overhead. The most common technique utilizes canonical Huffman encoding, which only requires Bn bits of information (where B is the number of bits per symbol and n is the size of the symbol's alphabet). Other methods, such as the "direct transmission" of the Huffman tree, produce variable-length encoding of the model which can reduce the overhead to just a few bytes, in some cases.

Because the compressed data can include unused "trailing bits", the decompressor must be able to determine when to stop producing output. This can be accomplished by either transmitting the length of the decompressed data along with the compression model or by defining a special code symbol to signify the end of input (the latter method can adversely affect code length optimality, however).

[edit]Applications