Subject: XBLOX vs. "CNets", lfsr dividers, etc.
Date: 28 Nov 1995 00:00:00 GMT
newsgroups: comp.arch.fpga,comp.lsi.cad

Perhaps this is of interest.  I have created an experimental set of C++
classes called "CNets" that let me specify structural (not behavioural)
designs which ultimately emit XNF primitives such as nets, gates, and
flipflops.  Using this specification language I can build up higher
level modules, the most sophisticated of which is a pipelined 32-bit
RISC processor plus on-chip peripherals such as boot ROM, UART, and
DRAM controller, in ~65% of a XC4010.

I use this approach in preference to both schematic capture and to
synthesis from HDLs.  It is more flexible, more powerful, and more
reusable than schematic capture and yet still allows me to precisely
and explicitly control primitive instantiation and placement, which can
be tricky using synthesis.  Not to mention this approach is much more
affordable than HDL synthesis.

(By the way, "CNets" does NOT deliver FPGA device independence, but it
could be adapted to that purpose.  I'm not convinced device
independence is such a panacea anyway -- for instance, either you
design to exploit distributed SRAMs and 3-state buses or you don't, and
if your current target device doesn't implement them you probably
should not require them.)


For instance, here is my universal linear feedback shift register
divider, which is known to work nicely for simple divisors like
n==(25000000/9600):

// emit an lfsr counter and decoder to divide by n
//
// See "Efficient Shift Registers, LFSR Counters, and
// Long Pseudo-Random Sequence Generators", Peter Alfke,
// Xilinx App Note, Aug. 1995
//
void lfsr_div(Net out, Net ce, Net reset, unsigned n) {
    ...
    // choose appropriate width counter
    static unsigned taps[32][4] = {
        { 0 }, { 0 }, { 0 }, { 3, 2 },
        { 4, 3 }, { 5, 3 }, { 6, 5 }, { 7, 6 },
        { 8, 6, 5, 4 }, { 9, 5 }, { 10, 7 }, { 11, 9 },
        { 12, 6, 4, 1 }, { 13, 4, 3, 1 }, { 14, 5, 3, 1 }, { 15, 14 },
        { 16, 15, 13, 4 }, { 17, 14 }, { 18, 11 }, { 19, 6, 2, 1 },
        { 20, 17 }, { 21, 19 }, { 22, 21 }, { 23, 18 },
        { 24, 23, 22, 17 }, { 25, 22 }, { 26, 6, 2, 1 }, { 27, 5, 2, 1
},
        { 28, 25 }, { 29, 27 }, { 30, 6, 4, 1, }, { 31, 28 }
    };
    check(n <= (1 << 30));
    for (unsigned bits = 1; n >= (1U << bits); bits++)
        ;
    check((1U << (bits-1)) <= n && n < (1U << bits));

    // determine bit pattern of terminal state (after n-1 clockings of lfsr)
    unsigned w = 0;
    for (unsigned i = 1; i < n; i++) {
        unsigned in = 0;
        for (unsigned j = 0; j < 4 && taps[bits][j]; j++)
            in ^= (w >> (taps[bits][j]) - 1) & 1;
        w = ((w << 1) & ((1 << bits) - 1)) ^ !in;
        check(w != 0);
    }

    // emit shift register and gates to recognize terminal state
    bus(lfsr, bits+1);
    out = lfsr(bits,1) == w;
    lfsr[0] = gnd;
    net(lfsr_in) = nomap(xnor(lfsr[taps[bits][0]], lfsr[taps[bits][1]],
                              lfsr[taps[bits][2]], lfsr[taps[bits][3]]));
    net(lfsr_reset) = out | reset;
    ff(lfsr[1], lfsr_in & ~lfsr_reset, ce);
    for (i = 2; i <= bits; i++)
        ff(lfsr[i], lfsr[i-1] & ~lfsr_reset, ce);
}


In case it's not perfectly obvious, :-), the last two groups of statements do
the following:

    bus(lfsr, bits+1);        -- declare lfsr to be a bus of bits+1 nets
    out = lfsr(bits,1) == w;  -- emit AND gate(s) to recognize the
                                  word 'w' in bits (bits..1) of bus lfsr
    lfsr[0] = gnd;            -- set lfsr[0] to gnd, necessary for the
                                  following XNOR to be correct when
                                  taps[i] is 0

    -- emit an XNOR of up to 4 inputs taking various taps from the lfsr
        shift register flipflop outputs.  'nomap' suppresses the default FMAP:
    net(lfsr_in) = nomap(xnor(lfsr[taps[bits][0]], lfsr[taps[bits][1]],
                              lfsr[taps[bits][2]], lfsr[taps[bits][3]]));

    -- set lfsr_reset to be the OR of out and reset signals:
    net(lfsr_reset) = out | reset;

    -- emit a flipflop driving lfsr[1] whose D is the AND of lfsr_in and
        NOT lfsr_reset and whose clock enable is 'ce':
    ff(lfsr[1], lfsr_in & ~lfsr_reset, ce);

    -- emit the rest of the flipflops, each of whose D input is the Q output of
        the previous 'flop, qualified by not reset, and whose clock enables
        are 'ce':
    for (i = 2; i <= bits; i++)
        ff(lfsr[i], lfsr[i-1] & ~lfsr_reset, ce);


Anyway, the salient ideas are:
* extend a real programming language with circuit specification datatypes
* employ structural specification, close to the FPGA primitive elements

Is anyone else using a similar approach?

Jan Gray

Copyright © 2000, Gray Research LLC. All rights reserved.
Last updated: Feb 03 2001