/*****************************************************************************/

/*
 * TOGGLE.V (Toggle Register Operations)
 *
 * Copyright (c) 2004-2007 by Wayne Stahnke
 * All Rights Reserved
 */

/*****************************************************************************/

/*
 * References:
 *
 * (1) "On the Toggle Register Polynomial," by Wayne Stahnke.  Information
 *     and Control, Vol. 39, pp. 149-157 (1978).
 *
 * (2) "Algebraic Theory of Flip-Flop Sequence Generators," by W. O. Alltop,
 *     A. V. Pratt, and R. C. Burton.  Information and Control, Vol. 12,
 *     pp. 193-205 (1968).
 *
 * (3) "Algebraic Coding Theory," Elwyn R. Berlekamp (1968).  McGraw-Hill,
 *     San Francisco, CA.
 *
 * (4) "Error-Correcting Codes," W. Wesley Peterson and E. J. Weldon, Jr.
 *     Second edition (1972).  The MIT Press, Cambridge, MA.
 *
 * (5) "Linear Sequential Switching Circuits," William H. Kautz, editor
 *     (1965).  Holden-Day, San Francisco, CA.
 *
 * (6) "Linear Sequential Circuits," Arthur Gill (1967).  McGraw-Hill, San
 *     Francisco, CA.
 */

/*****************************************************************************/

/* Finite state machine */

module fsm11 (eoi, state, vector, load, enable, clock);
    output  eoi; /* end of interval */
    output  [10:0] state; /* current state */
    input   [10:0] vector; /* restart vector */
    input   load; /* load restart vector above */
    input   enable; /* enable operation */
    input   clock; /* system clock */

/* Local variables */
    wire    eoi; /* end of interval */
    reg     [10:0] state; /* finite state machine */
    wire    [10:0] bump; /* next state of state machine above */
    reg     [10:0] next_restart; /* upcoming restart vector */
    reg     [10:0] restart; /* current restart vector */

/*
 * The finite state machine is an 11-bit toggle register consisting of two
 * trigger flipflops and 9 delay flipflops connected in a loop, creating a
 * cycle of all 2047 non-zero states.  The remaining state is included in
 * this cycle by modifying the logic to cause a transition into, and then
 * immediately out of, the all-zero state.
 *
 * For a discussion of the theory underlying toggle register polynomials
 * in general, and a justification of the choice of polynomial used here,
 * see Reference (1).
 */

    assign bump =
      {(~|state[10:1] ^ /* include all-zero state */
      (state[0] ^ state[10])), /* 1 trigger flipflop */
      (state[10] ^ state[9]), /* 1 trigger flipflop */
      state[9:1]}; /* 9 delay flipflops */

/*
 * We must double buffer the restart vector to ensure that each cycle length
 * is a desired length.  To see this, consider the case that obtains without
 * double buffering when the cycle is to be shortened: if the toggle register
 * state is beyond the upcoming restart vector but has not yet arrived at the
 * current restart vector, the resulting cycle length will be greater than
 * either one of the desired lengths.  Double buffering solves this problem.
 */

    always @(posedge clock) begin
        if (~enable)
            next_restart <= 0;
        else if (load)
            next_restart <= vector;
        else
            next_restart <= next_restart;
    end

/*
 * We prefer to start with the all-zero state for simplicity, which requires
 * detecting the restart condition one state earlier than would otherwise be
 * the case.  We achieve this by comparing the restart vector with the next
 * state, rather than with the current state.
 */

    assign eoi = (restart == bump); /* end of interval */

    always @(posedge clock) begin
        if (~enable) begin /* initialize */
            state <= 0;
            restart <= 0;
        end

        else if (eoi) begin /* end of interval */
            state <= 0;
            restart <= next_restart;
        end

        else begin /* advance */
            state <= bump;
            restart <= restart;
        end
    end
endmodule

/*****************************************************************************/

/* Map length into vector */

