US 4,032,764 AGrant
Means and Method for Generating Permutations of a Square
Issue Date:1977-06-28
•2 Claims
•4 Drawing Sheets
Abstract
A means and method for generating random permutations on a square having k.sup.2 subsquares based upon a circuitry including a maximal-length sequence generator.
Metadata
Inventor
- John E. Savage
Application Information
Application Number:US 6368107
Filing Date:1975-12-01
Priority Date:1975-12-01
Art Unit:236
Classifications
IPC:
G06F 102G07C 1500
Field of Search:
235273331328340152138 A;1397859323 R
Patent Drawings (4 sheets)
Description
BACKGROUND OF THE INVENTION
For many applications, including the generation of random number tables for games of chance, it is desirable to have ready availability of random permutations on a square. While this can be done in a completely manual fashion, where large numbers of such game cards are required, the obtaining of data by wholly mental steps is time consuming and fraught with the possibility of error. Random number generators are known in the art, but most simple random number generators have no means for preventing duplication of previously obtained numbers over a given number of cycles.
SUMMARY OF THE INVENTION
Briefly stated, the invention contemplates the utilization of a type of linear feedback shift-register known as a "maximal-length sequence generator" in combination with other circuitry to obtain integers within a desired value range with the assurance that duplication is avoided over a given number of cycles.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a schematic representation of a known linear feedback shift-register.
FIG. 2 is a schematic view of a known maximal-length feedback shift-register.
FIG. 3 is a schematic view of a typical square having a given number of subsquares to be randomly numbered.
FIG. 4 is a block diagram of an embodiment of the invention.
FIG. 5 is a generalized block diagram of a basic permutation generator forming a part of the embodiment.
FIG. 6 is a block diagram of a portion of a circuit comprising a part of the embodiment.
FIG. 7 is a block diagram showing a remaining portion of a circuit comprising a part of the embodiment.
DISCUSSION OF APPLICABLE MATHEMATICAL THEORY
Before entering into a detailed consideration of the disclosed embodiments of the invention, a discussion of the mathematical theory involved is considered apposite.
Consider a binary linear feedback shift-register (LFSR) shown in FIG. 1. Here h.sub.n.sub.-1, h.sub.n.sub.-2, . . . , h.sub.o are 0 or 1. The contents of all cells are 0 or 1 and those for which h.sub.i = 1 are added modulo-2 and the sum is used to replace the contents of cell c.sub.n.sub.-1 after a shift right which replaces c.sub.i with c.sub.i.sub.-1 for 0.ltoreq. i.ltoreq. n- 2.
We associate with the shift-register the characteristic polynomial h(x)= x.sup.n +h.sub.n-1 x.sup.n.sup.-1 + h.sub.n.sub.-2 x.sup.n.sup.-2 + . . . + h.sub.1 x+h.sub.o. There are special such polynomials which are known as "primitive polynomials." These are the minimal polynomials of primitive elements of a Galois field of size 2.sup.n. When such polynomials are used to define a shift-register, the register has the property that when initialized with any binary n-tuple (its state) other than 0 it will cycle through 2.sup.n -1 different states before returning to the original n-tuple. Such registers are called "maximal length sequence generators" and are well known in the art. The register shown in FIG. 2 is of this type and will cycle through 2.sup.7 -1= 127 different, non-zero states before repeating a state. It has h(x)= x.sup.7 +x.sup.3 +1.
Permutations of a Square
Consider a square which is divided into k.sup.2 subsquares as shown in FIG. 3. The rows and columns are numbered as shown, and a square in the i th row and j th column are identified by the pair (i,j). The k.sup.2 squares can be ordered by rows, columns, diagonally and many other ways. Ordered by rows they are (1, 1), (1, 2), . . . , (1, k), (2, 1), . . . , (2, k), . . . (k, 1), . . . , (k, k). By columns they are (1, 1), (2, 1), . . . , (k, 1), (1, 2), (2, 2), . . . , (k, 2), . . . , (k, k). Other orderings can be obtained by reversing the order of rows, of columns or both. In a diagonal ordering, the squares are ordered from left to right on consecutive diagonals starting from (1, 1), that is, (1, 1), (2, 1), (1, 2), (3, 1), (2, 2), . . . , (k, k).
A Procedure for Generation of "Random" Permutations of a Square
There follows a procedure for generating a permutation of the pairs (i, j), where both i and j are greater than or equal to 1. The procedure is given for 1 is less than or equal to k which is less than or equal to 9 but can be generalized to any value of k.
1. Choose a value of n greater than or equal to 7.
2. Choose a primitive binary polynominal h(x) of degree N-1.
3. construct an n-stage LFSR with characteristic polynomial h(x).
4. Choose an initial state for the shift-register. (This is easily done with n switches.)
5. Choose a set of 7 stages from the n stage register and associate the numbers 1, 2, 4, 8, 16, 32, 64 in some order with these stages.
6. Beginning with the initial state, cycle until a state is found which has 0's in every position (if any) except the 7 chosen positions. Call such a state a satisfiable state. [A satisfiable state is represented by the integer obtained by adding the powers of 2 for those stages containing 1. For example, if in FIG. 2 we associate 1 with the rightmost stage, 2 with the next and 64 with the leftmost and the shift-register contains 1100010, then this state is represented by the integer 98.]
7. A satisfiable state is tested to determine whether its representing integer is a two digit decimal number of the form ij where i and j are both greater than or equal to 1 and less than or equal to k. Such states are called acceptable states.
8. Steps 6. and 7. are repeated until k.sup.2 acceptable states are found.
The decimal numbers associated with the k.sup.2 acceptable states generated by this procedure are distinct and represent a permutation of the pairs in (i, j) where both i and j are greater than or equal to 1 and less than or equal to k.
By the choice of the minimal polynomial, the state of the LFSR runs through all non-zero binary n-tuples before repeating. It therefore runs through all non-zero tuples with 0 in all but the 7 chosen positions and in these positions it runs through all 2.sup.7 - 1= 127 different non-zero patterns of seven digits. The assigning of powers of two to these positions generates integers which range from 1 to 127. Therefore, all pairs of non-zero decimal digits are generated. The selection procedure chooses just those pairs which correspond to pairs in (i, j) where both i and j are greater than or equal to 1 and less than or equal to k.
To generate a permutation of the k.times. k square
(a) order the k.sup.2 subsquares of the square by rows, or by columns (and by inverting the order on rows or columns or both) or diagonally.
(b) in such an ordering, assign to each subsquare a pair of digits produced by the above procedure in the order in which they are produced.
As an example, consider the maximal length linear feedback shift-register shown in FIG. 2. Here
(a) n= 7
(b) h(x)= x.sup.7 +x.sup.3 +1
Also, assign the powers of 2 in order from right to left so that the rightmost cell is assigned 2.sup.o = 1 and the leftmost is assigned 2.sup.6 = 64. Initialize the shift-register with 1100010. The first pair of decimal digits produced is 98 and the last before repeating is 69. When k= 9 and the subsquares are ordered according to rows, the resulting permutation is one which can be employed with a Bingo-type playing card or similar device.
DETAILED DESCRIPTION OF THE DISCLOSED EMBODIMENT
FIG. 5 depicts the basic generator of permutations. The basic generator is a linear sequential filter with a plurality of feedback paths between selected time-spaced taps thereon and its input. The input is the modulo-2 sum of the feedback components.
The basic generator comprises a plurality of N stages of delay represented here by a shift-register 11 with N stages SR-0 through SR-(N-1), a plurality of N parallel inputs 12 and a serial input 13. It has a plurality of N parallel outputs 14 and a control input 15, which, when 0, permits the parallel transfer of the N parallel inputs to the N stages and which, when 1, permits transfer of the serial input 13 into stage SR-(N-1). These transfers occur when the clock input 16 makes a transition from 0 to 1. The basic shift-register can be assembled from 4-bit parallel-access shift-registers which are commercially available. The filter also contains N multipliers 17 with factors c.sub.O through c.sub.N.sub.-1 at taps on register 11, and a plurality of modulo-2 adders 18 connected in tandem between multipliers 17 and the serial input 13.
The basic generator of FIG. 5 has been analyzed in terms of the number of stages N and the multiplicative factors c.sub.O through c.sub.N.sub.-1. A tap polynomial h(x) may be written as
in equation 1 the powers of x identify the taps from the input of stage SR-(N-1) to the output of stage SR-0. The serial input corresponds to the coefficient of x.sup.N which is 1. At all other taps, the c.sub.j coefficients are chosen from 0 or 1, to make the polynomial in Equation 1 primitive over the field of two elements. A polynomial is primitive if it is irreducible, i.e. has no factors but itself and 1, and divides x.sup.m +1 for m=2.sup.n -1 but for no smaller m. Tables of primitive polynomial coefficients are known in the art, and may be generated by known computer techniques. (See footnote 1)
Basic generators of N stages have the following property that when initialized with a non-zero state (x.sub. N.sub.-1, x.sub.N.sub.-2, . . . , x.sub.0) and when the state is advanced by pulsing the clock input 16 exactly 2.sup.N -1 advances are necessary to return the state to the initial state. Furthermore, all of the possible non-zero states will appear before the initial state is encountered. If the initial state is the zero state (0,0, . . . ,0), the basic generator remains in the state after each pulsing of the clock input.
There are eighteen choices of coefficients that will render a seventh-degree polynomial h(x) primitive. A choice with the minimum number of coefficients is
Equation 2 defines a basic generator with seven stages SR-0 through SR-6, a modulo-2 adder 18 having inputs from stages SR-0 and SR-3 through multipliers of unity gain at c.sub.0 and c.sub.3 and an output connected to the serial input 13, (see FIG. 2).
FIG. 4 depicts the generator for permutations of the square. A set of seven stages on the basic generator 19 is chosen in some order and the outputs 20 are applied as input to 21 which is a circuit which decodes the seven digit binary number into a three digit decimal number. The three digit decimal number 22 is represented as three numbers in binary-coded decimal (BCD). These numbers in BCD are (d.sub.03,d.sub.02,d.sub.01,d.sub. 00), (d.sub.13,d.sub. 12,d.sub.11,d.sub.10) and (d.sub.20) and are the coefficients of 1, 10 and 100 respectively, in the decimal representation of the binary number (y.sub.6,y.sub.5,y.sub.4,y.sub.3,y.sub.2,y.sub.1,y.sub.0). The first two BCD numbers 22 are supplied as input to standard BCD to decimal decoders 23 each of which has ten outputs labeled 0, 1, 2, . . . , 9. Exactly one output of each BCD to decimal decoder 23 is 1 on a given input and the remaining outputs are 0.
Four OR circuits 24 are depicted in FIG. 5 and each forms the logical OR of all its inputs. One OR 24 has as inputs those parallel outputs 25 of the basic generator which are not used as inputs to the decoder 21, (if the number of stages N=7, there are no outputs 25) and the BCD number d.sub.20 in 22 which is the coefficients of 100 in the decimal expansion of the binary number (y.sub. 6,y.sub.5,y.sub.4,y.sub.3,y.sub.2,y.sub.1 ,y.sub.0). The outputs of three OR's are combined in the fourth OR whose output 26 is 0 only when all inputs to all OR's are 0. This occurs exactly when
the BCD numbers (d.sub. 13,d.sub.12,d.sub.11,d.sub.10) and (d.sub. 03,d.sub.02,d.sub.01,d.sub.00) lie between one and k (k.ltoreq. 9) and
the BCD number d.sub.20 is 0 and
the N- 7 outputs 25 are exactly 0.
One consequence of these conditions is that the decimal number representing the binary number (y.sub. 6,y.sub.5,y.sub.4,y.sub.3,y.sub.2,y.sub.1,y.sub.0) is a pair i,j where i and j lie between 1 and k and where the number has value i.multidot.10+ j.
The output 26 is complemented by the inverter 27 and supplied as input to the AND gates 28 and to the output 29. Only one output in each group of outputs 30 and 31 is 1 and this occurs when the corresponding output of the BCD to decimal decoder 23 is 1 and the above stated conditions apply. When an output in 30 and 31 is 1, it denotes an integer r between 1 and k where k.ltoreq. 9.
By the property cited above for the basic generator, the permutation generator of FIG. 4 will produce outputs at 30 and 31 which denote integers i and j, respectively, and all possible pairs (i,j) where i and j lie between 1 and k, will be produced by advancing the clock at most 2.sup.N -1 times. Each time that such a pair is produced, the output 29 has value 1. The outputs at 29, 30 and 31 can be used to drive some form of display or recording device, (not shown).
FIG. 6 depicts a circuit which produces the BCD number (d.sub. 03,d.sub.02,d.sub.01,d.sub.00) mentioned above and a pair of digits (q.sub. 1,q.sub.0) which are used to produce the two remaining BCD numbers. The number P associated with the binary number (y.sub. 6,y.sub.5,y.sub.4,y.sub.3,y.sub.2,y.sub.1,y.sub.0) is given by
Equation 3 shows P as a sum of those decimal numbers whose multipliers Y.sub.j are 1. The "units" of the number P are the "units" of the number Q given by
this number is obtained by representing 1,2,4,6,8, in BCD and forming the sum of the following binary numbers
the sum of the first two binary numbers in Equation 5 is (0,Y.sub.6,Y.sub.5,0).
The circuit of FIG. 6 contains 12 full adders 32. A combination of five full adders in 33 forms the binary sum of the three binary numbers (0,Y.sub.6,Y.sub.5,0), (0,Y.sub.4,Y.sub.4,0) and (y.sub. 3,Y.sub.2,Y.sub.1,Y.sub.0). The result of the sum 34 (Q of Equation 4) is supplied to the adder chains 35 and 36. In 35 the decimal number 10 is substracted from the sum 34 by adding the two's complement of (0,1,0,1,0), namely (1,0,1,1,0). The overflow signal e.sub.1 is 1 only if Q is 10 or larger and if Q is less than 20, 35 yields the BCD representation 37 of the "units" of Q. In 36 the decimal number 20 is subtracted by adding the two's complement of (1,0,1,0,0), namely (0,1,1,0,0). The overflow signal e.sub.2 is 1 only if Q is 20 or larger and in this case 36 yields as output the BCD representation 38 of the "units" of Q.
The AND gates 39 are used to select the "units" of Q. When e.sub.1 is 0 and the output of the inverter 40 is 1, the output of 33 is chosen. In this case Q is less than 10. The output of 35 is chosen if e.sub.1 is 1 and e.sub.2 is 0, that is, the output of 41 is 1. In this case Q is between 10 and 19. Also, the output of 36 is chosen when e.sub.2 is 1. In this case, Q is 20 or greater. The OR gates 42 combine the outputs from the AND's 39.
The pair (q.sub.1 ,q.sub.0) represents in binary the number of "tens" in Q.
The number of "tens" in P is the number of "tens" in Q plus the number in y.sub.6 .multidot.6, y.sub.5 .multidot. 3, y.sub.4 .multidot. 1 which are the "tens" of the integers y.sub.6 .multidot. 64, y.sub.5 .multidot. 32, and y.sub.4 .multidot. 16. In binary these numbers are
Thus, the numbers of "tens" in P is the sum of these four binary numbers which is equivalent to the sum of the following three binary numbers
FIG. 7 depicts a circuit for computing the number of "tens" and hundreds in P. Eight full adders 43 are used. In 44 the sum of the three binary numbers in Equation 7 is formed. The result 45 is then supplied to an adder 46 that subtracts the decimal number 10 by adding the two's complement of (1,0,1,0), namely, (0,1,1,0). The result 47 is the "tens" of P if e.sub.3 is 1, that is, if the sum 45 is greater than or equal to 10. Otherwise, that is, when e.sub.3 is 0, the "tens" of P is 45. If e.sub.3 is 1, P is greater than or equal to 100. Therefore, d.sub.20 is equal to e.sub.3.
The AND gates 48 select the result 45 if e.sub.3 is 0, in which case the output of the inverter 49 is 1, and the result 47 is selected if e.sub.3 is 1. The OR gates 50 combine the results.
The values of (i,j) are random and non-repetitive for the pre-determined given number of cycles, and may be used to number the squares k.sup.2 in any order desired.
I wish it to be understood that I do not consider the invention limited to the precise details of structure shown and set forth in this specification, for obvious modifications will occur to those skilled in the art to which the invention pertains.
Claims
I claim:
1. A device for generating permutations of a square having k.sup.2 subsquares by generating values of the pairs (i,j) where both i and j are greater than or equal to 1 and equal to or less than k, comprising: a basic generator including a maximal length shift-register having a series of inputs corresponding to the characteristic polynomial h(x)= x.sup.n +h.sub.n.sub.-1 x.sup.n.sup.-2 + h.sub.n.sub.-2 x.sup.n.sup.-2 + . . . + h.sub.1 x+ h.sub.0, said register having the properties that when initialized with any binary n-tuple other than 0 it will cycle through 2.sup.n -1 different states before returning to said n-tuple; a binary to decimal decoder having at least a 7 digit binary input recieivng the output of said maximal length shift-register, and at least a 3 digit decimal output in binary coded decimal form; first and second binary coded decimal to decimal decoders receiving the output of 2 of said 3 digit output, a first OR gate receiving the output of the remaining third and other of said at least 3 digit output; and second and third OR gates receiving the outputs, respectively, from said first and second binary coded decimal to decimal decoders, a fourth OR gate receiving the output of said first, second and third OR gates such that the output of the same is zero only when all inputs to said second and third OR gates are zero; and a plurality of AND gates sensing the output of said fourth OR gate and outputs of both of said first and second binary to decimal decoders; said AND gates having a 1 output denoting an integer between 1 and k.
2. A method of obtaining random permutations of a square which is divided into k.sup.2 subsquares in which the rows and columns identify a square in the i th row and j th column by the pairs i,j, comprising the steps of: 1. Selecting a value of n equal to or greater than the number of subsquares; 2. Selecting a primitive binary polynomial h(x) of degree n; 3. Providing an n-stage linear feedback shift-register with characteristic polynomial h(x); 4. Selecting an initial state for the shift-register; 5. Selecting a set of r stages from said n stage register and associating the numbers 1, 2, 4, 8, 16, 32, 64 . . . in a given order with these stages, r.ltoreq.7; 6. Beginning with the initial state, cycling said register until a state is found which has 0's in every position except the chosen r stages, in which said state is represented by the integer obtained by adding the powers of 2 for those stages containing 1; 7. Testing said state to determine whether its representing integer is a 2 digit decimal number of the form i,j where both i and j are greater than or equal to 1 and less than or equal to k; 8. Repeating steps 6 and 7 until k.sup.2 representing integers are found.
Patent Citations (4)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US3171082 | 1965-02-01 | Dillard et al. | |
| US3653026 | 1972-03-01 | Hurly | |
| US3761696 | 1973-09-01 | Russell | |
| US3895807 | 1975-07-01 | Friedman |