Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/6707
| Title: | การทำให้เป็นบรรทัดฐานของจำนวนที่มีค่าน้ำหนักน้อยที่สุดแบบทำควบคู่กัน |
| Other Titles: | On-the-fly minimum weight number normalization |
| Authors: | นิธิชัย อนันตะเศรษฐกูล |
| Advisors: | อรรถสิทธิ์ สุรฤกษ์ |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์ |
| Advisor's Email: | athasit@cp.eng.chula.ac.th |
| Subjects: | ทฤษฎีจำนวนเลข การคำนวณของคอมพิวเตอร์ คอมพิวเตอร์อัลกอริทึม |
| Issue Date: | 2548 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | ในการคำนวณเลขคณิตคอมพิวเตอร์ จำนวนของดิจิตที่ไม่เป็นศูนย์ มีผลต่อความเร็วในการคำนวณอย่างเห็นได้ชัด ดังนั้นประเด็นที่น่าสนใจคือ การหารูปแบบการแทนจำนวนที่มีค่าน้ำหนักน้อยที่สุด เพื่อจะส่งผลให้การคำนวณมีความเร็วยิ่งขึ้น ที่ผ่านมามีงานวิจัยทางด้านนี้มากมายซึ่งเวลาที่ใช้ในการคำนวณเป็นเวลาเชิงเส้นตรง เช่น การแปลงชุดตัวเลขโดยหน้าต่างการเลื่อนไหล โดย ฟิลิบและเบิร์ก ในปี ค.ศ. 2004 แนวคิดของงานวิจัยนี้คือลดจำนวนของดิจิตที่ไม่เป็นศูนย์ให้ได้มากที่สุด อัลกอริทึมในการแปลงโดยหน้าต่างการเลื่อนไหลนี้ถูกพิสูจน์แล้วว่า ผลลัพธ์ที่ได้อยู่ในรูปแบบที่มีค่าน้ำหนักน้อยที่สุดโดยมีพารามิเตอร์คือ ขอบเขตล่าง ขอบเขตบน เลขฐานและขนาดของหน้าต่าง การแปลงนี้ทำจากขวาไปซ้าย ซึ่งเป็นการแปลงแบบลำดับส่งผลให้มีความเร็วเป็นเวลาเชิงเส้นตรง งานวิจัยนี้ได้เสนอกระบวนการการแปลงแบบขนาน โดยอาศัยสถาปัตยกรรมการแปลงแบบทำควบคู่กัน และนำมาประยุกต์ใช้กับระบบจำนวนซ้ำซ้อนแบบมีเครื่องหมาย เราได้เสนอวิธีการการแปลงที่เรียกว่า การทำให้เป็นบรรทัดฐาน สำหรับระบบเลขฐานที่มากกว่าหรือเท่ากับสอง ซึ่งมีความเร็วเป็นเวลาออการิทึม ประกอบกับบทพิสูจน์เพื่อแสดงให้เห็นว่าการทำให้เป็นบรรทัดฐานนี้ทำงานถูกต้อง |
| Other Abstract: | Performing some arithmetic operations in computer system, number of nonzero digits can have an effect on the time used for the computation. Therefore the number representation in the form of minimum weight which we are interested is due to the benefit in term of increasing the computational speed. There are several researches studied on minimum weight digit set conversion for which the time complexity is linear on the length of the input bit-string. Recently technique proposed in this area is a sliding window conversion algorithm by Phillips and Burgess in 2004. The idea is to minimize the number of nonzero digits in the bit-string. The sliding window algorithm has been proven that the result bit-string has a possible minimum weight by specifying some parameters: lower bound, upper bound, base, and window size. The conversion algorithm processes from right to left and results to the complexity. This thesis introduces a conversion process in parallel manner by applying on-the-fly architecture combining with a redundant number system. We have proposed a minimum weight normalization algorithm for all bases greater than or equal to two along with the proof for the algorithm. It is also shown in the thesis that our method can be performed with the logarithmic time complexity on the length of the input. |
| Description: | วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2548 |
| Degree Name: | วิทยาศาสตรมหาบัณฑิต |
| Degree Level: | ปริญญาโท |
| Degree Discipline: | วิทยาศาสตร์คอมพิวเตอร์ |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/6707 |
| ISBN: | 9745325163 |
| Type: | Thesis |
| Appears in Collections: | Eng - Theses |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| nitichai.pdf | 1.25 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.