`define TELESCOPE /* RESIDUE/TELESCOPE selects mapping method */

`ifdef RESIDUE
/*
 * Given a desired length l we form the "exponent" e = (2047 - l) from the
 * length by taking its one's complement.  We then determine the residue of
 * x^e modulo g(x) = x^11 + x^2 + 1 and map it into the vector required for
 * operation.  The mapping is as follows:
 *
 *     Length  |  Exponent  |  Residue      |  Vector
 *     --------+------------+---------------+-------------
 *          0  |      2047  |  00000000001  |  00000000000
 *          1  |      2046  |  10000000010  |  10000000000
 *          2  |      2045  |  01000000001  |  11000000000
 *          3  |      2044  |  10100000010  |  10100000000
 *          4  |      2043  |  01010000001  |  11010000000
 *          5  |      2042  |  10101000010  |  10101000000
 *          6  |      2041  |  01010100001  |  11010100000
 *          7  |      2040  |  10101010010  |  10101010000
 *          8  |      2039  |  01010101001  |  11010101000
 *          9  |      2038  |  10101010110  |  10101010100
 *         10  |      2037  |  01010101011  |  11010101010
 *         11  |      2036  |  10101010111  |  10101010101
 *         12  |      2035  |  11010101001  |  01010101010
 *         13  |      2034  |  11101010110  |  01101010101
 *         14  |      2033  |  01110101011  |  11110101010
 *         15  |      2032  |  10111010111  |  10111010101
 *       ....  |      ....  |  ...........  |  ...........
 *       2032  |        15  |  00001010000  |  00001010000
 *       2033  |        14  |  00000101000  |  00000101000
 *       2034  |        13  |  00000010100  |  00000010100
 *       2035  |        12  |  00000001010  |  00000001010
 *       2036  |        11  |  00000000101  |  00000000101
 *       2037  |        10  |  10000000000  |  10000000010
 *       2038  |         9  |  01000000000  |  11000000001
 *       2039  |         8  |  00100000000  |  00100000000
 *       2040  |         7  |  00010000000  |  00010000000
 *       2041  |         6  |  00001000000  |  00001000000
 *       2042  |         5  |  00000100000  |  00000100000
 *       2043  |         4  |  00000010000  |  00000010000
 *       2044  |         3  |  00000001000  |  00000001000
 *       2045  |         2  |  00000000100  |  00000000100
 *       2046  |         1  |  00000000010  |  00000000010
 *       2047  |         0  |  00000000001  |  00000000001
 *
 * Note that the first entry in this table, for which a length of zero is
 * mapped into the null vector, cannot be found directly from the residue
 * because x^2047 = x^0 = 1.  We therefore manage this case using special
 * means, indicated in the comments below.
 */

module map11 (busy, vector, length, load, clock);
    output  busy; /* operation under way */
    output  [10:0] vector; /* outgoing vector */
    input   [10:0] length; /* incoming length */
    input   load; /* load incoming length above */
    input   clock; /* system clock */

/* Local variables */
    reg     [10:0] exponent; /* rotated exponent */
    reg     [10:0] residue; /* running residue */
    wire    [10:0] square; /* square residue above */
    wire    [10:0] square_bump; /* square residue and multiply by x */

    reg     [3:0] bit_count; /* bit count with x^4 + x + 1 */
    wire    busy = |bit_count; /* operation under way */

/*
 * Let s denote the residue class containing x, where the residue is formed
 * modulo g(x), an irreducible polynomial.  Then s^2 represents the residue
 * class containing x^2, and in general, if r(x) is any polynomial, then r(s)
 * represents the residue class containing r(x).
 *
 * We determine s^e modulo g(x) by starting with s^0 = 1.  For each bit in
 * the length we first double the exponent of s (by squaring the residue)
 * and if the bit is a 1 we also increment it (by multiplying the squared
 * residue by s).  We call this latter operation "bumping" the residue.
 *
 * The best way to show this procedure is by example.  If the desired length
 * is 1196 the final exponent of s is (2047 - 1196) = 851 = 11'b01101010011.
 * We initialize the residue to 00000000001.  We then proceed as follows:
 *
 *     Bit  |  Operation      |  Residue      |  Residue Class
 *     -----+-----------------+---------------+---------------
 *     0    |  square         |  00000000001  |  s^0
 *     1    |  square & bump  |  00000000010  |  s^1
 *     1    |  square & bump  |  00000001000  |  s^3
 *     0    |  square         |  00001000000  |  s^6
 *     1    |  square & bump  |  00000010100  |  s^13
 *     0    |  square         |  00100010000  |  s^26
 *     1    |  square & bump  |  01101000000  |  s^53
 *     0    |  square         |  01000101010  |  s^106
 *     0    |  square         |  11011000100  |  s^212
 *     1    |  square & bump  |  00101101110  |  s^425
 *     1    |  square & bump  |  00111111001  |  s^851
 */

/*
 * Squaring is a linear operation in a field that includes the binary field
 * because (a + b)^2 = a^2 + b^2, which allows us to square the residue in a
 * single operation, as presented in Reference (3), pp. 50-51. Squaring the
 * residue effectively doubles the running exponent.
 */

    assign square = /* square residue */
      {residue[5],
      (residue[9] ^ residue[10]),
      residue[4],
      (residue[8] ^ residue[9]),
      residue[3],
      (residue[7] ^ residue[8]),
      residue[2],
      (residue[6] ^ residue[7]),
      (residue[1] ^ residue[10]),
      residue[6],
      (residue[0] ^ residue[10])};

