ชุดตัวเลขตรรกยะสำหรับการเข้ารหัสอาร์เอนแบบเชื่อมตรง

Rational Digit-Set for On-Line RN-Coding

Name: พิภพ เทียนประภาสิทธิ์

ThaSH: รหัสและการเข้ารหัส

ThaSH: จำนวนตรรกยะ

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

Abstract: Designing number system can affect the performance of computation in a computer system. Among many researches purposed, signed-digit number system is one of the most well-known systems. A digit in this number system can have a positive and negative sign to represent a number. The advantage of this number system is an ability to limit a carry propagation during a computation which can be applied to reduce a computational time. There is an interesting number system that applies the concept of signed-digit number system. It is called Round-to-Nearest-Coding (RN-Coding). An idea of this number system is to reduce unnecessary time consumption during a rounding process. A rounding process in RN-Coding can be done by truncating at any position of a number representation (a sequence of digits). The obtained number representation always has the same numerical value as a rounding to the nearest. The concept of rounding process in RN-coding is suitable to be applied to a problem that frequently needs a rounding process especially in a pipeline or on-line computation manner. If there is no need to wait for a rounding process during an on-line computation, then each output digit can be passed to the next computation immediately. However, a RN-Coding does not support an on-line computation. In this dissertation, we propose a novel number system called rational digit set number system which can work in positive integer and negative integer base. Our system uses rational digits to represent a number instead of only integer digits. The idea is that using rational digits allow us to do a rounding by truncation like RN-Coding and it also supports an on-line computation manner. On-line elementary arithmetic computation in our system can be performed by an on-line digit set conversion using an on-line finite automaton with an on-line delay. Moreover, we can prove that any number can have a representation in our system.

จุฬาลงกรณ์มหาวิทยาลัย. สำนักงานวิทยทรัพยากร

Address: กรุงเทพมหานคร

Email: cuir@car.chula.ac.th

Name: อรรถสิทธิ์ สุรฤกษ์

Role: ที่ปรึกษา

Created: 2559

Modified: 2562-08-21

Issued: 2562-08-21

วิทยานิพนธ์/Thesis

application/pdf

URL: http://cuir.car.chula.ac.th/handle/123456789/54872

tha

DegreeName: วิศวกรรมศาสตรดุษฎีบัณฑิต

Level: ปริญญาเอก

Descipline: วิศวกรรมคอมพิวเตอร์

Grantor: จุฬาลงกรณ์มหาวิทยาลัย

©copyrights จุฬาลงกรณ์มหาวิทยาลัย

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	5571430721[1].pdf	2.26 MB

ใช้เวลา

0.024145 วินาที