/*****************************************************************************/
/*
* 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
/*****************************************************************************/