Lana ฟังชื่อแล้วเขาคือใครกันหนอ ..
หากใครได้ศึกษา วิชา Information Theory หรือวิชาเกี่ยวกับการเข้ารหัสช่องสัญญาณ หรือ Source Coding ทั้งหลาย อาจคุ้นกับภาพ ๆ นี้ เนื่องจาก คุณ Lena Söderberg
สาวสวยที่คุณจะได้พบได้ในหลาย ๆ งานวิจัยเกี่ยวกับทางด้าน Image Compression หรือใครที่คิดทฤษฏี ใหม่ ๆ หรือเพียงแค่เพิ่มประสิทธิภาพของทฤษฏีเก่า อีกนิด ก็มักจะใช้฿าพนี้ เพื่อเปรียบเทียบก่อน และหลัง โดยจริงๆ ภาพนี้ถูกตีพิมพ์ในหนังสือ PlayBoy ! ตกใจใช่ไหมครับ ว่า วงการ PlayBoy นั้นมาเกี่ยวกับ วงการวิชาการ และนักวิชาการได้อย่าไร …
เหตุการเกิดขึ้นเมื่อปี 1973 เมื่อผู้ช่วยนักวิจัย ของ Professor Alexander Sawchuk ที่อยู่ใน Lab Signal and Image Processing Institute (SIPI) ของ University of Southern California กำลังทำงานวิจัย พยายามหาภาพต้นแบบ เพื่อทดสอบ ทฤษฏีที่เขาคิดค้นขึ้น โดยต้องการภาพที่ดูดี มีแสงกว้าง และให้ความลึก โดยมีพืนสีหน้าชัดเจน โดยได้เปิดหนังสือ PlayBoy พบคุณ Lenna จึงนำมา Scan โดยให้ได้ภาพขนาด 512 × 512 Pixel โดยภาพจริง ๆ นั้น ฮึ ฮึ ไม่ต้อง Said เลย ..แฮะ แฮะ
฿าพต้นฉบับ ที่ใช้ในการทำงานวิจัย
จากครั้งนั้น ถือว่ามีผลมากกับ สายงานวิจัยทาง ด้าน image processing และ image compression algorithms โดยแทบจะเรียกได้ว่า ในช่วงนั้น งานวิจัยใครไม่ได้ใช้ภาพคุณ Lena อาจดูเชยไปเลยทีเดียว
ตัวอย่าง Paper ที่ใช้ภาพคุณ Lena ในการอธิบาย algorithms
ภาพคุณ lena ในปัจจุบัน (แต่คงหลายปีแล้ว…)
หากใครอยู่ในสายนี้ หรือทำงานวิจัยด้านนี้ เห็นภาพคงนึกถึงสมัยเรียนที่ นั่งคำนวณ ทฤษฏีต่างๆ นา เต็มไปหมด แต่สมัยนี้เปิด Math Lab พิมพ์ก๊อกแก๊ก อึดใจเดียวก็เห็นผลลัพท์ แล้ว ….เฮ้อ …
ขอบพระคุณที่สนใจอ่าน
อ่านเพิ่มเติม : http://en.wikipedia.org/wiki/Lenna
การเข้ารหัส Convolution Code
Convolution Code หรือบางคนอาจเรียกว่า รหัสแบบขด จัดอยู่ในกลุ่มของ การเข้ารหัสผ่านช่องสัญญาณ (Channel Coding) โดยมีจุดประสงค์ เพื่อให้ผู้รับ รับสัญญาณ ได้ครบถ้วน หรือหากเกิดมีสัญญาณรบกวนขึ้น ผู้รับสามารถรับรู้ได้ถึงความผิดพลาด ของข้อมูลที่ได้รับ อีกทั้งสามารถแก้ไขข้อผิดพลาดนั้น ๆ ได้ โดยวิธีนี้เรียกว่า Forward Error Correction (FEC)
การเข้ารหัส Convolution Code นั้น นำไปใช้อย่างแพร่หลาย เช่นใช้ในการส่งสัญญาณวิทยุระบบดิจิตอล โทรศัพท์มือถือ รวมถึงในสัญญาณดาวเทียม และใน BlueTooth อาจเนื่องจากหากเกิดข้อผิดพลาด หรือมี Noise เข้ามากวน ฝั่งผู้รับสามารถตรวจสอบ และแก้ไขให้ข้อมูลที่ได้รับ กลับมาถูกต้อง แต่ถ้าเกิด Noise แบบแถบ (Burst noise) ล่ะก็ อาจช่วยได้ไม่ทั้งหมด อาจต้องใช้เทคนิค Bit Interleave เข้ามาช่วย ผมเคยทดสอบด้วย Math Lab ได้ผลค่อนข้างดีเดียว
การเข้ารหัส Convolution Code นั้น เริ่มต้นด้วยมีการสร้าง Generator เพื่อทำการแปลงข้อมูลจาก Bit ข้อมูล เป็น Bit รหัส Convolution Code โดยที่เริ่มต้นจากกระแสข้อมูล ที่ต้องการเข้ารหัสวิ่งผ่าน ตัวสร้างรหัส จะนำแต่ละ Bit ข้อมูลมาเพิ่มรหัส ดัง฿าพ
ข้อมูลที่ต้องการส่ง คือ 110101เมื่อตัวสร้างรหัสแล้วจะได้รหัส Convolution คือ 11 10 11 01 01 01 ซึ่งแม้จะขนาดยาวกว่าเพิ่ม แต่ได้เพิ่ม Bit เพื่อให้ปลายทางสามารถตรวจสอบ และกู้คืนความผิดปกติได้ หลักการทำงาน โดยการเปลี่ยนแปลง
การถอดรหัส Convolution
หากเป็นการอธิบายให้เห็นภาพ จะใช้ แผนภาพ Viterbi algorithm ซึ่งจะแผนเส้นทางเดิน ของข้อมูล ซึ่งจะแสดงเส้นทางที่เป็นไปได้
จากตัวอย่าง จะเห็นว่าฝั่งผู้รับมีข้อมูลผิดถึง 2 bit (Bit สีแดง) โดยสามารถถอดรหัส โดยไล่ตามเส้นทางของ Bit ที่ได้รับในแผนภูมิ Viterbi algorithm หากไม่มีเส้นทางไหนที่เป็นไปได้ แต่เมื่อถอดไปอีก จะเห็นเส้นทางต่อไป จึงทำให้สามารถสร้างเส้นทางที่ขาดไป ได้
จากการทดสอบด้วย Math Lab นั้น มีฟังก์ชั่น การเข้ารหัส Convolution ให้เรียกใช้ จากการทดสอบ ด้วยข้อมูลทดสอบนั้น หากผิดเพียง 1 Bit ปลายทางสามารถกู้คืนได้ แต่หากผิด 2 Bit ติดกัน สามารถแก้ไขได้ โดยมีโอกาศผิด 30% แต่หากผิด 1 Bit สลับกัน มีโอกาสกู้คืนผิดถึง 50% วิธีการแก้ปัญหานั้น ให้ใช้ รหัส Convolution ควบคู่กับเทคนิค Bit Interleaving และยังสามารถป้องกัน Burst Errors (การเกิด Noise ทำให้เกิด Error เป็นแถบ) ดังภาพ
เมื่อเกิด Burst Error เกิดขึ้น เมื่อ De-Interleaving ทำให้ Bit ที่เสียหายกระจายตัวกันออกไป หลังจากนั้นก็ Decode รหัส Convolution อีกครั้ง ซึ่งจะทำให้รหัส Convolution เป็นพระเอกขึ้นมาทีเดียว
ขอบพระคุณที่สนใจอ่าน
อ่านเพิ่มเติม : http://en.wikipedia.org/wiki/Convolution_code
ทฤษฏีสารสนเทศ (Information Theory)
ทฤษฏีที่ว่าด้วย การเข้ารหัสข้อมูล และการเข้ารหัสช่องสัญญาณ โดยมีภาพรวมดังนี้
฿าพรวมของ Information นั้นแบ่งได้เป็น 2 ส่วนหลัก ๆ คือ
1. Source Coding
หรือสามารถเรียกอีกอย่างหนึ่งได้ว่า Data Compression หมายถึงกระบวนการสร้างข้อมูลในรูปแบบ Digital ที่ไม่ซ้ำกัน เช่นหากเราต้องการส่ง a b c ไปให้ถึงผู้รับ จะทำอย่างไรให้ข้อมูลที่ส่งไปถึงผู้รับ โดยที่ผู้รับเข้าใจตรงกัน ว่าสิ่งที่ผู้ส่งมานั้น คือ a b หรือ c ซึ่งในความเป็นจริงๆ ข้อมูลที่จะส่งมีตั้งแต่ a-z A-Z ตัวเลข ตัวอักษรพิเศษ ^ & % $ # ส่งอย่างไร ถึงจะใช้จำนวน bit ที่สั้น และปลายทางสามารถเข้าใจได้ทันทีว่า Bit ที่ได้รับนั้น คือข้อมูลใด โดยมีจุดประสงค์ เพื่อจัดเก็บที่ดี (ขนาดเล็กลง) และเพื่อส่งข้อมูลถึงกัน (ข้อมูลจะมีขนาดเล็ก ส่งได้เร็ว)
- แบ่งตามประเภทการสูญเสียข้อมูล แบ่งได้ดังนี้
- Losseless Compression
- หมายถึงการบีบอัดข้อมูล โดยที่ไม่ยอมสูญเสียข้อมูลเลย
- Lossy Compression
- หมายถึง การบีบอัดข้อมูล โดยที่ยอมสูญเสียข้อมูลบ้าง แต่ฝั่งผู้รับสามารถรับรู้ และตีความหมายได้
- แบ่งตามลักษณะข้อมูล แบ่งได้ดังนี้
- Multimedia Coding เน้นถึง Algorithm สำหรับส่งส่งสัญญาณ Audio, Images และ Video เช่น
- Text
- Speech
- Music
- Audio
- Graphic
- Image Video
- more …
- ตัวอย่างงานวิจัยทางด้านนี้ จนเป็นที่ยอมรับในอุตสาหกรรม และเราได้ใช้โดยไม่รู้ตัวเช่น
- Standard: H:series, MPEG, VRML .. เพลงที่เราฟัง, MP3, DVD เป็นต้น
- Networking: streaming, QoS, VBR
- MMX Technology (คุ้น ๆ ไหม สำหรับคนใช้ Pantium II )
- Databases : Retrive and Indexing
- more …
- Data Compression เน้นถึง Algorithm สำหรับส่งข้อมูลถึงปลายทางโดยไม่แยกแยะข้อมูล โดยที่ข้อมูลชุดใหม่ที่สร้างขึ้น มีขนาดกระทัดรัด
2. Channel Coding
การเข้ารหัสผ่านช่องสัญญาณ (Channel Coding) โดยมีจุดประสงค์ เพื่อให้ผู้รับ รับสัญญาณ ได้ครบถ้วน หรือหากเกิดมีสัญญาณรบกวนขึ้น ผู้รับสามารถรับรู้ได้ถึงความผิดพลาด โดยที่ไม่ได้เน้นการบีบอัดข้อมูลมากนัก อาจเพิ่ม Bit เข้าไปตรวจสอบ หรือเพิ่มจำนวน Bit เข้าไป เพื่อให้ฝั่งรับสามารถตรวจสอบ และสามารถแก้ไขข้อผิดพลาดนั้น ๆ ได้ โดยวิธีนี้เรียกว่า Forward Error Correction (FEC) ตัวอย่างเช่น
- Block Code [Hamming code(7,4)]
- Convolution Coding
- Turbo Coding
- more …
Channel Coding ที่เพียงแค่ให้ผู้รับปลายทางทราบว่ามีข้อมูลผิดพลาดเข้ามาเพียงอย่างเดียว และผู้รับร้องขอให้ผู้ส่ง ส่งใหม่ เรียกว่า Automatic Repeat-reQuest (ARQ) ตัวอย่างได้แก่
ขอบพระคุณที่สนใจอ่าน
อ่านเพิ่มเติม : http://en.wikipedia.org/wiki/Information_Theory
Huffman Coding
เป็นส่วนหนึ่งของ Data Compression แบบที่เรียกว่า Lossless Compression ที่เมื่อผู้รับปลายทาง รับข้อมูล สามารถ Decode กลับมาเป็นข้อมูลได้ครบถ้วน ถือว่าเป็นแม่แบบของ Data Compression เนื่องจากเป็นหลักในการศึกษาทฤษฏีอื่น ๆ ต่อไป
ตัวอย่างการเข้ารหัส Huffman Code
ผู้ส่ง ต้องการส่งข้อมูลดังนี้ {a , b , c , d } โดยที่มีโอกาศเกิดคำนั้นในเอกสาร {0.5 ; 0.3 ; 0.1 ; 0.1 } หากคิดง่าย โดยการแทนตัวอักษรดังนี้
- a = 00
- b = 01
- c = 10
- d = 11
หากต้องการส่งข้อมูล abcd ไปยังผู้รับ หากแทนตัวอักษรด้วยจำนวน 2 Bit จะได้ข้อมูล 00011011 ไปยังปลายทาง สังเกตุว่า เราใช้ ถึง 2 Bit ในการแทนตัวอักษรทั้งหมด ซึ่งไม่จำเป็นต้องใช้ Bit จำนวนมากขนาดนั้น
หากเราใช้ Huffman Code ให้การแทนนั้น เราจะสามารถแทน
- a = 1
- b = 01
- c = 001
- d = 000
สามารถคำนวณค่าเฉลี่ยการใช้ Bit แทนตัวอักษรได้ดังนี้
(0.5)*1+(0.3)*2+(0.1)*3+(0.1)*3 = 1.7 Bit เท่านั้น
ยิ่งหากมีเอกสารมากขึ้นยิ่งสามารถลดจำนวน Bit ได้มากขึ้น
ขอบพระคุณที่สนใจอ่าน
อ่านเพิ่มเติม : http://en.wikipedia.org/wiki/Huffman_coding
