Chulalongkorn University Theses and Dissertations (Chula ETD)

อัลกอริทึมการบวกและการคูณสำหรับระบบจำนวนฐานคู่ทั่วไป

Other Title (Parallel Title in Other Language of ETD)

Addition and multiplication algorithm for generic double-base number system

Year (A.D.)

2006

Document Type

Thesis

First Advisor

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

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิศวกรรมศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

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

DOI

10.58837/CHULA.THE.2006.1477

Abstract

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

Other Abstract (Other language abstract of ETD)

Number system has a great effect to computer arithmetic calculation thus a lot of researchers have proposed many new number systems. One of them is Double-Base Number System. It represents positive integer by using two bases; usually be two and three. The advantages of this system are its high redundancy degree and sparseness. Many papers are concentrated on basic arithmetic operations that are addition and multiplication. However, earlier algorithms are non-deterministic. This thesis proposes deterministic addition and multiplication algorithms which can also manipulate the generic double-base mumber system. The addition time is linearly dependent on the amount of rows. In addition, this addition algorithm is pipeline-able. The multiplication is based on our proposed addition algorithm. The complexity of this operation depends on the number of active cells in the multiplicand. Furthermore, all algorithms are proved theoretically and practically by simulation on synchronized digital circuits.

Link to Full Text

Share

COinS