Combinational logic synthesis based on the dual form of Reed-Muller representation.

Faraj, Khalid (2005) Combinational logic synthesis based on the dual form of Reed-Muller representation. PhD thesis, Edinburgh Napier University.

Available under License Creative Commons Attribution Non-commercial.

Download (3059kB) | Preview


    In certain applications, AND/XOR (Reed-Muller), and ORlXNOR (Dual
    form of Reed-Muller) logic have shown some attractive advantages over the
    standard Sum of Products (SOP) and Product of Sums (POS). Bidirectional
    conversion algorithms between SOP and AND/XOR also between POS and
    ORlXNOR based on Sparse and partitioning techniques are presented for multiple
    output Boolean functions. The developed programs are tested for some
    benchmarks with up to 20 inputs and 40 outputs.
    A new direct method is presented to calculate the coefficients of the Fixed
    Polarity Dual Reed-Muller (FPDRM) from the truth vector of the POS. Any
    Boolean function can be expressed by FPDRM forms. There are 211 polarities for
    an n-variable function and the number of sum terms depends on these polarities.
    Finding the best polarity is costly interims of CPU time, in order to search for the
    best polarity which will lead to the minimum number of sums for a particular
    function. Therefore, an algorithm is developed to compute all the coefficients of
    the Fixed Polarity Dual Reed-Muller (FPDRM) with polarity p from any polarity q.
    This technique is used to find the best polarity of FPDRM among the 211 fixed
    polarities. The algorithm is based on the Dual- polarity property and the Gray code
    strategy. Therefore, there is no need to start from POS form to find FPDRM
    coefficients for all the polarities. The proposed methods are efficient in terms of
    memory size and CPU time. A fast algorithm is developed and implemented in C
    language which can convert between POSs and FPDRMs. The program was tested
    for up to 23 variables. A modified version of the same program was used to find
    the best polarity. For up to 13 variables the CPU time was less than 42 seconds.
    To search for the optimal polarity for large number of variables and to
    reduce the se arch time 0 ffinding the 0 ptimal polarity 0 fthe function, two new
    algorithms are developed and presented in this thesis. The first one is used to
    convert between P OS and Positive Polarity Dual Reed-Muller (PPDRM) forms.
    The second algorithm will find the optimal fixed polarity for the FPDRM among
    the 211 different polarities for large n-variable functions. The most popular
    minimization criterion of the FPDRM form is obtained by the exhaustive search of
    the entire polarity vector. A non-exhaustive method for FPDRM expansions is
    presented. The new algorithms are based on separation of the truth vector (T) of
    POSs around each variable Xi into two groups. Instead of generating all of the
    polarity sets and searching for the best polarity, this algorithm will find the optimal
    polarity using the separation and sparse techniques, which will lead to optimal
    polarity. Time efficiency and computing speed are thus achieved in this technique.
    The algorithms don't require a large size of memory and don't require a long CPU
    time. The two algorithms are implemented in C language and tested for some
    benchmark. The proposed methods are fast and efficient as shown in the
    experimental results and can be used for large number of variables.

    Item Type: Thesis (PhD)
    Uncontrolled Keywords: AND/XOR (Reed-Muller), ORlXNOR (Dual form of Reed-Muller); Fixed Polarity Dual Reed-Muller (FPDRM); polarity; algorithms;
    University Divisions/Research Centres: Faculty of Engineering, Computing and Creative Industries > School of Engineering and the Built Environment
    Dewey Decimal Subjects: 600 Technology > 620 Engineering > 621 Electronic & mechanical engineering > 621.3 Electrical & electronic engineering
    Library of Congress Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering
    Item ID: 4339
    Depositing User: Mrs Lyn Gibson
    Date Deposited: 15 Apr 2011 14:29
    Last Modified: 23 Apr 2012 12:51

    Actions (login required)

    View Item

    Document Downloads

    More statistics for this item...

    Edinburgh Napier University is a registered Scottish charity. Registration number SC018373