/*
 * As with squaring, multiplying by x is a linear operation.  Thus we can
 * square and multiply by x in a single operation that effectively doubles
 * and increments the running exponent.
 */

    assign square_bump = /* square residue and multiply by x */
      {square[9],
      square[8],
      square[7],
      square[6],
      square[5],
      square[4],
      square[3],
      square[2],
      (square[1] ^ square[10]),
      square[0],
      square[10]};

/* Determine residue of x^e modulo g(x) = x^11 + x^2 + 1 */
    always @(posedge clock) begin
        if (load) begin /* initiate operation */
            exponent <= ~length; /* exponent = (2047 - length) */
            residue <= 11'b00000000001;
            bit_count <= 4'b1100; /* state 11 */
        end

        else if (busy) begin /* square (and possibly multiply by x) */
            exponent <= {exponent[9:0], exponent[10]}; /* rotate left */
            residue <= (exponent[10]) ? square_bump : square;
            bit_count <= {((bit_count[1] ^ bit_count[0]) & |bit_count[3:1]),
              bit_count[3:1]};
        end

        else begin /* done */
            exponent <= exponent;
            residue <= residue;
            bit_count <= {((bit_count[1] ^ bit_count[0]) & |bit_count[3:1]),
              bit_count[3:1]}; /* or "bit_count <= 0;" */
        end
    end

/* Map residue into vector */
    assign vector =
      {(residue[10] ^ residue[9]),
      residue[9],
      residue[8],
      residue[7],
      residue[6],
      residue[5],
      residue[4],
      residue[3],
      residue[2],
      (residue[10] ^ residue[1]),
      ((residue[9] ^ residue[0]) ^
        &exponent)}; /* null vector "special means" */
endmodule
`endif

`ifdef TELESCOPE
/*
 * There is no requirement to maintain the residue.  We can operate directly
 * on the vector at each step by mapping the vector to the residue, squaring
 * and possibly multiplying by x, and mapping back.  The operations required
 * to do this are readily telescoped, yielding a simple realization.
 *
 * We can simplify the logic further by combining the load operation with
 * the first "square" or "square and advance" operation.  We can also use
 * the vacated positions of the shifted exponent to signal that the mapping
 * operation is done, eliminating the need for a separate bit counter.
 *
 * These simplifications are embodied in the logic given here, resulting in
 * a particularly simple and attractive realization.
 */  

module map11 (busy, vector, length, load, clock);
    output  busy; /* operation under way */
    output  [10:0] vector; /* outgoing vector */
    input   [10:0] length; /* incoming length */
    input   load; /* load incoming length above */
    input   clock; /* system clock */

/* Local variables */
    reg     [10:0] exponent; /* shifted exponent and bit counter */
    wire    busy = |exponent[9:0]; /* operation under way */
    reg     [10:0] vector; /* outgoing vector */
    wire    [10:0] square; /* square vector above */
    wire    [10:0] square_bump; /* square vector and advance */

    assign square = /* square vector */
      {(vector[5] ^ vector[10]),
      vector[10],
      vector[4],
      (vector[8] ^ vector[9]),
      vector[3],
      (vector[7] ^ vector[8]),
      vector[2],
      (vector[6] ^ vector[7]),
      vector[1],
      (vector[5] ^ vector[6]),
      vector[0]};

    assign square_bump = /* square vector and advance */
      {(vector[4] ^ vector[10]),
      vector[4],
      (vector[8] ^ vector[9]),
      vector[3],
      (vector[7] ^ vector[8]),
      vector[2],
      (vector[6] ^ vector[7]),
      vector[1],
      (vector[5] ^ vector[6]),
      vector[0],
      (vector[4] ^ vector[5])};

/* Determine vector */
    always @(posedge clock) begin
        if (load) begin /* initiate operation */
            exponent <= {~length[9:0], 1'b1};
            vector <= (|length) ?
              {9'b0, ~length[10], length[10]} : /* nonzero length */
              11'b0; /* null vector "special means" */
        end

        else if (busy) begin /* square (and possibly advance) */
            exponent <= (exponent << 1);
            vector <= (exponent[10]) ? square_bump : square;
        end

        else begin /* done */
            exponent <= (exponent << 1); /* or "exponent <= 0;" */
            vector <= vector;
        end
    end
endmodule
`endif

/*****************************************************************************/