• Admin
    UC Research Repository
    View Item 
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Theses and Dissertations
    • View Item
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of the RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    Statistics

    View Usage Statistics

    Multiple Constant Multiplication Optimization Using Common Subexpression Elimination and Redundant Numbers

    Thumbnail
    View/Open
    Thesis embargoed until 02-04-2016 (3.221Mb)
    Al-Hasani_Use_of_thesis_form.pdf (132.1Kb)
    Author
    Al-Hasani, Firas Ali Jawad
    Date
    2014
    Permanent Link
    http://hdl.handle.net/10092/9054
    Thesis Discipline
    Electrical Engineering
    Degree Grantor
    University of Canterbury
    Degree Level
    Doctoral
    Degree Name
    Doctor of Philosophy

    The multiple constant multiplication (MCM) operation is a fundamental operation in digital signal processing (DSP) and digital image processing (DIP). Examples of the MCM are in finite impulse response (FIR) and infinite impulse response (IIR) filters, matrix multiplication, and transforms. The aim of this work is minimizing the complexity of the MCM operation using common subexpression elimination (CSE) technique and redundant number representations. The CSE technique searches and eliminates common digit patterns (subexpressions) among MCM coefficients. More common subexpressions can be found by representing the MCM coefficients using redundant number representations.

    A CSE algorithm is proposed that works on a type of redundant numbers called the zero-dominant set (ZDS). The ZDS is an extension over the representations of minimum number of non-zero digits called minimum Hamming weight (MHW). Using the ZDS improves CSE algorithms' performance as compared with using the MHW representations. The disadvantage of using the ZDS is it increases the possibility of overlapping patterns (digit collisions). In this case, one or more digits are shared between a number of patterns. Eliminating a pattern results in losing other patterns because of eliminating the common digits. A pattern preservation algorithm (PPA) is developed to resolve the overlapping patterns in the representations. A tree and graph encoders are proposed to generate a larger space of number representations. The algorithms generate redundant representations of a value for a given digit set, radix, and wordlength. The tree encoder is modified to search for common subexpressions simultaneously with generating of the representation tree. A complexity measure is proposed to compare between the subexpressions at each node. The algorithm terminates generating the rest of the representation tree when it finds subexpressions with maximum sharing. This reduces the search space while minimizes the hardware complexity.

    A combinatoric model of the MCM problem is proposed in this work. The model is obtained by enumerating all the possible solutions of the MCM that resemble a graph called the demand graph. Arc routing on this graph gives the solutions of the MCM problem. A similar arc routing is found in the capacitated arc routing such as the winter salting problem. Ant colony optimization (ACO) meta-heuristics is proposed to traverse the demand graph. The ACO is simulated on a PC using Python programming language. This is to verify the model correctness and the work of the ACO. A parallel simulation of the ACO is carried out on a multi-core super computer using C++ boost graph library.

    Subjects
    Common subexpression elimination (CSE)
     
    multiple constant multiplication (MCM)
     
    multiplier block (MB)
     
    multiplierless multiple constant multiplication
     
    adder step
     
    logic depth (LD)
     
    logic operator (LO)
     
    lower bound and optimality
     
    graph dependent method
     
    radix number system
     
    redundant number representations
     
    pattern preservation algorithm (PPA)
     
    zero-dominant set (ZDS)
     
    polynomial ring
     
    radix polynomials
     
    complete residue system modulo radix
     
    congruent relation
     
    tree encoder
     
    graph encoder
     
    subexpression tree algorithm (STA)
     
    A-operation
     
    combinatorial model of multiple constant multiplication
     
    demand graph
     
    dynamic capacitated arc routing problem
     
    metaheuristics
     
    ant colony optimization (ACO)
     
    max-min ant system (MMAS)
     
    parallel computing
     
    computer cluster.
    Collections
    • Engineering: Theses and Dissertations [2157]
    Rights
    http://library.canterbury.ac.nz/thesis/etheses_copyright.shtml

    Related items

    Showing items related by title, author, creator and subject.

    • Multiple memory systems: Contributions of human and animal serial reaction time tasks 

      Christie, Michael A (University of Canterbury. Psychology, 2001)
      Human memory systems have been divided into two broad domains, one responsible for 'declarative memory' and the other for 'non-declarative memory'. The evidence for multiple memory systems is reviewed with respect to the ...
    • An efficient biomimetic swimming robot capable of multiple gaits of locomotion : design, modelling and fabrication. 

      Masoomi, Sayyed Farideddin (University of Canterbury. Mechanical Engineering, 2014)
      Replacing humans with underwater robots for accomplishing marine tasks such as oceanic supervision and undersea operations have been an endeavour from long time ago. Hence, a number of underwater robots have been developed. ...
    • The design and evaluation of a multiple-language active network architecture enabled via middleware 

      Cook, Carl (University of Canterbury. Computer Science, 2001)
      In conventional data communication networks, the basic network components are passive; routing decisions are made solely on the basis of packet header information. In contrast, active networks allow added computation within ...

    UC Research Repository
    University Library
    University of Canterbury
    Private Bag 4800
    Christchurch 8140

    Phone
    364 2987 ext 8718

    Email
    ucresearchrepository@canterbury.ac.nz

    Follow us
    FacebookTwitterYoutube

    © University of Canterbury Library
    Send Feedback | Contact Us